home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.pdx.edu / 2014.02.ftp.ee.pdx.edu.tar / ftp.ee.pdx.edu / pub / lpf / patent.essence < prev    next >
Text File  |  1992-11-03  |  4KB  |  163 lines
  1. /*
  2.     lz78.c -- Copyleft (C) 1990 by James A. Woods,
  3.     RIACS, NASA Ames Research Center.
  4.  
  5.     essence of U.S. patent #4,464,650 by Lempel/Ziv/Cohn/Eastman,
  6.     assignees Sperry Corporation and AT&T Bell Laboratories.
  7.     invented 1976, published IEEE Trans. Info Theory, 1978,
  8.     filed Aug. 10, 1981, awarded Aug. 7, 1984.
  9. */
  10.  
  11. #include <stdio.h>
  12.  
  13. #define BITS 14
  14. short table[(1<<BITS) * 256];    /* 8MB for 14-bit codes, 32MB for 16-bit */
  15.  
  16. main()
  17. {
  18.     register int K, i, p, prefix;
  19.     register long code;
  20.  
  21.     i++;
  22.     prefix = 0;
  23.  
  24.     while ((K = (getchar())) != EOF) {
  25.     code = (long) ((K << BITS) + prefix);
  26.     if ( (p = table[code]) != 0 )
  27.             prefix = p;
  28.     else {
  29. /*
  30.         output(prefix, BITS);  /* bitstuff or cascade with arithmetic coder
  31.         output(K, 8);
  32. */
  33.         putchar((prefix>>8) & 0377);  /* tokens hardcoded at 16 bits here */
  34.         putchar(prefix & 0377);
  35.         putchar(K);
  36.  
  37.         prefix = 0;
  38.  
  39.         if (i < (1<<BITS)) 
  40.         table[code] = (short) i++;
  41.         }
  42.     }
  43. }
  44.  
  45. -----------------------------------------------------------------------------
  46. /*
  47.     lzw.c -- Copyleft (C) 1985 by James A. Woods, NASA Ames Research Center
  48.  
  49.     essence of U.S. patent #4,558,302 by Terry Welch, assignee Sperry Corp.,
  50.     filed Jun. 20, 1983, published 1984, awarded Dec. 10, 1985.
  51.  
  52.     LZW is also known as LZMW1.  independently discovered by Victor Miller /
  53.     Mark Wegman, U.S. patent #4,814,746, assignee IBM,
  54.     filed June 1, 1983, published 1984, awarded March 21, 1989.
  55.     earlier file date takes precedence!
  56.  
  57.     code adds one table initialization plus three lines of change to lz78.c
  58. */
  59.  
  60. #include <stdio.h>
  61.  
  62. #define BITS 14
  63. short table[(1<<BITS) * 256];    /* 8MB for 14-bit codes, 32MB for 16-bit */
  64.  
  65. main()
  66. {
  67.     register int K, i, p, prefix;
  68.     register long code;
  69.  
  70.     for (i = 0; i < 256; i++)
  71.     table[i] = i;
  72.     i++;
  73.     prefix = getchar();
  74.  
  75.     while ((K = (getchar())) != EOF) {
  76.     code = (long) ((K << BITS) + prefix);
  77.     if ( (p = table[code]) != 0 )
  78.             prefix = p;
  79.     else {
  80. /*
  81.         output(prefix, BITS);  /* bitstuff or cascade with arithmetic coder
  82. */
  83.         putchar((prefix>>8) & 0377);  /* tokens hardcoded at 16 bits here */
  84.         putchar(prefix & 0377);
  85.  
  86.         prefix = K;
  87.  
  88.         if (i < (1<<BITS)) 
  89.         table[code] = (short) i++;
  90.         }
  91.     }
  92. }
  93.  
  94. -----------------------------------------------------------------------------
  95. /*
  96.     lzwap.c -- Copyleft (C) 1990 by James A. Woods,
  97.     RIACS, NASA Ames Research Center.
  98.  
  99.     essence of U.S. patent #4,876,541 by James A. Storer, Brandeis Univ.,
  100.     assignee Data Compression Corporation, filed Oct. 25, 1987,
  101.     awarded Oct. 24, 1989.  Independently rediscovered by
  102.     Daniel J. Bernstein, NYU, 1990, and Nigel Horspool, U. Victoria
  103.     (see DCC '91 conference proceedings).
  104.  
  105.     LZW-based, with "all-prefixes" addition.
  106. */
  107.  
  108. #include <stdio.h>
  109.  
  110. #define BITS 14
  111. short table[(1<<BITS) * 256];   /* 8MB for 14-bit codes, 32MB for 16-bit */
  112.  
  113. int curmatch[2000];
  114.  
  115. main()
  116. {
  117.     register int K, i, j, p, prefix;
  118.     register long code;
  119.     long oldmatch, newcode;
  120.     int count;
  121.  
  122.     count = 1;
  123.  
  124.     for (i = 0; i < 256; i++)
  125.     table[i] = i;
  126.  
  127.     i++;
  128.     curmatch[0] = prefix = getchar();
  129.  
  130.     while ((K = (getchar())) != EOF) {
  131.     curmatch[count] = K;
  132.     code = (long) ((K << BITS) + prefix);
  133.     if ( (p = table[code]) != 0 ) {
  134.         count++;
  135.         prefix = p;
  136.     }
  137.     else {
  138. /*
  139.         output(prefix, BITS);  /* bitstuff or cascade with arithmetic coder
  140. */
  141.         putchar((prefix>>8) & 0377);  /* tokens hardcoded at 16 bits here */
  142.         putchar(prefix & 0377);
  143.  
  144.         if (i < (1<<BITS)) {
  145.         if ( count > 1) {
  146.             for (j = 1; j < count; j++) {
  147.             newcode = (long) (((curmatch[j]) << BITS) + oldmatch);
  148.                 if (i < (1<<BITS)) 
  149.                 oldmatch = table[newcode] = (short) i++;
  150.             }
  151.         }
  152.             if (i < (1<<BITS)) 
  153.             oldmatch = table[code] = (short) i++;
  154.         }
  155.         prefix = K;
  156.         curmatch[0] = K;
  157.         count = 1;
  158.         }
  159.     }
  160. }
  161. -----------------------------------------------------------------------------
  162.  
  163.