source: trunk/gsdl/src/mgpp/lib/huffman.cpp@ 855

Last change on this file since 855 was 855, checked in by sjboddie, 24 years ago

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