X-Git-Url: https://git.zerfleddert.de/cgi-bin/gitweb.cgi/proxmark3-svn/blobdiff_plain/e61530408c4b3605390748fc544b5afcfda996a3..62a38cc8835cc7b98a30ee3e670e6eb582ddd8cd:/client/fpga_compress.c

diff --git a/client/fpga_compress.c b/client/fpga_compress.c
index 9e0946b2..28154243 100644
--- a/client/fpga_compress.c
+++ b/client/fpga_compress.c
@@ -3,219 +3,288 @@
 // at your option, any later version. See the LICENSE.txt file for the text of
 // the license.
 //-----------------------------------------------------------------------------
-// Flasher frontend tool
+// Compression tool for FPGA config files. Compress several *.bit files at
+// compile time. Decompression is done at run time (see fpgaloader.c).
+// This uses the zlib library tuned to this specific case. The small file sizes
+// allow to use "insane" parameters for optimum compression ratio.
 //-----------------------------------------------------------------------------
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include "sleep.h"
-#include "proxmark3.h"
-#include "flash.h"
-#include "uart.h"
-#include "usb_cmd.h"
+#include <stdint.h>
+#include <stdbool.h>
+#include "zlib.h"
 
 #define MAX(a,b) ((a)>(b)?(a):(b))
 
-struct huffman_record {
-		int16_t symbol;
-		uint16_t count;
-		uint8_t code_size;
-		uint8_t code;
-		struct huffman_record *left;
-		struct huffman_record *right;
-		struct huffman_record *next;
-	};
+// zlib configuration
+#define COMPRESS_LEVEL           9  // use best possible compression
+#define COMPRESS_WINDOW_BITS    15  // default = max = 15 for a window of 2^15 = 32KBytes
+#define COMPRESS_MEM_LEVEL       9  // determines the amount of memory allocated during compression. Default = 8.
+/* COMPRESS_STRATEGY can be 
+	Z_DEFAULT_STRATEGY (the default), 
+	Z_FILTERED (more huffmann, less string matching),
+	Z_HUFFMAN_ONLY (huffman only, no string matching)
+	Z_RLE (distances limited to one)
+	Z_FIXED (prevents the use of dynamic Huffman codes)
+*/
 
-typedef struct huffman_record huffman_record_t;
+#define	COMPRESS_STRATEGY       Z_DEFAULT_STRATEGY
+// zlib tuning parameters:
+#define COMPRESS_GOOD_LENGTH           258
+#define COMPRESS_MAX_LAZY              258
+#define COMPRESS_MAX_NICE_LENGTH       258
+#define COMPRESS_MAX_CHAIN            8192
 
-#define FPGA_CONFIG_SIZE	42175
-static uint8_t fpga_config[FPGA_CONFIG_SIZE];
-static huffman_record_t leaf_nodes[256];
-static uint8_t start_code[256];
+#define FPGA_INTERLEAVE_SIZE           288  // (the FPGA's internal config frame size is 288 bits. Interleaving with 288 bytes should give best compression)
+#define FPGA_CONFIG_SIZE             42336  // our current fpga_[lh]f.bit files are 42175 bytes. Rounded up to next multiple of FPGA_INTERLEAVE_SIZE
 
-static void usage(char *argv0)
+static void usage(void)
 {
-	fprintf(stderr, "Usage:   %s [-d] <infile> <outfile>\n\n", argv0);
-	fprintf(stderr, "\t-d\tdecompress\n\n");
+	fprintf(stderr, "Usage: fpga_compress <infile1> <infile2> ... <infile_n> <outfile>\n");
+	fprintf(stderr, "          Combine n FPGA bitstream files and compress them into one.\n\n");
+	fprintf(stderr, "       fpga_compress -d <infile> <outfile>");
+	fprintf(stderr, "          Decompress <infile>. Write result to <outfile>");
 }
 
 
-void add_to_heap(huffman_record_t **heap, huffman_record_t *new_record)
+static voidpf fpga_deflate_malloc(voidpf opaque, uInt items, uInt size)
 {
-	huffman_record_t *succ = *heap;
-	huffman_record_t *pred = NULL;
-	
-//	fprintf(stderr, "Adding symbol %d, count %d\n", new_record->symbol, new_record->count);
-	
-	while (succ != NULL && new_record->count > succ->count) {
-		pred = succ;
-		succ = succ->next;
-	}
+	return malloc(items*size);
+}
 
-	// insert new record
-	new_record->next = succ;
-	if (pred == NULL) {			// first record in heap
-		*heap = new_record;
-	} else {
-		pred->next = new_record;
-	}
+
+static void fpga_deflate_free(voidpf opaque, voidpf address)
+{
+	return free(address);
 }
