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