git.cworth.org Git - gzip/blob - 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
   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 <config.h>
  55 #include "tailor.h"
  56 #include "gzip.h"
  57 #include "crypt.h"
  58
  59 #ifdef DEBUG
  60 #  include <stdio.h>
  61 #endif
  62
  63 #ifdef RCSID
  64 static char rcsid[] = "$Id: bits.c,v 0.9 1993/06/11 10:16:58 jloup Exp $";
  65 #endif
  66
  67 /* ===========================================================================
  68  * Local data used by the "bit string" routines.
  69  */
  70
  71 local file_t zfile; /* output gzip file */
  72
  73 local unsigned short bi_buf;
  74 /* Output buffer. bits are inserted starting at the bottom (least significant
  75  * bits).
  76  */
  77
  78 #define Buf_size (8 * 2*sizeof(char))
  79 /* Number of bits used within bi_buf. (bi_buf might be implemented on
  80  * more than 16 bits on some systems.)
  81  */
  82
  83 local int bi_valid;
  84 /* Number of valid bits in bi_buf.  All bits above the last valid bit
  85  * are always zero.
  86  */
  87
  88 int (*read_buf) OF((char *buf, unsigned size));
  89 /* Current input function. Set to mem_read for in-memory compression */
  90
  91 #ifdef DEBUG
  92   off_t bits_sent;   /* bit length of the compressed data */
  93 #endif
  94
  95 /* ===========================================================================
  96  * Initialize the bit string routines.
  97  */
  98 void bi_init (zipfile)
  99     file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
 100 {
 101     zfile  = zipfile;
 102     bi_buf = 0;
 103     bi_valid = 0;
 104 #ifdef DEBUG
 105     bits_sent = 0L;
 106 #endif
 107
 108     /* Set the defaults for file compression. They are set by memcompress
 109      * for in-memory compression.
 110      */
 111     if (zfile != NO_FILE) {
 112         read_buf  = file_read;
 113     }
 114 }
 115
 116 /* ===========================================================================
 117  * Send a value on a given number of bits.
 118  * IN assertion: length <= 16 and value fits in length bits.
 119  */
 120 void send_bits(value, length)
 121     int value;  /* value to send */
 122     int length; /* number of bits */
 123 {
 124 #ifdef DEBUG
 125     Tracev((stderr," l %2d v %4x ", length, value));
 126     Assert(length > 0 && length <= 15, "invalid length");
 127     bits_sent += (off_t)length;
 128 #endif
 129     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
 130      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
 131      * unused bits in value.
 132      */
 133     if (bi_valid > (int)Buf_size - length) {
 134         bi_buf |= (value << bi_valid);
 135         put_short(bi_buf);
 136         bi_buf = (ush)value >> (Buf_size - bi_valid);
 137         bi_valid += length - Buf_size;
 138     } else {
 139         bi_buf |= value << bi_valid;
 140         bi_valid += length;
 141     }
 142 }
 143
 144 /* ===========================================================================
 145  * Reverse the first len bits of a code, using straightforward code (a faster
 146  * method would use a table)
 147  * IN assertion: 1 <= len <= 15
 148  */
 149 unsigned bi_reverse(code, len)
 150     unsigned code; /* the value to invert */
 151     int len;       /* its bit length */
 152 {
 153     register unsigned res = 0;
 154     do {
 155         res |= code & 1;
 156         code >>= 1, res <<= 1;
 157     } while (--len > 0);
 158     return res >> 1;
 159 }
 160
 161 /* ===========================================================================
 162  * Write out any remaining bits in an incomplete byte.
 163  */
 164 void bi_windup()
 165 {
 166     if (bi_valid > 8) {
 167         put_short(bi_buf);
 168     } else if (bi_valid > 0) {
 169         put_byte(bi_buf);
 170     }
 171     bi_buf = 0;
 172     bi_valid = 0;
 173 #ifdef DEBUG
 174     bits_sent = (bits_sent+7) & ~7;
 175 #endif
 176 }
 177
 178 /* ===========================================================================
 179  * Copy a stored block to the zip file, storing first the length and its
 180  * one's complement if requested.
 181  */
 182 void copy_block(buf, len, header)
 183     char     *buf;    /* the input data */
 184     unsigned len;     /* its length */
 185     int      header;  /* true if block header must be written */
 186 {
 187     bi_windup();              /* align on byte boundary */
 188
 189     if (header) {
 190         put_short((ush)len);
 191         put_short((ush)~len);
 192 #ifdef DEBUG
 193         bits_sent += 2*16;
 194 #endif
 195     }
 196 #ifdef DEBUG
 197     bits_sent += (off_t)len<<3;
 198 #endif
 199     while (len--) {
 200 #ifdef CRYPT
 201         int t;
 202         if (key) zencode(*buf, t);
 203 #endif
 204         put_byte(*buf++);
 205     }
 206 }