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