home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / gzip124.zip / gzip-1.2.4 / bits.c < prev    next >
C/C++ Source or Header  |  1993-08-13  |  6KB  |  206 lines
  1. /* bits.c -- output variable-length bit strings
  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.  
  8. /*
  9.  *  PURPOSE
  10.  *
  11.  *      Output variable-length bit strings. Compression can be done
  12.  *      to a file or to memory. (The latter is not supported in this version.)
  13.  *
  14.  *  DISCUSSION
  15.  *
  16.  *      The PKZIP "deflate" file format interprets compressed file data
  17.  *      as a sequence of bits.  Multi-bit strings in the file may cross
  18.  *      byte boundaries without restriction.
  19.  *
  20.  *      The first bit of each byte is the low-order bit.
  21.  *
  22.  *      The routines in this file allow a variable-length bit value to
  23.  *      be output right-to-left (useful for literal values). For
  24.  *      left-to-right output (useful for code strings from the tree routines),
  25.  *      the bits must have been reversed first with bi_reverse().
  26.  *
  27.  *      For in-memory compression, the compressed bit stream goes directly
  28.  *      into the requested output buffer. The input data is read in blocks
  29.  *      by the mem_read() function. The buffer is limited to 64K on 16 bit
  30.  *      machines.
  31.  *
  32.  *  INTERFACE
  33.  *
  34.  *      void bi_init (FILE *zipfile)
  35.  *          Initialize the bit string routines.
  36.  *
  37.  *      void send_bits (int value, int length)
  38.  *          Write out a bit string, taking the source bits right to
  39.  *          left.
  40.  *
  41.  *      int bi_reverse (int value, int length)
  42.  *          Reverse the bits of a bit string, taking the source bits left to
  43.  *          right and emitting them right to left.
  44.  *
  45.  *      void bi_windup (void)
  46.  *          Write out any remaining bits in an incomplete byte.
  47.  *
  48.  *      void copy_block(char *buf, unsigned len, int header)
  49.  *          Copy a stored block to the zip file, storing first the length and
  50.  *          its one's complement if requested.
  51.  *
  52.  */
  53.  
  54. #include "tailor.h"
  55. #include "gzip.h"
  56. #include "crypt.h"
  57.  
  58. #ifdef DEBUG
  59. #  include <stdio.h>
  60. #endif
  61.  
  62. #ifdef RCSID
  63. static char rcsid[] = "$Id: bits.c,v 0.9 1993/06/11 10:16:58 jloup Exp $";
  64. #endif
  65.  
  66. /* ===========================================================================
  67.  * Local data used by the "bit string" routines.
  68.  */
  69.  
  70. local file_t zfile; /* output gzip file */
  71.  
  72. local unsigned short bi_buf;
  73. /* Output buffer. bits are inserted starting at the bottom (least significant
  74.  * bits).
  75.  */
  76.  
  77. #define Buf_size (8 * 2*sizeof(char))
  78. /* Number of bits used within bi_buf. (bi_buf might be implemented on
  79.  * more than 16 bits on some systems.)
  80.  */
  81.  
  82. local int bi_valid;
  83. /* Number of valid bits in bi_buf.  All bits above the last valid bit
  84.  * are always zero.
  85.  */
  86.  
  87. int (*read_buf) OF((char *buf, unsigned size));
  88. /* Current input function. Set to mem_read for in-memory compression */
  89.  
  90. #ifdef DEBUG
  91.   ulg bits_sent;   /* bit length of the compressed data */
  92. #endif
  93.  
  94. /* ===========================================================================
  95.  * Initialize the bit string routines.
  96.  */
  97. void bi_init (zipfile)
  98.     file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
  99. {
  100.     zfile  = zipfile;
  101.     bi_buf = 0;
  102.     bi_valid = 0;
  103. #ifdef DEBUG
  104.     bits_sent = 0L;
  105. #endif
  106.  
  107.     /* Set the defaults for file compression. They are set by memcompress
  108.      * for in-memory compression.
  109.      */
  110.     if (zfile != NO_FILE) {
  111.     read_buf  = file_read;
  112.     }
  113. }
  114.  
  115. /* ===========================================================================
  116.  * Send a value on a given number of bits.
  117.  * IN assertion: length <= 16 and value fits in length bits.
  118.  */
  119. void send_bits(value, length)
  120.     int value;  /* value to send */
  121.     int length; /* number of bits */
  122. {
  123. #ifdef DEBUG
  124.     Tracev((stderr," l %2d v %4x ", length, value));
  125.     Assert(length > 0 && length <= 15, "invalid length");
  126.     bits_sent += (ulg)length;
  127. #endif
  128.     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
  129.      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
  130.      * unused bits in value.
  131.      */
  132.     if (bi_valid > (int)Buf_size - length) {
  133.         bi_buf |= (value << bi_valid);
  134.         put_short(bi_buf);
  135.         bi_buf = (ush)value >> (Buf_size - bi_valid);
  136.         bi_valid += length - Buf_size;
  137.     } else {
  138.         bi_buf |= value << bi_valid;
  139.         bi_valid += length;
  140.     }
  141. }
  142.  
  143. /* ===========================================================================
  144.  * Reverse the first len bits of a code, using straightforward code (a faster
  145.  * method would use a table)
  146.  * IN assertion: 1 <= len <= 15
  147.  */
  148. unsigned bi_reverse(code, len)
  149.     unsigned code; /* the value to invert */
  150.     int len;       /* its bit length */
  151. {
  152.     register unsigned res = 0;
  153.     do {
  154.         res |= code & 1;
  155.         code >>= 1, res <<= 1;
  156.     } while (--len > 0);
  157.     return res >> 1;
  158. }
  159.  
  160. /* ===========================================================================
  161.  * Write out any remaining bits in an incomplete byte.
  162.  */
  163. void bi_windup()
  164. {
  165.     if (bi_valid > 8) {
  166.         put_short(bi_buf);
  167.     } else if (bi_valid > 0) {
  168.         put_byte(bi_buf);
  169.     }
  170.     bi_buf = 0;
  171.     bi_valid = 0;
  172. #ifdef DEBUG
  173.     bits_sent = (bits_sent+7) & ~7;
  174. #endif
  175. }
  176.  
  177. /* ===========================================================================
  178.  * Copy a stored block to the zip file, storing first the length and its
  179.  * one's complement if requested.
  180.  */
  181. void copy_block(buf, len, header)
  182.     char     *buf;    /* the input data */
  183.     unsigned len;     /* its length */
  184.     int      header;  /* true if block header must be written */
  185. {
  186.     bi_windup();              /* align on byte boundary */
  187.  
  188.     if (header) {
  189.         put_short((ush)len);   
  190.         put_short((ush)~len);
  191. #ifdef DEBUG
  192.         bits_sent += 2*16;
  193. #endif
  194.     }
  195. #ifdef DEBUG
  196.     bits_sent += (ulg)len<<3;
  197. #endif
  198.     while (len--) {
  199. #ifdef CRYPT
  200.         int t;
  201.     if (key) zencode(*buf, t);
  202. #endif
  203.     put_byte(*buf++);
  204.     }
  205. }
  206.