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