Sort of garbage collection commit. :-| Many things are still

broken. API has changed a lot and it will still change a
little more here and there. The command line tool doesn't
have all the required changes to reflect the API changes, so
it's easy to get "internal error" or trigger assertions.

8 files changed, 272 insertions, 303 deletions

diff --git a/src/liblzma/rangecoder/Makefile.am b/src/liblzma/rangecoder/Makefile.am
index 6e80f8d7..f6824292 100644
--- a/src/liblzma/rangecoder/Makefile.am
+++ b/src/liblzma/rangecoder/Makefile.am
@@ -12,7 +12,7 @@
 ##  Lesser General Public License for more details.
 ##
 
-EXTRA_DIST = price_table_gen.c
+EXTRA_DIST = price_tablegen.c
 
 noinst_LTLIBRARIES = librangecoder.la
 
@@ -21,8 +21,10 @@ librangecoder_la_CPPFLAGS = \
 	-I@top_srcdir@/src/liblzma/api \
 	-I@top_srcdir@/src/liblzma/common
 
-if COND_MAIN_ENCODER
-librangecoder_la_SOURCES += range_encoder.h
+if COND_ENCODER_LZMA
+librangecoder_la_SOURCES += \
+	range_encoder.h \
+	price.h
 if COND_SMALL
 librangecoder_la_SOURCES += price_table_init.c
 else
@@ -30,6 +32,6 @@ librangecoder_la_SOURCES += price_table.c
 endif
 endif
 
-if COND_MAIN_DECODER
+if COND_DECODER_LZMA
 librangecoder_la_SOURCES += range_decoder.h
 endif
diff --git a/src/liblzma/rangecoder/price.h b/src/liblzma/rangecoder/price.h
new file mode 100644
index 00000000..001f753d
--- /dev/null
+++ b/src/liblzma/rangecoder/price.h
@@ -0,0 +1,111 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       price.h
+/// \brief      Probability price calculation
+//
+//  Copyright (C) 1999-2008 Igor Pavlov
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_PRICE_H
+#define LZMA_PRICE_H
+
+
+#define RC_MOVE_REDUCING_BITS 4
+#define RC_BIT_PRICE_SHIFT_BITS 4
+#define RC_PRICE_TABLE_SIZE (RC_BIT_MODEL_TOTAL >> RC_MOVE_REDUCING_BITS)
+
+#define RC_INFINITY_PRICE (UINT32_C(1) << 30)
+
+
+#if !defined(LZMA_RANGE_ENCODER_H) || defined(HAVE_SMALL)
+/// Probability prices used by *_get_price() macros. This is initialized
+/// by lzma_rc_init() and is not modified later.
+extern uint32_t lzma_rc_prices[RC_PRICE_TABLE_SIZE];
+
+/// Initializes lzma_rc_prices[]. This needs to be called only once.
+extern void lzma_rc_init(void);
+
+#else
+// Not building a size optimized version, so we use a precomputed
+// constant table.
+extern const uint32_t lzma_rc_prices[RC_PRICE_TABLE_SIZE];
+
+#endif
+
+
+static inline uint32_t
+rc_bit_price(const probability prob, const uint32_t bit)
+{
+	return lzma_rc_prices[(prob ^ ((UINT32_C(0) - bit)
+			& (RC_BIT_MODEL_TOTAL - 1))) >> RC_MOVE_REDUCING_BITS];
+}
+
+
+static inline uint32_t
+rc_bit_0_price(const probability prob)
+{
+	return lzma_rc_prices[prob >> RC_MOVE_REDUCING_BITS];
+}
+
+
+static inline uint32_t
+rc_bit_1_price(const probability prob)
+{
+	return lzma_rc_prices[(prob ^ (RC_BIT_MODEL_TOTAL - 1))
+			>> RC_MOVE_REDUCING_BITS];
+}
+
+
+static inline uint32_t
+rc_bittree_price(const probability *const probs,
+		const uint32_t bit_levels, uint32_t symbol)
+{
+	uint32_t price = 0;
+	symbol += UINT32_C(1) << bit_levels;
+
+	do {
+		const uint32_t bit = symbol & 1;
+		symbol >>= 1;
+		price += rc_bit_price(probs[symbol], bit);
+	} while (symbol != 1);
+
+	return price;
+}
+
+
+static inline uint32_t
+rc_bittree_reverse_price(const probability *const probs,
+		uint32_t bit_levels, uint32_t symbol)
+{
+	uint32_t price = 0;
+	uint32_t model_index = 1;
+
+	do {
+		const uint32_t bit = symbol & 1;
+		symbol >>= 1;
+		price += rc_bit_price(probs[model_index], bit);
+		model_index = (model_index << 1) + bit;
+	} while (--bit_levels != 0);
+
+	return price;
+}
+
+
+static inline uint32_t
+rc_direct_price(const uint32_t bits)
+{
+	 return bits << RC_BIT_PRICE_SHIFT_BITS;
+}
+
+#endif
diff --git a/src/liblzma/rangecoder/price_table.c b/src/liblzma/rangecoder/price_table.c
index d0b50fa6..539206b1 100644
--- a/src/liblzma/rangecoder/price_table.c
+++ b/src/liblzma/rangecoder/price_table.c
@@ -1,70 +1,22 @@
-/* This file has been automatically generated by price_table_gen.c. */
+/* This file has been automatically generated by price_tablegen.c. */
 
 #include "range_encoder.h"
 
