2
/*-------------------------------------------------------------*/
3
/*--- Huffman coding low-level stuff ---*/
5
/*-------------------------------------------------------------*/
7
/* ------------------------------------------------------------------
8
This file is part of bzip2/libbzip2, a program and library for
9
lossless, block-sorting data compression.
11
bzip2/libbzip2 version 1.0.6 of 6 September 2010
12
Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
14
Please read the WARNING, DISCLAIMER and PATENTS sections in the
17
This program is released under the terms of the license contained
19
------------------------------------------------------------------ */
22
#include "bzlib_private.h"
24
/*---------------------------------------------------*/
25
#define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
26
#define DEPTHOF(zz1) ((zz1) & 0x000000ff)
27
#define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
29
#define ADDWEIGHTS(zw1,zw2) \
30
(WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
31
(1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
36
zz = z; tmp = heap[zz]; \
37
while (weight[tmp] < weight[heap[zz >> 1]]) { \
38
heap[zz] = heap[zz >> 1]; \
47
zz = z; tmp = heap[zz]; \
50
if (yy > nHeap) break; \
52
weight[heap[yy+1]] < weight[heap[yy]]) \
54
if (weight[tmp] < weight[heap[yy]]) break; \
55
heap[zz] = heap[yy]; \
62
/*---------------------------------------------------*/
63
void BZ2_hbMakeCodeLengths ( UChar *len,
69
Nodes and heap entries run from 1. Entry 0
70
for both the heap and nodes is a sentinel.
72
Int32 nNodes, nHeap, n1, n2, i, j, k;
75
Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
76
Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
77
Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
79
for (i = 0; i < alphaSize; i++)
80
weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
91
for (i = 1; i <= alphaSize; i++) {
98
AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
101
n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
102
n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
104
parent[n1] = parent[n2] = nNodes;
105
weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
108
heap[nHeap] = nNodes;
112
AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
115
for (i = 1; i <= alphaSize; i++) {
118
while (parent[k] >= 0) { k = parent[k]; j++; }
120
if (j > maxLen) tooLong = True;
123
if (! tooLong) break;
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.
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. */
142
for (i = 1; i <= alphaSize; i++) {
151
/*---------------------------------------------------*/
152
void BZ2_hbAssignCodes ( Int32 *code,
161
for (n = minLen; n <= maxLen; n++) {
162
for (i = 0; i < alphaSize; i++)
163
if (length[i] == n) { code[i] = vec; vec++; };
169
/*---------------------------------------------------*/
170
void BZ2_hbCreateDecodeTables ( Int32 *limit,
181
for (i = minLen; i <= maxLen; i++)
182
for (j = 0; j < alphaSize; j++)
183
if (length[j] == i) { perm[pp] = j; pp++; };
185
for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
186
for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
188
for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
190
for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
193
for (i = minLen; i <= maxLen; i++) {
194
vec += (base[i+1] - base[i]);
198
for (i = minLen + 1; i <= maxLen; i++)
199
base[i] = ((limit[i-1] + 1) << 1) - base[i];
203
/*-------------------------------------------------------------*/
204
/*--- end huffman.c ---*/
205
/*-------------------------------------------------------------*/