bits.c

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