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 <sys/types.h>
  69
  70 #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  71 #include <string.h>
  72 #else
  73 #include <strings.h>
  74 #endif
  75
  76 #ifdef STDC_HEADERS
  77 #include <stdlib.h>
  78 #endif
  79
  80 #if ENABLE_NLS
  81 # include <libintl.h>
  82 # define _(Text) gettext (Text)
  83 #else
  84 # define _(Text) Text
  85 #define textdomain(Domain)
  86 #define bindtextdomain(Package, Directory)
  87 #endif
  88 #ifdef gettext_noop
  89 # define N_(String) gettext_noop (String)
  90 #else
  91 /* We used to use (String) instead of just String, but apparentl;y ISO C
  92  * doesn't allow this (at least, that's what HP said when someone reported
  93  * this as a compiler bug).  This is HP case number 1205608192.  See
  94  * also http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11250 (which references
  95  * ANSI 3.5.7p14-15).  The Intel icc compiler also rejects constructs
  96  * like: static const char buf[] = ("string");
  97  */
  98 # define N_(String) String
  99 #endif
 100
 101
 102 #include "locatedb.h"
 103 #include <getline.h>
 104 #include <getopt.h>
 105 #include "closeout.h"
 106
 107 char *xmalloc PARAMS((size_t));
 108
 109 /* The name this program was run with.  */
 110 char *program_name;
 111
 112 /* Write out a 16-bit int, high byte first (network byte order).  */
 113
 114 static void
 115 put_short (int c, FILE *fp)
 116 {
 117   putc (c >> 8, fp);
 118   putc (c, fp);
 119 }
 120
 121 /* Return the length of the longest common prefix of strings S1 and S2. */
 122
 123 static int
 124 prefix_length (char *s1, char *s2)
 125 {
 126   register char *start;
 127
 128   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
 129     ;
 130   return s1 - start;
 131 }
 132
 133 static struct option const longopts[] =
 134 {
 135   {"help", no_argument, NULL, 'h'},
 136   {"version", no_argument, NULL, 'v'},
 137   {"null", no_argument, NULL, '0'},
 138   {NULL, no_argument, NULL, 0}
 139 };
 140
 141 extern char *version_string;
 142
 143 /* The name this program was run with. */
 144 char *program_name;
 145
 146
 147 static void
 148 usage (FILE *stream)
 149 {
 150   fprintf (stream,
 151            _("Usage: %s [-0 | --null] [--version] [--help]\n"),
 152            program_name);
 153   fputs (_("\nReport bugs to <bug-findutils@gnu.org>.\n"), stream);
 154 }
 155
 156
 157 int
 158 main (int argc, char **argv)
 159 {
 160   char *path;                   /* The current input entry.  */
 161   char *oldpath;                /* The previous input entry.  */
 162   size_t pathsize, oldpathsize; /* Amounts allocated for them.  */
 163   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
 164   int line_len;                 /* Length of input line.  */
 165   int delimiter = '\n';
 166   int optc;
 167
 168   program_name = argv[0];
 169   atexit (close_stdout);
 170
 171   pathsize = oldpathsize = 1026; /* Increased as necessary by getline.  */
 172   path = xmalloc (pathsize);
 173   oldpath = xmalloc (oldpathsize);
 174
 175   /* Set to anything not starting with a slash, to force the first
 176      prefix count to 0.  */
 177   strcpy (oldpath, " ");
 178   oldcount = 0;
 179
 180
 181   while ((optc = getopt_long (argc, argv, "hv0", longopts, (int *) 0)) != -1)
 182     switch (optc)
 183       {
 184       case '0':
 185         delimiter = 0;
 186         break;
 187
 188       case 'h':
 189         usage (stdout);
 190         return 0;
 191
 192       case 'v':
 193         printf (_("GNU locate version %s\n"), version_string);
 194         return 0;
 195
 196       default:
 197         usage (stderr);
 198         return 1;
 199       }
 200
 201   /* We expect to have no arguments. */
 202   if (optind != argc)
 203     {
 204       usage (stderr);
 205       return 1;
 206     }
 207
 208
 209
 210   fwrite (LOCATEDB_MAGIC, sizeof (LOCATEDB_MAGIC), 1, stdout);
 211
 212   while ((line_len = getdelim (&path, &pathsize, delimiter, stdin)) > 0)
 213     {
 214       path[line_len - 1] = '\0'; /* FIXME temporary: nuke the newline.  */
 215
 216       count = prefix_length (oldpath, path);
 217       diffcount = count - oldcount;
 218       oldcount = count;
 219       /* If the difference is small, it fits in one byte;
 220          otherwise, two bytes plus a marker noting that fact.  */
 221       if (diffcount < -127 || diffcount > 127)
 222         {
 223           putc (LOCATEDB_ESCAPE, stdout);
 224           put_short (diffcount, stdout);
 225         }
 226       else
 227         putc (diffcount, stdout);
 228
 229       fputs (path + count, stdout);
 230       putc ('\0', stdout);
 231
 232       {
 233         /* Swap path and oldpath and their sizes.  */
 234         char *tmppath = oldpath;
 235         size_t tmppathsize = oldpathsize;
 236         oldpath = path;
 237         oldpathsize = pathsize;
 238         path = tmppath;
 239         pathsize = tmppathsize;
 240       }
 241     }
 242
 243   free (path);
 244   free (oldpath);
 245
 246   return 0;
 247 }