source: trunk/gsdl/packages/mg/lib/huffman.c@ 10853

Last change on this file since 10853 was 439, checked in by sjboddie, 25 years ago

renamed mg-1.3d directory mg
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
File size: 9.9 KB
Line 
1/**************************************************************************
2 *
3 * huffman.c -- Huffman coding functions
4 * Copyright (C) 1994 Neil Sharman
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 *
20 * $Id: huffman.c 439 1999-08-10 21:23:37Z sjboddie $
21 *
22 **************************************************************************/
23
24/*
25 $Log$
26 Revision 1.1 1999/08/10 21:16:51 sjboddie
27 renamed mg-1.3d directory mg
28
29 Revision 1.1 1998/11/17 09:32:03 rjmcnab
30 *** empty log message ***
31
32 * Revision 1.1 1994/08/22 00:24:44 tes
33 * Initial placement under CVS.
34 *
35 */
36
37static char *RCSID = "$Id: huffman.c 439 1999-08-10 21:23:37Z sjboddie $";
38
39#include "sysfuncs.h"
40#include "memlib.h"
41#include "huffman.h"
42#include "messages.h"
43#include "netorder.h" /* [RPAP - Jan 97: Endian Ordering] */
44
45/* ->data on success,
46 NULL on error
47 */
48huff_data *
49Generate_Huffman_Data (int num, long *freqs, huff_data * data,
50 u_long * mem)
51{
52 int HNum, i, count;
53 unsigned long *heap;
54 huff_data *hd = data;
55 if (!hd)
56 {
57 if (!(hd = Xmalloc (sizeof (huff_data))))
58 goto error0;
59 }
60 if (!(heap = Xmalloc (num * 2 * sizeof (*heap))))
61 goto error1;
62 if (!(hd->clens = Xmalloc (num * sizeof (char))))
63 goto error2;
64 hd->num_codes = num;
65 if (mem)
66 {
67 if (hd != data)
68 *mem += sizeof (huff_data);
69 *mem += num * sizeof (char);
70 }
71 bcopy ((char *) freqs, (char *) &heap[num], num * sizeof (*heap));
72 bzero ((char *) heap, num * sizeof (*heap));
73
74 /* Initialise the pointers to the leaves */
75 for (count = i = 0; i < num; i++)
76 if (heap[num + i])
77 heap[count++] = num + i;
78
79 /* Reorganise the pointers so that it is a heap */
80 HNum = count;
81 for (i = HNum / 2; i > 0; i--)
82 {
83 register int curr, child;
84 curr = i;
85 child = curr * 2;
86 while (child <= HNum)
87 {
88 if (child < HNum && heap[heap[child]] < heap[heap[child - 1]])
89 child++;
90 if (heap[heap[curr - 1]] > heap[heap[child - 1]])
91 {
92 register u_long temp;
93 temp = heap[child - 1];
94 heap[child - 1] = heap[curr - 1];
95 heap[curr - 1] = temp;
96 curr = child;
97 child = 2 * curr;
98 }
99 else
100 break;
101 }
102 }
103
104
105 /* Form the huffman tree */
106 while (HNum > 1)
107 {
108 int pos[2];
109
110 for (i = 0; i < 2; i++)
111 {
112 register int curr, child;
113 pos[i] = heap[0];
114 heap[0] = heap[--HNum];
115 curr = 1;
116 child = 2;
117 while (child <= HNum)
118 {
119 if (child < HNum &&
120 heap[heap[child]] < heap[heap[child - 1]])
121 child++;
122 if (heap[heap[curr - 1]] > heap[heap[child - 1]])
123 {
124 register int temp;
125 temp = heap[child - 1];
126 heap[child - 1] = heap[curr - 1];
127 heap[curr - 1] = temp;
128 curr = child;
129 child = 2 * curr;
130 }
131 else
132 break;
133 }
134 }
135
136 heap[HNum + 1] = heap[pos[0]] + heap[pos[1]];
137 heap[pos[0]] = heap[pos[1]] = HNum + 1;
138
139 heap[HNum] = HNum + 1;
140
141 {
142 register int parent, curr;
143 HNum++;
144 curr = HNum;
145 parent = curr >> 1;
146 while (parent && heap[heap[parent - 1]] > heap[heap[curr - 1]])
147 {
148 register int temp;
149 temp = heap[parent - 1];
150 heap[parent - 1] = heap[curr - 1];
151 heap[curr - 1] = temp;
152 curr = parent;
153 parent = curr >> 1;
154 }
155 }
156 }
157
158
159 /* Calculate the code lens */
160 heap[0] = -1UL;
161 heap[1] = 0;
162 for (i = 2; i < num * 2; i++)
163 heap[i] = heap[heap[i]] + 1;
164
165 /* zero the lencount's array */
166 bzero ((char *) hd->lencount, sizeof (hd->lencount));
167 hd->maxcodelen = 0;
168 hd->mincodelen = 100;
169
170 /* Set the code length of each leaf in the huffman tree */
171 for (i = 0; i < num; i++)
172 {
173 register u_long codelen = heap[i + num];
174 hd->clens[i] = (char) codelen;
175 if (!codelen)
176 continue;
177 if (codelen > hd->maxcodelen)
178 hd->maxcodelen = codelen;
179 if (codelen < hd->mincodelen)
180 hd->mincodelen = codelen;
181 hd->lencount[codelen]++;
182 }
183
184
185 if (hd->maxcodelen == 0 && hd->mincodelen == 100)
186 {
187 hd->num_codes = 0;
188 }
189 else
190 {
191 /* Calculate the current codes for each different code length */
192 hd->min_code[hd->maxcodelen] = 0;
193 for (i = hd->maxcodelen - 1; i>=0; i--)
194 hd->min_code[i] = (hd->min_code[i + 1] + hd->lencount[i + 1]) >> 1;
195 }
196 free (heap);
197 return (hd);
198
199error2:
200 free (heap);
201error1:
202 if (!data)
203 free (hd);
204error0:
205 return (NULL);
206
207}
208
209unsigned long *
210Generate_Huffman_Codes (huff_data * data, u_long * mem)
211{
212 int i;
213 unsigned long *codes;
214 unsigned long mc[MAX_HUFFCODE_LEN + 1];
215
216 if (!data)
217 return (NULL);
218 if (!(codes = Xmalloc (data->num_codes * sizeof (*codes))))
219 return (NULL);
220 if (mem)
221 *mem += data->num_codes * sizeof (*codes);
222 bcopy ((char *) data->min_code, (char *) mc, sizeof (mc));
223 for (i = 0; i < data->num_codes; i++)
224 if (data->clens[i])
225 codes[i] = mc[(int) (data->clens[i])]++;
226
227 return (codes);
228}
229
230
231unsigned long **
232Generate_Huffman_Vals (huff_data * data, u_long * mem)
233{
234 int i;
235 unsigned long *fcode[MAX_HUFFCODE_LEN + 1];
236 unsigned long **values;
237 unsigned long *vals;
238
239 if (!data)
240 return (NULL);
241 if (!(vals = Xmalloc (data->num_codes * sizeof (*vals))))
242 return (NULL);
243 if (!(values = Xmalloc ((MAX_HUFFCODE_LEN + 1) * sizeof (unsigned long *))))
244 {
245 free (vals);
246 return (NULL);
247 }
248
249 bzero ((char *) values, (MAX_HUFFCODE_LEN + 1) * sizeof (unsigned long *));
250
251 if (mem)
252 *mem += data->num_codes * sizeof (*vals) +
253 (MAX_HUFFCODE_LEN + 1) * sizeof (unsigned long *);
254
255 fcode[0] = values[0] = &vals[0];
256 for (i = 1; i <= data->maxcodelen; i++)
257 fcode[i] = values[i] = &vals[(values[i - 1] - vals) + data->lencount[i - 1]];
258
259 for (i = 0; i < data->num_codes; i++)
260 if (data->clens[i])
261 *fcode[(int) (data->clens[i])]++ = i;
262 return (values);
263}
264
265
266
267double
268Calculate_Huffman_Size (int num, long *freqs, long *counts)
269{
270 double size = 0;
271 huff_data hd;
272 int i;
273 if (!Generate_Huffman_Data (num, freqs, &hd, NULL))
274 return -1;
275 for (i = 0; i < num; i++)
276 size += counts[i] * hd.clens[i];
277 Xfree (hd.clens);
278 return size;
279}
280
281
282
283int
284Write_Huffman_Data (FILE * f, huff_data * hd)
285{
286 /* [RPAP - Jan 97: Endian Ordering] */
287 HTONSI(hd->num_codes);
288 HTONSI(hd->mincodelen);
289 HTONSI(hd->maxcodelen);
290
291 if (fwrite (&hd->num_codes, sizeof (hd->num_codes), 1, f) != 1)
292 return -1;
293
294 if (fwrite (&hd->mincodelen, sizeof (hd->mincodelen), 1, f) != 1)
295 return -1;
296
297 if (fwrite (&hd->maxcodelen, sizeof (hd->maxcodelen), 1, f) != 1)
298 return -1;
299
300 /* [RPAP - Jan 97: Endian Ordering] */
301 NTOHSI(hd->num_codes);
302 NTOHSI(hd->mincodelen);
303 NTOHSI(hd->maxcodelen);
304
305 if (hd->num_codes)
306 {
307 /* [RPAP - Jan 97: Endian Ordering] */
308 int i;
309 for (i = hd->mincodelen; i < hd->maxcodelen + 1; i++)
310 HTONSI(hd->lencount[i]);
311 for (i = 0; i < hd->maxcodelen + 1; i++)
312 HTONUL(hd->min_code[i]);
313
314 if (fwrite (hd->lencount + hd->mincodelen, sizeof (*hd->lencount),
315 hd->maxcodelen - hd->mincodelen + 1, f) !=
316 hd->maxcodelen - hd->mincodelen + 1)
317 return -1;
318
319 if (fwrite (hd->min_code, sizeof (*hd->min_code), hd->maxcodelen + 1, f) !=
320 hd->maxcodelen + 1)
321 return -1;
322
323 if (fwrite (hd->clens, sizeof (*hd->clens), hd->num_codes, f) != hd->num_codes)
324 return -1;
325
326 /* [RPAP - Jan 97: Endian Ordering] */
327 for (i = hd->mincodelen; i < hd->maxcodelen + 1; i++)
328 NTOHSI(hd->lencount[i]);
329 for (i = 0; i < hd->maxcodelen + 1; i++)
330 NTOHUL(hd->min_code[i]);
331 }
332 return 0;
333}
334
335
336
337
338static int
339General_Read_Huffman_Data (size_t (*rd) (), void *f,
340 huff_data * hd, u_long * mem, u_long * disk)
341{
342 if (rd (&hd->num_codes, sizeof (hd->num_codes), 1, f) != 1)
343 return -1;
344
345 if (rd (&hd->mincodelen, sizeof (hd->mincodelen), 1, f) != 1)
346 return -1;
347
348 if (rd (&hd->maxcodelen, sizeof (hd->maxcodelen), 1, f) != 1)
349 return -1;
350
351 /* [RPAP - Jan 97: Endian Ordering] */
352 NTOHSI(hd->num_codes);
353 NTOHSI(hd->mincodelen);
354 NTOHSI(hd->maxcodelen);
355
356 if (disk)
357 (*disk) += sizeof (hd->num_codes) + sizeof (hd->mincodelen) +
358 sizeof (hd->maxcodelen);
359
360 hd->clens = NULL;
361
362 if (hd->num_codes)
363 {
364 int i; /* [RPAP - Jan 97: Endian Ordering] */
365
366 bzero ((char *) (hd->lencount), sizeof (hd->lencount));
367 if (rd (hd->lencount + hd->mincodelen, sizeof (*hd->lencount),
368 hd->maxcodelen - hd->mincodelen + 1, f) !=
369 hd->maxcodelen - hd->mincodelen + 1)
370 return -1;
371
372 /* [RPAP - Jan 97: Endian Ordering] */
373 for (i = hd->mincodelen; i < hd->maxcodelen + 1; i++)
374 NTOHSI(hd->lencount[i]);
375
376 if (disk)
377 (*disk) += sizeof (*hd->lencount) * (hd->maxcodelen - hd->mincodelen + 1);
378
379 bzero ((char *) (hd->min_code), sizeof (hd->min_code));
380
381 if (rd (hd->min_code, sizeof (*hd->min_code), hd->maxcodelen + 1, f) !=
382 hd->maxcodelen + 1)
383 return -1;
384
385 /* [RPAP - Jan 97: Endian Ordering] */
386 for (i = 0; i < hd->maxcodelen + 1; i++)
387 NTOHUL(hd->min_code[i]);
388
389 if (disk)
390 (*disk) += sizeof (*hd->min_code) * (hd->maxcodelen + 1);
391
392 if (!(hd->clens = Xmalloc (sizeof (*hd->clens) * hd->num_codes)))
393 return -1;
394
395
396 if (rd (hd->clens, sizeof (*hd->clens), hd->num_codes, f) != hd->num_codes)
397 return -1;
398
399 if (disk)
400 (*disk) += sizeof (*hd->clens) * hd->num_codes;
401 }
402
403 if (mem)
404 *mem += sizeof (*hd->clens) * hd->num_codes;
405 return 0;
406}
407
408
409
410int
411Read_Huffman_Data (FILE * f, huff_data * hd, u_long * mem, u_long * disk)
412{
413 return General_Read_Huffman_Data (fread, f, hd, mem, disk);
414}
415
416
417
418
419int
420F_Read_Huffman_Data (File * f, huff_data * hd, u_long * mem, u_long * disk)
421{
422 return General_Read_Huffman_Data (Fread, f, hd, mem, disk);
423}
Note: See TracBrowser for help on using the repository browser.