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.
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 $
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.)
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.
22 * The first bit of each byte is the low-order bit.
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().
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
36 * void bi_init (FILE *zipfile)
37 * Initialize the bit string routines.
39 * void send_bits (int value, int length)
40 * Write out a bit string, taking the source bits right to
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.
47 * void bi_windup (void)
48 * Write out any remaining bits in an incomplete byte.
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.
64 /* ===========================================================================
65 * Local data used by the "bit string" routines.
68 local file_t zfile; /* output gzip file */
70 local unsigned short bi_buf;
71 /* Output buffer. bits are inserted starting at the bottom (least significant
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.)
81 /* Number of valid bits in bi_buf. All bits above the last valid bit
85 int (*read_buf) OF((char *buf, unsigned size));
86 /* Current input function. Set to mem_read for in-memory compression */
89 ulg bits_sent; /* bit length of the compressed data */
92 /* ===========================================================================
93 * Initialize the bit string routines.
95 void bi_init (zipfile)
96 file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
105 /* Set the defaults for file compression. They are set by memcompress
106 * for in-memory compression.
108 if (zfile != NO_FILE) {
109 read_buf = file_read;
113 /* ===========================================================================
114 * Send a value on a given number of bits.
115 * IN assertion: length <= 16 and value fits in length bits.
117 void send_bits(value, length)
118 int value; /* value to send */
119 int length; /* number of bits */
122 Tracev((stderr," l %2d v %4x ", length, value));
123 Assert(length > 0 && length <= 15, "invalid length");
124 bits_sent += (ulg)length;
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.
130 if (bi_valid > (int)Buf_size - length) {
131 bi_buf |= (value << bi_valid);
133 bi_buf = (ush)value >> (Buf_size - bi_valid);
134 bi_valid += length - Buf_size;
136 bi_buf |= value << bi_valid;
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
146 unsigned bi_reverse(code, len)
147 unsigned code; /* the value to invert */
148 int len; /* its bit length */
150 register unsigned res = 0;
153 code >>= 1, res <<= 1;
158 /* ===========================================================================
159 * Write out any remaining bits in an incomplete byte.
165 } else if (bi_valid > 0) {
171 bits_sent = (bits_sent+7) & ~7;
175 /* ===========================================================================
176 * Copy a stored block to the zip file, storing first the length and its
177 * one's complement if requested.
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 */
184 bi_windup(); /* align on byte boundary */
188 put_short((ush)~len);
194 bits_sent += (ulg)len<<3;
199 if (key) zencode(*buf, t);