← Back to branch summary

~ubuntu-branches/ubuntu/trusty/busybox/trusty

« back to all changes in this revision

Viewing changes to archival/libarchive/bz/bzlib.c

  • Committer: Scott Moser
  • Date: 2011-05-27 16:06:28 UTC
  • mfrom: (68.1.6 oneiric)
  • Revision ID: smoser@ubuntu.com-20110527160628-t1lo3pfw92ef8vnf
https://launchpad.net/bugs/788888
* Resynchronise with Debian (LP: #788888).  Remaining changes:
  - [udeb] Enable chvt, getopt (and -l), killall, losetup, NFS
    mount, od, ping, stat, and remote syslog.
  - [deb] Enable mdev.
  - [deb, static] Enable fractional sleep and CGI support for httpd.
  - Enable 'mount -f' and mount helpers for all targets.
  - Add busybox-initramfs.
  - test-bin.patch: Move test and friends to /bin.
  - static-sh-alias.patch: Add static-sh alias name for ash, and install
    /bin/static-sh symlink to busybox in busybox-static.
  - Add cross-compiling support.
* grep-o-loop.patch: dropped as fix and testcase in upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
archival/libarchive/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
int isempty_RL(EState* s)
 
80
{
 
81
        return (s->state_in_ch >= 256 || s->state_in_len <= 0);
 
82
}
 
83
 
 
84
 
 
85
/*---------------------------------------------------*/
 
86
static
 
87
void BZ2_bzCompressInit(bz_stream *strm, int blockSize100k)
 
88
{
 
89
        int32_t n;
 
90
        EState* s;
 
91
 
 
92
        s = xzalloc(sizeof(EState));
 
93
        s->strm = strm;
 
94
 
 
95
        n        = 100000 * blockSize100k;
 
96
        s->arr1  = xmalloc(n                    * sizeof(uint32_t));
 
97
        s->mtfv  = (uint16_t*)s->arr1;
 
98
        s->ptr   = (uint32_t*)s->arr1;
 
99
        s->arr2  = xmalloc((n + BZ_N_OVERSHOOT) * sizeof(uint32_t));
 
100
        s->block = (uint8_t*)s->arr2;
 
101
        s->ftab  = xmalloc(65537                * sizeof(uint32_t));
 
102
 
 
103
        s->crc32table = crc32_filltable(NULL, 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
 
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
 
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
 
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
 
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->numZ) break;
 
241
 
 
242
                /*progress_out = True;*/
 
243
                *(s->strm->next_out) = s->zbits[s->state_out_pos];
 
244
                s->state_out_pos++;
 
245
                s->strm->avail_out--;
 
246
                s->strm->next_out++;
 
247
                s->strm->total_out++;
 
248
        }
 
249
        /*return progress_out;*/
 
250
}
 
251
 
 
252
 
 
253
/*---------------------------------------------------*/
 
254
static
 
255
void /*Bool*/ handle_compress(bz_stream *strm)
 
256
{
 
257
        /*Bool progress_in  = False;*/
 
258
        /*Bool progress_out = False;*/
 
259
        EState* s = strm->state;
 
260
 
 
261
        while (1) {
 
262
                if (s->state == BZ_S_OUTPUT) {
 
263
                        /*progress_out |=*/ copy_output_until_stop(s);
 
264
                        if (s->state_out_pos < s->numZ) break;
 
265
                        if (s->mode == BZ_M_FINISHING
 
266
                        //# && s->avail_in_expect == 0
 
267
                         && s->strm->avail_in == 0
 
268
                         && isempty_RL(s))
 
269
                                break;
 
270
                        prepare_new_block(s);
 
271
                        s->state = BZ_S_INPUT;
 
272
#ifdef FLUSH_IS_UNUSED
 
273
                        if (s->mode == BZ_M_FLUSHING
 
274
                         && s->avail_in_expect == 0
 
275
                         && isempty_RL(s))
 
276
                                break;
 
277
#endif
 
278
                }
 
279
 
 
280
                if (s->state == BZ_S_INPUT) {
 
281
                        /*progress_in |=*/ copy_input_until_stop(s);
 
282
                        //#if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) {
 
283
                        if (s->mode != BZ_M_RUNNING && s->strm->avail_in == 0) {
 
284
                                flush_RL(s);
 
285
                                BZ2_compressBlock(s, (s->mode == BZ_M_FINISHING));
 
286
                                s->state = BZ_S_OUTPUT;
 
287
                        } else
 
288
                        if (s->nblock >= s->nblockMAX) {
 
289
                                BZ2_compressBlock(s, 0);
 
290
                                s->state = BZ_S_OUTPUT;
 
291
                        } else
 
292
                        if (s->strm->avail_in == 0) {
 
293
                                break;
 
294
                        }
 
295
                }
 
296
        }
 
297
 
 
298
        /*return progress_in || progress_out;*/
 
299
}
 
