src/liblzma/rangecoder/price.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       price.h
   4 /// \brief      Probability price calculation
   5 //
   6 //  Copyright (C) 1999-2008 Igor Pavlov
   7 //
   8 //  This library is free software; you can redistribute it and/or
   9 //  modify it under the terms of the GNU Lesser General Public
  10 //  License as published by the Free Software Foundation; either
  11 //  version 2.1 of the License, or (at your option) any later version.
  12 //
  13 //  This library is distributed in the hope that it will be useful,
  14 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 //  Lesser General Public License for more details.
  17 //
  18 ///////////////////////////////////////////////////////////////////////////////
  19
  20 #ifndef LZMA_PRICE_H
  21 #define LZMA_PRICE_H
  22
  23
  24 #define RC_MOVE_REDUCING_BITS 4
  25 #define RC_BIT_PRICE_SHIFT_BITS 4
  26 #define RC_PRICE_TABLE_SIZE (RC_BIT_MODEL_TOTAL >> RC_MOVE_REDUCING_BITS)
  27
  28 #define RC_INFINITY_PRICE (UINT32_C(1) << 30)
  29
  30
  31 #if !defined(LZMA_RANGE_ENCODER_H) || defined(HAVE_SMALL)
  32 /// Probability prices used by *_get_price() macros. This is initialized
  33 /// by lzma_rc_init() and is not modified later.
  34 extern uint32_t lzma_rc_prices[RC_PRICE_TABLE_SIZE];
  35
  36 /// Initializes lzma_rc_prices[]. This needs to be called only once.
  37 extern void lzma_rc_init(void);
  38
  39 #else
  40 // Not building a size optimized version, so we use a precomputed
  41 // constant table.
  42 extern const uint32_t lzma_rc_prices[RC_PRICE_TABLE_SIZE];
  43
  44 #endif
  45
  46
  47 static inline uint32_t
  48 rc_bit_price(const probability prob, const uint32_t bit)
  49 {
  50         return lzma_rc_prices[(prob ^ ((UINT32_C(0) - bit)
  51                         & (RC_BIT_MODEL_TOTAL - 1))) >> RC_MOVE_REDUCING_BITS];
  52 }
  53
  54
  55 static inline uint32_t
  56 rc_bit_0_price(const probability prob)
  57 {
  58         return lzma_rc_prices[prob >> RC_MOVE_REDUCING_BITS];
  59 }
  60
  61
  62 static inline uint32_t
  63 rc_bit_1_price(const probability prob)
  64 {
  65         return lzma_rc_prices[(prob ^ (RC_BIT_MODEL_TOTAL - 1))
  66                         >> RC_MOVE_REDUCING_BITS];
  67 }
  68
  69
  70 static inline uint32_t
  71 rc_bittree_price(const probability *const probs,
  72                 const uint32_t bit_levels, uint32_t symbol)
  73 {
  74         uint32_t price = 0;
  75         symbol += UINT32_C(1) << bit_levels;
  76
  77         do {
  78                 const uint32_t bit = symbol & 1;
  79                 symbol >>= 1;
  80                 price += rc_bit_price(probs[symbol], bit);
  81         } while (symbol != 1);
  82
  83         return price;
  84 }
  85
  86
  87 static inline uint32_t
  88 rc_bittree_reverse_price(const probability *const probs,
  89                 uint32_t bit_levels, uint32_t symbol)
  90 {
  91         uint32_t price = 0;
  92         uint32_t model_index = 1;
  93
  94         do {
  95                 const uint32_t bit = symbol & 1;
  96                 symbol >>= 1;
  97                 price += rc_bit_price(probs[model_index], bit);
  98                 model_index = (model_index << 1) + bit;
  99         } while (--bit_levels != 0);
 100
 101         return price;
 102 }
 103
 104
 105 static inline uint32_t
 106 rc_direct_price(const uint32_t bits)
 107 {
 108          return bits << RC_BIT_PRICE_SHIFT_BITS;
 109 }
 110
 111 #endif