Mercurial > vba-linux

annotate src/win32/7zip/7z/C/HuffEnc.c @ 1:f9f4f1b99eed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
importing src directory
author Robert McIntyre <rlm@mit.edu>
date Sat, 03 Mar 2012 10:31:27 -0600
parents
children
rev   line source
rlm@1 1 /* HuffEnc.c -- functions for Huffman encoding
rlm@1 2 2008-08-05
rlm@1 3 Igor Pavlov
rlm@1 4 Public domain */
rlm@1 5
rlm@1 6 #include "HuffEnc.h"
rlm@1 7 #include "Sort.h"
rlm@1 8
rlm@1 9 #define kMaxLen 16
rlm@1 10 #define NUM_BITS 10
rlm@1 11 #define MASK ((1 << NUM_BITS) - 1)
rlm@1 12
rlm@1 13 #define NUM_COUNTERS 64
rlm@1 14
rlm@1 15 #define HUFFMAN_SPEED_OPT
rlm@1 16
rlm@1 17 void Huffman_Generate(const UInt32 *freqs, UInt32 *p, Byte *lens, UInt32 numSymbols, UInt32 maxLen)
rlm@1 18 {
rlm@1 19 UInt32 num = 0;
rlm@1 20 /* if (maxLen > 10) maxLen = 10; */
rlm@1 21 {
rlm@1 22 UInt32 i;
rlm@1 23
rlm@1 24 #ifdef HUFFMAN_SPEED_OPT
rlm@1 25
rlm@1 26 UInt32 counters[NUM_COUNTERS];
rlm@1 27 for (i = 0; i < NUM_COUNTERS; i++)
rlm@1 28 counters[i] = 0;
rlm@1 29 for (i = 0; i < numSymbols; i++)
rlm@1 30 {
rlm@1 31 UInt32 freq = freqs[i];
rlm@1 32 counters[(freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1]++;
rlm@1 33 }
rlm@1 34
rlm@1 35 for (i = 1; i < NUM_COUNTERS; i++)
rlm@1 36 {
rlm@1 37 UInt32 temp = counters[i];
rlm@1 38 counters[i] = num;
rlm@1 39 num += temp;
rlm@1 40 }
rlm@1 41
rlm@1 42 for (i = 0; i < numSymbols; i++)
rlm@1 43 {
rlm@1 44 UInt32 freq = freqs[i];
rlm@1 45 if (freq == 0)
rlm@1 46 lens[i] = 0;
rlm@1 47 else
rlm@1 48 p[counters[((freq < NUM_COUNTERS - 1) ? freq : NUM_COUNTERS - 1)]++] = i | (freq << NUM_BITS);
rlm@1 49 }
rlm@1 50 counters[0] = 0;
rlm@1 51 HeapSort(p + counters[NUM_COUNTERS - 2], counters[NUM_COUNTERS - 1] - counters[NUM_COUNTERS - 2]);
rlm@1 52
rlm@1 53 #else
rlm@1 54
rlm@1 55 for (i = 0; i < numSymbols; i++)
rlm@1 56 {
rlm@1 57 UInt32 freq = freqs[i];
rlm@1 58 if (freq == 0)
rlm@1 59 lens[i] = 0;
rlm@1 60 else
rlm@1 61 p[num++] = i | (freq << NUM_BITS);
rlm@1 62 }
rlm@1 63 HeapSort(p, num);
rlm@1 64
rlm@1 65 #endif
rlm@1 66 }
rlm@1 67
rlm@1 68 if (num < 2)
rlm@1 69 {
rlm@1 70 int minCode = 0;
rlm@1 71 int maxCode = 1;
rlm@1 72 if (num == 1)
rlm@1 73 {
rlm@1 74 maxCode = (int)(p[0] & MASK);
rlm@1 75 if (maxCode == 0)
rlm@1 76 maxCode++;
rlm@1 77 }
rlm@1 78 p[minCode] = 0;
rlm@1 79 p[maxCode] = 1;
rlm@1 80 lens[minCode] = lens[maxCode] = 1;
rlm@1 81 return;
rlm@1 82 }
rlm@1 83
rlm@1 84 {
rlm@1 85 UInt32 b, e, i;
rlm@1 86
rlm@1 87 i = b = e = 0;
rlm@1 88 do
rlm@1 89 {
rlm@1 90 UInt32 n, m, freq;
rlm@1 91 n = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;
rlm@1 92 freq = (p[n] & ~MASK);
rlm@1 93 p[n] = (p[n] & MASK) | (e << NUM_BITS);
rlm@1 94 m = (i != num && (b == e || (p[i] >> NUM_BITS) <= (p[b] >> NUM_BITS))) ? i++ : b++;
rlm@1 95 freq += (p[m] & ~MASK);
rlm@1 96 p[m] = (p[m] & MASK) | (e << NUM_BITS);
rlm@1 97 p[e] = (p[e] & MASK) | freq;
rlm@1 98 e++;
rlm@1 99 }
rlm@1 100 while (num - e > 1);
rlm@1 101
rlm@1 102 {
rlm@1 103 UInt32 lenCounters[kMaxLen + 1];
rlm@1 104 for (i = 0; i <= kMaxLen; i++)
rlm@1 105 lenCounters[i] = 0;
rlm@1 106
rlm@1 107 p[--e] &= MASK;
rlm@1 108 lenCounters[1] = 2;
rlm@1 109 while (e > 0)
rlm@1 110 {
rlm@1 111 UInt32 len = (p[p[--e] >> NUM_BITS] >> NUM_BITS) + 1;
rlm@1 112 p[e] = (p[e] & MASK) | (len << NUM_BITS);
rlm@1 113 if (len >= maxLen)
rlm@1 114 for (len = maxLen - 1; lenCounters[len] == 0; len--);
rlm@1 115 lenCounters[len]--;
rlm@1 116 lenCounters[len + 1] += 2;
rlm@1 117 }
rlm@1 118
rlm@1 119 {
rlm@1 120 UInt32 len;
rlm@1 121 i = 0;
rlm@1 122 for (len = maxLen; len != 0; len--)
rlm@1 123 {
rlm@1 124 UInt32 num;
rlm@1 125 for (num = lenCounters[len]; num != 0; num--)
rlm@1 126 lens[p[i++] & MASK] = (Byte)len;
rlm@1 127 }
rlm@1 128 }
rlm@1 129
rlm@1 130 {
rlm@1 131 UInt32 nextCodes[kMaxLen + 1];
rlm@1 132 {
rlm@1 133 UInt32 code = 0;
rlm@1 134 UInt32 len;
rlm@1 135 for (len = 1; len <= kMaxLen; len++)
rlm@1 136 nextCodes[len] = code = (code + lenCounters[len - 1]) << 1;
rlm@1 137 }
rlm@1 138 /* if (code + lenCounters[kMaxLen] - 1 != (1 << kMaxLen) - 1) throw 1; */
rlm@1 139
rlm@1 140 {
rlm@1 141 UInt32 i;
rlm@1 142 for (i = 0; i < numSymbols; i++)
rlm@1 143 p[i] = nextCodes[lens[i]]++;
rlm@1 144 }
rlm@1 145 }
rlm@1 146 }
rlm@1 147 }
rlm@1 148 }