1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
28 /* All Rights Reserved */
29
30
31 #pragma ident "%Z%%M% %I% %E% SMI"
32
33 #include <unistd.h>
34 #include <stdlib.h>
35 #include <stdio.h>
36 #include <locale.h>
37 #include "hash.h"
38 #include "huff.h"
39
40 int encode(long, long *);
41
42 #define S (BYTE * sizeof (long))
43 #define B (BYTE * sizeof (unsigned))
44 unsigned *table;
45 int hindex[NI];
46 unsigned wp; /* word pointer */
47 int bp = B; /* bit pointer */
48 static int ignore;
49 static int extra;
50
51 static int
append(register unsigned w1,register int i)52 append(register unsigned w1, register int i)
53 {
54 while (wp < ND - 1) {
55 table[wp] |= w1>>(B-bp);
56 i -= bp;
57 if (i < 0) {
58 bp = -i;
59 return (1);
60 }
61 w1 <<= bp;
62 bp = B;
63 wp++;
64 }
65 return (0);
66 }
67
68
69 /*
70 * usage: hashin N
71 * where N is number of words in dictionary
72 * and standard input contains sorted, unique
73 * hashed words in octal
74 */
75
76 int
main(int argc,char ** argv)77 main(int argc, char **argv)
78 {
79 long h, k, d;
80 int i;
81 long count;
82 long w1;
83 long x;
84 int t, u;
85 double z;
86
87 /* Set locale environment variables local definitions */
88 (void) setlocale(LC_ALL, "");
89 #if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */
90 #define TEXT_DOMAIN "SYS_TEST" /* Use this only if it wasn't */
91 #endif
92 (void) textdomain(TEXT_DOMAIN);
93
94 k = 0;
95 u = 0;
96 if (argc != 2) {
97 (void) fprintf(stderr, gettext("%s: arg count\n"), argv[0]);
98 exit(1);
99 }
100 table = (unsigned *)malloc(ND * sizeof (*table));
101 if (table == 0) {
102 (void) fprintf(stderr, gettext("%s: no space for table\n"),
103 argv[0]);
104 exit(1);
105 }
106 if ((atof(argv[1])) == 0.0) {
107 (void) fprintf(stderr, gettext("%s: illegal count"), argv[0]);
108 exit(1);
109 }
110
111 z = huff((1L<<HASHWIDTH)/atof(argv[1]));
112 (void) fprintf(stderr, gettext("%s: expected code widths = %f\n"),
113 argv[0], z);
114 for (count = 0; scanf("%lo", (unsigned long *)&h) == 1; ++count) {
115 if ((t = h >> (HASHWIDTH - INDEXWIDTH)) != u) {
116 if (bp != B)
117 wp++;
118 bp = B;
119 while (u < t)
120 hindex[++u] = wp;
121 k = (long)t<<(HASHWIDTH-INDEXWIDTH);
122 }
123 d = h-k;
124 k = h;
125 for (;;) {
126 for (x = d; ; x /= 2) {
127 i = encode(x, &w1);
128 if (i > 0)
129 break;
130 }
131 if (i > B) {
132 if (!(append((unsigned)(w1>>(long) (i-B)), B) &&
133 append((unsigned)(w1<<(long) (B+B-i)),
134 i-B)))
135 ignore++;
136 } else
137 if (!append((unsigned)(w1<<(long)(B-i)), i))
138 ignore++;
139 d -= x;
140 if (d > 0)
141 extra++;
142 else
143 break;
144 }
145 }
146 if (bp != B)
147 wp++;
148 while (++u < NI)
149 hindex[u] = wp;
150 whuff();
151 (void) fwrite((char *)hindex, sizeof (*hindex), NI, stdout);
152 (void) fwrite((char *)table, sizeof (*table), wp, stdout);
153 (void) fprintf(stderr,
154 gettext("%s: %ld items, %d ignored, %d extra, %u words occupied\n"),
155 argv[0], count, ignore, extra, wp);
156 count -= ignore;
157 (void) fprintf(stderr, "%s: %f table bits/item, %f table+index bits\n",
158 argv[0], (((float)BYTE * wp) * sizeof (*table) / count),
159 (BYTE * ((float)wp * sizeof (*table) + sizeof (hindex)) / count));
160 return (0);
161 }
162