300
 
 
301
 
 
302
/*---------------------------------------------------*/
 
303
static
 
304
int BZ2_bzCompress(bz_stream *strm, int action)
 
305
{
 
306
        /*Bool progress;*/
 
307
        EState* s;
 
308
 
 
309
        s = strm->state;
 
310
 
 
311
        switch (s->mode) {
 
312
                case BZ_M_RUNNING:
 
313
                        if (action == BZ_RUN) {
 
314
                                /*progress =*/ handle_compress(strm);
 
315
                                /*return progress ? BZ_RUN_OK : BZ_PARAM_ERROR;*/
 
316
                                return BZ_RUN_OK;
 
317
                        }
 
318
#ifdef FLUSH_IS_UNUSED
 
319
                        else
 
320
                        if (action == BZ_FLUSH) {
 
321
                                //#s->avail_in_expect = strm->avail_in;
 
322
                                s->mode = BZ_M_FLUSHING;
 
323
                                goto case_BZ_M_FLUSHING;
 
324
                        }
 
325
#endif
 
326
                        else
 
327
                        /*if (action == BZ_FINISH)*/ {
 
328
                                //#s->avail_in_expect = strm->avail_in;
 
329
                                s->mode = BZ_M_FINISHING;
 
330
                                goto case_BZ_M_FINISHING;
 
331
                        }
 
332
 
 
333
#ifdef FLUSH_IS_UNUSED
 
334
 case_BZ_M_FLUSHING:
 
335
                case BZ_M_FLUSHING:
 
336
                        /*if (s->avail_in_expect != s->strm->avail_in)
 
337
                                return BZ_SEQUENCE_ERROR;*/
 
338
                        /*progress =*/ handle_compress(strm);
 
339
                        if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
 
340
                                return BZ_FLUSH_OK;
 
341
                        s->mode = BZ_M_RUNNING;
 
342
                        return BZ_RUN_OK;
 
343
#endif
 
344
 
 
345
 case_BZ_M_FINISHING:
 
346
                /*case BZ_M_FINISHING:*/
 
347
                default:
 
348
                        /*if (s->avail_in_expect != s->strm->avail_in)
 
349
                                return BZ_SEQUENCE_ERROR;*/
 
350
                        /*progress =*/ handle_compress(strm);
 
351
                        /*if (!progress) return BZ_SEQUENCE_ERROR;*/
 
352
                        //#if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
 
353
                        //#     return BZ_FINISH_OK;
 
354
                        if (s->strm->avail_in > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ)
 
355
                                return BZ_FINISH_OK;
 
356
                        /*s->mode = BZ_M_IDLE;*/
 
357
                        return BZ_STREAM_END;
 
358
        }
 
359
        /* return BZ_OK; --not reached--*/
 
360
}
 
361
 
 
362
 
 
363
/*---------------------------------------------------*/
 
364
static
 
365
void BZ2_bzCompressEnd(bz_stream *strm)
 
366
{
 
367
        EState* s;
 
368
 
 
369
        s = strm->state;
 
370
        free(s->arr1);
 
371
        free(s->arr2);
 
372
        free(s->ftab);
 
373
        free(s->crc32table);
 
374
        free(s);
 
375
}
 
376
 
 
377
 
 
378
/*---------------------------------------------------*/
 
379
/*--- Misc convenience stuff                      ---*/
 
380
/*---------------------------------------------------*/
 
381
 
 
382
/*---------------------------------------------------*/
 
383
#ifdef EXAMPLE_CODE_FOR_MEM_TO_MEM_COMPRESSION
 
384
static
 
385
int BZ2_bzBuffToBuffCompress(char* dest,
 
386
                unsigned int* destLen,
 
387
                char*         source,
 
388
                unsigned int  sourceLen,
 
389
                int           blockSize100k)
 
390
{
 
391
        bz_stream strm;
 
392
        int ret;
 
393
 
 
394
        if (dest == NULL || destLen == NULL
 
395
         || source == NULL
 
396
         || blockSize100k < 1 || blockSize100k > 9
 
397
        ) {
 
398
                return BZ_PARAM_ERROR;
 
399
        }
 
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
/*-------------------------------------------------------------*/