Annotation of /trunk/mkinitrd-magellan/busybox/archival/bz/bzlib.c
Parent Directory | Revision Log
Revision 816 -
(hide annotations)
(download)
Fri Apr 24 18:33:46 2009 UTC (15 years, 1 month ago) by niro
File MIME type: text/plain
File size: 10836 byte(s)
Fri Apr 24 18:33:46 2009 UTC (15 years, 1 month ago) by niro
File MIME type: text/plain
File size: 10836 byte(s)
-updated to busybox-1.13.4
1 | niro | 816 | /* |
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 | /*-------------------------------------------------------------*/ |