-	
 
-uint16_t set_codesize(huffman_record_t *tree_ptr, uint8_t depth)
+
+static bool all_feof(FILE *infile[], uint8_t num_infiles)
 {
-	uint16_t max_size = depth;
-	tree_ptr->code_size = depth;
-	if (tree_ptr->left != NULL) {
-		max_size = MAX(set_codesize(tree_ptr->left, depth+1), max_size);
-	}
-	if (tree_ptr->right != NULL) {
-		max_size = MAX(set_codesize(tree_ptr->right, depth+1), max_size);
+	for (uint16_t i = 0; i < num_infiles; i++) {
+		if (!feof(infile[i])) {
+			return false;
+		}
 	}
-	return max_size;
-}	
+	
+	return true;
+}
+
 
-int huffman_encode(FILE *infile, FILE *outfile)
+int zlib_compress(FILE *infile[], uint8_t num_infiles, FILE *outfile)
 {
-	int i;
-	
-	// init leaf_nodes:
-	for (i = 0; i < 256; i++) {
-		leaf_nodes[i].count = 0;
-		leaf_nodes[i].symbol = i;
-		leaf_nodes[i].left = NULL;
-		leaf_nodes[i].right = NULL;
-		leaf_nodes[i].next = NULL;
-	}
+	uint8_t *fpga_config;
+	uint32_t i;
+	int32_t ret;
+	uint8_t c;
+	z_stream compressed_fpga_stream;
+
+	fpga_config = malloc(num_infiles * FPGA_CONFIG_SIZE);
 	
-	// read the input file into fpga_config[] and count occurrences of each symbol:
+	// read the input files. Interleave them into fpga_config[]
 	i = 0;
-	while(!feof(infile)) {
-		uint8_t c;
-		c = fgetc(infile);
-		fpga_config[i++] = c;
-		leaf_nodes[c].count++;
-		if (i > FPGA_CONFIG_SIZE+1) {
-			fprintf(stderr, "Input file too big (> %d bytes). This is probably not a PM3 FPGA config file.", FPGA_CONFIG_SIZE);
-			fclose(infile);
-			fclose(outfile);
-			return -1;
+	do {
+
+		if (i >= num_infiles * FPGA_CONFIG_SIZE) {
+			fprintf(stderr, "Input files too big (total > %u bytes). These are probably not PM3 FPGA config files.\n", num_infiles*FPGA_CONFIG_SIZE);
+			for(uint16_t j = 0; j < num_infiles; j++) {
+				fclose(infile[j]);
+			}
+			free(fpga_config);
+			return(EXIT_FAILURE);
 		}
-	}
-	
-	fprintf(stderr, "\nStatistics: (symbol: count)\n");
-	for (i = 0; i < 256; i++) {
-		fprintf(stderr, "%3d: %5d\n", i, leaf_nodes[i].count);
-	}
 
-	// build the Huffman tree:
-	huffman_record_t *heap_ptr = NULL;
+		for(uint16_t j = 0; j < num_infiles; j++) {
+			for(uint16_t k = 0; k < FPGA_INTERLEAVE_SIZE; k++) {
+				c = fgetc(infile[j]);
+				if (!feof(infile[j])) {
+					fpga_config[i++] = c;
+				} else if (num_infiles > 1) {
+					fpga_config[i++] = '\0';
+				}
+			}
+		}
 
-	for (i = 0; i < 256; i++) {
-		add_to_heap(&heap_ptr, &leaf_nodes[i]); 
-	}
+	} while (!all_feof(infile, num_infiles));
 
-	fprintf(stderr, "\nSorted statistics: (symbol: count)\n");
-	for (huffman_record_t *p = heap_ptr; p != NULL; p = p->next) {
-		fprintf(stderr, "%3d: %5d\n", p->symbol, p->count);
-	}
+	// initialize zlib structures
+	compressed_fpga_stream.next_in = fpga_config;
+	compressed_fpga_stream.avail_in = i;
+	compressed_fpga_stream.zalloc = fpga_deflate_malloc;
+	compressed_fpga_stream.zfree = fpga_deflate_free;
+	compressed_fpga_stream.opaque = Z_NULL;
+	ret = deflateInit2(&compressed_fpga_stream, 
+						COMPRESS_LEVEL,
+						Z_DEFLATED,
+						COMPRESS_WINDOW_BITS,
+						COMPRESS_MEM_LEVEL,
+						COMPRESS_STRATEGY);
 
-	for (i = 0; i < 255; i++) {
-		// remove and combine the first two nodes
-		huffman_record_t *p1, *p2;
-		p1 = heap_ptr;
-		p2 = heap_ptr->next;
-		heap_ptr = p2->next;
-		huffman_record_t *new_node = malloc(sizeof(huffman_record_t));
-		new_node->left = p1;
-		new_node->right = p2;
-		new_node->count = p1->count + p2->count;
-		add_to_heap(&heap_ptr, new_node); 
+	// estimate the size of the compressed output
+	uint32_t outsize_max = deflateBound(&compressed_fpga_stream, compressed_fpga_stream.avail_in);
+	uint8_t *outbuf = malloc(outsize_max);
+	compressed_fpga_stream.next_out = outbuf;
+	compressed_fpga_stream.avail_out = outsize_max;
+        
+	if (ret == Z_OK) {
+		ret = deflateTune(&compressed_fpga_stream,
+							COMPRESS_GOOD_LENGTH,
+							COMPRESS_MAX_LAZY,
+							COMPRESS_MAX_NICE_LENGTH,
+							COMPRESS_MAX_CHAIN);
 	}
 	
-	uint16_t max_codesize = set_codesize(heap_ptr, 0);
-
-	fprintf(stderr, "\nStatistics: (symbol: count, codesize)\n");
-	uint32_t compressed_size = 0;
-	for (i = 0; i < 256; i++) {
-		fprintf(stderr, "%3d: %5d, %d\n", leaf_nodes[i].symbol, leaf_nodes[i].count, leaf_nodes[i].code_size);
-		compressed_size += leaf_nodes[i].count * leaf_nodes[i].code_size;
+	if (ret == Z_OK) {
+		ret = deflate(&compressed_fpga_stream, Z_FINISH);
 	}
-	fprintf(stderr, "Compressed size = %ld (%f% of original size)", (compressed_size+7)/8, (float)(compressed_size)/(FPGA_CONFIG_SIZE * 8) * 100);
-	fprintf(stderr, "Max Codesize = %d bits", max_codesize);
 	
-	uint8_t code = 0;
-	for (i = max_codesize; i > 0; i--) {
-		code = (code + 1) >> 1;
-		start_code[i] = code;
-		for (uint16_t j = 0; j < 256; j++) {
-			if (leaf_nodes[j].code_size == i) {
-				leaf_nodes[j].code = code;
-				code++;
-			}
+	fprintf(stderr, "compressed %u input bytes to %lu output bytes\n", i, compressed_fpga_stream.total_out);
+
+	if (ret != Z_STREAM_END) {
+		fprintf(stderr, "Error in deflate(): %i %s\n", ret, compressed_fpga_stream.msg);
+		free(outbuf);
+		deflateEnd(&compressed_fpga_stream);
+		for(uint16_t j = 0; j < num_infiles; j++) {
+			fclose(infile[j]);
 		}
-	}
+		fclose(outfile);
+		free(infile);
+		free(fpga_config);
+		return(EXIT_FAILURE);
+		}
+		
+	for (i = 0; i < compressed_fpga_stream.total_out; i++) {
+		fputc(outbuf[i], outfile);
+	}	
 
-	
-	fprintf(stderr, "\nStatistics: (symbol: count, codesize, code)\n");
-	for (i = 0; i < 256; i++) {
-		fprintf(stderr, "%3d: %5d, %d, %02x\n", leaf_nodes[i].symbol, leaf_nodes[i].count, leaf_nodes[i].code_size, leaf_nodes[i].code);
+	free(outbuf);
+	deflateEnd(&compressed_fpga_stream);
+	for(uint16_t j = 0; j < num_infiles; j++) {
+		fclose(infile[j]);
 	}
-		
-	fclose(infile);
 	fclose(outfile);
+	free(infile);
+	free(fpga_config);
+	
+	return(EXIT_SUCCESS);
 	
-	return 0;
 }
 
-int huffman_decode(FILE *infile, FILE *outfile)
+
+int zlib_decompress(FILE *infile, FILE *outfile)
 {
-	return 0;
+	#define DECOMPRESS_BUF_SIZE 1024
+	uint8_t outbuf[DECOMPRESS_BUF_SIZE];
+	uint8_t inbuf[DECOMPRESS_BUF_SIZE];
+	int32_t ret;
+	
+	z_stream compressed_fpga_stream;
+
+	// initialize zlib structures
+	compressed_fpga_stream.next_in = inbuf;
+	compressed_fpga_stream.avail_in = 0;
+	compressed_fpga_stream.next_out = outbuf;
+	compressed_fpga_stream.avail_out = DECOMPRESS_BUF_SIZE;
+	compressed_fpga_stream.zalloc = fpga_deflate_malloc;
+	compressed_fpga_stream.zfree = fpga_deflate_free;
+	compressed_fpga_stream.opaque = Z_NULL;
+	
+	ret = inflateInit2(&compressed_fpga_stream, 0);
+	
+	do {
+		if (compressed_fpga_stream.avail_in == 0) {
+			compressed_fpga_stream.next_in = inbuf;
+			uint16_t i = 0;
+			do {
+				int32_t c = fgetc(infile);
+				if (!feof(infile)) {
+					inbuf[i++] = c & 0xFF;
+					compressed_fpga_stream.avail_in++;
+				} else {
+					break;
+				}
+			} while (i < DECOMPRESS_BUF_SIZE);
+		}
+
+		ret = inflate(&compressed_fpga_stream, Z_SYNC_FLUSH);
+
+		if (ret != Z_OK && ret != Z_STREAM_END) {
+			break;
+		}
+
+		if (compressed_fpga_stream.avail_out == 0) {
+			for (uint16_t i = 0; i < DECOMPRESS_BUF_SIZE; i++) {
+				fputc(outbuf[i], outfile);
+			}
+			compressed_fpga_stream.avail_out = DECOMPRESS_BUF_SIZE;
+			compressed_fpga_stream.next_out = outbuf;
+		}
+	} while (ret == Z_OK);
+
+	if (ret == Z_STREAM_END) {  // reached end of input
+		uint16_t i = 0;
+		while (compressed_fpga_stream.avail_out < DECOMPRESS_BUF_SIZE) {
+			fputc(outbuf[i++], outfile);
+			compressed_fpga_stream.avail_out++;
+		}
+		fclose(outfile);
+		fclose(infile);
+		return(EXIT_SUCCESS);
+	} else {
+		fprintf(stderr, "Error. Inflate() returned error %i, %s", ret, compressed_fpga_stream.msg);
+		fclose(outfile);
+		fclose(infile);
+		return(EXIT_FAILURE);
+	}
+	
 }
 
 
 int main(int argc, char **argv)
 {
-	bool decode = false;
-	char *infilename;
-	char *outfilename;
+	FILE **infiles;
+	FILE *outfile;
 	
-	if (argc < 3) {
-		usage(argv[0]);
-		return -1;
+	if (argc == 1 || argc == 2) {
+		usage();
+		return(EXIT_FAILURE);
 	}
-
-	if (argc > 3) {
-		if (!strcmp(argv[1], "-d")) {
-			decode = true;
-			infilename = argv[2];
-			outfilename = argv[3];
-		} else {
-			usage(argv[0]);
-			return -1;
+	
+	if (!strcmp(argv[1], "-d")) { // Decompress
+		infiles = calloc(1, sizeof(FILE*));
+		if (argc != 4) {
+			usage();
+			return(EXIT_FAILURE);
+		} 
+		infiles[0] = fopen(argv[2], "rb");
+		if (infiles[0] == NULL) {
+			fprintf(stderr, "Error. Cannot open input file %s", argv[2]);
+			return(EXIT_FAILURE);
 		}
-	} else {
-		infilename = argv[1];
-		outfilename = argv[2];
-	}	
+		outfile = fopen(argv[3], "wb");
+		if (outfile == NULL) {
+			fprintf(stderr, "Error. Cannot open output file %s", argv[3]);
+			return(EXIT_FAILURE);
+		}
+		return zlib_decompress(infiles[0], outfile);
 
-	FILE *infile = fopen(infilename, "rb");
-	if (infile == NULL) {
-		fprintf(stderr, "Error. Cannot open input file %s", infilename);
-		return -1;
+	} else { // Compress
+
+		infiles = calloc(argc-2, sizeof(FILE*));
+		for (uint16_t i = 0; i < argc-2; i++) { 
+			infiles[i] = fopen(argv[i+1], "rb");
+			if (infiles[i] == NULL) {
+				fprintf(stderr, "Error. Cannot open input file %s", argv[i+1]);
+				return(EXIT_FAILURE);
+			}
 		}
-		
-	FILE *outfile = fopen(outfilename, "wb");
-	if (outfile == NULL) {
-		fprintf(stderr, "Error. Cannot open output file %s", outfilename);
-		fclose(infile);
-		return -1;
+		outfile = fopen(argv[argc-1], "wb");
+		if (outfile == NULL) {
+			fprintf(stderr, "Error. Cannot open output file %s", argv[argc-1]);
+			return(EXIT_FAILURE);
 		}
-		
-	if (decode) {
-		return huffman_decode(infile, outfile);
-	} else {
-		return huffman_encode(infile, outfile);
+		return zlib_compress(infiles, argc-2, outfile);
 	}
 }