home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1785 < prev    next >
Internet Message Format  |  1990-12-28  |  5KB
  1. From: gtoal@tharr.UUCP (Graham Toal)
  2. Newsgroups: alt.sources
  3. Subject: run length encoding (alt.sources.d discussions)
  4. Message-ID: <957@tharr.UUCP>
  5. Date: 6 Sep 90 13:16:16 GMT
  6.  
  7. Archive-name: runlen.c
  8.  
  9. /*
  10.  
  11. (   by the way, this and the previous huffman prog aren't meant to
  12.     be utilities for using - they're just for experimenting with;
  13.     I *don't* want yet another non-standard compression prog floating
  14.     around.  I'd never live it down ;-)   )
  15.  
  16.    More experimentation with compression: a simple run-length filter.
  17.  
  18.    This is the first idea that came into my head - these codings
  19.    are chosen so that all but a <dle> on its own stay the same
  20.    size or get smaller.  However maybe a better idea would be a
  21.    coding which moved 3-byte sequences into 2-bytes; on data which
  22.    is arrays of machine words, 2, 3, and 4 byte sequences are
  23.    disproportionately common. (24 or 32-bit-wide picture files?)
  24.  
  25.    Anyway, this took a 1028K scan (b/w, 300dpi) of a line drawing
  26.    (Doonesbury cartoon) and shrunk it to 395K; then the huffman
  27.    code I posted last week compressed that to 206K.
  28.  
  29.    This compares middling well to 188K from 'compress'.
  30.  
  31.  
  32.    A textual postscript file went from 310K, rle -> 249K,  huff -> 137K.
  33.  
  34.  
  35.         <dle>                            <dle><0>
  36.         <dle><dle>                       <dle><1>
  37.         <dle><dle> ... n ... <dle><dle>  <dle><2><n-1>
  38.         a                                a
  39.         aa                               aa
  40.         aaa                              aaa
  41.         aaaa                             a<dle><3>
  42.          :
  43.         aaaaaaa ... n ... aa             a<dle><n-1>
  44.          :
  45.         aaa ... 256 ... aaaaa            a<dle><255>
  46.         
  47.  
  48.     Maybe folks could hack up other simple filters, and experiment
  49.     with putting them together in various orders.  By the way, I tried
  50.     delta compression (processing the difference between the last byte
  51.     and this byte, rather than the byte itself).  Didn't help. Got worse
  52.     in fact :-(
  53.  
  54.  */
  55.  
  56.  
  57.  
  58. #include <stdio.h>
  59. #include <string.h>
  60. #include <stdlib.h>
  61.  
  62. #define RLE_MAGIC 290690L
  63.  
  64. FILE *input_file;
  65. FILE *output_file;
  66.  
  67. #ifndef TRUE
  68. #define TRUE (0==0)
  69. #define FALSE (0!=0)
  70. #endif
  71.  
  72. int DLE = 234;
  73.  
  74. void output_run(FILE *f, int ch, int count) {
  75.   if (ch == DLE) {
  76.     fputc(DLE, f);
  77.     if (count > 2) fputc(2, f);
  78.     fputc(count-1, f);
  79.   } else {
  80.     fputc(ch, f);
  81.     if (count == 1) return;
  82.     if (count > 3) fputc(DLE, f); else fputc(ch, f);
  83.     if (count == 3) fputc(ch, f);
  84.     if (count > 3) fputc(count-1, f);
  85.   }
  86. }
  87.  
  88. void hfputw(long w, FILE *f)
  89. {
  90.   fputc((int)((w>>24L)&255L), f);
  91.   fputc((int)((w>>16L)&255L), f);
  92.   fputc((int)((w>> 8L)&255L), f);
  93.   fputc((int)((w     )&255L), f);
  94. }
  95.  
  96. long hfgetw(FILE *f)
  97. {
  98. long w;
  99.   w = fgetc(f); w = w<<8L;
  100.   w |= fgetc(f); w = w<<8L;
  101.   w |= fgetc(f); w = w<<8L;
  102.   w |= fgetc(f);
  103.   return(w);
  104. }
  105.  
  106. int main(int argc, char **argv)
  107. {
  108. long fsize;
  109. int curr, last;
  110. int count;
  111. int a;
  112.  
  113.  
  114.   if (argc != 4 || *argv[1] != '-') {
  115.     fprintf(stderr, "syntax: %s {-e,-d} input output\n", argv[0]);
  116.     exit(0);
  117.   }
  118.  
  119.   input_file = fopen(argv[2], "rb");
  120.   if (input_file == NULL) {
  121.     fprintf(stderr, "%s: cannot open input file %s\n", argv[0], argv[2]);
  122.     exit(0);
  123.   }
  124.  
  125.   if (strcmp(argv[1], "-e") == 0) {
  126.     output_file = fopen(argv[3], "wb");
  127.     if (output_file == NULL) {
  128.       fprintf(stderr, "%s: cannot open output file %s\n", argv[0], argv[3]);
  129.       fclose(input_file);
  130.       exit(0);
  131.     }
  132.     fseek(input_file, 0L, SEEK_END);
  133.     fsize = ftell(input_file);
  134.     fclose(input_file);
  135.     input_file = fopen(argv[2], "rb");
  136.     hfputw(RLE_MAGIC, output_file);
  137.     hfputw(fsize, output_file);
  138.  
  139.     curr = fgetc(input_file); count = 1;
  140.     for (;;) {
  141.       for (;;) {
  142.         a = fgetc(input_file);
  143.         if (a == EOF) break;
  144.         if (a != curr) break;
  145.         count++;
  146.         if (count == 257) break;
  147.       }
  148.       if (a == EOF) break;
  149.       output_run(output_file, curr, count);
  150.       curr = a; count = 1;
  151.     }
  152.     output_run(output_file, curr, count);
  153.  
  154.     fclose(input_file);
  155.     fclose(output_file);
  156.   } else if (strcmp(argv[1], "-d") == 0) {
  157.     long check_magic;
  158.  
  159.     check_magic = hfgetw(input_file);
  160.     if (check_magic != RLE_MAGIC) {
  161.       fprintf(stderr, "%s: input file %s not huffman encoded (%ld vs %ld)\n",
  162.         argv[0], argv[2], check_magic, RLE_MAGIC);
  163.       exit(0);
  164.     }
  165.     output_file = fopen(argv[3], "wb");
  166.     fsize = hfgetw(input_file);
  167.  
  168.     last = -1;
  169.     for (;;) {
  170.       int i;
  171.  
  172.       a = fgetc(input_file);
  173.       if (a == EOF) break;
  174.       if (a == DLE) {
  175.         count = fgetc(input_file);
  176.         if (count <= 2 && last != -1) fputc(last, output_file), last = -1;
  177.         if (count == 0) {
  178.           fputc(DLE, output_file);
  179.         } else if (count == 1) {
  180.           fputc(DLE, output_file);
  181.           fputc(DLE, output_file);
  182.         } else if (count == 2) {
  183.           count = fgetc(input_file);
  184.           for (i = 0; i < count+1; i++) fputc(DLE, output_file);
  185.         } else {
  186.           if (last == -1) fprintf(stderr, "Error #1\n");
  187.           for (i = 0; i < count+1; i++) fputc(last, output_file);
  188.         }
  189.         last = -1;
  190.       } else {
  191.         if (last != -1) fputc(last, output_file);
  192.         last = a;
  193.       }
  194.     }
  195.     if (last != -1) fputc(last, output_file);
  196.  
  197.     fclose(input_file);
  198.     fclose(output_file);
  199.   } else {
  200.     fprintf(stderr, "syntax: %s {-e,-d} input output\n", argv[0]);
  201.   }
  202.   exit(0);
  203. }
  204.