aboutsummaryrefslogtreecommitdiff
path: root/src/liblzma/rangecoder
diff options
context:
space:
mode:
authorLasse Collin <lasse.collin@tukaani.org>2007-12-09 00:42:33 +0200
committerLasse Collin <lasse.collin@tukaani.org>2007-12-09 00:42:33 +0200
commit5d018dc03549c1ee4958364712fb0c94e1bf2741 (patch)
tree1b211911fb33fddb3f04b77f99e81df23623ffc4 /src/liblzma/rangecoder
downloadxz-5d018dc03549c1ee4958364712fb0c94e1bf2741.tar.xz
Imported to git.
Diffstat (limited to 'src/liblzma/rangecoder')
-rw-r--r--src/liblzma/rangecoder/Makefile.am28
-rw-r--r--src/liblzma/rangecoder/range_common.h68
-rw-r--r--src/liblzma/rangecoder/range_decoder.h189
-rw-r--r--src/liblzma/rangecoder/range_encoder.c46
-rw-r--r--src/liblzma/rangecoder/range_encoder.h317
5 files changed, 648 insertions, 0 deletions
diff --git a/src/liblzma/rangecoder/Makefile.am b/src/liblzma/rangecoder/Makefile.am
new file mode 100644
index 00000000..ef5d1464
--- /dev/null
+++ b/src/liblzma/rangecoder/Makefile.am
@@ -0,0 +1,28 @@
+##
+## Copyright (C) 2006 Lasse Collin
+##
+## 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.
+##
+
+noinst_LTLIBRARIES = librangecoder.la
+
+librangecoder_la_SOURCES = range_common.h
+librangecoder_la_CPPFLAGS = \
+ -I@top_srcdir@/src/liblzma/api \
+ -I@top_srcdir@/src/liblzma/common
+
+if COND_MAIN_ENCODER
+librangecoder_la_SOURCES += range_encoder.c range_encoder.h
+endif
+
+if COND_MAIN_DECODER
+librangecoder_la_SOURCES += range_decoder.h
+endif
diff --git a/src/liblzma/rangecoder/range_common.h b/src/liblzma/rangecoder/range_common.h
new file mode 100644
index 00000000..9e8f89a2
--- /dev/null
+++ b/src/liblzma/rangecoder/range_common.h
@@ -0,0 +1,68 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file range_common.h
+/// \brief Common things for range encoder and decoder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2006 Lasse Collin
+//
+// 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_RANGE_COMMON_H
+#define LZMA_RANGE_COMMON_H
+
+#include "common.h"
+
+
+///////////////
+// 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
+
+
+////////////
+// Macros //
+////////////
+
+// Resets the probability so that both 0 and 1 have probability of 50 %
+#define bit_reset(prob) \
+ prob = BIT_MODEL_TOTAL >> 1
+
+// This does the same for a complete bit tree.
+// (A tree represented as an array.)
+#define bittree_reset(probs, bit_levels) \
+ for (uint32_t bt_i = 0; bt_i < (1 << (bit_levels)); ++bt_i) \
+ bit_reset((probs)[bt_i])
+
+
+//////////////////////
+// Type definitions //
+//////////////////////
+
+// Bit coder speed optimization
+// uint16_t is enough for probability, but usually uint32_t is faster and it
+// doesn't waste too much memory. If uint64_t is fastest on 64-bit CPU, you
+// probably want to use that instead of uint32_t. With uint64_t you will
+// waste RAM _at maximum_ of 4.5 MiB (same for both encoding and decoding).
+typedef uint32_t probability;
+
+#endif
diff --git a/src/liblzma/rangecoder/range_decoder.h b/src/liblzma/rangecoder/range_decoder.h
new file mode 100644
index 00000000..0583faaf
--- /dev/null
+++ b/src/liblzma/rangecoder/range_decoder.h
@@ -0,0 +1,189 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file range_decoder.h
+/// \brief Range Decoder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// 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_RANGE_DECODER_H
+#define LZMA_RANGE_DECODER_H
+
+#include "range_common.h"
+
+
+typedef struct {
+ uint32_t range;
+ uint32_t code;
+} lzma_range_decoder;
+
+
+/// Makes local copies of range decoder variables.
+#define rc_to_local(rc) \
+ uint32_t rc_range = (rc).range; \
+ uint32_t rc_code = (rc).code; \
+ uint32_t rc_bound
+
+/// Stores the local copes back to the range decoder structure.
+#define rc_from_local(rc) \
+do {\
+ (rc).range = rc_range; \
+ (rc).code = rc_code; \
+} while (0)
+
+/// Resets the range decoder structure.
+#define rc_reset(rc) \
+do { \
+ (rc).range = UINT32_MAX; \
+ (rc).code = 0; \
+} while (0)
+
+
+// All of the macros in this file expect the following variables being defined:
+// - uint32_t rc_range;
+// - uint32_t rc_code;
+// - uint32_t rc_bound; // Temporary variable
+// - uint8_t *in;
+// - size_t in_pos_local; // Local alias for *in_pos
+
+
+//////////////////
+// Buffer "I/O" //
+//////////////////
+
+// Read the next byte of compressed data from buffer_in, if needed.
+#define rc_normalize() \
+do { \
+ if (rc_range < TOP_VALUE) { \
+ rc_range <<= SHIFT_BITS; \
+ rc_code = (rc_code << SHIFT_BITS) | in[in_pos_local++]; \
+ } \
+} 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); \
+ if (rc_code < rc_bound)
+
+
+#define update_bit_0(prob) \
+do { \
+ rc_range = rc_bound; \
+ prob += (BIT_MODEL_TOTAL - (prob)) >> MOVE_BITS; \
+} while (0)
+
+
+#define update_bit_1(prob) \
+do { \
+ rc_range -= rc_bound; \
+ rc_code -= rc_bound; \
+ prob -= (prob) >> MOVE_BITS; \
+} while (0)
+
+
+// Dummy versions don't update prob.
+#define update_bit_0_dummy() \
+ rc_range = rc_bound
+
+
+#define update_bit_1_dummy() \
+do { \
+ rc_range -= rc_bound; \
+ rc_code -= rc_bound; \
+} while (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); \
+} 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)
+
+#endif
diff --git a/src/liblzma/rangecoder/range_encoder.c b/src/liblzma/rangecoder/range_encoder.c
new file mode 100644
index 00000000..f03bd873
--- /dev/null
+++ b/src/liblzma/rangecoder/range_encoder.c
@@ -0,0 +1,46 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file range_encoder.c
+/// \brief Static initializations for the range encoder's prices array
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// 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.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "range_encoder.h"
+
+
+#define NUM_BITS (BIT_MODEL_TOTAL_BITS - MOVE_REDUCING_BITS)
+
+
+uint32_t lzma_rc_prob_prices[BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS];
+
+
+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));
+ }
+ }
+
+ return;
+}
diff --git a/src/liblzma/rangecoder/range_encoder.h b/src/liblzma/rangecoder/range_encoder.h
new file mode 100644
index 00000000..d513cfd1
--- /dev/null
+++ b/src/liblzma/rangecoder/range_encoder.h
@@ -0,0 +1,317 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file range_encoder.h
+/// \brief Range Encoder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// 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_RANGE_ENCODER_H
+#define LZMA_RANGE_ENCODER_H
+
+#include "range_common.h"
+
+
+// Allow #including this file even if RC_TEMP_BUFFER_SIZE isn't defined.
+#ifdef RC_BUFFER_SIZE
+typedef struct {
+ uint64_t low;
+ uint32_t range;
+ uint32_t cache_size;
+ uint8_t cache;
+ uint8_t buffer[RC_BUFFER_SIZE];
+ size_t buffer_size;
+} lzma_range_encoder;
+#endif
+
+
+/// Makes local copies of range encoder variables.
+#define rc_to_local(rc) \
+ uint64_t rc_low = (rc).low; \
+ uint32_t rc_range = (rc).range; \
+ uint32_t rc_cache_size = (rc).cache_size; \
+ uint8_t rc_cache = (rc).cache; \
+ uint8_t *rc_buffer = (rc).buffer; \
+ size_t rc_buffer_size = (rc).buffer_size
+
+/// Stores the local copes back to the range encoder structure.
+#define rc_from_local(rc) \
+do { \
+ (rc).low = rc_low; \
+ (rc).range = rc_range; \
+ (rc).cache_size = rc_cache_size; \
+ (rc).cache = rc_cache; \
+ (rc).buffer_size = rc_buffer_size; \
+} while (0)
+
+/// Resets the range encoder structure.
+#define rc_reset(rc) \
+do { \
+ (rc).low = 0; \
+ (rc).range = 0xFFFFFFFF; \
+ (rc).cache_size = 1; \
+ (rc).cache = 0; \
+ (rc).buffer_size = 0; \
+} while (0)
+
+
+//////////////////
+// Bit encoding //
+//////////////////
+
+// These macros expect that the following variables are defined:
+// - uint64_t rc_low;
+// - uint32_t rc_range;
+// - uint8_t rc_cache;
+// - uint32_t rc_cache_size;
+// - uint8_t *out;
+// - size_t out_pos_local; // Local copy of *out_pos
+// - size_t size_out;
+
+
+// Combined from NRangeCoder::CEncoder::Encode()
+// and NRangeCoder::CEncoder::UpdateModel().
+#define bit_encode(prob, symbol) \
+do { \
+ probability rc_prob = prob; \
+ const uint32_t rc_bound \
+ = (rc_range >> BIT_MODEL_TOTAL_BITS) * rc_prob; \
+ if ((symbol) == 0) { \
+ rc_range = rc_bound; \
+ rc_prob += (BIT_MODEL_TOTAL - rc_prob) >> MOVE_BITS; \
+ } else { \
+ rc_low += rc_bound; \
+ rc_range -= rc_bound; \
+ rc_prob -= rc_prob >> MOVE_BITS; \
+ } \
+ prob = rc_prob; \
+ rc_normalize(); \
+} while (0)
+
+
+// Optimized version of bit_encode(prob, 0)
+#define bit_encode_0(prob) \
+do { \
+ probability rc_prob = prob; \
+ rc_range = (rc_range >> BIT_MODEL_TOTAL_BITS) * rc_prob; \
+ rc_prob += (BIT_MODEL_TOTAL - rc_prob) >> MOVE_BITS; \
+ prob = rc_prob; \
+ rc_normalize(); \
+} while (0)
+
+
+// Optimized version of bit_encode(prob, 1)
+#define bit_encode_1(prob) \
+do { \
+ probability rc_prob = prob; \
+ const uint32_t rc_bound = (rc_range >> BIT_MODEL_TOTAL_BITS) \
+ * rc_prob; \
+ rc_low += rc_bound; \
+ rc_range -= rc_bound; \
+ rc_prob -= rc_prob >> MOVE_BITS; \
+ prob = rc_prob; \
+ rc_normalize(); \
+} while (0)
+
+
+///////////////////////
+// Bit tree encoding //
+///////////////////////
+
+#define bittree_encode(probs, bit_levels, symbol) \
+do { \
+ uint32_t model_index = 1; \
+ for (int32_t bit_index = bit_levels - 1; \
+ bit_index >= 0; --bit_index) { \
+ const uint32_t bit = ((symbol) >> bit_index) & 1; \
+ bit_encode((probs)[model_index], bit); \
+ model_index = (model_index << 1) | bit; \
+ } \
+} while (0)
+
+
+#define bittree_reverse_encode(probs, bit_levels, symbol) \
+do { \
+ uint32_t model_index = 1; \
+ for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
+ const uint32_t bit = ((symbol) >> bit_index) & 1; \
+ bit_encode((probs)[model_index], bit); \
+ model_index = (model_index << 1) | bit; \
+ } \
+} while (0)
+
+
+/////////////////
+// Direct bits //
+/////////////////
+
+#define rc_encode_direct_bits(value, num_total_bits) \
+do { \
+ for (int32_t rc_i = (num_total_bits) - 1; rc_i >= 0; --rc_i) { \
+ rc_range >>= 1; \
+ if ((((value) >> rc_i) & 1) == 1) \
+ rc_low += rc_range; \
+ rc_normalize(); \
+ } \
+} while (0)
+
+
+//////////////////
+// Buffer "I/O" //
+//////////////////
+
+// Calls rc_shift_low() to write out a byte if needed.
+#define rc_normalize() \
+do { \
+ if (rc_range < TOP_VALUE) { \
+ rc_range <<= SHIFT_BITS; \
+ rc_shift_low(); \
+ } \
+} while (0)
+
+
+// Flushes all the pending output.
+#define rc_flush() \
+ for (int32_t rc_i = 0; rc_i < 5; ++rc_i) \
+ rc_shift_low()
+
+
+// Writes the compressed data to next_out.
+// TODO: Notation change?
+// (uint32_t)(0xFF000000) => ((uint32_t)(0xFF) << TOP_BITS)
+// TODO: Another notation change?
+// rc_low = (uint32_t)(rc_low) << SHIFT_BITS;
+// =>
+// rc_low &= TOP_VALUE - 1;
+// rc_low <<= SHIFT_BITS;
+#define rc_shift_low() \
+do { \
+ if ((uint32_t)(rc_low) < (uint32_t)(0xFF000000) \
+ || (uint32_t)(rc_low >> 32) != 0) { \
+ uint8_t rc_temp = rc_cache; \
+ do { \
+ rc_write_byte(rc_temp + (uint8_t)(rc_low >> 32)); \
+ rc_temp = 0xFF; \
+ } while(--rc_cache_size != 0); \
+ rc_cache = (uint8_t)((uint32_t)(rc_low) >> 24); \
+ } \
+ ++rc_cache_size; \
+ rc_low = (uint32_t)(rc_low) << SHIFT_BITS; \
+} while (0)
+
+
+// Write one byte of compressed data to *next_out. Updates out_pos_local.
+// If out_pos_local == out_size, the byte is appended to rc_buffer.
+#define rc_write_byte(b) \
+do { \
+ if (out_pos_local == out_size) { \
+ rc_buffer[rc_buffer_size++] = (uint8_t)(b); \
+ assert(rc_buffer_size < RC_BUFFER_SIZE); \
+ } else { \
+ assert(rc_buffer_size == 0); \
+ out[out_pos_local++] = (uint8_t)(b); \
+ } \
+} while (0)
+
+
+//////////////////
+// Price macros //
+//////////////////
+
+// These macros expect that the following variables are defined:
+// - uint32_t lzma_rc_prob_prices;
+
+#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]
+
+
+// Adds price to price_target. TODO Optimize/Cleanup?
+#define bittree_get_price(price_target, probs, bit_levels, symbol) \
+do { \
+ uint32_t bittree_symbol = (symbol) | (UINT32_C(1) << bit_levels); \
+ while (bittree_symbol != 1) { \
+ price_target += bit_get_price((probs)[bittree_symbol >> 1], \
+ bittree_symbol & 1); \
+ bittree_symbol >>= 1; \
+ } \
+} while (0)
+
+
+// Adds price to price_target.
+#define bittree_reverse_get_price(price_target, probs, bit_levels, symbol) \
+do { \
+ uint32_t model_index = 1; \
+ for (uint32_t bit_index = 0; bit_index < bit_levels; ++bit_index) { \
+ const uint32_t bit = ((symbol) >> bit_index) & 1; \
+ price_target += bit_get_price((probs)[model_index], bit); \
+ model_index = (model_index << 1) | bit; \
+ } \
+} while (0)
+
+
+//////////////////////
+// Global variables //
+//////////////////////
+
+// 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];
+
+
+///////////////
+// Functions //
+///////////////
+
+/// Initializes lzma_rc_prob_prices[]. This needs to be called only once.
+extern void lzma_rc_init(void);
+
+
+#ifdef RC_BUFFER_SIZE
+/// Flushes data from rc->temp[] to out[] as much as possible. If everything
+/// cannot be flushed, returns true; false otherwise.
+static inline bool
+rc_flush_buffer(lzma_range_encoder *rc,
+ uint8_t *out, size_t *out_pos, size_t out_size)
+{
+ if (rc->buffer_size > 0) {
+ const size_t out_avail = out_size - *out_pos;
+ if (rc->buffer_size > out_avail) {
+ memcpy(out + *out_pos, rc->buffer, out_avail);
+ *out_pos += out_avail;
+ rc->buffer_size -= out_avail;
+ memmove(rc->buffer, rc->buffer + out_avail,
+ rc->buffer_size);
+ return true;
+ }
+
+ memcpy(out + *out_pos, rc->buffer, rc->buffer_size);
+ *out_pos += rc->buffer_size;
+ rc->buffer_size = 0;
+ }
+
+ return false;
+}
+#endif
+
+#endif