1 /*
2 * Copyright (c) 1989, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * James A. Woods.
7 *
8 * %sccs.include.redist.c%
9 */
10
11 #ifndef lint
12 static char copyright[] =
13 "@(#) Copyright (c) 1989, 1993\n\
14 The Regents of the University of California. All rights reserved.\n";
15 #endif /* not lint */
16
17 #ifndef lint
18 static char sccsid[] = "@(#)locate.code.c 8.4 (Berkeley) 05/04/95";
19 #endif /* not lint */
20
21 /*
22 * PURPOSE: sorted list compressor (works with a modified 'find'
23 * to encode/decode a filename database)
24 *
25 * USAGE: bigram < list > bigrams
26 * process bigrams (see updatedb) > common_bigrams
27 * code common_bigrams < list > squozen_list
28 *
29 * METHOD: Uses 'front compression' (see ";login:", Volume 8, Number 1
30 * February/March 1983, p. 8). Output format is, per line, an
31 * offset differential count byte followed by a partially bigram-
32 * encoded ascii residue. A bigram is a two-character sequence,
33 * the first 128 most common of which are encoded in one byte.
34 *
35 * EXAMPLE: For simple front compression with no bigram encoding,
36 * if the input is... then the output is...
37 *
38 * /usr/src 0 /usr/src
39 * /usr/src/cmd/aardvark.c 8 /cmd/aardvark.c
40 * /usr/src/cmd/armadillo.c 14 armadillo.c
41 * /usr/tmp/zoo 5 tmp/zoo
42 *
43 * The codes are:
44 *
45 * 0-28 likeliest differential counts + offset to make nonnegative
46 * 30 switch code for out-of-range count to follow in next word
47 * 128-255 bigram codes (128 most common, as determined by 'updatedb')
48 * 32-127 single character (printable) ascii residue (ie, literal)
49 *
50 * SEE ALSO: updatedb.csh, bigram.c
51 *
52 * AUTHOR: James A. Woods, Informatics General Corp.,
53 * NASA Ames Research Center, 10/82
54 */
55
56 #include <sys/param.h>
57
58 #include <err.h>
59 #include <errno.h>
60 #include <stdio.h>
61 #include <stdlib.h>
62 #include <string.h>
63 #include <unistd.h>
64
65 #include "locate.h"
66
67 #define BGBUFSIZE (NBG * 2) /* size of bigram buffer */
68
69 char buf1[MAXPATHLEN] = " ";
70 char buf2[MAXPATHLEN];
71 char bigrams[BGBUFSIZE + 1] = { 0 };
72
73 int bgindex __P((char *));
74 void usage __P((void));
75
76 int
main(argc,argv)77 main(argc, argv)
78 int argc;
79 char *argv[];
80 {
81 register char *cp, *oldpath, *path;
82 int ch, code, count, diffcount, oldcount;
83 FILE *fp;
84
85 while ((ch = getopt(argc, argv, "")) != EOF)
86 switch(ch) {
87 case '?':
88 default:
89 usage();
90 }
91 argc -= optind;
92 argv += optind;
93
94 if (argc != 1)
95 usage();
96
97 if ((fp = fopen(argv[0], "r")) == NULL)
98 err(1, "%s", argv[0]);
99
100 /* First copy bigram array to stdout. */
101 (void)fgets(bigrams, BGBUFSIZE + 1, fp);
102 if (fwrite(bigrams, 1, BGBUFSIZE, stdout) != BGBUFSIZE)
103 err(1, "stdout");
104 (void)fclose(fp);
105
106 oldpath = buf1;
107 path = buf2;
108 oldcount = 0;
109 while (fgets(path, sizeof(buf2), stdin) != NULL) {
110 /* Truncate newline. */
111 cp = path + strlen(path) - 1;
112 if (cp > path && *cp == '\n')
113 *cp = '\0';
114
115 /* Squelch characters that would botch the decoding. */
116 for (cp = path; *cp != '\0'; cp++) {
117 if ((u_char)*cp >= PARITY || *cp <= SWITCH)
118 *cp = '?';
119 }
120
121 /* Skip longest common prefix. */
122 for (cp = path; *cp == *oldpath; cp++, oldpath++)
123 if (*oldpath == '\0')
124 break;
125 count = cp - path;
126 diffcount = count - oldcount + OFFSET;
127 oldcount = count;
128 if (diffcount < 0 || diffcount > 2 * OFFSET) {
129 if (putchar(SWITCH) == EOF ||
130 putw(diffcount, stdout) == EOF)
131 err(1, "stdout");
132 } else
133 if (putchar(diffcount) == EOF)
134 err(1, "stdout");
135
136 while (*cp != '\0') {
137 if (*(cp + 1) == '\0') {
138 if (putchar(*cp) == EOF)
139 err(1, "stdout");
140 break;
141 }
142 if ((code = bgindex(cp)) < 0) {
143 if (putchar(*cp++) == EOF ||
144 putchar(*cp++) == EOF)
145 err(1, "stdout");
146 } else {
147 /* Found, so mark byte with parity bit. */
148 if (putchar((code / 2) | PARITY) == EOF)
149 err(1, "stdout");
150 cp += 2;
151 }
152 }
153 if (path == buf1) { /* swap pointers */
154 path = buf2;
155 oldpath = buf1;
156 } else {
157 path = buf1;
158 oldpath = buf2;
159 }
160 }
161 /* Non-zero status if there were errors */
162 if (fflush(stdout) != 0 || ferror(stdout))
163 exit(1);
164 exit(0);
165 }
166
167 int
bgindex(bg)168 bgindex(bg) /* Return location of bg in bigrams or -1. */
169 char *bg;
170 {
171 register char bg0, bg1, *p;
172
173 bg0 = bg[0];
174 bg1 = bg[1];
175 for (p = bigrams; *p != '\0'; p++)
176 if (*p++ == bg0 && *p == bg1)
177 break;
178 return (*p == '\0' ? -1 : --p - bigrams);
179 }
180
181 void
usage()182 usage()
183 {
184 (void)fprintf(stderr,
185 "usage: locate.code common_bigrams < list > squozen_list\n");
186 exit(1);
187 }
188