![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to bliss_huffman.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / bliss|
Return to bliss_huffman.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / bliss |
1.1 misho 1: /*
2: * Copyright (C) 2014 Tobias Brunner
3: * Copyright (C) 2014 Andreas Steffen
4: * HSR Hochschule fuer Technik Rapperswil
5: *
6: * This program is free software; you can redistribute it and/or modify it
7: * under the terms of the GNU General Public License as published by the
8: * Free Software Foundation; either version 2 of the License, or (at your
9: * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
10: *
11: * This program is distributed in the hope that it will be useful, but
12: * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14: * for more details.
15: */
16:
17: #include "bliss_param_set.h"
18:
19: #include <library.h>
20:
21: #include <stdio.h>
22: #include <math.h>
23:
24: typedef struct tuple_t tuple_t;
25:
26: struct tuple_t {
27: int8_t z1;
28: int8_t z2;
29: uint16_t index;
30: uint16_t bits;
31: uint32_t code;
32: };
33:
34: typedef struct node_t node_t;
35:
36: struct node_t {
37: node_t *next;
38: node_t *l;
39: node_t *r;
40: tuple_t *tuple;
41: double p;
42: uint16_t depth;
43: uint16_t index;
44: };
45:
46: static void print_node(node_t *node)
47: {
48: if (node->tuple)
49: {
50: fprintf(stderr, "(%1d,%2d)", node->tuple->z1, node->tuple->z2);
51: }
52: else
53: {
54: fprintf(stderr, " ");
55: }
56: fprintf(stderr, " %18.16f\n", node->p);
57: }
58:
59: static double code_node(node_t *node, int *index, uint8_t bits, uint32_t code)
60: {
61: double code_length = 0;
62:
63: node->index = (*index)++;
64:
65: if (node->tuple)
66: {
67: node->tuple->code = code;
68: node->tuple->bits = bits;
69: code_length += node->p * bits;
70: }
71: if (node->l)
72: {
73: code_length += code_node(node->l, index, bits + 1, (code << 1));
74: }
75: if (node->r)
76: {
77: code_length += code_node(node->r, index, bits + 1, (code << 1) + 1);
78: }
79:
80: return code_length;
81:
82: }
83:
84: static void write_node(node_t *node)
85: {
86: int16_t node_0, node_1, tuple;
87:
88: node_0 = node->l ? node->l->index : BLISS_HUFFMAN_CODE_NO_NODE;
89: node_1 = node->r ? node->r->index : BLISS_HUFFMAN_CODE_NO_NODE;
90: tuple = node->tuple ? node->tuple->index : BLISS_HUFFMAN_CODE_NO_TUPLE;
91:
92: printf("\t{ %3d, %3d, %3d }, /* %3d: ", node_0, node_1, tuple, node->index);
93:
94: if (node->tuple)
95: {
96: printf("(%d,%2d) %2u bit%s ", node->tuple->z1, node->tuple->z2,
97: node->tuple->bits, (node->tuple->bits == 1) ? " " : "s");
98: }
99: printf("*/\n");
100:
101: if (node->l)
102: {
103: write_node(node->l);
104: }
105: if (node->r)
106: {
107: write_node(node->r);
108: }
109: }
110:
111: static void write_header(void)
112: {
113: printf("/*\n");
114: printf(" * Copyright (C) 2014 Andreas Steffen\n");
115: printf(" * HSR Hochschule fuer Technik Rapperswil\n");
116: printf(" *\n");
117: printf(" * Optimum Huffman code for BLISS-X signatures\n");
118: printf(" *\n");
119: printf(" * This file has been automatically generated by the"
120: " bliss_huffman utility\n");
121: printf(" * Do not edit manually!\n");
122: printf(" */\n\n");
123: };
124:
125: static void write_code_tables(int bliss_type, int n_z1, int n_z2, node_t *nodes,
126: tuple_t **tuples)
127: {
128: int index, i, k;
129: uint32_t bit;
130: double code_length;
131:
132: printf("#include \"bliss_huffman_code.h\"\n\n");
133:
134: printf("static bliss_huffman_code_node_t nodes[] = {\n");
135: index = 0;
136: code_length = code_node(nodes, &index, 0, 0);
137: write_node(nodes);
138: printf("};\n\n");
139:
140: printf("static bliss_huffman_code_tuple_t tuples[] = {\n");
141: index = 0;
142: for (i = 0; i < n_z1; i++)
143: {
144: if (i > 0)
145: {
146: printf("\n");
147: }
148: for (k = 1 - n_z2; k < n_z2; k++)
149: {
150: printf("\t{ %5u, %2u }, /* %3d: (%1d,%2d) ",
151: tuples[index]->code, tuples[index]->bits, index, i, k);
152: bit = 1 << (tuples[index]->bits - 1);
153: while (bit)
154: {
155: printf("%s", (tuples[index]->code & bit) ? "1" : "0");
156: bit >>= 1;
157: }
158: printf(" */\n");
159: index++;
160: }
161: }
162: printf("};\n\n");
163: printf("/* code_length = %6.4f bits/tuple (%d bits) */\n\n",
164: code_length, (int)(512 * code_length + 1));
165:
166: printf("bliss_huffman_code_t bliss_huffman_code_%d = {\n", bliss_type);
167: printf("\t.n_z1 = %d,\n", n_z1);
168: printf("\t.n_z2 = %d,\n", n_z2);
169: printf("\t.tuples = tuples,\n");
170: printf("\t.nodes = nodes\n");
171: printf("};\n");
172: }
173:
174: static void destroy_node(node_t *node)
175: {
176: if (node->l)
177: {
178: destroy_node(node->l);
179: }
180: if (node->r)
181: {
182: destroy_node(node->r);
183: }
184: free(node->tuple);
185: free(node);
186: }
187:
188: static void remove_node(node_t *list, node_t **last, node_t *node)
189: {
190: node_t *current, *prev;
191:
192: for (current = list->next, prev = list; current;
193: prev = current, current = current->next)
194: {
195: if (current == node)
196: {
197: prev->next = current->next;
198: if (*last == current)
199: {
200: *last = prev->next ?: prev;
201: }
202: break;
203: }
204: }
205: }
206:
207: /**
208: * Generate a Huffman code for the optimum encoding of BLISS signatures
209: */
210: int main(int argc, char *argv[])
211: {
212: const bliss_param_set_t *set;
213: int dx, bliss_type, depth = 1, groups, groups_left, pairs = 1;
214: int i_max = 9, k_max = 8, index_max = (2*k_max - 1) * i_max;
215: int i, i_top, k, k_top;
216: uint16_t index;
217: double p, p_z1[i_max], p_z2[k_max], x_z1[i_max], x_z2[k_max];
218: double t, x, x0, p_sum, entropy = 0, erf_i, erf_k, erf_0 = 0;
219: tuple_t *tuple, *tuples[index_max];
220: node_t *node, *node_l, *node_r, *nodes = NULL;
221: node_t *node_list, *node_last;
222:
223: if (argc < 2)
224: {
225: fprintf(stderr, "usage: bliss_huffman <bliss type> [<pairs>]\n");
226: exit(1);
227: }
228: if (argc > 2)
229: {
230: pairs = atoi(argv[2]);
231: }
232: fprintf(stderr, "%d code pairs with constant length\n\n", pairs);
233: groups_left = groups = pairs >> 1;
234:
235: bliss_type = atoi(argv[1]);
236: set = bliss_param_set_get_by_id(bliss_type);
237: if (!set)
238: {
239: fprintf(stderr, "bliss type %d unsupported\n", bliss_type);
240: exit(1);
241: }
242: write_header();
243: printf("/*\n");
244: printf(" * Design: sigma = %u\n", set->sigma);
245: printf(" *\n");
246:
247: t = 1/(sqrt(2) * set->sigma);
248:
249: /* Probability distribution for z1 */
250: i_top = (set->B_inf + 255) / 256;
251: p_sum = 0;
252: x = 0;
253:
254: for (i = 0; i < i_top; i++)
255: {
256: x = min(x + 256, set->B_inf);
257: erf_i = erf(t*x);
258: p_z1[i] = erf_i - erf_0;
259: p_sum += p_z1[i];
260: erf_0 = erf_i;
261: x_z1[i] = x;
262: }
263:
264: /* Normalize and print the probability distribution for z1 */
265: printf(" * i p_z1[i]\n");
266: x0 = 0;
267:
268: for (i = 0; i < i_top; i++)
269: {
270: p_z1[i] /= p_sum;
271: printf(" * %2d %18.16f %4.0f .. %4.0f\n", i, p_z1[i], x0, x_z1[i]);
272: x0 = x_z1[i];
273: }
274: printf(" *\n");
275:
276: /* Probability distribution for z2 */
277: dx = 1 << set->d;
278: k_top = 1 + set->B_inf / dx;
279: x = (dx >> 1) - 0.5;
280: p_sum = 0;
281:
282: for (k = 0; k < k_top; k++)
283: {
284:
285: erf_k = erf(t*x) / 2;
286: p_z2[k] = (k == 0) ? 2*erf_k : erf_k - erf_0;
287: p_sum += (k == 0) ? p_z2[k] : 2*p_z2[k];
288: erf_0 = erf_k;
289: x_z2[k] = x;
290: x += dx;
291: }
292:
293: /* Normalize the probability distribution for z2 */
294: for (k = 0; k < k_top; k++)
295: {
296: p_z2[k] /= p_sum;
297: }
298:
299: /* Print the probability distribution for z2 */
300: printf(" * k p_z2[k] dx = %d\n", dx);
301:
302: for (k = 1 - k_top; k < k_top; k++)
303: {
304:
305: printf(" * %2d %18.16f ",k, p_z2[abs(k)]);
306: if (k < 0)
307: {
308: printf(" %7.1f ..%7.1f\n", -x_z2[-k], -x_z2[-k-1]);
309: }
310: else if (k == 0)
311: {
312: printf(" %7.1f ..%7.1f\n", -x_z2[k], x_z2[k]);
313: }
314: else
315: {
316: printf(" %7.1f ..%7.1f\n", x_z2[k-1], x_z2[k]);
317: }
318: }
319: printf(" *\n");
320:
321: /* Compute probabilities of tuples (z1, z2) */
322: INIT(node_list);
323: node_last = node_list;
324: printf(" * (i, k) p\n");
325: p_sum =0;
326: index = 0;
327:
328: for (i = 0; i < i_top; i++)
329: {
330: for (k = 1 - k_top; k < k_top; k++)
331: {
332: p = p_z1[i] * p_z2[abs(k)];
333: printf(" * (%1d,%2d) %18.16f\n", i, k, p);
334: p_sum += p;
335: entropy += -log(p) * p;
336:
337: INIT(tuple,
338: .z1 = i,
339: .z2 = k,
340: .index = index,
341: );
342: tuples[index++] = tuple;
343:
344: INIT(node,
345: .p = p,
346: .tuple = tuple,
347: );
348: node_last->next = node;
349: node_last = node;
350: }
351: printf(" *\n");
352: }
353: entropy /= log(2);
354: printf(" * p_sum %18.16f\n", p_sum);
355: printf(" *\n");
356: printf(" * entropy = %6.4f bits/tuple (%d bits)\n",
357: entropy, (int)(512 * entropy));
358: printf(" */\n\n");
359:
360: /* Build Huffman tree */
361: while (node_list->next != node_last)
362: {
363: node_r = node_l = NULL;
364:
365: for (node = node_list->next; node; node = node->next)
366: {
367: if (pairs > 0)
368: {
369: if (!node->tuple)
370: {
371: continue;
372: }
373: }
374: else if (groups_left > 0)
375: {
376: if (node->tuple || node->depth != depth)
377: {
378: continue;
379: }
380: }
381: if (node_r == NULL || node->p < node_r->p)
382: {
383: node_l = node_r;
384: node_r = node;
385: }
386: else if (node_l == NULL || node->p < node_l->p)
387: {
388: node_l = node;
389: }
390: }
391:
392: INIT(node,
393: .l = node_l,
394: .r = node_r,
395: .p = node_l->p + node_r->p,
396: .depth = 1 + max(node_l->depth, node_r->depth),
397: .tuple = NULL,
398: );
399: print_node(node_r);
400: print_node(node_l);
401: fprintf(stderr, " %18.16f", node->p);
402:
403: remove_node(node_list, &node_last, node_l);
404: remove_node(node_list, &node_last, node_r);
405: node_last->next = node;
406: node_last = node;
407:
408: if (pairs > 0)
409: {
410: pairs--;
411: }
412: else if (groups > 0)
413: {
414: if (--groups_left == 0)
415: {
416: groups >>= 1;
417: groups_left = groups;
418: depth++;
419: }
420: }
421: fprintf(stderr, "\n\n");
422: }
423:
424:
425: nodes = node_list->next;
426:
427: write_code_tables(bliss_type, i_top, k_top, nodes, tuples);
428:
429: destroy_node(nodes);
430: destroy_node(node_list);
431: exit(0);
432: }
433: