1 /* $NetBSD: unlz.c,v 1.11 2026/01/10 00:48:44 mrg Exp $ */ 2 3 /*- 4 * Copyright (c) 2018 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Christos Zoulas. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* Lzd - Educational decompressor for the lzip format 33 Copyright (C) 2013-2018 Antonio Diaz Diaz. 34 35 This program is free software. Redistribution and use in source and 36 binary forms, with or without modification, are permitted provided 37 that the following conditions are met: 38 39 1. Redistributions of source code must retain the above copyright 40 notice, this list of conditions and the following disclaimer. 41 42 2. Redistributions in binary form must reproduce the above copyright 43 notice, this list of conditions and the following disclaimer in the 44 documentation and/or other materials provided with the distribution. 45 46 This program is distributed in the hope that it will be useful, 47 but WITHOUT ANY WARRANTY; without even the implied warranty of 48 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 49 */ 50 51 #include <sys/param.h> 52 #include <stdio.h> 53 #include <string.h> 54 #include <stdlib.h> 55 #include <stdint.h> 56 #include <stdbool.h> 57 #include <errno.h> 58 #include <unistd.h> 59 60 #define LZ_STATES 12 61 62 #define LITERAL_CONTEXT_BITS 3 63 #define POS_STATE_BITS 2 64 #define POS_STATES (1 << POS_STATE_BITS) 65 #define POS_STATE_MASK (POS_STATES - 1) 66 67 #define STATES 4 68 #define DIS_SLOT_BITS 6 69 70 #define DIS_MODEL_START 4 71 #define DIS_MODEL_END 14 72 73 #define MODELED_DISTANCES (1 << (DIS_MODEL_END / 2)) 74 #define DIS_ALIGN_BITS 4 75 #define DIS_ALIGN_SIZE (1 << DIS_ALIGN_BITS) 76 77 #define LOW_BITS 3 78 #define MID_BITS 3 79 #define HIGH_BITS 8 80 81 #define LOW_SYMBOLS (1 << LOW_BITS) 82 #define MID_SYMBOLS (1 << MID_BITS) 83 #define HIGH_SYMBOLS (1 << HIGH_BITS) 84 85 #define MAX_SYMBOLS (LOW_SYMBOLS + MID_SYMBOLS + HIGH_SYMBOLS) 86 87 #define MIN_MATCH_LEN 2 88 89 #define BIT_MODEL_MOVE_BITS 5 90 #define BIT_MODEL_TOTAL_BITS 11 91 #define BIT_MODEL_TOTAL (1 << BIT_MODEL_TOTAL_BITS) 92 #define BIT_MODEL_INIT (BIT_MODEL_TOTAL / 2) 93 94 static const int lz_st_next[] = { 95 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5, 96 }; 97 98 static bool 99 lz_st_is_char(int st) { 100 return st < 7; 101 } 102 103 static int 104 lz_st_get_char(int st) { 105 return lz_st_next[st]; 106 } 107 108 static int 109 lz_st_get_match(int st) { 110 return st < 7 ? 7 : 10; 111 } 112 113 static int 114 lz_st_get_rep(int st) { 115 return st < 7 ? 8 : 11; 116 } 117 118 static int 119 lz_st_get_short_rep(int st) { 120 return st < 7 ? 9 : 11; 121 } 122 123 struct lz_len_model { 124 int choice1; 125 int choice2; 126 int bm_low[POS_STATES][LOW_SYMBOLS]; 127 int bm_mid[POS_STATES][MID_SYMBOLS]; 128 int bm_high[HIGH_SYMBOLS]; 129 }; 130 131 static uint32_t lz_crc[256]; 132 133 static void 134 lz_crc_init(void) 135 { 136 for (unsigned i = 0; i < __arraycount(lz_crc); i++) { 137 unsigned c = i; 138 for (unsigned j = 0; j < 8; j++) { 139 if (c & 1) 140 c = 0xEDB88320U ^ (c >> 1); 141 else 142 c >>= 1; 143 } 144 lz_crc[i] = c; 145 } 146 } 147 148 static void 149 lz_crc_update(uint32_t *crc, const uint8_t *buf, size_t len) 150 { 151 for (size_t i = 0; i < len; i++) 152 *crc = lz_crc[(*crc ^ buf[i]) & 0xFF] ^ (*crc >> 8); 153 } 154 155 struct lz_range_decoder { 156 FILE *fp; 157 uint32_t code; 158 uint32_t range; 159 }; 160 161 static int 162 lz_rd_create(struct lz_range_decoder *rd, FILE *fp) 163 { 164 rd->fp = fp; 165 rd->code = 0; 166 rd->range = ~0; 167 for (int i = 0; i < 5; i++) 168 rd->code = (rd->code << 8) | (uint8_t)getc(rd->fp); 169 return ferror(rd->fp) ? -1 : 0; 170 } 171 172 static unsigned 173 lz_rd_decode(struct lz_range_decoder *rd, int num_bits) 174 { 175 unsigned symbol = 0; 176 177 for (int i = num_bits; i > 0; i--) { 178 rd->range >>= 1; 179 symbol <<= 1; 180 if (rd->code >= rd->range) { 181 rd->code -= rd->range; 182 symbol |= 1; 183 } 184 if (rd->range <= 0x00FFFFFFU) { 185 rd->range <<= 8; 186 rd->code = (rd->code << 8) | (uint8_t)getc(rd->fp); 187 } 188 } 189 190 return symbol; 191 } 192 193 static unsigned 194 lz_rd_decode_bit(struct lz_range_decoder *rd, int *bm) 195 { 196 unsigned symbol; 197 const uint32_t bound = (rd->range >> BIT_MODEL_TOTAL_BITS) * *bm; 198 199 if(rd->code < bound) { 200 rd->range = bound; 201 *bm += (BIT_MODEL_TOTAL - *bm) >> BIT_MODEL_MOVE_BITS; 202 symbol = 0; 203 } 204 else { 205 rd->range -= bound; 206 rd->code -= bound; 207 *bm -= *bm >> BIT_MODEL_MOVE_BITS; 208 symbol = 1; 209 } 210 211 if (rd->range <= 0x00FFFFFFU) { 212 rd->range <<= 8; 213 rd->code = (rd->code << 8) | (uint8_t)getc(rd->fp); 214 } 215 return symbol; 216 } 217 218 static unsigned 219 lz_rd_decode_tree(struct lz_range_decoder *rd, int *bm, int num_bits) 220 { 221 unsigned symbol = 1; 222 223 for (int i = 0; i < num_bits; i++) 224 symbol = (symbol << 1) | lz_rd_decode_bit(rd, &bm[symbol]); 225 226 return symbol - (1 << num_bits); 227 } 228 229 static unsigned 230 lz_rd_decode_tree_reversed(struct lz_range_decoder *rd, int *bm, int num_bits) 231 { 232 unsigned symbol = lz_rd_decode_tree(rd, bm, num_bits); 233 unsigned reversed_symbol = 0; 234 235 for (int i = 0; i < num_bits; i++) { 236 reversed_symbol = (reversed_symbol << 1) | (symbol & 1); 237 symbol >>= 1; 238 } 239 240 return reversed_symbol; 241 } 242 243 static unsigned 244 lz_rd_decode_matched(struct lz_range_decoder *rd, int *bm, int match_byte) 245 { 246 unsigned symbol = 1; 247 248 for (int i = 7; i >= 0; i--) { 249 const unsigned match_bit = (match_byte >> i) & 1; 250 const unsigned bit = lz_rd_decode_bit(rd, 251 &bm[symbol + (match_bit << 8) + 0x100]); 252 symbol = (symbol << 1) | bit; 253 if (match_bit != bit) { 254 while (symbol < 0x100) { 255 symbol = (symbol << 1) | 256 lz_rd_decode_bit(rd, &bm[symbol]); 257 } 258 break; 259 } 260 } 261 return symbol & 0xFF; 262 } 263 264 static unsigned 265 lz_rd_decode_len(struct lz_range_decoder *rd, struct lz_len_model *lm, 266 int pos_state) 267 { 268 if (lz_rd_decode_bit(rd, &lm->choice1) == 0) 269 return lz_rd_decode_tree(rd, lm->bm_low[pos_state], LOW_BITS); 270 271 if (lz_rd_decode_bit(rd, &lm->choice2) == 0) { 272 return LOW_SYMBOLS + 273 lz_rd_decode_tree(rd, lm->bm_mid[pos_state], MID_BITS); 274 } 275 276 return LOW_SYMBOLS + MID_SYMBOLS + 277 lz_rd_decode_tree(rd, lm->bm_high, HIGH_BITS); 278 } 279 280 struct lz_decoder { 281 FILE *fin, *fout; 282 FILE *prein; 283 off_t pos, ppos, spos, dict_size; 284 bool wrapped; 285 uint32_t crc; 286 uint8_t *obuf; 287 struct lz_range_decoder rdec; 288 char *pre; 289 size_t prelen; 290 }; 291 292 static int 293 lz_flush(struct lz_decoder *lz) 294 { 295 off_t offs = lz->pos - lz->spos; 296 if (offs <= 0) 297 return -1; 298 299 size_t size = (size_t)offs; 300 lz_crc_update(&lz->crc, lz->obuf + lz->spos, size); 301 if (!tflag && fwrite(lz->obuf + lz->spos, 1, size, lz->fout) != size) 302 return -1; 303 304 lz->wrapped = lz->pos >= lz->dict_size; 305 if (lz->wrapped) { 306 lz->ppos += lz->pos; 307 lz->pos = 0; 308 } 309 lz->spos = lz->pos; 310 return 0; 311 } 312 313 static int 314 lz_read(void *cookie, char *rbp, int num) 315 { 316 int copylen = 0; 317 struct lz_decoder *lz = cookie; 318 319 if (lz->prelen) { 320 copylen = MIN(num, (int)lz->prelen); 321 memcpy(rbp, lz->pre, copylen); 322 323 lz->pre += copylen; 324 lz->prelen -= copylen; 325 rbp += copylen; 326 num -= copylen; 327 } 328 329 if (num) 330 copylen += fread(rbp, 1, num, lz->prein); 331 332 return copylen; 333 } 334 335 static int 336 lz_close(void *cookie) 337 { 338 struct lz_decoder *lz = cookie; 339 340 fclose(lz->prein); 341 342 return 0; 343 } 344 345 static void 346 lz_destroy(struct lz_decoder *lz) 347 { 348 if (lz->fin) 349 fclose(lz->fin); 350 if (lz->fout) 351 fclose(lz->fout); 352 free(lz->obuf); 353 } 354 355 static int 356 lz_create(struct lz_decoder *lz, int fin, int fdout, int dict_size, 357 char *pre, size_t prelen) 358 { 359 memset(lz, 0, sizeof(*lz)); 360 361 if (prelen == 0) { 362 lz->fin = fdopen(dup(fin), "r"); 363 if (lz->fin == NULL) 364 goto out; 365 } else { 366 /* Need to drain the pre-buffer first. */ 367 lz->prein = fdopen(dup(fin), "r"); 368 if (lz->prein == NULL) 369 goto out; 370 371 lz->fin = funopen(lz, lz_read, NULL, NULL, lz_close); 372 if (lz->fin == NULL) { 373 fclose(lz->prein); 374 goto out; 375 } 376 377 lz->pre = pre; 378 lz->prelen = prelen; 379 } 380 381 lz->fout = fdopen(dup(fdout), "w"); 382 if (lz->fout == NULL) 383 goto out; 384 385 lz->pos = lz->ppos = lz->spos = 0; 386 lz->crc = ~0; 387 lz->dict_size = dict_size; 388 lz->wrapped = false; 389 390 lz->obuf = malloc(dict_size); 391 if (lz->obuf == NULL) 392 goto out; 393 394 if (lz_rd_create(&lz->rdec, lz->fin) == -1) 395 goto out; 396 return 0; 397 out: 398 lz_destroy(lz); 399 return -1; 400 } 401 402 static uint8_t 403 lz_peek(const struct lz_decoder *lz, unsigned ahead) 404 { 405 off_t diff = lz->pos - ahead - 1; 406 407 if (diff >= 0) 408 return lz->obuf[diff]; 409 410 if (lz->wrapped) 411 return lz->obuf[lz->dict_size + diff]; 412 413 return 0; 414 } 415 416 static void 417 lz_put(struct lz_decoder *lz, uint8_t b) 418 { 419 lz->obuf[lz->pos++] = b; 420 if (lz->dict_size == lz->pos) 421 lz_flush(lz); 422 } 423 424 static off_t 425 lz_get_data_position(const struct lz_decoder *lz) 426 { 427 return lz->ppos + lz->pos; 428 } 429 430 static unsigned 431 lz_get_crc(const struct lz_decoder *lz) 432 { 433 return lz->crc ^ 0xffffffffU; 434 } 435 436 static void 437 lz_bm_init(int *a, size_t l) 438 { 439 for (size_t i = 0; i < l; i++) 440 a[i] = BIT_MODEL_INIT; 441 } 442 443 #define LZ_BM_INIT(a) lz_bm_init(a, __arraycount(a)) 444 #define LZ_BM_INIT2(a) do { \ 445 size_t l = __arraycount(a[0]); \ 446 for (size_t i = 0; i < __arraycount(a); i++) \ 447 lz_bm_init(a[i], l); \ 448 } while (0) 449 450 #define LZ_MODEL_INIT(a) do { \ 451 a.choice1 = BIT_MODEL_INIT; \ 452 a.choice2 = BIT_MODEL_INIT; \ 453 LZ_BM_INIT2(a.bm_low); \ 454 LZ_BM_INIT2(a.bm_mid); \ 455 LZ_BM_INIT(a.bm_high); \ 456 } while (0) 457 458 static bool 459 lz_decode_member(struct lz_decoder *lz) 460 { 461 int bm_literal[1 << LITERAL_CONTEXT_BITS][0x300]; 462 int bm_match[LZ_STATES][POS_STATES]; 463 int bm_rep[4][LZ_STATES]; 464 int bm_len[LZ_STATES][POS_STATES]; 465 int bm_dis_slot[LZ_STATES][1 << DIS_SLOT_BITS]; 466 int bm_dis[MODELED_DISTANCES - DIS_MODEL_END + 1]; 467 int bm_align[DIS_ALIGN_SIZE]; 468 469 LZ_BM_INIT2(bm_literal); 470 LZ_BM_INIT2(bm_match); 471 LZ_BM_INIT2(bm_rep); 472 LZ_BM_INIT2(bm_len); 473 LZ_BM_INIT2(bm_dis_slot); 474 LZ_BM_INIT(bm_dis); 475 LZ_BM_INIT(bm_align); 476 477 struct lz_len_model match_len_model; 478 struct lz_len_model rep_len_model; 479 480 LZ_MODEL_INIT(match_len_model); 481 LZ_MODEL_INIT(rep_len_model); 482 483 struct lz_range_decoder *rd = &lz->rdec; 484 unsigned rep[4] = { 0 }; 485 486 487 int state = 0; 488 489 while (!feof(lz->fin) && !ferror(lz->fin)) { 490 const int pos_state = lz_get_data_position(lz) & POS_STATE_MASK; 491 // bit 1 492 if (lz_rd_decode_bit(rd, &bm_match[state][pos_state]) == 0) { 493 const uint8_t prev_byte = lz_peek(lz, 0); 494 const int literal_state = 495 prev_byte >> (8 - LITERAL_CONTEXT_BITS); 496 int *bm = bm_literal[literal_state]; 497 if (lz_st_is_char(state)) 498 lz_put(lz, lz_rd_decode_tree(rd, bm, 8)); 499 else { 500 int peek = lz_peek(lz, rep[0]); 501 lz_put(lz, lz_rd_decode_matched(rd, bm, peek)); 502 } 503 state = lz_st_get_char(state); 504 continue; 505 } 506 int len; 507 // bit 2 508 if (lz_rd_decode_bit(rd, &bm_rep[0][state]) != 0) { 509 // bit 3 510 if (lz_rd_decode_bit(rd, &bm_rep[1][state]) == 0) { 511 // bit 4 512 if (lz_rd_decode_bit(rd, 513 &bm_len[state][pos_state]) == 0) 514 { 515 state = lz_st_get_short_rep(state); 516 lz_put(lz, lz_peek(lz, rep[0])); 517 continue; 518 } 519 } else { 520 unsigned distance; 521 // bit 4 522 if (lz_rd_decode_bit(rd, &bm_rep[2][state]) 523 == 0) 524 distance = rep[1]; 525 else { 526 // bit 5 527 if (lz_rd_decode_bit(rd, 528 &bm_rep[3][state]) == 0) 529 distance = rep[2]; 530 else { 531 distance = rep[3]; 532 rep[3] = rep[2]; 533 } 534 rep[2] = rep[1]; 535 } 536 rep[1] = rep[0]; 537 rep[0] = distance; 538 } 539 state = lz_st_get_rep(state); 540 len = MIN_MATCH_LEN + 541 lz_rd_decode_len(rd, &rep_len_model, pos_state); 542 } else { 543 rep[3] = rep[2]; rep[2] = rep[1]; rep[1] = rep[0]; 544 len = MIN_MATCH_LEN + 545 lz_rd_decode_len(rd, &match_len_model, pos_state); 546 const int len_state = 547 MIN(len - MIN_MATCH_LEN, STATES - 1); 548 rep[0] = lz_rd_decode_tree(rd, bm_dis_slot[len_state], 549 DIS_SLOT_BITS); 550 if (rep[0] >= DIS_MODEL_START) { 551 const unsigned dis_slot = rep[0]; 552 const int direct_bits = (dis_slot >> 1) - 1; 553 rep[0] = (2 | (dis_slot & 1)) << direct_bits; 554 if (dis_slot < DIS_MODEL_END) 555 rep[0] += lz_rd_decode_tree_reversed(rd, 556 &bm_dis[rep[0] - dis_slot], 557 direct_bits); 558 else { 559 rep[0] += lz_rd_decode(rd, direct_bits 560 - DIS_ALIGN_BITS) << DIS_ALIGN_BITS; 561 rep[0] += lz_rd_decode_tree_reversed(rd, 562 bm_align, DIS_ALIGN_BITS); 563 if (rep[0] == 0xFFFFFFFFU) { 564 lz_flush(lz); 565 return len == MIN_MATCH_LEN; 566 } 567 } 568 } 569 state = lz_st_get_match(state); 570 if (rep[0] >= lz->dict_size || 571 (rep[0] >= lz->pos && !lz->wrapped)) { 572 lz_flush(lz); 573 return false; 574 } 575 } 576 for (int i = 0; i < len; i++) 577 lz_put(lz, lz_peek(lz, rep[0])); 578 } 579 lz_flush(lz); 580 return false; 581 } 582 583 /* 584 * 0-3 CRC32 of the uncompressed data 585 * 4-11 size of the uncompressed data 586 * 12-19 member size including header and trailer 587 */ 588 #define TRAILER_SIZE 20 589 590 591 static off_t 592 lz_decode(int fin, int fdout, unsigned dict_size, off_t *insize, 593 char *pre, size_t prelen) 594 { 595 struct lz_decoder lz; 596 off_t rv = -1; 597 598 if (lz_create(&lz, fin, fdout, dict_size, pre, prelen) == -1) 599 return -1; 600 601 if (!lz_decode_member(&lz)) 602 goto out; 603 604 uint8_t trailer[TRAILER_SIZE]; 605 606 for(size_t i = 0; i < __arraycount(trailer); i++) 607 trailer[i] = (uint8_t)getc(lz.fin); 608 609 unsigned crc = 0; 610 for (int i = 3; i >= 0; --i) { 611 crc <<= 8; 612 crc += trailer[i]; 613 } 614 615 int64_t data_size = 0; 616 for (int i = 11; i >= 4; --i) { 617 data_size <<= 8; 618 data_size += trailer[i]; 619 } 620 621 if (crc != lz_get_crc(&lz) || data_size != lz_get_data_position(&lz)) 622 goto out; 623 624 rv = 0; 625 for (int i = 19; i >= 12; --i) { 626 rv <<= 8; 627 rv += trailer[i]; 628 } 629 if (insize) 630 *insize = rv; 631 #if 0 632 /* Does not work with pipes */ 633 rv = ftello(lz.fout); 634 #else 635 rv = data_size; 636 #endif 637 out: 638 lz_destroy(&lz); 639 return rv; 640 } 641 642 643 /* 644 * 0-3 magic 645 * 4 version 646 * 5 coded dict_size 647 */ 648 #define HDR_SIZE 6 649 #define MIN_DICTIONARY_SIZE (1 << 12) 650 #define MAX_DICTIONARY_SIZE (1 << 29) 651 652 static const char hdrmagic[] = { 'L', 'Z', 'I', 'P', 1 }; 653 654 static unsigned 655 lz_get_dict_size(unsigned char c) 656 { 657 unsigned dict_size = 1 << (c & 0x1f); 658 dict_size -= (dict_size >> 4) * ( (c >> 5) & 0x7); 659 if (dict_size < MIN_DICTIONARY_SIZE || dict_size > MAX_DICTIONARY_SIZE) 660 return 0; 661 return dict_size; 662 } 663 664 static off_t 665 unlz(int fin, int fout, char *pre, size_t prelen, off_t *bytes_in) 666 { 667 if (lz_crc[0] == 0) 668 lz_crc_init(); 669 size_t copylen = 0; 670 671 char header[HDR_SIZE]; 672 673 if (pre && prelen) { 674 copylen = MIN(prelen, sizeof header); 675 memcpy(header, pre, copylen); 676 677 pre += copylen; 678 prelen -= copylen; 679 } 680 681 if (copylen < sizeof header) { 682 ssize_t nr = read(fin, header + copylen, 683 sizeof(header) - copylen); 684 685 switch (nr) { 686 case -1: 687 return -1; 688 case 0: 689 return prelen ? -1 : 0; 690 default: 691 if ((size_t)nr != sizeof(header) - copylen) 692 return -1; 693 break; 694 } 695 } 696 697 if (memcmp(header, hdrmagic, sizeof(hdrmagic)) != 0) 698 return -1; 699 700 unsigned dict_size = lz_get_dict_size(header[5]); 701 if (dict_size == 0) 702 return -1; 703 704 return lz_decode(fin, fout, dict_size, bytes_in, pre, prelen); 705 } 706
Indexes created Sun Oct 25 00:26:45 UTC 2026