-const uint32_t lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS] = {
-	   0, 576, 512, 480, 448, 432, 416, 400,
-	 384, 376, 368, 360, 352, 344, 336, 328,
-	 320, 316, 312, 308, 304, 300, 296, 292,
-	 288, 284, 280, 276, 272, 268, 264, 260,
-	 256, 254, 252, 250, 248, 246, 244, 242,
-	 240, 238, 236, 234, 232, 230, 228, 226,
-	 224, 222, 220, 218, 216, 214, 212, 210,
-	 208, 206, 204, 202, 200, 198, 196, 194,
-	 192, 191, 190, 189, 188, 187, 186, 185,
-	 184, 183, 182, 181, 180, 179, 178, 177,
-	 176, 175, 174, 173, 172, 171, 170, 169,
-	 168, 167, 166, 165, 164, 163, 162, 161,
-	 160, 159, 158, 157, 156, 155, 154, 153,
-	 152, 151, 150, 149, 148, 147, 146, 145,
-	 144, 143, 142, 141, 140, 139, 138, 137,
-	 136, 135, 134, 133, 132, 131, 130, 129,
-	 128, 127, 127, 126, 126, 125, 125, 124,
-	 124, 123, 123, 122, 122, 121, 121, 120,
-	 120, 119, 119, 118, 118, 117, 117, 116,
-	 116, 115, 115, 114, 114, 113, 113, 112,
-	 112, 111, 111, 110, 110, 109, 109, 108,
-	 108, 107, 107, 106, 106, 105, 105, 104,
-	 104, 103, 103, 102, 102, 101, 101, 100,
-	 100,  99,  99,  98,  98,  97,  97,  96,
-	  96,  95,  95,  94,  94,  93,  93,  92,
-	  92,  91,  91,  90,  90,  89,  89,  88,
-	  88,  87,  87,  86,  86,  85,  85,  84,
-	  84,  83,  83,  82,  82,  81,  81,  80,
-	  80,  79,  79,  78,  78,  77,  77,  76,
-	  76,  75,  75,  74,  74,  73,  73,  72,
-	  72,  71,  71,  70,  70,  69,  69,  68,
-	  68,  67,  67,  66,  66,  65,  65,  64,
-	  64,  63,  63,  63,  63,  62,  62,  62,
-	  62,  61,  61,  61,  61,  60,  60,  60,
-	  60,  59,  59,  59,  59,  58,  58,  58,
-	  58,  57,  57,  57,  57,  56,  56,  56,
-	  56,  55,  55,  55,  55,  54,  54,  54,
-	  54,  53,  53,  53,  53,  52,  52,  52,
-	  52,  51,  51,  51,  51,  50,  50,  50,
-	  50,  49,  49,  49,  49,  48,  48,  48,
-	  48,  47,  47,  47,  47,  46,  46,  46,
-	  46,  45,  45,  45,  45,  44,  44,  44,
-	  44,  43,  43,  43,  43,  42,  42,  42,
-	  42,  41,  41,  41,  41,  40,  40,  40,
-	  40,  39,  39,  39,  39,  38,  38,  38,
-	  38,  37,  37,  37,  37,  36,  36,  36,
-	  36,  35,  35,  35,  35,  34,  34,  34,
-	  34,  33,  33,  33,  33,  32,  32,  32,
-	  32,  31,  31,  31,  31,  30,  30,  30,
-	  30,  29,  29,  29,  29,  28,  28,  28,
-	  28,  27,  27,  27,  27,  26,  26,  26,
-	  26,  25,  25,  25,  25,  24,  24,  24,
-	  24,  23,  23,  23,  23,  22,  22,  22,
-	  22,  21,  21,  21,  21,  20,  20,  20,
-	  20,  19,  19,  19,  19,  18,  18,  18,
-	  18,  17,  17,  17,  17,  16,  16,  16,
-	  16,  15,  15,  15,  15,  14,  14,  14,
-	  14,  13,  13,  13,  13,  12,  12,  12,
-	  12,  11,  11,  11,  11,  10,  10,  10,
-	  10,   9,   9,   9,   9,   8,   8,   8,
-	   8,   7,   7,   7,   7,   6,   6,   6,
-	   6,   5,   5,   5,   5,   4,   4,   4,
-	   4,   3,   3,   3,   3,   2,   2,   2,
-	   2,   1,   1,   1,   1,   0,   0,   0
+const uint32_t lzma_rc_prices[RC_PRICE_TABLE_SIZE] = {
+	 128, 103,  91,  84,  78,  73,  69,  66,
+	  63,  61,  58,  56,  54,  52,  51,  49,
+	  48,  46,  45,  44,  43,  42,  41,  40,
+	  39,  38,  37,  36,  35,  34,  34,  33,
+	  32,  31,  31,  30,  29,  29,  28,  28,
+	  27,  26,  26,  25,  25,  24,  24,  23,
+	  23,  22,  22,  22,  21,  21,  20,  20,
+	  19,  19,  19,  18,  18,  17,  17,  17,
+	  16,  16,  16,  15,  15,  15,  14,  14,
+	  14,  13,  13,  13,  12,  12,  12,  11,
+	  11,  11,  11,  10,  10,  10,  10,   9,
+	   9,   9,   9,   8,   8,   8,   8,   7,
+	   7,   7,   7,   6,   6,   6,   6,   5,
+	   5,   5,   5,   5,   4,   4,   4,   4,
+	   3,   3,   3,   3,   3,   2,   2,   2,
+	   2,   2,   2,   1,   1,   1,   1,   1
 };
diff --git a/src/liblzma/rangecoder/price_table_init.c b/src/liblzma/rangecoder/price_table_init.c
index 4714dfd6..9c7d799b 100644
--- a/src/liblzma/rangecoder/price_table_init.c
+++ b/src/liblzma/rangecoder/price_table_init.c
@@ -23,25 +23,32 @@
 #endif
 
 
-#define NUM_BITS (BIT_MODEL_TOTAL_BITS - MOVE_REDUCING_BITS)
-
-
-uint32_t lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS];
+uint32_t lzma_rc_prices[RC_PRICE_TABLE_SIZE];
 
 
 extern void
 lzma_rc_init(void)
 {
-	// Initialize lzma_rc_prob_prices[].
-	for (int i = NUM_BITS - 1; i >= 0; --i) {
-		const uint32_t start = 1 << (NUM_BITS - i - 1);
-		const uint32_t end = 1 << (NUM_BITS - i);
-
-		for (uint32_t j = start; j < end; ++j) {
-			lzma_rc_prob_prices[j] = (i << BIT_PRICE_SHIFT_BITS)
-				+ (((end - j) << BIT_PRICE_SHIFT_BITS)
-				>> (NUM_BITS - i - 1));
+	for (uint32_t i = (UINT32_C(1) << RC_MOVE_REDUCING_BITS) / 2;
+			i < RC_BIT_MODEL_TOTAL;
+			i += (UINT32_C(1) << RC_MOVE_REDUCING_BITS)) {
+		const uint32_t cycles_bits = RC_BIT_PRICE_SHIFT_BITS;
+		uint32_t w = i;
+		uint32_t bit_count = 0;
+
+		for (uint32_t j = 0; j < cycles_bits; ++j) {
+			w *= w;
+			bit_count <<= 1;
+
+			while (w >= (UINT32_C(1) << 16)) {
+				w >>= 1;
+				++bit_count;
+			}
 		}
+
+		lzma_rc_prices[i >> RC_MOVE_REDUCING_BITS]
+				= (RC_BIT_MODEL_TOTAL_BITS << cycles_bits)
+				- 15 - bit_count;
 	}
 
 	return;
diff --git a/src/liblzma/rangecoder/price_table_gen.c b/src/liblzma/rangecoder/price_tablegen.c
index 946d8215..68513635 100644
--- a/src/liblzma/rangecoder/price_table_gen.c
+++ b/src/liblzma/rangecoder/price_tablegen.c
@@ -1,9 +1,9 @@
 ///////////////////////////////////////////////////////////////////////////////
 //
-/// \file       price_table_gen.c
+/// \file       price_tablegen.c
 /// \brief      Probability price table generator
 ///
-/// Compiling: gcc -std=c99 -o price_table_gen price_table_gen.c
+/// Compiling: gcc -std=c99 -o price_tablegen price_tablegen.c
 //
 //  Copyright (C) 2007 Lasse Collin
 //
@@ -19,10 +19,11 @@
 //
 ///////////////////////////////////////////////////////////////////////////////
 
-#include <sys/types.h>
+#include <stddef.h>
 #include <inttypes.h>
 #include <stdio.h>
 #include "range_common.h"
+#include "price.h"
 #include "price_table_init.c"
 
 
@@ -32,18 +33,18 @@ main(void)
 	lzma_rc_init();
 
 	printf("/* This file has been automatically generated by "
-			"price_table_gen.c. */\n\n"
+			"price_tablegen.c. */\n\n"
 			"#include \"range_encoder.h\"\n\n"
-			"const uint32_t lzma_rc_prob_prices["
-			"BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS] = {");
+			"const uint32_t lzma_rc_prices["
+			"RC_PRICE_TABLE_SIZE] = {");
 
-	const size_t array_size = sizeof(lzma_rc_prob_prices)
-			/ sizeof(lzma_rc_prob_prices[0]);
+	const size_t array_size = sizeof(lzma_rc_prices)
+			/ sizeof(lzma_rc_prices[0]);
 	for (size_t i = 0; i < array_size; ++i) {
 		if (i % 8 == 0)
 			printf("\n\t");
 
-		printf("%4" PRIu32, lzma_rc_prob_prices[i]);
+		printf("%4" PRIu32, lzma_rc_prices[i]);
 
 		if (i != array_size - 1)
 			printf(",");
diff --git a/src/liblzma/rangecoder/range_common.h b/src/liblzma/rangecoder/range_common.h
index 7613621a..6e5b0994 100644
--- a/src/liblzma/rangecoder/range_common.h
+++ b/src/liblzma/rangecoder/range_common.h
@@ -30,15 +30,12 @@
 // Constants //
 ///////////////
 
-#define SHIFT_BITS 8
-#define TOP_BITS 24
-#define TOP_VALUE (UINT32_C(1) << TOP_BITS)
-#define BIT_MODEL_TOTAL_BITS 11
-#define BIT_MODEL_TOTAL (UINT32_C(1) << BIT_MODEL_TOTAL_BITS)
-#define MOVE_BITS 5
-
-#define MOVE_REDUCING_BITS 2
-#define BIT_PRICE_SHIFT_BITS 6
+#define RC_SHIFT_BITS 8
+#define RC_TOP_BITS 24
+#define RC_TOP_VALUE (UINT32_C(1) << RC_TOP_BITS)
+#define RC_BIT_MODEL_TOTAL_BITS 11
+#define RC_BIT_MODEL_TOTAL (UINT32_C(1) << RC_BIT_MODEL_TOTAL_BITS)
+#define RC_MOVE_BITS 5
 
 
 ////////////
@@ -47,7 +44,7 @@
 
 // Resets the probability so that both 0 and 1 have probability of 50 %
 #define bit_reset(prob) \
-	prob = BIT_MODEL_TOTAL >> 1
+	prob = RC_BIT_MODEL_TOTAL >> 1
 
 // This does the same for a complete bit tree.
 // (A tree represented as an array.)
diff --git a/src/liblzma/rangecoder/range_decoder.h b/src/liblzma/rangecoder/range_decoder.h
index 62162448..ca2d392e 100644
--- a/src/liblzma/rangecoder/range_decoder.h
+++ b/src/liblzma/rangecoder/range_decoder.h
@@ -31,6 +31,7 @@ typedef struct {
 } lzma_range_decoder;
 
 
+/// Reads the first five bytes to initialize the range decoder.
 static inline bool
 rc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in,
 		size_t *restrict in_pos, size_t in_size)
@@ -48,14 +49,22 @@ rc_read_init(lzma_range_decoder *rc, const uint8_t *restrict in,
 }
 
 
-/// Makes local copies of range decoder variables.
-#define rc_to_local(range_decoder) \
+/// Makes local copies of range decoder and *in_pos variables. Doing this
+/// improves speed significantly. The range decoder macros expect also
+/// variables `in' and `in_size' to be defined.
+#define rc_to_local(range_decoder, in_pos) \
 	lzma_range_decoder rc = range_decoder; \
+	size_t rc_in_pos = (in_pos); \
 	uint32_t rc_bound
 
+
 /// Stores the local copes back to the range decoder structure.
-#define rc_from_local(range_decoder) \
-	range_decoder = rc
+#define rc_from_local(range_decoder, in_pos) \
+do { \
+	range_decoder = rc; \
+	in_pos = rc_in_pos; \
+} while (0)
+
 
 /// Resets the range decoder structure.
 #define rc_reset(range_decoder) \
@@ -66,158 +75,112 @@ do { \
 } while (0)
 
 
-// All of the macros in this file expect the following variables being defined:
-//  - lzma_range_decoder range_decoder;
-//  - uint32_t rc_bound;   // Temporary variable
-//  - uint8_t *in;
-//  - size_t in_pos_local; // Local alias for *in_pos
-
+/// When decoding has been properly finished, rc.code is always zero unless
+/// the input stream is corrupt. So checking this can catch some corrupt
+/// files especially if they don't have any other integrity check.
+#define rc_is_finished(range_decoder) \
+	((range_decoder).code == 0)
 
-//////////////////
-// Buffer "I/O" //
-//////////////////
 
-// Read the next byte of compressed data from buffer_in, if needed.
-#define rc_normalize() \
+/// Read the next input byte if needed. If more input is needed but there is
+/// no more input available, "goto out" is used to jump out of the main
+/// decoder loop.
+#define rc_normalize(seq) \
 do { \
-	if (rc.range < TOP_VALUE) { \
-		rc.range <<= SHIFT_BITS; \
-		rc.code = (rc.code << SHIFT_BITS) | in[in_pos_local++]; \
+	if (rc.range < RC_TOP_VALUE) { \
+		if (unlikely(rc_in_pos == in_size)) { \
+			coder->sequence = seq; \
+			goto out; \
+		} \
+		rc.range <<= RC_SHIFT_BITS; \
+		rc.code = (rc.code << RC_SHIFT_BITS) | in[rc_in_pos++]; \
 	} \
 } while (0)
 
 
-//////////////////
-// Bit decoding //
-//////////////////
-
-// Range decoder's DecodeBit() is splitted into three macros:
-//    if_bit_0(prob) {
-//        update_bit_0(prob)
-//        ...
-//    } else {
-//        update_bit_1(prob)
-//        ...
-//    }
-
-#define if_bit_0(prob) \
-	rc_normalize(); \
-	rc_bound = (rc.range >> BIT_MODEL_TOTAL_BITS) * (prob); \
+/// Start decoding a bit. This must be used together with rc_update_0()
+/// and rc_update_1():
+///
+///     rc_if_0(prob, seq) {
+///         rc_update_0(prob);
+///         // Do something
+///     } else {
+///         rc_update_1(prob);
+///         // Do something else
+///     }
+///
+#define rc_if_0(prob, seq) \
+	rc_normalize(seq); \
+	rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
 	if (rc.code < rc_bound)
 
 
-#define update_bit_0(prob) \
+/// Update the range decoder state and the used probability variable to
+/// match a decoded bit of 0.
+#define rc_update_0(prob) \
 do { \
 	rc.range = rc_bound; \
-	prob += (BIT_MODEL_TOTAL - (prob)) >> MOVE_BITS; \
+	prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \
 } while (0)
 
 
-#define update_bit_1(prob) \
+/// Update the range decoder state and the used probability variable to
+/// match a decoded bit of 1.
+#define rc_update_1(prob) \
 do { \
 	rc.range -= rc_bound; \
 	rc.code -= rc_bound; \
-	prob -= (prob) >> MOVE_BITS; \
+	prob -= (prob) >> RC_MOVE_BITS; \
 } while (0)
 
 
-#define rc_decode_direct(dest, count) \
+/// Decodes one bit and runs action0 or action1 depending on the decoded bit.
+/// This macro is used as the last step in bittree reverse decoders since
+/// those don't use "symbol" for anything else than indexing the probability
+/// arrays.
+#define rc_bit_last(prob, action0, action1, seq) \
 do { \
-	rc_normalize(); \
-	rc.range >>= 1; \
-	rc.code -= rc.range; \
-	rc_bound = UINT32_C(0) - (rc.code >> 31); \
-	rc.code += rc.range & rc_bound; \
-	dest = (dest << 1) + (rc_bound + 1); \
-} while (--count > 0)
+	rc_if_0(prob, seq) { \
+		rc_update_0(prob); \
+		action0; \
+	} else { \
+		rc_update_1(prob); \
+		action1; \
+	} \
+} while (0)
 
 
-// Dummy versions don't update prob or dest.
-#define update_bit_0_dummy() \
-	rc.range = rc_bound
+/// Decodes one bit, updates "symbol", and runs action0 or action1 depending
+/// on the decoded bit.
+#define rc_bit(prob, action0, action1, seq) \
+	rc_bit_last(prob, \
+		symbol <<= 1; action0, \
+		symbol = (symbol << 1) + 1; action1, \
+		seq);
 
 
-#define update_bit_1_dummy() \
-do { \
-	rc.range -= rc_bound; \
-	rc.code -= rc_bound; \
-} while (0)
+/// Like rc_bit() but add "case seq:" as a prefix. This makes the unrolled
+/// loops more readable because the code isn't littered with "case"
+/// statements. On the other hand this also makes it less readable, since
+/// spotting the places where the decoder loop may be restarted is less
+/// obvious.
+#define rc_bit_case(prob, action0, action1, seq) \
+	case seq: rc_bit(prob, action0, action1, seq)
 
 
-#define rc_decode_direct_dummy(count) \
+/// Decode a bit without using a probability.
+#define rc_direct(dest, seq) \
 do { \
-	rc_normalize(); \
+	rc_normalize(seq); \
 	rc.range >>= 1; \
 	rc.code -= rc.range; \
-	rc.code += rc.range & (UINT32_C(0) - (rc.code >> 31)); \
-} while (--count > 0)
-
-
-///////////////////////
-// Bit tree decoding //
-///////////////////////
-
-#define bittree_decode(target, probs, bit_levels) \
-do { \
-	uint32_t model_index = 1; \
-	for (uint32_t bit_index = (bit_levels); bit_index != 0; --bit_index) { \
-		if_bit_0((probs)[model_index]) { \
-			update_bit_0((probs)[model_index]); \
-			model_index <<= 1; \
-		} else { \
-			update_bit_1((probs)[model_index]); \
-			model_index = (model_index << 1) | 1; \
-		} \
-	} \
-	target += model_index - (1 << bit_levels); \
-} while (0)
-
-
-#define bittree_reverse_decode(target, probs, bit_levels) \
-do { \
-	uint32_t model_index = 1; \
-	for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
-		if_bit_0((probs)[model_index]) { \
-			update_bit_0((probs)[model_index]); \
-			model_index <<= 1; \
-		} else { \
-			update_bit_1((probs)[model_index]); \
-			model_index = (model_index << 1) | 1; \
-			target += 1 << bit_index; \
-		} \
-	} \
-} while (0)
-
-
-// Dummy versions don't update prob.
-#define bittree_decode_dummy(target, probs, bit_levels) \
-do { \
-	uint32_t model_index = 1; \
-	for (uint32_t bit_index = (bit_levels); bit_index != 0; --bit_index) { \
-		if_bit_0((probs)[model_index]) { \
-			update_bit_0_dummy(); \
-			model_index <<= 1; \
-		} else { \
-			update_bit_1_dummy(); \
-			model_index = (model_index << 1) | 1; \
-		} \
-	} \
-	target += model_index - (1 << bit_levels); \
+	rc_bound = UINT32_C(0) - (rc.code >> 31); \
+	rc.code += rc.range & rc_bound; \
+	dest = (dest << 1) + (rc_bound + 1); \
 } while (0)
 
 
-#define bittree_reverse_decode_dummy(probs, bit_levels) \
-do { \
-	uint32_t model_index = 1; \
-	for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
-		if_bit_0((probs)[model_index]) { \
-			update_bit_0_dummy(); \
-			model_index <<= 1; \
-		} else { \
-			update_bit_1_dummy(); \
-			model_index = (model_index << 1) | 1; \
-		} \
-	} \
-} while (0)
+// NOTE: No macros are provided for bittree decoding. It seems to be simpler
+// to just write them open in the code.
 
 #endif
