diff options
Diffstat (limited to 'src/liblzma/rangecoder')
| -rw-r--r-- | src/liblzma/rangecoder/Makefile.am | 28 | ||||
| -rw-r--r-- | src/liblzma/rangecoder/range_common.h | 68 | ||||
| -rw-r--r-- | src/liblzma/rangecoder/range_decoder.h | 189 | ||||
| -rw-r--r-- | src/liblzma/rangecoder/range_encoder.c | 46 | ||||
| -rw-r--r-- | src/liblzma/rangecoder/range_encoder.h | 317 |
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 |