home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / A / FIND / FINDUTIL.1 / FINDUTIL / findutils-4.1 / locate / code.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-26  |  5.8 KB  |  215 lines
  1. /* code -- bigram- and front-encode filenames for locate
  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., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. /* Compress a sorted list.
  19.    Works with `find' to encode a filename database to save space
  20.    and search time.
  21.  
  22.    Usage:
  23.  
  24.    bigram < file_list > bigrams
  25.    process-bigrams > most_common_bigrams
  26.    code most_common_bigrams < file_list > squeezed_list
  27.  
  28.    Uses `front compression' (see ";login:", March 1983, p. 8).
  29.    The output begins with the 128 most common bigrams.
  30.    After that, the output format is, for each line,
  31.    an offset (from the previous line) differential count byte
  32.    followed by a (partially bigram-encoded) ASCII remainder.
  33.    The output lines have no terminating byte; the start of the next line
  34.    is indicated by its first byte having a value <= 30.
  35.    
  36.    The encoding of the output bytes is:
  37.  
  38.    0-28        likeliest differential counts + offset (14) to make nonnegative
  39.    30        escape code for out-of-range count to follow in next halfword
  40.    128-255     bigram codes (the 128 most common, as determined by `updatedb')
  41.    32-127      single character (printable) ASCII remainder
  42.  
  43.    Written by James A. Woods <jwoods@adobe.com>.
  44.    Modified by David MacKenzie <djm@gnu.ai.mit.edu>.  */
  45.  
  46. #include <config.h>
  47. #include <stdio.h>
  48. #include <sys/types.h>
  49.  
  50. #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  51. #include <string.h>
  52. #else
  53. #include <strings.h>
  54. #endif
  55.  
  56. #ifdef STDC_HEADERS
  57. #include <stdlib.h>
  58. #endif
  59.  
  60. #include "locatedb.h"
  61.  
  62. char *xmalloc ();
  63.  
  64. /* The name this program was run with.  */
  65. char *program_name;
  66.  
  67. /* The 128 most common bigrams in the file list, padded with NULs
  68.    if there are fewer.  */
  69. static char bigrams[257] = {0};
  70.  
  71. /* Return the offset of PATTERN in STRING, or -1 if not found. */
  72.  
  73. static int
  74. strindex (string, pattern)
  75.      char *string, *pattern;
  76. {
  77.   register char *s;
  78.  
  79.   for (s = string; *s != '\0'; s++)
  80.     /* Fast first char check. */
  81.     if (*s == *pattern)
  82.       {
  83.     register char *p2 = pattern + 1, *s2 = s + 1;
  84.     while (*p2 != '\0' && *p2 == *s2)
  85.       p2++, s2++;
  86.     if (*p2 == '\0')
  87.       return s2 - strlen (pattern) - string;
  88.       }
  89.   return -1;
  90. }
  91.  
  92. /* Return the length of the longest common prefix of strings S1 and S2. */
  93.  
  94. static int
  95. prefix_length (s1, s2)
  96.      char *s1, *s2;
  97. {
  98.   register char *start;
  99.  
  100.   for (start = s1; *s1 == *s2 && *s1 != '\0'; s1++, s2++)
  101.     ;
  102.   return s1 - start;
  103. }
  104.  
  105. void
  106. main (argc, argv)
  107.      int argc;
  108.      char **argv;
  109. {
  110.   char *path;            /* The current input entry.  */
  111.   char *oldpath;        /* The previous input entry.  */
  112.   size_t pathsize, oldpathsize;    /* Amounts allocated for them.  */
  113.   int count, oldcount, diffcount; /* Their prefix lengths & the difference. */
  114.   char bigram[3];        /* Bigram to search for in table.  */
  115.   int code;            /* Index of `bigram' in bigrams table.  */
  116.   FILE *fp;            /* Most common bigrams file.  */
  117.   int line_len;            /* Length of input line.  */
  118.  
  119.   program_name = argv[0];
  120.  
  121.   bigram[2] = '\0';
  122.  
  123.   if (argc != 2)
  124.     {
  125.       fprintf (stderr, "Usage: %s most_common_bigrams < list > coded_list\n",
  126.            argv[0]);
  127.       exit (2);
  128.     }
  129.  
  130.   fp = fopen (argv[1], "r");
  131.   if (fp == NULL)
  132.     {
  133.       fprintf (stderr, "%s: ", argv[0]);
  134.       perror (argv[1]);
  135.       exit (1);
  136.     }
  137.  
  138.   pathsize = oldpathsize = 1026; /* Increased as necessary by getstr.  */
  139.   path = xmalloc (pathsize);
  140.   oldpath = xmalloc (oldpathsize);
  141.  
  142.   /* Set to anything not starting with a slash, to force the first
  143.      prefix count to 0.  */
  144.   strcpy (oldpath, " ");
  145.   oldcount = 0;
  146.  
  147.   /* Copy the list of most common bigrams to the output,
  148.      padding with NULs if there are <128 of them.  */
  149.   fgets (bigrams, 257, fp);
  150.   fwrite (bigrams, 1, 256, stdout);
  151.   fclose (fp);
  152.  
  153.   while ((line_len = getstr (&path, &pathsize, stdin, '\n', 0)) > 0)
  154.     {
  155.       char *pp;
  156.  
  157.       path[line_len - 1] = '\0'; /* Remove newline. */
  158.  
  159.       /* Squelch unprintable chars in path so as not to botch decoding.  */
  160.       for (pp = path; *pp != '\0'; pp++)
  161.     {
  162.       *pp &= 0177;
  163.       if (*pp < 040 || *pp == 0177)
  164.         *pp = '?';
  165.     }
  166.  
  167.       count = prefix_length (oldpath, path);
  168.       diffcount = count - oldcount;
  169.       oldcount = count;
  170.       /* If the difference is small, it fits in one byte;
  171.      otherwise, two bytes plus a marker noting that fact.  */
  172.       if (diffcount < -LOCATEDB_OLD_OFFSET || diffcount > LOCATEDB_OLD_OFFSET)
  173.     {
  174.       putc (LOCATEDB_OLD_ESCAPE, stdout);
  175.       putw (diffcount + LOCATEDB_OLD_OFFSET, stdout);
  176.     }
  177.       else
  178.     putc (diffcount + LOCATEDB_OLD_OFFSET, stdout);
  179.  
  180.       /* Look for bigrams in the remainder of the path.  */
  181.       for (pp = path + count; *pp != '\0'; pp += 2)
  182.     {
  183.       if (pp[1] == '\0')
  184.         {
  185.           /* No bigram is possible; only one char is left.  */
  186.           putchar (*pp);
  187.           break;
  188.         }
  189.       bigram[0] = *pp;
  190.       bigram[1] = pp[1];
  191.       /* Linear search for specific bigram in string table. */
  192.       code = strindex (bigrams, bigram);
  193.       if (code % 2 == 0)
  194.         putchar ((code / 2) | 0200); /* It's a common bigram.  */
  195.       else
  196.         fputs (bigram, stdout); /* Write the text as printable ASCII.  */
  197.     }
  198.  
  199.       {
  200.     /* Swap path and oldpath and their sizes.  */
  201.     char *tmppath = oldpath;
  202.     size_t tmppathsize = oldpathsize;
  203.     oldpath = path;
  204.     oldpathsize = pathsize;
  205.     path = tmppath;
  206.     pathsize = tmppathsize;
  207.       }
  208.     }
  209.  
  210.   free (path);
  211.   free (oldpath);
  212.  
  213.   exit (0);
  214. }
  215.