locate/frcode.c

   1 /* frcode -- front-compress a sorted list
   2    Copyright (C) 1994 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.
  26    (FIXME newline-terminated, until we figure out how to sort
  27    NUL-terminated strings.)
  28
  29    The output entries are in the same order as the input;
  30    each entry consists of an offset-differential count byte
  31    (the additional number of characters of prefix of the preceding entry to
  32    use beyond the number that the preceding entry is using of its predecessor),
  33    followed by a null-terminated ASCII remainder.
  34
  35    If the offset-differential count is larger than can be stored
  36    in a byte (+/-127), the byte has the value LOCATEDB_ESCAPE
  37    and the count follows in a 2-byte word, with the high byte first
  38    (network byte order).
  39
  40    Example:
  41
  42    Input, with NULs changed to newlines:
  43    /usr/src
  44    /usr/src/cmd/aardvark.c
  45    /usr/src/cmd/armadillo.c
  46    /usr/tmp/zoo
  47
  48    Length of the longest prefix of the preceding entry to share:
  49    0 /usr/src
  50    8 /cmd/aardvark.c
  51    14 rmadillo.c
  52    5 tmp/zoo
  53
  54    Output, with NULs changed to newlines and count bytes made printable:
  55    0 LOCATE02
  56    0 /usr/src
  57    8 /cmd/aardvark.c
  58    6 rmadillo.c
  59    -9 tmp/zoo
  60
  61    (6 = 14 - 8, and -9 = 5 - 14)
  62
  63    Written by James A. Woods <jwoods@adobe.com>.
  64    Modified by David MacKenzie <djm@gnu.org>.  */
  65
  66 #include <config.h>
  67 #include <stdio.h>
  68 #include <limits.h>
  69 #include <assert.h>
  70 #include <sys/types.h>
  71
  72 #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  73 #include <string.h>
  74 #else
  75 #include <strings.h>
  76 #endif
  77
  78 #ifdef STDC_HEADERS
  79 #include <stdlib.h>
  80 #endif
  81
  82 #if ENABLE_NLS
  83 # include <libintl.h>
  84 # define _(Text) gettext (Text)
  85 #else
  86 # define _(Text) Text
  87 #define textdomain(Domain)
  88 #define bindtextdomain(Package, Directory)
  89 #endif
  90 #ifdef gettext_noop
  91 # define N_(String) gettext_noop (String)
  92 #else
  93 /* We used to use (String) instead of just String, but apparentl;y ISO C
  94  * doesn't allow this (at least, that's what HP said when someone reported
  95  * this as a compiler bug).  This is HP case number 1205608192.  See
  96  * also http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11250 (which references
  97  * ANSI 3.5.7p14-15).  The Intel icc compiler also rejects constructs
  98  * like: static const char buf[] = ("string");
  99  */
 100 # define N_(String) String
 101 #endif
 102
 103
 104 #include "locatedb.h"
 105 #include <getline.h>
 106 #include <getopt.h>
 107 #include "closeout.h"
 108
 109 char *xmalloc PARAMS((size_t));
 110
 111 /* The name this program was run with.  */
 112 char *program_name;
 113
 114 /* Write out a 16-bit int, high byte first (network byte order).  */
 115
 116 static void
 117 put_short (int c, FILE *fp)
 118 {
 119   /* XXX: The value may be negative, but I think ISO C doesn't
 120    * guarantee the assumptions we're making here will hold.
 121    */
 122   assert(c <= SHRT_MAX);
 123   assert(c >= SHRT_MIN);
 124   putc (c >> 8, fp);
 125   putc (c, fp);
 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 /* The name this program was run with. */
 157 char *program_name;
 158
 159
 160 static void
 161 usage (FILE *stream)
 162 {
 163   fprintf (stream,
 164            _("Usage: %s [-0 | --null] [--version] [--help]\n"),
 165            program_name);
 166   fputs (_("\nReport bugs to <bug-findutils@gnu.org>.\n"), stream);
 167 }
 168
 169
 170 int
 171 main (int argc, char **argv)
 172 {
 173   char *path;                   /* The current input entry.  */
 174   char *oldpath;                /* The previous input entry.  */
 175   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 176   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 177   int line_len;                 /* Length of input line.  */
 178   int delimiter = '\n';
 179   int optc;
 180
 181   program_name = argv[0];
 182   atexit (close_stdout);
 183
 184   pathsize = oldpathsize = 1026; /* Increased as necessary by getline.  */
 185   path = xmalloc (pathsize);
 186   oldpath = xmalloc (oldpathsize);
 187
 188   oldpath[0] = 0;
 189   oldcount = 0;
 190
 191
 192   while ((optc = getopt_long (argc, argv, "hv0", longopts, (int *) 0)) != -1)
 193     switch (optc)
 194       {
 195       case '0':
 196         delimiter = 0;
 197         break;
 198
 199       case 'h':
 200         usage (stdout);
 201         return 0;
 202
 203       case 'v':
 204         printf (_("GNU locate version %s\n"), version_string);
 205         return 0;
 206
 207       default:
 208         usage (stderr);
 209         return 1;
 210       }
 211
 212   /* We expect to have no arguments. */
 213   if (optind != argc)
 214     {
 215       usage (stderr);
 216       return 1;
 217     }
 218
 219
 220
 221   fwrite (LOCATEDB_MAGIC, sizeof (LOCATEDB_MAGIC), 1, stdout);
 222
 223   while ((line_len = getdelim (&path, &pathsize, delimiter, stdin)) > 0)
 224     {
 225       path[line_len - 1] = '\0'; /* FIXME temporary: nuke the newline.  */
 226
 227       count = prefix_length (oldpath, path);
 228       diffcount = count - oldcount;
 229       if ( (diffcount > SHRT_MAX) || (diffcount < SHRT_MIN) )
 230         {
 231           /* We do this to prevent overflow of the value we
 232            * write with put_short()
 233            */
 234           count = 0;
 235           diffcount = (-oldcount);
 236         }
 237       oldcount = count;
 238
 239       /* If the difference is small, it fits in one byte;
 240          otherwise, two bytes plus a marker noting that fact.  */
 241       if (diffcount < LOCATEDB_ONEBYTE_MIN || diffcount > LOCATEDB_ONEBYTE_MAX)
 242         {
 243           putc (LOCATEDB_ESCAPE, stdout);
 244           put_short (diffcount, stdout);
 245         }
 246       else
 247         putc (diffcount, stdout);
 248
 249       fputs (path + count, stdout);
 250       putc ('\0', stdout);
 251
 252       {
 253         /* Swap path and oldpath and their sizes.  */
 254         char *tmppath = oldpath;
 255         size_t tmppathsize = oldpathsize;
 256         oldpath = path;
 257         oldpathsize = pathsize;
 258         path = tmppath;
 259         pathsize = tmppathsize;
 260       }
 261     }
 262
 263   free (path);
 264   free (oldpath);
 265
 266   return 0;
 267 }