# Python code coverage for Modules/zlib/inftrees.c

# | count | content |
---|---|---|

1 | n/a | /* inftrees.c -- generate Huffman trees for efficient decoding |

2 | n/a | * Copyright (C) 1995-2017 Mark Adler |

3 | n/a | * For conditions of distribution and use, see copyright notice in zlib.h |

4 | n/a | */ |

5 | n/a | |

6 | n/a | #include "zutil.h" |

7 | n/a | #include "inftrees.h" |

8 | n/a | |

9 | n/a | #define MAXBITS 15 |

10 | n/a | |

11 | n/a | const char inflate_copyright[] = |

12 | n/a | " inflate 1.2.11 Copyright 1995-2017 Mark Adler "; |

13 | n/a | /* |

14 | n/a | If you use the zlib library in a product, an acknowledgment is welcome |

15 | n/a | in the documentation of your product. If for some reason you cannot |

16 | n/a | include such an acknowledgment, I would appreciate that you keep this |

17 | n/a | copyright string in the executable of your product. |

18 | n/a | */ |

19 | n/a | |

20 | n/a | /* |

21 | n/a | Build a set of tables to decode the provided canonical Huffman code. |

22 | n/a | The code lengths are lens[0..codes-1]. The result starts at *table, |

23 | n/a | whose indices are 0..2^bits-1. work is a writable array of at least |

24 | n/a | lens shorts, which is used as a work area. type is the type of code |

25 | n/a | to be generated, CODES, LENS, or DISTS. On return, zero is success, |

26 | n/a | -1 is an invalid code, and +1 means that ENOUGH isn't enough. table |

27 | n/a | on return points to the next available entry's address. bits is the |

28 | n/a | requested root table index bits, and on return it is the actual root |

29 | n/a | table index bits. It will differ if the request is greater than the |

30 | n/a | longest code or if it is less than the shortest code. |

31 | n/a | */ |

32 | n/a | int ZLIB_INTERNAL inflate_table(type, lens, codes, table, bits, work) |

33 | n/a | codetype type; |

34 | n/a | unsigned short FAR *lens; |

35 | n/a | unsigned codes; |

36 | n/a | code FAR * FAR *table; |

37 | n/a | unsigned FAR *bits; |

38 | n/a | unsigned short FAR *work; |

