/* minor edits by CNGSOFT to allow command line parameters *
 * and to fuse both encoder and decoder into a single file */

/* benchmark: FIRMWARE.MAN, 286982 bytes: 75225 / 75255 (-c) / 121307 (-C) / 121306 (-c -C) */

/*
 * (c) Copyright 2012-2016 by Einar Saukas. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * 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.
 *     * The name of its author may not be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 <COPYRIGHT HOLDER> 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 <stdio.h>
#include <stdlib.h>
#include <string.h>

/****** zx7.h ******/

int MAX_OFFSET = 2176; /* range 1..2176 */
int MIN_OFFSET =  128; /* 2176=2048+128 */
int MAX_BITS =     16; /* log_2 (65536) */
int MAX_LEN  =  1<<16; /* size 2..65536 */

int flag_v = 0; // verbose

typedef struct optimal_t {
	size_t bits;
	int offset;
	int len;
} Optimal;


unsigned char *output_data;
size_t output_index;

size_t input_index;

int bit_mask;

/****** optimize.c ******/

int count_bits(int offset, int len) {
	offset = offset > MIN_OFFSET ? 1+12+1 : 1+8+1;
	while (len > 1) {
		offset += 2;
		len >>= 1;
	}
	return offset; // elias_gamma_bits
}

Optimal* optimize(unsigned char *input_data, size_t input_size) {
	size_t *min;
	size_t *max;
	size_t *matches;
	size_t *match_slots;
	Optimal *optimal;
	size_t *match;
	int match_index;
	int offset;
	size_t len;
	size_t best_len;
	size_t bits;
	size_t i;

	/* allocate all data structures at once */
	min = (size_t *)calloc(MAX_OFFSET+1, sizeof(size_t));
	max = (size_t *)calloc(MAX_OFFSET+1, sizeof(size_t));
	matches = (size_t *)calloc(256*256, sizeof(size_t));
	match_slots = (size_t *)calloc(input_size, sizeof(size_t));
	optimal = (Optimal *)calloc(input_size, sizeof(Optimal));

	if (!min || !max || !matches || !match_slots || !optimal) {
		 fprintf(stderr, "error: out of memory!\n");
		 exit(1);
	}

	/* first byte is always literal */
	optimal[0].bits = 8;

	/* process remaining bytes */
	for (i = 1; i < input_size; i++) {
		if (!(i&511)) fprintf(stderr, "%02i%%\010\010\010", (100*i)/input_size); // patch 20161105: waiting...
		int opt_i_offset = 0, opt_i_len = 0, opt_i_bits = optimal[i-1].bits + 9;
		match_index = input_data[i-1] << 8 | input_data[i];
		best_len = 1;
		for (match = &matches[match_index]; *match && (best_len < MAX_LEN); match = &match_slots[*match]) {
			offset = i - *match;
			if (offset > MAX_OFFSET) {
				*match = 0;
				break;
			}
			for (len = 2; len <= MAX_LEN && i >= len; len++) {
				if (len > best_len) {
					best_len = len;
					bits = optimal[i-len].bits + count_bits(offset, len-1);
					if (opt_i_bits > bits) {
						opt_i_bits = bits;
						opt_i_offset = offset;
						opt_i_len = len;
					}
				} else if (max[offset] && (i+1 == max[offset]+len)) {
					len = i-min[offset];
					if (len > best_len) {
						len = best_len;
					}
				}
				if (i < offset+len || input_data[i-len] != input_data[i-len-offset]) {
					break;
				}
			}
			min[offset] = i+1-len;
			max[offset] = i;
		}
		optimal[i].bits = opt_i_bits;
		optimal[i].offset = opt_i_offset;
		optimal[i].len = opt_i_len;
		match_slots[i] = matches[match_index];
		matches[match_index] = i;
	}

	///* save time by releasing the largest block only, the O.S. will clean everything else later */
	//free(match_slots);

	return optimal;
}

/****** compress.c ******/

size_t bit_index;
int diff;

#define read_bytes(n, delta) { diff += n; if (diff > *delta) *delta=diff; }
#define encode_byte(value) { output_data[output_index++] = (value); diff--; }

void encode_bit(int value) {
	if (!bit_mask) {
		bit_mask = 1<<7;
		bit_index = output_index;
		encode_byte(0);
	}
	if (value > 0) {
		output_data[bit_index] |= bit_mask;
	}
	bit_mask >>= 1;
}

void write_elias_gamma(int value) {
	int i;

	for (i = 2; i <= value; i <<= 1) {
		encode_bit(0);
	}
	while ((i >>= 1) > 0) {
		encode_bit(value & i);
	}
}

