lz77.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 const char *progname;
   6
   7 struct pair {
   8   unsigned int distance;
   9   unsigned int length;
  10 };
  11
  12 unsigned char *window;
  13 size_t buffer_size, window_cap, buffer_cap;
  14
  15 void fill_buffer (void) {
  16   unsigned int i;
  17   int c;
  18   for (i = window_cap + buffer_size; i < window_cap + buffer_cap; i++) {
  19     c = getchar();
  20     if (c == EOF) {
  21       break;
  22     }
  23     window[i] = (unsigned char) c;
  24     buffer_size ++;
  25   }
  26 }
  27
  28 void shift_buffer (unsigned int shift) {
  29   memmove (&window[0], &window[shift], window_cap + buffer_cap - shift);
  30   buffer_size -= shift;
  31 }
  32
  33 unsigned int comlen(const unsigned char *str1
  34   , const unsigned char *str2
  35   , unsigned int limit) {
  36   unsigned int len = 0;
  37   while (*str1++ == *str2++ && len < limit)
  38     len ++;
  39   return len;
  40 }
  41
  42 struct pair find_match (void) {
  43   unsigned int i;
  44   unsigned int clen;
  45   unsigned int dist, len;
  46   struct pair match;
  47   dist = 0;
  48   len  = 0;
  49   for (i = 0; i < window_cap; i++) {
  50     clen = comlen(&window[i], &window[window_cap], buffer_size - 1);
  51     if (clen >= len) {
  52       len = clen;
  53       dist = window_cap - i;
  54     }
  55   }
  56   match.distance = len ? dist : 0;
  57   match.length   = len;
  58   return match;
  59 }
  60
  61 void write_pair (struct pair pair) {
  62   int c;
  63   c = pair.distance % 256;
  64   putchar(c);
  65   c = (pair.distance / 256) | (pair.length << 3);
  66   putchar(c);
  67 }
  68
  69 void compress (void) {
  70   struct pair match;
  71   fill_buffer ();
  72   while (buffer_size) {
  73     match = find_match ();
  74     shift_buffer (match.length + 1);
  75     write_pair (match);
  76     putchar ((int) window[window_cap - 1]);
  77     fill_buffer ();
  78   }
  79 }
  80
  81 int read_pair (struct pair *pair) {
  82   int c;
  83   int tmp;
  84   c = getchar ();
  85   if (c == EOF) {
  86     return 0;
  87   }
  88   tmp = c;
  89   c = getchar ();
  90   if (c == EOF) {
  91     fprintf(stderr, "%s: Unexpected end of file.\n", progname);
  92     exit (1);
  93   }
  94   tmp = tmp | ((c & 0x07) << 8);
  95   pair -> distance = tmp;
  96   pair -> length   = c >> 3;
  97   return 1;
  98 }
  99
 100 void decompress (void) {
 101   struct pair pair;
 102   unsigned int i;
 103   int c;
 104   while (read_pair (&pair)) {
 105     c = getchar();
 106     if (c == EOF) {
 107       fprintf(stderr, "%s: Unexpected end of file.\n", progname);
 108       exit (1);
 109     }
 110     for (i = 0; i < pair.length; i++) {
 111       window[window_cap + i] = window[window_cap - pair.distance + i];
 112       buffer_size ++;
 113     }
 114     window[window_cap + buffer_size++] = (unsigned char) c;
 115     for (i = 0; i < buffer_size; i++) {
 116       putchar ((int) window[window_cap+i]);
 117     }
 118     shift_buffer (buffer_size);
 119   }
 120 }
 121
 122 int main (int argc, char **argv) {
 123   progname = argv[0];
 124   window_cap = 2048;
 125   buffer_cap = 32;
 126   window = (unsigned char *) malloc (sizeof (unsigned char)
 127     * (window_cap + buffer_cap));
 128   if (window == NULL) {
 129     fprintf(stderr, "%s: Can not allocate memory.\n", progname);
 130     return 1;
 131   }
 132   memset (window, 0, window_cap + buffer_cap);
 133   if (argc == 2 && strcmp("-d", argv[1]) == 0) {
 134     decompress ();
 135   } else if (argc == 1) {
 136     compress ();
 137   } else {
 138     fprintf(stderr, "Usage: %s [-d]\n", progname);
 139     return 1;
 140   }
 141   free (window);
 142   return 0;
 143 }