source: trunk/src/libbz2/bzlib.c

Last change on this file was 249, checked in by umoeller, 23 years ago

Build updates, moved files from warpin.
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 16.5 KB
Line 
1
2/*-------------------------------------------------------------*/
3/*--- Library top-level functions. ---*/
4/*--- bzlib.c ---*/
5/*-------------------------------------------------------------*/
6
7/*--
8 This file is a part of bzip2 and/or libbzip2, a program and
9 library for lossless, block-sorting data compression.
10
11 Copyright (C) 1996-2000 Julian R Seward. All rights reserved.
12
13 Redistribution and use in source and binary forms, with or without
14 modification, are permitted provided that the following conditions
15 are met:
16
17 1. Redistributions of source code must retain the above copyright
18 notice, this list of conditions and the following disclaimer.
19
20 2. The origin of this software must not be misrepresented; you must
21 not claim that you wrote the original software. If you use this
22 software in a product, an acknowledgment in the product
23 documentation would be appreciated but is not required.
24
25 3. Altered source versions must be plainly marked as such, and must
26 not be misrepresented as being the original software.
27
28 4. The name of the author may not be used to endorse or promote
29 products derived from this software without specific prior written
30 permission.
31
32 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
33 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
34 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
35 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
36 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
37 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
38 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
39 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
40 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
41 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
42 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43
44 Julian Seward, Cambridge, UK.
45 jseward@acm.org
46 bzip2/libbzip2 version 1.0 of 21 March 2000
47
48 This program is based on (at least) the work of:
49 Mike Burrows
50 David Wheeler
51 Peter Fenwick
52 Alistair Moffat
53 Radford Neal
54 Ian H. Witten
55 Robert Sedgewick
56 Jon L. Bentley
57
58 For more information on these sources, see the manual.
59--*/
60
61/*--
62 CHANGES
63 ~~~~~~~
64 0.9.0 -- original version.
65
66 0.9.0a/b -- no changes in this file.
67
68 0.9.0c
69 * made zero-length BZ_FLUSH work correctly in bzCompress().
70 * fixed bzWrite/bzRead to ignore zero-length requests.
71 * fixed bzread to correctly handle read requests after EOF.
72 * wrong parameter order in call to bzDecompressInit in
73 bzBuffToBuffDecompress. Fixed.
74--*/
75
76#include "bzlib_private.h"
77
78/*---------------------------------------------------*/
79/*--- Decompression stuff ---*/
80/*---------------------------------------------------*/
81
82/*---------------------------------------------------*/
83#ifndef BZ_NO_STDIO
84void BZ2_bz__AssertH__fail ( int errcode )
85{
86 fprintf(stderr,
87 "\n\nbzip2/libbzip2: internal error number %d.\n"
88 "This is a bug in bzip2/libbzip2, %s.\n"
89 "Please report it to me at: jseward@acm.org. If this happened\n"
90 "when you were using some program which uses libbzip2 as a\n"
91 "component, you should also report this bug to the author(s)\n"
92 "of that program. Please make an effort to report this bug;\n"
93 "timely and accurate bug reports eventually lead to higher\n"
94 "quality software. Thanks. Julian Seward, 21 March 2000.\n\n",
95 errcode,
96 BZ2_bzlibVersion()
97 );
98 exit(3);
99}
100#endif
101
102
103/*---------------------------------------------------*/
104extern
105int bz_config_ok ( void )
106{
107 if (sizeof(int) != 4) return 0;
108 if (sizeof(short) != 2) return 0;
109 if (sizeof(char) != 1) return 0;
110 return 1;
111}
112
113
114/*---------------------------------------------------*/
115extern
116void* default_bzalloc ( void* opaque, Int32 items, Int32 size )
117{
118 void* v = malloc ( items * size );
119 return v;
120}
121
122extern
123void default_bzfree ( void* opaque, void* addr )
124{
125 if (addr != NULL) free ( addr );
126}
127
128/*---------------------------------------------------*/
129int BZ2_bzDecompressInit
130 ( bz_stream* strm,
131 int verbosity,
132 int small )
133{
134 DState* s;
135
136 if (!bz_config_ok()) return BZ_CONFIG_ERROR;
137
138 if (strm == NULL) return BZ_PARAM_ERROR;
139 if (small != 0 && small != 1) return BZ_PARAM_ERROR;
140 if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;
141
142 if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
143 if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
144
145 s = (DState*) BZALLOC( sizeof(DState) );
146 if (s == NULL) return BZ_MEM_ERROR;
147 s->strm = strm;
148 strm->state = s;
149 s->state = BZ_X_MAGIC_1;
150 s->bsLive = 0;
151 s->bsBuff = 0;
152 s->calculatedCombinedCRC = 0;
153 strm->total_in_lo32 = 0;
154 strm->total_in_hi32 = 0;
155 strm->total_out_lo32 = 0;
156 strm->total_out_hi32 = 0;
157 s->smallDecompress = (Bool)small;
158 s->ll4 = NULL;
159 s->ll16 = NULL;
160 s->tt = NULL;
161 s->currBlockNo = 0;
162 s->verbosity = verbosity;
163
164 return BZ_OK;
165}
166
167
168/*---------------------------------------------------*/
169static
170void unRLE_obuf_to_output_FAST ( DState* s )
171{
172 UChar k1;
173
174 if (s->blockRandomised) {
175
176 while (True) {
177 /* try to finish existing run */
178 while (True) {
179 if (s->strm->avail_out == 0) return;
180 if (s->state_out_len == 0) break;
181 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
182 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
183 s->state_out_len--;
184 s->strm->next_out++;
185 s->strm->avail_out--;
186 s->strm->total_out_lo32++;
187 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
188 }
189
190 /* can a new run be started? */
191 if (s->nblock_used == s->save_nblock+1) return;
192
193
194 s->state_out_len = 1;
195 s->state_out_ch = s->k0;
196 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
197 k1 ^= BZ_RAND_MASK; s->nblock_used++;
198 if (s->nblock_used == s->save_nblock+1) continue;
199 if (k1 != s->k0) { s->k0 = k1; continue; };
200
201 s->state_out_len = 2;
202 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
203 k1 ^= BZ_RAND_MASK; s->nblock_used++;
204 if (s->nblock_used == s->save_nblock+1) continue;
205 if (k1 != s->k0) { s->k0 = k1; continue; };
206
207 s->state_out_len = 3;
208 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
209 k1 ^= BZ_RAND_MASK; s->nblock_used++;
210 if (s->nblock_used == s->save_nblock+1) continue;
211 if (k1 != s->k0) { s->k0 = k1; continue; };
212
213 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
214 k1 ^= BZ_RAND_MASK; s->nblock_used++;
215 s->state_out_len = ((Int32)k1) + 4;
216 BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK;
217 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
218 }
219
220 } else {
221
222 /* restore */
223 UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC;
224 UChar c_state_out_ch = s->state_out_ch;
225 Int32 c_state_out_len = s->state_out_len;
226 Int32 c_nblock_used = s->nblock_used;
227 Int32 c_k0 = s->k0;
228 UInt32* c_tt = s->tt;
229 UInt32 c_tPos = s->tPos;
230 char* cs_next_out = s->strm->next_out;
231 unsigned int cs_avail_out = s->strm->avail_out;
232 /* end restore */
233
234 UInt32 avail_out_INIT = cs_avail_out;
235 Int32 s_save_nblockPP = s->save_nblock+1;
236 unsigned int total_out_lo32_old;
237
238 while (True) {
239
240 /* try to finish existing run */
241 if (c_state_out_len > 0) {
242 while (True) {
243 if (cs_avail_out == 0) goto return_notr;
244 if (c_state_out_len == 1) break;
245 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
246 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
247 c_state_out_len--;
248 cs_next_out++;
249 cs_avail_out--;
250 }
251 s_state_out_len_eq_one:
252 {
253 if (cs_avail_out == 0) {
254 c_state_out_len = 1; goto return_notr;
255 };
256 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
257 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
258 cs_next_out++;
259 cs_avail_out--;
260 }
261 }
262 /* can a new run be started? */
263 if (c_nblock_used == s_save_nblockPP) {
264 c_state_out_len = 0; goto return_notr;
265 };
266 c_state_out_ch = c_k0;
267 BZ_GET_FAST_C(k1); c_nblock_used++;
268 if (k1 != c_k0) {
269 c_k0 = k1; goto s_state_out_len_eq_one;
270 };
271 if (c_nblock_used == s_save_nblockPP)
272 goto s_state_out_len_eq_one;
273
274 c_state_out_len = 2;
275 BZ_GET_FAST_C(k1); c_nblock_used++;
276 if (c_nblock_used == s_save_nblockPP) continue;
277 if (k1 != c_k0) { c_k0 = k1; continue; };
278
279 c_state_out_len = 3;
280 BZ_GET_FAST_C(k1); c_nblock_used++;
281 if (c_nblock_used == s_save_nblockPP) continue;
282 if (k1 != c_k0) { c_k0 = k1; continue; };
283
284 BZ_GET_FAST_C(k1); c_nblock_used++;
285 c_state_out_len = ((Int32)k1) + 4;
286 BZ_GET_FAST_C(c_k0); c_nblock_used++;
287 }
288
289 return_notr:
290 total_out_lo32_old = s->strm->total_out_lo32;
291 s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
292 if (s->strm->total_out_lo32 < total_out_lo32_old)
293 s->strm->total_out_hi32++;
294
295 /* save */
296 s->calculatedBlockCRC = c_calculatedBlockCRC;
297 s->state_out_ch = c_state_out_ch;
298 s->state_out_len = c_state_out_len;
299 s->nblock_used = c_nblock_used;
300 s->k0 = c_k0;
301 s->tt = c_tt;
302 s->tPos = c_tPos;
303 s->strm->next_out = cs_next_out;
304 s->strm->avail_out = cs_avail_out;
305 /* end save */
306 }
307}
308
309
310
311/*---------------------------------------------------*/
312__inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab )
313{
314 Int32 nb, na, mid;
315 nb = 0;
316 na = 256;
317 do {
318 mid = (nb + na) >> 1;
319 if (indx >= cftab[mid]) nb = mid; else na = mid;
320 }
321 while (na - nb != 1);
322 return nb;
323}
324
325
326/*---------------------------------------------------*/
327static
328void unRLE_obuf_to_output_SMALL ( DState* s )
329{
330 UChar k1;
331
332 if (s->blockRandomised) {
333
334 while (True) {
335 /* try to finish existing run */
336 while (True) {
337 if (s->strm->avail_out == 0) return;
338 if (s->state_out_len == 0) break;
339 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
340 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
341 s->state_out_len--;
342 s->strm->next_out++;
343 s->strm->avail_out--;
344 s->strm->total_out_lo32++;
345 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
346 }
347
348 /* can a new run be started? */
349 if (s->nblock_used == s->save_nblock+1) return;
350
351
352 s->state_out_len = 1;
353 s->state_out_ch = s->k0;
354 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
355 k1 ^= BZ_RAND_MASK; s->nblock_used++;
356 if (s->nblock_used == s->save_nblock+1) continue;
357 if (k1 != s->k0) { s->k0 = k1; continue; };
358
359 s->state_out_len = 2;
360 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
361 k1 ^= BZ_RAND_MASK; s->nblock_used++;
362 if (s->nblock_used == s->save_nblock+1) continue;
363 if (k1 != s->k0) { s->k0 = k1; continue; };
364
365 s->state_out_len = 3;
366 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
367 k1 ^= BZ_RAND_MASK; s->nblock_used++;
368 if (s->nblock_used == s->save_nblock+1) continue;
369 if (k1 != s->k0) { s->k0 = k1; continue; };
370
371 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
372 k1 ^= BZ_RAND_MASK; s->nblock_used++;
373 s->state_out_len = ((Int32)k1) + 4;
374 BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK;
375 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
376 }
377
378 } else {
379
380 while (True) {
381 /* try to finish existing run */
382 while (True) {
383 if (s->strm->avail_out == 0) return;
384 if (s->state_out_len == 0) break;
385 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
386 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
387 s->state_out_len--;
388 s->strm->next_out++;
389 s->strm->avail_out--;
390 s->strm->total_out_lo32++;
391 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
392 }
393
394 /* can a new run be started? */
395 if (s->nblock_used == s->save_nblock+1) return;
396
397 s->state_out_len = 1;
398 s->state_out_ch = s->k0;
399 BZ_GET_SMALL(k1); s->nblock_used++;
400 if (s->nblock_used == s->save_nblock+1) continue;
401 if (k1 != s->k0) { s->k0 = k1; continue; };
402
403 s->state_out_len = 2;
404 BZ_GET_SMALL(k1); s->nblock_used++;
405 if (s->nblock_used == s->save_nblock+1) continue;
406 if (k1 != s->k0) { s->k0 = k1; continue; };
407
408 s->state_out_len = 3;
409 BZ_GET_SMALL(k1); s->nblock_used++;
410 if (s->nblock_used == s->save_nblock+1) continue;
411 if (k1 != s->k0) { s->k0 = k1; continue; };
412
413 BZ_GET_SMALL(k1); s->nblock_used++;
414 s->state_out_len = ((Int32)k1) + 4;
415 BZ_GET_SMALL(s->k0); s->nblock_used++;
416 }
417
418 }
419}
420
421
422/*---------------------------------------------------*/
423int BZ2_bzDecompress ( bz_stream *strm )
424{
425 DState* s;
426 if (strm == NULL) return BZ_PARAM_ERROR;
427 s = (DState*) strm->state;
428 if (s == NULL) return BZ_PARAM_ERROR;
429 if (s->strm != strm) return BZ_PARAM_ERROR;
430
431 while (True) {
432 if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;
433 if (s->state == BZ_X_OUTPUT) {
434 if (s->smallDecompress)
435 unRLE_obuf_to_output_SMALL ( s ); else
436 unRLE_obuf_to_output_FAST ( s );
437 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
438 BZ_FINALISE_CRC ( s->calculatedBlockCRC );
439 if (s->verbosity >= 3)
440 VPrintf2 ( " {0x%x, 0x%x}", s->storedBlockCRC,
441 s->calculatedBlockCRC );
442 if (s->verbosity >= 2) VPrintf0 ( "]" );
443 if (s->calculatedBlockCRC != s->storedBlockCRC)
444 return BZ_DATA_ERROR;
445 s->calculatedCombinedCRC
446 = (s->calculatedCombinedCRC << 1) |
447 (s->calculatedCombinedCRC >> 31);
448 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
449 s->state = BZ_X_BLKHDR_1;
450 } else {
451 return BZ_OK;
452 }
453 }
454 if (s->state >= BZ_X_MAGIC_1) {
455 Int32 r = BZ2_decompress ( s );
456 if (r == BZ_STREAM_END) {
457 if (s->verbosity >= 3)
458 VPrintf2 ( "\n combined CRCs: stored = 0x%x, computed = 0x%x",
459 s->storedCombinedCRC, s->calculatedCombinedCRC );
460 if (s->calculatedCombinedCRC != s->storedCombinedCRC)
461 return BZ_DATA_ERROR;
462 return r;
463 }
464 if (s->state != BZ_X_OUTPUT) return r;
465 }
466 }
467
468 AssertH ( 0, 6001 );
469
470 return 0; /*NOTREACHED*/
471}
472
473
474/*---------------------------------------------------*/
475int BZ2_bzDecompressEnd ( bz_stream *strm )
476{
477 DState* s;
478 if (strm == NULL) return BZ_PARAM_ERROR;
479 s = (DState*) strm->state;
480 if (s == NULL) return BZ_PARAM_ERROR;
481 if (s->strm != strm) return BZ_PARAM_ERROR;
482
483 if (s->tt != NULL) BZFREE(s->tt);
484 if (s->ll16 != NULL) BZFREE(s->ll16);
485 if (s->ll4 != NULL) BZFREE(s->ll4);
486
487 BZFREE(strm->state);
488 strm->state = NULL;
489
490 return BZ_OK;
491}
492
493
494
495/*-------------------------------------------------------------*/
496/*--- end bzlib.c ---*/
497/*-------------------------------------------------------------*/
Note: See TracBrowser for help on using the repository browser.