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: src/usr.bin/locate/code/locate.code.c,v 1.11.2.1 2001/03/04 08:46:46 kris Exp $
  38  * $DragonFly: src/usr.bin/locate/code/locate.code.c,v 1.4 2005/08/04 17:31:23 drhodus Exp $
  39  *
  40  * @(#) Copyright (c) 1989, 1993 The Regents of the University of California.  All rights reserved.
  41  * @(#)locate.code.c    8.1 (Berkeley) 6/6/93
  42  */
  43
  44 /*
  45  * PURPOSE:     sorted list compressor (works with a modified 'find'
  46  *              to encode/decode a filename database)
  47  *
  48  * USAGE:       bigram < list > bigrams
  49  *              process bigrams (see updatedb) > common_bigrams
  50  *              code common_bigrams < list > squozen_list
  51  *
  52  * METHOD:      Uses 'front compression' (see ";login:", Volume 8, Number 1
  53  *              February/March 1983, p. 8).  Output format is, per line, an
  54  *              offset differential count byte followed by a partially bigram-
  55  *              encoded ascii residue.  A bigram is a two-character sequence,
  56  *              the first 128 most common of which are encoded in one byte.
  57  *
  58  * EXAMPLE:     For simple front compression with no bigram encoding,
  59  *              if the input is...              then the output is...
  60  *
  61  *              /usr/src                         0 /usr/src
  62  *              /usr/src/cmd/aardvark.c          8 /cmd/aardvark.c
  63  *              /usr/src/cmd/armadillo.c        14 armadillo.c
  64  *              /usr/tmp/zoo                     5 tmp/zoo
  65  *
  66  *      The codes are:
  67  *
  68  *      0-28    likeliest differential counts + offset to make nonnegative
  69  *      30      switch code for out-of-range count to follow in next word
  70  *      31      an 8 bit char followed
  71  *      128-255 bigram codes (128 most common, as determined by 'updatedb')
  72  *      32-127  single character (printable) ascii residue (ie, literal)
  73  *
  74  * The locate database store any character except newline ('\n')
  75  * and NUL ('\0'). The 8-bit character support don't wast extra
  76  * space until you have characters in file names less than 32
  77  * or greather than 127.
  78  *
  79  *
  80  * SEE ALSO:    updatedb.sh, ../bigram/locate.bigram.c
  81  *
  82  * AUTHOR:      James A. Woods, Informatics General Corp.,
  83  *              NASA Ames Research Center, 10/82
  84  *              8-bit file names characters:
  85  *                      Wolfram Schneider, Berlin September 1996
  86  */
  87
  88 #include <sys/param.h>
  89 #include <err.h>
  90 #include <errno.h>
  91 #include <stdlib.h>
  92 #include <string.h>
  93 #include <stdio.h>
  94 #include <unistd.h>
  95 #include "locate.h"
  96
  97 #define BGBUFSIZE       (NBG * 2)       /* size of bigram buffer */
  98
  99 u_char buf1[MAXPATHLEN] = " ";
 100 u_char buf2[MAXPATHLEN];
 101 u_char bigrams[BGBUFSIZE + 1] = { 0 };
 102
 103 #define LOOKUP 1 /* use a lookup array instead a function, 3x faster */
 104
 105 #ifdef LOOKUP
 106 #define BGINDEX(x) (big[(u_char)*x][(u_char)*(x + 1)])
 107 typedef short bg_t;
 108 bg_t big[UCHAR_MAX + 1][UCHAR_MAX + 1];
 109 #else
 110 #define BGINDEX(x) bgindex(x)
 111 typedef int bg_t;
 112 int     bgindex(char *);
 113 #endif /* LOOKUP */
 114
 115
 116 void    usage(void);
 117
 118 int
 119 main(argc, argv)
 120         int argc;
 121         char *argv[];
 122 {
 123         u_char *cp, *oldpath, *path;
 124         int ch, code, count, diffcount, oldcount;
 125         FILE *fp;
 126         int i, j;
 127
 128         while ((ch = getopt(argc, argv, "")) != -1)
 129                 switch(ch) {
 130                 default:
 131                         usage();
 132                 }
 133         argc -= optind;
 134         argv += optind;
 135
 136         if (argc != 1)
 137                 usage();
 138
 139         if ((fp = fopen(argv[0], "r")) == NULL)
 140                 err(1, "%s", argv[0]);
 141
 142         /* First copy bigram array to stdout. */
 143         (void)fgets(bigrams, BGBUFSIZE + 1, fp);
 144
 145         if (fwrite(bigrams, 1, BGBUFSIZE, stdout) != BGBUFSIZE)
 146                 err(1, "stdout");
 147         (void)fclose(fp);
 148
 149 #ifdef LOOKUP
 150         /* init lookup table */
 151         for (i = 0; i < UCHAR_MAX + 1; i++)
 152                 for (j = 0; j < UCHAR_MAX + 1; j++)
 153                         big[i][j] = (bg_t)-1;
 154
 155         for (cp = bigrams, i = 0; *cp != '\0'; i += 2, cp += 2)
 156                 big[(u_char)*cp][(u_char)*(cp + 1)] = (bg_t)i;
 157
 158 #endif /* LOOKUP */
 159
 160         oldpath = buf1;
 161         path = buf2;
 162         oldcount = 0;
 163
 164         while (fgets(path, sizeof(buf2), stdin) != NULL) {
 165
 166                 /* skip empty lines */
 167                 if (*path == '\n')
 168                         continue;
 169
 170                 /* remove newline */
 171                 for (cp = path; *cp != '\0'; cp++) {
 172 #ifndef LOCATE_CHAR30
 173                         /* old locate implementations core'd for char 30 */
 174                         if (*cp == SWITCH)
 175                                 *cp = '?';
 176                         else
 177 #endif /* !LOCATE_CHAR30 */
 178
 179                         /* chop newline */
 180                         if (*cp == '\n')
 181                                 *cp = '\0';
 182                 }
 183
 184                 /* Skip longest common prefix. */
 185                 for (cp = path; *cp == *oldpath; cp++, oldpath++)
 186                         if (*cp == '\0')
 187                                 break;
 188
 189                 count = cp - path;
 190                 diffcount = count - oldcount + OFFSET;
 191                 oldcount = count;
 192                 if (diffcount < 0 || diffcount > 2 * OFFSET) {
 193                         if (putchar(SWITCH) == EOF ||
 194                             putw(diffcount, stdout) == EOF)
 195                                 err(1, "stdout");
 196                 } else
 197                         if (putchar(diffcount) == EOF)
 198                                 err(1, "stdout");
 199
 200                 while (*cp != '\0') {
 201                         /* print *two* characters */
 202
 203                         if ((code = BGINDEX(cp)) != (bg_t)-1) {
 204                                 /*
 205                                  * print *one* as bigram
 206                                  * Found, so mark byte with
 207                                  *  parity bit.
 208                                  */
 209                                 if (putchar((code / 2) | PARITY) == EOF)
 210                                         err(1, "stdout");
 211                                 cp += 2;
 212                         }
 213
 214                         else {
 215                                 for (i = 0; i < 2; i++) {
 216                                         if (*cp == '\0')
 217                                                 break;
 218
 219                                         /* print umlauts in file names */
 220                                         if (*cp < ASCII_MIN ||
 221                                             *cp > ASCII_MAX) {
 222                                                 if (putchar(UMLAUT) == EOF ||
 223                                                     putchar(*cp++) == EOF)
 224                                                         err(1, "stdout");
 225                                         }
 226
 227                                         else {
 228                                                 /* normal character */
 229                                                 if(putchar(*cp++) == EOF)
 230                                                         err(1, "stdout");
 231                                         }
 232                                 }
 233
 234                         }
 235                 }
 236
 237                 if (path == buf1) {             /* swap pointers */
 238                         path = buf2;
 239                         oldpath = buf1;
 240                 } else {
 241                         path = buf1;
 242                         oldpath = buf2;
 243                 }
 244         }
 245         /* Non-zero status if there were errors */
 246         if (fflush(stdout) != 0 || ferror(stdout))
 247                 exit(1);
 248         exit(0);
 249 }
 250
 251 #ifndef LOOKUP
 252 int
 253 bgindex(bg)                     /* Return location of bg in bigrams or -1. */
 254         char *bg;
 255 {
 256         char bg0, bg1, *p;
 257
 258         bg0 = bg[0];
 259         bg1 = bg[1];
 260         for (p = bigrams; *p != NULL; p++)
 261                 if (*p++ == bg0 && *p == bg1)
 262                         break;
 263         return (*p == NULL ? -1 : (--p - bigrams));
 264 }
 265 #endif /* !LOOKUP */
 266
 267 void
 268 usage()
 269 {
 270         (void)fprintf(stderr,
 271             "usage: locate.code common_bigrams < list > squozen_list\n");
 272         exit(1);
 273 }