usr/gzip/bits.c

/* bits.c -- output variable-length bit strings
 * Copyright (C) 1992-1993 Jean-loup Gailly
 * This is free software; you can redistribute it and/or modify it under the
 * terms of the GNU General Public License, see the file COPYING.
 */


/*
 *  PURPOSE
 *
 *      Output variable-length bit strings. Compression can be done
 *      to a file or to memory. (The latter is not supported in this version.)
 *
 *  DISCUSSION
 *
 *      The PKZIP "deflate" file format interprets compressed file data
 *      as a sequence of bits.  Multi-bit strings in the file may cross
 *      byte boundaries without restriction.
 *
 *      The first bit of each byte is the low-order bit.
 *
 *      The routines in this file allow a variable-length bit value to
 *      be output right-to-left (useful for literal values). For
 *      left-to-right output (useful for code strings from the tree routines),
 *      the bits must have been reversed first with bi_reverse().
 *
 *      For in-memory compression, the compressed bit stream goes directly
 *      into the requested output buffer. The input data is read in blocks
 *      by the mem_read() function. The buffer is limited to 64K on 16 bit
 *      machines.
 *
 *  INTERFACE
 *
 *      void bi_init (FILE *zipfile)
 *          Initialize the bit string routines.
 *
 *      void send_bits (int value, int length)
 *          Write out a bit string, taking the source bits right to
 *          left.
 *
 *      int bi_reverse (int value, int length)
 *          Reverse the bits of a bit string, taking the source bits left to
 *          right and emitting them right to left.
 *
 *      void bi_windup (void)
 *          Write out any remaining bits in an incomplete byte.
 *
 *      void copy_block(char *buf, unsigned len, int header)
 *          Copy a stored block to the zip file, storing first the length and
 *          its one's complement if requested.
 *
 */

#include "tailor.h"
#include "gzip.h"

#ifdef DEBUG
#  include <stdio.h>
#endif

#ifdef RCSID
static char rcsid[] = "$Id: bits.c,v 1.1 2002/08/18 00:59:21 hpa Exp $";
#endif

/* ===========================================================================
 * Local data used by the "bit string" routines.
 */

local file_t zfile; /* output gzip file */

local unsigned short bi_buf;
/* Output buffer. bits are inserted starting at the bottom (least significant
 * bits).
 */

#define Buf_size (8 * 2*sizeof(char))
/* Number of bits used within bi_buf. (bi_buf might be implemented on
 * more than 16 bits on some systems.)
 */

local int bi_valid;
/* Number of valid bits in bi_buf.  All bits above the last valid bit
 * are always zero.
 */

int (*read_buf) OF((char *buf, unsigned size));
/* Current input function. Set to mem_read for in-memory compression */

#ifdef DEBUG
  ulg bits_sent;   /* bit length of the compressed data */
#endif

/* ===========================================================================
 * Initialize the bit string routines.
 */
void bi_init (zipfile)
    file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
{
    zfile  = zipfile;
    bi_buf = 0;
    bi_valid = 0;
#ifdef DEBUG
    bits_sent = 0L;
#endif

    /* Set the defaults for file compression. They are set by memcompress
     * for in-memory compression.
     */
    if (zfile != NO_FILE) {
	read_buf  = file_read;
    }
}

/* ===========================================================================
 * Send a value on a given number of bits.
 * IN assertion: length <= 16 and value fits in length bits.
 */
void send_bits(value, length)
    int value;  /* value to send */
    int length; /* number of bits */
{
#ifdef DEBUG
    Tracev((stderr," l %2d v %4x ", length, value));
    Assert(length > 0 && length <= 15, "invalid length");
    bits_sent += (ulg)length;
#endif
    /* If not enough room in bi_buf, use (valid) bits from bi_buf and
     * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
     * unused bits in value.
     */
    if (bi_valid > (int)Buf_size - length) {
        bi_buf |= (value << bi_valid);
        put_short(bi_buf);
        bi_buf = (ush)value >> (Buf_size - bi_valid);
        bi_valid += length - Buf_size;
    } else {
        bi_buf |= value << bi_valid;
        bi_valid += length;
    }
}

/* ===========================================================================
 * Reverse the first len bits of a code, using straightforward code (a faster
 * method would use a table)
 * IN assertion: 1 <= len <= 15
 */
unsigned bi_reverse(code, len)
    unsigned code; /* the value to invert */
    int len;       /* its bit length */
{
    register unsigned res = 0;
    do {
        res |= code & 1;
        code >>= 1, res <<= 1;
    } while (--len > 0);
    return res >> 1;
}

/* ===========================================================================
 * Write out any remaining bits in an incomplete byte.
 */
void bi_windup()
{
    if (bi_valid > 8) {
        put_short(bi_buf);
    } else if (bi_valid > 0) {
        put_byte(bi_buf);
    }
    bi_buf = 0;
    bi_valid = 0;
#ifdef DEBUG
    bits_sent = (bits_sent+7) & ~7;
#endif
}

/* ===========================================================================
 * Copy a stored block to the zip file, storing first the length and its
 * one's complement if requested.
 */
void copy_block(buf, len, header)
    char     *buf;    /* the input data */
    unsigned len;     /* its length */
    int      header;  /* true if block header must be written */
{
    bi_windup();              /* align on byte boundary */

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