Branch data Line data Source code
1 : : /* Lzma decompressor for Linux kernel. Shamelessly snarfed
2 : : *from busybox 1.1.1
3 : : *
4 : : *Linux kernel adaptation
5 : : *Copyright (C) 2006 Alain < alain@knaff.lu >
6 : : *
7 : : *Based on small lzma deflate implementation/Small range coder
8 : : *implementation for lzma.
9 : : *Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org >
10 : : *
11 : : *Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
12 : : *Copyright (C) 1999-2005 Igor Pavlov
13 : : *
14 : : *Copyrights of the parts, see headers below.
15 : : *
16 : : *
17 : : *This program is free software; you can redistribute it and/or
18 : : *modify it under the terms of the GNU Lesser General Public
19 : : *License as published by the Free Software Foundation; either
20 : : *version 2.1 of the License, or (at your option) any later version.
21 : : *
22 : : *This program is distributed in the hope that it will be useful,
23 : : *but WITHOUT ANY WARRANTY; without even the implied warranty of
24 : : *MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 : : *Lesser General Public License for more details.
26 : : *
27 : : *You should have received a copy of the GNU Lesser General Public
28 : : *License along with this library; if not, write to the Free Software
29 : : *Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
30 : : */
31 : :
32 : : #ifdef STATIC
33 : : #define PREBOOT
34 : : #else
35 : : #include <linux/decompress/unlzma.h>
36 : : #endif /* STATIC */
37 : :
38 : : #include <linux/decompress/mm.h>
39 : :
40 : : #define MIN(a, b) (((a) < (b)) ? (a) : (b))
41 : :
42 : 0 : static long long INIT read_int(unsigned char *ptr, int size)
43 : : {
44 : 0 : int i;
45 : 0 : long long ret = 0;
46 : :
47 [ # # ]: 0 : for (i = 0; i < size; i++)
48 : 0 : ret = (ret << 8) | ptr[size-i-1];
49 : 0 : return ret;
50 : : }
51 : :
52 : : #define ENDIAN_CONVERT(x) \
53 : : x = (typeof(x))read_int((unsigned char *)&x, sizeof(x))
54 : :
55 : :
56 : : /* Small range coder implementation for lzma.
57 : : *Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org >
58 : : *
59 : : *Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
60 : : *Copyright (c) 1999-2005 Igor Pavlov
61 : : */
62 : :
63 : : #include <linux/compiler.h>
64 : :
65 : : #define LZMA_IOBUF_SIZE 0x10000
66 : :
67 : : struct rc {
68 : : long (*fill)(void*, unsigned long);
69 : : uint8_t *ptr;
70 : : uint8_t *buffer;
71 : : uint8_t *buffer_end;
72 : : long buffer_size;
73 : : uint32_t code;
74 : : uint32_t range;
75 : : uint32_t bound;
76 : : void (*error)(char *);
77 : : };
78 : :
79 : :
80 : : #define RC_TOP_BITS 24
81 : : #define RC_MOVE_BITS 5
82 : : #define RC_MODEL_TOTAL_BITS 11
83 : :
84 : :
85 : 0 : static long INIT nofill(void *buffer, unsigned long len)
86 : : {
87 : 0 : return -1;
88 : : }
89 : :
90 : : /* Called twice: once at startup and once in rc_normalize() */
91 : 0 : static void INIT rc_read(struct rc *rc)
92 : : {
93 : 0 : rc->buffer_size = rc->fill((char *)rc->buffer, LZMA_IOBUF_SIZE);
94 [ # # ]: 0 : if (rc->buffer_size <= 0)
95 : 0 : rc->error("unexpected EOF");
96 : 0 : rc->ptr = rc->buffer;
97 : 0 : rc->buffer_end = rc->buffer + rc->buffer_size;
98 : 0 : }
99 : :
100 : : /* Called once */
101 : 0 : static inline void INIT rc_init(struct rc *rc,
102 : : long (*fill)(void*, unsigned long),
103 : : char *buffer, long buffer_size)
104 : : {
105 [ # # ]: 0 : if (fill)
106 : 0 : rc->fill = fill;
107 : : else
108 : 0 : rc->fill = nofill;
109 : 0 : rc->buffer = (uint8_t *)buffer;
110 : 0 : rc->buffer_size = buffer_size;
111 : 0 : rc->buffer_end = rc->buffer + rc->buffer_size;
112 : 0 : rc->ptr = rc->buffer;
113 : :
114 : 0 : rc->code = 0;
115 : 0 : rc->range = 0xFFFFFFFF;
116 : 0 : }
117 : :
118 : 0 : static inline void INIT rc_init_code(struct rc *rc)
119 : : {
120 : 0 : int i;
121 : :
122 [ # # ]: 0 : for (i = 0; i < 5; i++) {
123 [ # # ]: 0 : if (rc->ptr >= rc->buffer_end)
124 : 0 : rc_read(rc);
125 : 0 : rc->code = (rc->code << 8) | *rc->ptr++;
126 : : }
127 : 0 : }
128 : :
129 : :
130 : : /* Called twice, but one callsite is in inline'd rc_is_bit_0_helper() */
131 : 0 : static void INIT rc_do_normalize(struct rc *rc)
132 : : {
133 [ # # ]: 0 : if (rc->ptr >= rc->buffer_end)
134 : 0 : rc_read(rc);
135 : 0 : rc->range <<= 8;
136 : 0 : rc->code = (rc->code << 8) | *rc->ptr++;
137 : 0 : }
138 : 0 : static inline void INIT rc_normalize(struct rc *rc)
139 : : {
140 [ # # ]: 0 : if (rc->range < (1 << RC_TOP_BITS))
141 : 0 : rc_do_normalize(rc);
142 : 0 : }
143 : :
144 : : /* Called 9 times */
145 : : /* Why rc_is_bit_0_helper exists?
146 : : *Because we want to always expose (rc->code < rc->bound) to optimizer
147 : : */
148 : 0 : static inline uint32_t INIT rc_is_bit_0_helper(struct rc *rc, uint16_t *p)
149 : : {
150 : 0 : rc_normalize(rc);
151 : 0 : rc->bound = *p * (rc->range >> RC_MODEL_TOTAL_BITS);
152 : 0 : return rc->bound;
153 : : }
154 : 0 : static inline int INIT rc_is_bit_0(struct rc *rc, uint16_t *p)
155 : : {
156 : 0 : uint32_t t = rc_is_bit_0_helper(rc, p);
157 : 0 : return rc->code < t;
158 : : }
159 : :
160 : : /* Called ~10 times, but very small, thus inlined */
161 : : static inline void INIT rc_update_bit_0(struct rc *rc, uint16_t *p)
162 : : {
163 : : rc->range = rc->bound;
164 : : *p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
165 : : }
166 : 0 : static inline void INIT rc_update_bit_1(struct rc *rc, uint16_t *p)
167 : : {
168 : 0 : rc->range -= rc->bound;
169 : 0 : rc->code -= rc->bound;
170 : 0 : *p -= *p >> RC_MOVE_BITS;
171 : 0 : }
172 : :
173 : : /* Called 4 times in unlzma loop */
174 : 0 : static int INIT rc_get_bit(struct rc *rc, uint16_t *p, int *symbol)
175 : : {
176 [ # # ]: 0 : if (rc_is_bit_0(rc, p)) {
177 : 0 : rc_update_bit_0(rc, p);
178 : 0 : *symbol *= 2;
179 : 0 : return 0;
180 : : } else {
181 : 0 : rc_update_bit_1(rc, p);
182 : 0 : *symbol = *symbol * 2 + 1;
183 : 0 : return 1;
184 : : }
185 : : }
186 : :
187 : : /* Called once */
188 : 0 : static inline int INIT rc_direct_bit(struct rc *rc)
189 : : {
190 : 0 : rc_normalize(rc);
191 : 0 : rc->range >>= 1;
192 [ # # ]: 0 : if (rc->code >= rc->range) {
193 : 0 : rc->code -= rc->range;
194 : 0 : return 1;
195 : : }
196 : : return 0;
197 : : }
198 : :
199 : : /* Called twice */
200 : : static inline void INIT
201 : 0 : rc_bit_tree_decode(struct rc *rc, uint16_t *p, int num_levels, int *symbol)
202 : : {
203 : 0 : int i = num_levels;
204 : :
205 : 0 : *symbol = 1;
206 [ # # ]: 0 : while (i--)
207 : 0 : rc_get_bit(rc, p + *symbol, symbol);
208 : 0 : *symbol -= 1 << num_levels;
209 : 0 : }
210 : :
211 : :
212 : : /*
213 : : * Small lzma deflate implementation.
214 : : * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org >
215 : : *
216 : : * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)
217 : : * Copyright (C) 1999-2005 Igor Pavlov
218 : : */
219 : :
220 : :
221 : : struct lzma_header {
222 : : uint8_t pos;
223 : : uint32_t dict_size;
224 : : uint64_t dst_size;
225 : : } __attribute__ ((packed)) ;
226 : :
227 : :
228 : : #define LZMA_BASE_SIZE 1846
229 : : #define LZMA_LIT_SIZE 768
230 : :
231 : : #define LZMA_NUM_POS_BITS_MAX 4
232 : :
233 : : #define LZMA_LEN_NUM_LOW_BITS 3
234 : : #define LZMA_LEN_NUM_MID_BITS 3
235 : : #define LZMA_LEN_NUM_HIGH_BITS 8
236 : :
237 : : #define LZMA_LEN_CHOICE 0
238 : : #define LZMA_LEN_CHOICE_2 (LZMA_LEN_CHOICE + 1)
239 : : #define LZMA_LEN_LOW (LZMA_LEN_CHOICE_2 + 1)
240 : : #define LZMA_LEN_MID (LZMA_LEN_LOW \
241 : : + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS)))
242 : : #define LZMA_LEN_HIGH (LZMA_LEN_MID \
243 : : +(1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BITS)))
244 : : #define LZMA_NUM_LEN_PROBS (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS))
245 : :
246 : : #define LZMA_NUM_STATES 12
247 : : #define LZMA_NUM_LIT_STATES 7
248 : :
249 : : #define LZMA_START_POS_MODEL_INDEX 4
250 : : #define LZMA_END_POS_MODEL_INDEX 14
251 : : #define LZMA_NUM_FULL_DISTANCES (1 << (LZMA_END_POS_MODEL_INDEX >> 1))
252 : :
253 : : #define LZMA_NUM_POS_SLOT_BITS 6
254 : : #define LZMA_NUM_LEN_TO_POS_STATES 4
255 : :
256 : : #define LZMA_NUM_ALIGN_BITS 4
257 : :
258 : : #define LZMA_MATCH_MIN_LEN 2
259 : :
260 : : #define LZMA_IS_MATCH 0
261 : : #define LZMA_IS_REP (LZMA_IS_MATCH + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
262 : : #define LZMA_IS_REP_G0 (LZMA_IS_REP + LZMA_NUM_STATES)
263 : : #define LZMA_IS_REP_G1 (LZMA_IS_REP_G0 + LZMA_NUM_STATES)
264 : : #define LZMA_IS_REP_G2 (LZMA_IS_REP_G1 + LZMA_NUM_STATES)
265 : : #define LZMA_IS_REP_0_LONG (LZMA_IS_REP_G2 + LZMA_NUM_STATES)
266 : : #define LZMA_POS_SLOT (LZMA_IS_REP_0_LONG \
267 : : + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX))
268 : : #define LZMA_SPEC_POS (LZMA_POS_SLOT \
269 : : +(LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS))
270 : : #define LZMA_ALIGN (LZMA_SPEC_POS \
271 : : + LZMA_NUM_FULL_DISTANCES - LZMA_END_POS_MODEL_INDEX)
272 : : #define LZMA_LEN_CODER (LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS))
273 : : #define LZMA_REP_LEN_CODER (LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS)
274 : : #define LZMA_LITERAL (LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS)
275 : :
276 : :
277 : : struct writer {
278 : : uint8_t *buffer;
279 : : uint8_t previous_byte;
280 : : size_t buffer_pos;
281 : : int bufsize;
282 : : size_t global_pos;
283 : : long (*flush)(void*, unsigned long);
284 : : struct lzma_header *header;
285 : : };
286 : :
287 : : struct cstate {
288 : : int state;
289 : : uint32_t rep0, rep1, rep2, rep3;
290 : : };
291 : :
292 : 0 : static inline size_t INIT get_pos(struct writer *wr)
293 : : {
294 : 0 : return
295 : 0 : wr->global_pos + wr->buffer_pos;
296 : : }
297 : :
298 : 0 : static inline uint8_t INIT peek_old_byte(struct writer *wr,
299 : : uint32_t offs)
300 : : {
301 [ # # ]: 0 : if (!wr->flush) {
302 : : int32_t pos;
303 [ # # ]: 0 : while (offs > wr->header->dict_size)
304 : 0 : offs -= wr->header->dict_size;
305 : 0 : pos = wr->buffer_pos - offs;
306 : 0 : return wr->buffer[pos];
307 : : } else {
308 : 0 : uint32_t pos = wr->buffer_pos - offs;
309 [ # # ]: 0 : while (pos >= wr->header->dict_size)
310 : 0 : pos += wr->header->dict_size;
311 : 0 : return wr->buffer[pos];
312 : : }
313 : :
314 : : }
315 : :
316 : 0 : static inline int INIT write_byte(struct writer *wr, uint8_t byte)
317 : : {
318 : 0 : wr->buffer[wr->buffer_pos++] = wr->previous_byte = byte;
319 [ # # # # ]: 0 : if (wr->flush && wr->buffer_pos == wr->header->dict_size) {
320 : 0 : wr->buffer_pos = 0;
321 : 0 : wr->global_pos += wr->header->dict_size;
322 : 0 : if (wr->flush((char *)wr->buffer, wr->header->dict_size)
323 [ # # ]: 0 : != wr->header->dict_size)
324 : 0 : return -1;
325 : : }
326 : : return 0;
327 : : }
328 : :
329 : :
330 : 0 : static inline int INIT copy_byte(struct writer *wr, uint32_t offs)
331 : : {
332 : 0 : return write_byte(wr, peek_old_byte(wr, offs));
333 : : }
334 : :
335 : 0 : static inline int INIT copy_bytes(struct writer *wr,
336 : : uint32_t rep0, int len)
337 : : {
338 : 0 : do {
339 [ # # ]: 0 : if (copy_byte(wr, rep0))
340 : : return -1;
341 : 0 : len--;
342 [ # # # # ]: 0 : } while (len != 0 && wr->buffer_pos < wr->header->dst_size);
343 : :
344 : : return len;
345 : : }
346 : :
347 : : static inline int INIT process_bit0(struct writer *wr, struct rc *rc,
348 : : struct cstate *cst, uint16_t *p,
349 : : int pos_state, uint16_t *prob,
350 : : int lc, uint32_t literal_pos_mask) {
351 : : int mi = 1;
352 : : rc_update_bit_0(rc, prob);
353 : : prob = (p + LZMA_LITERAL +
354 : : (LZMA_LIT_SIZE
355 : : * (((get_pos(wr) & literal_pos_mask) << lc)
356 : : + (wr->previous_byte >> (8 - lc))))
357 : : );
358 : :
359 : : if (cst->state >= LZMA_NUM_LIT_STATES) {
360 : : int match_byte = peek_old_byte(wr, cst->rep0);
361 : : do {
362 : : int bit;
363 : : uint16_t *prob_lit;
364 : :
365 : : match_byte <<= 1;
366 : : bit = match_byte & 0x100;
367 : : prob_lit = prob + 0x100 + bit + mi;
368 : : if (rc_get_bit(rc, prob_lit, &mi)) {
369 : : if (!bit)
370 : : break;
371 : : } else {
372 : : if (bit)
373 : : break;
374 : : }
375 : : } while (mi < 0x100);
376 : : }
377 : : while (mi < 0x100) {
378 : : uint16_t *prob_lit = prob + mi;
379 : : rc_get_bit(rc, prob_lit, &mi);
380 : : }
381 : : if (cst->state < 4)
382 : : cst->state = 0;
383 : : else if (cst->state < 10)
384 : : cst->state -= 3;
385 : : else
386 : : cst->state -= 6;
387 : :
388 : : return write_byte(wr, mi);
389 : : }
390 : :
391 : 0 : static inline int INIT process_bit1(struct writer *wr, struct rc *rc,
392 : : struct cstate *cst, uint16_t *p,
393 : : int pos_state, uint16_t *prob) {
394 : 0 : int offset;
395 : 0 : uint16_t *prob_len;
396 : 0 : int num_bits;
397 : 0 : int len;
398 : :
399 : 0 : rc_update_bit_1(rc, prob);
400 : 0 : prob = p + LZMA_IS_REP + cst->state;
401 [ # # ]: 0 : if (rc_is_bit_0(rc, prob)) {
402 : 0 : rc_update_bit_0(rc, prob);
403 : 0 : cst->rep3 = cst->rep2;
404 : 0 : cst->rep2 = cst->rep1;
405 : 0 : cst->rep1 = cst->rep0;
406 [ # # ]: 0 : cst->state = cst->state < LZMA_NUM_LIT_STATES ? 0 : 3;
407 : 0 : prob = p + LZMA_LEN_CODER;
408 : : } else {
409 : 0 : rc_update_bit_1(rc, prob);
410 : 0 : prob = p + LZMA_IS_REP_G0 + cst->state;
411 [ # # ]: 0 : if (rc_is_bit_0(rc, prob)) {
412 : 0 : rc_update_bit_0(rc, prob);
413 : 0 : prob = (p + LZMA_IS_REP_0_LONG
414 : 0 : + (cst->state <<
415 : 0 : LZMA_NUM_POS_BITS_MAX) +
416 : : pos_state);
417 [ # # ]: 0 : if (rc_is_bit_0(rc, prob)) {
418 : 0 : rc_update_bit_0(rc, prob);
419 : :
420 : 0 : cst->state = cst->state < LZMA_NUM_LIT_STATES ?
421 [ # # ]: 0 : 9 : 11;
422 : 0 : return copy_byte(wr, cst->rep0);
423 : : } else {
424 : 0 : rc_update_bit_1(rc, prob);
425 : : }
426 : : } else {
427 : 0 : uint32_t distance;
428 : :
429 : 0 : rc_update_bit_1(rc, prob);
430 : 0 : prob = p + LZMA_IS_REP_G1 + cst->state;
431 [ # # ]: 0 : if (rc_is_bit_0(rc, prob)) {
432 : 0 : rc_update_bit_0(rc, prob);
433 : 0 : distance = cst->rep1;
434 : : } else {
435 : 0 : rc_update_bit_1(rc, prob);
436 : 0 : prob = p + LZMA_IS_REP_G2 + cst->state;
437 [ # # ]: 0 : if (rc_is_bit_0(rc, prob)) {
438 : 0 : rc_update_bit_0(rc, prob);
439 : 0 : distance = cst->rep2;
440 : : } else {
441 : 0 : rc_update_bit_1(rc, prob);
442 : 0 : distance = cst->rep3;
443 : 0 : cst->rep3 = cst->rep2;
444 : : }
445 : 0 : cst->rep2 = cst->rep1;
446 : : }
447 : 0 : cst->rep1 = cst->rep0;
448 : 0 : cst->rep0 = distance;
449 : : }
450 [ # # ]: 0 : cst->state = cst->state < LZMA_NUM_LIT_STATES ? 8 : 11;
451 : 0 : prob = p + LZMA_REP_LEN_CODER;
452 : : }
453 : :
454 : 0 : prob_len = prob + LZMA_LEN_CHOICE;
455 [ # # ]: 0 : if (rc_is_bit_0(rc, prob_len)) {
456 : 0 : rc_update_bit_0(rc, prob_len);
457 : 0 : prob_len = (prob + LZMA_LEN_LOW
458 : 0 : + (pos_state <<
459 : : LZMA_LEN_NUM_LOW_BITS));
460 : 0 : offset = 0;
461 : 0 : num_bits = LZMA_LEN_NUM_LOW_BITS;
462 : : } else {
463 : 0 : rc_update_bit_1(rc, prob_len);
464 : 0 : prob_len = prob + LZMA_LEN_CHOICE_2;
465 [ # # ]: 0 : if (rc_is_bit_0(rc, prob_len)) {
466 : 0 : rc_update_bit_0(rc, prob_len);
467 : 0 : prob_len = (prob + LZMA_LEN_MID
468 : 0 : + (pos_state <<
469 : : LZMA_LEN_NUM_MID_BITS));
470 : 0 : offset = 1 << LZMA_LEN_NUM_LOW_BITS;
471 : 0 : num_bits = LZMA_LEN_NUM_MID_BITS;
472 : : } else {
473 : 0 : rc_update_bit_1(rc, prob_len);
474 : 0 : prob_len = prob + LZMA_LEN_HIGH;
475 : 0 : offset = ((1 << LZMA_LEN_NUM_LOW_BITS)
476 : : + (1 << LZMA_LEN_NUM_MID_BITS));
477 : 0 : num_bits = LZMA_LEN_NUM_HIGH_BITS;
478 : : }
479 : : }
480 : :
481 : 0 : rc_bit_tree_decode(rc, prob_len, num_bits, &len);
482 : 0 : len += offset;
483 : :
484 [ # # ]: 0 : if (cst->state < 4) {
485 : 0 : int pos_slot;
486 : :
487 : 0 : cst->state += LZMA_NUM_LIT_STATES;
488 : 0 : prob =
489 : 0 : p + LZMA_POS_SLOT +
490 : : ((len <
491 : 0 : LZMA_NUM_LEN_TO_POS_STATES ? len :
492 : : LZMA_NUM_LEN_TO_POS_STATES - 1)
493 : 0 : << LZMA_NUM_POS_SLOT_BITS);
494 : 0 : rc_bit_tree_decode(rc, prob,
495 : : LZMA_NUM_POS_SLOT_BITS,
496 : : &pos_slot);
497 [ # # ]: 0 : if (pos_slot >= LZMA_START_POS_MODEL_INDEX) {
498 : 0 : int i, mi;
499 : 0 : num_bits = (pos_slot >> 1) - 1;
500 : 0 : cst->rep0 = 2 | (pos_slot & 1);
501 [ # # ]: 0 : if (pos_slot < LZMA_END_POS_MODEL_INDEX) {
502 : 0 : cst->rep0 <<= num_bits;
503 : 0 : prob = p + LZMA_SPEC_POS +
504 : 0 : cst->rep0 - pos_slot - 1;
505 : : } else {
506 : 0 : num_bits -= LZMA_NUM_ALIGN_BITS;
507 [ # # ]: 0 : while (num_bits--)
508 : 0 : cst->rep0 = (cst->rep0 << 1) |
509 : 0 : rc_direct_bit(rc);
510 : 0 : prob = p + LZMA_ALIGN;
511 : 0 : cst->rep0 <<= LZMA_NUM_ALIGN_BITS;
512 : 0 : num_bits = LZMA_NUM_ALIGN_BITS;
513 : : }
514 : 0 : i = 1;
515 : 0 : mi = 1;
516 [ # # ]: 0 : while (num_bits--) {
517 [ # # ]: 0 : if (rc_get_bit(rc, prob + mi, &mi))
518 : 0 : cst->rep0 |= i;
519 : 0 : i <<= 1;
520 : : }
521 : : } else
522 : 0 : cst->rep0 = pos_slot;
523 [ # # ]: 0 : if (++(cst->rep0) == 0)
524 : 0 : return 0;
525 [ # # ]: 0 : if (cst->rep0 > wr->header->dict_size
526 [ # # ]: 0 : || cst->rep0 > get_pos(wr))
527 : : return -1;
528 : : }
529 : :
530 : 0 : len += LZMA_MATCH_MIN_LEN;
531 : :
532 : 0 : return copy_bytes(wr, cst->rep0, len);
533 : : }
534 : :
535 : :
536 : :
537 : 0 : STATIC inline int INIT unlzma(unsigned char *buf, long in_len,
538 : : long (*fill)(void*, unsigned long),
539 : : long (*flush)(void*, unsigned long),
540 : : unsigned char *output,
541 : : long *posp,
542 : : void(*error)(char *x)
543 : : )
544 : : {
545 : 0 : struct lzma_header header;
546 : 0 : int lc, pb, lp;
547 : 0 : uint32_t pos_state_mask;
548 : 0 : uint32_t literal_pos_mask;
549 : 0 : uint16_t *p;
550 : 0 : int num_probs;
551 : 0 : struct rc rc;
552 : 0 : int i, mi;
553 : 0 : struct writer wr;
554 : 0 : struct cstate cst;
555 : 0 : unsigned char *inbuf;
556 : 0 : int ret = -1;
557 : :
558 : 0 : rc.error = error;
559 : :
560 [ # # ]: 0 : if (buf)
561 : : inbuf = buf;
562 : : else
563 : 0 : inbuf = malloc(LZMA_IOBUF_SIZE);
564 [ # # ]: 0 : if (!inbuf) {
565 : 0 : error("Could not allocate input buffer");
566 : 0 : goto exit_0;
567 : : }
568 : :
569 : 0 : cst.state = 0;
570 : 0 : cst.rep0 = cst.rep1 = cst.rep2 = cst.rep3 = 1;
571 : :
572 : 0 : wr.header = &header;
573 : 0 : wr.flush = flush;
574 : 0 : wr.global_pos = 0;
575 : 0 : wr.previous_byte = 0;
576 : 0 : wr.buffer_pos = 0;
577 : :
578 : 0 : rc_init(&rc, fill, inbuf, in_len);
579 : :
580 [ # # ]: 0 : for (i = 0; i < sizeof(header); i++) {
581 [ # # ]: 0 : if (rc.ptr >= rc.buffer_end)
582 : 0 : rc_read(&rc);
583 : 0 : ((unsigned char *)&header)[i] = *rc.ptr++;
584 : : }
585 : :
586 [ # # ]: 0 : if (header.pos >= (9 * 5 * 5)) {
587 : 0 : error("bad header");
588 : 0 : goto exit_1;
589 : : }
590 : :
591 : 0 : mi = 0;
592 : 0 : lc = header.pos;
593 [ # # ]: 0 : while (lc >= 9) {
594 : 0 : mi++;
595 : 0 : lc -= 9;
596 : : }
597 : : pb = 0;
598 : : lp = mi;
599 [ # # ]: 0 : while (lp >= 5) {
600 : 0 : pb++;
601 : 0 : lp -= 5;
602 : : }
603 : 0 : pos_state_mask = (1 << pb) - 1;
604 : 0 : literal_pos_mask = (1 << lp) - 1;
605 : :
606 : 0 : ENDIAN_CONVERT(header.dict_size);
607 : 0 : ENDIAN_CONVERT(header.dst_size);
608 : :
609 [ # # ]: 0 : if (header.dict_size == 0)
610 : 0 : header.dict_size = 1;
611 : :
612 [ # # ]: 0 : if (output)
613 : 0 : wr.buffer = output;
614 : : else {
615 : 0 : wr.bufsize = MIN(header.dst_size, header.dict_size);
616 : 0 : wr.buffer = large_malloc(wr.bufsize);
617 : : }
618 [ # # ]: 0 : if (wr.buffer == NULL)
619 : 0 : goto exit_1;
620 : :
621 : 0 : num_probs = LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp));
622 : 0 : p = (uint16_t *) large_malloc(num_probs * sizeof(*p));
623 [ # # ]: 0 : if (p == NULL)
624 : 0 : goto exit_2;
625 : : num_probs = LZMA_LITERAL + (LZMA_LIT_SIZE << (lc + lp));
626 [ # # ]: 0 : for (i = 0; i < num_probs; i++)
627 : 0 : p[i] = (1 << RC_MODEL_TOTAL_BITS) >> 1;
628 : :
629 : 0 : rc_init_code(&rc);
630 : :
631 [ # # ]: 0 : while (get_pos(&wr) < header.dst_size) {
632 : 0 : int pos_state = get_pos(&wr) & pos_state_mask;
633 : 0 : uint16_t *prob = p + LZMA_IS_MATCH +
634 : 0 : (cst.state << LZMA_NUM_POS_BITS_MAX) + pos_state;
635 [ # # ]: 0 : if (rc_is_bit_0(&rc, prob)) {
636 [ # # ]: 0 : if (process_bit0(&wr, &rc, &cst, p, pos_state, prob,
637 : : lc, literal_pos_mask)) {
638 : 0 : error("LZMA data is corrupt");
639 : 0 : goto exit_3;
640 : : }
641 : : } else {
642 [ # # ]: 0 : if (process_bit1(&wr, &rc, &cst, p, pos_state, prob)) {
643 : 0 : error("LZMA data is corrupt");
644 : 0 : goto exit_3;
645 : : }
646 [ # # ]: 0 : if (cst.rep0 == 0)
647 : : break;
648 : : }
649 [ # # ]: 0 : if (rc.buffer_size <= 0)
650 : 0 : goto exit_3;
651 : : }
652 : :
653 [ # # ]: 0 : if (posp)
654 : 0 : *posp = rc.ptr-rc.buffer;
655 [ # # # # ]: 0 : if (!wr.flush || wr.flush(wr.buffer, wr.buffer_pos) == wr.buffer_pos)
656 : : ret = 0;
657 : 0 : exit_3:
658 : 0 : large_free(p);
659 : 0 : exit_2:
660 [ # # ]: 0 : if (!output)
661 : 0 : large_free(wr.buffer);
662 : 0 : exit_1:
663 [ # # ]: 0 : if (!buf)
664 : 0 : free(inbuf);
665 : 0 : exit_0:
666 : 0 : return ret;
667 : : }
668 : :
669 : : #ifdef PREBOOT
670 : : STATIC int INIT __decompress(unsigned char *buf, long in_len,
671 : : long (*fill)(void*, unsigned long),
672 : : long (*flush)(void*, unsigned long),
673 : : unsigned char *output, long out_len,
674 : : long *posp,
675 : : void (*error)(char *x))
676 : : {
677 : : return unlzma(buf, in_len - 4, fill, flush, output, posp, error);
678 : : }
679 : : #endif
|
