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 |
|
15 void 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 } |
|