1/* Compress/HuffmanEncode.c */ 2 3#include "HuffmanEncode.h" 4#include "../../Sort.h" 5 6#define kMaxLen 16 7#define NUM_BITS 10 8#define MASK ((1 << NUM_BITS) - 1) 9 10#define NUM_COUNTERS 64 11 12/* use BLOCK_SORT_EXTERNAL_FLAGS if blockSize > 1M */ 13#define HUFFMAN_SPEED_OPT 14 15void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 numSymbols, UInt32 maxLen) 16{ 17 UInt32 num = 0; 18 /* if (maxLen > 10) maxLen = 10; */ 19 { 20 UInt32 i; 21 22 #ifdef HUFFMAN_SPEED_OPT 23 24 UInt32 counters[NUM_COUNTERS]; 25 for (i = 0; i < NUM_COUNTERS; i++) 26 counters[i] = 0; 27 for (i = 0; i < numSymbols; i++) 28 { 29 UInt32 freq = freqs[i]; 30 counters[(freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1]++; 31 } 32 33 for (i = 1; i < NUM_COUNTERS; i++) 34 { 35 UInt32 temp = counters[i]; 36 counters[i] = num; 37 num += temp; 38 } 39 40 for (i = 0; i < numSymbols; i++) 41 { 42 UInt32 freq = freqs[i]; 43 if (freq == 0) 44 lens[i] = 0; 45 else 46 p[counters[((freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1)]++] = i | (freq << NUM_BITS); 47 } 48 counters[0] = 0; 49 HeapSort(p + counters[NUM_COUNTERS - 2], counters[NUM_COUNTERS - 1] - counters[NUM_COUNTERS - 2]); 50 51 #else 52 53 for (i = 0; i < numSymbols; i++) 54 { 55 UInt32 freq = freqs[i]; 56 if (freq == 0) 57 lens[i] = 0; 58 else 59 p[num++] = i | (freq << NUM_BITS); 60 } 61 HeapSort(p, num); 62 63 #endif 64 } 65 66 if (num < 2) 67 { 68 int minCode = 0; 69 int maxCode = 1; 70 if (num == 1) 71 { 72 maxCode = p[0] & MASK; 73 if (maxCode == 0) 74 maxCode++; 75 } 76 p[minCode] = 0; 77 p[maxCode] = 1; 78 lens[minCode] = lens[maxCode] = 1; 79 return; 80 } 81 82 { 83 UInt32 b, e, i; 84 85 i = b = e = 0; 86 do 87 { 88 UInt32 n, m, freq; 89 n = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++; 90 freq = (p[n] & ~MASK); 91 p[n] = (p[n] & MASK) | (e << NUM_BITS); 92 m = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++; 93 freq += (p[m] & ~MASK); 94 p[m] = (p[m] & MASK) | (e << NUM_BITS); 95 p[e] = (p[e] & MASK) | freq; 96 e++; 97 } 98 while (num - e > 1); 99 100 { 101 UInt32 lenCounters[kMaxLen + 1]; 102 for (i = 0; i <= kMaxLen; i++) 103 lenCounters[i] = 0; 104 105 p[--e] &= MASK; 106 lenCounters[1] = 2; 107 while (e > 0) 108 { 109 UInt32 len = (p[p[--e] >> NUM_BITS] >> NUM_BITS) + 1; 110 p[e] = (p[e] & MASK) | (len << NUM_BITS); 111 if (len >= maxLen) 112 for (len = maxLen - 1; lenCounters[len] == 0; len--); 113 lenCounters[len]--; 114 lenCounters[len + 1] += 2; 115 } 116 117 { 118 UInt32 len; 119 i = 0; 120 for (len = maxLen; len != 0; len--) 121 { 122 UInt32 num; 123 for (num = lenCounters[len]; num != 0; num--) 124 lens[p[i++] & MASK] = (Byte)len; 125 } 126 } 127 128 { 129 UInt32 nextCodes[kMaxLen + 1]; 130 { 131 UInt32 code = 0; 132 UInt32 len; 133 for (len = 1; len <= kMaxLen; len++) 134 nextCodes[len] = code = (code + lenCounters[len - 1]) << 1; 135 } 136 /* if (code + lenCounters[kMaxLen] - 1 != (1 << kMaxLen) - 1) throw 1; */ 137 138 { 139 UInt32 i; 140 for (i = 0; i < numSymbols; i++) 141 p[i] = nextCodes[lens[i]]++; 142 } 143 } 144 } 145 } 146} 147