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
 113 char *xmalloc PARAMS((size_t));
 114
 115 /* The name this program was run with.  */
 116 char *program_name;
 117
 118 /* Write out a 16-bit int, high byte first (network byte order).
 119  * Return true iff all went well.
 120  */
 121 static int
 122 put_short (int c, FILE *fp)
 123 {
 124   /* XXX: The value of c may be negative.  ANSI C 1989 (section 6.3.7)
 125    * indicates that the result of shifting a negative value right is
 126    * implementation defined.
 127    */
 128   assert (c <= SHRT_MAX);
 129   assert (c >= SHRT_MIN);
 130   return (putc (c >> 8, fp) != EOF) && (putc (c, fp) != EOF);
 131 }
 132
 133 /* Return the length of the longest common prefix of strings S1 and S2. */
 134
 135 static int
 136 prefix_length (char *s1, char *s2)
 137 {
 138   register char *start;
 139   int limit = INT_MAX;
 140   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
 141     {
 142       /* Don't emit a prefix length that will not fit into
 143        * our return type.
 144        */
 145       if (0 == --limit)
 146         break;
 147     }
 148   return s1 - start;
 149 }
 150
 151 static struct option const longopts[] =
 152 {
 153   {"help", no_argument, NULL, 'h'},
 154   {"version", no_argument, NULL, 'v'},
 155   {"null", no_argument, NULL, '0'},
 156   {NULL, no_argument, NULL, 0}
 157 };
 158
 159 extern char *version_string;
 160
 161 /* The name this program was run with. */
 162 char *program_name;
 163
 164
 165 static void
 166 usage (FILE *stream)
 167 {
 168   fprintf (stream,
 169            _("Usage: %s [-0 | --null] [--version] [--help]\n"),
 170            program_name);
 171   fputs (_("\nReport bugs to <bug-findutils@gnu.org>.\n"), stream);
 172 }
 173
 174 static long
 175 get_seclevel(char *s)
 176 {
 177   long result;
 178   char *p;
 179
 180   /* Reset errno in oreder to be able to distinguish LONG_MAX/LONG_MIN
 181    * from values whichare actually out of range
 182    */
 183   errno = 0;
 184
 185   result = strtol(s, &p, 10);
 186   if ((0==result) && (p == optarg))
 187     {
 188       error(1, 0, _("You need to specify a security level as a decimal integer."));
 189       /*NOTREACHED*/
 190       return -1;
 191     }
 192   else if ((LONG_MIN==result || LONG_MAX==result) && errno)
 193
 194     {
 195       error(1, 0, _("Security level %s is outside the convertible range."), s);
 196       /*NOTREACHED*/
 197       return -1;
 198     }
 199   else if (*p)
 200     {
 201       /* Some suffix exists */
 202       error(1, 0, _("Security level %s has unexpected suffix %s."), s, p);
 203       /*NOTREACHED*/
 204       return -1;
 205     }
 206   else
 207     {
 208       return result;
 209     }
 210 }
 211
 212 static void
 213 outerr(void)
 214 {
 215   /* Issue the same error message as closeout() would. */
 216   error(1, errno, _("write error"));
 217 }
 218
 219 int
 220 main (int argc, char **argv)
 221 {
 222   char *path;                   /* The current input entry.  */
 223   char *oldpath;                /* The previous input entry.  */
 224   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 225   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 226   int line_len;                 /* Length of input line.  */
 227   int delimiter = '\n';
 228   int optc;
 229   int slocate_compat = 0;
 230   long slocate_seclevel = 0L;
 231
 232   program_name = argv[0];
 233   if (!program_name)
 234     program_name = "frcode";
 235   atexit (close_stdout);
 236
 237   pathsize = oldpathsize = 1026; /* Increased as necessary by getline.  */
 238   path = xmalloc (pathsize);
 239   oldpath = xmalloc (oldpathsize);
 240
 241   oldpath[0] = 0;
 242   oldcount = 0;
 243
 244
 245   while ((optc = getopt_long (argc, argv, "hv0S:", longopts, (int *) 0)) != -1)
 246     switch (optc)
 247       {
 248       case '0':
 249         delimiter = 0;
 250         break;
 251
 252       case 'S':
 253         slocate_compat = 1;
 254         slocate_seclevel = get_seclevel(optarg);
 255         if (slocate_seclevel < 0 || slocate_seclevel > 1)
 256           {
 257             error(1, 0,
 258                   _("slocate security level %ld is unsupported."),
 259                   slocate_seclevel);
 260           }
 261         break;
 262
 263       case 'h':
 264         usage (stdout);
 265         return 0;
 266
 267       case 'v':
 268         printf (_("GNU locate version %s\n"), version_string);
 269         return 0;
 270
 271       default:
 272         usage (stderr);
 273         return 1;
 274       }
 275
 276   /* We expect to have no arguments. */
 277   if (optind != argc)
 278     {
 279       usage (stderr);
 280       return 1;
 281     }
 282
 283
 284   if (slocate_compat)
 285     {
 286       fputc(slocate_seclevel ? '1' : '0', stdout);
 287       fputc(0, stdout);
 288
 289     }
 290   else
 291     {
 292       /* GNU LOCATE02 format */
 293       if (fwrite (LOCATEDB_MAGIC, 1, sizeof (LOCATEDB_MAGIC), stdout)
 294           != sizeof(LOCATEDB_MAGIC))
 295         {
 296           error(1, errno, _("Failed to write to standard output"));
 297         }
 298     }
 299
 300
 301   while ((line_len = getdelim (&path, &pathsize, delimiter, stdin)) > 0)
 302     {
 303       path[line_len - 1] = '\0'; /* FIXME temporary: nuke the newline.  */
 304
 305       count = prefix_length (oldpath, path);
 306       diffcount = count - oldcount;
 307       if ( (diffcount > SHRT_MAX) || (diffcount < SHRT_MIN) )
 308         {
 309           /* We do this to prevent overflow of the value we
 310            * write with put_short()
 311            */
 312           count = 0;
 313           diffcount = (-oldcount);
 314         }
 315       oldcount = count;
 316
 317       if (slocate_compat)
 318         {
 319           /* Emit no count for the first pathname. */
 320           slocate_compat = 0;
 321         }
 322       else
 323         {
 324           /* If the difference is small, it fits in one byte;
 325              otherwise, two bytes plus a marker noting that fact.  */
 326           if (diffcount < LOCATEDB_ONEBYTE_MIN
 327               || diffcount > LOCATEDB_ONEBYTE_MAX)
 328             {
 329               if (EOF == putc (LOCATEDB_ESCAPE, stdout))
 330                 outerr();
 331               if (!put_short (diffcount, stdout))
 332                 outerr();
 333             }
 334           else
 335             {
 336               if (EOF == putc (diffcount, stdout))
 337                 outerr();
 338             }
 339         }
 340
 341       if ( (EOF == fputs (path + count, stdout))
 342            || (EOF == putc ('\0', stdout)))
 343         {
 344           outerr();
 345         }
 346
 347       if (1)
 348         {
 349           /* Swap path and oldpath and their sizes.  */
 350           char *tmppath = oldpath;
 351           size_t tmppathsize = oldpathsize;
 352           oldpath = path;
 353           oldpathsize = pathsize;
 354           path = tmppath;
 355           pathsize = tmppathsize;
 356         }
 357     }
 358
 359   free (path);
 360   free (oldpath);
 361
 362   return 0;
 363 }