locate/code.c

   1 /* code -- bigram- and front-encode filenames for locate
   2    Copyright (C) 1994, 2005, 2007, 2008, 2010, 2011 Free Software
   3    Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation, either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 /* Compress a sorted list.
  20    Works with `find' to encode a filename database to save space
  21    and search time.
  22
  23    Usage:
  24
  25    bigram < file_list > bigrams
  26    process-bigrams > most_common_bigrams
  27    code most_common_bigrams < file_list > squeezed_list
  28
  29    Uses `front compression' (see ";login:", March 1983, p. 8).
  30    The output begins with the 128 most common bigrams.
  31    After that, the output format is, for each line,
  32    an offset (from the previous line) differential count byte
  33    followed by a (partially bigram-encoded) ASCII remainder.
  34    The output lines have no terminating byte; the start of the next line
  35    is indicated by its first byte having a value <= 30.
  36
  37    The encoding of the output bytes is:
  38
  39    0-28         likeliest differential counts + offset (14) to make nonnegative
  40    30           escape code for out-of-range count to follow in next halfword
  41    128-255      bigram codes (the 128 most common, as determined by `updatedb')
  42    32-127       single character (printable) ASCII remainder
  43
  44    Written by James A. Woods <jwoods@adobe.com>.
  45    Modified by David MacKenzie <djm@gnu.org>.  */
  46
  47 /* config.h should always be included first. */
  48 #include <config.h>
  49
  50 /* system headers. */
  51 #include <errno.h>
  52 #include <stdbool.h>
  53 #include <stdio.h>
  54 #include <stdlib.h>
  55 #include <string.h>
  56 #include <sys/types.h>
  57
  58 /* gnulib headers. */
  59 #include "closeout.h"
  60 #include "error.h"
  61 #include "gettext.h"
  62 #include "progname.h"
  63 #include "xalloc.h"
  64
  65 /* find headers. */
  66 #include "findutils-version.h"
  67 #include "locatedb.h"
  68
  69 #if ENABLE_NLS
  70 # include <libintl.h>
  71 # define _(Text) gettext (Text)
  72 #else
  73 # define _(Text) Text
  74 #define textdomain(Domain)
  75 #define bindtextdomain(Package, Directory)
  76 #endif
  77 #ifdef gettext_noop
  78 # define N_(String) gettext_noop (String)
  79 #else
  80 /* See locate.c for explanation as to why not use (String) */
  81 # define N_(String) String
  82 #endif
  83
  84
  85 #ifndef ATTRIBUTE_NORETURN
  86 # define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
  87 #endif
  88
  89
  90 /* The 128 most common bigrams in the file list, padded with NULs
  91    if there are fewer.  */
  92 static char bigrams[257] = {0};
  93
  94 /* Return the offset of PATTERN in STRING, or -1 if not found. */
  95
  96 static int
  97 strindex (char *string, char *pattern)
  98 {
  99   register char *s;
 100
 101   for (s = string; *s != '\0'; s++)
 102     /* Fast first char check. */
 103     if (*s == *pattern)
 104       {
 105         register char *p2 = pattern + 1, *s2 = s + 1;
 106         while (*p2 != '\0' && *p2 == *s2)
 107           p2++, s2++;
 108         if (*p2 == '\0')
 109           return s2 - strlen (pattern) - string;
 110       }
 111   return -1;
 112 }
 113
 114 /* Return the length of the longest common prefix of strings S1 and S2. */
 115
 116 static int
 117 prefix_length (char *s1, char *s2)
 118 {
 119   register char *start;
 120
 121   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
 122     ;
 123   return s1 - start;
 124 }
 125
 126 extern char *version_string;
 127
 128 static void
 129 usage (FILE *stream)
 130 {
 131   fprintf (stream, _("\
 132 Usage: %s [--version | --help]\n\
 133 or     %s most_common_bigrams < file-list > locate-database\n"),
 134            program_name, program_name);
 135   fputs (_("\nReport bugs to <bug-findutils@gnu.org>.\n"), stream);
 136 }
 137
 138
 139 static void inerr (const char *filename) ATTRIBUTE_NORETURN;
 140 static void outerr (void)                 ATTRIBUTE_NORETURN;
 141
 142 static void
 143 inerr (const char *filename)
 144 {
 145   error (EXIT_FAILURE, errno, "%s", filename);
 146   /*NOTREACHED*/
 147   abort ();
 148 }
 149
 150 static void
 151 outerr (void)
 152 {
 153   error (EXIT_FAILURE, errno, _("write error"));
 154   /*NOTREACHED*/
 155   abort ();
 156 }
 157
 158
 159 int
 160 main (int argc, char **argv)
 161 {
 162   char *path;                   /* The current input entry.  */
 163   char *oldpath;                /* The previous input entry.  */
 164   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 165   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 166   char bigram[3];               /* Bigram to search for in table.  */
 167   int code;                     /* Index of `bigram' in bigrams table.  */
 168   FILE *fp;                     /* Most common bigrams file.  */
 169   int line_len;                 /* Length of input line.  */
 170
 171   set_program_name (argv[0]);
 172   if (atexit (close_stdout))
 173     {
 174       error (EXIT_FAILURE, errno, _("The atexit library function failed"));
 175     }
 176
 177   bigram[2] = '\0';
 178
 179   if (argc != 2)
 180     {
 181       usage (stderr);
 182       return 2;
 183     }
 184
 185   if (0 == strcmp (argv[1], "--help"))
 186     {
 187       usage (stdout);
 188       return 0;
 189     }
 190   else if (0 == strcmp (argv[1], "--version"))
 191     {
 192       display_findutils_version ("code");
 193       return 0;
 194     }
 195
 196   fp = fopen (argv[1], "r");
 197   if (fp == NULL)
 198     {
 199       fprintf (stderr, "%s: ", argv[0]);
 200       perror (argv[1]);
 201       return 1;
 202     }
 203
 204   pathsize = oldpathsize = 1026; /* Increased as necessary by getline.  */
 205   path = xmalloc (pathsize);
 206   oldpath = xmalloc (oldpathsize);
 207
 208   /* Set to empty string, to force the first prefix count to 0.  */
 209   oldpath[0] = '\0';
 210   oldcount = 0;
 211
 212   /* Copy the list of most common bigrams to the output,
 213      padding with NULs if there are <128 of them.  */
 214   if (NULL == fgets (bigrams, 257, fp))
 215     inerr (argv[1]);
 216
 217   if (256 != fwrite (bigrams, 1, 256, stdout))
 218      outerr ();
 219
 220   if (EOF == fclose (fp))
 221      inerr (argv[1]);
 222
 223   while ((line_len = getline (&path, &pathsize, stdin)) > 0)
 224     {
 225       char *pp;
 226
 227       path[line_len - 1] = '\0'; /* Remove newline. */
 228
 229       /* Squelch unprintable chars in path so as not to botch decoding.  */
 230       for (pp = path; *pp != '\0'; pp++)
 231         {
 232           if (!(*pp >= 040 && *pp < 0177))
 233             *pp = '?';
 234         }
 235
 236       count = prefix_length (oldpath, path);
 237       diffcount = count - oldcount;
 238       oldcount = count;
 239       /* If the difference is small, it fits in one byte;
 240          otherwise, two bytes plus a marker noting that fact.  */
 241       if (diffcount < -LOCATEDB_OLD_OFFSET || diffcount > LOCATEDB_OLD_OFFSET)
 242         {
 243           if (EOF ==- putc (LOCATEDB_OLD_ESCAPE, stdout))
 244             outerr ();
 245
 246           if (!putword (stdout,
 247                         diffcount+LOCATEDB_OLD_OFFSET,
 248                         GetwordEndianStateNative))
 249             outerr ();
 250         }
 251       else
 252         {
 253           if (EOF == putc (diffcount + LOCATEDB_OLD_OFFSET, stdout))
 254             outerr ();
 255         }
 256
 257       /* Look for bigrams in the remainder of the path.  */
 258       for (pp = path + count; *pp != '\0'; pp += 2)
 259         {
 260           if (pp[1] == '\0')
 261             {
 262               /* No bigram is possible; only one char is left.  */
 263               putchar (*pp);
 264               break;
 265             }
 266           bigram[0] = *pp;
 267           bigram[1] = pp[1];
 268           /* Linear search for specific bigram in string table. */
 269           code = strindex (bigrams, bigram);
 270           if (code % 2 == 0)
 271             putchar ((code / 2) | 0200); /* It's a common bigram.  */
 272           else
 273             fputs (bigram, stdout); /* Write the text as printable ASCII.  */
 274         }
 275
 276       {
 277         /* Swap path and oldpath and their sizes.  */
 278         char *tmppath = oldpath;
 279         size_t tmppathsize = oldpathsize;
 280         oldpath = path;
 281         oldpathsize = pathsize;
 282         path = tmppath;
 283         pathsize = tmppathsize;
 284       }
 285     }
 286
 287   free (path);
 288   free (oldpath);
 289
 290   return 0;
 291 }