2 * bzip2 is written by Julian Seward <jseward@bzip.org>.
3 * Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>.
4 * See README and LICENSE files in this directory for more information.
7 /*-------------------------------------------------------------*/
8 /*--- Huffman coding low-level stuff ---*/
10 /*-------------------------------------------------------------*/
12 /* ------------------------------------------------------------------
13 This file is part of bzip2/libbzip2, a program and library for
14 lossless, block-sorting data compression.
16 bzip2/libbzip2 version 1.0.4 of 20 December 2006
17 Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
19 Please read the WARNING, DISCLAIMER and PATENTS sections in the
22 This program is released under the terms of the license contained
24 ------------------------------------------------------------------ */
26 /* #include "bzlib_private.h" */
28 /*---------------------------------------------------*/
29 #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
30 #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
31 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
33 #define ADDWEIGHTS(zw1,zw2) \
34 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
35 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
42 while (weight[tmp] < weight[heap[zz >> 1]]) { \
43 heap[zz] = heap[zz >> 1]; \
50 /* 90 bytes, 0.3% of overall compress speed */
51 #if CONFIG_BZIP2_FEATURE_SPEED >= 1
53 /* macro works better than inline (gcc 4.2.1) */
54 #define DOWNHEAP1(heap, weight, Heap) \
56 int32_t zz, yy, tmp; \
64 && weight[heap[yy+1]] < weight[heap[yy]]) \
66 if (weight[tmp] < weight[heap[yy]]) \
68 heap[zz] = heap[yy]; \
77 void DOWNHEAP1(int32_t *heap, int32_t *weight, int32_t nHeap)
87 && weight[heap[yy + 1]] < weight[heap[yy]])
89 if (weight[tmp] < weight[heap[yy]])
99 /*---------------------------------------------------*/
101 void BZ2_hbMakeCodeLengths(uint8_t *len,
107 * Nodes and heap entries run from 1. Entry 0
108 * for both the heap and nodes is a sentinel.
110 int32_t nNodes, nHeap, n1, n2, i, j, k;
113 int32_t heap [BZ_MAX_ALPHA_SIZE + 2];
114 int32_t weight[BZ_MAX_ALPHA_SIZE * 2];
115 int32_t parent[BZ_MAX_ALPHA_SIZE * 2];
117 for (i = 0; i < alphaSize; i++)
118 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
128 for (i = 1; i <= alphaSize; i++) {
135 AssertH(nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001);
138 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP1(heap, weight, nHeap);
139 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP1(heap, weight, nHeap);
141 parent[n1] = parent[n2] = nNodes;
142 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
145 heap[nHeap] = nNodes;
149 AssertH(nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002);
152 for (i = 1; i <= alphaSize; i++) {
155 while (parent[k] >= 0) {
167 /* 17 Oct 04: keep-going condition for the following loop used
168 to be 'i < alphaSize', which missed the last element,
169 theoretically leading to the possibility of the compressor
170 looping. However, this count-scaling step is only needed if
171 one of the generated Huffman code words is longer than
172 maxLen, which up to and including version 1.0.2 was 20 bits,
173 which is extremely unlikely. In version 1.0.3 maxLen was
174 changed to 17 bits, which has minimal effect on compression
175 ratio, but does mean this scaling step is used from time to
176 time, enough to verify that it works.
178 This means that bzip2-1.0.3 and later will only produce
179 Huffman codes with a maximum length of 17 bits. However, in
180 order to preserve backwards compatibility with bitstreams
181 produced by versions pre-1.0.3, the decompressor must still
182 handle lengths of up to 20. */
184 for (i = 1; i <= alphaSize; i++) {
193 /*---------------------------------------------------*/
195 void BZ2_hbAssignCodes(int32_t *code,
204 for (n = minLen; n <= maxLen; n++) {
205 for (i = 0; i < alphaSize; i++) {
206 if (length[i] == n) {
216 /*-------------------------------------------------------------*/
217 /*--- end huffman.c ---*/
218 /*-------------------------------------------------------------*/