rlm@1: /* HuffEnc.c -- functions for Huffman encoding
rlm@1: 2008-08-05
rlm@1: Igor Pavlov
rlm@1: Public domain */
rlm@1: 
rlm@1: #include "HuffEnc.h"
rlm@1: #include "Sort.h"
rlm@1: 
rlm@1: #define kMaxLen 16
rlm@1: #define NUM_BITS 10
rlm@1: #define MASK ((1 << NUM_BITS) - 1)
rlm@1: 
rlm@1: #define NUM_COUNTERS 64
rlm@1: 
rlm@1: #define HUFFMAN_SPEED_OPT
rlm@1: 
rlm@1: void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 numSymbols, UInt32 maxLen)
rlm@1: {
rlm@1:   UInt32 num = 0;
rlm@1:   /* if (maxLen > 10) maxLen = 10; */
rlm@1:   {
rlm@1:     UInt32 i;
rlm@1:     
rlm@1:     #ifdef HUFFMAN_SPEED_OPT
rlm@1:     
rlm@1:     UInt32 counters[NUM_COUNTERS];
rlm@1:     for (i = 0; i < NUM_COUNTERS; i++)
rlm@1:       counters[i] = 0;
rlm@1:     for (i = 0; i < numSymbols; i++)
rlm@1:     {
rlm@1:       UInt32 freq = freqs[i];
rlm@1:       counters[(freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1]++;
rlm@1:     }
rlm@1:  
rlm@1:     for (i = 1; i < NUM_COUNTERS; i++)
rlm@1:     {
rlm@1:       UInt32 temp = counters[i];
rlm@1:       counters[i] = num;
rlm@1:       num += temp;
rlm@1:     }
rlm@1: 
rlm@1:     for (i = 0; i < numSymbols; i++)
rlm@1:     {
rlm@1:       UInt32 freq = freqs[i];
rlm@1:       if (freq == 0)
rlm@1:         lens[i] = 0;
rlm@1:       else
rlm@1:         p[counters[((freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1)]++] = i | (freq << NUM_BITS);
rlm@1:     }
rlm@1:     counters[0] = 0;
rlm@1:     HeapSort(p + counters[NUM_COUNTERS - 2], counters[NUM_COUNTERS - 1] - counters[NUM_COUNTERS - 2]);
rlm@1:     
rlm@1:     #else
rlm@1: 
rlm@1:     for (i = 0; i < numSymbols; i++)
rlm@1:     {
rlm@1:       UInt32 freq = freqs[i];
rlm@1:       if (freq == 0)
rlm@1:         lens[i] = 0;
rlm@1:       else
rlm@1:         p[num++] = i | (freq << NUM_BITS);
rlm@1:     }
rlm@1:     HeapSort(p, num);
rlm@1: 
rlm@1:     #endif
rlm@1:   }
rlm@1: 
rlm@1:   if (num < 2)
rlm@1:   {
rlm@1:     int minCode = 0;
rlm@1:     int maxCode = 1;
rlm@1:     if (num == 1)
rlm@1:     {
rlm@1:       maxCode = (int)(p[0] & MASK);
rlm@1:       if (maxCode == 0)
rlm@1:         maxCode++;
rlm@1:     }
rlm@1:     p[minCode] = 0;
rlm@1:     p[maxCode] = 1;
rlm@1:     lens[minCode] = lens[maxCode] = 1;
rlm@1:     return;
rlm@1:   }
rlm@1:   
rlm@1:   {
rlm@1:     UInt32 b, e, i;
rlm@1:   
rlm@1:     i = b = e = 0;
rlm@1:     do
rlm@1:     {
rlm@1:       UInt32 n, m, freq;
rlm@1:       n = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;
rlm@1:       freq = (p[n] & ~MASK);
rlm@1:       p[n] = (p[n] & MASK) | (e << NUM_BITS);
rlm@1:       m = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;
rlm@1:       freq += (p[m] & ~MASK);
rlm@1:       p[m] = (p[m] & MASK) | (e << NUM_BITS);
rlm@1:       p[e] = (p[e] & MASK) | freq;
rlm@1:       e++;
rlm@1:     }
rlm@1:     while (num - e > 1);
rlm@1:     
rlm@1:     {
rlm@1:       UInt32 lenCounters[kMaxLen + 1];
rlm@1:       for (i = 0; i <= kMaxLen; i++)
rlm@1:         lenCounters[i] = 0;
rlm@1:       
rlm@1:       p[--e] &= MASK;
rlm@1:       lenCounters[1] = 2;
rlm@1:       while (e > 0)
rlm@1:       {
rlm@1:         UInt32 len = (p[p[--e] >> NUM_BITS] >> NUM_BITS) + 1;
rlm@1:         p[e] = (p[e] & MASK) | (len << NUM_BITS);
rlm@1:         if (len >= maxLen)
rlm@1:           for (len = maxLen - 1; lenCounters[len] == 0; len--);
rlm@1:         lenCounters[len]--;
rlm@1:         lenCounters[len + 1] += 2;
rlm@1:       }
rlm@1:       
rlm@1:       {
rlm@1:         UInt32 len;
rlm@1:         i = 0;
rlm@1:         for (len = maxLen; len != 0; len--)
rlm@1:         {
rlm@1:           UInt32 num;
rlm@1:           for (num = lenCounters[len]; num != 0; num--)
rlm@1:             lens[p[i++] & MASK] = (Byte)len;
rlm@1:         }
rlm@1:       }
rlm@1:       
rlm@1:       {
rlm@1:         UInt32 nextCodes[kMaxLen + 1];
rlm@1:         {
rlm@1:           UInt32 code = 0;
rlm@1:           UInt32 len;
rlm@1:           for (len = 1; len <= kMaxLen; len++)
rlm@1:             nextCodes[len] = code = (code + lenCounters[len - 1]) << 1;
rlm@1:         }
rlm@1:         /* if (code + lenCounters[kMaxLen] - 1 != (1 << kMaxLen) - 1) throw 1; */
rlm@1: 
rlm@1:         {
rlm@1:           UInt32 i;
rlm@1:           for (i = 0; i < numSymbols; i++)
rlm@1:             p[i] = nextCodes[lens[i]]++;
rlm@1:         }
rlm@1:       }
rlm@1:     }
rlm@1:   }
rlm@1: }