1 /*
2 * Copyright (c) 1989 The Regents of the University of California.
3 * All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * James A. Woods.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37 #ifndef lint
38 char copyright[] =
39 "@(#) Copyright (c) 1989 The Regents of the University of California.\n\
40 All rights reserved.\n";
41 #endif /* not lint */
42
43 #ifndef lint
44 static char sccsid[] = "@(#)locate.code.c 4.8 (Berkeley) 6/1/90";
45 #endif /* not lint */
46
47 /*
48 * PURPOSE: sorted list compressor (works with a modified 'find'
49 * to encode/decode a filename database)
50 *
51 * USAGE: bigram < list > bigrams
52 * process bigrams (see updatedb) > common_bigrams
53 * code common_bigrams < list > squozen_list
54 *
55 * METHOD: Uses 'front compression' (see ";login:", Volume 8, Number 1
56 * February/March 1983, p. 8 ). Output format is, per line, an
57 * offset differential count byte followed by a partially bigram-
58 * encoded ascii residue. A bigram is a two-character sequence,
59 * the first 128 most common of which are encoded in one byte.
60 *
61 * EXAMPLE: For simple front compression with no bigram encoding,
62 * if the input is... then the output is...
63 *
64 * /usr/src 0 /usr/src
65 * /usr/src/cmd/aardvark.c 8 /cmd/aardvark.c
66 * /usr/src/cmd/armadillo.c 14 armadillo.c
67 * /usr/tmp/zoo 5 tmp/zoo
68 *
69 * The codes are:
70 *
71 * 0-28 likeliest differential counts + offset to make nonnegative
72 * 30 switch code for out-of-range count to follow in next word
73 * 128-255 bigram codes (128 most common, as determined by 'updatedb')
74 * 32-127 single character (printable) ascii residue (ie, literal)
75 *
76 * SEE ALSO: updatedb.csh, bigram.c, find.c
77 *
78 * AUTHOR: James A. Woods, Informatics General Corp.,
79 * NASA Ames Research Center, 10/82
80 */
81
82 #include <sys/param.h>
83 #include <stdio.h>
84 #include "locate.h"
85
86 #define BGBUFSIZE (NBG * 2) /* size of bigram buffer */
87
88 char buf1[PATH_MAX] = " ";
89 char buf2[PATH_MAX];
90 char bigrams[BGBUFSIZE + 1] = { 0 };
91
main(argc,argv)92 main ( argc, argv )
93 int argc; char *argv[];
94 {
95 register char *cp, *oldpath = buf1, *path = buf2;
96 int code, count, diffcount, oldcount = 0;
97 FILE *fp;
98
99 if ((fp = fopen(argv[1], "r")) == NULL) {
100 printf("Usage: code common_bigrams < list > squozen_list\n");
101 exit(1);
102 }
103 /* first copy bigram array to stdout */
104 fgets ( bigrams, BGBUFSIZE + 1, fp );
105 fwrite ( bigrams, 1, BGBUFSIZE, stdout );
106 fclose( fp );
107
108 while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) {
109 /* truncate newline */
110 cp = path + strlen(path) - 1;
111 if (cp > path && *cp == '\n')
112 *cp = '\0';
113 /* squelch characters that would botch the decoding */
114 for ( cp = path; *cp != NULL; cp++ ) {
115 if ( (unsigned char)*cp >= PARITY )
116 *cp &= PARITY-1;
117 else if ( *cp <= SWITCH )
118 *cp = '?';
119 }
120 /* skip longest common prefix */
121 for ( cp = path; *cp == *oldpath; cp++, oldpath++ )
122 if ( *oldpath == NULL )
123 break;
124 count = cp - path;
125 diffcount = count - oldcount + OFFSET;
126 oldcount = count;
127 if ( diffcount < 0 || diffcount > 2*OFFSET ) {
128 putc ( SWITCH, stdout );
129 putw ( diffcount, stdout );
130 }
131 else
132 putc ( diffcount, stdout );
133
134 while ( *cp != NULL ) {
135 if ( *(cp + 1) == NULL ) {
136 putchar ( *cp );
137 break;
138 }
139 if ( (code = bgindex ( cp )) < 0 ) {
140 putchar ( *cp++ );
141 putchar ( *cp++ );
142 }
143 else { /* found, so mark byte with parity bit */
144 putchar ( (code / 2) | PARITY );
145 cp += 2;
146 }
147 }
148 if ( path == buf1 ) /* swap pointers */
149 path = buf2, oldpath = buf1;
150 else
151 path = buf1, oldpath = buf2;
152 }
153 }
154
bgindex(bg)155 bgindex ( bg ) /* return location of bg in bigrams or -1 */
156 char *bg;
157 {
158 register char *p;
159 register char bg0 = bg[0], bg1 = bg[1];
160
161 for ( p = bigrams; *p != NULL; p++ )
162 if ( *p++ == bg0 && *p == bg1 )
163 break;
164 return ( *p == NULL ? -1 : --p - bigrams );
165 }
166