File Coverage

huffman.c
Criterion Covered Total %
statement 58 63 92.0
branch 60 66 90.9
condition n/a
subroutine n/a
pod n/a
total 118 129 91.4


line stmt bran cond sub pod time code
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.8 of 13 July 2019
12             Copyright (C) 1996-2019 Julian Seward
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             /*---------------------------------------------------*/
63 220           void 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 21228 100         for (i = 0; i < alphaSize; i++)
80 21008 100         weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
81              
82             while (True) {
83              
84 220           nNodes = alphaSize;
85 220           nHeap = 0;
86              
87 220           heap[0] = 0;
88 220           weight[0] = 0;
89 220           parent[0] = -2;
90              
91 21228 100         for (i = 1; i <= alphaSize; i++) {
92 21008           parent[i] = -1;
93 21008           nHeap++;
94 21008           heap[nHeap] = i;
95 37617 100         UPHEAP(nHeap);
96             }
97              
98 220 50         AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
99              
100 21008 100         while (nHeap > 1) {
101 128024 100         n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
    100          
    100          
    100          
102 123415 100         n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
    100          
    100          
    100          
103 20788           nNodes++;
104 20788           parent[n1] = parent[n2] = nNodes;
105 20788           weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
106 20788           parent[nNodes] = -1;
107 20788           nHeap++;
108 20788           heap[nHeap] = nNodes;
109 21814 100         UPHEAP(nHeap);
110             }
111              
112 220 50         AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
113              
114 220           tooLong = False;
115 21228 100         for (i = 1; i <= alphaSize; i++) {
116 21008           j = 0;
117 21008           k = i;
118 183483 100         while (parent[k] >= 0) { k = parent[k]; j++; }
119 21008           len[i-1] = j;
120 21008 50         if (j > maxLen) tooLong = True;
121             }
122              
123 220 50         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 0 0         for (i = 1; i <= alphaSize; i++) {
143 0           j = weight[i] >> 8;
144 0           j = 1 + (j / 2);
145 0           weight[i] = j << 8;
146             }
147 0           }
148 220           }
149              
150              
151             /*---------------------------------------------------*/
152 55           void BZ2_hbAssignCodes ( Int32 *code,
153             UChar *length,
154             Int32 minLen,
155             Int32 maxLen,
156             Int32 alphaSize )
157             {
158             Int32 n, vec, i;
159              
160 55           vec = 0;
161 242 100         for (n = minLen; n <= maxLen; n++) {
162 24513 100         for (i = 0; i < alphaSize; i++)
163 24326 100         if (length[i] == n) { code[i] = vec; vec++; };
164 187           vec <<= 1;
165             }
166 55           }
167              
168              
169             /*---------------------------------------------------*/
170 81           void 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 81           pp = 0;
181 374 100         for (i = minLen; i <= maxLen; i++)
182 34892 100         for (j = 0; j < alphaSize; j++)
183 34599 100         if (length[j] == i) { perm[pp] = j; pp++; };
184              
185 1944 100         for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
186 7235 100         for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
187              
188 1863 100         for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
189              
190 1944 100         for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
191 81           vec = 0;
192              
193 374 100         for (i = minLen; i <= maxLen; i++) {
194 293           vec += (base[i+1] - base[i]);
195 293           limit[i] = vec-1;
196 293           vec <<= 1;
197             }
198 293 100         for (i = minLen + 1; i <= maxLen; i++)
199 212           base[i] = ((limit[i-1] + 1) << 1) - base[i];
200 81           }
201              
202              
203             /*-------------------------------------------------------------*/
204             /*--- end huffman.c ---*/
205             /*-------------------------------------------------------------*/