misc/libphysfs/lzma/C/Compress/Huffman/HuffmanEncode.c
changeset 12213 bb5522e88ab2
equal deleted inserted replaced
12212:ea891871f481 12213:bb5522e88ab2
       
     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 }