Mercurial > vba-linux

     1 /* HuffEnc.c -- functions for Huffman encoding

     2 2008-08-05

     3 Igor Pavlov

     4 Public domain */

     5 

     6 #include "HuffEnc.h"

     7 #include "Sort.h"

     8 

     9 #define kMaxLen 16

    10 #define NUM_BITS 10

    11 #define MASK ((1 << NUM_BITS) - 1)

    12 

    13 #define NUM_COUNTERS 64

    14 

    15 #define HUFFMAN_SPEED_OPT

    16 

    17 void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 numSymbols, UInt32 maxLen)

    18 {

    19   UInt32 num = 0;

    20   /* if (maxLen > 10) maxLen = 10; */

    21   {

    22     UInt32 i;

    23     

    24     #ifdef HUFFMAN_SPEED_OPT

    25     

    26     UInt32 counters[NUM_COUNTERS];

    27     for (i = 0; i < NUM_COUNTERS; i++)

    28       counters[i] = 0;

    29     for (i = 0; i < numSymbols; i++)

    30     {

    31       UInt32 freq = freqs[i];

    32       counters[(freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1]++;

    33     }

    34  

    35     for (i = 1; i < NUM_COUNTERS; i++)

    36     {

    37       UInt32 temp = counters[i];

    38       counters[i] = num;

    39       num += temp;

    40     }

    41 

    42     for (i = 0; i < numSymbols; i++)

    43     {

    44       UInt32 freq = freqs[i];

    45       if (freq == 0)

    46         lens[i] = 0;

    47       else

    48         p[counters[((freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1)]++] = i | (freq << NUM_BITS);

    49     }

    50     counters[0] = 0;

    51     HeapSort(p + counters[NUM_COUNTERS - 2], counters[NUM_COUNTERS - 1] - counters[NUM_COUNTERS - 2]);

    52     

    53     #else

    54 

    55     for (i = 0; i < numSymbols; i++)

    56     {

    57       UInt32 freq = freqs[i];

    58       if (freq == 0)

    59         lens[i] = 0;

    60       else

    61         p[num++] = i | (freq << NUM_BITS);

    62     }

    63     HeapSort(p, num);

    64 

    65     #endif

    66   }

    67 

    68   if (num < 2)

    69   {

    70     int minCode = 0;

    71     int maxCode = 1;

    72     if (num == 1)

    73     {

    74       maxCode = (int)(p[0] & MASK);

    75       if (maxCode == 0)

    76         maxCode++;

    77     }

    78     p[minCode] = 0;

    79     p[maxCode] = 1;

    80     lens[minCode] = lens[maxCode] = 1;

    81     return;

    82   }

    83   

    84   {

    85     UInt32 b, e, i;

    86   

    87     i = b = e = 0;

    88     do

    89     {

    90       UInt32 n, m, freq;

    91       n = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;

    92       freq = (p[n] & ~MASK);

    93       p[n] = (p[n] & MASK) | (e << NUM_BITS);

    94       m = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;

    95       freq += (p[m] & ~MASK);

    96       p[m] = (p[m] & MASK) | (e << NUM_BITS);

    97       p[e] = (p[e] & MASK) | freq;

    98       e++;

    99     }

   100     while (num - e > 1);

   101     

   102     {

   103       UInt32 lenCounters[kMaxLen + 1];

   104       for (i = 0; i <= kMaxLen; i++)

   105         lenCounters[i] = 0;

   106       

   107       p[--e] &= MASK;

   108       lenCounters[1] = 2;

   109       while (e > 0)

   110       {

   111         UInt32 len = (p[p[--e] >> NUM_BITS] >> NUM_BITS) + 1;

   112         p[e] = (p[e] & MASK) | (len << NUM_BITS);

   113         if (len >= maxLen)

   114           for (len = maxLen - 1; lenCounters[len] == 0; len--);

   115         lenCounters[len]--;

   116         lenCounters[len + 1] += 2;

   117       }

   118       

   119       {

   120         UInt32 len;

   121         i = 0;

   122         for (len = maxLen; len != 0; len--)

   123         {

   124           UInt32 num;

   125           for (num = lenCounters[len]; num != 0; num--)

   126             lens[p[i++] & MASK] = (Byte)len;

   127         }

   128       }

   129       

   130       {

   131         UInt32 nextCodes[kMaxLen + 1];

   132         {

   133           UInt32 code = 0;

   134           UInt32 len;

   135           for (len = 1; len <= kMaxLen; len++)

   136             nextCodes[len] = code = (code + lenCounters[len - 1]) << 1;

   137         }

   138         /* if (code + lenCounters[kMaxLen] - 1 != (1 << kMaxLen) - 1) throw 1; */

   139 

   140         {

   141           UInt32 i;

   142           for (i = 0; i < numSymbols; i++)

   143             p[i] = nextCodes[lens[i]]++;

   144         }

   145       }

   146     }

   147   }

   148 }
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:47 -0600
parents	f9f4f1b99eed
children