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