locate/frcode.c

   1 /* frcode -- front-compress a sorted list
   2    Copyright (C) 1994,2005,2006,2007 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  17    USA.
  18 */
  19
  20 /* Usage: frcode < sorted-list > compressed-list
  21
  22    Uses front compression (also known as incremental encoding);
  23    see ";login:", March 1983, p. 8.
  24
  25    The input is a sorted list of NUL-terminated strings (or
  26    newline-terminated if the -0 option is not given).
  27
  28    The output entries are in the same order as the input; each entry
  29    consists of a signed offset-differential count byte (the additional
  30    number of characters of prefix of the preceding entry to use beyond
  31    the number that the preceding entry is using of its predecessor),
  32    followed by a null-terminated ASCII remainder.
  33
  34    If the offset-differential count is larger than can be stored
  35    in a byte (+/-127), the byte has the value LOCATEDB_ESCAPE
  36    and the count follows in a 2-byte word, with the high byte first
  37    (network byte order).
  38
  39    Example:
  40
  41    Input, with NULs changed to newlines:
  42    /usr/src
  43    /usr/src/cmd/aardvark.c
  44    /usr/src/cmd/armadillo.c
  45    /usr/tmp/zoo
  46
  47    Length of the longest prefix of the preceding entry to share:
  48    0 /usr/src
  49    8 /cmd/aardvark.c
  50    14 rmadillo.c
  51    5 tmp/zoo
  52
  53    Output, with NULs changed to newlines and count bytes made printable:
  54    0 LOCATE02
  55    0 /usr/src
  56    8 /cmd/aardvark.c
  57    6 rmadillo.c
  58    -9 tmp/zoo
  59
  60    (6 = 14 - 8, and -9 = 5 - 14)
  61
  62    Written by James A. Woods <jwoods@adobe.com>.
  63    Modified by David MacKenzie <djm@gnu.org>.
  64    Modified by James Youngman <jay@gnu.org>.
  65 */
  66
  67 #include <config.h>
  68
  69
  70 #include <stdio.h>
  71 #include <limits.h>
  72 #include <assert.h>
  73 #include <errno.h>
  74 #include <sys/types.h>
  75 #include <stdbool.h>
  76
  77 #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  78 #include <string.h>
  79 #else
  80 #include <strings.h>
  81 #endif
  82
  83 #ifdef STDC_HEADERS
  84 #include <stdlib.h>
  85 #endif
  86
  87 #if ENABLE_NLS
  88 # include <libintl.h>
  89 # define _(Text) gettext (Text)
  90 #else
  91 # define _(Text) Text
  92 #define textdomain(Domain)
  93 #define bindtextdomain(Package, Directory)
  94 #endif
  95 #ifdef gettext_noop
  96 # define N_(String) gettext_noop (String)
  97 #else
  98 /* We used to use (String) instead of just String, but apparently ISO C
  99  * doesn't allow this (at least, that's what HP said when someone reported
 100  * this as a compiler bug).  This is HP case number 1205608192.  See
 101  * also http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11250 (which references
 102  * ANSI 3.5.7p14-15).  The Intel icc compiler also rejects constructs
 103  * like: static const char buf[] = ("string");
 104  */
 105 # define N_(String) String
 106 #endif
 107
 108
 109 #include "locatedb.h"
 110 #include <getline.h>
 111 #include <getopt.h>
 112 #include "error.h"
 113 #include "closeout.h"
 114
 115 char *xmalloc PARAMS((size_t));
 116
 117 /* The name this program was run with.  */
 118 char *program_name;
 119
 120 /* Write out a 16-bit int, high byte first (network byte order).
 121  * Return true iff all went well.
 122  */
 123 static int
 124 put_short (int c, FILE *fp)
 125 {
 126   /* XXX: The value of c may be negative.  ANSI C 1989 (section 6.3.7)
 127    * indicates that the result of shifting a negative value right is
 128    * implementation defined.
 129    */
 130   assert(c <= SHRT_MAX);
 131   assert(c >= SHRT_MIN);
 132   return (putc (c >> 8, fp) != EOF) && (putc (c, fp) != EOF);
 133 }
 134
 135 /* Return the length of the longest common prefix of strings S1 and S2. */
 136
 137 static int
 138 prefix_length (char *s1, char *s2)
 139 {
 140   register char *start;
 141   int limit = INT_MAX;
 142   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
 143     {
 144       /* Don't emit a prefix length that will not fit into
 145        * our return type.
 146        */
 147       if (0 == --limit)
 148         break;
 149     }
 150   return s1 - start;
 151 }
 152
 153 static struct option const longopts[] =
 154 {
 155   {"help", no_argument, NULL, 'h'},
 156   {"version", no_argument, NULL, 'v'},
 157   {"null", no_argument, NULL, '0'},
 158   {NULL, no_argument, NULL, 0}
 159 };
 160
 161 extern char *version_string;
 162
 163 /* The name this program was run with. */
 164 char *program_name;
 165
 166
 167 static void
 168 usage (FILE *stream)
 169 {
 170   fprintf (stream,
 171            _("Usage: %s [-0 | --null] [--version] [--help]\n"),
 172            program_name);
 173   fputs (_("\nReport bugs to <bug-findutils@gnu.org>.\n"), stream);
 174 }
 175
 176 static long
 177 get_seclevel(char *s)
 178 {
 179   long result;
 180   char *p;
 181
 182   /* Reset errno in oreder to be able to distinguish LONG_MAX/LONG_MIN
 183    * from values whichare actually out of range
 184    */
 185   errno = 0;
 186
 187   result = strtol(s, &p, 10);
 188   if ((0==result) && (p == optarg))
 189     {
 190       error(1, 0, _("You need to specify a security level as a decimal integer."));
 191       /*NOTREACHED*/
 192       return -1;
 193     }
 194   else if ((LONG_MIN==result || LONG_MAX==result) && errno)
 195
 196     {
 197       error(1, 0, _("Security level %s is outside the convertible range."), s);
 198       /*NOTREACHED*/
 199       return -1;
 200     }
 201   else if (*p)
 202     {
 203       /* Some suffix exists */
 204       error(1, 0, _("Security level %s has unexpected suffix %s."), s, p);
 205       /*NOTREACHED*/
 206       return -1;
 207     }
 208   else
 209     {
 210       return result;
 211     }
 212 }
 213
 214 static void
 215 outerr(void)
 216 {
 217   /* Issue the same error message as closeout() would. */
 218   error(1, errno, _("write error"));
 219 }
 220
 221 int
 222 main (int argc, char **argv)
 223 {
 224   char *path;                   /* The current input entry.  */
 225   char *oldpath;                /* The previous input entry.  */
 226   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 227   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 228   int line_len;                 /* Length of input line.  */
 229   int delimiter = '\n';
 230   int optc;
 231   int slocate_compat = 0;
 232   long slocate_seclevel = 0L;
 233
 234   program_name = argv[0];
 235   if (!program_name)
 236     program_name = "frcode";
 237   atexit (close_stdout);
 238
 239   pathsize = oldpathsize = 1026; /* Increased as necessary by getline.  */
 240   path = xmalloc (pathsize);
 241   oldpath = xmalloc (oldpathsize);
 242
 243   oldpath[0] = 0;
 244   oldcount = 0;
 245
 246
 247   while ((optc = getopt_long (argc, argv, "hv0S:", longopts, (int *) 0)) != -1)
 248     switch (optc)
 249       {
 250       case '0':
 251         delimiter = 0;
 252         break;
 253
 254       case 'S':
 255         slocate_compat = 1;
 256         slocate_seclevel = get_seclevel(optarg);
 257         if (slocate_seclevel < 0 || slocate_seclevel > 1)
 258           {
 259             error(1, 0,
 260                   _("slocate security level %ld is unsupported."),
 261                   slocate_seclevel);
 262           }
 263         break;
 264
 265       case 'h':
 266         usage (stdout);
 267         return 0;
 268
 269       case 'v':
 270         printf (_("GNU locate version %s\n"), version_string);
 271         return 0;
 272
 273       default:
 274         usage (stderr);
 275         return 1;
 276       }
 277
 278   /* We expect to have no arguments. */
 279   if (optind != argc)
 280     {
 281       usage (stderr);
 282       return 1;
 283     }
 284
 285
 286   if (slocate_compat)
 287     {
 288       fputc(slocate_seclevel ? '1' : '0', stdout);
 289       fputc(0, stdout);
 290
 291     }
 292   else
 293     {
 294       /* GNU LOCATE02 format */
 295       if (fwrite (LOCATEDB_MAGIC, 1, sizeof (LOCATEDB_MAGIC), stdout)
 296           != sizeof(LOCATEDB_MAGIC))
 297         {
 298           error(1, errno, _("Failed to write to standard output"));
 299         }
 300     }
 301
 302
 303   while ((line_len = getdelim (&path, &pathsize, delimiter, stdin)) > 0)
 304     {
 305       path[line_len - 1] = '\0'; /* FIXME temporary: nuke the newline.  */
 306
 307       count = prefix_length (oldpath, path);
 308       diffcount = count - oldcount;
 309       if ( (diffcount > SHRT_MAX) || (diffcount < SHRT_MIN) )
 310         {
 311           /* We do this to prevent overflow of the value we
 312            * write with put_short()
 313            */
 314           count = 0;
 315           diffcount = (-oldcount);
 316         }
 317       oldcount = count;
 318
 319       if (slocate_compat)
 320         {
 321           /* Emit no count for the first pathname. */
 322           slocate_compat = 0;
 323         }
 324       else
 325         {
 326           /* If the difference is small, it fits in one byte;
 327              otherwise, two bytes plus a marker noting that fact.  */
 328           if (diffcount < LOCATEDB_ONEBYTE_MIN
 329               || diffcount > LOCATEDB_ONEBYTE_MAX)
 330             {
 331               if (EOF == putc (LOCATEDB_ESCAPE, stdout))
 332                 outerr();
 333               if (!put_short (diffcount, stdout))
 334                 outerr();
 335             }
 336           else
 337             {
 338               if (EOF == putc (diffcount, stdout))
 339                 outerr();
 340             }
 341         }
 342
 343       if ( (EOF == fputs (path + count, stdout))
 344            || (EOF == putc ('\0', stdout)))
 345         {
 346           outerr();
 347         }
 348
 349       if (1)
 350         {
 351           /* Swap path and oldpath and their sizes.  */
 352           char *tmppath = oldpath;
 353           size_t tmppathsize = oldpathsize;
 354           oldpath = path;
 355           oldpathsize = pathsize;
 356           path = tmppath;
 357           pathsize = tmppathsize;
 358         }
 359     }
 360
 361   free (path);
 362   free (oldpath);
 363
 364   return 0;
 365 }