17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate * with the License.
87c478bd9Sstevel@tonic-gate *
97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate * and limitations under the License.
137c478bd9Sstevel@tonic-gate *
147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * CDDL HEADER END
217c478bd9Sstevel@tonic-gate */
227c478bd9Sstevel@tonic-gate /*
23*0d8b5334Sceastha * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
247c478bd9Sstevel@tonic-gate * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
277c478bd9Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
287c478bd9Sstevel@tonic-gate /* All Rights Reserved */
297c478bd9Sstevel@tonic-gate
307c478bd9Sstevel@tonic-gate #include <unistd.h>
317c478bd9Sstevel@tonic-gate #include <stdlib.h>
327c478bd9Sstevel@tonic-gate #include <stdio.h>
337c478bd9Sstevel@tonic-gate
347c478bd9Sstevel@tonic-gate #define BYTE 8
357c478bd9Sstevel@tonic-gate #define QW 1 /* width of bas-q digit in bits */
367c478bd9Sstevel@tonic-gate
377c478bd9Sstevel@tonic-gate /*
387c478bd9Sstevel@tonic-gate * this stuff should be local and hidden; it was made
397c478bd9Sstevel@tonic-gate * accessible outside for dirty reasons: 20% faster spell
407c478bd9Sstevel@tonic-gate */
417c478bd9Sstevel@tonic-gate #include "huff.h"
427c478bd9Sstevel@tonic-gate struct huff huffcode;
437c478bd9Sstevel@tonic-gate
447c478bd9Sstevel@tonic-gate /*
457c478bd9Sstevel@tonic-gate * Infinite Huffman code
467c478bd9Sstevel@tonic-gate *
477c478bd9Sstevel@tonic-gate * Let the messages be exponentially distributed with ratio r:
487c478bd9Sstevel@tonic-gate * P {message k} = r^k*(1-r), k = 0, 1, ...
497c478bd9Sstevel@tonic-gate * Let the messages be coded in base q, and suppose
507c478bd9Sstevel@tonic-gate * r^n = 1/q
517c478bd9Sstevel@tonic-gate * If each decade(base q) contains n codes, then
527c478bd9Sstevel@tonic-gate * the messages assigned to each decade will be q times
537c478bd9Sstevel@tonic-gate * as probable as the next. Moreover the code for the tail of
547c478bd9Sstevel@tonic-gate * the distribution after truncating one decade should look
557c478bd9Sstevel@tonic-gate * just like the original, but longer by one leading digit q-1.
567c478bd9Sstevel@tonic-gate * q(z+n) = z + (q-1)q^w
577c478bd9Sstevel@tonic-gate * where z is first code of decade, w is width of code, in shortest
587c478bd9Sstevel@tonic-gate * full decade. Examples, base 2:
597c478bd9Sstevel@tonic-gate * r^1 = 1/2 r^5 = 1/2
607c478bd9Sstevel@tonic-gate * 0 0110
617c478bd9Sstevel@tonic-gate * 10 0111
627c478bd9Sstevel@tonic-gate * 110 1000
637c478bd9Sstevel@tonic-gate * 1110 1001
647c478bd9Sstevel@tonic-gate * ... 1010
657c478bd9Sstevel@tonic-gate * 10110
667c478bd9Sstevel@tonic-gate * w = 1, z = 0 w = 4, z = 0110
677c478bd9Sstevel@tonic-gate * Rewriting slightly
687c478bd9Sstevel@tonic-gate * (q-1)z + q*n = (q-1)q^w
697c478bd9Sstevel@tonic-gate * whence z is a multiple of q and n is a multiple of q-1. Let
707c478bd9Sstevel@tonic-gate * z = cq, n = d(q-1)
717c478bd9Sstevel@tonic-gate * We pick w to be the least integer such that
727c478bd9Sstevel@tonic-gate * d = n/(q-1) <= q^(w-1)
737c478bd9Sstevel@tonic-gate * Then solve for c
747c478bd9Sstevel@tonic-gate * c = q^(w-1) - d
757c478bd9Sstevel@tonic-gate * If c is not zero, the first decade may be preceded by
767c478bd9Sstevel@tonic-gate * even shorter (w-1)-digit codes 0, 1, ..., c-1. Thus
777c478bd9Sstevel@tonic-gate * the example code with r^5 = 1/2 becomes
787c478bd9Sstevel@tonic-gate * 000
797c478bd9Sstevel@tonic-gate * 001
807c478bd9Sstevel@tonic-gate * 010
817c478bd9Sstevel@tonic-gate * 0110
827c478bd9Sstevel@tonic-gate * 0111
837c478bd9Sstevel@tonic-gate * 1000
847c478bd9Sstevel@tonic-gate * 1001
857c478bd9Sstevel@tonic-gate * 1010
867c478bd9Sstevel@tonic-gate * 10110
877c478bd9Sstevel@tonic-gate * ...
887c478bd9Sstevel@tonic-gate * 110110
897c478bd9Sstevel@tonic-gate * ...
907c478bd9Sstevel@tonic-gate * The expected number of base-q digits in a codeword is then
917c478bd9Sstevel@tonic-gate * w - 1 + r^c/(1-r^n)
927c478bd9Sstevel@tonic-gate * The present routines require q to be a power of 2
937c478bd9Sstevel@tonic-gate */
947c478bd9Sstevel@tonic-gate /*
957c478bd9Sstevel@tonic-gate * There is a lot of hanky-panky with left justification against
967c478bd9Sstevel@tonic-gate * sign instead of simple left justification because
977c478bd9Sstevel@tonic-gate * unsigned long is not available
987c478bd9Sstevel@tonic-gate */
997c478bd9Sstevel@tonic-gate #define L (BYTE*(sizeof (long))-1) /* length of signless long */
1007c478bd9Sstevel@tonic-gate #define MASK (~((unsigned long)1<<L)) /* mask out sign */
1017c478bd9Sstevel@tonic-gate
1027c478bd9Sstevel@tonic-gate /*
1037c478bd9Sstevel@tonic-gate * decode the prefix of word y (which is left justified against sign)
1047c478bd9Sstevel@tonic-gate * place mesage number into place pointed to by kp
1057c478bd9Sstevel@tonic-gate * return length (in bits) of decoded prefix or 0 if code is out of
1067c478bd9Sstevel@tonic-gate * range
1077c478bd9Sstevel@tonic-gate */
1087c478bd9Sstevel@tonic-gate int
decode(long y,long * pk)1097c478bd9Sstevel@tonic-gate decode(long y, long *pk)
1107c478bd9Sstevel@tonic-gate {
111*0d8b5334Sceastha int l;
1127c478bd9Sstevel@tonic-gate long v;
1137c478bd9Sstevel@tonic-gate if (y < cs) {
1147c478bd9Sstevel@tonic-gate *pk = y >> (long)(L+QW-w);
1157c478bd9Sstevel@tonic-gate return (w-QW);
1167c478bd9Sstevel@tonic-gate }
1177c478bd9Sstevel@tonic-gate for (l = w, v = v0; y >= qcs;
1187c478bd9Sstevel@tonic-gate y = ((unsigned long)y << QW) & MASK, v += n)
1197c478bd9Sstevel@tonic-gate if ((l += QW) > L)
1207c478bd9Sstevel@tonic-gate return (0);
1217c478bd9Sstevel@tonic-gate *pk = v + (y>>(long)(L-w));
1227c478bd9Sstevel@tonic-gate return (l);
1237c478bd9Sstevel@tonic-gate }
1247c478bd9Sstevel@tonic-gate
1257c478bd9Sstevel@tonic-gate /*
1267c478bd9Sstevel@tonic-gate * encode message k and put result (right justified) into
1277c478bd9Sstevel@tonic-gate * place pointed to by py.
1287c478bd9Sstevel@tonic-gate * return length (in bits) of result,
1297c478bd9Sstevel@tonic-gate * or 0 if code is too long
1307c478bd9Sstevel@tonic-gate */
1317c478bd9Sstevel@tonic-gate
1327c478bd9Sstevel@tonic-gate int
encode(long k,long * py)1337c478bd9Sstevel@tonic-gate encode(long k, long *py)
1347c478bd9Sstevel@tonic-gate {
135*0d8b5334Sceastha int l;
1367c478bd9Sstevel@tonic-gate long y;
1377c478bd9Sstevel@tonic-gate if (k < c) {
1387c478bd9Sstevel@tonic-gate *py = k;
1397c478bd9Sstevel@tonic-gate return (w-QW);
1407c478bd9Sstevel@tonic-gate }
1417c478bd9Sstevel@tonic-gate for (k -= c, y = 1, l = w; k >= n; k -= n, y <<= QW)
1427c478bd9Sstevel@tonic-gate if ((l += QW) > L)
1437c478bd9Sstevel@tonic-gate return (0);
1447c478bd9Sstevel@tonic-gate *py = ((y-1)<<w) + cq + k;
1457c478bd9Sstevel@tonic-gate return (l);
1467c478bd9Sstevel@tonic-gate }
1477c478bd9Sstevel@tonic-gate
1487c478bd9Sstevel@tonic-gate
1497c478bd9Sstevel@tonic-gate /*
1507c478bd9Sstevel@tonic-gate * Initialization code, given expected value of k
1517c478bd9Sstevel@tonic-gate * E(k) = r/(1-r) = a
1527c478bd9Sstevel@tonic-gate * and given base width b
1537c478bd9Sstevel@tonic-gate * return expected length of coded messages
1547c478bd9Sstevel@tonic-gate */
1557c478bd9Sstevel@tonic-gate static struct qlog {
1567c478bd9Sstevel@tonic-gate long p;
1577c478bd9Sstevel@tonic-gate double u;
1587c478bd9Sstevel@tonic-gate } z;
1597c478bd9Sstevel@tonic-gate
1607c478bd9Sstevel@tonic-gate static struct qlog
qlog(double x,double y,long p,double u)1617c478bd9Sstevel@tonic-gate qlog(double x, double y, long p, double u) /* find smallest p so x^p<=y */
1627c478bd9Sstevel@tonic-gate {
1637c478bd9Sstevel@tonic-gate
1647c478bd9Sstevel@tonic-gate if (u/x <= y) {
1657c478bd9Sstevel@tonic-gate z.p = 0;
1667c478bd9Sstevel@tonic-gate z.u = 1;
1677c478bd9Sstevel@tonic-gate } else {
1687c478bd9Sstevel@tonic-gate z = qlog(x, y, p+p, u*u);
1697c478bd9Sstevel@tonic-gate if (u*z.u/x > y) {
1707c478bd9Sstevel@tonic-gate z.p += p;
1717c478bd9Sstevel@tonic-gate z.u *= u;
1727c478bd9Sstevel@tonic-gate }
1737c478bd9Sstevel@tonic-gate }
1747c478bd9Sstevel@tonic-gate return (z);
1757c478bd9Sstevel@tonic-gate }
1767c478bd9Sstevel@tonic-gate
1777c478bd9Sstevel@tonic-gate double
huff(float a)1787c478bd9Sstevel@tonic-gate huff(float a)
1797c478bd9Sstevel@tonic-gate {
180*0d8b5334Sceastha int i, q;
1817c478bd9Sstevel@tonic-gate long d, j;
1827c478bd9Sstevel@tonic-gate double r = a/(1.0 + a);
1837c478bd9Sstevel@tonic-gate double rc, rq;
1847c478bd9Sstevel@tonic-gate
1857c478bd9Sstevel@tonic-gate for (i = 0, q = 1, rq = r; i < QW; i++, q *= 2, rq *= rq)
1867c478bd9Sstevel@tonic-gate continue;
1877c478bd9Sstevel@tonic-gate rq /= r; /* rq = r^(q-1) */
1887c478bd9Sstevel@tonic-gate (void) qlog(rq, 1./q, 1L, rq);
1897c478bd9Sstevel@tonic-gate d = z.p;
1907c478bd9Sstevel@tonic-gate n = d*(q-1);
1917c478bd9Sstevel@tonic-gate if (n != d * (q - 1))
1927c478bd9Sstevel@tonic-gate abort(); /* time to make n long */
1937c478bd9Sstevel@tonic-gate for (w = QW, j = 1; j < d; w += QW, j *= q)
1947c478bd9Sstevel@tonic-gate continue;
1957c478bd9Sstevel@tonic-gate c = j - d;
1967c478bd9Sstevel@tonic-gate cq = c*q;
1977c478bd9Sstevel@tonic-gate cs = cq<<(L-w);
1987c478bd9Sstevel@tonic-gate qcs = (((long)(q-1)<<w) + cq) << (L-QW-w);
1997c478bd9Sstevel@tonic-gate v0 = c - cq;
2007c478bd9Sstevel@tonic-gate for (i = 0, rc = 1; i < c; i++, rc *= r) /* rc = r^c */
2017c478bd9Sstevel@tonic-gate continue;
2027c478bd9Sstevel@tonic-gate return (w + QW*(rc/(1-z.u) - 1));
2037c478bd9Sstevel@tonic-gate }
2047c478bd9Sstevel@tonic-gate
2057c478bd9Sstevel@tonic-gate void
whuff(void)2067c478bd9Sstevel@tonic-gate whuff(void)
2077c478bd9Sstevel@tonic-gate {
2087c478bd9Sstevel@tonic-gate (void) fwrite((char *) & huffcode, sizeof (huffcode), 1, stdout);
2097c478bd9Sstevel@tonic-gate }
2107c478bd9Sstevel@tonic-gate
2117c478bd9Sstevel@tonic-gate int
rhuff(FILE * f)2127c478bd9Sstevel@tonic-gate rhuff(FILE *f)
2137c478bd9Sstevel@tonic-gate {
2147c478bd9Sstevel@tonic-gate return (read(fileno(f), (char *)&huffcode, sizeof (huffcode)) ==
2157c478bd9Sstevel@tonic-gate sizeof (huffcode));
2167c478bd9Sstevel@tonic-gate }
217