locate/frcode.c

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