/[pcsx2_0.9.7]/trunk/3rdparty/bzip2/huffman.c
ViewVC logotype

Annotation of /trunk/3rdparty/bzip2/huffman.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (hide annotations) (download)
Mon Sep 6 11:40:06 2010 UTC (9 years, 9 months ago) by william
File MIME type: text/plain
File size: 7184 byte(s)
exported r3113 from ./upstream/trunk
1 william 10
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.4 of 20 December 2006
12     Copyright (C) 1996-2006 Julian Seward <jseward@bzip.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     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     for (i = 0; i < alphaSize; i++)
80     weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
81    
82     while (True) {
83    
84     nNodes = alphaSize;
85     nHeap = 0;
86    
87     heap[0] = 0;
88     weight[0] = 0;
89     parent[0] = -2;
90    
91     for (i = 1; i <= alphaSize; i++) {
92     parent[i] = -1;
93     nHeap++;
94     heap[nHeap] = i;
95     UPHEAP(nHeap);
96     }
97    
98     AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
99    
100     while (nHeap > 1) {
101     n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
102     n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
103     nNodes++;
104     parent[n1] = parent[n2] = nNodes;
105     weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
106     parent[nNodes] = -1;
107     nHeap++;
108     heap[nHeap] = nNodes;
109     UPHEAP(nHeap);
110     }
111    
112     AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
113    
114     tooLong = False;
115     for (i = 1; i <= alphaSize; i++) {
116     j = 0;
117     k = i;
118     while (parent[k] >= 0) { k = parent[k]; j++; }
119     len[i-1] = j;
120     if (j > maxLen) tooLong = True;
121     }
122    
123     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     for (i = 1; i <= alphaSize; i++) {
143     j = weight[i] >> 8;
144     j = 1 + (j / 2);
145     weight[i] = j << 8;
146     }
147     }
148     }
149    
150    
151     /*---------------------------------------------------*/
152     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     for (n = minLen; n <= maxLen; n++) {
162     for (i = 0; i < alphaSize; i++)
163     if (length[i] == n) { code[i] = vec; vec++; };
164     vec <<= 1;
165     }
166     }
167    
168    
169     /*---------------------------------------------------*/
170     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     for (i = minLen; i <= maxLen; i++)
182     for (j = 0; j < alphaSize; j++)
183     if (length[j] == i) { perm[pp] = j; pp++; };
184    
185     for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
186     for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
187    
188     for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
189    
190     for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
191     vec = 0;
192    
193     for (i = minLen; i <= maxLen; i++) {
194     vec += (base[i+1] - base[i]);
195     limit[i] = vec-1;
196     vec <<= 1;
197     }
198     for (i = minLen + 1; i <= maxLen; i++)
199     base[i] = ((limit[i-1] + 1) << 1) - base[i];
200     }
201    
202    
203     /*-------------------------------------------------------------*/
204     /*--- end huffman.c ---*/
205     /*-------------------------------------------------------------*/

  ViewVC Help
Powered by ViewVC 1.1.22