Mercurial > vba-linux
view src/win32/7zip/7z/C/HuffEnc.c @ 4:5f6f2134e8ce
apu appears to not be used
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sat, 03 Mar 2012 10:35:58 -0600 |
parents | f9f4f1b99eed |
children |
line wrap: on
line source
1 /* HuffEnc.c -- functions for Huffman encoding2 2008-08-053 Igor Pavlov4 Public domain */6 #include "HuffEnc.h"7 #include "Sort.h"9 #define kMaxLen 1610 #define NUM_BITS 1011 #define MASK ((1 << NUM_BITS) - 1)13 #define NUM_COUNTERS 6415 #define HUFFMAN_SPEED_OPT17 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;24 #ifdef HUFFMAN_SPEED_OPT26 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 }35 for (i = 1; i < NUM_COUNTERS; i++)36 {37 UInt32 temp = counters[i];38 counters[i] = num;39 num += temp;40 }42 for (i = 0; i < numSymbols; i++)43 {44 UInt32 freq = freqs[i];45 if (freq == 0)46 lens[i] = 0;47 else48 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]);53 #else55 for (i = 0; i < numSymbols; i++)56 {57 UInt32 freq = freqs[i];58 if (freq == 0)59 lens[i] = 0;60 else61 p[num++] = i | (freq << NUM_BITS);62 }63 HeapSort(p, num);65 #endif66 }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 }84 {85 UInt32 b, e, i;87 i = b = e = 0;88 do89 {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);102 {103 UInt32 lenCounters[kMaxLen + 1];104 for (i = 0; i <= kMaxLen; i++)105 lenCounters[i] = 0;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 }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 }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; */140 {141 UInt32 i;142 for (i = 0; i < numSymbols; i++)143 p[i] = nextCodes[lens[i]]++;144 }145 }146 }147 }148 }