]> git.zerfleddert.de Git - proxmark3-svn/blob - client/fpga_compress.c
9e0946b28c9274b2590dd5e6491f1b7adddd457b
[proxmark3-svn] / client / fpga_compress.c
1 //-----------------------------------------------------------------------------
2 // This code is licensed to you under the terms of the GNU GPL, version 2 or,
3 // at your option, any later version. See the LICENSE.txt file for the text of
4 // the license.
5 //-----------------------------------------------------------------------------
6 // Flasher frontend tool
7 //-----------------------------------------------------------------------------
8
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12 #include "sleep.h"
13 #include "proxmark3.h"
14 #include "flash.h"
15 #include "uart.h"
16 #include "usb_cmd.h"
17
18 #define MAX(a,b) ((a)>(b)?(a):(b))
19
20 struct huffman_record {
21 int16_t symbol;
22 uint16_t count;
23 uint8_t code_size;
24 uint8_t code;
25 struct huffman_record *left;
26 struct huffman_record *right;
27 struct huffman_record *next;
28 };
29
30 typedef struct huffman_record huffman_record_t;
31
32 #define FPGA_CONFIG_SIZE 42175
33 static uint8_t fpga_config[FPGA_CONFIG_SIZE];
34 static huffman_record_t leaf_nodes[256];
35 static uint8_t start_code[256];
36
37 static void usage(char *argv0)
38 {
39 fprintf(stderr, "Usage: %s [-d] <infile> <outfile>\n\n", argv0);
40 fprintf(stderr, "\t-d\tdecompress\n\n");
41 }
42
43
44 void add_to_heap(huffman_record_t **heap, huffman_record_t *new_record)
45 {
46 huffman_record_t *succ = *heap;
47 huffman_record_t *pred = NULL;
48
49 // fprintf(stderr, "Adding symbol %d, count %d\n", new_record->symbol, new_record->count);
50
51 while (succ != NULL && new_record->count > succ->count) {
52 pred = succ;
53 succ = succ->next;
54 }
55
56 // insert new record
57 new_record->next = succ;
58 if (pred == NULL) { // first record in heap
59 *heap = new_record;
60 } else {
61 pred->next = new_record;
62 }
63 }
64
65
66 uint16_t set_codesize(huffman_record_t *tree_ptr, uint8_t depth)
67 {
68 uint16_t max_size = depth;
69 tree_ptr->code_size = depth;
70 if (tree_ptr->left != NULL) {
71 max_size = MAX(set_codesize(tree_ptr->left, depth+1), max_size);
72 }
73 if (tree_ptr->right != NULL) {
74 max_size = MAX(set_codesize(tree_ptr->right, depth+1), max_size);
75 }
76 return max_size;
77 }
78
79 int huffman_encode(FILE *infile, FILE *outfile)
80 {
81 int i;
82
83 // init leaf_nodes:
84 for (i = 0; i < 256; i++) {
85 leaf_nodes[i].count = 0;
86 leaf_nodes[i].symbol = i;
87 leaf_nodes[i].left = NULL;
88 leaf_nodes[i].right = NULL;
89 leaf_nodes[i].next = NULL;
90 }
91
92 // read the input file into fpga_config[] and count occurrences of each symbol:
93 i = 0;
94 while(!feof(infile)) {
95 uint8_t c;
96 c = fgetc(infile);
97 fpga_config[i++] = c;
98 leaf_nodes[c].count++;
99 if (i > FPGA_CONFIG_SIZE+1) {
100 fprintf(stderr, "Input file too big (> %d bytes). This is probably not a PM3 FPGA config file.", FPGA_CONFIG_SIZE);
101 fclose(infile);
102 fclose(outfile);
103 return -1;
104 }
105 }
106
107 fprintf(stderr, "\nStatistics: (symbol: count)\n");
108 for (i = 0; i < 256; i++) {
109 fprintf(stderr, "%3d: %5d\n", i, leaf_nodes[i].count);
110 }
111
112 // build the Huffman tree:
113 huffman_record_t *heap_ptr = NULL;
114
115 for (i = 0; i < 256; i++) {
116 add_to_heap(&heap_ptr, &leaf_nodes[i]);
117 }
118
119 fprintf(stderr, "\nSorted statistics: (symbol: count)\n");
120 for (huffman_record_t *p = heap_ptr; p != NULL; p = p->next) {
121 fprintf(stderr, "%3d: %5d\n", p->symbol, p->count);
122 }
123
124 for (i = 0; i < 255; i++) {
125 // remove and combine the first two nodes
126 huffman_record_t *p1, *p2;
127 p1 = heap_ptr;
128 p2 = heap_ptr->next;
129 heap_ptr = p2->next;
130 huffman_record_t *new_node = malloc(sizeof(huffman_record_t));
131 new_node->left = p1;
132 new_node->right = p2;
133 new_node->count = p1->count + p2->count;
134 add_to_heap(&heap_ptr, new_node);
135 }
136
137 uint16_t max_codesize = set_codesize(heap_ptr, 0);
138
139 fprintf(stderr, "\nStatistics: (symbol: count, codesize)\n");
140 uint32_t compressed_size = 0;
141 for (i = 0; i < 256; i++) {
142 fprintf(stderr, "%3d: %5d, %d\n", leaf_nodes[i].symbol, leaf_nodes[i].count, leaf_nodes[i].code_size);
143 compressed_size += leaf_nodes[i].count * leaf_nodes[i].code_size;
144 }
145 fprintf(stderr, "Compressed size = %ld (%f% of original size)", (compressed_size+7)/8, (float)(compressed_size)/(FPGA_CONFIG_SIZE * 8) * 100);
146 fprintf(stderr, "Max Codesize = %d bits", max_codesize);
147
148 uint8_t code = 0;
149 for (i = max_codesize; i > 0; i--) {
150 code = (code + 1) >> 1;
151 start_code[i] = code;
152 for (uint16_t j = 0; j < 256; j++) {
153 if (leaf_nodes[j].code_size == i) {
154 leaf_nodes[j].code = code;
155 code++;
156 }
157 }
158 }
159
160
161 fprintf(stderr, "\nStatistics: (symbol: count, codesize, code)\n");
162 for (i = 0; i < 256; i++) {
163 fprintf(stderr, "%3d: %5d, %d, %02x\n", leaf_nodes[i].symbol, leaf_nodes[i].count, leaf_nodes[i].code_size, leaf_nodes[i].code);
164 }
165
166 fclose(infile);
167 fclose(outfile);
168
169 return 0;
170 }
171
172 int huffman_decode(FILE *infile, FILE *outfile)
173 {
174 return 0;
175 }
176
177
178 int main(int argc, char **argv)
179 {
180 bool decode = false;
181 char *infilename;
182 char *outfilename;
183
184 if (argc < 3) {
185 usage(argv[0]);
186 return -1;
187 }
188
189 if (argc > 3) {
190 if (!strcmp(argv[1], "-d")) {
191 decode = true;
192 infilename = argv[2];
193 outfilename = argv[3];
194 } else {
195 usage(argv[0]);
196 return -1;
197 }
198 } else {
199 infilename = argv[1];
200 outfilename = argv[2];
201 }
202
203 FILE *infile = fopen(infilename, "rb");
204 if (infile == NULL) {
205 fprintf(stderr, "Error. Cannot open input file %s", infilename);
206 return -1;
207 }
208
209 FILE *outfile = fopen(outfilename, "wb");
210 if (outfile == NULL) {
211 fprintf(stderr, "Error. Cannot open output file %s", outfilename);
212 fclose(infile);
213 return -1;
214 }
215
216 if (decode) {
217 return huffman_decode(infile, outfile);
218 } else {
219 return huffman_encode(infile, outfile);
220 }
221 }
Impressum, Datenschutz