18b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* inftrees.c -- generate Huffman trees for efficient decoding 217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner * Copyright (C) 1995-2013 Mark Adler 38b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 48b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 58b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 68b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "zutil.h" 78b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "inftrees.h" 88b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 98b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define MAXBITS 15 108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectconst char inflate_copyright[] = 1217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner " inflate 1.2.8 Copyright 1995-2013 Mark Adler "; 138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* 148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project If you use the zlib library in a product, an acknowledgment is welcome 158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project in the documentation of your product. If for some reason you cannot 168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project include such an acknowledgment, I would appreciate that you keep this 178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project copyright string in the executable of your product. 188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* 218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Build a set of tables to decode the provided canonical Huffman code. 228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project The code lengths are lens[0..codes-1]. The result starts at *table, 238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project whose indices are 0..2^bits-1. work is a writable array of at least 248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project lens shorts, which is used as a work area. type is the type of code 258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project to be generated, CODES, LENS, or DISTS. On return, zero is success, 268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project -1 is an invalid code, and +1 means that ENOUGH isn't enough. table 278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project on return points to the next available entry's address. bits is the 288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project requested root table index bits, and on return it is the actual root 298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project table index bits. It will differ if the request is greater than the 308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project longest code or if it is less than the shortest code. 318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 3217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turnerint ZLIB_INTERNAL inflate_table(type, lens, codes, table, bits, work) 338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectcodetype type; 348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectunsigned short FAR *lens; 358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectunsigned codes; 368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectcode FAR * FAR *table; 378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectunsigned FAR *bits; 388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectunsigned short FAR *work; 398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned len; /* a code's length in bits */ 418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned sym; /* index of code symbols */ 428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned min, max; /* minimum and maximum code lengths */ 438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned root; /* number of index bits for root table */ 448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned curr; /* number of index bits for current table */ 458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned drop; /* code bits to drop for sub-table */ 468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int left; /* number of prefix codes available */ 478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned used; /* code entries in table used */ 488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned huff; /* Huffman code */ 498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned incr; /* for incrementing code, index */ 508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned fill; /* index for replicating entries */ 518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned low; /* low bits for current root entry */ 528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned mask; /* mask for low root bits */ 5317b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner code here; /* table entry for duplication */ 548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code FAR *next; /* next available space in table */ 558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project const unsigned short FAR *base; /* base value table to use */ 568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project const unsigned short FAR *extra; /* extra bits table to use */ 578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int end; /* use base and extra for symbol > end */ 588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned short count[MAXBITS+1]; /* number of codes of each length */ 598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned short offs[MAXBITS+1]; /* offsets in table for each length */ 608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project static const unsigned short lbase[31] = { /* Length codes 257..285 base */ 618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project static const unsigned short lext[31] = { /* Length codes 257..285 extra */ 648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 6517b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 72, 78}; 668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project static const unsigned short dbase[32] = { /* Distance codes 0..29 base */ 678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 8193, 12289, 16385, 24577, 0, 0}; 708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project static const unsigned short dext[32] = { /* Distance codes 0..29 extra */ 718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 28, 28, 29, 29, 64, 64}; 748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* 768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Process a set of code lengths to create a canonical Huffman code. The 778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code lengths are lens[0..codes-1]. Each length corresponds to the 788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project symbols 0..codes-1. The Huffman code is generated by first sorting the 798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project symbols by length from short to long, and retaining the symbol order 808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for codes with equal lengths. Then the code starts with all zero bits 818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for the first code of the shortest length, and the codes are integer 828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project increments for the same length, and zeros are appended as the length 838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project increases. For the deflate format, these bits are stored backwards 848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project from their more natural integer increment ordering, and so when the 858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project decoding tables are built in the large loop below, the integer codes 868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project are incremented backwards. 878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project This routine assumes, but does not check, that all of the entries in 898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project lens[] are in the range 0..MAXBITS. The caller must assure this. 908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1..MAXBITS is interpreted as that code length. zero means that that 918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project symbol does not occur in this code. 928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project The codes are sorted by computing a count of codes for each length, 948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project creating from that a table of starting indices for each length in the 958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project sorted table, and then entering the symbols in order in the sorted 968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project table. The sorted table is work[], with that space being provided by 978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project the caller. 988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project The length counts are used for other purposes as well, i.e. finding 1008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project the minimum and maximum length codes, determining if there are any 1018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project codes at all, checking for a valid set of lengths, and looking ahead 1028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project at length counts to determine sub-table sizes when building the 1038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project decoding tables. 1048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 1058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */ 1078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (len = 0; len <= MAXBITS; len++) 1088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project count[len] = 0; 1098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (sym = 0; sym < codes; sym++) 1108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project count[lens[sym]]++; 1118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* bound code lengths, force root to be within code lengths */ 1138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project root = *bits; 1148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (max = MAXBITS; max >= 1; max--) 1158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (count[max] != 0) break; 1168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (root > max) root = max; 1178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (max == 0) { /* no symbols to code at all */ 11817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.op = (unsigned char)64; /* invalid code marker */ 11917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.bits = (unsigned char)1; 12017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.val = (unsigned short)0; 12117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner *(*table)++ = here; /* make a table to force an error */ 12217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner *(*table)++ = here; 1238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project *bits = 1; 1248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return 0; /* no symbols, but wait for decoding to report error */ 1258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 12617b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner for (min = 1; min < max; min++) 1278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (count[min] != 0) break; 1288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (root < min) root = min; 1298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* check for an over-subscribed or incomplete set of lengths */ 1318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project left = 1; 1328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (len = 1; len <= MAXBITS; len++) { 1338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project left <<= 1; 1348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project left -= count[len]; 1358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (left < 0) return -1; /* over-subscribed */ 1368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (left > 0 && (type == CODES || max != 1)) 1388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return -1; /* incomplete set */ 1398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* generate offsets into symbol table for each length for sorting */ 1418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project offs[1] = 0; 1428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (len = 1; len < MAXBITS; len++) 1438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project offs[len + 1] = offs[len] + count[len]; 1448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* sort symbols by length, by symbol order within each length */ 1468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (sym = 0; sym < codes; sym++) 1478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym; 1488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* 1508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Create and fill in decoding tables. In this loop, the table being 1518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project filled is at next and has curr index bits. The code being used is huff 1528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project with length len. That code is converted to an index by dropping drop 1538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits off of the bottom. For codes where len is less than drop + curr, 1548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project those top drop + curr - len bits are incremented through all values to 1558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fill the table with replicated entries. 1568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project root is the number of index bits for the root table. When len exceeds 1588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project root, sub-tables are created pointed to by the root entry with an index 1598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project of the low root bits of huff. This is saved in low to check for when a 1608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project new sub-table should be started. drop is zero when the root table is 1618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project being filled, and drop is root when sub-tables are being filled. 1628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project When a new sub-table is needed, it is necessary to look ahead in the 1648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code lengths to determine what size sub-table is needed. The length 1658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project counts are used for this, and so count[] is decremented as codes are 1668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project entered in the tables. 1678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project used keeps track of how many table entries have been allocated from the 16917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner provided *table space. It is checked for LENS and DIST tables against 17017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in 17117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner the initial root table size constants. See the comments in inftrees.h 17217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner for more information. 1738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project sym increments through all symbols, and the loop terminates when 1758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project all codes of length max, i.e. all codes, have been processed. This 1768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project routine permits incomplete codes, so another loop after this one fills 1778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project in the rest of the decoding tables with invalid code markers. 1788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 1798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* set up for code type */ 1818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project switch (type) { 1828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project case CODES: 1838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project base = extra = work; /* dummy value--not used */ 1848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project end = 19; 1858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project break; 1868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project case LENS: 1878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project base = lbase; 1888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project base -= 257; 1898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project extra = lext; 1908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project extra -= 257; 1918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project end = 256; 1928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project break; 1938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project default: /* DISTS */ 1948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project base = dbase; 1958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project extra = dext; 1968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project end = -1; 1978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* initialize state for loop */ 2008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project huff = 0; /* starting code */ 2018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project sym = 0; /* starting code symbol */ 2028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len = min; /* starting code length */ 2038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project next = *table; /* current table to fill in */ 2048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project curr = root; /* current table index bits */ 2058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project drop = 0; /* current bits to drop from code for index */ 2068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project low = (unsigned)(-1); /* trigger new sub-table when len > root */ 2078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project used = 1U << root; /* use root table entries */ 2088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project mask = used - 1; /* mask for comparing low */ 2098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* check available table space */ 21117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner if ((type == LENS && used > ENOUGH_LENS) || 21217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner (type == DISTS && used > ENOUGH_DISTS)) 2138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return 1; 2148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* process all codes and make table entries */ 2168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (;;) { 2178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* create table entry */ 21817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.bits = (unsigned char)(len - drop); 2198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if ((int)(work[sym]) < end) { 22017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.op = (unsigned char)0; 22117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.val = work[sym]; 2228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else if ((int)(work[sym]) > end) { 22417b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.op = (unsigned char)(extra[work[sym]]); 22517b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.val = base[work[sym]]; 2268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else { 22817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.op = (unsigned char)(32 + 64); /* end of block */ 22917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.val = 0; 2308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* replicate for those indices with low len bits equal to huff */ 2338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project incr = 1U << (len - drop); 2348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fill = 1U << curr; 2358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project min = fill; /* save offset to next table */ 2368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project do { 2378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fill -= incr; 23817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner next[(huff >> drop) + fill] = here; 2398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (fill != 0); 2408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* backwards increment the len-bit code huff */ 2428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project incr = 1U << (len - 1); 2438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (huff & incr) 2448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project incr >>= 1; 2458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (incr != 0) { 2468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project huff &= incr - 1; 2478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project huff += incr; 2488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else 2508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project huff = 0; 2518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* go to next symbol, update count, len */ 2538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project sym++; 2548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (--(count[len]) == 0) { 2558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len == max) break; 2568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len = lens[work[sym]]; 2578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* create new sub-table if needed */ 2608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len > root && (huff & mask) != low) { 2618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* if first time, transition to sub-tables */ 2628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (drop == 0) 2638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project drop = root; 2648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* increment past last table */ 2668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project next += min; /* here min is 1 << curr */ 2678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* determine length of next table */ 2698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project curr = len - drop; 2708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project left = (int)(1 << curr); 2718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (curr + drop < max) { 2728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project left -= count[curr + drop]; 2738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (left <= 0) break; 2748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project curr++; 2758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project left <<= 1; 2768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* check for enough space */ 2798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project used += 1U << curr; 28017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner if ((type == LENS && used > ENOUGH_LENS) || 28117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner (type == DISTS && used > ENOUGH_DISTS)) 2828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return 1; 2838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* point entry in root table to sub-table */ 2858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project low = huff & mask; 2868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project (*table)[low].op = (unsigned char)curr; 2878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project (*table)[low].bits = (unsigned char)root; 2888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project (*table)[low].val = (unsigned short)(next - *table); 2898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 29217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner /* fill in remaining table entry if code is incomplete (guaranteed to have 29317b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner at most one remaining entry, since if the code is incomplete, the 29417b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner maximum code length that was allowed to get this far is one bit) */ 29517b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner if (huff != 0) { 29617b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.op = (unsigned char)64; /* invalid code marker */ 29717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.bits = (unsigned char)(len - drop); 29817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here.val = (unsigned short)0; 29917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner next[huff] = here; 3008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 3018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* set return parameters */ 3038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project *table += used; 3048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project *bits = root; 3058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return 0; 3068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 307