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