2 // implements canonical Huffman
16 static void sort (Ttree *tree, int lo, int up)
25 { while (tree[j].freq > temp.freq) j--;
27 while (i<j && tree[i].freq <= temp.freq) i++;
31 if (i-lo < up-i) { sort(tree,lo,i-1); lo = i+1; }
32 else { sort(tree,i+1,up); up = i-1; }
36 static void setdepths (Ttree *tree, uint node, int depth)
38 { if (tree[node].ch1 == -1) // leaf
39 { tree[node].h.depth = depth;
42 setdepths (tree,tree[node].ch1,depth+1);
43 setdepths (tree,tree[node].ch2,depth+1);
46 THuff createHuff (uint *freq, uint lim)
52 // remove zero frequencies
54 tree = (Ttree*)malloc((2*(lim+1)-1)*sizeof(Ttree));
56 for (i=0;i<=(int)lim;i++)
58 { tree[j].freq = freq[i];
64 // now run Huffman algorithm
66 for (i=0;i<=(int)lim;i++)
67 { tree[i].h.prev = i+1;
68 tree[i].ch1 = tree[i].ch2 = -1;
70 tree[lim].h.prev = -1;
71 // last = next node to process, ptr = search point, fre = next free cell
72 // leaves are in 0..lim in decreasing freq order
73 // internal nodes are in lim+1.. 2*lim, created in incr. fre order
74 last=0; ptr = 0; fre = lim+1;
75 for (i=0;i<(int)lim;i++)
76 { tree[fre].ch1 = last;
77 last = tree[last].h.prev;
79 tree[fre].freq = tree[tree[fre].ch1].freq+tree[tree[fre].ch2].freq;
80 while ((tree[ptr].h.prev != -1) &&
81 (tree[tree[ptr].h.prev].freq <= tree[fre].freq))
82 ptr = tree[ptr].h.prev;
83 tree[fre].h.prev = tree[ptr].h.prev;
84 tree[ptr].h.prev = fre;
85 last = tree[last].h.prev;
88 // now assign depths recursively
89 setdepths (tree,2*lim,0);
90 H.s.spos = (uint*)malloc ((H.max+1)*sizeof(uint));
91 for (i=0;i<=(int)H.max;i++) H.s.spos[i] = ~0;
92 H.num = (uint*)malloc ((lim+1)*sizeof(uint)); // max possible depth
95 { H.s.spos[tree[i].symb] = i;
96 while ((int)tree[i].h.depth > d)
97 { H.num[d] = i+1; d++; }
101 for (d=H.depth;d>0;d--) H.num[d] = H.num[d-1] - H.num[d];
102 H.num[0] = (lim == 0);
103 H.num = (uint*)realloc(H.num,(H.depth+1)*sizeof(uint));
105 for (i=0;i<=(int)lim;i++)
106 H.total += freq[tree[i].symb] * tree[i].h.depth;
111 void bitzero (register uint *e, register uint p,
125 *e &= ~(((1<<len)-1)<<p);
128 ulong encodeHuff (THuff H, uint symb, uint *stream, ulong ptr)
133 pos = H.s.spos[symb];
136 while (pos >= H.num[d])
137 { code = (code + H.num[d]) >> 1;
141 if (d > W) { bitzero(stream,ptr,d-W); ptr += d-W; d = W; }
143 { if ((code >> d) & 1) bitset(stream,ptr);
144 else bitclean(stream,ptr);
150 ulong decodeHuff (THuff H, uint *symb, uint *stream, ulong ptr)
156 while (pos < H.fst[d])
157 { pos = (pos << 1) | bitget(stream,ptr);
160 *symb = H.s.symb[H.num[d]+pos-H.fst[d]];
164 /* { uint pos; // This "improved" code is actually slower!
169 wrd = *stream >> off;
172 while (pos < H.fst[d])
173 { pos = (pos << 1) | (wrd & 1);
174 d++; wrd >>= 1; off++;
175 if (off == W) { wrd = *++stream; off = 0; }
177 *symb = H.s.symb[H.num[d]+pos-H.fst[d]];
181 void saveHuff (THuff H, FILE *f)
183 { uint *symb = (uint*)malloc((H.lim+1)*sizeof(uint));
185 for (i=0;i<=H.max;i++)
186 if (H.s.spos[i] != (uint)~0) symb[H.s.spos[i]] = i;
187 uint l=fwrite (&H.max,sizeof(uint),1,f);
188 l += fwrite (&H.lim,sizeof(uint),1,f);
189 l += fwrite (&H.depth,sizeof(uint),1,f);
190 l += fwrite (symb,sizeof(uint),H.lim+1,f);
191 l += fwrite (H.num,sizeof(uint),H.depth+1,f);
195 uint sizeHuff (THuff H)
197 { return (4+(H.lim+1)+(H.depth+1))*sizeof(uint);
200 void freeHuff (THuff H)
202 { free (H.s.spos); free (H.num);
205 THuff loadHuff (FILE *f, int enc)
211 uint l = fread (&H.max,sizeof(uint),1,f);
212 l += fread (&H.lim,sizeof(uint),1,f);
213 l += fread (&H.depth,sizeof(uint),1,f);
214 symb = (uint*)malloc ((H.lim+1)*sizeof(uint));
215 l += fread (symb,sizeof(uint),H.lim+1,f);
217 { H.s.spos = (uint*)malloc ((H.max+1)*sizeof(uint));
218 for (i=0;i<=H.max;i++) H.s.spos[i] = (uint)~0;
219 for (i=0;i<=H.lim;i++) H.s.spos[symb[i]] = i;
222 else H.s.symb = symb;
223 H.num = (uint*)malloc ((H.depth+1)*sizeof(uint));
224 l += fread (H.num,sizeof(uint),H.depth+1,f);
226 { H.fst = (uint*)malloc ((H.depth+1)*sizeof(uint));
227 H.fst[H.depth] = 0; dold = 0;
228 for (d=H.depth-1;d>=0;d--)
230 H.fst[d] = (H.fst[d+1]+dact) >> 1;