home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume25 / freeze / part01 / encode.c < prev    next >
C/C++ Source or Header  |  1991-11-04  |  4KB  |  187 lines
  1. #include "freeze.h"
  2. #include "lz.h"
  3. #include "huf.h"
  4. #include "bitio.h"
  5.  
  6. /* for future versions ?... */
  7.  
  8. #define LENGTH_OFFSET   256
  9. #define EncodeLiteral(l)        EncodeChar(l)
  10. #define EncodeLength(l)         EncodeChar(l + LENGTH_OFFSET)
  11.  
  12. /*
  13.  * Freezes stdin to stdout
  14.  */
  15.  
  16. void freeze ()
  17. {
  18.     register u_short i, len, r, s;
  19.     register short c;
  20.     putchar(MAGIC1);
  21.     putchar(MAGIC2_2);
  22.  
  23. /* Huffman-dependent part */
  24.     write_header();
  25.     StartHuff(N_CHAR2);
  26.     init(Table2);
  27. /* end of Huffman-dependent part */
  28.  
  29.     InitTree();     /* LZ dependent */
  30.     InitIO();
  31.  
  32.     s = 0;
  33.     r = N2 - F2;
  34.     for (i = s; i < r; i++)
  35.         text_buf[i] = ' ';
  36.     for (len = 0; len < F2 && (c = getchar()) != EOF; len++)
  37.         text_buf[r + len] = c;
  38.  
  39.     /* check for magic header */
  40.     if(!topipe && !force && text_buf[r] == MAGIC1 &&
  41.         text_buf[r + 1] >= MAGIC2_1) {
  42.         if (quiet != 1)
  43.             fprintf(stderr, " already frozen ");
  44.         exit_stat = 2;
  45.         return;
  46.     }
  47.  
  48.     in_count = len;
  49.     for (i = 0; i <= F2; i++)
  50.         InsertNode(r + i - F2);
  51.  
  52.     while (len != 0) {
  53.         Get_Next_Match(r,1);
  54.         if (match_length > len)
  55.             match_length = len;
  56.  
  57.         if (match_length <= THRESHOLD) {
  58.             match_length = 1;
  59.             EncodeLiteral(text_buf[r]);
  60. #ifdef DEBUG
  61.             symbols_out ++;
  62.             if (verbose)
  63.                 fprintf(stderr, "'%s'\n",
  64.                     pr_char(text_buf[r]));
  65. #endif /* DEBUG */
  66.         } else if (greedy) {
  67. /* GREEDY parsing (compression rate 1.5% worse, but 40% faster) */
  68.  
  69.             EncodeLength((u_short) (match_length - THRESHOLD));
  70.             EncodePosition((u_short)match_position);
  71.  
  72.         } else {
  73.             register u_short orig_length, orig_position, oldchar;
  74.  
  75. /* This fragment (delayed coding, non-greedy) is due to ideas of
  76.     Jan Mark Wams' <jms@cs.vu.nl> COMIC:
  77. */
  78.             oldchar = text_buf[r];
  79.             orig_length = match_length;
  80.             orig_position = match_position;
  81.  
  82.             DeleteNode(s);
  83.             Next_Char(N2, F2);
  84.             Get_Next_Match(r,2);
  85.  
  86.             if (match_length > len) match_length = len;
  87.  
  88.             if (orig_length > match_length) {
  89.                 EncodeLength((u_short)
  90.                     (orig_length - THRESHOLD));
  91.                 EncodePosition((u_short)orig_position);
  92. #ifdef DEBUG
  93.                 match_position = orig_position;
  94. #endif  /* DEBUG */
  95.                 match_length = orig_length - 1;
  96.             } else {
  97.                 EncodeLiteral(oldchar);
  98. #ifdef DEBUG
  99.                 symbols_out ++;
  100.                 if (verbose)
  101.                     fprintf(stderr, "'%s'\n",
  102.                         pr_char(oldchar));
  103. #endif  /* DEBUG */
  104.                 EncodeLength(match_length - THRESHOLD);
  105.                 EncodePosition(match_position);
  106.             }
  107. #ifdef DEBUG
  108.             refers_out ++;
  109.             if (verbose) {
  110.                 register short pos =
  111.                     (r - 1 - match_position) & (N2 - 1),
  112.                 leng = match_length;
  113.                 fputc('"', stderr);
  114.                 for(; leng; leng--, pos++)
  115.                     fprintf(stderr, "%s",
  116.                         pr_char(text_buf[pos]));
  117.                 fprintf(stderr, "\"\n");
  118.             }
  119. #endif /* DEBUG */
  120.         }
  121.  
  122. /* Process the rest of the matched sequence (insertion in the list
  123.     only, without any matching !!!)
  124. */
  125.  
  126.         for (i = 0; i < match_length &&
  127.                 (c = getchar()) != EOF; i++) {
  128.             DeleteNode(s);
  129.             text_buf[s] = c;
  130.             if (s < F2 - 1)
  131.                 text_buf[s + N2] = c;
  132.             s = (s + 1) & (N2 - 1);
  133.             r = (r + 1) & (N2 - 1);
  134.             InsertNode(r);
  135.         }
  136.  
  137.         in_count += i;
  138.  
  139.         INDICATOR
  140.  
  141.         while (i++ < match_length) {
  142.             DeleteNode(s);
  143.             s = (s + 1) & (N2 - 1);
  144.             r = (r + 1) & (N2 - 1);
  145.             if (--len) InsertNode(r);
  146.         }
  147.     }
  148.  
  149.     /* to flush literals */
  150.     EncodeLength((short)ENDOF - LENGTH_OFFSET);
  151. #ifdef DEBUG
  152.     symbols_out ++;
  153. #endif
  154.     EncodeEnd();
  155.     /*
  156.      * Print out stats on stderr
  157.      */
  158.     if(quiet != 1) {
  159. #ifdef GATHER_STAT
  160.     fprintf(stderr, "Average number of steps: ");
  161.     prratio(stderr, node_steps, node_matches);
  162.     fprintf(stderr, "\n");
  163. #endif
  164. #ifdef DEBUG
  165.     fprintf( stderr,
  166.         "%ld chars in, %ld codes (%ld bytes) out, freezing factor: ",
  167.         in_count, symbols_out + refers_out, bytes_out);
  168.     prratio( stderr, in_count, bytes_out );
  169.     fprintf( stderr, "\n");
  170.     fprintf( stderr, "\tFreezing as in compact: " );
  171.     prratio( stderr, in_count-bytes_out, in_count );
  172.     prbits( stderr, in_count, bytes_out);
  173.     fprintf( stderr, "\n");
  174.     fprintf( stderr, "\tSymbols: %ld; references: %ld.\n",
  175.         symbols_out, refers_out);
  176. #else /* !DEBUG */
  177.     fprintf( stderr, "Freezing: " );
  178.     prratio( stderr, in_count-bytes_out, in_count );
  179.     prbits( stderr, in_count, bytes_out);
  180. #endif /* DEBUG */
  181.     }
  182.     if(bytes_out >= in_count)    /* exit(2) if no savings */
  183.     exit_stat = 2;
  184.     return;
  185. }
  186.  
  187.