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