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