author  Ryan C. Gordon <icculus@icculus.org> 
Sun, 07 Dec 2003 05:29:20 +0000  
changeset 602  691c1eadb8b7 
permissions  rwrr 
602
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

1 
/* inftrees.c  generate Huffman trees for efficient decoding 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

2 
* Copyright (C) 19952003 Mark Adler 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

3 
* For conditions of distribution and use, see copyright notice in zlib.h 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

4 
*/ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

5 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

6 
#include "zutil.h" 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

7 
#include "inftrees.h" 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

8 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

9 
#define MAXBITS 15 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

10 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

11 
const char inflate_copyright[] = 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

12 
" inflate 1.2.1 Copyright 19952003 Mark Adler "; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

13 
/* 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

14 
If you use the zlib library in a product, an acknowledgment is welcome 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

15 
in the documentation of your product. If for some reason you cannot 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

16 
include such an acknowledgment, I would appreciate that you keep this 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

17 
copyright string in the executable of your product. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

18 
*/ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

19 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

20 
/* 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

21 
Build a set of tables to decode the provided canonical Huffman code. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

22 
The code lengths are lens[0..codes1]. The result starts at *table, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

23 
whose indices are 0..2^bits1. work is a writable array of at least 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

24 
lens shorts, which is used as a work area. type is the type of code 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

25 
to be generated, CODES, LENS, or DISTS. On return, zero is success, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

26 
1 is an invalid code, and +1 means that ENOUGH isn't enough. table 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

27 
on return points to the next available entry's address. bits is the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

28 
requested root table index bits, and on return it is the actual root 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

29 
table index bits. It will differ if the request is greater than the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

30 
longest code or if it is less than the shortest code. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

31 
*/ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

32 
int inflate_table(type, lens, codes, table, bits, work) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

33 
codetype type; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

34 
unsigned short FAR *lens; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

35 
unsigned codes; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

36 
code FAR * FAR *table; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

37 
unsigned FAR *bits; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

38 
unsigned short FAR *work; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

