1 #include <string.h>
2 #include <stdlib.h>
3 #include <assert.h>
4
5 #include "fraenkel_compress.h"
6
compress_fraenkel(unsigned char * src,unsigned char * dst,unsigned int len)7 unsigned int compress_fraenkel(
8 unsigned char * src,
9 unsigned char * dst,
10 unsigned int len
11 ) {
12 int i,j,r,s = 0,q=0;
13 char * tmp = malloc(len);
14 char * msrc = src;
15 assert(len<1024*256);
16 do {
17 for(s=0,r=0,j=0,i=0;i<len;i++) {
18 if (msrc[i]) {
19 dst[ q++ ] = msrc[i];
20 r |= 1<< (i & 7);
21 };
22 if (i % 8 == 7) {
23 tmp[ s++ ] = r;
24 r = 0;
25 };
26 };
27 if (i % 8) {
28 tmp[ s++ ] = r;
29 };
30 len = s;
31 msrc = tmp;
32 } while(len != 1);
33 dst[ q++ ] = tmp[0];
34 return q;
35 }
36
expand_fraenkel(unsigned char * src,unsigned char * odst,unsigned int len)37 unsigned int expand_fraenkel(
38 unsigned char * src,
39 unsigned char * odst,
40 unsigned int len
41 ) {
42 char dst[ 1024*256 ];
43 int s = len;
44 int pass = 1;
45 int i = 0, f = 0,j;
46 dst[i++]=src[--s];
47 do {
48 int F = f; /* start of previous run */
49 f = i; /* start of this run */
50 for(j=0;j<pass;j++) {
51 int k;
52 int m = dst[ F+j ]; /* pick up the N values from the previous run. */
53 for(k=0;k<8;k++) {
54 int bit = 7-k;
55 if (m & (1<<bit)) {
56 dst[i++] = src[ --s ];
57 } else {
58 dst[i++] = 0;
59 }
60 };
61 };
62 pass *= 8;
63 } while(s > 0);
64
65 /* last run, from f until i and swap */
66 for(j=0;i>f;)
67 odst[j++] = dst[--i];
68
69 return j;
70 }
71
72 #ifdef TEST_FRAENKEL
main(int argc,char ** argv)73 int main(int argc, char ** argv) {
74 unsigned char a[] = {
75 /* 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 */
76 0,0,1,4,0,0,0,1, 5,0,0,0,7,0,0,0, 0,0,0,7,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,7,0, 0,0,0,0,0,0,0,0,
77 0,0,0,0,0,0,0,0, 0,7,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,7,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,7,
78 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,7,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,7,0,0, 0,0,0,0,0,0,0,0,
79 0,0,1,4,0,0,0,1,99,0,0,0,7,0,0,0, 0,0,0,7,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,
80 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,
81 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,
82 0,0,0,0,0,0,0,0, 7,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,7,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,7,0,
83 0,0,0,0,0,0,0,0, 7,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,7,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,7,0
84 };
85 unsigned char b[ 1024 ];
86 unsigned char c[ 1024 ];
87 int i,l,m;
88
89 printf("in :");
90 for(i=0;i<sizeof(a);i++)
91 printf("%02x ",a[i]);
92 printf("\n");
93 l = compress_fraenkel(a,b,sizeof(a));
94
95 printf("cmp :");
96 for(i=0;i<l;i++)
97 printf("%02x ",b[i]);
98 printf("\n");
99
100 m = expand_fraenkel(b,c,l);
101
102 printf("out :");
103 for(i=0;i<m;i++) {
104 int x = 0;
105 if (i<sizeof(a)) x=a[i];
106 printf("%02x%c",c[i], (x == c[i]) ? ' ' : '!');
107 }
108 printf("\n");
109
110 printf("Size %d -> %d (%.02f) -> %d\n",sizeof(a),l,100.0*l/sizeof(a),m);
111
112 return(0);
113 }
114 #endif
115
116