1 /*
2 * bzip2 is written by Julian Seward <jseward@bzip.org>.
3 * Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>.
4 * See README and LICENSE files in this directory for more information.
5 */
6
7 /*-------------------------------------------------------------*/
8 /*--- Library top-level functions. ---*/
9 /*--- bzlib.c ---*/
10 /*-------------------------------------------------------------*/
11
12 /* ------------------------------------------------------------------
13 This file is part of bzip2/libbzip2, a program and library for
14 lossless, block-sorting data compression.
15
16 bzip2/libbzip2 version 1.0.4 of 20 December 2006
17 Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
18
19 Please read the WARNING, DISCLAIMER and PATENTS sections in the
20 README file.
21
22 This program is released under the terms of the license contained
23 in the file LICENSE.
24 ------------------------------------------------------------------ */
25
26 /* CHANGES
27 * 0.9.0 -- original version.
28 * 0.9.0a/b -- no changes in this file.
29 * 0.9.0c -- made zero-length BZ_FLUSH work correctly in bzCompress().
30 * fixed bzWrite/bzRead to ignore zero-length requests.
31 * fixed bzread to correctly handle read requests after EOF.
32 * wrong parameter order in call to bzDecompressInit in
33 * bzBuffToBuffDecompress. Fixed.
34 */
35
36 /* #include "bzlib_private.h" */
37
38 /*---------------------------------------------------*/
39 /*--- Compression stuff ---*/
40 /*---------------------------------------------------*/
41
42 /*---------------------------------------------------*/
43 #if BZ_LIGHT_DEBUG
44 static
bz_assert_fail(int errcode)45 void bz_assert_fail(int errcode)
46 {
47 /* if (errcode == 1007) bb_error_msg_and_die("probably bad RAM"); */
48 bb_error_msg_and_die("internal error %d", errcode);
49 }
50 #endif
51
52 /*---------------------------------------------------*/
53 static
prepare_new_block(EState * s)54 void prepare_new_block(EState* s)
55 {
56 int i;
57 s->nblock = 0;
58 //indexes into s->zbits[], initialzation moved to init of s->zbits
59 //s->posZ = s->zbits; // was: s->numZ = 0;
60 //s->state_out_pos = s->zbits;
61 BZ_INITIALISE_CRC(s->blockCRC);
62 /* inlined memset would be nice to have here */
63 for (i = 0; i < 256; i++)
64 s->inUse[i] = 0;
65 s->blockNo++;
66 }
67
68
69 /*---------------------------------------------------*/
70 static
71 ALWAYS_INLINE
init_RL(EState * s)72 void init_RL(EState* s)
73 {
74 s->state_in_ch = 256;
75 s->state_in_len = 0;
76 }
77
78
79 static
isempty_RL(EState * s)80 int isempty_RL(EState* s)
81 {
82 return (s->state_in_ch >= 256 || s->state_in_len <= 0);
83 }
84
85
86 /*---------------------------------------------------*/
87 static
BZ2_bzCompressInit(bz_stream * strm,int blockSize100k)88 void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
89 {
90 unsigned n;
91 EState* s;
92
93 s = xzalloc(sizeof(EState));
94 s->strm = strm;
95
96 n = 100000 * blockSize100k;
97 s->arr1 = xmalloc(n * sizeof(uint32_t));
98 s->mtfv = (uint16_t*)s->arr1;
99 s->ptr = (uint32_t*)s->arr1;
100 s->arr2 = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t));
101 s->block = (uint8_t*)s->arr2;
102
103 crc32_filltable(s->crc32table, 1);
104
105 s->state = BZ_S_INPUT;
106 s->mode = BZ_M_RUNNING;
107 s->blockSize100k = blockSize100k;
108 s->nblockMAX = n - 19;
109
110 strm->state = s;
111 /*strm->total_in = 0;*/
112 strm->total_out = 0;
113 init_RL(s);
114 prepare_new_block(s);
115 }
116
117
118 /*---------------------------------------------------*/
119 static
add_pair_to_block(EState * s)120 void add_pair_to_block(EState* s)
121 {
122 int32_t i;
123 uint8_t ch = (uint8_t)(s->state_in_ch);
124 for (i = 0; i < s->state_in_len; i++) {
125 BZ_UPDATE_CRC(s, s->blockCRC, ch);
126 }
127 s->inUse[s->state_in_ch] = 1;
128 switch (s->state_in_len) {
129 case 3:
130 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
131 /* fall through */
132 case 2:
133 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
134 /* fall through */
135 case 1:
136 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
137 break;
138 default:
139 s->inUse[s->state_in_len - 4] = 1;
140 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
141 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
142 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
143 s->block[s->nblock] = (uint8_t)ch; s->nblock++;
144 s->block[s->nblock] = (uint8_t)(s->state_in_len - 4);
145 s->nblock++;
146 break;
147 }
148 }
149
150
151 /*---------------------------------------------------*/
152 static
flush_RL(EState * s)153 void flush_RL(EState* s)
154 {
155 if (s->state_in_ch < 256) add_pair_to_block(s);
156 init_RL(s);
157 }
158
159
160 /*---------------------------------------------------*/
161 #define ADD_CHAR_TO_BLOCK(zs, zchh0) \
162 { \
163 uint32_t zchh = (uint32_t)(zchh0); \
164 /*-- fast track the common case --*/ \
165 if (zchh != zs->state_in_ch && zs->state_in_len == 1) { \
166 uint8_t ch = (uint8_t)(zs->state_in_ch); \
167 BZ_UPDATE_CRC(zs, zs->blockCRC, ch); \
168 zs->inUse[zs->state_in_ch] = 1; \
169 zs->block[zs->nblock] = (uint8_t)ch; \
170 zs->nblock++; \
171 zs->state_in_ch = zchh; \
172 } \
173 else \
174 /*-- general, uncommon cases --*/ \
175 if (zchh != zs->state_in_ch || zs->state_in_len == 255) { \
176 if (zs->state_in_ch < 256) \
177 add_pair_to_block(zs); \
178 zs->state_in_ch = zchh; \
179 zs->state_in_len = 1; \
180 } else { \
181 zs->state_in_len++; \
182 } \
183 }
184
185
186 /*---------------------------------------------------*/
187 static
copy_input_until_stop(EState * s)188 void /*Bool*/ copy_input_until_stop(EState* s)
189 {
190 /*Bool progress_in = False;*/
191
192 #ifdef SAME_CODE_AS_BELOW
193 if (s->mode == BZ_M_RUNNING) {
194 /*-- fast track the common case --*/
195 while (1) {
196 /*-- no input? --*/
197 if (s->strm->avail_in == 0) break;
198 /*-- block full? --*/
199 if (s->nblock >= s->nblockMAX) break;
200 /*progress_in = True;*/
201 ADD_CHAR_TO_BLOCK(s, (uint32_t)(*(uint8_t*)(s->strm->next_in)));
202 s->strm->next_in++;
203 s->strm->avail_in--;
204 /*s->strm->total_in++;*/
205 }
206 } else
207 #endif
208 {
209 /*-- general, uncommon case --*/
210 while (1) {
211 /*-- no input? --*/
212 if (s->strm->avail_in == 0) break;
213 /*-- block full? --*/
214 if (s->nblock >= s->nblockMAX) break;
215 //# /*-- flush/finish end? --*/
216 //# if (s->avail_in_expect == 0) break;
217 /*progress_in = True;*/
218 ADD_CHAR_TO_BLOCK(s, *(uint8_t*)(s->strm->next_in));
219 s->strm->next_in++;
220 s->strm->avail_in--;
221 /*s->strm->total_in++;*/
222 //# s->avail_in_expect--;
223 }
224 }
225 /*return progress_in;*/
226 }
227
228
229 /*---------------------------------------------------*/
230 static
copy_output_until_stop(EState * s)231 void /*Bool*/ copy_output_until_stop(EState* s)
232 {
233 /*Bool progress_out = False;*/
234
235 while (1) {
236 /*-- no output space? --*/
237 if (s->strm->avail_out == 0) break;
238
239 /*-- block done? --*/
240 if (s->state_out_pos >= s->posZ) break;
241
242 /*progress_out = True;*/
243 *(s->strm->next_out) = *s->state_out_pos++;
244 s->strm->avail_out--;
245 s->strm->next_out++;
246 s->strm->total_out++;
247 }
248 /*return progress_out;*/
249 }
250
251
252 /*---------------------------------------------------*/
253 static
handle_compress(bz_stream * strm)254 void /*Bool*/ handle_compress(bz_stream *strm)
255 {
256 /*Bool progress_in = False;*/
257 /*Bool progress_out = False;*/
258 EState* s = strm->state;
259
260 while (1) {
261 if (s->state == BZ_S_OUTPUT) {
262 /*progress_out |=*/ copy_output_until_stop(s);
263 if (s->state_out_pos < s->posZ) break;
264 if (s->mode == BZ_M_FINISHING
265 //# && s->avail_in_expect == 0
266 && s->strm->avail_in == 0
267 && isempty_RL(s))
268 break;
269 prepare_new_block(s);
270 s->state = BZ_S_INPUT;
271 #ifdef FLUSH_IS_UNUSED
272 if (s->mode == BZ_M_FLUSHING
273 && s->avail_in_expect == 0
274 && isempty_RL(s))
275 break;
276 #endif
277 }
278
279 if (s->state == BZ_S_INPUT) {
280 /*progress_in |=*/ copy_input_until_stop(s);
281 //#if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
282 if (s->mode != BZ_M_RUNNING && s->strm->avail_in == 0) {
283 flush_RL(s);
284 BZ2_compressBlock(s, (s->mode == BZ_M_FINISHING));
285 s->state = BZ_S_OUTPUT;
286 } else
287 if (s->nblock >= s->nblockMAX) {
288 BZ2_compressBlock(s, 0);
289 s->state = BZ_S_OUTPUT;
290 } else
291 if (s->strm->avail_in == 0) {
292 break;
293 }
294 }
295 }
296
297 /*return progress_in || progress_out;*/
298 }
299
300
301 /*---------------------------------------------------*/
302 static
BZ2_bzCompress(bz_stream * strm,int action)303 int BZ2_bzCompress(bz_stream *strm, int action)
304 {
305 /*Bool progress;*/
306 EState* s;
307
308 s = strm->state;
309
310 switch (s->mode) {
311 case BZ_M_RUNNING:
312 if (action == BZ_RUN) {
313 /*progress =*/ handle_compress(strm);
314 /*return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;*/
315 return BZ_RUN_OK;
316 }
317 #ifdef FLUSH_IS_UNUSED
318 else
319 if (action == BZ_FLUSH) {
320 //#s->avail_in_expect = strm->avail_in;
321 s->mode = BZ_M_FLUSHING;
322 goto case_BZ_M_FLUSHING;
323 }
324 #endif
325 else
326 /*if (action == BZ_FINISH)*/ {
327 //#s->avail_in_expect = strm->avail_in;
328 s->mode = BZ_M_FINISHING;
329 goto case_BZ_M_FINISHING;
330 }
331
332 #ifdef FLUSH_IS_UNUSED
333 case_BZ_M_FLUSHING:
334 case BZ_M_FLUSHING:
335 /*if (s->avail_in_expect != s->strm->avail_in)
336 return BZ_SEQUENCE_ERROR;*/
337 /*progress =*/ handle_compress(strm);
338 if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->posZ)
339 return BZ_FLUSH_OK;
340 s->mode = BZ_M_RUNNING;
341 return BZ_RUN_OK;
342 #endif
343
344 case_BZ_M_FINISHING:
345 /*case BZ_M_FINISHING:*/
346 default:
347 /*if (s->avail_in_expect != s->strm->avail_in)
348 return BZ_SEQUENCE_ERROR;*/
349 /*progress =*/ handle_compress(strm);
350 /*if (!progress) return BZ_SEQUENCE_ERROR;*/
351 //#if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->posZ)
352 //# return BZ_FINISH_OK;
353 if (s->strm->avail_in > 0 || !isempty_RL(s) || s->state_out_pos < s->posZ)
354 return BZ_FINISH_OK;
355 /*s->mode = BZ_M_IDLE;*/
356 return BZ_STREAM_END;
357 }
358 /* return BZ_OK; --not reached--*/
359 }
360
361
362 /*---------------------------------------------------*/
363 static
BZ2_bzCompressEnd(bz_stream * strm)364 void BZ2_bzCompressEnd(bz_stream *strm)
365 {
366 EState* s;
367
368 s = strm->state;
369 free(s->arr1);
370 free(s->arr2);
371 //free(s->ftab); // made it array member of s
372 //free(s->crc32table); // ditto
373 free(s);
374 }
375
376
377 /*---------------------------------------------------*/
378 /*--- Misc convenience stuff ---*/
379 /*---------------------------------------------------*/
380
381 /*---------------------------------------------------*/
382 #ifdef EXAMPLE_CODE_FOR_MEM_TO_MEM_COMPRESSION
383 static
BZ2_bzBuffToBuffCompress(char * dest,unsigned int * destLen,char * source,unsigned int sourceLen,int blockSize100k)384 int BZ2_bzBuffToBuffCompress(char* dest,
385 unsigned int* destLen,
386 char* source,
387 unsigned int sourceLen,
388 int blockSize100k)
389 {
390 bz_stream strm;
391 int ret;
392
393 if (dest == NULL || destLen == NULL
394 || source == NULL
395 || blockSize100k < 1 || blockSize100k > 9
396 ) {
397 return BZ_PARAM_ERROR;
398 }
399
400 BZ2_bzCompressInit(&strm, blockSize100k);
401
402 strm.next_in = source;
403 strm.next_out = dest;
404 strm.avail_in = sourceLen;
405 strm.avail_out = *destLen;
406
407 ret = BZ2_bzCompress(&strm, BZ_FINISH);
408 if (ret == BZ_FINISH_OK) goto output_overflow;
409 if (ret != BZ_STREAM_END) goto errhandler;
410
411 /* normal termination */
412 *destLen -= strm.avail_out;
413 BZ2_bzCompressEnd(&strm);
414 return BZ_OK;
415
416 output_overflow:
417 BZ2_bzCompressEnd(&strm);
418 return BZ_OUTBUFF_FULL;
419
420 errhandler:
421 BZ2_bzCompressEnd(&strm);
422 return ret;
423 }
424 #endif
425
426 /*-------------------------------------------------------------*/
427 /*--- end bzlib.c ---*/
428 /*-------------------------------------------------------------*/
429