www.pudn.com > gzip_win.zip > bits.c

/* bits.c -- output variable-length bit strings 
 * 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. 
 */ 
 
 
/* 
 *  PURPOSE 
 * 
 *      Output variable-length bit strings. Compression can be done 
 *      to a file or to memory. (The latter is not supported in this version.) 
 * 
 *  DISCUSSION 
 * 
 *      The PKZIP "deflate" file format interprets compressed file data 
 *      as a sequence of bits.  Multi-bit strings in the file may cross 
 *      byte boundaries without restriction. 
 * 
 *      The first bit of each byte is the low-order bit. 
 * 
 *      The routines in this file allow a variable-length bit value to 
 *      be output right-to-left (useful for literal values). For 
 *      left-to-right output (useful for code strings from the tree routines), 
 *      the bits must have been reversed first with bi_reverse(). 
 * 
 *      For in-memory compression, the compressed bit stream goes directly 
 *      into the requested output buffer. The input data is read in blocks 
 *      by the mem_read() function. The buffer is limited to 64K on 16 bit 
 *      machines. 
 * 
 *  INTERFACE 
 * 
 *      void bi_init (FILE *zipfile) 
 *          Initialize the bit string routines. 
 * 
 *      void send_bits (int value, int length) 
 *          Write out a bit string, taking the source bits right to 
 *          left. 
 * 
 *      int bi_reverse (int value, int length) 
 *          Reverse the bits of a bit string, taking the source bits left to 
 *          right and emitting them right to left. 
 * 
 *      void bi_windup (void) 
 *          Write out any remaining bits in an incomplete byte. 
 * 
 *      void copy_block(char *buf, unsigned len, int header) 
 *          Copy a stored block to the zip file, storing first the length and 
 *          its one's complement if requested. 
 * 
 */ 
 
#include "tailor.h" 
#include "gzip.h" 
#include "crypt.h" 
 
#ifdef DEBUG 
#  include  
#endif 
 
#ifdef RCSID 
static char rcsid[] = "$Id: bits.c,v 0.9 1993/06/11 10:16:58 jloup Exp $"; 
#endif 
 
/* =========================================================================== 
 * Local data used by the "bit string" routines. 
 */ 
 
local file_t zfile; /* output gzip file */ 
 
local unsigned short bi_buf; 
/* Output buffer. bits are inserted starting at the bottom (least significant 
 * bits). 
 */ 
 
#define Buf_size (8 * 2*sizeof(char)) 
/* Number of bits used within bi_buf. (bi_buf might be implemented on 
 * more than 16 bits on some systems.) 
 */ 
 
local int bi_valid; 
/* Number of valid bits in bi_buf.  All bits above the last valid bit 
 * are always zero. 
 */ 
 
int (*read_buf) OF((char *buf, unsigned size)); 
/* Current input function. Set to mem_read for in-memory compression */ 
 
#ifdef DEBUG 
  ulg bits_sent;   /* bit length of the compressed data */ 
#endif 
 
/* =========================================================================== 
 * Initialize the bit string routines. 
 */ 
void bi_init (zipfile) 
    file_t zipfile; /* output zip file, NO_FILE for in-memory compression */ 
{ 
    zfile  = zipfile; 
    bi_buf = 0; 
    bi_valid = 0; 
#ifdef DEBUG 
    bits_sent = 0L; 
#endif 
 
    /* Set the defaults for file compression. They are set by memcompress 
     * for in-memory compression. 
     */ 
    if (zfile != NO_FILE) { 
	read_buf  = file_read; 
    } 
} 
 
/* =========================================================================== 
 * Send a value on a given number of bits. 
 * IN assertion: length <= 16 and value fits in length bits. 
 */ 
void send_bits(value, length) 
    int value;  /* value to send */ 
    int length; /* number of bits */ 
{ 
#ifdef DEBUG 
    Tracev((stderr," l %2d v %4x ", length, value)); 
    Assert(length > 0 && length <= 15, "invalid length"); 
    bits_sent += (ulg)length; 
#endif 
    /* If not enough room in bi_buf, use (valid) bits from bi_buf and 
     * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 
     * unused bits in value. 
     */ 
    if (bi_valid > (int)Buf_size - length) { 
        bi_buf |= (value << bi_valid); 
        put_short(bi_buf); 
        bi_buf = (ush)value >> (Buf_size - bi_valid); 
        bi_valid += length - Buf_size; 
    } else { 
        bi_buf |= value << bi_valid; 
        bi_valid += length; 
    } 
} 
 
/* =========================================================================== 
 * Reverse the first len bits of a code, using straightforward code (a faster 
 * method would use a table) 
 * IN assertion: 1 <= len <= 15 
 */ 
unsigned bi_reverse(code, len) 
    unsigned code; /* the value to invert */ 
    int len;       /* its bit length */ 
{ 
    register unsigned res = 0; 
    do { 
        res |= code & 1; 
        code >>= 1, res <<= 1; 
    } while (--len > 0); 
    return res >> 1; 
} 
 
/* =========================================================================== 
 * Write out any remaining bits in an incomplete byte. 
 */ 
void bi_windup() 
{ 
    if (bi_valid > 8) { 
        put_short(bi_buf); 
    } else if (bi_valid > 0) { 
        put_byte(bi_buf); 
    } 
    bi_buf = 0; 
    bi_valid = 0; 
#ifdef DEBUG 
    bits_sent = (bits_sent+7) & ~7; 
#endif 
} 
 
/* =========================================================================== 
 * Copy a stored block to the zip file, storing first the length and its 
 * one's complement if requested. 
 */ 
void copy_block(buf, len, header) 
    char     *buf;    /* the input data */ 
    unsigned len;     /* its length */ 
    int      header;  /* true if block header must be written */ 
{ 
    bi_windup();              /* align on byte boundary */ 
 
    if (header) { 
        put_short((ush)len);    
        put_short((ush)~len); 
#ifdef DEBUG 
        bits_sent += 2*16; 
#endif 
    } 
#ifdef DEBUG 
    bits_sent += (ulg)len<<3; 
#endif 
    while (len--) { 
#ifdef CRYPT 
        int t; 
	if (key) zencode(*buf, t); 
#endif 
	put_byte(*buf++); 
    } 
}