1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/win32/7zip/7z/C/HuffEnc.c	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,148 @@
     1.4 +/* HuffEnc.c -- functions for Huffman encoding
     1.5 +2008-08-05
     1.6 +Igor Pavlov
     1.7 +Public domain */
     1.8 +
     1.9 +#include "HuffEnc.h"
    1.10 +#include "Sort.h"
    1.11 +
    1.12 +#define kMaxLen 16
    1.13 +#define NUM_BITS 10
    1.14 +#define MASK ((1 << NUM_BITS) - 1)
    1.15 +
    1.16 +#define NUM_COUNTERS 64
    1.17 +
    1.18 +#define HUFFMAN_SPEED_OPT
    1.19 +
    1.20 +void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 numSymbols, UInt32 maxLen)
    1.21 +{
    1.22 +  UInt32 num = 0;
    1.23 +  /* if (maxLen > 10) maxLen = 10; */
    1.24 +  {
    1.25 +    UInt32 i;
    1.26 +    
    1.27 +    #ifdef HUFFMAN_SPEED_OPT
    1.28 +    
    1.29 +    UInt32 counters[NUM_COUNTERS];
    1.30 +    for (i = 0; i < NUM_COUNTERS; i++)
    1.31 +      counters[i] = 0;
    1.32 +    for (i = 0; i < numSymbols; i++)
    1.33 +    {
    1.34 +      UInt32 freq = freqs[i];
    1.35 +      counters[(freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1]++;
    1.36 +    }
    1.37 + 
    1.38 +    for (i = 1; i < NUM_COUNTERS; i++)
    1.39 +    {
    1.40 +      UInt32 temp = counters[i];
    1.41 +      counters[i] = num;
    1.42 +      num += temp;
    1.43 +    }
    1.44 +
    1.45 +    for (i = 0; i < numSymbols; i++)
    1.46 +    {
    1.47 +      UInt32 freq = freqs[i];
    1.48 +      if (freq == 0)
    1.49 +        lens[i] = 0;
    1.50 +      else
    1.51 +        p[counters[((freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1)]++] = i | (freq << NUM_BITS);
    1.52 +    }
    1.53 +    counters[0] = 0;
    1.54 +    HeapSort(p + counters[NUM_COUNTERS - 2], counters[NUM_COUNTERS - 1] - counters[NUM_COUNTERS - 2]);
    1.55 +    
    1.56 +    #else
    1.57 +
    1.58 +    for (i = 0; i < numSymbols; i++)
    1.59 +    {
    1.60 +      UInt32 freq = freqs[i];
    1.61 +      if (freq == 0)
    1.62 +        lens[i] = 0;
    1.63 +      else
    1.64 +        p[num++] = i | (freq << NUM_BITS);
    1.65 +    }
    1.66 +    HeapSort(p, num);
    1.67 +
    1.68 +    #endif
    1.69 +  }
    1.70 +
    1.71 +  if (num < 2)
    1.72 +  {
    1.73 +    int minCode = 0;
    1.74 +    int maxCode = 1;
    1.75 +    if (num == 1)
    1.76 +    {
    1.77 +      maxCode = (int)(p[0] & MASK);
    1.78 +      if (maxCode == 0)
    1.79 +        maxCode++;
    1.80 +    }
    1.81 +    p[minCode] = 0;
    1.82 +    p[maxCode] = 1;
    1.83 +    lens[minCode] = lens[maxCode] = 1;
    1.84 +    return;
    1.85 +  }
    1.86 +  
    1.87 +  {
    1.88 +    UInt32 b, e, i;
    1.89 +  
    1.90 +    i = b = e = 0;
    1.91 +    do
    1.92 +    {
    1.93 +      UInt32 n, m, freq;
    1.94 +      n = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;
    1.95 +      freq = (p[n] & ~MASK);
    1.96 +      p[n] = (p[n] & MASK) | (e << NUM_BITS);
    1.97 +      m = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;
    1.98 +      freq += (p[m] & ~MASK);
    1.99 +      p[m] = (p[m] & MASK) | (e << NUM_BITS);
   1.100 +      p[e] = (p[e] & MASK) | freq;
   1.101 +      e++;
   1.102 +    }
   1.103 +    while (num - e > 1);
   1.104 +    
   1.105 +    {
   1.106 +      UInt32 lenCounters[kMaxLen + 1];
   1.107 +      for (i = 0; i <= kMaxLen; i++)
   1.108 +        lenCounters[i] = 0;
   1.109 +      
   1.110 +      p[--e] &= MASK;
   1.111 +      lenCounters[1] = 2;
   1.112 +      while (e > 0)
   1.113 +      {
   1.114 +        UInt32 len = (p[p[--e] >> NUM_BITS] >> NUM_BITS) + 1;
   1.115 +        p[e] = (p[e] & MASK) | (len << NUM_BITS);
   1.116 +        if (len >= maxLen)
   1.117 +          for (len = maxLen - 1; lenCounters[len] == 0; len--);
   1.118 +        lenCounters[len]--;
   1.119 +        lenCounters[len + 1] += 2;
   1.120 +      }
   1.121 +      
   1.122 +      {
   1.123 +        UInt32 len;
   1.124 +        i = 0;
   1.125 +        for (len = maxLen; len != 0; len--)
   1.126 +        {
   1.127 +          UInt32 num;
   1.128 +          for (num = lenCounters[len]; num != 0; num--)
   1.129 +            lens[p[i++] & MASK] = (Byte)len;
   1.130 +        }
   1.131 +      }
   1.132 +      
   1.133 +      {
   1.134 +        UInt32 nextCodes[kMaxLen + 1];
   1.135 +        {
   1.136 +          UInt32 code = 0;
   1.137 +          UInt32 len;
   1.138 +          for (len = 1; len <= kMaxLen; len++)
   1.139 +            nextCodes[len] = code = (code + lenCounters[len - 1]) << 1;
   1.140 +        }
   1.141 +        /* if (code + lenCounters[kMaxLen] - 1 != (1 << kMaxLen) - 1) throw 1; */
   1.142 +
   1.143 +        {
   1.144 +          UInt32 i;
   1.145 +          for (i = 0; i < numSymbols; i++)
   1.146 +            p[i] = nextCodes[lens[i]]++;
   1.147 +        }
   1.148 +      }
   1.149 +    }
   1.150 +  }
   1.151 +}