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