diff --git a/src/liblzma/rangecoder/range_encoder.h b/src/liblzma/rangecoder/range_encoder.h
index b156ee7f..f66e955c 100644
--- a/src/liblzma/rangecoder/range_encoder.h
+++ b/src/liblzma/rangecoder/range_encoder.h
@@ -22,6 +22,7 @@
 #define LZMA_RANGE_ENCODER_H
 
 #include "range_common.h"
+#include "price.h"
 
 
 /// Maximum number of symbols that can be put pending into lzma_range_encoder
@@ -87,7 +88,7 @@ rc_bittree(lzma_range_encoder *rc, probability *probs,
 	do {
 		const uint32_t bit = (symbol >> --bit_count) & 1;
 		rc_bit(rc, &probs[model_index], bit);
-		model_index = (model_index << 1) | bit;
+		model_index = (model_index << 1) + bit;
 	} while (bit_count != 0);
 }
 
@@ -102,7 +103,7 @@ rc_bittree_reverse(lzma_range_encoder *rc, probability *probs,
 		const uint32_t bit = symbol & 1;
 		symbol >>= 1;
 		rc_bit(rc, &probs[model_index], bit);
-		model_index = (model_index << 1) | bit;
+		model_index = (model_index << 1) + bit;
 	} while (--bit_count != 0);
 }
 
