git.zerfleddert.de Git - proxmark3-svn/blob - 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 }