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 */
220d8b5334Sceastha /*
230d8b5334Sceastha * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
240d8b5334Sceastha * Use is subject to license terms.
250d8b5334Sceastha */
260d8b5334Sceastha
277c478bd9Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
28*2e8cdddbSRobert Mustacchi /* All Rights Reserved */
297c478bd9Sstevel@tonic-gate
307c478bd9Sstevel@tonic-gate
317c478bd9Sstevel@tonic-gate #include <unistd.h>
327c478bd9Sstevel@tonic-gate #include <stdlib.h>
337c478bd9Sstevel@tonic-gate #include <stdio.h>
347c478bd9Sstevel@tonic-gate #include <locale.h>
357c478bd9Sstevel@tonic-gate #include "hash.h"
367c478bd9Sstevel@tonic-gate #include "huff.h"
377c478bd9Sstevel@tonic-gate
387c478bd9Sstevel@tonic-gate int encode(long, long *);
397c478bd9Sstevel@tonic-gate
407c478bd9Sstevel@tonic-gate #define S (BYTE * sizeof (long))
417c478bd9Sstevel@tonic-gate #define B (BYTE * sizeof (unsigned))
427c478bd9Sstevel@tonic-gate unsigned *table;
437c478bd9Sstevel@tonic-gate int hindex[NI];
447c478bd9Sstevel@tonic-gate unsigned wp; /* word pointer */
457c478bd9Sstevel@tonic-gate int bp = B; /* bit pointer */
467c478bd9Sstevel@tonic-gate static int ignore;
477c478bd9Sstevel@tonic-gate static int extra;
487c478bd9Sstevel@tonic-gate
497c478bd9Sstevel@tonic-gate static int
append(register unsigned w1,register int i)507c478bd9Sstevel@tonic-gate append(register unsigned w1, register int i)
517c478bd9Sstevel@tonic-gate {
527c478bd9Sstevel@tonic-gate while (wp < ND - 1) {
537c478bd9Sstevel@tonic-gate table[wp] |= w1>>(B-bp);
547c478bd9Sstevel@tonic-gate i -= bp;
557c478bd9Sstevel@tonic-gate if (i < 0) {
567c478bd9Sstevel@tonic-gate bp = -i;
577c478bd9Sstevel@tonic-gate return (1);
587c478bd9Sstevel@tonic-gate }
597c478bd9Sstevel@tonic-gate w1 <<= bp;
607c478bd9Sstevel@tonic-gate bp = B;
617c478bd9Sstevel@tonic-gate wp++;
627c478bd9Sstevel@tonic-gate }
637c478bd9Sstevel@tonic-gate return (0);
647c478bd9Sstevel@tonic-gate }
657c478bd9Sstevel@tonic-gate
667c478bd9Sstevel@tonic-gate
677c478bd9Sstevel@tonic-gate /*
687c478bd9Sstevel@tonic-gate * usage: hashin N
697c478bd9Sstevel@tonic-gate * where N is number of words in dictionary
707c478bd9Sstevel@tonic-gate * and standard input contains sorted, unique
717c478bd9Sstevel@tonic-gate * hashed words in octal
727c478bd9Sstevel@tonic-gate */
737c478bd9Sstevel@tonic-gate
740d8b5334Sceastha int
main(int argc,char ** argv)757c478bd9Sstevel@tonic-gate main(int argc, char **argv)
767c478bd9Sstevel@tonic-gate {
777c478bd9Sstevel@tonic-gate long h, k, d;
787c478bd9Sstevel@tonic-gate int i;
797c478bd9Sstevel@tonic-gate long count;
807c478bd9Sstevel@tonic-gate long w1;
817c478bd9Sstevel@tonic-gate long x;
827c478bd9Sstevel@tonic-gate int t, u;
837c478bd9Sstevel@tonic-gate double z;
847c478bd9Sstevel@tonic-gate
857c478bd9Sstevel@tonic-gate /* Set locale environment variables local definitions */
867c478bd9Sstevel@tonic-gate (void) setlocale(LC_ALL, "");
877c478bd9Sstevel@tonic-gate #if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */
887c478bd9Sstevel@tonic-gate #define TEXT_DOMAIN "SYS_TEST" /* Use this only if it wasn't */
897c478bd9Sstevel@tonic-gate #endif
907c478bd9Sstevel@tonic-gate (void) textdomain(TEXT_DOMAIN);
917c478bd9Sstevel@tonic-gate
927c478bd9Sstevel@tonic-gate k = 0;
937c478bd9Sstevel@tonic-gate u = 0;
947c478bd9Sstevel@tonic-gate if (argc != 2) {
957c478bd9Sstevel@tonic-gate (void) fprintf(stderr, gettext("%s: arg count\n"), argv[0]);
967c478bd9Sstevel@tonic-gate exit(1);
977c478bd9Sstevel@tonic-gate }
98*2e8cdddbSRobert Mustacchi table = (unsigned *)calloc(ND, sizeof (*table));
997c478bd9Sstevel@tonic-gate if (table == 0) {
1007c478bd9Sstevel@tonic-gate (void) fprintf(stderr, gettext("%s: no space for table\n"),
1017c478bd9Sstevel@tonic-gate argv[0]);
1027c478bd9Sstevel@tonic-gate exit(1);
1037c478bd9Sstevel@tonic-gate }
1047c478bd9Sstevel@tonic-gate if ((atof(argv[1])) == 0.0) {
1057c478bd9Sstevel@tonic-gate (void) fprintf(stderr, gettext("%s: illegal count"), argv[0]);
1067c478bd9Sstevel@tonic-gate exit(1);
1077c478bd9Sstevel@tonic-gate }
1087c478bd9Sstevel@tonic-gate
1097c478bd9Sstevel@tonic-gate z = huff((1L<<HASHWIDTH)/atof(argv[1]));
1107c478bd9Sstevel@tonic-gate (void) fprintf(stderr, gettext("%s: expected code widths = %f\n"),
1117c478bd9Sstevel@tonic-gate argv[0], z);
1127c478bd9Sstevel@tonic-gate for (count = 0; scanf("%lo", (unsigned long *)&h) == 1; ++count) {
1137c478bd9Sstevel@tonic-gate if ((t = h >> (HASHWIDTH - INDEXWIDTH)) != u) {
1147c478bd9Sstevel@tonic-gate if (bp != B)
1157c478bd9Sstevel@tonic-gate wp++;
1167c478bd9Sstevel@tonic-gate bp = B;
1177c478bd9Sstevel@tonic-gate while (u < t)
1187c478bd9Sstevel@tonic-gate hindex[++u] = wp;
1197c478bd9Sstevel@tonic-gate k = (long)t<<(HASHWIDTH-INDEXWIDTH);
1207c478bd9Sstevel@tonic-gate }
1217c478bd9Sstevel@tonic-gate d = h-k;
1227c478bd9Sstevel@tonic-gate k = h;
1237c478bd9Sstevel@tonic-gate for (;;) {
1247c478bd9Sstevel@tonic-gate for (x = d; ; x /= 2) {
1257c478bd9Sstevel@tonic-gate i = encode(x, &w1);
1267c478bd9Sstevel@tonic-gate if (i > 0)
1277c478bd9Sstevel@tonic-gate break;
1287c478bd9Sstevel@tonic-gate }
1297c478bd9Sstevel@tonic-gate if (i > B) {
130*2e8cdddbSRobert Mustacchi if (!(append((unsigned)(w1>>(long)(i-B)), B) &&
131*2e8cdddbSRobert Mustacchi append((unsigned)(w1<<(long)(B+B-i)),
1327c478bd9Sstevel@tonic-gate i-B)))
1337c478bd9Sstevel@tonic-gate ignore++;
1347c478bd9Sstevel@tonic-gate } else
1357c478bd9Sstevel@tonic-gate if (!append((unsigned)(w1<<(long)(B-i)), i))
1367c478bd9Sstevel@tonic-gate ignore++;
1377c478bd9Sstevel@tonic-gate d -= x;
1387c478bd9Sstevel@tonic-gate if (d > 0)
1397c478bd9Sstevel@tonic-gate extra++;
1407c478bd9Sstevel@tonic-gate else
1417c478bd9Sstevel@tonic-gate break;
1427c478bd9Sstevel@tonic-gate }
1437c478bd9Sstevel@tonic-gate }
1447c478bd9Sstevel@tonic-gate if (bp != B)
1457c478bd9Sstevel@tonic-gate wp++;
1467c478bd9Sstevel@tonic-gate while (++u < NI)
1477c478bd9Sstevel@tonic-gate hindex[u] = wp;
1487c478bd9Sstevel@tonic-gate whuff();
1497c478bd9Sstevel@tonic-gate (void) fwrite((char *)hindex, sizeof (*hindex), NI, stdout);
1507c478bd9Sstevel@tonic-gate (void) fwrite((char *)table, sizeof (*table), wp, stdout);
1517c478bd9Sstevel@tonic-gate (void) fprintf(stderr,
1527c478bd9Sstevel@tonic-gate gettext("%s: %ld items, %d ignored, %d extra, %u words occupied\n"),
1537c478bd9Sstevel@tonic-gate argv[0], count, ignore, extra, wp);
1547c478bd9Sstevel@tonic-gate count -= ignore;
1557c478bd9Sstevel@tonic-gate (void) fprintf(stderr, "%s: %f table bits/item, %f table+index bits\n",
1567c478bd9Sstevel@tonic-gate argv[0], (((float)BYTE * wp) * sizeof (*table) / count),
1577c478bd9Sstevel@tonic-gate (BYTE * ((float)wp * sizeof (*table) + sizeof (hindex)) / count));
1580d8b5334Sceastha return (0);
1597c478bd9Sstevel@tonic-gate }
160