Mercurial > vba-linux

annotate src/win32/7zip/7z/CPP/7zip/Compress/RangeCoder.h @ 1:f9f4f1b99eed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
importing src directory
author Robert McIntyre <rlm@mit.edu>
date Sat, 03 Mar 2012 10:31:27 -0600
parents
children
rev   line source
rlm@1 1 // Compress/RangeCoder.h
rlm@1 2
rlm@1 3 #ifndef __COMPRESS_RANGE_CODER_H
rlm@1 4 #define __COMPRESS_RANGE_CODER_H
rlm@1 5
rlm@1 6 #include "../Common/InBuffer.h"
rlm@1 7 #include "../Common/OutBuffer.h"
rlm@1 8
rlm@1 9 namespace NCompress {
rlm@1 10 namespace NRangeCoder {
rlm@1 11
rlm@1 12 const int kNumTopBits = 24;
rlm@1 13 const UInt32 kTopValue = (1 << kNumTopBits);
rlm@1 14
rlm@1 15 class CEncoder
rlm@1 16 {
rlm@1 17 UInt32 _cacheSize;
rlm@1 18 Byte _cache;
rlm@1 19 public:
rlm@1 20 UInt64 Low;
rlm@1 21 UInt32 Range;
rlm@1 22 COutBuffer Stream;
rlm@1 23 bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
rlm@1 24
rlm@1 25 void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); }
rlm@1 26 void Init()
rlm@1 27 {
rlm@1 28 Stream.Init();
rlm@1 29 Low = 0;
rlm@1 30 Range = 0xFFFFFFFF;
rlm@1 31 _cacheSize = 1;
rlm@1 32 _cache = 0;
rlm@1 33 }
rlm@1 34
rlm@1 35 void FlushData()
rlm@1 36 {
rlm@1 37 // Low += 1;
rlm@1 38 for(int i = 0; i < 5; i++)
rlm@1 39 ShiftLow();
rlm@1 40 }
rlm@1 41
rlm@1 42 HRESULT FlushStream() { return Stream.Flush(); }
rlm@1 43
rlm@1 44 void ReleaseStream() { Stream.ReleaseStream(); }
rlm@1 45
rlm@1 46 void Encode(UInt32 start, UInt32 size, UInt32 total)
rlm@1 47 {
rlm@1 48 Low += start * (Range /= total);
rlm@1 49 Range *= size;
rlm@1 50 while (Range < kTopValue)
rlm@1 51 {
rlm@1 52 Range <<= 8;
rlm@1 53 ShiftLow();
rlm@1 54 }
rlm@1 55 }
rlm@1 56
rlm@1 57 void ShiftLow()
rlm@1 58 {
rlm@1 59 if ((UInt32)Low < (UInt32)0xFF000000 || (int)(Low >> 32) != 0)
rlm@1 60 {
rlm@1 61 Byte temp = _cache;
rlm@1 62 do
rlm@1 63 {
rlm@1 64 Stream.WriteByte((Byte)(temp + (Byte)(Low >> 32)));
rlm@1 65 temp = 0xFF;
rlm@1 66 }
rlm@1 67 while(--_cacheSize != 0);
rlm@1 68 _cache = (Byte)((UInt32)Low >> 24);
rlm@1 69 }
rlm@1 70 _cacheSize++;
rlm@1 71 Low = (UInt32)Low << 8;
rlm@1 72 }
rlm@1 73
rlm@1 74 void EncodeDirectBits(UInt32 value, int numBits)
rlm@1 75 {
rlm@1 76 for (numBits--; numBits >= 0; numBits--)
rlm@1 77 {
rlm@1 78 Range >>= 1;
rlm@1 79 Low += Range & (0 - ((value >> numBits) & 1));
rlm@1 80 if (Range < kTopValue)
rlm@1 81 {
rlm@1 82 Range <<= 8;
rlm@1 83 ShiftLow();
rlm@1 84 }
rlm@1 85 }
rlm@1 86 }
rlm@1 87
rlm@1 88 void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol)
rlm@1 89 {
rlm@1 90 UInt32 newBound = (Range >> numTotalBits) * size0;
rlm@1 91 if (symbol == 0)
rlm@1 92 Range = newBound;
rlm@1 93 else
rlm@1 94 {
rlm@1 95 Low += newBound;
rlm@1 96 Range -= newBound;
rlm@1 97 }
rlm@1 98 while (Range < kTopValue)
rlm@1 99 {
rlm@1 100 Range <<= 8;
rlm@1 101 ShiftLow();
rlm@1 102 }
rlm@1 103 }
rlm@1 104
rlm@1 105 UInt64 GetProcessedSize() { return Stream.GetProcessedSize() + _cacheSize + 4; }
rlm@1 106 };
rlm@1 107
rlm@1 108 class CDecoder
rlm@1 109 {
rlm@1 110 public:
rlm@1 111 CInBuffer Stream;
rlm@1 112 UInt32 Range;
rlm@1 113 UInt32 Code;
rlm@1 114 bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
rlm@1 115
rlm@1 116 void Normalize()
rlm@1 117 {
rlm@1 118 while (Range < kTopValue)
rlm@1 119 {
rlm@1 120 Code = (Code << 8) | Stream.ReadByte();
rlm@1 121 Range <<= 8;
rlm@1 122 }
rlm@1 123 }
rlm@1 124
rlm@1 125 void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
rlm@1 126 void Init()
rlm@1 127 {
rlm@1 128 Stream.Init();
rlm@1 129 Code = 0;
rlm@1 130 Range = 0xFFFFFFFF;
rlm@1 131 for(int i = 0; i < 5; i++)
rlm@1 132 Code = (Code << 8) | Stream.ReadByte();
rlm@1 133 }
rlm@1 134
rlm@1 135 void ReleaseStream() { Stream.ReleaseStream(); }
rlm@1 136
rlm@1 137 UInt32 GetThreshold(UInt32 total)
rlm@1 138 {
rlm@1 139 return (Code) / ( Range /= total);
rlm@1 140 }
rlm@1 141
rlm@1 142 void Decode(UInt32 start, UInt32 size)
rlm@1 143 {
rlm@1 144 Code -= start * Range;
rlm@1 145 Range *= size;
rlm@1 146 Normalize();
rlm@1 147 }
rlm@1 148
rlm@1 149 UInt32 DecodeDirectBits(int numTotalBits)
rlm@1 150 {
rlm@1 151 UInt32 range = Range;
rlm@1 152 UInt32 code = Code;
rlm@1 153 UInt32 result = 0;
rlm@1 154 for (int i = numTotalBits; i != 0; i--)
rlm@1 155 {
rlm@1 156 range >>= 1;
rlm@1 157 /*
rlm@1 158 result <<= 1;
rlm@1 159 if (code >= range)
rlm@1 160 {
rlm@1 161 code -= range;
rlm@1 162 result |= 1;
rlm@1 163 }
rlm@1 164 */
rlm@1 165 UInt32 t = (code - range) >> 31;
rlm@1 166 code -= range & (t - 1);
rlm@1 167 result = (result << 1) | (1 - t);
rlm@1 168
rlm@1 169 if (range < kTopValue)
rlm@1 170 {
rlm@1 171 code = (code << 8) | Stream.ReadByte();
rlm@1 172 range <<= 8;
rlm@1 173 }
rlm@1 174 }
rlm@1 175 Range = range;
rlm@1 176 Code = code;
rlm@1 177 return result;
rlm@1 178 }
rlm@1 179
rlm@1 180 UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits)
rlm@1 181 {
rlm@1 182 UInt32 newBound = (Range >> numTotalBits) * size0;
rlm@1 183 UInt32 symbol;
rlm@1 184 if (Code < newBound)
rlm@1 185 {
rlm@1 186 symbol = 0;
rlm@1 187 Range = newBound;
rlm@1 188 }
rlm@1 189 else
rlm@1 190 {
rlm@1 191 symbol = 1;
rlm@1 192 Code -= newBound;
rlm@1 193 Range -= newBound;
rlm@1 194 }
rlm@1 195 Normalize();
rlm@1 196 return symbol;
rlm@1 197 }
rlm@1 198
rlm@1 199 UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); }
rlm@1 200 };
rlm@1 201
rlm@1 202 }}
rlm@1 203
rlm@1 204 #endif