locate/code/locate.code.c

   1 /*      $NetBSD: locate.code.c,v 1.6 1997/10/19 04:11:54 lukem 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.6 1997/10/19 04:11:54 lukem 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         FILE *fp;
 116
 117         while ((ch = getopt(argc, argv, "")) != -1)
 118                 switch(ch) {
 119                 case '?':
 120                 default:
 121                         usage();
 122                 }
 123         argc -= optind;
 124         argv += optind;
 125
 126         if (argc != 1)
 127                 usage();
 128
 129         if ((fp = fopen(argv[0], "r")) == NULL)
 130                 err(1, "%s", argv[0]);
 131
 132         /* First copy bigram array to stdout. */
 133         (void)fgets(bigrams, BGBUFSIZE + 1, fp);
 134         if (fwrite(bigrams, 1, BGBUFSIZE, stdout) != BGBUFSIZE)
 135                 err(1, "stdout");
 136         (void)fclose(fp);
 137
 138         oldpath = buf1;
 139         path = buf2;
 140         oldcount = 0;
 141         while (fgets(path, sizeof(buf2), stdin) != NULL) {
 142                 /* Truncate newline. */
 143                 cp = path + strlen(path) - 1;
 144                 if (cp > path && *cp == '\n')
 145                         *cp = '\0';
 146
 147                 /* Squelch characters that would botch the decoding. */
 148                 for (cp = path; *cp != '\0'; cp++) {
 149                         *cp &= PARITY-1;
 150                         if (*cp <= SWITCH)
 151                                 *cp = '?';
 152                 }
 153
 154                 /* Skip longest common prefix. */
 155                 for (cp = path; *cp == *oldpath; cp++, oldpath++)
 156                         if (*oldpath == '\0')
 157                                 break;
 158                 count = cp - path;
 159                 diffcount = count - oldcount + OFFSET;
 160                 oldcount = count;
 161                 if (diffcount < 0 || diffcount > 2 * OFFSET) {
 162                         if (putchar(SWITCH) == EOF ||
 163                             putw(diffcount, stdout) == EOF)
 164                                 err(1, "stdout");
 165                 } else
 166                         if (putchar(diffcount) == EOF)
 167                                 err(1, "stdout");
 168
 169                 while (*cp != '\0') {
 170                         if (*(cp + 1) == '\0') {
 171                                 if (putchar(*cp) == EOF)
 172                                         err(1, "stdout");
 173                                 break;
 174                         }
 175                         if ((code = bgindex(cp)) < 0) {
 176                                 if (putchar(*cp++) == EOF ||
 177                                     putchar(*cp++) == EOF)
 178                                         err(1, "stdout");
 179                         } else {
 180                                 /* Found, so mark byte with parity bit. */
 181                                 if (putchar((code / 2) | PARITY) == EOF)
 182                                         err(1, "stdout");
 183                                 cp += 2;
 184                         }
 185                 }
 186                 if (path == buf1) {             /* swap pointers */
 187                         path = buf2;
 188                         oldpath = buf1;
 189                 } else {
 190                         path = buf1;
 191                         oldpath = buf2;
 192                 }
 193         }
 194         /* Non-zero status if there were errors */
 195         if (fflush(stdout) != 0 || ferror(stdout))
 196                 exit(1);
 197         exit(0);
 198 }
 199
 200 int
 201 bgindex(bg)                     /* Return location of bg in bigrams or -1. */
 202         char *bg;
 203 {
 204         char bg0, bg1, *p;
 205
 206         bg0 = bg[0];
 207         bg1 = bg[1];
 208         for (p = bigrams; *p != '\0'; p++)
 209                 if (*p++ == bg0 && *p == bg1)
 210                         break;
 211         return (*p == '\0' ? -1 : --p - bigrams);
 212 }
 213
 214 void
 215 usage()
 216 {
 217         (void)fprintf(stderr,
 218             "usage: locate.code common_bigrams < list > squozen_list\n");
 219         exit(1);
 220 }