vcs.maemo.org Git - physicsfs/blob - lzma/CS/7zip/Compress/RangeCoder/RangeCoderBitTree.cs

   1 using System;
   2
   3 namespace SevenZip.Compression.RangeCoder
   4 {
   5         struct BitTreeEncoder
   6         {
   7                 BitEncoder[] Models;
   8                 int NumBitLevels;
   9
  10                 public BitTreeEncoder(int numBitLevels)
  11                 {
  12                         NumBitLevels = numBitLevels;
  13                         Models = new BitEncoder[1 << numBitLevels];
  14                 }
  15
  16                 public void Init()
  17                 {
  18                         for (uint i = 1; i < (1 << NumBitLevels); i++)
  19                                 Models[i].Init();
  20                 }
  21
  22                 public void Encode(Encoder rangeEncoder, UInt32 symbol)
  23                 {
  24                         UInt32 m = 1;
  25                         for (int bitIndex = NumBitLevels; bitIndex > 0; )
  26                         {
  27                                 bitIndex--;
  28                                 UInt32 bit = (symbol >> bitIndex) & 1;
  29                                 Models[m].Encode(rangeEncoder, bit);
  30                                 m = (m << 1) | bit;
  31                         }
  32                 }
  33
  34                 public void ReverseEncode(Encoder rangeEncoder, UInt32 symbol)
  35                 {
  36                         UInt32 m = 1;
  37                         for (UInt32 i = 0; i < NumBitLevels; i++)
  38                         {
  39                                 UInt32 bit = symbol & 1;
  40                                 Models[m].Encode(rangeEncoder, bit);
  41                                 m = (m << 1) | bit;
  42                                 symbol >>= 1;
  43                         }
  44                 }
  45
  46                 public UInt32 GetPrice(UInt32 symbol)
  47                 {
  48                         UInt32 price = 0;
  49                         UInt32 m = 1;
  50                         for (int bitIndex = NumBitLevels; bitIndex > 0; )
  51                         {
  52                                 bitIndex--;
  53                                 UInt32 bit = (symbol >> bitIndex) & 1;
  54                                 price += Models[m].GetPrice(bit);
  55                                 m = (m << 1) + bit;
  56                         }
  57                         return price;
  58                 }
  59
  60                 public UInt32 ReverseGetPrice(UInt32 symbol)
  61                 {
  62                         UInt32 price = 0;
  63                         UInt32 m = 1;
  64                         for (int i = NumBitLevels; i > 0; i--)
  65                         {
  66                                 UInt32 bit = symbol & 1;
  67                                 symbol >>= 1;
  68                                 price += Models[m].GetPrice(bit);
  69                                 m = (m << 1) | bit;
  70                         }
  71                         return price;
  72                 }
  73
  74                 public static UInt32 ReverseGetPrice(BitEncoder[] Models, UInt32 startIndex,
  75                         int NumBitLevels, UInt32 symbol)
  76                 {
  77                         UInt32 price = 0;
  78                         UInt32 m = 1;
  79                         for (int i = NumBitLevels; i > 0; i--)
  80                         {
  81                                 UInt32 bit = symbol & 1;
  82                                 symbol >>= 1;
  83                                 price += Models[startIndex + m].GetPrice(bit);
  84                                 m = (m << 1) | bit;
  85                         }
  86                         return price;
  87                 }
  88
  89                 public static void ReverseEncode(BitEncoder[] Models, UInt32 startIndex,
  90                         Encoder rangeEncoder, int NumBitLevels, UInt32 symbol)
  91                 {
  92                         UInt32 m = 1;
  93                         for (int i = 0; i < NumBitLevels; i++)
  94                         {
  95                                 UInt32 bit = symbol & 1;
  96                                 Models[startIndex + m].Encode(rangeEncoder, bit);
  97                                 m = (m << 1) | bit;
  98                                 symbol >>= 1;
  99                         }
 100                 }
 101         }
 102
 103         struct BitTreeDecoder
 104         {
 105                 BitDecoder[] Models;
 106                 int NumBitLevels;
 107
 108                 public BitTreeDecoder(int numBitLevels)
 109                 {
 110                         NumBitLevels = numBitLevels;
 111                         Models = new BitDecoder[1 << numBitLevels];
 112                 }
 113
 114                 public void Init()
 115                 {
 116                         for (uint i = 1; i < (1 << NumBitLevels); i++)
 117                                 Models[i].Init();
 118                 }
 119
 120                 public uint Decode(RangeCoder.Decoder rangeDecoder)
 121                 {
 122                         uint m = 1;
 123                         for (int bitIndex = NumBitLevels; bitIndex > 0; bitIndex--)
 124                                 m = (m << 1) + Models[m].Decode(rangeDecoder);
 125                         return m - ((uint)1 << NumBitLevels);
 126                 }
 127
 128                 public uint ReverseDecode(RangeCoder.Decoder rangeDecoder)
 129                 {
 130                         uint m = 1;
 131                         uint symbol = 0;
 132                         for (int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++)
 133                         {
 134                                 uint bit = Models[m].Decode(rangeDecoder);
 135                                 m <<= 1;
 136                                 m += bit;
 137                                 symbol |= (bit << bitIndex);
 138                         }
 139                         return symbol;
 140                 }
 141
 142                 public static uint ReverseDecode(BitDecoder[] Models, UInt32 startIndex,
 143                         RangeCoder.Decoder rangeDecoder, int NumBitLevels)
 144                 {
 145                         uint m = 1;
 146                         uint symbol = 0;
 147                         for (int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++)
 148                         {
 149                                 uint bit = Models[startIndex + m].Decode(rangeDecoder);
 150                                 m <<= 1;
 151                                 m += bit;
 152                                 symbol |= (bit << bitIndex);
 153                         }
 154                         return symbol;
 155                 }
 156         }
 157 }