Added icecompr

7 files changed, 566 insertions, 0 deletions

diff --git a/icecompr/.gitignore b/icecompr/.gitignore
new file mode 100644
index 0000000..1ebf48a
--- /dev/null
+++ b/icecompr/.gitignore
@@ -0,0 +1,5 @@
+icecompr
+iceuncompr
+example_?k.compr
+example_?k.ok
+example_?k.uncompr
diff --git a/icecompr/Makefile b/icecompr/Makefile
new file mode 100644
index 0000000..88512f0
--- /dev/null
+++ b/icecompr/Makefile
@@ -0,0 +1,31 @@
+
+all: icecompr iceuncompr
+
+test: example_1k.ok example_8k.ok
+
+icecompr: icecompr.cc
+	clang++ -o icecompr -Wall -Wextra -std=c++11 icecompr.cc
+
+iceuncompr: iceuncompr.c
+	clang -o iceuncompr -Wall -Wextra iceuncompr.c
+
+%.compr: %.bin icecompr
+	./icecompr -v $< $@
+	
+
+%.uncompr: %.compr iceuncompr
+	./iceuncompr $< $@
+
+%.ok: %.uncompr %.bin
+	cmp $^
+	touch $@
+
+clean:
+	rm -f icecompr iceuncompr
+	rm -f example_1k.compr example_8k.compr
+	rm -f example_1k.uncompr example_8k.uncompr
+	rm -f example_1k.ok example_8k.ok
+
+.SECONDARY:
+.PHONY: all test clean
+
diff --git a/icecompr/README b/icecompr/README
new file mode 100644
index 0000000..5e04bb5
--- /dev/null
+++ b/icecompr/README
@@ -0,0 +1,52 @@
+
+A simple compression algorithm for iCE40 bit-streams
+====================================================
+
+This directory contains tools for compressing and uncompressing
+iCE40 bit-streams. The motivation is to reduce the bandwidth
+requirements for bit-stream upload.
+
+Note that iCE40 FPGAs can not uncompress this compressed bit-streams!
+Uncompression must be performed by e.g. a uC on the FPGA board.
+
+This compression algorithm uses the fact that most bits in an iCE40
+bit-stream are cleared.
+
+The bit-stream is encoded as the distances between set bits (i.e.
+the length of runs of ZERO bits between two ONE bits). This sequence
+of integers is stored using a simple prefix code to spend fewer bits
+on smaller (more frequent) numbers.
+
+The algorithm includes an escape-mechanism to mix uncompressed binary
+data with compressed bit-streams. This is useful when the bit-stream
+contains sections that do not compress well with this algorithm, for
+example in BRAM initialization data.
+
+The compressed bitstream starts with the ASCII string "ICECOMPR", i.e.
+the hex values 0x49434543 and 0x4f4d5052 (stored as big-endian numbers).
+
+After the 8 bytes magic the compressed bitstream is a stream of the
+following opcodes that must be interpreted by the decompressor. The
+notation ZERO and ONE is used for zero and one bits. The notation foo[N]
+is used for an N bit value "foo", transmitted MSB first.
+
+	ONE count[2]
+	ZERO ONE count[5]
+	ZERO ZERO ONE count[8]
+	ZERO ZERO ZERO ZERO ONE count[23]
+	  output count ZERO bits followed by a single ONE bit
+
+	ZERO ZERO ZERO ONE count[6] data[count]
+	  output the count data bits followed by a single ONE bit
+
+	ZERO ZERO ZERO ZERO ZERO count[23]
+	  output count ZERO bits and stop decompressing. (end of file)
+
+The program "icecompr" (C++11, ISC license) contains an implementation of a
+compressor and a decompressor. The decompressor in this program however is
+only used for integrity checking the compressed bit-stream.
+
+The program "iceuncompr" (plain C, public domain) contains an implementation
+of a stand-alone decompressor. Simply copy&paste this implementation into
+your uC firmware.
+
diff --git a/icecompr/example_1k.bin b/icecompr/example_1k.bin
new file mode 100644
index 0000000..0321b9a
--- /dev/null
+++ b/icecompr/example_1k.bin
diff --git a/icecompr/example_8k.bin b/icecompr/example_8k.bin
new file mode 100644
index 0000000..8b6c7c5
--- /dev/null
+++ b/icecompr/example_8k.bin
diff --git a/icecompr/icecompr.cc b/icecompr/icecompr.cc
new file mode 100644
index 0000000..322de9a
--- /dev/null
+++ b/icecompr/icecompr.cc
@@ -0,0 +1,316 @@
+/*
+ *  IceCompr -- A simple compressor for iCE40 bit-streams
+ *
+ *  Copyright (C) 2017  Clifford Wolf <clifford@clifford.at>
+ *
+ *  Permission to use, copy, modify, and/or distribute this software for any
+ *  purpose with or without fee is hereby granted, provided that the above
+ *  copyright notice and this permission notice appear in all copies.
+ *
+ *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <string.h>
+#include <errno.h>
+#include <vector>
+#include <map>
+
+int verbose = 0;
+
+static void push_int_bits(std::vector<bool> &outbits, int value, int bits)
+{
+	while (bits-- > 0)
+		outbits.push_back((value >> bits) & 1);
+}
+
+static void push_zero_bits(std::vector<bool> &outbits, int bits)
+{
+	while (bits-- > 0)
+		outbits.push_back(false);
+}
+
+static int decode_int_from_bits(const std::vector<bool> &inbits, int &cursor, int bits)
+{
+	int ret = 0;
+	while (bits-- > 0)
+		if (inbits.at(cursor++))
+			ret |= 1 << bits;
+	return ret;
+}
+
+void ice_compress(std::vector<bool> &outbits, const std::vector<bool> &inbits)
+{
+	int opcode_stats_d4 = 0;
+	int opcode_stats_d32 = 0;
+	int opcode_stats_d256 = 0;
+	int opcode_stats_raw = 0;
+	int opcode_stats_d8M = 0;
+	int opcode_stats_end = 0;
+
+	std::vector<int> deltas;
+	int numzeros = 0;
+
+	for (auto bit : inbits)
+	{
+		if (bit) {
+			deltas.push_back(numzeros);
+			numzeros = 0;
+		} else {
+			numzeros++;
+		}
+	}
+
+	for (int i = 0; i < int(deltas.size()); i++)
+	{
+		int raw_len = 0;
+		int compr_len = 0;
+		int best_compr_raw_diff = -1;
+		int best_compr_raw_idx = -1;
+		int best_compr_raw_len = -1;
+
+		for (int j = 0; j+i < int(deltas.size()); j++)
+		{
+			int delta = deltas.at(i + j);
+			raw_len += delta + 1;
+
+			if (delta < 4)
+				compr_len += 3;
+			else if (delta < 32)
+				compr_len += 7;
+			else if (delta < 256)
+				compr_len += 11;
+			else
+				compr_len += 26;
+
+			if (compr_len - raw_len < std::max(best_compr_raw_diff - 4, 0) || raw_len > 64)
+				break;
+
+			if (compr_len - raw_len > best_compr_raw_diff) {
+				best_compr_raw_diff = compr_len - raw_len;
+				best_compr_raw_idx = j;
+				best_compr_raw_len = raw_len;
+			}
+		}
+
+		if (best_compr_raw_diff > 9)
+		{
+			opcode_stats_raw++;
+			outbits.push_back(false);
+			outbits.push_back(false);
+			outbits.push_back(false);
+			outbits.push_back(true);
+			push_int_bits(outbits, best_compr_raw_len-1, 6);
+
+			for (int j = 0; j <= best_compr_raw_idx; j++) {
+				int delta = deltas.at(i + j);
+				for (int k = 0; k < delta; k++)
+					outbits.push_back(false);
+				if (j < best_compr_raw_idx)
+					outbits.push_back(true);
+			}
+
+			i += best_compr_raw_idx;
+			continue;
+		}
+
+		int delta = deltas.at(i);
+
+		if (delta < 4) {
+			opcode_stats_d4++;
+			outbits.push_back(true);
+			push_int_bits(outbits, delta, 2);
+		} else
+		if (delta < 32) {
+			opcode_stats_d32++;
+			outbits.push_back(false);
+			outbits.push_back(true);
+			push_int_bits(outbits, delta, 5);
+		} else
+		if (delta < 256) {
+			opcode_stats_d256++;
+			outbits.push_back(false);
+			outbits.push_back(false);
+			outbits.push_back(true);
+			push_int_bits(outbits, delta, 8);
+		} else {
+			opcode_stats_d8M++;
+			outbits.push_back(false);
+			outbits.push_back(false);
+			outbits.push_back(false);
+			outbits.push_back(false);
+			outbits.push_back(true);
+			push_int_bits(outbits, delta, 23);
+		}
+	}
+
+	opcode_stats_end++;
+	outbits.push_back(false);
+	outbits.push_back(false);
+	outbits.push_back(false);
+	outbits.push_back(false);
+	outbits.push_back(false);
+	push_int_bits(outbits, numzeros, 23);
+
+	if (verbose > 1) {
+		fprintf(stderr, "opcode d4   %5d\n", opcode_stats_d4);
+		fprintf(stderr, "opcode d32  %5d\n", opcode_stats_d32);
+		fprintf(stderr, "opcode d256 %5d\n", opcode_stats_d256);
+		fprintf(stderr, "opcode raw  %5d\n", opcode_stats_raw);
+		fprintf(stderr, "opcode d8M  %5d\n", opcode_stats_d8M);
+		fprintf(stderr, "opcode end  %5d\n", opcode_stats_end);
+	}
+}
+
+void ice_uncompress(std::vector<bool> &outbits, const std::vector<bool> &inbits)
+{
+	int cursor = 0;
+
+	while (cursor < int(inbits.size()))
+	{
+		if (inbits.at(cursor++)) {
+			int zeros = decode_int_from_bits(inbits, cursor, 2);
+			push_zero_bits(outbits, zeros);
+			outbits.push_back(true);
+		} else
+		if (inbits.at(cursor++)) {
+			int zeros = decode_int_from_bits(inbits, cursor, 5);
+			push_zero_bits(outbits, zeros);
+			outbits.push_back(true);
+		} else
+		if (inbits.at(cursor++)) {
+			int zeros = decode_int_from_bits(inbits, cursor, 8);
+			push_zero_bits(outbits, zeros);
+			outbits.push_back(true);
+		} else
+		if (inbits.at(cursor++)) {
+			int raw_len = decode_int_from_bits(inbits, cursor, 6);
+			while (raw_len--)
+				outbits.push_back(inbits.at(cursor++));
+			outbits.push_back(true);
+		} else
+		if (inbits.at(cursor++)) {
+			int zeros = decode_int_from_bits(inbits, cursor, 23);
+			push_zero_bits(outbits, zeros);
+			outbits.push_back(true);
+		} else {
+			int zeros = decode_int_from_bits(inbits, cursor, 23);
+			push_zero_bits(outbits, zeros);
+		}
+	}
+}
+
+void help()
+{
+	printf("\n");
+	printf("Usage: icecompr [-v] [input-file [output-file]]\n");
+	printf("\n");
+	exit(1);
+}
+
+int main(int argc, char **argv)
+{
+	FILE *input_file = stdin;
+	FILE *output_file = stdout;
+
+	int opt;
+	while ((opt = getopt(argc, argv, "v")) != -1)
+	{
+		switch (opt)
+		{
+		case 'v':
+			verbose++;
+			break;
+		default:
+			help();
+		}
+	}
+
+	if (optind < argc) {
+		input_file = fopen(argv[optind], "rb");
+		if (input_file == NULL) {
+			fprintf(stderr, "Failed to open input file `%s': %s\n", argv[optind], strerror(errno));
+			return 1;
+		}
+		optind++;
+	}
+
+	if (optind < argc) {
+		output_file = fopen(argv[optind], "wb");
+		if (output_file == NULL) {
+			fprintf(stderr, "Failed to open output file `%s': %s\n", argv[optind], strerror(errno));
+			return 1;
+		}
+		optind++;
+	}
+
+	if (optind != argc)
+		help();
+
+	std::vector<bool> original_bits;
+	int count_set_bits = 0;
+
+	while (1)
+	{
+		int byte = fgetc(input_file);
+
+		if (byte < 0)
+			break;
+
+		// MSB first
+		for (int i = 7; i >= 0; i--) {
+			bool bit = (byte >> i) & 1;
+			if (bit) count_set_bits++;
+			original_bits.push_back(bit);
+		}
+	}
+
+	int uncompressed_size = original_bits.size();
+
+	if (verbose > 0) {
+		fprintf(stderr, "Percentage of set bits: %.2f%%\n", (100.0*count_set_bits) / uncompressed_size);
+		fprintf(stderr, "Uncompressed size: %8d bits\n", uncompressed_size);
+	}
+
+	std::vector<bool> compressed_bits;
+	ice_compress(compressed_bits, original_bits);
+
+	int compressed_size = compressed_bits.size();
+
+	if (verbose > 0) {
+		fprintf(stderr, "Compressed size:   %8d bits\n", compressed_size);
+		fprintf(stderr, "Space savings: %.2f%%\n", 100 - (100.0*compressed_size) / uncompressed_size);
+	}
+
+	std::vector<bool> uncompressed_bits;
+	ice_uncompress(uncompressed_bits, compressed_bits);
+
+	bool check_ok = original_bits == uncompressed_bits;
+
+	if (verbose > 0 || !check_ok) {
+		fprintf(stderr, "Integrity check: %s\n", check_ok ? "OK" : "ERROR");
+		if (!check_ok)
+			return 1;
+	}
+
+	fprintf(output_file, "ICECOMPR");
+	for (int i = 0; i < int(compressed_bits.size()); i += 8) {
+		int value = 0;
+		for (int j = 0; j < 8 && i+j < int(compressed_bits.size()); j++)
+			if (compressed_bits.at(i+j))
+				value |= 1 << (7-j);
+		fputc(value, output_file);
+	}
+	
+	return 0;
+}
+
diff --git a/icecompr/iceuncompr.c b/icecompr/iceuncompr.c
new file mode 100644
index 0000000..04e7dc8
--- /dev/null
+++ b/icecompr/iceuncompr.c
@@ -0,0 +1,162 @@
+// This is free and unencumbered software released into the public domain.
+//
+// Anyone is free to copy, modify, publish, use, compile, sell, or
+// distribute this software, either in source code form or as a compiled
+// binary, for any purpose, commercial or non-commercial, and by any
+// means.
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <string.h>
+#include <errno.h>
+
+FILE *input_file;
+FILE *output_file;
+
+int read_bitcounter;
+int read_buffer;
+
+int write_bitcounter;
+int write_buffer;
+
+static int read_bit()
+{
+	if (read_bitcounter == 0) {
+		read_bitcounter = 8;
+		read_buffer = fgetc(input_file);
+	}
+
+	read_bitcounter--;
+	return (read_buffer >> read_bitcounter) & 1;
+}
+
+static void write_bit(int value)
+{
+	write_bitcounter--;
+
+	if (value)
+		write_buffer |= 1 << write_bitcounter;
+	
+	if (write_bitcounter == 0) {
+		fputc(write_buffer, output_file);
+		write_bitcounter = 8;
+		write_buffer = 0;
+	}
+}
+
+static int read_int(int bits)
+{
+	int ret = 0;
+	while (bits-- > 0)
+		if (read_bit())
+			ret |= 1 << bits;
+	return ret;
+}
+
+static void write_zeros(int bits)
+{
+	while (bits-- > 0)
+		write_bit(0);
+}
+
+int ice_uncompress()
+{
+	read_bitcounter = 0;
+	read_buffer = 0;
+
+	write_bitcounter = 8;
+	write_buffer = 0;
+
+	int magic1_ok = read_int(32) == 0x49434543;
+	int magic2_ok = read_int(32) == 0x4f4d5052;
+
+	if (!magic1_ok || !magic2_ok) {
+		fprintf(stderr, "Missing ICECOMPR magic. Abort!\n");
+		return 1;
+	}
+
+	while (1)
+	{
+		if (read_bit()) {
+			write_zeros(read_int(2));
+			write_bit(1);
+		} else
+		if (read_bit()) {
+			write_zeros(read_int(5));
+			write_bit(1);
+		} else
+		if (read_bit()) {
+			write_zeros(read_int(8));
+			write_bit(1);
+		} else
+		if (read_bit()) {
+			int n = read_int(6);
+			while (n--)
+				write_bit(read_bit());
+			write_bit(1);
+		} else
+		if (read_bit()) {
+			write_zeros(read_int(23));
+			write_bit(1);
+		} else {
+			write_zeros(read_int(23));
+			break;
+		}
+	}
+
+	return 0;
+}
+
+void help()
+{
+	printf("\n");
+	printf("Usage: iceuncompr [input-file [output-file]]\n");
+	printf("\n");
+	exit(1);
+}
+
+int main(int argc, char **argv)
+{
+	input_file = stdin;
+	output_file = stdout;
+
+	int opt;
+	while ((opt = getopt(argc, argv, "v")) != -1)
+	{
+		switch (opt)
+		{
+		case 'v':
+			break;
+		default:
+			help();
+		}
+	}
+
+	if (optind < argc) {
+		input_file = fopen(argv[optind], "rb");
+		if (input_file == NULL) {
+			fprintf(stderr, "Failed to open input file `%s': %s\n", argv[optind], strerror(errno));
+			return 1;
+		}
+		optind++;
+	}
+
+	if (optind < argc) {
+		output_file = fopen(argv[optind], "wb");
+		if (output_file == NULL) {
+			fprintf(stderr, "Failed to open output file `%s': %s\n", argv[optind], strerror(errno));
+			return 1;
+		}
+		optind++;
+	}
+
+	if (optind != argc)
+		help();
+
+	if (optind != argc)
+		help();
+
+	return ice_uncompress();
+}
+