2
* This file contains code from zlib library v.1.2.3 with modifications
3
* by aCaB <acab@clamav.net> to allow decompression of deflate64 stereams
4
* (aka zip method 9). The implementation is heavily inspired by InfoZip
5
* and zlib's inf9back.c
7
* Full copy of the original zlib license follows:
10
/* zlib.h -- interface of the 'zlib' general purpose compression library
11
version 1.2.3, July 18th, 2005
13
Copyright (C) 1995-2005 Jean-loup Gailly and Mark Adler
15
This software is provided 'as-is', without any express or implied
16
warranty. In no event will the authors be held liable for any damages
17
arising from the use of this software.
19
Permission is granted to anyone to use this software for any purpose,
20
including commercial applications, and to alter it and redistribute it
21
freely, subject to the following restrictions:
23
1. The origin of this software must not be misrepresented; you must not
24
claim that you wrote the original software. If you use this software
25
in a product, an acknowledgment in the product documentation would be
26
appreciated but is not required.
27
2. Altered source versions must be plainly marked as such, and must not be
28
misrepresented as being the original software.
29
3. This notice may not be removed or altered from any source distribution.
31
Jean-loup Gailly Mark Adler
32
jloup@gzip.org madler@alumni.caltech.edu
35
The data format used by the zlib library is described by RFCs (Request for
36
Comments) 1950 to 1952 in the files http://www.ietf.org/rfc/rfc1950.txt
37
(zlib format), rfc1951.txt (deflate format) and rfc1952.txt (gzip format).
40
const char inflate64_copyright[] =
41
" inflate 1.2.3 Copyright 1995-2005 Mark Adler ";
43
If you use the zlib library in a product, an acknowledgment is welcome
44
in the documentation of your product. If for some reason you cannot
45
include such an acknowledgment, I would appreciate that you keep this
46
copyright string in the executable of your product.
51
#include "inflate64_priv.h"
53
#include <stdlib.h> /* calloc/free */
54
#include <string.h> /* memcpy */
58
/* function prototypes */
59
local void fixedtables OF((struct inflate_state FAR *state));
60
local int updatewindow OF((z_stream64p strm, unsigned out));
61
local int inflate_table OF((codetype type, unsigned short FAR *lens,
62
unsigned codes, code FAR * FAR *table,
63
unsigned FAR *bits, unsigned short FAR *work));
66
int ZEXPORT inflate64Init2(strm, windowBits)
70
struct inflate_state FAR *state;
72
if (strm == Z_NULL) return Z_STREAM_ERROR;
73
state = (struct inflate_state FAR *)cli_calloc(1, sizeof(struct inflate_state));
74
if (state == Z_NULL) return Z_MEM_ERROR;
75
Tracev((stderr, "inflate: allocated\n"));
76
strm->state = (struct internal_state FAR *)state;
79
windowBits = -windowBits;
82
state->wrap = (windowBits >> 4) + 1;
84
if (windowBits < 8 || windowBits > MAX_WBITS64) {
87
return Z_STREAM_ERROR;
89
state->wbits = (unsigned)windowBits;
90
state->window = Z_NULL;
91
strm->total_in = strm->total_out = state->total = 0;
92
strm->adler = 1; /* to support ill-conceived Java test suite */
102
state->lencode = state->distcode = state->next = state->codes;
103
Tracev((stderr, "inflate: reset\n"));
108
Return state with length and distance decoding tables and index sizes set to
109
fixed code decoding. Normally this returns fixed tables from inffixed.h.
110
If BUILDFIXED is defined, then instead this routine builds the tables the
111
first time it's called, and returns those tables the first time and
112
thereafter. This reduces the size of the code by about 2K bytes, in
113
exchange for a little execution time. However, BUILDFIXED should not be
114
used for threaded applications, since the rewriting of the tables and virgin
115
may not be thread-safe.
117
local void fixedtables(state)
118
struct inflate_state FAR *state;
121
static int virgin = 1;
122
static code *lenfix, *distfix;
123
static code fixed[544];
125
/* build fixed huffman tables if first call (may not be thread safe) */
130
/* literal/length table */
132
while (sym < 144) state->lens[sym++] = 8;
133
while (sym < 256) state->lens[sym++] = 9;
134
while (sym < 280) state->lens[sym++] = 7;
135
while (sym < 288) state->lens[sym++] = 8;
139
inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
143
while (sym < 32) state->lens[sym++] = 5;
146
inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
148
/* do this just once */
151
#else /* !BUILDFIXED */
152
# include "inffixed64.h"
153
#endif /* BUILDFIXED */
154
state->lencode = lenfix;
156
state->distcode = distfix;
161
Update the window with the last wsize (normally 32K) bytes written before
162
returning. If window does not exist yet, create it. This is only called
163
when a window is already in use, or when output has been written during this
164
inflate call, but the end of the deflate stream has not been reached yet.
165
It is also called to create a window for dictionary data when a dictionary
168
Providing output buffers larger than 32K to inflate() should provide a speed
169
advantage, since only the last 32K of output is copied to the sliding window
170
upon return from inflate(), and since all distances after the first 32K of
171
output will fall in the output data, making match copies simpler and faster.
172
The advantage may be dependent on the size of the processor's data caches.
174
local int updatewindow(strm, out)
178
struct inflate_state FAR *state;
181
state = (struct inflate_state FAR *)strm->state;
183
/* if it hasn't been done already, allocate space for the window */
184
if (state->window == Z_NULL) {
185
state->window = (unsigned char FAR *)cli_calloc(1U << state->wbits, sizeof(unsigned char));
186
if (state->window == Z_NULL) return 1;
189
/* if window not in use yet, initialize */
190
if (state->wsize == 0) {
191
state->wsize = 1U << state->wbits;
196
/* copy state->wsize or less output bytes into the circular window */
197
copy = out - strm->avail_out;
198
if (copy >= state->wsize) {
199
memcpy(state->window, strm->next_out - state->wsize, state->wsize);
201
state->whave = state->wsize;
204
dist = state->wsize - state->write;
205
if (dist > copy) dist = copy;
206
memcpy(state->window + state->write, strm->next_out - copy, dist);
209
memcpy(state->window, strm->next_out - copy, copy);
211
state->whave = state->wsize;
214
state->write += dist;
215
if (state->write == state->wsize) state->write = 0;
216
if (state->whave < state->wsize) state->whave += dist;
222
/* Macros for inflate(): */
224
/* check function to use adler32() for zlib or crc32() for gzip */
225
# define UPDATE(check, buf, len) adler32(check, buf, len)
227
/* Load registers with state in inflate() for speed */
230
put = strm->next_out; \
231
left = strm->avail_out; \
232
next = strm->next_in; \
233
have = strm->avail_in; \
234
hold = state->hold; \
235
bits = state->bits; \
238
/* Restore state from registers in inflate() */
241
strm->next_out = put; \
242
strm->avail_out = left; \
243
strm->next_in = next; \
244
strm->avail_in = have; \
245
state->hold = hold; \
246
state->bits = bits; \
249
/* Clear the input bit accumulator */
256
/* Get a byte of input into the bit accumulator, or return from inflate()
257
if there is no input available. */
260
if (have == 0) goto inf_leave; \
262
hold += (unsigned long)(*next++) << bits; \
266
/* Assure that there are at least n bits in the bit accumulator. If there is
267
not enough available input to do that, then return from inflate(). */
268
#define NEEDBITS(n) \
270
while (bits < (unsigned)(n)) \
274
/* Return the low n bits of the bit accumulator (n < 16) */
276
((unsigned)hold & ((1U << (n)) - 1))
278
/* Remove n bits from the bit accumulator */
279
#define DROPBITS(n) \
282
bits -= (unsigned)(n); \
285
/* Remove zero to seven bits as needed to go to a byte boundary */
292
/* Reverse the bytes in a 32-bit value */
294
((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
295
(((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
298
inflate() uses a state machine to process as much input data and generate as
299
much output data as possible before returning. The state machine is
300
structured roughly as follows:
302
for (;;) switch (state) {
305
if (not enough input data or output space to make progress)
307
... make progress ...
313
so when inflate() is called again, the same case is attempted again, and
314
if the appropriate resources are provided, the machine proceeds to the
315
next state. The NEEDBITS() macro is usually the way the state evaluates
316
whether it can proceed or should return. NEEDBITS() does the return if
317
the requested bits are not available. The typical use of the BITS macros
321
... do something with BITS(n) ...
324
where NEEDBITS(n) either returns from inflate() if there isn't enough
325
input left to load n bits into the accumulator, or it continues. BITS(n)
326
gives the low n bits in the accumulator. When done, DROPBITS(n) drops
327
the low n bits off the accumulator. INITBITS() clears the accumulator
328
and sets the number of available bits to zero. BYTEBITS() discards just
329
enough bits to put the accumulator on a byte boundary. After BYTEBITS()
330
and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
332
NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
333
if there is no input available. The decoding of variable length codes uses
334
PULLBYTE() directly in order to pull just enough bytes to decode the next
337
Some states loop until they get enough input, making sure that enough
338
state information is maintained to continue the loop where it left off
339
if NEEDBITS() returns in the loop. For example, want, need, and keep
340
would all have to actually be part of the saved state in case NEEDBITS()
344
while (want < need) {
346
keep[want++] = BITS(n);
352
As shown above, if the next state is also the next case, then the break
355
A state may also return if there is not enough output space available to
356
complete that state. Those states are copying stored data, writing a
357
literal byte, and copying a matching string.
359
When returning, a "goto inf_leave" is used to update the total counters,
360
update the check value, and determine whether any progress has been made
361
during that inflate() call in order to return the proper return code.
362
Progress is defined as a change in either strm->avail_in or strm->avail_out.
363
When there is a window, goto inf_leave will update the window with the last
364
output written. If a goto inf_leave occurs in the middle of decompression
365
and there is no window currently, goto inf_leave will create one and copy
366
output to the window for the next call of inflate().
368
In this implementation, the flush parameter of inflate() only affects the
369
return code (per zlib.h). inflate() always writes as much as possible to
370
strm->next_out, given the space available and the provided input--the effect
371
documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
372
the allocation of and copying into a sliding window until necessary, which
373
provides the effect documented in zlib.h for Z_FINISH when the entire input
374
stream available. So the only thing the flush parameter actually does is:
375
when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
376
will return Z_BUF_ERROR if it has not reached the end of the stream.
379
int ZEXPORT inflate64(strm, flush)
383
struct inflate_state FAR *state;
384
unsigned char FAR *next; /* next input */
385
unsigned char FAR *put; /* next output */
386
unsigned have, left; /* available input and output */
387
unsigned long hold; /* bit buffer */
388
unsigned bits; /* bits in bit buffer */
389
unsigned in, out; /* save starting available input and output */
390
unsigned copy; /* number of stored or match bytes to copy */
391
unsigned char FAR *from; /* where to copy match bytes from */
392
code this; /* current decoding table entry */
393
code last; /* parent table entry */
394
unsigned len; /* length to copy for repeats, bits to drop */
395
int ret; /* return code */
396
static const unsigned short order[19] = /* permutation of code lengths */
397
{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
399
if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
400
(strm->next_in == Z_NULL && strm->avail_in != 0))
401
return Z_STREAM_ERROR;
403
state = (struct inflate_state FAR *)strm->state;
404
if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
410
switch (state->mode) {
412
if (state->wrap == 0) {
413
state->mode = TYPEDO;
418
((BITS(8) << 8) + (hold >> 8)) % 31) {
419
state->mode = ACAB_BAD;
422
if (BITS(4) != Z_DEFLATED) {
423
state->mode = ACAB_BAD;
428
if (len > state->wbits) {
429
state->mode = ACAB_BAD;
432
state->dmax = 1U << len;
433
Tracev((stderr, "inflate: zlib header ok\n"));
434
strm->adler = state->check = adler32(0L, Z_NULL, 0);
435
state->mode = hold & 0x200 ? DICTID : TYPE;
440
strm->adler = state->check = REVERSE(hold);
447
if (flush == Z_BLOCK) goto inf_leave;
455
state->last = BITS(1);
458
case 0: /* stored block */
459
Tracev((stderr, "inflate: stored block%s\n",
460
state->last ? " (last)" : ""));
461
state->mode = STORED;
463
case 1: /* fixed block */
465
Tracev((stderr, "inflate: fixed codes block%s\n",
466
state->last ? " (last)" : ""));
467
state->mode = LEN; /* decode codes */
469
case 2: /* dynamic block */
470
Tracev((stderr, "inflate: dynamic codes block%s\n",
471
state->last ? " (last)" : ""));
475
state->mode = ACAB_BAD;
480
BYTEBITS(); /* go to byte boundary */
482
if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
483
state->mode = ACAB_BAD;
486
state->length = (unsigned)hold & 0xffff;
487
Tracev((stderr, "inflate: stored length %u\n",
492
copy = state->length;
494
if (copy > have) copy = have;
495
if (copy > left) copy = left;
496
if (copy == 0) goto inf_leave;
497
memcpy(put, next, copy);
502
state->length -= copy;
505
Tracev((stderr, "inflate: stored end\n"));
510
state->nlen = BITS(5) + 257;
512
state->ndist = BITS(5) + 1;
514
state->ncode = BITS(4) + 4;
516
#ifndef PKZIP_BUG_WORKAROUND
517
if (state->nlen > 286 || state->ndist > 30) {
518
state->mode = ACAB_BAD;
522
Tracev((stderr, "inflate: table sizes ok\n"));
524
state->mode = LENLENS;
526
while (state->have < state->ncode) {
528
state->lens[order[state->have++]] = (unsigned short)BITS(3);
531
while (state->have < 19)
532
state->lens[order[state->have++]] = 0;
533
state->next = state->codes;
534
state->lencode = (code const FAR *)(state->next);
536
ret = inflate_table(CODES, state->lens, 19, &(state->next),
537
&(state->lenbits), state->work);
539
state->mode = ACAB_BAD;
542
Tracev((stderr, "inflate: code lengths ok\n"));
544
state->mode = CODELENS;
546
while (state->have < state->nlen + state->ndist) {
548
this = state->lencode[BITS(state->lenbits)];
549
if ((unsigned)(this.bits) <= bits) break;
555
state->lens[state->have++] = this.val;
558
if (this.val == 16) {
559
NEEDBITS(this.bits + 2);
561
if (state->have == 0) {
562
state->mode = ACAB_BAD;
565
len = state->lens[state->have - 1];
569
else if (this.val == 17) {
570
NEEDBITS(this.bits + 3);
577
NEEDBITS(this.bits + 7);
583
if (state->have + copy > state->nlen + state->ndist) {
584
state->mode = ACAB_BAD;
588
state->lens[state->have++] = (unsigned short)len;
592
/* handle error breaks in while */
593
if (state->mode == ACAB_BAD) break;
595
/* build code tables */
596
state->next = state->codes;
597
state->lencode = (code const FAR *)(state->next);
599
ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
600
&(state->lenbits), state->work);
602
state->mode = ACAB_BAD;
605
state->distcode = (code const FAR *)(state->next);
607
ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
608
&(state->next), &(state->distbits), state->work);
610
state->mode = ACAB_BAD;
613
Tracev((stderr, "inflate: codes ok\n"));
616
/* if (have >= 6 && left >= 258) {
618
inflate_fast(strm, out);
623
this = state->lencode[BITS(state->lenbits)];
624
if ((unsigned)(this.bits) <= bits) break;
627
if (this.op && (this.op & 0xf0) == 0) {
630
this = state->lencode[last.val +
631
(BITS(last.bits + last.op) >> last.bits)];
632
if ((unsigned)(last.bits + this.bits) <= bits) break;
638
state->length = (unsigned)this.val;
639
if ((int)(this.op) == 0) {
640
Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
641
"inflate: literal '%c'\n" :
642
"inflate: literal 0x%02x\n", this.val));
646
Tracevv((stderr, "inflate: op %u\n", this.op));
648
Tracevv((stderr, "inflate: end of block\n"));
653
state->mode = ACAB_BAD;
656
state->extra = (unsigned)(this.op) & 31;
657
state->mode = LENEXT;
660
NEEDBITS(state->extra);
661
state->length += BITS(state->extra);
662
DROPBITS(state->extra);
664
Tracevv((stderr, "inflate: length %u\n", state->length));
668
this = state->distcode[BITS(state->distbits)];
669
if ((unsigned)(this.bits) <= bits) break;
672
if ((this.op & 0xf0) == 0) {
675
this = state->distcode[last.val +
676
(BITS(last.bits + last.op) >> last.bits)];
677
if ((unsigned)(last.bits + this.bits) <= bits) break;
684
state->mode = ACAB_BAD;
687
Tracevv((stderr, "inflate: val %u\n", state->offset));
688
state->offset = (unsigned)this.val;
689
state->extra = (unsigned)(this.op) & 15;
690
state->mode = DISTEXT;
693
NEEDBITS(state->extra);
694
state->offset += BITS(state->extra);
695
DROPBITS(state->extra);
697
#ifdef INFLATE_STRICT
698
if (state->offset > state->dmax) {
699
state->mode = ACAB_BAD;
703
if (state->offset > state->whave + out - left) {
704
state->mode = ACAB_BAD;
707
Tracevv((stderr, "inflate: distance %u\n", state->offset));
710
if (left == 0) goto inf_leave;
712
if (state->offset > copy) { /* copy from window */
713
copy = state->offset - copy;
714
if (copy > state->write) {
715
copy -= state->write;
716
from = state->window + (state->wsize - copy);
719
from = state->window + (state->write - copy);
720
if (copy > state->length) copy = state->length;
722
else { /* copy from output */
723
from = put - state->offset;
724
copy = state->length;
726
if (copy > left) copy = left;
728
state->length -= copy;
732
if (state->length == 0) state->mode = LEN;
735
if (left == 0) goto inf_leave;
736
*put++ = (unsigned char)(state->length);
744
strm->total_out += out;
747
strm->adler = state->check =
748
UPDATE(state->check, put - out, out);
751
REVERSE(hold)) != state->check) {
752
state->mode = ACAB_BAD;
756
Tracev((stderr, "inflate: check matches trailer\n"));
769
return Z_STREAM_ERROR;
773
Return from inflate(), updating the total counts and the check value.
774
If there was no progress during the inflate() call, return a buffer
775
error. Call updatewindow() to create and/or update the window state.
776
Note: a memory error from inflate() is non-recoverable.
780
if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
781
if (updatewindow(strm, out)) {
785
in -= strm->avail_in;
786
out -= strm->avail_out;
787
strm->total_in += in;
788
strm->total_out += out;
790
if (state->wrap && out)
791
strm->adler = state->check =
792
UPDATE(state->check, strm->next_out - out, out);
793
strm->data_type = state->bits + (state->last ? 64 : 0) +
794
(state->mode == TYPE ? 128 : 0);
795
if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
800
int ZEXPORT inflate64End(strm)
803
struct inflate_state FAR *state;
804
if (strm == Z_NULL || strm->state == Z_NULL)
805
return Z_STREAM_ERROR;
806
state = (struct inflate_state FAR *)strm->state;
807
if (state->window != Z_NULL) free(state->window);
809
strm->state = Z_NULL;
810
Tracev((stderr, "inflate: end\n"));
816
Build a set of tables to decode the provided canonical Huffman code.
817
The code lengths are lens[0..codes-1]. The result starts at *table,
818
whose indices are 0..2^bits-1. work is a writable array of at least
819
lens shorts, which is used as a work area. type is the type of code
820
to be generated, CODES, LENS, or DISTS. On return, zero is success,
821
-1 is an invalid code, and +1 means that ENOUGH isn't enough. table
822
on return points to the next available entry's address. bits is the
823
requested root table index bits, and on return it is the actual root
824
table index bits. It will differ if the request is greater than the
825
longest code or if it is less than the shortest code.
827
local int inflate_table(type, lens, codes, table, bits, work)
829
unsigned short FAR *lens;
831
code FAR * FAR *table;
833
unsigned short FAR *work;
835
unsigned len; /* a code's length in bits */
836
unsigned sym; /* index of code symbols */
837
unsigned min, max; /* minimum and maximum code lengths */
838
unsigned root; /* number of index bits for root table */
839
unsigned curr; /* number of index bits for current table */
840
unsigned drop; /* code bits to drop for sub-table */
841
int left; /* number of prefix codes available */
842
unsigned used; /* code entries in table used */
843
unsigned huff; /* Huffman code */
844
unsigned incr; /* for incrementing code, index */
845
unsigned fill; /* index for replicating entries */
846
unsigned low; /* low bits for current root entry */
847
unsigned mask; /* mask for low root bits */
848
code this; /* table entry for duplication */
849
code FAR *next; /* next available space in table */
850
const unsigned short FAR *base; /* base value table to use */
851
const unsigned short FAR *extra; /* extra bits table to use */
852
int end; /* use base and extra for symbol > end */
853
unsigned short count[MAXBITS+1]; /* number of codes of each length */
854
unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
855
static const unsigned short lbase[31] = { /* Length codes 257..285 base */
856
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
857
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, /* 258 */ 3, 0, 0};
858
static const unsigned short lext[31] = { /* Length codes 257..285 extra */
859
/* 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, */
860
/* 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 31, 201, 196}; */
861
128, 128, 128, 128, 128, 128, 128, 128, 129, 129, 129, 129, 130, 130, 130, 130,
862
131, 131, 131, 131, 132, 132, 132, 132, 133, 133, 133, 133, 144, 201, 196};
863
static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
864
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
865
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
866
8193, 12289, 16385, 24577, 32769, 49153};
867
static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
868
16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
869
23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
870
28, 28, 29, 29, 30, 30};
873
Process a set of code lengths to create a canonical Huffman code. The
874
code lengths are lens[0..codes-1]. Each length corresponds to the
875
symbols 0..codes-1. The Huffman code is generated by first sorting the
876
symbols by length from short to long, and retaining the symbol order
877
for codes with equal lengths. Then the code starts with all zero bits
878
for the first code of the shortest length, and the codes are integer
879
increments for the same length, and zeros are appended as the length
880
increases. For the deflate format, these bits are stored backwards
881
from their more natural integer increment ordering, and so when the
882
decoding tables are built in the large loop below, the integer codes
883
are incremented backwards.
885
This routine assumes, but does not check, that all of the entries in
886
lens[] are in the range 0..MAXBITS. The caller must assure this.
887
1..MAXBITS is interpreted as that code length. zero means that that
888
symbol does not occur in this code.
890
The codes are sorted by computing a count of codes for each length,
891
creating from that a table of starting indices for each length in the
892
sorted table, and then entering the symbols in order in the sorted
893
table. The sorted table is work[], with that space being provided by
896
The length counts are used for other purposes as well, i.e. finding
897
the minimum and maximum length codes, determining if there are any
898
codes at all, checking for a valid set of lengths, and looking ahead
899
at length counts to determine sub-table sizes when building the
903
/* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
904
for (len = 0; len <= MAXBITS; len++)
906
for (sym = 0; sym < codes; sym++)
909
/* bound code lengths, force root to be within code lengths */
911
for (max = MAXBITS; max >= 1; max--)
912
if (count[max] != 0) break;
913
if (root > max) root = max;
914
if (max == 0) { /* no symbols to code at all */
915
this.op = (unsigned char)64; /* invalid code marker */
916
this.bits = (unsigned char)1;
917
this.val = (unsigned short)0;
918
*(*table)++ = this; /* make a table to force an error */
921
return 0; /* no symbols, but wait for decoding to report error */
923
for (min = 1; min <= MAXBITS; min++)
924
if (count[min] != 0) break;
925
if (root < min) root = min;
927
/* check for an over-subscribed or incomplete set of lengths */
929
for (len = 1; len <= MAXBITS; len++) {
932
if (left < 0) return -1; /* over-subscribed */
934
if (left > 0 && (type == CODES || max != 1))
935
return -1; /* incomplete set */
937
/* generate offsets into symbol table for each length for sorting */
939
for (len = 1; len < MAXBITS; len++)
940
offs[len + 1] = offs[len] + count[len];
942
/* sort symbols by length, by symbol order within each length */
943
for (sym = 0; sym < codes; sym++)
944
if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
947
Create and fill in decoding tables. In this loop, the table being
948
filled is at next and has curr index bits. The code being used is huff
949
with length len. That code is converted to an index by dropping drop
950
bits off of the bottom. For codes where len is less than drop + curr,
951
those top drop + curr - len bits are incremented through all values to
952
fill the table with replicated entries.
954
root is the number of index bits for the root table. When len exceeds
955
root, sub-tables are created pointed to by the root entry with an index
956
of the low root bits of huff. This is saved in low to check for when a
957
new sub-table should be started. drop is zero when the root table is
958
being filled, and drop is root when sub-tables are being filled.
960
When a new sub-table is needed, it is necessary to look ahead in the
961
code lengths to determine what size sub-table is needed. The length
962
counts are used for this, and so count[] is decremented as codes are
963
entered in the tables.
965
used keeps track of how many table entries have been allocated from the
966
provided *table space. It is checked when a LENS table is being made
967
against the space in *table, ENOUGH, minus the maximum space needed by
968
the worst case distance code, MAXD. This should never happen, but the
969
sufficiency of ENOUGH has not been proven exhaustively, hence the check.
970
This assumes that when type == LENS, bits == 9.
972
sym increments through all symbols, and the loop terminates when
973
all codes of length max, i.e. all codes, have been processed. This
974
routine permits incomplete codes, so another loop after this one fills
975
in the rest of the decoding tables with invalid code markers.
978
/* set up for code type */
981
base = extra = work; /* dummy value--not used */
997
/* initialize state for loop */
998
huff = 0; /* starting code */
999
sym = 0; /* starting code symbol */
1000
len = min; /* starting code length */
1001
next = *table; /* current table to fill in */
1002
curr = root; /* current table index bits */
1003
drop = 0; /* current bits to drop from code for index */
1004
low = (unsigned)(-1); /* trigger new sub-table when len > root */
1005
used = 1U << root; /* use root table entries */
1006
mask = used - 1; /* mask for comparing low */
1008
/* check available table space */
1009
if (type == LENS && used >= ENOUGH - MAXD)
1012
/* process all codes and make table entries */
1014
/* create table entry */
1015
this.bits = (unsigned char)(len - drop);
1016
if ((int)(work[sym]) < end) {
1017
this.op = (unsigned char)0;
1018
this.val = work[sym];
1020
else if ((int)(work[sym]) > end) {
1021
this.op = (unsigned char)(extra[work[sym]]);
1022
this.val = base[work[sym]];
1025
this.op = (unsigned char)(32 + 64); /* end of block */
1029
/* replicate for those indices with low len bits equal to huff */
1030
incr = 1U << (len - drop);
1032
min = fill; /* save offset to next table */
1035
next[(huff >> drop) + fill] = this;
1036
} while (fill != 0);
1038
/* backwards increment the len-bit code huff */
1039
incr = 1U << (len - 1);
1049
/* go to next symbol, update count, len */
1051
if (--(count[len]) == 0) {
1052
if (len == max) break;
1053
len = lens[work[sym]];
1056
/* create new sub-table if needed */
1057
if (len > root && (huff & mask) != low) {
1058
/* if first time, transition to sub-tables */
1062
/* increment past last table */
1063
next += min; /* here min is 1 << curr */
1065
/* determine length of next table */
1067
left = (int)(1 << curr);
1068
while (curr + drop < max) {
1069
left -= count[curr + drop];
1070
if (left <= 0) break;
1075
/* check for enough space */
1077
if (type == LENS && used >= ENOUGH - MAXD)
1080
/* point entry in root table to sub-table */
1082
(*table)[low].op = (unsigned char)curr;
1083
(*table)[low].bits = (unsigned char)root;
1084
(*table)[low].val = (unsigned short)(next - *table);
1089
Fill in rest of table for incomplete codes. This loop is similar to the
1090
loop above in incrementing huff for table indices. It is assumed that
1091
len is equal to curr + drop, so there is no loop needed to increment
1092
through high index bits. When the current sub-table is filled, the loop
1093
drops back to the root table to fill in any remaining entries there.
1095
this.op = (unsigned char)64; /* invalid code marker */
1096
this.bits = (unsigned char)(len - drop);
1097
this.val = (unsigned short)0;
1099
/* when done with sub-table, drop back to root table */
1100
if (drop != 0 && (huff & mask) != low) {
1104
this.bits = (unsigned char)len;
1107
/* put invalid code marker in table */
1108
next[huff >> drop] = this;
1110
/* backwards increment the len-bit code huff */
1111
incr = 1U << (len - 1);
1122
/* set return parameters */
added
removed
libclamav/inflate64.c
