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