remove trailing whitespace
[people/mcb30/busybox.git] / archival / bz / bzlib.c
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
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
54 void prepare_new_block(EState* s)
55 {
56         int i;
57         s->nblock = 0;
58         s->numZ = 0;
59         s->state_out_pos = 0;
60         BZ_INITIALISE_CRC(s->blockCRC);
61         /* inlined memset would be nice to have here */
62         for (i = 0; i < 256; i++)
63                 s->inUse[i] = 0;
64         s->blockNo++;
65 }
66
67
68 /*---------------------------------------------------*/
69 static
70 ALWAYS_INLINE
71 void init_RL(EState* s)
72 {
73         s->state_in_ch = 256;
74         s->state_in_len = 0;
75 }
76
77
78 static
79 Bool isempty_RL(EState* s)
80 {
81         if (s->state_in_ch < 256 && s->state_in_len > 0)
82                 return False;
83         return True;
84 }
85
86
87 /*---------------------------------------------------*/
88 static
89 void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
90 {
91         int32_t n;
92         EState* s;
93
94         s = xzalloc(sizeof(EState));
95         s->strm = strm;
96
97         n        = 100000 * blockSize100k;
98         s->arr1  = xmalloc(n                    * sizeof(uint32_t));
99         s->mtfv  = (uint16_t*)s->arr1;
100         s->ptr   = (uint32_t*)s->arr1;
101         s->arr2  = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t));
102         s->block = (uint8_t*)s->arr2;
103         s->ftab  = xmalloc(65537                * sizeof(uint32_t));
104
105         s->crc32table = crc32_filltable(NULL, 1);
106
107         s->state             = BZ_S_INPUT;
108         s->mode              = BZ_M_RUNNING;
109         s->blockSize100k     = blockSize100k;
110         s->nblockMAX         = n - 19;
111
112         strm->state          = s;
113         /*strm->total_in     = 0;*/
114         strm->total_out      = 0;
115         init_RL(s);
116         prepare_new_block(s);
117 }
118
119
120 /*---------------------------------------------------*/
121 static
122 void add_pair_to_block(EState* s)
123 {
124         int32_t i;
125         uint8_t ch = (uint8_t)(s->state_in_ch);
126         for (i = 0; i < s->state_in_len; i++) {
127                 BZ_UPDATE_CRC(s, s->blockCRC, ch);
128         }
129         s->inUse[s->state_in_ch] = 1;
130         switch (s->state_in_len) {
131                 case 3:
132                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
133                         /* fall through */
134                 case 2:
135                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
136                         /* fall through */
137                 case 1:
138                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
139                         break;
140                 default:
141                         s->inUse[s->state_in_len - 4] = 1;
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)ch; s->nblock++;
145                         s->block[s->nblock] = (uint8_t)ch; s->nblock++;
146                         s->block[s->nblock] = (uint8_t)(s->state_in_len - 4);
147                         s->nblock++;
148                         break;
149         }
150 }
151
152
153 /*---------------------------------------------------*/
154 static
155 void flush_RL(EState* s)
156 {
157         if (s->state_in_ch < 256) add_pair_to_block(s);
158         init_RL(s);
159 }
160
161
162 /*---------------------------------------------------*/
163 #define ADD_CHAR_TO_BLOCK(zs, zchh0) \
164 { \
165         uint32_t zchh = (uint32_t)(zchh0); \
166         /*-- fast track the common case --*/ \
167         if (zchh != zs->state_in_ch && zs->state_in_len == 1) { \
168                 uint8_t ch = (uint8_t)(zs->state_in_ch); \
169                 BZ_UPDATE_CRC(zs, zs->blockCRC, ch); \
170                 zs->inUse[zs->state_in_ch] = 1; \
171                 zs->block[zs->nblock] = (uint8_t)ch; \
172                 zs->nblock++; \
173                 zs->state_in_ch = zchh; \
174         } \
175         else \
176         /*-- general, uncommon cases --*/ \
177         if (zchh != zs->state_in_ch || zs->state_in_len == 255) { \
178                 if (zs->state_in_ch < 256) \
179                         add_pair_to_block(zs); \
180                 zs->state_in_ch = zchh; \
181                 zs->state_in_len = 1; \
182         } else { \
183                 zs->state_in_len++; \
184         } \
185 }
186
187
188 /*---------------------------------------------------*/
189 static
190 void /*Bool*/ copy_input_until_stop(EState* s)
191 {
192         /*Bool progress_in = False;*/
193
194 #ifdef SAME_CODE_AS_BELOW
195         if (s->mode == BZ_M_RUNNING) {
196                 /*-- fast track the common case --*/
197                 while (1) {
198                         /*-- no input? --*/
199                         if (s->strm->avail_in == 0) break;
200                         /*-- block full? --*/
201                         if (s->nblock >= s->nblockMAX) break;
202                         /*progress_in = True;*/
203                         ADD_CHAR_TO_BLOCK(s, (uint32_t)(*(uint8_t*)(s->strm->next_in)));
204                         s->strm->next_in++;
205                         s->strm->avail_in--;
206                         /*s->strm->total_in++;*/
207                 }
208         } else
209 #endif
210         {
211                 /*-- general, uncommon case --*/
212                 while (1) {
213                         /*-- no input? --*/
214                         if (s->strm->avail_in == 0) break;
215                         /*-- block full? --*/
216                         if (s->nblock >= s->nblockMAX) break;
217                 //#     /*-- flush/finish end? --*/
218                 //#     if (s->avail_in_expect == 0) break;
219                         /*progress_in = True;*/
220                         ADD_CHAR_TO_BLOCK(s, *(uint8_t*)(s->strm->next_in));
221                         s->strm->next_in++;
222                         s->strm->avail_in--;
223                         /*s->strm->total_in++;*/
224                 //#     s->avail_in_expect--;
225                 }
226         }
227         /*return progress_in;*/
228 }
229
230
231 /*---------------------------------------------------*/
232 static
233 void /*Bool*/ copy_output_until_stop(EState* s)
234 {
235         /*Bool progress_out = False;*/
236
237         while (1) {
238                 /*-- no output space? --*/
239                 if (s->strm->avail_out == 0) break;
240
241                 /*-- block done? --*/
242                 if (s->state_out_pos >= s->numZ) break;
243
244                 /*progress_out = True;*/
245                 *(s->strm->next_out) = s->zbits[s->state_out_pos];
246                 s->state_out_pos++;
247                 s->strm->avail_out--;
248                 s->strm->next_out++;
249                 s->strm->total_out++;
250         }
251         /*return progress_out;*/
252 }
253
254
255 /*---------------------------------------------------*/
256 static
257 void /*Bool*/ handle_compress(bz_stream *strm)
258 {
259         /*Bool progress_in  = False;*/
260         /*Bool progress_out = False;*/
261         EState* s = strm->state;
262
263         while (1) {
264                 if (s->state == BZ_S_OUTPUT) {
265                         /*progress_out |=*/ copy_output_until_stop(s);
266                         if (s->state_out_pos < s->numZ) break;
267                         if (s->mode == BZ_M_FINISHING
268                         //# && s->avail_in_expect == 0
269                          && s->strm->avail_in == 0
270                          && isempty_RL(s))
271                                 break;
272                         prepare_new_block(s);
273                         s->state = BZ_S_INPUT;
274 #ifdef FLUSH_IS_UNUSED
275                         if (s->mode == BZ_M_FLUSHING
276                          && s->avail_in_expect == 0
277                          && isempty_RL(s))
278                                 break;
279 #endif
280                 }
281
282                 if (s->state == BZ_S_INPUT) {
283                         /*progress_in |=*/ copy_input_until_stop(s);
284                         //#if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
285                         if (s->mode != BZ_M_RUNNING && s->strm->avail_in == 0) {
286                                 flush_RL(s);
287                                 BZ2_compressBlock(s, (s->mode == BZ_M_FINISHING));
288                                 s->state = BZ_S_OUTPUT;
289                         } else
290                         if (s->nblock >= s->nblockMAX) {
291                                 BZ2_compressBlock(s, 0);
292                                 s->state = BZ_S_OUTPUT;
293                         } else
294                         if (s->strm->avail_in == 0) {
295                                 break;
296                         }
297                 }
298         }
299
300         /*return progress_in || progress_out;*/
301 }
302
303
304 /*---------------------------------------------------*/
305 static
306 int BZ2_bzCompress(bz_stream *strm, int action)
307 {
308         /*Bool progress;*/
309         EState* s;
310
311         s = strm->state;
312
313         switch (s->mode) {
314                 case BZ_M_RUNNING:
315                         if (action == BZ_RUN) {
316                                 /*progress =*/ handle_compress(strm);
317                                 /*return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;*/
318                                 return BZ_RUN_OK;
319                         }
320 #ifdef FLUSH_IS_UNUSED
321                         else
322                         if (action == BZ_FLUSH) {
323                                 //#s->avail_in_expect = strm->avail_in;
324                                 s->mode = BZ_M_FLUSHING;
325                                 goto case_BZ_M_FLUSHING;
326                         }
327 #endif
328                         else
329                         /*if (action == BZ_FINISH)*/ {
330                                 //#s->avail_in_expect = strm->avail_in;
331                                 s->mode = BZ_M_FINISHING;
332                                 goto case_BZ_M_FINISHING;
333                         }
334
335 #ifdef FLUSH_IS_UNUSED
336 case_BZ_M_FLUSHING:
337                 case BZ_M_FLUSHING:
338                         /*if (s->avail_in_expect != s->strm->avail_in)
339                                 return BZ_SEQUENCE_ERROR;*/
340                         /*progress =*/ handle_compress(strm);
341                         if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
342                                 return BZ_FLUSH_OK;
343                         s->mode = BZ_M_RUNNING;
344                         return BZ_RUN_OK;
345 #endif
346
347  case_BZ_M_FINISHING:
348                 /*case BZ_M_FINISHING:*/
349                 default:
350                         /*if (s->avail_in_expect != s->strm->avail_in)
351                                 return BZ_SEQUENCE_ERROR;*/
352                         /*progress =*/ handle_compress(strm);
353                         /*if (!progress) return BZ_SEQUENCE_ERROR;*/
354                         //#if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
355                         //#     return BZ_FINISH_OK;
356                         if (s->strm->avail_in > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
357                                 return BZ_FINISH_OK;
358                         /*s->mode = BZ_M_IDLE;*/
359                         return BZ_STREAM_END;
360         }
361         /* return BZ_OK; --not reached--*/
362 }
363
364
365 /*---------------------------------------------------*/
366 static
367 void BZ2_bzCompressEnd(bz_stream *strm)
368 {
369         EState* s;
370
371         s = strm->state;
372         free(s->arr1);
373         free(s->arr2);
374         free(s->ftab);
375         free(s->crc32table);
376         free(strm->state);
377 }
378
379
380 /*---------------------------------------------------*/
381 /*--- Misc convenience stuff                      ---*/
382 /*---------------------------------------------------*/
383
384 /*---------------------------------------------------*/
385 #ifdef EXAMPLE_CODE_FOR_MEM_TO_MEM_COMPRESSION
386 static
387 int BZ2_bzBuffToBuffCompress(char* dest,
388                 unsigned int* destLen,
389                 char*         source,
390                 unsigned int  sourceLen,
391                 int           blockSize100k)
392 {
393         bz_stream strm;
394         int ret;
395
396         if (dest == NULL || destLen == NULL ||
397                  source == NULL ||
398                  blockSize100k < 1 || blockSize100k > 9)
399                 return BZ_PARAM_ERROR;
400
401         BZ2_bzCompressInit(&strm, blockSize100k);
402
403         strm.next_in = source;
404         strm.next_out = dest;
405         strm.avail_in = sourceLen;
406         strm.avail_out = *destLen;
407
408         ret = BZ2_bzCompress(&strm, BZ_FINISH);
409         if (ret == BZ_FINISH_OK) goto output_overflow;
410         if (ret != BZ_STREAM_END) goto errhandler;
411
412         /* normal termination */
413         *destLen -= strm.avail_out;
414         BZ2_bzCompressEnd(&strm);
415         return BZ_OK;
416
417  output_overflow:
418         BZ2_bzCompressEnd(&strm);
419         return BZ_OUTBUFF_FULL;
420
421  errhandler:
422         BZ2_bzCompressEnd(&strm);
423         return ret;
424 }
425 #endif
426
427 /*-------------------------------------------------------------*/
428 /*--- end                                           bzlib.c ---*/
429 /*-------------------------------------------------------------*/