/* HuffEnc.c -- functions for Huffman encoding
2009-09-02 : Igor Pavlov : Public domain */

#include "HuffEnc.h"
#include "Sort.h"

#define kMaxLen 16
#define NUM_BITS 10
#define MASK ((1 << NUM_BITS) - 1)

#define NUM_COUNTERS 64

#define HUFFMAN_SPEED_OPT

void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 numSymbols, UInt32 maxLen)
{
  UInt32 num = 0;
  /* if (maxLen > 10) maxLen = 10; */
  {
    UInt32 i;
    
    #ifdef HUFFMAN_SPEED_OPT
    
    UInt32 counters[NUM_COUNTERS];
    for (i = 0; i < NUM_COUNTERS; i++)
      counters[i] = 0;
    for (i = 0; i < numSymbols; i++)
    {
      UInt32 freq = freqs[i];
      counters[(freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1]++;
    }
 
    for (i = 1; i < NUM_COUNTERS; i++)
    {
      UInt32 temp = counters[i];
      counters[i] = num;
      num += temp;
    }

    for (i = 0; i < numSymbols; i++)
    {
      UInt32 freq = freqs[i];
      if (freq == 0)
        lens[i] = 0;
      else
        p[counters[((freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1)]++] = i | (freq << NUM_BITS);
    }
    counters[0] = 0;
    HeapSort(p + counters[NUM_COUNTERS - 2], counters[NUM_COUNTERS - 1] - counters[NUM_COUNTERS - 2]);
    
    #else

    for (i = 0; i < numSymbols; i++)
    {
      UInt32 freq = freqs[i];
      if (freq == 0)
        lens[i] = 0;
      else
        p[num++] = i | (freq << NUM_BITS);
    }
    HeapSort(p, num);

    #endif
  }

  if (num < 2)
  {
    unsigned minCode = 0;
    unsigned maxCode = 1;
    if (num == 1)
    {
      maxCode = (unsigned)p[0] & MASK;
      if (maxCode == 0)
        maxCode++;
    }
    p[minCode] = 0;
    p[maxCode] = 1;
    lens[minCode] = lens[maxCode] = 1;
    return;
  }
  
  {
    UInt32 b, e, i;
  
    i = b = e = 0;
    do
    {
      UInt32 n, m, freq;
      n = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;
      freq = (p[n] & ~MASK);
      p[n] = (p[n] & MASK) | (e << NUM_BITS);
      m = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;
      freq += (p[m] & ~MASK);
      p[m] = (p[m] & MASK) | (e << NUM_BITS);
      p[e] = (p[e] & MASK) | freq;
      e++;
    }
    while (num - e > 1);
    
    {
      UInt32 lenCounters[kMaxLen + 1];
      for (i = 0; i <= kMaxLen; i++)
        lenCounters[i] = 0;
      
      p[--e] &= MASK;
      lenCounters[1] = 2;
      while (e > 0)
      {
        UInt32 len = (p[p[--e] >> NUM_BITS] >> NUM_BITS) + 1;
        p[e] = (p[e] & MASK) | (len << NUM_BITS);
        if (len >= maxLen)
          for (len = maxLen - 1; lenCounters[len] == 0; len--);
        lenCounters[len]--;
        lenCounters[len + 1] += 2;
      }
      
      {
        UInt32 len;
        i = 0;
        for (len = maxLen; len != 0; len--)
        {
          UInt32 num;
          for (num = lenCounters[len]; num != 0; num--)
            lens[p[i++] & MASK] = (Byte)len;
        }
      }
      
      {
        UInt32 nextCodes[kMaxLen + 1];
        {
          UInt32 code = 0;
          UInt32 len;
          for (len = 1; len <= kMaxLen; len++)
            nextCodes[len] = code = (code + lenCounters[len - 1]) << 1;
        }
        /* if (code + lenCounters[kMaxLen] - 1 != (1 << kMaxLen) - 1) throw 1; */

        {
          UInt32 i;
          for (i = 0; i < numSymbols; i++)
            p[i] = nextCodes[lens[i]]++;
        }
      }
    }
  }
}