inftrees.c (muscle7.61) | : | inftrees.c (muscle7.62) | ||
---|---|---|---|---|

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

* Copyright (C) 1995-2013 Mark Adler | * Copyright (C) 1995-2017 Mark Adler | |||

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

*/ | */ | |||

#include "zutil.h" | #include "zutil.h" | |||

#include "inftrees.h" | #include "inftrees.h" | |||

#define MAXBITS 15 | #define MAXBITS 15 | |||

const char inflate_copyright[] = | const char inflate_copyright[] = | |||

" inflate 1.2.8 Copyright 1995-2013 Mark Adler "; | " inflate 1.2.11 Copyright 1995-2017 Mark Adler "; | |||

/* | /* | |||

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

in the documentation of your product. If for some reason you cannot | in the documentation of your product. If for some reason you cannot | |||

include such an acknowledgment, I would appreciate that you keep this | include such an acknowledgment, I would appreciate that you keep this | |||

copyright string in the executable of your product. | copyright string in the executable of your product. | |||

*/ | */ | |||

/* | /* | |||

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

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

skipping to change at line 57 | skipping to change at line 57 | |||

unsigned used; /* code entries in table used */ | unsigned used; /* code entries in table used */ | |||

unsigned huff; /* Huffman code */ | unsigned huff; /* Huffman code */ | |||

unsigned incr; /* for incrementing code, index */ | unsigned incr; /* for incrementing code, index */ | |||

unsigned fill; /* index for replicating entries */ | unsigned fill; /* index for replicating entries */ | |||

unsigned low; /* low bits for current root entry */ | unsigned low; /* low bits for current root entry */ | |||

unsigned mask; /* mask for low root bits */ | unsigned mask; /* mask for low root bits */ | |||

code here; /* table entry for duplication */ | code here; /* table entry for duplication */ | |||

code FAR *next; /* next available space in table */ | code FAR *next; /* next available space in table */ | |||

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

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

int end; /* use base and extra for symbol > end */ | unsigned match; /* use base and extra for symbol >= match */ | |||

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

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

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

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

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

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

16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, | 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, | |||

19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 72, 78}; | 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 77, 202}; | |||

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

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

257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, | 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, | |||

8193, 12289, 16385, 24577, 0, 0}; | 8193, 12289, 16385, 24577, 0, 0}; | |||

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

16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, | 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, | |||

23, 23, 24, 24, 25, 25, 26, 26, 27, 27, | 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, | |||

28, 28, 29, 29, 64, 64}; | 28, 28, 29, 29, 64, 64}; | |||

/* | /* | |||

skipping to change at line 184 | skipping to change at line 184 | |||

sym increments through all symbols, and the loop terminates when | sym increments through all symbols, and the loop terminates when | |||

all codes of length max, i.e. all codes, have been processed. This | all codes of length max, i.e. all codes, have been processed. This | |||

routine permits incomplete codes, so another loop after this one fills | routine permits incomplete codes, so another loop after this one fills | |||

in the rest of the decoding tables with invalid code markers. | in the rest of the decoding tables with invalid code markers. | |||

*/ | */ | |||

/* set up for code type */ | /* set up for code type */ | |||

switch (type) { | switch (type) { | |||

case CODES: | case CODES: | |||

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

end = 19; | match = 20; | |||

break; | break; | |||

case LENS: | case LENS: | |||

base = lbase; | base = lbase; | |||

base -= 257; | ||||

extra = lext; | extra = lext; | |||

extra -= 257; | match = 257; | |||

end = 256; | ||||

break; | break; | |||

default: /* DISTS */ | default: /* DISTS */ | |||

base = dbase; | base = dbase; | |||

extra = dext; | extra = dext; | |||

end = -1; | match = 0; | |||

} | } | |||

/* initialize state for loop */ | /* initialize state for loop */ | |||

huff = 0; /* starting code */ | huff = 0; /* starting code */ | |||

sym = 0; /* starting code symbol */ | sym = 0; /* starting code symbol */ | |||

len = min; /* starting code length */ | len = min; /* starting code length */ | |||

next = *table; /* current table to fill in */ | next = *table; /* current table to fill in */ | |||

curr = root; /* current table index bits */ | curr = root; /* current table index bits */ | |||

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

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

skipping to change at line 219 | skipping to change at line 217 | |||

/* check available table space */ | /* check available table space */ | |||

if ((type == LENS && used > ENOUGH_LENS) || | if ((type == LENS && used > ENOUGH_LENS) || | |||

(type == DISTS && used > ENOUGH_DISTS)) | (type == DISTS && used > ENOUGH_DISTS)) | |||

return 1; | return 1; | |||

/* process all codes and make table entries */ | /* process all codes and make table entries */ | |||

for (;;) { | for (;;) { | |||

/* create table entry */ | /* create table entry */ | |||

here.bits = (unsigned char)(len - drop); | here.bits = (unsigned char)(len - drop); | |||

if ((int)(work[sym]) < end) { | if (work[sym] + 1U < match) { | |||

here.op = (unsigned char)0; | here.op = (unsigned char)0; | |||

here.val = work[sym]; | here.val = work[sym]; | |||

} | } | |||

else if ((int)(work[sym]) > end) { | else if (work[sym] >= match) { | |||

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

here.val = base[work[sym]]; | here.val = base[work[sym] - match]; | |||

} | } | |||

else { | else { | |||

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

here.val = 0; | here.val = 0; | |||

} | } | |||

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

incr = 1U << (len - drop); | incr = 1U << (len - drop); | |||

fill = 1U << curr; | fill = 1U << curr; | |||

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

End of changes. 11 change blocks. | ||||

14 lines changed or deleted | | 12 lines changed or added |