4db6eed887148ca18fa9614bf5a380245919d36e
[mw/micromonitor-lm32.git] / umon_main / host / src / utils / packdata.c
1 /*
2  *      Huffman encoding program 
3  *      Usage:  pack [[ - ] filename ... ] filename ...
4  *              - option: enable/disable listing of statistics
5  *  ELS:
6  *  This is a hack of the original pack.c to support packing of raw data
7  *  within a program.  No files, just memory space.  The entry point is
8  *  the function packdata() below.
9  */
10
11
12 #include  <stdio.h>
13 #include  <stdlib.h>
14 #include <sys/types.h>
15 #include <sys/stat.h>
16
17 //extern        char *malloc();
18
19 typedef unsigned char uchar;
20
21 #define END     256
22 #define NAMELEN 80
23 #define SUF0    '.'
24 #define SUF1    'z'
25
26 /* union for overlaying a long int with a set of four characters */
27 union FOUR {
28         struct { long int lng; } lint;
29         struct { char c0, c1, c2, c3; } chars;
30 };
31
32 /* character counters */
33 static long     count [END+1];
34 static union    FOUR insize;
35 static long     outsize;
36 static long     dictsize;
37 static int      diffbytes;
38
39 /* i/o stuff */
40 static char     inbuff [BUFSIZ];
41 static char     outbuff [BUFSIZ+4];
42
43 /* variables associated with the tree */
44 static int      maxlev;
45 static int      levcount [25];
46 static int      lastnode;
47 static int      parent [2*END+1];
48
49 /* variables associated with the encoding process */
50 static char     length [END+1];
51 static long     bits [END+1];
52 static union    FOUR mask;
53 static long     inc;
54 #if defined(vax) || defined(i386)
55 char    *maskshuff[4]  = {&(mask.chars.c3), &(mask.chars.c2), &(mask.chars.c1), &(mask.chars.c0)};
56 #elif defined(pdp11)
57 char    *maskshuff[4]  = {&(mask.chars.c1), &(mask.chars.c0), &(mask.chars.c3), &(mask.chars.c2)};
58 #else   /* just about everything else */
59 char    *maskshuff[4]  = {&(mask.chars.c0), &(mask.chars.c1), &(mask.chars.c2), &(mask.chars.c3)};
60 #endif
61
62 /* the heap */
63 static int      n;
64 static struct   heap {
65         long int count;
66         int node;
67 } heap [END+2];
68 #define hmove(a,b) {(b).count = (a).count; (b).node = (a).node;}
69
70 /* encode the current file */
71 /* return 1 if successful, 0 otherwise */
72 static
73 output ()
74 {
75         extern long lseek();
76         int c, i, inleft;
77         char *inp;
78         register char **q, *outp;
79         register int bitsleft;
80         long temp;
81
82         /* output ``PACKED'' header */
83         outbuff[0] = 037;       /* ascii US */
84         outbuff[1] = 036;       /* ascii RS */
85         /* output the length and the dictionary */
86         temp = insize.lint.lng;
87         for (i=5; i>=2; i--) {
88                 outbuff[i] =  (char) (temp & 0377);
89                 temp >>= 8;
90         }
91         outp = &outbuff[6];
92         *outp++ = maxlev;
93         for (i=1; i<maxlev; i++)
94                 *outp++ = levcount[i];
95         *outp++ = levcount[maxlev]-2;
96         for (i=1; i<=maxlev; i++)
97                 for (c=0; c<END; c++)
98                         if (length[c] == i)
99                                 *outp++ = c;
100         dictsize = outp-&outbuff[0];
101
102         /* output the text */
103         outsize = 0;
104         bitsleft = 8;
105         inleft = 0;
106         do {
107                 if (inleft <= 0) {
108                         inleft = getdata(inp = &inbuff[0], BUFSIZ);
109                         if (inleft < 0) {
110                                 fprintf(stderr,": getdata() error");
111                                 return (0);
112                         }
113                 }
114                 c = (--inleft < 0) ? END : (*inp++ & 0377);
115                 mask.lint.lng = bits[c]<<bitsleft;
116                 q = &maskshuff[0];
117                 if (bitsleft == 8)
118                         *outp = **q++;
119                 else
120                         *outp |= **q++;
121                 bitsleft -= length[c];
122                 while (bitsleft < 0) {
123                         *++outp = **q++;
124                         bitsleft += 8;
125                 }
126                 if (outp >= &outbuff[BUFSIZ]) {
127                         putdata(outbuff, BUFSIZ);
128                         ((union FOUR *) outbuff)->lint.lng = ((union FOUR *) &outbuff[BUFSIZ])->lint.lng;
129                         outp -= BUFSIZ;
130                         outsize += BUFSIZ;
131                 }
132         } while (c != END);
133         if (bitsleft < 8)
134                 outp++;
135         c = outp-outbuff;
136         putdata(outbuff,c);
137         outsize += c;
138         return (1);
139 }
140
141 /* makes a heap out of heap[i],...,heap[n] */
142 static
143 heapify (i)
144 {
145         register int k;
146         int lastparent;
147         struct heap heapsubi;
148         hmove (heap[i], heapsubi);
149         lastparent = n/2;
150         while (i <= lastparent) {
151                 k = 2*i;
152                 if (heap[k].count > heap[k+1].count && k < n)
153                         k++;
154                 if (heapsubi.count < heap[k].count)
155                         break;
156                 hmove (heap[k], heap[i]);
157                 i = k;
158         }
159         hmove (heapsubi, heap[i]);
160 }
161
162 /* return 1 after successful packing, 0 otherwise */
163 static int
164 packbuffer()
165 {
166         register int c, i, p;
167         long bitsout;
168
169         /* put occurring chars in heap with their counts */
170         diffbytes = -1;
171         count[END] = 1;
172         insize.lint.lng = n = 0;
173         for (i=END; i>=0; i--) {
174                 parent[i] = 0;
175                 if (count[i] > 0) {
176                         diffbytes++;
177                         insize.lint.lng += count[i];
178                         heap[++n].count = count[i];
179                         heap[n].node = i;
180                 }
181         }
182         if (diffbytes == 1) {
183                 fprintf(stderr,": trivial file");
184                 return (0);
185         }
186         insize.lint.lng >>= 1;
187         for (i=n/2; i>=1; i--)
188                 heapify(i);
189
190         /* build Huffman tree */
191         lastnode = END;
192         while (n > 1) {
193                 parent[heap[1].node] = ++lastnode;
194                 inc = heap[1].count;
195                 hmove (heap[n], heap[1]);
196                 n--;
197                 heapify(1);
198                 parent[heap[1].node] = lastnode;
199                 heap[1].node = lastnode;
200                 heap[1].count += inc;
201                 heapify(1);
202         }
203         parent[lastnode] = 0;
204
205         /* assign lengths to encoding for each character */
206         bitsout = maxlev = 0;
207         for (i=1; i<=24; i++)
208                 levcount[i] = 0;
209         for (i=0; i<=END; i++) {
210                 c = 0;
211                 for (p=parent[i]; p!=0; p=parent[p])
212                         c++;
213                 levcount[c]++;
214                 length[i] = c;
215                 if (c > maxlev)
216                         maxlev = c;
217                 bitsout += c*(count[i]>>1);
218         }
219         if (maxlev > 24) {
220                 /* can't occur unless insize.lint.lng >= 2**24 */
221                 fprintf(stderr,": Huffman tree has too many levels");
222                 return(0);
223         }
224
225         /* don't bother if no compression results */
226         outsize = ((bitsout+7)>>3)+6+maxlev+diffbytes;
227         if ((insize.lint.lng+BUFSIZ-1)/BUFSIZ <= (outsize+BUFSIZ-1)/BUFSIZ) {
228                 fprintf(stderr,"no saving");
229                 return(0);
230         }
231
232         /* compute bit patterns for each character */
233         inc = 1L << 24;
234         inc >>= maxlev;
235         mask.lint.lng = 0;
236         for (i=maxlev; i>0; i--) {
237                 for (c=0; c<=END; c++)
238                         if (length[c] == i) {
239                                 bits[c] = mask.lint.lng;
240                                 mask.lint.lng += inc;
241                         }
242                 mask.lint.lng &= ~inc;
243                 inc <<= 1;
244         }
245         return (output());
246 }
247
248 int sourceSize;
249 char *sourceBase;
250 char *destBase;
251
252 getdata(buffer,size)
253 char    *buffer;
254 int             size;
255 {
256         int     i, tot;
257
258         if (size < sourceSize)
259                 tot = size;
260         else
261                 tot = sourceSize;
262
263         sourceSize -= tot;
264         for(i=0;i<tot;i++)
265                 *buffer++ = *sourceBase++;
266         return(tot);
267 }
268
269 putdata(buffer,size)
270 char    *buffer;
271 int             size;
272 {
273         int     i;
274
275         for(i=0;i<size;i++)
276                 *destBase++ = *buffer++;
277         return(size);
278 }
279
280 packdata(src,dest,srcsize,verbose)
281 char    *src, *dest;
282 int             srcsize, verbose;
283 {
284         int     i;
285
286         sourceSize = srcsize;
287         sourceBase = src;
288         destBase = dest;
289
290         /* Gather character frequency statistics */
291         for (i=0; i<END; i++)
292                 count[i] = 0;
293         for(i=0;i<srcsize;i++)
294                 count[(src[i]&0xff)] += 2;
295
296         if (!packbuffer()) {
297                 fprintf(stderr," - file unchanged\n");
298                 return(0);
299         }
300
301         if (verbose) {
302                 printf("%d%% compression (from %d to %d bytes)\n",
303                         (int)(((double)(-outsize+(insize.lint.lng))/
304                          (double)insize.lint.lng)*100),insize.lint.lng, outsize);
305         }
306
307         return(outsize);
308 }