1 /*-
2 * Copyright (c) 2008 Joerg Sonnenberger
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
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.
13 *
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.
24 */
25
26 /*-
27 * Copyright (c) 1985, 1986, 1992, 1993
28 * The Regents of the University of California. All rights reserved.
29 *
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.
33 *
34 * Redistribution and use in source and binary forms, with or without
35 * modification, are permitted provided that the following conditions
36 * are met:
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.
45 *
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
56 * SUCH DAMAGE.
57 */
58
59 #include "archive_platform.h"
60
61 #ifdef HAVE_ERRNO_H
62 #include <errno.h>
63 #endif
64 #ifdef HAVE_STDLIB_H
65 #include <stdlib.h>
66 #endif
67 #ifdef HAVE_STRING_H
68 #include <string.h>
69 #endif
70
71 #include "archive.h"
72 #include "archive_private.h"
73 #include "archive_write_private.h"
74
75 #define HSIZE 69001 /* 95% occupancy */
76 #define HSHIFT 8 /* 8 - trunc(log2(HSIZE / 65536)) */
77 #define CHECK_GAP 10000 /* Ratio check interval. */
78
79 #define MAXCODE(bits) ((1 << (bits)) - 1)
80
81 /*
82 * the next two codes should not be changed lightly, as they must not
83 * lie within the contiguous general code space.
84 */
85 #define FIRST 257 /* First free entry. */
86 #define CLEAR 256 /* Table clear output code. */
87
88 struct compress {
89 int64_t in_count, out_count, checkpoint;
90
91 int code_len; /* Number of bits/code. */
92 int cur_maxcode; /* Maximum code, given n_bits. */
93 int max_maxcode; /* Should NEVER generate this code. */
94 int hashtab [HSIZE];
95 unsigned short codetab [HSIZE];
96 int first_free; /* First unused entry. */
97 int compress_ratio;
98
99 int cur_code, cur_fcode;
100
101 int bit_offset;
102 unsigned char bit_buf;
103
104 unsigned char *compressed;
105 size_t compressed_buffer_size;
106 size_t compressed_offset;
107 };
108
109 static int archive_compressor_compress_open(struct archive_write_filter *);
110 static int archive_compressor_compress_write(struct archive_write_filter *,
111 const void *, size_t);
112 static int archive_compressor_compress_close(struct archive_write_filter *);
113 static int archive_compressor_compress_free(struct archive_write_filter *);
114 static void free_data(struct compress *);
115
116 #if ARCHIVE_VERSION_NUMBER < 4000000
117 int
archive_write_set_compression_compress(struct archive * a)118 archive_write_set_compression_compress(struct archive *a)
119 {
120 __archive_write_filters_free(a);
121 return (archive_write_add_filter_compress(a));
122 }
123 #endif
124
125 /*
126 * Add a compress filter to this write handle.
127 */
128 int
archive_write_add_filter_compress(struct archive * a)129 archive_write_add_filter_compress(struct archive *a)
130 {
131 struct archive_write_filter *f;
132 struct compress *compress;
133
134 archive_check_magic(a, ARCHIVE_WRITE_MAGIC,
135 ARCHIVE_STATE_NEW, "archive_write_add_filter_compress");
136
137 compress = calloc(1, sizeof(*compress));
138 if (compress == NULL)
139 goto memerr;
140
141 f = __archive_write_allocate_filter(a);
142 if (f == NULL)
143 goto memerr;
144 f->name = "compress";
145 f->code = ARCHIVE_FILTER_COMPRESS;
146 f->data = compress;
147 f->open = archive_compressor_compress_open;
148 f->write = archive_compressor_compress_write;
149 f->close = archive_compressor_compress_close;
150 f->free = archive_compressor_compress_free;
151
152 return (ARCHIVE_OK);
153 memerr:
154 free_data(compress);
155 archive_set_error(a, ENOMEM,
156 "Can't allocate data for compression");
157 return (ARCHIVE_FATAL);
158 }
159
160 /*
161 * Setup callback.
162 */
163 static int
archive_compressor_compress_open(struct archive_write_filter * f)164 archive_compressor_compress_open(struct archive_write_filter *f)
165 {
166 struct compress *compress = f->data;
167 size_t bs = 65536, bpb;
168
169 if (f->archive->magic == ARCHIVE_WRITE_MAGIC) {
170 /* Buffer size should be a multiple number of the bytes
171 * per block for performance. */
172 bpb = archive_write_get_bytes_per_block(f->archive);
173 if (bpb > bs)
174 bs = bpb;
175 else if (bpb != 0)
176 bs -= bs % bpb;
177 }
178 compress->compressed_buffer_size = bs;
179 compress->compressed = malloc(compress->compressed_buffer_size);
180
181 if (compress->compressed == NULL) {
182 archive_set_error(f->archive, ENOMEM,
183 "Can't allocate data for compression buffer");
184 return (ARCHIVE_FATAL);
185 }
186
187 /* Should NEVER generate this code. */
188 compress->max_maxcode = 0x10000;
189 /* Length of input. */
190 compress->in_count = 0;
191 compress->bit_buf = 0;
192 compress->bit_offset = 0;
193 /* Includes 3-byte header mojo. */
194 compress->out_count = 3;
195 compress->compress_ratio = 0;
196 compress->checkpoint = CHECK_GAP;
197 compress->code_len = 9;
198 compress->cur_maxcode = MAXCODE(compress->code_len);
199 compress->first_free = FIRST;
200
201 memset(compress->hashtab, 0xff, sizeof(compress->hashtab));
202
203 /* Prime output buffer with a gzip header. */
204 compress->compressed[0] = 0x1f; /* Compress */
205 compress->compressed[1] = 0x9d;
206 compress->compressed[2] = 0x90; /* Block mode, 16bit max */
207 compress->compressed_offset = 3;
208
209 return (ARCHIVE_OK);
210 }
211
212 /*-
213 * Output the given code.
214 * Inputs:
215 * code: A n_bits-bit integer. If == -1, then EOF. This assumes
216 * that n_bits <= (long)wordsize - 1.
217 * Outputs:
218 * Outputs code to the file.
219 * Assumptions:
220 * Chars are 8 bits long.
221 * Algorithm:
222 * Maintain a BITS character long buffer (so that 8 codes will
223 * fit in it exactly). Use the VAX insv instruction to insert each
224 * code in turn. When the buffer fills up empty it and start over.
225 */
226
227 static const unsigned char rmask[9] =
228 {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
229
230 static int
output_byte(struct archive_write_filter * f,unsigned char c)231 output_byte(struct archive_write_filter *f, unsigned char c)
232 {
233 struct compress *compress = f->data;
234
235 compress->compressed[compress->compressed_offset++] = c;
236 ++compress->out_count;
237
238 if (compress->compressed_buffer_size == compress->compressed_offset) {
239 int ret = __archive_write_filter(f->next_filter,
240 compress->compressed, compress->compressed_buffer_size);
241 if (ret != ARCHIVE_OK)
242 return ARCHIVE_FATAL;
243 compress->compressed_offset = 0;
244 }
245
246 return ARCHIVE_OK;
247 }
248
249 static int
output_code(struct archive_write_filter * f,int ocode)250 output_code(struct archive_write_filter *f, int ocode)
251 {
252 struct compress *compress = f->data;
253 int bits, ret, clear_flg, bit_offset;
254
255 clear_flg = ocode == CLEAR;
256
257 /*
258 * Since ocode is always >= 8 bits, only need to mask the first
259 * hunk on the left.
260 */
261 bit_offset = compress->bit_offset % 8;
262 compress->bit_buf |= (ocode << bit_offset) & 0xff;
263 output_byte(f, compress->bit_buf);
264
265 bits = compress->code_len - (8 - bit_offset);
266 ocode >>= 8 - bit_offset;
267 /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
268 if (bits >= 8) {
269 output_byte(f, ocode & 0xff);
270 ocode >>= 8;
271 bits -= 8;
272 }
273 /* Last bits. */
274 compress->bit_offset += compress->code_len;
275 compress->bit_buf = ocode & rmask[bits];
276 if (compress->bit_offset == compress->code_len * 8)
277 compress->bit_offset = 0;
278
279 /*
280 * If the next entry is going to be too big for the ocode size,
281 * then increase it, if possible.
282 */
283 if (clear_flg || compress->first_free > compress->cur_maxcode) {
284 /*
285 * Write the whole buffer, because the input side won't
286 * discover the size increase until after it has read it.
287 */
288 if (compress->bit_offset > 0) {
289 while (compress->bit_offset < compress->code_len * 8) {
290 ret = output_byte(f, compress->bit_buf);
291 if (ret != ARCHIVE_OK)
292 return ret;
293 compress->bit_offset += 8;
294 compress->bit_buf = 0;
295 }
296 }
297 compress->bit_buf = 0;
298 compress->bit_offset = 0;
299
300 if (clear_flg) {
301 compress->code_len = 9;
302 compress->cur_maxcode = MAXCODE(compress->code_len);
303 } else {
304 compress->code_len++;
305 if (compress->code_len == 16)
306 compress->cur_maxcode = compress->max_maxcode;
307 else
308 compress->cur_maxcode = MAXCODE(compress->code_len);
309 }
310 }
311
312 return (ARCHIVE_OK);
313 }
314
315 static int
output_flush(struct archive_write_filter * f)316 output_flush(struct archive_write_filter *f)
317 {
318 struct compress *compress = f->data;
319 int ret;
320
321 /* At EOF, write the rest of the buffer. */
322 if (compress->bit_offset % 8) {
323 compress->code_len = (compress->bit_offset % 8 + 7) / 8;
324 ret = output_byte(f, compress->bit_buf);
325 if (ret != ARCHIVE_OK)
326 return ret;
327 }
328
329 return (ARCHIVE_OK);
330 }
331
332 /*
333 * Write data to the compressed stream.
334 */
335 static int
archive_compressor_compress_write(struct archive_write_filter * f,const void * buff,size_t length)336 archive_compressor_compress_write(struct archive_write_filter *f,
337 const void *buff, size_t length)
338 {
339 struct compress *compress = f->data;
340 int i;
341 int ratio;
342 int c, disp, ret;
343 const unsigned char *bp;
344
345 if (length == 0)
346 return ARCHIVE_OK;
347
348 bp = buff;
349
350 if (compress->in_count == 0) {
351 compress->cur_code = *bp++;
352 ++compress->in_count;
353 --length;
354 }
355
356 while (length--) {
357 c = *bp++;
358 compress->in_count++;
359 compress->cur_fcode = (c << 16) | compress->cur_code;
360 /* Xor hashing. */
361 i = ((c << HSHIFT) ^ compress->cur_code);
362
363 if (compress->hashtab[i] == compress->cur_fcode) {
364 compress->cur_code = compress->codetab[i];
365 continue;
366 }
367 if (compress->hashtab[i] < 0) /* Empty slot. */
368 goto nomatch;
369 /* Secondary hash (after G. Knott). */
370 if (i == 0)
371 disp = 1;
372 else
373 disp = HSIZE - i;
374 probe:
375 if ((i -= disp) < 0)
376 i += HSIZE;
377
378 if (compress->hashtab[i] == compress->cur_fcode) {
379 compress->cur_code = compress->codetab[i];
380 continue;
381 }
382 if (compress->hashtab[i] >= 0)
383 goto probe;
384 nomatch:
385 ret = output_code(f, compress->cur_code);
386 if (ret != ARCHIVE_OK)
387 return ret;
388 compress->cur_code = c;
389 if (compress->first_free < compress->max_maxcode) {
390 compress->codetab[i] = compress->first_free++; /* code -> hashtable */
391 compress->hashtab[i] = compress->cur_fcode;
392 continue;
393 }
394 if (compress->in_count < compress->checkpoint)
395 continue;
396
397 compress->checkpoint = compress->in_count + CHECK_GAP;
398
399 if (compress->in_count <= 0x007fffff && compress->out_count != 0)
400 ratio = (int)(compress->in_count * 256 / compress->out_count);
401 else if ((ratio = (int)(compress->out_count / 256)) == 0)
402 ratio = 0x7fffffff;
403 else
404 ratio = (int)(compress->in_count / ratio);
405
406 if (ratio > compress->compress_ratio)
407 compress->compress_ratio = ratio;
408 else {
409 compress->compress_ratio = 0;
410 memset(compress->hashtab, 0xff, sizeof(compress->hashtab));
411 compress->first_free = FIRST;
412 ret = output_code(f, CLEAR);
413 if (ret != ARCHIVE_OK)
414 return ret;
415 }
416 }
417
418 return (ARCHIVE_OK);
419 }
420
421
422 /*
423 * Finish the compression...
424 */
425 static int
archive_compressor_compress_close(struct archive_write_filter * f)426 archive_compressor_compress_close(struct archive_write_filter *f)
427 {
428 struct compress *compress = f->data;
429 int ret;
430
431 ret = output_code(f, compress->cur_code);
432 if (ret != ARCHIVE_OK)
433 return ret;
434 ret = output_flush(f);
435 if (ret != ARCHIVE_OK)
436 return ret;
437
438 /* Write the last block */
439 ret = __archive_write_filter(f->next_filter,
440 compress->compressed, compress->compressed_offset);
441 return (ret);
442 }
443
444 static int
archive_compressor_compress_free(struct archive_write_filter * f)445 archive_compressor_compress_free(struct archive_write_filter *f)
446 {
447 free_data(f->data);
448 f->data = NULL;
449 return (ARCHIVE_OK);
450 }
451
452 static void
free_data(struct compress * compress)453 free_data(struct compress *compress)
454 {
455 if (compress != NULL) {
456 free(compress->compressed);
457 free(compress);
458 }
459 }
460