aboutsummaryrefslogtreecommitdiff
path: root/src/liblzma/rangecoder
diff options
context:
space:
mode:
Diffstat (limited to 'src/liblzma/rangecoder')
-rw-r--r--src/liblzma/rangecoder/Makefile.am10
-rw-r--r--src/liblzma/rangecoder/price.h111
-rw-r--r--src/liblzma/rangecoder/price_table.c84
-rw-r--r--src/liblzma/rangecoder/price_table_init.c33
-rw-r--r--src/liblzma/rangecoder/price_tablegen.c (renamed from src/liblzma/rangecoder/price_table_gen.c)19
-rw-r--r--src/liblzma/rangecoder/range_common.h17
-rw-r--r--src/liblzma/rangecoder/range_decoder.h209
-rw-r--r--src/liblzma/rangecoder/range_encoder.h92
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-20 11:34:35 +0000