vcs.maemo.org Git - physicsfs/blob - lzma/C/Compress/Huffman/HuffmanEncode.c

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