![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to huff.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv8dc / cmd / spell|
Return to huff.c CVS log | Up to [Research Unix] / researchv8dc / cmd / spell |
1.1 root 1: /* @(#)huff.c 1.3 */
2: #include <stdio.h>
3: #define BYTE 8
4: #define QW 1 /* width of bas-q digit in bits */
5:
6: /* this stuff should be local and hidden; it was made
7: * accessible outside for dirty reasons: 20% faster spell
8: */
9: #include "huff.h"
10: struct huff huffcode;
11:
12: /* Infinite Huffman code
13: *
14: * Let the messages be exponentially distributed with ratio r:
15: * P{message k} = r^k*(1-r), k=0,1,...
16: * Let the messages be coded in base q, and suppose
17: * r^n = 1/q
18: * If each decade (base q) contains n codes, then
19: * the messages assigned to each decade will be q times
20: * as probable as the next. Moreover the code for the tail of
21: * the distribution after truncating one decade should look
22: * just like the original, but longer by one leading digit q-1.
23: * q(z+n) = z + (q-1)q^w
24: * where z is first code of decade, w is width of code (in shortest
25: * full decade). Examples, base 2:
26: * r^1 = 1/2 r^5 = 1/2
27: * 0 0110
28: * 10 0111
29: * 110 1000
30: * 1110 1001
31: * ... 1010
32: * 10110
33: * w=1,z=0 w=4,z=0110
34: * Rewriting slightly
35: * (q-1)z + q*n = (q-1)q^w
36: * whence z is a multiple of q and n is a multiple of q-1. Let
37: * z = cq, n = d(q-1)
38: * We pick w to be the least integer such that
39: * d = n/(q-1) <= q^(w-1)
40: * Then solve for c
41: * c = q^(w-1) - d
42: * If c is not zero, the first decade may be preceded by
43: * even shorter (w-1)-digit codes 0,1,...,c-1. Thus
44: * the example code with r^5 = 1/2 becomes
45: * 000
46: * 001
47: * 010
48: * 0110
49: * 0111
50: * 1000
51: * 1001
52: * 1010
53: * 10110
54: * ...
55: * 110110
56: * ...
57: * The expected number of base-q digits in a codeword is then
58: * w - 1 + r^c/(1-r^n)
59: * The present routines require q to be a power of 2
60: */
61: /* There is a lot of hanky-panky with left justification against
62: * sign instead of simple left justification because
63: * unsigned long is not available
64: */
65: #define L (BYTE*(sizeof(long))-1) /* length of signless long */
66: #define MASK (~(1L<<L)) /* mask out sign */
67:
68: /* decode the prefix of word y (which is left justified against sign)
69: * place mesage number into place pointed to by kp
70: * return length (in bits) of decoded prefix or 0 if code is out of
71: * range
72: */
73: decode(y,pk)
74: long y;
75: long *pk;
76: {
77: register l;
78: long v;
79: if(y < cs) {
80: *pk = y >> (L+QW-w);
81: return(w-QW);
82: }
83: for(l=w,v=v0; y>=qcs; y=(y<<QW)&MASK,v+=n)
84: if((l+=QW) > L)
85: return(0);
86: *pk = v + (y>>(L-w));
87: return(l);
88: }
89:
90: /* encode message k and put result (right justified) into
91: * place pointed to by py.
92: * return length (in bits) of result,
93: * or 0 if code is too long
94: */
95: encode(k,py)
96: long k;
97: long *py;
98: {
99: register l;
100: long y;
101: if(k < c) {
102: *py = k;
103: return(w-QW);
104: }
105: for(k-=c,y=1,l=w; k>=n; k-=n,y<<=QW)
106: if((l+=QW) > L)
107: return(0);
108: *py = ((y-1)<<w) + cq + k;
109: return(l);
110: }
111: /* Initialization code, given expected value of k
112: * E(k) = r/(1-r) = a
113: * and given base width b
114: * return expected length of coded messages
115: */
116: struct qlog {
117: long p;
118: double u;
119: };
120: double
121: huff(a)
122: float a;
123: {
124: struct qlog qlog();
125: struct qlog z;
126: register i, q;
127: long d, j;
128: double r = a/(1.0 + a);
129: double rc, rq;
130: for(i=0,q=1,rq=r; i<QW; i++,q*=2,rq*=rq)
131: continue;
132: rq /= r; /* rq = r^(q-1) */
133: z = qlog(rq, 1./q, 1L, rq);
134: d = z.p;
135: n = d*(q-1);
136: if(n!=d*(q-1))
137: abort(); /*time to make n long*/
138: for(w=QW,j=1; j<d; w+=QW,j*=q)
139: continue;
140: c = j - d;
141: cq = c*q;
142: cs = cq<<(L-w);
143: qcs = (((long)(q-1)<<w) + cq) << (L-QW-w);
144: v0 = c - cq;
145: for(i=0,rc=1; i<c; i++,rc*=r) /* rc = r^c */
146: continue;
147: return(w + QW*(rc/(1-z.u) - 1));
148: }
149:
150: struct qlog
151: qlog(x, y, p, u) /*find smallest p so x^p<=y */
152: double x,y,u;
153: long p;
154: {
155: struct qlog z;
156: if(u/x <= y) {
157: z.p = 0;
158: z.u = 1;
159: } else {
160: z = qlog(x, y, p+p, u*u);
161: if(u*z.u/x > y) {
162: z.p += p;
163: z.u *= u;
164: }
165: }
166: return(z);
167: }
168:
169: whuff()
170: {
171: fwrite((char*)&huffcode,sizeof(huffcode),1,stdout);
172: }
173:
174: rhuff(f)
175: FILE *f;
176: {
177: return(read(fileno(f), (char*)&huffcode, sizeof(huffcode)) == sizeof(huffcode));
178: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.