source: MondoRescue/branches/3.3/mindi-busybox/archival/libarchive/decompress_unlzma.c@ 3803

Last change on this file since 3803 was 3621, checked in by Bruno Cornec, 10 years ago

New 3?3 banch for incorporation of latest busybox 1.25. Changing minor version to handle potential incompatibilities.
  • Property svn:eol-style set to native
File size: 11.9 KB
RevLine 
[2725]1/* vi: set sw=4 ts=4: */
2/*
3 * Small lzma deflate implementation.
4 * Copyright (C) 2006 Aurelien Jacobs <aurel@gnuage.org>
5 *
6 * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
7 * Copyright (C) 1999-2005 Igor Pavlov
8 *
9 * Licensed under GPLv2 or later, see file LICENSE in this source tree.
10 */
11#include "libbb.h"
[3232]12#include "bb_archive.h"
[2725]13
14#if ENABLE_FEATURE_LZMA_FAST
15# define speed_inline ALWAYS_INLINE
16# define size_inline
17#else
18# define speed_inline
19# define size_inline ALWAYS_INLINE
20#endif
21
22
23typedef struct {
24 int fd;
25 uint8_t *ptr;
26
27/* Was keeping rc on stack in unlzma and separately allocating buffer,
28 * but with "buffer 'attached to' allocated rc" code is smaller: */
29 /* uint8_t *buffer; */
30#define RC_BUFFER ((uint8_t*)(rc+1))
31
32 uint8_t *buffer_end;
33
34/* Had provisions for variable buffer, but we don't need it here */
35 /* int buffer_size; */
36#define RC_BUFFER_SIZE 0x10000
37
38 uint32_t code;
39 uint32_t range;
40 uint32_t bound;
41} rc_t;
42
43#define RC_TOP_BITS 24
44#define RC_MOVE_BITS 5
45#define RC_MODEL_TOTAL_BITS 11
46
47
[3621]48/* Called once in rc_do_normalize() */
49static void rc_read(rc_t *rc)
[2725]50{
51 int buffer_size = safe_read(rc->fd, RC_BUFFER, RC_BUFFER_SIZE);
52//TODO: return -1 instead
53//This will make unlzma delete broken unpacked file on unpack errors
54 if (buffer_size <= 0)
55 bb_error_msg_and_die("unexpected EOF");
[3621]56 rc->buffer_end = RC_BUFFER + buffer_size;
[2725]57 rc->ptr = RC_BUFFER;
58}
59
60/* Called twice, but one callsite is in speed_inline'd rc_is_bit_1() */
61static void rc_do_normalize(rc_t *rc)
62{
63 if (rc->ptr >= rc->buffer_end)
64 rc_read(rc);
65 rc->range <<= 8;
66 rc->code = (rc->code << 8) | *rc->ptr++;
67}
[3621]68static ALWAYS_INLINE void rc_normalize(rc_t *rc)
69{
70 if (rc->range < (1 << RC_TOP_BITS)) {
71 rc_do_normalize(rc);
72 }
73}
[2725]74
75/* Called once */
76static ALWAYS_INLINE rc_t* rc_init(int fd) /*, int buffer_size) */
77{
78 int i;
79 rc_t *rc;
80
81 rc = xzalloc(sizeof(*rc) + RC_BUFFER_SIZE);
82
83 rc->fd = fd;
84 /* rc->ptr = rc->buffer_end; */
85
86 for (i = 0; i < 5; i++) {
87 rc_do_normalize(rc);
88 }
[3621]89 rc->range = 0xffffffff;
[2725]90 return rc;
91}
92
93/* Called once */
94static ALWAYS_INLINE void rc_free(rc_t *rc)
95{
96 free(rc);
97}
98
99/* rc_is_bit_1 is called 9 times */
100static speed_inline int rc_is_bit_1(rc_t *rc, uint16_t *p)
101{
102 rc_normalize(rc);
103 rc->bound = *p * (rc->range >> RC_MODEL_TOTAL_BITS);
104 if (rc->code < rc->bound) {
105 rc->range = rc->bound;
106 *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
107 return 0;
108 }
109 rc->range -= rc->bound;
110 rc->code -= rc->bound;
111 *p -= *p >> RC_MOVE_BITS;
112 return 1;
113}
114
115/* Called 4 times in unlzma loop */
[3621]116static ALWAYS_INLINE int rc_get_bit(rc_t *rc, uint16_t *p, int *symbol)
[2725]117{
118 int ret = rc_is_bit_1(rc, p);
119 *symbol = *symbol * 2 + ret;
120 return ret;
121}
122
123/* Called once */
124static ALWAYS_INLINE int rc_direct_bit(rc_t *rc)
125{
126 rc_normalize(rc);
127 rc->range >>= 1;
128 if (rc->code >= rc->range) {
129 rc->code -= rc->range;
130 return 1;
131 }
132 return 0;
133}
134
135/* Called twice */
136static speed_inline void
137rc_bit_tree_decode(rc_t *rc, uint16_t *p, int num_levels, int *symbol)
138{
139 int i = num_levels;
140
141 *symbol = 1;
142 while (i--)
143 rc_get_bit(rc, p + *symbol, symbol);
144 *symbol -= 1 << num_levels;
145}
146
147
148typedef struct {
149 uint8_t pos;
150 uint32_t dict_size;
151 uint64_t dst_size;
152} PACKED lzma_header_t;
153
154
155/* #defines will force compiler to compute/optimize each one with each usage.
156 * Have heart and use enum instead. */
157enum {
158 LZMA_BASE_SIZE = 1846,
159 LZMA_LIT_SIZE = 768,
160
161 LZMA_NUM_POS_BITS_MAX = 4,
162
163 LZMA_LEN_NUM_LOW_BITS = 3,
164 LZMA_LEN_NUM_MID_BITS = 3,
165 LZMA_LEN_NUM_HIGH_BITS = 8,
166
167 LZMA_LEN_CHOICE = 0,
168 LZMA_LEN_CHOICE_2 = (LZMA_LEN_CHOICE + 1),
169 LZMA_LEN_LOW = (LZMA_LEN_CHOICE_2 + 1),
170 LZMA_LEN_MID = (LZMA_LEN_LOW \
171 + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS))),
172 LZMA_LEN_HIGH = (LZMA_LEN_MID \
173 + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BITS))),
174 LZMA_NUM_LEN_PROBS = (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS)),
175
176 LZMA_NUM_STATES = 12,
177 LZMA_NUM_LIT_STATES = 7,
178
179 LZMA_START_POS_MODEL_INDEX = 4,
180 LZMA_END_POS_MODEL_INDEX = 14,
181 LZMA_NUM_FULL_DISTANCES = (1 << (LZMA_END_POS_MODEL_INDEX >> 1)),
182
183 LZMA_NUM_POS_SLOT_BITS = 6,
184 LZMA_NUM_LEN_TO_POS_STATES = 4,
185
186 LZMA_NUM_ALIGN_BITS = 4,
187
188 LZMA_MATCH_MIN_LEN = 2,
189
190 LZMA_IS_MATCH = 0,
191 LZMA_IS_REP = (LZMA_IS_MATCH + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX)),
192 LZMA_IS_REP_G0 = (LZMA_IS_REP + LZMA_NUM_STATES),
193 LZMA_IS_REP_G1 = (LZMA_IS_REP_G0 + LZMA_NUM_STATES),
194 LZMA_IS_REP_G2 = (LZMA_IS_REP_G1 + LZMA_NUM_STATES),
195 LZMA_IS_REP_0_LONG = (LZMA_IS_REP_G2 + LZMA_NUM_STATES),
196 LZMA_POS_SLOT = (LZMA_IS_REP_0_LONG \
197 + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX)),
198 LZMA_SPEC_POS = (LZMA_POS_SLOT \
199 + (LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS)),
200 LZMA_ALIGN = (LZMA_SPEC_POS \
201 + LZMA_NUM_FULL_DISTANCES - LZMA_END_POS_MODEL_INDEX),
202 LZMA_LEN_CODER = (LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS)),
203 LZMA_REP_LEN_CODER = (LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS),
204 LZMA_LITERAL = (LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS),
205};
206
207
208IF_DESKTOP(long long) int FAST_FUNC
[3621]209unpack_lzma_stream(transformer_state_t *xstate)
[2725]210{
211 IF_DESKTOP(long long total_written = 0;)
212 lzma_header_t header;
213 int lc, pb, lp;
214 uint32_t pos_state_mask;
215 uint32_t literal_pos_mask;
216 uint16_t *p;
217 rc_t *rc;
218 int i;
219 uint8_t *buffer;
220 uint8_t previous_byte = 0;
221 size_t buffer_pos = 0, global_pos = 0;
222 int len = 0;
223 int state = 0;
224 uint32_t rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1;
225
[3621]226 if (full_read(xstate->src_fd, &header, sizeof(header)) != sizeof(header)
[2725]227 || header.pos >= (9 * 5 * 5)
228 ) {
229 bb_error_msg("bad lzma header");
230 return -1;
231 }
232
233 i = header.pos / 9;
234 lc = header.pos % 9;
235 pb = i / 5;
236 lp = i % 5;
237 pos_state_mask = (1 << pb) - 1;
238 literal_pos_mask = (1 << lp) - 1;
239
[3621]240 /* Example values from linux-3.3.4.tar.lzma:
241 * dict_size: 64M, dst_size: 2^64-1
242 */
[2725]243 header.dict_size = SWAP_LE32(header.dict_size);
244 header.dst_size = SWAP_LE64(header.dst_size);
245
246 if (header.dict_size == 0)
247 header.dict_size++;
248
249 buffer = xmalloc(MIN(header.dst_size, header.dict_size));
250
[3621]251 {
252 int num_probs;
[2725]253
[3621]254 num_probs = LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp));
255 p = xmalloc(num_probs * sizeof(*p));
256 num_probs += LZMA_LITERAL - LZMA_BASE_SIZE;
257 for (i = 0; i < num_probs; i++)
258 p[i] = (1 << RC_MODEL_TOTAL_BITS) >> 1;
259 }
[2725]260
[3621]261 rc = rc_init(xstate->src_fd); /*, RC_BUFFER_SIZE); */
262
[2725]263 while (global_pos + buffer_pos < header.dst_size) {
264 int pos_state = (buffer_pos + global_pos) & pos_state_mask;
265 uint16_t *prob = p + LZMA_IS_MATCH + (state << LZMA_NUM_POS_BITS_MAX) + pos_state;
266
267 if (!rc_is_bit_1(rc, prob)) {
268 static const char next_state[LZMA_NUM_STATES] =
269 { 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5 };
270 int mi = 1;
271
272 prob = (p + LZMA_LITERAL
273 + (LZMA_LIT_SIZE * ((((buffer_pos + global_pos) & literal_pos_mask) << lc)
274 + (previous_byte >> (8 - lc))
275 )
276 )
277 );
278
279 if (state >= LZMA_NUM_LIT_STATES) {
280 int match_byte;
281 uint32_t pos = buffer_pos - rep0;
282
283 while (pos >= header.dict_size)
284 pos += header.dict_size;
285 match_byte = buffer[pos];
286 do {
287 int bit;
288
289 match_byte <<= 1;
290 bit = match_byte & 0x100;
291 bit ^= (rc_get_bit(rc, prob + 0x100 + bit + mi, &mi) << 8); /* 0x100 or 0 */
292 if (bit)
293 break;
294 } while (mi < 0x100);
295 }
296 while (mi < 0x100) {
297 rc_get_bit(rc, prob + mi, &mi);
298 }
299
300 state = next_state[state];
301
302 previous_byte = (uint8_t) mi;
303#if ENABLE_FEATURE_LZMA_FAST
304 one_byte1:
305 buffer[buffer_pos++] = previous_byte;
306 if (buffer_pos == header.dict_size) {
307 buffer_pos = 0;
308 global_pos += header.dict_size;
[3621]309 if (transformer_write(xstate, buffer, header.dict_size) != (ssize_t)header.dict_size)
[2725]310 goto bad;
311 IF_DESKTOP(total_written += header.dict_size;)
312 }
313#else
314 len = 1;
315 goto one_byte2;
316#endif
317 } else {
[3621]318 int num_bits;
[2725]319 int offset;
320 uint16_t *prob2;
321#define prob_len prob2
322
323 prob2 = p + LZMA_IS_REP + state;
324 if (!rc_is_bit_1(rc, prob2)) {
325 rep3 = rep2;
326 rep2 = rep1;
327 rep1 = rep0;
328 state = state < LZMA_NUM_LIT_STATES ? 0 : 3;
329 prob2 = p + LZMA_LEN_CODER;
330 } else {
331 prob2 += LZMA_IS_REP_G0 - LZMA_IS_REP;
332 if (!rc_is_bit_1(rc, prob2)) {
333 prob2 = (p + LZMA_IS_REP_0_LONG
334 + (state << LZMA_NUM_POS_BITS_MAX)
335 + pos_state
336 );
337 if (!rc_is_bit_1(rc, prob2)) {
338#if ENABLE_FEATURE_LZMA_FAST
339 uint32_t pos = buffer_pos - rep0;
340 state = state < LZMA_NUM_LIT_STATES ? 9 : 11;
341 while (pos >= header.dict_size)
342 pos += header.dict_size;
343 previous_byte = buffer[pos];
344 goto one_byte1;
345#else
346 state = state < LZMA_NUM_LIT_STATES ? 9 : 11;
347 len = 1;
348 goto string;
349#endif
350 }
351 } else {
352 uint32_t distance;
353
354 prob2 += LZMA_IS_REP_G1 - LZMA_IS_REP_G0;
355 distance = rep1;
356 if (rc_is_bit_1(rc, prob2)) {
357 prob2 += LZMA_IS_REP_G2 - LZMA_IS_REP_G1;
358 distance = rep2;
359 if (rc_is_bit_1(rc, prob2)) {
360 distance = rep3;
361 rep3 = rep2;
362 }
363 rep2 = rep1;
364 }
365 rep1 = rep0;
366 rep0 = distance;
367 }
368 state = state < LZMA_NUM_LIT_STATES ? 8 : 11;
369 prob2 = p + LZMA_REP_LEN_CODER;
370 }
371
372 prob_len = prob2 + LZMA_LEN_CHOICE;
373 num_bits = LZMA_LEN_NUM_LOW_BITS;
374 if (!rc_is_bit_1(rc, prob_len)) {
375 prob_len += LZMA_LEN_LOW - LZMA_LEN_CHOICE
376 + (pos_state << LZMA_LEN_NUM_LOW_BITS);
377 offset = 0;
378 } else {
379 prob_len += LZMA_LEN_CHOICE_2 - LZMA_LEN_CHOICE;
380 if (!rc_is_bit_1(rc, prob_len)) {
381 prob_len += LZMA_LEN_MID - LZMA_LEN_CHOICE_2
382 + (pos_state << LZMA_LEN_NUM_MID_BITS);
383 offset = 1 << LZMA_LEN_NUM_LOW_BITS;
384 num_bits += LZMA_LEN_NUM_MID_BITS - LZMA_LEN_NUM_LOW_BITS;
385 } else {
386 prob_len += LZMA_LEN_HIGH - LZMA_LEN_CHOICE_2;
387 offset = ((1 << LZMA_LEN_NUM_LOW_BITS)
388 + (1 << LZMA_LEN_NUM_MID_BITS));
389 num_bits += LZMA_LEN_NUM_HIGH_BITS - LZMA_LEN_NUM_LOW_BITS;
390 }
391 }
392 rc_bit_tree_decode(rc, prob_len, num_bits, &len);
393 len += offset;
394
395 if (state < 4) {
396 int pos_slot;
397 uint16_t *prob3;
398
399 state += LZMA_NUM_LIT_STATES;
400 prob3 = p + LZMA_POS_SLOT +
401 ((len < LZMA_NUM_LEN_TO_POS_STATES ? len :
402 LZMA_NUM_LEN_TO_POS_STATES - 1)
403 << LZMA_NUM_POS_SLOT_BITS);
404 rc_bit_tree_decode(rc, prob3,
405 LZMA_NUM_POS_SLOT_BITS, &pos_slot);
406 rep0 = pos_slot;
407 if (pos_slot >= LZMA_START_POS_MODEL_INDEX) {
408 int i2, mi2, num_bits2 = (pos_slot >> 1) - 1;
409 rep0 = 2 | (pos_slot & 1);
410 if (pos_slot < LZMA_END_POS_MODEL_INDEX) {
411 rep0 <<= num_bits2;
412 prob3 = p + LZMA_SPEC_POS + rep0 - pos_slot - 1;
413 } else {
414 for (; num_bits2 != LZMA_NUM_ALIGN_BITS; num_bits2--)
415 rep0 = (rep0 << 1) | rc_direct_bit(rc);
416 rep0 <<= LZMA_NUM_ALIGN_BITS;
417 prob3 = p + LZMA_ALIGN;
418 }
419 i2 = 1;
420 mi2 = 1;
421 while (num_bits2--) {
422 if (rc_get_bit(rc, prob3 + mi2, &mi2))
423 rep0 |= i2;
424 i2 <<= 1;
425 }
426 }
427 if (++rep0 == 0)
428 break;
429 }
430
431 len += LZMA_MATCH_MIN_LEN;
432 IF_NOT_FEATURE_LZMA_FAST(string:)
433 do {
434 uint32_t pos = buffer_pos - rep0;
435 while (pos >= header.dict_size)
436 pos += header.dict_size;
437 previous_byte = buffer[pos];
438 IF_NOT_FEATURE_LZMA_FAST(one_byte2:)
439 buffer[buffer_pos++] = previous_byte;
440 if (buffer_pos == header.dict_size) {
441 buffer_pos = 0;
442 global_pos += header.dict_size;
[3621]443 if (transformer_write(xstate, buffer, header.dict_size) != (ssize_t)header.dict_size)
[2725]444 goto bad;
445 IF_DESKTOP(total_written += header.dict_size;)
446 }
447 len--;
448 } while (len != 0 && buffer_pos < header.dst_size);
[3621]449 /* FIXME: ...........^^^^^
450 * shouldn't it be "global_pos + buffer_pos < header.dst_size"?
451 */
[2725]452 }
453 }
454
455 {
456 IF_NOT_DESKTOP(int total_written = 0; /* success */)
457 IF_DESKTOP(total_written += buffer_pos;)
[3621]458 if (transformer_write(xstate, buffer, buffer_pos) != (ssize_t)buffer_pos) {
[2725]459 bad:
460 total_written = -1; /* failure */
461 }
462 rc_free(rc);
463 free(p);
464 free(buffer);
465 return total_written;
466 }
467}
Note: See TracBrowser for help on using the repository browser.