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