File Coverage

cpan/Compress-Raw-Bzip2/huffman.c
Criterion Covered Total %
statement 49 53 92.5
branch n/a
condition n/a
subroutine n/a
total 49 53 92.5


line stmt bran cond sub 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.6 of 6 September 2010
12           Copyright (C) 1996-2010 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 8376         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 203472         for (i = 0; i < alphaSize; i++)
80 195096         weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
81            
82           while (True) {
83            
84           nNodes = alphaSize;
85           nHeap = 0;
86            
87 8376         heap[0] = 0;
88 8376         weight[0] = 0;
89 8376         parent[0] = -2;
90            
91 203472         for (i = 1; i <= alphaSize; i++) {
92 195096         parent[i] = -1;
93 195096         nHeap++;
94 195096         heap[nHeap] = i;
95 195096         UPHEAP(nHeap);
96           }
97            
98 8376         AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
99          
100 195096         while (nHeap > 1) {
101 186720         n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
102 186720         n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
103 186720         nNodes++;
104 186720         parent[n1] = parent[n2] = nNodes;
105 186720         weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
106 186720         parent[nNodes] = -1;
107           nHeap++;
108 186720         heap[nHeap] = nNodes;
109 186720         UPHEAP(nHeap);
110           }
111            
112 8376         AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
113            
114           tooLong = False;
115 195096         for (i = 1; i <= alphaSize; i++) {
116           j = 0;
117           k = i;
118 1149264         while (parent[k] >= 0) { k = parent[k]; j++; }
119 195096         len[i-1] = j;
120 195096         if (j > maxLen) tooLong = True;
121           }
122          
123 8376         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         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           }
148 8376         }
149            
150            
151           /*---------------------------------------------------*/
152 2094         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           vec = 0;
161 8044         for (n = minLen; n <= maxLen; n++) {
162 194678         for (i = 0; i < alphaSize; i++)
163 194678         if (length[i] == n) { code[i] = vec; vec++; };
164 5950         vec <<= 1;
165           }
166 2094         }
167            
168            
169           /*---------------------------------------------------*/
170 7522         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           pp = 0;
181 31554         for (i = minLen; i <= maxLen; i++)
182 622526         for (j = 0; j < alphaSize; j++)
183 622526         if (length[j] == i) { perm[pp] = j; pp++; };
184            
185 173006         for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
186 164512         for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
187            
188 165484         for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
189            
190 173006         for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
191           vec = 0;
192            
193 24032         for (i = minLen; i <= maxLen; i++) {
194 24032         vec += (base[i+1] - base[i]);
195 24032         limit[i] = vec-1;
196 24032         vec <<= 1;
197           }
198 24032         for (i = minLen + 1; i <= maxLen; i++)
199 16510         base[i] = ((limit[i-1] + 1) << 1) - base[i];
200 7522         }
201            
202            
203           /*-------------------------------------------------------------*/
204           /*--- end huffman.c ---*/
205           /*-------------------------------------------------------------*/