1 /************************************************************************************
2 Includes
3 ************************************************************************************/
4 #include "All.h"
5 #include "BitArray.h"
6
7 /************************************************************************************
8 Declares
9 ************************************************************************************/
10 #define BIT_ARRAY_ELEMENTS (4096) // the number of elements in the bit array (4 MB)
11 #define BIT_ARRAY_BYTES (BIT_ARRAY_ELEMENTS * 4) // the number of bytes in the bit array
12 #define BIT_ARRAY_BITS (BIT_ARRAY_BYTES * 8) // the number of bits in the bit array
13
14 #define MAX_ELEMENT_BITS 128
15 #define REFILL_BIT_THRESHOLD (BIT_ARRAY_BITS - MAX_ELEMENT_BITS)
16
17 #define CODE_BITS 32
18 #define TOP_VALUE ((unsigned int) 1 << (CODE_BITS - 1))
19 #define SHIFT_BITS (CODE_BITS - 9)
20 #define EXTRA_BITS ((CODE_BITS - 2) % 8 + 1)
21 #define BOTTOM_VALUE (TOP_VALUE >> 8)
22
23 /************************************************************************************
24 Lookup tables
25 ************************************************************************************/
26 const uint32 K_SUM_MIN_BOUNDARY[32] = {0,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648UL,0,0,0,0};
27
28 #define MODEL_ELEMENTS 64
29 #define RANGE_OVERFLOW_TOTAL_WIDTH 65536
30 #define RANGE_OVERFLOW_SHIFT 16
31
32 const uint32 RANGE_TOTAL[64] = {0,19578,36160,48417,56323,60899,63265,64435,64971,65232,65351,65416,65447,65466,65476,65482,65485,65488,65490,65491,65492,65493,65494,65495,65496,65497,65498,65499,65500,65501,65502,65503,65504,65505,65506,65507,65508,65509,65510,65511,65512,65513,65514,65515,65516,65517,65518,65519,65520,65521,65522,65523,65524,65525,65526,65527,65528,65529,65530,65531,65532,65533,65534,65535,};
33 const uint32 RANGE_WIDTH[64] = {19578,16582,12257,7906,4576,2366,1170,536,261,119,65,31,19,10,6,3,3,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,};
34
35 #ifdef BUILD_RANGE_TABLE
36 int g_aryOverflows[256] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
37 int g_nTotalOverflow = 0;
38 #endif
39
40 /************************************************************************************
41 Constructor
42 ************************************************************************************/
CBitArray(CIO * pIO)43 CBitArray::CBitArray(CIO *pIO)
44 {
45 // allocate memory for the bit array
46 m_pBitArray = new uint32 [BIT_ARRAY_ELEMENTS];
47 memset(m_pBitArray, 0, BIT_ARRAY_BYTES);
48
49 // initialize other variables
50 m_nCurrentBitIndex = 0;
51 m_pIO = pIO;
52 }
53
54 /************************************************************************************
55 Destructor
56 ************************************************************************************/
~CBitArray()57 CBitArray::~CBitArray()
58 {
59 // free the bit array
60 SAFE_ARRAY_DELETE(m_pBitArray)
61 #ifdef BUILD_RANGE_TABLE
62 OutputRangeTable();
63 #endif
64 }
65
66 /************************************************************************************
67 Output the bit array via the CIO (typically saves to disk)
68 ************************************************************************************/
OutputBitArray(BOOL bFinalize)69 int CBitArray::OutputBitArray(BOOL bFinalize)
70 {
71 // write the entire file to disk
72 unsigned int nBytesWritten = 0;
73 unsigned int nBytesToWrite = 0;
74 // unsigned int nRetVal = 0;
75
76 if (bFinalize)
77 {
78 nBytesToWrite = ((m_nCurrentBitIndex >> 5) * 4) + 4;
79
80 m_MD5.AddData(m_pBitArray, nBytesToWrite);
81
82 RETURN_ON_ERROR(m_pIO->Write(m_pBitArray, nBytesToWrite, &nBytesWritten))
83
84 // reset the bit pointer
85 m_nCurrentBitIndex = 0;
86 }
87 else
88 {
89 nBytesToWrite = (m_nCurrentBitIndex >> 5) * 4;
90
91 m_MD5.AddData(m_pBitArray, nBytesToWrite);
92
93 RETURN_ON_ERROR(m_pIO->Write(m_pBitArray, nBytesToWrite, &nBytesWritten))
94
95 // move the last value to the front of the bit array
96 m_pBitArray[0] = m_pBitArray[m_nCurrentBitIndex >> 5];
97 m_nCurrentBitIndex = (m_nCurrentBitIndex & 31);
98
99 // zero the rest of the memory (may not need the +1 because of frame byte alignment)
100 memset(&m_pBitArray[1], 0, min((int)nBytesToWrite + 1, BIT_ARRAY_BYTES - 1));
101 }
102
103 // return a success
104 return ERROR_SUCCESS;
105 }
106
107 /************************************************************************************
108 Range coding macros -- ugly, but outperform inline's (every cycle counts here)
109 ************************************************************************************/
110 #define PUTC(VALUE) m_pBitArray[m_nCurrentBitIndex >> 5] |= ((VALUE) & 0xFF) << (24 - (m_nCurrentBitIndex & 31)); m_nCurrentBitIndex += 8;
111 #define PUTC_NOCAP(VALUE) m_pBitArray[m_nCurrentBitIndex >> 5] |= (VALUE) << (24 - (m_nCurrentBitIndex & 31)); m_nCurrentBitIndex += 8;
112
113 #define NORMALIZE_RANGE_CODER \
114 while (m_RangeCoderInfo.range <= BOTTOM_VALUE) \
115 { \
116 if (m_RangeCoderInfo.low < (0xFF << SHIFT_BITS)) \
117 { \
118 PUTC(m_RangeCoderInfo.buffer); \
119 for ( ; m_RangeCoderInfo.help; m_RangeCoderInfo.help--) { PUTC_NOCAP(0xFF); } \
120 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.low >> SHIFT_BITS); \
121 } \
122 else if (m_RangeCoderInfo.low & TOP_VALUE) \
123 { \
124 PUTC(m_RangeCoderInfo.buffer + 1); \
125 m_nCurrentBitIndex += (m_RangeCoderInfo.help * 8); \
126 m_RangeCoderInfo.help = 0; \
127 m_RangeCoderInfo.buffer = (m_RangeCoderInfo.low >> SHIFT_BITS); \
128 } \
129 else \
130 { \
131 m_RangeCoderInfo.help++; \
132 } \
133 \
134 m_RangeCoderInfo.low = (m_RangeCoderInfo.low << 8) & (TOP_VALUE - 1); \
135 m_RangeCoderInfo.range <<= 8; \
136 }
137
138 #define ENCODE_FAST(RANGE_WIDTH, RANGE_TOTAL, SHIFT) \
139 NORMALIZE_RANGE_CODER \
140 const int nTemp = m_RangeCoderInfo.range >> (SHIFT); \
141 m_RangeCoderInfo.range = nTemp * (RANGE_WIDTH); \
142 m_RangeCoderInfo.low += nTemp * (RANGE_TOTAL);
143
144 #define ENCODE_DIRECT(VALUE, SHIFT) \
145 NORMALIZE_RANGE_CODER \
146 m_RangeCoderInfo.range = m_RangeCoderInfo.range >> (SHIFT); \
147 m_RangeCoderInfo.low += m_RangeCoderInfo.range * (VALUE);
148
149 /************************************************************************************
150 Directly encode bits to the bitstream
151 ************************************************************************************/
EncodeBits(unsigned int nValue,int nBits)152 int CBitArray::EncodeBits(unsigned int nValue, int nBits)
153 {
154 // make sure there is room for the data
155 // this is a little slower than ensuring a huge block to start with, but it's safer
156 if (m_nCurrentBitIndex > REFILL_BIT_THRESHOLD)
157 {
158 RETURN_ON_ERROR(OutputBitArray())
159 }
160
161 ENCODE_DIRECT(nValue, nBits);
162 return 0;
163 }
164
165 /************************************************************************************
166 Encodes an unsigned int to the bit array (no rice coding)
167 ************************************************************************************/
EncodeUnsignedLong(unsigned int n)168 int CBitArray::EncodeUnsignedLong(unsigned int n)
169 {
170 // make sure there are at least 8 bytes in the buffer
171 if (m_nCurrentBitIndex > (BIT_ARRAY_BYTES - 8))
172 {
173 RETURN_ON_ERROR(OutputBitArray())
174 }
175
176 // encode the value
177 uint32 nBitArrayIndex = m_nCurrentBitIndex >> 5;
178 int nBitIndex = m_nCurrentBitIndex & 31;
179
180 if (nBitIndex == 0)
181 {
182 m_pBitArray[nBitArrayIndex] = n;
183 }
184 else
185 {
186 m_pBitArray[nBitArrayIndex] |= n >> nBitIndex;
187 m_pBitArray[nBitArrayIndex + 1] = n << (32 - nBitIndex);
188 }
189
190 m_nCurrentBitIndex += 32;
191
192 return 0;
193 }
194
195 /************************************************************************************
196 Advance to a byte boundary (for frame alignment)
197 ************************************************************************************/
AdvanceToByteBoundary()198 void CBitArray::AdvanceToByteBoundary()
199 {
200 while (m_nCurrentBitIndex % 8)
201 m_nCurrentBitIndex++;
202 }
203
204 /************************************************************************************
205 Encode a value
206 ************************************************************************************/
EncodeValue(int nEncode,BIT_ARRAY_STATE & BitArrayState)207 int CBitArray::EncodeValue(int nEncode, BIT_ARRAY_STATE & BitArrayState)
208 {
209 // make sure there is room for the data
210 // this is a little slower than ensuring a huge block to start with, but it's safer
211 if (m_nCurrentBitIndex > REFILL_BIT_THRESHOLD)
212 {
213 RETURN_ON_ERROR(OutputBitArray())
214 }
215
216 // convert to unsigned
217 nEncode = (nEncode > 0) ? nEncode * 2 - 1 : -nEncode * 2;
218
219 int nOriginalKSum = BitArrayState.nKSum;
220
221 // get the working k
222 // int nTempK = (BitArrayState.k) ? BitArrayState.k - 1 : 0;
223
224 // update nKSum
225 BitArrayState.nKSum += ((nEncode + 1) / 2) - ((BitArrayState.nKSum + 16) >> 5);
226
227 // update k
228 if (BitArrayState.nKSum < K_SUM_MIN_BOUNDARY[BitArrayState.k])
229 BitArrayState.k--;
230 else if (BitArrayState.nKSum >= K_SUM_MIN_BOUNDARY[BitArrayState.k + 1])
231 BitArrayState.k++;
232
233 // figure the pivot value
234 int nPivotValue = max(nOriginalKSum / 32, 1);
235 int nOverflow = nEncode / nPivotValue;
236 int nBase = nEncode - (nOverflow * nPivotValue);
237
238 // store the overflow
239 if (nOverflow < (MODEL_ELEMENTS - 1))
240 {
241 ENCODE_FAST(RANGE_WIDTH[nOverflow], RANGE_TOTAL[nOverflow], RANGE_OVERFLOW_SHIFT);
242
243 #ifdef BUILD_RANGE_TABLE
244 g_aryOverflows[nOverflow]++;
245 g_nTotalOverflow++;
246 #endif
247 }
248 else
249 {
250 // store the "special" overflow (tells that perfect k is encoded next)
251 ENCODE_FAST(RANGE_WIDTH[MODEL_ELEMENTS - 1], RANGE_TOTAL[MODEL_ELEMENTS - 1], RANGE_OVERFLOW_SHIFT);
252
253 #ifdef BUILD_RANGE_TABLE
254 g_aryOverflows[MODEL_ELEMENTS - 1]++;
255 g_nTotalOverflow++;
256 #endif
257
258 // code the overflow using straight bits
259 ENCODE_DIRECT((nOverflow >> 16) & 0xFFFF, 16);
260 ENCODE_DIRECT(nOverflow & 0xFFFF, 16);
261 }
262
263 // code the base
264 {
265 if (nPivotValue >= (1 << 16))
266 {
267 int nPivotValueBits = 0;
268 while ((nPivotValue >> nPivotValueBits) > 0) { nPivotValueBits++; }
269 int nSplitFactor = 1 << (nPivotValueBits - 16);
270
271 // we know that base is smaller than pivot coming into this
272 // however, after we divide both by an integer, they could be the same
273 // we account by adding one to the pivot, but this hurts compression
274 // by (1 / nSplitFactor) -- therefore we maximize the split factor
275 // that gets one added to it
276
277 // encode the pivot as two pieces
278 int nPivotValueA = (nPivotValue / nSplitFactor) + 1;
279 int nPivotValueB = nSplitFactor;
280
281 int nBaseA = nBase / nSplitFactor;
282 int nBaseB = nBase % nSplitFactor;
283
284 {
285 NORMALIZE_RANGE_CODER
286 const int nTemp = m_RangeCoderInfo.range / nPivotValueA;
287 m_RangeCoderInfo.range = nTemp;
288 m_RangeCoderInfo.low += nTemp * nBaseA;
289 }
290
291 {
292 NORMALIZE_RANGE_CODER
293 const int nTemp = m_RangeCoderInfo.range / nPivotValueB;
294 m_RangeCoderInfo.range = nTemp;
295 m_RangeCoderInfo.low += nTemp * nBaseB;
296 }
297 }
298 else
299 {
300
301 NORMALIZE_RANGE_CODER
302 const int nTemp = m_RangeCoderInfo.range / nPivotValue;
303 m_RangeCoderInfo.range = nTemp;
304 m_RangeCoderInfo.low += nTemp * nBase;
305 }
306 }
307
308 return 0;
309 }
310
311 /************************************************************************************
312 Flush
313 ************************************************************************************/
FlushBitArray()314 void CBitArray::FlushBitArray()
315 {
316 // advance to a byte boundary (for alignment)
317 AdvanceToByteBoundary();
318
319 // the range coder
320 m_RangeCoderInfo.low = 0; // full code range
321 m_RangeCoderInfo.range = TOP_VALUE;
322 m_RangeCoderInfo.buffer = 0;
323 m_RangeCoderInfo.help = 0; // no bytes to follow
324 }
325
FlushState(BIT_ARRAY_STATE & BitArrayState)326 void CBitArray::FlushState(BIT_ARRAY_STATE & BitArrayState)
327 {
328 // k and ksum
329 BitArrayState.k = 10;
330 BitArrayState.nKSum = (1 << BitArrayState.k) * 16;
331 }
332
333 /************************************************************************************
334 Finalize
335 ************************************************************************************/
Finalize()336 void CBitArray::Finalize()
337 {
338 NORMALIZE_RANGE_CODER
339
340 unsigned int nTemp = (m_RangeCoderInfo.low >> SHIFT_BITS) + 1;
341
342 if (nTemp > 0xFF) // we have a carry
343 {
344 PUTC(m_RangeCoderInfo.buffer + 1);
345 for ( ; m_RangeCoderInfo.help; m_RangeCoderInfo.help--)
346 {
347 PUTC(0);
348 }
349 }
350 else // no carry
351 {
352 PUTC(m_RangeCoderInfo.buffer);
353 for ( ; m_RangeCoderInfo.help; m_RangeCoderInfo.help--)
354 {
355 PUTC(((unsigned char) 0xFF));
356 }
357 }
358
359 // we must output these bytes so the decoder can properly work at the end of the stream
360 PUTC(nTemp & 0xFF);
361 PUTC(0);
362 PUTC(0);
363 PUTC(0);
364 }
365
366 /************************************************************************************
367 Build a range table (for development / debugging)
368 ************************************************************************************/
369 #ifdef BUILD_RANGE_TABLE
OutputRangeTable()370 void CBitArray::OutputRangeTable()
371 {
372 int z;
373
374 if (g_nTotalOverflow == 0) return;
375
376 int nTotal = 0;
377 int aryWidth[256]; ZeroMemory(aryWidth, 256 * 4);
378 for (z = 0; z < MODEL_ELEMENTS; z++)
379 {
380 aryWidth[z] = int(((float(g_aryOverflows[z]) * float(65536)) + (g_nTotalOverflow / 2)) / float(g_nTotalOverflow));
381 if (aryWidth[z] == 0) aryWidth[z] = 1;
382 nTotal += aryWidth[z];
383 }
384
385 z = 0;
386 while (nTotal > 65536)
387 {
388 if (aryWidth[z] != 1)
389 {
390 aryWidth[z]--;
391 nTotal--;
392 }
393 z++;
394 if (z == MODEL_ELEMENTS) z = 0;
395 }
396
397 z = 0;
398 while (nTotal < 65536)
399 {
400 aryWidth[z++]++;
401 nTotal++;
402 if (z == MODEL_ELEMENTS) z = 0;
403 }
404
405 int aryTotal[256]; ZeroMemory(aryTotal, 256 * 4);
406 for (z = 0; z < MODEL_ELEMENTS; z++)
407 {
408 for (int q = 0; q < z; q++)
409 {
410 aryTotal[z] += aryWidth[q];
411 }
412 }
413
414 TCHAR buf[1024];
415 _stprintf(buf, _T("const uint32 RANGE_TOTAL[%d] = {"), MODEL_ELEMENTS);
416 ODS(buf);
417 for (z = 0; z < MODEL_ELEMENTS; z++)
418 {
419 _stprintf(buf, _T("%d,"), aryTotal[z]);
420 OutputDebugString(buf);
421 }
422 ODS(_T("};\n"));
423
424 _stprintf(buf, _T("const uint32 RANGE_WIDTH[%d] = {"), MODEL_ELEMENTS);
425 ODS(buf);
426 for (z = 0; z < MODEL_ELEMENTS; z++)
427 {
428 _stprintf(buf, _T("%d,"), aryWidth[z]);
429 OutputDebugString(buf);
430 }
431 ODS(_T("};\n\n"));
432 }
433 #endif // #ifdef BUILD_RANGE_TABLE
434