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 #ifndef STATIC 33 #include <linux/decompress/unlzma.h> 34 #endif /* STATIC */ 35 36 #include <linux/decompress/mm.h> 37 #include <linux/slab.h> 38 39 #define MIN(a, b) (((a) < (b)) ? (a) : (b)) 40 41 static 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 /* Small range coder implementation for lzma. 56 *Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org > 57 * 58 *Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/) 59 *Copyright (c) 1999-2005 Igor Pavlov 60 */ 61 62 #include <linux/compiler.h> 63 64 #define LZMA_IOBUF_SIZE 0x10000 65 66 struct 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 /* Called twice: once at startup and once in rc_normalize() */ 84 static 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 /* Called once */ 94 static 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 108 static 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 /* Called once. TODO: bb_maybe_free() */ 121 static inline void INIT rc_free(struct rc *rc) 122 { 123 free(rc->buffer); 124 } 125 126 /* Called twice, but one callsite is in inline'd rc_is_bit_0_helper() */ 127 static 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 } 134 static 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 /* Called 9 times */ 141 /* Why rc_is_bit_0_helper exists? 142 *Because we want to always expose (rc->code < rc->bound) to optimizer 143 */ 144 static 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 } 150 static 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 /* Called ~10 times, but very small, thus inlined */ 157 static 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 } 162 static 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 /* Called 4 times in unlzma loop */ 170 static 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 /* Called once */ 184 static 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 /* Called twice */ 196 static inline void INIT 197 rc_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 * Small lzma deflate implementation. 210 * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org > 211 * 212 * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/) 213 * Copyright (C) 1999-2005 Igor Pavlov 214 */ 215 216 217 struct 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 273 struct 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 283 struct cstate { 284 int state; 285 uint32_t rep0, rep1, rep2, rep3; 286 }; 287 288 static inline size_t INIT get_pos(struct writer *wr) 289 { 290 return 291 wr->global_pos + wr->buffer_pos; 292 } 293 294 static 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 312 static 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 323 static inline void INIT copy_byte(struct writer *wr, uint32_t offs) 324 { 325 write_byte(wr, peek_old_byte(wr, offs)); 326 } 327 328 static 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 337 static 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 380 static 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 524 STATIC 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; /* Uncompressed size hack active in pre-boot 548 environment */ 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); 638 exit_2: 639 if (!output) 640 large_free(wr.buffer); 641 exit_1: 642 if (!buf) 643 free(inbuf); 644 exit_0: 645 return ret; 646 } 647 648 #define decompress unlzma 649