@@ -146,7 +147,7 @@ rc_shift_low(lzma_range_encoder *rc,
 	}
 
 	++rc->cache_size;
-	rc->low = (rc->low & 0x00FFFFFF) << SHIFT_BITS;
+	rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
 
 	return false;
 }
@@ -156,32 +157,35 @@ static inline bool
 rc_encode(lzma_range_encoder *rc,
 		uint8_t *out, size_t *out_pos, size_t out_size)
 {
+	assert(rc->count <= RC_SYMBOLS_MAX);
+
 	while (rc->pos < rc->count) {
 		// Normalize
-		if (rc->range < TOP_VALUE) {
+		if (rc->range < RC_TOP_VALUE) {
 			if (rc_shift_low(rc, out, out_pos, out_size))
 				return true;
 
-			rc->range <<= SHIFT_BITS;
+			rc->range <<= RC_SHIFT_BITS;
 		}
 
 		// Encode a bit
 		switch (rc->symbols[rc->pos]) {
 		case RC_BIT_0: {
 			probability prob = *rc->probs[rc->pos];
-			rc->range = (rc->range >> BIT_MODEL_TOTAL_BITS) * prob;
-			prob += (BIT_MODEL_TOTAL - prob) >> MOVE_BITS;
+			rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
+					* prob;
+			prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
 			*rc->probs[rc->pos] = prob;
 			break;
 		}
 
 		case RC_BIT_1: {
 			probability prob = *rc->probs[rc->pos];
-			const uint32_t bound = prob
-					* (rc->range >> BIT_MODEL_TOTAL_BITS);
+			const uint32_t bound = prob * (rc->range
+					>> RC_BIT_MODEL_TOTAL_BITS);
 			rc->low += bound;
 			rc->range -= bound;
-			prob -= prob >> MOVE_BITS;
+			prob -= prob >> RC_MOVE_BITS;
 			*rc->probs[rc->pos] = prob;
 			break;
 		}
@@ -231,72 +235,4 @@ rc_pending(const lzma_range_encoder *rc)
 	return rc->cache_size + 5 - 1;
 }
 
-
-////////////
-// Prices //
-////////////
-
-#ifdef HAVE_SMALL
-/// Probability prices used by *_get_price() macros. This is initialized
-/// by lzma_rc_init() and is not modified later.
-extern uint32_t lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS];
-
-/// Initializes lzma_rc_prob_prices[]. This needs to be called only once.
-extern void lzma_rc_init(void);
-
-#else
-// Not building a size optimized version, so we use a precomputed
-// constant table.
-extern const uint32_t
-lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS];
-
-#endif
-
-
-#define bit_get_price(prob, symbol) \
-	lzma_rc_prob_prices[((((prob) - (symbol)) ^ (-(symbol))) \
-			& (BIT_MODEL_TOTAL - 1)) >> MOVE_REDUCING_BITS]
-
-
-#define bit_get_price_0(prob) \
-	lzma_rc_prob_prices[(prob) >> MOVE_REDUCING_BITS]
-
-
-#define bit_get_price_1(prob) \
-	lzma_rc_prob_prices[(BIT_MODEL_TOTAL - (prob)) >> MOVE_REDUCING_BITS]
-
-
-static inline uint32_t
-bittree_get_price(const probability *probs,
-		uint32_t bit_levels, uint32_t symbol)
-{
-	uint32_t price = 0;
-	symbol |= UINT32_C(1) << bit_levels;
-
-	do {
-		price += bit_get_price(probs[symbol >> 1], symbol & 1);
-		symbol >>= 1;
-	} while (symbol != 1);
-
-	return price;
-}
-
-
-static inline uint32_t
-bittree_reverse_get_price(const probability *probs,
-		uint32_t bit_levels, uint32_t symbol)
-{
-	uint32_t price = 0;
-	uint32_t model_index = 1;
-
-	do {
-		const uint32_t bit = symbol & 1;
-		symbol >>= 1;
-		price += bit_get_price(probs[model_index], bit);
-		model_index = (model_index << 1) | bit;
-	} while (--bit_levels != 0);
-
-	return price;
-}
-
 #endif