C/HuffEnc.c

   1 /* HuffEnc.c -- functions for Huffman encoding\r
   2 2009-09-02 : Igor Pavlov : Public domain */\r
   3 \r
   4 #include "HuffEnc.h"\r
   5 #include "Sort.h"\r
   6 \r
   7 #define kMaxLen 16\r
   8 #define NUM_BITS 10\r
   9 #define MASK ((1 << NUM_BITS) - 1)\r
  10 \r
  11 #define NUM_COUNTERS 64\r
  12 \r
  13 #define HUFFMAN_SPEED_OPT\r
  14 \r
  15 void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 numSymbols, UInt32 maxLen)\r
  16 {\r
  17   UInt32 num = 0;\r
  18   /* if (maxLen > 10) maxLen = 10; */\r
  19   {\r
  20     UInt32 i;\r
  21     \r
  22     #ifdef HUFFMAN_SPEED_OPT\r
  23     \r
  24     UInt32 counters[NUM_COUNTERS];\r
  25     for (i = 0; i < NUM_COUNTERS; i++)\r
  26       counters[i] = 0;\r
  27     for (i = 0; i < numSymbols; i++)\r
  28     {\r
  29       UInt32 freq = freqs[i];\r
  30       counters[(freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1]++;\r
  31     }\r
  32  \r
  33     for (i = 1; i < NUM_COUNTERS; i++)\r
  34     {\r
  35       UInt32 temp = counters[i];\r
  36       counters[i] = num;\r
  37       num += temp;\r
  38     }\r
  39 \r
  40     for (i = 0; i < numSymbols; i++)\r
  41     {\r
  42       UInt32 freq = freqs[i];\r
  43       if (freq == 0)\r
  44         lens[i] = 0;\r
  45       else\r
  46         p[counters[((freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1)]++] = i | (freq << NUM_BITS);\r
  47     }\r
  48     counters[0] = 0;\r
  49     HeapSort(p + counters[NUM_COUNTERS - 2], counters[NUM_COUNTERS - 1] - counters[NUM_COUNTERS - 2]);\r
  50     \r
  51     #else\r
  52 \r
  53     for (i = 0; i < numSymbols; i++)\r
  54     {\r
  55       UInt32 freq = freqs[i];\r
  56       if (freq == 0)\r
  57         lens[i] = 0;\r
  58       else\r
  59         p[num++] = i | (freq << NUM_BITS);\r
  60     }\r
  61     HeapSort(p, num);\r
  62 \r
  63     #endif\r
  64   }\r
  65 \r
  66   if (num < 2)\r
  67   {\r
  68     unsigned minCode = 0;\r
  69     unsigned maxCode = 1;\r
  70     if (num == 1)\r
  71     {\r
  72       maxCode = (unsigned)p[0] & MASK;\r
  73       if (maxCode == 0)\r
  74         maxCode++;\r
  75     }\r
  76     p[minCode] = 0;\r
  77     p[maxCode] = 1;\r
  78     lens[minCode] = lens[maxCode] = 1;\r
  79     return;\r
  80   }\r
  81   \r
  82   {\r
  83     UInt32 b, e, i;\r
  84   \r
  85     i = b = e = 0;\r
  86     do\r
  87     {\r
  88       UInt32 n, m, freq;\r
  89       n = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;\r
  90       freq = (p[n] & ~MASK);\r
  91       p[n] = (p[n] & MASK) | (e << NUM_BITS);\r
  92       m = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;\r
  93       freq += (p[m] & ~MASK);\r
  94       p[m] = (p[m] & MASK) | (e << NUM_BITS);\r
  95       p[e] = (p[e] & MASK) | freq;\r
  96       e++;\r
  97     }\r
  98     while (num - e > 1);\r
  99     \r
 100     {\r
 101       UInt32 lenCounters[kMaxLen + 1];\r
 102       for (i = 0; i <= kMaxLen; i++)\r
 103         lenCounters[i] = 0;\r
 104       \r
 105       p[--e] &= MASK;\r
 106       lenCounters[1] = 2;\r
 107       while (e > 0)\r
 108       {\r
 109         UInt32 len = (p[p[--e] >> NUM_BITS] >> NUM_BITS) + 1;\r
 110         p[e] = (p[e] & MASK) | (len << NUM_BITS);\r
 111         if (len >= maxLen)\r
 112           for (len = maxLen - 1; lenCounters[len] == 0; len--);\r
 113         lenCounters[len]--;\r
 114         lenCounters[len + 1] += 2;\r
 115       }\r
 116       \r
 117       {\r
 118         UInt32 len;\r
 119         i = 0;\r
 120         for (len = maxLen; len != 0; len--)\r
 121         {\r
 122           UInt32 num;\r
 123           for (num = lenCounters[len]; num != 0; num--)\r
 124             lens[p[i++] & MASK] = (Byte)len;\r
 125         }\r
 126       }\r
 127       \r
 128       {\r
 129         UInt32 nextCodes[kMaxLen + 1];\r
 130         {\r
 131           UInt32 code = 0;\r
 132           UInt32 len;\r
 133           for (len = 1; len <= kMaxLen; len++)\r
 134             nextCodes[len] = code = (code + lenCounters[len - 1]) << 1;\r
 135         }\r
 136         /* if (code + lenCounters[kMaxLen] - 1 != (1 << kMaxLen) - 1) throw 1; */\r
 137 \r
 138         {\r
 139           UInt32 i;\r
 140           for (i = 0; i < numSymbols; i++)\r
 141             p[i] = nextCodes[lens[i]]++;\r
 142         }\r
 143       }\r
 144     }\r
 145   }\r
 146 }\r