/*-

 * Copyright (c) 2008 Joerg Sonnenberger

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR

 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,

 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

/*-

 * Copyright (c) 1985, 1986, 1992, 1993

 *	The Regents of the University of California.  All rights reserved.

 *

 * This code is derived from software contributed to Berkeley by

 * Diomidis Spinellis and James A. Woods, derived from original

 * work by Spencer Thomas and Joseph Orost.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 * 3. Neither the name of the University nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND

 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE

 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

 * SUCH DAMAGE.

 */

#include "archive_platform.h"

__FBSDID("$FreeBSD: head/lib/libarchive/archive_write_set_compression_compress.c 201111 2009-12-28 03:33:05Z kientzle $");

#ifdef HAVE_ERRNO_H

#include <errno.h>

#endif

#ifdef HAVE_STDLIB_H

#include <stdlib.h>

#endif

#ifdef HAVE_STRING_H

#include <string.h>

#endif

#include "archive.h"

#include "archive_private.h"

#include "archive_write_private.h"

#define	HSIZE		69001	/* 95% occupancy */

#define	HSHIFT		8	/* 8 - trunc(log2(HSIZE / 65536)) */

#define	CHECK_GAP 10000		/* Ratio check interval. */

#define	MAXCODE(bits)	((1 << (bits)) - 1)

/*

 * the next two codes should not be changed lightly, as they must not

 * lie within the contiguous general code space.

 */

#define	FIRST	257		/* First free entry. */

#define	CLEAR	256		/* Table clear output code. */

struct private_data {

	int64_t in_count, out_count, checkpoint;

	int code_len;			/* Number of bits/code. */

	int cur_maxcode;		/* Maximum code, given n_bits. */

	int max_maxcode;		/* Should NEVER generate this code. */

	int hashtab [HSIZE];

	unsigned short codetab [HSIZE];

	int first_free;		/* First unused entry. */

	int compress_ratio;

	int cur_code, cur_fcode;

	int bit_offset;

	unsigned char bit_buf;

	unsigned char	*compressed;

	size_t		 compressed_buffer_size;

	size_t		 compressed_offset;

};

static int archive_compressor_compress_open(struct archive_write_filter *);

static int archive_compressor_compress_write(struct archive_write_filter *,

		    const void *, size_t);

static int archive_compressor_compress_close(struct archive_write_filter *);

static int archive_compressor_compress_free(struct archive_write_filter *);

#if ARCHIVE_VERSION_NUMBER < 4000000

int

archive_write_set_compression_compress(struct archive *a)

{

	__archive_write_filters_free(a);

	return (archive_write_add_filter_compress(a));

}

#endif

/*

 * Add a compress filter to this write handle.

 */

int

archive_write_add_filter_compress(struct archive *_a)

{

	struct archive_write *a = (struct archive_write *)_a;

	struct archive_write_filter *f = __archive_write_allocate_filter(_a);

	archive_check_magic(&a->archive, ARCHIVE_WRITE_MAGIC,

	    ARCHIVE_STATE_NEW, "archive_write_add_filter_compress");

	f->open = &archive_compressor_compress_open;

	f->code = ARCHIVE_FILTER_COMPRESS;

	f->name = "compress";

	return (ARCHIVE_OK);

}

/*

 * Setup callback.

 */

static int

archive_compressor_compress_open(struct archive_write_filter *f)

