Contents of /trunk/mkinitrd-magellan/busybox/archival/bz/bzlib.c
Parent Directory | Revision Log
Revision 816 -
(show annotations)
(download)
Fri Apr 24 18:33:46 2009 UTC (15 years, 5 months ago) by niro
File MIME type: text/plain
File size: 10836 byte(s)
Fri Apr 24 18:33:46 2009 UTC (15 years, 5 months ago) by niro
File MIME type: text/plain
File size: 10836 byte(s)
-updated to busybox-1.13.4
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 | #if ENABLE_FEATURE_CLEAN_UP |
365 | static |
366 | void BZ2_bzCompressEnd(bz_stream *strm) |
367 | { |
368 | EState* s; |
369 | |
370 | s = strm->state; |
371 | free(s->arr1); |
372 | free(s->arr2); |
373 | free(s->ftab); |
374 | free(s->crc32table); |
375 | free(strm->state); |
376 | } |
377 | #endif |
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 | /*-------------------------------------------------------------*/ |