1
2/*-------------------------------------------------------------*/
3/*--- Huffman coding low-level stuff                        ---*/
4/*---                                             huffman.c ---*/
5/*-------------------------------------------------------------*/
6
7/* ------------------------------------------------------------------
8   This file is part of bzip2/libbzip2, a program and library for
9   lossless, block-sorting data compression.
10
11   bzip2/libbzip2 version 1.0.6 of 6 September 2010
12   Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
13
14   Please read the WARNING, DISCLAIMER and PATENTS sections in the
15   README file.
16
17   This program is released under the terms of the license contained
18   in the file LICENSE.
19   ------------------------------------------------------------------ */
20
21
22#include "bzlib_private.h"
23
24/*---------------------------------------------------*/
25#define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
26#define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
27#define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
28
29#define ADDWEIGHTS(zw1,zw2)                           \
30   (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
31   (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
32
33#define UPHEAP(z)                                     \
34{                                                     \
35   Int32 zz, tmp;                                     \
36   zz = z; tmp = heap[zz];                            \
37   while (weight[tmp] < weight[heap[zz >> 1]]) {      \
38      heap[zz] = heap[zz >> 1];                       \
39      zz >>= 1;                                       \
40   }                                                  \
41   heap[zz] = tmp;                                    \
42}
43
44#define DOWNHEAP(z)                                   \
45{                                                     \
46   Int32 zz, yy, tmp;                                 \
47   zz = z; tmp = heap[zz];                            \
48   while (True) {                                     \
49      yy = zz << 1;                                   \
50      if (yy > nHeap) break;                          \
51      if (yy < nHeap &&                               \
52          weight[heap[yy+1]] < weight[heap[yy]])      \
53         yy++;                                        \
54      if (weight[tmp] < weight[heap[yy]]) break;      \
55      heap[zz] = heap[yy];                            \
56      zz = yy;                                        \
57   }                                                  \
58   heap[zz] = tmp;                                    \
59}
60
61
62/*---------------------------------------------------*/
63void BZ2_hbMakeCodeLengths ( UChar *len,
64                             Int32 *freq,
65                             Int32 alphaSize,
66                             Int32 maxLen )
67{
68   /*--
69      Nodes and heap entries run from 1.  Entry 0
70      for both the heap and nodes is a sentinel.
71   --*/
72   Int32 nNodes, nHeap, n1, n2, i, j, k;
73   Bool  tooLong;
74
75   Int32 heap   [ BZ_MAX_ALPHA_SIZE + 2 ];
76   Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
77   Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
78
79   for (i = 0; i < alphaSize; i++)
80      weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
81
82   while (True) {
83
84      nNodes = alphaSize;
85      nHeap = 0;
86
87      heap[0] = 0;
88      weight[0] = 0;
89      parent[0] = -2;
90
91      for (i = 1; i <= alphaSize; i++) {
92         parent[i] = -1;
93         nHeap++;
94         heap[nHeap] = i;
95         UPHEAP(nHeap);
96      }
97
98      AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
99
100      while (nHeap > 1) {
101         n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
102         n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
103         nNodes++;
104         parent[n1] = parent[n2] = nNodes;
105         weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
106         parent[nNodes] = -1;
107         nHeap++;
108         heap[nHeap] = nNodes;
109         UPHEAP(nHeap);
110      }
111
112      AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
113
114      tooLong = False;
115      for (i = 1; i <= alphaSize; i++) {
116         j = 0;
117         k = i;
118         while (parent[k] >= 0) { k = parent[k]; j++; }
119         len[i-1] = j;
120         if (j > maxLen) tooLong = True;
121      }
122
123      if (! tooLong) break;
124
125      /* 17 Oct 04: keep-going condition for the following loop used
126         to be 'i < alphaSize', which missed the last element,
127         theoretically leading to the possibility of the compressor
128         looping.  However, this count-scaling step is only needed if
129         one of the generated Huffman code words is longer than
130         maxLen, which up to and including version 1.0.2 was 20 bits,
131         which is extremely unlikely.  In version 1.0.3 maxLen was
132         changed to 17 bits, which has minimal effect on compression
133         ratio, but does mean this scaling step is used from time to
134         time, enough to verify that it works.
135
136         This means that bzip2-1.0.3 and later will only produce
137         Huffman codes with a maximum length of 17 bits.  However, in
138         order to preserve backwards compatibility with bitstreams
139         produced by versions pre-1.0.3, the decompressor must still
140         handle lengths of up to 20. */
141
142      for (i = 1; i <= alphaSize; i++) {
143         j = weight[i] >> 8;
144         j = 1 + (j / 2);
145         weight[i] = j << 8;
146      }
147   }
148}
149
150
151/*---------------------------------------------------*/
152void BZ2_hbAssignCodes ( Int32 *code,
153                         UChar *length,
154                         Int32 minLen,
155                         Int32 maxLen,
156                         Int32 alphaSize )
157{
158   Int32 n, vec, i;
159
160   vec = 0;
161   for (n = minLen; n <= maxLen; n++) {
162      for (i = 0; i < alphaSize; i++)
163         if (length[i] == n) { code[i] = vec; vec++; };
164      vec <<= 1;
165   }
166}
167
168
169/*---------------------------------------------------*/
170void BZ2_hbCreateDecodeTables ( Int32 *limit,
171                                Int32 *base,
172                                Int32 *perm,
173                                UChar *length,
174                                Int32 minLen,
175                                Int32 maxLen,
176                                Int32 alphaSize )
177{
178   Int32 pp, i, j, vec;
179
180   pp = 0;
181   for (i = minLen; i <= maxLen; i++)
182      for (j = 0; j < alphaSize; j++)
183         if (length[j] == i) { perm[pp] = j; pp++; };
184
185   for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
186   for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
187
188   for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
189
190   for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
191   vec = 0;
192
193   for (i = minLen; i <= maxLen; i++) {
194      vec += (base[i+1] - base[i]);
195      limit[i] = vec-1;
196      vec <<= 1;
197   }
198   for (i = minLen + 1; i <= maxLen; i++)
199      base[i] = ((limit[i-1] + 1) << 1) - base[i];
200}
201
202
203/*-------------------------------------------------------------*/
204/*--- end                                         huffman.c ---*/
205/*-------------------------------------------------------------*/
206