unsigned char *compress(Optimal *optimal, unsigned char *input_data, size_t input_size, size_t *output_size, int *delta) {
	size_t input_prev;
	int offset1;
	int mask;
	int i;

	/* calculate and allocate output buffer */
	input_index = input_size-1;
	*output_size = (optimal[input_index].bits + 2 + MAX_BITS + 7) / 8;
	output_data = (unsigned char *)malloc(*output_size);
	if (!output_data) {
		 fprintf(stderr, "error: out of memory!\n");
		 exit(1);
	}

	/* initialize delta */
	diff = *output_size - input_size;
	*delta = 0;

	/* un-reverse optimal sequence */
	optimal[input_index].bits = 0;
	while (input_index > 0) {
		input_prev = input_index - (optimal[input_index].len > 0 ? optimal[input_index].len : 1);
		optimal[input_prev].bits = input_index;
		input_index = input_prev;
	}

	output_index = 0;
	bit_mask = 0;

	/* first byte is always literal */
	encode_byte(input_data[0]);
	read_bytes(1, delta);

	/* process remaining bytes */
	while ((input_index = optimal[input_index].bits) > 0) {
		if (!optimal[input_index].len) {
			if (flag_v)
				printf(".");

			/* literal indicator */
			encode_bit(0);

			/* literal value */
			encode_byte(input_data[input_index]);
			read_bytes(1, delta);

		} else {
			if (flag_v)
				printf("%i,%i\n",optimal[input_index].len,optimal[input_index].offset);

			/* sequence indicator */
			encode_bit(1);

			/* sequence length */
			write_elias_gamma(optimal[input_index].len-1);

			/* sequence offset */
			offset1 = optimal[input_index].offset-1;
			if (offset1 < MIN_OFFSET) {
				encode_byte(offset1);
			} else {
				offset1 -= 128;
				encode_byte(offset1 | 128);
				for (mask = 1024; mask >= 128; mask >>= 1) {
					encode_bit(offset1 & mask);
				}
			}
			read_bytes(optimal[input_index].len, delta);
		}
	}

	/* sequence indicator */
	encode_bit(1);
	/* end marker > MAX_LEN */
	for (i = 0; i < MAX_BITS; i++)
		encode_bit(0);
	encode_bit(1);

	return output_data;
}

/****** dzx7.c ******/

int BUFFER_SIZE = 1<<14; /* must be > MAX_OFFSET */

unsigned char *input_buffer;

size_t input_length;

int bit_value;

#define read_byte() (input_buffer[input_index++])
	/*if (input_index == input_length ) {
		fprintf(stderr, "error: truncated source!\n");
	}*/

int read_bit() {
	bit_mask >>= 1;
	if (!bit_mask) {
		bit_mask = 1<<7;
		bit_value = read_byte();
	}
	return bit_value & bit_mask ? 1 : 0;
}

int read_elias_gamma() {
	int i;
	int value;

	i = 0;
	while (!read_bit()) {
		i++;
	}
	if (i == MAX_BITS) {
		return -1;
	}
	value = 1;
	while (i--) {
		value = value << 1 | read_bit();
	}
	return value;
}

int read_offset() {
	int value;
	int i;

	value = read_byte();
	if (value < MIN_OFFSET) {
		return value;
	} else {
		i = read_bit();
		i = i << 1 | read_bit();
		i = i << 1 | read_bit();
		i = i << 1 | read_bit();
		return value + (i << 7);
	}
}

void decode_byte(int value) {
	output_data[output_index++] = value;
	if (output_index == BUFFER_SIZE) {
		BUFFER_SIZE <<= 1;
		output_data = (unsigned char*)realloc(output_data, BUFFER_SIZE);
	}
}

void decode_bytes(int offset, int length) {
	if (offset > output_index) {
		fprintf(stderr, "error: invalid data at offset %u!\n", (unsigned int)offset);
		exit(1);
	}
	int i = output_index-offset;
	while (length-- > 0) {
		decode_byte(output_data[i]);
		i++;
	}
}

