huffman.c

filter: Statementstmt 93.5% 58 / 62 Branchbran 90.9% 60 / 66 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.1% 118 / 128 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blocksort.c ↑ Summary compress.c »
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 <jseward@acm.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 /*---------------------------------------------------*/
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 ▶ for (i = 0; i < alphaSize; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < alphaSize; i++) 21008 220 21228
80 21008 ▶ weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
Branch: 1 branch
BranchTrueFalseTotal
weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8; 18701 2307 21008
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 ▶ for (i = 1; i <= alphaSize; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i <= alphaSize; i++) { 21008 220 21228
92 21008 parent[i] = -1;
93 21008 nHeap++;
94 21008 heap[nHeap] = i;
95 37636 ▶ UPHEAP(nHeap);
Branch: 1 branch
BranchTrueFalseTotal
UPHEAP(nHeap); 16628 21008 37636
96 }
97  
98 220 ▶ AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
Branch: 1 branch
BranchTrueFalseTotal
AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 ); 0 220 220
99  
100 21008 ▶ while (nHeap > 1) {
Branch: 1 branch
BranchTrueFalseTotal
while (nHeap > 1) { 20788 220 21008
101 128238 ▶ n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
Branch: 4 branches
BranchTrueFalseTotal
n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 19580 108658 128238
n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 107365 1293 108658
n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 48499 58866 107365
n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 1208 107450 108658
102 123219 ▶ n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
Branch: 4 branches
BranchTrueFalseTotal
n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 16477 106742 123219
n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 105494 1248 106742
n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 48134 57360 105494
n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 4311 102431 106742
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 21857 ▶ UPHEAP(nHeap);
Branch: 1 branch
BranchTrueFalseTotal
UPHEAP(nHeap); 1069 20788 21857
110 }
111  
112 220 ▶ AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
Branch: 1 branch
BranchTrueFalseTotal
AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 ); 0 220 220
113  
114 220 tooLong = False;
115 21228 ▶ for (i = 1; i <= alphaSize; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i <= alphaSize; i++) { 21008 220 21228
116 21008 j = 0;
117 21008 k = i;
118 183349 ▶ while (parent[k] >= 0) { k = parent[k]; j++; }
Branch: 1 branch
BranchTrueFalseTotal
while (parent[k] >= 0) { k = parent[k]; j++; } 162341 21008 183349
119 21008 len[i-1] = j;
120 21008 ▶ if (j > maxLen) tooLong = True;
Branch: 1 branch
BranchTrueFalseTotal
if (j > maxLen) tooLong = True; 0 21008 21008
121 }
122  
123 220 ▶ if (! tooLong) break;
Branch: 1 branch
BranchTrueFalseTotal
if (! tooLong) break; 220 0 220
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 ▶ for (i = 1; i <= alphaSize; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i <= alphaSize; i++) { 0 0 0
143 0 j = weight[i] >> 8;
144 0 j = 1 + (j / 2);
145 0 weight[i] = j << 8;
146 }
147 }
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 238 ▶ for (n = minLen; n <= maxLen; n++) {
Branch: 1 branch
BranchTrueFalseTotal
for (n = minLen; n <= maxLen; n++) { 183 55 238
162 23481 ▶ for (i = 0; i < alphaSize; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < alphaSize; i++) 23298 183 23481
163 23298 ▶ if (length[i] == n) { code[i] = vec; vec++; };
Branch: 1 branch
BranchTrueFalseTotal
if (length[i] == n) { code[i] = vec; vec++; }; 5252 18046 23298
164 183 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 369 ▶ for (i = minLen; i <= maxLen; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = minLen; i <= maxLen; i++) 288 81 369
182 33602 ▶ for (j = 0; j < alphaSize; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < alphaSize; j++) 33314 288 33602
183 33314 ▶ if (length[j] == i) { perm[pp] = j; pp++; };
Branch: 1 branch
BranchTrueFalseTotal
if (length[j] == i) { perm[pp] = j; pp++; }; 7154 26160 33314
184  
185 1944 ▶ for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0; 1863 81 1944
186 7235 ▶ for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < alphaSize; i++) base[length[i]+1]++; 7154 81 7235
187  
188 1863 ▶ for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1]; 1782 81 1863
189  
190 1944 ▶ for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0; 1863 81 1944
191 81 vec = 0;
192  
193 369 ▶ for (i = minLen; i <= maxLen; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = minLen; i <= maxLen; i++) { 288 81 369
194 288 vec += (base[i+1] - base[i]);
195 288 limit[i] = vec-1;
196 288 vec <<= 1;
197 }
198 288 ▶ for (i = minLen + 1; i <= maxLen; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = minLen + 1; i <= maxLen; i++) 207 81 288
199 207 base[i] = ((limit[i-1] + 1) << 1) - base[i];
200 81 }
201  
202  
203 /*-------------------------------------------------------------*/
204 /*--- end huffman.c ---*/
205 /*-------------------------------------------------------------*/
« blocksort.c ↑ Summary compress.c »