{

	int ret;

	struct private_data *state;

	size_t bs = 65536, bpb;

	f->code = ARCHIVE_FILTER_COMPRESS;

	f->name = "compress";

	ret = __archive_write_open_filter(f->next_filter);

	if (ret != ARCHIVE_OK)

		return (ret);

	state = (struct private_data *)calloc(1, sizeof(*state));

	if (state == NULL) {

		archive_set_error(f->archive, ENOMEM,

		    "Can't allocate data for compression");

		return (ARCHIVE_FATAL);

	}

	if (f->archive->magic == ARCHIVE_WRITE_MAGIC) {

		/* Buffer size should be a multiple number of the of bytes

		 * per block for performance. */

		bpb = archive_write_get_bytes_per_block(f->archive);

		if (bpb > bs)

			bs = bpb;

		else if (bpb != 0)

			bs -= bs % bpb;

	}

	state->compressed_buffer_size = bs;

	state->compressed = malloc(state->compressed_buffer_size);

	if (state->compressed == NULL) {

		archive_set_error(f->archive, ENOMEM,

		    "Can't allocate data for compression buffer");

		free(state);

		return (ARCHIVE_FATAL);

	}

	f->write = archive_compressor_compress_write;

	f->close = archive_compressor_compress_close;

	f->free = archive_compressor_compress_free;

	state->max_maxcode = 0x10000;	/* Should NEVER generate this code. */

	state->in_count = 0;		/* Length of input. */

	state->bit_buf = 0;

	state->bit_offset = 0;

	state->out_count = 3;		/* Includes 3-byte header mojo. */

	state->compress_ratio = 0;

	state->checkpoint = CHECK_GAP;

	state->code_len = 9;

	state->cur_maxcode = MAXCODE(state->code_len);

	state->first_free = FIRST;

	memset(state->hashtab, 0xff, sizeof(state->hashtab));

	/* Prime output buffer with a gzip header. */

	state->compressed[0] = 0x1f; /* Compress */

	state->compressed[1] = 0x9d;

	state->compressed[2] = 0x90; /* Block mode, 16bit max */

	state->compressed_offset = 3;

	f->data = state;

	return (0);

}

/*-

 * Output the given code.

 * Inputs:

 * 	code:	A n_bits-bit integer.  If == -1, then EOF.  This assumes

 *		that n_bits <= (long)wordsize - 1.

 * Outputs:

 * 	Outputs code to the file.

 * Assumptions:

 *	Chars are 8 bits long.

 * Algorithm:

 * 	Maintain a BITS character long buffer (so that 8 codes will

 * fit in it exactly).  Use the VAX insv instruction to insert each

 * code in turn.  When the buffer fills up empty it and start over.

 */

static const unsigned char rmask[9] =

	{0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};

static int

output_byte(struct archive_write_filter *f, unsigned char c)

{

	struct private_data *state = f->data;

	state->compressed[state->compressed_offset++] = c;

	++state->out_count;

	if (state->compressed_buffer_size == state->compressed_offset) {

		int ret = __archive_write_filter(f->next_filter,

		    state->compressed, state->compressed_buffer_size);

		if (ret != ARCHIVE_OK)

			return ARCHIVE_FATAL;

		state->compressed_offset = 0;

	}

	return ARCHIVE_OK;

}

static int

output_code(struct archive_write_filter *f, int ocode)

{

	struct private_data *state = f->data;

	int bits, ret, clear_flg, bit_offset;

	clear_flg = ocode == CLEAR;

	/*

	 * Since ocode is always >= 8 bits, only need to mask the first

	 * hunk on the left.

	 */

	bit_offset = state->bit_offset % 8;

	state->bit_buf |= (ocode << bit_offset) & 0xff;

	output_byte(f, state->bit_buf);

	bits = state->code_len - (8 - bit_offset);

	ocode >>= 8 - bit_offset;

	/* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */

	if (bits >= 8) {

		output_byte(f, ocode & 0xff);

		ocode >>= 8;

		bits -= 8;

	}

	/* Last bits. */

	state->bit_offset += state->code_len;

	state->bit_buf = ocode & rmask[bits];

	if (state->bit_offset == state->code_len * 8)

		state->bit_offset = 0;

	/*

	 * If the next entry is going to be too big for the ocode size,

	 * then increase it, if possible.

	 */

	if (clear_flg || state->first_free > state->cur_maxcode) {

	       /*

		* Write the whole buffer, because the input side won't

		* discover the size increase until after it has read it.

		*/

		if (state->bit_offset > 0) {

			while (state->bit_offset < state->code_len * 8) {

				ret = output_byte(f, state->bit_buf);

				if (ret != ARCHIVE_OK)

					return ret;

				state->bit_offset += 8;

				state->bit_buf = 0;

			}

		}

		state->bit_buf = 0;

		state->bit_offset = 0;

		if (clear_flg) {

			state->code_len = 9;

			state->cur_maxcode = MAXCODE(state->code_len);

		} else {

			state->code_len++;

			if (state->code_len == 16)

				state->cur_maxcode = state->max_maxcode;

			else

				state->cur_maxcode = MAXCODE(state->code_len);

		}

	}

	return (ARCHIVE_OK);

}

