usr.bin/locate/code/locate.code.c

   1 /*
   2  * Copyright (c) 1995 Wolfram Schneider <wosch@FreeBSD.org>. Berlin.
   3  * Copyright (c) 1989, 1993
   4  *      The Regents of the University of California.  All rights reserved.
   5  *
   6  * This code is derived from software contributed to Berkeley by
   7  * James A. Woods.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  * 3. All advertising materials mentioning features or use of this software
  18  *    must display the following acknowledgement:
  19  *      This product includes software developed by the University of
  20  *      California, Berkeley and its contributors.
  21  * 4. Neither the name of the University nor the names of its contributors
  22  *    may be used to endorse or promote products derived from this software
  23  *    without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  26  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  29  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  30  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  31  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  32  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  33  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  34  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  35  * SUCH DAMAGE.
  36  *
  37  * $FreeBSD$
  38  */
  39
  40 #if 0
  41 #ifndef lint
  42 static char copyright[] =
  43 "@(#) Copyright (c) 1989, 1993\n\
  44         The Regents of the University of California.  All rights reserved.\n";
  45 #endif /* not lint */
  46
  47 #ifndef lint
  48 static char sccsid[] = "@(#)locate.code.c       8.1 (Berkeley) 6/6/93";
  49 #endif /* not lint */
  50 #endif
  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  *      31      an 8 bit char followed
  79  *      128-255 bigram codes (128 most common, as determined by 'updatedb')
  80  *      32-127  single character (printable) ascii residue (ie, literal)
  81  *
  82  * The locate database store any character except newline ('\n')
  83  * and NUL ('\0'). The 8-bit character support don't wast extra
  84  * space until you have characters in file names less than 32
  85  * or greather than 127.
  86  *
  87  *
  88  * SEE ALSO:    updatedb.sh, ../bigram/locate.bigram.c
  89  *
  90  * AUTHOR:      James A. Woods, Informatics General Corp.,
  91  *              NASA Ames Research Center, 10/82
  92  *              8-bit file names characters:
  93  *                      Wolfram Schneider, Berlin September 1996
  94  */
  95
  96 #include <sys/param.h>
  97 #include <err.h>
  98 #include <errno.h>
  99 #include <stdlib.h>
 100 #include <string.h>
 101 #include <stdio.h>
 102 #include <unistd.h>
 103 #include "locate.h"
 104
 105 #define BGBUFSIZE       (NBG * 2)       /* size of bigram buffer */
 106
 107 u_char buf1[MAXPATHLEN] = " ";
 108 u_char buf2[MAXPATHLEN];
 109 u_char bigrams[BGBUFSIZE + 1] = { 0 };
 110
 111 #define LOOKUP 1 /* use a lookup array instead a function, 3x faster */
 112
 113 #ifdef LOOKUP
 114 #define BGINDEX(x) (big[(u_char)*x][(u_char)*(x + 1)])
 115 typedef short bg_t;
 116 bg_t big[UCHAR_MAX + 1][UCHAR_MAX + 1];
 117 #else
 118 #define BGINDEX(x) bgindex(x)
 119 typedef int bg_t;
 120 int     bgindex(char *);
 121 #endif /* LOOKUP */
 122
 123
 124 void    usage(void);
 125
 126 int
 127 main(int argc, char *argv[])
 128 {
 129         u_char *cp, *oldpath, *path;
 130         int ch, code, count, diffcount, oldcount;
 131         u_int i, j;
 132         FILE *fp;
 133
 134         while ((ch = getopt(argc, argv, "")) != -1)
 135                 switch(ch) {
 136                 default:
 137                         usage();
 138                 }
 139         argc -= optind;
 140         argv += optind;
 141
 142         if (argc != 1)
 143                 usage();
 144
 145         if ((fp = fopen(argv[0], "r")) == NULL)
 146                 err(1, "%s", argv[0]);
 147
 148         /* First copy bigram array to stdout. */
 149         (void)fgets(bigrams, BGBUFSIZE + 1, fp);
 150
 151         if (fwrite(bigrams, 1, BGBUFSIZE, stdout) != BGBUFSIZE)
 152                 err(1, "stdout");
 153         (void)fclose(fp);
 154
 155 #ifdef LOOKUP
 156         /* init lookup table */
 157         for (i = 0; i < UCHAR_MAX + 1; i++)
 158                 for (j = 0; j < UCHAR_MAX + 1; j++)
 159                         big[i][j] = (bg_t)-1;
 160
 161         for (cp = bigrams, i = 0; *cp != '\0'; i += 2, cp += 2)
 162                 big[(u_char)*cp][(u_char)*(cp + 1)] = (bg_t)i;
 163
 164 #endif /* LOOKUP */
 165
 166         oldpath = buf1;
 167         path = buf2;
 168         oldcount = 0;
 169
 170         while (fgets(path, sizeof(buf2), stdin) != NULL) {
 171
 172                 /* skip empty lines */
 173                 if (*path == '\n')
 174                         continue;
 175
 176                 /* remove newline */
 177                 for (cp = path; *cp != '\0'; cp++) {
 178 #ifndef LOCATE_CHAR30
 179                         /* old locate implementations core'd for char 30 */
 180                         if (*cp == SWITCH)
 181                                 *cp = '?';
 182                         else
 183 #endif /* !LOCATE_CHAR30 */
 184
 185                         /* chop newline */
 186                         if (*cp == '\n')
 187                                 *cp = '\0';
 188                 }
 189
 190                 /* Skip longest common prefix. */
 191                 for (cp = path; *cp == *oldpath; cp++, oldpath++)
 192                         if (*cp == '\0')
 193                                 break;
 194
 195                 count = cp - path;
 196                 diffcount = count - oldcount + OFFSET;
 197                 oldcount = count;
 198                 if (diffcount < 0 || diffcount > 2 * OFFSET) {
 199                         if (putchar(SWITCH) == EOF ||
 200                             putw(diffcount, stdout) == EOF)
 201                                 err(1, "stdout");
 202                 } else
 203                         if (putchar(diffcount) == EOF)
 204                                 err(1, "stdout");
 205
 206                 while (*cp != '\0') {
 207                         /* print *two* characters */
 208
 209                         if ((code = BGINDEX(cp)) != (bg_t)-1) {
 210                                 /*
 211                                  * print *one* as bigram
 212                                  * Found, so mark byte with
 213                                  *  parity bit.
 214                                  */
 215                                 if (putchar((code / 2) | PARITY) == EOF)
 216                                         err(1, "stdout");
 217                                 cp += 2;
 218                         }
 219
 220                         else {
 221                                 for (i = 0; i < 2; i++) {
 222                                         if (*cp == '\0')
 223                                                 break;
 224
 225                                         /* print umlauts in file names */
 226                                         if (*cp < ASCII_MIN ||
 227                                             *cp > ASCII_MAX) {
 228                                                 if (putchar(UMLAUT) == EOF ||
 229                                                     putchar(*cp++) == EOF)
 230                                                         err(1, "stdout");
 231                                         }
 232
 233                                         else {
 234                                                 /* normal character */
 235                                                 if(putchar(*cp++) == EOF)
 236                                                         err(1, "stdout");
 237                                         }
 238                                 }
 239
 240                         }
 241                 }
 242
 243                 if (path == buf1) {             /* swap pointers */
 244                         path = buf2;
 245                         oldpath = buf1;
 246                 } else {
 247                         path = buf1;
 248                         oldpath = buf2;
 249                 }
 250         }
 251         /* Non-zero status if there were errors */
 252         if (fflush(stdout) != 0 || ferror(stdout))
 253                 exit(1);
 254         exit(0);
 255 }
 256
 257 #ifndef LOOKUP
 258 int
 259 bgindex(char *bg)               /* Return location of bg in bigrams or -1. */
 260 {
 261         char bg0, bg1, *p;
 262
 263         bg0 = bg[0];
 264         bg1 = bg[1];
 265         for (p = bigrams; *p != NULL; p++)
 266                 if (*p++ == bg0 && *p == bg1)
 267                         break;
 268         return (*p == NULL ? -1 : (--p - bigrams));
 269 }
 270 #endif /* !LOOKUP */
 271
 272 void
 273 usage(void)
 274 {
 275         (void)fprintf(stderr,
 276             "usage: locate.code common_bigrams < list > squozen_list\n");
 277         exit(1);
 278 }