1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #include "fixer.h"
6
7 #include "huffman.hpp"
8
9 /* KJL 17:12:25 17/09/98 - Huffman compression/decompression routines */
10
11 typedef struct
12 {
13 int Symbol;
14 unsigned int Count;
15 } HuffItem;
16
17 typedef struct HuffNode // 16-byte node structure
18 {
19 union
20 { // the FIRST four bytes
21 struct HuffNode *zero; // points to the "zero" branch or...
22 unsigned int value; // holds the value of an end node
23 };
24
25 union
26 { // the SECOND four bytes
27 struct HuffNode *one; // points to the "one" branch or...
28 struct HuffNode *link; // points to next end node in list
29 };
30
31 struct HuffNode *parent; // the THIRD four bytes, parent node
32
33 // union
34 // { // the FOURTH four bytes
35 unsigned int bits; // the bit pattern of this end node
36 // struct
37 // {
38 // unsigned char flag;
39 // unsigned char curdepth;
40 // unsigned char maxdepth;
41 // unsigned char unused;
42 // };
43 // };
44
45 } HuffNode;
46
47 typedef struct
48 {
49 long wid;
50 long bits;
51
52 } HuffEncode;
53
54 static HuffItem SymbolCensus[257];
55 static HuffNode TreeNodes[2*257];
56 static int Depths[MAX_DEPTH+1];
57 static HuffEncode EncodingTable[257];
58
59 #define AllocateMemory malloc
60
61
62 /* KJL 17:16:03 17/09/98 - Compression */
63 static void PerformSymbolCensus(unsigned char *sourcePtr, int length);
64 static int __cdecl HuffItemsSortSub(const void *cmp1, const void *cmp2);
65 static void SortCensusData(void);
66 static void BuildHuffmanTree(void);
67 static void MakeHuffTreeFromHuffItems(HuffNode *base, HuffItem *source, int count);
68 static void MakeCodeLengthsFromHuffTree(int *dest, HuffNode *source, int maxdepth);
69 static int HuffDepthsAdjust(int *depth, int maxdepth);
70 static void MakeHuffmanEncodeTable(HuffEncode *encodetable, HuffItem *item, int *depths);
71 static int HuffEncodeBytes(int *dest, unsigned char *source, int count, HuffEncode *table);
72
73
HuffmanCompression(unsigned char * sourcePtr,int length)74 extern HuffmanPackage *HuffmanCompression(unsigned char *sourcePtr, int length)
75 {
76 HuffmanPackage *outpackage;
77
78
79 // Step 1: Perform the symbol census
80 PerformSymbolCensus(sourcePtr,length);
81 // Step 2: Sorting the census data
82 SortCensusData();
83 // Step 3: Building the Huffman tree
84 BuildHuffmanTree();
85 // Step 4: Making the code lengths table
86 MakeCodeLengthsFromHuffTree(Depths, TreeNodes, MAX_DEPTH);
87 // Step 5: Limiting code lengths
88 HuffDepthsAdjust(Depths, MAX_DEPTH);
89 // Step 6: Making the encoding table
90 MakeHuffmanEncodeTable(EncodingTable,&SymbolCensus[256],Depths);
91 // Step 7: Encoding data
92 outpackage = (HuffmanPackage*)AllocateMemory(sizeof(HuffmanPackage)+length);
93 strncpy(outpackage->Identifier,COMPRESSED_RIF_IDENTIFIER,8);
94 outpackage->CompressedDataSize = HuffEncodeBytes((int*)(outpackage+1), sourcePtr, length, EncodingTable);
95 outpackage->UncompressedDataSize = length;
96 for (int n = 0; n < MAX_DEPTH; n++)
97 {
98 outpackage->CodelengthCount[n] = Depths[n + 1];
99 }
100 for (int n = 0; n < 256; n++)
101 {
102 outpackage->ByteAssignment[n] = SymbolCensus[n + 1].Symbol;
103 }
104 return outpackage;
105 }
106
PerformSymbolCensus(unsigned char * sourcePtr,int length)107 static void PerformSymbolCensus(unsigned char *sourcePtr, int length)
108 {
109 // init array
110 for (int i=0; i<257; i++)
111 {
112 SymbolCensus[i].Symbol = i;
113 SymbolCensus[i].Count = 0;
114 }
115
116 // count 'em
117 do
118 {
119 SymbolCensus[*sourcePtr++].Count++;
120 }
121 while (--length);
122 }
123
HuffItemsSortSub(const void * cmp1,const void * cmp2)124 static int __cdecl HuffItemsSortSub(const void *cmp1, const void *cmp2)
125 {
126 if (((HuffItem *)cmp1)->Count > ((HuffItem *)cmp2)->Count)
127 return 1;
128 if (((HuffItem *)cmp1)->Count < ((HuffItem *)cmp2)->Count)
129 return -1;
130 return 0;
131 }
SortCensusData(void)132 static void SortCensusData(void)
133 {
134 qsort(SymbolCensus, 257, sizeof(HuffItem), HuffItemsSortSub);
135 }
136
BuildHuffmanTree(void)137 static void BuildHuffmanTree(void)
138 {
139 MakeHuffTreeFromHuffItems(TreeNodes,SymbolCensus,257);
140 }
141
MakeHuffTreeFromHuffItems(HuffNode * base,HuffItem * source,int count)142 static void MakeHuffTreeFromHuffItems(HuffNode *base, HuffItem *source, int count)
143 {
144 HuffNode *movdest, *temp;
145 int n, upperlim, lowerlim, index;
146 unsigned int sum;
147
148 if (!count) return;
149
150 movdest = base + 1;
151 temp = base + count;
152 memset(temp, 0, count * sizeof(HuffNode));
153 for (n = 0; n < count; n++)
154 {
155 temp[n].bits = source[n].Count;
156 }
157 while ((upperlim = --count))
158 {
159 if (temp[0].zero)
160 temp[0].zero->parent = temp[0].one->parent = movdest;
161 if (temp[1].zero)
162 temp[1].zero->parent = temp[1].one->parent = movdest + 1;
163 movdest[0] = *temp++;
164 movdest[1] = *temp;
165 sum = movdest[0].bits + movdest[1].bits;
166 lowerlim = 1;
167
168 while (lowerlim != upperlim)
169 {
170 index = (lowerlim + upperlim) >> 1;
171 if (sum >= temp[index].bits)
172 {
173 lowerlim = index + 1;
174 }
175 else
176 {
177 upperlim = index;
178 }
179 }
180 index = lowerlim - 1;
181 memmove(temp, temp + 1, index * sizeof(HuffNode));
182 temp[index].bits = sum;
183 temp[index].zero = movdest;
184 temp[index].one = movdest + 1;
185 movdest += 2;
186 }
187 base[0] = temp[0];
188 if (base[0].zero)
189 base[0].zero->parent = base[0].one->parent = base;
190 }
191
MakeCodeLengthsFromHuffTree(int * dest,HuffNode * source,int maxdepth)192 static void MakeCodeLengthsFromHuffTree(int *dest, HuffNode *source, int maxdepth)
193 {
194 int n, depth;
195 HuffNode *back;
196
197 for (n = 0; n < maxdepth + 1; n++)
198 dest[n] = 0;
199 depth = 0;
200 while (1)
201 {
202 while (source->one)
203 {
204 source = source->one;
205 depth++;
206 }
207
208 if (depth > maxdepth) dest[maxdepth]++;
209 else dest[depth]++;
210
211 do
212 {
213 back = source;
214 source = source->parent;
215 if (!depth--)
216 return;
217 }
218 while (back == source->zero);
219
220 source = source->zero;
221 depth++;
222 }
223 }
224
HuffDepthsAdjust(int * depth,int maxdepth)225 static int HuffDepthsAdjust(int *depth, int maxdepth)
226 {
227 unsigned int n, m, items, sum, goal, gain, busts;
228 unsigned int promotions, excess, hi;
229
230 goal = 1 << maxdepth;
231 for (n = 0, sum = 0, items = 0; n <= (unsigned int)maxdepth; n++)
232 {
233 items += depth[n];
234 sum += (goal >> n) * depth[n];
235 }
236 if (items > goal)
237 return -1; // failure
238 for (n = maxdepth - 1; sum > goal; n--)
239 {
240 if (depth[n])
241 {
242 gain = (1 << (maxdepth - n)) - 1;
243 busts = (sum - goal + gain - 1) / gain;
244 busts = (unsigned int)depth[n] < busts ? depth[n] : busts;
245 depth[n] -= busts;
246 depth[maxdepth] += busts;
247 sum -= busts * gain;
248 }
249 }
250 excess = goal - sum;
251 for (n = 0; excess; n++)
252 {
253 hi = 1 << (maxdepth - n);
254 for (m = n + 1; m <= (unsigned int)maxdepth; m++)
255 {
256 gain = hi - (1 << (maxdepth - m));
257 if (excess < gain)
258 break;
259 if (depth[m])
260 {
261 promotions = excess / gain;
262 promotions = (unsigned int)depth[m] > promotions ? promotions : depth[m];
263 depth[n] += promotions;
264 depth[m] -= promotions;
265 excess -= promotions * gain;
266 }
267 }
268 }
269 return 0; // success
270 }
271
MakeHuffmanEncodeTable(HuffEncode * encodetable,HuffItem * item,int * depths)272 static void MakeHuffmanEncodeTable(HuffEncode *encodetable, HuffItem *item, int *depths)
273 {
274 unsigned int d, bitwidth, depthbit, bt, cur;
275 int *dep;
276
277 dep = depths + 1; // skip depth zero
278 bitwidth = 0; // start from small bitwidths
279 cur = 0; // current bit pattern
280 do
281 {
282 do
283 {
284 bitwidth++; // go deeper
285 depthbit = 1 << (bitwidth - 1); // keep depth marker
286 d = *dep++; // get count here
287 }
288 while (!d); // until count non-zero
289 while (d--)
290 { // for all on this level
291 encodetable[item->Symbol].wid = bitwidth; // record width
292 encodetable[item->Symbol].bits = cur; // record bits
293 item--; // count backwards an item
294 bt = depthbit; // bt is a temp value
295 while (1)
296 {
297 cur ^= bt; // do an add modulo 1
298 if ((cur & bt) || !bt) // break if now a 1
299 break; // or out of bits
300 bt >>= 1; // do next bit position
301 }
302 }
303 }
304 while (cur); // until cur exhausted
305 }
306
HuffEncodeBytes(int * dest,unsigned char * source,int count,HuffEncode * table)307 static int HuffEncodeBytes(int *dest, unsigned char *source, int count, HuffEncode *table)
308 {
309 int *start;
310 int wid, val, available;
311 unsigned int accum, bits;
312 unsigned char *sourcelim, *sourceend;
313
314 if (!count) return 0;
315
316 accum = 0;
317 start = dest;
318 sourcelim = sourceend = source + count;
319 available = 32;
320 if (sourcelim - 32 < sourcelim)
321 {
322 sourcelim -= 32;
323 }
324 else
325 {
326 sourcelim = source;
327 }
328 if (source < sourcelim)
329 {
330 do
331 {
332 goto lpstart;
333 do
334 {
335 accum = (accum >> wid) | (bits << (32 - wid));
336 lpstart: val = *source++;
337 wid = table[val].wid;
338 bits = table[val].bits;
339 }
340 while ((available -= wid) >= 0);
341
342 wid += available;
343 if (wid) accum = (accum >> wid) | (bits << (32 - wid));
344 *dest++ = accum;
345 wid -= available;
346 accum = bits << (32 - wid);
347 available += 32;
348 }
349 while (source < sourcelim);
350 }
351 while (1)
352 {
353 if (source < sourceend)
354 {
355 val = *source++;
356 }
357 else if (source == sourceend)
358 {
359 val = 0x100; // terminator
360 source++;
361 }
362 else break; // done
363
364 wid = table[val].wid;
365 bits = table[val].bits;
366
367 if ((available -= wid) < 0)
368 {
369 wid += available;
370 if (wid)
371 accum = (accum >> wid) | (bits << (32 - wid));
372 *dest++ = accum;
373 wid -= available;
374 accum = bits << (32 - wid);
375 available += 32;
376 }
377 else
378 {
379 accum = (accum >> wid) | (bits << (32 - wid));
380 }
381 }
382 *dest++ = accum >> available;
383 return (int)((dest - start) * 4);
384 }
385
386
387
388
389
390
391 /* KJL 17:16:24 17/09/98 - Decompression */
392 static int DecodeTable[1<<MAX_DEPTH];
393
394 static void MakeHuffmanDecodeTable(const int *depth, int depthmax, const unsigned char *list);
395 static int HuffmanDecode(unsigned char *dest, const int *source, const int *table, int length);
396
397
HuffmanDecompress(const HuffmanPackage * inpackage)398 extern char *HuffmanDecompress(const HuffmanPackage *inpackage)
399 {
400 unsigned char *uncompressedData = NULL;
401 // Step 1: Make the decoding table
402 MakeHuffmanDecodeTable(inpackage->CodelengthCount, MAX_DEPTH, inpackage->ByteAssignment);
403
404 // Step 2: Decode data
405 uncompressedData = (unsigned char*)AllocateMemory(inpackage->UncompressedDataSize+16);
406 if (uncompressedData)
407 {
408 HuffmanDecode(uncompressedData,(int*)(inpackage+1),DecodeTable,inpackage->UncompressedDataSize);
409 }
410
411 return (char*)uncompressedData;
412 }
413
MakeHuffmanDecodeTable(const int * depth,int depthmax,const unsigned char * list)414 static void MakeHuffmanDecodeTable(const int *depth, int depthmax, const unsigned char *list)
415 {
416 int thisdepth, depthbit, repcount, repspace, lenbits, temp, count;
417 int *outp;
418 int o = 0;
419 const unsigned char *p;
420 int *outtbl = DecodeTable;
421
422 lenbits = 0;
423 repcount = 1 << depthmax;
424 repspace = 1;
425 thisdepth = 0;
426 depthbit = 4;
427 p = list + 255;
428 while (1)
429 {
430 do
431 {
432 lenbits++;
433 depthbit <<= 1;
434 repspace <<= 1;
435 repcount >>= 1;
436 }
437 while (!(thisdepth = *depth++));
438 do
439 {
440 if (p < list)
441 {
442 temp = 0xff;
443 }
444 else
445 {
446 temp = lenbits | (*p-- << 8);
447 }
448 outp = outtbl + (o >> 2);
449 count = repcount;
450 do
451 {
452 *outp = temp;
453 outp += repspace;
454 }
455 while (--count);
456 temp = depthbit;
457 do
458 {
459 temp >>= 1;
460 if (temp & 3) return;
461 o ^= temp;
462 }
463 while (!(o & temp));
464 }
465 while (--thisdepth);
466 }
467 }
468
469
470 #define EDXMASK ((((1 << (MAX_DEPTH + 1)) - 1) ^ 1) ^ -1)
471
HuffmanDecode(unsigned char * dest,const int * source,const int * table,int length)472 static int HuffmanDecode(unsigned char *dest, const int *source, const int *table, int length)
473 {
474 unsigned char *start;
475 int available, reserve, fill, wid;
476 unsigned int bits=0, resbits;
477 const unsigned char *p;
478
479 start = dest;
480 available = 0;
481 reserve = 0;
482 wid = 0;
483 resbits = 0;
484 do
485 {
486 available += wid;
487 fill = 31 - available;
488 bits <<= fill;
489 if (fill > reserve)
490 {
491 fill -= reserve;
492 available += reserve;
493 if (reserve)
494 {
495 bits = (bits >> reserve) | (resbits << (32 - reserve));
496 }
497 resbits = *source++;
498 reserve = 32;
499 }
500 bits = (bits >> fill) | (resbits << (32 - fill));
501 resbits >>= fill;
502 reserve -= fill;
503 available = 31;
504 goto lpent;
505 do
506 {
507 bits >>= wid;
508 *dest++ = p[1];
509 lpent: p = (const unsigned char *)(((const short *)table)+(bits & ~EDXMASK));
510 }
511 while ((available -= (wid = *p)) >= 0 && (dest-start)!=length);
512
513 }
514 while (available > -32 && (dest-start)!=length);
515 return (int)(dest - start);
516 }
517