blob: ca32bd82cd0e962845a2cecb2fe7d846b27e1bdd
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_aux_data_t *aux UNUSED_PARAM, int src_fd, int dst_fd) |
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 | int num_bits; |
218 | int num_probs; |
219 | rc_t *rc; |
220 | int i; |
221 | uint8_t *buffer; |
222 | uint8_t previous_byte = 0; |
223 | size_t buffer_pos = 0, global_pos = 0; |
224 | int len = 0; |
225 | int state = 0; |
226 | uint32_t rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; |
227 | |
228 | if (full_read(src_fd, &header, sizeof(header)) != sizeof(header) |
229 | || header.pos >= (9 * 5 * 5) |
230 | ) { |
231 | bb_error_msg("bad lzma header"); |
232 | return -1; |
233 | } |
234 | |
235 | i = header.pos / 9; |
236 | lc = header.pos % 9; |
237 | pb = i / 5; |
238 | lp = i % 5; |
239 | pos_state_mask = (1 << pb) - 1; |
240 | literal_pos_mask = (1 << lp) - 1; |
241 | |
242 | header.dict_size = SWAP_LE32(header.dict_size); |
243 | header.dst_size = SWAP_LE64(header.dst_size); |
244 | |
245 | if (header.dict_size == 0) |
246 | header.dict_size++; |
247 | |
248 | buffer = xmalloc(MIN(header.dst_size, header.dict_size)); |
249 | |
250 | num_probs = LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp)); |
251 | p = xmalloc(num_probs * sizeof(*p)); |
252 | num_probs += LZMA_LITERAL - LZMA_BASE_SIZE; |
253 | for (i = 0; i < num_probs; i++) |
254 | p[i] = (1 << RC_MODEL_TOTAL_BITS) >> 1; |
255 | |
256 | rc = rc_init(src_fd); /*, RC_BUFFER_SIZE); */ |
257 | |
258 | while (global_pos + buffer_pos < header.dst_size) { |
259 | int pos_state = (buffer_pos + global_pos) & pos_state_mask; |
260 | uint16_t *prob = p + LZMA_IS_MATCH + (state << LZMA_NUM_POS_BITS_MAX) + pos_state; |
261 | |
262 | if (!rc_is_bit_1(rc, prob)) { |
263 | static const char next_state[LZMA_NUM_STATES] = |
264 | { 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5 }; |
265 | int mi = 1; |
266 | |
267 | prob = (p + LZMA_LITERAL |
268 | + (LZMA_LIT_SIZE * ((((buffer_pos + global_pos) & literal_pos_mask) << lc) |
269 | + (previous_byte >> (8 - lc)) |
270 | ) |
271 | ) |
272 | ); |
273 | |
274 | if (state >= LZMA_NUM_LIT_STATES) { |
275 | int match_byte; |
276 | uint32_t pos = buffer_pos - rep0; |
277 | |
278 | while (pos >= header.dict_size) |
279 | pos += header.dict_size; |
280 | match_byte = buffer[pos]; |
281 | do { |
282 | int bit; |
283 | |
284 | match_byte <<= 1; |
285 | bit = match_byte & 0x100; |
286 | bit ^= (rc_get_bit(rc, prob + 0x100 + bit + mi, &mi) << 8); /* 0x100 or 0 */ |
287 | if (bit) |
288 | break; |
289 | } while (mi < 0x100); |
290 | } |
291 | while (mi < 0x100) { |
292 | rc_get_bit(rc, prob + mi, &mi); |
293 | } |
294 | |
295 | state = next_state[state]; |
296 | |
297 | previous_byte = (uint8_t) mi; |
298 | #if ENABLE_FEATURE_LZMA_FAST |
299 | one_byte1: |
300 | buffer[buffer_pos++] = previous_byte; |
301 | if (buffer_pos == header.dict_size) { |
302 | buffer_pos = 0; |
303 | global_pos += header.dict_size; |
304 | if (full_write(dst_fd, buffer, header.dict_size) != (ssize_t)header.dict_size) |
305 | goto bad; |
306 | IF_DESKTOP(total_written += header.dict_size;) |
307 | } |
308 | #else |
309 | len = 1; |
310 | goto one_byte2; |
311 | #endif |
312 | } else { |
313 | int offset; |
314 | uint16_t *prob2; |
315 | #define prob_len prob2 |
316 | |
317 | prob2 = p + LZMA_IS_REP + state; |
318 | if (!rc_is_bit_1(rc, prob2)) { |
319 | rep3 = rep2; |
320 | rep2 = rep1; |
321 | rep1 = rep0; |
322 | state = state < LZMA_NUM_LIT_STATES ? 0 : 3; |
323 | prob2 = p + LZMA_LEN_CODER; |
324 | } else { |
325 | prob2 += LZMA_IS_REP_G0 - LZMA_IS_REP; |
326 | if (!rc_is_bit_1(rc, prob2)) { |
327 | prob2 = (p + LZMA_IS_REP_0_LONG |
328 | + (state << LZMA_NUM_POS_BITS_MAX) |
329 | + pos_state |
330 | ); |
331 | if (!rc_is_bit_1(rc, prob2)) { |
332 | #if ENABLE_FEATURE_LZMA_FAST |
333 | uint32_t pos = buffer_pos - rep0; |
334 | state = state < LZMA_NUM_LIT_STATES ? 9 : 11; |
335 | while (pos >= header.dict_size) |
336 | pos += header.dict_size; |
337 | previous_byte = buffer[pos]; |
338 | goto one_byte1; |
339 | #else |
340 | state = state < LZMA_NUM_LIT_STATES ? 9 : 11; |
341 | len = 1; |
342 | goto string; |
343 | #endif |
344 | } |
345 | } else { |
346 | uint32_t distance; |
347 | |
348 | prob2 += LZMA_IS_REP_G1 - LZMA_IS_REP_G0; |
349 | distance = rep1; |
350 | if (rc_is_bit_1(rc, prob2)) { |
351 | prob2 += LZMA_IS_REP_G2 - LZMA_IS_REP_G1; |
352 | distance = rep2; |
353 | if (rc_is_bit_1(rc, prob2)) { |
354 | distance = rep3; |
355 | rep3 = rep2; |
356 | } |
357 | rep2 = rep1; |
358 | } |
359 | rep1 = rep0; |
360 | rep0 = distance; |
361 | } |
362 | state = state < LZMA_NUM_LIT_STATES ? 8 : 11; |
363 | prob2 = p + LZMA_REP_LEN_CODER; |
364 | } |
365 | |
366 | prob_len = prob2 + LZMA_LEN_CHOICE; |
367 | num_bits = LZMA_LEN_NUM_LOW_BITS; |
368 | if (!rc_is_bit_1(rc, prob_len)) { |
369 | prob_len += LZMA_LEN_LOW - LZMA_LEN_CHOICE |
370 | + (pos_state << LZMA_LEN_NUM_LOW_BITS); |
371 | offset = 0; |
372 | } else { |
373 | prob_len += LZMA_LEN_CHOICE_2 - LZMA_LEN_CHOICE; |
374 | if (!rc_is_bit_1(rc, prob_len)) { |
375 | prob_len += LZMA_LEN_MID - LZMA_LEN_CHOICE_2 |
376 | + (pos_state << LZMA_LEN_NUM_MID_BITS); |
377 | offset = 1 << LZMA_LEN_NUM_LOW_BITS; |
378 | num_bits += LZMA_LEN_NUM_MID_BITS - LZMA_LEN_NUM_LOW_BITS; |
379 | } else { |
380 | prob_len += LZMA_LEN_HIGH - LZMA_LEN_CHOICE_2; |
381 | offset = ((1 << LZMA_LEN_NUM_LOW_BITS) |
382 | + (1 << LZMA_LEN_NUM_MID_BITS)); |
383 | num_bits += LZMA_LEN_NUM_HIGH_BITS - LZMA_LEN_NUM_LOW_BITS; |
384 | } |
385 | } |
386 | rc_bit_tree_decode(rc, prob_len, num_bits, &len); |
387 | len += offset; |
388 | |
389 | if (state < 4) { |
390 | int pos_slot; |
391 | uint16_t *prob3; |
392 | |
393 | state += LZMA_NUM_LIT_STATES; |
394 | prob3 = p + LZMA_POS_SLOT + |
395 | ((len < LZMA_NUM_LEN_TO_POS_STATES ? len : |
396 | LZMA_NUM_LEN_TO_POS_STATES - 1) |
397 | << LZMA_NUM_POS_SLOT_BITS); |
398 | rc_bit_tree_decode(rc, prob3, |
399 | LZMA_NUM_POS_SLOT_BITS, &pos_slot); |
400 | rep0 = pos_slot; |
401 | if (pos_slot >= LZMA_START_POS_MODEL_INDEX) { |
402 | int i2, mi2, num_bits2 = (pos_slot >> 1) - 1; |
403 | rep0 = 2 | (pos_slot & 1); |
404 | if (pos_slot < LZMA_END_POS_MODEL_INDEX) { |
405 | rep0 <<= num_bits2; |
406 | prob3 = p + LZMA_SPEC_POS + rep0 - pos_slot - 1; |
407 | } else { |
408 | for (; num_bits2 != LZMA_NUM_ALIGN_BITS; num_bits2--) |
409 | rep0 = (rep0 << 1) | rc_direct_bit(rc); |
410 | rep0 <<= LZMA_NUM_ALIGN_BITS; |
411 | prob3 = p + LZMA_ALIGN; |
412 | } |
413 | i2 = 1; |
414 | mi2 = 1; |
415 | while (num_bits2--) { |
416 | if (rc_get_bit(rc, prob3 + mi2, &mi2)) |
417 | rep0 |= i2; |
418 | i2 <<= 1; |
419 | } |
420 | } |
421 | if (++rep0 == 0) |
422 | break; |
423 | } |
424 | |
425 | len += LZMA_MATCH_MIN_LEN; |
426 | IF_NOT_FEATURE_LZMA_FAST(string:) |
427 | do { |
428 | uint32_t pos = buffer_pos - rep0; |
429 | while (pos >= header.dict_size) |
430 | pos += header.dict_size; |
431 | previous_byte = buffer[pos]; |
432 | IF_NOT_FEATURE_LZMA_FAST(one_byte2:) |
433 | buffer[buffer_pos++] = previous_byte; |
434 | if (buffer_pos == header.dict_size) { |
435 | buffer_pos = 0; |
436 | global_pos += header.dict_size; |
437 | if (full_write(dst_fd, buffer, header.dict_size) != (ssize_t)header.dict_size) |
438 | goto bad; |
439 | IF_DESKTOP(total_written += header.dict_size;) |
440 | } |
441 | len--; |
442 | } while (len != 0 && buffer_pos < header.dst_size); |
443 | } |
444 | } |
445 | |
446 | { |
447 | IF_NOT_DESKTOP(int total_written = 0; /* success */) |
448 | IF_DESKTOP(total_written += buffer_pos;) |
449 | if (full_write(dst_fd, buffer, buffer_pos) != (ssize_t)buffer_pos) { |
450 | bad: |
451 | total_written = -1; /* failure */ |
452 | } |
453 | rc_free(rc); |
454 | free(p); |
455 | free(buffer); |
456 | return total_written; |
457 | } |
458 | } |
459 |