static int

output_flush(struct archive_write_filter *f)

{

	struct private_data *state = f->data;

	int ret;

	/* At EOF, write the rest of the buffer. */

	if (state->bit_offset % 8) {

		state->code_len = (state->bit_offset % 8 + 7) / 8;

		ret = output_byte(f, state->bit_buf);

		if (ret != ARCHIVE_OK)

			return ret;

	}

	return (ARCHIVE_OK);

}

/*

 * Write data to the compressed stream.

 */

static int

archive_compressor_compress_write(struct archive_write_filter *f,

    const void *buff, size_t length)

{

	struct private_data *state = (struct private_data *)f->data;

	int i;

	int ratio;

	int c, disp, ret;

	const unsigned char *bp;

	if (length == 0)

		return ARCHIVE_OK;

	bp = buff;

	if (state->in_count == 0) {

		state->cur_code = *bp++;

		++state->in_count;

		--length;

	}

	while (length--) {

		c = *bp++;

		state->in_count++;

		state->cur_fcode = (c << 16) + state->cur_code;

		i = ((c << HSHIFT) ^ state->cur_code);	/* Xor hashing. */

		if (state->hashtab[i] == state->cur_fcode) {

			state->cur_code = state->codetab[i];

			continue;

		}

		if (state->hashtab[i] < 0)	/* Empty slot. */

			goto nomatch;

		/* Secondary hash (after G. Knott). */

		if (i == 0)

			disp = 1;

		else

			disp = HSIZE - i;

 probe:

		if ((i -= disp) < 0)

			i += HSIZE;

		if (state->hashtab[i] == state->cur_fcode) {

			state->cur_code = state->codetab[i];

			continue;

		}

		if (state->hashtab[i] >= 0)

			goto probe;

 nomatch:

		ret = output_code(f, state->cur_code);

		if (ret != ARCHIVE_OK)

			return ret;

		state->cur_code = c;

		if (state->first_free < state->max_maxcode) {

			state->codetab[i] = state->first_free++;	/* code -> hashtable */

			state->hashtab[i] = state->cur_fcode;

			continue;

		}

		if (state->in_count < state->checkpoint)

			continue;

		state->checkpoint = state->in_count + CHECK_GAP;

		if (state->in_count <= 0x007fffff && state->out_count != 0)

			ratio = (int)(state->in_count * 256 / state->out_count);

		else if ((ratio = (int)(state->out_count / 256)) == 0)

			ratio = 0x7fffffff;

		else

			ratio = (int)(state->in_count / ratio);

		if (ratio > state->compress_ratio)

			state->compress_ratio = ratio;

		else {

			state->compress_ratio = 0;

			memset(state->hashtab, 0xff, sizeof(state->hashtab));

			state->first_free = FIRST;

			ret = output_code(f, CLEAR);

			if (ret != ARCHIVE_OK)

				return ret;

		}

	}

	return (ARCHIVE_OK);

}

/*

 * Finish the compression...

 */

static int

archive_compressor_compress_close(struct archive_write_filter *f)

{

	struct private_data *state = (struct private_data *)f->data;

	int ret, ret2;

	ret = output_code(f, state->cur_code);

	if (ret != ARCHIVE_OK)

		goto cleanup;

	ret = output_flush(f);

	if (ret != ARCHIVE_OK)

		goto cleanup;

	/* Write the last block */

	ret = __archive_write_filter(f->next_filter,

	    state->compressed, state->compressed_offset);

cleanup:

	ret2 = __archive_write_close_filter(f->next_filter);

	if (ret > ret2)

		ret = ret2;

	free(state->compressed);

	free(state);

	return (ret);

}

static int

archive_compressor_compress_free(struct archive_write_filter *f)

{

	(void)f; /* UNUSED */

	return (ARCHIVE_OK);

}