maint: update to latest gnulib; use fdutimens, not gl_futimens
[gzip.git] / bits.c
blob57fb0d4ef920cf463579f6dab1c210c29205798e
1 /* bits.c -- output variable-length bit strings
3 Copyright (C) 1999, 2009-2010 Free Software Foundation, Inc.
4 Copyright (C) 1992-1993 Jean-loup Gailly
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.
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.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software Foundation,
18 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
22 * PURPOSE
24 * Output variable-length bit strings. Compression can be done
25 * to a file or to memory. (The latter is not supported in this version.)
27 * DISCUSSION
29 * The PKZIP "deflate" file format interprets compressed file data
30 * as a sequence of bits. Multi-bit strings in the file may cross
31 * byte boundaries without restriction.
33 * The first bit of each byte is the low-order bit.
35 * The routines in this file allow a variable-length bit value to
36 * be output right-to-left (useful for literal values). For
37 * left-to-right output (useful for code strings from the tree routines),
38 * the bits must have been reversed first with bi_reverse().
40 * For in-memory compression, the compressed bit stream goes directly
41 * into the requested output buffer. The input data is read in blocks
42 * by the mem_read() function. The buffer is limited to 64K on 16 bit
43 * machines.
45 * INTERFACE
47 * void bi_init (FILE *zipfile)
48 * Initialize the bit string routines.
50 * void send_bits (int value, int length)
51 * Write out a bit string, taking the source bits right to
52 * left.
54 * int bi_reverse (int value, int length)
55 * Reverse the bits of a bit string, taking the source bits left to
56 * right and emitting them right to left.
58 * void bi_windup (void)
59 * Write out any remaining bits in an incomplete byte.
61 * void copy_block(char *buf, unsigned len, int header)
62 * Copy a stored block to the zip file, storing first the length and
63 * its one's complement if requested.
67 #include <config.h>
68 #include "tailor.h"
69 #include "gzip.h"
70 #include "crypt.h"
72 #ifdef DEBUG
73 # include <stdio.h>
74 #endif
76 /* ===========================================================================
77 * Local data used by the "bit string" routines.
80 local file_t zfile; /* output gzip file */
82 local unsigned short bi_buf;
83 /* Output buffer. bits are inserted starting at the bottom (least significant
84 * bits).
87 #define Buf_size (8 * 2*sizeof(char))
88 /* Number of bits used within bi_buf. (bi_buf might be implemented on
89 * more than 16 bits on some systems.)
92 local int bi_valid;
93 /* Number of valid bits in bi_buf. All bits above the last valid bit
94 * are always zero.
97 int (*read_buf) OF((char *buf, unsigned size));
98 /* Current input function. Set to mem_read for in-memory compression */
100 #ifdef DEBUG
101 off_t bits_sent; /* bit length of the compressed data */
102 #endif
104 /* ===========================================================================
105 * Initialize the bit string routines.
107 void bi_init (zipfile)
108 file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
110 zfile = zipfile;
111 bi_buf = 0;
112 bi_valid = 0;
113 #ifdef DEBUG
114 bits_sent = 0L;
115 #endif
117 /* Set the defaults for file compression. They are set by memcompress
118 * for in-memory compression.
120 if (zfile != NO_FILE) {
121 read_buf = file_read;
125 /* ===========================================================================
126 * Send a value on a given number of bits.
127 * IN assertion: length <= 16 and value fits in length bits.
129 void send_bits(value, length)
130 int value; /* value to send */
131 int length; /* number of bits */
133 #ifdef DEBUG
134 Tracev((stderr," l %2d v %4x ", length, value));
135 Assert(length > 0 && length <= 15, "invalid length");
136 bits_sent += (off_t)length;
137 #endif
138 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
139 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
140 * unused bits in value.
142 if (bi_valid > (int)Buf_size - length) {
143 bi_buf |= (value << bi_valid);
144 put_short(bi_buf);
145 bi_buf = (ush)value >> (Buf_size - bi_valid);
146 bi_valid += length - Buf_size;
147 } else {
148 bi_buf |= value << bi_valid;
149 bi_valid += length;
153 /* ===========================================================================
154 * Reverse the first len bits of a code, using straightforward code (a faster
155 * method would use a table)
156 * IN assertion: 1 <= len <= 15
158 unsigned bi_reverse(code, len)
159 unsigned code; /* the value to invert */
160 int len; /* its bit length */
162 register unsigned res = 0;
163 do {
164 res |= code & 1;
165 code >>= 1, res <<= 1;
166 } while (--len > 0);
167 return res >> 1;
170 /* ===========================================================================
171 * Write out any remaining bits in an incomplete byte.
173 void bi_windup()
175 if (bi_valid > 8) {
176 put_short(bi_buf);
177 } else if (bi_valid > 0) {
178 put_byte(bi_buf);
180 bi_buf = 0;
181 bi_valid = 0;
182 #ifdef DEBUG
183 bits_sent = (bits_sent+7) & ~7;
184 #endif
187 /* ===========================================================================
188 * Copy a stored block to the zip file, storing first the length and its
189 * one's complement if requested.
191 void copy_block(buf, len, header)
192 char *buf; /* the input data */
193 unsigned len; /* its length */
194 int header; /* true if block header must be written */
196 bi_windup(); /* align on byte boundary */
198 if (header) {
199 put_short((ush)len);
200 put_short((ush)~len);
201 #ifdef DEBUG
202 bits_sent += 2*16;
203 #endif
205 #ifdef DEBUG
206 bits_sent += (off_t)len<<3;
207 #endif
208 while (len--) {
209 #ifdef CRYPT
210 int t;
211 if (key) zencode(*buf, t);
212 #endif
213 put_byte(*buf++);