[3365] | 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 | */
|
---|
| 31 | huff_data *
|
---|
| 32 | Generate_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 */
|
---|
[8692] | 58 | for (count = i = 0; i < num; ++i)
|
---|
[3365] | 59 | if (heap[num + i])
|
---|
| 60 | heap[count++] = num + i;
|
---|
| 61 |
|
---|
| 62 | /* Reorganise the pointers so that it is a heap */
|
---|
| 63 | HNum = count;
|
---|
[8692] | 64 | for (i = HNum / 2; i > 0; --i)
|
---|
[3365] | 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]])
|
---|
[8692] | 72 | ++child;
|
---|
[3365] | 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 |
|
---|
[8692] | 93 | for (i = 0; i < 2; ++i)
|
---|
[3365] | 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]])
|
---|
[8692] | 104 | ++child;
|
---|
[3365] | 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;
|
---|
[8692] | 126 | ++HNum;
|
---|
[3365] | 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;
|
---|
[8692] | 145 | for (i = 2; i < num * 2; ++i)
|
---|
[3365] | 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 */
|
---|
[8692] | 154 | for (i = 0; i < num; ++i)
|
---|
[3365] | 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;
|
---|
[8692] | 164 | ++hd->lencount[codelen];
|
---|
[3365] | 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;
|
---|
[8692] | 176 | for (i = hd->maxcodelen - 1; i>=0; --i)
|
---|
[3365] | 177 | hd->min_code[i] = (hd->min_code[i + 1] + hd->lencount[i + 1]) >> 1;
|
---|
| 178 | }
|
---|
[8692] | 179 | delete []heap;
|
---|
[3365] | 180 | return (hd);
|
---|
| 181 |
|
---|
| 182 | error2:
|
---|
[8692] | 183 | delete []heap;
|
---|
[3365] | 184 | error1:
|
---|
| 185 | if (!data)
|
---|
| 186 | delete hd;
|
---|
| 187 | error0:
|
---|
| 188 | return (NULL);
|
---|
| 189 |
|
---|
| 190 | }
|
---|
| 191 |
|
---|
| 192 | unsigned long *
|
---|
| 193 | Generate_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));
|
---|
[8692] | 206 | for (i = 0; i < data->num_codes; ++i)
|
---|
[3365] | 207 | if (data->clens[i])
|
---|
| 208 | codes[i] = mc[(int) (data->clens[i])]++;
|
---|
| 209 |
|
---|
| 210 | return (codes);
|
---|
| 211 | }
|
---|
| 212 |
|
---|
| 213 |
|
---|
| 214 | unsigned long **
|
---|
| 215 | Generate_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 | {
|
---|
[8692] | 228 | delete []vals;
|
---|
[3365] | 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];
|
---|
[8692] | 239 | for (i = 1; i <= data->maxcodelen; ++i)
|
---|
[3365] | 240 | fcode[i] = values[i] = &vals[(values[i - 1] - vals) + data->lencount[i - 1]];
|
---|
| 241 |
|
---|
[8692] | 242 | for (i = 0; i < data->num_codes; ++i)
|
---|
[3365] | 243 | if (data->clens[i])
|
---|
| 244 | *fcode[(int) (data->clens[i])]++ = i;
|
---|
| 245 | return (values);
|
---|
| 246 | }
|
---|
| 247 |
|
---|
| 248 |
|
---|
| 249 |
|
---|
| 250 | double
|
---|
| 251 | Calculate_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;
|
---|
[8692] | 258 | for (i = 0; i < num; ++i)
|
---|
[3365] | 259 | size += counts[i] * hd.clens[i];
|
---|
[8692] | 260 | delete []hd.clens;
|
---|
[3365] | 261 | return size;
|
---|
| 262 | }
|
---|
| 263 |
|
---|
| 264 |
|
---|
| 265 |
|
---|
| 266 | int
|
---|
| 267 | Write_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;
|
---|
[8692] | 292 | for (i = hd->mincodelen; i < hd->maxcodelen + 1; ++i)
|
---|
[3365] | 293 | HTONSI(hd->lencount[i]);
|
---|
[8692] | 294 | for (i = 0; i < hd->maxcodelen + 1; ++i)
|
---|
[3365] | 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] */
|
---|
[8692] | 310 | for (i = hd->mincodelen; i < hd->maxcodelen + 1; ++i)
|
---|
[3365] | 311 | NTOHSI(hd->lencount[i]);
|
---|
[8692] | 312 | for (i = 0; i < hd->maxcodelen + 1; ++i)
|
---|
[3365] | 313 | NTOHUL(hd->min_code[i]);
|
---|
| 314 | }
|
---|
| 315 | return 0;
|
---|
| 316 | }
|
---|
| 317 |
|
---|
| 318 |
|
---|
| 319 |
|
---|
| 320 | int 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] */
|
---|
[8692] | 352 | for (i = hd->mincodelen; i < hd->maxcodelen + 1; ++i)
|
---|
[3365] | 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] */
|
---|
[8692] | 365 | for (i = 0; i < hd->maxcodelen + 1; ++i)
|
---|
[3365] | 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 | }
|
---|