1 // This benchmark is basically bzip2 (mashed to be a single file)
2 // compressing and decompressing some data. It tests Valgrind's handling of
3 // realistic and "difficult" (ie. lots of branches and memory accesses)
4 // integer code. Execution is spread out over quite a few basic blocks;
5 // --profile-flags indicates that to get to the top 90%th percentile of
6 // dynamic BB counts requires considering the top 51 basic blocks
7
8 // This program can be used both as part of the performance test
9 // suite, in which case we want it to run for quite a while,
10 // and as part of the regression (correctness) test suite, in
11 // which case we want it to run quickly and be verbose.
12 // So it does the latter iff given a command line arg.
13
14 // Licensing: the code within is mostly taken from bzip2, which has a BSD
15 // license. There is a little code from VEX, which is licensed under GPLv2
16 // And it's all written by Julian Seward.
17
18 #define BZ_NO_STDIO
19
20
21 /*-------------------------------------------------------------*/
22 /*--- Private header file for the library. ---*/
23 /*--- bzlib_private.h ---*/
24 /*-------------------------------------------------------------*/
25
26 /*--
27 This file is a part of bzip2 and/or libbzip2, a program and
28 library for lossless, block-sorting data compression.
29
30 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
31
32 Redistribution and use in source and binary forms, with or without
33 modification, are permitted provided that the following conditions
34 are met:
35
36 1. Redistributions of source code must retain the above copyright
37 notice, this list of conditions and the following disclaimer.
38
39 2. The origin of this software must not be misrepresented; you must
40 not claim that you wrote the original software. If you use this
41 software in a product, an acknowledgment in the product
42 documentation would be appreciated but is not required.
43
44 3. Altered source versions must be plainly marked as such, and must
45 not be misrepresented as being the original software.
46
47 4. The name of the author may not be used to endorse or promote
48 products derived from this software without specific prior written
49 permission.
50
51 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
52 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
53 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
54 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
55 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
56 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
57 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
58 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
59 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
60 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
61 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
62
63 Julian Seward, Cambridge, UK.
64 jseward@bzip.org
65 bzip2/libbzip2 version 1.0 of 21 March 2000
66
67 This program is based on (at least) the work of:
68 Mike Burrows
69 David Wheeler
70 Peter Fenwick
71 Alistair Moffat
72 Radford Neal
73 Ian H. Witten
74 Robert Sedgewick
75 Jon L. Bentley
76
77 For more information on these sources, see the manual.
78 --*/
79
80
81 #ifndef _BZLIB_PRIVATE_H
82 #define _BZLIB_PRIVATE_H
83
84 #include <stdlib.h>
85
86 #ifndef BZ_NO_STDIO
87 #include <stdio.h>
88 #include <ctype.h>
89 #include <string.h>
90 #endif
91
92
93 /*-------------------------------------------------------------*/
94 /*--- Public header file for the library. ---*/
95 /*--- bzlib.h ---*/
96 /*-------------------------------------------------------------*/
97
98 /*--
99 This file is a part of bzip2 and/or libbzip2, a program and
100 library for lossless, block-sorting data compression.
101
102 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
103
104 Redistribution and use in source and binary forms, with or without
105 modification, are permitted provided that the following conditions
106 are met:
107
108 1. Redistributions of source code must retain the above copyright
109 notice, this list of conditions and the following disclaimer.
110
111 2. The origin of this software must not be misrepresented; you must
112 not claim that you wrote the original software. If you use this
113 software in a product, an acknowledgment in the product
114 documentation would be appreciated but is not required.
115
116 3. Altered source versions must be plainly marked as such, and must
117 not be misrepresented as being the original software.
118
119 4. The name of the author may not be used to endorse or promote
120 products derived from this software without specific prior written
121 permission.
122
123 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
124 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
125 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
126 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
127 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
128 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
129 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
130 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
131 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
132 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
133 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
134
135 Julian Seward, Cambridge, UK.
136 jseward@bzip.org
137 bzip2/libbzip2 version 1.0 of 21 March 2000
138
139 This program is based on (at least) the work of:
140 Mike Burrows
141 David Wheeler
142 Peter Fenwick
143 Alistair Moffat
144 Radford Neal
145 Ian H. Witten
146 Robert Sedgewick
147 Jon L. Bentley
148
149 For more information on these sources, see the manual.
150 --*/
151
152
153 #ifndef _BZLIB_H
154 #define _BZLIB_H
155
156 #ifdef __cplusplus
157 extern "C" {
158 #endif
159
160 #define BZ_RUN 0
161 #define BZ_FLUSH 1
162 #define BZ_FINISH 2
163
164 #define BZ_OK 0
165 #define BZ_RUN_OK 1
166 #define BZ_FLUSH_OK 2
167 #define BZ_FINISH_OK 3
168 #define BZ_STREAM_END 4
169 #define BZ_SEQUENCE_ERROR (-1)
170 #define BZ_PARAM_ERROR (-2)
171 #define BZ_MEM_ERROR (-3)
172 #define BZ_DATA_ERROR (-4)
173 #define BZ_DATA_ERROR_MAGIC (-5)
174 #define BZ_IO_ERROR (-6)
175 #define BZ_UNEXPECTED_EOF (-7)
176 #define BZ_OUTBUFF_FULL (-8)
177 #define BZ_CONFIG_ERROR (-9)
178
179 typedef
180 struct {
181 char *next_in;
182 unsigned int avail_in;
183 unsigned int total_in_lo32;
184 unsigned int total_in_hi32;
185
186 char *next_out;
187 unsigned int avail_out;
188 unsigned int total_out_lo32;
189 unsigned int total_out_hi32;
190
191 void *state;
192
193 void *(*bzalloc)(void *,int,int);
194 void (*bzfree)(void *,void *);
195 void *opaque;
196 }
197 bz_stream;
198
199
200 #ifndef BZ_IMPORT
201 #define BZ_EXPORT
202 #endif
203
204 #ifndef BZ_NO_STDIO
205 /* Need a definitition for FILE */
206 #include <stdio.h>
207 #endif
208
209 #ifdef _WIN32
210 # include <windows.h>
211 # ifdef small
212 /* windows.h define small to char */
213 # undef small
214 # endif
215 # ifdef BZ_EXPORT
216 # define BZ_API(func) WINAPI func
217 # define BZ_EXTERN extern
218 # else
219 /* import windows dll dynamically */
220 # define BZ_API(func) (WINAPI * func)
221 # define BZ_EXTERN
222 # endif
223 #else
224 # define BZ_API(func) func
225 # define BZ_EXTERN extern
226 #endif
227
228
229 /*-- Core (low-level) library functions --*/
230
231 BZ_EXTERN int BZ_API(BZ2_bzCompressInit) (
232 bz_stream* strm,
233 int blockSize100k,
234 int verbosity,
235 int workFactor
236 );
237
238 BZ_EXTERN int BZ_API(BZ2_bzCompress) (
239 bz_stream* strm,
240 int action
241 );
242
243 BZ_EXTERN int BZ_API(BZ2_bzCompressEnd) (
244 bz_stream* strm
245 );
246
247 BZ_EXTERN int BZ_API(BZ2_bzDecompressInit) (
248 bz_stream *strm,
249 int verbosity,
250 int small
251 );
252
253 BZ_EXTERN int BZ_API(BZ2_bzDecompress) (
254 bz_stream* strm
255 );
256
257 BZ_EXTERN int BZ_API(BZ2_bzDecompressEnd) (
258 bz_stream *strm
259 );
260
261
262
263 /*-- High(er) level library functions --*/
264
265 #ifndef BZ_NO_STDIO
266 #define BZ_MAX_UNUSED 5000
267
268 typedef void BZFILE;
269
270 BZ_EXTERN BZFILE* BZ_API(BZ2_bzReadOpen) (
271 int* bzerror,
272 FILE* f,
273 int verbosity,
274 int small,
275 void* unused,
276 int nUnused
277 );
278
279 BZ_EXTERN void BZ_API(BZ2_bzReadClose) (
280 int* bzerror,
281 BZFILE* b
282 );
283
284 BZ_EXTERN void BZ_API(BZ2_bzReadGetUnused) (
285 int* bzerror,
286 BZFILE* b,
287 void** unused,
288 int* nUnused
289 );
290
291 BZ_EXTERN int BZ_API(BZ2_bzRead) (
292 int* bzerror,
293 BZFILE* b,
294 void* buf,
295 int len
296 );
297
298 BZ_EXTERN BZFILE* BZ_API(BZ2_bzWriteOpen) (
299 int* bzerror,
300 FILE* f,
301 int blockSize100k,
302 int verbosity,
303 int workFactor
304 );
305
306 BZ_EXTERN void BZ_API(BZ2_bzWrite) (
307 int* bzerror,
308 BZFILE* b,
309 void* buf,
310 int len
311 );
312
313 BZ_EXTERN void BZ_API(BZ2_bzWriteClose) (
314 int* bzerror,
315 BZFILE* b,
316 int abandon,
317 unsigned int* nbytes_in,
318 unsigned int* nbytes_out
319 );
320
321 BZ_EXTERN void BZ_API(BZ2_bzWriteClose64) (
322 int* bzerror,
323 BZFILE* b,
324 int abandon,
325 unsigned int* nbytes_in_lo32,
326 unsigned int* nbytes_in_hi32,
327 unsigned int* nbytes_out_lo32,
328 unsigned int* nbytes_out_hi32
329 );
330 #endif
331
332
333 /*-- Utility functions --*/
334
335 BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffCompress) (
336 char* dest,
337 unsigned int* destLen,
338 char* source,
339 unsigned int sourceLen,
340 int blockSize100k,
341 int verbosity,
342 int workFactor
343 );
344
345 BZ_EXTERN int BZ_API(BZ2_bzBuffToBuffDecompress) (
346 char* dest,
347 unsigned int* destLen,
348 char* source,
349 unsigned int sourceLen,
350 int small,
351 int verbosity
352 );
353
354
355 /*--
356 Code contributed by Yoshioka Tsuneo
357 (QWF00133@niftyserve.or.jp/tsuneo-y@is.aist-nara.ac.jp),
358 to support better zlib compatibility.
359 This code is not _officially_ part of libbzip2 (yet);
360 I haven't tested it, documented it, or considered the
361 threading-safeness of it.
362 If this code breaks, please contact both Yoshioka and me.
363 --*/
364
365 BZ_EXTERN const char * BZ_API(BZ2_bzlibVersion) (
366 void
367 );
368
369 #ifndef BZ_NO_STDIO
370 BZ_EXTERN BZFILE * BZ_API(BZ2_bzopen) (
371 const char *path,
372 const char *mode
373 );
374
375 BZ_EXTERN BZFILE * BZ_API(BZ2_bzdopen) (
376 int fd,
377 const char *mode
378 );
379
380 BZ_EXTERN int BZ_API(BZ2_bzread) (
381 BZFILE* b,
382 void* buf,
383 int len
384 );
385
386 BZ_EXTERN int BZ_API(BZ2_bzwrite) (
387 BZFILE* b,
388 void* buf,
389 int len
390 );
391
392 BZ_EXTERN int BZ_API(BZ2_bzflush) (
393 BZFILE* b
394 );
395
396 BZ_EXTERN void BZ_API(BZ2_bzclose) (
397 BZFILE* b
398 );
399
400 BZ_EXTERN const char * BZ_API(BZ2_bzerror) (
401 BZFILE *b,
402 int *errnum
403 );
404 #endif
405
406 #ifdef __cplusplus
407 }
408 #endif
409
410 #endif
411
412 /*-------------------------------------------------------------*/
413 /*--- end bzlib.h ---*/
414 /*-------------------------------------------------------------*/
415
416
417
418
419 /*-- General stuff. --*/
420
421 #define BZ_VERSION "1.0.3, 17-Oct-2004"
422
423 typedef char Char;
424 typedef unsigned char Bool;
425 typedef unsigned char UChar;
426 typedef int Int32;
427 typedef unsigned int UInt32;
428 typedef short Int16;
429 typedef unsigned short UInt16;
430
431 #define True ((Bool)1)
432 #define False ((Bool)0)
433
434 #ifndef __GNUC__
435 #define __inline__ /* */
436 #endif
437
438 #ifndef BZ_NO_STDIO
439 extern void BZ2_bz__AssertH__fail ( int errcode );
440 #define AssertH(cond,errcode) \
441 { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }
442 #if BZ_DEBUG
443 #define AssertD(cond,msg) \
444 { if (!(cond)) { \
445 fprintf ( stderr, \
446 "\n\nlibbzip2(debug build): internal error\n\t%s\n", msg );\
447 exit(1); \
448 }}
449 #else
450 #define AssertD(cond,msg) /* */
451 #endif
452 #define VPrintf0(zf) \
453 fprintf(stderr,zf)
454 #define VPrintf1(zf,za1) \
455 fprintf(stderr,zf,za1)
456 #define VPrintf2(zf,za1,za2) \
457 fprintf(stderr,zf,za1,za2)
458 #define VPrintf3(zf,za1,za2,za3) \
459 fprintf(stderr,zf,za1,za2,za3)
460 #define VPrintf4(zf,za1,za2,za3,za4) \
461 fprintf(stderr,zf,za1,za2,za3,za4)
462 #define VPrintf5(zf,za1,za2,za3,za4,za5) \
463 fprintf(stderr,zf,za1,za2,za3,za4,za5)
464 #else
465 extern void bz_internal_error ( int errcode );
466 #define AssertH(cond,errcode) \
467 { if (!(cond)) bz_internal_error ( errcode ); }
468 #define AssertD(cond,msg) /* */
469 #define VPrintf0(zf) \
470 vex_printf(zf)
471 #define VPrintf1(zf,za1) \
472 vex_printf(zf,za1)
473 #define VPrintf2(zf,za1,za2) \
474 vex_printf(zf,za1,za2)
475 #define VPrintf3(zf,za1,za2,za3) \
476 vex_printf(zf,za1,za2,za3)
477 #define VPrintf4(zf,za1,za2,za3,za4) \
478 vex_printf(zf,za1,za2,za3,za4)
479 #define VPrintf5(zf,za1,za2,za3,za4,za5) \
480 vex_printf(zf,za1,za2,za3,za4,za5)
481 #endif
482
483
484 #define BZALLOC(nnn) (strm->bzalloc)(strm->opaque,(nnn),1)
485 #define BZFREE(ppp) (strm->bzfree)(strm->opaque,(ppp))
486
487
488 /*-- Header bytes. --*/
489
490 #define BZ_HDR_B 0x42 /* 'B' */
491 #define BZ_HDR_Z 0x5a /* 'Z' */
492 #define BZ_HDR_h 0x68 /* 'h' */
493 #define BZ_HDR_0 0x30 /* '0' */
494
495 /*-- Constants for the back end. --*/
496
497 #define BZ_MAX_ALPHA_SIZE 258
498 #define BZ_MAX_CODE_LEN 23
499
500 #define BZ_RUNA 0
501 #define BZ_RUNB 1
502
503 #define BZ_N_GROUPS 6
504 #define BZ_G_SIZE 50
505 #define BZ_N_ITERS 4
506
507 #define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))
508
509
510
511 /*-- Stuff for randomising repetitive blocks. --*/
512
513 extern Int32 BZ2_rNums[512];
514
515 #define BZ_RAND_DECLS \
516 Int32 rNToGo; \
517 Int32 rTPos \
518
519 #define BZ_RAND_INIT_MASK \
520 s->rNToGo = 0; \
521 s->rTPos = 0 \
522
523 #define BZ_RAND_MASK ((s->rNToGo == 1) ? 1 : 0)
524
525 #define BZ_RAND_UPD_MASK \
526 if (s->rNToGo == 0) { \
527 s->rNToGo = BZ2_rNums[s->rTPos]; \
528 s->rTPos++; \
529 if (s->rTPos == 512) s->rTPos = 0; \
530 } \
531 s->rNToGo--;
532
533
534
535 /*-- Stuff for doing CRCs. --*/
536
537 extern UInt32 BZ2_crc32Table[256];
538
539 #define BZ_INITIALISE_CRC(crcVar) \
540 { \
541 crcVar = 0xffffffffL; \
542 }
543
544 #define BZ_FINALISE_CRC(crcVar) \
545 { \
546 crcVar = ~(crcVar); \
547 }
548
549 #define BZ_UPDATE_CRC(crcVar,cha) \
550 { \
551 crcVar = (crcVar << 8) ^ \
552 BZ2_crc32Table[(crcVar >> 24) ^ \
553 ((UChar)cha)]; \
554 }
555
556
557
558 /*-- States and modes for compression. --*/
559
560 #define BZ_M_IDLE 1
561 #define BZ_M_RUNNING 2
562 #define BZ_M_FLUSHING 3
563 #define BZ_M_FINISHING 4
564
565 #define BZ_S_OUTPUT 1
566 #define BZ_S_INPUT 2
567
568 #define BZ_N_RADIX 2
569 #define BZ_N_QSORT 12
570 #define BZ_N_SHELL 18
571 #define BZ_N_OVERSHOOT (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
572
573
574
575
576 /*-- Structure holding all the compression-side stuff. --*/
577
578 typedef
579 struct {
580 /* pointer back to the struct bz_stream */
581 bz_stream* strm;
582
583 /* mode this stream is in, and whether inputting */
584 /* or outputting data */
585 Int32 mode;
586 Int32 state;
587
588 /* remembers avail_in when flush/finish requested */
589 UInt32 avail_in_expect;
590
591 /* for doing the block sorting */
592 UInt32* arr1;
593 UInt32* arr2;
594 UInt32* ftab;
595 Int32 origPtr;
596
597 /* aliases for arr1 and arr2 */
598 UInt32* ptr;
599 UChar* block;
600 UInt16* mtfv;
601 UChar* zbits;
602
603 /* for deciding when to use the fallback sorting algorithm */
604 Int32 workFactor;
605
606 /* run-length-encoding of the input */
607 UInt32 state_in_ch;
608 Int32 state_in_len;
609 BZ_RAND_DECLS;
610
611 /* input and output limits and current posns */
612 Int32 nblock;
613 Int32 nblockMAX;
614 Int32 numZ;
615 Int32 state_out_pos;
616
617 /* map of bytes used in block */
618 Int32 nInUse;
619 Bool inUse[256];
620 UChar unseqToSeq[256];
621
622 /* the buffer for bit stream creation */
623 UInt32 bsBuff;
624 Int32 bsLive;
625
626 /* block and combined CRCs */
627 UInt32 blockCRC;
628 UInt32 combinedCRC;
629
630 /* misc administratium */
631 Int32 verbosity;
632 Int32 blockNo;
633 Int32 blockSize100k;
634
635 /* stuff for coding the MTF values */
636 Int32 nMTF;
637 Int32 mtfFreq [BZ_MAX_ALPHA_SIZE];
638 UChar selector [BZ_MAX_SELECTORS];
639 UChar selectorMtf[BZ_MAX_SELECTORS];
640
641 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
642 Int32 code [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
643 Int32 rfreq [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
644 /* second dimension: only 3 needed; 4 makes index calculations faster */
645 UInt32 len_pack[BZ_MAX_ALPHA_SIZE][4];
646
647 }
648 EState;
649
650
651
652 /*-- externs for compression. --*/
653
654 extern void
655 BZ2_blockSort ( EState* );
656
657 extern void
658 BZ2_compressBlock ( EState*, Bool );
659
660 extern void
661 BZ2_bsInitWrite ( EState* );
662
663 extern void
664 BZ2_hbAssignCodes ( Int32*, UChar*, Int32, Int32, Int32 );
665
666 extern void
667 BZ2_hbMakeCodeLengths ( UChar*, Int32*, Int32, Int32 );
668
669
670
671 /*-- states for decompression. --*/
672
673 #define BZ_X_IDLE 1
674 #define BZ_X_OUTPUT 2
675
676 #define BZ_X_MAGIC_1 10
677 #define BZ_X_MAGIC_2 11
678 #define BZ_X_MAGIC_3 12
679 #define BZ_X_MAGIC_4 13
680 #define BZ_X_BLKHDR_1 14
681 #define BZ_X_BLKHDR_2 15
682 #define BZ_X_BLKHDR_3 16
683 #define BZ_X_BLKHDR_4 17
684 #define BZ_X_BLKHDR_5 18
685 #define BZ_X_BLKHDR_6 19
686 #define BZ_X_BCRC_1 20
687 #define BZ_X_BCRC_2 21
688 #define BZ_X_BCRC_3 22
689 #define BZ_X_BCRC_4 23
690 #define BZ_X_RANDBIT 24
691 #define BZ_X_ORIGPTR_1 25
692 #define BZ_X_ORIGPTR_2 26
693 #define BZ_X_ORIGPTR_3 27
694 #define BZ_X_MAPPING_1 28
695 #define BZ_X_MAPPING_2 29
696 #define BZ_X_SELECTOR_1 30
697 #define BZ_X_SELECTOR_2 31
698 #define BZ_X_SELECTOR_3 32
699 #define BZ_X_CODING_1 33
700 #define BZ_X_CODING_2 34
701 #define BZ_X_CODING_3 35
702 #define BZ_X_MTF_1 36
703 #define BZ_X_MTF_2 37
704 #define BZ_X_MTF_3 38
705 #define BZ_X_MTF_4 39
706 #define BZ_X_MTF_5 40
707 #define BZ_X_MTF_6 41
708 #define BZ_X_ENDHDR_2 42
709 #define BZ_X_ENDHDR_3 43
710 #define BZ_X_ENDHDR_4 44
711 #define BZ_X_ENDHDR_5 45
712 #define BZ_X_ENDHDR_6 46
713 #define BZ_X_CCRC_1 47
714 #define BZ_X_CCRC_2 48
715 #define BZ_X_CCRC_3 49
716 #define BZ_X_CCRC_4 50
717
718
719
720 /*-- Constants for the fast MTF decoder. --*/
721
722 #define MTFA_SIZE 4096
723 #define MTFL_SIZE 16
724
725
726
727 /*-- Structure holding all the decompression-side stuff. --*/
728
729 typedef
730 struct {
731 /* pointer back to the struct bz_stream */
732 bz_stream* strm;
733
734 /* state indicator for this stream */
735 Int32 state;
736
737 /* for doing the final run-length decoding */
738 UChar state_out_ch;
739 Int32 state_out_len;
740 Bool blockRandomised;
741 BZ_RAND_DECLS;
742
743 /* the buffer for bit stream reading */
744 UInt32 bsBuff;
745 Int32 bsLive;
746
747 /* misc administratium */
748 Int32 blockSize100k;
749 Bool smallDecompress;
750 Int32 currBlockNo;
751 Int32 verbosity;
752
753 /* for undoing the Burrows-Wheeler transform */
754 Int32 origPtr;
755 UInt32 tPos;
756 Int32 k0;
757 Int32 unzftab[256];
758 Int32 nblock_used;
759 Int32 cftab[257];
760 Int32 cftabCopy[257];
761
762 /* for undoing the Burrows-Wheeler transform (FAST) */
763 UInt32 *tt;
764
765 /* for undoing the Burrows-Wheeler transform (SMALL) */
766 UInt16 *ll16;
767 UChar *ll4;
768
769 /* stored and calculated CRCs */
770 UInt32 storedBlockCRC;
771 UInt32 storedCombinedCRC;
772 UInt32 calculatedBlockCRC;
773 UInt32 calculatedCombinedCRC;
774
775 /* map of bytes used in block */
776 Int32 nInUse;
777 Bool inUse[256];
778 Bool inUse16[16];
779 UChar seqToUnseq[256];
780
781 /* for decoding the MTF values */
782 UChar mtfa [MTFA_SIZE];
783 Int32 mtfbase[256 / MTFL_SIZE];
784 UChar selector [BZ_MAX_SELECTORS];
785 UChar selectorMtf[BZ_MAX_SELECTORS];
786 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
787
788 Int32 limit [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
789 Int32 base [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
790 Int32 perm [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
791 Int32 minLens[BZ_N_GROUPS];
792
793 /* save area for scalars in the main decompress code */
794 Int32 save_i;
795 Int32 save_j;
796 Int32 save_t;
797 Int32 save_alphaSize;
798 Int32 save_nGroups;
799 Int32 save_nSelectors;
800 Int32 save_EOB;
801 Int32 save_groupNo;
802 Int32 save_groupPos;
803 Int32 save_nextSym;
804 Int32 save_nblockMAX;
805 Int32 save_nblock;
806 Int32 save_es;
807 Int32 save_N;
808 Int32 save_curr;
809 Int32 save_zt;
810 Int32 save_zn;
811 Int32 save_zvec;
812 Int32 save_zj;
813 Int32 save_gSel;
814 Int32 save_gMinlen;
815 Int32* save_gLimit;
816 Int32* save_gBase;
817 Int32* save_gPerm;
818
819 }
820 DState;
821
822
823
824 /*-- Macros for decompression. --*/
825
826 #define BZ_GET_FAST(cccc) \
827 s->tPos = s->tt[s->tPos]; \
828 cccc = (UChar)(s->tPos & 0xff); \
829 s->tPos >>= 8;
830
831 #define BZ_GET_FAST_C(cccc) \
832 c_tPos = c_tt[c_tPos]; \
833 cccc = (UChar)(c_tPos & 0xff); \
834 c_tPos >>= 8;
835
836 #define SET_LL4(i,n) \
837 { if (((i) & 0x1) == 0) \
838 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else \
839 s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4); \
840 }
841
842 #define GET_LL4(i) \
843 ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
844
845 #define SET_LL(i,n) \
846 { s->ll16[i] = (UInt16)(n & 0x0000ffff); \
847 SET_LL4(i, n >> 16); \
848 }
849
850 #define GET_LL(i) \
851 (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
852
853 #define BZ_GET_SMALL(cccc) \
854 cccc = BZ2_indexIntoF ( s->tPos, s->cftab ); \
855 s->tPos = GET_LL(s->tPos);
856
857
858 /*-- externs for decompression. --*/
859
860 extern Int32
861 BZ2_indexIntoF ( Int32, Int32* );
862
863 extern Int32
864 BZ2_decompress ( DState* );
865
866 extern void
867 BZ2_hbCreateDecodeTables ( Int32*, Int32*, Int32*, UChar*,
868 Int32, Int32, Int32 );
869
870
871 #endif
872
873
874 /*-- BZ_NO_STDIO seems to make NULL disappear on some platforms. --*/
875
876 #ifdef BZ_NO_STDIO
877 #ifndef NULL
878 #define NULL 0
879 #endif
880 #endif
881
882
883 /*-------------------------------------------------------------*/
884 /*--- end bzlib_private.h ---*/
885 /*-------------------------------------------------------------*/
886
887
888 /* Something which has the same size as void* on the host. That is,
889 it is 32 bits on a 32-bit host and 64 bits on a 64-bit host, and so
890 it can safely be coerced to and from a pointer type on the host
891 machine. */
892 typedef unsigned long HWord;
893 typedef char HChar;
894 typedef signed int Int;
895 typedef unsigned int UInt;
896
897 typedef signed long long int Long;
898 typedef unsigned long long int ULong;
899
900
901 /////////////////////////////////////////////////////////////////////
902 /////////////////////////////////////////////////////////////////////
903
904 static HWord (*serviceFn)(HWord,HWord) = 0;
905
906 #if 0
907 static char* my_strcpy ( char* dest, const char* src )
908 {
909 char* dest_orig = dest;
910 while (*src) *dest++ = *src++;
911 *dest = 0;
912 return dest_orig;
913 }
914
915 static void* my_memcpy ( void *dest, const void *src, int sz )
916 {
917 const char *s = (const char *)src;
918 char *d = (char *)dest;
919
920 while (sz--)
921 *d++ = *s++;
922
923 return dest;
924 }
925
926 static void* my_memmove( void *dst, const void *src, unsigned int len )
927 {
928 register char *d;
929 register char *s;
930 if ( dst > src ) {
931 d = (char *)dst + len - 1;
932 s = (char *)src + len - 1;
933 while ( len >= 4 ) {
934 *d-- = *s--;
935 *d-- = *s--;
936 *d-- = *s--;
937 *d-- = *s--;
938 len -= 4;
939 }
940 while ( len-- ) {
941 *d-- = *s--;
942 }
943 } else if ( dst < src ) {
944 d = (char *)dst;
945 s = (char *)src;
946 while ( len >= 4 ) {
947 *d++ = *s++;
948 *d++ = *s++;
949 *d++ = *s++;
950 *d++ = *s++;
951 len -= 4;
952 }
953 while ( len-- ) {
954 *d++ = *s++;
955 }
956 }
957 return dst;
958 }
959 #endif
960
my_strcat(char * dest,const char * src)961 char* my_strcat ( char* dest, const char* src )
962 {
963 char* dest_orig = dest;
964 while (*dest) dest++;
965 while (*src) *dest++ = *src++;
966 *dest = 0;
967 return dest_orig;
968 }
969
970
971 /////////////////////////////////////////////////////////////////////
972
vex_log_bytes(char * p,int n)973 static void vex_log_bytes ( char* p, int n )
974 {
975 int i;
976 for (i = 0; i < n; i++)
977 (*serviceFn)( 1, (int)p[i] );
978 }
979
980 /*---------------------------------------------------------*/
981 /*--- vex_printf ---*/
982 /*---------------------------------------------------------*/
983
984 /* This should be the only <...> include in the entire VEX library.
985 New code for vex_util.c should go above this point. */
986 #include <stdarg.h>
987
vex_toupper(HChar c)988 static HChar vex_toupper ( HChar c )
989 {
990 if (c >= 'a' && c <= 'z')
991 return c + ('A' - 'a');
992 else
993 return c;
994 }
995
vex_strlen(const HChar * str)996 static Int vex_strlen ( const HChar* str )
997 {
998 Int i = 0;
999 while (str[i] != 0) i++;
1000 return i;
1001 }
1002
vex_streq(const HChar * s1,const HChar * s2)1003 Bool vex_streq ( const HChar* s1, const HChar* s2 )
1004 {
1005 while (True) {
1006 if (*s1 == 0 && *s2 == 0)
1007 return True;
1008 if (*s1 != *s2)
1009 return False;
1010 s1++;
1011 s2++;
1012 }
1013 }
1014
1015 /* Some flags. */
1016 #define VG_MSG_SIGNED 1 /* The value is signed. */
1017 #define VG_MSG_ZJUSTIFY 2 /* Must justify with '0'. */
1018 #define VG_MSG_LJUSTIFY 4 /* Must justify on the left. */
1019 #define VG_MSG_PAREN 8 /* Parenthesize if present (for %y) */
1020 #define VG_MSG_COMMA 16 /* Add commas to numbers (for %d, %u) */
1021
1022 /* Copy a string into the buffer. */
1023 static UInt
myvprintf_str(void (* send)(HChar),Int flags,Int width,HChar * str,Bool capitalise)1024 myvprintf_str ( void(*send)(HChar), Int flags, Int width, HChar* str,
1025 Bool capitalise )
1026 {
1027 # define MAYBE_TOUPPER(ch) (capitalise ? vex_toupper(ch) : (ch))
1028 UInt ret = 0;
1029 Int i, extra;
1030 Int len = vex_strlen(str);
1031
1032 if (width == 0) {
1033 ret += len;
1034 for (i = 0; i < len; i++)
1035 send(MAYBE_TOUPPER(str[i]));
1036 return ret;
1037 }
1038
1039 if (len > width) {
1040 ret += width;
1041 for (i = 0; i < width; i++)
1042 send(MAYBE_TOUPPER(str[i]));
1043 return ret;
1044 }
1045
1046 extra = width - len;
1047 if (flags & VG_MSG_LJUSTIFY) {
1048 ret += extra;
1049 for (i = 0; i < extra; i++)
1050 send(' ');
1051 }
1052 ret += len;
1053 for (i = 0; i < len; i++)
1054 send(MAYBE_TOUPPER(str[i]));
1055 if (!(flags & VG_MSG_LJUSTIFY)) {
1056 ret += extra;
1057 for (i = 0; i < extra; i++)
1058 send(' ');
1059 }
1060
1061 # undef MAYBE_TOUPPER
1062
1063 return ret;
1064 }
1065
1066 /* Write P into the buffer according to these args:
1067 * If SIGN is true, p is a signed.
1068 * BASE is the base.
1069 * If WITH_ZERO is true, '0' must be added.
1070 * WIDTH is the width of the field.
1071 */
1072 static UInt
myvprintf_int64(void (* send)(HChar),Int flags,Int base,Int width,ULong pL)1073 myvprintf_int64 ( void(*send)(HChar), Int flags, Int base, Int width, ULong pL)
1074 {
1075 HChar buf[40];
1076 Int ind = 0;
1077 Int i, nc = 0;
1078 Bool neg = False;
1079 HChar *digits = "0123456789ABCDEF";
1080 UInt ret = 0;
1081 UInt p = (UInt)pL;
1082
1083 if (base < 2 || base > 16)
1084 return ret;
1085
1086 if ((flags & VG_MSG_SIGNED) && (Int)p < 0) {
1087 p = - (Int)p;
1088 neg = True;
1089 }
1090
1091 if (p == 0)
1092 buf[ind++] = '0';
1093 else {
1094 while (p > 0) {
1095 if ((flags & VG_MSG_COMMA) && 10 == base &&
1096 0 == (ind-nc) % 3 && 0 != ind)
1097 {
1098 buf[ind++] = ',';
1099 nc++;
1100 }
1101 buf[ind++] = digits[p % base];
1102 p /= base;
1103 }
1104 }
1105
1106 if (neg)
1107 buf[ind++] = '-';
1108
1109 if (width > 0 && !(flags & VG_MSG_LJUSTIFY)) {
1110 for(; ind < width; ind++) {
1111 //vassert(ind < 39);
1112 buf[ind] = ((flags & VG_MSG_ZJUSTIFY) ? '0': ' ');
1113 }
1114 }
1115
1116 /* Reverse copy to buffer. */
1117 ret += ind;
1118 for (i = ind -1; i >= 0; i--) {
1119 send(buf[i]);
1120 }
1121 if (width > 0 && (flags & VG_MSG_LJUSTIFY)) {
1122 for(; ind < width; ind++) {
1123 ret++;
1124 send(' '); // Never pad with zeroes on RHS -- changes the value!
1125 }
1126 }
1127 return ret;
1128 }
1129
1130
1131 /* A simple vprintf(). */
1132 static
vprintf_wrk(void (* send)(HChar),const HChar * format,va_list vargs)1133 UInt vprintf_wrk ( void(*send)(HChar), const HChar *format, va_list vargs )
1134 {
1135 UInt ret = 0;
1136 int i;
1137 int flags;
1138 int width;
1139 Bool is_long;
1140
1141 /* We assume that vargs has already been initialised by the
1142 caller, using va_start, and that the caller will similarly
1143 clean up with va_end.
1144 */
1145
1146 for (i = 0; format[i] != 0; i++) {
1147 if (format[i] != '%') {
1148 send(format[i]);
1149 ret++;
1150 continue;
1151 }
1152 i++;
1153 /* A '%' has been found. Ignore a trailing %. */
1154 if (format[i] == 0)
1155 break;
1156 if (format[i] == '%') {
1157 /* `%%' is replaced by `%'. */
1158 send('%');
1159 ret++;
1160 continue;
1161 }
1162 flags = 0;
1163 is_long = False;
1164 width = 0; /* length of the field. */
1165 if (format[i] == '(') {
1166 flags |= VG_MSG_PAREN;
1167 i++;
1168 }
1169 /* If ',' follows '%', commas will be inserted. */
1170 if (format[i] == ',') {
1171 flags |= VG_MSG_COMMA;
1172 i++;
1173 }
1174 /* If '-' follows '%', justify on the left. */
1175 if (format[i] == '-') {
1176 flags |= VG_MSG_LJUSTIFY;
1177 i++;
1178 }
1179 /* If '0' follows '%', pads will be inserted. */
1180 if (format[i] == '0') {
1181 flags |= VG_MSG_ZJUSTIFY;
1182 i++;
1183 }
1184 /* Compute the field length. */
1185 while (format[i] >= '0' && format[i] <= '9') {
1186 width *= 10;
1187 width += format[i++] - '0';
1188 }
1189 while (format[i] == 'l') {
1190 i++;
1191 is_long = True;
1192 }
1193
1194 switch (format[i]) {
1195 case 'd': /* %d */
1196 flags |= VG_MSG_SIGNED;
1197 if (is_long)
1198 ret += myvprintf_int64(send, flags, 10, width,
1199 (ULong)(va_arg (vargs, Long)));
1200 else
1201 ret += myvprintf_int64(send, flags, 10, width,
1202 (ULong)(va_arg (vargs, Int)));
1203 break;
1204 case 'u': /* %u */
1205 if (is_long)
1206 ret += myvprintf_int64(send, flags, 10, width,
1207 (ULong)(va_arg (vargs, ULong)));
1208 else
1209 ret += myvprintf_int64(send, flags, 10, width,
1210 (ULong)(va_arg (vargs, UInt)));
1211 break;
1212 case 'p': /* %p */
1213 ret += 2;
1214 send('0');
1215 send('x');
1216 ret += myvprintf_int64(send, flags, 16, width,
1217 (ULong)((HWord)va_arg (vargs, void *)));
1218 break;
1219 case 'x': /* %x */
1220 if (is_long)
1221 ret += myvprintf_int64(send, flags, 16, width,
1222 (ULong)(va_arg (vargs, ULong)));
1223 else
1224 ret += myvprintf_int64(send, flags, 16, width,
1225 (ULong)(va_arg (vargs, UInt)));
1226 break;
1227 case 'c': /* %c */
1228 ret++;
1229 send((va_arg (vargs, int)));
1230 break;
1231 case 's': case 'S': { /* %s */
1232 char *str = va_arg (vargs, char *);
1233 if (str == (char*) 0) str = "(null)";
1234 ret += myvprintf_str(send, flags, width, str,
1235 (format[i]=='S'));
1236 break;
1237 }
1238 # if 0
1239 case 'y': { /* %y - print symbol */
1240 Addr a = va_arg(vargs, Addr);
1241
1242 HChar *name;
1243 if (VG_(get_fnname_w_offset)(a, &name)) {
1244 HChar buf[1 + VG_strlen(name) + 1 + 1];
1245 if (flags & VG_MSG_PAREN) {
1246 VG_(sprintf)(str, "(%s)", name):
1247 } else {
1248 VG_(sprintf)(str, "%s", name):
1249 }
1250 ret += myvprintf_str(send, flags, width, buf, 0);
1251 }
1252 break;
1253 }
1254 # endif
1255 default:
1256 break;
1257 }
1258 }
1259 return ret;
1260 }
1261
1262
1263 /* A general replacement for printf(). Note that only low-level
1264 debugging info should be sent via here. The official route is to
1265 to use vg_message(). This interface is deprecated.
1266 */
1267 static HChar myprintf_buf[1000];
1268 static Int n_myprintf_buf;
1269
add_to_myprintf_buf(HChar c)1270 static void add_to_myprintf_buf ( HChar c )
1271 {
1272 if (c == '\n' || n_myprintf_buf >= 1000-10 /*paranoia*/ ) {
1273 (*vex_log_bytes)( myprintf_buf, vex_strlen(myprintf_buf) );
1274 n_myprintf_buf = 0;
1275 myprintf_buf[n_myprintf_buf] = 0;
1276 }
1277 myprintf_buf[n_myprintf_buf++] = c;
1278 myprintf_buf[n_myprintf_buf] = 0;
1279 }
1280
vex_printf(const char * format,...)1281 static UInt vex_printf ( const char *format, ... )
1282 {
1283 UInt ret;
1284 va_list vargs;
1285 va_start(vargs,format);
1286
1287 n_myprintf_buf = 0;
1288 myprintf_buf[n_myprintf_buf] = 0;
1289 ret = vprintf_wrk ( add_to_myprintf_buf, format, vargs );
1290
1291 if (n_myprintf_buf > 0) {
1292 (*vex_log_bytes)( myprintf_buf, n_myprintf_buf );
1293 }
1294
1295 va_end(vargs);
1296
1297 return ret;
1298 }
1299
1300 /*---------------------------------------------------------------*/
1301 /*--- end vex_util.c ---*/
1302 /*---------------------------------------------------------------*/
1303
1304
1305 /////////////////////////////////////////////////////////////////////
1306 /////////////////////////////////////////////////////////////////////
1307 /////////////////////////////////////////////////////////////////////
1308 /////////////////////////////////////////////////////////////////////
1309
1310
1311 /*-------------------------------------------------------------*/
1312 /*--- Decompression machinery ---*/
1313 /*--- decompress.c ---*/
1314 /*-------------------------------------------------------------*/
1315
1316 /*--
1317 This file is a part of bzip2 and/or libbzip2, a program and
1318 library for lossless, block-sorting data compression.
1319
1320 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
1321
1322 Redistribution and use in source and binary forms, with or without
1323 modification, are permitted provided that the following conditions
1324 are met:
1325
1326 1. Redistributions of source code must retain the above copyright
1327 notice, this list of conditions and the following disclaimer.
1328
1329 2. The origin of this software must not be misrepresented; you must
1330 not claim that you wrote the original software. If you use this
1331 software in a product, an acknowledgment in the product
1332 documentation would be appreciated but is not required.
1333
1334 3. Altered source versions must be plainly marked as such, and must
1335 not be misrepresented as being the original software.
1336
1337 4. The name of the author may not be used to endorse or promote
1338 products derived from this software without specific prior written
1339 permission.
1340
1341 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
1342 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
1343 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1344 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
1345 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1346 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
1347 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1348 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
1349 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
1350 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
1351 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1352
1353 Julian Seward, Cambridge, UK.
1354 jseward@bzip.org
1355 bzip2/libbzip2 version 1.0 of 21 March 2000
1356
1357 This program is based on (at least) the work of:
1358 Mike Burrows
1359 David Wheeler
1360 Peter Fenwick
1361 Alistair Moffat
1362 Radford Neal
1363 Ian H. Witten
1364 Robert Sedgewick
1365 Jon L. Bentley
1366
1367 For more information on these sources, see the manual.
1368 --*/
1369
1370
1371
1372
1373 /*---------------------------------------------------*/
1374 static
makeMaps_d(DState * s)1375 void makeMaps_d ( DState* s )
1376 {
1377 Int32 i;
1378 s->nInUse = 0;
1379 for (i = 0; i < 256; i++)
1380 if (s->inUse[i]) {
1381 s->seqToUnseq[s->nInUse] = i;
1382 s->nInUse++;
1383 }
1384 }
1385
1386
1387 /*---------------------------------------------------*/
1388 #define RETURN(rrr) \
1389 { retVal = rrr; goto save_state_and_return; };
1390
1391 #define GET_BITS(lll,vvv,nnn) \
1392 case lll: s->state = lll; \
1393 while (True) { \
1394 if (s->bsLive >= nnn) { \
1395 UInt32 v; \
1396 v = (s->bsBuff >> \
1397 (s->bsLive-nnn)) & ((1 << nnn)-1); \
1398 s->bsLive -= nnn; \
1399 vvv = v; \
1400 break; \
1401 } \
1402 if (s->strm->avail_in == 0) RETURN(BZ_OK); \
1403 s->bsBuff \
1404 = (s->bsBuff << 8) | \
1405 ((UInt32) \
1406 (*((UChar*)(s->strm->next_in)))); \
1407 s->bsLive += 8; \
1408 s->strm->next_in++; \
1409 s->strm->avail_in--; \
1410 s->strm->total_in_lo32++; \
1411 if (s->strm->total_in_lo32 == 0) \
1412 s->strm->total_in_hi32++; \
1413 }
1414
1415 #define GET_UCHAR(lll,uuu) \
1416 GET_BITS(lll,uuu,8)
1417
1418 #define GET_BIT(lll,uuu) \
1419 GET_BITS(lll,uuu,1)
1420
1421 /*---------------------------------------------------*/
1422 #define GET_MTF_VAL(label1,label2,lval) \
1423 { \
1424 if (groupPos == 0) { \
1425 groupNo++; \
1426 if (groupNo >= nSelectors) \
1427 RETURN(BZ_DATA_ERROR); \
1428 groupPos = BZ_G_SIZE; \
1429 gSel = s->selector[groupNo]; \
1430 gMinlen = s->minLens[gSel]; \
1431 gLimit = &(s->limit[gSel][0]); \
1432 gPerm = &(s->perm[gSel][0]); \
1433 gBase = &(s->base[gSel][0]); \
1434 } \
1435 groupPos--; \
1436 zn = gMinlen; \
1437 GET_BITS(label1, zvec, zn); \
1438 while (1) { \
1439 if (zn > 20 /* the longest code */) \
1440 RETURN(BZ_DATA_ERROR); \
1441 if (zvec <= gLimit[zn]) break; \
1442 zn++; \
1443 GET_BIT(label2, zj); \
1444 zvec = (zvec << 1) | zj; \
1445 }; \
1446 if (zvec - gBase[zn] < 0 \
1447 || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \
1448 RETURN(BZ_DATA_ERROR); \
1449 lval = gPerm[zvec - gBase[zn]]; \
1450 }
1451
1452
1453
1454 /*---------------------------------------------------*/
BZ2_indexIntoF(Int32 indx,Int32 * cftab)1455 __inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab )
1456 {
1457 Int32 nb, na, mid;
1458 nb = 0;
1459 na = 256;
1460 do {
1461 mid = (nb + na) >> 1;
1462 if (indx >= cftab[mid]) nb = mid; else na = mid;
1463 }
1464 while (na - nb != 1);
1465 return nb;
1466 }
1467
1468 /*---------------------------------------------------*/
BZ2_decompress(DState * s)1469 Int32 BZ2_decompress ( DState* s )
1470 {
1471 UChar uc;
1472 Int32 retVal;
1473 Int32 minLen, maxLen;
1474 bz_stream* strm = s->strm;
1475
1476 /* stuff that needs to be saved/restored */
1477 Int32 i;
1478 Int32 j;
1479 Int32 t;
1480 Int32 alphaSize;
1481 Int32 nGroups;
1482 Int32 nSelectors;
1483 Int32 EOB;
1484 Int32 groupNo;
1485 Int32 groupPos;
1486 Int32 nextSym;
1487 Int32 nblockMAX;
1488 Int32 nblock;
1489 Int32 es;
1490 Int32 N;
1491 Int32 curr;
1492 Int32 zt;
1493 Int32 zn;
1494 Int32 zvec;
1495 Int32 zj;
1496 Int32 gSel;
1497 Int32 gMinlen;
1498 Int32* gLimit;
1499 Int32* gBase;
1500 Int32* gPerm;
1501
1502 if (s->state == BZ_X_MAGIC_1) {
1503 /*initialise the save area*/
1504 s->save_i = 0;
1505 s->save_j = 0;
1506 s->save_t = 0;
1507 s->save_alphaSize = 0;
1508 s->save_nGroups = 0;
1509 s->save_nSelectors = 0;
1510 s->save_EOB = 0;
1511 s->save_groupNo = 0;
1512 s->save_groupPos = 0;
1513 s->save_nextSym = 0;
1514 s->save_nblockMAX = 0;
1515 s->save_nblock = 0;
1516 s->save_es = 0;
1517 s->save_N = 0;
1518 s->save_curr = 0;
1519 s->save_zt = 0;
1520 s->save_zn = 0;
1521 s->save_zvec = 0;
1522 s->save_zj = 0;
1523 s->save_gSel = 0;
1524 s->save_gMinlen = 0;
1525 s->save_gLimit = NULL;
1526 s->save_gBase = NULL;
1527 s->save_gPerm = NULL;
1528 }
1529
1530 /*restore from the save area*/
1531 i = s->save_i;
1532 j = s->save_j;
1533 t = s->save_t;
1534 alphaSize = s->save_alphaSize;
1535 nGroups = s->save_nGroups;
1536 nSelectors = s->save_nSelectors;
1537 EOB = s->save_EOB;
1538 groupNo = s->save_groupNo;
1539 groupPos = s->save_groupPos;
1540 nextSym = s->save_nextSym;
1541 nblockMAX = s->save_nblockMAX;
1542 nblock = s->save_nblock;
1543 es = s->save_es;
1544 N = s->save_N;
1545 curr = s->save_curr;
1546 zt = s->save_zt;
1547 zn = s->save_zn;
1548 zvec = s->save_zvec;
1549 zj = s->save_zj;
1550 gSel = s->save_gSel;
1551 gMinlen = s->save_gMinlen;
1552 gLimit = s->save_gLimit;
1553 gBase = s->save_gBase;
1554 gPerm = s->save_gPerm;
1555
1556 retVal = BZ_OK;
1557
1558 switch (s->state) {
1559
1560 GET_UCHAR(BZ_X_MAGIC_1, uc);
1561 if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
1562
1563 GET_UCHAR(BZ_X_MAGIC_2, uc);
1564 if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
1565
1566 GET_UCHAR(BZ_X_MAGIC_3, uc)
1567 if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
1568
1569 GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
1570 if (s->blockSize100k < (BZ_HDR_0 + 1) ||
1571 s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
1572 s->blockSize100k -= BZ_HDR_0;
1573
1574 if (s->smallDecompress) {
1575 s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
1576 s->ll4 = BZALLOC(
1577 ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
1578 );
1579 if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
1580 } else {
1581 s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
1582 if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
1583 }
1584
1585 GET_UCHAR(BZ_X_BLKHDR_1, uc);
1586
1587 if (uc == 0x17) goto endhdr_2;
1588 if (uc != 0x31) RETURN(BZ_DATA_ERROR);
1589 GET_UCHAR(BZ_X_BLKHDR_2, uc);
1590 if (uc != 0x41) RETURN(BZ_DATA_ERROR);
1591 GET_UCHAR(BZ_X_BLKHDR_3, uc);
1592 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
1593 GET_UCHAR(BZ_X_BLKHDR_4, uc);
1594 if (uc != 0x26) RETURN(BZ_DATA_ERROR);
1595 GET_UCHAR(BZ_X_BLKHDR_5, uc);
1596 if (uc != 0x53) RETURN(BZ_DATA_ERROR);
1597 GET_UCHAR(BZ_X_BLKHDR_6, uc);
1598 if (uc != 0x59) RETURN(BZ_DATA_ERROR);
1599
1600 s->currBlockNo++;
1601 if (s->verbosity >= 2)
1602 VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo );
1603
1604 s->storedBlockCRC = 0;
1605 GET_UCHAR(BZ_X_BCRC_1, uc);
1606 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1607 GET_UCHAR(BZ_X_BCRC_2, uc);
1608 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1609 GET_UCHAR(BZ_X_BCRC_3, uc);
1610 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1611 GET_UCHAR(BZ_X_BCRC_4, uc);
1612 s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
1613
1614 GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
1615
1616 s->origPtr = 0;
1617 GET_UCHAR(BZ_X_ORIGPTR_1, uc);
1618 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1619 GET_UCHAR(BZ_X_ORIGPTR_2, uc);
1620 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1621 GET_UCHAR(BZ_X_ORIGPTR_3, uc);
1622 s->origPtr = (s->origPtr << 8) | ((Int32)uc);
1623
1624 if (s->origPtr < 0)
1625 RETURN(BZ_DATA_ERROR);
1626 if (s->origPtr > 10 + 100000*s->blockSize100k)
1627 RETURN(BZ_DATA_ERROR);
1628
1629 /*--- Receive the mapping table ---*/
1630 for (i = 0; i < 16; i++) {
1631 GET_BIT(BZ_X_MAPPING_1, uc);
1632 if (uc == 1)
1633 s->inUse16[i] = True; else
1634 s->inUse16[i] = False;
1635 }
1636
1637 for (i = 0; i < 256; i++) s->inUse[i] = False;
1638
1639 for (i = 0; i < 16; i++)
1640 if (s->inUse16[i])
1641 for (j = 0; j < 16; j++) {
1642 GET_BIT(BZ_X_MAPPING_2, uc);
1643 if (uc == 1) s->inUse[i * 16 + j] = True;
1644 }
1645 makeMaps_d ( s );
1646 if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
1647 alphaSize = s->nInUse+2;
1648
1649 /*--- Now the selectors ---*/
1650 GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
1651 if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
1652 GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
1653 if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
1654 for (i = 0; i < nSelectors; i++) {
1655 j = 0;
1656 while (True) {
1657 GET_BIT(BZ_X_SELECTOR_3, uc);
1658 if (uc == 0) break;
1659 j++;
1660 if (j >= nGroups) RETURN(BZ_DATA_ERROR);
1661 }
1662 s->selectorMtf[i] = j;
1663 }
1664
1665 /*--- Undo the MTF values for the selectors. ---*/
1666 {
1667 UChar pos[BZ_N_GROUPS], tmp, v;
1668 for (v = 0; v < nGroups; v++) pos[v] = v;
1669
1670 for (i = 0; i < nSelectors; i++) {
1671 v = s->selectorMtf[i];
1672 tmp = pos[v];
1673 while (v > 0) { pos[v] = pos[v-1]; v--; }
1674 pos[0] = tmp;
1675 s->selector[i] = tmp;
1676 }
1677 }
1678
1679 /*--- Now the coding tables ---*/
1680 for (t = 0; t < nGroups; t++) {
1681 GET_BITS(BZ_X_CODING_1, curr, 5);
1682 for (i = 0; i < alphaSize; i++) {
1683 while (True) {
1684 if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
1685 GET_BIT(BZ_X_CODING_2, uc);
1686 if (uc == 0) break;
1687 GET_BIT(BZ_X_CODING_3, uc);
1688 if (uc == 0) curr++; else curr--;
1689 }
1690 s->len[t][i] = curr;
1691 }
1692 }
1693
1694 /*--- Create the Huffman decoding tables ---*/
1695 for (t = 0; t < nGroups; t++) {
1696 minLen = 32;
1697 maxLen = 0;
1698 for (i = 0; i < alphaSize; i++) {
1699 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
1700 if (s->len[t][i] < minLen) minLen = s->len[t][i];
1701 }
1702 BZ2_hbCreateDecodeTables (
1703 &(s->limit[t][0]),
1704 &(s->base[t][0]),
1705 &(s->perm[t][0]),
1706 &(s->len[t][0]),
1707 minLen, maxLen, alphaSize
1708 );
1709 s->minLens[t] = minLen;
1710 }
1711
1712 /*--- Now the MTF values ---*/
1713
1714 EOB = s->nInUse+1;
1715 nblockMAX = 100000 * s->blockSize100k;
1716 groupNo = -1;
1717 groupPos = 0;
1718
1719 for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
1720
1721 /*-- MTF init --*/
1722 {
1723 Int32 ii, jj, kk;
1724 kk = MTFA_SIZE-1;
1725 for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
1726 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1727 s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
1728 kk--;
1729 }
1730 s->mtfbase[ii] = kk + 1;
1731 }
1732 }
1733 /*-- end MTF init --*/
1734
1735 nblock = 0;
1736 GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
1737
1738 while (True) {
1739
1740 if (nextSym == EOB) break;
1741
1742 if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
1743
1744 es = -1;
1745 N = 1;
1746 do {
1747 if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
1748 if (nextSym == BZ_RUNB) es = es + (1+1) * N;
1749 N = N * 2;
1750 GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
1751 }
1752 while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
1753
1754 es++;
1755 uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
1756 s->unzftab[uc] += es;
1757
1758 if (s->smallDecompress)
1759 while (es > 0) {
1760 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1761 s->ll16[nblock] = (UInt16)uc;
1762 nblock++;
1763 es--;
1764 }
1765 else
1766 while (es > 0) {
1767 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1768 s->tt[nblock] = (UInt32)uc;
1769 nblock++;
1770 es--;
1771 };
1772
1773 continue;
1774
1775 } else {
1776
1777 if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
1778
1779 /*-- uc = MTF ( nextSym-1 ) --*/
1780 {
1781 Int32 ii, jj, kk, pp, lno, off;
1782 UInt32 nn;
1783 nn = (UInt32)(nextSym - 1);
1784
1785 if (nn < MTFL_SIZE) {
1786 /* avoid general-case expense */
1787 pp = s->mtfbase[0];
1788 uc = s->mtfa[pp+nn];
1789 while (nn > 3) {
1790 Int32 z = pp+nn;
1791 s->mtfa[(z) ] = s->mtfa[(z)-1];
1792 s->mtfa[(z)-1] = s->mtfa[(z)-2];
1793 s->mtfa[(z)-2] = s->mtfa[(z)-3];
1794 s->mtfa[(z)-3] = s->mtfa[(z)-4];
1795 nn -= 4;
1796 }
1797 while (nn > 0) {
1798 s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
1799 };
1800 s->mtfa[pp] = uc;
1801 } else {
1802 /* general case */
1803 lno = nn / MTFL_SIZE;
1804 off = nn % MTFL_SIZE;
1805 pp = s->mtfbase[lno] + off;
1806 uc = s->mtfa[pp];
1807 while (pp > s->mtfbase[lno]) {
1808 s->mtfa[pp] = s->mtfa[pp-1]; pp--;
1809 };
1810 s->mtfbase[lno]++;
1811 while (lno > 0) {
1812 s->mtfbase[lno]--;
1813 s->mtfa[s->mtfbase[lno]]
1814 = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
1815 lno--;
1816 }
1817 s->mtfbase[0]--;
1818 s->mtfa[s->mtfbase[0]] = uc;
1819 if (s->mtfbase[0] == 0) {
1820 kk = MTFA_SIZE-1;
1821 for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
1822 for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
1823 s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
1824 kk--;
1825 }
1826 s->mtfbase[ii] = kk + 1;
1827 }
1828 }
1829 }
1830 }
1831 /*-- end uc = MTF ( nextSym-1 ) --*/
1832
1833 s->unzftab[s->seqToUnseq[uc]]++;
1834 if (s->smallDecompress)
1835 s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
1836 s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]);
1837 nblock++;
1838
1839 GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
1840 continue;
1841 }
1842 }
1843
1844 /* Now we know what nblock is, we can do a better sanity
1845 check on s->origPtr.
1846 */
1847 if (s->origPtr < 0 || s->origPtr >= nblock)
1848 RETURN(BZ_DATA_ERROR);
1849
1850 /*-- Set up cftab to facilitate generation of T^(-1) --*/
1851 s->cftab[0] = 0;
1852 for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
1853 for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
1854 for (i = 0; i <= 256; i++) {
1855 if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
1856 /* s->cftab[i] can legitimately be == nblock */
1857 RETURN(BZ_DATA_ERROR);
1858 }
1859 }
1860
1861 s->state_out_len = 0;
1862 s->state_out_ch = 0;
1863 BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
1864 s->state = BZ_X_OUTPUT;
1865 if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
1866
1867 if (s->smallDecompress) {
1868
1869 /*-- Make a copy of cftab, used in generation of T --*/
1870 for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
1871
1872 /*-- compute the T vector --*/
1873 for (i = 0; i < nblock; i++) {
1874 uc = (UChar)(s->ll16[i]);
1875 SET_LL(i, s->cftabCopy[uc]);
1876 s->cftabCopy[uc]++;
1877 }
1878
1879 /*-- Compute T^(-1) by pointer reversal on T --*/
1880 i = s->origPtr;
1881 j = GET_LL(i);
1882 do {
1883 Int32 tmp = GET_LL(j);
1884 SET_LL(j, i);
1885 i = j;
1886 j = tmp;
1887 }
1888 while (i != s->origPtr);
1889
1890 s->tPos = s->origPtr;
1891 s->nblock_used = 0;
1892 if (s->blockRandomised) {
1893 BZ_RAND_INIT_MASK;
1894 BZ_GET_SMALL(s->k0); s->nblock_used++;
1895 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
1896 } else {
1897 BZ_GET_SMALL(s->k0); s->nblock_used++;
1898 }
1899
1900 } else {
1901
1902 /*-- compute the T^(-1) vector --*/
1903 for (i = 0; i < nblock; i++) {
1904 uc = (UChar)(s->tt[i] & 0xff);
1905 s->tt[s->cftab[uc]] |= (i << 8);
1906 s->cftab[uc]++;
1907 }
1908
1909 s->tPos = s->tt[s->origPtr] >> 8;
1910 s->nblock_used = 0;
1911 if (s->blockRandomised) {
1912 BZ_RAND_INIT_MASK;
1913 BZ_GET_FAST(s->k0); s->nblock_used++;
1914 BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
1915 } else {
1916 BZ_GET_FAST(s->k0); s->nblock_used++;
1917 }
1918
1919 }
1920
1921 RETURN(BZ_OK);
1922
1923
1924
1925 endhdr_2:
1926
1927 GET_UCHAR(BZ_X_ENDHDR_2, uc);
1928 if (uc != 0x72) RETURN(BZ_DATA_ERROR);
1929 GET_UCHAR(BZ_X_ENDHDR_3, uc);
1930 if (uc != 0x45) RETURN(BZ_DATA_ERROR);
1931 GET_UCHAR(BZ_X_ENDHDR_4, uc);
1932 if (uc != 0x38) RETURN(BZ_DATA_ERROR);
1933 GET_UCHAR(BZ_X_ENDHDR_5, uc);
1934 if (uc != 0x50) RETURN(BZ_DATA_ERROR);
1935 GET_UCHAR(BZ_X_ENDHDR_6, uc);
1936 if (uc != 0x90) RETURN(BZ_DATA_ERROR);
1937
1938 s->storedCombinedCRC = 0;
1939 GET_UCHAR(BZ_X_CCRC_1, uc);
1940 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1941 GET_UCHAR(BZ_X_CCRC_2, uc);
1942 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1943 GET_UCHAR(BZ_X_CCRC_3, uc);
1944 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1945 GET_UCHAR(BZ_X_CCRC_4, uc);
1946 s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
1947
1948 s->state = BZ_X_IDLE;
1949 RETURN(BZ_STREAM_END);
1950
1951 default: AssertH ( False, 4001 );
1952 }
1953
1954 AssertH ( False, 4002 );
1955
1956 save_state_and_return:
1957
1958 s->save_i = i;
1959 s->save_j = j;
1960 s->save_t = t;
1961 s->save_alphaSize = alphaSize;
1962 s->save_nGroups = nGroups;
1963 s->save_nSelectors = nSelectors;
1964 s->save_EOB = EOB;
1965 s->save_groupNo = groupNo;
1966 s->save_groupPos = groupPos;
1967 s->save_nextSym = nextSym;
1968 s->save_nblockMAX = nblockMAX;
1969 s->save_nblock = nblock;
1970 s->save_es = es;
1971 s->save_N = N;
1972 s->save_curr = curr;
1973 s->save_zt = zt;
1974 s->save_zn = zn;
1975 s->save_zvec = zvec;
1976 s->save_zj = zj;
1977 s->save_gSel = gSel;
1978 s->save_gMinlen = gMinlen;
1979 s->save_gLimit = gLimit;
1980 s->save_gBase = gBase;
1981 s->save_gPerm = gPerm;
1982
1983 return retVal;
1984 }
1985
1986
1987 /*-------------------------------------------------------------*/
1988 /*--- end decompress.c ---*/
1989 /*-------------------------------------------------------------*/
1990
1991 /*-------------------------------------------------------------*/
1992 /*--- Block sorting machinery ---*/
1993 /*--- blocksort.c ---*/
1994 /*-------------------------------------------------------------*/
1995
1996 /*--
1997 This file is a part of bzip2 and/or libbzip2, a program and
1998 library for lossless, block-sorting data compression.
1999
2000 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
2001
2002 Redistribution and use in source and binary forms, with or without
2003 modification, are permitted provided that the following conditions
2004 are met:
2005
2006 1. Redistributions of source code must retain the above copyright
2007 notice, this list of conditions and the following disclaimer.
2008
2009 2. The origin of this software must not be misrepresented; you must
2010 not claim that you wrote the original software. If you use this
2011 software in a product, an acknowledgment in the product
2012 documentation would be appreciated but is not required.
2013
2014 3. Altered source versions must be plainly marked as such, and must
2015 not be misrepresented as being the original software.
2016
2017 4. The name of the author may not be used to endorse or promote
2018 products derived from this software without specific prior written
2019 permission.
2020
2021 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
2022 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
2023 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2024 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
2025 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2026 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
2027 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
2028 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
2029 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
2030 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
2031 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2032
2033 Julian Seward, Cambridge, UK.
2034 jseward@bzip.org
2035 bzip2/libbzip2 version 1.0 of 21 March 2000
2036
2037 This program is based on (at least) the work of:
2038 Mike Burrows
2039 David Wheeler
2040 Peter Fenwick
2041 Alistair Moffat
2042 Radford Neal
2043 Ian H. Witten
2044 Robert Sedgewick
2045 Jon L. Bentley
2046
2047 For more information on these sources, see the manual.
2048
2049 To get some idea how the block sorting algorithms in this file
2050 work, read my paper
2051 On the Performance of BWT Sorting Algorithms
2052 in Proceedings of the IEEE Data Compression Conference 2000,
2053 Snowbird, Utah, USA, 27-30 March 2000. The main sort in this
2054 file implements the algorithm called cache in the paper.
2055 --*/
2056
2057
2058
2059 /*---------------------------------------------*/
2060 /*--- Fallback O(N log(N)^2) sorting ---*/
2061 /*--- algorithm, for repetitive blocks ---*/
2062 /*---------------------------------------------*/
2063
2064 /*---------------------------------------------*/
2065 static
2066 __inline__
fallbackSimpleSort(UInt32 * fmap,UInt32 * eclass,Int32 lo,Int32 hi)2067 void fallbackSimpleSort ( UInt32* fmap,
2068 UInt32* eclass,
2069 Int32 lo,
2070 Int32 hi )
2071 {
2072 Int32 i, j, tmp;
2073 UInt32 ec_tmp;
2074
2075 if (lo == hi) return;
2076
2077 if (hi - lo > 3) {
2078 for ( i = hi-4; i >= lo; i-- ) {
2079 tmp = fmap[i];
2080 ec_tmp = eclass[tmp];
2081 for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 )
2082 fmap[j-4] = fmap[j];
2083 fmap[j-4] = tmp;
2084 }
2085 }
2086
2087 for ( i = hi-1; i >= lo; i-- ) {
2088 tmp = fmap[i];
2089 ec_tmp = eclass[tmp];
2090 for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ )
2091 fmap[j-1] = fmap[j];
2092 fmap[j-1] = tmp;
2093 }
2094 }
2095
2096
2097 /*---------------------------------------------*/
2098 #define fswap(zz1, zz2) \
2099 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
2100
2101 #define fvswap(zzp1, zzp2, zzn) \
2102 { \
2103 Int32 yyp1 = (zzp1); \
2104 Int32 yyp2 = (zzp2); \
2105 Int32 yyn = (zzn); \
2106 while (yyn > 0) { \
2107 fswap(fmap[yyp1], fmap[yyp2]); \
2108 yyp1++; yyp2++; yyn--; \
2109 } \
2110 }
2111
2112
2113 #define fmin(a,b) ((a) < (b)) ? (a) : (b)
2114
2115 #define fpush(lz,hz) { stackLo[sp] = lz; \
2116 stackHi[sp] = hz; \
2117 sp++; }
2118
2119 #define fpop(lz,hz) { sp--; \
2120 lz = stackLo[sp]; \
2121 hz = stackHi[sp]; }
2122
2123 #define FALLBACK_QSORT_SMALL_THRESH 10
2124 #define FALLBACK_QSORT_STACK_SIZE 100
2125
2126
2127 static
fallbackQSort3(UInt32 * fmap,UInt32 * eclass,Int32 loSt,Int32 hiSt)2128 void fallbackQSort3 ( UInt32* fmap,
2129 UInt32* eclass,
2130 Int32 loSt,
2131 Int32 hiSt )
2132 {
2133 Int32 unLo, unHi, ltLo, gtHi, n, m;
2134 Int32 sp, lo, hi;
2135 UInt32 med, r, r3;
2136 Int32 stackLo[FALLBACK_QSORT_STACK_SIZE];
2137 Int32 stackHi[FALLBACK_QSORT_STACK_SIZE];
2138
2139 r = 0;
2140
2141 sp = 0;
2142 fpush ( loSt, hiSt );
2143
2144 while (sp > 0) {
2145
2146 AssertH ( sp < FALLBACK_QSORT_STACK_SIZE, 1004 );
2147
2148 fpop ( lo, hi );
2149 if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) {
2150 fallbackSimpleSort ( fmap, eclass, lo, hi );
2151 continue;
2152 }
2153
2154 /* Random partitioning. Median of 3 sometimes fails to
2155 avoid bad cases. Median of 9 seems to help but
2156 looks rather expensive. This too seems to work but
2157 is cheaper. Guidance for the magic constants
2158 7621 and 32768 is taken from Sedgewick's algorithms
2159 book, chapter 35.
2160 */
2161 r = ((r * 7621) + 1) % 32768;
2162 r3 = r % 3;
2163 if (r3 == 0) med = eclass[fmap[lo]]; else
2164 if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else
2165 med = eclass[fmap[hi]];
2166
2167 unLo = ltLo = lo;
2168 unHi = gtHi = hi;
2169
2170 while (1) {
2171 while (1) {
2172 if (unLo > unHi) break;
2173 n = (Int32)eclass[fmap[unLo]] - (Int32)med;
2174 if (n == 0) {
2175 fswap(fmap[unLo], fmap[ltLo]);
2176 ltLo++; unLo++;
2177 continue;
2178 };
2179 if (n > 0) break;
2180 unLo++;
2181 }
2182 while (1) {
2183 if (unLo > unHi) break;
2184 n = (Int32)eclass[fmap[unHi]] - (Int32)med;
2185 if (n == 0) {
2186 fswap(fmap[unHi], fmap[gtHi]);
2187 gtHi--; unHi--;
2188 continue;
2189 };
2190 if (n < 0) break;
2191 unHi--;
2192 }
2193 if (unLo > unHi) break;
2194 fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--;
2195 }
2196
2197 AssertD ( unHi == unLo-1, "fallbackQSort3(2)" );
2198
2199 if (gtHi < ltLo) continue;
2200
2201 n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n);
2202 m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m);
2203
2204 n = lo + unLo - ltLo - 1;
2205 m = hi - (gtHi - unHi) + 1;
2206
2207 if (n - lo > hi - m) {
2208 fpush ( lo, n );
2209 fpush ( m, hi );
2210 } else {
2211 fpush ( m, hi );
2212 fpush ( lo, n );
2213 }
2214 }
2215 }
2216
2217 #undef fmin
2218 #undef fpush
2219 #undef fpop
2220 #undef fswap
2221 #undef fvswap
2222 #undef FALLBACK_QSORT_SMALL_THRESH
2223 #undef FALLBACK_QSORT_STACK_SIZE
2224
2225
2226 /*---------------------------------------------*/
2227 /* Pre:
2228 nblock > 0
2229 eclass exists for [0 .. nblock-1]
2230 ((UChar*)eclass) [0 .. nblock-1] holds block
2231 ptr exists for [0 .. nblock-1]
2232
2233 Post:
2234 ((UChar*)eclass) [0 .. nblock-1] holds block
2235 All other areas of eclass destroyed
2236 fmap [0 .. nblock-1] holds sorted order
2237 bhtab [ 0 .. 2+(nblock/32) ] destroyed
2238 */
2239
2240 #define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31))
2241 #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31))
2242 #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31)))
2243 #define WORD_BH(zz) bhtab[(zz) >> 5]
2244 #define UNALIGNED_BH(zz) ((zz) & 0x01f)
2245
2246 static
fallbackSort(UInt32 * fmap,UInt32 * eclass,UInt32 * bhtab,Int32 nblock,Int32 verb)2247 void fallbackSort ( UInt32* fmap,
2248 UInt32* eclass,
2249 UInt32* bhtab,
2250 Int32 nblock,
2251 Int32 verb )
2252 {
2253 Int32 ftab[257];
2254 Int32 ftabCopy[256];
2255 Int32 H, i, j, k, l, r, cc, cc1;
2256 Int32 nNotDone;
2257 Int32 nBhtab;
2258 UChar* eclass8 = (UChar*)eclass;
2259
2260 /*--
2261 Initial 1-char radix sort to generate
2262 initial fmap and initial BH bits.
2263 --*/
2264 if (verb >= 4)
2265 VPrintf0 ( " bucket sorting ...\n" );
2266 for (i = 0; i < 257; i++) ftab[i] = 0;
2267 for (i = 0; i < nblock; i++) ftab[eclass8[i]]++;
2268 for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i];
2269 for (i = 1; i < 257; i++) ftab[i] += ftab[i-1];
2270
2271 for (i = 0; i < nblock; i++) {
2272 j = eclass8[i];
2273 k = ftab[j] - 1;
2274 ftab[j] = k;
2275 fmap[k] = i;
2276 }
2277
2278 nBhtab = 2 + (nblock / 32);
2279 for (i = 0; i < nBhtab; i++) bhtab[i] = 0;
2280 for (i = 0; i < 256; i++) SET_BH(ftab[i]);
2281
2282 /*--
2283 Inductively refine the buckets. Kind-of an
2284 "exponential radix sort" (!), inspired by the
2285 Manber-Myers suffix array construction algorithm.
2286 --*/
2287
2288 /*-- set sentinel bits for block-end detection --*/
2289 for (i = 0; i < 32; i++) {
2290 SET_BH(nblock + 2*i);
2291 CLEAR_BH(nblock + 2*i + 1);
2292 }
2293
2294 /*-- the log(N) loop --*/
2295 H = 1;
2296 while (1) {
2297
2298 if (verb >= 4)
2299 VPrintf1 ( " depth %6d has ", H );
2300
2301 j = 0;
2302 for (i = 0; i < nblock; i++) {
2303 if (ISSET_BH(i)) j = i;
2304 k = fmap[i] - H; if (k < 0) k += nblock;
2305 eclass[k] = j;
2306 }
2307
2308 nNotDone = 0;
2309 r = -1;
2310 while (1) {
2311
2312 /*-- find the next non-singleton bucket --*/
2313 k = r + 1;
2314 while (ISSET_BH(k) && UNALIGNED_BH(k)) k++;
2315 if (ISSET_BH(k)) {
2316 while (WORD_BH(k) == 0xffffffff) k += 32;
2317 while (ISSET_BH(k)) k++;
2318 }
2319 l = k - 1;
2320 if (l >= nblock) break;
2321 while (!ISSET_BH(k) && UNALIGNED_BH(k)) k++;
2322 if (!ISSET_BH(k)) {
2323 while (WORD_BH(k) == 0x00000000) k += 32;
2324 while (!ISSET_BH(k)) k++;
2325 }
2326 r = k - 1;
2327 if (r >= nblock) break;
2328
2329 /*-- now [l, r] bracket current bucket --*/
2330 if (r > l) {
2331 nNotDone += (r - l + 1);
2332 fallbackQSort3 ( fmap, eclass, l, r );
2333
2334 /*-- scan bucket and generate header bits-- */
2335 cc = -1;
2336 for (i = l; i <= r; i++) {
2337 cc1 = eclass[fmap[i]];
2338 if (cc != cc1) { SET_BH(i); cc = cc1; };
2339 }
2340 }
2341 }
2342
2343 if (verb >= 4)
2344 VPrintf1 ( "%6d unresolved strings\n", nNotDone );
2345
2346 H *= 2;
2347 if (H > nblock || nNotDone == 0) break;
2348 }
2349
2350 /*--
2351 Reconstruct the original block in
2352 eclass8 [0 .. nblock-1], since the
2353 previous phase destroyed it.
2354 --*/
2355 if (verb >= 4)
2356 VPrintf0 ( " reconstructing block ...\n" );
2357 j = 0;
2358 for (i = 0; i < nblock; i++) {
2359 while (ftabCopy[j] == 0) j++;
2360 ftabCopy[j]--;
2361 eclass8[fmap[i]] = (UChar)j;
2362 }
2363 AssertH ( j < 256, 1005 );
2364 }
2365
2366 #undef SET_BH
2367 #undef CLEAR_BH
2368 #undef ISSET_BH
2369 #undef WORD_BH
2370 #undef UNALIGNED_BH
2371
2372
2373 /*---------------------------------------------*/
2374 /*--- The main, O(N^2 log(N)) sorting ---*/
2375 /*--- algorithm. Faster for "normal" ---*/
2376 /*--- non-repetitive blocks. ---*/
2377 /*---------------------------------------------*/
2378
2379 /*---------------------------------------------*/
2380 static
2381 __inline__
mainGtU(UInt32 i1,UInt32 i2,UChar * block,UInt16 * quadrant,UInt32 nblock,Int32 * budget)2382 Bool mainGtU ( UInt32 i1,
2383 UInt32 i2,
2384 UChar* block,
2385 UInt16* quadrant,
2386 UInt32 nblock,
2387 Int32* budget )
2388 {
2389 Int32 k;
2390 UChar c1, c2;
2391 UInt16 s1, s2;
2392
2393 AssertD ( i1 != i2, "mainGtU" );
2394 /* 1 */
2395 c1 = block[i1]; c2 = block[i2];
2396 if (c1 != c2) return (c1 > c2);
2397 i1++; i2++;
2398 /* 2 */
2399 c1 = block[i1]; c2 = block[i2];
2400 if (c1 != c2) return (c1 > c2);
2401 i1++; i2++;
2402 /* 3 */
2403 c1 = block[i1]; c2 = block[i2];
2404 if (c1 != c2) return (c1 > c2);
2405 i1++; i2++;
2406 /* 4 */
2407 c1 = block[i1]; c2 = block[i2];
2408 if (c1 != c2) return (c1 > c2);
2409 i1++; i2++;
2410 /* 5 */
2411 c1 = block[i1]; c2 = block[i2];
2412 if (c1 != c2) return (c1 > c2);
2413 i1++; i2++;
2414 /* 6 */
2415 c1 = block[i1]; c2 = block[i2];
2416 if (c1 != c2) return (c1 > c2);
2417 i1++; i2++;
2418 /* 7 */
2419 c1 = block[i1]; c2 = block[i2];
2420 if (c1 != c2) return (c1 > c2);
2421 i1++; i2++;
2422 /* 8 */
2423 c1 = block[i1]; c2 = block[i2];
2424 if (c1 != c2) return (c1 > c2);
2425 i1++; i2++;
2426 /* 9 */
2427 c1 = block[i1]; c2 = block[i2];
2428 if (c1 != c2) return (c1 > c2);
2429 i1++; i2++;
2430 /* 10 */
2431 c1 = block[i1]; c2 = block[i2];
2432 if (c1 != c2) return (c1 > c2);
2433 i1++; i2++;
2434 /* 11 */
2435 c1 = block[i1]; c2 = block[i2];
2436 if (c1 != c2) return (c1 > c2);
2437 i1++; i2++;
2438 /* 12 */
2439 c1 = block[i1]; c2 = block[i2];
2440 if (c1 != c2) return (c1 > c2);
2441 i1++; i2++;
2442
2443 k = nblock + 8;
2444
2445 do {
2446 /* 1 */
2447 c1 = block[i1]; c2 = block[i2];
2448 if (c1 != c2) return (c1 > c2);
2449 s1 = quadrant[i1]; s2 = quadrant[i2];
2450 if (s1 != s2) return (s1 > s2);
2451 i1++; i2++;
2452 /* 2 */
2453 c1 = block[i1]; c2 = block[i2];
2454 if (c1 != c2) return (c1 > c2);
2455 s1 = quadrant[i1]; s2 = quadrant[i2];
2456 if (s1 != s2) return (s1 > s2);
2457 i1++; i2++;
2458 /* 3 */
2459 c1 = block[i1]; c2 = block[i2];
2460 if (c1 != c2) return (c1 > c2);
2461 s1 = quadrant[i1]; s2 = quadrant[i2];
2462 if (s1 != s2) return (s1 > s2);
2463 i1++; i2++;
2464 /* 4 */
2465 c1 = block[i1]; c2 = block[i2];
2466 if (c1 != c2) return (c1 > c2);
2467 s1 = quadrant[i1]; s2 = quadrant[i2];
2468 if (s1 != s2) return (s1 > s2);
2469 i1++; i2++;
2470 /* 5 */
2471 c1 = block[i1]; c2 = block[i2];
2472 if (c1 != c2) return (c1 > c2);
2473 s1 = quadrant[i1]; s2 = quadrant[i2];
2474 if (s1 != s2) return (s1 > s2);
2475 i1++; i2++;
2476 /* 6 */
2477 c1 = block[i1]; c2 = block[i2];
2478 if (c1 != c2) return (c1 > c2);
2479 s1 = quadrant[i1]; s2 = quadrant[i2];
2480 if (s1 != s2) return (s1 > s2);
2481 i1++; i2++;
2482 /* 7 */
2483 c1 = block[i1]; c2 = block[i2];
2484 if (c1 != c2) return (c1 > c2);
2485 s1 = quadrant[i1]; s2 = quadrant[i2];
2486 if (s1 != s2) return (s1 > s2);
2487 i1++; i2++;
2488 /* 8 */
2489 c1 = block[i1]; c2 = block[i2];
2490 if (c1 != c2) return (c1 > c2);
2491 s1 = quadrant[i1]; s2 = quadrant[i2];
2492 if (s1 != s2) return (s1 > s2);
2493 i1++; i2++;
2494
2495 if (i1 >= nblock) i1 -= nblock;
2496 if (i2 >= nblock) i2 -= nblock;
2497
2498 k -= 8;
2499 (*budget)--;
2500 }
2501 while (k >= 0);
2502
2503 return False;
2504 }
2505
2506
2507 /*---------------------------------------------*/
2508 /*--
2509 Knuth's increments seem to work better
2510 than Incerpi-Sedgewick here. Possibly
2511 because the number of elems to sort is
2512 usually small, typically <= 20.
2513 --*/
2514 static
2515 Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
2516 9841, 29524, 88573, 265720,
2517 797161, 2391484 };
2518
2519 static
mainSimpleSort(UInt32 * ptr,UChar * block,UInt16 * quadrant,Int32 nblock,Int32 lo,Int32 hi,Int32 d,Int32 * budget)2520 void mainSimpleSort ( UInt32* ptr,
2521 UChar* block,
2522 UInt16* quadrant,
2523 Int32 nblock,
2524 Int32 lo,
2525 Int32 hi,
2526 Int32 d,
2527 Int32* budget )
2528 {
2529 Int32 i, j, h, bigN, hp;
2530 UInt32 v;
2531
2532 bigN = hi - lo + 1;
2533 if (bigN < 2) return;
2534
2535 hp = 0;
2536 while (incs[hp] < bigN) hp++;
2537 hp--;
2538
2539 for (; hp >= 0; hp--) {
2540 h = incs[hp];
2541
2542 i = lo + h;
2543 while (True) {
2544
2545 /*-- copy 1 --*/
2546 if (i > hi) break;
2547 v = ptr[i];
2548 j = i;
2549 while ( mainGtU (
2550 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
2551 ) ) {
2552 ptr[j] = ptr[j-h];
2553 j = j - h;
2554 if (j <= (lo + h - 1)) break;
2555 }
2556 ptr[j] = v;
2557 i++;
2558
2559 /*-- copy 2 --*/
2560 if (i > hi) break;
2561 v = ptr[i];
2562 j = i;
2563 while ( mainGtU (
2564 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
2565 ) ) {
2566 ptr[j] = ptr[j-h];
2567 j = j - h;
2568 if (j <= (lo + h - 1)) break;
2569 }
2570 ptr[j] = v;
2571 i++;
2572
2573 /*-- copy 3 --*/
2574 if (i > hi) break;
2575 v = ptr[i];
2576 j = i;
2577 while ( mainGtU (
2578 ptr[j-h]+d, v+d, block, quadrant, nblock, budget
2579 ) ) {
2580 ptr[j] = ptr[j-h];
2581 j = j - h;
2582 if (j <= (lo + h - 1)) break;
2583 }
2584 ptr[j] = v;
2585 i++;
2586
2587 if (*budget < 0) return;
2588 }
2589 }
2590 }
2591
2592
2593 /*---------------------------------------------*/
2594 /*--
2595 The following is an implementation of
2596 an elegant 3-way quicksort for strings,
2597 described in a paper "Fast Algorithms for
2598 Sorting and Searching Strings", by Robert
2599 Sedgewick and Jon L. Bentley.
2600 --*/
2601
2602 #define mswap(zz1, zz2) \
2603 { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; }
2604
2605 #define mvswap(zzp1, zzp2, zzn) \
2606 { \
2607 Int32 yyp1 = (zzp1); \
2608 Int32 yyp2 = (zzp2); \
2609 Int32 yyn = (zzn); \
2610 while (yyn > 0) { \
2611 mswap(ptr[yyp1], ptr[yyp2]); \
2612 yyp1++; yyp2++; yyn--; \
2613 } \
2614 }
2615
2616 static
2617 __inline__
mmed3(UChar a,UChar b,UChar c)2618 UChar mmed3 ( UChar a, UChar b, UChar c )
2619 {
2620 UChar t;
2621 if (a > b) { t = a; a = b; b = t; };
2622 if (b > c) {
2623 b = c;
2624 if (a > b) b = a;
2625 }
2626 return b;
2627 }
2628
2629 #define mmin(a,b) ((a) < (b)) ? (a) : (b)
2630
2631 #define mpush(lz,hz,dz) { stackLo[sp] = lz; \
2632 stackHi[sp] = hz; \
2633 stackD [sp] = dz; \
2634 sp++; }
2635
2636 #define mpop(lz,hz,dz) { sp--; \
2637 lz = stackLo[sp]; \
2638 hz = stackHi[sp]; \
2639 dz = stackD [sp]; }
2640
2641
2642 #define mnextsize(az) (nextHi[az]-nextLo[az])
2643
2644 #define mnextswap(az,bz) \
2645 { Int32 tz; \
2646 tz = nextLo[az]; nextLo[az] = nextLo[bz]; nextLo[bz] = tz; \
2647 tz = nextHi[az]; nextHi[az] = nextHi[bz]; nextHi[bz] = tz; \
2648 tz = nextD [az]; nextD [az] = nextD [bz]; nextD [bz] = tz; }
2649
2650
2651 #define MAIN_QSORT_SMALL_THRESH 20
2652 #define MAIN_QSORT_DEPTH_THRESH (BZ_N_RADIX + BZ_N_QSORT)
2653 #define MAIN_QSORT_STACK_SIZE 100
2654
2655 static
mainQSort3(UInt32 * ptr,UChar * block,UInt16 * quadrant,Int32 nblock,Int32 loSt,Int32 hiSt,Int32 dSt,Int32 * budget)2656 void mainQSort3 ( UInt32* ptr,
2657 UChar* block,
2658 UInt16* quadrant,
2659 Int32 nblock,
2660 Int32 loSt,
2661 Int32 hiSt,
2662 Int32 dSt,
2663 Int32* budget )
2664 {
2665 Int32 unLo, unHi, ltLo, gtHi, n, m, med;
2666 Int32 sp, lo, hi, d;
2667
2668 Int32 stackLo[MAIN_QSORT_STACK_SIZE];
2669 Int32 stackHi[MAIN_QSORT_STACK_SIZE];
2670 Int32 stackD [MAIN_QSORT_STACK_SIZE];
2671
2672 Int32 nextLo[3];
2673 Int32 nextHi[3];
2674 Int32 nextD [3];
2675
2676 sp = 0;
2677 mpush ( loSt, hiSt, dSt );
2678
2679 while (sp > 0) {
2680
2681 AssertH ( sp < MAIN_QSORT_STACK_SIZE, 1001 );
2682
2683 mpop ( lo, hi, d );
2684 if (hi - lo < MAIN_QSORT_SMALL_THRESH ||
2685 d > MAIN_QSORT_DEPTH_THRESH) {
2686 mainSimpleSort ( ptr, block, quadrant, nblock, lo, hi, d, budget );
2687 if (*budget < 0) return;
2688 continue;
2689 }
2690
2691 med = (Int32)
2692 mmed3 ( block[ptr[ lo ]+d],
2693 block[ptr[ hi ]+d],
2694 block[ptr[ (lo+hi)>>1 ]+d] );
2695
2696 unLo = ltLo = lo;
2697 unHi = gtHi = hi;
2698
2699 while (True) {
2700 while (True) {
2701 if (unLo > unHi) break;
2702 n = ((Int32)block[ptr[unLo]+d]) - med;
2703 if (n == 0) {
2704 mswap(ptr[unLo], ptr[ltLo]);
2705 ltLo++; unLo++; continue;
2706 };
2707 if (n > 0) break;
2708 unLo++;
2709 }
2710 while (True) {
2711 if (unLo > unHi) break;
2712 n = ((Int32)block[ptr[unHi]+d]) - med;
2713 if (n == 0) {
2714 mswap(ptr[unHi], ptr[gtHi]);
2715 gtHi--; unHi--; continue;
2716 };
2717 if (n < 0) break;
2718 unHi--;
2719 }
2720 if (unLo > unHi) break;
2721 mswap(ptr[unLo], ptr[unHi]); unLo++; unHi--;
2722 }
2723
2724 AssertD ( unHi == unLo-1, "mainQSort3(2)" );
2725
2726 if (gtHi < ltLo) {
2727 mpush(lo, hi, d+1 );
2728 continue;
2729 }
2730
2731 n = mmin(ltLo-lo, unLo-ltLo); mvswap(lo, unLo-n, n);
2732 m = mmin(hi-gtHi, gtHi-unHi); mvswap(unLo, hi-m+1, m);
2733
2734 n = lo + unLo - ltLo - 1;
2735 m = hi - (gtHi - unHi) + 1;
2736
2737 nextLo[0] = lo; nextHi[0] = n; nextD[0] = d;
2738 nextLo[1] = m; nextHi[1] = hi; nextD[1] = d;
2739 nextLo[2] = n+1; nextHi[2] = m-1; nextD[2] = d+1;
2740
2741 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
2742 if (mnextsize(1) < mnextsize(2)) mnextswap(1,2);
2743 if (mnextsize(0) < mnextsize(1)) mnextswap(0,1);
2744
2745 AssertD (mnextsize(0) >= mnextsize(1), "mainQSort3(8)" );
2746 AssertD (mnextsize(1) >= mnextsize(2), "mainQSort3(9)" );
2747
2748 mpush (nextLo[0], nextHi[0], nextD[0]);
2749 mpush (nextLo[1], nextHi[1], nextD[1]);
2750 mpush (nextLo[2], nextHi[2], nextD[2]);
2751 }
2752 }
2753
2754 #undef mswap
2755 #undef mvswap
2756 #undef mpush
2757 #undef mpop
2758 #undef mmin
2759 #undef mnextsize
2760 #undef mnextswap
2761 #undef MAIN_QSORT_SMALL_THRESH
2762 #undef MAIN_QSORT_DEPTH_THRESH
2763 #undef MAIN_QSORT_STACK_SIZE
2764
2765
2766 /*---------------------------------------------*/
2767 /* Pre:
2768 nblock > N_OVERSHOOT
2769 block32 exists for [0 .. nblock-1 +N_OVERSHOOT]
2770 ((UChar*)block32) [0 .. nblock-1] holds block
2771 ptr exists for [0 .. nblock-1]
2772
2773 Post:
2774 ((UChar*)block32) [0 .. nblock-1] holds block
2775 All other areas of block32 destroyed
2776 ftab [0 .. 65536 ] destroyed
2777 ptr [0 .. nblock-1] holds sorted order
2778 if (*budget < 0), sorting was abandoned
2779 */
2780
2781 #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8])
2782 #define SETMASK (1 << 21)
2783 #define CLEARMASK (~(SETMASK))
2784
2785 static
mainSort(UInt32 * ptr,UChar * block,UInt16 * quadrant,UInt32 * ftab,Int32 nblock,Int32 verb,Int32 * budget)2786 void mainSort ( UInt32* ptr,
2787 UChar* block,
2788 UInt16* quadrant,
2789 UInt32* ftab,
2790 Int32 nblock,
2791 Int32 verb,
2792 Int32* budget )
2793 {
2794 Int32 i, j, k, ss, sb;
2795 Int32 runningOrder[256];
2796 Bool bigDone[256];
2797 Int32 copyStart[256];
2798 Int32 copyEnd [256];
2799 UChar c1;
2800 Int32 numQSorted;
2801 UInt16 s;
2802 if (verb >= 4) VPrintf0 ( " main sort initialise ...\n" );
2803
2804 /*-- set up the 2-byte frequency table --*/
2805 for (i = 65536; i >= 0; i--) ftab[i] = 0;
2806
2807 j = block[0] << 8;
2808 i = nblock-1;
2809 for (; i >= 3; i -= 4) {
2810 quadrant[i] = 0;
2811 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
2812 ftab[j]++;
2813 quadrant[i-1] = 0;
2814 j = (j >> 8) | ( ((UInt16)block[i-1]) << 8);
2815 ftab[j]++;
2816 quadrant[i-2] = 0;
2817 j = (j >> 8) | ( ((UInt16)block[i-2]) << 8);
2818 ftab[j]++;
2819 quadrant[i-3] = 0;
2820 j = (j >> 8) | ( ((UInt16)block[i-3]) << 8);
2821 ftab[j]++;
2822 }
2823 for (; i >= 0; i--) {
2824 quadrant[i] = 0;
2825 j = (j >> 8) | ( ((UInt16)block[i]) << 8);
2826 ftab[j]++;
2827 }
2828
2829 /*-- (emphasises close relationship of block & quadrant) --*/
2830 for (i = 0; i < BZ_N_OVERSHOOT; i++) {
2831 block [nblock+i] = block[i];
2832 quadrant[nblock+i] = 0;
2833 }
2834
2835 if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" );
2836
2837 /*-- Complete the initial radix sort --*/
2838 for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];
2839
2840 s = block[0] << 8;
2841 i = nblock-1;
2842 for (; i >= 3; i -= 4) {
2843 s = (s >> 8) | (block[i] << 8);
2844 j = ftab[s] -1;
2845 ftab[s] = j;
2846 ptr[j] = i;
2847 s = (s >> 8) | (block[i-1] << 8);
2848 j = ftab[s] -1;
2849 ftab[s] = j;
2850 ptr[j] = i-1;
2851 s = (s >> 8) | (block[i-2] << 8);
2852 j = ftab[s] -1;
2853 ftab[s] = j;
2854 ptr[j] = i-2;
2855 s = (s >> 8) | (block[i-3] << 8);
2856 j = ftab[s] -1;
2857 ftab[s] = j;
2858 ptr[j] = i-3;
2859 }
2860 for (; i >= 0; i--) {
2861 s = (s >> 8) | (block[i] << 8);
2862 j = ftab[s] -1;
2863 ftab[s] = j;
2864 ptr[j] = i;
2865 }
2866
2867 /*--
2868 Now ftab contains the first loc of every small bucket.
2869 Calculate the running order, from smallest to largest
2870 big bucket.
2871 --*/
2872 for (i = 0; i <= 255; i++) {
2873 bigDone [i] = False;
2874 runningOrder[i] = i;
2875 }
2876
2877 {
2878 Int32 vv;
2879 Int32 h = 1;
2880 do h = 3 * h + 1; while (h <= 256);
2881 do {
2882 h = h / 3;
2883 for (i = h; i <= 255; i++) {
2884 vv = runningOrder[i];
2885 j = i;
2886 while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) {
2887 runningOrder[j] = runningOrder[j-h];
2888 j = j - h;
2889 if (j <= (h - 1)) goto zero;
2890 }
2891 zero:
2892 runningOrder[j] = vv;
2893 }
2894 } while (h != 1);
2895 }
2896
2897 /*--
2898 The main sorting loop.
2899 --*/
2900
2901 numQSorted = 0;
2902
2903 for (i = 0; i <= 255; i++) {
2904
2905 /*--
2906 Process big buckets, starting with the least full.
2907 Basically this is a 3-step process in which we call
2908 mainQSort3 to sort the small buckets [ss, j], but
2909 also make a big effort to avoid the calls if we can.
2910 --*/
2911 ss = runningOrder[i];
2912
2913 /*--
2914 Step 1:
2915 Complete the big bucket [ss] by quicksorting
2916 any unsorted small buckets [ss, j], for j != ss.
2917 Hopefully previous pointer-scanning phases have already
2918 completed many of the small buckets [ss, j], so
2919 we don't have to sort them at all.
2920 --*/
2921 for (j = 0; j <= 255; j++) {
2922 if (j != ss) {
2923 sb = (ss << 8) + j;
2924 if ( ! (ftab[sb] & SETMASK) ) {
2925 Int32 lo = ftab[sb] & CLEARMASK;
2926 Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;
2927 if (hi > lo) {
2928 if (verb >= 4)
2929 VPrintf4 ( " qsort [0x%x, 0x%x] "
2930 "done %d this %d\n",
2931 ss, j, numQSorted, hi - lo + 1 );
2932 mainQSort3 (
2933 ptr, block, quadrant, nblock,
2934 lo, hi, BZ_N_RADIX, budget
2935 );
2936 numQSorted += (hi - lo + 1);
2937 if (*budget < 0) return;
2938 }
2939 }
2940 ftab[sb] |= SETMASK;
2941 }
2942 }
2943
2944 AssertH ( !bigDone[ss], 1006 );
2945
2946 /*--
2947 Step 2:
2948 Now scan this big bucket [ss] so as to synthesise the
2949 sorted order for small buckets [t, ss] for all t,
2950 including, magically, the bucket [ss,ss] too.
2951 This will avoid doing Real Work in subsequent Step 1's.
2952 --*/
2953 {
2954 for (j = 0; j <= 255; j++) {
2955 copyStart[j] = ftab[(j << 8) + ss] & CLEARMASK;
2956 copyEnd [j] = (ftab[(j << 8) + ss + 1] & CLEARMASK) - 1;
2957 }
2958 for (j = ftab[ss << 8] & CLEARMASK; j < copyStart[ss]; j++) {
2959 k = ptr[j]-1; if (k < 0) k += nblock;
2960 c1 = block[k];
2961 if (!bigDone[c1])
2962 ptr[ copyStart[c1]++ ] = k;
2963 }
2964 for (j = (ftab[(ss+1) << 8] & CLEARMASK) - 1; j > copyEnd[ss]; j--) {
2965 k = ptr[j]-1; if (k < 0) k += nblock;
2966 c1 = block[k];
2967 if (!bigDone[c1])
2968 ptr[ copyEnd[c1]-- ] = k;
2969 }
2970 }
2971
2972 AssertH ( (copyStart[ss]-1 == copyEnd[ss])
2973 ||
2974 /* Extremely rare case missing in bzip2-1.0.0 and 1.0.1.
2975 Necessity for this case is demonstrated by compressing
2976 a sequence of approximately 48.5 million of character
2977 251; 1.0.0/1.0.1 will then die here. */
2978 (copyStart[ss] == 0 && copyEnd[ss] == nblock-1),
2979 1007 )
2980
2981 for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK;
2982
2983 /*--
2984 Step 3:
2985 The [ss] big bucket is now done. Record this fact,
2986 and update the quadrant descriptors. Remember to
2987 update quadrants in the overshoot area too, if
2988 necessary. The "if (i < 255)" test merely skips
2989 this updating for the last bucket processed, since
2990 updating for the last bucket is pointless.
2991
2992 The quadrant array provides a way to incrementally
2993 cache sort orderings, as they appear, so as to
2994 make subsequent comparisons in fullGtU() complete
2995 faster. For repetitive blocks this makes a big
2996 difference (but not big enough to be able to avoid
2997 the fallback sorting mechanism, exponential radix sort).
2998
2999 The precise meaning is: at all times:
3000
3001 for 0 <= i < nblock and 0 <= j <= nblock
3002
3003 if block[i] != block[j],
3004
3005 then the relative values of quadrant[i] and
3006 quadrant[j] are meaningless.
3007
3008 else {
3009 if quadrant[i] < quadrant[j]
3010 then the string starting at i lexicographically
3011 precedes the string starting at j
3012
3013 else if quadrant[i] > quadrant[j]
3014 then the string starting at j lexicographically
3015 precedes the string starting at i
3016
3017 else
3018 the relative ordering of the strings starting
3019 at i and j has not yet been determined.
3020 }
3021 --*/
3022 bigDone[ss] = True;
3023
3024 if (i < 255) {
3025 Int32 bbStart = ftab[ss << 8] & CLEARMASK;
3026 Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;
3027 Int32 shifts = 0;
3028
3029 while ((bbSize >> shifts) > 65534) shifts++;
3030
3031 for (j = bbSize-1; j >= 0; j--) {
3032 Int32 a2update = ptr[bbStart + j];
3033 UInt16 qVal = (UInt16)(j >> shifts);
3034 quadrant[a2update] = qVal;
3035 if (a2update < BZ_N_OVERSHOOT)
3036 quadrant[a2update + nblock] = qVal;
3037 }
3038 AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
3039 }
3040
3041 }
3042
3043 if (verb >= 4)
3044 VPrintf3 ( " %d pointers, %d sorted, %d scanned\n",
3045 nblock, numQSorted, nblock - numQSorted );
3046 }
3047
3048 #undef BIGFREQ
3049 #undef SETMASK
3050 #undef CLEARMASK
3051
3052
3053 /*---------------------------------------------*/
3054 /* Pre:
3055 nblock > 0
3056 arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
3057 ((UChar*)arr2) [0 .. nblock-1] holds block
3058 arr1 exists for [0 .. nblock-1]
3059
3060 Post:
3061 ((UChar*)arr2) [0 .. nblock-1] holds block
3062 All other areas of block destroyed
3063 ftab [ 0 .. 65536 ] destroyed
3064 arr1 [0 .. nblock-1] holds sorted order
3065 */
BZ2_blockSort(EState * s)3066 void BZ2_blockSort ( EState* s )
3067 {
3068 UInt32* ptr = s->ptr;
3069 UChar* block = s->block;
3070 UInt32* ftab = s->ftab;
3071 Int32 nblock = s->nblock;
3072 Int32 verb = s->verbosity;
3073 Int32 wfact = s->workFactor;
3074 UInt16* quadrant;
3075 Int32 budget;
3076 Int32 budgetInit;
3077 Int32 i;
3078
3079 if (nblock < /* 10000 */1000 ) {
3080 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
3081 } else {
3082 /* Calculate the location for quadrant, remembering to get
3083 the alignment right. Assumes that &(block[0]) is at least
3084 2-byte aligned -- this should be ok since block is really
3085 the first section of arr2.
3086 */
3087 i = nblock+BZ_N_OVERSHOOT;
3088 if (i & 1) i++;
3089 quadrant = (UInt16*)(&(block[i]));
3090
3091 /* (wfact-1) / 3 puts the default-factor-30
3092 transition point at very roughly the same place as
3093 with v0.1 and v0.9.0.
3094 Not that it particularly matters any more, since the
3095 resulting compressed stream is now the same regardless
3096 of whether or not we use the main sort or fallback sort.
3097 */
3098 if (wfact < 1 ) wfact = 1;
3099 if (wfact > 100) wfact = 100;
3100 budgetInit = nblock * ((wfact-1) / 3);
3101 budget = budgetInit;
3102
3103 mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
3104 if (0 && verb >= 3)
3105 VPrintf3 ( " %d work, %d block, ratio %5.2f\n",
3106 budgetInit - budget,
3107 nblock,
3108 (float)(budgetInit - budget) /
3109 (float)(nblock==0 ? 1 : nblock) );
3110 if (budget < 0) {
3111 if (verb >= 2)
3112 VPrintf0 ( " too repetitive; using fallback"
3113 " sorting algorithm\n" );
3114 fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
3115 }
3116 }
3117
3118 s->origPtr = -1;
3119 for (i = 0; i < s->nblock; i++)
3120 if (ptr[i] == 0)
3121 { s->origPtr = i; break; };
3122
3123 AssertH( s->origPtr != -1, 1003 );
3124 }
3125
3126
3127 /*-------------------------------------------------------------*/
3128 /*--- end blocksort.c ---*/
3129 /*-------------------------------------------------------------*/
3130
3131 /*-------------------------------------------------------------*/
3132 /*--- Huffman coding low-level stuff ---*/
3133 /*--- huffman.c ---*/
3134 /*-------------------------------------------------------------*/
3135
3136 /*--
3137 This file is a part of bzip2 and/or libbzip2, a program and
3138 library for lossless, block-sorting data compression.
3139
3140 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
3141
3142 Redistribution and use in source and binary forms, with or without
3143 modification, are permitted provided that the following conditions
3144 are met:
3145
3146 1. Redistributions of source code must retain the above copyright
3147 notice, this list of conditions and the following disclaimer.
3148
3149 2. The origin of this software must not be misrepresented; you must
3150 not claim that you wrote the original software. If you use this
3151 software in a product, an acknowledgment in the product
3152 documentation would be appreciated but is not required.
3153
3154 3. Altered source versions must be plainly marked as such, and must
3155 not be misrepresented as being the original software.
3156
3157 4. The name of the author may not be used to endorse or promote
3158 products derived from this software without specific prior written
3159 permission.
3160
3161 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
3162 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
3163 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
3164 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
3165 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
3166 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
3167 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
3168 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
3169 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
3170 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
3171 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3172
3173 Julian Seward, Cambridge, UK.
3174 jseward@bzip.org
3175 bzip2/libbzip2 version 1.0 of 21 March 2000
3176
3177 This program is based on (at least) the work of:
3178 Mike Burrows
3179 David Wheeler
3180 Peter Fenwick
3181 Alistair Moffat
3182 Radford Neal
3183 Ian H. Witten
3184 Robert Sedgewick
3185 Jon L. Bentley
3186
3187 For more information on these sources, see the manual.
3188 --*/
3189
3190
3191
3192 /*---------------------------------------------------*/
3193 #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
3194 #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
3195 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
3196
3197 #define ADDWEIGHTS(zw1,zw2) \
3198 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
3199 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
3200
3201 #define UPHEAP(z) \
3202 { \
3203 Int32 zz, tmp; \
3204 zz = z; tmp = heap[zz]; \
3205 while (weight[tmp] < weight[heap[zz >> 1]]) { \
3206 heap[zz] = heap[zz >> 1]; \
3207 zz >>= 1; \
3208 } \
3209 heap[zz] = tmp; \
3210 }
3211
3212 #define DOWNHEAP(z) \
3213 { \
3214 Int32 zz, yy, tmp; \
3215 zz = z; tmp = heap[zz]; \
3216 while (True) { \
3217 yy = zz << 1; \
3218 if (yy > nHeap) break; \
3219 if (yy < nHeap && \
3220 weight[heap[yy+1]] < weight[heap[yy]]) \
3221 yy++; \
3222 if (weight[tmp] < weight[heap[yy]]) break; \
3223 heap[zz] = heap[yy]; \
3224 zz = yy; \
3225 } \
3226 heap[zz] = tmp; \
3227 }
3228
3229
3230 /*---------------------------------------------------*/
BZ2_hbMakeCodeLengths(UChar * len,Int32 * freq,Int32 alphaSize,Int32 maxLen)3231 void BZ2_hbMakeCodeLengths ( UChar *len,
3232 Int32 *freq,
3233 Int32 alphaSize,
3234 Int32 maxLen )
3235 {
3236 /*--
3237 Nodes and heap entries run from 1. Entry 0
3238 for both the heap and nodes is a sentinel.
3239 --*/
3240 Int32 nNodes, nHeap, n1, n2, i, j, k;
3241 Bool tooLong;
3242
3243 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
3244 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
3245 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
3246
3247 for (i = 0; i < alphaSize; i++)
3248 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
3249
3250 while (True) {
3251
3252 nNodes = alphaSize;
3253 nHeap = 0;
3254
3255 heap[0] = 0;
3256 weight[0] = 0;
3257 parent[0] = -2;
3258
3259 for (i = 1; i <= alphaSize; i++) {
3260 parent[i] = -1;
3261 nHeap++;
3262 heap[nHeap] = i;
3263 UPHEAP(nHeap);
3264 }
3265
3266 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
3267
3268 while (nHeap > 1) {
3269 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
3270 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
3271 nNodes++;
3272 parent[n1] = parent[n2] = nNodes;
3273 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
3274 parent[nNodes] = -1;
3275 nHeap++;
3276 heap[nHeap] = nNodes;
3277 UPHEAP(nHeap);
3278 }
3279
3280 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
3281
3282 tooLong = False;
3283 for (i = 1; i <= alphaSize; i++) {
3284 j = 0;
3285 k = i;
3286 while (parent[k] >= 0) { k = parent[k]; j++; }
3287 len[i-1] = j;
3288 if (j > maxLen) tooLong = True;
3289 }
3290
3291 if (! tooLong) break;
3292
3293 /* 17 Oct 04: keep-going condition for the following loop used
3294 to be 'i < alphaSize', which missed the last element,
3295 theoretically leading to the possibility of the compressor
3296 looping. However, this count-scaling step is only needed if
3297 one of the generated Huffman code words is longer than
3298 maxLen, which up to and including version 1.0.2 was 20 bits,
3299 which is extremely unlikely. In version 1.0.3 maxLen was
3300 changed to 17 bits, which has minimal effect on compression
3301 ratio, but does mean this scaling step is used from time to
3302 time, enough to verify that it works.
3303
3304 This means that bzip2-1.0.3 and later will only produce
3305 Huffman codes with a maximum length of 17 bits. However, in
3306 order to preserve backwards compatibility with bitstreams
3307 produced by versions pre-1.0.3, the decompressor must still
3308 handle lengths of up to 20. */
3309
3310 for (i = 1; i <= alphaSize; i++) {
3311 j = weight[i] >> 8;
3312 j = 1 + (j / 2);
3313 weight[i] = j << 8;
3314 }
3315 }
3316 }
3317
3318
3319 /*---------------------------------------------------*/
BZ2_hbAssignCodes(Int32 * code,UChar * length,Int32 minLen,Int32 maxLen,Int32 alphaSize)3320 void BZ2_hbAssignCodes ( Int32 *code,
3321 UChar *length,
3322 Int32 minLen,
3323 Int32 maxLen,
3324 Int32 alphaSize )
3325 {
3326 Int32 n, vec, i;
3327
3328 vec = 0;
3329 for (n = minLen; n <= maxLen; n++) {
3330 for (i = 0; i < alphaSize; i++)
3331 if (length[i] == n) { code[i] = vec; vec++; };
3332 vec <<= 1;
3333 }
3334 }
3335
3336
3337 /*---------------------------------------------------*/
BZ2_hbCreateDecodeTables(Int32 * limit,Int32 * base,Int32 * perm,UChar * length,Int32 minLen,Int32 maxLen,Int32 alphaSize)3338 void BZ2_hbCreateDecodeTables ( Int32 *limit,
3339 Int32 *base,
3340 Int32 *perm,
3341 UChar *length,
3342 Int32 minLen,
3343 Int32 maxLen,
3344 Int32 alphaSize )
3345 {
3346 Int32 pp, i, j, vec;
3347
3348 pp = 0;
3349 for (i = minLen; i <= maxLen; i++)
3350 for (j = 0; j < alphaSize; j++)
3351 if (length[j] == i) { perm[pp] = j; pp++; };
3352
3353 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
3354 for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
3355
3356 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
3357
3358 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
3359 vec = 0;
3360
3361 for (i = minLen; i <= maxLen; i++) {
3362 vec += (base[i+1] - base[i]);
3363 limit[i] = vec-1;
3364 vec <<= 1;
3365 }
3366 for (i = minLen + 1; i <= maxLen; i++)
3367 base[i] = ((limit[i-1] + 1) << 1) - base[i];
3368 }
3369
3370
3371 /*-------------------------------------------------------------*/
3372 /*--- end huffman.c ---*/
3373 /*-------------------------------------------------------------*/
3374
3375 /*-------------------------------------------------------------*/
3376 /*--- Compression machinery (not incl block sorting) ---*/
3377 /*--- compress.c ---*/
3378 /*-------------------------------------------------------------*/
3379
3380 /*--
3381 This file is a part of bzip2 and/or libbzip2, a program and
3382 library for lossless, block-sorting data compression.
3383
3384 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
3385
3386 Redistribution and use in source and binary forms, with or without
3387 modification, are permitted provided that the following conditions
3388 are met:
3389
3390 1. Redistributions of source code must retain the above copyright
3391 notice, this list of conditions and the following disclaimer.
3392
3393 2. The origin of this software must not be misrepresented; you must
3394 not claim that you wrote the original software. If you use this
3395 software in a product, an acknowledgment in the product
3396 documentation would be appreciated but is not required.
3397
3398 3. Altered source versions must be plainly marked as such, and must
3399 not be misrepresented as being the original software.
3400
3401 4. The name of the author may not be used to endorse or promote
3402 products derived from this software without specific prior written
3403 permission.
3404
3405 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
3406 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
3407 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
3408 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
3409 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
3410 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
3411 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
3412 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
3413 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
3414 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
3415 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3416
3417 Julian Seward, Cambridge, UK.
3418 jseward@bzip.org
3419 bzip2/libbzip2 version 1.0 of 21 March 2000
3420
3421 This program is based on (at least) the work of:
3422 Mike Burrows
3423 David Wheeler
3424 Peter Fenwick
3425 Alistair Moffat
3426 Radford Neal
3427 Ian H. Witten
3428 Robert Sedgewick
3429 Jon L. Bentley
3430
3431 For more information on these sources, see the manual.
3432 --*/
3433
3434 /*--
3435 CHANGES
3436 ~~~~~~~
3437 0.9.0 -- original version.
3438
3439 0.9.0a/b -- no changes in this file.
3440
3441 0.9.0c
3442 * changed setting of nGroups in sendMTFValues() so as to
3443 do a bit better on small files
3444 --*/
3445
3446
3447
3448 /*---------------------------------------------------*/
3449 /*--- Bit stream I/O ---*/
3450 /*---------------------------------------------------*/
3451
3452 /*---------------------------------------------------*/
BZ2_bsInitWrite(EState * s)3453 void BZ2_bsInitWrite ( EState* s )
3454 {
3455 s->bsLive = 0;
3456 s->bsBuff = 0;
3457 }
3458
3459
3460 /*---------------------------------------------------*/
3461 static
bsFinishWrite(EState * s)3462 void bsFinishWrite ( EState* s )
3463 {
3464 while (s->bsLive > 0) {
3465 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
3466 s->numZ++;
3467 s->bsBuff <<= 8;
3468 s->bsLive -= 8;
3469 }
3470 }
3471
3472
3473 /*---------------------------------------------------*/
3474 #define bsNEEDW(nz) \
3475 { \
3476 while (s->bsLive >= 8) { \
3477 s->zbits[s->numZ] \
3478 = (UChar)(s->bsBuff >> 24); \
3479 s->numZ++; \
3480 s->bsBuff <<= 8; \
3481 s->bsLive -= 8; \
3482 } \
3483 }
3484
3485
3486 /*---------------------------------------------------*/
3487 static
3488 __inline__
bsW(EState * s,Int32 n,UInt32 v)3489 void bsW ( EState* s, Int32 n, UInt32 v )
3490 {
3491 bsNEEDW ( n );
3492 s->bsBuff |= (v << (32 - s->bsLive - n));
3493 s->bsLive += n;
3494 }
3495
3496
3497 /*---------------------------------------------------*/
3498 static
bsPutUInt32(EState * s,UInt32 u)3499 void bsPutUInt32 ( EState* s, UInt32 u )
3500 {
3501 bsW ( s, 8, (u >> 24) & 0xffL );
3502 bsW ( s, 8, (u >> 16) & 0xffL );
3503 bsW ( s, 8, (u >> 8) & 0xffL );
3504 bsW ( s, 8, u & 0xffL );
3505 }
3506
3507
3508 /*---------------------------------------------------*/
3509 static
bsPutUChar(EState * s,UChar c)3510 void bsPutUChar ( EState* s, UChar c )
3511 {
3512 bsW( s, 8, (UInt32)c );
3513 }
3514
3515
3516 /*---------------------------------------------------*/
3517 /*--- The back end proper ---*/
3518 /*---------------------------------------------------*/
3519
3520 /*---------------------------------------------------*/
3521 static
makeMaps_e(EState * s)3522 void makeMaps_e ( EState* s )
3523 {
3524 Int32 i;
3525 s->nInUse = 0;
3526 for (i = 0; i < 256; i++)
3527 if (s->inUse[i]) {
3528 s->unseqToSeq[i] = s->nInUse;
3529 s->nInUse++;
3530 }
3531 }
3532
3533
3534 /*---------------------------------------------------*/
3535 static
generateMTFValues(EState * s)3536 void generateMTFValues ( EState* s )
3537 {
3538 UChar yy[256];
3539 Int32 i, j;
3540 Int32 zPend;
3541 Int32 wr;
3542 Int32 EOB;
3543
3544 /*
3545 After sorting (eg, here),
3546 s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
3547 and
3548 ((UChar*)s->arr2) [ 0 .. s->nblock-1 ]
3549 holds the original block data.
3550
3551 The first thing to do is generate the MTF values,
3552 and put them in
3553 ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
3554 Because there are strictly fewer or equal MTF values
3555 than block values, ptr values in this area are overwritten
3556 with MTF values only when they are no longer needed.
3557
3558 The final compressed bitstream is generated into the
3559 area starting at
3560 (UChar*) (&((UChar*)s->arr2)[s->nblock])
3561
3562 These storage aliases are set up in bzCompressInit(),
3563 except for the last one, which is arranged in
3564 compressBlock().
3565 */
3566 UInt32* ptr = s->ptr;
3567 UChar* block = s->block;
3568 UInt16* mtfv = s->mtfv;
3569
3570 makeMaps_e ( s );
3571 EOB = s->nInUse+1;
3572
3573 for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
3574
3575 wr = 0;
3576 zPend = 0;
3577 for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
3578
3579 for (i = 0; i < s->nblock; i++) {
3580 UChar ll_i;
3581 AssertD ( wr <= i, "generateMTFValues(1)" );
3582 j = ptr[i]-1; if (j < 0) j += s->nblock;
3583 ll_i = s->unseqToSeq[block[j]];
3584 AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
3585
3586 if (yy[0] == ll_i) {
3587 zPend++;
3588 } else {
3589
3590 if (zPend > 0) {
3591 zPend--;
3592 while (True) {
3593 if (zPend & 1) {
3594 mtfv[wr] = BZ_RUNB; wr++;
3595 s->mtfFreq[BZ_RUNB]++;
3596 } else {
3597 mtfv[wr] = BZ_RUNA; wr++;
3598 s->mtfFreq[BZ_RUNA]++;
3599 }
3600 if (zPend < 2) break;
3601 zPend = (zPend - 2) / 2;
3602 };
3603 zPend = 0;
3604 }
3605 {
3606 register UChar rtmp;
3607 register UChar* ryy_j;
3608 register UChar rll_i;
3609 rtmp = yy[1];
3610 yy[1] = yy[0];
3611 ryy_j = &(yy[1]);
3612 rll_i = ll_i;
3613 while ( rll_i != rtmp ) {
3614 register UChar rtmp2;
3615 ryy_j++;
3616 rtmp2 = rtmp;
3617 rtmp = *ryy_j;
3618 *ryy_j = rtmp2;
3619 };
3620 yy[0] = rtmp;
3621 j = ryy_j - &(yy[0]);
3622 mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
3623 }
3624
3625 }
3626 }
3627
3628 if (zPend > 0) {
3629 zPend--;
3630 while (True) {
3631 if (zPend & 1) {
3632 mtfv[wr] = BZ_RUNB; wr++;
3633 s->mtfFreq[BZ_RUNB]++;
3634 } else {
3635 mtfv[wr] = BZ_RUNA; wr++;
3636 s->mtfFreq[BZ_RUNA]++;
3637 }
3638 if (zPend < 2) break;
3639 zPend = (zPend - 2) / 2;
3640 };
3641 zPend = 0;
3642 }
3643
3644 mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
3645
3646 s->nMTF = wr;
3647 }
3648
3649
3650 /*---------------------------------------------------*/
3651 #define BZ_LESSER_ICOST 0
3652 #define BZ_GREATER_ICOST 15
3653
3654 static
sendMTFValues(EState * s)3655 void sendMTFValues ( EState* s )
3656 {
3657 Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
3658 Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
3659 Int32 nGroups, nBytes;
3660
3661 /*--
3662 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
3663 is a global since the decoder also needs it.
3664
3665 Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
3666 Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
3667 are also globals only used in this proc.
3668 Made global to keep stack frame size small.
3669 --*/
3670
3671
3672 UInt16 cost[BZ_N_GROUPS];
3673 Int32 fave[BZ_N_GROUPS];
3674
3675 UInt16* mtfv = s->mtfv;
3676
3677 if (s->verbosity >= 3)
3678 VPrintf3( " %d in block, %d after MTF & 1-2 coding, "
3679 "%d+2 syms in use\n",
3680 s->nblock, s->nMTF, s->nInUse );
3681
3682 alphaSize = s->nInUse+2;
3683 for (t = 0; t < BZ_N_GROUPS; t++)
3684 for (v = 0; v < alphaSize; v++)
3685 s->len[t][v] = BZ_GREATER_ICOST;
3686
3687 /*--- Decide how many coding tables to use ---*/
3688 AssertH ( s->nMTF > 0, 3001 );
3689 if (s->nMTF < 200) nGroups = 2; else
3690 if (s->nMTF < 600) nGroups = 3; else
3691 if (s->nMTF < 1200) nGroups = 4; else
3692 if (s->nMTF < 2400) nGroups = 5; else
3693 nGroups = 6;
3694
3695 /*--- Generate an initial set of coding tables ---*/
3696 {
3697 Int32 nPart, remF, tFreq, aFreq;
3698
3699 nPart = nGroups;
3700 remF = s->nMTF;
3701 gs = 0;
3702 while (nPart > 0) {
3703 tFreq = remF / nPart;
3704 ge = gs-1;
3705 aFreq = 0;
3706 while (aFreq < tFreq && ge < alphaSize-1) {
3707 ge++;
3708 aFreq += s->mtfFreq[ge];
3709 }
3710
3711 if (ge > gs
3712 && nPart != nGroups && nPart != 1
3713 && ((nGroups-nPart) % 2 == 1)) {
3714 aFreq -= s->mtfFreq[ge];
3715 ge--;
3716 }
3717
3718 if (0 && s->verbosity >= 3)
3719 VPrintf5( " initial group %d, [%d .. %d], "
3720 "has %d syms (%4.1f%%)\n",
3721 nPart, gs, ge, aFreq,
3722 (100.0 * (float)aFreq) / (float)(s->nMTF) );
3723
3724 for (v = 0; v < alphaSize; v++)
3725 if (v >= gs && v <= ge)
3726 s->len[nPart-1][v] = BZ_LESSER_ICOST; else
3727 s->len[nPart-1][v] = BZ_GREATER_ICOST;
3728
3729 nPart--;
3730 gs = ge+1;
3731 remF -= aFreq;
3732 }
3733 }
3734
3735 /*---
3736 Iterate up to BZ_N_ITERS times to improve the tables.
3737 ---*/
3738 for (iter = 0; iter < BZ_N_ITERS; iter++) {
3739
3740 for (t = 0; t < nGroups; t++) fave[t] = 0;
3741
3742 for (t = 0; t < nGroups; t++)
3743 for (v = 0; v < alphaSize; v++)
3744 s->rfreq[t][v] = 0;
3745
3746 /*---
3747 Set up an auxiliary length table which is used to fast-track
3748 the common case (nGroups == 6).
3749 ---*/
3750 if (nGroups == 6) {
3751 for (v = 0; v < alphaSize; v++) {
3752 s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
3753 s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
3754 s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
3755 }
3756 }
3757
3758 nSelectors = 0;
3759 totc = 0;
3760 gs = 0;
3761 while (True) {
3762
3763 /*--- Set group start & end marks. --*/
3764 if (gs >= s->nMTF) break;
3765 ge = gs + BZ_G_SIZE - 1;
3766 if (ge >= s->nMTF) ge = s->nMTF-1;
3767
3768 /*--
3769 Calculate the cost of this group as coded
3770 by each of the coding tables.
3771 --*/
3772 for (t = 0; t < nGroups; t++) cost[t] = 0;
3773
3774 if (nGroups == 6 && 50 == ge-gs+1) {
3775 /*--- fast track the common case ---*/
3776 register UInt32 cost01, cost23, cost45;
3777 register UInt16 icv;
3778 cost01 = cost23 = cost45 = 0;
3779
3780 # define BZ_ITER(nn) \
3781 icv = mtfv[gs+(nn)]; \
3782 cost01 += s->len_pack[icv][0]; \
3783 cost23 += s->len_pack[icv][1]; \
3784 cost45 += s->len_pack[icv][2]; \
3785
3786 BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4);
3787 BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9);
3788 BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
3789 BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
3790 BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
3791 BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
3792 BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
3793 BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
3794 BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
3795 BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
3796
3797 # undef BZ_ITER
3798
3799 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
3800 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
3801 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
3802
3803 } else {
3804 /*--- slow version which correctly handles all situations ---*/
3805 for (i = gs; i <= ge; i++) {
3806 UInt16 icv = mtfv[i];
3807 for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
3808 }
3809 }
3810
3811 /*--
3812 Find the coding table which is best for this group,
3813 and record its identity in the selector table.
3814 --*/
3815 bc = 999999999; bt = -1;
3816 for (t = 0; t < nGroups; t++)
3817 if (cost[t] < bc) { bc = cost[t]; bt = t; };
3818 totc += bc;
3819 fave[bt]++;
3820 s->selector[nSelectors] = bt;
3821 nSelectors++;
3822
3823 /*--
3824 Increment the symbol frequencies for the selected table.
3825 --*/
3826 if (nGroups == 6 && 50 == ge-gs+1) {
3827 /*--- fast track the common case ---*/
3828
3829 # define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
3830
3831 BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4);
3832 BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9);
3833 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
3834 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
3835 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
3836 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
3837 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
3838 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
3839 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
3840 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
3841
3842 # undef BZ_ITUR
3843
3844 } else {
3845 /*--- slow version which correctly handles all situations ---*/
3846 for (i = gs; i <= ge; i++)
3847 s->rfreq[bt][ mtfv[i] ]++;
3848 }
3849
3850 gs = ge+1;
3851 }
3852 if (s->verbosity >= 3) {
3853 VPrintf2 ( " pass %d: size is %d, grp uses are ",
3854 iter+1, totc/8 );
3855 for (t = 0; t < nGroups; t++)
3856 VPrintf1 ( "%d ", fave[t] );
3857 VPrintf0 ( "\n" );
3858 }
3859
3860 /*--
3861 Recompute the tables based on the accumulated frequencies.
3862 --*/
3863 /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See
3864 comment in huffman.c for details. */
3865 for (t = 0; t < nGroups; t++)
3866 BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
3867 alphaSize, 17 /*20*/ );
3868 }
3869
3870
3871 AssertH( nGroups < 8, 3002 );
3872 AssertH( nSelectors < 32768 &&
3873 nSelectors <= (2 + (900000 / BZ_G_SIZE)),
3874 3003 );
3875
3876
3877 /*--- Compute MTF values for the selectors. ---*/
3878 {
3879 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
3880 for (i = 0; i < nGroups; i++) pos[i] = i;
3881 for (i = 0; i < nSelectors; i++) {
3882 ll_i = s->selector[i];
3883 j = 0;
3884 tmp = pos[j];
3885 while ( ll_i != tmp ) {
3886 j++;
3887 tmp2 = tmp;
3888 tmp = pos[j];
3889 pos[j] = tmp2;
3890 };
3891 pos[0] = tmp;
3892 s->selectorMtf[i] = j;
3893 }
3894 };
3895
3896 /*--- Assign actual codes for the tables. --*/
3897 for (t = 0; t < nGroups; t++) {
3898 minLen = 32;
3899 maxLen = 0;
3900 for (i = 0; i < alphaSize; i++) {
3901 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
3902 if (s->len[t][i] < minLen) minLen = s->len[t][i];
3903 }
3904 AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
3905 AssertH ( !(minLen < 1), 3005 );
3906 BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
3907 minLen, maxLen, alphaSize );
3908 }
3909
3910 /*--- Transmit the mapping table. ---*/
3911 {
3912 Bool inUse16[16];
3913 for (i = 0; i < 16; i++) {
3914 inUse16[i] = False;
3915 for (j = 0; j < 16; j++)
3916 if (s->inUse[i * 16 + j]) inUse16[i] = True;
3917 }
3918
3919 nBytes = s->numZ;
3920 for (i = 0; i < 16; i++)
3921 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
3922
3923 for (i = 0; i < 16; i++)
3924 if (inUse16[i])
3925 for (j = 0; j < 16; j++) {
3926 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
3927 }
3928
3929 if (s->verbosity >= 3)
3930 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes );
3931 }
3932
3933 /*--- Now the selectors. ---*/
3934 nBytes = s->numZ;
3935 bsW ( s, 3, nGroups );
3936 bsW ( s, 15, nSelectors );
3937 for (i = 0; i < nSelectors; i++) {
3938 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
3939 bsW(s,1,0);
3940 }
3941 if (s->verbosity >= 3)
3942 VPrintf1( "selectors %d, ", s->numZ-nBytes );
3943
3944 /*--- Now the coding tables. ---*/
3945 nBytes = s->numZ;
3946
3947 for (t = 0; t < nGroups; t++) {
3948 Int32 curr = s->len[t][0];
3949 bsW ( s, 5, curr );
3950 for (i = 0; i < alphaSize; i++) {
3951 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
3952 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
3953 bsW ( s, 1, 0 );
3954 }
3955 }
3956
3957 if (s->verbosity >= 3)
3958 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
3959
3960 /*--- And finally, the block data proper ---*/
3961 nBytes = s->numZ;
3962 selCtr = 0;
3963 gs = 0;
3964 while (True) {
3965 if (gs >= s->nMTF) break;
3966 ge = gs + BZ_G_SIZE - 1;
3967 if (ge >= s->nMTF) ge = s->nMTF-1;
3968 AssertH ( s->selector[selCtr] < nGroups, 3006 );
3969
3970 if (nGroups == 6 && 50 == ge-gs+1) {
3971 /*--- fast track the common case ---*/
3972 UInt16 mtfv_i;
3973 UChar* s_len_sel_selCtr
3974 = &(s->len[s->selector[selCtr]][0]);
3975 Int32* s_code_sel_selCtr
3976 = &(s->code[s->selector[selCtr]][0]);
3977
3978 # define BZ_ITAH(nn) \
3979 mtfv_i = mtfv[gs+(nn)]; \
3980 bsW ( s, \
3981 s_len_sel_selCtr[mtfv_i], \
3982 s_code_sel_selCtr[mtfv_i] )
3983
3984 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4);
3985 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9);
3986 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
3987 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
3988 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
3989 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
3990 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
3991 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
3992 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
3993 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
3994
3995 # undef BZ_ITAH
3996
3997 } else {
3998 /*--- slow version which correctly handles all situations ---*/
3999 for (i = gs; i <= ge; i++) {
4000 bsW ( s,
4001 s->len [s->selector[selCtr]] [mtfv[i]],
4002 s->code [s->selector[selCtr]] [mtfv[i]] );
4003 }
4004 }
4005
4006
4007 gs = ge+1;
4008 selCtr++;
4009 }
4010 AssertH( selCtr == nSelectors, 3007 );
4011
4012 if (s->verbosity >= 3)
4013 VPrintf1( "codes %d\n", s->numZ-nBytes );
4014 }
4015
4016
4017 /*---------------------------------------------------*/
BZ2_compressBlock(EState * s,Bool is_last_block)4018 void BZ2_compressBlock ( EState* s, Bool is_last_block )
4019 {
4020 if (s->nblock > 0) {
4021
4022 BZ_FINALISE_CRC ( s->blockCRC );
4023 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
4024 s->combinedCRC ^= s->blockCRC;
4025 if (s->blockNo > 1) s->numZ = 0;
4026
4027 if (s->verbosity >= 2)
4028 VPrintf4( " block %d: crc = 0x%08x, "
4029 "combined CRC = 0x%08x, size = %d\n",
4030 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
4031
4032 BZ2_blockSort ( s );
4033 }
4034
4035 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
4036
4037 /*-- If this is the first block, create the stream header. --*/
4038 if (s->blockNo == 1) {
4039 BZ2_bsInitWrite ( s );
4040 bsPutUChar ( s, BZ_HDR_B );
4041 bsPutUChar ( s, BZ_HDR_Z );
4042 bsPutUChar ( s, BZ_HDR_h );
4043 bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
4044 }
4045
4046 if (s->nblock > 0) {
4047
4048 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
4049 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
4050 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
4051
4052 /*-- Now the block's CRC, so it is in a known place. --*/
4053 bsPutUInt32 ( s, s->blockCRC );
4054
4055 /*--
4056 Now a single bit indicating (non-)randomisation.
4057 As of version 0.9.5, we use a better sorting algorithm
4058 which makes randomisation unnecessary. So always set
4059 the randomised bit to 'no'. Of course, the decoder
4060 still needs to be able to handle randomised blocks
4061 so as to maintain backwards compatibility with
4062 older versions of bzip2.
4063 --*/
4064 bsW(s,1,0);
4065
4066 bsW ( s, 24, s->origPtr );
4067 generateMTFValues ( s );
4068 sendMTFValues ( s );
4069 }
4070
4071
4072 /*-- If this is the last block, add the stream trailer. --*/
4073 if (is_last_block) {
4074
4075 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
4076 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
4077 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
4078 bsPutUInt32 ( s, s->combinedCRC );
4079 if (s->verbosity >= 2)
4080 VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC );
4081 bsFinishWrite ( s );
4082 }
4083 }
4084
4085
4086 /*-------------------------------------------------------------*/
4087 /*--- end compress.c ---*/
4088 /*-------------------------------------------------------------*/
4089
4090
4091 /*-------------------------------------------------------------*/
4092 /*--- Table for randomising repetitive blocks ---*/
4093 /*--- randtable.c ---*/
4094 /*-------------------------------------------------------------*/
4095
4096 /*--
4097 This file is a part of bzip2 and/or libbzip2, a program and
4098 library for lossless, block-sorting data compression.
4099
4100 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
4101
4102 Redistribution and use in source and binary forms, with or without
4103 modification, are permitted provided that the following conditions
4104 are met:
4105
4106 1. Redistributions of source code must retain the above copyright
4107 notice, this list of conditions and the following disclaimer.
4108
4109 2. The origin of this software must not be misrepresented; you must
4110 not claim that you wrote the original software. If you use this
4111 software in a product, an acknowledgment in the product
4112 documentation would be appreciated but is not required.
4113
4114 3. Altered source versions must be plainly marked as such, and must
4115 not be misrepresented as being the original software.
4116
4117 4. The name of the author may not be used to endorse or promote
4118 products derived from this software without specific prior written
4119 permission.
4120
4121 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
4122 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
4123 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
4124 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
4125 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
4126 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
4127 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
4128 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
4129 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
4130 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
4131 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4132
4133 Julian Seward, Cambridge, UK.
4134 jseward@bzip.org
4135 bzip2/libbzip2 version 1.0 of 21 March 2000
4136
4137 This program is based on (at least) the work of:
4138 Mike Burrows
4139 David Wheeler
4140 Peter Fenwick
4141 Alistair Moffat
4142 Radford Neal
4143 Ian H. Witten
4144 Robert Sedgewick
4145 Jon L. Bentley
4146
4147 For more information on these sources, see the manual.
4148 --*/
4149
4150
4151
4152
4153 /*---------------------------------------------*/
4154 Int32 BZ2_rNums[512] = {
4155 619, 720, 127, 481, 931, 816, 813, 233, 566, 247,
4156 985, 724, 205, 454, 863, 491, 741, 242, 949, 214,
4157 733, 859, 335, 708, 621, 574, 73, 654, 730, 472,
4158 419, 436, 278, 496, 867, 210, 399, 680, 480, 51,
4159 878, 465, 811, 169, 869, 675, 611, 697, 867, 561,
4160 862, 687, 507, 283, 482, 129, 807, 591, 733, 623,
4161 150, 238, 59, 379, 684, 877, 625, 169, 643, 105,
4162 170, 607, 520, 932, 727, 476, 693, 425, 174, 647,
4163 73, 122, 335, 530, 442, 853, 695, 249, 445, 515,
4164 909, 545, 703, 919, 874, 474, 882, 500, 594, 612,
4165 641, 801, 220, 162, 819, 984, 589, 513, 495, 799,
4166 161, 604, 958, 533, 221, 400, 386, 867, 600, 782,
4167 382, 596, 414, 171, 516, 375, 682, 485, 911, 276,
4168 98, 553, 163, 354, 666, 933, 424, 341, 533, 870,
4169 227, 730, 475, 186, 263, 647, 537, 686, 600, 224,
4170 469, 68, 770, 919, 190, 373, 294, 822, 808, 206,
4171 184, 943, 795, 384, 383, 461, 404, 758, 839, 887,
4172 715, 67, 618, 276, 204, 918, 873, 777, 604, 560,
4173 951, 160, 578, 722, 79, 804, 96, 409, 713, 940,
4174 652, 934, 970, 447, 318, 353, 859, 672, 112, 785,
4175 645, 863, 803, 350, 139, 93, 354, 99, 820, 908,
4176 609, 772, 154, 274, 580, 184, 79, 626, 630, 742,
4177 653, 282, 762, 623, 680, 81, 927, 626, 789, 125,
4178 411, 521, 938, 300, 821, 78, 343, 175, 128, 250,
4179 170, 774, 972, 275, 999, 639, 495, 78, 352, 126,
4180 857, 956, 358, 619, 580, 124, 737, 594, 701, 612,
4181 669, 112, 134, 694, 363, 992, 809, 743, 168, 974,
4182 944, 375, 748, 52, 600, 747, 642, 182, 862, 81,
4183 344, 805, 988, 739, 511, 655, 814, 334, 249, 515,
4184 897, 955, 664, 981, 649, 113, 974, 459, 893, 228,
4185 433, 837, 553, 268, 926, 240, 102, 654, 459, 51,
4186 686, 754, 806, 760, 493, 403, 415, 394, 687, 700,
4187 946, 670, 656, 610, 738, 392, 760, 799, 887, 653,
4188 978, 321, 576, 617, 626, 502, 894, 679, 243, 440,
4189 680, 879, 194, 572, 640, 724, 926, 56, 204, 700,
4190 707, 151, 457, 449, 797, 195, 791, 558, 945, 679,
4191 297, 59, 87, 824, 713, 663, 412, 693, 342, 606,
4192 134, 108, 571, 364, 631, 212, 174, 643, 304, 329,
4193 343, 97, 430, 751, 497, 314, 983, 374, 822, 928,
4194 140, 206, 73, 263, 980, 736, 876, 478, 430, 305,
4195 170, 514, 364, 692, 829, 82, 855, 953, 676, 246,
4196 369, 970, 294, 750, 807, 827, 150, 790, 288, 923,
4197 804, 378, 215, 828, 592, 281, 565, 555, 710, 82,
4198 896, 831, 547, 261, 524, 462, 293, 465, 502, 56,
4199 661, 821, 976, 991, 658, 869, 905, 758, 745, 193,
4200 768, 550, 608, 933, 378, 286, 215, 979, 792, 961,
4201 61, 688, 793, 644, 986, 403, 106, 366, 905, 644,
4202 372, 567, 466, 434, 645, 210, 389, 550, 919, 135,
4203 780, 773, 635, 389, 707, 100, 626, 958, 165, 504,
4204 920, 176, 193, 713, 857, 265, 203, 50, 668, 108,
4205 645, 990, 626, 197, 510, 357, 358, 850, 858, 364,
4206 936, 638
4207 };
4208
4209
4210 /*-------------------------------------------------------------*/
4211 /*--- end randtable.c ---*/
4212 /*-------------------------------------------------------------*/
4213
4214 /*-------------------------------------------------------------*/
4215 /*--- Table for doing CRCs ---*/
4216 /*--- crctable.c ---*/
4217 /*-------------------------------------------------------------*/
4218
4219 /*--
4220 This file is a part of bzip2 and/or libbzip2, a program and
4221 library for lossless, block-sorting data compression.
4222
4223 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
4224
4225 Redistribution and use in source and binary forms, with or without
4226 modification, are permitted provided that the following conditions
4227 are met:
4228
4229 1. Redistributions of source code must retain the above copyright
4230 notice, this list of conditions and the following disclaimer.
4231
4232 2. The origin of this software must not be misrepresented; you must
4233 not claim that you wrote the original software. If you use this
4234 software in a product, an acknowledgment in the product
4235 documentation would be appreciated but is not required.
4236
4237 3. Altered source versions must be plainly marked as such, and must
4238 not be misrepresented as being the original software.
4239
4240 4. The name of the author may not be used to endorse or promote
4241 products derived from this software without specific prior written
4242 permission.
4243
4244 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
4245 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
4246 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
4247 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
4248 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
4249 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
4250 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
4251 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
4252 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
4253 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
4254 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4255
4256 Julian Seward, Cambridge, UK.
4257 jseward@bzip.org
4258 bzip2/libbzip2 version 1.0 of 21 March 2000
4259
4260 This program is based on (at least) the work of:
4261 Mike Burrows
4262 David Wheeler
4263 Peter Fenwick
4264 Alistair Moffat
4265 Radford Neal
4266 Ian H. Witten
4267 Robert Sedgewick
4268 Jon L. Bentley
4269
4270 For more information on these sources, see the manual.
4271 --*/
4272
4273
4274
4275
4276
4277 /*--
4278 I think this is an implementation of the AUTODIN-II,
4279 Ethernet & FDDI 32-bit CRC standard. Vaguely derived
4280 from code by Rob Warnock, in Section 51 of the
4281 comp.compression FAQ.
4282 --*/
4283
4284 UInt32 BZ2_crc32Table[256] = {
4285
4286 /*-- Ugly, innit? --*/
4287
4288 0x00000000L, 0x04c11db7L, 0x09823b6eL, 0x0d4326d9L,
4289 0x130476dcL, 0x17c56b6bL, 0x1a864db2L, 0x1e475005L,
4290 0x2608edb8L, 0x22c9f00fL, 0x2f8ad6d6L, 0x2b4bcb61L,
4291 0x350c9b64L, 0x31cd86d3L, 0x3c8ea00aL, 0x384fbdbdL,
4292 0x4c11db70L, 0x48d0c6c7L, 0x4593e01eL, 0x4152fda9L,
4293 0x5f15adacL, 0x5bd4b01bL, 0x569796c2L, 0x52568b75L,
4294 0x6a1936c8L, 0x6ed82b7fL, 0x639b0da6L, 0x675a1011L,
4295 0x791d4014L, 0x7ddc5da3L, 0x709f7b7aL, 0x745e66cdL,
4296 0x9823b6e0L, 0x9ce2ab57L, 0x91a18d8eL, 0x95609039L,
4297 0x8b27c03cL, 0x8fe6dd8bL, 0x82a5fb52L, 0x8664e6e5L,
4298 0xbe2b5b58L, 0xbaea46efL, 0xb7a96036L, 0xb3687d81L,
4299 0xad2f2d84L, 0xa9ee3033L, 0xa4ad16eaL, 0xa06c0b5dL,
4300 0xd4326d90L, 0xd0f37027L, 0xddb056feL, 0xd9714b49L,
4301 0xc7361b4cL, 0xc3f706fbL, 0xceb42022L, 0xca753d95L,
4302 0xf23a8028L, 0xf6fb9d9fL, 0xfbb8bb46L, 0xff79a6f1L,
4303 0xe13ef6f4L, 0xe5ffeb43L, 0xe8bccd9aL, 0xec7dd02dL,
4304 0x34867077L, 0x30476dc0L, 0x3d044b19L, 0x39c556aeL,
4305 0x278206abL, 0x23431b1cL, 0x2e003dc5L, 0x2ac12072L,
4306 0x128e9dcfL, 0x164f8078L, 0x1b0ca6a1L, 0x1fcdbb16L,
4307 0x018aeb13L, 0x054bf6a4L, 0x0808d07dL, 0x0cc9cdcaL,
4308 0x7897ab07L, 0x7c56b6b0L, 0x71159069L, 0x75d48ddeL,
4309 0x6b93dddbL, 0x6f52c06cL, 0x6211e6b5L, 0x66d0fb02L,
4310 0x5e9f46bfL, 0x5a5e5b08L, 0x571d7dd1L, 0x53dc6066L,
4311 0x4d9b3063L, 0x495a2dd4L, 0x44190b0dL, 0x40d816baL,
4312 0xaca5c697L, 0xa864db20L, 0xa527fdf9L, 0xa1e6e04eL,
4313 0xbfa1b04bL, 0xbb60adfcL, 0xb6238b25L, 0xb2e29692L,
4314 0x8aad2b2fL, 0x8e6c3698L, 0x832f1041L, 0x87ee0df6L,
4315 0x99a95df3L, 0x9d684044L, 0x902b669dL, 0x94ea7b2aL,
4316 0xe0b41de7L, 0xe4750050L, 0xe9362689L, 0xedf73b3eL,
4317 0xf3b06b3bL, 0xf771768cL, 0xfa325055L, 0xfef34de2L,
4318 0xc6bcf05fL, 0xc27dede8L, 0xcf3ecb31L, 0xcbffd686L,
4319 0xd5b88683L, 0xd1799b34L, 0xdc3abdedL, 0xd8fba05aL,
4320 0x690ce0eeL, 0x6dcdfd59L, 0x608edb80L, 0x644fc637L,
4321 0x7a089632L, 0x7ec98b85L, 0x738aad5cL, 0x774bb0ebL,
4322 0x4f040d56L, 0x4bc510e1L, 0x46863638L, 0x42472b8fL,
4323 0x5c007b8aL, 0x58c1663dL, 0x558240e4L, 0x51435d53L,
4324 0x251d3b9eL, 0x21dc2629L, 0x2c9f00f0L, 0x285e1d47L,
4325 0x36194d42L, 0x32d850f5L, 0x3f9b762cL, 0x3b5a6b9bL,
4326 0x0315d626L, 0x07d4cb91L, 0x0a97ed48L, 0x0e56f0ffL,
4327 0x1011a0faL, 0x14d0bd4dL, 0x19939b94L, 0x1d528623L,
4328 0xf12f560eL, 0xf5ee4bb9L, 0xf8ad6d60L, 0xfc6c70d7L,
4329 0xe22b20d2L, 0xe6ea3d65L, 0xeba91bbcL, 0xef68060bL,
4330 0xd727bbb6L, 0xd3e6a601L, 0xdea580d8L, 0xda649d6fL,
4331 0xc423cd6aL, 0xc0e2d0ddL, 0xcda1f604L, 0xc960ebb3L,
4332 0xbd3e8d7eL, 0xb9ff90c9L, 0xb4bcb610L, 0xb07daba7L,
4333 0xae3afba2L, 0xaafbe615L, 0xa7b8c0ccL, 0xa379dd7bL,
4334 0x9b3660c6L, 0x9ff77d71L, 0x92b45ba8L, 0x9675461fL,
4335 0x8832161aL, 0x8cf30badL, 0x81b02d74L, 0x857130c3L,
4336 0x5d8a9099L, 0x594b8d2eL, 0x5408abf7L, 0x50c9b640L,
4337 0x4e8ee645L, 0x4a4ffbf2L, 0x470cdd2bL, 0x43cdc09cL,
4338 0x7b827d21L, 0x7f436096L, 0x7200464fL, 0x76c15bf8L,
4339 0x68860bfdL, 0x6c47164aL, 0x61043093L, 0x65c52d24L,
4340 0x119b4be9L, 0x155a565eL, 0x18197087L, 0x1cd86d30L,
4341 0x029f3d35L, 0x065e2082L, 0x0b1d065bL, 0x0fdc1becL,
4342 0x3793a651L, 0x3352bbe6L, 0x3e119d3fL, 0x3ad08088L,
4343 0x2497d08dL, 0x2056cd3aL, 0x2d15ebe3L, 0x29d4f654L,
4344 0xc5a92679L, 0xc1683bceL, 0xcc2b1d17L, 0xc8ea00a0L,
4345 0xd6ad50a5L, 0xd26c4d12L, 0xdf2f6bcbL, 0xdbee767cL,
4346 0xe3a1cbc1L, 0xe760d676L, 0xea23f0afL, 0xeee2ed18L,
4347 0xf0a5bd1dL, 0xf464a0aaL, 0xf9278673L, 0xfde69bc4L,
4348 0x89b8fd09L, 0x8d79e0beL, 0x803ac667L, 0x84fbdbd0L,
4349 0x9abc8bd5L, 0x9e7d9662L, 0x933eb0bbL, 0x97ffad0cL,
4350 0xafb010b1L, 0xab710d06L, 0xa6322bdfL, 0xa2f33668L,
4351 0xbcb4666dL, 0xb8757bdaL, 0xb5365d03L, 0xb1f740b4L
4352 };
4353
4354
4355 /*-------------------------------------------------------------*/
4356 /*--- end crctable.c ---*/
4357 /*-------------------------------------------------------------*/
4358
4359 /*-------------------------------------------------------------*/
4360 /*--- Library top-level functions. ---*/
4361 /*--- bzlib.c ---*/
4362 /*-------------------------------------------------------------*/
4363
4364 /*--
4365 This file is a part of bzip2 and/or libbzip2, a program and
4366 library for lossless, block-sorting data compression.
4367
4368 Copyright (C) 1996-2004 Julian R Seward. All rights reserved.
4369
4370 Redistribution and use in source and binary forms, with or without
4371 modification, are permitted provided that the following conditions
4372 are met:
4373
4374 1. Redistributions of source code must retain the above copyright
4375 notice, this list of conditions and the following disclaimer.
4376
4377 2. The origin of this software must not be misrepresented; you must
4378 not claim that you wrote the original software. If you use this
4379 software in a product, an acknowledgment in the product
4380 documentation would be appreciated but is not required.
4381
4382 3. Altered source versions must be plainly marked as such, and must
4383 not be misrepresented as being the original software.
4384
4385 4. The name of the author may not be used to endorse or promote
4386 products derived from this software without specific prior written
4387 permission.
4388
4389 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
4390 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
4391 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
4392 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
4393 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
4394 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
4395 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
4396 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
4397 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
4398 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
4399 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4400
4401 Julian Seward, Cambridge, UK.
4402 jseward@bzip.org
4403 bzip2/libbzip2 version 1.0 of 21 March 2000
4404
4405 This program is based on (at least) the work of:
4406 Mike Burrows
4407 David Wheeler
4408 Peter Fenwick
4409 Alistair Moffat
4410 Radford Neal
4411 Ian H. Witten
4412 Robert Sedgewick
4413 Jon L. Bentley
4414
4415 For more information on these sources, see the manual.
4416 --*/
4417
4418 /*--
4419 CHANGES
4420 ~~~~~~~
4421 0.9.0 -- original version.
4422
4423 0.9.0a/b -- no changes in this file.
4424
4425 0.9.0c
4426 * made zero-length BZ_FLUSH work correctly in bzCompress().
4427 * fixed bzWrite/bzRead to ignore zero-length requests.
4428 * fixed bzread to correctly handle read requests after EOF.
4429 * wrong parameter order in call to bzDecompressInit in
4430 bzBuffToBuffDecompress. Fixed.
4431 --*/
4432
4433
4434
4435 /*---------------------------------------------------*/
4436 /*--- Compression stuff ---*/
4437 /*---------------------------------------------------*/
4438
4439
4440 /*---------------------------------------------------*/
BZ2_bz__AssertH__fail(int errcode)4441 void BZ2_bz__AssertH__fail ( int errcode )
4442 {
4443 vex_printf("BZ2_bz__AssertH__fail(%d) called, exiting\n", errcode);
4444 (*serviceFn)(0,0);
4445 }
4446
bz_internal_error(int errcode)4447 void bz_internal_error ( int errcode )
4448 {
4449 vex_printf("bz_internal_error called, exiting\n", errcode);
4450 (*serviceFn)(0,0);
4451 }
4452
4453 /*---------------------------------------------------*/
4454 static
bz_config_ok(void)4455 int bz_config_ok ( void )
4456 {
4457 if (sizeof(int) != 4) return 0;
4458 if (sizeof(short) != 2) return 0;
4459 if (sizeof(char) != 1) return 0;
4460 return 1;
4461 }
4462
4463
4464 /*---------------------------------------------------*/
4465 static
default_bzalloc(void * opaque,Int32 items,Int32 size)4466 void* default_bzalloc ( void* opaque, Int32 items, Int32 size )
4467 {
4468 void* v = (void*) (*serviceFn)(2, items * size );
4469 return v;
4470 }
4471
4472 static
default_bzfree(void * opaque,void * addr)4473 void default_bzfree ( void* opaque, void* addr )
4474 {
4475 if (addr != NULL) (*serviceFn)( 3, (HWord)addr );
4476 }
4477
4478
4479 /*---------------------------------------------------*/
4480 static
prepare_new_block(EState * s)4481 void prepare_new_block ( EState* s )
4482 {
4483 Int32 i;
4484 s->nblock = 0;
4485 s->numZ = 0;
4486 s->state_out_pos = 0;
4487 BZ_INITIALISE_CRC ( s->blockCRC );
4488 for (i = 0; i < 256; i++) s->inUse[i] = False;
4489 s->blockNo++;
4490 }
4491
4492
4493 /*---------------------------------------------------*/
4494 static
init_RL(EState * s)4495 void init_RL ( EState* s )
4496 {
4497 s->state_in_ch = 256;
4498 s->state_in_len = 0;
4499 }
4500
4501
4502 static
isempty_RL(EState * s)4503 Bool isempty_RL ( EState* s )
4504 {
4505 if (s->state_in_ch < 256 && s->state_in_len > 0)
4506 return False; else
4507 return True;
4508 }
4509
4510
4511 /*---------------------------------------------------*/
BZ_API(BZ2_bzCompressInit)4512 int BZ_API(BZ2_bzCompressInit)
4513 ( bz_stream* strm,
4514 int blockSize100k,
4515 int verbosity,
4516 int workFactor )
4517 {
4518 Int32 n;
4519 EState* s;
4520
4521 if (!bz_config_ok()) return BZ_CONFIG_ERROR;
4522
4523 if (strm == NULL ||
4524 blockSize100k < 1 || blockSize100k > 9 ||
4525 workFactor < 0 || workFactor > 250)
4526 return BZ_PARAM_ERROR;
4527
4528 if (workFactor == 0) workFactor = 30;
4529 if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
4530 if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
4531
4532 s = BZALLOC( sizeof(EState) );
4533 if (s == NULL) return BZ_MEM_ERROR;
4534 s->strm = strm;
4535
4536 s->arr1 = NULL;
4537 s->arr2 = NULL;
4538 s->ftab = NULL;
4539
4540 n = 100000 * blockSize100k;
4541 s->arr1 = BZALLOC( n * sizeof(UInt32) );
4542 s->arr2 = BZALLOC( (n+BZ_N_OVERSHOOT) * sizeof(UInt32) );
4543 s->ftab = BZALLOC( 65537 * sizeof(UInt32) );
4544
4545 if (s->arr1 == NULL || s->arr2 == NULL || s->ftab == NULL) {
4546 if (s->arr1 != NULL) BZFREE(s->arr1);
4547 if (s->arr2 != NULL) BZFREE(s->arr2);
4548 if (s->ftab != NULL) BZFREE(s->ftab);
4549 if (s != NULL) BZFREE(s);
4550 return BZ_MEM_ERROR;
4551 }
4552
4553 s->blockNo = 0;
4554 s->state = BZ_S_INPUT;
4555 s->mode = BZ_M_RUNNING;
4556 s->combinedCRC = 0;
4557 s->blockSize100k = blockSize100k;
4558 s->nblockMAX = 100000 * blockSize100k - 19;
4559 s->verbosity = verbosity;
4560 s->workFactor = workFactor;
4561
4562 s->block = (UChar*)s->arr2;
4563 s->mtfv = (UInt16*)s->arr1;
4564 s->zbits = NULL;
4565 s->ptr = (UInt32*)s->arr1;
4566
4567 strm->state = s;
4568 strm->total_in_lo32 = 0;
4569 strm->total_in_hi32 = 0;
4570 strm->total_out_lo32 = 0;
4571 strm->total_out_hi32 = 0;
4572 init_RL ( s );
4573 prepare_new_block ( s );
4574 return BZ_OK;
4575 }
4576
4577
4578 /*---------------------------------------------------*/
4579 static
add_pair_to_block(EState * s)4580 void add_pair_to_block ( EState* s )
4581 {
4582 Int32 i;
4583 UChar ch = (UChar)(s->state_in_ch);
4584 for (i = 0; i < s->state_in_len; i++) {
4585 BZ_UPDATE_CRC( s->blockCRC, ch );
4586 }
4587 s->inUse[s->state_in_ch] = True;
4588 switch (s->state_in_len) {
4589 case 1:
4590 s->block[s->nblock] = (UChar)ch; s->nblock++;
4591 break;
4592 case 2:
4593 s->block[s->nblock] = (UChar)ch; s->nblock++;
4594 s->block[s->nblock] = (UChar)ch; s->nblock++;
4595 break;
4596 case 3:
4597 s->block[s->nblock] = (UChar)ch; s->nblock++;
4598 s->block[s->nblock] = (UChar)ch; s->nblock++;
4599 s->block[s->nblock] = (UChar)ch; s->nblock++;
4600 break;
4601 default:
4602 s->inUse[s->state_in_len-4] = True;
4603 s->block[s->nblock] = (UChar)ch; s->nblock++;
4604 s->block[s->nblock] = (UChar)ch; s->nblock++;
4605 s->block[s->nblock] = (UChar)ch; s->nblock++;
4606 s->block[s->nblock] = (UChar)ch; s->nblock++;
4607 s->block[s->nblock] = ((UChar)(s->state_in_len-4));
4608 s->nblock++;
4609 break;
4610 }
4611 }
4612
4613
4614 /*---------------------------------------------------*/
4615 static
flush_RL(EState * s)4616 void flush_RL ( EState* s )
4617 {
4618 if (s->state_in_ch < 256) add_pair_to_block ( s );
4619 init_RL ( s );
4620 }
4621
4622
4623 /*---------------------------------------------------*/
4624 #define ADD_CHAR_TO_BLOCK(zs,zchh0) \
4625 { \
4626 UInt32 zchh = (UInt32)(zchh0); \
4627 /*-- fast track the common case --*/ \
4628 if (zchh != zs->state_in_ch && \
4629 zs->state_in_len == 1) { \
4630 UChar ch = (UChar)(zs->state_in_ch); \
4631 BZ_UPDATE_CRC( zs->blockCRC, ch ); \
4632 zs->inUse[zs->state_in_ch] = True; \
4633 zs->block[zs->nblock] = (UChar)ch; \
4634 zs->nblock++; \
4635 zs->state_in_ch = zchh; \
4636 } \
4637 else \
4638 /*-- general, uncommon cases --*/ \
4639 if (zchh != zs->state_in_ch || \
4640 zs->state_in_len == 255) { \
4641 if (zs->state_in_ch < 256) \
4642 add_pair_to_block ( zs ); \
4643 zs->state_in_ch = zchh; \
4644 zs->state_in_len = 1; \
4645 } else { \
4646 zs->state_in_len++; \
4647 } \
4648 }
4649
4650
4651 /*---------------------------------------------------*/
4652 static
copy_input_until_stop(EState * s)4653 Bool copy_input_until_stop ( EState* s )
4654 {
4655 Bool progress_in = False;
4656
4657 if (s->mode == BZ_M_RUNNING) {
4658
4659 /*-- fast track the common case --*/
4660 while (True) {
4661 /*-- block full? --*/
4662 if (s->nblock >= s->nblockMAX) break;
4663 /*-- no input? --*/
4664 if (s->strm->avail_in == 0) break;
4665 progress_in = True;
4666 ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) );
4667 s->strm->next_in++;
4668 s->strm->avail_in--;
4669 s->strm->total_in_lo32++;
4670 if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++;
4671 }
4672
4673 } else {
4674
4675 /*-- general, uncommon case --*/
4676 while (True) {
4677 /*-- block full? --*/
4678 if (s->nblock >= s->nblockMAX) break;
4679 /*-- no input? --*/
4680 if (s->strm->avail_in == 0) break;
4681 /*-- flush/finish end? --*/
4682 if (s->avail_in_expect == 0) break;
4683 progress_in = True;
4684 ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) );
4685 s->strm->next_in++;
4686 s->strm->avail_in--;
4687 s->strm->total_in_lo32++;
4688 if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++;
4689 s->avail_in_expect--;
4690 }
4691 }
4692 return progress_in;
4693 }
4694
4695
4696 /*---------------------------------------------------*/
4697 static
copy_output_until_stop(EState * s)4698 Bool copy_output_until_stop ( EState* s )
4699 {
4700 Bool progress_out = False;
4701
4702 while (True) {
4703
4704 /*-- no output space? --*/
4705 if (s->strm->avail_out == 0) break;
4706
4707 /*-- block done? --*/
4708 if (s->state_out_pos >= s->numZ) break;
4709
4710 progress_out = True;
4711 *(s->strm->next_out) = s->zbits[s->state_out_pos];
4712 s->state_out_pos++;
4713 s->strm->avail_out--;
4714 s->strm->next_out++;
4715 s->strm->total_out_lo32++;
4716 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
4717 }
4718
4719 return progress_out;
4720 }
4721
4722
4723 /*---------------------------------------------------*/
4724 static
handle_compress(bz_stream * strm)4725 Bool handle_compress ( bz_stream* strm )
4726 {
4727 Bool progress_in = False;
4728 Bool progress_out = False;
4729 EState* s = strm->state;
4730
4731 while (True) {
4732
4733 if (s->state == BZ_S_OUTPUT) {
4734 progress_out |= copy_output_until_stop ( s );
4735 if (s->state_out_pos < s->numZ) break;
4736 if (s->mode == BZ_M_FINISHING &&
4737 s->avail_in_expect == 0 &&
4738 isempty_RL(s)) break;
4739 prepare_new_block ( s );
4740 s->state = BZ_S_INPUT;
4741 if (s->mode == BZ_M_FLUSHING &&
4742 s->avail_in_expect == 0 &&
4743 isempty_RL(s)) break;
4744 }
4745
4746 if (s->state == BZ_S_INPUT) {
4747 progress_in |= copy_input_until_stop ( s );
4748 if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
4749 flush_RL ( s );
4750 BZ2_compressBlock ( s, (Bool)(s->mode == BZ_M_FINISHING) );
4751 s->state = BZ_S_OUTPUT;
4752 }
4753 else
4754 if (s->nblock >= s->nblockMAX) {
4755 BZ2_compressBlock ( s, False );
4756 s->state = BZ_S_OUTPUT;
4757 }
4758 else
4759 if (s->strm->avail_in == 0) {
4760 break;
4761 }
4762 }
4763
4764 }
4765
4766 return progress_in || progress_out;
4767 }
4768
4769
4770 /*---------------------------------------------------*/
BZ_API(BZ2_bzCompress)4771 int BZ_API(BZ2_bzCompress) ( bz_stream *strm, int action )
4772 {
4773 Bool progress;
4774 EState* s;
4775 if (strm == NULL) return BZ_PARAM_ERROR;
4776 s = strm->state;
4777 if (s == NULL) return BZ_PARAM_ERROR;
4778 if (s->strm != strm) return BZ_PARAM_ERROR;
4779
4780 preswitch:
4781 switch (s->mode) {
4782
4783 case BZ_M_IDLE:
4784 return BZ_SEQUENCE_ERROR;
4785
4786 case BZ_M_RUNNING:
4787 if (action == BZ_RUN) {
4788 progress = handle_compress ( strm );
4789 return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;
4790 }
4791 else
4792 if (action == BZ_FLUSH) {
4793 s->avail_in_expect = strm->avail_in;
4794 s->mode = BZ_M_FLUSHING;
4795 goto preswitch;
4796 }
4797 else
4798 if (action == BZ_FINISH) {
4799 s->avail_in_expect = strm->avail_in;
4800 s->mode = BZ_M_FINISHING;
4801 goto preswitch;
4802 }
4803 else
4804 return BZ_PARAM_ERROR;
4805
4806 case BZ_M_FLUSHING:
4807 if (action != BZ_FLUSH) return BZ_SEQUENCE_ERROR;
4808 if (s->avail_in_expect != s->strm->avail_in)
4809 return BZ_SEQUENCE_ERROR;
4810 progress = handle_compress ( strm );
4811 if (s->avail_in_expect > 0 || !isempty_RL(s) ||
4812 s->state_out_pos < s->numZ) return BZ_FLUSH_OK;
4813 s->mode = BZ_M_RUNNING;
4814 return BZ_RUN_OK;
4815
4816 case BZ_M_FINISHING:
4817 if (action != BZ_FINISH) return BZ_SEQUENCE_ERROR;
4818 if (s->avail_in_expect != s->strm->avail_in)
4819 return BZ_SEQUENCE_ERROR;
4820 progress = handle_compress ( strm );
4821 if (!progress) return BZ_SEQUENCE_ERROR;
4822 if (s->avail_in_expect > 0 || !isempty_RL(s) ||
4823 s->state_out_pos < s->numZ) return BZ_FINISH_OK;
4824 s->mode = BZ_M_IDLE;
4825 return BZ_STREAM_END;
4826 }
4827 return BZ_OK; /*--not reached--*/
4828 }
4829
4830
4831 /*---------------------------------------------------*/
BZ_API(BZ2_bzCompressEnd)4832 int BZ_API(BZ2_bzCompressEnd) ( bz_stream *strm )
4833 {
4834 EState* s;
4835 if (strm == NULL) return BZ_PARAM_ERROR;
4836 s = strm->state;
4837 if (s == NULL) return BZ_PARAM_ERROR;
4838 if (s->strm != strm) return BZ_PARAM_ERROR;
4839
4840 if (s->arr1 != NULL) BZFREE(s->arr1);
4841 if (s->arr2 != NULL) BZFREE(s->arr2);
4842 if (s->ftab != NULL) BZFREE(s->ftab);
4843 BZFREE(strm->state);
4844
4845 strm->state = NULL;
4846
4847 return BZ_OK;
4848 }
4849
4850
4851 /*---------------------------------------------------*/
4852 /*--- Decompression stuff ---*/
4853 /*---------------------------------------------------*/
4854
4855 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompressInit)4856 int BZ_API(BZ2_bzDecompressInit)
4857 ( bz_stream* strm,
4858 int verbosity,
4859 int small )
4860 {
4861 DState* s;
4862
4863 if (!bz_config_ok()) return BZ_CONFIG_ERROR;
4864
4865 if (strm == NULL) return BZ_PARAM_ERROR;
4866 if (small != 0 && small != 1) return BZ_PARAM_ERROR;
4867 if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR;
4868
4869 if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc;
4870 if (strm->bzfree == NULL) strm->bzfree = default_bzfree;
4871
4872 s = BZALLOC( sizeof(DState) );
4873 if (s == NULL) return BZ_MEM_ERROR;
4874 s->strm = strm;
4875 strm->state = s;
4876 s->state = BZ_X_MAGIC_1;
4877 s->bsLive = 0;
4878 s->bsBuff = 0;
4879 s->calculatedCombinedCRC = 0;
4880 strm->total_in_lo32 = 0;
4881 strm->total_in_hi32 = 0;
4882 strm->total_out_lo32 = 0;
4883 strm->total_out_hi32 = 0;
4884 s->smallDecompress = (Bool)small;
4885 s->ll4 = NULL;
4886 s->ll16 = NULL;
4887 s->tt = NULL;
4888 s->currBlockNo = 0;
4889 s->verbosity = verbosity;
4890
4891 return BZ_OK;
4892 }
4893
4894
4895 /*---------------------------------------------------*/
4896 /* Return True iff data corruption is discovered.
4897 Returns False if there is no problem.
4898 */
4899 static
unRLE_obuf_to_output_FAST(DState * s)4900 Bool unRLE_obuf_to_output_FAST ( DState* s )
4901 {
4902 UChar k1;
4903
4904 if (s->blockRandomised) {
4905
4906 while (True) {
4907 /* try to finish existing run */
4908 while (True) {
4909 if (s->strm->avail_out == 0) return False;
4910 if (s->state_out_len == 0) break;
4911 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
4912 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
4913 s->state_out_len--;
4914 s->strm->next_out++;
4915 s->strm->avail_out--;
4916 s->strm->total_out_lo32++;
4917 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
4918 }
4919
4920 /* can a new run be started? */
4921 if (s->nblock_used == s->save_nblock+1) return False;
4922
4923 /* Only caused by corrupt data stream? */
4924 if (s->nblock_used > s->save_nblock+1)
4925 return True;
4926
4927 s->state_out_len = 1;
4928 s->state_out_ch = s->k0;
4929 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
4930 k1 ^= BZ_RAND_MASK; s->nblock_used++;
4931 if (s->nblock_used == s->save_nblock+1) continue;
4932 if (k1 != s->k0) { s->k0 = k1; continue; };
4933
4934 s->state_out_len = 2;
4935 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
4936 k1 ^= BZ_RAND_MASK; s->nblock_used++;
4937 if (s->nblock_used == s->save_nblock+1) continue;
4938 if (k1 != s->k0) { s->k0 = k1; continue; };
4939
4940 s->state_out_len = 3;
4941 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
4942 k1 ^= BZ_RAND_MASK; s->nblock_used++;
4943 if (s->nblock_used == s->save_nblock+1) continue;
4944 if (k1 != s->k0) { s->k0 = k1; continue; };
4945
4946 BZ_GET_FAST(k1); BZ_RAND_UPD_MASK;
4947 k1 ^= BZ_RAND_MASK; s->nblock_used++;
4948 s->state_out_len = ((Int32)k1) + 4;
4949 BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK;
4950 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
4951 }
4952
4953 } else {
4954
4955 /* restore */
4956 UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC;
4957 UChar c_state_out_ch = s->state_out_ch;
4958 Int32 c_state_out_len = s->state_out_len;
4959 Int32 c_nblock_used = s->nblock_used;
4960 Int32 c_k0 = s->k0;
4961 UInt32* c_tt = s->tt;
4962 UInt32 c_tPos = s->tPos;
4963 char* cs_next_out = s->strm->next_out;
4964 unsigned int cs_avail_out = s->strm->avail_out;
4965 /* end restore */
4966
4967 UInt32 avail_out_INIT = cs_avail_out;
4968 Int32 s_save_nblockPP = s->save_nblock+1;
4969 unsigned int total_out_lo32_old;
4970
4971 while (True) {
4972
4973 /* try to finish existing run */
4974 if (c_state_out_len > 0) {
4975 while (True) {
4976 if (cs_avail_out == 0) goto return_notr;
4977 if (c_state_out_len == 1) break;
4978 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
4979 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
4980 c_state_out_len--;
4981 cs_next_out++;
4982 cs_avail_out--;
4983 }
4984 s_state_out_len_eq_one:
4985 {
4986 if (cs_avail_out == 0) {
4987 c_state_out_len = 1; goto return_notr;
4988 };
4989 *( (UChar*)(cs_next_out) ) = c_state_out_ch;
4990 BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch );
4991 cs_next_out++;
4992 cs_avail_out--;
4993 }
4994 }
4995 /* Only caused by corrupt data stream? */
4996 if (c_nblock_used > s_save_nblockPP)
4997 return True;
4998
4999 /* can a new run be started? */
5000 if (c_nblock_used == s_save_nblockPP) {
5001 c_state_out_len = 0; goto return_notr;
5002 };
5003 c_state_out_ch = c_k0;
5004 BZ_GET_FAST_C(k1); c_nblock_used++;
5005 if (k1 != c_k0) {
5006 c_k0 = k1; goto s_state_out_len_eq_one;
5007 };
5008 if (c_nblock_used == s_save_nblockPP)
5009 goto s_state_out_len_eq_one;
5010
5011 c_state_out_len = 2;
5012 BZ_GET_FAST_C(k1); c_nblock_used++;
5013 if (c_nblock_used == s_save_nblockPP) continue;
5014 if (k1 != c_k0) { c_k0 = k1; continue; };
5015
5016 c_state_out_len = 3;
5017 BZ_GET_FAST_C(k1); c_nblock_used++;
5018 if (c_nblock_used == s_save_nblockPP) continue;
5019 if (k1 != c_k0) { c_k0 = k1; continue; };
5020
5021 BZ_GET_FAST_C(k1); c_nblock_used++;
5022 c_state_out_len = ((Int32)k1) + 4;
5023 BZ_GET_FAST_C(c_k0); c_nblock_used++;
5024 }
5025
5026 return_notr:
5027 total_out_lo32_old = s->strm->total_out_lo32;
5028 s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out);
5029 if (s->strm->total_out_lo32 < total_out_lo32_old)
5030 s->strm->total_out_hi32++;
5031
5032 /* save */
5033 s->calculatedBlockCRC = c_calculatedBlockCRC;
5034 s->state_out_ch = c_state_out_ch;
5035 s->state_out_len = c_state_out_len;
5036 s->nblock_used = c_nblock_used;
5037 s->k0 = c_k0;
5038 s->tt = c_tt;
5039 s->tPos = c_tPos;
5040 s->strm->next_out = cs_next_out;
5041 s->strm->avail_out = cs_avail_out;
5042 /* end save */
5043 }
5044 return False;
5045 }
5046
5047
5048
5049 /*---------------------------------------------------*/
5050 /* Return True iff data corruption is discovered.
5051 Returns False if there is no problem.
5052 */
5053 static
unRLE_obuf_to_output_SMALL(DState * s)5054 Bool unRLE_obuf_to_output_SMALL ( DState* s )
5055 {
5056 UChar k1;
5057
5058 if (s->blockRandomised) {
5059
5060 while (True) {
5061 /* try to finish existing run */
5062 while (True) {
5063 if (s->strm->avail_out == 0) return False;
5064 if (s->state_out_len == 0) break;
5065 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
5066 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
5067 s->state_out_len--;
5068 s->strm->next_out++;
5069 s->strm->avail_out--;
5070 s->strm->total_out_lo32++;
5071 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
5072 }
5073
5074 /* can a new run be started? */
5075 if (s->nblock_used == s->save_nblock+1) return False;
5076
5077 /* Only caused by corrupt data stream? */
5078 if (s->nblock_used > s->save_nblock+1)
5079 return True;
5080
5081 s->state_out_len = 1;
5082 s->state_out_ch = s->k0;
5083 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
5084 k1 ^= BZ_RAND_MASK; s->nblock_used++;
5085 if (s->nblock_used == s->save_nblock+1) continue;
5086 if (k1 != s->k0) { s->k0 = k1; continue; };
5087
5088 s->state_out_len = 2;
5089 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
5090 k1 ^= BZ_RAND_MASK; s->nblock_used++;
5091 if (s->nblock_used == s->save_nblock+1) continue;
5092 if (k1 != s->k0) { s->k0 = k1; continue; };
5093
5094 s->state_out_len = 3;
5095 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
5096 k1 ^= BZ_RAND_MASK; s->nblock_used++;
5097 if (s->nblock_used == s->save_nblock+1) continue;
5098 if (k1 != s->k0) { s->k0 = k1; continue; };
5099
5100 BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK;
5101 k1 ^= BZ_RAND_MASK; s->nblock_used++;
5102 s->state_out_len = ((Int32)k1) + 4;
5103 BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK;
5104 s->k0 ^= BZ_RAND_MASK; s->nblock_used++;
5105 }
5106
5107 } else {
5108
5109 while (True) {
5110 /* try to finish existing run */
5111 while (True) {
5112 if (s->strm->avail_out == 0) return False;
5113 if (s->state_out_len == 0) break;
5114 *( (UChar*)(s->strm->next_out) ) = s->state_out_ch;
5115 BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch );
5116 s->state_out_len--;
5117 s->strm->next_out++;
5118 s->strm->avail_out--;
5119 s->strm->total_out_lo32++;
5120 if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++;
5121 }
5122
5123 /* can a new run be started? */
5124 if (s->nblock_used == s->save_nblock+1) return False;
5125
5126 /* Only caused by corrupt data stream? */
5127 if (s->nblock_used > s->save_nblock+1)
5128 return True;
5129
5130 s->state_out_len = 1;
5131 s->state_out_ch = s->k0;
5132 BZ_GET_SMALL(k1); s->nblock_used++;
5133 if (s->nblock_used == s->save_nblock+1) continue;
5134 if (k1 != s->k0) { s->k0 = k1; continue; };
5135
5136 s->state_out_len = 2;
5137 BZ_GET_SMALL(k1); s->nblock_used++;
5138 if (s->nblock_used == s->save_nblock+1) continue;
5139 if (k1 != s->k0) { s->k0 = k1; continue; };
5140
5141 s->state_out_len = 3;
5142 BZ_GET_SMALL(k1); s->nblock_used++;
5143 if (s->nblock_used == s->save_nblock+1) continue;
5144 if (k1 != s->k0) { s->k0 = k1; continue; };
5145
5146 BZ_GET_SMALL(k1); s->nblock_used++;
5147 s->state_out_len = ((Int32)k1) + 4;
5148 BZ_GET_SMALL(s->k0); s->nblock_used++;
5149 }
5150
5151 }
5152 }
5153
5154
5155 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompress)5156 int BZ_API(BZ2_bzDecompress) ( bz_stream *strm )
5157 {
5158 Bool corrupt;
5159 DState* s;
5160 if (strm == NULL) return BZ_PARAM_ERROR;
5161 s = strm->state;
5162 if (s == NULL) return BZ_PARAM_ERROR;
5163 if (s->strm != strm) return BZ_PARAM_ERROR;
5164
5165 while (True) {
5166 if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR;
5167 if (s->state == BZ_X_OUTPUT) {
5168 if (s->smallDecompress)
5169 corrupt = unRLE_obuf_to_output_SMALL ( s ); else
5170 corrupt = unRLE_obuf_to_output_FAST ( s );
5171 if (corrupt) return BZ_DATA_ERROR;
5172 if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) {
5173 BZ_FINALISE_CRC ( s->calculatedBlockCRC );
5174 if (s->verbosity >= 3)
5175 VPrintf2 ( " {0x%08x, 0x%08x}", s->storedBlockCRC,
5176 s->calculatedBlockCRC );
5177 if (s->verbosity >= 2) VPrintf0 ( "]" );
5178 if (s->calculatedBlockCRC != s->storedBlockCRC)
5179 return BZ_DATA_ERROR;
5180 s->calculatedCombinedCRC
5181 = (s->calculatedCombinedCRC << 1) |
5182 (s->calculatedCombinedCRC >> 31);
5183 s->calculatedCombinedCRC ^= s->calculatedBlockCRC;
5184 s->state = BZ_X_BLKHDR_1;
5185 } else {
5186 return BZ_OK;
5187 }
5188 }
5189 if (s->state >= BZ_X_MAGIC_1) {
5190 Int32 r = BZ2_decompress ( s );
5191 if (r == BZ_STREAM_END) {
5192 if (s->verbosity >= 3)
5193 VPrintf2 ( "\n combined CRCs: stored = 0x%08x, computed = 0x%08x",
5194 s->storedCombinedCRC, s->calculatedCombinedCRC );
5195 if (s->calculatedCombinedCRC != s->storedCombinedCRC)
5196 return BZ_DATA_ERROR;
5197 return r;
5198 }
5199 if (s->state != BZ_X_OUTPUT) return r;
5200 }
5201 }
5202
5203 AssertH ( 0, 6001 );
5204
5205 return 0; /*NOTREACHED*/
5206 }
5207
5208
5209 /*---------------------------------------------------*/
BZ_API(BZ2_bzDecompressEnd)5210 int BZ_API(BZ2_bzDecompressEnd) ( bz_stream *strm )
5211 {
5212 DState* s;
5213 if (strm == NULL) return BZ_PARAM_ERROR;
5214 s = strm->state;
5215 if (s == NULL) return BZ_PARAM_ERROR;
5216 if (s->strm != strm) return BZ_PARAM_ERROR;
5217
5218 if (s->tt != NULL) BZFREE(s->tt);
5219 if (s->ll16 != NULL) BZFREE(s->ll16);
5220 if (s->ll4 != NULL) BZFREE(s->ll4);
5221
5222 BZFREE(strm->state);
5223 strm->state = NULL;
5224
5225 return BZ_OK;
5226 }
5227
5228
5229 #ifndef BZ_NO_STDIO
5230 /*---------------------------------------------------*/
5231 /*--- File I/O stuff ---*/
5232 /*---------------------------------------------------*/
5233
5234 #define BZ_SETERR(eee) \
5235 { \
5236 if (bzerror != NULL) *bzerror = eee; \
5237 if (bzf != NULL) bzf->lastErr = eee; \
5238 }
5239
5240 typedef
5241 struct {
5242 FILE* handle;
5243 Char buf[BZ_MAX_UNUSED];
5244 Int32 bufN;
5245 Bool writing;
5246 bz_stream strm;
5247 Int32 lastErr;
5248 Bool initialisedOk;
5249 }
5250 bzFile;
5251
5252
5253 /*---------------------------------------------*/
myfeof(FILE * f)5254 static Bool myfeof ( FILE* f )
5255 {
5256 Int32 c = fgetc ( f );
5257 if (c == EOF) return True;
5258 ungetc ( c, f );
5259 return False;
5260 }
5261
5262
5263 /*---------------------------------------------------*/
BZ_API(BZ2_bzWriteOpen)5264 BZFILE* BZ_API(BZ2_bzWriteOpen)
5265 ( int* bzerror,
5266 FILE* f,
5267 int blockSize100k,
5268 int verbosity,
5269 int workFactor )
5270 {
5271 Int32 ret;
5272 bzFile* bzf = NULL;
5273
5274 BZ_SETERR(BZ_OK);
5275
5276 if (f == NULL ||
5277 (blockSize100k < 1 || blockSize100k > 9) ||
5278 (workFactor < 0 || workFactor > 250) ||
5279 (verbosity < 0 || verbosity > 4))
5280 { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };
5281
5282 if (ferror(f))
5283 { BZ_SETERR(BZ_IO_ERROR); return NULL; };
5284
5285 bzf = malloc ( sizeof(bzFile) );
5286 if (bzf == NULL)
5287 { BZ_SETERR(BZ_MEM_ERROR); return NULL; };
5288
5289 BZ_SETERR(BZ_OK);
5290 bzf->initialisedOk = False;
5291 bzf->bufN = 0;
5292 bzf->handle = f;
5293 bzf->writing = True;
5294 bzf->strm.bzalloc = NULL;
5295 bzf->strm.bzfree = NULL;
5296 bzf->strm.opaque = NULL;
5297
5298 if (workFactor == 0) workFactor = 30;
5299 ret = BZ2_bzCompressInit ( &(bzf->strm), blockSize100k,
5300 verbosity, workFactor );
5301 if (ret != BZ_OK)
5302 { BZ_SETERR(ret); free(bzf); return NULL; };
5303
5304 bzf->strm.avail_in = 0;
5305 bzf->initialisedOk = True;
5306 return bzf;
5307 }
5308
5309
5310
5311 /*---------------------------------------------------*/
BZ_API(BZ2_bzWrite)5312 void BZ_API(BZ2_bzWrite)
5313 ( int* bzerror,
5314 BZFILE* b,
5315 void* buf,
5316 int len )
5317 {
5318 Int32 n, n2, ret;
5319 bzFile* bzf = (bzFile*)b;
5320
5321 BZ_SETERR(BZ_OK);
5322 if (bzf == NULL || buf == NULL || len < 0)
5323 { BZ_SETERR(BZ_PARAM_ERROR); return; };
5324 if (!(bzf->writing))
5325 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
5326 if (ferror(bzf->handle))
5327 { BZ_SETERR(BZ_IO_ERROR); return; };
5328
5329 if (len == 0)
5330 { BZ_SETERR(BZ_OK); return; };
5331
5332 bzf->strm.avail_in = len;
5333 bzf->strm.next_in = buf;
5334
5335 while (True) {
5336 bzf->strm.avail_out = BZ_MAX_UNUSED;
5337 bzf->strm.next_out = bzf->buf;
5338 ret = BZ2_bzCompress ( &(bzf->strm), BZ_RUN );
5339 if (ret != BZ_RUN_OK)
5340 { BZ_SETERR(ret); return; };
5341
5342 if (bzf->strm.avail_out < BZ_MAX_UNUSED) {
5343 n = BZ_MAX_UNUSED - bzf->strm.avail_out;
5344 n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar),
5345 n, bzf->handle );
5346 if (n != n2 || ferror(bzf->handle))
5347 { BZ_SETERR(BZ_IO_ERROR); return; };
5348 }
5349
5350 if (bzf->strm.avail_in == 0)
5351 { BZ_SETERR(BZ_OK); return; };
5352 }
5353 }
5354
5355
5356 /*---------------------------------------------------*/
BZ_API(BZ2_bzWriteClose)5357 void BZ_API(BZ2_bzWriteClose)
5358 ( int* bzerror,
5359 BZFILE* b,
5360 int abandon,
5361 unsigned int* nbytes_in,
5362 unsigned int* nbytes_out )
5363 {
5364 BZ2_bzWriteClose64 ( bzerror, b, abandon,
5365 nbytes_in, NULL, nbytes_out, NULL );
5366 }
5367
5368
BZ_API(BZ2_bzWriteClose64)5369 void BZ_API(BZ2_bzWriteClose64)
5370 ( int* bzerror,
5371 BZFILE* b,
5372 int abandon,
5373 unsigned int* nbytes_in_lo32,
5374 unsigned int* nbytes_in_hi32,
5375 unsigned int* nbytes_out_lo32,
5376 unsigned int* nbytes_out_hi32 )
5377 {
5378 Int32 n, n2, ret;
5379 bzFile* bzf = (bzFile*)b;
5380
5381 if (bzf == NULL)
5382 { BZ_SETERR(BZ_OK); return; };
5383 if (!(bzf->writing))
5384 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
5385 if (ferror(bzf->handle))
5386 { BZ_SETERR(BZ_IO_ERROR); return; };
5387
5388 if (nbytes_in_lo32 != NULL) *nbytes_in_lo32 = 0;
5389 if (nbytes_in_hi32 != NULL) *nbytes_in_hi32 = 0;
5390 if (nbytes_out_lo32 != NULL) *nbytes_out_lo32 = 0;
5391 if (nbytes_out_hi32 != NULL) *nbytes_out_hi32 = 0;
5392
5393 if ((!abandon) && bzf->lastErr == BZ_OK) {
5394 while (True) {
5395 bzf->strm.avail_out = BZ_MAX_UNUSED;
5396 bzf->strm.next_out = bzf->buf;
5397 ret = BZ2_bzCompress ( &(bzf->strm), BZ_FINISH );
5398 if (ret != BZ_FINISH_OK && ret != BZ_STREAM_END)
5399 { BZ_SETERR(ret); return; };
5400
5401 if (bzf->strm.avail_out < BZ_MAX_UNUSED) {
5402 n = BZ_MAX_UNUSED - bzf->strm.avail_out;
5403 n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar),
5404 n, bzf->handle );
5405 if (n != n2 || ferror(bzf->handle))
5406 { BZ_SETERR(BZ_IO_ERROR); return; };
5407 }
5408
5409 if (ret == BZ_STREAM_END) break;
5410 }
5411 }
5412
5413 if ( !abandon && !ferror ( bzf->handle ) ) {
5414 fflush ( bzf->handle );
5415 if (ferror(bzf->handle))
5416 { BZ_SETERR(BZ_IO_ERROR); return; };
5417 }
5418
5419 if (nbytes_in_lo32 != NULL)
5420 *nbytes_in_lo32 = bzf->strm.total_in_lo32;
5421 if (nbytes_in_hi32 != NULL)
5422 *nbytes_in_hi32 = bzf->strm.total_in_hi32;
5423 if (nbytes_out_lo32 != NULL)
5424 *nbytes_out_lo32 = bzf->strm.total_out_lo32;
5425 if (nbytes_out_hi32 != NULL)
5426 *nbytes_out_hi32 = bzf->strm.total_out_hi32;
5427
5428 BZ_SETERR(BZ_OK);
5429 BZ2_bzCompressEnd ( &(bzf->strm) );
5430 free ( bzf );
5431 }
5432
5433
5434 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadOpen)5435 BZFILE* BZ_API(BZ2_bzReadOpen)
5436 ( int* bzerror,
5437 FILE* f,
5438 int verbosity,
5439 int small,
5440 void* unused,
5441 int nUnused )
5442 {
5443 bzFile* bzf = NULL;
5444 int ret;
5445
5446 BZ_SETERR(BZ_OK);
5447
5448 if (f == NULL ||
5449 (small != 0 && small != 1) ||
5450 (verbosity < 0 || verbosity > 4) ||
5451 (unused == NULL && nUnused != 0) ||
5452 (unused != NULL && (nUnused < 0 || nUnused > BZ_MAX_UNUSED)))
5453 { BZ_SETERR(BZ_PARAM_ERROR); return NULL; };
5454
5455 if (ferror(f))
5456 { BZ_SETERR(BZ_IO_ERROR); return NULL; };
5457
5458 bzf = malloc ( sizeof(bzFile) );
5459 if (bzf == NULL)
5460 { BZ_SETERR(BZ_MEM_ERROR); return NULL; };
5461
5462 BZ_SETERR(BZ_OK);
5463
5464 bzf->initialisedOk = False;
5465 bzf->handle = f;
5466 bzf->bufN = 0;
5467 bzf->writing = False;
5468 bzf->strm.bzalloc = NULL;
5469 bzf->strm.bzfree = NULL;
5470 bzf->strm.opaque = NULL;
5471
5472 while (nUnused > 0) {
5473 bzf->buf[bzf->bufN] = *((UChar*)(unused)); bzf->bufN++;
5474 unused = ((void*)( 1 + ((UChar*)(unused)) ));
5475 nUnused--;
5476 }
5477
5478 ret = BZ2_bzDecompressInit ( &(bzf->strm), verbosity, small );
5479 if (ret != BZ_OK)
5480 { BZ_SETERR(ret); free(bzf); return NULL; };
5481
5482 bzf->strm.avail_in = bzf->bufN;
5483 bzf->strm.next_in = bzf->buf;
5484
5485 bzf->initialisedOk = True;
5486 return bzf;
5487 }
5488
5489
5490 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadClose)5491 void BZ_API(BZ2_bzReadClose) ( int *bzerror, BZFILE *b )
5492 {
5493 bzFile* bzf = (bzFile*)b;
5494
5495 BZ_SETERR(BZ_OK);
5496 if (bzf == NULL)
5497 { BZ_SETERR(BZ_OK); return; };
5498
5499 if (bzf->writing)
5500 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
5501
5502 if (bzf->initialisedOk)
5503 (void)BZ2_bzDecompressEnd ( &(bzf->strm) );
5504 free ( bzf );
5505 }
5506
5507
5508 /*---------------------------------------------------*/
BZ_API(BZ2_bzRead)5509 int BZ_API(BZ2_bzRead)
5510 ( int* bzerror,
5511 BZFILE* b,
5512 void* buf,
5513 int len )
5514 {
5515 Int32 n, ret;
5516 bzFile* bzf = (bzFile*)b;
5517
5518 BZ_SETERR(BZ_OK);
5519
5520 if (bzf == NULL || buf == NULL || len < 0)
5521 { BZ_SETERR(BZ_PARAM_ERROR); return 0; };
5522
5523 if (bzf->writing)
5524 { BZ_SETERR(BZ_SEQUENCE_ERROR); return 0; };
5525
5526 if (len == 0)
5527 { BZ_SETERR(BZ_OK); return 0; };
5528
5529 bzf->strm.avail_out = len;
5530 bzf->strm.next_out = buf;
5531
5532 while (True) {
5533
5534 if (ferror(bzf->handle))
5535 { BZ_SETERR(BZ_IO_ERROR); return 0; };
5536
5537 if (bzf->strm.avail_in == 0 && !myfeof(bzf->handle)) {
5538 n = fread ( bzf->buf, sizeof(UChar),
5539 BZ_MAX_UNUSED, bzf->handle );
5540 if (ferror(bzf->handle))
5541 { BZ_SETERR(BZ_IO_ERROR); return 0; };
5542 bzf->bufN = n;
5543 bzf->strm.avail_in = bzf->bufN;
5544 bzf->strm.next_in = bzf->buf;
5545 }
5546
5547 ret = BZ2_bzDecompress ( &(bzf->strm) );
5548
5549 if (ret != BZ_OK && ret != BZ_STREAM_END)
5550 { BZ_SETERR(ret); return 0; };
5551
5552 if (ret == BZ_OK && myfeof(bzf->handle) &&
5553 bzf->strm.avail_in == 0 && bzf->strm.avail_out > 0)
5554 { BZ_SETERR(BZ_UNEXPECTED_EOF); return 0; };
5555
5556 if (ret == BZ_STREAM_END)
5557 { BZ_SETERR(BZ_STREAM_END);
5558 return len - bzf->strm.avail_out; };
5559 if (bzf->strm.avail_out == 0)
5560 { BZ_SETERR(BZ_OK); return len; };
5561
5562 }
5563
5564 return 0; /*not reached*/
5565 }
5566
5567
5568 /*---------------------------------------------------*/
BZ_API(BZ2_bzReadGetUnused)5569 void BZ_API(BZ2_bzReadGetUnused)
5570 ( int* bzerror,
5571 BZFILE* b,
5572 void** unused,
5573 int* nUnused )
5574 {
5575 bzFile* bzf = (bzFile*)b;
5576 if (bzf == NULL)
5577 { BZ_SETERR(BZ_PARAM_ERROR); return; };
5578 if (bzf->lastErr != BZ_STREAM_END)
5579 { BZ_SETERR(BZ_SEQUENCE_ERROR); return; };
5580 if (unused == NULL || nUnused == NULL)
5581 { BZ_SETERR(BZ_PARAM_ERROR); return; };
5582
5583 BZ_SETERR(BZ_OK);
5584 *nUnused = bzf->strm.avail_in;
5585 *unused = bzf->strm.next_in;
5586 }
5587 #endif
5588
5589
5590 /*---------------------------------------------------*/
5591 /*--- Misc convenience stuff ---*/
5592 /*---------------------------------------------------*/
5593
5594 /*---------------------------------------------------*/
BZ_API(BZ2_bzBuffToBuffCompress)5595 int BZ_API(BZ2_bzBuffToBuffCompress)
5596 ( char* dest,
5597 unsigned int* destLen,
5598 char* source,
5599 unsigned int sourceLen,
5600 int blockSize100k,
5601 int verbosity,
5602 int workFactor )
5603 {
5604 bz_stream strm;
5605 int ret;
5606
5607 if (dest == NULL || destLen == NULL ||
5608 source == NULL ||
5609 blockSize100k < 1 || blockSize100k > 9 ||
5610 verbosity < 0 || verbosity > 4 ||
5611 workFactor < 0 || workFactor > 250)
5612 return BZ_PARAM_ERROR;
5613
5614 if (workFactor == 0) workFactor = 30;
5615 strm.bzalloc = NULL;
5616 strm.bzfree = NULL;
5617 strm.opaque = NULL;
5618 ret = BZ2_bzCompressInit ( &strm, blockSize100k,
5619 verbosity, workFactor );
5620 if (ret != BZ_OK) return ret;
5621
5622 strm.next_in = source;
5623 strm.next_out = dest;
5624 strm.avail_in = sourceLen;
5625 strm.avail_out = *destLen;
5626
5627 ret = BZ2_bzCompress ( &strm, BZ_FINISH );
5628 if (ret == BZ_FINISH_OK) goto output_overflow;
5629 if (ret != BZ_STREAM_END) goto errhandler;
5630
5631 /* normal termination */
5632 *destLen -= strm.avail_out;
5633 BZ2_bzCompressEnd ( &strm );
5634 return BZ_OK;
5635
5636 output_overflow:
5637 BZ2_bzCompressEnd ( &strm );
5638 return BZ_OUTBUFF_FULL;
5639
5640 errhandler:
5641 BZ2_bzCompressEnd ( &strm );
5642 return ret;
5643 }
5644
5645
5646 /*---------------------------------------------------*/
BZ_API(BZ2_bzBuffToBuffDecompress)5647 int BZ_API(BZ2_bzBuffToBuffDecompress)
5648 ( char* dest,
5649 unsigned int* destLen,
5650 char* source,
5651 unsigned int sourceLen,
5652 int small,
5653 int verbosity )
5654 {
5655 bz_stream strm;
5656 int ret;
5657
5658 if (dest == NULL || destLen == NULL ||
5659 source == NULL ||
5660 (small != 0 && small != 1) ||
5661 verbosity < 0 || verbosity > 4)
5662 return BZ_PARAM_ERROR;
5663
5664 strm.bzalloc = NULL;
5665 strm.bzfree = NULL;
5666 strm.opaque = NULL;
5667 ret = BZ2_bzDecompressInit ( &strm, verbosity, small );
5668 if (ret != BZ_OK) return ret;
5669
5670 strm.next_in = source;
5671 strm.next_out = dest;
5672 strm.avail_in = sourceLen;
5673 strm.avail_out = *destLen;
5674
5675 ret = BZ2_bzDecompress ( &strm );
5676 if (ret == BZ_OK) goto output_overflow_or_eof;
5677 if (ret != BZ_STREAM_END) goto errhandler;
5678
5679 /* normal termination */
5680 *destLen -= strm.avail_out;
5681 BZ2_bzDecompressEnd ( &strm );
5682 return BZ_OK;
5683
5684 output_overflow_or_eof:
5685 if (strm.avail_out > 0) {
5686 BZ2_bzDecompressEnd ( &strm );
5687 return BZ_UNEXPECTED_EOF;
5688 } else {
5689 BZ2_bzDecompressEnd ( &strm );
5690 return BZ_OUTBUFF_FULL;
5691 };
5692
5693 errhandler:
5694 BZ2_bzDecompressEnd ( &strm );
5695 return ret;
5696 }
5697
5698
5699 /*---------------------------------------------------*/
5700 /*--
5701 Code contributed by Yoshioka Tsuneo
5702 (QWF00133@niftyserve.or.jp/tsuneo-y@is.aist-nara.ac.jp),
5703 to support better zlib compatibility.
5704 This code is not _officially_ part of libbzip2 (yet);
5705 I haven't tested it, documented it, or considered the
5706 threading-safeness of it.
5707 If this code breaks, please contact both Yoshioka and me.
5708 --*/
5709 /*---------------------------------------------------*/
5710
5711 /*---------------------------------------------------*/
5712 /*--
5713 return version like "0.9.0c".
5714 --*/
BZ_API(BZ2_bzlibVersion)5715 const char * BZ_API(BZ2_bzlibVersion)(void)
5716 {
5717 return BZ_VERSION;
5718 }
5719
5720
5721 #ifndef BZ_NO_STDIO
5722 /*---------------------------------------------------*/
5723
5724 #if defined(_WIN32) || defined(OS2) || defined(MSDOS)
5725 # include <fcntl.h>
5726 # include <io.h>
5727 # define SET_BINARY_MODE(file) setmode(fileno(file),O_BINARY)
5728 #else
5729 # define SET_BINARY_MODE(file)
5730 #endif
5731 static
bzopen_or_bzdopen(const char * path,int fd,const char * mode,int open_mode)5732 BZFILE * bzopen_or_bzdopen
5733 ( const char *path, /* no use when bzdopen */
5734 int fd, /* no use when bzdopen */
5735 const char *mode,
5736 int open_mode) /* bzopen: 0, bzdopen:1 */
5737 {
5738 int bzerr;
5739 char unused[BZ_MAX_UNUSED];
5740 int blockSize100k = 9;
5741 int writing = 0;
5742 char mode2[10] = "";
5743 FILE *fp = NULL;
5744 BZFILE *bzfp = NULL;
5745 int verbosity = 0;
5746 int workFactor = 30;
5747 int smallMode = 0;
5748 int nUnused = 0;
5749
5750 if (mode == NULL) return NULL;
5751 while (*mode) {
5752 switch (*mode) {
5753 case 'r':
5754 writing = 0; break;
5755 case 'w':
5756 writing = 1; break;
5757 case 's':
5758 smallMode = 1; break;
5759 default:
5760 if (isdigit((int)(*mode))) {
5761 blockSize100k = *mode-BZ_HDR_0;
5762 }
5763 }
5764 mode++;
5765 }
5766 strcat(mode2, writing ? "w" : "r" );
5767 strcat(mode2,"b"); /* binary mode */
5768
5769 if (open_mode==0) {
5770 if (path==NULL || strcmp(path,"")==0) {
5771 fp = (writing ? stdout : stdin);
5772 SET_BINARY_MODE(fp);
5773 } else {
5774 fp = fopen(path,mode2);
5775 }
5776 } else {
5777 #ifdef BZ_STRICT_ANSI
5778 fp = NULL;
5779 #else
5780 fp = fdopen(fd,mode2);
5781 #endif
5782 }
5783 if (fp == NULL) return NULL;
5784
5785 if (writing) {
5786 /* Guard against total chaos and anarchy -- JRS */
5787 if (blockSize100k < 1) blockSize100k = 1;
5788 if (blockSize100k > 9) blockSize100k = 9;
5789 bzfp = BZ2_bzWriteOpen(&bzerr,fp,blockSize100k,
5790 verbosity,workFactor);
5791 } else {
5792 bzfp = BZ2_bzReadOpen(&bzerr,fp,verbosity,smallMode,
5793 unused,nUnused);
5794 }
5795 if (bzfp == NULL) {
5796 if (fp != stdin && fp != stdout) fclose(fp);
5797 return NULL;
5798 }
5799 return bzfp;
5800 }
5801
5802
5803 /*---------------------------------------------------*/
5804 /*--
5805 open file for read or write.
5806 ex) bzopen("file","w9")
5807 case path="" or NULL => use stdin or stdout.
5808 --*/
BZ_API(BZ2_bzopen)5809 BZFILE * BZ_API(BZ2_bzopen)
5810 ( const char *path,
5811 const char *mode )
5812 {
5813 return bzopen_or_bzdopen(path,-1,mode,/*bzopen*/0);
5814 }
5815
5816
5817 /*---------------------------------------------------*/
BZ_API(BZ2_bzdopen)5818 BZFILE * BZ_API(BZ2_bzdopen)
5819 ( int fd,
5820 const char *mode )
5821 {
5822 return bzopen_or_bzdopen(NULL,fd,mode,/*bzdopen*/1);
5823 }
5824
5825
5826 /*---------------------------------------------------*/
BZ_API(BZ2_bzread)5827 int BZ_API(BZ2_bzread) (BZFILE* b, void* buf, int len )
5828 {
5829 int bzerr, nread;
5830 if (((bzFile*)b)->lastErr == BZ_STREAM_END) return 0;
5831 nread = BZ2_bzRead(&bzerr,b,buf,len);
5832 if (bzerr == BZ_OK || bzerr == BZ_STREAM_END) {
5833 return nread;
5834 } else {
5835 return -1;
5836 }
5837 }
5838
5839
5840 /*---------------------------------------------------*/
BZ_API(BZ2_bzwrite)5841 int BZ_API(BZ2_bzwrite) (BZFILE* b, void* buf, int len )
5842 {
5843 int bzerr;
5844
5845 BZ2_bzWrite(&bzerr,b,buf,len);
5846 if(bzerr == BZ_OK){
5847 return len;
5848 }else{
5849 return -1;
5850 }
5851 }
5852
5853
5854 /*---------------------------------------------------*/
BZ_API(BZ2_bzflush)5855 int BZ_API(BZ2_bzflush) (BZFILE *b)
5856 {
5857 /* do nothing now... */
5858 return 0;
5859 }
5860
5861
5862 /*---------------------------------------------------*/
BZ_API(BZ2_bzclose)5863 void BZ_API(BZ2_bzclose) (BZFILE* b)
5864 {
5865 int bzerr;
5866 FILE *fp = ((bzFile *)b)->handle;
5867
5868 if (b==NULL) {return;}
5869 if(((bzFile*)b)->writing){
5870 BZ2_bzWriteClose(&bzerr,b,0,NULL,NULL);
5871 if(bzerr != BZ_OK){
5872 BZ2_bzWriteClose(NULL,b,1,NULL,NULL);
5873 }
5874 }else{
5875 BZ2_bzReadClose(&bzerr,b);
5876 }
5877 if(fp!=stdin && fp!=stdout){
5878 fclose(fp);
5879 }
5880 }
5881
5882
5883 /*---------------------------------------------------*/
5884 /*--
5885 return last error code
5886 --*/
5887 static char *bzerrorstrings[] = {
5888 "OK"
5889 ,"SEQUENCE_ERROR"
5890 ,"PARAM_ERROR"
5891 ,"MEM_ERROR"
5892 ,"DATA_ERROR"
5893 ,"DATA_ERROR_MAGIC"
5894 ,"IO_ERROR"
5895 ,"UNEXPECTED_EOF"
5896 ,"OUTBUFF_FULL"
5897 ,"CONFIG_ERROR"
5898 ,"???" /* for future */
5899 ,"???" /* for future */
5900 ,"???" /* for future */
5901 ,"???" /* for future */
5902 ,"???" /* for future */
5903 ,"???" /* for future */
5904 };
5905
5906
BZ_API(BZ2_bzerror)5907 const char * BZ_API(BZ2_bzerror) (BZFILE *b, int *errnum)
5908 {
5909 int err = ((bzFile *)b)->lastErr;
5910
5911 if(err>0) err = 0;
5912 *errnum = err;
5913 return bzerrorstrings[err*-1];
5914 }
5915 #endif
5916
5917
5918 /*-------------------------------------------------------------*/
5919 /*--- end bzlib.c ---*/
5920 /*-------------------------------------------------------------*/
5921
5922
5923 /////////////////////////////////////////////////////////////////////
5924 /////////////////////////////////////////////////////////////////////
5925
5926
5927 /* A test program written to test robustness to decompression of
5928 corrupted data. Usage is
5929 unzcrash filename
5930 and the program will read the specified file, compress it (in memory),
5931 and then repeatedly decompress it, each time with a different bit of
5932 the compressed data inverted, so as to test all possible one-bit errors.
5933 This should not cause any invalid memory accesses. If it does,
5934 I want to know about it!
5935
5936 p.s. As you can see from the above description, the process is
5937 incredibly slow. A file of size eg 5KB will cause it to run for
5938 many hours.
5939 */
5940
5941 //#include <stdio.h>
5942 //#include <assert.h>
5943 //#include "bzlib.h"
5944
5945 #define M_BLOCK 1000000
5946
5947
5948 #define M_BLOCK_OUT (M_BLOCK + 1000000)
5949 char inbuf[M_BLOCK];
5950 char outbuf[M_BLOCK_OUT];
5951 char zbuf[M_BLOCK + 600 + (M_BLOCK / 100)];
5952
5953 int nIn;
5954 unsigned int nOut;
5955 unsigned int nZ;
5956
5957 #if 0
5958 static char *bzerrorstrings[] = {
5959 "OK"
5960 ,"SEQUENCE_ERROR"
5961 ,"PARAM_ERROR"
5962 ,"MEM_ERROR"
5963 ,"DATA_ERROR"
5964 ,"DATA_ERROR_MAGIC"
5965 ,"IO_ERROR"
5966 ,"UNEXPECTED_EOF"
5967 ,"OUTBUFF_FULL"
5968 ,"???" /* for future */
5969 ,"???" /* for future */
5970 ,"???" /* for future */
5971 ,"???" /* for future */
5972 ,"???" /* for future */
5973 ,"???" /* for future */
5974 };
5975 #endif
5976
flip_bit(int bit)5977 void flip_bit ( int bit )
5978 {
5979 int byteno = bit / 8;
5980 int bitno = bit % 8;
5981 UChar mask = 1 << bitno;
5982 //fprintf ( stderr, "(byte %d bit %d mask %d)",
5983 // byteno, bitno, (int)mask );
5984 zbuf[byteno] ^= mask;
5985 }
5986
set_inbuf(void)5987 void set_inbuf ( void )
5988 {
5989 inbuf[0] = 0;
5990 my_strcat(inbuf, "At her sixtieth birthday party, Margaret Thatcher ");
5991 my_strcat(inbuf, "blew on the cake to light the candles.\n");
5992 my_strcat(inbuf, "This program, bzip2, the associated library libbzip2, and all\n");
5993 my_strcat(inbuf, "documentation, are copyright (C) 1996-2004 Julian R Seward. All\n");
5994 my_strcat(inbuf, "rights reserved.\n");
5995 my_strcat(inbuf, "\n");
5996 my_strcat(inbuf, "Redistribution and use in source and binary forms, with or without\n");
5997 my_strcat(inbuf, "modification, are permitted provided that the following conditions\n");
5998 my_strcat(inbuf, "are met:\n");
5999 my_strcat(inbuf, "\n");
6000 my_strcat(inbuf, "1. Redistributions of source code must retain the above copyright\n");
6001 my_strcat(inbuf, " notice, this list of conditions and the following disclaimer.\n");
6002 my_strcat(inbuf, "\n");
6003 my_strcat(inbuf, "2. The origin of this software must not be misrepresented; you must\n");
6004 my_strcat(inbuf, " not claim that you wrote the original software. If you use this\n");
6005 my_strcat(inbuf, " software in a product, an acknowledgment in the product\n");
6006 my_strcat(inbuf, " documentation would be appreciated but is not required.\n");
6007 my_strcat(inbuf, "\n");
6008 my_strcat(inbuf, "3. Altered source versions must be plainly marked as such, and must\n");
6009 my_strcat(inbuf, " not be misrepresented as being the original software.\n");
6010 my_strcat(inbuf, "\n");
6011 my_strcat(inbuf, "4. The name of the author may not be used to endorse or promote\n");
6012 my_strcat(inbuf, " products derived from this software without specific prior written\n");
6013 my_strcat(inbuf, " permission.\n");
6014 my_strcat(inbuf, "\n");
6015 my_strcat(inbuf, "THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS\n");
6016 my_strcat(inbuf, "OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED\n");
6017 my_strcat(inbuf, "WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n");
6018 my_strcat(inbuf, "ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY\n");
6019 my_strcat(inbuf, "DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL\n");
6020 my_strcat(inbuf, "DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE\n");
6021 my_strcat(inbuf, "GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS\n");
6022 my_strcat(inbuf, "INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,\n");
6023 my_strcat(inbuf, "WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING\n");
6024 my_strcat(inbuf, "NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS\n");
6025 my_strcat(inbuf, "SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n");
6026 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6027 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6028 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6029 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6030 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6031 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6032 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6033 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6034 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6035 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6036 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6037 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6038 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6039 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6040 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6041 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6042 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6043 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6044 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6045 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6046 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6047 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6048 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6049 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6050 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6051 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6052 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6053 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6054 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6055 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6056 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6057 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6058 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6059 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6060 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6061 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6062 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6063 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6064 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6065 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6066 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6067 my_strcat(inbuf, "ababababababababababababababababababababababababababababababab");
6068 my_strcat(inbuf, " GNU GENERAL PUBLIC LICENSE\n");
6069 my_strcat(inbuf, " Version 2, June 1991\n");
6070 my_strcat(inbuf, "\n");
6071 my_strcat(inbuf, " Copyright (C) 1989, 1991 Free Software Foundation, Inc.\n");
6072 my_strcat(inbuf, " 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n");
6073 my_strcat(inbuf, " Everyone is permitted to copy and distribute verbatim copies\n");
6074 my_strcat(inbuf, " of this license document, but changing it is not allowed.\n");
6075 my_strcat(inbuf, "\n");
6076 my_strcat(inbuf, " Preamble\n");
6077 my_strcat(inbuf, "\n");
6078 my_strcat(inbuf, " The licenses for most software are designed to take away your\n");
6079 my_strcat(inbuf, "freedom to share and change it. By contrast, the GNU General Public\n");
6080 my_strcat(inbuf, "License is intended to guarantee your freedom to share and change free\n");
6081 my_strcat(inbuf, "software--to make sure the software is free for all its users. This\n");
6082 my_strcat(inbuf, "General Public License applies to most of the Free Software\n");
6083 my_strcat(inbuf, "Foundation's software and to any other program whose authors commit to\n");
6084 my_strcat(inbuf, "using it. (Some other Free Software Foundation software is covered by\n");
6085 my_strcat(inbuf, "the GNU Library General Public License instead.) You can apply it to\n");
6086 my_strcat(inbuf, "your programs, too.\n");
6087 my_strcat(inbuf, "\n");
6088 my_strcat(inbuf, " When we speak of free software, we are referring to freedom, not\n");
6089 my_strcat(inbuf, "price. Our General Public Licenses are designed to make sure that you\n");
6090 my_strcat(inbuf, "have the freedom to distribute copies of free software (and charge for\n");
6091 my_strcat(inbuf, "this service if you wish), that you receive source code or can get it\n");
6092 my_strcat(inbuf, "if you want it, that you can change the software or use pieces of it\n");
6093 my_strcat(inbuf, "in new free programs; and that you know you can do these things.\n");
6094 my_strcat(inbuf, "\n");
6095 my_strcat(inbuf, " To protect your rights, we need to make restrictions that forbid\n");
6096 my_strcat(inbuf, "anyone to deny you these rights or to ask you to surrender the rights.\n");
6097 my_strcat(inbuf, "These restrictions translate to certain responsibilities for you if you\n");
6098 my_strcat(inbuf, "distribute copies of the software, or if you modify it.\n");
6099 my_strcat(inbuf, "\n");
6100 my_strcat(inbuf, " For example, if you distribute copies of such a program, whether\n");
6101 my_strcat(inbuf, "gratis or for a fee, you must give the recipients all the rights that\n");
6102 my_strcat(inbuf, "you have. You must make sure that they, too, receive or can get the\n");
6103 my_strcat(inbuf, "source code. And you must show them these terms so they know their\n");
6104 my_strcat(inbuf, "rights.\n");
6105 my_strcat(inbuf, "\n");
6106 my_strcat(inbuf, " We protect your rights with two steps: (1) copyright the software, and\n");
6107 my_strcat(inbuf, "(2) offer you this license which gives you legal permission to copy,\n");
6108 my_strcat(inbuf, "distribute and/or modify the software.\n");
6109 my_strcat(inbuf, "\n");
6110 my_strcat(inbuf, " Also, for each author's protection and ours, we want to make certain\n");
6111 my_strcat(inbuf, "that everyone understands that there is no warranty for this free\n");
6112 my_strcat(inbuf, "software. If the software is modified by someone else and passed on, we\n");
6113 my_strcat(inbuf, "want its recipients to know that what they have is not the original, so\n");
6114 my_strcat(inbuf, "that any problems introduced by others will not reflect on the original\n");
6115 my_strcat(inbuf, "authors' reputations.\n");
6116 my_strcat(inbuf, "\n");
6117 my_strcat(inbuf, " Finally, any free program is threatened constantly by software\n");
6118 my_strcat(inbuf, "patents. We wish to avoid the danger that redistributors of a free\n");
6119 my_strcat(inbuf, "program will individually obtain patent licenses, in effect making the\n");
6120 my_strcat(inbuf, "program proprietary. To prevent this, we have made it clear that any\n");
6121 my_strcat(inbuf, "patent must be licensed for everyone's free use or not licensed at all.\n");
6122 my_strcat(inbuf, "\n");
6123 my_strcat(inbuf, " The precise terms and conditions for copying, distribution and\n");
6124 my_strcat(inbuf, "modification follow.\n");
6125 my_strcat(inbuf, "\n");
6126 my_strcat(inbuf, " GNU GENERAL PUBLIC LICENSE\n");
6127 my_strcat(inbuf, " TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION\n");
6128 my_strcat(inbuf, "\n");
6129 my_strcat(inbuf, " 0. This License applies to any program or other work which contains\n");
6130 my_strcat(inbuf, "a notice placed by the copyright holder saying it may be distributed\n");
6131 my_strcat(inbuf, "under the terms of this General Public License. The Program, below,\n");
6132 my_strcat(inbuf, "refers to any such program or work, and a work based on the Program\n");
6133 my_strcat(inbuf, "means either the Program or any derivative work under copyright law:\n");
6134 my_strcat(inbuf, "that is to say, a work containing the Program or a portion of it,\n");
6135 my_strcat(inbuf, "either verbatim or with modifications and/or translated into another\n");
6136 my_strcat(inbuf, "language. (Hereinafter, translation is included without limitation in\n");
6137 my_strcat(inbuf, "the term modification.) Each licensee is addressed as you.\n");
6138 my_strcat(inbuf, "\n");
6139 my_strcat(inbuf, "Activities other than copying, distribution and modification are not\n");
6140 my_strcat(inbuf, "covered by this License; they are outside its scope. The act of\n");
6141 my_strcat(inbuf, "running the Program is not restricted, and the output from the Program\n");
6142 my_strcat(inbuf, "is covered only if its contents constitute a work based on the\n");
6143 my_strcat(inbuf, "Program (independent of having been made by running the Program).\n");
6144 my_strcat(inbuf, "Whether that is true depends on what the Program does.\n");
6145 my_strcat(inbuf, "\n");
6146 my_strcat(inbuf, " 1. You may copy and distribute verbatim copies of the Program's\n");
6147 my_strcat(inbuf, "source code as you receive it, in any medium, provided that you\n");
6148 my_strcat(inbuf, "conspicuously and appropriately publish on each copy an appropriate\n");
6149 my_strcat(inbuf, "copyright notice and disclaimer of warranty; keep intact all the\n");
6150 my_strcat(inbuf, "notices that refer to this License and to the absence of any warranty;\n");
6151 my_strcat(inbuf, "and give any other recipients of the Program a copy of this License\n");
6152 my_strcat(inbuf, "along with the Program.\n");
6153 my_strcat(inbuf, "\n");
6154 my_strcat(inbuf, "You may charge a fee for the physical act of transferring a copy, and\n");
6155 my_strcat(inbuf, "you may at your option offer warranty protection in exchange for a fee.\n");
6156 my_strcat(inbuf, "\n");
6157 my_strcat(inbuf, " 2. You may modify your copy or copies of the Program or any portion\n");
6158 my_strcat(inbuf, "of it, thus forming a work based on the Program, and copy and\n");
6159 my_strcat(inbuf, "distribute such modifications or work under the terms of Section 1\n");
6160 my_strcat(inbuf, "above, provided that you also meet all of these conditions:\n");
6161 my_strcat(inbuf, "\n");
6162 my_strcat(inbuf, " a) You must cause the modified files to carry prominent notices\n");
6163 my_strcat(inbuf, " stating that you changed the files and the date of any change.\n");
6164 my_strcat(inbuf, "\n");
6165 my_strcat(inbuf, " b) You must cause any work that you distribute or publish, that in\n");
6166 my_strcat(inbuf, " whole or in part contains or is derived from the Program or any\n");
6167 my_strcat(inbuf, " part thereof, to be licensed as a whole at no charge to all third\n");
6168 my_strcat(inbuf, " parties under the terms of this License.\n");
6169 my_strcat(inbuf, "\n");
6170 my_strcat(inbuf, " c) If the modified program normally reads commands interactively\n");
6171 my_strcat(inbuf, " when run, you must cause it, when started running for such\n");
6172 my_strcat(inbuf, " interactive use in the most ordinary way, to print or display an\n");
6173 my_strcat(inbuf, " announcement including an appropriate copyright notice and a\n");
6174 my_strcat(inbuf, " notice that there is no warranty (or else, saying that you provide\n");
6175 my_strcat(inbuf, " a warranty) and that users may redistribute the program under\n");
6176 my_strcat(inbuf, " these conditions, and telling the user how to view a copy of this\n");
6177 my_strcat(inbuf, " License. (Exception: if the Program itself is interactive but\n");
6178 my_strcat(inbuf, " does not normally print such an announcement, your work based on\n");
6179 my_strcat(inbuf, " the Program is not required to print an announcement.)\n");
6180 my_strcat(inbuf, "\n");
6181 my_strcat(inbuf, "These requirements apply to the modified work as a whole. If\n");
6182 my_strcat(inbuf, "identifiable sections of that work are not derived from the Program,\n");
6183 my_strcat(inbuf, "and can be reasonably considered independent and separate works in\n");
6184 my_strcat(inbuf, "themselves, then this License, and its terms, do not apply to those\n");
6185 my_strcat(inbuf, "sections when you distribute them as separate works. But when you\n");
6186 my_strcat(inbuf, "distribute the same sections as part of a whole which is a work based\n");
6187 my_strcat(inbuf, "on the Program, the distribution of the whole must be on the terms of\n");
6188 my_strcat(inbuf, "this License, whose permissions for other licensees extend to the\n");
6189 my_strcat(inbuf, "entire whole, and thus to each and every part regardless of who wrote it.\n");
6190 my_strcat(inbuf, "\n");
6191 my_strcat(inbuf, "Thus, it is not the intent of this section to claim rights or contest\n");
6192 my_strcat(inbuf, "your rights to work written entirely by you; rather, the intent is to\n");
6193 my_strcat(inbuf, "exercise the right to control the distribution of derivative or\n");
6194 my_strcat(inbuf, "collective works based on the Program.\n");
6195 my_strcat(inbuf, "\n");
6196 my_strcat(inbuf, "In addition, mere aggregation of another work not based on the Program\n");
6197 my_strcat(inbuf, "with the Program (or with a work based on the Program) on a volume of\n");
6198 my_strcat(inbuf, "a storage or distribution medium does not bring the other work under\n");
6199 my_strcat(inbuf, "the scope of this License.\n");
6200 my_strcat(inbuf, "\n");
6201 my_strcat(inbuf, " 3. You may copy and distribute the Program (or a work based on it,\n");
6202 my_strcat(inbuf, "under Section 2) in object code or executable form under the terms of\n");
6203 my_strcat(inbuf, "Sections 1 and 2 above provided that you also do one of the following:\n");
6204 my_strcat(inbuf, "\n");
6205 my_strcat(inbuf, " a) Accompany it with the complete corresponding machine-readable\n");
6206 my_strcat(inbuf, " source code, which must be distributed under the terms of Sections\n");
6207 my_strcat(inbuf, " 1 and 2 above on a medium customarily used for software interchange; or,\n");
6208 my_strcat(inbuf, "\n");
6209 my_strcat(inbuf, " b) Accompany it with a written offer, valid for at least three\n");
6210 my_strcat(inbuf, " years, to give any third party, for a charge no more than your\n");
6211 my_strcat(inbuf, " cost of physically performing source distribution, a complete\n");
6212 my_strcat(inbuf, " machine-readable copy of the corresponding source code, to be\n");
6213 my_strcat(inbuf, " distributed under the terms of Sections 1 and 2 above on a medium\n");
6214 my_strcat(inbuf, " customarily used for software interchange; or,\n");
6215 my_strcat(inbuf, "\n");
6216 my_strcat(inbuf, " c) Accompany it with the information you received as to the offer\n");
6217 my_strcat(inbuf, " to distribute corresponding source code. (This alternative is\n");
6218 my_strcat(inbuf, " allowed only for noncommercial distribution and only if you\n");
6219 my_strcat(inbuf, " received the program in object code or executable form with such\n");
6220 my_strcat(inbuf, " an offer, in accord with Subsection b above.)\n");
6221 my_strcat(inbuf, "\n");
6222 my_strcat(inbuf, "The source code for a work means the preferred form of the work for\n");
6223 my_strcat(inbuf, "making modifications to it. For an executable work, complete source\n");
6224 my_strcat(inbuf, "code means all the source code for all modules it contains, plus any\n");
6225 my_strcat(inbuf, "associated interface definition files, plus the scripts used to\n");
6226 my_strcat(inbuf, "control compilation and installation of the executable. However, as a\n");
6227 my_strcat(inbuf, "special exception, the source code distributed need not include\n");
6228 my_strcat(inbuf, "anything that is normally distributed (in either source or binary\n");
6229 my_strcat(inbuf, "form) with the major components (compiler, kernel, and so on) of the\n");
6230 my_strcat(inbuf, "operating system on which the executable runs, unless that component\n");
6231 my_strcat(inbuf, "itself accompanies the executable.\n");
6232 my_strcat(inbuf, "\n");
6233 my_strcat(inbuf, "If distribution of executable or object code is made by offering\n");
6234 my_strcat(inbuf, "access to copy from a designated place, then offering equivalent\n");
6235 my_strcat(inbuf, "access to copy the source code from the same place counts as\n");
6236 my_strcat(inbuf, "distribution of the source code, even though third parties are not\n");
6237 my_strcat(inbuf, "compelled to copy the source along with the object code.\n");
6238 my_strcat(inbuf, "\n");
6239 my_strcat(inbuf, " 4. You may not copy, modify, sublicense, or distribute the Program\n");
6240 my_strcat(inbuf, "except as expressly provided under this License. Any attempt\n");
6241 my_strcat(inbuf, "otherwise to copy, modify, sublicense or distribute the Program is\n");
6242 my_strcat(inbuf, "void, and will automatically terminate your rights under this License.\n");
6243 my_strcat(inbuf, "However, parties who have received copies, or rights, from you under\n");
6244 my_strcat(inbuf, "this License will not have their licenses terminated so long as such\n");
6245 my_strcat(inbuf, "parties remain in full compliance.\n");
6246 my_strcat(inbuf, "\n");
6247 my_strcat(inbuf, " 5. You are not required to accept this License, since you have not\n");
6248 my_strcat(inbuf, "signed it. However, nothing else grants you permission to modify or\n");
6249 my_strcat(inbuf, "distribute the Program or its derivative works. These actions are\n");
6250 my_strcat(inbuf, "prohibited by law if you do not accept this License. Therefore, by\n");
6251 my_strcat(inbuf, "modifying or distributing the Program (or any work based on the\n");
6252 my_strcat(inbuf, "Program), you indicate your acceptance of this License to do so, and\n");
6253 my_strcat(inbuf, "all its terms and conditions for copying, distributing or modifying\n");
6254 my_strcat(inbuf, "the Program or works based on it.\n");
6255 my_strcat(inbuf, "\n");
6256 my_strcat(inbuf, " 6. Each time you redistribute the Program (or any work based on the\n");
6257 my_strcat(inbuf, "Program), the recipient automatically receives a license from the\n");
6258 my_strcat(inbuf, "original licensor to copy, distribute or modify the Program subject to\n");
6259 my_strcat(inbuf, "these terms and conditions. You may not impose any further\n");
6260 my_strcat(inbuf, "restrictions on the recipients' exercise of the rights granted herein.\n");
6261 my_strcat(inbuf, "You are not responsible for enforcing compliance by third parties to\n");
6262 my_strcat(inbuf, "this License.\n");
6263 my_strcat(inbuf, "\n");
6264 my_strcat(inbuf, " 7. If, as a consequence of a court judgment or allegation of patent\n");
6265 my_strcat(inbuf, "infringement or for any other reason (not limited to patent issues),\n");
6266 my_strcat(inbuf, "conditions are imposed on you (whether by court order, agreement or\n");
6267 my_strcat(inbuf, "otherwise) that contradict the conditions of this License, they do not\n");
6268 my_strcat(inbuf, "excuse you from the conditions of this License. If you cannot\n");
6269 my_strcat(inbuf, "distribute so as to satisfy simultaneously your obligations under this\n");
6270 my_strcat(inbuf, "License and any other pertinent obligations, then as a consequence you\n");
6271 my_strcat(inbuf, "may not distribute the Program at all. For example, if a patent\n");
6272 my_strcat(inbuf, "license would not permit royalty-free redistribution of the Program by\n");
6273 my_strcat(inbuf, "all those who receive copies directly or indirectly through you, then\n");
6274 my_strcat(inbuf, "the only way you could satisfy both it and this License would be to\n");
6275 my_strcat(inbuf, "refrain entirely from distribution of the Program.\n");
6276 my_strcat(inbuf, "\n");
6277 my_strcat(inbuf, "If any portion of this section is held invalid or unenforceable under\n");
6278 my_strcat(inbuf, "any particular circumstance, the balance of the section is intended to\n");
6279 my_strcat(inbuf, "apply and the section as a whole is intended to apply in other\n");
6280 my_strcat(inbuf, "circumstances.\n");
6281 my_strcat(inbuf, "\n");
6282 my_strcat(inbuf, "It is not the purpose of this section to induce you to infringe any\n");
6283 my_strcat(inbuf, "patents or other property right claims or to contest validity of any\n");
6284 my_strcat(inbuf, "such claims; this section has the sole purpose of protecting the\n");
6285 my_strcat(inbuf, "integrity of the free software distribution system, which is\n");
6286 my_strcat(inbuf, "implemented by public license practices. Many people have made\n");
6287 my_strcat(inbuf, "generous contributions to the wide range of software distributed\n");
6288 my_strcat(inbuf, "through that system in reliance on consistent application of that\n");
6289 my_strcat(inbuf, "system; it is up to the author/donor to decide if he or she is willing\n");
6290 my_strcat(inbuf, "to distribute software through any other system and a licensee cannot\n");
6291 my_strcat(inbuf, "impose that choice.\n");
6292 my_strcat(inbuf, "\n");
6293 my_strcat(inbuf, "This section is intended to make thoroughly clear what is believed to\n");
6294 my_strcat(inbuf, "be a consequence of the rest of this License.\n");
6295 my_strcat(inbuf, "\n");
6296 my_strcat(inbuf, " 8. If the distribution and/or use of the Program is restricted in\n");
6297 my_strcat(inbuf, "certain countries either by patents or by copyrighted interfaces, the\n");
6298 my_strcat(inbuf, "original copyright holder who places the Program under this License\n");
6299 my_strcat(inbuf, "may add an explicit geographical distribution limitation excluding\n");
6300 my_strcat(inbuf, "those countries, so that distribution is permitted only in or among\n");
6301 my_strcat(inbuf, "countries not thus excluded. In such case, this License incorporates\n");
6302 my_strcat(inbuf, "the limitation as if written in the body of this License.\n");
6303 my_strcat(inbuf, "\n");
6304 my_strcat(inbuf, " 9. The Free Software Foundation may publish revised and/or new versions\n");
6305 my_strcat(inbuf, "of the General Public License from time to time. Such new versions will\n");
6306 my_strcat(inbuf, "be similar in spirit to the present version, but may differ in detail to\n");
6307 my_strcat(inbuf, "address new problems or concerns.\n");
6308 my_strcat(inbuf, "\n");
6309 my_strcat(inbuf, "Each version is given a distinguishing version number. If the Program\n");
6310 my_strcat(inbuf, "specifies a version number of this License which applies to it and any\n");
6311 my_strcat(inbuf, "later version, you have the option of following the terms and conditions\n");
6312 my_strcat(inbuf, "either of that version or of any later version published by the Free\n");
6313 my_strcat(inbuf, "Software Foundation. If the Program does not specify a version number of\n");
6314 my_strcat(inbuf, "this License, you may choose any version ever published by the Free Software\n");
6315 my_strcat(inbuf, "Foundation.\n");
6316 my_strcat(inbuf, "\n");
6317 my_strcat(inbuf, " 10. If you wish to incorporate parts of the Program into other free\n");
6318 my_strcat(inbuf, "programs whose distribution conditions are different, write to the author\n");
6319 my_strcat(inbuf, "to ask for permission. For software which is copyrighted by the Free\n");
6320 my_strcat(inbuf, "Software Foundation, write to the Free Software Foundation; we sometimes\n");
6321 my_strcat(inbuf, "make exceptions for this. Our decision will be guided by the two goals\n");
6322 my_strcat(inbuf, "of preserving the free status of all derivatives of our free software and\n");
6323 my_strcat(inbuf, "of promoting the sharing and reuse of software generally.\n");
6324 my_strcat(inbuf, "\n");
6325 my_strcat(inbuf, " NO WARRANTY\n");
6326 my_strcat(inbuf, "\n");
6327 my_strcat(inbuf, " 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY\n");
6328 my_strcat(inbuf, "FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN\n");
6329 my_strcat(inbuf, "OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES\n");
6330 my_strcat(inbuf, "PROVIDE THE PROGRAM AS IS WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED\n");
6331 my_strcat(inbuf, "OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF\n");
6332 my_strcat(inbuf, "MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS\n");
6333 my_strcat(inbuf, "TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE\n");
6334 my_strcat(inbuf, "PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,\n");
6335 my_strcat(inbuf, "REPAIR OR CORRECTION.\n");
6336 my_strcat(inbuf, "\n");
6337 my_strcat(inbuf, " 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING\n");
6338 my_strcat(inbuf, "WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR\n");
6339 my_strcat(inbuf, "REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,\n");
6340 my_strcat(inbuf, "INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING\n");
6341 my_strcat(inbuf, "OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED\n");
6342 my_strcat(inbuf, "TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY\n");
6343 my_strcat(inbuf, "YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER\n");
6344 my_strcat(inbuf, "PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE\n");
6345 my_strcat(inbuf, "POSSIBILITY OF SUCH DAMAGES.\n");
6346 my_strcat(inbuf, "\n");
6347 my_strcat(inbuf, " END OF TERMS AND CONDITIONS\n");
6348 my_strcat(inbuf, "\n");
6349 my_strcat(inbuf, " How to Apply These Terms to Your New Programs\n");
6350 my_strcat(inbuf, "\n");
6351 my_strcat(inbuf, " If you develop a new program, and you want it to be of the greatest\n");
6352 my_strcat(inbuf, "possible use to the public, the best way to achieve this is to make it\n");
6353 my_strcat(inbuf, "free software which everyone can redistribute and change under these terms.\n");
6354 my_strcat(inbuf, "\n");
6355 my_strcat(inbuf, " To do so, attach the following notices to the program. It is safest\n");
6356 my_strcat(inbuf, "to attach them to the start of each source file to most effectively\n");
6357 my_strcat(inbuf, "convey the exclusion of warranty; and each file should have at least\n");
6358 my_strcat(inbuf, "the copyright line and a pointer to where the full notice is found.\n");
6359 my_strcat(inbuf, "\n");
6360 my_strcat(inbuf, " <one line to give the program's name and a brief idea of what it does.>\n");
6361 my_strcat(inbuf, " Copyright (C) <year> <name of author>\n");
6362 my_strcat(inbuf, "\n");
6363 my_strcat(inbuf, " This program is free software; you can redistribute it and/or modify\n");
6364 my_strcat(inbuf, " it under the terms of the GNU General Public License as published by\n");
6365 my_strcat(inbuf, " the Free Software Foundation; either version 2 of the License, or\n");
6366 my_strcat(inbuf, " (at your option) any later version.\n");
6367 my_strcat(inbuf, "\n");
6368 my_strcat(inbuf, " This program is distributed in the hope that it will be useful,\n");
6369 my_strcat(inbuf, " but WITHOUT ANY WARRANTY; without even the implied warranty of\n");
6370 my_strcat(inbuf, " MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n");
6371 my_strcat(inbuf, " GNU General Public License for more details.\n");
6372 my_strcat(inbuf, "\n");
6373 my_strcat(inbuf, " You should have received a copy of the GNU General Public License\n");
6374 my_strcat(inbuf, " along with this program; if not, write to the Free Software\n");
6375 my_strcat(inbuf, " Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n");
6376 my_strcat(inbuf, "\n");
6377 my_strcat(inbuf, "\n");
6378 my_strcat(inbuf, "Also add information on how to contact you by electronic and paper mail.\n");
6379 my_strcat(inbuf, "\n");
6380 my_strcat(inbuf, "If the program is interactive, make it output a short notice like this\n");
6381 my_strcat(inbuf, "when it starts in an interactive mode:\n");
6382 my_strcat(inbuf, "\n");
6383 my_strcat(inbuf, " Gnomovision version 69, Copyright (C) year name of author\n");
6384 my_strcat(inbuf, " Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.\n");
6385 my_strcat(inbuf, " This is free software, and you are welcome to redistribute it\n");
6386 my_strcat(inbuf, " under certain conditions; type `show c' for details.\n");
6387 my_strcat(inbuf, "\n");
6388 my_strcat(inbuf, "The hypothetical commands `show w' and `show c' should show the appropriate\n");
6389 my_strcat(inbuf, "parts of the General Public License. Of course, the commands you use may\n");
6390 my_strcat(inbuf, "be called something other than `show w' and `show c'; they could even be\n");
6391 my_strcat(inbuf, "mouse-clicks or menu items--whatever suits your program.\n");
6392 my_strcat(inbuf, "\n");
6393 my_strcat(inbuf, "You should also get your employer (if you work as a programmer) or your\n");
6394 my_strcat(inbuf, "school, if any, to sign a copyright disclaimer for the program, if\n");
6395 my_strcat(inbuf, "necessary. Here is a sample; alter the names:\n");
6396 my_strcat(inbuf, "\n");
6397 my_strcat(inbuf, " Yoyodyne, Inc., hereby disclaims all copyright interest in the program\n");
6398 my_strcat(inbuf, " `Gnomovision' (which makes passes at compilers) written by James Hacker.\n");
6399 my_strcat(inbuf, "\n");
6400 my_strcat(inbuf, " <signature of Ty Coon>, 1 April 1989\n");
6401 my_strcat(inbuf, " Ty Coon, President of Vice\n");
6402 my_strcat(inbuf, "\n");
6403 my_strcat(inbuf, "This General Public License does not permit incorporating your program into\n");
6404 my_strcat(inbuf, "proprietary programs. If your program is a subroutine library, you may\n");
6405 my_strcat(inbuf, "consider it more useful to permit linking proprietary applications with the\n");
6406 my_strcat(inbuf, "library. If this is what you want to do, use the GNU Library General\n");
6407 my_strcat(inbuf, "Public License instead of this License.\n");
6408
6409 my_strcat(inbuf, "\n");
6410 }
6411
6412 #include <stdio.h>
6413 #include "tests/malloc.h"
6414 #include <assert.h>
6415
6416 /* For providing services. */
g_serviceFn(HWord arg1,HWord arg2)6417 static HWord g_serviceFn ( HWord arg1, HWord arg2 )
6418 {
6419 switch (arg1) {
6420 case 0: /* EXIT */
6421 exit(0);
6422 case 1: /* PUTC */
6423 putchar(arg2);
6424 return 0;
6425 case 2: /* MALLOC */
6426 return (HWord)malloc(arg2);
6427 case 3: /* FREE */
6428 free((void*)arg2);
6429 return 0;
6430 default:
6431 assert(0);
6432 }
6433 }
6434
6435 static char *bzerrorstrings[] = {
6436 "OK"
6437 ,"SEQUENCE_ERROR"
6438 ,"PARAM_ERROR"
6439 ,"MEM_ERROR"
6440 ,"DATA_ERROR"
6441 ,"DATA_ERROR_MAGIC"
6442 ,"IO_ERROR"
6443 ,"UNEXPECTED_EOF"
6444 ,"OUTBUFF_FULL"
6445 ,"CONFIG_ERROR"
6446 ,"???" /* for future */
6447 ,"???" /* for future */
6448 ,"???" /* for future */
6449 ,"???" /* for future */
6450 ,"???" /* for future */
6451 ,"???" /* for future */
6452 };
6453
6454 // If given a cmd line arg, behave as a correctness regtest
6455 // (run fast and be verbose). If not, run for a long time
6456 // which is what is needed for the performance suite.
main(int argc,char ** argv)6457 int main ( int argc, char** argv )
6458 {
6459 int r;
6460 int bit;
6461 int i;
6462
6463 int regtest;
6464 assert(argc == 1 || argc == 2);
6465 regtest = argc==2;
6466
6467 serviceFn = g_serviceFn;
6468
6469 set_inbuf();
6470 nIn = vex_strlen(inbuf)+1;
6471 vex_printf( "%d bytes read\n", nIn );
6472
6473 nZ = M_BLOCK;
6474 r = BZ2_bzBuffToBuffCompress (
6475 zbuf, &nZ, inbuf, nIn, 9, 3/*verb*/, 30 );
6476
6477 if (r != BZ_OK) {
6478 vex_printf("initial compress failed!\n");
6479 (*serviceFn)(0,0);
6480 }
6481 vex_printf( "%d after compression\n", nZ );
6482
6483 for (bit = 0; bit < nZ*8; bit += (bit < 35 ? 1 : (regtest?2377:137))) {
6484 if (regtest)
6485 vex_printf( "bit %d ", bit );
6486 flip_bit ( bit );
6487 nOut = M_BLOCK_OUT;
6488 r = BZ2_bzBuffToBuffDecompress (
6489 outbuf, &nOut, zbuf, nZ, 1/*small*/, 0 );
6490 if (regtest)
6491 vex_printf( " %d %s ", r, bzerrorstrings[-r] );
6492
6493 if (r != BZ_OK) {
6494 if (regtest)
6495 vex_printf( "\n" );
6496 } else {
6497 if (nOut != nIn) {
6498 vex_printf( "nIn/nOut mismatch %d %d\n", nIn, nOut );
6499 (*serviceFn)(0,0);
6500 } else {
6501 for (i = 0; i < nOut; i++)
6502 if (inbuf[i] != outbuf[i]) {
6503 vex_printf( "mismatch at %d\n", i );
6504 (*serviceFn)(0,0);
6505 }
6506 if (i == nOut) vex_printf( "really ok!\n" );
6507 }
6508 }
6509
6510 flip_bit ( bit );
6511 }
6512
6513 #if 0
6514 assert (nOut == nIn);
6515 for (i = 0; i < nOut; i++) {
6516 if (inbuf[i] != outbuf[i]) {
6517 vex_printf( "difference at %d !\n", i );
6518 return 1;
6519 }
6520 }
6521 #endif
6522
6523 vex_printf( "all ok\n" );
6524 (*serviceFn)(0,0);
6525 /*NOTREACHED*/
6526 return 0;
6527 }
6528