home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / compress / splint.arc / splay.c < prev    next >
C/C++ Source or Header  |  1989-03-08  |  7KB  |  367 lines
  1. /* Splint:
  2.  * a data compression program
  3.  *
  4.  * This program refers the Pascal source codes of
  5.  * a splay-prefix encoding program in an article of
  6.  *
  7.  * Jones, Douglas. W,:
  8.  * Application of Splay Trees to Data Compression,
  9.  * Communications ACM, Vol. 31, No. 8, pp. 996 - 1007. (August 1988)
  10.  *
  11.  * Written by Kenji Rikitake and Naoshi Wakatabe.
  12.  * Copyright (C)1988, 1989 by Kenji Rikitake and Naoshi Wakatabe.
  13.  * All rights reserved.
  14.  * Permission to copy this program without fee all or part of this
  15.  * material is granted, provided that the copies are not made or
  16.  * distributed for direct commercial advantage.
  17.  *
  18.  * If you have any questions and/or suggestions, Contact
  19.  *
  20.  * Kenji Rikitake
  21.  * 4-19-11-102, Sakurajousui, Setagaya-ku,
  22.  * Tokyo 156 Japan
  23.  * JUNET: rikitake%wadalab.t.u-tokyo.JUNET@relay.cs.net
  24.  */
  25.  
  26. /* $Header: splay.cv  1.6  89/03/08 01:00:50  kenji  Exp $
  27.  * $Log: RCS/splay.cv $
  28.  * Revision 1.6  89/03/08 01:00:50  kenji
  29.  * combined with bitio.c by Kenji
  30.  * 
  31.  * Revision 1.5  89/03/01 14:10:26  kenji
  32.  * Kenji welcome Naoshi one of the authors
  33.  * Naoshi changed the tree by using "struct".
  34.  * This made things a bit faster
  35.  * 
  36.  * Revision 1.3  89/01/06 23:58:50  kenji
  37.  * encryption algorithm improved
  38.  * 
  39.  * Revision 1.2  89/01/06 23:36:16  kenji
  40.  * added block freeing routine.
  41.  * modified for using file pointers.
  42.  * 
  43.  * Revision 1.1  88/12/27 16:06:14  kenji
  44.  * Initial revision
  45.  * 
  46.  */
  47.  
  48. /* $Header: splay.cv  1.6  89/03/08 01:00:50  kenji  Exp $
  49.  * $Log: RCS/splay.cv $
  50.  * Revision 1.6  89/03/08 01:00:50  kenji
  51.  * combined with bitio.c by Kenji
  52.  * 
  53.  * Revision 1.5  89/03/01 14:10:26  kenji
  54.  * Kenji welcome Naoshi one of the authors
  55.  * Naoshi changed the tree by using "struct".
  56.  * This made things a bit faster
  57.  * 
  58.  * Revision 1.4  89/02/22 20:28:14  kenji
  59.  * Modified for Microsoft C 5.1 Small Model by Naoshi Wakatabe
  60.  * 
  61.  * Revision 1.3  89/01/06 23:58:50  kenji
  62.  * encryption algorithm improved
  63.  * 
  64.  * Revision 1.2  89/01/06 23:36:16  kenji
  65.  * added block freeing routine.
  66.  * modified for using file pointers.
  67.  * 
  68.  * Revision 1.1  88/12/27 16:06:14  kenji
  69.  * Initial revision
  70.  * 
  71.  */
  72.  
  73. static char *identfield = "$Header: splay.cv  1.6  89/03/08 01:00:50  kenji  Exp $";
  74.  
  75. /* splaying routines */
  76.  
  77. #include "splint.h"
  78.  
  79. /* splay-prefix tree structure */
  80.  
  81. /*
  82. int sup[MAXSTATE][TWICEMAX+1];
  83. int sleft[MAXSTATE][MAXCHAR+1];
  84. int sright[MAXSTATE][MAXCHAR+1];
  85. */
  86.  
  87. #ifndef MSDOS
  88. #define    far
  89. #else
  90. #define    malloc(size)    _fmalloc(size)
  91. #define    free(block)    _ffree(block)
  92. #endif
  93.  
  94. struct tree {
  95.     int    up[TWICEMAX + 1];
  96.     int    left[MAXCHAR + 1];
  97.     int    right[MAXCHAR + 1];
  98. };
  99.  
  100. struct tree far *stree[MAXSTATE];
  101. int state;
  102.  
  103. #define BIT_OVLIM 16    /* output bit overflow limit */
  104.  
  105. /* bit buffers */
  106. static int ibuf;        /* input waiting bits */
  107. static int ibitstogo;    /* # of bits in ibuf */
  108. static int igarbits;    /* # of bits past eof */
  109. static int obuf;        /* output waiting bits */
  110. static int obitstogo;    /* # of bits in obuf */
  111.  
  112. /* initialize bit i/o buffers */
  113. #define start_inputing_bits() {ibitstogo = 0; igarbits = 0;}
  114. #define start_outputing_bits() {obuf = 0; obitstogo = 8;}
  115.  
  116. /* output buffer flush */
  117. #define done_outputing_bits(outp) putc((obuf >> obitstogo), outp)
  118.  
  119. /* input a bit */
  120.  
  121. int input_bit(inp)
  122. FILE *inp;
  123. {
  124.     int t;
  125.     
  126.     if (ibitstogo == 0) {
  127.         ibuf = getc(inp);
  128.         if (ibuf == EOF) {
  129.             igarbits++;
  130.             if (igarbits > BIT_OVLIM) {
  131.                 fprintf(stderr, "splint: input file exceeds EOF\n");
  132.                 exit(-1);
  133.                 }
  134.             }
  135.         ibitstogo = 8;
  136.         }
  137.     t = ibuf & 1;
  138.     ibuf >>= 1;
  139.     ibitstogo--;
  140.     return t;
  141. }
  142.  
  143. /* output a bit */
  144.  
  145. void output_bit(bit, outp)
  146. int bit;
  147. FILE *outp;
  148. {
  149.     obuf >>= 1;
  150.     if (bit) {
  151.         obuf |= 0x80;
  152.         }
  153.     obitstogo--;
  154.     if (obitstogo == 0) {
  155.         putc(obuf, outp);
  156.         obitstogo = 8;
  157.         }
  158. }
  159.  
  160. /* malloc() with heap check */
  161. static void far *ch_malloc(size)
  162. size_t size;
  163. {
  164.     void far *blockp;
  165.  
  166.     if ((blockp = malloc(size)) == NULL) {
  167.         fprintf(stderr, "splint: out of memory\n");
  168.         exit(-1);
  169.         }
  170.     return blockp;
  171. }
  172.  
  173. /* initializing splay tree structure */
  174.  
  175. void spl_init()
  176. {
  177.     int i, j, s;
  178.     struct tree far *spp;
  179.     void splay();
  180.  
  181.     start_inputing_bits();
  182.     start_outputing_bits();
  183.  
  184.     for (s = 0; s < MAXSTATE; s++) {
  185.  
  186.  
  187.         spp = (struct tree far *)ch_malloc(sizeof(struct tree));
  188.         stree[s] = spp;
  189. #ifdef DEBUG
  190.         fprintf(stderr, "spl_init: s = %d\n", s);
  191.         fprintf(stderr, "coreleft = %ld\n", coreleft());
  192. #endif
  193.  
  194.         for (i = 2; i <= TWICEMAX; i++) {
  195.             spp->up[i] = i / 2;
  196.             }
  197.         for (j = 1; j <= MAXCHAR; j++) {
  198.             spp->left[j] = 2 * j;
  199.             spp->right[j] = 2 * j + 1;
  200.             }
  201.         }
  202.  
  203.     /* pre-splaying for cryptography */
  204.     j = strlen(spl_passwd) - 1;
  205.     for (s = 0; s < MAXSTATE; s++) {
  206.         for (i = j; i >= 0; i--) {
  207.             state = s;
  208.             splay(spl_passwd[i]);
  209.             }
  210.         }
  211.  
  212.     /* initial state */
  213.     state = 0;
  214.  
  215. }
  216.  
  217. /* unalloc used trees */
  218. /* free() with reverse sequence of ch_malloc() */
  219.  
  220. void free_trees()
  221. {
  222.     int s;
  223.  
  224.     for (s = MAXSTATE - 1; s >= 0; s--) {
  225.         free(stree[s]);
  226.         }
  227.  
  228. }
  229.  
  230. /* splay the tree with a symbol */
  231.  
  232. #ifndef ASM
  233. void splay(sym)
  234. int sym;
  235. {
  236.     int a, b, c, d;
  237.     struct tree far *spp;
  238.  
  239.     a = sym + SUCCMAX;
  240.     spp = stree[state];
  241.  
  242.     do {
  243.         c = spp->up[a];
  244.         if (c != ROOT) {
  245.             d = spp->up[c];
  246.             b = spp->left[d];
  247.             if (c == b) {
  248.                 b = spp->right[d];
  249.                 spp->right[d] = a;
  250.                 }
  251.             else {
  252.                 spp->left[d] = a;
  253.                 }
  254.             if (a == spp->left[c]) {
  255.                 spp->left[c] = b;
  256.                 }
  257.             else {
  258.                 spp->right[c] = b;
  259.                 }
  260.             spp->up[a] = d;
  261.             spp->up[b] = c;
  262.             a = d;
  263.             }
  264.         else {
  265.             a = c;
  266.             }
  267.     } while (a != ROOT);
  268.  
  269.     state = sym % MAXSTATE;
  270. }
  271. #endif
  272.  
  273. /* compress a symbol */
  274.  
  275. void spl_comp(sym, outp)
  276. int sym;
  277. FILE *outp;
  278. {
  279.     int sp, a;
  280.     int stack[MAXCHAR];
  281.     struct tree far *spp;
  282.     
  283.     a = sym + SUCCMAX;
  284.     sp = 0;
  285.     spp = stree[state];
  286.     do {
  287.         stack[sp] = (spp->right[spp->up[a]] == a) ? 1 : 0;
  288.         sp++;
  289.         a = spp->up[a];
  290.     } while (a != ROOT);
  291.     do {
  292.         sp--;
  293.         output_bit(stack[sp], outp);
  294.     } while (sp > 0);
  295.     splay(sym);
  296. }
  297.  
  298. /* expand a code into its symbol */
  299.  
  300. int spl_exp(inp)
  301. FILE *inp;
  302. {
  303.     int a, sym;
  304.     struct tree far *spp;
  305.     a = ROOT;
  306.     
  307.     spp = stree[state];
  308.     do {
  309.         if (input_bit(inp) == 0) {
  310.             a = spp->left[a];
  311.             }
  312.         else {
  313.             a = spp->right[a];
  314.             }
  315.     } while (a <= MAXCHAR);
  316.     sym = a - SUCCMAX;
  317.     splay(sym);
  318.     return sym;
  319. }
  320.  
  321. /* encoding from inp to outp */
  322.  
  323. void spl_encode(inp, outp)
  324. FILE *inp, *outp;
  325. {
  326.     int sym;
  327.  
  328.     spl_init();
  329.  
  330.     for(;;) {
  331.         if((sym = getc(inp)) == EOF) break;
  332.         spl_comp(sym, outp);
  333.         }
  334.  
  335. #ifdef DEBUG
  336.         fprintf(stderr, "spl_encode: got out of for loop\n");
  337. #endif
  338.     spl_comp(EOF_CODE, outp);
  339. #ifdef DEBUG
  340.         fprintf(stderr, "spl_encode: spl_comp(EOF_SYM) done\n");
  341. #endif
  342.     done_outputing_bits(outp);
  343.     free_trees();
  344. }
  345.  
  346. /* decoding from inp to outp */
  347.  
  348. void spl_decode(inp, outp)
  349. FILE *inp, *outp;
  350. {
  351.     int sym;
  352.  
  353.     spl_init();
  354.  
  355.     for(;;) {
  356.         sym = spl_exp(inp);
  357.         if(sym == EOF_CODE) break;
  358.         putc(sym, outp);
  359.         }
  360. #ifdef DEBUG
  361.         fprintf(stderr, "spl_decode: EOF_CODE received\n");
  362. #endif
  363.     free_trees();
  364. }
  365.  
  366. /* end */
  367.