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