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 #include <stdio.h>
  69 #include <limits.h>
  70 #include <assert.h>
  71 #include <errno.h>
  72 #include <sys/types.h>
  73
  74 #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  75 #include <string.h>
  76 #else
  77 #include <strings.h>
  78 #endif
  79
  80 #ifdef STDC_HEADERS
  81 #include <stdlib.h>
  82 #endif
  83
  84 #if ENABLE_NLS
  85 # include <libintl.h>
  86 # define _(Text) gettext (Text)
  87 #else
  88 # define _(Text) Text
  89 #define textdomain(Domain)
  90 #define bindtextdomain(Package, Directory)
  91 #endif
  92 #ifdef gettext_noop
  93 # define N_(String) gettext_noop (String)
  94 #else
  95 /* We used to use (String) instead of just String, but apparently ISO C
  96  * doesn't allow this (at least, that's what HP said when someone reported
  97  * this as a compiler bug).  This is HP case number 1205608192.  See
  98  * also http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11250 (which references
  99  * ANSI 3.5.7p14-15).  The Intel icc compiler also rejects constructs
 100  * like: static const char buf[] = ("string");
 101  */
 102 # define N_(String) String
 103 #endif
 104
 105
 106 #include "locatedb.h"
 107 #include <getline.h>
 108 #include <getopt.h>
 109 #include "error.h"
 110 #include "closeout.h"
 111
 112 char *xmalloc PARAMS((size_t));
 113
 114 /* The name this program was run with.  */
 115 char *program_name;
 116
 117 /* Write out a 16-bit int, high byte first (network byte order).
 118  * Return true iff all went well.
 119  */
 120 static int
 121 put_short (int c, FILE *fp)
 122 {
 123   /* XXX: The value of c may be negative.  ANSI C 1989 (section 6.3.7)
 124    * indicates that the result of shifting a negative value right is
 125    * implementation defined.
 126    */
 127   assert(c <= SHRT_MAX);
 128   assert(c >= SHRT_MIN);
 129   return (putc (c >> 8, fp) != EOF) && (putc (c, fp) != EOF);
 130 }
 131
 132 /* Return the length of the longest common prefix of strings S1 and S2. */
 133
 134 static int
 135 prefix_length (char *s1, char *s2)
 136 {
 137   register char *start;
 138   int limit = INT_MAX;
 139   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
 140     {
 141       /* Don't emit a prefix length that will not fit into
 142        * our return type.
 143        */
 144       if (0 == --limit)
 145         break;
 146     }
 147   return s1 - start;
 148 }
 149
 150 static struct option const longopts[] =
 151 {
 152   {"help", no_argument, NULL, 'h'},
 153   {"version", no_argument, NULL, 'v'},
 154   {"null", no_argument, NULL, '0'},
 155   {NULL, no_argument, NULL, 0}
 156 };
 157
 158 extern char *version_string;
 159
 160 /* The name this program was run with. */
 161 char *program_name;
 162
 163
 164 static void
 165 usage (FILE *stream)
 166 {
 167   fprintf (stream,
 168            _("Usage: %s [-0 | --null] [--version] [--help]\n"),
 169            program_name);
 170   fputs (_("\nReport bugs to <bug-findutils@gnu.org>.\n"), stream);
 171 }
 172
 173 static long
 174 get_seclevel(char *s)
 175 {
 176   long result;
 177   char *p;
 178
 179   /* Reset errno in oreder to be able to distinguish LONG_MAX/LONG_MIN
 180    * from values whichare actually out of range
 181    */
 182   errno = 0;
 183
 184   result = strtol(s, &p, 10);
 185   if ((0==result) && (p == optarg))
 186     {
 187       error(1, 0, _("You need to specify a security level as a decimal integer."));
 188       /*NOTREACHED*/
 189       return -1;
 190     }
 191   else if ((LONG_MIN==result || LONG_MAX==result) && errno)
 192
 193     {
 194       error(1, 0, _("Security level %s is outside the convertible range."), s);
 195       /*NOTREACHED*/
 196       return -1;
 197     }
 198   else if (*p)
 199     {
 200       /* Some suffix exists */
 201       error(1, 0, _("Security level %s has unexpected suffix %s."), s, p);
 202       /*NOTREACHED*/
 203       return -1;
 204     }
 205   else
 206     {
 207       return result;
 208     }
 209 }
 210
 211 static void
 212 outerr(void)
 213 {
 214   /* Issue the same error message as closeout() would. */
 215   error(1, errno, _("write error"));
 216 }
 217
 218 int
 219 main (int argc, char **argv)
 220 {
 221   char *path;                   /* The current input entry.  */
 222   char *oldpath;                /* The previous input entry.  */
 223   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 224   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 225   int line_len;                 /* Length of input line.  */
 226   int delimiter = '\n';
 227   int optc;
 228   int slocate_compat = 0;
 229   long slocate_seclevel = 0L;
 230
 231   program_name = argv[0];
 232   if (!program_name)
 233     program_name = "frcode";
 234   atexit (close_stdout);
 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(1, 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         printf (_("GNU locate version %s\n"), version_string);
 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(1, 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 }