Added icecompr
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 Binary files differ
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 Binary files differ
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(); +} +