2 * Copyright (c) 2008 Joerg Sonnenberger
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 * Copyright (c) 1985, 1986, 1992, 1993
28 * The Regents of the University of California. All rights reserved.
30 * This code is derived from software contributed to Berkeley by
31 * Diomidis Spinellis and James A. Woods, derived from original
32 * work by Spencer Thomas and Joseph Orost.
34 * Redistribution and use in source and binary forms, with or without
35 * modification, are permitted provided that the following conditions
37 * 1. Redistributions of source code must retain the above copyright
38 * notice, this list of conditions and the following disclaimer.
39 * 2. Redistributions in binary form must reproduce the above copyright
40 * notice, this list of conditions and the following disclaimer in the
41 * documentation and/or other materials provided with the distribution.
42 * 3. Neither the name of the University nor the names of its contributors
43 * may be used to endorse or promote products derived from this software
44 * without specific prior written permission.
46 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
47 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
50 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
51 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
52 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
53 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
54 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
55 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
59 #include "archive_platform.h"
61 __FBSDID("$FreeBSD: head/lib/libarchive/archive_write_set_compression_compress.c 201111 2009-12-28 03:33:05Z kientzle $");
74 #include "archive_private.h"
75 #include "archive_write_private.h"
77 #define HSIZE 69001 /* 95% occupancy */
78 #define HSHIFT 8 /* 8 - trunc(log2(HSIZE / 65536)) */
79 #define CHECK_GAP 10000 /* Ratio check interval. */
81 #define MAXCODE(bits) ((1 << (bits)) - 1)
84 * the next two codes should not be changed lightly, as they must not
85 * lie within the contiguous general code space.
87 #define FIRST 257 /* First free entry. */
88 #define CLEAR 256 /* Table clear output code. */
91 int64_t in_count, out_count, checkpoint;
93 int code_len; /* Number of bits/code. */
94 int cur_maxcode; /* Maximum code, given n_bits. */
95 int max_maxcode; /* Should NEVER generate this code. */
97 unsigned short codetab [HSIZE];
98 int first_free; /* First unused entry. */
101 int cur_code, cur_fcode;
104 unsigned char bit_buf;
106 unsigned char *compressed;
107 size_t compressed_buffer_size;
108 size_t compressed_offset;
111 static int archive_compressor_compress_open(struct archive_write_filter *);
112 static int archive_compressor_compress_write(struct archive_write_filter *,
113 const void *, size_t);
114 static int archive_compressor_compress_close(struct archive_write_filter *);
115 static int archive_compressor_compress_free(struct archive_write_filter *);
117 #if ARCHIVE_VERSION_NUMBER < 4000000
119 archive_write_set_compression_compress(struct archive *a)
121 __archive_write_filters_free(a);
122 return (archive_write_add_filter_compress(a));
127 * Add a compress filter to this write handle.
130 archive_write_add_filter_compress(struct archive *_a)
132 struct archive_write *a = (struct archive_write *)_a;
133 struct archive_write_filter *f = __archive_write_allocate_filter(_a);
135 archive_check_magic(&a->archive, ARCHIVE_WRITE_MAGIC,
136 ARCHIVE_STATE_NEW, "archive_write_add_filter_compress");
137 f->open = &archive_compressor_compress_open;
138 f->code = ARCHIVE_FILTER_COMPRESS;
139 f->name = "compress";
147 archive_compressor_compress_open(struct archive_write_filter *f)
149 struct private_data *state;
150 size_t bs = 65536, bpb;
152 f->code = ARCHIVE_FILTER_COMPRESS;
153 f->name = "compress";
155 state = (struct private_data *)calloc(1, sizeof(*state));
157 archive_set_error(f->archive, ENOMEM,
158 "Can't allocate data for compression");
159 return (ARCHIVE_FATAL);
162 if (f->archive->magic == ARCHIVE_WRITE_MAGIC) {
163 /* Buffer size should be a multiple number of the of bytes
164 * per block for performance. */
165 bpb = archive_write_get_bytes_per_block(f->archive);
171 state->compressed_buffer_size = bs;
172 state->compressed = malloc(state->compressed_buffer_size);
174 if (state->compressed == NULL) {
175 archive_set_error(f->archive, ENOMEM,
176 "Can't allocate data for compression buffer");
178 return (ARCHIVE_FATAL);
181 f->write = archive_compressor_compress_write;
182 f->close = archive_compressor_compress_close;
183 f->free = archive_compressor_compress_free;
185 state->max_maxcode = 0x10000; /* Should NEVER generate this code. */
186 state->in_count = 0; /* Length of input. */
188 state->bit_offset = 0;
189 state->out_count = 3; /* Includes 3-byte header mojo. */
190 state->compress_ratio = 0;
191 state->checkpoint = CHECK_GAP;
193 state->cur_maxcode = MAXCODE(state->code_len);
194 state->first_free = FIRST;
196 memset(state->hashtab, 0xff, sizeof(state->hashtab));
198 /* Prime output buffer with a gzip header. */
199 state->compressed[0] = 0x1f; /* Compress */
200 state->compressed[1] = 0x9d;
201 state->compressed[2] = 0x90; /* Block mode, 16bit max */
202 state->compressed_offset = 3;
209 * Output the given code.
211 * code: A n_bits-bit integer. If == -1, then EOF. This assumes
212 * that n_bits <= (long)wordsize - 1.
214 * Outputs code to the file.
216 * Chars are 8 bits long.
218 * Maintain a BITS character long buffer (so that 8 codes will
219 * fit in it exactly). Use the VAX insv instruction to insert each
220 * code in turn. When the buffer fills up empty it and start over.
223 static const unsigned char rmask[9] =
224 {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
227 output_byte(struct archive_write_filter *f, unsigned char c)
229 struct private_data *state = f->data;
231 state->compressed[state->compressed_offset++] = c;
234 if (state->compressed_buffer_size == state->compressed_offset) {
235 int ret = __archive_write_filter(f->next_filter,
236 state->compressed, state->compressed_buffer_size);
237 if (ret != ARCHIVE_OK)
238 return ARCHIVE_FATAL;
239 state->compressed_offset = 0;
246 output_code(struct archive_write_filter *f, int ocode)
248 struct private_data *state = f->data;
249 int bits, ret, clear_flg, bit_offset;
251 clear_flg = ocode == CLEAR;
254 * Since ocode is always >= 8 bits, only need to mask the first
257 bit_offset = state->bit_offset % 8;
258 state->bit_buf |= (ocode << bit_offset) & 0xff;
259 output_byte(f, state->bit_buf);
261 bits = state->code_len - (8 - bit_offset);
262 ocode >>= 8 - bit_offset;
263 /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
265 output_byte(f, ocode & 0xff);
270 state->bit_offset += state->code_len;
271 state->bit_buf = ocode & rmask[bits];
272 if (state->bit_offset == state->code_len * 8)
273 state->bit_offset = 0;
276 * If the next entry is going to be too big for the ocode size,
277 * then increase it, if possible.
279 if (clear_flg || state->first_free > state->cur_maxcode) {
281 * Write the whole buffer, because the input side won't
282 * discover the size increase until after it has read it.
284 if (state->bit_offset > 0) {
285 while (state->bit_offset < state->code_len * 8) {
286 ret = output_byte(f, state->bit_buf);
287 if (ret != ARCHIVE_OK)
289 state->bit_offset += 8;
294 state->bit_offset = 0;
298 state->cur_maxcode = MAXCODE(state->code_len);
301 if (state->code_len == 16)
302 state->cur_maxcode = state->max_maxcode;
304 state->cur_maxcode = MAXCODE(state->code_len);
312 output_flush(struct archive_write_filter *f)
314 struct private_data *state = f->data;
317 /* At EOF, write the rest of the buffer. */
318 if (state->bit_offset % 8) {
319 state->code_len = (state->bit_offset % 8 + 7) / 8;
320 ret = output_byte(f, state->bit_buf);
321 if (ret != ARCHIVE_OK)
329 * Write data to the compressed stream.
332 archive_compressor_compress_write(struct archive_write_filter *f,
333 const void *buff, size_t length)
335 struct private_data *state = (struct private_data *)f->data;
339 const unsigned char *bp;
346 if (state->in_count == 0) {
347 state->cur_code = *bp++;
355 state->cur_fcode = (c << 16) + state->cur_code;
356 i = ((c << HSHIFT) ^ state->cur_code); /* Xor hashing. */
358 if (state->hashtab[i] == state->cur_fcode) {
359 state->cur_code = state->codetab[i];
362 if (state->hashtab[i] < 0) /* Empty slot. */
364 /* Secondary hash (after G. Knott). */
373 if (state->hashtab[i] == state->cur_fcode) {
374 state->cur_code = state->codetab[i];
377 if (state->hashtab[i] >= 0)
380 ret = output_code(f, state->cur_code);
381 if (ret != ARCHIVE_OK)
384 if (state->first_free < state->max_maxcode) {
385 state->codetab[i] = state->first_free++; /* code -> hashtable */
386 state->hashtab[i] = state->cur_fcode;
389 if (state->in_count < state->checkpoint)
392 state->checkpoint = state->in_count + CHECK_GAP;
394 if (state->in_count <= 0x007fffff && state->out_count != 0)
395 ratio = (int)(state->in_count * 256 / state->out_count);
396 else if ((ratio = (int)(state->out_count / 256)) == 0)
399 ratio = (int)(state->in_count / ratio);
401 if (ratio > state->compress_ratio)
402 state->compress_ratio = ratio;
404 state->compress_ratio = 0;
405 memset(state->hashtab, 0xff, sizeof(state->hashtab));
406 state->first_free = FIRST;
407 ret = output_code(f, CLEAR);
408 if (ret != ARCHIVE_OK)
418 * Finish the compression...
421 archive_compressor_compress_close(struct archive_write_filter *f)
423 struct private_data *state = (struct private_data *)f->data;
426 ret = output_code(f, state->cur_code);
427 if (ret != ARCHIVE_OK)
429 ret = output_flush(f);
430 if (ret != ARCHIVE_OK)
433 /* Write the last block */
434 ret = __archive_write_filter(f->next_filter,
435 state->compressed, state->compressed_offset);
440 archive_compressor_compress_free(struct archive_write_filter *f)
442 struct private_data *state = (struct private_data *)f->data;
444 free(state->compressed);