bits.c

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