deflate.c

给出了 zip 压缩算法的完整实现过程。

         * order to compute the crc, update lookahead and possibly set eofile.
         */
        } else if (strstart >= WSIZE+MAX_DIST && sliding) {

#ifdef FORCE_METHOD
            /* When methods "stored" or "store_block" are requested, the
             * current block must be flushed before sliding the window.
             */
            if (level <= 2) FLUSH_BLOCK(0), block_start = strstart;
#endif
            /* By the IN assertion, the window is not empty so we can't confuse
             * more == 0 with more == 64K on a 16 bit machine.
             */
            memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE);
            match_start -= WSIZE;
            strstart    -= WSIZE; /* we now have strstart >= MAX_DIST: */

            block_start -= (long) WSIZE;

            for (n = 0; n < HASH_SIZE; n++) {
                m = head[n];
                head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
            }
            for (n = 0; n < WSIZE; n++) {
                m = prev[n];
                prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
                /* If n is not on any hash chain, prev[n] is garbage but
                 * its value will never be used.
                 */
            }
            more += WSIZE;
#ifndef WINDLL
            if (verbose) putc('.', stderr);
#else
            if (verbose) fprintf(stdout,"%c",'.');
#endif
        }
        if (eofile) return;

        /* If there was no sliding:
         *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
         *    more == window_size - lookahead - strstart
         * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
         * => more >= window_size - 2*WSIZE + 2
         * In the MMAP or BIG_MEM case (not yet supported in gzip),
         *   window_size == input_size + MIN_LOOKAHEAD  &&
         *   strstart + lookahead <= input_size => more >= MIN_LOOKAHEAD.
         * Otherwise, window_size == 2*WSIZE so more >= 2.
         * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
         */
        Assert(more >= 2, "more < 2");

        n = (*read_buf)((char*)window+strstart+lookahead, more);
        if (n == 0 || n == (unsigned)EOF) {
            eofile = 1;
        } else {
            lookahead += n;
        }
    } while (lookahead < MIN_LOOKAHEAD && !eofile);
}

/* ===========================================================================
 * Processes a new input file and return its compressed length. This
 * function does not perform lazy evaluation of matches and inserts
 * new strings in the dictionary only for unmatched strings or for short
 * matches. It is used only for the fast compression options.
 */
local ulg deflate_fast()
{
    IPos hash_head = NIL;       /* head of the hash chain */
    int flush;                  /* set if current block must be flushed */
    unsigned match_length = 0;  /* length of best match */

    prev_length = MIN_MATCH-1;
    while (lookahead != 0) {
        /* Insert the string window[strstart .. strstart+2] in the
         * dictionary, and set hash_head to the head of the hash chain:
         */
#ifndef DEFL_UNDETERM
        if (lookahead >= MIN_MATCH)
#endif
        INSERT_STRING(strstart, hash_head);

        /* Find the longest match, discarding those <= prev_length.
         * At this point we have always match_length < MIN_MATCH
         */
        if (hash_head != NIL && strstart - hash_head <= MAX_DIST) {
            /* To simplify the code, we prevent matches with the string
             * of window index 0 (in particular we have to avoid a match
             * of the string with itself at the start of the input file).
             */
#ifndef HUFFMAN_ONLY
#  ifndef DEFL_UNDETERM
            /* Do not look for matches beyond the end of the input.
             * This is necessary to make deflate deterministic.
             */
            if ((unsigned)nice_match > lookahead) nice_match = (int)lookahead;
#  endif
            match_length = longest_match (hash_head);
            /* longest_match() sets match_start */
            if (match_length > lookahead) match_length = lookahead;
#endif
        }
        if (match_length >= MIN_MATCH) {
            check_match(strstart, match_start, match_length);

            flush = ct_tally(strstart-match_start, match_length - MIN_MATCH);

            lookahead -= match_length;

            /* Insert new strings in the hash table only if the match length
             * is not too large. This saves time but degrades compression.
             */
            if (match_length <= max_insert_length
#ifndef DEFL_UNDETERM
                && lookahead >= MIN_MATCH
#endif
                                                 ) {
                match_length--; /* string at strstart already in hash table */
                do {
                    strstart++;
                    INSERT_STRING(strstart, hash_head);
                    /* strstart never exceeds WSIZE-MAX_MATCH, so there are
                     * always MIN_MATCH bytes ahead.
                     */
#ifdef DEFL_UNDETERM
                    /* If lookahead < MIN_MATCH these bytes are garbage,
                     * but it does not matter since the next lookahead bytes
                     * will be emitted as literals.
                     */
#endif
                } while (--match_length != 0);
                strstart++;
            } else {
                strstart += match_length;
                match_length = 0;
                ins_h = window[strstart];
                UPDATE_HASH(ins_h, window[strstart+1]);
#if MIN_MATCH != 3
                Call UPDATE_HASH() MIN_MATCH-3 more times
#endif
            }
        } else {
            /* No match, output a literal byte */
            Tracevv((stderr,"%c",window[strstart]));
            flush = ct_tally (0, window[strstart]);
            lookahead--;
            strstart++;
        }
        if (flush) FLUSH_BLOCK(0), block_start = strstart;

        /* Make sure that we always have enough lookahead, except
         * at the end of the input file. We need MAX_MATCH bytes
         * for the next match, plus MIN_MATCH bytes to insert the
         * string following the next match.
         */
        if (lookahead < MIN_LOOKAHEAD) fill_window();
    }
    return FLUSH_BLOCK(1); /* eof */
}

