1 // Compress/HuffmanDecoder.h 2 3 #ifndef __COMPRESS_HUFFMAN_DECODER_H 4 #define __COMPRESS_HUFFMAN_DECODER_H 5 6 #include "../../Common/MyTypes.h" 7 8 namespace NCompress { 9 namespace NHuffman { 10 11 const unsigned kNumPairLenBits = 4; 12 const unsigned kPairLenMask = (1 << kNumPairLenBits) - 1; 13 14 template <unsigned kNumBitsMax, UInt32 m_NumSymbols, unsigned kNumTableBits = 9> 15 class CDecoder 16 { 17 public: 18 UInt32 _limits[kNumBitsMax + 2]; 19 UInt32 _poses[kNumBitsMax + 1]; 20 UInt16 _lens[1 << kNumTableBits]; 21 UInt16 _symbols[m_NumSymbols]; 22 Build(const Byte * lens)23 bool Build(const Byte *lens) throw() 24 { 25 UInt32 counts[kNumBitsMax + 1]; 26 27 unsigned i; 28 for (i = 0; i <= kNumBitsMax; i++) 29 counts[i] = 0; 30 31 UInt32 sym; 32 33 for (sym = 0; sym < m_NumSymbols; sym++) 34 counts[lens[sym]]++; 35 36 const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax; 37 38 _limits[0] = 0; 39 40 UInt32 startPos = 0; 41 UInt32 sum = 0; 42 43 for (i = 1; i <= kNumBitsMax; i++) 44 { 45 const UInt32 cnt = counts[i]; 46 startPos += cnt << (kNumBitsMax - i); 47 if (startPos > kMaxValue) 48 return false; 49 _limits[i] = startPos; 50 counts[i] = sum; 51 _poses[i] = sum; 52 sum += cnt; 53 } 54 55 counts[0] = sum; 56 _poses[0] = sum; 57 _limits[kNumBitsMax + 1] = kMaxValue; 58 59 for (sym = 0; sym < m_NumSymbols; sym++) 60 { 61 unsigned len = lens[sym]; 62 if (len == 0) 63 continue; 64 65 unsigned offset = counts[len]++; 66 _symbols[offset] = (UInt16)sym; 67 68 if (len <= kNumTableBits) 69 { 70 offset -= _poses[len]; 71 UInt32 num = (UInt32)1 << (kNumTableBits - len); 72 UInt16 val = (UInt16)((sym << kNumPairLenBits) | len); 73 UInt16 *dest = _lens + (_limits[(size_t)len - 1] >> (kNumBitsMax - kNumTableBits)) + (offset << (kNumTableBits - len)); 74 for (UInt32 k = 0; k < num; k++) 75 dest[k] = val; 76 } 77 } 78 79 return true; 80 } 81 82 throw()83 bool BuildFull(const Byte *lens, UInt32 numSymbols = m_NumSymbols) throw() 84 { 85 UInt32 counts[kNumBitsMax + 1]; 86 87 unsigned i; 88 for (i = 0; i <= kNumBitsMax; i++) 89 counts[i] = 0; 90 91 UInt32 sym; 92 93 for (sym = 0; sym < numSymbols; sym++) 94 counts[lens[sym]]++; 95 96 const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax; 97 98 _limits[0] = 0; 99 100 UInt32 startPos = 0; 101 UInt32 sum = 0; 102 103 for (i = 1; i <= kNumBitsMax; i++) 104 { 105 const UInt32 cnt = counts[i]; 106 startPos += cnt << (kNumBitsMax - i); 107 if (startPos > kMaxValue) 108 return false; 109 _limits[i] = startPos; 110 counts[i] = sum; 111 _poses[i] = sum; 112 sum += cnt; 113 } 114 115 counts[0] = sum; 116 _poses[0] = sum; 117 _limits[kNumBitsMax + 1] = kMaxValue; 118 119 for (sym = 0; sym < numSymbols; sym++) 120 { 121 unsigned len = lens[sym]; 122 if (len == 0) 123 continue; 124 125 unsigned offset = counts[len]++; 126 _symbols[offset] = (UInt16)sym; 127 128 if (len <= kNumTableBits) 129 { 130 offset -= _poses[len]; 131 UInt32 num = (UInt32)1 << (kNumTableBits - len); 132 UInt16 val = (UInt16)((sym << kNumPairLenBits) | len); 133 UInt16 *dest = _lens + (_limits[(size_t)len - 1] >> (kNumBitsMax - kNumTableBits)) + (offset << (kNumTableBits - len)); 134 for (UInt32 k = 0; k < num; k++) 135 dest[k] = val; 136 } 137 } 138 139 return startPos == kMaxValue; 140 } 141 142 143 template <class TBitDecoder> 144 MY_FORCE_INLINE Decode(TBitDecoder * bitStream)145 UInt32 Decode(TBitDecoder *bitStream) const 146 { 147 UInt32 val = bitStream->GetValue(kNumBitsMax); 148 149 if (val < _limits[kNumTableBits]) 150 { 151 UInt32 pair = _lens[val >> (kNumBitsMax - kNumTableBits)]; 152 bitStream->MovePos((unsigned)(pair & kPairLenMask)); 153 return pair >> kNumPairLenBits; 154 } 155 156 unsigned numBits; 157 for (numBits = kNumTableBits + 1; val >= _limits[numBits]; numBits++); 158 159 if (numBits > kNumBitsMax) 160 return 0xFFFFFFFF; 161 162 bitStream->MovePos(numBits); 163 UInt32 index = _poses[numBits] + ((val - _limits[(size_t)numBits - 1]) >> (kNumBitsMax - numBits)); 164 return _symbols[index]; 165 } 166 167 168 template <class TBitDecoder> 169 MY_FORCE_INLINE DecodeFull(TBitDecoder * bitStream)170 UInt32 DecodeFull(TBitDecoder *bitStream) const 171 { 172 UInt32 val = bitStream->GetValue(kNumBitsMax); 173 174 if (val < _limits[kNumTableBits]) 175 { 176 UInt32 pair = _lens[val >> (kNumBitsMax - kNumTableBits)]; 177 bitStream->MovePos((unsigned)(pair & kPairLenMask)); 178 return pair >> kNumPairLenBits; 179 } 180 181 unsigned numBits; 182 for (numBits = kNumTableBits + 1; val >= _limits[numBits]; numBits++); 183 184 bitStream->MovePos(numBits); 185 UInt32 index = _poses[numBits] + ((val - _limits[(size_t)numBits - 1]) >> (kNumBitsMax - numBits)); 186 return _symbols[index]; 187 } 188 }; 189 190 191 192 template <UInt32 m_NumSymbols> 193 class CDecoder7b 194 { 195 Byte _lens[1 << 7]; 196 public: 197 Build(const Byte * lens)198 bool Build(const Byte *lens) throw() 199 { 200 const unsigned kNumBitsMax = 7; 201 202 UInt32 counts[kNumBitsMax + 1]; 203 UInt32 _poses[kNumBitsMax + 1]; 204 UInt32 _limits[kNumBitsMax + 1]; 205 206 unsigned i; 207 for (i = 0; i <= kNumBitsMax; i++) 208 counts[i] = 0; 209 210 UInt32 sym; 211 212 for (sym = 0; sym < m_NumSymbols; sym++) 213 counts[lens[sym]]++; 214 215 const UInt32 kMaxValue = (UInt32)1 << kNumBitsMax; 216 217 _limits[0] = 0; 218 219 UInt32 startPos = 0; 220 UInt32 sum = 0; 221 222 for (i = 1; i <= kNumBitsMax; i++) 223 { 224 const UInt32 cnt = counts[i]; 225 startPos += cnt << (kNumBitsMax - i); 226 if (startPos > kMaxValue) 227 return false; 228 _limits[i] = startPos; 229 counts[i] = sum; 230 _poses[i] = sum; 231 sum += cnt; 232 } 233 234 counts[0] = sum; 235 _poses[0] = sum; 236 237 for (sym = 0; sym < m_NumSymbols; sym++) 238 { 239 unsigned len = lens[sym]; 240 if (len == 0) 241 continue; 242 243 unsigned offset = counts[len]++; 244 245 { 246 offset -= _poses[len]; 247 UInt32 num = (UInt32)1 << (kNumBitsMax - len); 248 Byte val = (Byte)((sym << 3) | len); 249 Byte *dest = _lens + (_limits[(size_t)len - 1]) + (offset << (kNumBitsMax - len)); 250 for (UInt32 k = 0; k < num; k++) 251 dest[k] = val; 252 } 253 } 254 255 { 256 UInt32 limit = _limits[kNumBitsMax]; 257 UInt32 num = ((UInt32)1 << kNumBitsMax) - limit; 258 Byte *dest = _lens + limit; 259 for (UInt32 k = 0; k < num; k++) 260 dest[k] = (Byte)(0x1F << 3); 261 } 262 263 return true; 264 } 265 266 template <class TBitDecoder> Decode(TBitDecoder * bitStream)267 UInt32 Decode(TBitDecoder *bitStream) const 268 { 269 UInt32 val = bitStream->GetValue(7); 270 UInt32 pair = _lens[val]; 271 bitStream->MovePos((unsigned)(pair & 0x7)); 272 return pair >> 3; 273 } 274 }; 275 276 }} 277 278 #endif 279