From b637ae7030893ffdce1937553cdee2226f7642af Mon Sep 17 00:00:00 2001
From: Michael Gernoth <michael@gernoth.net>
Date: Tue, 3 Feb 2009 21:40:25 +0100
Subject: [PATCH 1/1] add possibly working compression algorithm

---
 rsb-lz.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 rsb-lz.h |  1 +
 2 files changed, 99 insertions(+)

diff --git a/rsb-lz.c b/rsb-lz.c
index 4dddd9b..2e50252 100644
--- a/rsb-lz.c
+++ b/rsb-lz.c
@@ -143,6 +143,104 @@ void lz_expand(struct data_in_s *data_in, struct data_out_s *data_out)
 	}
 }
 
+void set_next_bit(unsigned char *buf, unsigned int set, unsigned int *currbit) {
+	unsigned char *pos;
+	unsigned char bitpos;
+
+	if (set) {
+		pos = buf + ((*currbit) / 8);
+		bitpos = 0x80 >> ((*currbit) % 8);
+		*pos |= bitpos;
+	}
+
+	*currbit = *currbit + 1;
+}
+
+void write_bits(unsigned char *buf, unsigned int data, unsigned int bits, unsigned int *currbit) {
+	int i;
+	unsigned int bitpos;
+
+	bitpos = 1 << (bits - 1);
+
+	for (i = 0; i < bits; i++) {
+		set_next_bit(buf, data & bitpos, currbit);
+		bitpos >>= 1;
+	}
+}
+
+unsigned char *compress_lz(unsigned char *inbuf, int inlen, int *outlen)
+{
+	unsigned char *end = inbuf + inlen;
+	unsigned char *outbuf;
+	unsigned char window[1024];
+	int pos = 0;
+	int fill = 0;
+	unsigned int currbit = 0;
+	int offset;
+	int wordlen;
+	int found;
+	int i;
+
+	if ((outbuf = malloc((inlen * 2) + 4)) == NULL) {
+		perror("malloc");
+	}
+
+	*((unsigned int*)outbuf) = LZ_MAGIC;
+	currbit = 8 * 8;
+
+	while(inbuf < end) {
+		found = 0;
+		for (wordlen = 17; wordlen > 1; wordlen--) {
+			for (offset = 1; offset < ((fill < 1023) ? fill : 1023); offset++) {
+				if ((fill < 1023) &&
+				    (wordlen + offset > fill))
+					break;
+
+				for (i = 0; i < wordlen; i++) {
+					if (inbuf[i] != window[(offset + i) & 0x3ff]) {
+						break;
+					}
+				}
+				if (i == wordlen)
+					found = 1;
+			}
+			if (found)
+				break;
+		}
+
+		if (found) {
+			write_bits(outbuf, 0x00, 0x01, &currbit);
+			write_bits(outbuf, offset, 0x0a, &currbit);
+			write_bits(outbuf, wordlen - 1, 0x04, &currbit);
+			for (i = 0; i < wordlen; i++) {
+				window[pos] = *(inbuf + i);
+				pos = (pos + 1) & 0x3ff;
+			}
+			inbuf += wordlen;
+
+			if (fill < sizeof(window))
+				fill += wordlen;
+		} else {
+			write_bits(outbuf, 0x01, 0x01, &currbit);
+			write_bits(outbuf, *inbuf, 0x08, &currbit);
+			window[pos] = *inbuf;
+			pos = (pos + 1) & 0x3ff;
+			inbuf++;
+			if (fill < sizeof(window))
+				fill++;
+		}
+	}
+
+	write_bits(outbuf, 0x00, 0x01, &currbit);
+	write_bits(outbuf, 0x00, 0x0a, &currbit);
+
+	*outlen = (currbit / 8) + 1;
+
+	*((unsigned int*)(outbuf + 4)) = *outlen;
+
+	return outbuf;
+}
+
 /* Checksum is only used for the compressed firmware in 'firmware' */
 unsigned int crc_check(unsigned char *buf, unsigned int len, unsigned int magic)
 {
diff --git a/rsb-lz.h b/rsb-lz.h
index 767ceb9..442ec43 100644
--- a/rsb-lz.h
+++ b/rsb-lz.h
@@ -1,3 +1,4 @@
 #define LZ_MAGIC 0x6110beef
 
 void extract_lz_file(unsigned char *buf, unsigned char *name, unsigned char check_crc);
+unsigned char *compress_lz(unsigned char *inbuf, int inlen, int *outlen);
-- 
2.39.5