home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / MISC / GNU / FIND12AS.ZIP / LIB / CODE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-22  |  3.6 KB  |  162 lines
  1. /* code -- code filenames for fast-find
  2.  
  3.    Compress a sorted list.
  4.    Works with 'find' to encode and decode a filename database.
  5.  
  6.    Usage:
  7.  
  8.    bigram < list > bigrams
  9.    process-bigrams > common_bigrams
  10.    code common_bigrams < list > squeezed_list
  11.  
  12.    Uses 'front compression' (see ";login:", March 1983, p. 8).
  13.    Output format is, per line, an offset differential count byte
  14.    followed by a partially bigram-encoded ASCII residue.
  15.    
  16.    The codes are:
  17.    
  18.    0-28        likeliest differential counts + offset to make nonnegative
  19.    30        escape code for out-of-range count to follow in next word
  20.    128-255     bigram codes (128 most common, as determined by 'updatedb')
  21.    32-127      single character (printable) ASCII residue
  22.  
  23.    Author: James A. Woods (jaw@riacs.edu)
  24.    Modified by David MacKenzie (djm@ai.mit.edu)
  25.    MS-DOS mods: Thorsten Ohl (ohl@gnu.ai.mit.edu)
  26.    Public domain. */
  27.  
  28. #include <stdio.h>
  29. #include <sys/types.h>
  30.  
  31. #ifdef MSDOS
  32. #include <stdlib.h>
  33. #include <string.h>
  34. void main (int argc, char **argv);
  35. int prefix_length (char *s1, char *s2);
  36. int strindex (char *string, char *pattern);
  37. #else /* not MSDOS */
  38. #include <sys/param.h>
  39. #endif /* not MSDOS */
  40.  
  41. #ifndef MAXPATHLEN
  42. #define MAXPATHLEN 1024
  43. #endif
  44.  
  45. /* Switch code. */
  46. #define    RESET    30
  47.  
  48. char path[MAXPATHLEN];
  49.  
  50. char oldpath[MAXPATHLEN] = " ";
  51.  
  52. char bigrams[257] = {0};
  53.  
  54. void
  55. main (argc, argv)
  56.      int argc;
  57.      char *argv[];
  58. {
  59.   int count, oldcount, diffcount;
  60.   int j, code;
  61.   char bigram[3];
  62.   FILE *fp;
  63.  
  64.   oldcount = 0;
  65.   bigram[2] = '\0';
  66.  
  67.   if (argc != 2)
  68.     {
  69.       fprintf (stderr, "Usage: %s common_bigrams < list > coded_list\n",
  70.            argv[0]);
  71.       exit (2);
  72.     }
  73.  
  74.   fp = fopen (argv[1], "r");
  75.   if (fp == NULL)
  76.     {
  77.       fprintf (stderr, "%s: ", argv[0]);
  78.       perror (argv[1]);
  79.       exit (1);
  80.     }
  81.  
  82.   fgets (bigrams, 257, fp);
  83.   fwrite (bigrams, 1, 256, stdout);
  84.  
  85.   while (fgets (path, sizeof path, stdin) != NULL)
  86.     {
  87.       path[strlen (path) - 1] = '\0'; /* Remove newline. */
  88.  
  89.       /* Squelch unprintable chars so as not to botch decoding. */
  90.       for (j = 0; path[j] != '\0'; j++)
  91.     {
  92.       path[j] &= 0177;
  93.       if (path[j] < 040 || path[j] == 0177)
  94.         path[j] = '?';
  95.     }
  96.       count = prefix_length (oldpath, path);
  97.       diffcount = count - oldcount;
  98.       if (diffcount < -14 || diffcount > 14)
  99.     {
  100.       putc (RESET, stdout);
  101.       putw (diffcount + 14, stdout);
  102.     }
  103.       else
  104.     putc (diffcount + 14, stdout);
  105.  
  106.       for (j = count; path[j] != '\0'; j += 2)
  107.     {
  108.       if (path[j + 1] == '\0')
  109.         {
  110.           putchar (path[j]);
  111.           break;
  112.         }
  113.       bigram[0] = path[j];
  114.       bigram[1] = path[j + 1];
  115.       /* Linear search for specific bigram in string table. */
  116.       code = strindex (bigrams, bigram);
  117.       if (code % 2 == 0)
  118.         putchar ((code / 2) | 0200);
  119.       else
  120.         fputs (bigram, stdout);
  121.     }
  122.       strcpy (oldpath, path);
  123.       oldcount = count;
  124.     }
  125.   exit (0);
  126. }
  127.  
  128. /* Return location of PATTERN in STRING or -1. */
  129.  
  130. int
  131. strindex (string, pattern)
  132.      char *string, *pattern;
  133. {
  134.   register char *s, *p, *q;
  135.  
  136.   for (s = string; *s != '\0'; s++)
  137.     if (*s == *pattern)
  138.       {
  139.     /* Fast first char check. */
  140.     for (p = pattern + 1, q = s + 1; *p != '\0'; p++, q++)
  141.       if (*q != *p)
  142.         break;
  143.     if (*p == '\0')
  144.       return q - strlen (pattern) - string;
  145.       }
  146.   return -1;
  147. }
  148.  
  149. /* Return length of longest common prefix of strings S1 and S2. */
  150.  
  151. int
  152. prefix_length (s1, s2)
  153.      char *s1, *s2;
  154. {
  155.   register char *start;
  156.  
  157.   for (start = s1; *s1 == *s2; s1++, s2++)
  158.     if (*s1 == '\0')
  159.       break;
  160.   return s1 - start;
  161. }
  162.