39 
{ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

40 
unsigned len; /* a code's length in bits */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

41 
unsigned sym; /* index of code symbols */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

42 
unsigned min, max; /* minimum and maximum code lengths */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

43 
unsigned root; /* number of index bits for root table */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

44 
unsigned curr; /* number of index bits for current table */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

45 
unsigned drop; /* code bits to drop for subtable */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

46 
int left; /* number of prefix codes available */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

47 
unsigned used; /* code entries in table used */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

48 
unsigned huff; /* Huffman code */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

49 
unsigned incr; /* for incrementing code, index */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

50 
unsigned fill; /* index for replicating entries */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

51 
unsigned low; /* low bits for current root entry */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

52 
unsigned mask; /* mask for low root bits */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

53 
code this; /* table entry for duplication */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

54 
code FAR *next; /* next available space in table */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

55 
const unsigned short FAR *base; /* base value table to use */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

56 
const unsigned short FAR *extra; /* extra bits table to use */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

57 
int end; /* use base and extra for symbol > end */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

58 
unsigned short count[MAXBITS+1]; /* number of codes of each length */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

59 
unsigned short offs[MAXBITS+1]; /* offsets in table for each length */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

60 
static const unsigned short lbase[31] = { /* Length codes 257..285 base */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

61 
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

62 
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

63 
static const unsigned short lext[31] = { /* Length codes 257..285 extra */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

64 
16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

65 
19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 76, 66}; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

66 
static const unsigned short dbase[32] = { /* Distance codes 0..29 base */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

67 
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

68 
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

69 
8193, 12289, 16385, 24577, 0, 0}; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

70 
static const unsigned short dext[32] = { /* Distance codes 0..29 extra */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

71 
16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

72 
23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

73 
28, 28, 29, 29, 64, 64}; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

74 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

75 
/* 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

76 
Process a set of code lengths to create a canonical Huffman code. The 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

77 
code lengths are lens[0..codes1]. Each length corresponds to the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

78 
symbols 0..codes1. The Huffman code is generated by first sorting the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

79 
symbols by length from short to long, and retaining the symbol order 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

80 
for codes with equal lengths. Then the code starts with all zero bits 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

81 
for the first code of the shortest length, and the codes are integer 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

82 
increments for the same length, and zeros are appended as the length 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

83 
increases. For the deflate format, these bits are stored backwards 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

84 
from their more natural integer increment ordering, and so when the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

85 
decoding tables are built in the large loop below, the integer codes 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

86 
are incremented backwards. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

87 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

88 
This routine assumes, but does not check, that all of the entries in 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

89 
lens[] are in the range 0..MAXBITS. The caller must assure this. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

90 
1..MAXBITS is interpreted as that code length. zero means that that 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

91 
symbol does not occur in this code. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

92 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

93 
The codes are sorted by computing a count of codes for each length, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

94 
creating from that a table of starting indices for each length in the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

95 
sorted table, and then entering the symbols in order in the sorted 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

96 
table. The sorted table is work[], with that space being provided by 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

97 
the caller. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

98 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

99 
The length counts are used for other purposes as well, i.e. finding 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

100 
the minimum and maximum length codes, determining if there are any 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

101 
codes at all, checking for a valid set of lengths, and looking ahead 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

102 
at length counts to determine subtable sizes when building the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

103 
decoding tables. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

104 
*/ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

105 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

106 
/* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

107 
for (len = 0; len <= MAXBITS; len++) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

108 
count[len] = 0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

109 
for (sym = 0; sym < codes; sym++) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

110 
count[lens[sym]]++; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

111 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

112 
/* bound code lengths, force root to be within code lengths */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

113 
root = *bits; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

114 
for (max = MAXBITS; max >= 1; max) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

115 
if (count[max] != 0) break; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

116 
if (root > max) root = max; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

117 
if (max == 0) return 1; /* no codes! */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

118 
for (min = 1; min <= MAXBITS; min++) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

119 
if (count[min] != 0) break; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

120 
if (root < min) root = min; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

121 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

122 
/* check for an oversubscribed or incomplete set of lengths */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

123 
left = 1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

124 
for (len = 1; len <= MAXBITS; len++) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

125 
left <<= 1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

126 
left = count[len]; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

127 
if (left < 0) return 1; /* oversubscribed */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

128 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

129 
if (left > 0 && (type == CODES  (codes  count[0] != 1))) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

130 
return 1; /* incomplete set */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

131 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

132 
/* generate offsets into symbol table for each length for sorting */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

133 
offs[1] = 0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

134 
for (len = 1; len < MAXBITS; len++) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

135 
offs[len + 1] = offs[len] + count[len]; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

136 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

137 
/* sort symbols by length, by symbol order within each length */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

138 
for (sym = 0; sym < codes; sym++) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

139 
if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

140 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

141 
/* 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

142 
Create and fill in decoding tables. In this loop, the table being 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

143 
filled is at next and has curr index bits. The code being used is huff 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

144 
with length len. That code is converted to an index by dropping drop 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

145 
bits off of the bottom. For codes where len is less than drop + curr, 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

146 
those top drop + curr  len bits are incremented through all values to 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

147 
fill the table with replicated entries. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

148 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

149 
root is the number of index bits for the root table. When len exceeds 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

150 
root, subtables are created pointed to by the root entry with an index 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

151 
of the low root bits of huff. This is saved in low to check for when a 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

152 
new subtable should be started. drop is zero when the root table is 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

153 
being filled, and drop is root when subtables are being filled. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

154 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

155 
When a new subtable is needed, it is necessary to look ahead in the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

156 
code lengths to determine what size subtable is needed. The length 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

157 
counts are used for this, and so count[] is decremented as codes are 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

158 
entered in the tables. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

159 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

160 
used keeps track of how many table entries have been allocated from the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

161 
provided *table space. It is checked when a LENS table is being made 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

162 
against the space in *table, ENOUGH, minus the maximum space needed by 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

163 
the worst case distance code, MAXD. This should never happen, but the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

164 
sufficiency of ENOUGH has not been proven exhaustively, hence the check. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

165 
This assumes that when type == LENS, bits == 9. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

166 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

167 
sym increments through all symbols, and the loop terminates when 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

168 
all codes of length max, i.e. all codes, have been processed. This 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

169 
routine permits incomplete codes, so another loop after this one fills 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

170 
in the rest of the decoding tables with invalid code markers. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

171 
*/ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

172 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

173 
/* set up for code type */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

174 
switch (type) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

175 
case CODES: 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

176 
base = extra = work; /* dummy valuenot used */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

177 
end = 19; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

178 
break; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

179 
case LENS: 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

180 
base = lbase; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

181 
base = 257; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

182 
extra = lext; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

183 
extra = 257; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

184 
end = 256; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

185 
break; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

186 
default: /* DISTS */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

187 
base = dbase; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

188 
extra = dext; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

189 
end = 1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

190 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

191 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

192 
/* initialize state for loop */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

193 
huff = 0; /* starting code */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

194 
sym = 0; /* starting code symbol */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

195 
len = min; /* starting code length */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

196 
next = *table; /* current table to fill in */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

197 
curr = root; /* current table index bits */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

198 
drop = 0; /* current bits to drop from code for index */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

199 
low = (unsigned)(1); /* trigger new subtable when len > root */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

200 
used = 1U << root; /* use root table entries */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

201 
mask = used  1; /* mask for comparing low */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

202 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

203 
/* check available table space */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

204 
if (type == LENS && used >= ENOUGH  MAXD) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

205 
return 1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

206 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

207 
/* process all codes and make table entries */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

208 
for (;;) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

209 
/* create table entry */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

210 
this.bits = (unsigned char)(len  drop); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

211 
if ((int)(work[sym]) < end) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

212 
this.op = (unsigned char)0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

213 
this.val = work[sym]; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

214 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

215 
else if ((int)(work[sym]) > end) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

216 
this.op = (unsigned char)(extra[work[sym]]); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

217 
this.val = base[work[sym]]; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

218 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

219 
else { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

220 
this.op = (unsigned char)(32 + 64); /* end of block */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

221 
this.val = 0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

222 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

223 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

224 
/* replicate for those indices with low len bits equal to huff */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

225 
incr = 1U << (len  drop); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

226 
fill = 1U << curr; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

227 
do { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

228 
fill = incr; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

229 
next[(huff >> drop) + fill] = this; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

230 
} while (fill != 0); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

231 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

232 
/* backwards increment the lenbit code huff */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

233 
incr = 1U << (len  1); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

234 
while (huff & incr) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

235 
incr >>= 1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

236 
if (incr != 0) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

237 
huff &= incr  1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

238 
huff += incr; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

239 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

240 
else 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

241 
huff = 0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

242 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

243 
/* go to next symbol, update count, len */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

244 
sym++; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

245 
if ((count[len]) == 0) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

246 
if (len == max) break; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

247 
len = lens[work[sym]]; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

248 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

249 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

250 
/* create new subtable if needed */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

251 
if (len > root && (huff & mask) != low) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

252 
/* if first time, transition to subtables */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

253 
if (drop == 0) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

254 
drop = root; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

255 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

256 
/* increment past last table */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

257 
next += 1U << curr; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

258 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

259 
/* determine length of next table */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

260 
curr = len  drop; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

261 
left = (int)(1 << curr); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

262 
while (curr + drop < max) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

263 
left = count[curr + drop]; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

264 
if (left <= 0) break; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

265 
curr++; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

266 
left <<= 1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

267 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

268 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

269 
/* check for enough space */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

270 
used += 1U << curr; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

271 
if (type == LENS && used >= ENOUGH  MAXD) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

272 
return 1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

273 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

274 
/* point entry in root table to subtable */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

275 
low = huff & mask; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

276 
(*table)[low].op = (unsigned char)curr; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

277 
(*table)[low].bits = (unsigned char)root; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

278 
(*table)[low].val = (unsigned short)(next  *table); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

279 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

280 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

281 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

282 
/* 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

283 
Fill in rest of table for incomplete codes. This loop is similar to the 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

284 
loop above in incrementing huff for table indices. It is assumed that 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

285 
len is equal to curr + drop, so there is no loop needed to increment 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

286 
through high index bits. When the current subtable is filled, the loop 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

287 
drops back to the root table to fill in any remaining entries there. 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

288 
*/ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

289 
this.op = (unsigned char)64; /* invalid code marker */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

290 
this.bits = (unsigned char)(len  drop); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

291 
this.val = (unsigned short)0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

292 
while (huff != 0) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

293 
/* when done with subtable, drop back to root table */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

294 
if (drop != 0 && (huff & mask) != low) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

295 
drop = 0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

296 
len = root; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

297 
next = *table; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

298 
curr = root; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

299 
this.bits = (unsigned char)len; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

300 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

301 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

302 
/* put invalid code marker in table */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

303 
next[huff >> drop] = this; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

304 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

305 
/* backwards increment the lenbit code huff */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

306 
incr = 1U << (len  1); 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

307 
while (huff & incr) 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

308 
incr >>= 1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

309 
if (incr != 0) { 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

310 
huff &= incr  1; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

311 
huff += incr; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

312 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

313 
else 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

314 
huff = 0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

315 
} 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

316 

691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

317 
/* set return parameters */ 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

318 
*table += used; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

319 
*bits = root; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

320 
return 0; 
691c1eadb8b7
Upgraded internal zlib to 1.2.1 (thanks, Adam!)
Ryan C. Gordon <icculus@icculus.org>
parents:
diff
changeset

321 
} 