blob: c8622f97b3b02fbfcd659508e63d73ce370307d6
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" |
12 | #include "bb_archive.h" |
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 | |
23 | typedef 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 | |
48 | /* Called once in rc_do_normalize() */ |
49 | static void rc_read(rc_t *rc) |
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"); |
56 | rc->buffer_end = RC_BUFFER + buffer_size; |
57 | rc->ptr = RC_BUFFER; |
58 | } |
59 | |
60 | /* Called twice, but one callsite is in speed_inline'd rc_is_bit_1() */ |
61 | static 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 | } |
68 | static ALWAYS_INLINE void rc_normalize(rc_t *rc) |
69 | { |
70 | if (rc->range < (1 << RC_TOP_BITS)) { |
71 | rc_do_normalize(rc); |
72 | } |
73 | } |
74 | |
75 | /* Called once */ |
76 | static 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 | } |
89 | rc->range = 0xffffffff; |
90 | return rc; |
91 | } |
92 | |
93 | /* Called once */ |
94 | static ALWAYS_INLINE void rc_free(rc_t *rc) |
95 | { |
96 | free(rc); |
97 | } |
98 | |
99 | /* rc_is_bit_1 is called 9 times */ |
100 | static 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 */ |
116 | static ALWAYS_INLINE int rc_get_bit(rc_t *rc, uint16_t *p, int *symbol) |
117 | { |
118 | int ret = rc_is_bit_1(rc, p); |
119 | *symbol = *symbol * 2 + ret; |
120 | return ret; |
121 | } |
122 | |
123 | /* Called once */ |
124 | static 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 */ |
136 | static speed_inline void |
137 | rc_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 | |
148 | typedef 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. */ |
157 | enum { |
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 | |
208 | IF_DESKTOP(long long) int FAST_FUNC |
209 | unpack_lzma_stream(transformer_state_t *xstate) |
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 | |
226 | if (full_read(xstate->src_fd, &header, sizeof(header)) != sizeof(header) |
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 | |
240 | /* Example values from linux-3.3.4.tar.lzma: |
241 | * dict_size: 64M, dst_size: 2^64-1 |
242 | */ |
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 | |
251 | { |
252 | int num_probs; |
253 | |
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 | } |
260 | |
261 | rc = rc_init(xstate->src_fd); /*, RC_BUFFER_SIZE); */ |
262 | |
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; |
309 | if (transformer_write(xstate, buffer, header.dict_size) != (ssize_t)header.dict_size) |
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 { |
318 | int num_bits; |
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; |
443 | if (transformer_write(xstate, buffer, header.dict_size) != (ssize_t)header.dict_size) |
444 | goto bad; |
445 | IF_DESKTOP(total_written += header.dict_size;) |
446 | } |
447 | len--; |
448 | } while (len != 0 && buffer_pos < header.dst_size); |
449 | /* FIXME: ...........^^^^^ |
450 | * shouldn't it be "global_pos + buffer_pos < header.dst_size"? |
451 | */ |
452 | } |
453 | } |
454 | |
455 | { |
456 | IF_NOT_DESKTOP(int total_written = 0; /* success */) |
457 | IF_DESKTOP(total_written += buffer_pos;) |
458 | if (transformer_write(xstate, buffer, buffer_pos) != (ssize_t)buffer_pos) { |
459 | bad: |
460 | total_written = -1; /* failure */ |
461 | } |
462 | rc_free(rc); |
463 | free(p); |
464 | free(buffer); |
465 | return total_written; |
466 | } |
467 | } |
468 |