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

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