/* unpack.c -- decompress files in pack format.
* Copyright (C) 1992-1993 Jean-loup Gailly
* This is free software; you can redistribute it and/or modify it under the
* terms of the GNU General Public License, see the file COPYING.
static char rcsid
[] = "$Id: unpack.c,v 1.4 1993/06/11 19:25:36 jloup Exp $";
#define MIN(a,b) ((a) <= (b) ? (a) : (b))
/* The arguments must not have side effects. */
/* Maximum length of Huffman codes. (Minor modifications to the code
* would be needed to support 32 bits codes, but pack never generates
* more than 24 bits anyway.)
/* Number of literals, excluding the End of Block (EOB) code */
/* Maximum number of 'peek' bits used to optimize traversal of the
local ulg orig_len
; /* original uncompressed length */
local
int max_len
; /* maximum bit length of Huffman codes */
local uch literal
[LITERALS
];
/* The literal bytes present in the Huffman tree. The EOB code is not
local
int lit_base
[MAX_BITLEN
+1];
/* All literals of a given bit length are contiguous in literal[] and
* have contiguous codes. literal[code+lit_base[len]] is the literal
* for a code of len bits.
local
int leaves
[MAX_BITLEN
+1]; /* Number of leaves for each bit length */
local
int parents
[MAX_BITLEN
+1]; /* Number of parents for each bit length */
local
int peek_bits
; /* Number of peek bits currently used */
/* local uch prefix_len[1 << MAX_PEEK]; */
#define prefix_len outbuf
/* For each bit pattern b of peek_bits bits, prefix_len[b] is the length
* of the Huffman code starting with a prefix of b (upper bits), or 0
* if all codes of prefix b have more than peek_bits bits. It is not
* necessary to have a huge table (large MAX_PEEK) because most of the
* codes encountered in the input stream are short codes (by construction).
* So for most codes a single lookup will be necessary.
#if (1<<MAX_PEEK) > OUTBUFSIZ
error cannot overlay prefix_len
and outbuf
/* Bits are added on the low part of bitbuf and read from the high part. */
local
int valid
; /* number of valid bits in bitbuf */
/* all bits above the last valid bit are always zero */
/* Set code to the next 'bits' input bits without skipping them. code
* must be the name of a simple variable and bits must not have side effects.
* IN assertions: bits <= 25 (so that we still have room for an extra byte
* when valid is only 24), and mask = (1<<bits)-1.
#define look_bits(code,bits,mask) \
while (valid < (bits)) bitbuf = (bitbuf<<8) | (ulg)get_byte(), valid += 8; \
code = (bitbuf >> (valid-(bits))) & (mask); \
/* Skip the given number of bits (after having peeked at them): */
#define skip_bits(bits) (valid -= (bits))
#define clear_bitbuf() (valid = 0, bitbuf = 0)
local
void read_tree
OF((void));
local
void build_tree
OF((void));
/* ===========================================================================
int len
; /* bit length */
int base
; /* base offset for a sequence of leaves */
/* Read the original input size, MSB first */
for (n
= 1; n
<= 4; n
++) orig_len
= (orig_len
<< 8) | (ulg
)get_byte();
max_len
= (int)get_byte(); /* maximum bit length of Huffman codes */
if (max_len
> MAX_BITLEN
) {
error("invalid compressed data -- Huffman code > 32 bits");
/* Get the number of leaves at each bit length */
for (len
= 1; len
<= max_len
; len
++) {
leaves
[len
] = (int)get_byte();
error("too many leaves in Huffman tree");
Trace((stderr
, "orig_len %ld, max_len %d, leaves %d\n",
/* There are at least 2 and at most 256 leaves of length max_len.
* (Pack arbitrarily rejects empty files and files consisting of
* a single byte even repeated.) To fit the last leaf count in a
* byte, it is offset by 2. However, the last literal is the EOB
* code, and is not transmitted explicitly in the tree, so we must
* adjust here by one only.
/* Now read the leaves themselves */
for (len
= 1; len
<= max_len
; len
++) {
/* Remember where the literals of this length start in literal[] : */
/* And read the literals: */
for (n
= leaves
[len
]; n
> 0; n
--) {
literal
[base
++] = (uch
)get_byte();
leaves
[max_len
]++; /* Now include the EOB code in the Huffman tree */
/* ===========================================================================
* Build the Huffman tree and the prefix table.
int nodes
= 0; /* number of nodes (parents+leaves) at current bit length */
int len
; /* current bit length */
uch
*prefixp
; /* pointer in prefix_len */
for (len
= max_len
; len
>= 1; len
--) {
/* The number of parent nodes at this level is half the total
* number of nodes at parent level:
/* Update lit_base by the appropriate bias to skip the parent nodes
* (which are not represented in the literal array):
/* Restore nodes to be parents+leaves: */
/* Construct the prefix table, from shortest leaves to longest ones.
* The shortest code is all ones, so we start at the end of the table.
peek_bits
= MIN(max_len
, MAX_PEEK
);
prefixp
= &prefix_len
[1<<peek_bits
];
for (len
= 1; len
<= peek_bits
; len
++) {
int prefixes
= leaves
[len
] << (peek_bits
-len
); /* may be 0 */
while (prefixes
--) *--prefixp
= (uch
)len
;
/* The length of all other codes is unknown: */
while (prefixp
> prefix_len
) *--prefixp
= 0;
/* ===========================================================================
* Unpack in to out. This routine does not support the old pack format
* with magic header \037\037.
* IN assertions: the buffer inbuf contains already the beginning of
* the compressed data, from offsets inptr to insize-1 included.
* The magic header has already been checked. The output buffer is cleared.
int in
, out
; /* input and output file descriptors */
int len
; /* Bit length of current code */
unsigned eob
; /* End Of Block code */
register unsigned peek
; /* lookahead bits */
unsigned peek_mask
; /* Mask for peek_bits bits */
read_tree(); /* Read the Huffman tree */
build_tree(); /* Build the prefix table */
clear_bitbuf(); /* Initialize bit input */
peek_mask
= (1<<peek_bits
)-1;
/* The eob code is the largest code among all leaves of maximal length: */
Trace((stderr
, "eob %d %x\n", max_len
, eob
));
/* Decode the input data: */
/* Since eob is the longest code and not shorter than max_len,
* we can peek at max_len bits without having the risk of reading
* beyond the end of file.
look_bits(peek
, peek_bits
, peek_mask
);
peek
>>= peek_bits
- len
; /* discard the extra bits */
/* Code of more than peek_bits bits, we must traverse the tree */
len
++, mask
= (mask
<<1)+1;
look_bits(peek
, len
, mask
);
} while (peek
< (unsigned)parents
[len
]);
/* loop as long as peek is a parent node */
/* At this point, peek is the next complete code, of len bits */
if (peek
== eob
&& len
== max_len
) break; /* end of file? */
put_ubyte(literal
[peek
+lit_base
[len
]]);
Tracev((stderr
,"%02d %04x %c\n", len
, peek
,
literal
[peek
+lit_base
[len
]]));
Trace((stderr
, "bytes_out %ld\n", bytes_out
));
if (orig_len
!= (ulg
)bytes_out
) {
error("invalid compressed data--length error");