locate/code.c

   1 /* code -- bigram- and front-encode filenames for locate
   2    Copyright (C) 1994, 2005, 2007, 2008, 2010 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 3 of the License, or
   7    (at your option) 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, see <http://www.gnu.org/licenses/>.
  16 */
  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.org>.  */
  45
  46 #include <config.h>
  47 #include <stdio.h>
  48 #include <sys/types.h>
  49 #include <string.h>
  50 #include <errno.h>
  51 #include <stdbool.h>
  52
  53
  54 #ifdef STDC_HEADERS
  55 #include <stdlib.h>
  56 #endif
  57
  58 #if ENABLE_NLS
  59 # include <libintl.h>
  60 # define _(Text) gettext (Text)
  61 #else
  62 # define _(Text) Text
  63 #define textdomain(Domain)
  64 #define bindtextdomain(Package, Directory)
  65 #endif
  66 #ifdef gettext_noop
  67 # define N_(String) gettext_noop (String)
  68 #else
  69 /* See locate.c for explanation as to why not use (String) */
  70 # define N_(String) String
  71 #endif
  72
  73 #include "locatedb.h"
  74 #include "closeout.h"
  75 #include "xalloc.h"
  76 #include "gnulib-version.h"
  77 #include "progname.h"
  78 #include "error.h"
  79 #include "findutils-version.h"
  80
  81 #ifndef ATTRIBUTE_NORETURN
  82 # define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
  83 #endif
  84
  85
  86 /* The name this program was run with.  */
  87 extern const char *program_name;
  88
  89 /* The 128 most common bigrams in the file list, padded with NULs
  90    if there are fewer.  */
  91 static char bigrams[257] = {0};
  92
  93 /* Return the offset of PATTERN in STRING, or -1 if not found. */
  94
  95 static int
  96 strindex (char *string, char *pattern)
  97 {
  98   register char *s;
  99
 100   for (s = string; *s != '\0'; s++)
 101     /* Fast first char check. */
 102     if (*s == *pattern)
 103       {
 104         register char *p2 = pattern + 1, *s2 = s + 1;
 105         while (*p2 != '\0' && *p2 == *s2)
 106           p2++, s2++;
 107         if (*p2 == '\0')
 108           return s2 - strlen (pattern) - string;
 109       }
 110   return -1;
 111 }
 112
 113 /* Return the length of the longest common prefix of strings S1 and S2. */
 114
 115 static int
 116 prefix_length (char *s1, char *s2)
 117 {
 118   register char *start;
 119
 120   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
 121     ;
 122   return s1 - start;
 123 }
 124
 125 extern char *version_string;
 126
 127 static void
 128 usage (FILE *stream)
 129 {
 130   fprintf (stream, _("\
 131 Usage: %s [--version | --help]\n\
 132 or     %s most_common_bigrams < file-list > locate-database\n"),
 133            program_name, program_name);
 134   fputs (_("\nReport bugs to <bug-findutils@gnu.org>.\n"), stream);
 135 }
 136
 137
 138 static void inerr (const char *filename) ATTRIBUTE_NORETURN;
 139 static void outerr (void)                 ATTRIBUTE_NORETURN;
 140
 141 static void
 142 inerr (const char *filename)
 143 {
 144   error (EXIT_FAILURE, errno, "%s", filename);
 145   /*NOTREACHED*/
 146   abort ();
 147 }
 148
 149 static void
 150 outerr (void)
 151 {
 152   error (EXIT_FAILURE, errno, _("write error"));
 153   /*NOTREACHED*/
 154   abort ();
 155 }
 156
 157
 158 int
 159 main (int argc, char **argv)
 160 {
 161   char *path;                   /* The current input entry.  */
 162   char *oldpath;                /* The previous input entry.  */
 163   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 164   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 165   char bigram[3];               /* Bigram to search for in table.  */
 166   int code;                     /* Index of `bigram' in bigrams table.  */
 167   FILE *fp;                     /* Most common bigrams file.  */
 168   int line_len;                 /* Length of input line.  */
 169
 170   set_program_name (argv[0]);
 171   atexit (close_stdout);
 172
 173   bigram[2] = '\0';
 174
 175   if (argc != 2)
 176     {
 177       usage (stderr);
 178       return 2;
 179     }
 180
 181   if (0 == strcmp (argv[1], "--help"))
 182     {
 183       usage (stdout);
 184       return 0;
 185     }
 186   else if (0 == strcmp (argv[1], "--version"))
 187     {
 188       display_findutils_version ("code");
 189       return 0;
 190     }
 191
 192   fp = fopen (argv[1], "r");
 193   if (fp == NULL)
 194     {
 195       fprintf (stderr, "%s: ", argv[0]);
 196       perror (argv[1]);
 197       return 1;
 198     }
 199
 200   pathsize = oldpathsize = 1026; /* Increased as necessary by getline.  */
 201   path = xmalloc (pathsize);
 202   oldpath = xmalloc (oldpathsize);
 203
 204   /* Set to empty string, to force the first prefix count to 0.  */
 205   oldpath[0] = '\0';
 206   oldcount = 0;
 207
 208   /* Copy the list of most common bigrams to the output,
 209      padding with NULs if there are <128 of them.  */
 210   if (NULL == fgets (bigrams, 257, fp))
 211     inerr (argv[1]);
 212
 213   if (256 != fwrite (bigrams, 1, 256, stdout))
 214      outerr ();
 215
 216   if (EOF == fclose (fp))
 217      inerr (argv[1]);
 218
 219   while ((line_len = getline (&path, &pathsize, stdin)) > 0)
 220     {
 221       char *pp;
 222
 223       path[line_len - 1] = '\0'; /* Remove newline. */
 224
 225       /* Squelch unprintable chars in path so as not to botch decoding.  */
 226       for (pp = path; *pp != '\0'; pp++)
 227         {
 228           if (!(*pp >= 040 && *pp < 0177))
 229             *pp = '?';
 230         }
 231
 232       count = prefix_length (oldpath, path);
 233       diffcount = count - oldcount;
 234       oldcount = count;
 235       /* If the difference is small, it fits in one byte;
 236          otherwise, two bytes plus a marker noting that fact.  */
 237       if (diffcount < -LOCATEDB_OLD_OFFSET || diffcount > LOCATEDB_OLD_OFFSET)
 238         {
 239           if (EOF ==- putc (LOCATEDB_OLD_ESCAPE, stdout))
 240             outerr ();
 241
 242           if (!putword (stdout,
 243                         diffcount+LOCATEDB_OLD_OFFSET,
 244                         GetwordEndianStateNative))
 245             outerr ();
 246         }
 247       else
 248         {
 249           if (EOF == putc (diffcount + LOCATEDB_OLD_OFFSET, stdout))
 250             outerr ();
 251         }
 252
 253       /* Look for bigrams in the remainder of the path.  */
 254       for (pp = path + count; *pp != '\0'; pp += 2)
 255         {
 256           if (pp[1] == '\0')
 257             {
 258               /* No bigram is possible; only one char is left.  */
 259               putchar (*pp);
 260               break;
 261             }
 262           bigram[0] = *pp;
 263           bigram[1] = pp[1];
 264           /* Linear search for specific bigram in string table. */
 265           code = strindex (bigrams, bigram);
 266           if (code % 2 == 0)
 267             putchar ((code / 2) | 0200); /* It's a common bigram.  */
 268           else
 269             fputs (bigram, stdout); /* Write the text as printable ASCII.  */
 270         }
 271
 272       {
 273         /* Swap path and oldpath and their sizes.  */
 274         char *tmppath = oldpath;
 275         size_t tmppathsize = oldpathsize;
 276         oldpath = path;
 277         oldpathsize = pathsize;
 278         path = tmppath;
 279         pathsize = tmppathsize;
 280       }
 281     }
 282
 283   free (path);
 284   free (oldpath);
 285
 286   return 0;
 287 }