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_COMPRESSION_COMPRESS;
139
f->name = "compress";
147
archive_compressor_compress_open(struct archive_write_filter *f)
150
struct private_data *state;
152
f->code = ARCHIVE_COMPRESSION_COMPRESS;
153
f->name = "compress";
155
ret = __archive_write_open_filter(f->next_filter);
156
if (ret != ARCHIVE_OK)
159
state = (struct private_data *)calloc(1, sizeof(*state));
161
archive_set_error(f->archive, ENOMEM,
162
"Can't allocate data for compression");
163
return (ARCHIVE_FATAL);
166
state->compressed_buffer_size = 65536;
167
state->compressed = malloc(state->compressed_buffer_size);
169
if (state->compressed == NULL) {
170
archive_set_error(f->archive, ENOMEM,
171
"Can't allocate data for compression buffer");
173
return (ARCHIVE_FATAL);
176
f->write = archive_compressor_compress_write;
177
f->close = archive_compressor_compress_close;
178
f->free = archive_compressor_compress_free;
180
state->max_maxcode = 0x10000; /* Should NEVER generate this code. */
181
state->in_count = 0; /* Length of input. */
183
state->bit_offset = 0;
184
state->out_count = 3; /* Includes 3-byte header mojo. */
185
state->compress_ratio = 0;
186
state->checkpoint = CHECK_GAP;
188
state->cur_maxcode = MAXCODE(state->code_len);
189
state->first_free = FIRST;
191
memset(state->hashtab, 0xff, sizeof(state->hashtab));
193
/* Prime output buffer with a gzip header. */
194
state->compressed[0] = 0x1f; /* Compress */
195
state->compressed[1] = 0x9d;
196
state->compressed[2] = 0x90; /* Block mode, 16bit max */
197
state->compressed_offset = 3;
204
* Output the given code.
206
* code: A n_bits-bit integer. If == -1, then EOF. This assumes
207
* that n_bits <= (long)wordsize - 1.
209
* Outputs code to the file.
211
* Chars are 8 bits long.
213
* Maintain a BITS character long buffer (so that 8 codes will
214
* fit in it exactly). Use the VAX insv instruction to insert each
215
* code in turn. When the buffer fills up empty it and start over.
218
static const unsigned char rmask[9] =
219
{0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
222
output_byte(struct archive_write_filter *f, unsigned char c)
224
struct private_data *state = f->data;
226
state->compressed[state->compressed_offset++] = c;
229
if (state->compressed_buffer_size == state->compressed_offset) {
230
int ret = __archive_write_filter(f->next_filter,
231
state->compressed, state->compressed_buffer_size);
232
if (ret != ARCHIVE_OK)
233
return ARCHIVE_FATAL;
234
state->compressed_offset = 0;
241
output_code(struct archive_write_filter *f, int ocode)
243
struct private_data *state = f->data;
244
int bits, ret, clear_flg, bit_offset;
246
clear_flg = ocode == CLEAR;
249
* Since ocode is always >= 8 bits, only need to mask the first
252
bit_offset = state->bit_offset % 8;
253
state->bit_buf |= (ocode << bit_offset) & 0xff;
254
output_byte(f, state->bit_buf);
256
bits = state->code_len - (8 - bit_offset);
257
ocode >>= 8 - bit_offset;
258
/* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
260
output_byte(f, ocode & 0xff);
265
state->bit_offset += state->code_len;
266
state->bit_buf = ocode & rmask[bits];
267
if (state->bit_offset == state->code_len * 8)
268
state->bit_offset = 0;
271
* If the next entry is going to be too big for the ocode size,
272
* then increase it, if possible.
274
if (clear_flg || state->first_free > state->cur_maxcode) {
276
* Write the whole buffer, because the input side won't
277
* discover the size increase until after it has read it.
279
if (state->bit_offset > 0) {
280
while (state->bit_offset < state->code_len * 8) {
281
ret = output_byte(f, state->bit_buf);
282
if (ret != ARCHIVE_OK)
284
state->bit_offset += 8;
289
state->bit_offset = 0;
293
state->cur_maxcode = MAXCODE(state->code_len);
296
if (state->code_len == 16)
297
state->cur_maxcode = state->max_maxcode;
299
state->cur_maxcode = MAXCODE(state->code_len);
307
output_flush(struct archive_write_filter *f)
309
struct private_data *state = f->data;
312
/* At EOF, write the rest of the buffer. */
313
if (state->bit_offset % 8) {
314
state->code_len = (state->bit_offset % 8 + 7) / 8;
315
ret = output_byte(f, state->bit_buf);
316
if (ret != ARCHIVE_OK)
324
* Write data to the compressed stream.
327
archive_compressor_compress_write(struct archive_write_filter *f,
328
const void *buff, size_t length)
330
struct private_data *state = (struct private_data *)f->data;
334
const unsigned char *bp;
341
if (state->in_count == 0) {
342
state->cur_code = *bp++;
350
state->cur_fcode = (c << 16) + state->cur_code;
351
i = ((c << HSHIFT) ^ state->cur_code); /* Xor hashing. */
353
if (state->hashtab[i] == state->cur_fcode) {
354
state->cur_code = state->codetab[i];
357
if (state->hashtab[i] < 0) /* Empty slot. */
359
/* Secondary hash (after G. Knott). */
368
if (state->hashtab[i] == state->cur_fcode) {
369
state->cur_code = state->codetab[i];
372
if (state->hashtab[i] >= 0)
375
ret = output_code(f, state->cur_code);
376
if (ret != ARCHIVE_OK)
379
if (state->first_free < state->max_maxcode) {
380
state->codetab[i] = state->first_free++; /* code -> hashtable */
381
state->hashtab[i] = state->cur_fcode;
384
if (state->in_count < state->checkpoint)
387
state->checkpoint = state->in_count + CHECK_GAP;
389
if (state->in_count <= 0x007fffff)
390
ratio = state->in_count * 256 / state->out_count;
391
else if ((ratio = state->out_count / 256) == 0)
394
ratio = state->in_count / ratio;
396
if (ratio > state->compress_ratio)
397
state->compress_ratio = ratio;
399
state->compress_ratio = 0;
400
memset(state->hashtab, 0xff, sizeof(state->hashtab));
401
state->first_free = FIRST;
402
ret = output_code(f, CLEAR);
403
if (ret != ARCHIVE_OK)
413
* Finish the compression...
416
archive_compressor_compress_close(struct archive_write_filter *f)
418
struct private_data *state = (struct private_data *)f->data;
421
ret = output_code(f, state->cur_code);
422
if (ret != ARCHIVE_OK)
424
ret = output_flush(f);
425
if (ret != ARCHIVE_OK)
428
/* Write the last block */
429
ret = __archive_write_filter(f->next_filter,
430
state->compressed, state->compressed_offset);
432
ret2 = __archive_write_close_filter(f->next_filter);
435
free(state->compressed);
441
archive_compressor_compress_free(struct archive_write_filter *f)
443
(void)f; /* UNUSED */