39 | n/a | { |

40 | n/a | unsigned len; /* a code's length in bits */ |

41 | n/a | unsigned sym; /* index of code symbols */ |

42 | n/a | unsigned min, max; /* minimum and maximum code lengths */ |

43 | n/a | unsigned root; /* number of index bits for root table */ |

44 | n/a | unsigned curr; /* number of index bits for current table */ |

45 | n/a | unsigned drop; /* code bits to drop for sub-table */ |

46 | n/a | int left; /* number of prefix codes available */ |

47 | n/a | unsigned used; /* code entries in table used */ |

48 | n/a | unsigned huff; /* Huffman code */ |

49 | n/a | unsigned incr; /* for incrementing code, index */ |

50 | n/a | unsigned fill; /* index for replicating entries */ |

51 | n/a | unsigned low; /* low bits for current root entry */ |

52 | n/a | unsigned mask; /* mask for low root bits */ |

53 | n/a | code here; /* table entry for duplication */ |

54 | n/a | code FAR *next; /* next available space in table */ |

55 | n/a | const unsigned short FAR *base; /* base value table to use */ |

56 | n/a | const unsigned short FAR *extra; /* extra bits table to use */ |

57 | n/a | unsigned match; /* use base and extra for symbol >= match */ |

58 | n/a | unsigned short count[MAXBITS+1]; /* number of codes of each length */ |

59 | n/a | unsigned short offs[MAXBITS+1]; /* offsets in table for each length */ |

60 | n/a | static const unsigned short lbase[31] = { /* Length codes 257..285 base */ |

61 | n/a | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, |

62 | n/a | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; |

63 | n/a | static const unsigned short lext[31] = { /* Length codes 257..285 extra */ |

64 | n/a | 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, |

65 | n/a | 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 77, 202}; |

66 | n/a | static const unsigned short dbase[32] = { /* Distance codes 0..29 base */ |

67 | n/a | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, |

68 | n/a | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, |

69 | n/a | 8193, 12289, 16385, 24577, 0, 0}; |

70 | n/a | static const unsigned short dext[32] = { /* Distance codes 0..29 extra */ |

71 | n/a | 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, |

72 | n/a | 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, |

73 | n/a | 28, 28, 29, 29, 64, 64}; |

74 | n/a | |

75 | n/a | /* |

76 | n/a | Process a set of code lengths to create a canonical Huffman code. The |

77 | n/a | code lengths are lens[0..codes-1]. Each length corresponds to the |

78 | n/a | symbols 0..codes-1. The Huffman code is generated by first sorting the |

79 | n/a | symbols by length from short to long, and retaining the symbol order |

80 | n/a | for codes with equal lengths. Then the code starts with all zero bits |

81 | n/a | for the first code of the shortest length, and the codes are integer |

82 | n/a | increments for the same length, and zeros are appended as the length |

83 | n/a | increases. For the deflate format, these bits are stored backwards |

84 | n/a | from their more natural integer increment ordering, and so when the |

85 | n/a | decoding tables are built in the large loop below, the integer codes |

86 | n/a | are incremented backwards. |

87 | n/a | |

88 | n/a | This routine assumes, but does not check, that all of the entries in |

89 | n/a | lens[] are in the range 0..MAXBITS. The caller must assure this. |

90 | n/a | 1..MAXBITS is interpreted as that code length. zero means that that |

91 | n/a | symbol does not occur in this code. |

92 | n/a | |

93 | n/a | The codes are sorted by computing a count of codes for each length, |

94 | n/a | creating from that a table of starting indices for each length in the |

95 | n/a | sorted table, and then entering the symbols in order in the sorted |

96 | n/a | table. The sorted table is work[], with that space being provided by |

97 | n/a | the caller. |

98 | n/a | |

99 | n/a | The length counts are used for other purposes as well, i.e. finding |

100 | n/a | the minimum and maximum length codes, determining if there are any |

101 | n/a | codes at all, checking for a valid set of lengths, and looking ahead |

102 | n/a | at length counts to determine sub-table sizes when building the |

103 | n/a | decoding tables. |

104 | n/a | */ |

105 | n/a | |

106 | n/a | /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */ |

107 | n/a | for (len = 0; len <= MAXBITS; len++) |

108 | n/a | count[len] = 0; |

109 | n/a | for (sym = 0; sym < codes; sym++) |

110 | n/a | count[lens[sym]]++; |

111 | n/a | |

112 | n/a | /* bound code lengths, force root to be within code lengths */ |

113 | n/a | root = *bits; |

114 | n/a | for (max = MAXBITS; max >= 1; max--) |

115 | n/a | if (count[max] != 0) break; |

116 | n/a | if (root > max) root = max; |

117 | n/a | if (max == 0) { /* no symbols to code at all */ |

118 | n/a | here.op = (unsigned char)64; /* invalid code marker */ |

119 | n/a | here.bits = (unsigned char)1; |

120 | n/a | here.val = (unsigned short)0; |

121 | n/a | *(*table)++ = here; /* make a table to force an error */ |

122 | n/a | *(*table)++ = here; |

123 | n/a | *bits = 1; |

124 | n/a | return 0; /* no symbols, but wait for decoding to report error */ |

125 | n/a | } |

126 | n/a | for (min = 1; min < max; min++) |

127 | n/a | if (count[min] != 0) break; |

128 | n/a | if (root < min) root = min; |

129 | n/a | |

130 | n/a | /* check for an over-subscribed or incomplete set of lengths */ |

131 | n/a | left = 1; |

132 | n/a | for (len = 1; len <= MAXBITS; len++) { |

133 | n/a | left <<= 1; |

134 | n/a | left -= count[len]; |

135 | n/a | if (left < 0) return -1; /* over-subscribed */ |

136 | n/a | } |

137 | n/a | if (left > 0 && (type == CODES || max != 1)) |

138 | n/a | return -1; /* incomplete set */ |

139 | n/a | |

140 | n/a | /* generate offsets into symbol table for each length for sorting */ |

141 | n/a | offs[1] = 0; |

142 | n/a | for (len = 1; len < MAXBITS; len++) |

143 | n/a | offs[len + 1] = offs[len] + count[len]; |

144 | n/a | |

145 | n/a | /* sort symbols by length, by symbol order within each length */ |

146 | n/a | for (sym = 0; sym < codes; sym++) |

147 | n/a | if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym; |

148 | n/a | |

149 | n/a | /* |

150 | n/a | Create and fill in decoding tables. In this loop, the table being |

151 | n/a | filled is at next and has curr index bits. The code being used is huff |

152 | n/a | with length len. That code is converted to an index by dropping drop |

153 | n/a | bits off of the bottom. For codes where len is less than drop + curr, |

154 | n/a | those top drop + curr - len bits are incremented through all values to |

155 | n/a | fill the table with replicated entries. |

156 | n/a | |

157 | n/a | root is the number of index bits for the root table. When len exceeds |

158 | n/a | root, sub-tables are created pointed to by the root entry with an index |

159 | n/a | of the low root bits of huff. This is saved in low to check for when a |

160 | n/a | new sub-table should be started. drop is zero when the root table is |

161 | n/a | being filled, and drop is root when sub-tables are being filled. |

162 | n/a | |

163 | n/a | When a new sub-table is needed, it is necessary to look ahead in the |

164 | n/a | code lengths to determine what size sub-table is needed. The length |

165 | n/a | counts are used for this, and so count[] is decremented as codes are |

166 | n/a | entered in the tables. |

167 | n/a | |

168 | n/a | used keeps track of how many table entries have been allocated from the |

169 | n/a | provided *table space. It is checked for LENS and DIST tables against |

170 | n/a | the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in |

171 | n/a | the initial root table size constants. See the comments in inftrees.h |

172 | n/a | for more information. |

173 | n/a | |

174 | n/a | sym increments through all symbols, and the loop terminates when |

175 | n/a | all codes of length max, i.e. all codes, have been processed. This |

176 | n/a | routine permits incomplete codes, so another loop after this one fills |

177 | n/a | in the rest of the decoding tables with invalid code markers. |

178 | n/a | */ |

179 | n/a | |

180 | n/a | /* set up for code type */ |

181 | n/a | switch (type) { |

182 | n/a | case CODES: |

183 | n/a | base = extra = work; /* dummy value--not used */ |

184 | n/a | match = 20; |

185 | n/a | break; |

186 | n/a | case LENS: |

187 | n/a | base = lbase; |

188 | n/a | extra = lext; |

189 | n/a | match = 257; |

190 | n/a | break; |

191 | n/a | default: /* DISTS */ |

192 | n/a | base = dbase; |

193 | n/a | extra = dext; |

194 | n/a | match = 0; |

195 | n/a | } |

196 | n/a | |

197 | n/a | /* initialize state for loop */ |

198 | n/a | huff = 0; /* starting code */ |

199 | n/a | sym = 0; /* starting code symbol */ |

200 | n/a | len = min; /* starting code length */ |

201 | n/a | next = *table; /* current table to fill in */ |

202 | n/a | curr = root; /* current table index bits */ |

203 | n/a | drop = 0; /* current bits to drop from code for index */ |

204 | n/a | low = (unsigned)(-1); /* trigger new sub-table when len > root */ |

205 | n/a | used = 1U << root; /* use root table entries */ |

206 | n/a | mask = used - 1; /* mask for comparing low */ |

207 | n/a | |

208 | n/a | /* check available table space */ |

209 | n/a | if ((type == LENS && used > ENOUGH_LENS) || |

210 | n/a | (type == DISTS && used > ENOUGH_DISTS)) |

211 | n/a | return 1; |

212 | n/a | |

213 | n/a | /* process all codes and make table entries */ |

214 | n/a | for (;;) { |

215 | n/a | /* create table entry */ |

216 | n/a | here.bits = (unsigned char)(len - drop); |

217 | n/a | if (work[sym] + 1U < match) { |

218 | n/a | here.op = (unsigned char)0; |

219 | n/a | here.val = work[sym]; |

220 | n/a | } |

221 | n/a | else if (work[sym] >= match) { |

222 | n/a | here.op = (unsigned char)(extra[work[sym] - match]); |

223 | n/a | here.val = base[work[sym] - match]; |

224 | n/a | } |

225 | n/a | else { |

226 | n/a | here.op = (unsigned char)(32 + 64); /* end of block */ |

227 | n/a | here.val = 0; |

228 | n/a | } |

229 | n/a | |

230 | n/a | /* replicate for those indices with low len bits equal to huff */ |

231 | n/a | incr = 1U << (len - drop); |

232 | n/a | fill = 1U << curr; |

233 | n/a | min = fill; /* save offset to next table */ |

234 | n/a | do { |

235 | n/a | fill -= incr; |

236 | n/a | next[(huff >> drop) + fill] = here; |

237 | n/a | } while (fill != 0); |

238 | n/a | |

239 | n/a | /* backwards increment the len-bit code huff */ |

240 | n/a | incr = 1U << (len - 1); |

241 | n/a | while (huff & incr) |

242 | n/a | incr >>= 1; |

243 | n/a | if (incr != 0) { |

244 | n/a | huff &= incr - 1; |

245 | n/a | huff += incr; |

246 | n/a | } |

247 | n/a | else |

248 | n/a | huff = 0; |

249 | n/a | |

250 | n/a | /* go to next symbol, update count, len */ |

251 | n/a | sym++; |

252 | n/a | if (--(count[len]) == 0) { |

253 | n/a | if (len == max) break; |

254 | n/a | len = lens[work[sym]]; |

255 | n/a | } |

256 | n/a | |

257 | n/a | /* create new sub-table if needed */ |

258 | n/a | if (len > root && (huff & mask) != low) { |

259 | n/a | /* if first time, transition to sub-tables */ |

260 | n/a | if (drop == 0) |

261 | n/a | drop = root; |

262 | n/a | |

263 | n/a | /* increment past last table */ |

264 | n/a | next += min; /* here min is 1 << curr */ |

265 | n/a | |

266 | n/a | /* determine length of next table */ |

267 | n/a | curr = len - drop; |

268 | n/a | left = (int)(1 << curr); |

269 | n/a | while (curr + drop < max) { |

270 | n/a | left -= count[curr + drop]; |

271 | n/a | if (left <= 0) break; |

272 | n/a | curr++; |

273 | n/a | left <<= 1; |

274 | n/a | } |

275 | n/a | |

276 | n/a | /* check for enough space */ |

277 | n/a | used += 1U << curr; |

278 | n/a | if ((type == LENS && used > ENOUGH_LENS) || |

279 | n/a | (type == DISTS && used > ENOUGH_DISTS)) |

280 | n/a | return 1; |

281 | n/a | |

282 | n/a | /* point entry in root table to sub-table */ |

283 | n/a | low = huff & mask; |

284 | n/a | (*table)[low].op = (unsigned char)curr; |

285 | n/a | (*table)[low].bits = (unsigned char)root; |

286 | n/a | (*table)[low].val = (unsigned short)(next - *table); |

287 | n/a | } |

288 | n/a | } |

289 | n/a | |

290 | n/a | /* fill in remaining table entry if code is incomplete (guaranteed to have |

291 | n/a | at most one remaining entry, since if the code is incomplete, the |

292 | n/a | maximum code length that was allowed to get this far is one bit) */ |

293 | n/a | if (huff != 0) { |

294 | n/a | here.op = (unsigned char)64; /* invalid code marker */ |

295 | n/a | here.bits = (unsigned char)(len - drop); |

296 | n/a | here.val = (unsigned short)0; |

297 | n/a | next[huff] = here; |

298 | n/a | } |

299 | n/a | |

300 | n/a | /* set return parameters */ |

301 | n/a | *table += used; |

302 | n/a | *bits = root; |

303 | n/a | return 0; |

304 | n/a | } |