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
 119 static void
 120 put_short (int c, FILE *fp)
 121 {
 122   /* XXX: The value of c may be negative.  ANSI C 1989 (section 6.3.7)
 123    * indicates that the result of shifting a negative value right is
 124    * implementation defined.
 125    */
 126   assert(c <= SHRT_MAX);
 127   assert(c >= SHRT_MIN);
 128   putc (c >> 8, fp);
 129   putc (c, fp);
 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
 212 int
 213 main (int argc, char **argv)
 214 {
 215   char *path;                   /* The current input entry.  */
 216   char *oldpath;                /* The previous input entry.  */
 217   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 218   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 219   int line_len;                 /* Length of input line.  */
 220   int delimiter = '\n';
 221   int optc;
 222   int slocate_compat = 0;
 223   long slocate_seclevel = 0L;
 224
 225   program_name = argv[0];
 226   if (!program_name)
 227     program_name = "frcode";
 228   atexit (close_stdout);
 229
 230   pathsize = oldpathsize = 1026; /* Increased as necessary by getline.  */
 231   path = xmalloc (pathsize);
 232   oldpath = xmalloc (oldpathsize);
 233
 234   oldpath[0] = 0;
 235   oldcount = 0;
 236
 237
 238   while ((optc = getopt_long (argc, argv, "hv0S:", longopts, (int *) 0)) != -1)
 239     switch (optc)
 240       {
 241       case '0':
 242         delimiter = 0;
 243         break;
 244
 245       case 'S':
 246         slocate_compat = 1;
 247         slocate_seclevel = get_seclevel(optarg);
 248         if (slocate_seclevel < 0 || slocate_seclevel > 1)
 249           {
 250             error(1, 0,
 251                   _("slocate security level %ld is unsupported."),
 252                   slocate_seclevel);
 253           }
 254         break;
 255
 256       case 'h':
 257         usage (stdout);
 258         return 0;
 259
 260       case 'v':
 261         printf (_("GNU locate version %s\n"), version_string);
 262         return 0;
 263
 264       default:
 265         usage (stderr);
 266         return 1;
 267       }
 268
 269   /* We expect to have no arguments. */
 270   if (optind != argc)
 271     {
 272       usage (stderr);
 273       return 1;
 274     }
 275
 276
 277   if (slocate_compat)
 278     {
 279       fputc(slocate_seclevel ? '1' : '0', stdout);
 280       fputc(0, stdout);
 281
 282     }
 283   else
 284     {
 285       /* GNU LOCATE02 format */
 286       fwrite (LOCATEDB_MAGIC, sizeof (LOCATEDB_MAGIC), 1, stdout);
 287     }
 288
 289
 290   while ((line_len = getdelim (&path, &pathsize, delimiter, stdin)) > 0)
 291     {
 292       path[line_len - 1] = '\0'; /* FIXME temporary: nuke the newline.  */
 293
 294       count = prefix_length (oldpath, path);
 295       diffcount = count - oldcount;
 296       if ( (diffcount > SHRT_MAX) || (diffcount < SHRT_MIN) )
 297         {
 298           /* We do this to prevent overflow of the value we
 299            * write with put_short()
 300            */
 301           count = 0;
 302           diffcount = (-oldcount);
 303         }
 304       oldcount = count;
 305
 306       if (slocate_compat)
 307         {
 308           /* Emit no count for the first pathname. */
 309           slocate_compat = 0;
 310         }
 311       else
 312         {
 313           /* If the difference is small, it fits in one byte;
 314              otherwise, two bytes plus a marker noting that fact.  */
 315           if (diffcount < LOCATEDB_ONEBYTE_MIN || diffcount > LOCATEDB_ONEBYTE_MAX)
 316             {
 317               putc (LOCATEDB_ESCAPE, stdout);
 318               put_short (diffcount, stdout);
 319             }
 320           else
 321             {
 322               putc (diffcount, stdout);
 323             }
 324         }
 325
 326       fputs (path + count, stdout);
 327       putc ('\0', stdout);
 328
 329       {
 330         /* Swap path and oldpath and their sizes.  */
 331         char *tmppath = oldpath;
 332         size_t tmppathsize = oldpathsize;
 333         oldpath = path;
 334         oldpathsize = pathsize;
 335         path = tmppath;
 336         pathsize = tmppathsize;
 337       }
 338     }
 339
 340   free (path);
 341   free (oldpath);
 342
 343   return 0;
 344 }