locate/frcode.c

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