op public repos

Blob

Date:: Wed Apr 14 20:09:21 2004 UTC
Message:: add gzip, bzip2 '
Actions:: History | Blame | Raw File
1 
2 /*-------------------------------------------------------------*/
3 /*--- Huffman coding low-level stuff                        ---*/
4 /*---                                             huffman.c ---*/
5 /*-------------------------------------------------------------*/
6 
7 /*--
8   This file is a part of bzip2 and/or libbzip2, a program and
9   library for lossless, block-sorting data compression.
10 
11   Copyright (C) 1996-2000 Julian R Seward.  All rights reserved.
12 
13   Redistribution and use in source and binary forms, with or without
14   modification, are permitted provided that the following conditions
15   are met:
16 
17   1. Redistributions of source code must retain the above copyright
18      notice, this list of conditions and the following disclaimer.
19 
20   2. The origin of this software must not be misrepresented; you must 
21      not claim that you wrote the original software.  If you use this 
22      software in a product, an acknowledgment in the product 
23      documentation would be appreciated but is not required.
24 
25   3. Altered source versions must be plainly marked as such, and must
26      not be misrepresented as being the original software.
27 
28   4. The name of the author may not be used to endorse or promote 
29      products derived from this software without specific prior written 
30      permission.
31 
32   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
33   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
36   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
38   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
39   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
41   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
42   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43 
44   Julian Seward, Cambridge, UK.
45   jseward@acm.org
46   bzip2/libbzip2 version 1.0 of 21 March 2000
47 
48   This program is based on (at least) the work of:
49      Mike Burrows
50      David Wheeler
51      Peter Fenwick
52      Alistair Moffat
53      Radford Neal
54      Ian H. Witten
55      Robert Sedgewick
56      Jon L. Bentley
57 
58   For more information on these sources, see the manual.
59 --*/
60 
61 
62 #include "os.h"
63 #include "bzlib.h"
64 #include "bzlib_private.h"
65 
66 /*---------------------------------------------------*/
67 #define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
68 #define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
69 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
70 
71 #define ADDWEIGHTS(zw1,zw2)                           \
72    (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
73    (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
74 
75 #define UPHEAP(z)                                     \
76 {                                                     \
77    Int32 zz, tmp;                                     \
78    zz = z; tmp = heap[zz];                            \
79    while (weight[tmp] < weight[heap[zz >> 1]]) {      \
80       heap[zz] = heap[zz >> 1];                       \
81       zz >>= 1;                                       \
82    }                                                  \
83    heap[zz] = tmp;                                    \
84 }
85 
86 #define DOWNHEAP(z)                                   \
87 {                                                     \
88    Int32 zz, yy, tmp;                                 \
89    zz = z; tmp = heap[zz];                            \
90    while (True) {                                     \
91       yy = zz << 1;                                   \
92       if (yy > nHeap) break;                          \
93       if (yy < nHeap &&                               \
94           weight[heap[yy+1]] < weight[heap[yy]])      \
95          yy++;                                        \
96       if (weight[tmp] < weight[heap[yy]]) break;      \
97       heap[zz] = heap[yy];                            \
98       zz = yy;                                        \
99    }                                                  \
100    heap[zz] = tmp;                                    \
101 }
102 
103 
104 /*---------------------------------------------------*/
105 void BZ2_hbMakeCodeLengths ( UChar *len, 
106                              Int32 *freq,
107                              Int32 alphaSize,
108                              Int32 maxLen )
109 {
110    /*--
111       Nodes and heap entries run from 1.  Entry 0
112       for both the heap and nodes is a sentinel.
113    --*/
114    Int32 nNodes, nHeap, n1, n2, i, j, k;
115    Bool  tooLong;
116 
117    Int32 heap   [ BZ_MAX_ALPHA_SIZE + 2 ];
118    Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
119    Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; 
120 
121    for (i = 0; i < alphaSize; i++)
122       weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
123 
124    while (True) {
125 
126       nNodes = alphaSize;
127       nHeap = 0;
128 
129       heap[0] = 0;
130       weight[0] = 0;
131       parent[0] = -2;
132 
133       for (i = 1; i <= alphaSize; i++) {
134          parent[i] = -1;
135          nHeap++;
136          heap[nHeap] = i;
137          UPHEAP(nHeap);
138       }
139 
140       AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
141    
142       while (nHeap > 1) {
143          n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
144          n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
145          nNodes++;
146          parent[n1] = parent[n2] = nNodes;
147          weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
148          parent[nNodes] = -1;
149          nHeap++;
150          heap[nHeap] = nNodes;
151          UPHEAP(nHeap);
152       }
153 
154       AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
155 
156       tooLong = False;
157       for (i = 1; i <= alphaSize; i++) {
158          j = 0;
159          k = i;
160          while (parent[k] >= 0) { k = parent[k]; j++; }
161          len[i-1] = j;
162          if (j > maxLen) tooLong = True;
163       }
164       
165       if (! tooLong) break;
166 
167       for (i = 1; i < alphaSize; i++) {
168          j = weight[i] >> 8;
169          j = 1 + (j / 2);
170          weight[i] = j << 8;
171       }
172    }
173 }
174 
175 
176 /*---------------------------------------------------*/
177 void BZ2_hbAssignCodes ( Int32 *code,
178                          UChar *length,
179                          Int32 minLen,
180                          Int32 maxLen,
181                          Int32 alphaSize )
182 {
183    Int32 n, vec, i;
184 
185    vec = 0;
186    for (n = minLen; n <= maxLen; n++) {
187       for (i = 0; i < alphaSize; i++)
188          if (length[i] == n) { code[i] = vec; vec++; };
189       vec <<= 1;
190    }
191 }
192 
193 
194 /*---------------------------------------------------*/
195 void BZ2_hbCreateDecodeTables ( Int32 *limit,
196                                 Int32 *base,
197                                 Int32 *perm,
198                                 UChar *length,
199                                 Int32 minLen,
200                                 Int32 maxLen,
201                                 Int32 alphaSize )
202 {
203    Int32 pp, i, j, vec;
204 
205    pp = 0;
206    for (i = minLen; i <= maxLen; i++)
207       for (j = 0; j < alphaSize; j++)
208          if (length[j] == i) { perm[pp] = j; pp++; };
209 
210    for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
211    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
212 
213    for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
214 
215    for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
216    vec = 0;
217 
218    for (i = minLen; i <= maxLen; i++) {
219       vec += (base[i+1] - base[i]);
220       limit[i] = vec-1;
221       vec <<= 1;
222    }
223    for (i = minLen + 1; i <= maxLen; i++)
224       base[i] = ((limit[i-1] + 1) << 1) - base[i];
225 }
226 
227 
228 /*-------------------------------------------------------------*/
229 /*--- end                                         huffman.c ---*/
230 /*-------------------------------------------------------------*/