gnu/usr.bin/gzip/bits.c

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