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 #include <unistd.h> 32 #include <stdlib.h> 33 #include <stdio.h> 34 #include <locale.h> 35 #include "hash.h" 36 #include "huff.h" 37 38 int encode(long, long *); 39 40 #define S (BYTE * sizeof (long)) 41 #define B (BYTE * sizeof (unsigned)) 42 unsigned *table; 43 int hindex[NI]; 44 unsigned wp; /* word pointer */ 45 int bp = B; /* bit pointer */ 46 static int ignore; 47 static int extra; 48 49 static int 50 append(register unsigned w1, register int i) 51 { 52 while (wp < ND - 1) { 53 table[wp] |= w1>>(B-bp); 54 i -= bp; 55 if (i < 0) { 56 bp = -i; 57 return (1); 58 } 59 w1 <<= bp; 60 bp = B; 61 wp++; 62 } 63 return (0); 64 } 65 66 67 /* 68 * usage: hashin N 69 * where N is number of words in dictionary 70 * and standard input contains sorted, unique 71 * hashed words in octal 72 */ 73 74 int 75 main(int argc, char **argv) 76 { 77 long h, k, d; 78 int i; 79 long count; 80 long w1; 81 long x; 82 int t, u; 83 double z; 84 85 /* Set locale environment variables local definitions */ 86 (void) setlocale(LC_ALL, ""); 87 #if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */ 88 #define TEXT_DOMAIN "SYS_TEST" /* Use this only if it wasn't */ 89 #endif 90 (void) textdomain(TEXT_DOMAIN); 91 92 k = 0; 93 u = 0; 94 if (argc != 2) { 95 (void) fprintf(stderr, gettext("%s: arg count\n"), argv[0]); 96 exit(1); 97 } 98 table = (unsigned *)calloc(ND, sizeof (*table)); 99 if (table == 0) { 100 (void) fprintf(stderr, gettext("%s: no space for table\n"), 101 argv[0]); 102 exit(1); 103 } 104 if ((atof(argv[1])) == 0.0) { 105 (void) fprintf(stderr, gettext("%s: illegal count"), argv[0]); 106 exit(1); 107 } 108 109 z = huff((1L<<HASHWIDTH)/atof(argv[1])); 110 (void) fprintf(stderr, gettext("%s: expected code widths = %f\n"), 111 argv[0], z); 112 for (count = 0; scanf("%lo", (unsigned long *)&h) == 1; ++count) { 113 if ((t = h >> (HASHWIDTH - INDEXWIDTH)) != u) { 114 if (bp != B) 115 wp++; 116 bp = B; 117 while (u < t) 118 hindex[++u] = wp; 119 k = (long)t<<(HASHWIDTH-INDEXWIDTH); 120 } 121 d = h-k; 122 k = h; 123 for (;;) { 124 for (x = d; ; x /= 2) { 125 i = encode(x, &w1); 126 if (i > 0) 127 break; 128 } 129 if (i > B) { 130 if (!(append((unsigned)(w1>>(long)(i-B)), B) && 131 append((unsigned)(w1<<(long)(B+B-i)), 132 i-B))) 133 ignore++; 134 } else 135 if (!append((unsigned)(w1<<(long)(B-i)), i)) 136 ignore++; 137 d -= x; 138 if (d > 0) 139 extra++; 140 else 141 break; 142 } 143 } 144 if (bp != B) 145 wp++; 146 while (++u < NI) 147 hindex[u] = wp; 148 whuff(); 149 (void) fwrite((char *)hindex, sizeof (*hindex), NI, stdout); 150 (void) fwrite((char *)table, sizeof (*table), wp, stdout); 151 (void) fprintf(stderr, 152 gettext("%s: %ld items, %d ignored, %d extra, %u words occupied\n"), 153 argv[0], count, ignore, extra, wp); 154 count -= ignore; 155 (void) fprintf(stderr, "%s: %f table bits/item, %f table+index bits\n", 156 argv[0], (((float)BYTE * wp) * sizeof (*table) / count), 157 (BYTE * ((float)wp * sizeof (*table) + sizeof (hindex)) / count)); 158 return (0); 159 } 160