From d13d693155c176fc9e9ad5c50d48ccba27c2d9c6 Mon Sep 17 00:00:00 2001 From: Lasse Collin Date: Tue, 15 Jan 2008 07:40:21 +0200 Subject: Added precomputed range coder probability price table. --- src/liblzma/common/init_encoder.c | 5 ++- src/liblzma/rangecoder/Makefile.am | 9 +++- src/liblzma/rangecoder/price_table.c | 70 +++++++++++++++++++++++++++++++ src/liblzma/rangecoder/price_table_gen.c | 55 ++++++++++++++++++++++++ src/liblzma/rangecoder/price_table_init.c | 48 +++++++++++++++++++++ src/liblzma/rangecoder/range_common.h | 4 +- src/liblzma/rangecoder/range_encoder.c | 46 -------------------- src/liblzma/rangecoder/range_encoder.h | 21 +++++----- 8 files changed, 197 insertions(+), 61 deletions(-) create mode 100644 src/liblzma/rangecoder/price_table.c create mode 100644 src/liblzma/rangecoder/price_table_gen.c create mode 100644 src/liblzma/rangecoder/price_table_init.c delete mode 100644 src/liblzma/rangecoder/range_encoder.c diff --git a/src/liblzma/common/init_encoder.c b/src/liblzma/common/init_encoder.c index 4d3da506..13873aad 100644 --- a/src/liblzma/common/init_encoder.c +++ b/src/liblzma/common/init_encoder.c @@ -33,9 +33,10 @@ lzma_init_encoder(void) lzma_init_check(); #endif -// FIXME TODO Create precalculated tables. -#if defined(HAVE_ENCODER) && defined(HAVE_FILTER_LZMA) +#if defined(HAVE_SMALL) && defined(HAVE_ENCODER) && defined(HAVE_FILTER_LZMA) lzma_rc_init(); +#endif +#if defined(HAVE_ENCODER) && defined(HAVE_FILTER_LZMA) lzma_fastpos_init(); #endif diff --git a/src/liblzma/rangecoder/Makefile.am b/src/liblzma/rangecoder/Makefile.am index ef5d1464..6e80f8d7 100644 --- a/src/liblzma/rangecoder/Makefile.am +++ b/src/liblzma/rangecoder/Makefile.am @@ -12,6 +12,8 @@ ## Lesser General Public License for more details. ## +EXTRA_DIST = price_table_gen.c + noinst_LTLIBRARIES = librangecoder.la librangecoder_la_SOURCES = range_common.h @@ -20,7 +22,12 @@ librangecoder_la_CPPFLAGS = \ -I@top_srcdir@/src/liblzma/common if COND_MAIN_ENCODER -librangecoder_la_SOURCES += range_encoder.c range_encoder.h +librangecoder_la_SOURCES += range_encoder.h +if COND_SMALL +librangecoder_la_SOURCES += price_table_init.c +else +librangecoder_la_SOURCES += price_table.c +endif endif if COND_MAIN_DECODER diff --git a/src/liblzma/rangecoder/price_table.c b/src/liblzma/rangecoder/price_table.c new file mode 100644 index 00000000..d0b50fa6 --- /dev/null +++ b/src/liblzma/rangecoder/price_table.c @@ -0,0 +1,70 @@ +/* This file has been automatically generated by price_table_gen.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 +}; diff --git a/src/liblzma/rangecoder/price_table_gen.c b/src/liblzma/rangecoder/price_table_gen.c new file mode 100644 index 00000000..04703e4f --- /dev/null +++ b/src/liblzma/rangecoder/price_table_gen.c @@ -0,0 +1,55 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file price_table_gen.c +/// \brief Probability price table generator +/// +/// Compiling: gcc -std=c99 -o price_table_gen price_table_gen.c +// +// 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 +#include +#include +#include "range_common.h" +#include "price_table_init.c" + + +int +main(void) +{ + lzma_rc_init(); + + printf("/* This file has been automatically generated by " + "price_table_gen.c. */\n\n" + "#include \"range_encoder.h\"\n\n" + "const uint32_t lzma_rc_prob_prices[" + "BIT_MODEL_TOTAL >> MOVE_REDUCING_BITS] = {"); + + const size_t array_size = sizeof(lzma_rc_prob_prices) + / sizeof(lzma_rc_prob_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]); + + if (i != array_size - 1) + printf(","); + } + + printf("\n};\n"); + + return 0; +} diff --git a/src/liblzma/rangecoder/price_table_init.c b/src/liblzma/rangecoder/price_table_init.c new file mode 100644 index 00000000..4714dfd6 --- /dev/null +++ b/src/liblzma/rangecoder/price_table_init.c @@ -0,0 +1,48 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file price_table_init.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. +// +/////////////////////////////////////////////////////////////////////////////// + +#ifdef HAVE_CONFIG_H +# include "range_encoder.h" +#endif + + +#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_common.h b/src/liblzma/rangecoder/range_common.h index 9e8f89a2..20422b9a 100644 --- a/src/liblzma/rangecoder/range_common.h +++ b/src/liblzma/rangecoder/range_common.h @@ -21,7 +21,9 @@ #ifndef LZMA_RANGE_COMMON_H #define LZMA_RANGE_COMMON_H -#include "common.h" +#ifdef HAVE_CONFIG_H +# include "common.h" +#endif /////////////// diff --git a/src/liblzma/rangecoder/range_encoder.c b/src/liblzma/rangecoder/range_encoder.c deleted file mode 100644 index f03bd873..00000000 --- a/src/liblzma/rangecoder/range_encoder.c +++ /dev/null @@ -1,46 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////// -// -/// \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 index cd5e6457..9f03e226 100644 --- a/src/liblzma/rangecoder/range_encoder.h +++ b/src/liblzma/rangecoder/range_encoder.h @@ -246,21 +246,20 @@ do { \ } while (0) -////////////////////// -// Global variables // -////////////////////// - -// Probability prices used by *_get_price() macros. This is initialized -// by lzma_rc_init() and is not modified later. +#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]; - -/////////////// -// Functions // -/////////////// - /// 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 #endif -- cgit v1.2.3