137637Sbostic /*
262062Sbostic  * Copyright (c) 1989, 1993
362062Sbostic  *	The Regents of the University of California.  All rights reserved.
437637Sbostic  *
537637Sbostic  * This code is derived from software contributed to Berkeley by
637637Sbostic  * James A. Woods.
737637Sbostic  *
842737Sbostic  * %sccs.include.redist.c%
937637Sbostic  */
1037637Sbostic 
1114040Smckusick #ifndef lint
1262062Sbostic static char copyright[] =
1362062Sbostic "@(#) Copyright (c) 1989, 1993\n\
1462062Sbostic 	The Regents of the University of California.  All rights reserved.\n";
1537637Sbostic #endif /* not lint */
1614040Smckusick 
1737637Sbostic #ifndef lint
18*69243Sbostic static char sccsid[] = "@(#)locate.code.c	8.4 (Berkeley) 05/04/95";
1937637Sbostic #endif /* not lint */
2037637Sbostic 
2114040Smckusick /*
2214040Smckusick  * PURPOSE:	sorted list compressor (works with a modified 'find'
2314040Smckusick  *		to encode/decode a filename database)
2414040Smckusick  *
2514051Smckusick  * USAGE:	bigram < list > bigrams
2614051Smckusick  *		process bigrams (see updatedb) > common_bigrams
2714051Smckusick  *		code common_bigrams < list > squozen_list
2814040Smckusick  *
2937636Sjak  * METHOD:	Uses 'front compression' (see ";login:", Volume 8, Number 1
3052426Sbostic  *		February/March 1983, p. 8).  Output format is, per line, an
3137636Sjak  *		offset differential count byte followed by a partially bigram-
3237636Sjak  *		encoded ascii residue.  A bigram is a two-character sequence,
3337636Sjak  *		the first 128 most common of which are encoded in one byte.
3414040Smckusick  *
3537636Sjak  * EXAMPLE:	For simple front compression with no bigram encoding,
3637636Sjak  *		if the input is...		then the output is...
3737636Sjak  *
3837636Sjak  *		/usr/src			 0 /usr/src
3937636Sjak  *		/usr/src/cmd/aardvark.c		 8 /cmd/aardvark.c
4037636Sjak  *		/usr/src/cmd/armadillo.c	14 armadillo.c
4137636Sjak  *		/usr/tmp/zoo			 5 tmp/zoo
4237636Sjak  *
4352279Sleres  *	The codes are:
4414040Smckusick  *
4552279Sleres  *	0-28	likeliest differential counts + offset to make nonnegative
4637636Sjak  *	30	switch code for out-of-range count to follow in next word
4737636Sjak  *	128-255 bigram codes (128 most common, as determined by 'updatedb')
4837636Sjak  *	32-127  single character (printable) ascii residue (ie, literal)
4914040Smckusick  *
5052426Sbostic  * SEE ALSO:	updatedb.csh, bigram.c
5152279Sleres  *
5214040Smckusick  * AUTHOR:	James A. Woods, Informatics General Corp.,
5314040Smckusick  *		NASA Ames Research Center, 10/82
5414040Smckusick  */
5514040Smckusick 
5640302Sbostic #include <sys/param.h>
57*69243Sbostic 
5859059Storek #include <err.h>
5952426Sbostic #include <errno.h>
60*69243Sbostic #include <stdio.h>
6152426Sbostic #include <stdlib.h>
6252426Sbostic #include <string.h>
63*69243Sbostic #include <unistd.h>
64*69243Sbostic 
6540302Sbostic #include "locate.h"
6614040Smckusick 
6752426Sbostic #define	BGBUFSIZE	(NBG * 2)	/* size of bigram buffer */
6814040Smckusick 
6937636Sjak char buf1[MAXPATHLEN] = " ";
7037636Sjak char buf2[MAXPATHLEN];
7137636Sjak char bigrams[BGBUFSIZE + 1] = { 0 };
7214040Smckusick 
7352426Sbostic int	bgindex __P((char *));
7452426Sbostic void	usage __P((void));
7552426Sbostic 
7652426Sbostic int
main(argc,argv)7752426Sbostic main(argc, argv)
7852426Sbostic 	int argc;
7952426Sbostic 	char *argv[];
8014040Smckusick {
8152426Sbostic 	register char *cp, *oldpath, *path;
8252426Sbostic 	int ch, code, count, diffcount, oldcount;
8314040Smckusick 	FILE *fp;
8414040Smckusick 
8552426Sbostic 	while ((ch = getopt(argc, argv, "")) != EOF)
8652426Sbostic 		switch(ch) {
8752426Sbostic 		case '?':
8852426Sbostic 		default:
8952426Sbostic 			usage();
9052426Sbostic 		}
9152426Sbostic 	argc -= optind;
9252426Sbostic 	argv += optind;
9314040Smckusick 
9452426Sbostic 	if (argc != 1)
9552426Sbostic 		usage();
9652426Sbostic 
9759059Storek 	if ((fp = fopen(argv[0], "r")) == NULL)
9859059Storek 		err(1, "%s", argv[0]);
9952426Sbostic 
10052426Sbostic 	/* First copy bigram array to stdout. */
10152426Sbostic 	(void)fgets(bigrams, BGBUFSIZE + 1, fp);
10252426Sbostic 	if (fwrite(bigrams, 1, BGBUFSIZE, stdout) != BGBUFSIZE)
10359059Storek 		err(1, "stdout");
10452426Sbostic 	(void)fclose(fp);
10552426Sbostic 
10652426Sbostic 	oldpath = buf1;
10752426Sbostic 	path = buf2;
10852426Sbostic 	oldcount = 0;
10952426Sbostic 	while (fgets(path, sizeof(buf2), stdin) != NULL) {
11052426Sbostic 		/* Truncate newline. */
11139275Sbostic 		cp = path + strlen(path) - 1;
11239275Sbostic 		if (cp > path && *cp == '\n')
11339275Sbostic 			*cp = '\0';
11452426Sbostic 
11552426Sbostic 		/* Squelch characters that would botch the decoding. */
11669017Sbostic 		for (cp = path; *cp != '\0'; cp++) {
11769017Sbostic 			if ((u_char)*cp >= PARITY || *cp <= SWITCH)
11837636Sjak 				*cp = '?';
11914040Smckusick 		}
12052426Sbostic 
12152426Sbostic 		/* Skip longest common prefix. */
12252426Sbostic 		for (cp = path; *cp == *oldpath; cp++, oldpath++)
12369017Sbostic 			if (*oldpath == '\0')
12437636Sjak 				break;
12537636Sjak 		count = cp - path;
12637636Sjak 		diffcount = count - oldcount + OFFSET;
12737636Sjak 		oldcount = count;
12853692Selan 		if (diffcount < 0 || diffcount > 2 * OFFSET) {
12952426Sbostic 			if (putchar(SWITCH) == EOF ||
13052426Sbostic 			    putw(diffcount, stdout) == EOF)
13159059Storek 				err(1, "stdout");
13253692Selan 		} else
13352426Sbostic 			if (putchar(diffcount) == EOF)
13459059Storek 				err(1, "stdout");
13514040Smckusick 
13669017Sbostic 		while (*cp != '\0') {
13769017Sbostic 			if (*(cp + 1) == '\0') {
13852426Sbostic 				if (putchar(*cp) == EOF)
13959059Storek 					err(1, "stdout");
14014040Smckusick 				break;
14114040Smckusick 			}
14252426Sbostic 			if ((code = bgindex(cp)) < 0) {
14352426Sbostic 				if (putchar(*cp++) == EOF ||
14452426Sbostic 				    putchar(*cp++) == EOF)
14559059Storek 					err(1, "stdout");
14652426Sbostic 			} else {
14752426Sbostic 				/* Found, so mark byte with parity bit. */
14852426Sbostic 				if (putchar((code / 2) | PARITY) == EOF)
14959059Storek 					err(1, "stdout");
15037636Sjak 				cp += 2;
15137636Sjak 			}
15214040Smckusick 		}
15352426Sbostic 		if (path == buf1) {		/* swap pointers */
15452426Sbostic 			path = buf2;
15552426Sbostic 			oldpath = buf1;
15652426Sbostic 		} else {
15752426Sbostic 			path = buf1;
15852426Sbostic 			oldpath = buf2;
15952426Sbostic 		}
16014040Smckusick 	}
16152775Smckusick 	/* Non-zero status if there were errors */
16252775Smckusick 	if (fflush(stdout) != 0 || ferror(stdout))
16352775Smckusick 		exit(1);
16452426Sbostic 	exit(0);
16514040Smckusick }
16614040Smckusick 
16752426Sbostic int
bgindex(bg)16852426Sbostic bgindex(bg)			/* Return location of bg in bigrams or -1. */
16937636Sjak 	char *bg;
17014040Smckusick {
17152426Sbostic 	register char bg0, bg1, *p;
17214040Smckusick 
17352426Sbostic 	bg0 = bg[0];
17452426Sbostic 	bg1 = bg[1];
17569017Sbostic 	for (p = bigrams; *p != '\0'; p++)
17652426Sbostic 		if (*p++ == bg0 && *p == bg1)
17737636Sjak 			break;
17869017Sbostic 	return (*p == '\0' ? -1 : --p - bigrams);
17914040Smckusick }
18052426Sbostic 
18152426Sbostic void
usage()18252426Sbostic usage()
18352426Sbostic {
18452426Sbostic 	(void)fprintf(stderr,
18552426Sbostic 	    "usage: locate.code common_bigrams < list > squozen_list\n");
18652426Sbostic 	exit(1);
18752426Sbostic }
188