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