diff options
Diffstat (limited to 'utils/bzip2')
-rw-r--r-- | utils/bzip2/LICENSE | 42 | ||||
-rw-r--r-- | utils/bzip2/Makefile | 15 | ||||
-rw-r--r-- | utils/bzip2/blocksort.c | 1094 | ||||
-rw-r--r-- | utils/bzip2/bzlib.c | 1572 | ||||
-rw-r--r-- | utils/bzip2/bzlib.h | 282 | ||||
-rw-r--r-- | utils/bzip2/bzlib_private.h | 512 | ||||
-rw-r--r-- | utils/bzip2/compress.c | 672 | ||||
-rw-r--r-- | utils/bzip2/crctable.c | 104 | ||||
-rw-r--r-- | utils/bzip2/decompress.c | 646 | ||||
-rw-r--r-- | utils/bzip2/huffman.c | 205 | ||||
-rw-r--r-- | utils/bzip2/randtable.c | 84 |
11 files changed, 5228 insertions, 0 deletions
diff --git a/utils/bzip2/LICENSE b/utils/bzip2/LICENSE new file mode 100644 index 0000000000..cc614178cf --- /dev/null +++ b/utils/bzip2/LICENSE | |||
@@ -0,0 +1,42 @@ | |||
1 | |||
2 | -------------------------------------------------------------------------- | ||
3 | |||
4 | This program, "bzip2", the associated library "libbzip2", and all | ||
5 | documentation, are copyright (C) 1996-2010 Julian R Seward. All | ||
6 | rights reserved. | ||
7 | |||
8 | Redistribution and use in source and binary forms, with or without | ||
9 | modification, are permitted provided that the following conditions | ||
10 | are met: | ||
11 | |||
12 | 1. Redistributions of source code must retain the above copyright | ||
13 | notice, this list of conditions and the following disclaimer. | ||
14 | |||
15 | 2. The origin of this software must not be misrepresented; you must | ||
16 | not claim that you wrote the original software. If you use this | ||
17 | software in a product, an acknowledgment in the product | ||
18 | documentation would be appreciated but is not required. | ||
19 | |||
20 | 3. Altered source versions must be plainly marked as such, and must | ||
21 | not be misrepresented as being the original software. | ||
22 | |||
23 | 4. The name of the author may not be used to endorse or promote | ||
24 | products derived from this software without specific prior written | ||
25 | permission. | ||
26 | |||
27 | THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS | ||
28 | OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | ||
29 | WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
30 | ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY | ||
31 | DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
32 | DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE | ||
33 | GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
34 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, | ||
35 | WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING | ||
36 | NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | ||
37 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
38 | |||
39 | Julian Seward, jseward@bzip.org | ||
40 | bzip2/libbzip2 version 1.0.6 of 6 September 2010 | ||
41 | |||
42 | -------------------------------------------------------------------------- | ||
diff --git a/utils/bzip2/Makefile b/utils/bzip2/Makefile new file mode 100644 index 0000000000..6dc59ed025 --- /dev/null +++ b/utils/bzip2/Makefile | |||
@@ -0,0 +1,15 @@ | |||
1 | # __________ __ ___. | ||
2 | # Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
3 | # Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
4 | # Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
5 | # Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
6 | # \/ \/ \/ \/ \/ | ||
7 | # $Id$ | ||
8 | # | ||
9 | |||
10 | LIBSOURCES := blocksort.c compress.c decompress.c randtable.c \ | ||
11 | bzlib.c crctable.c huffman.c | ||
12 | |||
13 | OUTPUT := bz2 | ||
14 | |||
15 | include ../libtools.make | ||
diff --git a/utils/bzip2/blocksort.c b/utils/bzip2/blocksort.c new file mode 100644 index 0000000000..d0d662cd4e --- /dev/null +++ b/utils/bzip2/blocksort.c | |||
@@ -0,0 +1,1094 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Block sorting machinery ---*/ | ||
4 | /*--- blocksort.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 <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 | /*--- Fallback O(N log(N)^2) sorting ---*/ | ||
26 | /*--- algorithm, for repetitive blocks ---*/ | ||
27 | /*---------------------------------------------*/ | ||
28 | |||
29 | /*---------------------------------------------*/ | ||
30 | static | ||
31 | __inline__ | ||
32 | void fallbackSimpleSort ( UInt32* fmap, | ||
33 | UInt32* eclass, | ||
34 | Int32 lo, | ||
35 | Int32 hi ) | ||
36 | { | ||
37 | Int32 i, j, tmp; | ||
38 | UInt32 ec_tmp; | ||
39 | |||
40 | if (lo == hi) return; | ||
41 | |||
42 | if (hi - lo > 3) { | ||
43 | for ( i = hi-4; i >= lo; i-- ) { | ||
44 | tmp = fmap[i]; | ||
45 | ec_tmp = eclass[tmp]; | ||
46 | for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) | ||
47 | fmap[j-4] = fmap[j]; | ||
48 | fmap[j-4] = tmp; | ||
49 | } | ||
50 | } | ||
51 | |||
52 | for ( i = hi-1; i >= lo; i-- ) { | ||
53 | tmp = fmap[i]; | ||
54 | ec_tmp = eclass[tmp]; | ||
55 | for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) | ||
56 | fmap[j-1] = fmap[j]; | ||
57 | fmap[j-1] = tmp; | ||
58 | } | ||
59 | } | ||
60 | |||
61 | |||
62 | /*---------------------------------------------*/ | ||
63 | #define fswap(zz1, zz2) \ | ||
64 | { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } | ||
65 | |||
66 | #define fvswap(zzp1, zzp2, zzn) \ | ||
67 | { \ | ||
68 | Int32 yyp1 = (zzp1); \ | ||
69 | Int32 yyp2 = (zzp2); \ | ||
70 | Int32 yyn = (zzn); \ | ||
71 | while (yyn > 0) { \ | ||
72 | fswap(fmap[yyp1], fmap[yyp2]); \ | ||
73 | yyp1++; yyp2++; yyn--; \ | ||
74 | } \ | ||
75 | } | ||
76 | |||
77 | |||
78 | #define fmin(a,b) ((a) < (b)) ? (a) : (b) | ||
79 | |||
80 | #define fpush(lz,hz) { stackLo[sp] = lz; \ | ||
81 | stackHi[sp] = hz; \ | ||
82 | sp++; } | ||
83 | |||
84 | #define fpop(lz,hz) { sp--; \ | ||
85 | lz = stackLo[sp]; \ | ||
86 | hz = stackHi[sp]; } | ||
87 | |||
88 | #define FALLBACK_QSORT_SMALL_THRESH 10 | ||
89 | #define FALLBACK_QSORT_STACK_SIZE 100 | ||
90 | |||
91 | |||
92 | static | ||
93 | void fallbackQSort3 ( UInt32* fmap, | ||
94 | UInt32* eclass, | ||
95 | Int32 loSt, | ||
96 | Int32 hiSt ) | ||
97 | { | ||
98 | Int32 unLo, unHi, ltLo, gtHi, n, m; | ||
99 | Int32 sp, lo, hi; | ||
100 | UInt32 med, r, r3; | ||
101 | Int32 stackLo[FALLBACK_QSORT_STACK_SIZE]; | ||
102 | Int32 stackHi[FALLBACK_QSORT_STACK_SIZE]; | ||
103 | |||
104 | r = 0; | ||
105 | |||
106 | sp = 0; | ||
107 | fpush ( loSt, hiSt ); | ||
108 | |||
109 | while (sp > 0) { | ||
110 | |||
111 | AssertH ( sp < FALLBACK_QSORT_STACK_SIZE - 1, 1004 ); | ||
112 | |||
113 | fpop ( lo, hi ); | ||
114 | if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { | ||
115 | fallbackSimpleSort ( fmap, eclass, lo, hi ); | ||
116 | continue; | ||
117 | } | ||
118 | |||
119 | /* Random partitioning. Median of 3 sometimes fails to | ||
120 | avoid bad cases. Median of 9 seems to help but | ||
121 | looks rather expensive. This too seems to work but | ||
122 | is cheaper. Guidance for the magic constants | ||
123 | 7621 and 32768 is taken from Sedgewick's algorithms | ||
124 | book, chapter 35. | ||
125 | */ | ||
126 | r = ((r * 7621) + 1) % 32768; | ||
127 | r3 = r % 3; | ||
128 | if (r3 == 0) med = eclass[fmap[lo]]; else | ||
129 | if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else | ||
130 | med = eclass[fmap[hi]]; | ||
131 | |||
132 | unLo = ltLo = lo; | ||
133 | unHi = gtHi = hi; | ||
134 | |||
135 | while (1) { | ||
136 | while (1) { | ||
137 | if (unLo > unHi) break; | ||
138 | n = (Int32)eclass[fmap[unLo]] - (Int32)med; | ||
139 | if (n == 0) { | ||
140 | fswap(fmap[unLo], fmap[ltLo]); | ||
141 | ltLo++; unLo++; | ||
142 | continue; | ||
143 | }; | ||
144 | if (n > 0) break; | ||
145 | unLo++; | ||
146 | } | ||
147 | while (1) { | ||
148 | if (unLo > unHi) break; | ||
149 | n = (Int32)eclass[fmap[unHi]] - (Int32)med; | ||
150 | if (n == 0) { | ||
151 | fswap(fmap[unHi], fmap[gtHi]); | ||
152 | gtHi--; unHi--; | ||
153 | continue; | ||
154 | }; | ||
155 | if (n < 0) break; | ||
156 | unHi--; | ||
157 | } | ||
158 | if (unLo > unHi) break; | ||
159 | fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; | ||
160 | } | ||
161 | |||
162 | AssertD ( unHi == unLo-1, "fallbackQSort3(2)" ); | ||
163 | |||
164 | if (gtHi < ltLo) continue; | ||
165 | |||
166 | n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); | ||
167 | m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); | ||
168 | |||
169 | n = lo + unLo - ltLo - 1; | ||
170 | m = hi - (gtHi - unHi) + 1; | ||
171 | |||
172 | if (n - lo > hi - m) { | ||
173 | fpush ( lo, n ); | ||
174 | fpush ( m, hi ); | ||
175 | } else { | ||
176 | fpush ( m, hi ); | ||
177 | fpush ( lo, n ); | ||
178 | } | ||
179 | } | ||
180 | } | ||
181 | |||
182 | #undef fmin | ||
183 | #undef fpush | ||
184 | #undef fpop | ||
185 | #undef fswap | ||
186 | #undef fvswap | ||
187 | #undef FALLBACK_QSORT_SMALL_THRESH | ||
188 | #undef FALLBACK_QSORT_STACK_SIZE | ||
189 | |||
190 | |||
191 | /*---------------------------------------------*/ | ||
192 | /* Pre: | ||
193 | nblock > 0 | ||
194 | eclass exists for [0 .. nblock-1] | ||
195 | ((UChar*)eclass) [0 .. nblock-1] holds block | ||
196 | ptr exists for [0 .. nblock-1] | ||
197 | |||
198 | Post: | ||
199 | ((UChar*)eclass) [0 .. nblock-1] holds block | ||
200 | All other areas of eclass destroyed | ||
201 | fmap [0 .. nblock-1] holds sorted order | ||
202 | bhtab [ 0 .. 2+(nblock/32) ] destroyed | ||
203 | */ | ||
204 | |||
205 | #define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31)) | ||
206 | #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31)) | ||
207 | #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31))) | ||
208 | #define WORD_BH(zz) bhtab[(zz) >> 5] | ||
209 | #define UNALIGNED_BH(zz) ((zz) & 0x01f) | ||
210 | |||
211 | static | ||
212 | void fallbackSort ( UInt32* fmap, | ||
213 | UInt32* eclass, | ||
214 | UInt32* bhtab, | ||
215 | Int32 nblock, | ||
216 | Int32 verb ) | ||
217 | { | ||
218 | Int32 ftab[257]; | ||
219 | Int32 ftabCopy[256]; | ||
220 | Int32 H, i, j, k, l, r, cc, cc1; | ||
221 | Int32 nNotDone; | ||
222 | Int32 nBhtab; | ||
223 | UChar* eclass8 = (UChar*)eclass; | ||
224 | |||
225 | /*-- | ||
226 | Initial 1-char radix sort to generate | ||
227 | initial fmap and initial BH bits. | ||
228 | --*/ | ||
229 | if (verb >= 4) | ||
230 | VPrintf0 ( " bucket sorting ...\n" ); | ||
231 | for (i = 0; i < 257; i++) ftab[i] = 0; | ||
232 | for (i = 0; i < nblock; i++) ftab[eclass8[i]]++; | ||
233 | for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; | ||
234 | for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; | ||
235 | |||
236 | for (i = 0; i < nblock; i++) { | ||
237 | j = eclass8[i]; | ||
238 | k = ftab[j] - 1; | ||
239 | ftab[j] = k; | ||
240 | fmap[k] = i; | ||
241 | } | ||
242 | |||
243 | nBhtab = 2 + (nblock / 32); | ||
244 | for (i = 0; i < nBhtab; i++) bhtab[i] = 0; | ||
245 | for (i = 0; i < 256; i++) SET_BH(ftab[i]); | ||
246 | |||
247 | /*-- | ||
248 | Inductively refine the buckets. Kind-of an | ||
249 | "exponential radix sort" (!), inspired by the | ||
250 | Manber-Myers suffix array construction algorithm. | ||
251 | --*/ | ||
252 | |||
253 | /*-- set sentinel bits for block-end detection --*/ | ||
254 | for (i = 0; i < 32; i++) { | ||
255 | SET_BH(nblock + 2*i); | ||
256 | CLEAR_BH(nblock + 2*i + 1); | ||
257 | } | ||
258 | |||
259 | /*-- the log(N) loop --*/ | ||
260 | H = 1; | ||
261 | while (1) { | ||
262 | |||
263 | if (verb >= 4) | ||
264 | VPrintf1 ( " depth %6d has ", H ); | ||
265 | |||
266 | j = 0; | ||
267 | for (i = 0; i < nblock; i++) { | ||
268 | if (ISSET_BH(i)) j = i; | ||
269 | k = fmap[i] - H; if (k < 0) k += nblock; | ||
270 | eclass[k] = j; | ||
271 | } | ||
272 | |||
273 | nNotDone = 0; | ||
274 | r = -1; | ||
275 | while (1) { | ||
276 | |||
277 | /*-- find the next non-singleton bucket --*/ | ||
278 | k = r + 1; | ||
279 | while (ISSET_BH(k) && UNALIGNED_BH(k)) k++; | ||
280 | if (ISSET_BH(k)) { | ||
281 | while (WORD_BH(k) == 0xffffffff) k += 32; | ||
282 | while (ISSET_BH(k)) k++; | ||
283 | } | ||
284 | l = k - 1; | ||
285 | if (l >= nblock) break; | ||
286 | while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++; | ||
287 | if (!ISSET_BH(k)) { | ||
288 | while (WORD_BH(k) == 0x00000000) k += 32; | ||
289 | while (!ISSET_BH(k)) k++; | ||
290 | } | ||
291 | r = k - 1; | ||
292 | if (r >= nblock) break; | ||
293 | |||
294 | /*-- now [l, r] bracket current bucket --*/ | ||
295 | if (r > l) { | ||
296 | nNotDone += (r - l + 1); | ||
297 | fallbackQSort3 ( fmap, eclass, l, r ); | ||
298 | |||
299 | /*-- scan bucket and generate header bits-- */ | ||
300 | cc = -1; | ||
301 | for (i = l; i <= r; i++) { | ||
302 | cc1 = eclass[fmap[i]]; | ||
303 | if (cc != cc1) { SET_BH(i); cc = cc1; }; | ||
304 | } | ||
305 | } | ||
306 | } | ||
307 | |||
308 | if (verb >= 4) | ||
309 | VPrintf1 ( "%6d unresolved strings\n", nNotDone ); | ||
310 | |||
311 | H *= 2; | ||
312 | if (H > nblock || nNotDone == 0) break; | ||
313 | } | ||
314 | |||
315 | /*-- | ||
316 | Reconstruct the original block in | ||
317 | eclass8 [0 .. nblock-1], since the | ||
318 | previous phase destroyed it. | ||
319 | --*/ | ||
320 | if (verb >= 4) | ||
321 | VPrintf0 ( " reconstructing block ...\n" ); | ||
322 | j = 0; | ||
323 | for (i = 0; i < nblock; i++) { | ||
324 | while (ftabCopy[j] == 0) j++; | ||
325 | ftabCopy[j]--; | ||
326 | eclass8[fmap[i]] = (UChar)j; | ||
327 | } | ||
328 | AssertH ( j < 256, 1005 ); | ||
329 | } | ||
330 | |||
331 | #undef SET_BH | ||
332 | #undef CLEAR_BH | ||
333 | #undef ISSET_BH | ||
334 | #undef WORD_BH | ||
335 | #undef UNALIGNED_BH | ||
336 | |||
337 | |||
338 | /*---------------------------------------------*/ | ||
339 | /*--- The main, O(N^2 log(N)) sorting ---*/ | ||
340 | /*--- algorithm. Faster for "normal" ---*/ | ||
341 | /*--- non-repetitive blocks. ---*/ | ||
342 | /*---------------------------------------------*/ | ||
343 | |||
344 | /*---------------------------------------------*/ | ||
345 | static | ||
346 | __inline__ | ||
347 | Bool mainGtU ( UInt32 i1, | ||
348 | UInt32 i2, | ||
349 | UChar* block, | ||
350 | UInt16* quadrant, | ||
351 | UInt32 nblock, | ||
352 | Int32* budget ) | ||
353 | { | ||
354 | Int32 k; | ||
355 | UChar c1, c2; | ||
356 | UInt16 s1, s2; | ||
357 | |||
358 | AssertD ( i1 != i2, "mainGtU" ); | ||
359 | /* 1 */ | ||
360 | c1 = block[i1]; c2 = block[i2]; | ||
361 | if (c1 != c2) return (c1 > c2); | ||
362 | i1++; i2++; | ||
363 | /* 2 */ | ||
364 | c1 = block[i1]; c2 = block[i2]; | ||
365 | if (c1 != c2) return (c1 > c2); | ||
366 | i1++; i2++; | ||
367 | /* 3 */ | ||
368 | c1 = block[i1]; c2 = block[i2]; | ||
369 | if (c1 != c2) return (c1 > c2); | ||
370 | i1++; i2++; | ||
371 | /* 4 */ | ||
372 | c1 = block[i1]; c2 = block[i2]; | ||
373 | if (c1 != c2) return (c1 > c2); | ||
374 | i1++; i2++; | ||
375 | /* 5 */ | ||
376 | c1 = block[i1]; c2 = block[i2]; | ||
377 | if (c1 != c2) return (c1 > c2); | ||
378 | i1++; i2++; | ||
379 | /* 6 */ | ||
380 | c1 = block[i1]; c2 = block[i2]; | ||
381 | if (c1 != c2) return (c1 > c2); | ||
382 | i1++; i2++; | ||
383 | /* 7 */ | ||
384 | c1 = block[i1]; c2 = block[i2]; | ||
385 | if (c1 != c2) return (c1 > c2); | ||
386 | i1++; i2++; | ||
387 | /* 8 */ | ||
388 | c1 = block[i1]; c2 = block[i2]; | ||
389 | if (c1 != c2) return (c1 > c2); | ||
390 | i1++; i2++; | ||
391 | /* 9 */ | ||
392 | c1 = block[i1]; c2 = block[i2]; | ||
393 | if (c1 != c2) return (c1 > c2); | ||
394 | i1++; i2++; | ||
395 | /* 10 */ | ||
396 | c1 = block[i1]; c2 = block[i2]; | ||
397 | if (c1 != c2) return (c1 > c2); | ||
398 | i1++; i2++; | ||
399 | /* 11 */ | ||
400 | c1 = block[i1]; c2 = block[i2]; | ||
401 | if (c1 != c2) return (c1 > c2); | ||
402 | i1++; i2++; | ||
403 | /* 12 */ | ||
404 | c1 = block[i1]; c2 = block[i2]; | ||
405 | if (c1 != c2) return (c1 > c2); | ||
406 | i1++; i2++; | ||
407 | |||
408 | k = nblock + 8; | ||
409 | |||
410 | do { | ||
411 | /* 1 */ | ||
412 | c1 = block[i1]; c2 = block[i2]; | ||
413 | if (c1 != c2) return (c1 > c2); | ||
414 | s1 = quadrant[i1]; s2 = quadrant[i2]; | ||
415 | if (s1 != s2) return (s1 > s2); | ||
416 | i1++; i2++; | ||
417 | /* 2 */ | ||
418 | c1 = block[i1]; c2 = block[i2]; | ||
419 | if (c1 != c2) return (c1 > c2); | ||
420 | s1 = quadrant[i1]; s2 = quadrant[i2]; | ||
421 | if (s1 != s2) return (s1 > s2); | ||
422 | i1++; i2++; | ||
423 | /* 3 */ | ||
424 | c1 = block[i1]; c2 = block[i2]; | ||
425 | if (c1 != c2) return (c1 > c2); | ||
426 | s1 = quadrant[i1]; s2 = quadrant[i2]; | ||
427 | if (s1 != s2) return (s1 > s2); | ||
428 | i1++; i2++; | ||
429 | /* 4 */ | ||
430 | c1 = block[i1]; c2 = block[i2]; | ||
431 | if (c1 != c2) return (c1 > c2); | ||
432 | s1 = quadrant[i1]; s2 = quadrant[i2]; | ||
433 | if (s1 != s2) return (s1 > s2); | ||
434 | i1++; i2++; | ||
435 | /* 5 */ | ||
436 | c1 = block[i1]; c2 = block[i2]; | ||
437 | if (c1 != c2) return (c1 > c2); | ||
438 | s1 = quadrant[i1]; s2 = quadrant[i2]; | ||
439 | if (s1 != s2) return (s1 > s2); | ||
440 | i1++; i2++; | ||
441 | /* 6 */ | ||
442 | c1 = block[i1]; c2 = block[i2]; | ||
443 | if (c1 != c2) return (c1 > c2); | ||
444 | s1 = quadrant[i1]; s2 = quadrant[i2]; | ||
445 | if (s1 != s2) return (s1 > s2); | ||
446 | i1++; i2++; | ||
447 | /* 7 */ | ||
448 | c1 = block[i1]; c2 = block[i2]; | ||
449 | if (c1 != c2) return (c1 > c2); | ||
450 | s1 = quadrant[i1]; s2 = quadrant[i2]; | ||
451 | if (s1 != s2) return (s1 > s2); | ||
452 | i1++; i2++; | ||
453 | /* 8 */ | ||
454 | c1 = block[i1]; c2 = block[i2]; | ||
455 | if (c1 != c2) return (c1 > c2); | ||
456 | s1 = quadrant[i1]; s2 = quadrant[i2]; | ||
457 | if (s1 != s2) return (s1 > s2); | ||
458 | i1++; i2++; | ||
459 | |||
460 | if (i1 >= nblock) i1 -= nblock; | ||
461 | if (i2 >= nblock) i2 -= nblock; | ||
462 | |||
463 | k -= 8; | ||
464 | (*budget)--; | ||
465 | } | ||
466 | while (k >= 0); | ||
467 | |||
468 | return False; | ||
469 | } | ||
470 | |||
471 | |||
472 | /*---------------------------------------------*/ | ||
473 | /*-- | ||
474 | Knuth's increments seem to work better | ||
475 | than Incerpi-Sedgewick here. Possibly | ||
476 | because the number of elems to sort is | ||
477 | usually small, typically <= 20. | ||
478 | --*/ | ||
479 | static | ||
480 | Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280, | ||
481 | 9841, 29524, 88573, 265720, | ||
482 | 797161, 2391484 }; | ||
483 | |||
484 | static | ||
485 | void mainSimpleSort ( UInt32* ptr, | ||
486 | UChar* block, | ||
487 | UInt16* quadrant, | ||
488 | Int32 nblock, | ||
489 | Int32 lo, | ||
490 | Int32 hi, | ||
491 | Int32 d, | ||
492 | Int32* budget ) | ||
493 | { | ||
494 | Int32 i, j, h, bigN, hp; | ||
495 | UInt32 v; | ||
496 | |||
497 | bigN = hi - lo + 1; | ||
498 | if (bigN < 2) return; | ||
499 | |||
500 | hp = 0; | ||
501 | while (incs[hp] < bigN) hp++; | ||
502 | hp--; | ||
503 | |||
504 | for (; hp >= 0; hp--) { | ||
505 | h = incs[hp]; | ||
506 | |||
507 | i = lo + h; | ||
508 | while (True) { | ||
509 | |||
510 | /*-- copy 1 --*/ | ||
511 | if (i > hi) break; | ||
512 | v = ptr[i]; | ||
513 | j = i; | ||
514 | while ( mainGtU ( | ||
515 | ptr[j-h]+d, v+d, block, quadrant, nblock, budget | ||
516 | ) ) { | ||
517 | ptr[j] = ptr[j-h]; | ||
518 | j = j - h; | ||
519 | if (j <= (lo + h - 1)) break; | ||
520 | } | ||
521 | ptr[j] = v; | ||
522 | i++; | ||
523 | |||
524 | /*-- copy 2 --*/ | ||
525 | if (i > hi) break; | ||
526 | v = ptr[i]; | ||
527 | j = i; | ||
528 | while ( mainGtU ( | ||
529 | ptr[j-h]+d, v+d, block, quadrant, nblock, budget | ||
530 | ) ) { | ||
531 | ptr[j] = ptr[j-h]; | ||
532 | j = j - h; | ||
533 | if (j <= (lo + h - 1)) break; | ||
534 | } | ||
535 | ptr[j] = v; | ||
536 | i++; | ||
537 | |||
538 | /*-- copy 3 --*/ | ||
539 | if (i > hi) break; | ||
540 | v = ptr[i]; | ||
541 | j = i; | ||
542 | while ( mainGtU ( | ||
543 | ptr[j-h]+d, v+d, block, quadrant, nblock, budget | ||
544 | ) ) { | ||
545 | ptr[j] = ptr[j-h]; | ||
546 | j = j - h; | ||
547 | if (j <= (lo + h - 1)) break; | ||
548 | } | ||
549 | ptr[j] = v; | ||
550 | i++; | ||
551 | |||
552 | if (*budget < 0) return; | ||
553 | } | ||
554 | } | ||
555 | } | ||
556 | |||
557 | |||
558 | /*---------------------------------------------*/ | ||
559 | /*-- | ||
560 | The following is an implementation of | ||
561 | an elegant 3-way quicksort for strings, | ||
562 | described in a paper "Fast Algorithms for | ||
563 | Sorting and Searching Strings", by Robert | ||
564 | Sedgewick and Jon L. Bentley. | ||
565 | --*/ | ||
566 | |||
567 | #define mswap(zz1, zz2) \ | ||
568 | { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } | ||
569 | |||
570 | #define mvswap(zzp1, zzp2, zzn) \ | ||
571 | { \ | ||
572 | Int32 yyp1 = (zzp1); \ | ||
573 | Int32 yyp2 = (zzp2); \ | ||
574 | Int32 yyn = (zzn); \ | ||
575 | while (yyn > 0) { \ | ||
576 | mswap(ptr[yyp1], ptr[yyp2]); \ | ||
577 | yyp1++; yyp2++; yyn--; \ | ||
578 | } \ | ||
579 | } | ||
580 | |||
581 | static | ||
582 | __inline__ | ||
583 | UChar mmed3 ( UChar a, UChar b, UChar c ) | ||
584 | { | ||
585 | UChar t; | ||
586 | if (a > b) { t = a; a = b; b = t; }; | ||
587 | if (b > c) { | ||
588 | b = c; | ||
589 | if (a > b) b = a; | ||
590 | } | ||
591 | return b; | ||
592 | } | ||
593 | |||
594 | #define mmin(a,b) ((a) < (b)) ? (a) : (b) | ||
595 | |||
596 | #define mpush(lz,hz,dz) { stackLo[sp] = lz; \ | ||
597 | stackHi[sp] = hz; \ | ||
598 | stackD [sp] = dz; \ | ||
599 | sp++; } | ||
600 | |||
601 | #define mpop(lz,hz,dz) { sp--; \ | ||
602 | lz = stackLo[sp]; \ | ||
603 | hz = stackHi[sp]; \ | ||
604 | dz = stackD [sp]; } | ||
605 | |||
606 | |||
607 | #define mnextsize(az) (nextHi[az]-nextLo[az]) | ||
608 | |||
609 | #define mnextswap(az,bz) \ | ||
610 | { Int32 tz; \ | ||
611 | tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \ | ||
612 | tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \ | ||
613 | tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; } | ||
614 | |||
615 | |||
616 | #define MAIN_QSORT_SMALL_THRESH 20 | ||
617 | #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT) | ||
618 | #define MAIN_QSORT_STACK_SIZE 100 | ||
619 | |||
620 | static | ||
621 | void mainQSort3 ( UInt32* ptr, | ||
622 | UChar* block, | ||
623 | UInt16* quadrant, | ||
624 | Int32 nblock, | ||
625 | Int32 loSt, | ||
626 | Int32 hiSt, | ||
627 | Int32 dSt, | ||
628 | Int32* budget ) | ||
629 | { | ||
630 | Int32 unLo, unHi, ltLo, gtHi, n, m, med; | ||
631 | Int32 sp, lo, hi, d; | ||
632 | |||
633 | Int32 stackLo[MAIN_QSORT_STACK_SIZE]; | ||
634 | Int32 stackHi[MAIN_QSORT_STACK_SIZE]; | ||
635 | Int32 stackD [MAIN_QSORT_STACK_SIZE]; | ||
636 | |||
637 | Int32 nextLo[3]; | ||
638 | Int32 nextHi[3]; | ||
639 | Int32 nextD [3]; | ||
640 | |||
641 | sp = 0; | ||
642 | mpush ( loSt, hiSt, dSt ); | ||
643 | |||
644 | while (sp > 0) { | ||
645 | |||
646 | AssertH ( sp < MAIN_QSORT_STACK_SIZE - 2, 1001 ); | ||
647 | |||
648 | mpop ( lo, hi, d ); | ||
649 | if (hi - lo < MAIN_QSORT_SMALL_THRESH || | ||
650 | d > MAIN_QSORT_DEPTH_THRESH) { | ||
651 | mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget ); | ||
652 | if (*budget < 0) return; | ||
653 | continue; | ||
654 | } | ||
655 | |||
656 | med = (Int32) | ||
657 | mmed3 ( block[ptr[ lo ]+d], | ||
658 | block[ptr[ hi ]+d], | ||
659 | block[ptr[ (lo+hi)>>1 ]+d] ); | ||
660 | |||
661 | unLo = ltLo = lo; | ||
662 | unHi = gtHi = hi; | ||
663 | |||
664 | while (True) { | ||
665 | while (True) { | ||
666 | if (unLo > unHi) break; | ||
667 | n = ((Int32)block[ptr[unLo]+d]) - med; | ||
668 | if (n == 0) { | ||
669 | mswap(ptr[unLo], ptr[ltLo]); | ||
670 | ltLo++; unLo++; continue; | ||
671 | }; | ||
672 | if (n > 0) break; | ||
673 | unLo++; | ||
674 | } | ||
675 | while (True) { | ||
676 | if (unLo > unHi) break; | ||
677 | n = ((Int32)block[ptr[unHi]+d]) - med; | ||
678 | if (n == 0) { | ||
679 | mswap(ptr[unHi], ptr[gtHi]); | ||
680 | gtHi--; unHi--; continue; | ||
681 | }; | ||
682 | if (n < 0) break; | ||
683 | unHi--; | ||
684 | } | ||
685 | if (unLo > unHi) break; | ||
686 | mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--; | ||
687 | } | ||
688 | |||
689 | AssertD ( unHi == unLo-1, "mainQSort3(2)" ); | ||
690 | |||
691 | if (gtHi < ltLo) { | ||
692 | mpush(lo, hi, d+1 ); | ||
693 | continue; | ||
694 | } | ||
695 | |||
696 | n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n); | ||
697 | m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m); | ||
698 | |||
699 | n = lo + unLo - ltLo - 1; | ||
700 | m = hi - (gtHi - unHi) + 1; | ||
701 | |||
702 | nextLo[0] = lo; nextHi[0] = n; nextD[0] = d; | ||
703 | nextLo[1] = m; nextHi[1] = hi; nextD[1] = d; | ||
704 | nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1; | ||
705 | |||
706 | if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); | ||
707 | if (mnextsize(1) < mnextsize(2)) mnextswap(1,2); | ||
708 | if (mnextsize(0) < mnextsize(1)) mnextswap(0,1); | ||
709 | |||
710 | AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" ); | ||
711 | AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" ); | ||
712 | |||
713 | mpush (nextLo[0], nextHi[0], nextD[0]); | ||
714 | mpush (nextLo[1], nextHi[1], nextD[1]); | ||
715 | mpush (nextLo[2], nextHi[2], nextD[2]); | ||
716 | } | ||
717 | } | ||
718 | |||
719 | #undef mswap | ||
720 | #undef mvswap | ||
721 | #undef mpush | ||
722 | #undef mpop | ||
723 | #undef mmin | ||
724 | #undef mnextsize | ||
725 | #undef mnextswap | ||
726 | #undef MAIN_QSORT_SMALL_THRESH | ||
727 | #undef MAIN_QSORT_DEPTH_THRESH | ||
728 | #undef MAIN_QSORT_STACK_SIZE | ||
729 | |||
730 | |||
731 | /*---------------------------------------------*/ | ||
732 | /* Pre: | ||
733 | nblock > N_OVERSHOOT | ||
734 | block32 exists for [0 .. nblock-1 +N_OVERSHOOT] | ||
735 | ((UChar*)block32) [0 .. nblock-1] holds block | ||
736 | ptr exists for [0 .. nblock-1] | ||
737 | |||
738 | Post: | ||
739 | ((UChar*)block32) [0 .. nblock-1] holds block | ||
740 | All other areas of block32 destroyed | ||
741 | ftab [0 .. 65536 ] destroyed | ||
742 | ptr [0 .. nblock-1] holds sorted order | ||
743 | if (*budget < 0), sorting was abandoned | ||
744 | */ | ||
745 | |||
746 | #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8]) | ||
747 | #define SETMASK (1 << 21) | ||
748 | #define CLEARMASK (~(SETMASK)) | ||
749 | |||
750 | static | ||
751 | void mainSort ( UInt32* ptr, | ||
752 | UChar* block, | ||
753 | UInt16* quadrant, | ||
754 | UInt32* ftab, | ||
755 | Int32 nblock, | ||
756 | Int32 verb, | ||
757 | Int32* budget ) | ||
758 | { | ||
759 | Int32 i, j, k, ss, sb; | ||
760 | Int32 runningOrder[256]; | ||
761 | Bool bigDone[256]; | ||
762 | Int32 copyStart[256]; | ||
763 | Int32 copyEnd [256]; | ||
764 | UChar c1; | ||
765 | Int32 numQSorted; | ||
766 | UInt16 s; | ||
767 | if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" ); | ||
768 | |||
769 | /*-- set up the 2-byte frequency table --*/ | ||
770 | for (i = 65536; i >= 0; i--) ftab[i] = 0; | ||
771 | |||
772 | j = block[0] << 8; | ||
773 | i = nblock-1; | ||
774 | for (; i >= 3; i -= 4) { | ||
775 | quadrant[i] = 0; | ||
776 | j = (j >> 8) | ( ((UInt16)block[i]) << 8); | ||
777 | ftab[j]++; | ||
778 | quadrant[i-1] = 0; | ||
779 | j = (j >> 8) | ( ((UInt16)block[i-1]) << 8); | ||
780 | ftab[j]++; | ||
781 | quadrant[i-2] = 0; | ||
782 | j = (j >> 8) | ( ((UInt16)block[i-2]) << 8); | ||
783 | ftab[j]++; | ||
784 | quadrant[i-3] = 0; | ||
785 | j = (j >> 8) | ( ((UInt16)block[i-3]) << 8); | ||
786 | ftab[j]++; | ||
787 | } | ||
788 | for (; i >= 0; i--) { | ||
789 | quadrant[i] = 0; | ||
790 | j = (j >> 8) | ( ((UInt16)block[i]) << 8); | ||
791 | ftab[j]++; | ||
792 | } | ||
793 | |||
794 | /*-- (emphasises close relationship of block & quadrant) --*/ | ||
795 | for (i = 0; i < BZ_N_OVERSHOOT; i++) { | ||
796 | block [nblock+i] = block[i]; | ||
797 | quadrant[nblock+i] = 0; | ||
798 | } | ||
799 | |||
800 | if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" ); | ||
801 | |||
802 | /*-- Complete the initial radix sort --*/ | ||
803 | for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; | ||
804 | |||
805 | s = block[0] << 8; | ||
806 | i = nblock-1; | ||
807 | for (; i >= 3; i -= 4) { | ||
808 | s = (s >> 8) | (block[i] << 8); | ||
809 | j = ftab[s] -1; | ||
810 | ftab[s] = j; | ||
811 | ptr[j] = i; | ||
812 | s = (s >> 8) | (block[i-1] << 8); | ||
813 | j = ftab[s] -1; | ||
814 | ftab[s] = j; | ||
815 | ptr[j] = i-1; | ||
816 | s = (s >> 8) | (block[i-2] << 8); | ||
817 | j = ftab[s] -1; | ||
818 | ftab[s] = j; | ||
819 | ptr[j] = i-2; | ||
820 | s = (s >> 8) | (block[i-3] << 8); | ||
821 | j = ftab[s] -1; | ||
822 | ftab[s] = j; | ||
823 | ptr[j] = i-3; | ||
824 | } | ||
825 | for (; i >= 0; i--) { | ||
826 | s = (s >> 8) | (block[i] << 8); | ||
827 | j = ftab[s] -1; | ||
828 | ftab[s] = j; | ||
829 | ptr[j] = i; | ||
830 | } | ||
831 | |||
832 | /*-- | ||
833 | Now ftab contains the first loc of every small bucket. | ||
834 | Calculate the running order, from smallest to largest | ||
835 | big bucket. | ||
836 | --*/ | ||
837 | for (i = 0; i <= 255; i++) { | ||
838 | bigDone [i] = False; | ||
839 | runningOrder[i] = i; | ||
840 | } | ||
841 | |||
842 | { | ||
843 | Int32 vv; | ||
844 | Int32 h = 1; | ||
845 | do h = 3 * h + 1; while (h <= 256); | ||
846 | do { | ||
847 | h = h / 3; | ||
848 | for (i = h; i <= 255; i++) { | ||
849 | vv = runningOrder[i]; | ||
850 | j = i; | ||
851 | while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) { | ||
852 | runningOrder[j] = runningOrder[j-h]; | ||
853 | j = j - h; | ||
854 | if (j <= (h - 1)) goto zero; | ||
855 | } | ||
856 | zero: | ||
857 | runningOrder[j] = vv; | ||
858 | } | ||
859 | } while (h != 1); | ||
860 | } | ||
861 | |||
862 | /*-- | ||
863 | The main sorting loop. | ||
864 | --*/ | ||
865 | |||
866 | numQSorted = 0; | ||
867 | |||
868 | for (i = 0; i <= 255; i++) { | ||
869 | |||
870 | /*-- | ||
871 | Process big buckets, starting with the least full. | ||
872 | Basically this is a 3-step process in which we call | ||
873 | mainQSort3 to sort the small buckets [ss, j], but | ||
874 | also make a big effort to avoid the calls if we can. | ||
875 | --*/ | ||
876 | ss = runningOrder[i]; | ||
877 | |||
878 | /*-- | ||
879 | Step 1: | ||
880 | Complete the big bucket [ss] by quicksorting | ||
881 | any unsorted small buckets [ss, j], for j != ss. | ||
882 | Hopefully previous pointer-scanning phases have already | ||
883 | completed many of the small buckets [ss, j], so | ||
884 | we don't have to sort them at all. | ||
885 | --*/ | ||
886 | for (j = 0; j <= 255; j++) { | ||
887 | if (j != ss) { | ||
888 | sb = (ss << 8) + j; | ||
889 | if ( ! (ftab[sb] & SETMASK) ) { | ||
890 | Int32 lo = ftab[sb] & CLEARMASK; | ||
891 | Int32 hi = (ftab[sb+1] & CLEARMASK) - 1; | ||
892 | if (hi > lo) { | ||
893 | if (verb >= 4) | ||
894 | VPrintf4 ( " qsort [0x%x, 0x%x] " | ||
895 | "done %d this %d\n", | ||
896 | ss, j, numQSorted, hi - lo + 1 ); | ||
897 | mainQSort3 ( | ||
898 | ptr, block, quadrant, nblock, | ||
899 | lo, hi, BZ_N_RADIX, budget | ||
900 | ); | ||
901 | numQSorted += (hi - lo + 1); | ||
902 | if (*budget < 0) return; | ||
903 | } | ||
904 | } | ||
905 | ftab[sb] |= SETMASK; | ||
906 | } | ||
907 | } | ||
908 | |||
909 | AssertH ( !bigDone[ss], 1006 ); | ||
910 | |||
911 | /*-- | ||
912 | Step 2: | ||
913 | Now scan this big bucket [ss] so as to synthesise the | ||
914 | sorted order for small buckets [t, ss] for all t, | ||
915 | including, magically, the bucket [ss,ss] too. | ||
916 | This will avoid doing Real Work in subsequent Step 1's. | ||
917 | --*/ | ||
918 | { | ||
919 | for (j = 0; j <= 255; j++) { | ||
920 | copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK; | ||
921 | copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1; | ||
922 | } | ||
923 | for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) { | ||
924 | k = ptr[j]-1; if (k < 0) k += nblock; | ||
925 | c1 = block[k]; | ||
926 | if (!bigDone[c1]) | ||
927 | ptr[ copyStart[c1]++ ] = k; | ||
928 | } | ||
929 | for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) { | ||
930 | k = ptr[j]-1; if (k < 0) k += nblock; | ||
931 | c1 = block[k]; | ||
932 | if (!bigDone[c1]) | ||
933 | ptr[ copyEnd[c1]-- ] = k; | ||
934 | } | ||
935 | } | ||
936 | |||
937 | AssertH ( (copyStart[ss]-1 == copyEnd[ss]) | ||
938 | || | ||
939 | /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1. | ||
940 | Necessity for this case is demonstrated by compressing | ||
941 | a sequence of approximately 48.5 million of character | ||
942 | 251; 1.0.0/1.0.1 will then die here. */ | ||
943 | (copyStart[ss] == 0 && copyEnd[ss] == nblock-1), | ||
944 | 1007 ) | ||
945 | |||
946 | for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK; | ||
947 | |||
948 | /*-- | ||
949 | Step 3: | ||
950 | The [ss] big bucket is now done. Record this fact, | ||
951 | and update the quadrant descriptors. Remember to | ||
952 | update quadrants in the overshoot area too, if | ||
953 | necessary. The "if (i < 255)" test merely skips | ||
954 | this updating for the last bucket processed, since | ||
955 | updating for the last bucket is pointless. | ||
956 | |||
957 | The quadrant array provides a way to incrementally | ||
958 | cache sort orderings, as they appear, so as to | ||
959 | make subsequent comparisons in fullGtU() complete | ||
960 | faster. For repetitive blocks this makes a big | ||
961 | difference (but not big enough to be able to avoid | ||
962 | the fallback sorting mechanism, exponential radix sort). | ||
963 | |||
964 | The precise meaning is: at all times: | ||
965 | |||
966 | for 0 <= i < nblock and 0 <= j <= nblock | ||
967 | |||
968 | if block[i] != block[j], | ||
969 | |||
970 | then the relative values of quadrant[i] and | ||
971 | quadrant[j] are meaningless. | ||
972 | |||
973 | else { | ||
974 | if quadrant[i] < quadrant[j] | ||
975 | then the string starting at i lexicographically | ||
976 | precedes the string starting at j | ||
977 | |||
978 | else if quadrant[i] > quadrant[j] | ||
979 | then the string starting at j lexicographically | ||
980 | precedes the string starting at i | ||
981 | |||
982 | else | ||
983 | the relative ordering of the strings starting | ||
984 | at i and j has not yet been determined. | ||
985 | } | ||
986 | --*/ | ||
987 | bigDone[ss] = True; | ||
988 | |||
989 | if (i < 255) { | ||
990 | Int32 bbStart = ftab[ss << 8] & CLEARMASK; | ||
991 | Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart; | ||
992 | Int32 shifts = 0; | ||
993 | |||
994 | while ((bbSize >> shifts) > 65534) shifts++; | ||
995 | |||
996 | for (j = bbSize-1; j >= 0; j--) { | ||
997 | Int32 a2update = ptr[bbStart + j]; | ||
998 | UInt16 qVal = (UInt16)(j >> shifts); | ||
999 | quadrant[a2update] = qVal; | ||
1000 | if (a2update < BZ_N_OVERSHOOT) | ||
1001 | quadrant[a2update + nblock] = qVal; | ||
1002 | } | ||
1003 | AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 ); | ||
1004 | } | ||
1005 | |||
1006 | } | ||
1007 | |||
1008 | if (verb >= 4) | ||
1009 | VPrintf3 ( " %d pointers, %d sorted, %d scanned\n", | ||
1010 | nblock, numQSorted, nblock - numQSorted ); | ||
1011 | } | ||
1012 | |||
1013 | #undef BIGFREQ | ||
1014 | #undef SETMASK | ||
1015 | #undef CLEARMASK | ||
1016 | |||
1017 | |||
1018 | /*---------------------------------------------*/ | ||
1019 | /* Pre: | ||
1020 | nblock > 0 | ||
1021 | arr2 exists for [0 .. nblock-1 +N_OVERSHOOT] | ||
1022 | ((UChar*)arr2) [0 .. nblock-1] holds block | ||
1023 | arr1 exists for [0 .. nblock-1] | ||
1024 | |||
1025 | Post: | ||
1026 | ((UChar*)arr2) [0 .. nblock-1] holds block | ||
1027 | All other areas of block destroyed | ||
1028 | ftab [ 0 .. 65536 ] destroyed | ||
1029 | arr1 [0 .. nblock-1] holds sorted order | ||
1030 | */ | ||
1031 | void BZ2_blockSort ( EState* s ) | ||
1032 | { | ||
1033 | UInt32* ptr = s->ptr; | ||
1034 | UChar* block = s->block; | ||
1035 | UInt32* ftab = s->ftab; | ||
1036 | Int32 nblock = s->nblock; | ||
1037 | Int32 verb = s->verbosity; | ||
1038 | Int32 wfact = s->workFactor; | ||
1039 | UInt16* quadrant; | ||
1040 | Int32 budget; | ||
1041 | Int32 budgetInit; | ||
1042 | Int32 i; | ||
1043 | |||
1044 | if (nblock < 10000) { | ||
1045 | fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); | ||
1046 | } else { | ||
1047 | /* Calculate the location for quadrant, remembering to get | ||
1048 | the alignment right. Assumes that &(block[0]) is at least | ||
1049 | 2-byte aligned -- this should be ok since block is really | ||
1050 | the first section of arr2. | ||
1051 | */ | ||
1052 | i = nblock+BZ_N_OVERSHOOT; | ||
1053 | if (i & 1) i++; | ||
1054 | quadrant = (UInt16*)(&(block[i])); | ||
1055 | |||
1056 | /* (wfact-1) / 3 puts the default-factor-30 | ||
1057 | transition point at very roughly the same place as | ||
1058 | with v0.1 and v0.9.0. | ||
1059 | Not that it particularly matters any more, since the | ||
1060 | resulting compressed stream is now the same regardless | ||
1061 | of whether or not we use the main sort or fallback sort. | ||
1062 | */ | ||
1063 | if (wfact < 1 ) wfact = 1; | ||
1064 | if (wfact > 100) wfact = 100; | ||
1065 | budgetInit = nblock * ((wfact-1) / 3); | ||
1066 | budget = budgetInit; | ||
1067 | |||
1068 | mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget ); | ||
1069 | if (verb >= 3) | ||
1070 | VPrintf3 ( " %d work, %d block, ratio %5.2f\n", | ||
1071 | budgetInit - budget, | ||
1072 | nblock, | ||
1073 | (float)(budgetInit - budget) / | ||
1074 | (float)(nblock==0 ? 1 : nblock) ); | ||
1075 | if (budget < 0) { | ||
1076 | if (verb >= 2) | ||
1077 | VPrintf0 ( " too repetitive; using fallback" | ||
1078 | " sorting algorithm\n" ); | ||
1079 | fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb ); | ||
1080 | } | ||
1081 | } | ||
1082 | |||
1083 | s->origPtr = -1; | ||
1084 | for (i = 0; i < s->nblock; i++) | ||
1085 | if (ptr[i] == 0) | ||
1086 | { s->origPtr = i; break; }; | ||
1087 | |||
1088 | AssertH( s->origPtr != -1, 1003 ); | ||
1089 | } | ||
1090 | |||
1091 | |||
1092 | /*-------------------------------------------------------------*/ | ||
1093 | /*--- end blocksort.c ---*/ | ||
1094 | /*-------------------------------------------------------------*/ | ||
diff --git a/utils/bzip2/bzlib.c b/utils/bzip2/bzlib.c new file mode 100644 index 0000000000..6e78e19407 --- /dev/null +++ b/utils/bzip2/bzlib.c | |||
@@ -0,0 +1,1572 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Library top-level functions. ---*/ | ||
4 | /*--- bzlib.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 <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 | /* CHANGES | ||
22 | 0.9.0 -- original version. | ||
23 | 0.9.0a/b -- no changes in this file. | ||
24 | 0.9.0c -- made zero-length BZ_FLUSH work correctly in bzCompress(). | ||
25 | fixed bzWrite/bzRead to ignore zero-length requests. | ||
26 | fixed bzread to correctly handle read requests after EOF. | ||
27 | wrong parameter order in call to bzDecompressInit in | ||
28 | bzBuffToBuffDecompress. Fixed. | ||
29 | */ | ||
30 | |||
31 | #include "bzlib_private.h" | ||
32 | |||
33 | |||
34 | /*---------------------------------------------------*/ | ||
35 | /*--- Compression stuff ---*/ | ||
36 | /*---------------------------------------------------*/ | ||
37 | |||
38 | |||
39 | /*---------------------------------------------------*/ | ||
40 | #ifndef BZ_NO_STDIO | ||
41 | void BZ2_bz__AssertH__fail ( int errcode ) | ||
42 | { | ||
43 | fprintf(stderr, | ||
44 | "\n\nbzip2/libbzip2: internal error number %d.\n" | ||
45 | "This is a bug in bzip2/libbzip2, %s.\n" | ||
46 | "Please report it to me at: jseward@bzip.org. If this happened\n" | ||
47 | "when you were using some program which uses libbzip2 as a\n" | ||
48 | "component, you should also report this bug to the author(s)\n" | ||
49 | "of that program. Please make an effort to report this bug;\n" | ||
50 | "timely and accurate bug reports eventually lead to higher\n" | ||
51 | "quality software. Thanks. Julian Seward, 10 December 2007.\n\n", | ||
52 | errcode, | ||
53 | BZ2_bzlibVersion() | ||
54 | ); | ||
55 | |||
56 | if (errcode == 1007) { | ||
57 | fprintf(stderr, | ||
58 | "\n*** A special note about internal error number 1007 ***\n" | ||
59 | "\n" | ||
60 | "Experience suggests that a common cause of i.e. 1007\n" | ||
61 | "is unreliable memory or other hardware. The 1007 assertion\n" | ||
62 | "just happens to cross-check the results of huge numbers of\n" | ||
63 | "memory reads/writes, and so acts (unintendedly) as a stress\n" | ||
64 | "test of your memory system.\n" | ||
65 | "\n" | ||
66 | "I suggest the following: try compressing the file again,\n" | ||
67 | "possibly monitoring progress in detail with the -vv flag.\n" | ||
68 | "\n" | ||
69 | "* If the error cannot be reproduced, and/or happens at different\n" | ||
70 | " points in compression, you may have a flaky memory system.\n" | ||
71 | " Try a memory-test program. I have used Memtest86\n" | ||
72 | " (www.memtest86.com). At the time of writing it is free (GPLd).\n" | ||
73 | " Memtest86 tests memory much more thorougly than your BIOSs\n" | ||
74 | " power-on test, and may find failures that the BIOS doesn't.\n" | ||
75 | "\n" | ||
76 | "* If the error can be repeatably reproduced, this is a bug in\n" | ||
77 | " bzip2, and I would very much like to hear about it. Please\n" | ||
78 | " let me know, and, ideally, save a copy of the file causing the\n" | ||
79 | " problem -- without which I will be unable to investigate it.\n" | ||
80 | "\n" | ||
81 | ); | ||
82 | } | ||
83 | |||
84 | exit(3); | ||
85 | } | ||
86 | #endif | ||
87 | |||
88 | |||
89 | /*---------------------------------------------------*/ | ||
90 | static | ||
91 | int bz_config_ok ( void ) | ||
92 | { | ||
93 | if (sizeof(int) != 4) return 0; | ||
94 | if (sizeof(short) != 2) return 0; | ||
95 | if (sizeof(char) != 1) return 0; | ||
96 | return 1; | ||
97 | } | ||
98 | |||
99 | |||
100 | /*---------------------------------------------------*/ | ||
101 | static | ||
102 | void* default_bzalloc ( void* opaque, Int32 items, Int32 size ) | ||
103 | { | ||
104 | void* v = malloc ( items * size ); | ||
105 | return v; | ||
106 | } | ||
107 | |||
108 | static | ||
109 | void default_bzfree ( void* opaque, void* addr ) | ||
110 | { | ||
111 | if (addr != NULL) free ( addr ); | ||
112 | } | ||
113 | |||
114 | |||
115 | /*---------------------------------------------------*/ | ||
116 | static | ||
117 | void prepare_new_block ( EState* s ) | ||
118 | { | ||
119 | Int32 i; | ||
120 | s->nblock = 0; | ||
121 | s->numZ = 0; | ||
122 | s->state_out_pos = 0; | ||
123 | BZ_INITIALISE_CRC ( s->blockCRC ); | ||
124 | for (i = 0; i < 256; i++) s->inUse[i] = False; | ||
125 | s->blockNo++; | ||
126 | } | ||
127 | |||
128 | |||
129 | /*---------------------------------------------------*/ | ||
130 | static | ||
131 | void init_RL ( EState* s ) | ||
132 | { | ||
133 | s->state_in_ch = 256; | ||
134 | s->state_in_len = 0; | ||
135 | } | ||
136 | |||
137 | |||
138 | static | ||
139 | Bool isempty_RL ( EState* s ) | ||
140 | { | ||
141 | if (s->state_in_ch < 256 && s->state_in_len > 0) | ||
142 | return False; else | ||
143 | return True; | ||
144 | } | ||
145 | |||
146 | |||
147 | /*---------------------------------------------------*/ | ||
148 | int BZ_API(BZ2_bzCompressInit) | ||
149 | ( bz_stream* strm, | ||
150 | int blockSize100k, | ||
151 | int verbosity, | ||
152 | int workFactor ) | ||
153 | { | ||
154 | Int32 n; | ||
155 | EState* s; | ||
156 | |||
157 | if (!bz_config_ok()) return BZ_CONFIG_ERROR; | ||
158 | |||
159 | if (strm == NULL || | ||
160 | blockSize100k < 1 || blockSize100k > 9 || | ||
161 | workFactor < 0 || workFactor > 250) | ||
162 | return BZ_PARAM_ERROR; | ||
163 | |||
164 | if (workFactor == 0) workFactor = 30; | ||
165 | if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc; | ||
166 | if (strm->bzfree == NULL) strm->bzfree = default_bzfree; | ||
167 | |||
168 | s = BZALLOC( sizeof(EState) ); | ||
169 | if (s == NULL) return BZ_MEM_ERROR; | ||
170 | s->strm = strm; | ||
171 | |||
172 | s->arr1 = NULL; | ||
173 | s->arr2 = NULL; | ||
174 | s->ftab = NULL; | ||
175 | |||
176 | n = 100000 * blockSize100k; | ||
177 | s->arr1 = BZALLOC( n * sizeof(UInt32) ); | ||
178 | s->arr2 = BZALLOC( (n+BZ_N_OVERSHOOT) * sizeof(UInt32) ); | ||
179 | s->ftab = BZALLOC( 65537 * sizeof(UInt32) ); | ||
180 | |||
181 | if (s->arr1 == NULL || s->arr2 == NULL || s->ftab == NULL) { | ||
182 | if (s->arr1 != NULL) BZFREE(s->arr1); | ||
183 | if (s->arr2 != NULL) BZFREE(s->arr2); | ||
184 | if (s->ftab != NULL) BZFREE(s->ftab); | ||
185 | if (s != NULL) BZFREE(s); | ||
186 | return BZ_MEM_ERROR; | ||
187 | } | ||
188 | |||
189 | s->blockNo = 0; | ||
190 | s->state = BZ_S_INPUT; | ||
191 | s->mode = BZ_M_RUNNING; | ||
192 | s->combinedCRC = 0; | ||
193 | s->blockSize100k = blockSize100k; | ||
194 | s->nblockMAX = 100000 * blockSize100k - 19; | ||
195 | s->verbosity = verbosity; | ||
196 | s->workFactor = workFactor; | ||
197 | |||
198 | s->block = (UChar*)s->arr2; | ||
199 | s->mtfv = (UInt16*)s->arr1; | ||
200 | s->zbits = NULL; | ||
201 | s->ptr = (UInt32*)s->arr1; | ||
202 | |||
203 | strm->state = s; | ||
204 | strm->total_in_lo32 = 0; | ||
205 | strm->total_in_hi32 = 0; | ||
206 | strm->total_out_lo32 = 0; | ||
207 | strm->total_out_hi32 = 0; | ||
208 | init_RL ( s ); | ||
209 | prepare_new_block ( s ); | ||
210 | return BZ_OK; | ||
211 | } | ||
212 | |||
213 | |||
214 | /*---------------------------------------------------*/ | ||
215 | static | ||
216 | void add_pair_to_block ( EState* s ) | ||
217 | { | ||
218 | Int32 i; | ||
219 | UChar ch = (UChar)(s->state_in_ch); | ||
220 | for (i = 0; i < s->state_in_len; i++) { | ||
221 | BZ_UPDATE_CRC( s->blockCRC, ch ); | ||
222 | } | ||
223 | s->inUse[s->state_in_ch] = True; | ||
224 | switch (s->state_in_len) { | ||
225 | case 1: | ||
226 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
227 | break; | ||
228 | case 2: | ||
229 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
230 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
231 | break; | ||
232 | case 3: | ||
233 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
234 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
235 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
236 | break; | ||
237 | default: | ||
238 | s->inUse[s->state_in_len-4] = True; | ||
239 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
240 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
241 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
242 | s->block[s->nblock] = (UChar)ch; s->nblock++; | ||
243 | s->block[s->nblock] = ((UChar)(s->state_in_len-4)); | ||
244 | s->nblock++; | ||
245 | break; | ||
246 | } | ||
247 | } | ||
248 | |||
249 | |||
250 | /*---------------------------------------------------*/ | ||
251 | static | ||
252 | void flush_RL ( EState* s ) | ||
253 | { | ||
254 | if (s->state_in_ch < 256) add_pair_to_block ( s ); | ||
255 | init_RL ( s ); | ||
256 | } | ||
257 | |||
258 | |||
259 | /*---------------------------------------------------*/ | ||
260 | #define ADD_CHAR_TO_BLOCK(zs,zchh0) \ | ||
261 | { \ | ||
262 | UInt32 zchh = (UInt32)(zchh0); \ | ||
263 | /*-- fast track the common case --*/ \ | ||
264 | if (zchh != zs->state_in_ch && \ | ||
265 | zs->state_in_len == 1) { \ | ||
266 | UChar ch = (UChar)(zs->state_in_ch); \ | ||
267 | BZ_UPDATE_CRC( zs->blockCRC, ch ); \ | ||
268 | zs->inUse[zs->state_in_ch] = True; \ | ||
269 | zs->block[zs->nblock] = (UChar)ch; \ | ||
270 | zs->nblock++; \ | ||
271 | zs->state_in_ch = zchh; \ | ||
272 | } \ | ||
273 | else \ | ||
274 | /*-- general, uncommon cases --*/ \ | ||
275 | if (zchh != zs->state_in_ch || \ | ||
276 | zs->state_in_len == 255) { \ | ||
277 | if (zs->state_in_ch < 256) \ | ||
278 | add_pair_to_block ( zs ); \ | ||
279 | zs->state_in_ch = zchh; \ | ||
280 | zs->state_in_len = 1; \ | ||
281 | } else { \ | ||
282 | zs->state_in_len++; \ | ||
283 | } \ | ||
284 | } | ||
285 | |||
286 | |||
287 | /*---------------------------------------------------*/ | ||
288 | static | ||
289 | Bool copy_input_until_stop ( EState* s ) | ||
290 | { | ||
291 | Bool progress_in = False; | ||
292 | |||
293 | if (s->mode == BZ_M_RUNNING) { | ||
294 | |||
295 | /*-- fast track the common case --*/ | ||
296 | while (True) { | ||
297 | /*-- block full? --*/ | ||
298 | if (s->nblock >= s->nblockMAX) break; | ||
299 | /*-- no input? --*/ | ||
300 | if (s->strm->avail_in == 0) break; | ||
301 | progress_in = True; | ||
302 | ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) ); | ||
303 | s->strm->next_in++; | ||
304 | s->strm->avail_in--; | ||
305 | s->strm->total_in_lo32++; | ||
306 | if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++; | ||
307 | } | ||
308 | |||
309 | } else { | ||
310 | |||
311 | /*-- general, uncommon case --*/ | ||
312 | while (True) { | ||
313 | /*-- block full? --*/ | ||
314 | if (s->nblock >= s->nblockMAX) break; | ||
315 | /*-- no input? --*/ | ||
316 | if (s->strm->avail_in == 0) break; | ||
317 | /*-- flush/finish end? --*/ | ||
318 | if (s->avail_in_expect == 0) break; | ||
319 | progress_in = True; | ||
320 | ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) ); | ||
321 | s->strm->next_in++; | ||
322 | s->strm->avail_in--; | ||
323 | s->strm->total_in_lo32++; | ||
324 | if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++; | ||
325 | s->avail_in_expect--; | ||
326 | } | ||
327 | } | ||
328 | return progress_in; | ||
329 | } | ||
330 | |||
331 | |||
332 | /*---------------------------------------------------*/ | ||
333 | static | ||
334 | Bool copy_output_until_stop ( EState* s ) | ||
335 | { | ||
336 | Bool progress_out = False; | ||
337 | |||
338 | while (True) { | ||
339 | |||
340 | /*-- no output space? --*/ | ||
341 | if (s->strm->avail_out == 0) break; | ||
342 | |||
343 | /*-- block done? --*/ | ||
344 | if (s->state_out_pos >= s->numZ) break; | ||
345 | |||
346 | progress_out = True; | ||
347 | *(s->strm->next_out) = s->zbits[s->state_out_pos]; | ||
348 | s->state_out_pos++; | ||
349 | s->strm->avail_out--; | ||
350 | s->strm->next_out++; | ||
351 | s->strm->total_out_lo32++; | ||
352 | if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; | ||
353 | } | ||
354 | |||
355 | return progress_out; | ||
356 | } | ||
357 | |||
358 | |||
359 | /*---------------------------------------------------*/ | ||
360 | static | ||
361 | Bool handle_compress ( bz_stream* strm ) | ||
362 | { | ||
363 | Bool progress_in = False; | ||
364 | Bool progress_out = False; | ||
365 | EState* s = strm->state; | ||
366 | |||
367 | while (True) { | ||
368 | |||
369 | if (s->state == BZ_S_OUTPUT) { | ||
370 | progress_out |= copy_output_until_stop ( s ); | ||
371 | if (s->state_out_pos < s->numZ) break; | ||
372 | if (s->mode == BZ_M_FINISHING && | ||
373 | s->avail_in_expect == 0 && | ||
374 | isempty_RL(s)) break; | ||
375 | prepare_new_block ( s ); | ||
376 | s->state = BZ_S_INPUT; | ||
377 | if (s->mode == BZ_M_FLUSHING && | ||
378 | s->avail_in_expect == 0 && | ||
379 | isempty_RL(s)) break; | ||
380 | } | ||
381 | |||
382 | if (s->state == BZ_S_INPUT) { | ||
383 | progress_in |= copy_input_until_stop ( s ); | ||
384 | if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) { | ||
385 | flush_RL ( s ); | ||
386 | BZ2_compressBlock ( s, (Bool)(s->mode == BZ_M_FINISHING) ); | ||
387 | s->state = BZ_S_OUTPUT; | ||
388 | } | ||
389 | else | ||
390 | if (s->nblock >= s->nblockMAX) { | ||
391 | BZ2_compressBlock ( s, False ); | ||
392 | s->state = BZ_S_OUTPUT; | ||
393 | } | ||
394 | else | ||
395 | if (s->strm->avail_in == 0) { | ||
396 | break; | ||
397 | } | ||
398 | } | ||
399 | |||
400 | } | ||
401 | |||
402 | return progress_in || progress_out; | ||
403 | } | ||
404 | |||
405 | |||
406 | /*---------------------------------------------------*/ | ||
407 | int BZ_API(BZ2_bzCompress) ( bz_stream *strm, int action ) | ||
408 | { | ||
409 | Bool progress; | ||
410 | EState* s; | ||
411 | if (strm == NULL) return BZ_PARAM_ERROR; | ||
412 | s = strm->state; | ||
413 | if (s == NULL) return BZ_PARAM_ERROR; | ||
414 | if (s->strm != strm) return BZ_PARAM_ERROR; | ||
415 | |||
416 | preswitch: | ||
417 | switch (s->mode) { | ||
418 | |||
419 | case BZ_M_IDLE: | ||
420 | return BZ_SEQUENCE_ERROR; | ||
421 | |||
422 | case BZ_M_RUNNING: | ||
423 | if (action == BZ_RUN) { | ||
424 | progress = handle_compress ( strm ); | ||
425 | return progress ? BZ_RUN_OK : BZ_PARAM_ERROR; | ||
426 | } | ||
427 | else | ||
428 | if (action == BZ_FLUSH) { | ||
429 | s->avail_in_expect = strm->avail_in; | ||
430 | s->mode = BZ_M_FLUSHING; | ||
431 | goto preswitch; | ||
432 | } | ||
433 | else | ||
434 | if (action == BZ_FINISH) { | ||
435 | s->avail_in_expect = strm->avail_in; | ||
436 | s->mode = BZ_M_FINISHING; | ||
437 | goto preswitch; | ||
438 | } | ||
439 | else | ||
440 | return BZ_PARAM_ERROR; | ||
441 | |||
442 | case BZ_M_FLUSHING: | ||
443 | if (action != BZ_FLUSH) return BZ_SEQUENCE_ERROR; | ||
444 | if (s->avail_in_expect != s->strm->avail_in) | ||
445 | return BZ_SEQUENCE_ERROR; | ||
446 | progress = handle_compress ( strm ); | ||
447 | if (s->avail_in_expect > 0 || !isempty_RL(s) || | ||
448 | s->state_out_pos < s->numZ) return BZ_FLUSH_OK; | ||
449 | s->mode = BZ_M_RUNNING; | ||
450 | return BZ_RUN_OK; | ||
451 | |||
452 | case BZ_M_FINISHING: | ||
453 | if (action != BZ_FINISH) return BZ_SEQUENCE_ERROR; | ||
454 | if (s->avail_in_expect != s->strm->avail_in) | ||
455 | return BZ_SEQUENCE_ERROR; | ||
456 | progress = handle_compress ( strm ); | ||
457 | if (!progress) return BZ_SEQUENCE_ERROR; | ||
458 | if (s->avail_in_expect > 0 || !isempty_RL(s) || | ||
459 | s->state_out_pos < s->numZ) return BZ_FINISH_OK; | ||
460 | s->mode = BZ_M_IDLE; | ||
461 | return BZ_STREAM_END; | ||
462 | } | ||
463 | return BZ_OK; /*--not reached--*/ | ||
464 | } | ||
465 | |||
466 | |||
467 | /*---------------------------------------------------*/ | ||
468 | int BZ_API(BZ2_bzCompressEnd) ( bz_stream *strm ) | ||
469 | { | ||
470 | EState* s; | ||
471 | if (strm == NULL) return BZ_PARAM_ERROR; | ||
472 | s = strm->state; | ||
473 | if (s == NULL) return BZ_PARAM_ERROR; | ||
474 | if (s->strm != strm) return BZ_PARAM_ERROR; | ||
475 | |||
476 | if (s->arr1 != NULL) BZFREE(s->arr1); | ||
477 | if (s->arr2 != NULL) BZFREE(s->arr2); | ||
478 | if (s->ftab != NULL) BZFREE(s->ftab); | ||
479 | BZFREE(strm->state); | ||
480 | |||
481 | strm->state = NULL; | ||
482 | |||
483 | return BZ_OK; | ||
484 | } | ||
485 | |||
486 | |||
487 | /*---------------------------------------------------*/ | ||
488 | /*--- Decompression stuff ---*/ | ||
489 | /*---------------------------------------------------*/ | ||
490 | |||
491 | /*---------------------------------------------------*/ | ||
492 | int BZ_API(BZ2_bzDecompressInit) | ||
493 | ( bz_stream* strm, | ||
494 | int verbosity, | ||
495 | int small ) | ||
496 | { | ||
497 | DState* s; | ||
498 | |||
499 | if (!bz_config_ok()) return BZ_CONFIG_ERROR; | ||
500 | |||
501 | if (strm == NULL) return BZ_PARAM_ERROR; | ||
502 | if (small != 0 && small != 1) return BZ_PARAM_ERROR; | ||
503 | if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR; | ||
504 | |||
505 | if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc; | ||
506 | if (strm->bzfree == NULL) strm->bzfree = default_bzfree; | ||
507 | |||
508 | s = BZALLOC( sizeof(DState) ); | ||
509 | if (s == NULL) return BZ_MEM_ERROR; | ||
510 | s->strm = strm; | ||
511 | strm->state = s; | ||
512 | s->state = BZ_X_MAGIC_1; | ||
513 | s->bsLive = 0; | ||
514 | s->bsBuff = 0; | ||
515 | s->calculatedCombinedCRC = 0; | ||
516 | strm->total_in_lo32 = 0; | ||
517 | strm->total_in_hi32 = 0; | ||
518 | strm->total_out_lo32 = 0; | ||
519 | strm->total_out_hi32 = 0; | ||
520 | s->smallDecompress = (Bool)small; | ||
521 | s->ll4 = NULL; | ||
522 | s->ll16 = NULL; | ||
523 | s->tt = NULL; | ||
524 | s->currBlockNo = 0; | ||
525 | s->verbosity = verbosity; | ||
526 | |||
527 | return BZ_OK; | ||
528 | } | ||
529 | |||
530 | |||
531 | /*---------------------------------------------------*/ | ||
532 | /* Return True iff data corruption is discovered. | ||
533 | Returns False if there is no problem. | ||
534 | */ | ||
535 | static | ||
536 | Bool unRLE_obuf_to_output_FAST ( DState* s ) | ||
537 | { | ||
538 | UChar k1; | ||
539 | |||
540 | if (s->blockRandomised) { | ||
541 | |||
542 | while (True) { | ||
543 | /* try to finish existing run */ | ||
544 | while (True) { | ||
545 | if (s->strm->avail_out == 0) return False; | ||
546 | if (s->state_out_len == 0) break; | ||
547 | *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; | ||
548 | BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); | ||
549 | s->state_out_len--; | ||
550 | s->strm->next_out++; | ||
551 | s->strm->avail_out--; | ||
552 | s->strm->total_out_lo32++; | ||
553 | if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; | ||
554 | } | ||
555 | |||
556 | /* can a new run be started? */ | ||
557 | if (s->nblock_used == s->save_nblock+1) return False; | ||
558 | |||
559 | /* Only caused by corrupt data stream? */ | ||
560 | if (s->nblock_used > s->save_nblock+1) | ||
561 | return True; | ||
562 | |||
563 | s->state_out_len = 1; | ||
564 | s->state_out_ch = s->k0; | ||
565 | BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; | ||
566 | k1 ^= BZ_RAND_MASK; s->nblock_used++; | ||
567 | if (s->nblock_used == s->save_nblock+1) continue; | ||
568 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
569 | |||
570 | s->state_out_len = 2; | ||
571 | BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; | ||
572 | k1 ^= BZ_RAND_MASK; s->nblock_used++; | ||
573 | if (s->nblock_used == s->save_nblock+1) continue; | ||
574 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
575 | |||
576 | s->state_out_len = 3; | ||
577 | BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; | ||
578 | k1 ^= BZ_RAND_MASK; s->nblock_used++; | ||
579 | if (s->nblock_used == s->save_nblock+1) continue; | ||
580 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
581 | |||
582 | BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; | ||
583 | k1 ^= BZ_RAND_MASK; s->nblock_used++; | ||
584 | s->state_out_len = ((Int32)k1) + 4; | ||
585 | BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK; | ||
586 | s->k0 ^= BZ_RAND_MASK; s->nblock_used++; | ||
587 | } | ||
588 | |||
589 | } else { | ||
590 | |||
591 | /* restore */ | ||
592 | UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC; | ||
593 | UChar c_state_out_ch = s->state_out_ch; | ||
594 | Int32 c_state_out_len = s->state_out_len; | ||
595 | Int32 c_nblock_used = s->nblock_used; | ||
596 | Int32 c_k0 = s->k0; | ||
597 | UInt32* c_tt = s->tt; | ||
598 | UInt32 c_tPos = s->tPos; | ||
599 | char* cs_next_out = s->strm->next_out; | ||
600 | unsigned int cs_avail_out = s->strm->avail_out; | ||
601 | Int32 ro_blockSize100k = s->blockSize100k; | ||
602 | /* end restore */ | ||
603 | |||
604 | UInt32 avail_out_INIT = cs_avail_out; | ||
605 | Int32 s_save_nblockPP = s->save_nblock+1; | ||
606 | unsigned int total_out_lo32_old; | ||
607 | |||
608 | while (True) { | ||
609 | |||
610 | /* try to finish existing run */ | ||
611 | if (c_state_out_len > 0) { | ||
612 | while (True) { | ||
613 | if (cs_avail_out == 0) goto return_notr; | ||
614 | if (c_state_out_len == 1) break; | ||
615 | *( (UChar*)(cs_next_out) ) = c_state_out_ch; | ||
616 | BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch ); | ||
617 | c_state_out_len--; | ||
618 | cs_next_out++; | ||
619 | cs_avail_out--; | ||
620 | } | ||
621 | s_state_out_len_eq_one: | ||
622 | { | ||
623 | if (cs_avail_out == 0) { | ||
624 | c_state_out_len = 1; goto return_notr; | ||
625 | }; | ||
626 | *( (UChar*)(cs_next_out) ) = c_state_out_ch; | ||
627 | BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch ); | ||
628 | cs_next_out++; | ||
629 | cs_avail_out--; | ||
630 | } | ||
631 | } | ||
632 | /* Only caused by corrupt data stream? */ | ||
633 | if (c_nblock_used > s_save_nblockPP) | ||
634 | return True; | ||
635 | |||
636 | /* can a new run be started? */ | ||
637 | if (c_nblock_used == s_save_nblockPP) { | ||
638 | c_state_out_len = 0; goto return_notr; | ||
639 | }; | ||
640 | c_state_out_ch = c_k0; | ||
641 | BZ_GET_FAST_C(k1); c_nblock_used++; | ||
642 | if (k1 != c_k0) { | ||
643 | c_k0 = k1; goto s_state_out_len_eq_one; | ||
644 | }; | ||
645 | if (c_nblock_used == s_save_nblockPP) | ||
646 | goto s_state_out_len_eq_one; | ||
647 | |||
648 | c_state_out_len = 2; | ||
649 | BZ_GET_FAST_C(k1); c_nblock_used++; | ||
650 | if (c_nblock_used == s_save_nblockPP) continue; | ||
651 | if (k1 != c_k0) { c_k0 = k1; continue; }; | ||
652 | |||
653 | c_state_out_len = 3; | ||
654 | BZ_GET_FAST_C(k1); c_nblock_used++; | ||
655 | if (c_nblock_used == s_save_nblockPP) continue; | ||
656 | if (k1 != c_k0) { c_k0 = k1; continue; }; | ||
657 | |||
658 | BZ_GET_FAST_C(k1); c_nblock_used++; | ||
659 | c_state_out_len = ((Int32)k1) + 4; | ||
660 | BZ_GET_FAST_C(c_k0); c_nblock_used++; | ||
661 | } | ||
662 | |||
663 | return_notr: | ||
664 | total_out_lo32_old = s->strm->total_out_lo32; | ||
665 | s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out); | ||
666 | if (s->strm->total_out_lo32 < total_out_lo32_old) | ||
667 | s->strm->total_out_hi32++; | ||
668 | |||
669 | /* save */ | ||
670 | s->calculatedBlockCRC = c_calculatedBlockCRC; | ||
671 | s->state_out_ch = c_state_out_ch; | ||
672 | s->state_out_len = c_state_out_len; | ||
673 | s->nblock_used = c_nblock_used; | ||
674 | s->k0 = c_k0; | ||
675 | s->tt = c_tt; | ||
676 | s->tPos = c_tPos; | ||
677 | s->strm->next_out = cs_next_out; | ||
678 | s->strm->avail_out = cs_avail_out; | ||
679 | /* end save */ | ||
680 | } | ||
681 | return False; | ||
682 | } | ||
683 | |||
684 | |||
685 | |||
686 | /*---------------------------------------------------*/ | ||
687 | __inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab ) | ||
688 | { | ||
689 | Int32 nb, na, mid; | ||
690 | nb = 0; | ||
691 | na = 256; | ||
692 | do { | ||
693 | mid = (nb + na) >> 1; | ||
694 | if (indx >= cftab[mid]) nb = mid; else na = mid; | ||
695 | } | ||
696 | while (na - nb != 1); | ||
697 | return nb; | ||
698 | } | ||
699 | |||
700 | |||
701 | /*---------------------------------------------------*/ | ||
702 | /* Return True iff data corruption is discovered. | ||
703 | Returns False if there is no problem. | ||
704 | */ | ||
705 | static | ||
706 | Bool unRLE_obuf_to_output_SMALL ( DState* s ) | ||
707 | { | ||
708 | UChar k1; | ||
709 | |||
710 | if (s->blockRandomised) { | ||
711 | |||
712 | while (True) { | ||
713 | /* try to finish existing run */ | ||
714 | while (True) { | ||
715 | if (s->strm->avail_out == 0) return False; | ||
716 | if (s->state_out_len == 0) break; | ||
717 | *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; | ||
718 | BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); | ||
719 | s->state_out_len--; | ||
720 | s->strm->next_out++; | ||
721 | s->strm->avail_out--; | ||
722 | s->strm->total_out_lo32++; | ||
723 | if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; | ||
724 | } | ||
725 | |||
726 | /* can a new run be started? */ | ||
727 | if (s->nblock_used == s->save_nblock+1) return False; | ||
728 | |||
729 | /* Only caused by corrupt data stream? */ | ||
730 | if (s->nblock_used > s->save_nblock+1) | ||
731 | return True; | ||
732 | |||
733 | s->state_out_len = 1; | ||
734 | s->state_out_ch = s->k0; | ||
735 | BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; | ||
736 | k1 ^= BZ_RAND_MASK; s->nblock_used++; | ||
737 | if (s->nblock_used == s->save_nblock+1) continue; | ||
738 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
739 | |||
740 | s->state_out_len = 2; | ||
741 | BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; | ||
742 | k1 ^= BZ_RAND_MASK; s->nblock_used++; | ||
743 | if (s->nblock_used == s->save_nblock+1) continue; | ||
744 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
745 | |||
746 | s->state_out_len = 3; | ||
747 | BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; | ||
748 | k1 ^= BZ_RAND_MASK; s->nblock_used++; | ||
749 | if (s->nblock_used == s->save_nblock+1) continue; | ||
750 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
751 | |||
752 | BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; | ||
753 | k1 ^= BZ_RAND_MASK; s->nblock_used++; | ||
754 | s->state_out_len = ((Int32)k1) + 4; | ||
755 | BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK; | ||
756 | s->k0 ^= BZ_RAND_MASK; s->nblock_used++; | ||
757 | } | ||
758 | |||
759 | } else { | ||
760 | |||
761 | while (True) { | ||
762 | /* try to finish existing run */ | ||
763 | while (True) { | ||
764 | if (s->strm->avail_out == 0) return False; | ||
765 | if (s->state_out_len == 0) break; | ||
766 | *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; | ||
767 | BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); | ||
768 | s->state_out_len--; | ||
769 | s->strm->next_out++; | ||
770 | s->strm->avail_out--; | ||
771 | s->strm->total_out_lo32++; | ||
772 | if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; | ||
773 | } | ||
774 | |||
775 | /* can a new run be started? */ | ||
776 | if (s->nblock_used == s->save_nblock+1) return False; | ||
777 | |||
778 | /* Only caused by corrupt data stream? */ | ||
779 | if (s->nblock_used > s->save_nblock+1) | ||
780 | return True; | ||
781 | |||
782 | s->state_out_len = 1; | ||
783 | s->state_out_ch = s->k0; | ||
784 | BZ_GET_SMALL(k1); s->nblock_used++; | ||
785 | if (s->nblock_used == s->save_nblock+1) continue; | ||
786 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
787 | |||
788 | s->state_out_len = 2; | ||
789 | BZ_GET_SMALL(k1); s->nblock_used++; | ||
790 | if (s->nblock_used == s->save_nblock+1) continue; | ||
791 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
792 | |||
793 | s->state_out_len = 3; | ||
794 | BZ_GET_SMALL(k1); s->nblock_used++; | ||
795 | if (s->nblock_used == s->save_nblock+1) continue; | ||
796 | if (k1 != s->k0) { s->k0 = k1; continue; }; | ||
797 | |||
798 | BZ_GET_SMALL(k1); s->nblock_used++; | ||
799 | s->state_out_len = ((Int32)k1) + 4; | ||
800 | BZ_GET_SMALL(s->k0); s->nblock_used++; | ||
801 | } | ||
802 | |||
803 | } | ||
804 | } | ||
805 | |||
806 | |||
807 | /*---------------------------------------------------*/ | ||
808 | int BZ_API(BZ2_bzDecompress) ( bz_stream *strm ) | ||
809 | { | ||
810 | Bool corrupt; | ||
811 | DState* s; | ||
812 | if (strm == NULL) return BZ_PARAM_ERROR; | ||
813 | s = strm->state; | ||
814 | if (s == NULL) return BZ_PARAM_ERROR; | ||
815 | if (s->strm != strm) return BZ_PARAM_ERROR; | ||
816 | |||
817 | while (True) { | ||
818 | if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR; | ||
819 | if (s->state == BZ_X_OUTPUT) { | ||
820 | if (s->smallDecompress) | ||
821 | corrupt = unRLE_obuf_to_output_SMALL ( s ); else | ||
822 | corrupt = unRLE_obuf_to_output_FAST ( s ); | ||
823 | if (corrupt) return BZ_DATA_ERROR; | ||
824 | if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) { | ||
825 | BZ_FINALISE_CRC ( s->calculatedBlockCRC ); | ||
826 | if (s->verbosity >= 3) | ||
827 | VPrintf2 ( " {0x%08x, 0x%08x}", s->storedBlockCRC, | ||
828 | s->calculatedBlockCRC ); | ||
829 | if (s->verbosity >= 2) VPrintf0 ( "]" ); | ||
830 | if (s->calculatedBlockCRC != s->storedBlockCRC) | ||
831 | return BZ_DATA_ERROR; | ||
832 | s->calculatedCombinedCRC | ||
833 | = (s->calculatedCombinedCRC << 1) | | ||
834 | (s->calculatedCombinedCRC >> 31); | ||
835 | s->calculatedCombinedCRC ^= s->calculatedBlockCRC; | ||
836 | s->state = BZ_X_BLKHDR_1; | ||
837 | } else { | ||
838 | return BZ_OK; | ||
839 | } | ||
840 | } | ||
841 | if (s->state >= BZ_X_MAGIC_1) { | ||
842 | Int32 r = BZ2_decompress ( s ); | ||
843 | if (r == BZ_STREAM_END) { | ||
844 | if (s->verbosity >= 3) | ||
845 | VPrintf2 ( "\n combined CRCs: stored = 0x%08x, computed = 0x%08x", | ||
846 | s->storedCombinedCRC, s->calculatedCombinedCRC ); | ||
847 | if (s->calculatedCombinedCRC != s->storedCombinedCRC) | ||
848 | return BZ_DATA_ERROR; | ||
849 | return r; | ||
850 | } | ||
851 | if (s->state != BZ_X_OUTPUT) return r; | ||
852 | } | ||
853 | } | ||
854 | |||
855 | AssertH ( 0, 6001 ); | ||
856 | |||
857 | return 0; /*NOTREACHED*/ | ||
858 | } | ||
859 | |||
860 | |||
861 | /*---------------------------------------------------*/ | ||
862 | int BZ_API(BZ2_bzDecompressEnd) ( bz_stream *strm ) | ||
863 | { | ||
864 | DState* s; | ||
865 | if (strm == NULL) return BZ_PARAM_ERROR; | ||
866 | s = strm->state; | ||
867 | if (s == NULL) return BZ_PARAM_ERROR; | ||
868 | if (s->strm != strm) return BZ_PARAM_ERROR; | ||
869 | |||
870 | if (s->tt != NULL) BZFREE(s->tt); | ||
871 | if (s->ll16 != NULL) BZFREE(s->ll16); | ||
872 | if (s->ll4 != NULL) BZFREE(s->ll4); | ||
873 | |||
874 | BZFREE(strm->state); | ||
875 | strm->state = NULL; | ||
876 | |||
877 | return BZ_OK; | ||
878 | } | ||
879 | |||
880 | |||
881 | #ifndef BZ_NO_STDIO | ||
882 | /*---------------------------------------------------*/ | ||
883 | /*--- File I/O stuff ---*/ | ||
884 | /*---------------------------------------------------*/ | ||
885 | |||
886 | #define BZ_SETERR(eee) \ | ||
887 | { \ | ||
888 | if (bzerror != NULL) *bzerror = eee; \ | ||
889 | if (bzf != NULL) bzf->lastErr = eee; \ | ||
890 | } | ||
891 | |||
892 | typedef | ||
893 | struct { | ||
894 | FILE* handle; | ||
895 | Char buf[BZ_MAX_UNUSED]; | ||
896 | Int32 bufN; | ||
897 | Bool writing; | ||
898 | bz_stream strm; | ||
899 | Int32 lastErr; | ||
900 | Bool initialisedOk; | ||
901 | } | ||
902 | bzFile; | ||
903 | |||
904 | |||
905 | /*---------------------------------------------*/ | ||
906 | static Bool myfeof ( FILE* f ) | ||
907 | { | ||
908 | Int32 c = fgetc ( f ); | ||
909 | if (c == EOF) return True; | ||
910 | ungetc ( c, f ); | ||
911 | return False; | ||
912 | } | ||
913 | |||
914 | |||
915 | /*---------------------------------------------------*/ | ||
916 | BZFILE* BZ_API(BZ2_bzWriteOpen) | ||
917 | ( int* bzerror, | ||
918 | FILE* f, | ||
919 | int blockSize100k, | ||
920 | int verbosity, | ||
921 | int workFactor ) | ||
922 | { | ||
923 | Int32 ret; | ||
924 | bzFile* bzf = NULL; | ||
925 | |||
926 | BZ_SETERR(BZ_OK); | ||
927 | |||
928 | if (f == NULL || | ||
929 | (blockSize100k < 1 || blockSize100k > 9) || | ||
930 | (workFactor < 0 || workFactor > 250) || | ||
931 | (verbosity < 0 || verbosity > 4)) | ||
932 | { BZ_SETERR(BZ_PARAM_ERROR); return NULL; }; | ||
933 | |||
934 | if (ferror(f)) | ||
935 | { BZ_SETERR(BZ_IO_ERROR); return NULL; }; | ||
936 | |||
937 | bzf = malloc ( sizeof(bzFile) ); | ||
938 | if (bzf == NULL) | ||
939 | { BZ_SETERR(BZ_MEM_ERROR); return NULL; }; | ||
940 | |||
941 | BZ_SETERR(BZ_OK); | ||
942 | bzf->initialisedOk = False; | ||
943 | bzf->bufN = 0; | ||
944 | bzf->handle = f; | ||
945 | bzf->writing = True; | ||
946 | bzf->strm.bzalloc = NULL; | ||
947 | bzf->strm.bzfree = NULL; | ||
948 | bzf->strm.opaque = NULL; | ||
949 | |||
950 | if (workFactor == 0) workFactor = 30; | ||
951 | ret = BZ2_bzCompressInit ( &(bzf->strm), blockSize100k, | ||
952 | verbosity, workFactor ); | ||
953 | if (ret != BZ_OK) | ||
954 | { BZ_SETERR(ret); free(bzf); return NULL; }; | ||
955 | |||
956 | bzf->strm.avail_in = 0; | ||
957 | bzf->initialisedOk = True; | ||
958 | return bzf; | ||
959 | } | ||
960 | |||
961 | |||
962 | |||
963 | /*---------------------------------------------------*/ | ||
964 | void BZ_API(BZ2_bzWrite) | ||
965 | ( int* bzerror, | ||
966 | BZFILE* b, | ||
967 | void* buf, | ||
968 | int len ) | ||
969 | { | ||
970 | Int32 n, n2, ret; | ||
971 | bzFile* bzf = (bzFile*)b; | ||
972 | |||
973 | BZ_SETERR(BZ_OK); | ||
974 | if (bzf == NULL || buf == NULL || len < 0) | ||
975 | { BZ_SETERR(BZ_PARAM_ERROR); return; }; | ||
976 | if (!(bzf->writing)) | ||
977 | { BZ_SETERR(BZ_SEQUENCE_ERROR); return; }; | ||
978 | if (ferror(bzf->handle)) | ||
979 | { BZ_SETERR(BZ_IO_ERROR); return; }; | ||
980 | |||
981 | if (len == 0) | ||
982 | { BZ_SETERR(BZ_OK); return; }; | ||
983 | |||
984 | bzf->strm.avail_in = len; | ||
985 | bzf->strm.next_in = buf; | ||
986 | |||
987 | while (True) { | ||
988 | bzf->strm.avail_out = BZ_MAX_UNUSED; | ||
989 | bzf->strm.next_out = bzf->buf; | ||
990 | ret = BZ2_bzCompress ( &(bzf->strm), BZ_RUN ); | ||
991 | if (ret != BZ_RUN_OK) | ||
992 | { BZ_SETERR(ret); return; }; | ||
993 | |||
994 | if (bzf->strm.avail_out < BZ_MAX_UNUSED) { | ||
995 | n = BZ_MAX_UNUSED - bzf->strm.avail_out; | ||
996 | n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar), | ||
997 | n, bzf->handle ); | ||
998 | if (n != n2 || ferror(bzf->handle)) | ||
999 | { BZ_SETERR(BZ_IO_ERROR); return; }; | ||
1000 | } | ||
1001 | |||
1002 | if (bzf->strm.avail_in == 0) | ||
1003 | { BZ_SETERR(BZ_OK); return; }; | ||
1004 | } | ||
1005 | } | ||
1006 | |||
1007 | |||
1008 | /*---------------------------------------------------*/ | ||
1009 | void BZ_API(BZ2_bzWriteClose) | ||
1010 | ( int* bzerror, | ||
1011 | BZFILE* b, | ||
1012 | int abandon, | ||
1013 | unsigned int* nbytes_in, | ||
1014 | unsigned int* nbytes_out ) | ||
1015 | { | ||
1016 | BZ2_bzWriteClose64 ( bzerror, b, abandon, | ||
1017 | nbytes_in, NULL, nbytes_out, NULL ); | ||
1018 | } | ||
1019 | |||
1020 | |||
1021 | void BZ_API(BZ2_bzWriteClose64) | ||
1022 | ( int* bzerror, | ||
1023 | BZFILE* b, | ||
1024 | int abandon, | ||
1025 | unsigned int* nbytes_in_lo32, | ||
1026 | unsigned int* nbytes_in_hi32, | ||
1027 | unsigned int* nbytes_out_lo32, | ||
1028 | unsigned int* nbytes_out_hi32 ) | ||
1029 | { | ||
1030 | Int32 n, n2, ret; | ||
1031 | bzFile* bzf = (bzFile*)b; | ||
1032 | |||
1033 | if (bzf == NULL) | ||
1034 | { BZ_SETERR(BZ_OK); return; }; | ||
1035 | if (!(bzf->writing)) | ||
1036 | { BZ_SETERR(BZ_SEQUENCE_ERROR); return; }; | ||
1037 | if (ferror(bzf->handle)) | ||
1038 | { BZ_SETERR(BZ_IO_ERROR); return; }; | ||
1039 | |||
1040 | if (nbytes_in_lo32 != NULL) *nbytes_in_lo32 = 0; | ||
1041 | if (nbytes_in_hi32 != NULL) *nbytes_in_hi32 = 0; | ||
1042 | if (nbytes_out_lo32 != NULL) *nbytes_out_lo32 = 0; | ||
1043 | if (nbytes_out_hi32 != NULL) *nbytes_out_hi32 = 0; | ||
1044 | |||
1045 | if ((!abandon) && bzf->lastErr == BZ_OK) { | ||
1046 | while (True) { | ||
1047 | bzf->strm.avail_out = BZ_MAX_UNUSED; | ||
1048 | bzf->strm.next_out = bzf->buf; | ||
1049 | ret = BZ2_bzCompress ( &(bzf->strm), BZ_FINISH ); | ||
1050 | if (ret != BZ_FINISH_OK && ret != BZ_STREAM_END) | ||
1051 | { BZ_SETERR(ret); return; }; | ||
1052 | |||
1053 | if (bzf->strm.avail_out < BZ_MAX_UNUSED) { | ||
1054 | n = BZ_MAX_UNUSED - bzf->strm.avail_out; | ||
1055 | n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar), | ||
1056 | n, bzf->handle ); | ||
1057 | if (n != n2 || ferror(bzf->handle)) | ||
1058 | { BZ_SETERR(BZ_IO_ERROR); return; }; | ||
1059 | } | ||
1060 | |||
1061 | if (ret == BZ_STREAM_END) break; | ||
1062 | } | ||
1063 | } | ||
1064 | |||
1065 | if ( !abandon && !ferror ( bzf->handle ) ) { | ||
1066 | fflush ( bzf->handle ); | ||
1067 | if (ferror(bzf->handle)) | ||
1068 | { BZ_SETERR(BZ_IO_ERROR); return; }; | ||
1069 | } | ||
1070 | |||
1071 | if (nbytes_in_lo32 != NULL) | ||
1072 | *nbytes_in_lo32 = bzf->strm.total_in_lo32; | ||
1073 | if (nbytes_in_hi32 != NULL) | ||
1074 | *nbytes_in_hi32 = bzf->strm.total_in_hi32; | ||
1075 | if (nbytes_out_lo32 != NULL) | ||
1076 | *nbytes_out_lo32 = bzf->strm.total_out_lo32; | ||
1077 | if (nbytes_out_hi32 != NULL) | ||
1078 | *nbytes_out_hi32 = bzf->strm.total_out_hi32; | ||
1079 | |||
1080 | BZ_SETERR(BZ_OK); | ||
1081 | BZ2_bzCompressEnd ( &(bzf->strm) ); | ||
1082 | free ( bzf ); | ||
1083 | } | ||
1084 | |||
1085 | |||
1086 | /*---------------------------------------------------*/ | ||
1087 | BZFILE* BZ_API(BZ2_bzReadOpen) | ||
1088 | ( int* bzerror, | ||
1089 | FILE* f, | ||
1090 | int verbosity, | ||
1091 | int small, | ||
1092 | void* unused, | ||
1093 | int nUnused ) | ||
1094 | { | ||
1095 | bzFile* bzf = NULL; | ||
1096 | int ret; | ||
1097 | |||
1098 | BZ_SETERR(BZ_OK); | ||
1099 | |||
1100 | if (f == NULL || | ||
1101 | (small != 0 && small != 1) || | ||
1102 | (verbosity < 0 || verbosity > 4) || | ||
1103 | (unused == NULL && nUnused != 0) || | ||
1104 | (unused != NULL && (nUnused < 0 || nUnused > BZ_MAX_UNUSED))) | ||
1105 | { BZ_SETERR(BZ_PARAM_ERROR); return NULL; }; | ||
1106 | |||
1107 | if (ferror(f)) | ||
1108 | { BZ_SETERR(BZ_IO_ERROR); return NULL; }; | ||
1109 | |||
1110 | bzf = malloc ( sizeof(bzFile) ); | ||
1111 | if (bzf == NULL) | ||
1112 | { BZ_SETERR(BZ_MEM_ERROR); return NULL; }; | ||
1113 | |||
1114 | BZ_SETERR(BZ_OK); | ||
1115 | |||
1116 | bzf->initialisedOk = False; | ||
1117 | bzf->handle = f; | ||
1118 | bzf->bufN = 0; | ||
1119 | bzf->writing = False; | ||
1120 | bzf->strm.bzalloc = NULL; | ||
1121 | bzf->strm.bzfree = NULL; | ||
1122 | bzf->strm.opaque = NULL; | ||
1123 | |||
1124 | while (nUnused > 0) { | ||
1125 | bzf->buf[bzf->bufN] = *((UChar*)(unused)); bzf->bufN++; | ||
1126 | unused = ((void*)( 1 + ((UChar*)(unused)) )); | ||
1127 | nUnused--; | ||
1128 | } | ||
1129 | |||
1130 | ret = BZ2_bzDecompressInit ( &(bzf->strm), verbosity, small ); | ||
1131 | if (ret != BZ_OK) | ||
1132 | { BZ_SETERR(ret); free(bzf); return NULL; }; | ||
1133 | |||
1134 | bzf->strm.avail_in = bzf->bufN; | ||
1135 | bzf->strm.next_in = bzf->buf; | ||
1136 | |||
1137 | bzf->initialisedOk = True; | ||
1138 | return bzf; | ||
1139 | } | ||
1140 | |||
1141 | |||
1142 | /*---------------------------------------------------*/ | ||
1143 | void BZ_API(BZ2_bzReadClose) ( int *bzerror, BZFILE *b ) | ||
1144 | { | ||
1145 | bzFile* bzf = (bzFile*)b; | ||
1146 | |||
1147 | BZ_SETERR(BZ_OK); | ||
1148 | if (bzf == NULL) | ||
1149 | { BZ_SETERR(BZ_OK); return; }; | ||
1150 | |||
1151 | if (bzf->writing) | ||
1152 | { BZ_SETERR(BZ_SEQUENCE_ERROR); return; }; | ||
1153 | |||
1154 | if (bzf->initialisedOk) | ||
1155 | (void)BZ2_bzDecompressEnd ( &(bzf->strm) ); | ||
1156 | free ( bzf ); | ||
1157 | } | ||
1158 | |||
1159 | |||
1160 | /*---------------------------------------------------*/ | ||
1161 | int BZ_API(BZ2_bzRead) | ||
1162 | ( int* bzerror, | ||
1163 | BZFILE* b, | ||
1164 | void* buf, | ||
1165 | int len ) | ||
1166 | { | ||
1167 | Int32 n, ret; | ||
1168 | bzFile* bzf = (bzFile*)b; | ||
1169 | |||
1170 | BZ_SETERR(BZ_OK); | ||
1171 | |||
1172 | if (bzf == NULL || buf == NULL || len < 0) | ||
1173 | { BZ_SETERR(BZ_PARAM_ERROR); return 0; }; | ||
1174 | |||
1175 | if (bzf->writing) | ||
1176 | { BZ_SETERR(BZ_SEQUENCE_ERROR); return 0; }; | ||
1177 | |||
1178 | if (len == 0) | ||
1179 | { BZ_SETERR(BZ_OK); return 0; }; | ||
1180 | |||
1181 | bzf->strm.avail_out = len; | ||
1182 | bzf->strm.next_out = buf; | ||
1183 | |||
1184 | while (True) { | ||
1185 | |||
1186 | if (ferror(bzf->handle)) | ||
1187 | { BZ_SETERR(BZ_IO_ERROR); return 0; }; | ||
1188 | |||
1189 | if (bzf->strm.avail_in == 0 && !myfeof(bzf->handle)) { | ||
1190 | n = fread ( bzf->buf, sizeof(UChar), | ||
1191 | BZ_MAX_UNUSED, bzf->handle ); | ||
1192 | if (ferror(bzf->handle)) | ||
1193 | { BZ_SETERR(BZ_IO_ERROR); return 0; }; | ||
1194 | bzf->bufN = n; | ||
1195 | bzf->strm.avail_in = bzf->bufN; | ||
1196 | bzf->strm.next_in = bzf->buf; | ||
1197 | } | ||
1198 | |||
1199 | ret = BZ2_bzDecompress ( &(bzf->strm) ); | ||
1200 | |||
1201 | if (ret != BZ_OK && ret != BZ_STREAM_END) | ||
1202 | { BZ_SETERR(ret); return 0; }; | ||
1203 | |||
1204 | if (ret == BZ_OK && myfeof(bzf->handle) && | ||
1205 | bzf->strm.avail_in == 0 && bzf->strm.avail_out > 0) | ||
1206 | { BZ_SETERR(BZ_UNEXPECTED_EOF); return 0; }; | ||
1207 | |||
1208 | if (ret == BZ_STREAM_END) | ||
1209 | { BZ_SETERR(BZ_STREAM_END); | ||
1210 | return len - bzf->strm.avail_out; }; | ||
1211 | if (bzf->strm.avail_out == 0) | ||
1212 | { BZ_SETERR(BZ_OK); return len; }; | ||
1213 | |||
1214 | } | ||
1215 | |||
1216 | return 0; /*not reached*/ | ||
1217 | } | ||
1218 | |||
1219 | |||
1220 | /*---------------------------------------------------*/ | ||
1221 | void BZ_API(BZ2_bzReadGetUnused) | ||
1222 | ( int* bzerror, | ||
1223 | BZFILE* b, | ||
1224 | void** unused, | ||
1225 | int* nUnused ) | ||
1226 | { | ||
1227 | bzFile* bzf = (bzFile*)b; | ||
1228 | if (bzf == NULL) | ||
1229 | { BZ_SETERR(BZ_PARAM_ERROR); return; }; | ||
1230 | if (bzf->lastErr != BZ_STREAM_END) | ||
1231 | { BZ_SETERR(BZ_SEQUENCE_ERROR); return; }; | ||
1232 | if (unused == NULL || nUnused == NULL) | ||
1233 | { BZ_SETERR(BZ_PARAM_ERROR); return; }; | ||
1234 | |||
1235 | BZ_SETERR(BZ_OK); | ||
1236 | *nUnused = bzf->strm.avail_in; | ||
1237 | *unused = bzf->strm.next_in; | ||
1238 | } | ||
1239 | #endif | ||
1240 | |||
1241 | |||
1242 | /*---------------------------------------------------*/ | ||
1243 | /*--- Misc convenience stuff ---*/ | ||
1244 | /*---------------------------------------------------*/ | ||
1245 | |||
1246 | /*---------------------------------------------------*/ | ||
1247 | int BZ_API(BZ2_bzBuffToBuffCompress) | ||
1248 | ( char* dest, | ||
1249 | unsigned int* destLen, | ||
1250 | char* source, | ||
1251 | unsigned int sourceLen, | ||
1252 | int blockSize100k, | ||
1253 | int verbosity, | ||
1254 | int workFactor ) | ||
1255 | { | ||
1256 | bz_stream strm; | ||
1257 | int ret; | ||
1258 | |||
1259 | if (dest == NULL || destLen == NULL || | ||
1260 | source == NULL || | ||
1261 | blockSize100k < 1 || blockSize100k > 9 || | ||
1262 | verbosity < 0 || verbosity > 4 || | ||
1263 | workFactor < 0 || workFactor > 250) | ||
1264 | return BZ_PARAM_ERROR; | ||
1265 | |||
1266 | if (workFactor == 0) workFactor = 30; | ||
1267 | strm.bzalloc = NULL; | ||
1268 | strm.bzfree = NULL; | ||
1269 | strm.opaque = NULL; | ||
1270 | ret = BZ2_bzCompressInit ( &strm, blockSize100k, | ||
1271 | verbosity, workFactor ); | ||
1272 | if (ret != BZ_OK) return ret; | ||
1273 | |||
1274 | strm.next_in = source; | ||
1275 | strm.next_out = dest; | ||
1276 | strm.avail_in = sourceLen; | ||
1277 | strm.avail_out = *destLen; | ||
1278 | |||
1279 | ret = BZ2_bzCompress ( &strm, BZ_FINISH ); | ||
1280 | if (ret == BZ_FINISH_OK) goto output_overflow; | ||
1281 | if (ret != BZ_STREAM_END) goto errhandler; | ||
1282 | |||
1283 | /* normal termination */ | ||
1284 | *destLen -= strm.avail_out; | ||
1285 | BZ2_bzCompressEnd ( &strm ); | ||
1286 | return BZ_OK; | ||
1287 | |||
1288 | output_overflow: | ||
1289 | BZ2_bzCompressEnd ( &strm ); | ||
1290 | return BZ_OUTBUFF_FULL; | ||
1291 | |||
1292 | errhandler: | ||
1293 | BZ2_bzCompressEnd ( &strm ); | ||
1294 | return ret; | ||
1295 | } | ||
1296 | |||
1297 | |||
1298 | /*---------------------------------------------------*/ | ||
1299 | int BZ_API(BZ2_bzBuffToBuffDecompress) | ||
1300 | ( char* dest, | ||
1301 | unsigned int* destLen, | ||
1302 | char* source, | ||
1303 | unsigned int sourceLen, | ||
1304 | int small, | ||
1305 | int verbosity ) | ||
1306 | { | ||
1307 | bz_stream strm; | ||
1308 | int ret; | ||
1309 | |||
1310 | if (dest == NULL || destLen == NULL || | ||
1311 | source == NULL || | ||
1312 | (small != 0 && small != 1) || | ||
1313 | verbosity < 0 || verbosity > 4) | ||
1314 | return BZ_PARAM_ERROR; | ||
1315 | |||
1316 | strm.bzalloc = NULL; | ||
1317 | strm.bzfree = NULL; | ||
1318 | strm.opaque = NULL; | ||
1319 | ret = BZ2_bzDecompressInit ( &strm, verbosity, small ); | ||
1320 | if (ret != BZ_OK) return ret; | ||
1321 | |||
1322 | strm.next_in = source; | ||
1323 | strm.next_out = dest; | ||
1324 | strm.avail_in = sourceLen; | ||
1325 | strm.avail_out = *destLen; | ||
1326 | |||
1327 | ret = BZ2_bzDecompress ( &strm ); | ||
1328 | if (ret == BZ_OK) goto output_overflow_or_eof; | ||
1329 | if (ret != BZ_STREAM_END) goto errhandler; | ||
1330 | |||
1331 | /* normal termination */ | ||
1332 | *destLen -= strm.avail_out; | ||
1333 | BZ2_bzDecompressEnd ( &strm ); | ||
1334 | return BZ_OK; | ||
1335 | |||
1336 | output_overflow_or_eof: | ||
1337 | if (strm.avail_out > 0) { | ||
1338 | BZ2_bzDecompressEnd ( &strm ); | ||
1339 | return BZ_UNEXPECTED_EOF; | ||
1340 | } else { | ||
1341 | BZ2_bzDecompressEnd ( &strm ); | ||
1342 | return BZ_OUTBUFF_FULL; | ||
1343 | }; | ||
1344 | |||
1345 | errhandler: | ||
1346 | BZ2_bzDecompressEnd ( &strm ); | ||
1347 | return ret; | ||
1348 | } | ||
1349 | |||
1350 | |||
1351 | /*---------------------------------------------------*/ | ||
1352 | /*-- | ||
1353 | Code contributed by Yoshioka Tsuneo (tsuneo@rr.iij4u.or.jp) | ||
1354 | to support better zlib compatibility. | ||
1355 | This code is not _officially_ part of libbzip2 (yet); | ||
1356 | I haven't tested it, documented it, or considered the | ||
1357 | threading-safeness of it. | ||
1358 | If this code breaks, please contact both Yoshioka and me. | ||
1359 | --*/ | ||
1360 | /*---------------------------------------------------*/ | ||
1361 | |||
1362 | /*---------------------------------------------------*/ | ||
1363 | /*-- | ||
1364 | return version like "0.9.5d, 4-Sept-1999". | ||
1365 | --*/ | ||
1366 | const char * BZ_API(BZ2_bzlibVersion)(void) | ||
1367 | { | ||
1368 | return BZ_VERSION; | ||
1369 | } | ||
1370 | |||
1371 | |||
1372 | #ifndef BZ_NO_STDIO | ||
1373 | /*---------------------------------------------------*/ | ||
1374 | |||
1375 | #if defined(_WIN32) || defined(OS2) || defined(MSDOS) | ||
1376 | # include <fcntl.h> | ||
1377 | # include <io.h> | ||
1378 | # define SET_BINARY_MODE(file) _setmode(_fileno(file),O_BINARY) | ||
1379 | #else | ||
1380 | # define SET_BINARY_MODE(file) | ||
1381 | #endif | ||
1382 | static | ||
1383 | BZFILE * bzopen_or_bzdopen | ||
1384 | ( const char *path, /* no use when bzdopen */ | ||
1385 | int fd, /* no use when bzdopen */ | ||
1386 | const char *mode, | ||
1387 | int open_mode) /* bzopen: 0, bzdopen:1 */ | ||
1388 | { | ||
1389 | int bzerr; | ||
1390 | char unused[BZ_MAX_UNUSED]; | ||
1391 | int blockSize100k = 9; | ||
1392 | int writing = 0; | ||
1393 | char mode2[10] = ""; | ||
1394 | FILE *fp = NULL; | ||
1395 | BZFILE *bzfp = NULL; | ||
1396 | int verbosity = 0; | ||
1397 | int workFactor = 30; | ||
1398 | int smallMode = 0; | ||
1399 | int nUnused = 0; | ||
1400 | |||
1401 | if (mode == NULL) return NULL; | ||
1402 | while (*mode) { | ||
1403 | switch (*mode) { | ||
1404 | case 'r': | ||
1405 | writing = 0; break; | ||
1406 | case 'w': | ||
1407 | writing = 1; break; | ||
1408 | case 's': | ||
1409 | smallMode = 1; break; | ||
1410 | default: | ||
1411 | if (isdigit((int)(*mode))) { | ||
1412 | blockSize100k = *mode-BZ_HDR_0; | ||
1413 | } | ||
1414 | } | ||
1415 | mode++; | ||
1416 | } | ||
1417 | strcat(mode2, writing ? "w" : "r" ); | ||
1418 | strcat(mode2,"b"); /* binary mode */ | ||
1419 | |||
1420 | if (open_mode==0) { | ||
1421 | if (path==NULL || strcmp(path,"")==0) { | ||
1422 | fp = (writing ? stdout : stdin); | ||
1423 | SET_BINARY_MODE(fp); | ||
1424 | } else { | ||
1425 | fp = fopen(path,mode2); | ||
1426 | } | ||
1427 | } else { | ||
1428 | #ifdef BZ_STRICT_ANSI | ||
1429 | fp = NULL; | ||
1430 | #else | ||
1431 | fp = _fdopen(fd,mode2); | ||
1432 | #endif | ||
1433 | } | ||
1434 | if (fp == NULL) return NULL; | ||
1435 | |||
1436 | if (writing) { | ||
1437 | /* Guard against total chaos and anarchy -- JRS */ | ||
1438 | if (blockSize100k < 1) blockSize100k = 1; | ||
1439 | if (blockSize100k > 9) blockSize100k = 9; | ||
1440 | bzfp = BZ2_bzWriteOpen(&bzerr,fp,blockSize100k, | ||
1441 | verbosity,workFactor); | ||
1442 | } else { | ||
1443 | bzfp = BZ2_bzReadOpen(&bzerr,fp,verbosity,smallMode, | ||
1444 | unused,nUnused); | ||
1445 | } | ||
1446 | if (bzfp == NULL) { | ||
1447 | if (fp != stdin && fp != stdout) fclose(fp); | ||
1448 | return NULL; | ||
1449 | } | ||
1450 | return bzfp; | ||
1451 | } | ||
1452 | |||
1453 | |||
1454 | /*---------------------------------------------------*/ | ||
1455 | /*-- | ||
1456 | open file for read or write. | ||
1457 | ex) bzopen("file","w9") | ||
1458 | case path="" or NULL => use stdin or stdout. | ||
1459 | --*/ | ||
1460 | BZFILE * BZ_API(BZ2_bzopen) | ||
1461 | ( const char *path, | ||
1462 | const char *mode ) | ||
1463 | { | ||
1464 | return bzopen_or_bzdopen(path,-1,mode,/*bzopen*/0); | ||
1465 | } | ||
1466 | |||
1467 | |||
1468 | /*---------------------------------------------------*/ | ||
1469 | BZFILE * BZ_API(BZ2_bzdopen) | ||
1470 | ( int fd, | ||
1471 | const char *mode ) | ||
1472 | { | ||
1473 | return bzopen_or_bzdopen(NULL,fd,mode,/*bzdopen*/1); | ||
1474 | } | ||
1475 | |||
1476 | |||
1477 | /*---------------------------------------------------*/ | ||
1478 | int BZ_API(BZ2_bzread) (BZFILE* b, void* buf, int len ) | ||
1479 | { | ||
1480 | int bzerr, nread; | ||
1481 | if (((bzFile*)b)->lastErr == BZ_STREAM_END) return 0; | ||
1482 | nread = BZ2_bzRead(&bzerr,b,buf,len); | ||
1483 | if (bzerr == BZ_OK || bzerr == BZ_STREAM_END) { | ||
1484 | return nread; | ||
1485 | } else { | ||
1486 | return -1; | ||
1487 | } | ||
1488 | } | ||
1489 | |||
1490 | |||
1491 | /*---------------------------------------------------*/ | ||
1492 | int BZ_API(BZ2_bzwrite) (BZFILE* b, void* buf, int len ) | ||
1493 | { | ||
1494 | int bzerr; | ||
1495 | |||
1496 | BZ2_bzWrite(&bzerr,b,buf,len); | ||
1497 | if(bzerr == BZ_OK){ | ||
1498 | return len; | ||
1499 | }else{ | ||
1500 | return -1; | ||
1501 | } | ||
1502 | } | ||
1503 | |||
1504 | |||
1505 | /*---------------------------------------------------*/ | ||
1506 | int BZ_API(BZ2_bzflush) (BZFILE *b) | ||
1507 | { | ||
1508 | /* do nothing now... */ | ||
1509 | return 0; | ||
1510 | } | ||
1511 | |||
1512 | |||
1513 | /*---------------------------------------------------*/ | ||
1514 | void BZ_API(BZ2_bzclose) (BZFILE* b) | ||
1515 | { | ||
1516 | int bzerr; | ||
1517 | FILE *fp; | ||
1518 | |||
1519 | if (b==NULL) {return;} | ||
1520 | fp = ((bzFile *)b)->handle; | ||
1521 | if(((bzFile*)b)->writing){ | ||
1522 | BZ2_bzWriteClose(&bzerr,b,0,NULL,NULL); | ||
1523 | if(bzerr != BZ_OK){ | ||
1524 | BZ2_bzWriteClose(NULL,b,1,NULL,NULL); | ||
1525 | } | ||
1526 | }else{ | ||
1527 | BZ2_bzReadClose(&bzerr,b); | ||
1528 | } | ||
1529 | if(fp!=stdin && fp!=stdout){ | ||
1530 | fclose(fp); | ||
1531 | } | ||
1532 | } | ||
1533 | |||
1534 | |||
1535 | /*---------------------------------------------------*/ | ||
1536 | /*-- | ||
1537 | return last error code | ||
1538 | --*/ | ||
1539 | static const char *bzerrorstrings[] = { | ||
1540 | "OK" | ||
1541 | ,"SEQUENCE_ERROR" | ||
1542 | ,"PARAM_ERROR" | ||
1543 | ,"MEM_ERROR" | ||
1544 | ,"DATA_ERROR" | ||
1545 | ,"DATA_ERROR_MAGIC" | ||
1546 | ,"IO_ERROR" | ||
1547 | ,"UNEXPECTED_EOF" | ||
1548 | ,"OUTBUFF_FULL" | ||
1549 | ,"CONFIG_ERROR" | ||
1550 | ,"???" /* for future */ | ||
1551 | ,"???" /* for future */ | ||
1552 | ,"???" /* for future */ | ||
1553 | ,"???" /* for future */ | ||
1554 | ,"???" /* for future */ | ||
1555 | ,"???" /* for future */ | ||
1556 | }; | ||
1557 | |||
1558 | |||
1559 | const char * BZ_API(BZ2_bzerror) (BZFILE *b, int *errnum) | ||
1560 | { | ||
1561 | int err = ((bzFile *)b)->lastErr; | ||
1562 | |||
1563 | if(err>0) err = 0; | ||
1564 | *errnum = err; | ||
1565 | return bzerrorstrings[err*-1]; | ||
1566 | } | ||
1567 | #endif | ||
1568 | |||
1569 | |||
1570 | /*-------------------------------------------------------------*/ | ||
1571 | /*--- end bzlib.c ---*/ | ||
1572 | /*-------------------------------------------------------------*/ | ||
diff --git a/utils/bzip2/bzlib.h b/utils/bzip2/bzlib.h new file mode 100644 index 0000000000..8277123da8 --- /dev/null +++ b/utils/bzip2/bzlib.h | |||
@@ -0,0 +1,282 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Public header file for the library. ---*/ | ||
4 | /*--- bzlib.h ---*/ | ||
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 <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 | #ifndef _BZLIB_H | ||
23 | #define _BZLIB_H | ||
24 | |||
25 | #ifdef __cplusplus | ||
26 | extern "C" { | ||
27 | #endif | ||
28 | |||
29 | #define BZ_RUN 0 | ||
30 | #define BZ_FLUSH 1 | ||
31 | #define BZ_FINISH 2 | ||
32 | |||
33 | #define BZ_OK 0 | ||
34 | #define BZ_RUN_OK 1 | ||
35 | #define BZ_FLUSH_OK 2 | ||
36 | #define BZ_FINISH_OK 3 | ||
37 | #define BZ_STREAM_END 4 | ||
38 | #define BZ_SEQUENCE_ERROR (-1) | ||
39 | #define BZ_PARAM_ERROR (-2) | ||
40 | #define BZ_MEM_ERROR (-3) | ||
41 | #define BZ_DATA_ERROR (-4) | ||
42 | #define BZ_DATA_ERROR_MAGIC (-5) | ||
43 | #define BZ_IO_ERROR (-6) | ||
44 | #define BZ_UNEXPECTED_EOF (-7) | ||
45 | #define BZ_OUTBUFF_FULL (-8) | ||
46 | #define BZ_CONFIG_ERROR (-9) | ||
47 | |||
48 | typedef | ||
49 | struct { | ||
50 | char *next_in; | ||
51 | unsigned int avail_in; | ||
52 | unsigned int total_in_lo32; | ||
53 | unsigned int total_in_hi32; | ||
54 | |||
55 | char *next_out; | ||
56 | unsigned int avail_out; | ||
57 | unsigned int total_out_lo32; | ||
58 | unsigned int total_out_hi32; | ||
59 | |||
60 | void *state; | ||
61 | |||
62 | void *(*bzalloc)(void *,int,int); | ||
63 | void (*bzfree)(void *,void *); | ||
64 | void *opaque; | ||
65 | } | ||
66 | bz_stream; | ||
67 | |||
68 | |||
69 | #ifndef BZ_IMPORT | ||
70 | #define BZ_EXPORT | ||
71 | #endif | ||
72 | |||
73 | #ifndef BZ_NO_STDIO | ||
74 | /* Need a definitition for FILE */ | ||
75 | #include <stdio.h> | ||
76 | #endif | ||
77 | |||
78 | #ifdef _WIN32 | ||
79 | # include <windows.h> | ||
80 | # ifdef small | ||
81 | /* windows.h define small to char */ | ||
82 | # undef small | ||
83 | # endif | ||
84 | # ifdef BZ_EXPORT | ||
85 | # define BZ_API(func) WINAPI func | ||
86 | # define BZ_EXTERN extern | ||
87 | # else | ||
88 | /* import windows dll dynamically */ | ||
89 | # define BZ_API(func) (WINAPI * func) | ||
90 | # define BZ_EXTERN | ||
91 | # endif | ||
92 | #else | ||
93 | # define BZ_API(func) func | ||
94 | # define BZ_EXTERN extern | ||
95 | #endif | ||
96 | |||
97 | |||
98 | /*-- Core (low-level) library functions --*/ | ||
99 | |||
100 | BZ_EXTERN int BZ_API(BZ2_bzCompressInit) ( | ||
101 | bz_stream* strm, | ||
102 | int blockSize100k, | ||
103 | int verbosity, | ||
104 | int workFactor | ||
105 | ); | ||
106 | |||
107 | BZ_EXTERN int BZ_API(BZ2_bzCompress) ( | ||
108 | bz_stream* strm, | ||
109 | int action | ||
110 | ); | ||
111 | |||
112 | BZ_EXTERN int BZ_API(BZ2_bzCompressEnd) ( | ||
113 | bz_stream* strm | ||
114 | ); | ||
115 | |||
116 | BZ_EXTERN int BZ_API(BZ2_bzDecompressInit) ( | ||
117 | bz_stream *strm, | ||
118 | int verbosity, | ||
119 | int small | ||
120 | ); | ||
121 | |||
122 | BZ_EXTERN int BZ_API(BZ2_bzDecompress) ( | ||
123 | bz_stream* strm | ||
124 | ); | ||
125 | |||
126 | BZ_EXTERN int BZ_API(BZ2_bzDecompressEnd) ( | ||
127 | bz_stream *strm | ||
128 | ); | ||
129 | |||
130 | |||
131 | |||
132 | /*-- High(er) level library functions --*/ | ||
133 | |||
134 | #ifndef BZ_NO_STDIO | ||
135 | #define BZ_MAX_UNUSED 5000 | ||
136 | |||
137 | typedef void BZFILE; | ||
138 | |||
139 | BZ_EXTERN BZFILE* BZ_API(BZ2_bzReadOpen) ( | ||
140 | int* bzerror, | ||
141 | FILE* f, | ||
142 | int verbosity, | ||
143 | int small, | ||
144 | void* unused, | ||
145 | int nUnused | ||
146 | ); | ||
147 | |||
148 | BZ_EXTERN void BZ_API(BZ2_bzReadClose) ( | ||
149 | int* bzerror, | ||
150 | BZFILE* b | ||
151 | ); | ||
152 | |||
153 | BZ_EXTERN void BZ_API(BZ2_bzReadGetUnused) ( | ||
154 | int* bzerror, | ||
155 | BZFILE* b, | ||
156 | void** unused, | ||
157 | int* nUnused | ||
158 | ); | ||
159 | |||
160 | BZ_EXTERN int BZ_API(BZ2_bzRead) ( | ||
161 | int* bzerror, | ||
162 | BZFILE* b, | ||
163 | void* buf, | ||
164 | int len | ||
165 | ); | ||
166 | |||
167 | BZ_EXTERN BZFILE* BZ_API(BZ2_bzWriteOpen) ( | ||
168 | int* bzerror, | ||
169 | FILE* f, | ||
170 | int blockSize100k, | ||
171 | int verbosity, | ||
172 | int workFactor | ||
173 | ); | ||
174 | |||
175 | BZ_EXTERN void BZ_API(BZ2_bzWrite) ( | ||
176 | int* bzerror, | ||
177 | BZFILE* b, | ||
178 | void* buf, | ||
179 | int len | ||
180 | ); | ||
181 | |||
182 | BZ_EXTERN void BZ_API(BZ2_bzWriteClose) ( | ||
183 | int* bzerror, | ||
184 | BZFILE* b, | ||
185 | int abandon, | ||
186 | unsigned int* nbytes_in, | ||
187 | unsigned int* nbytes_out | ||
188 | ); | ||
189 | |||
190 | BZ_EXTERN void BZ_API(BZ2_bzWriteClose64) ( | ||
191 | int* bzerror, | ||
192 | BZFILE* b, | ||
193 | int abandon, | ||
194 | unsigned int* nbytes_in_lo32, | ||
195 | unsigned int* nbytes_in_hi32, | ||
196 | unsigned int* nbytes_out_lo32, | ||
197 | unsigned int* nbytes_out_hi32 | ||
198 | ); | ||
199 | #endif | ||
200 | |||
201 | |||
202 | /*-- Utility functions --*/ | ||
203 | |||
204 | BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffCompress) ( | ||
205 | char* dest, | ||
206 | unsigned int* destLen, | ||
207 | char* source, | ||
208 | unsigned int sourceLen, | ||
209 | int blockSize100k, | ||
210 | int verbosity, | ||
211 | int workFactor | ||
212 | ); | ||
213 | |||
214 | BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffDecompress) ( | ||
215 | char* dest, | ||
216 | unsigned int* destLen, | ||
217 | char* source, | ||
218 | unsigned int sourceLen, | ||
219 | int small, | ||
220 | int verbosity | ||
221 | ); | ||
222 | |||
223 | |||
224 | /*-- | ||
225 | Code contributed by Yoshioka Tsuneo (tsuneo@rr.iij4u.or.jp) | ||
226 | to support better zlib compatibility. | ||
227 | This code is not _officially_ part of libbzip2 (yet); | ||
228 | I haven't tested it, documented it, or considered the | ||
229 | threading-safeness of it. | ||
230 | If this code breaks, please contact both Yoshioka and me. | ||
231 | --*/ | ||
232 | |||
233 | BZ_EXTERN const char * BZ_API(BZ2_bzlibVersion) ( | ||
234 | void | ||
235 | ); | ||
236 | |||
237 | #ifndef BZ_NO_STDIO | ||
238 | BZ_EXTERN BZFILE * BZ_API(BZ2_bzopen) ( | ||
239 | const char *path, | ||
240 | const char *mode | ||
241 | ); | ||
242 | |||
243 | BZ_EXTERN BZFILE * BZ_API(BZ2_bzdopen) ( | ||
244 | int fd, | ||
245 | const char *mode | ||
246 | ); | ||
247 | |||
248 | BZ_EXTERN int BZ_API(BZ2_bzread) ( | ||
249 | BZFILE* b, | ||
250 | void* buf, | ||
251 | int len | ||
252 | ); | ||
253 | |||
254 | BZ_EXTERN int BZ_API(BZ2_bzwrite) ( | ||
255 | BZFILE* b, | ||
256 | void* buf, | ||
257 | int len | ||
258 | ); | ||
259 | |||
260 | BZ_EXTERN int BZ_API(BZ2_bzflush) ( | ||
261 | BZFILE* b | ||
262 | ); | ||
263 | |||
264 | BZ_EXTERN void BZ_API(BZ2_bzclose) ( | ||
265 | BZFILE* b | ||
266 | ); | ||
267 | |||
268 | BZ_EXTERN const char * BZ_API(BZ2_bzerror) ( | ||
269 | BZFILE *b, | ||
270 | int *errnum | ||
271 | ); | ||
272 | #endif | ||
273 | |||
274 | #ifdef __cplusplus | ||
275 | } | ||
276 | #endif | ||
277 | |||
278 | #endif | ||
279 | |||
280 | /*-------------------------------------------------------------*/ | ||
281 | /*--- end bzlib.h ---*/ | ||
282 | /*-------------------------------------------------------------*/ | ||
diff --git a/utils/bzip2/bzlib_private.h b/utils/bzip2/bzlib_private.h new file mode 100644 index 0000000000..d2b1a97ccb --- /dev/null +++ b/utils/bzip2/bzlib_private.h | |||
@@ -0,0 +1,512 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Private header file for the library. ---*/ | ||
4 | /*--- bzlib_private.h ---*/ | ||
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 <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 | #ifndef _BZLIB_PRIVATE_H | ||
23 | #define _BZLIB_PRIVATE_H | ||
24 | |||
25 | #include <stdlib.h> | ||
26 | |||
27 | #ifndef BZ_NO_STDIO | ||
28 | #include <stdio.h> | ||
29 | #include <ctype.h> | ||
30 | #include <string.h> | ||
31 | #endif | ||
32 | |||
33 | #include "bzlib.h" | ||
34 | |||
35 | |||
36 | |||
37 | /*-- General stuff. --*/ | ||
38 | |||
39 | #define BZ_VERSION "1.0.6, 6-Sept-2010" | ||
40 | |||
41 | typedef char Char; | ||
42 | typedef unsigned char Bool; | ||
43 | typedef unsigned char UChar; | ||
44 | typedef int Int32; | ||
45 | typedef unsigned int UInt32; | ||
46 | typedef short Int16; | ||
47 | typedef unsigned short UInt16; | ||
48 | |||
49 | #define True ((Bool)1) | ||
50 | #define False ((Bool)0) | ||
51 | |||
52 | #ifndef __GNUC__ | ||
53 | #define __inline__ /* */ | ||
54 | #endif | ||
55 | |||
56 | #ifndef BZ_NO_STDIO | ||
57 | |||
58 | extern void BZ2_bz__AssertH__fail ( int errcode ); | ||
59 | #define AssertH(cond,errcode) \ | ||
60 | { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); } | ||
61 | |||
62 | #if BZ_DEBUG | ||
63 | #define AssertD(cond,msg) \ | ||
64 | { if (!(cond)) { \ | ||
65 | fprintf ( stderr, \ | ||
66 | "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\ | ||
67 | exit(1); \ | ||
68 | }} | ||
69 | #else | ||
70 | #define AssertD(cond,msg) /* */ | ||
71 | #endif | ||
72 | |||
73 | #define VPrintf0(zf) \ | ||
74 | fprintf(stderr,zf) | ||
75 | #define VPrintf1(zf,za1) \ | ||
76 | fprintf(stderr,zf,za1) | ||
77 | #define VPrintf2(zf,za1,za2) \ | ||
78 | fprintf(stderr,zf,za1,za2) | ||
79 | #define VPrintf3(zf,za1,za2,za3) \ | ||
80 | fprintf(stderr,zf,za1,za2,za3) | ||
81 | #define VPrintf4(zf,za1,za2,za3,za4) \ | ||
82 | fprintf(stderr,zf,za1,za2,za3,za4) | ||
83 | #define VPrintf5(zf,za1,za2,za3,za4,za5) \ | ||
84 | fprintf(stderr,zf,za1,za2,za3,za4,za5) | ||
85 | |||
86 | #else | ||
87 | |||
88 | extern void bz_internal_error ( int errcode ); | ||
89 | #define AssertH(cond,errcode) \ | ||
90 | { if (!(cond)) bz_internal_error ( errcode ); } | ||
91 | #define AssertD(cond,msg) do { } while (0) | ||
92 | #define VPrintf0(zf) do { } while (0) | ||
93 | #define VPrintf1(zf,za1) do { } while (0) | ||
94 | #define VPrintf2(zf,za1,za2) do { } while (0) | ||
95 | #define VPrintf3(zf,za1,za2,za3) do { } while (0) | ||
96 | #define VPrintf4(zf,za1,za2,za3,za4) do { } while (0) | ||
97 | #define VPrintf5(zf,za1,za2,za3,za4,za5) do { } while (0) | ||
98 | |||
99 | #endif | ||
100 | |||
101 | |||
102 | #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1) | ||
103 | #define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp)) | ||
104 | |||
105 | |||
106 | /*-- Header bytes. --*/ | ||
107 | |||
108 | #define BZ_HDR_B 0x42 /* 'B' */ | ||
109 | #define BZ_HDR_Z 0x5a /* 'Z' */ | ||
110 | #define BZ_HDR_h 0x68 /* 'h' */ | ||
111 | #define BZ_HDR_0 0x30 /* '0' */ | ||
112 | |||
113 | /*-- Constants for the back end. --*/ | ||
114 | |||
115 | #define BZ_MAX_ALPHA_SIZE 258 | ||
116 | #define BZ_MAX_CODE_LEN 23 | ||
117 | |||
118 | #define BZ_RUNA 0 | ||
119 | #define BZ_RUNB 1 | ||
120 | |||
121 | #define BZ_N_GROUPS 6 | ||
122 | #define BZ_G_SIZE 50 | ||
123 | #define BZ_N_ITERS 4 | ||
124 | |||
125 | #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE)) | ||
126 | |||
127 | |||
128 | |||
129 | /*-- Stuff for randomising repetitive blocks. --*/ | ||
130 | |||
131 | extern Int32 BZ2_rNums[512]; | ||
132 | |||
133 | #define BZ_RAND_DECLS \ | ||
134 | Int32 rNToGo; \ | ||
135 | Int32 rTPos \ | ||
136 | |||
137 | #define BZ_RAND_INIT_MASK \ | ||
138 | s->rNToGo = 0; \ | ||
139 | s->rTPos = 0 \ | ||
140 | |||
141 | #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0) | ||
142 | |||
143 | #define BZ_RAND_UPD_MASK \ | ||
144 | if (s->rNToGo == 0) { \ | ||
145 | s->rNToGo = BZ2_rNums[s->rTPos]; \ | ||
146 | s->rTPos++; \ | ||
147 | if (s->rTPos == 512) s->rTPos = 0; \ | ||
148 | } \ | ||
149 | s->rNToGo--; | ||
150 | |||
151 | |||
152 | |||
153 | /*-- Stuff for doing CRCs. --*/ | ||
154 | |||
155 | extern UInt32 BZ2_crc32Table[256]; | ||
156 | |||
157 | #define BZ_INITIALISE_CRC(crcVar) \ | ||
158 | { \ | ||
159 | crcVar = 0xffffffffL; \ | ||
160 | } | ||
161 | |||
162 | #define BZ_FINALISE_CRC(crcVar) \ | ||
163 | { \ | ||
164 | crcVar = ~(crcVar); \ | ||
165 | } | ||
166 | |||
167 | #define BZ_UPDATE_CRC(crcVar,cha) \ | ||
168 | { \ | ||
169 | crcVar = (crcVar << 8) ^ \ | ||
170 | BZ2_crc32Table[(crcVar >> 24) ^ \ | ||
171 | ((UChar)cha)]; \ | ||
172 | } | ||
173 | |||
174 | |||
175 | |||
176 | /*-- States and modes for compression. --*/ | ||
177 | |||
178 | #define BZ_M_IDLE 1 | ||
179 | #define BZ_M_RUNNING 2 | ||
180 | #define BZ_M_FLUSHING 3 | ||
181 | #define BZ_M_FINISHING 4 | ||
182 | |||
183 | #define BZ_S_OUTPUT 1 | ||
184 | #define BZ_S_INPUT 2 | ||
185 | |||
186 | #define BZ_N_RADIX 2 | ||
187 | #define BZ_N_QSORT 12 | ||
188 | #define BZ_N_SHELL 18 | ||
189 | #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2) | ||
190 | |||
191 | |||
192 | |||
193 | |||
194 | /*-- Structure holding all the compression-side stuff. --*/ | ||
195 | |||
196 | typedef | ||
197 | struct { | ||
198 | /* pointer back to the struct bz_stream */ | ||
199 | bz_stream* strm; | ||
200 | |||
201 | /* mode this stream is in, and whether inputting */ | ||
202 | /* or outputting data */ | ||
203 | Int32 mode; | ||
204 | Int32 state; | ||
205 | |||
206 | /* remembers avail_in when flush/finish requested */ | ||
207 | UInt32 avail_in_expect; | ||
208 | |||
209 | /* for doing the block sorting */ | ||
210 | UInt32* arr1; | ||
211 | UInt32* arr2; | ||
212 | UInt32* ftab; | ||
213 | Int32 origPtr; | ||
214 | |||
215 | /* aliases for arr1 and arr2 */ | ||
216 | UInt32* ptr; | ||
217 | UChar* block; | ||
218 | UInt16* mtfv; | ||
219 | UChar* zbits; | ||
220 | |||
221 | /* for deciding when to use the fallback sorting algorithm */ | ||
222 | Int32 workFactor; | ||
223 | |||
224 | /* run-length-encoding of the input */ | ||
225 | UInt32 state_in_ch; | ||
226 | Int32 state_in_len; | ||
227 | BZ_RAND_DECLS; | ||
228 | |||
229 | /* input and output limits and current posns */ | ||
230 | Int32 nblock; | ||
231 | Int32 nblockMAX; | ||
232 | Int32 numZ; | ||
233 | Int32 state_out_pos; | ||
234 | |||
235 | /* map of bytes used in block */ | ||
236 | Int32 nInUse; | ||
237 | Bool inUse[256]; | ||
238 | UChar unseqToSeq[256]; | ||
239 | |||
240 | /* the buffer for bit stream creation */ | ||
241 | UInt32 bsBuff; | ||
242 | Int32 bsLive; | ||
243 | |||
244 | /* block and combined CRCs */ | ||
245 | UInt32 blockCRC; | ||
246 | UInt32 combinedCRC; | ||
247 | |||
248 | /* misc administratium */ | ||
249 | Int32 verbosity; | ||
250 | Int32 blockNo; | ||
251 | Int32 blockSize100k; | ||
252 | |||
253 | /* stuff for coding the MTF values */ | ||
254 | Int32 nMTF; | ||
255 | Int32 mtfFreq [BZ_MAX_ALPHA_SIZE]; | ||
256 | UChar selector [BZ_MAX_SELECTORS]; | ||
257 | UChar selectorMtf[BZ_MAX_SELECTORS]; | ||
258 | |||
259 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
260 | Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
261 | Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
262 | /* second dimension: only 3 needed; 4 makes index calculations faster */ | ||
263 | UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4]; | ||
264 | |||
265 | } | ||
266 | EState; | ||
267 | |||
268 | |||
269 | |||
270 | /*-- externs for compression. --*/ | ||
271 | |||
272 | extern void | ||
273 | BZ2_blockSort ( EState* ); | ||
274 | |||
275 | extern void | ||
276 | BZ2_compressBlock ( EState*, Bool ); | ||
277 | |||
278 | extern void | ||
279 | BZ2_bsInitWrite ( EState* ); | ||
280 | |||
281 | extern void | ||
282 | BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 ); | ||
283 | |||
284 | extern void | ||
285 | BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 ); | ||
286 | |||
287 | |||
288 | |||
289 | /*-- states for decompression. --*/ | ||
290 | |||
291 | #define BZ_X_IDLE 1 | ||
292 | #define BZ_X_OUTPUT 2 | ||
293 | |||
294 | #define BZ_X_MAGIC_1 10 | ||
295 | #define BZ_X_MAGIC_2 11 | ||
296 | #define BZ_X_MAGIC_3 12 | ||
297 | #define BZ_X_MAGIC_4 13 | ||
298 | #define BZ_X_BLKHDR_1 14 | ||
299 | #define BZ_X_BLKHDR_2 15 | ||
300 | #define BZ_X_BLKHDR_3 16 | ||
301 | #define BZ_X_BLKHDR_4 17 | ||
302 | #define BZ_X_BLKHDR_5 18 | ||
303 | #define BZ_X_BLKHDR_6 19 | ||
304 | #define BZ_X_BCRC_1 20 | ||
305 | #define BZ_X_BCRC_2 21 | ||
306 | #define BZ_X_BCRC_3 22 | ||
307 | #define BZ_X_BCRC_4 23 | ||
308 | #define BZ_X_RANDBIT 24 | ||
309 | #define BZ_X_ORIGPTR_1 25 | ||
310 | #define BZ_X_ORIGPTR_2 26 | ||
311 | #define BZ_X_ORIGPTR_3 27 | ||
312 | #define BZ_X_MAPPING_1 28 | ||
313 | #define BZ_X_MAPPING_2 29 | ||
314 | #define BZ_X_SELECTOR_1 30 | ||
315 | #define BZ_X_SELECTOR_2 31 | ||
316 | #define BZ_X_SELECTOR_3 32 | ||
317 | #define BZ_X_CODING_1 33 | ||
318 | #define BZ_X_CODING_2 34 | ||
319 | #define BZ_X_CODING_3 35 | ||
320 | #define BZ_X_MTF_1 36 | ||
321 | #define BZ_X_MTF_2 37 | ||
322 | #define BZ_X_MTF_3 38 | ||
323 | #define BZ_X_MTF_4 39 | ||
324 | #define BZ_X_MTF_5 40 | ||
325 | #define BZ_X_MTF_6 41 | ||
326 | #define BZ_X_ENDHDR_2 42 | ||
327 | #define BZ_X_ENDHDR_3 43 | ||
328 | #define BZ_X_ENDHDR_4 44 | ||
329 | #define BZ_X_ENDHDR_5 45 | ||
330 | #define BZ_X_ENDHDR_6 46 | ||
331 | #define BZ_X_CCRC_1 47 | ||
332 | #define BZ_X_CCRC_2 48 | ||
333 | #define BZ_X_CCRC_3 49 | ||
334 | #define BZ_X_CCRC_4 50 | ||
335 | |||
336 | |||
337 | |||
338 | /*-- Constants for the fast MTF decoder. --*/ | ||
339 | |||
340 | #define MTFA_SIZE 4096 | ||
341 | #define MTFL_SIZE 16 | ||
342 | |||
343 | |||
344 | |||
345 | /*-- Structure holding all the decompression-side stuff. --*/ | ||
346 | |||
347 | typedef | ||
348 | struct { | ||
349 | /* pointer back to the struct bz_stream */ | ||
350 | bz_stream* strm; | ||
351 | |||
352 | /* state indicator for this stream */ | ||
353 | Int32 state; | ||
354 | |||
355 | /* for doing the final run-length decoding */ | ||
356 | UChar state_out_ch; | ||
357 | Int32 state_out_len; | ||
358 | Bool blockRandomised; | ||
359 | BZ_RAND_DECLS; | ||
360 | |||
361 | /* the buffer for bit stream reading */ | ||
362 | UInt32 bsBuff; | ||
363 | Int32 bsLive; | ||
364 | |||
365 | /* misc administratium */ | ||
366 | Int32 blockSize100k; | ||
367 | Bool smallDecompress; | ||
368 | Int32 currBlockNo; | ||
369 | Int32 verbosity; | ||
370 | |||
371 | /* for undoing the Burrows-Wheeler transform */ | ||
372 | Int32 origPtr; | ||
373 | UInt32 tPos; | ||
374 | Int32 k0; | ||
375 | Int32 unzftab[256]; | ||
376 | Int32 nblock_used; | ||
377 | Int32 cftab[257]; | ||
378 | Int32 cftabCopy[257]; | ||
379 | |||
380 | /* for undoing the Burrows-Wheeler transform (FAST) */ | ||
381 | UInt32 *tt; | ||
382 | |||
383 | /* for undoing the Burrows-Wheeler transform (SMALL) */ | ||
384 | UInt16 *ll16; | ||
385 | UChar *ll4; | ||
386 | |||
387 | /* stored and calculated CRCs */ | ||
388 | UInt32 storedBlockCRC; | ||
389 | UInt32 storedCombinedCRC; | ||
390 | UInt32 calculatedBlockCRC; | ||
391 | UInt32 calculatedCombinedCRC; | ||
392 | |||
393 | /* map of bytes used in block */ | ||
394 | Int32 nInUse; | ||
395 | Bool inUse[256]; | ||
396 | Bool inUse16[16]; | ||
397 | UChar seqToUnseq[256]; | ||
398 | |||
399 | /* for decoding the MTF values */ | ||
400 | UChar mtfa [MTFA_SIZE]; | ||
401 | Int32 mtfbase[256 / MTFL_SIZE]; | ||
402 | UChar selector [BZ_MAX_SELECTORS]; | ||
403 | UChar selectorMtf[BZ_MAX_SELECTORS]; | ||
404 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
405 | |||
406 | Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
407 | Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
408 | Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
409 | Int32 minLens[BZ_N_GROUPS]; | ||
410 | |||
411 | /* save area for scalars in the main decompress code */ | ||
412 | Int32 save_i; | ||
413 | Int32 save_j; | ||
414 | Int32 save_t; | ||
415 | Int32 save_alphaSize; | ||
416 | Int32 save_nGroups; | ||
417 | Int32 save_nSelectors; | ||
418 | Int32 save_EOB; | ||
419 | Int32 save_groupNo; | ||
420 | Int32 save_groupPos; | ||
421 | Int32 save_nextSym; | ||
422 | Int32 save_nblockMAX; | ||
423 | Int32 save_nblock; | ||
424 | Int32 save_es; | ||
425 | Int32 save_N; | ||
426 | Int32 save_curr; | ||
427 | Int32 save_zt; | ||
428 | Int32 save_zn; | ||
429 | Int32 save_zvec; | ||
430 | Int32 save_zj; | ||
431 | Int32 save_gSel; | ||
432 | Int32 save_gMinlen; | ||
433 | Int32* save_gLimit; | ||
434 | Int32* save_gBase; | ||
435 | Int32* save_gPerm; | ||
436 | |||
437 | } | ||
438 | DState; | ||
439 | |||
440 | |||
441 | |||
442 | /*-- Macros for decompression. --*/ | ||
443 | |||
444 | #define BZ_GET_FAST(cccc) \ | ||
445 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ | ||
446 | if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \ | ||
447 | s->tPos = s->tt[s->tPos]; \ | ||
448 | cccc = (UChar)(s->tPos & 0xff); \ | ||
449 | s->tPos >>= 8; | ||
450 | |||
451 | #define BZ_GET_FAST_C(cccc) \ | ||
452 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ | ||
453 | if (c_tPos >= (UInt32)100000 * (UInt32)ro_blockSize100k) return True; \ | ||
454 | c_tPos = c_tt[c_tPos]; \ | ||
455 | cccc = (UChar)(c_tPos & 0xff); \ | ||
456 | c_tPos >>= 8; | ||
457 | |||
458 | #define SET_LL4(i,n) \ | ||
459 | { if (((i) & 0x1) == 0) \ | ||
460 | s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \ | ||
461 | s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ | ||
462 | } | ||
463 | |||
464 | #define GET_LL4(i) \ | ||
465 | ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF) | ||
466 | |||
467 | #define SET_LL(i,n) \ | ||
468 | { s->ll16[i] = (UInt16)(n & 0x0000ffff); \ | ||
469 | SET_LL4(i, n >> 16); \ | ||
470 | } | ||
471 | |||
472 | #define GET_LL(i) \ | ||
473 | (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16)) | ||
474 | |||
475 | #define BZ_GET_SMALL(cccc) \ | ||
476 | /* c_tPos is unsigned, hence test < 0 is pointless. */ \ | ||
477 | if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \ | ||
478 | cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \ | ||
479 | s->tPos = GET_LL(s->tPos); | ||
480 | |||
481 | |||
482 | /*-- externs for decompression. --*/ | ||
483 | |||
484 | extern Int32 | ||
485 | BZ2_indexIntoF ( Int32, Int32* ); | ||
486 | |||
487 | extern Int32 | ||
488 | BZ2_decompress ( DState* ); | ||
489 | |||
490 | extern void | ||
491 | BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*, | ||
492 | Int32, Int32, Int32 ); | ||
493 | |||
494 | |||
495 | #endif | ||
496 | |||
497 | |||
498 | /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/ | ||
499 | |||
500 | #ifdef BZ_NO_STDIO | ||
501 | #ifndef NULL | ||
502 | #define NULL 0 | ||
503 | #endif | ||
504 | #endif | ||
505 | |||
506 | #ifndef WIN32 | ||
507 | #define _fdopen fdopen | ||
508 | #endif | ||
509 | |||
510 | /*-------------------------------------------------------------*/ | ||
511 | /*--- end bzlib_private.h ---*/ | ||
512 | /*-------------------------------------------------------------*/ | ||
diff --git a/utils/bzip2/compress.c b/utils/bzip2/compress.c new file mode 100644 index 0000000000..caf7696011 --- /dev/null +++ b/utils/bzip2/compress.c | |||
@@ -0,0 +1,672 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Compression machinery (not incl block sorting) ---*/ | ||
4 | /*--- compress.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 <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 | /* CHANGES | ||
23 | 0.9.0 -- original version. | ||
24 | 0.9.0a/b -- no changes in this file. | ||
25 | 0.9.0c -- changed setting of nGroups in sendMTFValues() | ||
26 | so as to do a bit better on small files | ||
27 | */ | ||
28 | |||
29 | #include "bzlib_private.h" | ||
30 | |||
31 | |||
32 | /*---------------------------------------------------*/ | ||
33 | /*--- Bit stream I/O ---*/ | ||
34 | /*---------------------------------------------------*/ | ||
35 | |||
36 | /*---------------------------------------------------*/ | ||
37 | void BZ2_bsInitWrite ( EState* s ) | ||
38 | { | ||
39 | s->bsLive = 0; | ||
40 | s->bsBuff = 0; | ||
41 | } | ||
42 | |||
43 | |||
44 | /*---------------------------------------------------*/ | ||
45 | static | ||
46 | void bsFinishWrite ( EState* s ) | ||
47 | { | ||
48 | while (s->bsLive > 0) { | ||
49 | s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24); | ||
50 | s->numZ++; | ||
51 | s->bsBuff <<= 8; | ||
52 | s->bsLive -= 8; | ||
53 | } | ||
54 | } | ||
55 | |||
56 | |||
57 | /*---------------------------------------------------*/ | ||
58 | #define bsNEEDW(nz) \ | ||
59 | { \ | ||
60 | while (s->bsLive >= 8) { \ | ||
61 | s->zbits[s->numZ] \ | ||
62 | = (UChar)(s->bsBuff >> 24); \ | ||
63 | s->numZ++; \ | ||
64 | s->bsBuff <<= 8; \ | ||
65 | s->bsLive -= 8; \ | ||
66 | } \ | ||
67 | } | ||
68 | |||
69 | |||
70 | /*---------------------------------------------------*/ | ||
71 | static | ||
72 | __inline__ | ||
73 | void bsW ( EState* s, Int32 n, UInt32 v ) | ||
74 | { | ||
75 | bsNEEDW ( n ); | ||
76 | s->bsBuff |= (v << (32 - s->bsLive - n)); | ||
77 | s->bsLive += n; | ||
78 | } | ||
79 | |||
80 | |||
81 | /*---------------------------------------------------*/ | ||
82 | static | ||
83 | void bsPutUInt32 ( EState* s, UInt32 u ) | ||
84 | { | ||
85 | bsW ( s, 8, (u >> 24) & 0xffL ); | ||
86 | bsW ( s, 8, (u >> 16) & 0xffL ); | ||
87 | bsW ( s, 8, (u >> 8) & 0xffL ); | ||
88 | bsW ( s, 8, u & 0xffL ); | ||
89 | } | ||
90 | |||
91 | |||
92 | /*---------------------------------------------------*/ | ||
93 | static | ||
94 | void bsPutUChar ( EState* s, UChar c ) | ||
95 | { | ||
96 | bsW( s, 8, (UInt32)c ); | ||
97 | } | ||
98 | |||
99 | |||
100 | /*---------------------------------------------------*/ | ||
101 | /*--- The back end proper ---*/ | ||
102 | /*---------------------------------------------------*/ | ||
103 | |||
104 | /*---------------------------------------------------*/ | ||
105 | static | ||
106 | void makeMaps_e ( EState* s ) | ||
107 | { | ||
108 | Int32 i; | ||
109 | s->nInUse = 0; | ||
110 | for (i = 0; i < 256; i++) | ||
111 | if (s->inUse[i]) { | ||
112 | s->unseqToSeq[i] = s->nInUse; | ||
113 | s->nInUse++; | ||
114 | } | ||
115 | } | ||
116 | |||
117 | |||
118 | /*---------------------------------------------------*/ | ||
119 | static | ||
120 | void generateMTFValues ( EState* s ) | ||
121 | { | ||
122 | UChar yy[256]; | ||
123 | Int32 i, j; | ||
124 | Int32 zPend; | ||
125 | Int32 wr; | ||
126 | Int32 EOB; | ||
127 | |||
128 | /* | ||
129 | After sorting (eg, here), | ||
130 | s->arr1 [ 0 .. s->nblock-1 ] holds sorted order, | ||
131 | and | ||
132 | ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] | ||
133 | holds the original block data. | ||
134 | |||
135 | The first thing to do is generate the MTF values, | ||
136 | and put them in | ||
137 | ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ]. | ||
138 | Because there are strictly fewer or equal MTF values | ||
139 | than block values, ptr values in this area are overwritten | ||
140 | with MTF values only when they are no longer needed. | ||
141 | |||
142 | The final compressed bitstream is generated into the | ||
143 | area starting at | ||
144 | (UChar*) (&((UChar*)s->arr2)[s->nblock]) | ||
145 | |||
146 | These storage aliases are set up in bzCompressInit(), | ||
147 | except for the last one, which is arranged in | ||
148 | compressBlock(). | ||
149 | */ | ||
150 | UInt32* ptr = s->ptr; | ||
151 | UChar* block = s->block; | ||
152 | UInt16* mtfv = s->mtfv; | ||
153 | |||
154 | makeMaps_e ( s ); | ||
155 | EOB = s->nInUse+1; | ||
156 | |||
157 | for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0; | ||
158 | |||
159 | wr = 0; | ||
160 | zPend = 0; | ||
161 | for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i; | ||
162 | |||
163 | for (i = 0; i < s->nblock; i++) { | ||
164 | UChar ll_i; | ||
165 | AssertD ( wr <= i, "generateMTFValues(1)" ); | ||
166 | j = ptr[i]-1; if (j < 0) j += s->nblock; | ||
167 | ll_i = s->unseqToSeq[block[j]]; | ||
168 | AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" ); | ||
169 | |||
170 | if (yy[0] == ll_i) { | ||
171 | zPend++; | ||
172 | } else { | ||
173 | |||
174 | if (zPend > 0) { | ||
175 | zPend--; | ||
176 | while (True) { | ||
177 | if (zPend & 1) { | ||
178 | mtfv[wr] = BZ_RUNB; wr++; | ||
179 | s->mtfFreq[BZ_RUNB]++; | ||
180 | } else { | ||
181 | mtfv[wr] = BZ_RUNA; wr++; | ||
182 | s->mtfFreq[BZ_RUNA]++; | ||
183 | } | ||
184 | if (zPend < 2) break; | ||
185 | zPend = (zPend - 2) / 2; | ||
186 | }; | ||
187 | zPend = 0; | ||
188 | } | ||
189 | { | ||
190 | register UChar rtmp; | ||
191 | register UChar* ryy_j; | ||
192 | register UChar rll_i; | ||
193 | rtmp = yy[1]; | ||
194 | yy[1] = yy[0]; | ||
195 | ryy_j = &(yy[1]); | ||
196 | rll_i = ll_i; | ||
197 | while ( rll_i != rtmp ) { | ||
198 | register UChar rtmp2; | ||
199 | ryy_j++; | ||
200 | rtmp2 = rtmp; | ||
201 | rtmp = *ryy_j; | ||
202 | *ryy_j = rtmp2; | ||
203 | }; | ||
204 | yy[0] = rtmp; | ||
205 | j = ryy_j - &(yy[0]); | ||
206 | mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++; | ||
207 | } | ||
208 | |||
209 | } | ||
210 | } | ||
211 | |||
212 | if (zPend > 0) { | ||
213 | zPend--; | ||
214 | while (True) { | ||
215 | if (zPend & 1) { | ||
216 | mtfv[wr] = BZ_RUNB; wr++; | ||
217 | s->mtfFreq[BZ_RUNB]++; | ||
218 | } else { | ||
219 | mtfv[wr] = BZ_RUNA; wr++; | ||
220 | s->mtfFreq[BZ_RUNA]++; | ||
221 | } | ||
222 | if (zPend < 2) break; | ||
223 | zPend = (zPend - 2) / 2; | ||
224 | }; | ||
225 | zPend = 0; | ||
226 | } | ||
227 | |||
228 | mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++; | ||
229 | |||
230 | s->nMTF = wr; | ||
231 | } | ||
232 | |||
233 | |||
234 | /*---------------------------------------------------*/ | ||
235 | #define BZ_LESSER_ICOST 0 | ||
236 | #define BZ_GREATER_ICOST 15 | ||
237 | |||
238 | static | ||
239 | void sendMTFValues ( EState* s ) | ||
240 | { | ||
241 | Int32 v, t, i, j, gs, ge, totc, bt, bc, iter; | ||
242 | Int32 nSelectors, alphaSize, minLen, maxLen, selCtr; | ||
243 | Int32 nGroups, nBytes; | ||
244 | |||
245 | /*-- | ||
246 | UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
247 | is a global since the decoder also needs it. | ||
248 | |||
249 | Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
250 | Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; | ||
251 | are also globals only used in this proc. | ||
252 | Made global to keep stack frame size small. | ||
253 | --*/ | ||
254 | |||
255 | |||
256 | UInt16 cost[BZ_N_GROUPS]; | ||
257 | Int32 fave[BZ_N_GROUPS]; | ||
258 | |||
259 | UInt16* mtfv = s->mtfv; | ||
260 | |||
261 | if (s->verbosity >= 3) | ||
262 | VPrintf3( " %d in block, %d after MTF & 1-2 coding, " | ||
263 | "%d+2 syms in use\n", | ||
264 | s->nblock, s->nMTF, s->nInUse ); | ||
265 | |||
266 | alphaSize = s->nInUse+2; | ||
267 | for (t = 0; t < BZ_N_GROUPS; t++) | ||
268 | for (v = 0; v < alphaSize; v++) | ||
269 | s->len[t][v] = BZ_GREATER_ICOST; | ||
270 | |||
271 | /*--- Decide how many coding tables to use ---*/ | ||
272 | AssertH ( s->nMTF > 0, 3001 ); | ||
273 | if (s->nMTF < 200) nGroups = 2; else | ||
274 | if (s->nMTF < 600) nGroups = 3; else | ||
275 | if (s->nMTF < 1200) nGroups = 4; else | ||
276 | if (s->nMTF < 2400) nGroups = 5; else | ||
277 | nGroups = 6; | ||
278 | |||
279 | /*--- Generate an initial set of coding tables ---*/ | ||
280 | { | ||
281 | Int32 nPart, remF, tFreq, aFreq; | ||
282 | |||
283 | nPart = nGroups; | ||
284 | remF = s->nMTF; | ||
285 | gs = 0; | ||
286 | while (nPart > 0) { | ||
287 | tFreq = remF / nPart; | ||
288 | ge = gs-1; | ||
289 | aFreq = 0; | ||
290 | while (aFreq < tFreq && ge < alphaSize-1) { | ||
291 | ge++; | ||
292 | aFreq += s->mtfFreq[ge]; | ||
293 | } | ||
294 | |||
295 | if (ge > gs | ||
296 | && nPart != nGroups && nPart != 1 | ||
297 | && ((nGroups-nPart) % 2 == 1)) { | ||
298 | aFreq -= s->mtfFreq[ge]; | ||
299 | ge--; | ||
300 | } | ||
301 | |||
302 | if (s->verbosity >= 3) | ||
303 | VPrintf5( " initial group %d, [%d .. %d], " | ||
304 | "has %d syms (%4.1f%%)\n", | ||
305 | nPart, gs, ge, aFreq, | ||
306 | (100.0 * (float)aFreq) / (float)(s->nMTF) ); | ||
307 | |||
308 | for (v = 0; v < alphaSize; v++) | ||
309 | if (v >= gs && v <= ge) | ||
310 | s->len[nPart-1][v] = BZ_LESSER_ICOST; else | ||
311 | s->len[nPart-1][v] = BZ_GREATER_ICOST; | ||
312 | |||
313 | nPart--; | ||
314 | gs = ge+1; | ||
315 | remF -= aFreq; | ||
316 | } | ||
317 | } | ||
318 | |||
319 | /*--- | ||
320 | Iterate up to BZ_N_ITERS times to improve the tables. | ||
321 | ---*/ | ||
322 | for (iter = 0; iter < BZ_N_ITERS; iter++) { | ||
323 | |||
324 | for (t = 0; t < nGroups; t++) fave[t] = 0; | ||
325 | |||
326 | for (t = 0; t < nGroups; t++) | ||
327 | for (v = 0; v < alphaSize; v++) | ||
328 | s->rfreq[t][v] = 0; | ||
329 | |||
330 | /*--- | ||
331 | Set up an auxiliary length table which is used to fast-track | ||
332 | the common case (nGroups == 6). | ||
333 | ---*/ | ||
334 | if (nGroups == 6) { | ||
335 | for (v = 0; v < alphaSize; v++) { | ||
336 | s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v]; | ||
337 | s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v]; | ||
338 | s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v]; | ||
339 | } | ||
340 | } | ||
341 | |||
342 | nSelectors = 0; | ||
343 | totc = 0; | ||
344 | gs = 0; | ||
345 | while (True) { | ||
346 | |||
347 | /*--- Set group start & end marks. --*/ | ||
348 | if (gs >= s->nMTF) break; | ||
349 | ge = gs + BZ_G_SIZE - 1; | ||
350 | if (ge >= s->nMTF) ge = s->nMTF-1; | ||
351 | |||
352 | /*-- | ||
353 | Calculate the cost of this group as coded | ||
354 | by each of the coding tables. | ||
355 | --*/ | ||
356 | for (t = 0; t < nGroups; t++) cost[t] = 0; | ||
357 | |||
358 | if (nGroups == 6 && 50 == ge-gs+1) { | ||
359 | /*--- fast track the common case ---*/ | ||
360 | register UInt32 cost01, cost23, cost45; | ||
361 | register UInt16 icv; | ||
362 | cost01 = cost23 = cost45 = 0; | ||
363 | |||
364 | # define BZ_ITER(nn) \ | ||
365 | icv = mtfv[gs+(nn)]; \ | ||
366 | cost01 += s->len_pack[icv][0]; \ | ||
367 | cost23 += s->len_pack[icv][1]; \ | ||
368 | cost45 += s->len_pack[icv][2]; \ | ||
369 | |||
370 | BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4); | ||
371 | BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9); | ||
372 | BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14); | ||
373 | BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19); | ||
374 | BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24); | ||
375 | BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29); | ||
376 | BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34); | ||
377 | BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39); | ||
378 | BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44); | ||
379 | BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49); | ||
380 | |||
381 | # undef BZ_ITER | ||
382 | |||
383 | cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16; | ||
384 | cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16; | ||
385 | cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16; | ||
386 | |||
387 | } else { | ||
388 | /*--- slow version which correctly handles all situations ---*/ | ||
389 | for (i = gs; i <= ge; i++) { | ||
390 | UInt16 icv = mtfv[i]; | ||
391 | for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv]; | ||
392 | } | ||
393 | } | ||
394 | |||
395 | /*-- | ||
396 | Find the coding table which is best for this group, | ||
397 | and record its identity in the selector table. | ||
398 | --*/ | ||
399 | bc = 999999999; bt = -1; | ||
400 | for (t = 0; t < nGroups; t++) | ||
401 | if (cost[t] < bc) { bc = cost[t]; bt = t; }; | ||
402 | totc += bc; | ||
403 | fave[bt]++; | ||
404 | s->selector[nSelectors] = bt; | ||
405 | nSelectors++; | ||
406 | |||
407 | /*-- | ||
408 | Increment the symbol frequencies for the selected table. | ||
409 | --*/ | ||
410 | if (nGroups == 6 && 50 == ge-gs+1) { | ||
411 | /*--- fast track the common case ---*/ | ||
412 | |||
413 | # define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++ | ||
414 | |||
415 | BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4); | ||
416 | BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9); | ||
417 | BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14); | ||
418 | BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19); | ||
419 | BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24); | ||
420 | BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29); | ||
421 | BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34); | ||
422 | BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39); | ||
423 | BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44); | ||
424 | BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49); | ||
425 | |||
426 | # undef BZ_ITUR | ||
427 | |||
428 | } else { | ||
429 | /*--- slow version which correctly handles all situations ---*/ | ||
430 | for (i = gs; i <= ge; i++) | ||
431 | s->rfreq[bt][ mtfv[i] ]++; | ||
432 | } | ||
433 | |||
434 | gs = ge+1; | ||
435 | } | ||
436 | if (s->verbosity >= 3) { | ||
437 | VPrintf2 ( " pass %d: size is %d, grp uses are ", | ||
438 | iter+1, totc/8 ); | ||
439 | for (t = 0; t < nGroups; t++) | ||
440 | VPrintf1 ( "%d ", fave[t] ); | ||
441 | VPrintf0 ( "\n" ); | ||
442 | } | ||
443 | |||
444 | /*-- | ||
445 | Recompute the tables based on the accumulated frequencies. | ||
446 | --*/ | ||
447 | /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See | ||
448 | comment in huffman.c for details. */ | ||
449 | for (t = 0; t < nGroups; t++) | ||
450 | BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), | ||
451 | alphaSize, 17 /*20*/ ); | ||
452 | } | ||
453 | |||
454 | |||
455 | AssertH( nGroups < 8, 3002 ); | ||
456 | AssertH( nSelectors < 32768 && | ||
457 | nSelectors <= (2 + (900000 / BZ_G_SIZE)), | ||
458 | 3003 ); | ||
459 | |||
460 | |||
461 | /*--- Compute MTF values for the selectors. ---*/ | ||
462 | { | ||
463 | UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp; | ||
464 | for (i = 0; i < nGroups; i++) pos[i] = i; | ||
465 | for (i = 0; i < nSelectors; i++) { | ||
466 | ll_i = s->selector[i]; | ||
467 | j = 0; | ||
468 | tmp = pos[j]; | ||
469 | while ( ll_i != tmp ) { | ||
470 | j++; | ||
471 | tmp2 = tmp; | ||
472 | tmp = pos[j]; | ||
473 | pos[j] = tmp2; | ||
474 | }; | ||
475 | pos[0] = tmp; | ||
476 | s->selectorMtf[i] = j; | ||
477 | } | ||
478 | }; | ||
479 | |||
480 | /*--- Assign actual codes for the tables. --*/ | ||
481 | for (t = 0; t < nGroups; t++) { | ||
482 | minLen = 32; | ||
483 | maxLen = 0; | ||
484 | for (i = 0; i < alphaSize; i++) { | ||
485 | if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; | ||
486 | if (s->len[t][i] < minLen) minLen = s->len[t][i]; | ||
487 | } | ||
488 | AssertH ( !(maxLen > 17 /*20*/ ), 3004 ); | ||
489 | AssertH ( !(minLen < 1), 3005 ); | ||
490 | BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), | ||
491 | minLen, maxLen, alphaSize ); | ||
492 | } | ||
493 | |||
494 | /*--- Transmit the mapping table. ---*/ | ||
495 | { | ||
496 | Bool inUse16[16]; | ||
497 | for (i = 0; i < 16; i++) { | ||
498 | inUse16[i] = False; | ||
499 | for (j = 0; j < 16; j++) | ||
500 | if (s->inUse[i * 16 + j]) inUse16[i] = True; | ||
501 | } | ||
502 | |||
503 | nBytes = s->numZ; | ||
504 | for (i = 0; i < 16; i++) | ||
505 | if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0); | ||
506 | |||
507 | for (i = 0; i < 16; i++) | ||
508 | if (inUse16[i]) | ||
509 | for (j = 0; j < 16; j++) { | ||
510 | if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0); | ||
511 | } | ||
512 | |||
513 | if (s->verbosity >= 3) | ||
514 | VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes ); | ||
515 | } | ||
516 | |||
517 | /*--- Now the selectors. ---*/ | ||
518 | nBytes = s->numZ; | ||
519 | bsW ( s, 3, nGroups ); | ||
520 | bsW ( s, 15, nSelectors ); | ||
521 | for (i = 0; i < nSelectors; i++) { | ||
522 | for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1); | ||
523 | bsW(s,1,0); | ||
524 | } | ||
525 | if (s->verbosity >= 3) | ||
526 | VPrintf1( "selectors %d, ", s->numZ-nBytes ); | ||
527 | |||
528 | /*--- Now the coding tables. ---*/ | ||
529 | nBytes = s->numZ; | ||
530 | |||
531 | for (t = 0; t < nGroups; t++) { | ||
532 | Int32 curr = s->len[t][0]; | ||
533 | bsW ( s, 5, curr ); | ||
534 | for (i = 0; i < alphaSize; i++) { | ||
535 | while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ }; | ||
536 | while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ }; | ||
537 | bsW ( s, 1, 0 ); | ||
538 | } | ||
539 | } | ||
540 | |||
541 | if (s->verbosity >= 3) | ||
542 | VPrintf1 ( "code lengths %d, ", s->numZ-nBytes ); | ||
543 | |||
544 | /*--- And finally, the block data proper ---*/ | ||
545 | nBytes = s->numZ; | ||
546 | selCtr = 0; | ||
547 | gs = 0; | ||
548 | while (True) { | ||
549 | if (gs >= s->nMTF) break; | ||
550 | ge = gs + BZ_G_SIZE - 1; | ||
551 | if (ge >= s->nMTF) ge = s->nMTF-1; | ||
552 | AssertH ( s->selector[selCtr] < nGroups, 3006 ); | ||
553 | |||
554 | if (nGroups == 6 && 50 == ge-gs+1) { | ||
555 | /*--- fast track the common case ---*/ | ||
556 | UInt16 mtfv_i; | ||
557 | UChar* s_len_sel_selCtr | ||
558 | = &(s->len[s->selector[selCtr]][0]); | ||
559 | Int32* s_code_sel_selCtr | ||
560 | = &(s->code[s->selector[selCtr]][0]); | ||
561 | |||
562 | # define BZ_ITAH(nn) \ | ||
563 | mtfv_i = mtfv[gs+(nn)]; \ | ||
564 | bsW ( s, \ | ||
565 | s_len_sel_selCtr[mtfv_i], \ | ||
566 | s_code_sel_selCtr[mtfv_i] ) | ||
567 | |||
568 | BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4); | ||
569 | BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9); | ||
570 | BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14); | ||
571 | BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19); | ||
572 | BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24); | ||
573 | BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29); | ||
574 | BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34); | ||
575 | BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39); | ||
576 | BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44); | ||
577 | BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49); | ||
578 | |||
579 | # undef BZ_ITAH | ||
580 | |||
581 | } else { | ||
582 | /*--- slow version which correctly handles all situations ---*/ | ||
583 | for (i = gs; i <= ge; i++) { | ||
584 | bsW ( s, | ||
585 | s->len [s->selector[selCtr]] [mtfv[i]], | ||
586 | s->code [s->selector[selCtr]] [mtfv[i]] ); | ||
587 | } | ||
588 | } | ||
589 | |||
590 | |||
591 | gs = ge+1; | ||
592 | selCtr++; | ||
593 | } | ||
594 | AssertH( selCtr == nSelectors, 3007 ); | ||
595 | |||
596 | if (s->verbosity >= 3) | ||
597 | VPrintf1( "codes %d\n", s->numZ-nBytes ); | ||
598 | } | ||
599 | |||
600 | |||
601 | /*---------------------------------------------------*/ | ||
602 | void BZ2_compressBlock ( EState* s, Bool is_last_block ) | ||
603 | { | ||
604 | if (s->nblock > 0) { | ||
605 | |||
606 | BZ_FINALISE_CRC ( s->blockCRC ); | ||
607 | s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); | ||
608 | s->combinedCRC ^= s->blockCRC; | ||
609 | if (s->blockNo > 1) s->numZ = 0; | ||
610 | |||
611 | if (s->verbosity >= 2) | ||
612 | VPrintf4( " block %d: crc = 0x%08x, " | ||
613 | "combined CRC = 0x%08x, size = %d\n", | ||
614 | s->blockNo, s->blockCRC, s->combinedCRC, s->nblock ); | ||
615 | |||
616 | BZ2_blockSort ( s ); | ||
617 | } | ||
618 | |||
619 | s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]); | ||
620 | |||
621 | /*-- If this is the first block, create the stream header. --*/ | ||
622 | if (s->blockNo == 1) { | ||
623 | BZ2_bsInitWrite ( s ); | ||
624 | bsPutUChar ( s, BZ_HDR_B ); | ||
625 | bsPutUChar ( s, BZ_HDR_Z ); | ||
626 | bsPutUChar ( s, BZ_HDR_h ); | ||
627 | bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) ); | ||
628 | } | ||
629 | |||
630 | if (s->nblock > 0) { | ||
631 | |||
632 | bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 ); | ||
633 | bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 ); | ||
634 | bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 ); | ||
635 | |||
636 | /*-- Now the block's CRC, so it is in a known place. --*/ | ||
637 | bsPutUInt32 ( s, s->blockCRC ); | ||
638 | |||
639 | /*-- | ||
640 | Now a single bit indicating (non-)randomisation. | ||
641 | As of version 0.9.5, we use a better sorting algorithm | ||
642 | which makes randomisation unnecessary. So always set | ||
643 | the randomised bit to 'no'. Of course, the decoder | ||
644 | still needs to be able to handle randomised blocks | ||
645 | so as to maintain backwards compatibility with | ||
646 | older versions of bzip2. | ||
647 | --*/ | ||
648 | bsW(s,1,0); | ||
649 | |||
650 | bsW ( s, 24, s->origPtr ); | ||
651 | generateMTFValues ( s ); | ||
652 | sendMTFValues ( s ); | ||
653 | } | ||
654 | |||
655 | |||
656 | /*-- If this is the last block, add the stream trailer. --*/ | ||
657 | if (is_last_block) { | ||
658 | |||
659 | bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 ); | ||
660 | bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 ); | ||
661 | bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 ); | ||
662 | bsPutUInt32 ( s, s->combinedCRC ); | ||
663 | if (s->verbosity >= 2) | ||
664 | VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC ); | ||
665 | bsFinishWrite ( s ); | ||
666 | } | ||
667 | } | ||
668 | |||
669 | |||
670 | /*-------------------------------------------------------------*/ | ||
671 | /*--- end compress.c ---*/ | ||
672 | /*-------------------------------------------------------------*/ | ||
diff --git a/utils/bzip2/crctable.c b/utils/bzip2/crctable.c new file mode 100644 index 0000000000..1fea7e946c --- /dev/null +++ b/utils/bzip2/crctable.c | |||
@@ -0,0 +1,104 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Table for doing CRCs ---*/ | ||
4 | /*--- crctable.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 <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 | I think this is an implementation of the AUTODIN-II, | ||
26 | Ethernet & FDDI 32-bit CRC standard. Vaguely derived | ||
27 | from code by Rob Warnock, in Section 51 of the | ||
28 | comp.compression FAQ. | ||
29 | --*/ | ||
30 | |||
31 | UInt32 BZ2_crc32Table[256] = { | ||
32 | |||
33 | /*-- Ugly, innit? --*/ | ||
34 | |||
35 | 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L, | ||
36 | 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L, | ||
37 | 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L, | ||
38 | 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL, | ||
39 | 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L, | ||
40 | 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L, | ||
41 | 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L, | ||
42 | 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL, | ||
43 | 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L, | ||
44 | 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L, | ||
45 | 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L, | ||
46 | 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL, | ||
47 | 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L, | ||
48 | 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L, | ||
49 | 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L, | ||
50 | 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL, | ||
51 | 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL, | ||
52 | 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L, | ||
53 | 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L, | ||
54 | 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL, | ||
55 | 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL, | ||
56 | 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L, | ||
57 | 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L, | ||
58 | 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL, | ||
59 | 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL, | ||
60 | 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L, | ||
61 | 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L, | ||
62 | 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL, | ||
63 | 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL, | ||
64 | 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L, | ||
65 | 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L, | ||
66 | 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL, | ||
67 | 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L, | ||
68 | 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL, | ||
69 | 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL, | ||
70 | 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L, | ||
71 | 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L, | ||
72 | 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL, | ||
73 | 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL, | ||
74 | 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L, | ||
75 | 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L, | ||
76 | 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL, | ||
77 | 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL, | ||
78 | 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L, | ||
79 | 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L, | ||
80 | 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL, | ||
81 | 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL, | ||
82 | 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L, | ||
83 | 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L, | ||
84 | 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL, | ||
85 | 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L, | ||
86 | 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L, | ||
87 | 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L, | ||
88 | 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL, | ||
89 | 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L, | ||
90 | 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L, | ||
91 | 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L, | ||
92 | 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL, | ||
93 | 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L, | ||
94 | 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L, | ||
95 | 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L, | ||
96 | 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL, | ||
97 | 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L, | ||
98 | 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L | ||
99 | }; | ||
100 | |||
101 | |||
102 | /*-------------------------------------------------------------*/ | ||
103 | /*--- end crctable.c ---*/ | ||
104 | /*-------------------------------------------------------------*/ | ||
diff --git a/utils/bzip2/decompress.c b/utils/bzip2/decompress.c new file mode 100644 index 0000000000..311f5668f9 --- /dev/null +++ b/utils/bzip2/decompress.c | |||
@@ -0,0 +1,646 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Decompression machinery ---*/ | ||
4 | /*--- decompress.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 <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 | /*---------------------------------------------------*/ | ||
26 | static | ||
27 | void makeMaps_d ( DState* s ) | ||
28 | { | ||
29 | Int32 i; | ||
30 | s->nInUse = 0; | ||
31 | for (i = 0; i < 256; i++) | ||
32 | if (s->inUse[i]) { | ||
33 | s->seqToUnseq[s->nInUse] = i; | ||
34 | s->nInUse++; | ||
35 | } | ||
36 | } | ||
37 | |||
38 | |||
39 | /*---------------------------------------------------*/ | ||
40 | #define RETURN(rrr) \ | ||
41 | { retVal = rrr; goto save_state_and_return; }; | ||
42 | |||
43 | #define GET_BITS(lll,vvv,nnn) \ | ||
44 | case lll: s->state = lll; \ | ||
45 | while (True) { \ | ||
46 | if (s->bsLive >= nnn) { \ | ||
47 | UInt32 v; \ | ||
48 | v = (s->bsBuff >> \ | ||
49 | (s->bsLive-nnn)) & ((1 << nnn)-1); \ | ||
50 | s->bsLive -= nnn; \ | ||
51 | vvv = v; \ | ||
52 | break; \ | ||
53 | } \ | ||
54 | if (s->strm->avail_in == 0) RETURN(BZ_OK); \ | ||
55 | s->bsBuff \ | ||
56 | = (s->bsBuff << 8) | \ | ||
57 | ((UInt32) \ | ||
58 | (*((UChar*)(s->strm->next_in)))); \ | ||
59 | s->bsLive += 8; \ | ||
60 | s->strm->next_in++; \ | ||
61 | s->strm->avail_in--; \ | ||
62 | s->strm->total_in_lo32++; \ | ||
63 | if (s->strm->total_in_lo32 == 0) \ | ||
64 | s->strm->total_in_hi32++; \ | ||
65 | } | ||
66 | |||
67 | #define GET_UCHAR(lll,uuu) \ | ||
68 | GET_BITS(lll,uuu,8) | ||
69 | |||
70 | #define GET_BIT(lll,uuu) \ | ||
71 | GET_BITS(lll,uuu,1) | ||
72 | |||
73 | /*---------------------------------------------------*/ | ||
74 | #define GET_MTF_VAL(label1,label2,lval) \ | ||
75 | { \ | ||
76 | if (groupPos == 0) { \ | ||
77 | groupNo++; \ | ||
78 | if (groupNo >= nSelectors) \ | ||
79 | RETURN(BZ_DATA_ERROR); \ | ||
80 | groupPos = BZ_G_SIZE; \ | ||
81 | gSel = s->selector[groupNo]; \ | ||
82 | gMinlen = s->minLens[gSel]; \ | ||
83 | gLimit = &(s->limit[gSel][0]); \ | ||
84 | gPerm = &(s->perm[gSel][0]); \ | ||
85 | gBase = &(s->base[gSel][0]); \ | ||
86 | } \ | ||
87 | groupPos--; \ | ||
88 | zn = gMinlen; \ | ||
89 | GET_BITS(label1, zvec, zn); \ | ||
90 | while (1) { \ | ||
91 | if (zn > 20 /* the longest code */) \ | ||
92 | RETURN(BZ_DATA_ERROR); \ | ||
93 | if (zvec <= gLimit[zn]) break; \ | ||
94 | zn++; \ | ||
95 | GET_BIT(label2, zj); \ | ||
96 | zvec = (zvec << 1) | zj; \ | ||
97 | }; \ | ||
98 | if (zvec - gBase[zn] < 0 \ | ||
99 | || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ | ||
100 | RETURN(BZ_DATA_ERROR); \ | ||
101 | lval = gPerm[zvec - gBase[zn]]; \ | ||
102 | } | ||
103 | |||
104 | |||
105 | /*---------------------------------------------------*/ | ||
106 | Int32 BZ2_decompress ( DState* s ) | ||
107 | { | ||
108 | UChar uc; | ||
109 | Int32 retVal; | ||
110 | Int32 minLen, maxLen; | ||
111 | bz_stream* strm = s->strm; | ||
112 | |||
113 | /* stuff that needs to be saved/restored */ | ||
114 | Int32 i; | ||
115 | Int32 j; | ||
116 | Int32 t; | ||
117 | Int32 alphaSize; | ||
118 | Int32 nGroups; | ||
119 | Int32 nSelectors; | ||
120 | Int32 EOB; | ||
121 | Int32 groupNo; | ||
122 | Int32 groupPos; | ||
123 | Int32 nextSym; | ||
124 | Int32 nblockMAX; | ||
125 | Int32 nblock; | ||
126 | Int32 es; | ||
127 | Int32 N; | ||
128 | Int32 curr; | ||
129 | Int32 zt; | ||
130 | Int32 zn; | ||
131 | Int32 zvec; | ||
132 | Int32 zj; | ||
133 | Int32 gSel; | ||
134 | Int32 gMinlen; | ||
135 | Int32* gLimit; | ||
136 | Int32* gBase; | ||
137 | Int32* gPerm; | ||
138 | |||
139 | if (s->state == BZ_X_MAGIC_1) { | ||
140 | /*initialise the save area*/ | ||
141 | s->save_i = 0; | ||
142 | s->save_j = 0; | ||
143 | s->save_t = 0; | ||
144 | s->save_alphaSize = 0; | ||
145 | s->save_nGroups = 0; | ||
146 | s->save_nSelectors = 0; | ||
147 | s->save_EOB = 0; | ||
148 | s->save_groupNo = 0; | ||
149 | s->save_groupPos = 0; | ||
150 | s->save_nextSym = 0; | ||
151 | s->save_nblockMAX = 0; | ||
152 | s->save_nblock = 0; | ||
153 | s->save_es = 0; | ||
154 | s->save_N = 0; | ||
155 | s->save_curr = 0; | ||
156 | s->save_zt = 0; | ||
157 | s->save_zn = 0; | ||
158 | s->save_zvec = 0; | ||
159 | s->save_zj = 0; | ||
160 | s->save_gSel = 0; | ||
161 | s->save_gMinlen = 0; | ||
162 | s->save_gLimit = NULL; | ||
163 | s->save_gBase = NULL; | ||
164 | s->save_gPerm = NULL; | ||
165 | } | ||
166 | |||
167 | /*restore from the save area*/ | ||
168 | i = s->save_i; | ||
169 | j = s->save_j; | ||
170 | t = s->save_t; | ||
171 | alphaSize = s->save_alphaSize; | ||
172 | nGroups = s->save_nGroups; | ||
173 | nSelectors = s->save_nSelectors; | ||
174 | EOB = s->save_EOB; | ||
175 | groupNo = s->save_groupNo; | ||
176 | groupPos = s->save_groupPos; | ||
177 | nextSym = s->save_nextSym; | ||
178 | nblockMAX = s->save_nblockMAX; | ||
179 | nblock = s->save_nblock; | ||
180 | es = s->save_es; | ||
181 | N = s->save_N; | ||
182 | curr = s->save_curr; | ||
183 | zt = s->save_zt; | ||
184 | zn = s->save_zn; | ||
185 | zvec = s->save_zvec; | ||
186 | zj = s->save_zj; | ||
187 | gSel = s->save_gSel; | ||
188 | gMinlen = s->save_gMinlen; | ||
189 | gLimit = s->save_gLimit; | ||
190 | gBase = s->save_gBase; | ||
191 | gPerm = s->save_gPerm; | ||
192 | |||
193 | retVal = BZ_OK; | ||
194 | |||
195 | switch (s->state) { | ||
196 | |||
197 | GET_UCHAR(BZ_X_MAGIC_1, uc); | ||
198 | if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC); | ||
199 | |||
200 | GET_UCHAR(BZ_X_MAGIC_2, uc); | ||
201 | if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC); | ||
202 | |||
203 | GET_UCHAR(BZ_X_MAGIC_3, uc) | ||
204 | if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC); | ||
205 | |||
206 | GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) | ||
207 | if (s->blockSize100k < (BZ_HDR_0 + 1) || | ||
208 | s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC); | ||
209 | s->blockSize100k -= BZ_HDR_0; | ||
210 | |||
211 | if (s->smallDecompress) { | ||
212 | s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); | ||
213 | s->ll4 = BZALLOC( | ||
214 | ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) | ||
215 | ); | ||
216 | if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); | ||
217 | } else { | ||
218 | s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); | ||
219 | if (s->tt == NULL) RETURN(BZ_MEM_ERROR); | ||
220 | } | ||
221 | |||
222 | GET_UCHAR(BZ_X_BLKHDR_1, uc); | ||
223 | |||
224 | if (uc == 0x17) goto endhdr_2; | ||
225 | if (uc != 0x31) RETURN(BZ_DATA_ERROR); | ||
226 | GET_UCHAR(BZ_X_BLKHDR_2, uc); | ||
227 | if (uc != 0x41) RETURN(BZ_DATA_ERROR); | ||
228 | GET_UCHAR(BZ_X_BLKHDR_3, uc); | ||
229 | if (uc != 0x59) RETURN(BZ_DATA_ERROR); | ||
230 | GET_UCHAR(BZ_X_BLKHDR_4, uc); | ||
231 | if (uc != 0x26) RETURN(BZ_DATA_ERROR); | ||
232 | GET_UCHAR(BZ_X_BLKHDR_5, uc); | ||
233 | if (uc != 0x53) RETURN(BZ_DATA_ERROR); | ||
234 | GET_UCHAR(BZ_X_BLKHDR_6, uc); | ||
235 | if (uc != 0x59) RETURN(BZ_DATA_ERROR); | ||
236 | |||
237 | s->currBlockNo++; | ||
238 | if (s->verbosity >= 2) | ||
239 | VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); | ||
240 | |||
241 | s->storedBlockCRC = 0; | ||
242 | GET_UCHAR(BZ_X_BCRC_1, uc); | ||
243 | s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); | ||
244 | GET_UCHAR(BZ_X_BCRC_2, uc); | ||
245 | s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); | ||
246 | GET_UCHAR(BZ_X_BCRC_3, uc); | ||
247 | s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); | ||
248 | GET_UCHAR(BZ_X_BCRC_4, uc); | ||
249 | s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); | ||
250 | |||
251 | GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); | ||
252 | |||
253 | s->origPtr = 0; | ||
254 | GET_UCHAR(BZ_X_ORIGPTR_1, uc); | ||
255 | s->origPtr = (s->origPtr << 8) | ((Int32)uc); | ||
256 | GET_UCHAR(BZ_X_ORIGPTR_2, uc); | ||
257 | s->origPtr = (s->origPtr << 8) | ((Int32)uc); | ||
258 | GET_UCHAR(BZ_X_ORIGPTR_3, uc); | ||
259 | s->origPtr = (s->origPtr << 8) | ((Int32)uc); | ||
260 | |||
261 | if (s->origPtr < 0) | ||
262 | RETURN(BZ_DATA_ERROR); | ||
263 | if (s->origPtr > 10 + 100000*s->blockSize100k) | ||
264 | RETURN(BZ_DATA_ERROR); | ||
265 | |||
266 | /*--- Receive the mapping table ---*/ | ||
267 | for (i = 0; i < 16; i++) { | ||
268 | GET_BIT(BZ_X_MAPPING_1, uc); | ||
269 | if (uc == 1) | ||
270 | s->inUse16[i] = True; else | ||
271 | s->inUse16[i] = False; | ||
272 | } | ||
273 | |||
274 | for (i = 0; i < 256; i++) s->inUse[i] = False; | ||
275 | |||
276 | for (i = 0; i < 16; i++) | ||
277 | if (s->inUse16[i]) | ||
278 | for (j = 0; j < 16; j++) { | ||
279 | GET_BIT(BZ_X_MAPPING_2, uc); | ||
280 | if (uc == 1) s->inUse[i * 16 + j] = True; | ||
281 | } | ||
282 | makeMaps_d ( s ); | ||
283 | if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); | ||
284 | alphaSize = s->nInUse+2; | ||
285 | |||
286 | /*--- Now the selectors ---*/ | ||
287 | GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); | ||
288 | if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); | ||
289 | GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); | ||
290 | if (nSelectors < 1) RETURN(BZ_DATA_ERROR); | ||
291 | for (i = 0; i < nSelectors; i++) { | ||
292 | j = 0; | ||
293 | while (True) { | ||
294 | GET_BIT(BZ_X_SELECTOR_3, uc); | ||
295 | if (uc == 0) break; | ||
296 | j++; | ||
297 | if (j >= nGroups) RETURN(BZ_DATA_ERROR); | ||
298 | } | ||
299 | s->selectorMtf[i] = j; | ||
300 | } | ||
301 | |||
302 | /*--- Undo the MTF values for the selectors. ---*/ | ||
303 | { | ||
304 | UChar pos[BZ_N_GROUPS], tmp, v; | ||
305 | for (v = 0; v < nGroups; v++) pos[v] = v; | ||
306 | |||
307 | for (i = 0; i < nSelectors; i++) { | ||
308 | v = s->selectorMtf[i]; | ||
309 | tmp = pos[v]; | ||
310 | while (v > 0) { pos[v] = pos[v-1]; v--; } | ||
311 | pos[0] = tmp; | ||
312 | s->selector[i] = tmp; | ||
313 | } | ||
314 | } | ||
315 | |||
316 | /*--- Now the coding tables ---*/ | ||
317 | for (t = 0; t < nGroups; t++) { | ||
318 | GET_BITS(BZ_X_CODING_1, curr, 5); | ||
319 | for (i = 0; i < alphaSize; i++) { | ||
320 | while (True) { | ||
321 | if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); | ||
322 | GET_BIT(BZ_X_CODING_2, uc); | ||
323 | if (uc == 0) break; | ||
324 | GET_BIT(BZ_X_CODING_3, uc); | ||
325 | if (uc == 0) curr++; else curr--; | ||
326 | } | ||
327 | s->len[t][i] = curr; | ||
328 | } | ||
329 | } | ||
330 | |||
331 | /*--- Create the Huffman decoding tables ---*/ | ||
332 | for (t = 0; t < nGroups; t++) { | ||
333 | minLen = 32; | ||
334 | maxLen = 0; | ||
335 | for (i = 0; i < alphaSize; i++) { | ||
336 | if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; | ||
337 | if (s->len[t][i] < minLen) minLen = s->len[t][i]; | ||
338 | } | ||
339 | BZ2_hbCreateDecodeTables ( | ||
340 | &(s->limit[t][0]), | ||
341 | &(s->base[t][0]), | ||
342 | &(s->perm[t][0]), | ||
343 | &(s->len[t][0]), | ||
344 | minLen, maxLen, alphaSize | ||
345 | ); | ||
346 | s->minLens[t] = minLen; | ||
347 | } | ||
348 | |||
349 | /*--- Now the MTF values ---*/ | ||
350 | |||
351 | EOB = s->nInUse+1; | ||
352 | nblockMAX = 100000 * s->blockSize100k; | ||
353 | groupNo = -1; | ||
354 | groupPos = 0; | ||
355 | |||
356 | for (i = 0; i <= 255; i++) s->unzftab[i] = 0; | ||
357 | |||
358 | /*-- MTF init --*/ | ||
359 | { | ||
360 | Int32 ii, jj, kk; | ||
361 | kk = MTFA_SIZE-1; | ||
362 | for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { | ||
363 | for (jj = MTFL_SIZE-1; jj >= 0; jj--) { | ||
364 | s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); | ||
365 | kk--; | ||
366 | } | ||
367 | s->mtfbase[ii] = kk + 1; | ||
368 | } | ||
369 | } | ||
370 | /*-- end MTF init --*/ | ||
371 | |||
372 | nblock = 0; | ||
373 | GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); | ||
374 | |||
375 | while (True) { | ||
376 | |||
377 | if (nextSym == EOB) break; | ||
378 | |||
379 | if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { | ||
380 | |||
381 | es = -1; | ||
382 | N = 1; | ||
383 | do { | ||
384 | /* Check that N doesn't get too big, so that es doesn't | ||
385 | go negative. The maximum value that can be | ||
386 | RUNA/RUNB encoded is equal to the block size (post | ||
387 | the initial RLE), viz, 900k, so bounding N at 2 | ||
388 | million should guard against overflow without | ||
389 | rejecting any legitimate inputs. */ | ||
390 | if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR); | ||
391 | if (nextSym == BZ_RUNA) es = es + (0+1) * N; else | ||
392 | if (nextSym == BZ_RUNB) es = es + (1+1) * N; | ||
393 | N = N * 2; | ||
394 | GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); | ||
395 | } | ||
396 | while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); | ||
397 | |||
398 | es++; | ||
399 | uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; | ||
400 | s->unzftab[uc] += es; | ||
401 | |||
402 | if (s->smallDecompress) | ||
403 | while (es > 0) { | ||
404 | if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); | ||
405 | s->ll16[nblock] = (UInt16)uc; | ||
406 | nblock++; | ||
407 | es--; | ||
408 | } | ||
409 | else | ||
410 | while (es > 0) { | ||
411 | if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); | ||
412 | s->tt[nblock] = (UInt32)uc; | ||
413 | nblock++; | ||
414 | es--; | ||
415 | }; | ||
416 | |||
417 | continue; | ||
418 | |||
419 | } else { | ||
420 | |||
421 | if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); | ||
422 | |||
423 | /*-- uc = MTF ( nextSym-1 ) --*/ | ||
424 | { | ||
425 | Int32 ii, jj, kk, pp, lno, off; | ||
426 | UInt32 nn; | ||
427 | nn = (UInt32)(nextSym - 1); | ||
428 | |||
429 | if (nn < MTFL_SIZE) { | ||
430 | /* avoid general-case expense */ | ||
431 | pp = s->mtfbase[0]; | ||
432 | uc = s->mtfa[pp+nn]; | ||
433 | while (nn > 3) { | ||
434 | Int32 z = pp+nn; | ||
435 | s->mtfa[(z) ] = s->mtfa[(z)-1]; | ||
436 | s->mtfa[(z)-1] = s->mtfa[(z)-2]; | ||
437 | s->mtfa[(z)-2] = s->mtfa[(z)-3]; | ||
438 | s->mtfa[(z)-3] = s->mtfa[(z)-4]; | ||
439 | nn -= 4; | ||
440 | } | ||
441 | while (nn > 0) { | ||
442 | s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; | ||
443 | }; | ||
444 | s->mtfa[pp] = uc; | ||
445 | } else { | ||
446 | /* general case */ | ||
447 | lno = nn / MTFL_SIZE; | ||
448 | off = nn % MTFL_SIZE; | ||
449 | pp = s->mtfbase[lno] + off; | ||
450 | uc = s->mtfa[pp]; | ||
451 | while (pp > s->mtfbase[lno]) { | ||
452 | s->mtfa[pp] = s->mtfa[pp-1]; pp--; | ||
453 | }; | ||
454 | s->mtfbase[lno]++; | ||
455 | while (lno > 0) { | ||
456 | s->mtfbase[lno]--; | ||
457 | s->mtfa[s->mtfbase[lno]] | ||
458 | = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; | ||
459 | lno--; | ||
460 | } | ||
461 | s->mtfbase[0]--; | ||
462 | s->mtfa[s->mtfbase[0]] = uc; | ||
463 | if (s->mtfbase[0] == 0) { | ||
464 | kk = MTFA_SIZE-1; | ||
465 | for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { | ||
466 | for (jj = MTFL_SIZE-1; jj >= 0; jj--) { | ||
467 | s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; | ||
468 | kk--; | ||
469 | } | ||
470 | s->mtfbase[ii] = kk + 1; | ||
471 | } | ||
472 | } | ||
473 | } | ||
474 | } | ||
475 | /*-- end uc = MTF ( nextSym-1 ) --*/ | ||
476 | |||
477 | s->unzftab[s->seqToUnseq[uc]]++; | ||
478 | if (s->smallDecompress) | ||
479 | s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else | ||
480 | s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); | ||
481 | nblock++; | ||
482 | |||
483 | GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); | ||
484 | continue; | ||
485 | } | ||
486 | } | ||
487 | |||
488 | /* Now we know what nblock is, we can do a better sanity | ||
489 | check on s->origPtr. | ||
490 | */ | ||
491 | if (s->origPtr < 0 || s->origPtr >= nblock) | ||
492 | RETURN(BZ_DATA_ERROR); | ||
493 | |||
494 | /*-- Set up cftab to facilitate generation of T^(-1) --*/ | ||
495 | /* Check: unzftab entries in range. */ | ||
496 | for (i = 0; i <= 255; i++) { | ||
497 | if (s->unzftab[i] < 0 || s->unzftab[i] > nblock) | ||
498 | RETURN(BZ_DATA_ERROR); | ||
499 | } | ||
500 | /* Actually generate cftab. */ | ||
501 | s->cftab[0] = 0; | ||
502 | for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; | ||
503 | for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; | ||
504 | /* Check: cftab entries in range. */ | ||
505 | for (i = 0; i <= 256; i++) { | ||
506 | if (s->cftab[i] < 0 || s->cftab[i] > nblock) { | ||
507 | /* s->cftab[i] can legitimately be == nblock */ | ||
508 | RETURN(BZ_DATA_ERROR); | ||
509 | } | ||
510 | } | ||
511 | /* Check: cftab entries non-descending. */ | ||
512 | for (i = 1; i <= 256; i++) { | ||
513 | if (s->cftab[i-1] > s->cftab[i]) { | ||
514 | RETURN(BZ_DATA_ERROR); | ||
515 | } | ||
516 | } | ||
517 | |||
518 | s->state_out_len = 0; | ||
519 | s->state_out_ch = 0; | ||
520 | BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); | ||
521 | s->state = BZ_X_OUTPUT; | ||
522 | if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); | ||
523 | |||
524 | if (s->smallDecompress) { | ||
525 | |||
526 | /*-- Make a copy of cftab, used in generation of T --*/ | ||
527 | for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; | ||
528 | |||
529 | /*-- compute the T vector --*/ | ||
530 | for (i = 0; i < nblock; i++) { | ||
531 | uc = (UChar)(s->ll16[i]); | ||
532 | SET_LL(i, s->cftabCopy[uc]); | ||
533 | s->cftabCopy[uc]++; | ||
534 | } | ||
535 | |||
536 | /*-- Compute T^(-1) by pointer reversal on T --*/ | ||
537 | i = s->origPtr; | ||
538 | j = GET_LL(i); | ||
539 | do { | ||
540 | Int32 tmp = GET_LL(j); | ||
541 | SET_LL(j, i); | ||
542 | i = j; | ||
543 | j = tmp; | ||
544 | } | ||
545 | while (i != s->origPtr); | ||
546 | |||
547 | s->tPos = s->origPtr; | ||
548 | s->nblock_used = 0; | ||
549 | if (s->blockRandomised) { | ||
550 | BZ_RAND_INIT_MASK; | ||
551 | BZ_GET_SMALL(s->k0); s->nblock_used++; | ||
552 | BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; | ||
553 | } else { | ||
554 | BZ_GET_SMALL(s->k0); s->nblock_used++; | ||
555 | } | ||
556 | |||
557 | } else { | ||
558 | |||
559 | /*-- compute the T^(-1) vector --*/ | ||
560 | for (i = 0; i < nblock; i++) { | ||
561 | uc = (UChar)(s->tt[i] & 0xff); | ||
562 | s->tt[s->cftab[uc]] |= (i << 8); | ||
563 | s->cftab[uc]++; | ||
564 | } | ||
565 | |||
566 | s->tPos = s->tt[s->origPtr] >> 8; | ||
567 | s->nblock_used = 0; | ||
568 | if (s->blockRandomised) { | ||
569 | BZ_RAND_INIT_MASK; | ||
570 | BZ_GET_FAST(s->k0); s->nblock_used++; | ||
571 | BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; | ||
572 | } else { | ||
573 | BZ_GET_FAST(s->k0); s->nblock_used++; | ||
574 | } | ||
575 | |||
576 | } | ||
577 | |||
578 | RETURN(BZ_OK); | ||
579 | |||
580 | |||
581 | |||
582 | endhdr_2: | ||
583 | |||
584 | GET_UCHAR(BZ_X_ENDHDR_2, uc); | ||
585 | if (uc != 0x72) RETURN(BZ_DATA_ERROR); | ||
586 | GET_UCHAR(BZ_X_ENDHDR_3, uc); | ||
587 | if (uc != 0x45) RETURN(BZ_DATA_ERROR); | ||
588 | GET_UCHAR(BZ_X_ENDHDR_4, uc); | ||
589 | if (uc != 0x38) RETURN(BZ_DATA_ERROR); | ||
590 | GET_UCHAR(BZ_X_ENDHDR_5, uc); | ||
591 | if (uc != 0x50) RETURN(BZ_DATA_ERROR); | ||
592 | GET_UCHAR(BZ_X_ENDHDR_6, uc); | ||
593 | if (uc != 0x90) RETURN(BZ_DATA_ERROR); | ||
594 | |||
595 | s->storedCombinedCRC = 0; | ||
596 | GET_UCHAR(BZ_X_CCRC_1, uc); | ||
597 | s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); | ||
598 | GET_UCHAR(BZ_X_CCRC_2, uc); | ||
599 | s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); | ||
600 | GET_UCHAR(BZ_X_CCRC_3, uc); | ||
601 | s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); | ||
602 | GET_UCHAR(BZ_X_CCRC_4, uc); | ||
603 | s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); | ||
604 | |||
605 | s->state = BZ_X_IDLE; | ||
606 | RETURN(BZ_STREAM_END); | ||
607 | |||
608 | default: AssertH ( False, 4001 ); | ||
609 | } | ||
610 | |||
611 | AssertH ( False, 4002 ); | ||
612 | |||
613 | save_state_and_return: | ||
614 | |||
615 | s->save_i = i; | ||
616 | s->save_j = j; | ||
617 | s->save_t = t; | ||
618 | s->save_alphaSize = alphaSize; | ||
619 | s->save_nGroups = nGroups; | ||
620 | s->save_nSelectors = nSelectors; | ||
621 | s->save_EOB = EOB; | ||
622 | s->save_groupNo = groupNo; | ||
623 | s->save_groupPos = groupPos; | ||
624 | s->save_nextSym = nextSym; | ||
625 | s->save_nblockMAX = nblockMAX; | ||
626 | s->save_nblock = nblock; | ||
627 | s->save_es = es; | ||
628 | s->save_N = N; | ||
629 | s->save_curr = curr; | ||
630 | s->save_zt = zt; | ||
631 | s->save_zn = zn; | ||
632 | s->save_zvec = zvec; | ||
633 | s->save_zj = zj; | ||
634 | s->save_gSel = gSel; | ||
635 | s->save_gMinlen = gMinlen; | ||
636 | s->save_gLimit = gLimit; | ||
637 | s->save_gBase = gBase; | ||
638 | s->save_gPerm = gPerm; | ||
639 | |||
640 | return retVal; | ||
641 | } | ||
642 | |||
643 | |||
644 | /*-------------------------------------------------------------*/ | ||
645 | /*--- end decompress.c ---*/ | ||
646 | /*-------------------------------------------------------------*/ | ||
diff --git a/utils/bzip2/huffman.c b/utils/bzip2/huffman.c new file mode 100644 index 0000000000..2283fdbc5a --- /dev/null +++ b/utils/bzip2/huffman.c | |||
@@ -0,0 +1,205 @@ | |||
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 <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 | /*-------------------------------------------------------------*/ | ||
diff --git a/utils/bzip2/randtable.c b/utils/bzip2/randtable.c new file mode 100644 index 0000000000..6d62459906 --- /dev/null +++ b/utils/bzip2/randtable.c | |||
@@ -0,0 +1,84 @@ | |||
1 | |||
2 | /*-------------------------------------------------------------*/ | ||
3 | /*--- Table for randomising repetitive blocks ---*/ | ||
4 | /*--- randtable.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 <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 | /*---------------------------------------------*/ | ||
26 | Int32 BZ2_rNums[512] = { | ||
27 | 619, 720, 127, 481, 931, 816, 813, 233, 566, 247, | ||
28 | 985, 724, 205, 454, 863, 491, 741, 242, 949, 214, | ||
29 | 733, 859, 335, 708, 621, 574, 73, 654, 730, 472, | ||
30 | 419, 436, 278, 496, 867, 210, 399, 680, 480, 51, | ||
31 | 878, 465, 811, 169, 869, 675, 611, 697, 867, 561, | ||
32 | 862, 687, 507, 283, 482, 129, 807, 591, 733, 623, | ||
33 | 150, 238, 59, 379, 684, 877, 625, 169, 643, 105, | ||
34 | 170, 607, 520, 932, 727, 476, 693, 425, 174, 647, | ||
35 | 73, 122, 335, 530, 442, 853, 695, 249, 445, 515, | ||
36 | 909, 545, 703, 919, 874, 474, 882, 500, 594, 612, | ||
37 | 641, 801, 220, 162, 819, 984, 589, 513, 495, 799, | ||
38 | 161, 604, 958, 533, 221, 400, 386, 867, 600, 782, | ||
39 | 382, 596, 414, 171, 516, 375, 682, 485, 911, 276, | ||
40 | 98, 553, 163, 354, 666, 933, 424, 341, 533, 870, | ||
41 | 227, 730, 475, 186, 263, 647, 537, 686, 600, 224, | ||
42 | 469, 68, 770, 919, 190, 373, 294, 822, 808, 206, | ||
43 | 184, 943, 795, 384, 383, 461, 404, 758, 839, 887, | ||
44 | 715, 67, 618, 276, 204, 918, 873, 777, 604, 560, | ||
45 | 951, 160, 578, 722, 79, 804, 96, 409, 713, 940, | ||
46 | 652, 934, 970, 447, 318, 353, 859, 672, 112, 785, | ||
47 | 645, 863, 803, 350, 139, 93, 354, 99, 820, 908, | ||
48 | 609, 772, 154, 274, 580, 184, 79, 626, 630, 742, | ||
49 | 653, 282, 762, 623, 680, 81, 927, 626, 789, 125, | ||
50 | 411, 521, 938, 300, 821, 78, 343, 175, 128, 250, | ||
51 | 170, 774, 972, 275, 999, 639, 495, 78, 352, 126, | ||
52 | 857, 956, 358, 619, 580, 124, 737, 594, 701, 612, | ||
53 | 669, 112, 134, 694, 363, 992, 809, 743, 168, 974, | ||
54 | 944, 375, 748, 52, 600, 747, 642, 182, 862, 81, | ||
55 | 344, 805, 988, 739, 511, 655, 814, 334, 249, 515, | ||
56 | 897, 955, 664, 981, 649, 113, 974, 459, 893, 228, | ||
57 | 433, 837, 553, 268, 926, 240, 102, 654, 459, 51, | ||
58 | 686, 754, 806, 760, 493, 403, 415, 394, 687, 700, | ||
59 | 946, 670, 656, 610, 738, 392, 760, 799, 887, 653, | ||
60 | 978, 321, 576, 617, 626, 502, 894, 679, 243, 440, | ||
61 | 680, 879, 194, 572, 640, 724, 926, 56, 204, 700, | ||
62 | 707, 151, 457, 449, 797, 195, 791, 558, 945, 679, | ||
63 | 297, 59, 87, 824, 713, 663, 412, 693, 342, 606, | ||
64 | 134, 108, 571, 364, 631, 212, 174, 643, 304, 329, | ||
65 | 343, 97, 430, 751, 497, 314, 983, 374, 822, 928, | ||
66 | 140, 206, 73, 263, 980, 736, 876, 478, 430, 305, | ||
67 | 170, 514, 364, 692, 829, 82, 855, 953, 676, 246, | ||
68 | 369, 970, 294, 750, 807, 827, 150, 790, 288, 923, | ||
69 | 804, 378, 215, 828, 592, 281, 565, 555, 710, 82, | ||
70 | 896, 831, 547, 261, 524, 462, 293, 465, 502, 56, | ||
71 | 661, 821, 976, 991, 658, 869, 905, 758, 745, 193, | ||
72 | 768, 550, 608, 933, 378, 286, 215, 979, 792, 961, | ||
73 | 61, 688, 793, 644, 986, 403, 106, 366, 905, 644, | ||
74 | 372, 567, 466, 434, 645, 210, 389, 550, 919, 135, | ||
75 | 780, 773, 635, 389, 707, 100, 626, 958, 165, 504, | ||
76 | 920, 176, 193, 713, 857, 265, 203, 50, 668, 108, | ||
77 | 645, 990, 626, 197, 510, 357, 358, 850, 858, 364, | ||
78 | 936, 638 | ||
79 | }; | ||
80 | |||
81 | |||
82 | /*-------------------------------------------------------------*/ | ||
83 | /*--- end randtable.c ---*/ | ||
84 | /*-------------------------------------------------------------*/ | ||