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

Last change on this file since 3159 was 2928, checked in by jrm21, 22 years ago

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