home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / cpm / utils / arc-lbr / splay.arc / UNSPL.C < prev    next >
C/C++ Source or Header  |  1988-08-25  |  2KB  |  102 lines
  1. /*
  2.     Splay Tree Compression
  3.  
  4.     from: "Application Of Splay Trees To Data Compression"
  5.           by Douglas W. Jones, Communications of the ACM, August 1988
  6.  
  7.     implemented in C by Bodo Rueskamp, <br@unido.uucp>
  8. */
  9.  
  10. /*  splay tree uncompress  */
  11.  
  12. #include <stdio.h>
  13.  
  14. int left[257], right[257], up[514];
  15.  
  16. int bit_input()
  17. {
  18.     static int bitnum = 0;
  19.     static int byte;
  20.  
  21.     if (bitnum == 0) {
  22.         if ((byte = getchar()) == -1) {
  23.             fprintf(stderr, "unexpected end of input\n");
  24.             exit(1);
  25.         }
  26.         bitnum = 8;
  27.     }
  28.     byte <<= 1;
  29.     --bitnum;
  30.     return((byte >> 8) & 1);
  31. }
  32.  
  33. void initialize()
  34. {
  35.     int i;
  36.  
  37.     for (i=0; i<514; ++i)
  38.         up[i] = i / 2;
  39.     for (i=0; i<257; ++i) {
  40.         left[i] = i * 2;
  41.         right[i] = i * 2 + 1;
  42.     }
  43. }
  44.  
  45. void splay(plain)
  46. int plain;
  47. {
  48.     int a, b, c, d;
  49.  
  50.     a = plain + 257;
  51.     while (a) {  /*  walk up the tree semi-rotating pairs  */
  52.         c = up[a];
  53.         if (c) {  /*  a pair remains  */
  54.             d = up[c];
  55.             /*  exchange children of pair  */
  56.             b = left[d];
  57.             if (c == b) {
  58.                 b = right[d];
  59.                 right[d] = a;
  60.             } else {
  61.                 left[d] = a;
  62.             }
  63.             if (a == left[c]) {
  64.                 left[c] = b;
  65.             } else {
  66.                 right[c] = b;
  67.             }
  68.             up[a] = d;
  69.             up[b] = c;
  70.             a = d;
  71.         } else {  /*  handle odd node at end  */
  72.             a = c;
  73.         }
  74.     }
  75. }
  76.  
  77. int uncompress()
  78. {
  79.     int a;
  80.  
  81.     a = 0;
  82.     while (a < 257)
  83.         a = bit_input() ? right[a] : left[a];
  84.     a -= 257;
  85.     splay(a);
  86.     return(a);
  87. }
  88.  
  89. main()
  90. {
  91.     int c;
  92.  
  93.     if ((getchar() != 0x1f) || (getchar() != 'S')) {
  94.         fprintf(stderr, "stdin not in compressed format\n");
  95.         exit(1);
  96.     }
  97.     initialize();
  98.     while ((c = uncompress()) != 256)
  99.         putchar(c);
  100.     return(0);
  101. }
  102.