/* ===========================================================================
 * Same as above, but achieves better compression. We use a lazy
 * evaluation for matches: a match is finally adopted only if there is
 * no better match at the next window position.
 */
ulg deflate()
{
    IPos hash_head = NIL;       /* head of hash chain */
    IPos prev_match;            /* previous match */
    int flush;                  /* set if current block must be flushed */
    int match_available = 0;    /* set if previous match exists */
    register unsigned match_length = MIN_MATCH-1; /* length of best match */
#ifdef DEBUG
    extern ulg isize;           /* byte length of input file, for debug only */
#endif

    if (level <= 3) return deflate_fast(); /* optimized for speed */

    /* Process the input block. */
    while (lookahead != 0) {
        /* Insert the string window[strstart .. strstart+2] in the
         * dictionary, and set hash_head to the head of the hash chain:
         */
#ifndef DEFL_UNDETERM
        if (lookahead >= MIN_MATCH)
#endif
        INSERT_STRING(strstart, hash_head);

        /* Find the longest match, discarding those <= prev_length.
         */
        prev_length = match_length, prev_match = match_start;
        match_length = MIN_MATCH-1;

        if (hash_head != NIL && prev_length < max_lazy_match &&
            strstart - hash_head <= MAX_DIST) {
            /* To simplify the code, we prevent matches with the string
             * of window index 0 (in particular we have to avoid a match
             * of the string with itself at the start of the input file).
             */
#ifndef HUFFMAN_ONLY
#  ifndef DEFL_UNDETERM
            /* Do not look for matches beyond the end of the input.
             * This is necessary to make deflate deterministic.
             */
            if ((unsigned)nice_match > lookahead) nice_match = (int)lookahead;
#  endif
            match_length = longest_match (hash_head);
            /* longest_match() sets match_start */
            if (match_length > lookahead) match_length = lookahead;
#endif

#ifdef FILTERED
            /* Ignore matches of length <= 5 */
            if (match_length <= 5) {
#else
            /* Ignore a length 3 match if it is too distant: */
            if (match_length == MIN_MATCH && strstart-match_start > TOO_FAR){
#endif
                /* If prev_match is also MIN_MATCH, match_start is garbage
                 * but we will ignore the current match anyway.
                 */
                match_length = MIN_MATCH-1;
            }
        }
        /* If there was a match at the previous step and the current
         * match is not better, output the previous match:
         */
        if (prev_length >= MIN_MATCH && match_length <= prev_length) {
#ifndef DEFL_UNDETERM
            unsigned max_insert = strstart + lookahead - MIN_MATCH;

#endif
            check_match(strstart-1, prev_match, prev_length);

            flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH);

            /* Insert in hash table all strings up to the end of the match.
             * strstart-1 and strstart are already inserted.
             */
            lookahead -= prev_length-1;
            prev_length -= 2;
#ifndef DEFL_UNDETERM
            do {
                if (++strstart <= max_insert) {
                    INSERT_STRING(strstart, hash_head);
                    /* strstart never exceeds WSIZE-MAX_MATCH, so there are
                     * always MIN_MATCH bytes ahead.
                     */
                }
            } while (--prev_length != 0);
            strstart++;
#else /* DEFL_UNDETERM */
            do {
                strstart++;
                INSERT_STRING(strstart, hash_head);
                /* strstart never exceeds WSIZE-MAX_MATCH, so there are
                 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
                 * these bytes are garbage, but it does not matter since the
                 * next lookahead bytes will always be emitted as literals.
                 */
            } while (--prev_length != 0);
            strstart++;
#endif /* ?DEFL_UNDETERM */
            match_available = 0;
            match_length = MIN_MATCH-1;

            if (flush) FLUSH_BLOCK(0), block_start = strstart;

        } else if (match_available) {
            /* If there was no match at the previous position, output a
             * single literal. If there was a match but the current match
             * is longer, truncate the previous match to a single literal.
             */
            Tracevv((stderr,"%c",window[strstart-1]));
            if (ct_tally (0, window[strstart-1])) {
                FLUSH_BLOCK(0), block_start = strstart;
            }
            strstart++;
            lookahead--;
        } else {
            /* There is no previous match to compare with, wait for
             * the next step to decide.
             */
            match_available = 1;
            strstart++;
            lookahead--;
        }
        Assert(strstart <= isize && lookahead <= isize, "a bit too far");

        /* Make sure that we always have enough lookahead, except
         * at the end of the input file. We need MAX_MATCH bytes
         * for the next match, plus MIN_MATCH bytes to insert the
         * string following the next match.
         */
        if (lookahead < MIN_LOOKAHEAD) fill_window();
    }
    if (match_available) ct_tally (0, window[strstart-1]);

    return FLUSH_BLOCK(1); /* eof */
}
#endif /* !USE_ZLIB */