10Sstevel@tonic-gate /*
20Sstevel@tonic-gate * CDDL HEADER START
30Sstevel@tonic-gate *
40Sstevel@tonic-gate * The contents of this file are subject to the terms of the
50Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
60Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
70Sstevel@tonic-gate * with the License.
80Sstevel@tonic-gate *
90Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
100Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
110Sstevel@tonic-gate * See the License for the specific language governing permissions
120Sstevel@tonic-gate * and limitations under the License.
130Sstevel@tonic-gate *
140Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
150Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
160Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
170Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
180Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
190Sstevel@tonic-gate *
200Sstevel@tonic-gate * CDDL HEADER END
210Sstevel@tonic-gate */
22*239Sceastha /*
23*239Sceastha * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
24*239Sceastha * Use is subject to license terms.
25*239Sceastha */
26*239Sceastha
270Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
280Sstevel@tonic-gate /* All Rights Reserved */
290Sstevel@tonic-gate
300Sstevel@tonic-gate
31*239Sceastha #pragma ident "%Z%%M% %I% %E% SMI"
32*239Sceastha
330Sstevel@tonic-gate #include <unistd.h>
340Sstevel@tonic-gate #include <stdlib.h>
350Sstevel@tonic-gate #include <stdio.h>
360Sstevel@tonic-gate #include <locale.h>
370Sstevel@tonic-gate #include "hash.h"
380Sstevel@tonic-gate #include "huff.h"
390Sstevel@tonic-gate
400Sstevel@tonic-gate int encode(long, long *);
410Sstevel@tonic-gate
420Sstevel@tonic-gate #define S (BYTE * sizeof (long))
430Sstevel@tonic-gate #define B (BYTE * sizeof (unsigned))
440Sstevel@tonic-gate unsigned *table;
450Sstevel@tonic-gate int hindex[NI];
460Sstevel@tonic-gate unsigned wp; /* word pointer */
470Sstevel@tonic-gate int bp = B; /* bit pointer */
480Sstevel@tonic-gate static int ignore;
490Sstevel@tonic-gate static int extra;
500Sstevel@tonic-gate
510Sstevel@tonic-gate static int
append(register unsigned w1,register int i)520Sstevel@tonic-gate append(register unsigned w1, register int i)
530Sstevel@tonic-gate {
540Sstevel@tonic-gate while (wp < ND - 1) {
550Sstevel@tonic-gate table[wp] |= w1>>(B-bp);
560Sstevel@tonic-gate i -= bp;
570Sstevel@tonic-gate if (i < 0) {
580Sstevel@tonic-gate bp = -i;
590Sstevel@tonic-gate return (1);
600Sstevel@tonic-gate }
610Sstevel@tonic-gate w1 <<= bp;
620Sstevel@tonic-gate bp = B;
630Sstevel@tonic-gate wp++;
640Sstevel@tonic-gate }
650Sstevel@tonic-gate return (0);
660Sstevel@tonic-gate }
670Sstevel@tonic-gate
680Sstevel@tonic-gate
690Sstevel@tonic-gate /*
700Sstevel@tonic-gate * usage: hashin N
710Sstevel@tonic-gate * where N is number of words in dictionary
720Sstevel@tonic-gate * and standard input contains sorted, unique
730Sstevel@tonic-gate * hashed words in octal
740Sstevel@tonic-gate */
750Sstevel@tonic-gate
76*239Sceastha int
main(int argc,char ** argv)770Sstevel@tonic-gate main(int argc, char **argv)
780Sstevel@tonic-gate {
790Sstevel@tonic-gate long h, k, d;
800Sstevel@tonic-gate int i;
810Sstevel@tonic-gate long count;
820Sstevel@tonic-gate long w1;
830Sstevel@tonic-gate long x;
840Sstevel@tonic-gate int t, u;
850Sstevel@tonic-gate double z;
860Sstevel@tonic-gate
870Sstevel@tonic-gate /* Set locale environment variables local definitions */
880Sstevel@tonic-gate (void) setlocale(LC_ALL, "");
890Sstevel@tonic-gate #if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */
900Sstevel@tonic-gate #define TEXT_DOMAIN "SYS_TEST" /* Use this only if it wasn't */
910Sstevel@tonic-gate #endif
920Sstevel@tonic-gate (void) textdomain(TEXT_DOMAIN);
930Sstevel@tonic-gate
940Sstevel@tonic-gate k = 0;
950Sstevel@tonic-gate u = 0;
960Sstevel@tonic-gate if (argc != 2) {
970Sstevel@tonic-gate (void) fprintf(stderr, gettext("%s: arg count\n"), argv[0]);
980Sstevel@tonic-gate exit(1);
990Sstevel@tonic-gate }
1000Sstevel@tonic-gate table = (unsigned *)malloc(ND * sizeof (*table));
1010Sstevel@tonic-gate if (table == 0) {
1020Sstevel@tonic-gate (void) fprintf(stderr, gettext("%s: no space for table\n"),
1030Sstevel@tonic-gate argv[0]);
1040Sstevel@tonic-gate exit(1);
1050Sstevel@tonic-gate }
1060Sstevel@tonic-gate if ((atof(argv[1])) == 0.0) {
1070Sstevel@tonic-gate (void) fprintf(stderr, gettext("%s: illegal count"), argv[0]);
1080Sstevel@tonic-gate exit(1);
1090Sstevel@tonic-gate }
1100Sstevel@tonic-gate
1110Sstevel@tonic-gate z = huff((1L<<HASHWIDTH)/atof(argv[1]));
1120Sstevel@tonic-gate (void) fprintf(stderr, gettext("%s: expected code widths = %f\n"),
1130Sstevel@tonic-gate argv[0], z);
1140Sstevel@tonic-gate for (count = 0; scanf("%lo", (unsigned long *)&h) == 1; ++count) {
1150Sstevel@tonic-gate if ((t = h >> (HASHWIDTH - INDEXWIDTH)) != u) {
1160Sstevel@tonic-gate if (bp != B)
1170Sstevel@tonic-gate wp++;
1180Sstevel@tonic-gate bp = B;
1190Sstevel@tonic-gate while (u < t)
1200Sstevel@tonic-gate hindex[++u] = wp;
1210Sstevel@tonic-gate k = (long)t<<(HASHWIDTH-INDEXWIDTH);
1220Sstevel@tonic-gate }
1230Sstevel@tonic-gate d = h-k;
1240Sstevel@tonic-gate k = h;
1250Sstevel@tonic-gate for (;;) {
1260Sstevel@tonic-gate for (x = d; ; x /= 2) {
1270Sstevel@tonic-gate i = encode(x, &w1);
1280Sstevel@tonic-gate if (i > 0)
1290Sstevel@tonic-gate break;
1300Sstevel@tonic-gate }
1310Sstevel@tonic-gate if (i > B) {
1320Sstevel@tonic-gate if (!(append((unsigned)(w1>>(long) (i-B)), B) &&
1330Sstevel@tonic-gate append((unsigned)(w1<<(long) (B+B-i)),
1340Sstevel@tonic-gate i-B)))
1350Sstevel@tonic-gate ignore++;
1360Sstevel@tonic-gate } else
1370Sstevel@tonic-gate if (!append((unsigned)(w1<<(long)(B-i)), i))
1380Sstevel@tonic-gate ignore++;
1390Sstevel@tonic-gate d -= x;
1400Sstevel@tonic-gate if (d > 0)
1410Sstevel@tonic-gate extra++;
1420Sstevel@tonic-gate else
1430Sstevel@tonic-gate break;
1440Sstevel@tonic-gate }
1450Sstevel@tonic-gate }
1460Sstevel@tonic-gate if (bp != B)
1470Sstevel@tonic-gate wp++;
1480Sstevel@tonic-gate while (++u < NI)
1490Sstevel@tonic-gate hindex[u] = wp;
1500Sstevel@tonic-gate whuff();
1510Sstevel@tonic-gate (void) fwrite((char *)hindex, sizeof (*hindex), NI, stdout);
1520Sstevel@tonic-gate (void) fwrite((char *)table, sizeof (*table), wp, stdout);
1530Sstevel@tonic-gate (void) fprintf(stderr,
1540Sstevel@tonic-gate gettext("%s: %ld items, %d ignored, %d extra, %u words occupied\n"),
1550Sstevel@tonic-gate argv[0], count, ignore, extra, wp);
1560Sstevel@tonic-gate count -= ignore;
1570Sstevel@tonic-gate (void) fprintf(stderr, "%s: %f table bits/item, %f table+index bits\n",
1580Sstevel@tonic-gate argv[0], (((float)BYTE * wp) * sizeof (*table) / count),
1590Sstevel@tonic-gate (BYTE * ((float)wp * sizeof (*table) + sizeof (hindex)) / count));
160*239Sceastha return (0);
1610Sstevel@tonic-gate }
162