diff options
author | Julian Seward <jseward@acm.org> | 1998-08-23 22:13:13 +0200 |
---|---|---|
committer | Julian Seward <jseward@acm.org> | 1998-08-23 22:13:13 +0200 |
commit | 977101ad5f833f5c0a574bfeea408e5301a6b052 (patch) | |
tree | fc1e8fed202869c116cbf6b8c362456042494a0a /bzip2.c | |
parent | 1eb67a9d8f7f05ae310bc9ef297d176f3a3f8a37 (diff) | |
download | bzip2-977101ad5f833f5c0a574bfeea408e5301a6b052.tar.gz bzip2-977101ad5f833f5c0a574bfeea408e5301a6b052.tar.bz2 bzip2-977101ad5f833f5c0a574bfeea408e5301a6b052.zip |
bzip2-0.9.0cbzip2-0.9.0c
Diffstat (limited to 'bzip2.c')
-rw-r--r-- | bzip2.c | 3389 |
1 files changed, 434 insertions, 2955 deletions
@@ -4,28 +4,45 @@ | |||
4 | /*-----------------------------------------------------------*/ | 4 | /*-----------------------------------------------------------*/ |
5 | 5 | ||
6 | /*-- | 6 | /*-- |
7 | This program is bzip2, a lossless, block-sorting data compressor, | 7 | This file is a part of bzip2 and/or libbzip2, a program and |
8 | version 0.1pl2, dated 29-Aug-1997. | 8 | library for lossless, block-sorting data compression. |
9 | 9 | ||
10 | Copyright (C) 1996, 1997 by Julian Seward. | 10 | Copyright (C) 1996-1998 Julian R Seward. All rights reserved. |
11 | Guildford, Surrey, UK | 11 | |
12 | email: jseward@acm.org | 12 | Redistribution and use in source and binary forms, with or without |
13 | 13 | modification, are permitted provided that the following conditions | |
14 | This program is free software; you can redistribute it and/or modify | 14 | are met: |
15 | it under the terms of the GNU General Public License as published by | 15 | |
16 | the Free Software Foundation; either version 2 of the License, or | 16 | 1. Redistributions of source code must retain the above copyright |
17 | (at your option) any later version. | 17 | notice, this list of conditions and the following disclaimer. |
18 | 18 | ||
19 | This program is distributed in the hope that it will be useful, | 19 | 2. The origin of this software must not be misrepresented; you must |
20 | but WITHOUT ANY WARRANTY; without even the implied warranty of | 20 | not claim that you wrote the original software. If you use this |
21 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | 21 | software in a product, an acknowledgment in the product |
22 | GNU General Public License for more details. | 22 | documentation would be appreciated but is not required. |
23 | 23 | ||
24 | You should have received a copy of the GNU General Public License | 24 | 3. Altered source versions must be plainly marked as such, and must |
25 | along with this program; if not, write to the Free Software | 25 | not be misrepresented as being the original software. |
26 | Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | 26 | |
27 | 27 | 4. The name of the author may not be used to endorse or promote | |
28 | The GNU General Public License is contained in the file LICENSE. | 28 | products derived from this software without specific prior written |
29 | permission. | ||
30 | |||
31 | THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS | ||
32 | OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | ||
33 | WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
34 | ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY | ||
35 | DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
36 | DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE | ||
37 | GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
38 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, | ||
39 | WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING | ||
40 | NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | ||
41 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
42 | |||
43 | Julian Seward, Guildford, Surrey, UK. | ||
44 | jseward@acm.org | ||
45 | bzip2/libbzip2 version 0.9.0c of 18 October 1998 | ||
29 | 46 | ||
30 | This program is based on (at least) the work of: | 47 | This program is based on (at least) the work of: |
31 | Mike Burrows | 48 | Mike Burrows |
@@ -37,21 +54,23 @@ | |||
37 | Robert Sedgewick | 54 | Robert Sedgewick |
38 | Jon L. Bentley | 55 | Jon L. Bentley |
39 | 56 | ||
40 | For more information on these sources, see the file ALGORITHMS. | 57 | For more information on these sources, see the manual. |
41 | --*/ | 58 | --*/ |
42 | 59 | ||
60 | |||
43 | /*----------------------------------------------------*/ | 61 | /*----------------------------------------------------*/ |
44 | /*--- IMPORTANT ---*/ | 62 | /*--- IMPORTANT ---*/ |
45 | /*----------------------------------------------------*/ | 63 | /*----------------------------------------------------*/ |
46 | 64 | ||
47 | /*-- | 65 | /*-- |
48 | WARNING: | 66 | WARNING: |
49 | This program (attempts to) compress data by performing several | 67 | This program and library (attempts to) compress data by |
50 | non-trivial transformations on it. Unless you are 100% familiar | 68 | performing several non-trivial transformations on it. |
51 | with *all* the algorithms contained herein, and with the | 69 | Unless you are 100% familiar with *all* the algorithms |
52 | consequences of modifying them, you should NOT meddle with the | 70 | contained herein, and with the consequences of modifying them, |
53 | compression or decompression machinery. Incorrect changes can | 71 | you should NOT meddle with the compression or decompression |
54 | and very likely *will* lead to disasterous loss of data. | 72 | machinery. Incorrect changes can and very likely *will* |
73 | lead to disasterous loss of data. | ||
55 | 74 | ||
56 | DISCLAIMER: | 75 | DISCLAIMER: |
57 | I TAKE NO RESPONSIBILITY FOR ANY LOSS OF DATA ARISING FROM THE | 76 | I TAKE NO RESPONSIBILITY FOR ANY LOSS OF DATA ARISING FROM THE |
@@ -65,18 +84,19 @@ | |||
65 | of various special cases in the code which occur with very low | 84 | of various special cases in the code which occur with very low |
66 | but non-zero probability make it impossible to rule out the | 85 | but non-zero probability make it impossible to rule out the |
67 | possibility of bugs remaining in the program. DO NOT COMPRESS | 86 | possibility of bugs remaining in the program. DO NOT COMPRESS |
68 | ANY DATA WITH THIS PROGRAM UNLESS YOU ARE PREPARED TO ACCEPT THE | 87 | ANY DATA WITH THIS PROGRAM AND/OR LIBRARY UNLESS YOU ARE PREPARED |
69 | POSSIBILITY, HOWEVER SMALL, THAT THE DATA WILL NOT BE RECOVERABLE. | 88 | TO ACCEPT THE POSSIBILITY, HOWEVER SMALL, THAT THE DATA WILL |
89 | NOT BE RECOVERABLE. | ||
70 | 90 | ||
71 | That is not to say this program is inherently unreliable. | 91 | That is not to say this program is inherently unreliable. |
72 | Indeed, I very much hope the opposite is true. bzip2 has been | 92 | Indeed, I very much hope the opposite is true. bzip2/libbzip2 |
73 | carefully constructed and extensively tested. | 93 | has been carefully constructed and extensively tested. |
74 | 94 | ||
75 | PATENTS: | 95 | PATENTS: |
76 | To the best of my knowledge, bzip2 does not use any patented | 96 | To the best of my knowledge, bzip2/libbzip2 does not use any |
77 | algorithms. However, I do not have the resources available to | 97 | patented algorithms. However, I do not have the resources |
78 | carry out a full patent search. Therefore I cannot give any | 98 | available to carry out a full patent search. Therefore I cannot |
79 | guarantee of the above statement. | 99 | give any guarantee of the above statement. |
80 | --*/ | 100 | --*/ |
81 | 101 | ||
82 | 102 | ||
@@ -103,6 +123,10 @@ | |||
103 | --*/ | 123 | --*/ |
104 | #define BZ_LCCWIN32 0 | 124 | #define BZ_LCCWIN32 0 |
105 | 125 | ||
126 | #ifdef _WIN32 | ||
127 | #define BZ_LCCWIN32 1 | ||
128 | #define BZ_UNIX 0 | ||
129 | #endif | ||
106 | 130 | ||
107 | 131 | ||
108 | /*---------------------------------------------*/ | 132 | /*---------------------------------------------*/ |
@@ -112,12 +136,10 @@ | |||
112 | 136 | ||
113 | #include <stdio.h> | 137 | #include <stdio.h> |
114 | #include <stdlib.h> | 138 | #include <stdlib.h> |
115 | #if DEBUG | ||
116 | #include <assert.h> | ||
117 | #endif | ||
118 | #include <string.h> | 139 | #include <string.h> |
119 | #include <signal.h> | 140 | #include <signal.h> |
120 | #include <math.h> | 141 | #include <math.h> |
142 | #include "bzlib.h" | ||
121 | 143 | ||
122 | #define ERROR_IF_EOF(i) { if ((i) == EOF) ioError(); } | 144 | #define ERROR_IF_EOF(i) { if ((i) == EOF) ioError(); } |
123 | #define ERROR_IF_NOT_ZERO(i) { if ((i) != 0) ioError(); } | 145 | #define ERROR_IF_NOT_ZERO(i) { if ((i) != 0) ioError(); } |
@@ -130,68 +152,45 @@ | |||
130 | --*/ | 152 | --*/ |
131 | 153 | ||
132 | #if BZ_UNIX | 154 | #if BZ_UNIX |
133 | #include <sys/types.h> | 155 | # include <sys/types.h> |
134 | #include <utime.h> | 156 | # include <utime.h> |
135 | #include <unistd.h> | 157 | # include <unistd.h> |
136 | #include <malloc.h> | 158 | # include <sys/stat.h> |
137 | #include <sys/stat.h> | 159 | # include <sys/times.h> |
138 | #include <sys/times.h> | 160 | |
139 | 161 | # define PATH_SEP '/' | |
140 | #define Int32 int | 162 | # define MY_LSTAT lstat |
141 | #define UInt32 unsigned int | 163 | # define MY_S_IFREG S_ISREG |
142 | #define Char char | 164 | # define MY_STAT stat |
143 | #define UChar unsigned char | 165 | |
144 | #define Int16 short | 166 | # define APPEND_FILESPEC(root, name) \ |
145 | #define UInt16 unsigned short | ||
146 | |||
147 | #define PATH_SEP '/' | ||
148 | #define MY_LSTAT lstat | ||
149 | #define MY_S_IFREG S_ISREG | ||
150 | #define MY_STAT stat | ||
151 | |||
152 | #define APPEND_FILESPEC(root, name) \ | ||
153 | root=snocString((root), (name)) | 167 | root=snocString((root), (name)) |
154 | 168 | ||
155 | #define SET_BINARY_MODE(fd) /**/ | 169 | # define SET_BINARY_MODE(fd) /**/ |
156 | 170 | ||
157 | /*-- | 171 | # ifdef __GNUC__ |
158 | You should try very hard to persuade your C compiler | 172 | # define NORETURN __attribute__ ((noreturn)) |
159 | to inline the bits marked INLINE. Otherwise bzip2 will | 173 | # else |
160 | run rather slowly. gcc version 2.x is recommended. | 174 | # define NORETURN /**/ |
161 | --*/ | 175 | # endif |
162 | #ifdef __GNUC__ | ||
163 | #define INLINE inline | ||
164 | #define NORETURN __attribute__ ((noreturn)) | ||
165 | #else | ||
166 | #define INLINE /**/ | ||
167 | #define NORETURN /**/ | ||
168 | #endif | ||
169 | #endif | 176 | #endif |
170 | 177 | ||
171 | 178 | ||
172 | 179 | ||
173 | #if BZ_LCCWIN32 | 180 | #if BZ_LCCWIN32 |
174 | #include <io.h> | 181 | # include <io.h> |
175 | #include <fcntl.h> | 182 | # include <fcntl.h> |
176 | #include <sys\stat.h> | 183 | # include <sys\stat.h> |
177 | 184 | ||
178 | #define Int32 int | 185 | # define NORETURN /**/ |
179 | #define UInt32 unsigned int | 186 | # define PATH_SEP '\\' |
180 | #define Int16 short | 187 | # define MY_LSTAT _stat |
181 | #define UInt16 unsigned short | 188 | # define MY_STAT _stat |
182 | #define Char char | 189 | # define MY_S_IFREG(x) ((x) & _S_IFREG) |
183 | #define UChar unsigned char | 190 | |
184 | 191 | # if 0 | |
185 | #define INLINE /**/ | ||
186 | #define NORETURN /**/ | ||
187 | #define PATH_SEP '\\' | ||
188 | #define MY_LSTAT _stat | ||
189 | #define MY_STAT _stat | ||
190 | #define MY_S_IFREG(x) ((x) & _S_IFREG) | ||
191 | |||
192 | #if 0 | ||
193 | /*-- lcc-win32 seems to expand wildcards itself --*/ | 192 | /*-- lcc-win32 seems to expand wildcards itself --*/ |
194 | #define APPEND_FILESPEC(root, spec) \ | 193 | # define APPEND_FILESPEC(root, spec) \ |
195 | do { \ | 194 | do { \ |
196 | if ((spec)[0] == '-') { \ | 195 | if ((spec)[0] == '-') { \ |
197 | root = snocString((root), (spec)); \ | 196 | root = snocString((root), (spec)); \ |
@@ -211,12 +210,12 @@ | |||
211 | } \ | 210 | } \ |
212 | } \ | 211 | } \ |
213 | } while ( 0 ) | 212 | } while ( 0 ) |
214 | #else | 213 | # else |
215 | #define APPEND_FILESPEC(root, name) \ | 214 | # define APPEND_FILESPEC(root, name) \ |
216 | root = snocString ((root), (name)) | 215 | root = snocString ((root), (name)) |
217 | #endif | 216 | # endif |
218 | 217 | ||
219 | #define SET_BINARY_MODE(fd) \ | 218 | # define SET_BINARY_MODE(fd) \ |
220 | do { \ | 219 | do { \ |
221 | int retVal = setmode ( fileno ( fd ), \ | 220 | int retVal = setmode ( fileno ( fd ), \ |
222 | O_BINARY ); \ | 221 | O_BINARY ); \ |
@@ -231,111 +230,32 @@ | |||
231 | Some more stuff for all platforms :-) | 230 | Some more stuff for all platforms :-) |
232 | --*/ | 231 | --*/ |
233 | 232 | ||
234 | #define Bool unsigned char | 233 | typedef char Char; |
235 | #define True 1 | 234 | typedef unsigned char Bool; |
236 | #define False 0 | 235 | typedef unsigned char UChar; |
236 | typedef int Int32; | ||
237 | typedef unsigned int UInt32; | ||
238 | typedef short Int16; | ||
239 | typedef unsigned short UInt16; | ||
240 | |||
241 | #define True ((Bool)1) | ||
242 | #define False ((Bool)0) | ||
237 | 243 | ||
238 | /*-- | 244 | /*-- |
239 | IntNative is your platform's `native' int size. | 245 | IntNative is your platform's `native' int size. |
240 | Only here to avoid probs with 64-bit platforms. | 246 | Only here to avoid probs with 64-bit platforms. |
241 | --*/ | 247 | --*/ |
242 | #define IntNative int | 248 | typedef int IntNative; |
243 | |||
244 | |||
245 | /*-- | ||
246 | change to 1, or compile with -DDEBUG=1 to debug | ||
247 | --*/ | ||
248 | #ifndef DEBUG | ||
249 | #define DEBUG 0 | ||
250 | #endif | ||
251 | |||
252 | |||
253 | /*---------------------------------------------------*/ | ||
254 | /*--- ---*/ | ||
255 | /*---------------------------------------------------*/ | ||
256 | |||
257 | /*-- | ||
258 | Implementation notes, July 1997 | ||
259 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | ||
260 | |||
261 | Memory allocation | ||
262 | ~~~~~~~~~~~~~~~~~ | ||
263 | All large data structures are allocated on the C heap, | ||
264 | for better or for worse. That includes the various | ||
265 | arrays of pointers, striped words, bytes, frequency | ||
266 | tables and buffers for compression and decompression. | ||
267 | |||
268 | bzip2 can operate at various block-sizes, ranging from | ||
269 | 100k to 900k in 100k steps, and it allocates only as | ||
270 | much as it needs to. When compressing, we know from the | ||
271 | command-line options what the block-size is going to be, | ||
272 | so all allocation can be done at start-up; if that | ||
273 | succeeds, there can be no further allocation problems. | ||
274 | |||
275 | Decompression is more complicated. Each compressed file | ||
276 | contains, in its header, a byte indicating the block | ||
277 | size used for compression. This means bzip2 potentially | ||
278 | needs to reallocate memory for each file it deals with, | ||
279 | which in turn opens the possibility for a memory allocation | ||
280 | failure part way through a run of files, by encountering | ||
281 | a file requiring a much larger block size than all the | ||
282 | ones preceding it. | ||
283 | |||
284 | The policy is to simply give up if a memory allocation | ||
285 | failure occurs. During decompression, it would be | ||
286 | possible to move on to subsequent files in the hope that | ||
287 | some might ask for a smaller block size, but the | ||
288 | complications for doing this seem more trouble than they | ||
289 | are worth. | ||
290 | |||
291 | |||
292 | Compressed file formats | ||
293 | ~~~~~~~~~~~~~~~~~~~~~~~ | ||
294 | [This is now entirely different from both 0.21, and from | ||
295 | any previous Huffman-coded variant of bzip. | ||
296 | See the associated file bzip2.txt for details.] | ||
297 | |||
298 | |||
299 | Error conditions | ||
300 | ~~~~~~~~~~~~~~~~ | ||
301 | Dealing with error conditions is the least satisfactory | ||
302 | aspect of bzip2. The policy is to try and leave the | ||
303 | filesystem in a consistent state, then quit, even if it | ||
304 | means not processing some of the files mentioned in the | ||
305 | command line. `A consistent state' means that a file | ||
306 | exists either in its compressed or uncompressed form, | ||
307 | but not both. This boils down to the rule `delete the | ||
308 | output file if an error condition occurs, leaving the | ||
309 | input intact'. Input files are only deleted when we can | ||
310 | be pretty sure the output file has been written and | ||
311 | closed successfully. | ||
312 | |||
313 | Errors are a dog because there's so many things to | ||
314 | deal with. The following can happen mid-file, and | ||
315 | require cleaning up. | ||
316 | |||
317 | internal `panics' -- indicating a bug | ||
318 | corrupted or inconsistent compressed file | ||
319 | can't allocate enough memory to decompress this file | ||
320 | I/O error reading/writing/opening/closing | ||
321 | signal catches -- Control-C, SIGTERM, SIGHUP. | ||
322 | |||
323 | Other conditions, primarily pertaining to file names, | ||
324 | can be checked in-between files, which makes dealing | ||
325 | with them easier. | ||
326 | --*/ | ||
327 | |||
328 | 249 | ||
329 | 250 | ||
330 | /*---------------------------------------------------*/ | 251 | /*---------------------------------------------------*/ |
331 | /*--- Misc (file handling) data decls ---*/ | 252 | /*--- Misc (file handling) data decls ---*/ |
332 | /*---------------------------------------------------*/ | 253 | /*---------------------------------------------------*/ |
333 | 254 | ||
334 | UInt32 bytesIn, bytesOut; | ||
335 | Int32 verbosity; | 255 | Int32 verbosity; |
336 | Bool keepInputFiles, smallMode, testFailsExist; | 256 | Bool keepInputFiles, smallMode; |
337 | UInt32 globalCrc; | 257 | Bool forceOverwrite, testFailsExist; |
338 | Int32 numFileNames, numFilesProcessed; | 258 | Int32 numFileNames, numFilesProcessed, blockSize100k; |
339 | 259 | ||
340 | 260 | ||
341 | /*-- source modes; F==file, I==stdin, O==stdout --*/ | 261 | /*-- source modes; F==file, I==stdin, O==stdout --*/ |
@@ -351,2691 +271,304 @@ Int32 numFileNames, numFilesProcessed; | |||
351 | Int32 opMode; | 271 | Int32 opMode; |
352 | Int32 srcMode; | 272 | Int32 srcMode; |
353 | 273 | ||
274 | #define FILE_NAME_LEN 1034 | ||
354 | 275 | ||
355 | Int32 longestFileName; | 276 | Int32 longestFileName; |
356 | Char inName[1024]; | 277 | Char inName[FILE_NAME_LEN]; |
357 | Char outName[1024]; | 278 | Char outName[FILE_NAME_LEN]; |
358 | Char *progName; | 279 | Char *progName; |
359 | Char progNameReally[1024]; | 280 | Char progNameReally[FILE_NAME_LEN]; |
360 | FILE *outputHandleJustInCase; | 281 | FILE *outputHandleJustInCase; |
361 | 282 | Int32 workFactor; | |
362 | void panic ( Char* ) NORETURN; | 283 | |
363 | void ioError ( void ) NORETURN; | 284 | void panic ( Char* ) NORETURN; |
364 | void compressOutOfMemory ( Int32, Int32 ) NORETURN; | 285 | void ioError ( void ) NORETURN; |
365 | void uncompressOutOfMemory ( Int32, Int32 ) NORETURN; | 286 | void outOfMemory ( void ) NORETURN; |
366 | void blockOverrun ( void ) NORETURN; | 287 | void blockOverrun ( void ) NORETURN; |
367 | void badBlockHeader ( void ) NORETURN; | 288 | void badBlockHeader ( void ) NORETURN; |
368 | void badBGLengths ( void ) NORETURN; | 289 | void badBGLengths ( void ) NORETURN; |
369 | void crcError ( UInt32, UInt32 ) NORETURN; | 290 | void crcError ( void ) NORETURN; |
370 | void bitStreamEOF ( void ) NORETURN; | 291 | void bitStreamEOF ( void ) NORETURN; |
371 | void cleanUpAndFail ( Int32 ) NORETURN; | 292 | void cleanUpAndFail ( Int32 ) NORETURN; |
372 | void compressedStreamEOF ( void ) NORETURN; | 293 | void compressedStreamEOF ( void ) NORETURN; |
373 | 294 | ||
295 | void copyFileName ( Char*, Char* ); | ||
374 | void* myMalloc ( Int32 ); | 296 | void* myMalloc ( Int32 ); |
375 | 297 | ||
376 | 298 | ||
377 | 299 | ||
378 | /*---------------------------------------------------*/ | 300 | /*---------------------------------------------------*/ |
379 | /*--- Data decls for the front end ---*/ | 301 | /*--- Processing of complete files and streams ---*/ |
380 | /*---------------------------------------------------*/ | ||
381 | |||
382 | /*-- | ||
383 | The overshoot bytes allow us to avoid most of | ||
384 | the cost of pointer renormalisation during | ||
385 | comparison of rotations in sorting. | ||
386 | The figure of 20 is derived as follows: | ||
387 | qSort3 allows an overshoot of up to 10. | ||
388 | It then calls simpleSort, which calls | ||
389 | fullGtU, also with max overshoot 10. | ||
390 | fullGtU does up to 10 comparisons without | ||
391 | renormalising, giving 10+10 == 20. | ||
392 | --*/ | ||
393 | #define NUM_OVERSHOOT_BYTES 20 | ||
394 | |||
395 | /*-- | ||
396 | These are the main data structures for | ||
397 | the Burrows-Wheeler transform. | ||
398 | --*/ | ||
399 | |||
400 | /*-- | ||
401 | Pointers to compression and decompression | ||
402 | structures. Set by | ||
403 | allocateCompressStructures and | ||
404 | setDecompressStructureSizes | ||
405 | |||
406 | The structures are always set to be suitable | ||
407 | for a block of size 100000 * blockSize100k. | ||
408 | --*/ | ||
409 | UChar *block; /*-- compress --*/ | ||
410 | UInt16 *quadrant; /*-- compress --*/ | ||
411 | Int32 *zptr; /*-- compress --*/ | ||
412 | UInt16 *szptr; /*-- overlays zptr ---*/ | ||
413 | Int32 *ftab; /*-- compress --*/ | ||
414 | |||
415 | UInt16 *ll16; /*-- small decompress --*/ | ||
416 | UChar *ll4; /*-- small decompress --*/ | ||
417 | |||
418 | Int32 *tt; /*-- fast decompress --*/ | ||
419 | UChar *ll8; /*-- fast decompress --*/ | ||
420 | |||
421 | |||
422 | /*-- | ||
423 | freq table collected to save a pass over the data | ||
424 | during decompression. | ||
425 | --*/ | ||
426 | Int32 unzftab[256]; | ||
427 | |||
428 | |||
429 | /*-- | ||
430 | index of the last char in the block, so | ||
431 | the block size == last + 1. | ||
432 | --*/ | ||
433 | Int32 last; | ||
434 | |||
435 | |||
436 | /*-- | ||
437 | index in zptr[] of original string after sorting. | ||
438 | --*/ | ||
439 | Int32 origPtr; | ||
440 | |||
441 | |||
442 | /*-- | ||
443 | always: in the range 0 .. 9. | ||
444 | The current block size is 100000 * this number. | ||
445 | --*/ | ||
446 | Int32 blockSize100k; | ||
447 | |||
448 | |||
449 | /*-- | ||
450 | Used when sorting. If too many long comparisons | ||
451 | happen, we stop sorting, randomise the block | ||
452 | slightly, and try again. | ||
453 | --*/ | ||
454 | |||
455 | Int32 workFactor; | ||
456 | Int32 workDone; | ||
457 | Int32 workLimit; | ||
458 | Bool blockRandomised; | ||
459 | Bool firstAttempt; | ||
460 | Int32 nBlocksRandomised; | ||
461 | |||
462 | |||
463 | |||
464 | /*---------------------------------------------------*/ | ||
465 | /*--- Data decls for the back end ---*/ | ||
466 | /*---------------------------------------------------*/ | ||
467 | |||
468 | #define MAX_ALPHA_SIZE 258 | ||
469 | #define MAX_CODE_LEN 23 | ||
470 | |||
471 | #define RUNA 0 | ||
472 | #define RUNB 1 | ||
473 | |||
474 | #define N_GROUPS 6 | ||
475 | #define G_SIZE 50 | ||
476 | #define N_ITERS 4 | ||
477 | |||
478 | #define MAX_SELECTORS (2 + (900000 / G_SIZE)) | ||
479 | |||
480 | Bool inUse[256]; | ||
481 | Int32 nInUse; | ||
482 | |||
483 | UChar seqToUnseq[256]; | ||
484 | UChar unseqToSeq[256]; | ||
485 | |||
486 | UChar selector [MAX_SELECTORS]; | ||
487 | UChar selectorMtf[MAX_SELECTORS]; | ||
488 | |||
489 | Int32 nMTF; | ||
490 | |||
491 | Int32 mtfFreq[MAX_ALPHA_SIZE]; | ||
492 | |||
493 | UChar len [N_GROUPS][MAX_ALPHA_SIZE]; | ||
494 | |||
495 | /*-- decompress only --*/ | ||
496 | Int32 limit [N_GROUPS][MAX_ALPHA_SIZE]; | ||
497 | Int32 base [N_GROUPS][MAX_ALPHA_SIZE]; | ||
498 | Int32 perm [N_GROUPS][MAX_ALPHA_SIZE]; | ||
499 | Int32 minLens[N_GROUPS]; | ||
500 | |||
501 | /*-- compress only --*/ | ||
502 | Int32 code [N_GROUPS][MAX_ALPHA_SIZE]; | ||
503 | Int32 rfreq[N_GROUPS][MAX_ALPHA_SIZE]; | ||
504 | |||
505 | |||
506 | /*---------------------------------------------------*/ | ||
507 | /*--- 32-bit CRC grunge ---*/ | ||
508 | /*---------------------------------------------------*/ | ||
509 | |||
510 | /*-- | ||
511 | I think this is an implementation of the AUTODIN-II, | ||
512 | Ethernet & FDDI 32-bit CRC standard. Vaguely derived | ||
513 | from code by Rob Warnock, in Section 51 of the | ||
514 | comp.compression FAQ. | ||
515 | --*/ | ||
516 | |||
517 | UInt32 crc32Table[256] = { | ||
518 | |||
519 | /*-- Ugly, innit? --*/ | ||
520 | |||
521 | 0x00000000UL, 0x04c11db7UL, 0x09823b6eUL, 0x0d4326d9UL, | ||
522 | 0x130476dcUL, 0x17c56b6bUL, 0x1a864db2UL, 0x1e475005UL, | ||
523 | 0x2608edb8UL, 0x22c9f00fUL, 0x2f8ad6d6UL, 0x2b4bcb61UL, | ||
524 | 0x350c9b64UL, 0x31cd86d3UL, 0x3c8ea00aUL, 0x384fbdbdUL, | ||
525 | 0x4c11db70UL, 0x48d0c6c7UL, 0x4593e01eUL, 0x4152fda9UL, | ||
526 | 0x5f15adacUL, 0x5bd4b01bUL, 0x569796c2UL, 0x52568b75UL, | ||
527 | 0x6a1936c8UL, 0x6ed82b7fUL, 0x639b0da6UL, 0x675a1011UL, | ||
528 | 0x791d4014UL, 0x7ddc5da3UL, 0x709f7b7aUL, 0x745e66cdUL, | ||
529 | 0x9823b6e0UL, 0x9ce2ab57UL, 0x91a18d8eUL, 0x95609039UL, | ||
530 | 0x8b27c03cUL, 0x8fe6dd8bUL, 0x82a5fb52UL, 0x8664e6e5UL, | ||
531 | 0xbe2b5b58UL, 0xbaea46efUL, 0xb7a96036UL, 0xb3687d81UL, | ||
532 | 0xad2f2d84UL, 0xa9ee3033UL, 0xa4ad16eaUL, 0xa06c0b5dUL, | ||
533 | 0xd4326d90UL, 0xd0f37027UL, 0xddb056feUL, 0xd9714b49UL, | ||
534 | 0xc7361b4cUL, 0xc3f706fbUL, 0xceb42022UL, 0xca753d95UL, | ||
535 | 0xf23a8028UL, 0xf6fb9d9fUL, 0xfbb8bb46UL, 0xff79a6f1UL, | ||
536 | 0xe13ef6f4UL, 0xe5ffeb43UL, 0xe8bccd9aUL, 0xec7dd02dUL, | ||
537 | 0x34867077UL, 0x30476dc0UL, 0x3d044b19UL, 0x39c556aeUL, | ||
538 | 0x278206abUL, 0x23431b1cUL, 0x2e003dc5UL, 0x2ac12072UL, | ||
539 | 0x128e9dcfUL, 0x164f8078UL, 0x1b0ca6a1UL, 0x1fcdbb16UL, | ||
540 | 0x018aeb13UL, 0x054bf6a4UL, 0x0808d07dUL, 0x0cc9cdcaUL, | ||
541 | 0x7897ab07UL, 0x7c56b6b0UL, 0x71159069UL, 0x75d48ddeUL, | ||
542 | 0x6b93dddbUL, 0x6f52c06cUL, 0x6211e6b5UL, 0x66d0fb02UL, | ||
543 | 0x5e9f46bfUL, 0x5a5e5b08UL, 0x571d7dd1UL, 0x53dc6066UL, | ||
544 | 0x4d9b3063UL, 0x495a2dd4UL, 0x44190b0dUL, 0x40d816baUL, | ||
545 | 0xaca5c697UL, 0xa864db20UL, 0xa527fdf9UL, 0xa1e6e04eUL, | ||
546 | 0xbfa1b04bUL, 0xbb60adfcUL, 0xb6238b25UL, 0xb2e29692UL, | ||
547 | 0x8aad2b2fUL, 0x8e6c3698UL, 0x832f1041UL, 0x87ee0df6UL, | ||
548 | 0x99a95df3UL, 0x9d684044UL, 0x902b669dUL, 0x94ea7b2aUL, | ||
549 | 0xe0b41de7UL, 0xe4750050UL, 0xe9362689UL, 0xedf73b3eUL, | ||
550 | 0xf3b06b3bUL, 0xf771768cUL, 0xfa325055UL, 0xfef34de2UL, | ||
551 | 0xc6bcf05fUL, 0xc27dede8UL, 0xcf3ecb31UL, 0xcbffd686UL, | ||
552 | 0xd5b88683UL, 0xd1799b34UL, 0xdc3abdedUL, 0xd8fba05aUL, | ||
553 | 0x690ce0eeUL, 0x6dcdfd59UL, 0x608edb80UL, 0x644fc637UL, | ||
554 | 0x7a089632UL, 0x7ec98b85UL, 0x738aad5cUL, 0x774bb0ebUL, | ||
555 | 0x4f040d56UL, 0x4bc510e1UL, 0x46863638UL, 0x42472b8fUL, | ||
556 | 0x5c007b8aUL, 0x58c1663dUL, 0x558240e4UL, 0x51435d53UL, | ||
557 | 0x251d3b9eUL, 0x21dc2629UL, 0x2c9f00f0UL, 0x285e1d47UL, | ||
558 | 0x36194d42UL, 0x32d850f5UL, 0x3f9b762cUL, 0x3b5a6b9bUL, | ||
559 | 0x0315d626UL, 0x07d4cb91UL, 0x0a97ed48UL, 0x0e56f0ffUL, | ||
560 | 0x1011a0faUL, 0x14d0bd4dUL, 0x19939b94UL, 0x1d528623UL, | ||
561 | 0xf12f560eUL, 0xf5ee4bb9UL, 0xf8ad6d60UL, 0xfc6c70d7UL, | ||
562 | 0xe22b20d2UL, 0xe6ea3d65UL, 0xeba91bbcUL, 0xef68060bUL, | ||
563 | 0xd727bbb6UL, 0xd3e6a601UL, 0xdea580d8UL, 0xda649d6fUL, | ||
564 | 0xc423cd6aUL, 0xc0e2d0ddUL, 0xcda1f604UL, 0xc960ebb3UL, | ||
565 | 0xbd3e8d7eUL, 0xb9ff90c9UL, 0xb4bcb610UL, 0xb07daba7UL, | ||
566 | 0xae3afba2UL, 0xaafbe615UL, 0xa7b8c0ccUL, 0xa379dd7bUL, | ||
567 | 0x9b3660c6UL, 0x9ff77d71UL, 0x92b45ba8UL, 0x9675461fUL, | ||
568 | 0x8832161aUL, 0x8cf30badUL, 0x81b02d74UL, 0x857130c3UL, | ||
569 | 0x5d8a9099UL, 0x594b8d2eUL, 0x5408abf7UL, 0x50c9b640UL, | ||
570 | 0x4e8ee645UL, 0x4a4ffbf2UL, 0x470cdd2bUL, 0x43cdc09cUL, | ||
571 | 0x7b827d21UL, 0x7f436096UL, 0x7200464fUL, 0x76c15bf8UL, | ||
572 | 0x68860bfdUL, 0x6c47164aUL, 0x61043093UL, 0x65c52d24UL, | ||
573 | 0x119b4be9UL, 0x155a565eUL, 0x18197087UL, 0x1cd86d30UL, | ||
574 | 0x029f3d35UL, 0x065e2082UL, 0x0b1d065bUL, 0x0fdc1becUL, | ||
575 | 0x3793a651UL, 0x3352bbe6UL, 0x3e119d3fUL, 0x3ad08088UL, | ||
576 | 0x2497d08dUL, 0x2056cd3aUL, 0x2d15ebe3UL, 0x29d4f654UL, | ||
577 | 0xc5a92679UL, 0xc1683bceUL, 0xcc2b1d17UL, 0xc8ea00a0UL, | ||
578 | 0xd6ad50a5UL, 0xd26c4d12UL, 0xdf2f6bcbUL, 0xdbee767cUL, | ||
579 | 0xe3a1cbc1UL, 0xe760d676UL, 0xea23f0afUL, 0xeee2ed18UL, | ||
580 | 0xf0a5bd1dUL, 0xf464a0aaUL, 0xf9278673UL, 0xfde69bc4UL, | ||
581 | 0x89b8fd09UL, 0x8d79e0beUL, 0x803ac667UL, 0x84fbdbd0UL, | ||
582 | 0x9abc8bd5UL, 0x9e7d9662UL, 0x933eb0bbUL, 0x97ffad0cUL, | ||
583 | 0xafb010b1UL, 0xab710d06UL, 0xa6322bdfUL, 0xa2f33668UL, | ||
584 | 0xbcb4666dUL, 0xb8757bdaUL, 0xb5365d03UL, 0xb1f740b4UL | ||
585 | }; | ||
586 | |||
587 | |||
588 | /*---------------------------------------------*/ | ||
589 | void initialiseCRC ( void ) | ||
590 | { | ||
591 | globalCrc = 0xffffffffUL; | ||
592 | } | ||
593 | |||
594 | |||
595 | /*---------------------------------------------*/ | ||
596 | UInt32 getFinalCRC ( void ) | ||
597 | { | ||
598 | return ~globalCrc; | ||
599 | } | ||
600 | |||
601 | |||
602 | /*---------------------------------------------*/ | ||
603 | UInt32 getGlobalCRC ( void ) | ||
604 | { | ||
605 | return globalCrc; | ||
606 | } | ||
607 | |||
608 | |||
609 | /*---------------------------------------------*/ | ||
610 | void setGlobalCRC ( UInt32 newCrc ) | ||
611 | { | ||
612 | globalCrc = newCrc; | ||
613 | } | ||
614 | |||
615 | |||
616 | /*---------------------------------------------*/ | ||
617 | #define UPDATE_CRC(crcVar,cha) \ | ||
618 | { \ | ||
619 | crcVar = (crcVar << 8) ^ \ | ||
620 | crc32Table[(crcVar >> 24) ^ \ | ||
621 | ((UChar)cha)]; \ | ||
622 | } | ||
623 | |||
624 | |||
625 | /*---------------------------------------------------*/ | ||
626 | /*--- Bit stream I/O ---*/ | ||
627 | /*---------------------------------------------------*/ | 302 | /*---------------------------------------------------*/ |
628 | 303 | ||
629 | |||
630 | UInt32 bsBuff; | ||
631 | Int32 bsLive; | ||
632 | FILE* bsStream; | ||
633 | Bool bsWriting; | ||
634 | |||
635 | |||
636 | /*---------------------------------------------*/ | ||
637 | void bsSetStream ( FILE* f, Bool wr ) | ||
638 | { | ||
639 | if (bsStream != NULL) panic ( "bsSetStream" ); | ||
640 | bsStream = f; | ||
641 | bsLive = 0; | ||
642 | bsBuff = 0; | ||
643 | bytesOut = 0; | ||
644 | bytesIn = 0; | ||
645 | bsWriting = wr; | ||
646 | } | ||
647 | |||
648 | |||
649 | /*---------------------------------------------*/ | ||
650 | void bsFinishedWithStream ( void ) | ||
651 | { | ||
652 | if (bsWriting) | ||
653 | while (bsLive > 0) { | ||
654 | fputc ( (UChar)(bsBuff >> 24), bsStream ); | ||
655 | bsBuff <<= 8; | ||
656 | bsLive -= 8; | ||
657 | bytesOut++; | ||
658 | } | ||
659 | bsStream = NULL; | ||
660 | } | ||
661 | |||
662 | |||
663 | /*---------------------------------------------*/ | ||
664 | #define bsNEEDR(nz) \ | ||
665 | { \ | ||
666 | while (bsLive < nz) { \ | ||
667 | Int32 zzi = fgetc ( bsStream ); \ | ||
668 | if (zzi == EOF) compressedStreamEOF(); \ | ||
669 | bsBuff = (bsBuff << 8) | (zzi & 0xffL); \ | ||
670 | bsLive += 8; \ | ||
671 | } \ | ||
672 | } | ||
673 | |||
674 | |||
675 | /*---------------------------------------------*/ | ||
676 | #define bsNEEDW(nz) \ | ||
677 | { \ | ||
678 | while (bsLive >= 8) { \ | ||
679 | fputc ( (UChar)(bsBuff >> 24), \ | ||
680 | bsStream ); \ | ||
681 | bsBuff <<= 8; \ | ||
682 | bsLive -= 8; \ | ||
683 | bytesOut++; \ | ||
684 | } \ | ||
685 | } | ||
686 | |||
687 | |||
688 | /*---------------------------------------------*/ | ||
689 | #define bsR1(vz) \ | ||
690 | { \ | ||
691 | bsNEEDR(1); \ | ||
692 | vz = (bsBuff >> (bsLive-1)) & 1; \ | ||
693 | bsLive--; \ | ||
694 | } | ||
695 | |||
696 | |||
697 | /*---------------------------------------------*/ | ||
698 | INLINE UInt32 bsR ( Int32 n ) | ||
699 | { | ||
700 | UInt32 v; | ||
701 | bsNEEDR ( n ); | ||
702 | v = (bsBuff >> (bsLive-n)) & ((1 << n)-1); | ||
703 | bsLive -= n; | ||
704 | return v; | ||
705 | } | ||
706 | |||
707 | |||
708 | /*---------------------------------------------*/ | ||
709 | INLINE void bsW ( Int32 n, UInt32 v ) | ||
710 | { | ||
711 | bsNEEDW ( n ); | ||
712 | bsBuff |= (v << (32 - bsLive - n)); | ||
713 | bsLive += n; | ||
714 | } | ||
715 | |||
716 | |||
717 | /*---------------------------------------------*/ | ||
718 | UChar bsGetUChar ( void ) | ||
719 | { | ||
720 | return (UChar)bsR(8); | ||
721 | } | ||
722 | |||
723 | |||
724 | /*---------------------------------------------*/ | ||
725 | void bsPutUChar ( UChar c ) | ||
726 | { | ||
727 | bsW(8, (UInt32)c ); | ||
728 | } | ||
729 | |||
730 | |||
731 | /*---------------------------------------------*/ | 304 | /*---------------------------------------------*/ |
732 | Int32 bsGetUInt32 ( void ) | 305 | Bool myfeof ( FILE* f ) |
733 | { | 306 | { |
734 | UInt32 u; | 307 | Int32 c = fgetc ( f ); |
735 | u = 0; | 308 | if (c == EOF) return True; |
736 | u = (u << 8) | bsR(8); | 309 | ungetc ( c, f ); |
737 | u = (u << 8) | bsR(8); | 310 | return False; |
738 | u = (u << 8) | bsR(8); | ||
739 | u = (u << 8) | bsR(8); | ||
740 | return u; | ||
741 | } | ||
742 | |||
743 | |||
744 | /*---------------------------------------------*/ | ||
745 | UInt32 bsGetIntVS ( UInt32 numBits ) | ||
746 | { | ||
747 | return (UInt32)bsR(numBits); | ||
748 | } | ||
749 | |||
750 | |||
751 | /*---------------------------------------------*/ | ||
752 | UInt32 bsGetInt32 ( void ) | ||
753 | { | ||
754 | return (Int32)bsGetUInt32(); | ||
755 | } | ||
756 | |||
757 | |||
758 | /*---------------------------------------------*/ | ||
759 | void bsPutUInt32 ( UInt32 u ) | ||
760 | { | ||
761 | bsW ( 8, (u >> 24) & 0xffL ); | ||
762 | bsW ( 8, (u >> 16) & 0xffL ); | ||
763 | bsW ( 8, (u >> 8) & 0xffL ); | ||
764 | bsW ( 8, u & 0xffL ); | ||
765 | } | ||
766 | |||
767 | |||
768 | /*---------------------------------------------*/ | ||
769 | void bsPutInt32 ( Int32 c ) | ||
770 | { | ||
771 | bsPutUInt32 ( (UInt32)c ); | ||
772 | } | 311 | } |
773 | 312 | ||
774 | 313 | ||
775 | /*---------------------------------------------*/ | 314 | /*---------------------------------------------*/ |
776 | void bsPutIntVS ( Int32 numBits, UInt32 c ) | 315 | void compressStream ( FILE *stream, FILE *zStream ) |
777 | { | 316 | { |
778 | bsW ( numBits, c ); | 317 | BZFILE* bzf = NULL; |
779 | } | 318 | UChar ibuf[5000]; |
780 | 319 | Int32 nIbuf; | |
781 | 320 | UInt32 nbytes_in, nbytes_out; | |
782 | /*---------------------------------------------------*/ | 321 | Int32 bzerr, bzerr_dummy, ret; |
783 | /*--- Huffman coding low-level stuff ---*/ | ||
784 | /*---------------------------------------------------*/ | ||
785 | |||
786 | #define WEIGHTOF(zz0) ((zz0) & 0xffffff00) | ||
787 | #define DEPTHOF(zz1) ((zz1) & 0x000000ff) | ||
788 | #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3)) | ||
789 | |||
790 | #define ADDWEIGHTS(zw1,zw2) \ | ||
791 | (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \ | ||
792 | (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2))) | ||
793 | |||
794 | #define UPHEAP(z) \ | ||
795 | { \ | ||
796 | Int32 zz, tmp; \ | ||
797 | zz = z; tmp = heap[zz]; \ | ||
798 | while (weight[tmp] < weight[heap[zz >> 1]]) { \ | ||
799 | heap[zz] = heap[zz >> 1]; \ | ||
800 | zz >>= 1; \ | ||
801 | } \ | ||
802 | heap[zz] = tmp; \ | ||
803 | } | ||
804 | |||
805 | #define DOWNHEAP(z) \ | ||
806 | { \ | ||
807 | Int32 zz, yy, tmp; \ | ||
808 | zz = z; tmp = heap[zz]; \ | ||
809 | while (True) { \ | ||
810 | yy = zz << 1; \ | ||
811 | if (yy > nHeap) break; \ | ||
812 | if (yy < nHeap && \ | ||
813 | weight[heap[yy+1]] < weight[heap[yy]]) \ | ||
814 | yy++; \ | ||
815 | if (weight[tmp] < weight[heap[yy]]) break; \ | ||
816 | heap[zz] = heap[yy]; \ | ||
817 | zz = yy; \ | ||
818 | } \ | ||
819 | heap[zz] = tmp; \ | ||
820 | } | ||
821 | 322 | ||
323 | SET_BINARY_MODE(stream); | ||
324 | SET_BINARY_MODE(zStream); | ||
822 | 325 | ||
823 | /*---------------------------------------------*/ | 326 | if (ferror(stream)) goto errhandler_io; |
824 | void hbMakeCodeLengths ( UChar *len, | 327 | if (ferror(zStream)) goto errhandler_io; |
825 | Int32 *freq, | ||
826 | Int32 alphaSize, | ||
827 | Int32 maxLen ) | ||
828 | { | ||
829 | /*-- | ||
830 | Nodes and heap entries run from 1. Entry 0 | ||
831 | for both the heap and nodes is a sentinel. | ||
832 | --*/ | ||
833 | Int32 nNodes, nHeap, n1, n2, i, j, k; | ||
834 | Bool tooLong; | ||
835 | 328 | ||
836 | Int32 heap [ MAX_ALPHA_SIZE + 2 ]; | 329 | bzf = bzWriteOpen ( &bzerr, zStream, |
837 | Int32 weight [ MAX_ALPHA_SIZE * 2 ]; | 330 | blockSize100k, verbosity, workFactor ); |
838 | Int32 parent [ MAX_ALPHA_SIZE * 2 ]; | 331 | if (bzerr != BZ_OK) goto errhandler; |
839 | 332 | ||
840 | for (i = 0; i < alphaSize; i++) | 333 | if (verbosity >= 2) fprintf ( stderr, "\n" ); |
841 | weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8; | ||
842 | 334 | ||
843 | while (True) { | 335 | while (True) { |
844 | 336 | ||
845 | nNodes = alphaSize; | 337 | if (myfeof(stream)) break; |
846 | nHeap = 0; | 338 | nIbuf = fread ( ibuf, sizeof(UChar), 5000, stream ); |
847 | 339 | if (ferror(stream)) goto errhandler_io; | |
848 | heap[0] = 0; | 340 | if (nIbuf > 0) bzWrite ( &bzerr, bzf, (void*)ibuf, nIbuf ); |
849 | weight[0] = 0; | 341 | if (bzerr != BZ_OK) goto errhandler; |
850 | parent[0] = -2; | ||
851 | |||
852 | for (i = 1; i <= alphaSize; i++) { | ||
853 | parent[i] = -1; | ||
854 | nHeap++; | ||
855 | heap[nHeap] = i; | ||
856 | UPHEAP(nHeap); | ||
857 | } | ||
858 | if (!(nHeap < (MAX_ALPHA_SIZE+2))) | ||
859 | panic ( "hbMakeCodeLengths(1)" ); | ||
860 | |||
861 | while (nHeap > 1) { | ||
862 | n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); | ||
863 | n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); | ||
864 | nNodes++; | ||
865 | parent[n1] = parent[n2] = nNodes; | ||
866 | weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]); | ||
867 | parent[nNodes] = -1; | ||
868 | nHeap++; | ||
869 | heap[nHeap] = nNodes; | ||
870 | UPHEAP(nHeap); | ||
871 | } | ||
872 | if (!(nNodes < (MAX_ALPHA_SIZE * 2))) | ||
873 | panic ( "hbMakeCodeLengths(2)" ); | ||
874 | |||
875 | tooLong = False; | ||
876 | for (i = 1; i <= alphaSize; i++) { | ||
877 | j = 0; | ||
878 | k = i; | ||
879 | while (parent[k] >= 0) { k = parent[k]; j++; } | ||
880 | len[i-1] = j; | ||
881 | if (j > maxLen) tooLong = True; | ||
882 | } | ||
883 | |||
884 | if (! tooLong) break; | ||
885 | 342 | ||
886 | for (i = 1; i < alphaSize; i++) { | ||
887 | j = weight[i] >> 8; | ||
888 | j = 1 + (j / 2); | ||
889 | weight[i] = j << 8; | ||
890 | } | ||
891 | } | 343 | } |
892 | } | ||
893 | |||
894 | 344 | ||
895 | /*---------------------------------------------*/ | 345 | bzWriteClose ( &bzerr, bzf, 0, &nbytes_in, &nbytes_out ); |
896 | void hbAssignCodes ( Int32 *code, | 346 | if (bzerr != BZ_OK) goto errhandler; |
897 | UChar *length, | ||
898 | Int32 minLen, | ||
899 | Int32 maxLen, | ||
900 | Int32 alphaSize ) | ||
901 | { | ||
902 | Int32 n, vec, i; | ||
903 | 347 | ||
904 | vec = 0; | 348 | if (ferror(zStream)) goto errhandler_io; |
905 | for (n = minLen; n <= maxLen; n++) { | 349 | ret = fflush ( zStream ); |
906 | for (i = 0; i < alphaSize; i++) | 350 | if (ret == EOF) goto errhandler_io; |
907 | if (length[i] == n) { code[i] = vec; vec++; }; | 351 | if (zStream != stdout) { |
908 | vec <<= 1; | 352 | ret = fclose ( zStream ); |
353 | if (ret == EOF) goto errhandler_io; | ||
909 | } | 354 | } |
910 | } | 355 | if (ferror(stream)) goto errhandler_io; |
911 | 356 | ret = fclose ( stream ); | |
912 | 357 | if (ret == EOF) goto errhandler_io; | |
913 | /*---------------------------------------------*/ | ||
914 | void hbCreateDecodeTables ( Int32 *limit, | ||
915 | Int32 *base, | ||
916 | Int32 *perm, | ||
917 | UChar *length, | ||
918 | Int32 minLen, | ||
919 | Int32 maxLen, | ||
920 | Int32 alphaSize ) | ||
921 | { | ||
922 | Int32 pp, i, j, vec; | ||
923 | |||
924 | pp = 0; | ||
925 | for (i = minLen; i <= maxLen; i++) | ||
926 | for (j = 0; j < alphaSize; j++) | ||
927 | if (length[j] == i) { perm[pp] = j; pp++; }; | ||
928 | |||
929 | for (i = 0; i < MAX_CODE_LEN; i++) base[i] = 0; | ||
930 | for (i = 0; i < alphaSize; i++) base[length[i]+1]++; | ||
931 | 358 | ||
932 | for (i = 1; i < MAX_CODE_LEN; i++) base[i] += base[i-1]; | 359 | if (nbytes_in == 0) nbytes_in = 1; |
933 | 360 | ||
934 | for (i = 0; i < MAX_CODE_LEN; i++) limit[i] = 0; | 361 | if (verbosity >= 1) |
935 | vec = 0; | 362 | fprintf ( stderr, "%6.3f:1, %6.3f bits/byte, " |
936 | 363 | "%5.2f%% saved, %d in, %d out.\n", | |
937 | for (i = minLen; i <= maxLen; i++) { | 364 | (float)nbytes_in / (float)nbytes_out, |
938 | vec += (base[i+1] - base[i]); | 365 | (8.0 * (float)nbytes_out) / (float)nbytes_in, |
939 | limit[i] = vec-1; | 366 | 100.0 * (1.0 - (float)nbytes_out / (float)nbytes_in), |
940 | vec <<= 1; | 367 | nbytes_in, |
941 | } | 368 | nbytes_out |
942 | for (i = minLen + 1; i <= maxLen; i++) | 369 | ); |
943 | base[i] = ((limit[i-1] + 1) << 1) - base[i]; | ||
944 | } | ||
945 | |||
946 | |||
947 | |||
948 | /*---------------------------------------------------*/ | ||
949 | /*--- Undoing the reversible transformation ---*/ | ||
950 | /*---------------------------------------------------*/ | ||
951 | |||
952 | /*---------------------------------------------*/ | ||
953 | #define SET_LL4(i,n) \ | ||
954 | { if (((i) & 0x1) == 0) \ | ||
955 | ll4[(i) >> 1] = (ll4[(i) >> 1] & 0xf0) | (n); else \ | ||
956 | ll4[(i) >> 1] = (ll4[(i) >> 1] & 0x0f) | ((n) << 4); \ | ||
957 | } | ||
958 | |||
959 | #define GET_LL4(i) \ | ||
960 | (((UInt32)(ll4[(i) >> 1])) >> (((i) << 2) & 0x4) & 0xF) | ||
961 | |||
962 | #define SET_LL(i,n) \ | ||
963 | { ll16[i] = (UInt16)(n & 0x0000ffff); \ | ||
964 | SET_LL4(i, n >> 16); \ | ||
965 | } | ||
966 | |||
967 | #define GET_LL(i) \ | ||
968 | (((UInt32)ll16[i]) | (GET_LL4(i) << 16)) | ||
969 | |||
970 | |||
971 | /*---------------------------------------------*/ | ||
972 | /*-- | ||
973 | Manage memory for compression/decompression. | ||
974 | When compressing, a single block size applies to | ||
975 | all files processed, and that's set when the | ||
976 | program starts. But when decompressing, each file | ||
977 | processed could have been compressed with a | ||
978 | different block size, so we may have to free | ||
979 | and reallocate on a per-file basis. | ||
980 | |||
981 | A call with argument of zero means | ||
982 | `free up everything.' And a value of zero for | ||
983 | blockSize100k means no memory is currently allocated. | ||
984 | --*/ | ||
985 | 370 | ||
371 | return; | ||
986 | 372 | ||
987 | /*---------------------------------------------*/ | 373 | errhandler: |
988 | void allocateCompressStructures ( void ) | 374 | bzWriteClose ( &bzerr_dummy, bzf, 1, &nbytes_in, &nbytes_out ); |
989 | { | 375 | switch (bzerr) { |
990 | Int32 n = 100000 * blockSize100k; | 376 | case BZ_MEM_ERROR: |
991 | block = malloc ( (n + 1 + NUM_OVERSHOOT_BYTES) * sizeof(UChar) ); | 377 | outOfMemory (); |
992 | quadrant = malloc ( (n + NUM_OVERSHOOT_BYTES) * sizeof(Int16) ); | 378 | case BZ_IO_ERROR: |
993 | zptr = malloc ( n * sizeof(Int32) ); | 379 | errhandler_io: |
994 | ftab = malloc ( 65537 * sizeof(Int32) ); | 380 | ioError(); break; |
995 | 381 | default: | |
996 | if (block == NULL || quadrant == NULL || | 382 | panic ( "compress:unexpected error" ); |
997 | zptr == NULL || ftab == NULL) { | ||
998 | Int32 totalDraw | ||
999 | = (n + 1 + NUM_OVERSHOOT_BYTES) * sizeof(UChar) + | ||
1000 | (n + NUM_OVERSHOOT_BYTES) * sizeof(Int16) + | ||
1001 | n * sizeof(Int32) + | ||
1002 | 65537 * sizeof(Int32); | ||
1003 | |||
1004 | compressOutOfMemory ( totalDraw, n ); | ||
1005 | } | 383 | } |
1006 | 384 | ||
1007 | /*-- | 385 | panic ( "compress:end" ); |
1008 | Since we want valid indexes for block of | 386 | /*notreached*/ |
1009 | -1 to n + NUM_OVERSHOOT_BYTES - 1 | ||
1010 | inclusive. | ||
1011 | --*/ | ||
1012 | block++; | ||
1013 | |||
1014 | /*-- | ||
1015 | The back end needs a place to store the MTF values | ||
1016 | whilst it calculates the coding tables. We could | ||
1017 | put them in the zptr array. However, these values | ||
1018 | will fit in a short, so we overlay szptr at the | ||
1019 | start of zptr, in the hope of reducing the number | ||
1020 | of cache misses induced by the multiple traversals | ||
1021 | of the MTF values when calculating coding tables. | ||
1022 | Seems to improve compression speed by about 1%. | ||
1023 | --*/ | ||
1024 | szptr = (UInt16*)zptr; | ||
1025 | } | ||
1026 | |||
1027 | |||
1028 | /*---------------------------------------------*/ | ||
1029 | void setDecompressStructureSizes ( Int32 newSize100k ) | ||
1030 | { | ||
1031 | if (! (0 <= newSize100k && newSize100k <= 9 && | ||
1032 | 0 <= blockSize100k && blockSize100k <= 9)) | ||
1033 | panic ( "setDecompressStructureSizes" ); | ||
1034 | |||
1035 | if (newSize100k == blockSize100k) return; | ||
1036 | |||
1037 | blockSize100k = newSize100k; | ||
1038 | |||
1039 | if (ll16 != NULL) free ( ll16 ); | ||
1040 | if (ll4 != NULL) free ( ll4 ); | ||
1041 | if (ll8 != NULL) free ( ll8 ); | ||
1042 | if (tt != NULL) free ( tt ); | ||
1043 | |||
1044 | if (newSize100k == 0) return; | ||
1045 | |||
1046 | if (smallMode) { | ||
1047 | |||
1048 | Int32 n = 100000 * newSize100k; | ||
1049 | ll16 = malloc ( n * sizeof(UInt16) ); | ||
1050 | ll4 = malloc ( ((n+1) >> 1) * sizeof(UChar) ); | ||
1051 | |||
1052 | if (ll4 == NULL || ll16 == NULL) { | ||
1053 | Int32 totalDraw | ||
1054 | = n * sizeof(Int16) + ((n+1) >> 1) * sizeof(UChar); | ||
1055 | uncompressOutOfMemory ( totalDraw, n ); | ||
1056 | } | ||
1057 | |||
1058 | } else { | ||
1059 | |||
1060 | Int32 n = 100000 * newSize100k; | ||
1061 | ll8 = malloc ( n * sizeof(UChar) ); | ||
1062 | tt = malloc ( n * sizeof(Int32) ); | ||
1063 | |||
1064 | if (ll8 == NULL || tt == NULL) { | ||
1065 | Int32 totalDraw | ||
1066 | = n * sizeof(UChar) + n * sizeof(UInt32); | ||
1067 | uncompressOutOfMemory ( totalDraw, n ); | ||
1068 | } | ||
1069 | |||
1070 | } | ||
1071 | } | 387 | } |
1072 | 388 | ||
1073 | 389 | ||
1074 | 390 | ||
1075 | /*---------------------------------------------------*/ | ||
1076 | /*--- The new back end ---*/ | ||
1077 | /*---------------------------------------------------*/ | ||
1078 | |||
1079 | /*---------------------------------------------*/ | ||
1080 | void makeMaps ( void ) | ||
1081 | { | ||
1082 | Int32 i; | ||
1083 | nInUse = 0; | ||
1084 | for (i = 0; i < 256; i++) | ||
1085 | if (inUse[i]) { | ||
1086 | seqToUnseq[nInUse] = i; | ||
1087 | unseqToSeq[i] = nInUse; | ||
1088 | nInUse++; | ||
1089 | } | ||
1090 | } | ||
1091 | |||
1092 | |||
1093 | /*---------------------------------------------*/ | 391 | /*---------------------------------------------*/ |
1094 | void generateMTFValues ( void ) | 392 | Bool uncompressStream ( FILE *zStream, FILE *stream ) |
1095 | { | ||
1096 | UChar yy[256]; | ||
1097 | Int32 i, j; | ||
1098 | UChar tmp; | ||
1099 | UChar tmp2; | ||
1100 | Int32 zPend; | ||
1101 | Int32 wr; | ||
1102 | Int32 EOB; | ||
1103 | |||
1104 | makeMaps(); | ||
1105 | EOB = nInUse+1; | ||
1106 | |||
1107 | for (i = 0; i <= EOB; i++) mtfFreq[i] = 0; | ||
1108 | |||
1109 | wr = 0; | ||
1110 | zPend = 0; | ||
1111 | for (i = 0; i < nInUse; i++) yy[i] = (UChar) i; | ||
1112 | |||
1113 | |||
1114 | for (i = 0; i <= last; i++) { | ||
1115 | UChar ll_i; | ||
1116 | |||
1117 | #if DEBUG | ||
1118 | assert (wr <= i); | ||
1119 | #endif | ||
1120 | |||
1121 | ll_i = unseqToSeq[block[zptr[i] - 1]]; | ||
1122 | #if DEBUG | ||
1123 | assert (ll_i < nInUse); | ||
1124 | #endif | ||
1125 | |||
1126 | j = 0; | ||
1127 | tmp = yy[j]; | ||
1128 | while ( ll_i != tmp ) { | ||
1129 | j++; | ||
1130 | tmp2 = tmp; | ||
1131 | tmp = yy[j]; | ||
1132 | yy[j] = tmp2; | ||
1133 | }; | ||
1134 | yy[0] = tmp; | ||
1135 | |||
1136 | if (j == 0) { | ||
1137 | zPend++; | ||
1138 | } else { | ||
1139 | if (zPend > 0) { | ||
1140 | zPend--; | ||
1141 | while (True) { | ||
1142 | switch (zPend % 2) { | ||
1143 | case 0: szptr[wr] = RUNA; wr++; mtfFreq[RUNA]++; break; | ||
1144 | case 1: szptr[wr] = RUNB; wr++; mtfFreq[RUNB]++; break; | ||
1145 | }; | ||
1146 | if (zPend < 2) break; | ||
1147 | zPend = (zPend - 2) / 2; | ||
1148 | }; | ||
1149 | zPend = 0; | ||
1150 | } | ||
1151 | szptr[wr] = j+1; wr++; mtfFreq[j+1]++; | ||
1152 | } | ||
1153 | } | ||
1154 | |||
1155 | if (zPend > 0) { | ||
1156 | zPend--; | ||
1157 | while (True) { | ||
1158 | switch (zPend % 2) { | ||
1159 | case 0: szptr[wr] = RUNA; wr++; mtfFreq[RUNA]++; break; | ||
1160 | case 1: szptr[wr] = RUNB; wr++; mtfFreq[RUNB]++; break; | ||
1161 | }; | ||
1162 | if (zPend < 2) break; | ||
1163 | zPend = (zPend - 2) / 2; | ||
1164 | }; | ||
1165 | } | ||
1166 | |||
1167 | szptr[wr] = EOB; wr++; mtfFreq[EOB]++; | ||
1168 | |||
1169 | nMTF = wr; | ||
1170 | } | ||
1171 | |||
1172 | |||
1173 | /*---------------------------------------------*/ | ||
1174 | #define LESSER_ICOST 0 | ||
1175 | #define GREATER_ICOST 15 | ||
1176 | |||
1177 | void sendMTFValues ( void ) | ||
1178 | { | 393 | { |
1179 | Int32 v, t, i, j, gs, ge, totc, bt, bc, iter; | 394 | BZFILE* bzf = NULL; |
1180 | Int32 nSelectors, alphaSize, minLen, maxLen, selCtr; | 395 | Int32 bzerr, bzerr_dummy, ret, nread, streamNo, i; |
1181 | Int32 nGroups, nBytes; | 396 | UChar obuf[5000]; |
1182 | 397 | UChar unused[BZ_MAX_UNUSED]; | |
1183 | /*-- | 398 | Int32 nUnused; |
1184 | UChar len [N_GROUPS][MAX_ALPHA_SIZE]; | 399 | UChar* unusedTmp; |
1185 | is a global since the decoder also needs it. | ||
1186 | |||
1187 | Int32 code[N_GROUPS][MAX_ALPHA_SIZE]; | ||
1188 | Int32 rfreq[N_GROUPS][MAX_ALPHA_SIZE]; | ||
1189 | are also globals only used in this proc. | ||
1190 | Made global to keep stack frame size small. | ||
1191 | --*/ | ||
1192 | |||
1193 | |||
1194 | UInt16 cost[N_GROUPS]; | ||
1195 | Int32 fave[N_GROUPS]; | ||
1196 | |||
1197 | if (verbosity >= 3) | ||
1198 | fprintf ( stderr, | ||
1199 | " %d in block, %d after MTF & 1-2 coding, %d+2 syms in use\n", | ||
1200 | last+1, nMTF, nInUse ); | ||
1201 | |||
1202 | alphaSize = nInUse+2; | ||
1203 | for (t = 0; t < N_GROUPS; t++) | ||
1204 | for (v = 0; v < alphaSize; v++) | ||
1205 | len[t][v] = GREATER_ICOST; | ||
1206 | |||
1207 | /*--- Decide how many coding tables to use ---*/ | ||
1208 | if (nMTF <= 0) panic ( "sendMTFValues(0)" ); | ||
1209 | if (nMTF < 200) nGroups = 2; else | ||
1210 | if (nMTF < 800) nGroups = 4; else | ||
1211 | nGroups = 6; | ||
1212 | |||
1213 | /*--- Generate an initial set of coding tables ---*/ | ||
1214 | { | ||
1215 | Int32 nPart, remF, tFreq, aFreq; | ||
1216 | |||
1217 | nPart = nGroups; | ||
1218 | remF = nMTF; | ||
1219 | gs = 0; | ||
1220 | while (nPart > 0) { | ||
1221 | tFreq = remF / nPart; | ||
1222 | ge = gs-1; | ||
1223 | aFreq = 0; | ||
1224 | while (aFreq < tFreq && ge < alphaSize-1) { | ||
1225 | ge++; | ||
1226 | aFreq += mtfFreq[ge]; | ||
1227 | } | ||
1228 | |||
1229 | if (ge > gs | ||
1230 | && nPart != nGroups && nPart != 1 | ||
1231 | && ((nGroups-nPart) % 2 == 1)) { | ||
1232 | aFreq -= mtfFreq[ge]; | ||
1233 | ge--; | ||
1234 | } | ||
1235 | 400 | ||
1236 | if (verbosity >= 3) | 401 | nUnused = 0; |
1237 | fprintf ( stderr, | 402 | streamNo = 0; |
1238 | " initial group %d, [%d .. %d], has %d syms (%4.1f%%)\n", | ||
1239 | nPart, gs, ge, aFreq, | ||
1240 | (100.0 * (float)aFreq) / (float)nMTF ); | ||
1241 | |||
1242 | for (v = 0; v < alphaSize; v++) | ||
1243 | if (v >= gs && v <= ge) | ||
1244 | len[nPart-1][v] = LESSER_ICOST; else | ||
1245 | len[nPart-1][v] = GREATER_ICOST; | ||
1246 | |||
1247 | nPart--; | ||
1248 | gs = ge+1; | ||
1249 | remF -= aFreq; | ||
1250 | } | ||
1251 | } | ||
1252 | |||
1253 | /*--- | ||
1254 | Iterate up to N_ITERS times to improve the tables. | ||
1255 | ---*/ | ||
1256 | for (iter = 0; iter < N_ITERS; iter++) { | ||
1257 | |||
1258 | for (t = 0; t < nGroups; t++) fave[t] = 0; | ||
1259 | |||
1260 | for (t = 0; t < nGroups; t++) | ||
1261 | for (v = 0; v < alphaSize; v++) | ||
1262 | rfreq[t][v] = 0; | ||
1263 | |||
1264 | nSelectors = 0; | ||
1265 | totc = 0; | ||
1266 | gs = 0; | ||
1267 | while (True) { | ||
1268 | |||
1269 | /*--- Set group start & end marks. --*/ | ||
1270 | if (gs >= nMTF) break; | ||
1271 | ge = gs + G_SIZE - 1; | ||
1272 | if (ge >= nMTF) ge = nMTF-1; | ||
1273 | |||
1274 | /*-- | ||
1275 | Calculate the cost of this group as coded | ||
1276 | by each of the coding tables. | ||
1277 | --*/ | ||
1278 | for (t = 0; t < nGroups; t++) cost[t] = 0; | ||
1279 | |||
1280 | if (nGroups == 6) { | ||
1281 | register UInt16 cost0, cost1, cost2, cost3, cost4, cost5; | ||
1282 | cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0; | ||
1283 | for (i = gs; i <= ge; i++) { | ||
1284 | UInt16 icv = szptr[i]; | ||
1285 | cost0 += len[0][icv]; | ||
1286 | cost1 += len[1][icv]; | ||
1287 | cost2 += len[2][icv]; | ||
1288 | cost3 += len[3][icv]; | ||
1289 | cost4 += len[4][icv]; | ||
1290 | cost5 += len[5][icv]; | ||
1291 | } | ||
1292 | cost[0] = cost0; cost[1] = cost1; cost[2] = cost2; | ||
1293 | cost[3] = cost3; cost[4] = cost4; cost[5] = cost5; | ||
1294 | } else { | ||
1295 | for (i = gs; i <= ge; i++) { | ||
1296 | UInt16 icv = szptr[i]; | ||
1297 | for (t = 0; t < nGroups; t++) cost[t] += len[t][icv]; | ||
1298 | } | ||
1299 | } | ||
1300 | |||
1301 | /*-- | ||
1302 | Find the coding table which is best for this group, | ||
1303 | and record its identity in the selector table. | ||
1304 | --*/ | ||
1305 | bc = 999999999; bt = -1; | ||
1306 | for (t = 0; t < nGroups; t++) | ||
1307 | if (cost[t] < bc) { bc = cost[t]; bt = t; }; | ||
1308 | totc += bc; | ||
1309 | fave[bt]++; | ||
1310 | selector[nSelectors] = bt; | ||
1311 | nSelectors++; | ||
1312 | |||
1313 | /*-- | ||
1314 | Increment the symbol frequencies for the selected table. | ||
1315 | --*/ | ||
1316 | for (i = gs; i <= ge; i++) | ||
1317 | rfreq[bt][ szptr[i] ]++; | ||
1318 | |||
1319 | gs = ge+1; | ||
1320 | } | ||
1321 | if (verbosity >= 3) { | ||
1322 | fprintf ( stderr, | ||
1323 | " pass %d: size is %d, grp uses are ", | ||
1324 | iter+1, totc/8 ); | ||
1325 | for (t = 0; t < nGroups; t++) | ||
1326 | fprintf ( stderr, "%d ", fave[t] ); | ||
1327 | fprintf ( stderr, "\n" ); | ||
1328 | } | ||
1329 | |||
1330 | /*-- | ||
1331 | Recompute the tables based on the accumulated frequencies. | ||
1332 | --*/ | ||
1333 | for (t = 0; t < nGroups; t++) | ||
1334 | hbMakeCodeLengths ( &len[t][0], &rfreq[t][0], alphaSize, 20 ); | ||
1335 | } | ||
1336 | 403 | ||
404 | SET_BINARY_MODE(stream); | ||
405 | SET_BINARY_MODE(zStream); | ||
1337 | 406 | ||
1338 | if (!(nGroups < 8)) panic ( "sendMTFValues(1)" ); | 407 | if (ferror(stream)) goto errhandler_io; |
1339 | if (!(nSelectors < 32768 && | 408 | if (ferror(zStream)) goto errhandler_io; |
1340 | nSelectors <= (2 + (900000 / G_SIZE)))) | ||
1341 | panic ( "sendMTFValues(2)" ); | ||
1342 | |||
1343 | |||
1344 | /*--- Compute MTF values for the selectors. ---*/ | ||
1345 | { | ||
1346 | UChar pos[N_GROUPS], ll_i, tmp2, tmp; | ||
1347 | for (i = 0; i < nGroups; i++) pos[i] = i; | ||
1348 | for (i = 0; i < nSelectors; i++) { | ||
1349 | ll_i = selector[i]; | ||
1350 | j = 0; | ||
1351 | tmp = pos[j]; | ||
1352 | while ( ll_i != tmp ) { | ||
1353 | j++; | ||
1354 | tmp2 = tmp; | ||
1355 | tmp = pos[j]; | ||
1356 | pos[j] = tmp2; | ||
1357 | }; | ||
1358 | pos[0] = tmp; | ||
1359 | selectorMtf[i] = j; | ||
1360 | } | ||
1361 | }; | ||
1362 | |||
1363 | /*--- Assign actual codes for the tables. --*/ | ||
1364 | for (t = 0; t < nGroups; t++) { | ||
1365 | minLen = 32; | ||
1366 | maxLen = 0; | ||
1367 | for (i = 0; i < alphaSize; i++) { | ||
1368 | if (len[t][i] > maxLen) maxLen = len[t][i]; | ||
1369 | if (len[t][i] < minLen) minLen = len[t][i]; | ||
1370 | } | ||
1371 | if (maxLen > 20) panic ( "sendMTFValues(3)" ); | ||
1372 | if (minLen < 1) panic ( "sendMTFValues(4)" ); | ||
1373 | hbAssignCodes ( &code[t][0], &len[t][0], | ||
1374 | minLen, maxLen, alphaSize ); | ||
1375 | } | ||
1376 | |||
1377 | /*--- Transmit the mapping table. ---*/ | ||
1378 | { | ||
1379 | Bool inUse16[16]; | ||
1380 | for (i = 0; i < 16; i++) { | ||
1381 | inUse16[i] = False; | ||
1382 | for (j = 0; j < 16; j++) | ||
1383 | if (inUse[i * 16 + j]) inUse16[i] = True; | ||
1384 | } | ||
1385 | |||
1386 | nBytes = bytesOut; | ||
1387 | for (i = 0; i < 16; i++) | ||
1388 | if (inUse16[i]) bsW(1,1); else bsW(1,0); | ||
1389 | |||
1390 | for (i = 0; i < 16; i++) | ||
1391 | if (inUse16[i]) | ||
1392 | for (j = 0; j < 16; j++) | ||
1393 | if (inUse[i * 16 + j]) bsW(1,1); else bsW(1,0); | ||
1394 | |||
1395 | if (verbosity >= 3) | ||
1396 | fprintf ( stderr, " bytes: mapping %d, ", bytesOut-nBytes ); | ||
1397 | } | ||
1398 | |||
1399 | /*--- Now the selectors. ---*/ | ||
1400 | nBytes = bytesOut; | ||
1401 | bsW ( 3, nGroups ); | ||
1402 | bsW ( 15, nSelectors ); | ||
1403 | for (i = 0; i < nSelectors; i++) { | ||
1404 | for (j = 0; j < selectorMtf[i]; j++) bsW(1,1); | ||
1405 | bsW(1,0); | ||
1406 | } | ||
1407 | if (verbosity >= 3) | ||
1408 | fprintf ( stderr, "selectors %d, ", bytesOut-nBytes ); | ||
1409 | |||
1410 | /*--- Now the coding tables. ---*/ | ||
1411 | nBytes = bytesOut; | ||
1412 | |||
1413 | for (t = 0; t < nGroups; t++) { | ||
1414 | Int32 curr = len[t][0]; | ||
1415 | bsW ( 5, curr ); | ||
1416 | for (i = 0; i < alphaSize; i++) { | ||
1417 | while (curr < len[t][i]) { bsW(2,2); curr++; /* 10 */ }; | ||
1418 | while (curr > len[t][i]) { bsW(2,3); curr--; /* 11 */ }; | ||
1419 | bsW ( 1, 0 ); | ||
1420 | } | ||
1421 | } | ||
1422 | |||
1423 | if (verbosity >= 3) | ||
1424 | fprintf ( stderr, "code lengths %d, ", bytesOut-nBytes ); | ||
1425 | 409 | ||
1426 | /*--- And finally, the block data proper ---*/ | ||
1427 | nBytes = bytesOut; | ||
1428 | selCtr = 0; | ||
1429 | gs = 0; | ||
1430 | while (True) { | 410 | while (True) { |
1431 | if (gs >= nMTF) break; | ||
1432 | ge = gs + G_SIZE - 1; | ||
1433 | if (ge >= nMTF) ge = nMTF-1; | ||
1434 | for (i = gs; i <= ge; i++) { | ||
1435 | #if DEBUG | ||
1436 | assert (selector[selCtr] < nGroups); | ||
1437 | #endif | ||
1438 | bsW ( len [selector[selCtr]] [szptr[i]], | ||
1439 | code [selector[selCtr]] [szptr[i]] ); | ||
1440 | } | ||
1441 | 411 | ||
1442 | gs = ge+1; | 412 | bzf = bzReadOpen ( |
1443 | selCtr++; | 413 | &bzerr, zStream, verbosity, |
1444 | } | 414 | (int)smallMode, unused, nUnused |
1445 | if (!(selCtr == nSelectors)) panic ( "sendMTFValues(5)" ); | 415 | ); |
1446 | 416 | if (bzf == NULL || bzerr != BZ_OK) goto errhandler; | |
1447 | if (verbosity >= 3) | 417 | streamNo++; |
1448 | fprintf ( stderr, "codes %d\n", bytesOut-nBytes ); | 418 | |
1449 | } | 419 | while (bzerr == BZ_OK) { |
1450 | 420 | nread = bzRead ( &bzerr, bzf, obuf, 5000 ); | |
1451 | 421 | if (bzerr == BZ_DATA_ERROR_MAGIC) goto errhandler; | |
1452 | /*---------------------------------------------*/ | 422 | if ((bzerr == BZ_OK || bzerr == BZ_STREAM_END) && nread > 0) |
1453 | void moveToFrontCodeAndSend ( void ) | 423 | fwrite ( obuf, sizeof(UChar), nread, stream ); |
1454 | { | 424 | if (ferror(stream)) goto errhandler_io; |
1455 | bsPutIntVS ( 24, origPtr ); | ||
1456 | generateMTFValues(); | ||
1457 | sendMTFValues(); | ||
1458 | } | ||
1459 | |||
1460 | |||
1461 | /*---------------------------------------------*/ | ||
1462 | void recvDecodingTables ( void ) | ||
1463 | { | ||
1464 | Int32 i, j, t, nGroups, nSelectors, alphaSize; | ||
1465 | Int32 minLen, maxLen; | ||
1466 | Bool inUse16[16]; | ||
1467 | |||
1468 | /*--- Receive the mapping table ---*/ | ||
1469 | for (i = 0; i < 16; i++) | ||
1470 | if (bsR(1) == 1) | ||
1471 | inUse16[i] = True; else | ||
1472 | inUse16[i] = False; | ||
1473 | |||
1474 | for (i = 0; i < 256; i++) inUse[i] = False; | ||
1475 | |||
1476 | for (i = 0; i < 16; i++) | ||
1477 | if (inUse16[i]) | ||
1478 | for (j = 0; j < 16; j++) | ||
1479 | if (bsR(1) == 1) inUse[i * 16 + j] = True; | ||
1480 | |||
1481 | makeMaps(); | ||
1482 | alphaSize = nInUse+2; | ||
1483 | |||
1484 | /*--- Now the selectors ---*/ | ||
1485 | nGroups = bsR ( 3 ); | ||
1486 | nSelectors = bsR ( 15 ); | ||
1487 | for (i = 0; i < nSelectors; i++) { | ||
1488 | j = 0; | ||
1489 | while (bsR(1) == 1) j++; | ||
1490 | selectorMtf[i] = j; | ||
1491 | } | ||
1492 | |||
1493 | /*--- Undo the MTF values for the selectors. ---*/ | ||
1494 | { | ||
1495 | UChar pos[N_GROUPS], tmp, v; | ||
1496 | for (v = 0; v < nGroups; v++) pos[v] = v; | ||
1497 | |||
1498 | for (i = 0; i < nSelectors; i++) { | ||
1499 | v = selectorMtf[i]; | ||
1500 | tmp = pos[v]; | ||
1501 | while (v > 0) { pos[v] = pos[v-1]; v--; } | ||
1502 | pos[0] = tmp; | ||
1503 | selector[i] = tmp; | ||
1504 | } | 425 | } |
1505 | } | 426 | if (bzerr != BZ_STREAM_END) goto errhandler; |
1506 | |||
1507 | /*--- Now the coding tables ---*/ | ||
1508 | for (t = 0; t < nGroups; t++) { | ||
1509 | Int32 curr = bsR ( 5 ); | ||
1510 | for (i = 0; i < alphaSize; i++) { | ||
1511 | while (bsR(1) == 1) { | ||
1512 | if (bsR(1) == 0) curr++; else curr--; | ||
1513 | } | ||
1514 | len[t][i] = curr; | ||
1515 | } | ||
1516 | } | ||
1517 | |||
1518 | /*--- Create the Huffman decoding tables ---*/ | ||
1519 | for (t = 0; t < nGroups; t++) { | ||
1520 | minLen = 32; | ||
1521 | maxLen = 0; | ||
1522 | for (i = 0; i < alphaSize; i++) { | ||
1523 | if (len[t][i] > maxLen) maxLen = len[t][i]; | ||
1524 | if (len[t][i] < minLen) minLen = len[t][i]; | ||
1525 | } | ||
1526 | hbCreateDecodeTables ( | ||
1527 | &limit[t][0], &base[t][0], &perm[t][0], &len[t][0], | ||
1528 | minLen, maxLen, alphaSize | ||
1529 | ); | ||
1530 | minLens[t] = minLen; | ||
1531 | } | ||
1532 | } | ||
1533 | |||
1534 | |||
1535 | /*---------------------------------------------*/ | ||
1536 | #define GET_MTF_VAL(lval) \ | ||
1537 | { \ | ||
1538 | Int32 zt, zn, zvec, zj; \ | ||
1539 | if (groupPos == 0) { \ | ||
1540 | groupNo++; \ | ||
1541 | groupPos = G_SIZE; \ | ||
1542 | } \ | ||
1543 | groupPos--; \ | ||
1544 | zt = selector[groupNo]; \ | ||
1545 | zn = minLens[zt]; \ | ||
1546 | zvec = bsR ( zn ); \ | ||
1547 | while (zvec > limit[zt][zn]) { \ | ||
1548 | zn++; bsR1(zj); \ | ||
1549 | zvec = (zvec << 1) | zj; \ | ||
1550 | }; \ | ||
1551 | lval = perm[zt][zvec - base[zt][zn]]; \ | ||
1552 | } | ||
1553 | |||
1554 | |||
1555 | /*---------------------------------------------*/ | ||
1556 | void getAndMoveToFrontDecode ( void ) | ||
1557 | { | ||
1558 | UChar yy[256]; | ||
1559 | Int32 i, j, nextSym, limitLast; | ||
1560 | Int32 EOB, groupNo, groupPos; | ||
1561 | |||
1562 | limitLast = 100000 * blockSize100k; | ||
1563 | origPtr = bsGetIntVS ( 24 ); | ||
1564 | |||
1565 | recvDecodingTables(); | ||
1566 | EOB = nInUse+1; | ||
1567 | groupNo = -1; | ||
1568 | groupPos = 0; | ||
1569 | |||
1570 | /*-- | ||
1571 | Setting up the unzftab entries here is not strictly | ||
1572 | necessary, but it does save having to do it later | ||
1573 | in a separate pass, and so saves a block's worth of | ||
1574 | cache misses. | ||
1575 | --*/ | ||
1576 | for (i = 0; i <= 255; i++) unzftab[i] = 0; | ||
1577 | |||
1578 | for (i = 0; i <= 255; i++) yy[i] = (UChar) i; | ||
1579 | |||
1580 | last = -1; | ||
1581 | 427 | ||
1582 | GET_MTF_VAL(nextSym); | 428 | bzReadGetUnused ( &bzerr, bzf, (void**)(&unusedTmp), &nUnused ); |
429 | if (bzerr != BZ_OK) panic ( "decompress:bzReadGetUnused" ); | ||
1583 | 430 | ||
1584 | while (True) { | 431 | for (i = 0; i < nUnused; i++) unused[i] = unusedTmp[i]; |
1585 | |||
1586 | if (nextSym == EOB) break; | ||
1587 | |||
1588 | if (nextSym == RUNA || nextSym == RUNB) { | ||
1589 | UChar ch; | ||
1590 | Int32 s = -1; | ||
1591 | Int32 N = 1; | ||
1592 | do { | ||
1593 | if (nextSym == RUNA) s = s + (0+1) * N; else | ||
1594 | if (nextSym == RUNB) s = s + (1+1) * N; | ||
1595 | N = N * 2; | ||
1596 | GET_MTF_VAL(nextSym); | ||
1597 | } | ||
1598 | while (nextSym == RUNA || nextSym == RUNB); | ||
1599 | 432 | ||
1600 | s++; | 433 | bzReadClose ( &bzerr, bzf ); |
1601 | ch = seqToUnseq[yy[0]]; | 434 | if (bzerr != BZ_OK) panic ( "decompress:bzReadGetUnused" ); |
1602 | unzftab[ch] += s; | ||
1603 | 435 | ||
1604 | if (smallMode) | 436 | if (nUnused == 0 && myfeof(zStream)) break; |
1605 | while (s > 0) { | ||
1606 | last++; | ||
1607 | ll16[last] = ch; | ||
1608 | s--; | ||
1609 | } | ||
1610 | else | ||
1611 | while (s > 0) { | ||
1612 | last++; | ||
1613 | ll8[last] = ch; | ||
1614 | s--; | ||
1615 | }; | ||
1616 | |||
1617 | if (last >= limitLast) blockOverrun(); | ||
1618 | continue; | ||
1619 | |||
1620 | } else { | ||
1621 | |||
1622 | UChar tmp; | ||
1623 | last++; if (last >= limitLast) blockOverrun(); | ||
1624 | |||
1625 | tmp = yy[nextSym-1]; | ||
1626 | unzftab[seqToUnseq[tmp]]++; | ||
1627 | if (smallMode) | ||
1628 | ll16[last] = seqToUnseq[tmp]; else | ||
1629 | ll8[last] = seqToUnseq[tmp]; | ||
1630 | |||
1631 | /*-- | ||
1632 | This loop is hammered during decompression, | ||
1633 | hence the unrolling. | ||
1634 | |||
1635 | for (j = nextSym-1; j > 0; j--) yy[j] = yy[j-1]; | ||
1636 | --*/ | ||
1637 | |||
1638 | j = nextSym-1; | ||
1639 | for (; j > 3; j -= 4) { | ||
1640 | yy[j] = yy[j-1]; | ||
1641 | yy[j-1] = yy[j-2]; | ||
1642 | yy[j-2] = yy[j-3]; | ||
1643 | yy[j-3] = yy[j-4]; | ||
1644 | } | ||
1645 | for (; j > 0; j--) yy[j] = yy[j-1]; | ||
1646 | 437 | ||
1647 | yy[0] = tmp; | ||
1648 | GET_MTF_VAL(nextSym); | ||
1649 | continue; | ||
1650 | } | ||
1651 | } | 438 | } |
1652 | } | ||
1653 | |||
1654 | |||
1655 | /*---------------------------------------------------*/ | ||
1656 | /*--- Block-sorting machinery ---*/ | ||
1657 | /*---------------------------------------------------*/ | ||
1658 | 439 | ||
1659 | /*---------------------------------------------*/ | 440 | if (ferror(zStream)) goto errhandler_io; |
1660 | /*-- | 441 | ret = fclose ( zStream ); |
1661 | Compare two strings in block. We assume (see | 442 | if (ret == EOF) goto errhandler_io; |
1662 | discussion above) that i1 and i2 have a max | ||
1663 | offset of 10 on entry, and that the first | ||
1664 | bytes of both block and quadrant have been | ||
1665 | copied into the "overshoot area", ie | ||
1666 | into the subscript range | ||
1667 | [last+1 .. last+NUM_OVERSHOOT_BYTES]. | ||
1668 | --*/ | ||
1669 | INLINE Bool fullGtU ( Int32 i1, Int32 i2 ) | ||
1670 | { | ||
1671 | Int32 k; | ||
1672 | UChar c1, c2; | ||
1673 | UInt16 s1, s2; | ||
1674 | |||
1675 | #if DEBUG | ||
1676 | /*-- | ||
1677 | shellsort shouldn't ask to compare | ||
1678 | something with itself. | ||
1679 | --*/ | ||
1680 | assert (i1 != i2); | ||
1681 | #endif | ||
1682 | |||
1683 | c1 = block[i1]; | ||
1684 | c2 = block[i2]; | ||
1685 | if (c1 != c2) return (c1 > c2); | ||
1686 | i1++; i2++; | ||
1687 | |||
1688 | c1 = block[i1]; | ||
1689 | c2 = block[i2]; | ||
1690 | if (c1 != c2) return (c1 > c2); | ||
1691 | i1++; i2++; | ||
1692 | |||
1693 | c1 = block[i1]; | ||
1694 | c2 = block[i2]; | ||
1695 | if (c1 != c2) return (c1 > c2); | ||
1696 | i1++; i2++; | ||
1697 | |||
1698 | c1 = block[i1]; | ||
1699 | c2 = block[i2]; | ||
1700 | if (c1 != c2) return (c1 > c2); | ||
1701 | i1++; i2++; | ||
1702 | |||
1703 | c1 = block[i1]; | ||
1704 | c2 = block[i2]; | ||
1705 | if (c1 != c2) return (c1 > c2); | ||
1706 | i1++; i2++; | ||
1707 | |||
1708 | c1 = block[i1]; | ||
1709 | c2 = block[i2]; | ||
1710 | if (c1 != c2) return (c1 > c2); | ||
1711 | i1++; i2++; | ||
1712 | |||
1713 | k = last + 1; | ||
1714 | |||
1715 | do { | ||
1716 | |||
1717 | c1 = block[i1]; | ||
1718 | c2 = block[i2]; | ||
1719 | if (c1 != c2) return (c1 > c2); | ||
1720 | s1 = quadrant[i1]; | ||
1721 | s2 = quadrant[i2]; | ||
1722 | if (s1 != s2) return (s1 > s2); | ||
1723 | i1++; i2++; | ||
1724 | |||
1725 | c1 = block[i1]; | ||
1726 | c2 = block[i2]; | ||
1727 | if (c1 != c2) return (c1 > c2); | ||
1728 | s1 = quadrant[i1]; | ||
1729 | s2 = quadrant[i2]; | ||
1730 | if (s1 != s2) return (s1 > s2); | ||
1731 | i1++; i2++; | ||
1732 | |||
1733 | c1 = block[i1]; | ||
1734 | c2 = block[i2]; | ||
1735 | if (c1 != c2) return (c1 > c2); | ||
1736 | s1 = quadrant[i1]; | ||
1737 | s2 = quadrant[i2]; | ||
1738 | if (s1 != s2) return (s1 > s2); | ||
1739 | i1++; i2++; | ||
1740 | |||
1741 | c1 = block[i1]; | ||
1742 | c2 = block[i2]; | ||
1743 | if (c1 != c2) return (c1 > c2); | ||
1744 | s1 = quadrant[i1]; | ||
1745 | s2 = quadrant[i2]; | ||
1746 | if (s1 != s2) return (s1 > s2); | ||
1747 | i1++; i2++; | ||
1748 | |||
1749 | if (i1 > last) { i1 -= last; i1--; }; | ||
1750 | if (i2 > last) { i2 -= last; i2--; }; | ||
1751 | |||
1752 | k -= 4; | ||
1753 | workDone++; | ||
1754 | } | ||
1755 | while (k >= 0); | ||
1756 | 443 | ||
1757 | return False; | 444 | if (ferror(stream)) goto errhandler_io; |
1758 | } | 445 | ret = fflush ( stream ); |
1759 | 446 | if (ret != 0) goto errhandler_io; | |
1760 | /*---------------------------------------------*/ | 447 | if (stream != stdout) { |
1761 | /*-- | 448 | ret = fclose ( stream ); |
1762 | Knuth's increments seem to work better | 449 | if (ret == EOF) goto errhandler_io; |
1763 | than Incerpi-Sedgewick here. Possibly | ||
1764 | because the number of elems to sort is | ||
1765 | usually small, typically <= 20. | ||
1766 | --*/ | ||
1767 | Int32 incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280, | ||
1768 | 9841, 29524, 88573, 265720, | ||
1769 | 797161, 2391484 }; | ||
1770 | |||
1771 | void simpleSort ( Int32 lo, Int32 hi, Int32 d ) | ||
1772 | { | ||
1773 | Int32 i, j, h, bigN, hp; | ||
1774 | Int32 v; | ||
1775 | |||
1776 | bigN = hi - lo + 1; | ||
1777 | if (bigN < 2) return; | ||
1778 | |||
1779 | hp = 0; | ||
1780 | while (incs[hp] < bigN) hp++; | ||
1781 | hp--; | ||
1782 | |||
1783 | for (; hp >= 0; hp--) { | ||
1784 | h = incs[hp]; | ||
1785 | if (verbosity >= 5) | ||
1786 | fprintf ( stderr, " shell increment %d\n", h ); | ||
1787 | |||
1788 | i = lo + h; | ||
1789 | while (True) { | ||
1790 | |||
1791 | /*-- copy 1 --*/ | ||
1792 | if (i > hi) break; | ||
1793 | v = zptr[i]; | ||
1794 | j = i; | ||
1795 | while ( fullGtU ( zptr[j-h]+d, v+d ) ) { | ||
1796 | zptr[j] = zptr[j-h]; | ||
1797 | j = j - h; | ||
1798 | if (j <= (lo + h - 1)) break; | ||
1799 | } | ||
1800 | zptr[j] = v; | ||
1801 | i++; | ||
1802 | |||
1803 | /*-- copy 2 --*/ | ||
1804 | if (i > hi) break; | ||
1805 | v = zptr[i]; | ||
1806 | j = i; | ||
1807 | while ( fullGtU ( zptr[j-h]+d, v+d ) ) { | ||
1808 | zptr[j] = zptr[j-h]; | ||
1809 | j = j - h; | ||
1810 | if (j <= (lo + h - 1)) break; | ||
1811 | } | ||
1812 | zptr[j] = v; | ||
1813 | i++; | ||
1814 | |||
1815 | /*-- copy 3 --*/ | ||
1816 | if (i > hi) break; | ||
1817 | v = zptr[i]; | ||
1818 | j = i; | ||
1819 | while ( fullGtU ( zptr[j-h]+d, v+d ) ) { | ||
1820 | zptr[j] = zptr[j-h]; | ||
1821 | j = j - h; | ||
1822 | if (j <= (lo + h - 1)) break; | ||
1823 | } | ||
1824 | zptr[j] = v; | ||
1825 | i++; | ||
1826 | |||
1827 | if (workDone > workLimit && firstAttempt) return; | ||
1828 | } | ||
1829 | } | ||
1830 | } | ||
1831 | |||
1832 | |||
1833 | /*---------------------------------------------*/ | ||
1834 | /*-- | ||
1835 | The following is an implementation of | ||
1836 | an elegant 3-way quicksort for strings, | ||
1837 | described in a paper "Fast Algorithms for | ||
1838 | Sorting and Searching Strings", by Robert | ||
1839 | Sedgewick and Jon L. Bentley. | ||
1840 | --*/ | ||
1841 | |||
1842 | #define swap(lv1, lv2) \ | ||
1843 | { Int32 tmp = lv1; lv1 = lv2; lv2 = tmp; } | ||
1844 | |||
1845 | INLINE void vswap ( Int32 p1, Int32 p2, Int32 n ) | ||
1846 | { | ||
1847 | while (n > 0) { | ||
1848 | swap(zptr[p1], zptr[p2]); | ||
1849 | p1++; p2++; n--; | ||
1850 | } | ||
1851 | } | ||
1852 | |||
1853 | INLINE UChar med3 ( UChar a, UChar b, UChar c ) | ||
1854 | { | ||
1855 | UChar t; | ||
1856 | if (a > b) { t = a; a = b; b = t; }; | ||
1857 | if (b > c) { t = b; b = c; c = t; }; | ||
1858 | if (a > b) b = a; | ||
1859 | return b; | ||
1860 | } | ||
1861 | |||
1862 | |||
1863 | #define min(a,b) ((a) < (b)) ? (a) : (b) | ||
1864 | |||
1865 | typedef | ||
1866 | struct { Int32 ll; Int32 hh; Int32 dd; } | ||
1867 | StackElem; | ||
1868 | |||
1869 | #define push(lz,hz,dz) { stack[sp].ll = lz; \ | ||
1870 | stack[sp].hh = hz; \ | ||
1871 | stack[sp].dd = dz; \ | ||
1872 | sp++; } | ||
1873 | |||
1874 | #define pop(lz,hz,dz) { sp--; \ | ||
1875 | lz = stack[sp].ll; \ | ||
1876 | hz = stack[sp].hh; \ | ||
1877 | dz = stack[sp].dd; } | ||
1878 | |||
1879 | #define SMALL_THRESH 20 | ||
1880 | #define DEPTH_THRESH 10 | ||
1881 | |||
1882 | /*-- | ||
1883 | If you are ever unlucky/improbable enough | ||
1884 | to get a stack overflow whilst sorting, | ||
1885 | increase the following constant and try | ||
1886 | again. In practice I have never seen the | ||
1887 | stack go above 27 elems, so the following | ||
1888 | limit seems very generous. | ||
1889 | --*/ | ||
1890 | #define QSORT_STACK_SIZE 1000 | ||
1891 | |||
1892 | |||
1893 | void qSort3 ( Int32 loSt, Int32 hiSt, Int32 dSt ) | ||
1894 | { | ||
1895 | Int32 unLo, unHi, ltLo, gtHi, med, n, m; | ||
1896 | Int32 sp, lo, hi, d; | ||
1897 | StackElem stack[QSORT_STACK_SIZE]; | ||
1898 | |||
1899 | sp = 0; | ||
1900 | push ( loSt, hiSt, dSt ); | ||
1901 | |||
1902 | while (sp > 0) { | ||
1903 | |||
1904 | if (sp >= QSORT_STACK_SIZE) panic ( "stack overflow in qSort3" ); | ||
1905 | |||
1906 | pop ( lo, hi, d ); | ||
1907 | |||
1908 | if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH) { | ||
1909 | simpleSort ( lo, hi, d ); | ||
1910 | if (workDone > workLimit && firstAttempt) return; | ||
1911 | continue; | ||
1912 | } | ||
1913 | |||
1914 | med = med3 ( block[zptr[ lo ]+d], | ||
1915 | block[zptr[ hi ]+d], | ||
1916 | block[zptr[ (lo+hi)>>1 ]+d] ); | ||
1917 | |||
1918 | unLo = ltLo = lo; | ||
1919 | unHi = gtHi = hi; | ||
1920 | |||
1921 | while (True) { | ||
1922 | while (True) { | ||
1923 | if (unLo > unHi) break; | ||
1924 | n = ((Int32)block[zptr[unLo]+d]) - med; | ||
1925 | if (n == 0) { swap(zptr[unLo], zptr[ltLo]); ltLo++; unLo++; continue; }; | ||
1926 | if (n > 0) break; | ||
1927 | unLo++; | ||
1928 | } | ||
1929 | while (True) { | ||
1930 | if (unLo > unHi) break; | ||
1931 | n = ((Int32)block[zptr[unHi]+d]) - med; | ||
1932 | if (n == 0) { swap(zptr[unHi], zptr[gtHi]); gtHi--; unHi--; continue; }; | ||
1933 | if (n < 0) break; | ||
1934 | unHi--; | ||
1935 | } | ||
1936 | if (unLo > unHi) break; | ||
1937 | swap(zptr[unLo], zptr[unHi]); unLo++; unHi--; | ||
1938 | } | ||
1939 | #if DEBUG | ||
1940 | assert (unHi == unLo-1); | ||
1941 | #endif | ||
1942 | |||
1943 | if (gtHi < ltLo) { | ||
1944 | push(lo, hi, d+1 ); | ||
1945 | continue; | ||
1946 | } | ||
1947 | |||
1948 | n = min(ltLo-lo, unLo-ltLo); vswap(lo, unLo-n, n); | ||
1949 | m = min(hi-gtHi, gtHi-unHi); vswap(unLo, hi-m+1, m); | ||
1950 | |||
1951 | n = lo + unLo - ltLo - 1; | ||
1952 | m = hi - (gtHi - unHi) + 1; | ||
1953 | |||
1954 | push ( lo, n, d ); | ||
1955 | push ( n+1, m-1, d+1 ); | ||
1956 | push ( m, hi, d ); | ||
1957 | } | ||
1958 | } | ||
1959 | |||
1960 | |||
1961 | /*---------------------------------------------*/ | ||
1962 | |||
1963 | #define BIGFREQ(b) (ftab[((b)+1) << 8] - ftab[(b) << 8]) | ||
1964 | |||
1965 | #define SETMASK (1 << 21) | ||
1966 | #define CLEARMASK (~(SETMASK)) | ||
1967 | |||
1968 | void sortIt ( void ) | ||
1969 | { | ||
1970 | Int32 i, j, ss, sb; | ||
1971 | Int32 runningOrder[256]; | ||
1972 | Int32 copy[256]; | ||
1973 | Bool bigDone[256]; | ||
1974 | UChar c1, c2; | ||
1975 | Int32 numQSorted; | ||
1976 | |||
1977 | /*-- | ||
1978 | In the various block-sized structures, live data runs | ||
1979 | from 0 to last+NUM_OVERSHOOT_BYTES inclusive. First, | ||
1980 | set up the overshoot area for block. | ||
1981 | --*/ | ||
1982 | |||
1983 | if (verbosity >= 4) fprintf ( stderr, " sort initialise ...\n" ); | ||
1984 | for (i = 0; i < NUM_OVERSHOOT_BYTES; i++) | ||
1985 | block[last+i+1] = block[i % (last+1)]; | ||
1986 | for (i = 0; i <= last+NUM_OVERSHOOT_BYTES; i++) | ||
1987 | quadrant[i] = 0; | ||
1988 | |||
1989 | block[-1] = block[last]; | ||
1990 | |||
1991 | if (last < 4000) { | ||
1992 | |||
1993 | /*-- | ||
1994 | Use simpleSort(), since the full sorting mechanism | ||
1995 | has quite a large constant overhead. | ||
1996 | --*/ | ||
1997 | if (verbosity >= 4) fprintf ( stderr, " simpleSort ...\n" ); | ||
1998 | for (i = 0; i <= last; i++) zptr[i] = i; | ||
1999 | firstAttempt = False; | ||
2000 | workDone = workLimit = 0; | ||
2001 | simpleSort ( 0, last, 0 ); | ||
2002 | if (verbosity >= 4) fprintf ( stderr, " simpleSort done.\n" ); | ||
2003 | |||
2004 | } else { | ||
2005 | |||
2006 | numQSorted = 0; | ||
2007 | for (i = 0; i <= 255; i++) bigDone[i] = False; | ||
2008 | |||
2009 | if (verbosity >= 4) fprintf ( stderr, " bucket sorting ...\n" ); | ||
2010 | |||
2011 | for (i = 0; i <= 65536; i++) ftab[i] = 0; | ||
2012 | |||
2013 | c1 = block[-1]; | ||
2014 | for (i = 0; i <= last; i++) { | ||
2015 | c2 = block[i]; | ||
2016 | ftab[(c1 << 8) + c2]++; | ||
2017 | c1 = c2; | ||
2018 | } | ||
2019 | |||
2020 | for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1]; | ||
2021 | |||
2022 | c1 = block[0]; | ||
2023 | for (i = 0; i < last; i++) { | ||
2024 | c2 = block[i+1]; | ||
2025 | j = (c1 << 8) + c2; | ||
2026 | c1 = c2; | ||
2027 | ftab[j]--; | ||
2028 | zptr[ftab[j]] = i; | ||
2029 | } | ||
2030 | j = (block[last] << 8) + block[0]; | ||
2031 | ftab[j]--; | ||
2032 | zptr[ftab[j]] = last; | ||
2033 | |||
2034 | /*-- | ||
2035 | Now ftab contains the first loc of every small bucket. | ||
2036 | Calculate the running order, from smallest to largest | ||
2037 | big bucket. | ||
2038 | --*/ | ||
2039 | |||
2040 | for (i = 0; i <= 255; i++) runningOrder[i] = i; | ||
2041 | |||
2042 | { | ||
2043 | Int32 vv; | ||
2044 | Int32 h = 1; | ||
2045 | do h = 3 * h + 1; while (h <= 256); | ||
2046 | do { | ||
2047 | h = h / 3; | ||
2048 | for (i = h; i <= 255; i++) { | ||
2049 | vv = runningOrder[i]; | ||
2050 | j = i; | ||
2051 | while ( BIGFREQ(runningOrder[j-h]) > BIGFREQ(vv) ) { | ||
2052 | runningOrder[j] = runningOrder[j-h]; | ||
2053 | j = j - h; | ||
2054 | if (j <= (h - 1)) goto zero; | ||
2055 | } | ||
2056 | zero: | ||
2057 | runningOrder[j] = vv; | ||
2058 | } | ||
2059 | } while (h != 1); | ||
2060 | } | ||
2061 | |||
2062 | /*-- | ||
2063 | The main sorting loop. | ||
2064 | --*/ | ||
2065 | |||
2066 | for (i = 0; i <= 255; i++) { | ||
2067 | |||
2068 | /*-- | ||
2069 | Process big buckets, starting with the least full. | ||
2070 | --*/ | ||
2071 | ss = runningOrder[i]; | ||
2072 | |||
2073 | /*-- | ||
2074 | Complete the big bucket [ss] by quicksorting | ||
2075 | any unsorted small buckets [ss, j]. Hopefully | ||
2076 | previous pointer-scanning phases have already | ||
2077 | completed many of the small buckets [ss, j], so | ||
2078 | we don't have to sort them at all. | ||
2079 | --*/ | ||
2080 | for (j = 0; j <= 255; j++) { | ||
2081 | sb = (ss << 8) + j; | ||
2082 | if ( ! (ftab[sb] & SETMASK) ) { | ||
2083 | Int32 lo = ftab[sb] & CLEARMASK; | ||
2084 | Int32 hi = (ftab[sb+1] & CLEARMASK) - 1; | ||
2085 | if (hi > lo) { | ||
2086 | if (verbosity >= 4) | ||
2087 | fprintf ( stderr, | ||
2088 | " qsort [0x%x, 0x%x] done %d this %d\n", | ||
2089 | ss, j, numQSorted, hi - lo + 1 ); | ||
2090 | qSort3 ( lo, hi, 2 ); | ||
2091 | numQSorted += ( hi - lo + 1 ); | ||
2092 | if (workDone > workLimit && firstAttempt) return; | ||
2093 | } | ||
2094 | ftab[sb] |= SETMASK; | ||
2095 | } | ||
2096 | } | ||
2097 | |||
2098 | /*-- | ||
2099 | The ss big bucket is now done. Record this fact, | ||
2100 | and update the quadrant descriptors. Remember to | ||
2101 | update quadrants in the overshoot area too, if | ||
2102 | necessary. The "if (i < 255)" test merely skips | ||
2103 | this updating for the last bucket processed, since | ||
2104 | updating for the last bucket is pointless. | ||
2105 | --*/ | ||
2106 | bigDone[ss] = True; | ||
2107 | |||
2108 | if (i < 255) { | ||
2109 | Int32 bbStart = ftab[ss << 8] & CLEARMASK; | ||
2110 | Int32 bbSize = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart; | ||
2111 | Int32 shifts = 0; | ||
2112 | |||
2113 | while ((bbSize >> shifts) > 65534) shifts++; | ||
2114 | |||
2115 | for (j = 0; j < bbSize; j++) { | ||
2116 | Int32 a2update = zptr[bbStart + j]; | ||
2117 | UInt16 qVal = (UInt16)(j >> shifts); | ||
2118 | quadrant[a2update] = qVal; | ||
2119 | if (a2update < NUM_OVERSHOOT_BYTES) | ||
2120 | quadrant[a2update + last + 1] = qVal; | ||
2121 | } | ||
2122 | |||
2123 | if (! ( ((bbSize-1) >> shifts) <= 65535 )) panic ( "sortIt" ); | ||
2124 | } | ||
2125 | |||
2126 | /*-- | ||
2127 | Now scan this big bucket so as to synthesise the | ||
2128 | sorted order for small buckets [t, ss] for all t != ss. | ||
2129 | --*/ | ||
2130 | for (j = 0; j <= 255; j++) | ||
2131 | copy[j] = ftab[(j << 8) + ss] & CLEARMASK; | ||
2132 | |||
2133 | for (j = ftab[ss << 8] & CLEARMASK; | ||
2134 | j < (ftab[(ss+1) << 8] & CLEARMASK); | ||
2135 | j++) { | ||
2136 | c1 = block[zptr[j]-1]; | ||
2137 | if ( ! bigDone[c1] ) { | ||
2138 | zptr[copy[c1]] = zptr[j] == 0 ? last : zptr[j] - 1; | ||
2139 | copy[c1] ++; | ||
2140 | } | ||
2141 | } | ||
2142 | |||
2143 | for (j = 0; j <= 255; j++) ftab[(j << 8) + ss] |= SETMASK; | ||
2144 | } | ||
2145 | if (verbosity >= 4) | ||
2146 | fprintf ( stderr, " %d pointers, %d sorted, %d scanned\n", | ||
2147 | last+1, numQSorted, (last+1) - numQSorted ); | ||
2148 | } | ||
2149 | } | ||
2150 | |||
2151 | |||
2152 | /*---------------------------------------------------*/ | ||
2153 | /*--- Stuff for randomising repetitive blocks ---*/ | ||
2154 | /*---------------------------------------------------*/ | ||
2155 | |||
2156 | /*---------------------------------------------*/ | ||
2157 | Int32 rNums[512] = { | ||
2158 | 619, 720, 127, 481, 931, 816, 813, 233, 566, 247, | ||
2159 | 985, 724, 205, 454, 863, 491, 741, 242, 949, 214, | ||
2160 | 733, 859, 335, 708, 621, 574, 73, 654, 730, 472, | ||
2161 | 419, 436, 278, 496, 867, 210, 399, 680, 480, 51, | ||
2162 | 878, 465, 811, 169, 869, 675, 611, 697, 867, 561, | ||
2163 | 862, 687, 507, 283, 482, 129, 807, 591, 733, 623, | ||
2164 | 150, 238, 59, 379, 684, 877, 625, 169, 643, 105, | ||
2165 | 170, 607, 520, 932, 727, 476, 693, 425, 174, 647, | ||
2166 | 73, 122, 335, 530, 442, 853, 695, 249, 445, 515, | ||
2167 | 909, 545, 703, 919, 874, 474, 882, 500, 594, 612, | ||
2168 | 641, 801, 220, 162, 819, 984, 589, 513, 495, 799, | ||
2169 | 161, 604, 958, 533, 221, 400, 386, 867, 600, 782, | ||
2170 | 382, 596, 414, 171, 516, 375, 682, 485, 911, 276, | ||
2171 | 98, 553, 163, 354, 666, 933, 424, 341, 533, 870, | ||
2172 | 227, 730, 475, 186, 263, 647, 537, 686, 600, 224, | ||
2173 | 469, 68, 770, 919, 190, 373, 294, 822, 808, 206, | ||
2174 | 184, 943, 795, 384, 383, 461, 404, 758, 839, 887, | ||
2175 | 715, 67, 618, 276, 204, 918, 873, 777, 604, 560, | ||
2176 | 951, 160, 578, 722, 79, 804, 96, 409, 713, 940, | ||
2177 | 652, 934, 970, 447, 318, 353, 859, 672, 112, 785, | ||
2178 | 645, 863, 803, 350, 139, 93, 354, 99, 820, 908, | ||
2179 | 609, 772, 154, 274, 580, 184, 79, 626, 630, 742, | ||
2180 | 653, 282, 762, 623, 680, 81, 927, 626, 789, 125, | ||
2181 | 411, 521, 938, 300, 821, 78, 343, 175, 128, 250, | ||
2182 | 170, 774, 972, 275, 999, 639, 495, 78, 352, 126, | ||
2183 | 857, 956, 358, 619, 580, 124, 737, 594, 701, 612, | ||
2184 | 669, 112, 134, 694, 363, 992, 809, 743, 168, 974, | ||
2185 | 944, 375, 748, 52, 600, 747, 642, 182, 862, 81, | ||
2186 | 344, 805, 988, 739, 511, 655, 814, 334, 249, 515, | ||
2187 | 897, 955, 664, 981, 649, 113, 974, 459, 893, 228, | ||
2188 | 433, 837, 553, 268, 926, 240, 102, 654, 459, 51, | ||
2189 | 686, 754, 806, 760, 493, 403, 415, 394, 687, 700, | ||
2190 | 946, 670, 656, 610, 738, 392, 760, 799, 887, 653, | ||
2191 | 978, 321, 576, 617, 626, 502, 894, 679, 243, 440, | ||
2192 | 680, 879, 194, 572, 640, 724, 926, 56, 204, 700, | ||
2193 | 707, 151, 457, 449, 797, 195, 791, 558, 945, 679, | ||
2194 | 297, 59, 87, 824, 713, 663, 412, 693, 342, 606, | ||
2195 | 134, 108, 571, 364, 631, 212, 174, 643, 304, 329, | ||
2196 | 343, 97, 430, 751, 497, 314, 983, 374, 822, 928, | ||
2197 | 140, 206, 73, 263, 980, 736, 876, 478, 430, 305, | ||
2198 | 170, 514, 364, 692, 829, 82, 855, 953, 676, 246, | ||
2199 | 369, 970, 294, 750, 807, 827, 150, 790, 288, 923, | ||
2200 | 804, 378, 215, 828, 592, 281, 565, 555, 710, 82, | ||
2201 | 896, 831, 547, 261, 524, 462, 293, 465, 502, 56, | ||
2202 | 661, 821, 976, 991, 658, 869, 905, 758, 745, 193, | ||
2203 | 768, 550, 608, 933, 378, 286, 215, 979, 792, 961, | ||
2204 | 61, 688, 793, 644, 986, 403, 106, 366, 905, 644, | ||
2205 | 372, 567, 466, 434, 645, 210, 389, 550, 919, 135, | ||
2206 | 780, 773, 635, 389, 707, 100, 626, 958, 165, 504, | ||
2207 | 920, 176, 193, 713, 857, 265, 203, 50, 668, 108, | ||
2208 | 645, 990, 626, 197, 510, 357, 358, 850, 858, 364, | ||
2209 | 936, 638 | ||
2210 | }; | ||
2211 | |||
2212 | |||
2213 | #define RAND_DECLS \ | ||
2214 | Int32 rNToGo = 0; \ | ||
2215 | Int32 rTPos = 0; \ | ||
2216 | |||
2217 | #define RAND_MASK ((rNToGo == 1) ? 1 : 0) | ||
2218 | |||
2219 | #define RAND_UPD_MASK \ | ||
2220 | if (rNToGo == 0) { \ | ||
2221 | rNToGo = rNums[rTPos]; \ | ||
2222 | rTPos++; if (rTPos == 512) rTPos = 0; \ | ||
2223 | } \ | ||
2224 | rNToGo--; | ||
2225 | |||
2226 | |||
2227 | |||
2228 | /*---------------------------------------------------*/ | ||
2229 | /*--- The Reversible Transformation (tm) ---*/ | ||
2230 | /*---------------------------------------------------*/ | ||
2231 | |||
2232 | /*---------------------------------------------*/ | ||
2233 | void randomiseBlock ( void ) | ||
2234 | { | ||
2235 | Int32 i; | ||
2236 | RAND_DECLS; | ||
2237 | for (i = 0; i < 256; i++) inUse[i] = False; | ||
2238 | |||
2239 | for (i = 0; i <= last; i++) { | ||
2240 | RAND_UPD_MASK; | ||
2241 | block[i] ^= RAND_MASK; | ||
2242 | inUse[block[i]] = True; | ||
2243 | } | ||
2244 | } | ||
2245 | |||
2246 | |||
2247 | /*---------------------------------------------*/ | ||
2248 | void doReversibleTransformation ( void ) | ||
2249 | { | ||
2250 | Int32 i; | ||
2251 | |||
2252 | if (verbosity >= 2) fprintf ( stderr, "\n" ); | ||
2253 | |||
2254 | workLimit = workFactor * last; | ||
2255 | workDone = 0; | ||
2256 | blockRandomised = False; | ||
2257 | firstAttempt = True; | ||
2258 | |||
2259 | sortIt (); | ||
2260 | |||
2261 | if (verbosity >= 3) | ||
2262 | fprintf ( stderr, " %d work, %d block, ratio %5.2f\n", | ||
2263 | workDone, last, (float)workDone / (float)(last) ); | ||
2264 | |||
2265 | if (workDone > workLimit && firstAttempt) { | ||
2266 | if (verbosity >= 2) | ||
2267 | fprintf ( stderr, " sorting aborted; randomising block\n" ); | ||
2268 | randomiseBlock (); | ||
2269 | workLimit = workDone = 0; | ||
2270 | blockRandomised = True; | ||
2271 | firstAttempt = False; | ||
2272 | sortIt(); | ||
2273 | if (verbosity >= 3) | ||
2274 | fprintf ( stderr, " %d work, %d block, ratio %f\n", | ||
2275 | workDone, last, (float)workDone / (float)(last) ); | ||
2276 | } | ||
2277 | |||
2278 | origPtr = -1; | ||
2279 | for (i = 0; i <= last; i++) | ||
2280 | if (zptr[i] == 0) | ||
2281 | { origPtr = i; break; }; | ||
2282 | |||
2283 | if (origPtr == -1) panic ( "doReversibleTransformation" ); | ||
2284 | } | ||
2285 | |||
2286 | |||
2287 | /*---------------------------------------------*/ | ||
2288 | |||
2289 | INLINE Int32 indexIntoF ( Int32 indx, Int32 *cftab ) | ||
2290 | { | ||
2291 | Int32 nb, na, mid; | ||
2292 | nb = 0; | ||
2293 | na = 256; | ||
2294 | do { | ||
2295 | mid = (nb + na) >> 1; | ||
2296 | if (indx >= cftab[mid]) nb = mid; else na = mid; | ||
2297 | } | ||
2298 | while (na - nb != 1); | ||
2299 | return nb; | ||
2300 | } | ||
2301 | |||
2302 | |||
2303 | #define GET_SMALL(cccc) \ | ||
2304 | \ | ||
2305 | cccc = indexIntoF ( tPos, cftab ); \ | ||
2306 | tPos = GET_LL(tPos); | ||
2307 | |||
2308 | |||
2309 | void undoReversibleTransformation_small ( FILE* dst ) | ||
2310 | { | ||
2311 | Int32 cftab[257], cftabAlso[257]; | ||
2312 | Int32 i, j, tmp, tPos; | ||
2313 | UChar ch; | ||
2314 | |||
2315 | /*-- | ||
2316 | We assume here that the global array unzftab will | ||
2317 | already be holding the frequency counts for | ||
2318 | ll8[0 .. last]. | ||
2319 | --*/ | ||
2320 | |||
2321 | /*-- Set up cftab to facilitate generation of indexIntoF --*/ | ||
2322 | cftab[0] = 0; | ||
2323 | for (i = 1; i <= 256; i++) cftab[i] = unzftab[i-1]; | ||
2324 | for (i = 1; i <= 256; i++) cftab[i] += cftab[i-1]; | ||
2325 | |||
2326 | /*-- Make a copy of it, used in generation of T --*/ | ||
2327 | for (i = 0; i <= 256; i++) cftabAlso[i] = cftab[i]; | ||
2328 | |||
2329 | /*-- compute the T vector --*/ | ||
2330 | for (i = 0; i <= last; i++) { | ||
2331 | ch = (UChar)ll16[i]; | ||
2332 | SET_LL(i, cftabAlso[ch]); | ||
2333 | cftabAlso[ch]++; | ||
2334 | } | ||
2335 | |||
2336 | /*-- | ||
2337 | Compute T^(-1) by pointer reversal on T. This is rather | ||
2338 | subtle, in that, if the original block was two or more | ||
2339 | (in general, N) concatenated copies of the same thing, | ||
2340 | the T vector will consist of N cycles, each of length | ||
2341 | blocksize / N, and decoding will involve traversing one | ||
2342 | of these cycles N times. Which particular cycle doesn't | ||
2343 | matter -- they are all equivalent. The tricky part is to | ||
2344 | make sure that the pointer reversal creates a correct | ||
2345 | reversed cycle for us to traverse. So, the code below | ||
2346 | simply reverses whatever cycle origPtr happens to fall into, | ||
2347 | without regard to the cycle length. That gives one reversed | ||
2348 | cycle, which for normal blocks, is the entire block-size long. | ||
2349 | For repeated blocks, it will be interspersed with the other | ||
2350 | N-1 non-reversed cycles. Providing that the F-subscripting | ||
2351 | phase which follows starts at origPtr, all then works ok. | ||
2352 | --*/ | ||
2353 | i = origPtr; | ||
2354 | j = GET_LL(i); | ||
2355 | do { | ||
2356 | tmp = GET_LL(j); | ||
2357 | SET_LL(j, i); | ||
2358 | i = j; | ||
2359 | j = tmp; | ||
2360 | } | ||
2361 | while (i != origPtr); | ||
2362 | |||
2363 | /*-- | ||
2364 | We recreate the original by subscripting F through T^(-1). | ||
2365 | The run-length-decoder below requires characters incrementally, | ||
2366 | so tPos is set to a starting value, and is updated by | ||
2367 | the GET_SMALL macro. | ||
2368 | --*/ | ||
2369 | tPos = origPtr; | ||
2370 | |||
2371 | /*-------------------------------------------------*/ | ||
2372 | /*-- | ||
2373 | This is pretty much a verbatim copy of the | ||
2374 | run-length decoder present in the distribution | ||
2375 | bzip-0.21; it has to be here to avoid creating | ||
2376 | block[] as an intermediary structure. As in 0.21, | ||
2377 | this code derives from some sent to me by | ||
2378 | Christian von Roques. | ||
2379 | |||
2380 | It allows dst==NULL, so as to support the test (-t) | ||
2381 | option without slowing down the fast decompression | ||
2382 | code. | ||
2383 | --*/ | ||
2384 | { | ||
2385 | IntNative retVal; | ||
2386 | Int32 i2, count, chPrev, ch2; | ||
2387 | UInt32 localCrc; | ||
2388 | |||
2389 | count = 0; | ||
2390 | i2 = 0; | ||
2391 | ch2 = 256; /*-- not a char and not EOF --*/ | ||
2392 | localCrc = getGlobalCRC(); | ||
2393 | |||
2394 | { | ||
2395 | RAND_DECLS; | ||
2396 | while ( i2 <= last ) { | ||
2397 | chPrev = ch2; | ||
2398 | GET_SMALL(ch2); | ||
2399 | if (blockRandomised) { | ||
2400 | RAND_UPD_MASK; | ||
2401 | ch2 ^= (UInt32)RAND_MASK; | ||
2402 | } | ||
2403 | i2++; | ||
2404 | |||
2405 | if (dst) | ||
2406 | retVal = putc ( ch2, dst ); | ||
2407 | |||
2408 | UPDATE_CRC ( localCrc, (UChar)ch2 ); | ||
2409 | |||
2410 | if (ch2 != chPrev) { | ||
2411 | count = 1; | ||
2412 | } else { | ||
2413 | count++; | ||
2414 | if (count >= 4) { | ||
2415 | Int32 j2; | ||
2416 | UChar z; | ||
2417 | GET_SMALL(z); | ||
2418 | if (blockRandomised) { | ||
2419 | RAND_UPD_MASK; | ||
2420 | z ^= RAND_MASK; | ||
2421 | } | ||
2422 | for (j2 = 0; j2 < (Int32)z; j2++) { | ||
2423 | if (dst) retVal = putc (ch2, dst); | ||
2424 | UPDATE_CRC ( localCrc, (UChar)ch2 ); | ||
2425 | } | ||
2426 | i2++; | ||
2427 | count = 0; | ||
2428 | } | ||
2429 | } | ||
2430 | } | ||
2431 | } | ||
2432 | |||
2433 | setGlobalCRC ( localCrc ); | ||
2434 | } | ||
2435 | /*-- end of the in-line run-length-decoder. --*/ | ||
2436 | } | ||
2437 | #undef GET_SMALL | ||
2438 | |||
2439 | |||
2440 | /*---------------------------------------------*/ | ||
2441 | |||
2442 | #define GET_FAST(cccc) \ | ||
2443 | \ | ||
2444 | cccc = ll8[tPos]; \ | ||
2445 | tPos = tt[tPos]; | ||
2446 | |||
2447 | |||
2448 | void undoReversibleTransformation_fast ( FILE* dst ) | ||
2449 | { | ||
2450 | Int32 cftab[257]; | ||
2451 | Int32 i, tPos; | ||
2452 | UChar ch; | ||
2453 | |||
2454 | /*-- | ||
2455 | We assume here that the global array unzftab will | ||
2456 | already be holding the frequency counts for | ||
2457 | ll8[0 .. last]. | ||
2458 | --*/ | ||
2459 | |||
2460 | /*-- Set up cftab to facilitate generation of T^(-1) --*/ | ||
2461 | cftab[0] = 0; | ||
2462 | for (i = 1; i <= 256; i++) cftab[i] = unzftab[i-1]; | ||
2463 | for (i = 1; i <= 256; i++) cftab[i] += cftab[i-1]; | ||
2464 | |||
2465 | /*-- compute the T^(-1) vector --*/ | ||
2466 | for (i = 0; i <= last; i++) { | ||
2467 | ch = (UChar)ll8[i]; | ||
2468 | tt[cftab[ch]] = i; | ||
2469 | cftab[ch]++; | ||
2470 | } | 450 | } |
451 | if (verbosity >= 2) fprintf ( stderr, "\n " ); | ||
452 | return True; | ||
2471 | 453 | ||
2472 | /*-- | 454 | errhandler: |
2473 | We recreate the original by subscripting L through T^(-1). | 455 | bzReadClose ( &bzerr_dummy, bzf ); |
2474 | The run-length-decoder below requires characters incrementally, | 456 | switch (bzerr) { |
2475 | so tPos is set to a starting value, and is updated by | 457 | case BZ_IO_ERROR: |
2476 | the GET_FAST macro. | 458 | errhandler_io: |
2477 | --*/ | 459 | ioError(); break; |
2478 | tPos = tt[origPtr]; | 460 | case BZ_DATA_ERROR: |
2479 | 461 | crcError(); | |
2480 | /*-------------------------------------------------*/ | 462 | case BZ_MEM_ERROR: |
2481 | /*-- | 463 | outOfMemory(); |
2482 | This is pretty much a verbatim copy of the | 464 | case BZ_UNEXPECTED_EOF: |
2483 | run-length decoder present in the distribution | 465 | compressedStreamEOF(); |
2484 | bzip-0.21; it has to be here to avoid creating | 466 | case BZ_DATA_ERROR_MAGIC: |
2485 | block[] as an intermediary structure. As in 0.21, | 467 | if (streamNo == 1) { |
2486 | this code derives from some sent to me by | 468 | return False; |
2487 | Christian von Roques. | 469 | } else { |
2488 | --*/ | 470 | fprintf ( stderr, |
2489 | { | 471 | "\n%s: %s: trailing garbage after EOF ignored\n", |
2490 | IntNative retVal; | 472 | progName, inName ); |
2491 | Int32 i2, count, chPrev, ch2; | 473 | return True; |
2492 | UInt32 localCrc; | ||
2493 | |||
2494 | count = 0; | ||
2495 | i2 = 0; | ||
2496 | ch2 = 256; /*-- not a char and not EOF --*/ | ||
2497 | localCrc = getGlobalCRC(); | ||
2498 | |||
2499 | if (blockRandomised) { | ||
2500 | RAND_DECLS; | ||
2501 | while ( i2 <= last ) { | ||
2502 | chPrev = ch2; | ||
2503 | GET_FAST(ch2); | ||
2504 | RAND_UPD_MASK; | ||
2505 | ch2 ^= (UInt32)RAND_MASK; | ||
2506 | i2++; | ||
2507 | |||
2508 | retVal = putc ( ch2, dst ); | ||
2509 | UPDATE_CRC ( localCrc, (UChar)ch2 ); | ||
2510 | |||
2511 | if (ch2 != chPrev) { | ||
2512 | count = 1; | ||
2513 | } else { | ||
2514 | count++; | ||
2515 | if (count >= 4) { | ||
2516 | Int32 j2; | ||
2517 | UChar z; | ||
2518 | GET_FAST(z); | ||
2519 | RAND_UPD_MASK; | ||
2520 | z ^= RAND_MASK; | ||
2521 | for (j2 = 0; j2 < (Int32)z; j2++) { | ||
2522 | retVal = putc (ch2, dst); | ||
2523 | UPDATE_CRC ( localCrc, (UChar)ch2 ); | ||
2524 | } | ||
2525 | i2++; | ||
2526 | count = 0; | ||
2527 | } | ||
2528 | } | ||
2529 | } | ||
2530 | |||
2531 | } else { | ||
2532 | |||
2533 | while ( i2 <= last ) { | ||
2534 | chPrev = ch2; | ||
2535 | GET_FAST(ch2); | ||
2536 | i2++; | ||
2537 | |||
2538 | retVal = putc ( ch2, dst ); | ||
2539 | UPDATE_CRC ( localCrc, (UChar)ch2 ); | ||
2540 | |||
2541 | if (ch2 != chPrev) { | ||
2542 | count = 1; | ||
2543 | } else { | ||
2544 | count++; | ||
2545 | if (count >= 4) { | ||
2546 | Int32 j2; | ||
2547 | UChar z; | ||
2548 | GET_FAST(z); | ||
2549 | for (j2 = 0; j2 < (Int32)z; j2++) { | ||
2550 | retVal = putc (ch2, dst); | ||
2551 | UPDATE_CRC ( localCrc, (UChar)ch2 ); | ||
2552 | } | ||
2553 | i2++; | ||
2554 | count = 0; | ||
2555 | } | ||
2556 | } | ||
2557 | } | 474 | } |
2558 | 475 | default: | |
2559 | } /*-- if (blockRandomised) --*/ | 476 | panic ( "decompress:unexpected error" ); |
2560 | |||
2561 | setGlobalCRC ( localCrc ); | ||
2562 | } | ||
2563 | /*-- end of the in-line run-length-decoder. --*/ | ||
2564 | } | ||
2565 | #undef GET_FAST | ||
2566 | |||
2567 | |||
2568 | /*---------------------------------------------------*/ | ||
2569 | /*--- The block loader and RLEr ---*/ | ||
2570 | /*---------------------------------------------------*/ | ||
2571 | |||
2572 | /*---------------------------------------------*/ | ||
2573 | /* Top 16: run length, 1 to 255. | ||
2574 | * Lower 16: the char, or MY_EOF for EOF. | ||
2575 | */ | ||
2576 | |||
2577 | #define MY_EOF 257 | ||
2578 | |||
2579 | INLINE Int32 getRLEpair ( FILE* src ) | ||
2580 | { | ||
2581 | Int32 runLength; | ||
2582 | IntNative ch, chLatest; | ||
2583 | |||
2584 | ch = getc ( src ); | ||
2585 | |||
2586 | /*--- Because I have no idea what kind of a value EOF is. ---*/ | ||
2587 | if (ch == EOF) { | ||
2588 | ERROR_IF_NOT_ZERO ( ferror(src)); | ||
2589 | return (1 << 16) | MY_EOF; | ||
2590 | } | ||
2591 | |||
2592 | runLength = 0; | ||
2593 | do { | ||
2594 | chLatest = getc ( src ); | ||
2595 | runLength++; | ||
2596 | bytesIn++; | ||
2597 | } | ||
2598 | while (ch == chLatest && runLength < 255); | ||
2599 | |||
2600 | if ( chLatest != EOF ) { | ||
2601 | if ( ungetc ( chLatest, src ) == EOF ) | ||
2602 | panic ( "getRLEpair: ungetc failed" ); | ||
2603 | } else { | ||
2604 | ERROR_IF_NOT_ZERO ( ferror(src) ); | ||
2605 | } | ||
2606 | |||
2607 | /*--- Conditional is just a speedup hack. ---*/ | ||
2608 | if (runLength == 1) { | ||
2609 | UPDATE_CRC ( globalCrc, (UChar)ch ); | ||
2610 | return (1 << 16) | ch; | ||
2611 | } else { | ||
2612 | Int32 i; | ||
2613 | for (i = 1; i <= runLength; i++) | ||
2614 | UPDATE_CRC ( globalCrc, (UChar)ch ); | ||
2615 | return (runLength << 16) | ch; | ||
2616 | } | 477 | } |
2617 | } | ||
2618 | 478 | ||
2619 | 479 | panic ( "decompress:end" ); | |
2620 | /*---------------------------------------------*/ | 480 | return True; /*notreached*/ |
2621 | void loadAndRLEsource ( FILE* src ) | ||
2622 | { | ||
2623 | Int32 ch, allowableBlockSize, i; | ||
2624 | |||
2625 | last = -1; | ||
2626 | ch = 0; | ||
2627 | |||
2628 | for (i = 0; i < 256; i++) inUse[i] = False; | ||
2629 | |||
2630 | /*--- 20 is just a paranoia constant ---*/ | ||
2631 | allowableBlockSize = 100000 * blockSize100k - 20; | ||
2632 | |||
2633 | while (last < allowableBlockSize && ch != MY_EOF) { | ||
2634 | Int32 rlePair, runLen; | ||
2635 | rlePair = getRLEpair ( src ); | ||
2636 | ch = rlePair & 0xFFFF; | ||
2637 | runLen = (UInt32)rlePair >> 16; | ||
2638 | |||
2639 | #if DEBUG | ||
2640 | assert (runLen >= 1 && runLen <= 255); | ||
2641 | #endif | ||
2642 | |||
2643 | if (ch != MY_EOF) { | ||
2644 | inUse[ch] = True; | ||
2645 | switch (runLen) { | ||
2646 | case 1: | ||
2647 | last++; block[last] = (UChar)ch; break; | ||
2648 | case 2: | ||
2649 | last++; block[last] = (UChar)ch; | ||
2650 | last++; block[last] = (UChar)ch; break; | ||
2651 | case 3: | ||
2652 | last++; block[last] = (UChar)ch; | ||
2653 | last++; block[last] = (UChar)ch; | ||
2654 | last++; block[last] = (UChar)ch; break; | ||
2655 | default: | ||
2656 | inUse[runLen-4] = True; | ||
2657 | last++; block[last] = (UChar)ch; | ||
2658 | last++; block[last] = (UChar)ch; | ||
2659 | last++; block[last] = (UChar)ch; | ||
2660 | last++; block[last] = (UChar)ch; | ||
2661 | last++; block[last] = (UChar)(runLen-4); break; | ||
2662 | } | ||
2663 | } | ||
2664 | } | ||
2665 | } | 481 | } |
2666 | 482 | ||
2667 | 483 | ||
2668 | /*---------------------------------------------------*/ | ||
2669 | /*--- Processing of complete files and streams ---*/ | ||
2670 | /*---------------------------------------------------*/ | ||
2671 | |||
2672 | /*---------------------------------------------*/ | 484 | /*---------------------------------------------*/ |
2673 | void compressStream ( FILE *stream, FILE *zStream ) | 485 | Bool testStream ( FILE *zStream ) |
2674 | { | 486 | { |
2675 | IntNative retVal; | 487 | BZFILE* bzf = NULL; |
2676 | UInt32 blockCRC, combinedCRC; | 488 | Int32 bzerr, bzerr_dummy, ret, nread, streamNo, i; |
2677 | Int32 blockNo; | 489 | UChar obuf[5000]; |
490 | UChar unused[BZ_MAX_UNUSED]; | ||
491 | Int32 nUnused; | ||
492 | UChar* unusedTmp; | ||
2678 | 493 | ||
2679 | blockNo = 0; | 494 | nUnused = 0; |
2680 | bytesIn = 0; | 495 | streamNo = 0; |
2681 | bytesOut = 0; | ||
2682 | nBlocksRandomised = 0; | ||
2683 | 496 | ||
2684 | SET_BINARY_MODE(stream); | ||
2685 | SET_BINARY_MODE(zStream); | 497 | SET_BINARY_MODE(zStream); |
2686 | 498 | if (ferror(zStream)) goto errhandler_io; | |
2687 | ERROR_IF_NOT_ZERO ( ferror(stream) ); | ||
2688 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | ||
2689 | |||
2690 | bsSetStream ( zStream, True ); | ||
2691 | |||
2692 | /*--- Write `magic' bytes B and Z, | ||
2693 | then h indicating file-format == huffmanised, | ||
2694 | followed by a digit indicating blockSize100k. | ||
2695 | ---*/ | ||
2696 | bsPutUChar ( 'B' ); | ||
2697 | bsPutUChar ( 'Z' ); | ||
2698 | bsPutUChar ( 'h' ); | ||
2699 | bsPutUChar ( '0' + blockSize100k ); | ||
2700 | |||
2701 | combinedCRC = 0; | ||
2702 | |||
2703 | if (verbosity >= 2) fprintf ( stderr, "\n" ); | ||
2704 | 499 | ||
2705 | while (True) { | 500 | while (True) { |
2706 | 501 | ||
2707 | blockNo++; | 502 | bzf = bzReadOpen ( |
2708 | initialiseCRC (); | 503 | &bzerr, zStream, verbosity, |
2709 | loadAndRLEsource ( stream ); | 504 | (int)smallMode, unused, nUnused |
2710 | ERROR_IF_NOT_ZERO ( ferror(stream) ); | 505 | ); |
2711 | if (last == -1) break; | 506 | if (bzf == NULL || bzerr != BZ_OK) goto errhandler; |
2712 | 507 | streamNo++; | |
2713 | blockCRC = getFinalCRC (); | ||
2714 | combinedCRC = (combinedCRC << 1) | (combinedCRC >> 31); | ||
2715 | combinedCRC ^= blockCRC; | ||
2716 | |||
2717 | if (verbosity >= 2) | ||
2718 | fprintf ( stderr, " block %d: crc = 0x%8x, combined CRC = 0x%8x, size = %d", | ||
2719 | blockNo, blockCRC, combinedCRC, last+1 ); | ||
2720 | |||
2721 | /*-- sort the block and establish posn of original string --*/ | ||
2722 | doReversibleTransformation (); | ||
2723 | |||
2724 | /*-- | ||
2725 | A 6-byte block header, the value chosen arbitrarily | ||
2726 | as 0x314159265359 :-). A 32 bit value does not really | ||
2727 | give a strong enough guarantee that the value will not | ||
2728 | appear by chance in the compressed datastream. Worst-case | ||
2729 | probability of this event, for a 900k block, is about | ||
2730 | 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits. | ||
2731 | For a compressed file of size 100Gb -- about 100000 blocks -- | ||
2732 | only a 48-bit marker will do. NB: normal compression/ | ||
2733 | decompression do *not* rely on these statistical properties. | ||
2734 | They are only important when trying to recover blocks from | ||
2735 | damaged files. | ||
2736 | --*/ | ||
2737 | bsPutUChar ( 0x31 ); bsPutUChar ( 0x41 ); | ||
2738 | bsPutUChar ( 0x59 ); bsPutUChar ( 0x26 ); | ||
2739 | bsPutUChar ( 0x53 ); bsPutUChar ( 0x59 ); | ||
2740 | |||
2741 | /*-- Now the block's CRC, so it is in a known place. --*/ | ||
2742 | bsPutUInt32 ( blockCRC ); | ||
2743 | |||
2744 | /*-- Now a single bit indicating randomisation. --*/ | ||
2745 | if (blockRandomised) { | ||
2746 | bsW(1,1); nBlocksRandomised++; | ||
2747 | } else | ||
2748 | bsW(1,0); | ||
2749 | |||
2750 | /*-- Finally, block's contents proper. --*/ | ||
2751 | moveToFrontCodeAndSend (); | ||
2752 | |||
2753 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | ||
2754 | } | ||
2755 | |||
2756 | if (verbosity >= 2 && nBlocksRandomised > 0) | ||
2757 | fprintf ( stderr, " %d block%s needed randomisation\n", | ||
2758 | nBlocksRandomised, | ||
2759 | nBlocksRandomised == 1 ? "" : "s" ); | ||
2760 | |||
2761 | /*-- | ||
2762 | Now another magic 48-bit number, 0x177245385090, to | ||
2763 | indicate the end of the last block. (sqrt(pi), if | ||
2764 | you want to know. I did want to use e, but it contains | ||
2765 | too much repetition -- 27 18 28 18 28 46 -- for me | ||
2766 | to feel statistically comfortable. Call me paranoid.) | ||
2767 | --*/ | ||
2768 | |||
2769 | bsPutUChar ( 0x17 ); bsPutUChar ( 0x72 ); | ||
2770 | bsPutUChar ( 0x45 ); bsPutUChar ( 0x38 ); | ||
2771 | bsPutUChar ( 0x50 ); bsPutUChar ( 0x90 ); | ||
2772 | |||
2773 | bsPutUInt32 ( combinedCRC ); | ||
2774 | if (verbosity >= 2) | ||
2775 | fprintf ( stderr, " final combined CRC = 0x%x\n ", combinedCRC ); | ||
2776 | 508 | ||
2777 | /*-- Close the files in an utterly paranoid way. --*/ | 509 | while (bzerr == BZ_OK) { |
2778 | bsFinishedWithStream (); | 510 | nread = bzRead ( &bzerr, bzf, obuf, 5000 ); |
2779 | 511 | if (bzerr == BZ_DATA_ERROR_MAGIC) goto errhandler; | |
2780 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | 512 | } |
2781 | retVal = fflush ( zStream ); | 513 | if (bzerr != BZ_STREAM_END) goto errhandler; |
2782 | ERROR_IF_EOF ( retVal ); | ||
2783 | retVal = fclose ( zStream ); | ||
2784 | ERROR_IF_EOF ( retVal ); | ||
2785 | |||
2786 | ERROR_IF_NOT_ZERO ( ferror(stream) ); | ||
2787 | retVal = fclose ( stream ); | ||
2788 | ERROR_IF_EOF ( retVal ); | ||
2789 | |||
2790 | if (bytesIn == 0) bytesIn = 1; | ||
2791 | if (bytesOut == 0) bytesOut = 1; | ||
2792 | 514 | ||
2793 | if (verbosity >= 1) | 515 | bzReadGetUnused ( &bzerr, bzf, (void**)(&unusedTmp), &nUnused ); |
2794 | fprintf ( stderr, "%6.3f:1, %6.3f bits/byte, " | 516 | if (bzerr != BZ_OK) panic ( "test:bzReadGetUnused" ); |
2795 | "%5.2f%% saved, %d in, %d out.\n", | ||
2796 | (float)bytesIn / (float)bytesOut, | ||
2797 | (8.0 * (float)bytesOut) / (float)bytesIn, | ||
2798 | 100.0 * (1.0 - (float)bytesOut / (float)bytesIn), | ||
2799 | bytesIn, | ||
2800 | bytesOut | ||
2801 | ); | ||
2802 | } | ||
2803 | 517 | ||
518 | for (i = 0; i < nUnused; i++) unused[i] = unusedTmp[i]; | ||
2804 | 519 | ||
2805 | /*---------------------------------------------*/ | 520 | bzReadClose ( &bzerr, bzf ); |
2806 | Bool uncompressStream ( FILE *zStream, FILE *stream ) | 521 | if (bzerr != BZ_OK) panic ( "test:bzReadGetUnused" ); |
2807 | { | 522 | if (nUnused == 0 && myfeof(zStream)) break; |
2808 | UChar magic1, magic2, magic3, magic4; | ||
2809 | UChar magic5, magic6; | ||
2810 | UInt32 storedBlockCRC, storedCombinedCRC; | ||
2811 | UInt32 computedBlockCRC, computedCombinedCRC; | ||
2812 | Int32 currBlockNo; | ||
2813 | IntNative retVal; | ||
2814 | 523 | ||
2815 | SET_BINARY_MODE(stream); | ||
2816 | SET_BINARY_MODE(zStream); | ||
2817 | |||
2818 | ERROR_IF_NOT_ZERO ( ferror(stream) ); | ||
2819 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | ||
2820 | |||
2821 | bsSetStream ( zStream, False ); | ||
2822 | |||
2823 | /*-- | ||
2824 | A bad magic number is `recoverable from'; | ||
2825 | return with False so the caller skips the file. | ||
2826 | --*/ | ||
2827 | magic1 = bsGetUChar (); | ||
2828 | magic2 = bsGetUChar (); | ||
2829 | magic3 = bsGetUChar (); | ||
2830 | magic4 = bsGetUChar (); | ||
2831 | if (magic1 != 'B' || | ||
2832 | magic2 != 'Z' || | ||
2833 | magic3 != 'h' || | ||
2834 | magic4 < '1' || | ||
2835 | magic4 > '9') { | ||
2836 | bsFinishedWithStream(); | ||
2837 | retVal = fclose ( stream ); | ||
2838 | ERROR_IF_EOF ( retVal ); | ||
2839 | return False; | ||
2840 | } | 524 | } |
2841 | 525 | ||
2842 | setDecompressStructureSizes ( magic4 - '0' ); | 526 | if (ferror(zStream)) goto errhandler_io; |
2843 | computedCombinedCRC = 0; | 527 | ret = fclose ( zStream ); |
2844 | 528 | if (ret == EOF) goto errhandler_io; | |
2845 | if (verbosity >= 2) fprintf ( stderr, "\n " ); | ||
2846 | currBlockNo = 0; | ||
2847 | |||
2848 | while (True) { | ||
2849 | magic1 = bsGetUChar (); | ||
2850 | magic2 = bsGetUChar (); | ||
2851 | magic3 = bsGetUChar (); | ||
2852 | magic4 = bsGetUChar (); | ||
2853 | magic5 = bsGetUChar (); | ||
2854 | magic6 = bsGetUChar (); | ||
2855 | if (magic1 == 0x17 && magic2 == 0x72 && | ||
2856 | magic3 == 0x45 && magic4 == 0x38 && | ||
2857 | magic5 == 0x50 && magic6 == 0x90) break; | ||
2858 | |||
2859 | if (magic1 != 0x31 || magic2 != 0x41 || | ||
2860 | magic3 != 0x59 || magic4 != 0x26 || | ||
2861 | magic5 != 0x53 || magic6 != 0x59) badBlockHeader(); | ||
2862 | |||
2863 | storedBlockCRC = bsGetUInt32 (); | ||
2864 | |||
2865 | if (bsR(1) == 1) | ||
2866 | blockRandomised = True; else | ||
2867 | blockRandomised = False; | ||
2868 | |||
2869 | currBlockNo++; | ||
2870 | if (verbosity >= 2) | ||
2871 | fprintf ( stderr, "[%d: huff+mtf ", currBlockNo ); | ||
2872 | getAndMoveToFrontDecode (); | ||
2873 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | ||
2874 | |||
2875 | initialiseCRC(); | ||
2876 | if (verbosity >= 2) fprintf ( stderr, "rt+rld" ); | ||
2877 | if (smallMode) | ||
2878 | undoReversibleTransformation_small ( stream ); | ||
2879 | else | ||
2880 | undoReversibleTransformation_fast ( stream ); | ||
2881 | |||
2882 | ERROR_IF_NOT_ZERO ( ferror(stream) ); | ||
2883 | |||
2884 | computedBlockCRC = getFinalCRC(); | ||
2885 | if (verbosity >= 3) | ||
2886 | fprintf ( stderr, " {0x%x, 0x%x}", storedBlockCRC, computedBlockCRC ); | ||
2887 | if (verbosity >= 2) fprintf ( stderr, "] " ); | ||
2888 | |||
2889 | /*-- A bad CRC is considered a fatal error. --*/ | ||
2890 | if (storedBlockCRC != computedBlockCRC) | ||
2891 | crcError ( storedBlockCRC, computedBlockCRC ); | ||
2892 | |||
2893 | computedCombinedCRC = (computedCombinedCRC << 1) | (computedCombinedCRC >> 31); | ||
2894 | computedCombinedCRC ^= computedBlockCRC; | ||
2895 | }; | ||
2896 | 529 | ||
2897 | if (verbosity >= 2) fprintf ( stderr, "\n " ); | 530 | if (verbosity >= 2) fprintf ( stderr, "\n " ); |
2898 | |||
2899 | storedCombinedCRC = bsGetUInt32 (); | ||
2900 | if (verbosity >= 2) | ||
2901 | fprintf ( stderr, | ||
2902 | "combined CRCs: stored = 0x%x, computed = 0x%x\n ", | ||
2903 | storedCombinedCRC, computedCombinedCRC ); | ||
2904 | if (storedCombinedCRC != computedCombinedCRC) | ||
2905 | crcError ( storedCombinedCRC, computedCombinedCRC ); | ||
2906 | |||
2907 | |||
2908 | bsFinishedWithStream (); | ||
2909 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | ||
2910 | retVal = fclose ( zStream ); | ||
2911 | ERROR_IF_EOF ( retVal ); | ||
2912 | |||
2913 | ERROR_IF_NOT_ZERO ( ferror(stream) ); | ||
2914 | retVal = fflush ( stream ); | ||
2915 | ERROR_IF_NOT_ZERO ( retVal ); | ||
2916 | if (stream != stdout) { | ||
2917 | retVal = fclose ( stream ); | ||
2918 | ERROR_IF_EOF ( retVal ); | ||
2919 | } | ||
2920 | return True; | 531 | return True; |
2921 | } | ||
2922 | |||
2923 | |||
2924 | /*---------------------------------------------*/ | ||
2925 | Bool testStream ( FILE *zStream ) | ||
2926 | { | ||
2927 | UChar magic1, magic2, magic3, magic4; | ||
2928 | UChar magic5, magic6; | ||
2929 | UInt32 storedBlockCRC, storedCombinedCRC; | ||
2930 | UInt32 computedBlockCRC, computedCombinedCRC; | ||
2931 | Int32 currBlockNo; | ||
2932 | IntNative retVal; | ||
2933 | |||
2934 | SET_BINARY_MODE(zStream); | ||
2935 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | ||
2936 | |||
2937 | bsSetStream ( zStream, False ); | ||
2938 | |||
2939 | magic1 = bsGetUChar (); | ||
2940 | magic2 = bsGetUChar (); | ||
2941 | magic3 = bsGetUChar (); | ||
2942 | magic4 = bsGetUChar (); | ||
2943 | if (magic1 != 'B' || | ||
2944 | magic2 != 'Z' || | ||
2945 | magic3 != 'h' || | ||
2946 | magic4 < '1' || | ||
2947 | magic4 > '9') { | ||
2948 | bsFinishedWithStream(); | ||
2949 | fclose ( zStream ); | ||
2950 | fprintf ( stderr, "\n%s: bad magic number (ie, not created by bzip2)\n", | ||
2951 | inName ); | ||
2952 | return False; | ||
2953 | } | ||
2954 | 532 | ||
2955 | smallMode = True; | 533 | errhandler: |
2956 | setDecompressStructureSizes ( magic4 - '0' ); | 534 | bzReadClose ( &bzerr_dummy, bzf ); |
2957 | computedCombinedCRC = 0; | 535 | switch (bzerr) { |
2958 | 536 | case BZ_IO_ERROR: | |
2959 | if (verbosity >= 2) fprintf ( stderr, "\n" ); | 537 | errhandler_io: |
2960 | currBlockNo = 0; | 538 | ioError(); break; |
2961 | 539 | case BZ_DATA_ERROR: | |
2962 | while (True) { | ||
2963 | magic1 = bsGetUChar (); | ||
2964 | magic2 = bsGetUChar (); | ||
2965 | magic3 = bsGetUChar (); | ||
2966 | magic4 = bsGetUChar (); | ||
2967 | magic5 = bsGetUChar (); | ||
2968 | magic6 = bsGetUChar (); | ||
2969 | if (magic1 == 0x17 && magic2 == 0x72 && | ||
2970 | magic3 == 0x45 && magic4 == 0x38 && | ||
2971 | magic5 == 0x50 && magic6 == 0x90) break; | ||
2972 | |||
2973 | currBlockNo++; | ||
2974 | if (magic1 != 0x31 || magic2 != 0x41 || | ||
2975 | magic3 != 0x59 || magic4 != 0x26 || | ||
2976 | magic5 != 0x53 || magic6 != 0x59) { | ||
2977 | bsFinishedWithStream(); | ||
2978 | fclose ( zStream ); | ||
2979 | fprintf ( stderr, | 540 | fprintf ( stderr, |
2980 | "\n%s, block %d: bad header (not == 0x314159265359)\n", | 541 | "\n%s: data integrity (CRC) error in data\n", |
2981 | inName, currBlockNo ); | 542 | inName ); |
2982 | return False; | 543 | return False; |
2983 | } | 544 | case BZ_MEM_ERROR: |
2984 | storedBlockCRC = bsGetUInt32 (); | 545 | outOfMemory(); |
2985 | 546 | case BZ_UNEXPECTED_EOF: | |
2986 | if (bsR(1) == 1) | 547 | fprintf ( stderr, |
2987 | blockRandomised = True; else | 548 | "\n%s: file ends unexpectedly\n", |
2988 | blockRandomised = False; | 549 | inName ); |
2989 | |||
2990 | if (verbosity >= 2) | ||
2991 | fprintf ( stderr, " block [%d: huff+mtf ", currBlockNo ); | ||
2992 | getAndMoveToFrontDecode (); | ||
2993 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | ||
2994 | |||
2995 | initialiseCRC(); | ||
2996 | if (verbosity >= 2) fprintf ( stderr, "rt+rld" ); | ||
2997 | undoReversibleTransformation_small ( NULL ); | ||
2998 | |||
2999 | computedBlockCRC = getFinalCRC(); | ||
3000 | if (verbosity >= 3) | ||
3001 | fprintf ( stderr, " {0x%x, 0x%x}", storedBlockCRC, computedBlockCRC ); | ||
3002 | if (verbosity >= 2) fprintf ( stderr, "] " ); | ||
3003 | |||
3004 | if (storedBlockCRC != computedBlockCRC) { | ||
3005 | bsFinishedWithStream(); | ||
3006 | fclose ( zStream ); | ||
3007 | fprintf ( stderr, "\n%s, block %d: computed CRC does not match stored one\n", | ||
3008 | inName, currBlockNo ); | ||
3009 | return False; | 550 | return False; |
3010 | } | 551 | case BZ_DATA_ERROR_MAGIC: |
3011 | 552 | if (streamNo == 1) { | |
3012 | if (verbosity >= 2) fprintf ( stderr, "ok\n" ); | 553 | fprintf ( stderr, |
3013 | computedCombinedCRC = (computedCombinedCRC << 1) | (computedCombinedCRC >> 31); | 554 | "\n%s: bad magic number (ie, not created by bzip2)\n", |
3014 | computedCombinedCRC ^= computedBlockCRC; | 555 | inName ); |
3015 | }; | 556 | return False; |
3016 | 557 | } else { | |
3017 | storedCombinedCRC = bsGetUInt32 (); | 558 | fprintf ( stderr, |
3018 | if (verbosity >= 2) | 559 | "\n%s: %s: trailing garbage after EOF ignored\n", |
3019 | fprintf ( stderr, | 560 | progName, inName ); |
3020 | " combined CRCs: stored = 0x%x, computed = 0x%x\n ", | 561 | return True; |
3021 | storedCombinedCRC, computedCombinedCRC ); | 562 | } |
3022 | if (storedCombinedCRC != computedCombinedCRC) { | 563 | default: |
3023 | bsFinishedWithStream(); | 564 | panic ( "test:unexpected error" ); |
3024 | fclose ( zStream ); | ||
3025 | fprintf ( stderr, "\n%s: computed CRC does not match stored one\n", | ||
3026 | inName ); | ||
3027 | return False; | ||
3028 | } | 565 | } |
3029 | 566 | ||
3030 | bsFinishedWithStream (); | 567 | panic ( "test:end" ); |
3031 | ERROR_IF_NOT_ZERO ( ferror(zStream) ); | 568 | return True; /*notreached*/ |
3032 | retVal = fclose ( zStream ); | ||
3033 | ERROR_IF_EOF ( retVal ); | ||
3034 | return True; | ||
3035 | } | 569 | } |
3036 | 570 | ||
3037 | 571 | ||
3038 | |||
3039 | /*---------------------------------------------------*/ | 572 | /*---------------------------------------------------*/ |
3040 | /*--- Error [non-] handling grunge ---*/ | 573 | /*--- Error [non-] handling grunge ---*/ |
3041 | /*---------------------------------------------------*/ | 574 | /*---------------------------------------------------*/ |
@@ -3059,8 +592,7 @@ void showFileNames ( void ) | |||
3059 | fprintf ( | 592 | fprintf ( |
3060 | stderr, | 593 | stderr, |
3061 | "\tInput file = %s, output file = %s\n", | 594 | "\tInput file = %s, output file = %s\n", |
3062 | inName==NULL ? "(null)" : inName, | 595 | inName, outName |
3063 | outName==NULL ? "(null)" : outName | ||
3064 | ); | 596 | ); |
3065 | } | 597 | } |
3066 | 598 | ||
@@ -3072,8 +604,7 @@ void cleanUpAndFail ( Int32 ec ) | |||
3072 | 604 | ||
3073 | if ( srcMode == SM_F2F && opMode != OM_TEST ) { | 605 | if ( srcMode == SM_F2F && opMode != OM_TEST ) { |
3074 | fprintf ( stderr, "%s: Deleting output file %s, if it exists.\n", | 606 | fprintf ( stderr, "%s: Deleting output file %s, if it exists.\n", |
3075 | progName, | 607 | progName, outName ); |
3076 | outName==NULL ? "(null)" : outName ); | ||
3077 | if (outputHandleJustInCase != NULL) | 608 | if (outputHandleJustInCase != NULL) |
3078 | fclose ( outputHandleJustInCase ); | 609 | fclose ( outputHandleJustInCase ); |
3079 | retVal = remove ( outName ); | 610 | retVal = remove ( outName ); |
@@ -3108,11 +639,10 @@ void panic ( Char* s ) | |||
3108 | 639 | ||
3109 | 640 | ||
3110 | /*---------------------------------------------*/ | 641 | /*---------------------------------------------*/ |
3111 | void badBGLengths ( void ) | 642 | void crcError () |
3112 | { | 643 | { |
3113 | fprintf ( stderr, | 644 | fprintf ( stderr, |
3114 | "\n%s: error when reading background model code lengths,\n" | 645 | "\n%s: Data integrity error when decompressing.\n", |
3115 | "\twhich probably means the compressed file is corrupted.\n", | ||
3116 | progName ); | 646 | progName ); |
3117 | showFileNames(); | 647 | showFileNames(); |
3118 | cadvise(); | 648 | cadvise(); |
@@ -3121,19 +651,6 @@ void badBGLengths ( void ) | |||
3121 | 651 | ||
3122 | 652 | ||
3123 | /*---------------------------------------------*/ | 653 | /*---------------------------------------------*/ |
3124 | void crcError ( UInt32 crcStored, UInt32 crcComputed ) | ||
3125 | { | ||
3126 | fprintf ( stderr, | ||
3127 | "\n%s: Data integrity error when decompressing.\n" | ||
3128 | "\tStored CRC = 0x%x, computed CRC = 0x%x\n", | ||
3129 | progName, crcStored, crcComputed ); | ||
3130 | showFileNames(); | ||
3131 | cadvise(); | ||
3132 | cleanUpAndFail( 2 ); | ||
3133 | } | ||
3134 | |||
3135 | |||
3136 | /*---------------------------------------------*/ | ||
3137 | void compressedStreamEOF ( void ) | 654 | void compressedStreamEOF ( void ) |
3138 | { | 655 | { |
3139 | fprintf ( stderr, | 656 | fprintf ( stderr, |
@@ -3160,46 +677,6 @@ void ioError ( ) | |||
3160 | 677 | ||
3161 | 678 | ||
3162 | /*---------------------------------------------*/ | 679 | /*---------------------------------------------*/ |
3163 | void blockOverrun () | ||
3164 | { | ||
3165 | fprintf ( stderr, | ||
3166 | "\n%s: block overrun during decompression,\n" | ||
3167 | "\twhich probably means the compressed file\n" | ||
3168 | "\tis corrupted.\n", | ||
3169 | progName ); | ||
3170 | showFileNames(); | ||
3171 | cadvise(); | ||
3172 | cleanUpAndFail( 2 ); | ||
3173 | } | ||
3174 | |||
3175 | |||
3176 | /*---------------------------------------------*/ | ||
3177 | void badBlockHeader () | ||
3178 | { | ||
3179 | fprintf ( stderr, | ||
3180 | "\n%s: bad block header in the compressed file,\n" | ||
3181 | "\twhich probably means it is corrupted.\n", | ||
3182 | progName ); | ||
3183 | showFileNames(); | ||
3184 | cadvise(); | ||
3185 | cleanUpAndFail( 2 ); | ||
3186 | } | ||
3187 | |||
3188 | |||
3189 | /*---------------------------------------------*/ | ||
3190 | void bitStreamEOF () | ||
3191 | { | ||
3192 | fprintf ( stderr, | ||
3193 | "\n%s: read past the end of compressed data,\n" | ||
3194 | "\twhich probably means it is corrupted.\n", | ||
3195 | progName ); | ||
3196 | showFileNames(); | ||
3197 | cadvise(); | ||
3198 | cleanUpAndFail( 2 ); | ||
3199 | } | ||
3200 | |||
3201 | |||
3202 | /*---------------------------------------------*/ | ||
3203 | void mySignalCatcher ( IntNative n ) | 680 | void mySignalCatcher ( IntNative n ) |
3204 | { | 681 | { |
3205 | fprintf ( stderr, | 682 | fprintf ( stderr, |
@@ -3233,27 +710,11 @@ void mySIGSEGVorSIGBUScatcher ( IntNative n ) | |||
3233 | 710 | ||
3234 | 711 | ||
3235 | /*---------------------------------------------*/ | 712 | /*---------------------------------------------*/ |
3236 | void uncompressOutOfMemory ( Int32 draw, Int32 blockSize ) | 713 | void outOfMemory ( void ) |
3237 | { | ||
3238 | fprintf ( stderr, | ||
3239 | "\n%s: Can't allocate enough memory for decompression.\n" | ||
3240 | "\tRequested %d bytes for a block size of %d.\n" | ||
3241 | "\tTry selecting space-economic decompress (with flag -s)\n" | ||
3242 | "\tand failing that, find a machine with more memory.\n", | ||
3243 | progName, draw, blockSize ); | ||
3244 | showFileNames(); | ||
3245 | cleanUpAndFail(1); | ||
3246 | } | ||
3247 | |||
3248 | |||
3249 | /*---------------------------------------------*/ | ||
3250 | void compressOutOfMemory ( Int32 draw, Int32 blockSize ) | ||
3251 | { | 714 | { |
3252 | fprintf ( stderr, | 715 | fprintf ( stderr, |
3253 | "\n%s: Can't allocate enough memory for compression.\n" | 716 | "\n%s: couldn't allocate enough memory\n", |
3254 | "\tRequested %d bytes for a block size of %d.\n" | 717 | progName ); |
3255 | "\tTry selecting a small block size (with flag -s).\n", | ||
3256 | progName, draw, blockSize ); | ||
3257 | showFileNames(); | 718 | showFileNames(); |
3258 | cleanUpAndFail(1); | 719 | cleanUpAndFail(1); |
3259 | } | 720 | } |
@@ -3274,6 +735,24 @@ void pad ( Char *s ) | |||
3274 | 735 | ||
3275 | 736 | ||
3276 | /*---------------------------------------------*/ | 737 | /*---------------------------------------------*/ |
738 | void copyFileName ( Char* to, Char* from ) | ||
739 | { | ||
740 | if ( strlen(from) > FILE_NAME_LEN-10 ) { | ||
741 | fprintf ( | ||
742 | stderr, | ||
743 | "bzip2: file name\n`%s'\nis suspiciously (> 1024 chars) long.\n" | ||
744 | "Try using a reasonable file name instead. Sorry! :)\n", | ||
745 | from | ||
746 | ); | ||
747 | exit(1); | ||
748 | } | ||
749 | |||
750 | strncpy(to,from,FILE_NAME_LEN-10); | ||
751 | to[FILE_NAME_LEN-10]='\0'; | ||
752 | } | ||
753 | |||
754 | |||
755 | /*---------------------------------------------*/ | ||
3277 | Bool fileExists ( Char* name ) | 756 | Bool fileExists ( Char* name ) |
3278 | { | 757 | { |
3279 | FILE *tmp = fopen ( name, "rb" ); | 758 | FILE *tmp = fopen ( name, "rb" ); |
@@ -3287,7 +766,7 @@ Bool fileExists ( Char* name ) | |||
3287 | /*-- | 766 | /*-- |
3288 | if in doubt, return True | 767 | if in doubt, return True |
3289 | --*/ | 768 | --*/ |
3290 | Bool notABogStandardFile ( Char* name ) | 769 | Bool notAStandardFile ( Char* name ) |
3291 | { | 770 | { |
3292 | IntNative i; | 771 | IntNative i; |
3293 | struct MY_STAT statBuf; | 772 | struct MY_STAT statBuf; |
@@ -3300,9 +779,9 @@ Bool notABogStandardFile ( Char* name ) | |||
3300 | 779 | ||
3301 | 780 | ||
3302 | /*---------------------------------------------*/ | 781 | /*---------------------------------------------*/ |
3303 | void copyDateAndPermissions ( Char *srcName, Char *dstName ) | 782 | void copyDatePermissionsAndOwner ( Char *srcName, Char *dstName ) |
3304 | { | 783 | { |
3305 | #if BZ_UNIX | 784 | #if BZ_UNIX |
3306 | IntNative retVal; | 785 | IntNative retVal; |
3307 | struct MY_STAT statBuf; | 786 | struct MY_STAT statBuf; |
3308 | struct utimbuf uTimBuf; | 787 | struct utimbuf uTimBuf; |
@@ -3314,13 +793,34 @@ void copyDateAndPermissions ( Char *srcName, Char *dstName ) | |||
3314 | 793 | ||
3315 | retVal = chmod ( dstName, statBuf.st_mode ); | 794 | retVal = chmod ( dstName, statBuf.st_mode ); |
3316 | ERROR_IF_NOT_ZERO ( retVal ); | 795 | ERROR_IF_NOT_ZERO ( retVal ); |
796 | /* Not sure if this is really portable or not. Causes | ||
797 | problems on my x86-Linux Redhat 5.0 box. Decided | ||
798 | to omit it from 0.9.0. JRS, 27 June 98. If you | ||
799 | understand Unix file semantics and portability issues | ||
800 | well enough to fix this properly, drop me a line | ||
801 | at jseward@acm.org. | ||
802 | retVal = chown ( dstName, statBuf.st_uid, statBuf.st_gid ); | ||
803 | ERROR_IF_NOT_ZERO ( retVal ); | ||
804 | */ | ||
3317 | retVal = utime ( dstName, &uTimBuf ); | 805 | retVal = utime ( dstName, &uTimBuf ); |
3318 | ERROR_IF_NOT_ZERO ( retVal ); | 806 | ERROR_IF_NOT_ZERO ( retVal ); |
3319 | #endif | 807 | #endif |
3320 | } | 808 | } |
3321 | 809 | ||
3322 | 810 | ||
3323 | /*---------------------------------------------*/ | 811 | /*---------------------------------------------*/ |
812 | void setInterimPermissions ( Char *dstName ) | ||
813 | { | ||
814 | #if BZ_UNIX | ||
815 | IntNative retVal; | ||
816 | retVal = chmod ( dstName, S_IRUSR | S_IWUSR ); | ||
817 | ERROR_IF_NOT_ZERO ( retVal ); | ||
818 | #endif | ||
819 | } | ||
820 | |||
821 | |||
822 | |||
823 | /*---------------------------------------------*/ | ||
3324 | Bool endsInBz2 ( Char* name ) | 824 | Bool endsInBz2 ( Char* name ) |
3325 | { | 825 | { |
3326 | Int32 n = strlen ( name ); | 826 | Int32 n = strlen ( name ); |
@@ -3353,13 +853,13 @@ void compress ( Char *name ) | |||
3353 | panic ( "compress: bad modes\n" ); | 853 | panic ( "compress: bad modes\n" ); |
3354 | 854 | ||
3355 | switch (srcMode) { | 855 | switch (srcMode) { |
3356 | case SM_I2O: strcpy ( inName, "(stdin)" ); | 856 | case SM_I2O: copyFileName ( inName, "(stdin)" ); |
3357 | strcpy ( outName, "(stdout)" ); break; | 857 | copyFileName ( outName, "(stdout)" ); break; |
3358 | case SM_F2F: strcpy ( inName, name ); | 858 | case SM_F2F: copyFileName ( inName, name ); |
3359 | strcpy ( outName, name ); | 859 | copyFileName ( outName, name ); |
3360 | strcat ( outName, ".bz2" ); break; | 860 | strcat ( outName, ".bz2" ); break; |
3361 | case SM_F2O: strcpy ( inName, name ); | 861 | case SM_F2O: copyFileName ( inName, name ); |
3362 | strcpy ( outName, "(stdout)" ); break; | 862 | copyFileName ( outName, "(stdout)" ); break; |
3363 | } | 863 | } |
3364 | 864 | ||
3365 | if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) { | 865 | if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) { |
@@ -3377,12 +877,12 @@ void compress ( Char *name ) | |||
3377 | progName, inName ); | 877 | progName, inName ); |
3378 | return; | 878 | return; |
3379 | } | 879 | } |
3380 | if ( srcMode != SM_I2O && notABogStandardFile ( inName )) { | 880 | if ( srcMode != SM_I2O && notAStandardFile ( inName )) { |
3381 | fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n", | 881 | fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n", |
3382 | progName, inName ); | 882 | progName, inName ); |
3383 | return; | 883 | return; |
3384 | } | 884 | } |
3385 | if ( srcMode == SM_F2F && fileExists ( outName ) ) { | 885 | if ( srcMode == SM_F2F && !forceOverwrite && fileExists ( outName ) ) { |
3386 | fprintf ( stderr, "%s: Output file %s already exists, skipping.\n", | 886 | fprintf ( stderr, "%s: Output file %s already exists, skipping.\n", |
3387 | progName, outName ); | 887 | progName, outName ); |
3388 | return; | 888 | return; |
@@ -3434,6 +934,7 @@ void compress ( Char *name ) | |||
3434 | progName, inName ); | 934 | progName, inName ); |
3435 | return; | 935 | return; |
3436 | }; | 936 | }; |
937 | setInterimPermissions ( outName ); | ||
3437 | break; | 938 | break; |
3438 | 939 | ||
3439 | default: | 940 | default: |
@@ -3454,7 +955,7 @@ void compress ( Char *name ) | |||
3454 | 955 | ||
3455 | /*--- If there was an I/O error, we won't get here. ---*/ | 956 | /*--- If there was an I/O error, we won't get here. ---*/ |
3456 | if ( srcMode == SM_F2F ) { | 957 | if ( srcMode == SM_F2F ) { |
3457 | copyDateAndPermissions ( inName, outName ); | 958 | copyDatePermissionsAndOwner ( inName, outName ); |
3458 | if ( !keepInputFiles ) { | 959 | if ( !keepInputFiles ) { |
3459 | IntNative retVal = remove ( inName ); | 960 | IntNative retVal = remove ( inName ); |
3460 | ERROR_IF_NOT_ZERO ( retVal ); | 961 | ERROR_IF_NOT_ZERO ( retVal ); |
@@ -3474,15 +975,15 @@ void uncompress ( Char *name ) | |||
3474 | panic ( "uncompress: bad modes\n" ); | 975 | panic ( "uncompress: bad modes\n" ); |
3475 | 976 | ||
3476 | switch (srcMode) { | 977 | switch (srcMode) { |
3477 | case SM_I2O: strcpy ( inName, "(stdin)" ); | 978 | case SM_I2O: copyFileName ( inName, "(stdin)" ); |
3478 | strcpy ( outName, "(stdout)" ); break; | 979 | copyFileName ( outName, "(stdout)" ); break; |
3479 | case SM_F2F: strcpy ( inName, name ); | 980 | case SM_F2F: copyFileName ( inName, name ); |
3480 | strcpy ( outName, name ); | 981 | copyFileName ( outName, name ); |
3481 | if (endsInBz2 ( outName )) | 982 | if (endsInBz2 ( outName )) |
3482 | outName [ strlen ( outName ) - 4 ] = '\0'; | 983 | outName [ strlen ( outName ) - 4 ] = '\0'; |
3483 | break; | 984 | break; |
3484 | case SM_F2O: strcpy ( inName, name ); | 985 | case SM_F2O: copyFileName ( inName, name ); |
3485 | strcpy ( outName, "(stdout)" ); break; | 986 | copyFileName ( outName, "(stdout)" ); break; |
3486 | } | 987 | } |
3487 | 988 | ||
3488 | if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) { | 989 | if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) { |
@@ -3501,12 +1002,12 @@ void uncompress ( Char *name ) | |||
3501 | progName, inName ); | 1002 | progName, inName ); |
3502 | return; | 1003 | return; |
3503 | } | 1004 | } |
3504 | if ( srcMode != SM_I2O && notABogStandardFile ( inName )) { | 1005 | if ( srcMode != SM_I2O && notAStandardFile ( inName )) { |
3505 | fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n", | 1006 | fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n", |
3506 | progName, inName ); | 1007 | progName, inName ); |
3507 | return; | 1008 | return; |
3508 | } | 1009 | } |
3509 | if ( srcMode == SM_F2F && fileExists ( outName ) ) { | 1010 | if ( srcMode == SM_F2F && !forceOverwrite && fileExists ( outName ) ) { |
3510 | fprintf ( stderr, "%s: Output file %s already exists, skipping.\n", | 1011 | fprintf ( stderr, "%s: Output file %s already exists, skipping.\n", |
3511 | progName, outName ); | 1012 | progName, outName ); |
3512 | return; | 1013 | return; |
@@ -3550,6 +1051,7 @@ void uncompress ( Char *name ) | |||
3550 | progName, inName ); | 1051 | progName, inName ); |
3551 | return; | 1052 | return; |
3552 | }; | 1053 | }; |
1054 | setInterimPermissions ( outName ); | ||
3553 | break; | 1055 | break; |
3554 | 1056 | ||
3555 | default: | 1057 | default: |
@@ -3571,7 +1073,7 @@ void uncompress ( Char *name ) | |||
3571 | /*--- If there was an I/O error, we won't get here. ---*/ | 1073 | /*--- If there was an I/O error, we won't get here. ---*/ |
3572 | if ( magicNumberOK ) { | 1074 | if ( magicNumberOK ) { |
3573 | if ( srcMode == SM_F2F ) { | 1075 | if ( srcMode == SM_F2F ) { |
3574 | copyDateAndPermissions ( inName, outName ); | 1076 | copyDatePermissionsAndOwner ( inName, outName ); |
3575 | if ( !keepInputFiles ) { | 1077 | if ( !keepInputFiles ) { |
3576 | IntNative retVal = remove ( inName ); | 1078 | IntNative retVal = remove ( inName ); |
3577 | ERROR_IF_NOT_ZERO ( retVal ); | 1079 | ERROR_IF_NOT_ZERO ( retVal ); |
@@ -3607,11 +1109,11 @@ void testf ( Char *name ) | |||
3607 | if (name == NULL && srcMode != SM_I2O) | 1109 | if (name == NULL && srcMode != SM_I2O) |
3608 | panic ( "testf: bad modes\n" ); | 1110 | panic ( "testf: bad modes\n" ); |
3609 | 1111 | ||
3610 | strcpy ( outName, "(none)" ); | 1112 | copyFileName ( outName, "(none)" ); |
3611 | switch (srcMode) { | 1113 | switch (srcMode) { |
3612 | case SM_I2O: strcpy ( inName, "(stdin)" ); break; | 1114 | case SM_I2O: copyFileName ( inName, "(stdin)" ); break; |
3613 | case SM_F2F: strcpy ( inName, name ); break; | 1115 | case SM_F2F: copyFileName ( inName, name ); break; |
3614 | case SM_F2O: strcpy ( inName, name ); break; | 1116 | case SM_F2O: copyFileName ( inName, name ); break; |
3615 | } | 1117 | } |
3616 | 1118 | ||
3617 | if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) { | 1119 | if ( srcMode != SM_I2O && containsDubiousChars ( inName ) ) { |
@@ -3630,7 +1132,7 @@ void testf ( Char *name ) | |||
3630 | progName, inName ); | 1132 | progName, inName ); |
3631 | return; | 1133 | return; |
3632 | } | 1134 | } |
3633 | if ( srcMode != SM_I2O && notABogStandardFile ( inName )) { | 1135 | if ( srcMode != SM_I2O && notAStandardFile ( inName )) { |
3634 | fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n", | 1136 | fprintf ( stderr, "%s: Input file %s is not a normal file, skipping.\n", |
3635 | progName, inName ); | 1137 | progName, inName ); |
3636 | return; | 1138 | return; |
@@ -3684,25 +1186,18 @@ void license ( void ) | |||
3684 | fprintf ( stderr, | 1186 | fprintf ( stderr, |
3685 | 1187 | ||
3686 | "bzip2, a block-sorting file compressor. " | 1188 | "bzip2, a block-sorting file compressor. " |
3687 | "Version 0.1pl2, 29-Aug-97.\n" | 1189 | "Version 0.9.0c, 18-Oct-98.\n" |
3688 | " \n" | 1190 | " \n" |
3689 | " Copyright (C) 1996, 1997 by Julian Seward.\n" | 1191 | " Copyright (C) 1996, 1997, 1998 by Julian Seward.\n" |
3690 | " \n" | 1192 | " \n" |
3691 | " This program is free software; you can redistribute it and/or modify\n" | 1193 | " This program is free software; you can redistribute it and/or modify\n" |
3692 | " it under the terms of the GNU General Public License as published by\n" | 1194 | " it under the terms set out in the LICENSE file, which is included\n" |
3693 | " the Free Software Foundation; either version 2 of the License, or\n" | 1195 | " in the bzip2-0.9.0c source distribution.\n" |
3694 | " (at your option) any later version.\n" | ||
3695 | " \n" | 1196 | " \n" |
3696 | " This program is distributed in the hope that it will be useful,\n" | 1197 | " This program is distributed in the hope that it will be useful,\n" |
3697 | " but WITHOUT ANY WARRANTY; without even the implied warranty of\n" | 1198 | " but WITHOUT ANY WARRANTY; without even the implied warranty of\n" |
3698 | " MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n" | 1199 | " MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n" |
3699 | " GNU General Public License for more details.\n" | 1200 | " LICENSE file for more details.\n" |
3700 | " \n" | ||
3701 | " You should have received a copy of the GNU General Public License\n" | ||
3702 | " along with this program; if not, write to the Free Software\n" | ||
3703 | " Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.\n" | ||
3704 | " \n" | ||
3705 | " The GNU General Public License is contained in the file LICENSE.\n" | ||
3706 | " \n" | 1201 | " \n" |
3707 | ); | 1202 | ); |
3708 | } | 1203 | } |
@@ -3714,16 +1209,17 @@ void usage ( Char *fullProgName ) | |||
3714 | fprintf ( | 1209 | fprintf ( |
3715 | stderr, | 1210 | stderr, |
3716 | "bzip2, a block-sorting file compressor. " | 1211 | "bzip2, a block-sorting file compressor. " |
3717 | "Version 0.1pl2, 29-Aug-97.\n" | 1212 | "Version 0.9.0c, 18-Oct-98.\n" |
3718 | "\n usage: %s [flags and input files in any order]\n" | 1213 | "\n usage: %s [flags and input files in any order]\n" |
3719 | "\n" | 1214 | "\n" |
3720 | " -h --help print this message\n" | 1215 | " -h --help print this message\n" |
3721 | " -d --decompress force decompression\n" | 1216 | " -d --decompress force decompression\n" |
3722 | " -f --compress force compression\n" | 1217 | " -z --compress force compression\n" |
1218 | " -k --keep keep (don't delete) input files\n" | ||
1219 | " -f --force overwrite existing output filess\n" | ||
3723 | " -t --test test compressed file integrity\n" | 1220 | " -t --test test compressed file integrity\n" |
3724 | " -c --stdout output to standard out\n" | 1221 | " -c --stdout output to standard out\n" |
3725 | " -v --verbose be verbose (a 2nd -v gives more)\n" | 1222 | " -v --verbose be verbose (a 2nd -v gives more)\n" |
3726 | " -k --keep keep (don't delete) input files\n" | ||
3727 | " -L --license display software version & license\n" | 1223 | " -L --license display software version & license\n" |
3728 | " -V --version display software version & license\n" | 1224 | " -V --version display software version & license\n" |
3729 | " -s --small use less memory (at most 2500k)\n" | 1225 | " -s --small use less memory (at most 2500k)\n" |
@@ -3731,15 +1227,16 @@ void usage ( Char *fullProgName ) | |||
3731 | " --repetitive-fast compress repetitive blocks faster\n" | 1227 | " --repetitive-fast compress repetitive blocks faster\n" |
3732 | " --repetitive-best compress repetitive blocks better\n" | 1228 | " --repetitive-best compress repetitive blocks better\n" |
3733 | "\n" | 1229 | "\n" |
3734 | " If invoked as `bzip2', the default action is to compress.\n" | 1230 | " If invoked as `bzip2', default action is to compress.\n" |
3735 | " as `bunzip2', the default action is to decompress.\n" | 1231 | " as `bunzip2', default action is to decompress.\n" |
1232 | " as `bz2cat', default action is to decompress to stdout.\n" | ||
3736 | "\n" | 1233 | "\n" |
3737 | " If no file names are given, bzip2 compresses or decompresses\n" | 1234 | " If no file names are given, bzip2 compresses or decompresses\n" |
3738 | " from standard input to standard output. You can combine\n" | 1235 | " from standard input to standard output. You can combine\n" |
3739 | " flags, so `-v -4' means the same as -v4 or -4v, &c.\n" | 1236 | " short flags, so `-v -4' means the same as -v4 or -4v, &c.\n" |
3740 | #if BZ_UNIX | 1237 | #if BZ_UNIX |
3741 | "\n" | 1238 | "\n" |
3742 | #endif | 1239 | #endif |
3743 | , | 1240 | , |
3744 | 1241 | ||
3745 | fullProgName | 1242 | fullProgName |
@@ -3776,14 +1273,7 @@ void *myMalloc ( Int32 n ) | |||
3776 | void* p; | 1273 | void* p; |
3777 | 1274 | ||
3778 | p = malloc ( (size_t)n ); | 1275 | p = malloc ( (size_t)n ); |
3779 | if (p == NULL) { | 1276 | if (p == NULL) outOfMemory (); |
3780 | fprintf ( | ||
3781 | stderr, | ||
3782 | "%s: `malloc' failed on request for %d bytes.\n", | ||
3783 | progName, n | ||
3784 | ); | ||
3785 | exit ( 1 ); | ||
3786 | } | ||
3787 | return p; | 1277 | return p; |
3788 | } | 1278 | } |
3789 | 1279 | ||
@@ -3817,7 +1307,6 @@ Cell *snocString ( Cell *root, Char *name ) | |||
3817 | } | 1307 | } |
3818 | 1308 | ||
3819 | 1309 | ||
3820 | |||
3821 | /*---------------------------------------------*/ | 1310 | /*---------------------------------------------*/ |
3822 | #define ISFLAG(s) (strcmp(aa->name, (s))==0) | 1311 | #define ISFLAG(s) (strcmp(aa->name, (s))==0) |
3823 | 1312 | ||
@@ -3829,11 +1318,6 @@ IntNative main ( IntNative argc, Char *argv[] ) | |||
3829 | Cell *argList; | 1318 | Cell *argList; |
3830 | Cell *aa; | 1319 | Cell *aa; |
3831 | 1320 | ||
3832 | |||
3833 | #if DEBUG | ||
3834 | fprintf ( stderr, "bzip2: *** compiled with debugging ON ***\n" ); | ||
3835 | #endif | ||
3836 | |||
3837 | /*-- Be really really really paranoid :-) --*/ | 1321 | /*-- Be really really really paranoid :-) --*/ |
3838 | if (sizeof(Int32) != 4 || sizeof(UInt32) != 4 || | 1322 | if (sizeof(Int32) != 4 || sizeof(UInt32) != 4 || |
3839 | sizeof(Int16) != 2 || sizeof(UInt16) != 2 || | 1323 | sizeof(Int16) != 2 || sizeof(UInt16) != 2 || |
@@ -3844,7 +1328,7 @@ IntNative main ( IntNative argc, Char *argv[] ) | |||
3844 | "\tof 4, 2 and 1 bytes to run properly, and they don't.\n" | 1328 | "\tof 4, 2 and 1 bytes to run properly, and they don't.\n" |
3845 | "\tProbably you can fix this by defining them correctly,\n" | 1329 | "\tProbably you can fix this by defining them correctly,\n" |
3846 | "\tand recompiling. Bye!\n" ); | 1330 | "\tand recompiling. Bye!\n" ); |
3847 | exit(1); | 1331 | exit(3); |
3848 | } | 1332 | } |
3849 | 1333 | ||
3850 | 1334 | ||
@@ -3852,35 +1336,28 @@ IntNative main ( IntNative argc, Char *argv[] ) | |||
3852 | signal (SIGINT, mySignalCatcher); | 1336 | signal (SIGINT, mySignalCatcher); |
3853 | signal (SIGTERM, mySignalCatcher); | 1337 | signal (SIGTERM, mySignalCatcher); |
3854 | signal (SIGSEGV, mySIGSEGVorSIGBUScatcher); | 1338 | signal (SIGSEGV, mySIGSEGVorSIGBUScatcher); |
3855 | #if BZ_UNIX | 1339 | #if BZ_UNIX |
3856 | signal (SIGHUP, mySignalCatcher); | 1340 | signal (SIGHUP, mySignalCatcher); |
3857 | signal (SIGBUS, mySIGSEGVorSIGBUScatcher); | 1341 | signal (SIGBUS, mySIGSEGVorSIGBUScatcher); |
3858 | #endif | 1342 | #endif |
3859 | 1343 | ||
3860 | 1344 | ||
3861 | /*-- Initialise --*/ | 1345 | /*-- Initialise --*/ |
3862 | outputHandleJustInCase = NULL; | 1346 | outputHandleJustInCase = NULL; |
3863 | ftab = NULL; | ||
3864 | ll4 = NULL; | ||
3865 | ll16 = NULL; | ||
3866 | ll8 = NULL; | ||
3867 | tt = NULL; | ||
3868 | block = NULL; | ||
3869 | zptr = NULL; | ||
3870 | smallMode = False; | 1347 | smallMode = False; |
3871 | keepInputFiles = False; | 1348 | keepInputFiles = False; |
1349 | forceOverwrite = False; | ||
3872 | verbosity = 0; | 1350 | verbosity = 0; |
3873 | blockSize100k = 9; | 1351 | blockSize100k = 9; |
3874 | testFailsExist = False; | 1352 | testFailsExist = False; |
3875 | bsStream = NULL; | ||
3876 | numFileNames = 0; | 1353 | numFileNames = 0; |
3877 | numFilesProcessed = 0; | 1354 | numFilesProcessed = 0; |
3878 | workFactor = 30; | 1355 | workFactor = 30; |
3879 | 1356 | ||
3880 | strcpy ( inName, "(none)" ); | 1357 | copyFileName ( inName, "(none)" ); |
3881 | strcpy ( outName, "(none)" ); | 1358 | copyFileName ( outName, "(none)" ); |
3882 | 1359 | ||
3883 | strcpy ( progNameReally, argv[0] ); | 1360 | copyFileName ( progNameReally, argv[0] ); |
3884 | progName = &progNameReally[0]; | 1361 | progName = &progNameReally[0]; |
3885 | for (tmp = &progNameReally[0]; *tmp != '\0'; tmp++) | 1362 | for (tmp = &progNameReally[0]; *tmp != '\0'; tmp++) |
3886 | if (*tmp == PATH_SEP) progName = tmp + 1; | 1363 | if (*tmp == PATH_SEP) progName = tmp + 1; |
@@ -3903,20 +1380,26 @@ IntNative main ( IntNative argc, Char *argv[] ) | |||
3903 | } | 1380 | } |
3904 | 1381 | ||
3905 | 1382 | ||
3906 | /*-- Determine what to do (compress/uncompress/test). --*/ | 1383 | /*-- Determine source modes; flag handling may change this too. --*/ |
1384 | if (numFileNames == 0) | ||
1385 | srcMode = SM_I2O; else srcMode = SM_F2F; | ||
1386 | |||
1387 | |||
1388 | /*-- Determine what to do (compress/uncompress/test/cat). --*/ | ||
3907 | /*-- Note that subsequent flag handling may change this. --*/ | 1389 | /*-- Note that subsequent flag handling may change this. --*/ |
3908 | opMode = OM_Z; | 1390 | opMode = OM_Z; |
3909 | 1391 | ||
3910 | if ( (strcmp ( "bunzip2", progName ) == 0) || | 1392 | if ( (strstr ( progName, "unzip" ) != 0) || |
3911 | (strcmp ( "BUNZIP2", progName ) == 0) || | 1393 | (strstr ( progName, "UNZIP" ) != 0) ) |
3912 | (strcmp ( "bunzip2.exe", progName ) == 0) || | ||
3913 | (strcmp ( "BUNZIP2.EXE", progName ) == 0) ) | ||
3914 | opMode = OM_UNZ; | 1394 | opMode = OM_UNZ; |
3915 | 1395 | ||
3916 | 1396 | if ( (strstr ( progName, "z2cat" ) != 0) || | |
3917 | /*-- Determine source modes; flag handling may change this too. --*/ | 1397 | (strstr ( progName, "Z2CAT" ) != 0) || |
3918 | if (numFileNames == 0) | 1398 | (strstr ( progName, "zcat" ) != 0) || |
3919 | srcMode = SM_I2O; else srcMode = SM_F2F; | 1399 | (strstr ( progName, "ZCAT" ) != 0) ) { |
1400 | opMode = OM_UNZ; | ||
1401 | srcMode = (numFileNames == 0) ? SM_I2O : SM_F2O; | ||
1402 | } | ||
3920 | 1403 | ||
3921 | 1404 | ||
3922 | /*-- Look at the flags. --*/ | 1405 | /*-- Look at the flags. --*/ |
@@ -3926,7 +1409,8 @@ IntNative main ( IntNative argc, Char *argv[] ) | |||
3926 | switch (aa->name[j]) { | 1409 | switch (aa->name[j]) { |
3927 | case 'c': srcMode = SM_F2O; break; | 1410 | case 'c': srcMode = SM_F2O; break; |
3928 | case 'd': opMode = OM_UNZ; break; | 1411 | case 'd': opMode = OM_UNZ; break; |
3929 | case 'f': opMode = OM_Z; break; | 1412 | case 'z': opMode = OM_Z; break; |
1413 | case 'f': forceOverwrite = True; break; | ||
3930 | case 't': opMode = OM_TEST; break; | 1414 | case 't': opMode = OM_TEST; break; |
3931 | case 'k': keepInputFiles = True; break; | 1415 | case 'k': keepInputFiles = True; break; |
3932 | case 's': smallMode = True; break; | 1416 | case 's': smallMode = True; break; |
@@ -3957,6 +1441,7 @@ IntNative main ( IntNative argc, Char *argv[] ) | |||
3957 | if (ISFLAG("--stdout")) srcMode = SM_F2O; else | 1441 | if (ISFLAG("--stdout")) srcMode = SM_F2O; else |
3958 | if (ISFLAG("--decompress")) opMode = OM_UNZ; else | 1442 | if (ISFLAG("--decompress")) opMode = OM_UNZ; else |
3959 | if (ISFLAG("--compress")) opMode = OM_Z; else | 1443 | if (ISFLAG("--compress")) opMode = OM_Z; else |
1444 | if (ISFLAG("--force")) forceOverwrite = True; else | ||
3960 | if (ISFLAG("--test")) opMode = OM_TEST; else | 1445 | if (ISFLAG("--test")) opMode = OM_TEST; else |
3961 | if (ISFLAG("--keep")) keepInputFiles = True; else | 1446 | if (ISFLAG("--keep")) keepInputFiles = True; else |
3962 | if (ISFLAG("--small")) smallMode = True; else | 1447 | if (ISFLAG("--small")) smallMode = True; else |
@@ -3974,14 +1459,9 @@ IntNative main ( IntNative argc, Char *argv[] ) | |||
3974 | } | 1459 | } |
3975 | } | 1460 | } |
3976 | 1461 | ||
1462 | if (verbosity > 4) verbosity = 4; | ||
3977 | if (opMode == OM_Z && smallMode) blockSize100k = 2; | 1463 | if (opMode == OM_Z && smallMode) blockSize100k = 2; |
3978 | 1464 | ||
3979 | if (opMode == OM_Z && srcMode == SM_F2O && numFileNames > 1) { | ||
3980 | fprintf ( stderr, "%s: I won't compress multiple files to stdout.\n", | ||
3981 | progName ); | ||
3982 | exit ( 1 ); | ||
3983 | } | ||
3984 | |||
3985 | if (srcMode == SM_F2O && numFileNames == 0) { | 1465 | if (srcMode == SM_F2O && numFileNames == 0) { |
3986 | fprintf ( stderr, "%s: -c expects at least one filename.\n", | 1466 | fprintf ( stderr, "%s: -c expects at least one filename.\n", |
3987 | progName ); | 1467 | progName ); |
@@ -3997,7 +1477,6 @@ IntNative main ( IntNative argc, Char *argv[] ) | |||
3997 | if (opMode != OM_Z) blockSize100k = 0; | 1477 | if (opMode != OM_Z) blockSize100k = 0; |
3998 | 1478 | ||
3999 | if (opMode == OM_Z) { | 1479 | if (opMode == OM_Z) { |
4000 | allocateCompressStructures(); | ||
4001 | if (srcMode == SM_I2O) | 1480 | if (srcMode == SM_I2O) |
4002 | compress ( NULL ); | 1481 | compress ( NULL ); |
4003 | else | 1482 | else |