locate/code.c

   1 /* code -- bigram- and front-encode filenames for locate
   2    Copyright (C) 1994 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 /* Compress a sorted list.
  19    Works with `find' to encode a filename database to save space
  20    and search time.
  21
  22    Usage:
  23
  24    bigram < file_list > bigrams
  25    process-bigrams > most_common_bigrams
  26    code most_common_bigrams < file_list > squeezed_list
  27
  28    Uses `front compression' (see ";login:", March 1983, p. 8).
  29    The output begins with the 128 most common bigrams.
  30    After that, the output format is, for each line,
  31    an offset (from the previous line) differential count byte
  32    followed by a (partially bigram-encoded) ASCII remainder.
  33    The output lines have no terminating byte; the start of the next line
  34    is indicated by its first byte having a value <= 30.
  35
  36    The encoding of the output bytes is:
  37
  38    0-28         likeliest differential counts + offset (14) to make nonnegative
  39    30           escape code for out-of-range count to follow in next halfword
  40    128-255      bigram codes (the 128 most common, as determined by `updatedb')
  41    32-127       single character (printable) ASCII remainder
  42
  43    Written by James A. Woods <jwoods@adobe.com>.
  44    Modified by David MacKenzie <djm@gnu.ai.mit.edu>.  */
  45
  46 #include <config.h>
  47 #include <stdio.h>
  48 #include <sys/types.h>
  49
  50 #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  51 #include <string.h>
  52 #else
  53 #include <strings.h>
  54 #endif
  55
  56 #ifdef STDC_HEADERS
  57 #include <stdlib.h>
  58 #endif
  59
  60 #include "locatedb.h"
  61
  62 char *xmalloc ();
  63
  64 /* The name this program was run with.  */
  65 char *program_name;
  66
  67 /* The 128 most common bigrams in the file list, padded with NULs
  68    if there are fewer.  */
  69 static char bigrams[257] = {0};
  70
  71 /* Return the offset of PATTERN in STRING, or -1 if not found. */
  72
  73 static int
  74 strindex (string, pattern)
  75      char *string, *pattern;
  76 {
  77   register char *s;
  78
  79   for (s = string; *s != '\0'; s++)
  80     /* Fast first char check. */
  81     if (*s == *pattern)
  82       {
  83         register char *p2 = pattern + 1, *s2 = s + 1;
  84         while (*p2 != '\0' && *p2 == *s2)
  85           p2++, s2++;
  86         if (*p2 == '\0')
  87           return s2 - strlen (pattern) - string;
  88       }
  89   return -1;
  90 }
  91
  92 /* Return the length of the longest common prefix of strings S1 and S2. */
  93
  94 static int
  95 prefix_length (s1, s2)
  96      char *s1, *s2;
  97 {
  98   register char *start;
  99
 100   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
 101     ;
 102   return s1 - start;
 103 }
 104
 105 void
 106 main (argc, argv)
 107      int argc;
 108      char **argv;
 109 {
 110   char *path;                   /* The current input entry.  */
 111   char *oldpath;                /* The previous input entry.  */
 112   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 113   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 114   char bigram[3];               /* Bigram to search for in table.  */
 115   int code;                     /* Index of `bigram' in bigrams table.  */
 116   FILE *fp;                     /* Most common bigrams file.  */
 117   int line_len;                 /* Length of input line.  */
 118
 119   program_name = argv[0];
 120
 121   bigram[2] = '\0';
 122
 123   if (argc != 2)
 124     {
 125       fprintf (stderr, "Usage: %s most_common_bigrams < list > coded_list\n",
 126                argv[0]);
 127       exit (2);
 128     }
 129
 130   fp = fopen (argv[1], "r");
 131   if (fp == NULL)
 132     {
 133       fprintf (stderr, "%s: ", argv[0]);
 134       perror (argv[1]);
 135       exit (1);
 136     }
 137
 138   pathsize = oldpathsize = 1026; /* Increased as necessary by getstr.  */
 139   path = xmalloc (pathsize);
 140   oldpath = xmalloc (oldpathsize);
 141
 142   /* Set to anything not starting with a slash, to force the first
 143      prefix count to 0.  */
 144   strcpy (oldpath, " ");
 145   oldcount = 0;
 146
 147   /* Copy the list of most common bigrams to the output,
 148      padding with NULs if there are <128 of them.  */
 149   fgets (bigrams, 257, fp);
 150   fwrite (bigrams, 1, 256, stdout);
 151   fclose (fp);
 152
 153   while ((line_len = getstr (&path, &pathsize, stdin, '\n', 0)) > 0)
 154     {
 155       char *pp;
 156
 157       path[line_len - 1] = '\0'; /* Remove newline. */
 158
 159       /* Squelch unprintable chars in path so as not to botch decoding.  */
 160       for (pp = path; *pp != '\0'; pp++)
 161         {
 162           *pp &= 0177;
 163           if (*pp < 040 || *pp == 0177)
 164             *pp = '?';
 165         }
 166
 167       count = prefix_length (oldpath, path);
 168       diffcount = count - oldcount;
 169       oldcount = count;
 170       /* If the difference is small, it fits in one byte;
 171          otherwise, two bytes plus a marker noting that fact.  */
 172       if (diffcount < -LOCATEDB_OLD_OFFSET || diffcount > LOCATEDB_OLD_OFFSET)
 173         {
 174           putc (LOCATEDB_OLD_ESCAPE, stdout);
 175           putw (diffcount + LOCATEDB_OLD_OFFSET, stdout);
 176         }
 177       else
 178         putc (diffcount + LOCATEDB_OLD_OFFSET, stdout);
 179
 180       /* Look for bigrams in the remainder of the path.  */
 181       for (pp = path + count; *pp != '\0'; pp += 2)
 182         {
 183           if (pp[1] == '\0')
 184             {
 185               /* No bigram is possible; only one char is left.  */
 186               putchar (*pp);
 187               break;
 188             }
 189           bigram[0] = *pp;
 190           bigram[1] = pp[1];
 191           /* Linear search for specific bigram in string table. */
 192           code = strindex (bigrams, bigram);
 193           if (code % 2 == 0)
 194             putchar ((code / 2) | 0200); /* It's a common bigram.  */
 195           else
 196             fputs (bigram, stdout); /* Write the text as printable ASCII.  */
 197         }
 198
 199       {
 200         /* Swap path and oldpath and their sizes.  */
 201         char *tmppath = oldpath;
 202         size_t tmppathsize = oldpathsize;
 203         oldpath = path;
 204         oldpathsize = pathsize;
 205         path = tmppath;
 206         pathsize = tmppathsize;
 207       }
 208     }
 209
 210   free (path);
 211   free (oldpath);
 212
 213   exit (0);
 214 }