unsigned char *decompress(unsigned char *input_data, size_t input_size, size_t *output_size) {

	int length;

	output_data = (unsigned char *)malloc(BUFFER_SIZE);
	if (!output_data) {
		fprintf(stderr, "error: out of memory!\n");
		exit(1);
	}

	input_length = input_size;
	input_buffer = input_data;
	input_index = 0;
	output_index = 0;
	bit_mask = 0;

	decode_byte(read_byte());

	while (input_index<input_size) {
		if (!read_bit()) {
			if (flag_v)
				printf(".");
			decode_byte(read_byte());
		} else {
			length = read_elias_gamma()+1;
			if (!length) {
				*output_size = output_index;
				return output_data;
			} else
			{
				int offset=read_offset()+1;
				if (flag_v)
					printf("%i,%i\n",length,offset);
				decode_bytes(offset, length);
			}
		}
	}
	fprintf(stderr, "warning: data underflow\n");
	*output_size = output_index;
	return output_data;
}

/****** zx7.c ******/

char *input_name;
char *output_name;

FILE *ifp;
FILE *ofp;

unsigned char *input_data;

//size_t partial_counter;
//size_t total_counter;
size_t input_size;
size_t output_size;

int delta;

void reverse(unsigned char *buffer, size_t size) {
	size_t i=0;
	size_t j=size;
	while (i<j) {
		int k=buffer[i];
		buffer[i++]=buffer[--j];
		buffer[j]=k;
	}
}

int main(int argc, char *argv[]) {
	int flag_b=0, flag_d=0, i;

	for (i=1;i<argc;i++)
		if (!strcmp(argv[i],"-b")) { flag_b=1; } else
		if (!strcmp(argv[i],"-d")) { flag_d=1; } else
		if (!strcmp(argv[i],"-c")) { MAX_BITS=8; MAX_LEN=  256; } else
		if (!strcmp(argv[i],"-C")) { MAX_OFFSET=MIN_OFFSET=256; } else
		if (!strcmp(argv[i],"-v")) { flag_v=1; } else
		if (!input_name) { input_name=argv[i]; } else
		if (!output_name) { output_name=argv[i]; }
	if (!output_name) {
		fprintf(stderr, "(c) Copyright 2012-2015 by Einar Saukas. All rights reserved.\nUsage: %s [option...] source target\n"
			"  -d  decrunch\t  -b  backwards\t  -v  verbose\n"
			"  -c  short sequences\t  -C  short distances\n"
			,argv[0]);
		exit(1);
	}

	/* open input file */
	ifp = fopen(input_name, "rb");
	if (!ifp) {
		fprintf(stderr, "error: cannot open source!\n");
		exit(1);
	}

	/* determine input size */
	fseek(ifp, 0L, SEEK_END);
	input_size = ftell(ifp);
	fseek(ifp, 0L, SEEK_SET);
	/*if (!input_size) {
		fprintf(stderr, "error: empty source!\n");
		exit(1);
	}*/

	/* allocate input buffer */
	input_data = (unsigned char *)malloc(input_size);
	if (!input_data) {
		fprintf(stderr, "error: out of memory!\n");
		exit(1);
	}

	/* read input file */
	//total_counter = 0;
	//do {
		//partial_counter =+total_counter-total_counter
			fread(input_data, sizeof(char), input_size, ifp);
		//total_counter += partial_counter;
	//} while (partial_counter > 0);

	/*if (total_counter != input_size) {
		fprintf(stderr, "error: cannot read source!\n");
		exit(1);
	}*/

	/* close input file */
	fclose(ifp);

	if (flag_b)
		reverse(input_data, input_size);

	if (flag_d)
		/* generate output file */
		output_data = decompress(input_data, input_size, &output_size);
	else
		/* generate output file */
		output_data = compress(optimize(input_data, input_size), input_data, input_size, &output_size, &delta);

	/* done! */
	printf("Optimal LZ77/LZSS compression by Einar Saukas\nFile converted from %u to %u bytes! (%g%%",
		(unsigned int)input_size, (unsigned int)output_size, (100.0*output_size)/input_size);
	if (!flag_d)
		printf(", delta %d", delta);
	printf(")\n");

	if (flag_b)
		reverse(output_data, output_size);

	/* check output file */
	//if (fopen(output_name, "rb") != NULL) {
		//fprintf(stderr, "error: already existing output file!\n");
		//exit(1);
	//}

	/* create output file */
	ofp = fopen(output_name, "wb");
	if (!ofp) {
		fprintf(stderr, "error: cannot create target!\n");
		exit(1);
	}

	/* write output file */
	//total_counter = 0;
	//do {
		//partial_counter =+total_counter-total_counter
			fwrite(output_data, sizeof(char), output_size, ofp);
		//total_counter += partial_counter;
	//} while (partial_counter > 0);

	/*if ( total_counter != output_size) {
		fprintf(stderr, "error: cannot write target!\n");
		exit(1);
	}*/

	/* close output file */
	fclose(ofp);

	return 0;
}
