diff options
author | 2012-02-12 17:55:51 +0000 | |
---|---|---|
committer | 2012-02-12 17:55:51 +0000 | |
commit | d75dbab0de7da33196f08f0cf7992d906ffbb832 (patch) | |
tree | d9120844b308fa2ac9844c182a86b79feddb84f3 /src/lib/lib7z/HuffEnc.c | |
parent | f594641814167d5de00ee2a0d6925c42e61fecc4 (diff) |
Add LZMA codec and .7z container support [David Haywood, R. Belmont]
Diffstat (limited to 'src/lib/lib7z/HuffEnc.c')
-rw-r--r-- | src/lib/lib7z/HuffEnc.c | 146 |
1 files changed, 146 insertions, 0 deletions
diff --git a/src/lib/lib7z/HuffEnc.c b/src/lib/lib7z/HuffEnc.c new file mode 100644 index 00000000000..561c7e5da82 --- /dev/null +++ b/src/lib/lib7z/HuffEnc.c @@ -0,0 +1,146 @@ +/* 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]]++; + } + } + } + } +} |