Return to unpack.c CVS log

Up to [MW Coherent from dump] / coherent / g / usr / bin / gzip

Annotation of coherent/g/usr/bin/gzip/unpack.c, revision 1.1

1.1     ! root        1: /* unpack.c -- decompress files in pack format.
        !             2:  * Copyright (C) 1992-1993 Jean-loup Gailly
        !             3:  * This is free software; you can redistribute it and/or modify it under the
        !             4:  * terms of the GNU General Public License, see the file COPYING.
        !             5:  */
        !             6: 
        !             7: #ifndef lint
        !             8: static char rcsid[] = "$Id: unpack.c,v 1.2 1993/02/04 13:21:06 jloup Exp $";
        !             9: #endif
        !            10: 
        !            11: #include "tailor.h"
        !            12: #include "gzip.h"
        !            13: #include "crypt.h"
        !            14: 
        !            15: #include <stdio.h>
        !            16: 
        !            17: #define MIN(a,b) ((a) <= (b) ? (a) : (b))
        !            18: /* The arguments must not have side effects. */
        !            19: 
        !            20: #define MAX_BITLEN 25
        !            21: /* Maximum length of Huffman codes. (Minor modifications to the code
        !            22:  * would be needed to support 32 bits codes, but pack never generates
        !            23:  * more than 24 bits anyway.)
        !            24:  */
        !            25: 
        !            26: #define LITERALS 256
        !            27: /* Number of literals, excluding the End of Block (EOB) code */
        !            28: 
        !            29: #define MAX_PEEK 12
        !            30: /* Maximum number of 'peek' bits used to optimize traversal of the
        !            31:  * Huffman tree.
        !            32:  */
        !            33: 
        !            34: local ulg orig_len;       /* original uncompressed length */
        !            35: local int max_len;        /* maximum bit length of Huffman codes */
        !            36: 
        !            37: local uch literal[LITERALS];
        !            38: /* The literal bytes present in the Huffman tree. The EOB code is not
        !            39:  * represented.
        !            40:  */
        !            41: 
        !            42: local int lit_base[MAX_BITLEN+1];
        !            43: /* All literals of a given bit length are contiguous in literal[] and
        !            44:  * have contiguous codes. literal[code+lit_base[len]] is the literal
        !            45:  * for a code of len bits.
        !            46:  */
        !            47: 
        !            48: local int leaves [MAX_BITLEN+1]; /* Number of leaves for each bit length */
        !            49: local int parents[MAX_BITLEN+1]; /* Number of parents for each bit length */
        !            50: 
        !            51: local int peek_bits; /* Number of peek bits currently used */
        !            52: 
        !            53: local uch prefix_len[1 << MAX_PEEK];
        !            54: /* For each bit pattern b of peek_bits bits, prefix_len[b] is the length
        !            55:  * of the Huffman code starting with a prefix of b (upper bits), or 0
        !            56:  * if all codes of prefix b have more than peek_bits bits. It is not
        !            57:  * necessary to have a huge table (large MAX_PEEK) because most of the
        !            58:  * codes encountered in the input stream are short codes (by construction).
        !            59:  * So for most codes a single lookup will be necessary.
        !            60:  */
        !            61: 
        !            62: local ulg bitbuf;
        !            63: /* Bits are added on the low part of bitbuf and read from the high part. */
        !            64: 
        !            65: local int valid;                  /* number of valid bits in bitbuf */
        !            66: /* all bits above the last valid bit are always zero */
        !            67: 
        !            68: /* Set code to the next 'bits' input bits without skipping them. code
        !            69:  * must be the name of a simple variable and bits must not have side effects.
        !            70:  * IN assertions: bits <= 25 (so that we still have room for an extra byte
        !            71:  * when valid is only 24), and mask = (1<<bits)-1.
        !            72:  */
        !            73: #define look_bits(code,bits,mask) \
        !            74: { \
        !            75:   while (valid < (bits)) bitbuf = (bitbuf<<8) | (ulg)get_byte(), valid += 8; \
        !            76:   code = (bitbuf >> (valid-(bits))) & (mask); \
        !            77: }
        !            78: 
        !            79: /* Skip the given number of bits (after having peeked at them): */
        !            80: #define skip_bits(bits)  (valid -= (bits))
        !            81: 
        !            82: #define clear_bitbuf() (valid = 0, bitbuf = 0)
        !            83: 
        !            84: /* Local functions */
        !            85: 
        !            86: local void read_tree  OF((void));
        !            87: local void build_tree OF((void));
        !            88: 
        !            89: /* ===========================================================================
        !            90:  * Read the Huffman tree.
        !            91:  */
        !            92: local void read_tree()
        !            93: {
        !            94:     int len;  /* bit length */
        !            95:     int base; /* base offset for a sequence of leaves */
        !            96:     int n;
        !            97: 
        !            98:     /* Read the original input size, MSB first */
        !            99:     orig_len = 0;
        !           100:     for (n = 1; n <= 4; n++) orig_len = (orig_len << 8) | (ulg)get_byte();
        !           101: 
        !           102:     max_len = (int)get_byte(); /* maximum bit length of Huffman codes */
        !           103:     if (max_len > MAX_BITLEN) {
        !           104:        error("invalid compressed data -- Huffman code > 32 bits");
        !           105:     }
        !           106: 
        !           107:     /* Get the number of leaves at each bit length */
        !           108:     n = 0;
        !           109:     for (len = 1; len <= max_len; len++) {
        !           110:        leaves[len] = (int)get_byte();
        !           111:        n += leaves[len];
        !           112:     }
        !           113:     if (n > LITERALS) {
        !           114:        error("too many leaves in Huffman tree");
        !           115:     }
        !           116:     Trace((stderr, "orig_len %ld, max_len %d, leaves %d\n",
        !           117:           orig_len, max_len, n));
        !           118:     /* There are at least 2 and at most 256 leaves of length max_len.
        !           119:      * (Pack arbitrarily rejects empty files and files consisting of
        !           120:      * a single byte even repeated.) To fit the last leaf count in a
        !           121:      * byte, it is offset by 2. However, the last literal is the EOB
        !           122:      * code, and is not transmitted explicitly in the tree, so we must
        !           123:      * adjust here by one only.
        !           124:      */
        !           125:     leaves[max_len]++;
        !           126: 
        !           127:     /* Now read the leaves themselves */
        !           128:     base = 0;
        !           129:     for (len = 1; len <= max_len; len++) {
        !           130:        /* Remember where the literals of this length start in literal[] : */
        !           131:        lit_base[len] = base;
        !           132:        /* And read the literals: */
        !           133:        for (n = leaves[len]; n > 0; n--) {
        !           134:            literal[base++] = (uch)get_byte();
        !           135:        }
        !           136:     }
        !           137:     leaves[max_len]++; /* Now include the EOB code in the Huffman tree */
        !           138: }
        !           139: 
        !           140: /* ===========================================================================
        !           141:  * Build the Huffman tree and the prefix table.
        !           142:  */
        !           143: local void build_tree()
        !           144: {
        !           145:     int nodes = 0; /* number of nodes (parents+leaves) at current bit length */
        !           146:     int len;       /* current bit length */
        !           147:     uch *prefixp;  /* pointer in prefix_len */
        !           148: 
        !           149:     for (len = max_len; len >= 1; len--) {
        !           150:        /* The number of parent nodes at this level is half the total
        !           151:         * number of nodes at parent level:
        !           152:         */
        !           153:        nodes >>= 1;
        !           154:        parents[len] = nodes;
        !           155:        /* Update lit_base by the appropriate bias to skip the parent nodes
        !           156:         * (which are not represented in the literal array):
        !           157:         */
        !           158:        lit_base[len] -= nodes;
        !           159:        /* Restore nodes to be parents+leaves: */
        !           160:        nodes += leaves[len];
        !           161:     }
        !           162:     /* Construct the prefix table, from shortest leaves to longest ones.
        !           163:      * The shortest code is all ones, so we start at the end of the table.
        !           164:      */
        !           165:     peek_bits = MIN(max_len, MAX_PEEK);
        !           166:     prefixp = &prefix_len[1<<peek_bits];
        !           167:     for (len = 1; len <= peek_bits; len++) {
        !           168:        int prefixes = leaves[len] << (peek_bits-len); /* may be 0 */
        !           169:        while (prefixes--) *--prefixp = (uch)len;
        !           170:     }
        !           171:     /* The length of all other codes is unknown: */
        !           172:     while (prefixp > prefix_len) *--prefixp = 0;
        !           173: }
        !           174: 
        !           175: /* ===========================================================================
        !           176:  * Unpack in to out.  This routine does not support the old pack format
        !           177:  * with magic header \037\037.
        !           178:  *
        !           179:  * IN assertions: the buffer inbuf contains already the beginning of
        !           180:  *   the compressed data, from offsets inptr to insize-1 included.
        !           181:  *   The magic header has already been checked. The output buffer is cleared.
        !           182:  */
        !           183: void unpack(in, out)
        !           184:     int in, out;            /* input and output file descriptors */
        !           185: {
        !           186:     int len;                /* Bit length of current code */
        !           187:     unsigned eob;           /* End Of Block code */
        !           188:     register unsigned peek; /* lookahead bits */
        !           189:     unsigned peek_mask;     /* Mask for peek_bits bits */
        !           190: 
        !           191:     ifd = in;
        !           192:     ofd = out;
        !           193: 
        !           194:     read_tree();     /* Read the Huffman tree */
        !           195:     build_tree();    /* Build the prefix table */
        !           196:     clear_bitbuf();  /* Initialize bit input */
        !           197:     peek_mask = (1<<peek_bits)-1;
        !           198: 
        !           199:     /* The eob code is the largest code among all leaves of maximal length: */
        !           200:     eob = leaves[max_len]-1;
        !           201:     Trace((stderr, "eob %d %x\n", max_len, eob));
        !           202: 
        !           203:     /* Decode the input data: */
        !           204:     for (;;) {
        !           205:        /* Since eob is the longest code and not shorter than max_len,
        !           206:          * we can peek at max_len bits without having the risk of reading
        !           207:          * beyond the end of file.
        !           208:         */
        !           209:        look_bits(peek, peek_bits, peek_mask);
        !           210:        len = prefix_len[peek];
        !           211:        if (len > 0) {
        !           212:            peek >>= peek_bits - len; /* discard the extra bits */
        !           213:        } else {
        !           214:            /* Code of more than peek_bits bits, we must traverse the tree */
        !           215:            ulg mask = peek_mask;
        !           216:            len = peek_bits;
        !           217:            do {
        !           218:                 len++, mask = (mask<<1)+1;
        !           219:                look_bits(peek, len, mask);
        !           220:            } while (peek < parents[len]);
        !           221:            /* loop as long as peek is a parent node */
        !           222:        }
        !           223:        /* At this point, peek is the next complete code, of len bits */
        !           224:        if (peek == eob && len == max_len) break; /* end of file? */
        !           225:        put_char(literal[peek+lit_base[len]]);
        !           226:        Tracev((stderr,"%02d %04x %c\n", len, peek,
        !           227:                literal[peek+lit_base[len]]));
        !           228:        skip_bits(len);
        !           229:     } /* for (;;) */
        !           230: 
        !           231:     flush_window();
        !           232:     Trace((stderr, "bytes_out %ld\n", bytes_out));
        !           233:     if (orig_len != bytes_out) {
        !           234:        error("invalid compressed data--length error");
        !           235:     }
        !           236: }
        !           237: 
        !           238: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.