home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / l / lds_10.zip / SPLAY / SPLAY.C < prev   
C/C++ Source or Header  |  1990-08-26  |  11KB  |  416 lines
  1. /* 
  2.     this program is a straight pascal to C translation of a program that
  3.     compresses and decompresses files using 'Splay' trees.  This is the
  4.     original comment block:
  5.         
  6. {*****************************************************************************
  7.   Compress and decompress files using the "splay tree" technique.
  8.   Based on an article by Douglas W. Jones, "Application of Splay Trees to
  9.   Data Compression", in Communications of the ACM, August 1988, page 996.
  10.  
  11.   This is a method somewhat similar to Huffman encoding (SQZ), but which is
  12.   locally adaptive. It therefore requires only a single pass over the
  13.   uncompressed file, and does not require storage of a code tree with the
  14.   compressed file. It is characterized by code simplicity and low data
  15.   overhead. Compression efficiency is not as good as recent ARC
  16.   implementations, especially for large files. However, for small files, the
  17.   efficiency of SPLAY approaches that of ARC's squashing technique.
  18.  
  19.   Usage:
  20.     SPLAY [/X] Infile Outfile
  21.  
  22.     when /X is not specified, Infile is compressed and written to OutFile.
  23.     when /X is specified, InFile must be a file previously compressed by
  24.     SPLAY, and OutFile will contain the expanded text.
  25.  
  26.     SPLAY will prompt for input if none is given on the command line.
  27.  
  28.   Caution! This program has very little error checking. It is primarily
  29.   intended as a demonstration of the technique. In particular, SPLAY will
  30.   overwrite OutFile without warning. Speed of SPLAY could be improved
  31.   enormously by writing the inner level bit-processing loops in assembler.
  32.  
  33.   Implemented on the IBM PC by
  34.     Kim Kokkonen
  35.     TurboPower Software
  36.     [72457,2131]
  37.     8/16/88
  38. *****************************************************************************}
  39.  
  40.     This program is a _translation_ not a rewrite!!! It indexes arrays
  41.     pascal style (1..X) instead of C style (0..X-1), and a few other
  42.     non-C conventions.  This should compile under any C compiler, it only
  43.     uses about 4 or 5 standard library functions.  It was compiled using
  44.     Turbo C++ 1.0 in the small memory model.  I have included the
  45.     original Turbo Pascal source code for reference purposes.  Also, the
  46.     program usage is slightly different, no '/' is required before the
  47.     'X' parameter.  It has been tested with files up to approximately
  48.     450K and also successfully compressed and uncompressed ZIP files
  49.     (although the compressed version was bigger!).  I retained almost all
  50.     the original program comments for clarity.  I will, hopefully,
  51.     translate this to normal looking C sometime soon.  If you have any
  52.     questions, comments, or complaints, let me know.
  53.         
  54.     Sean O'Connor
  55.     [74017,2501]
  56.     8-26-90
  57.         
  58.     An aside, Douglas Jones was a professor I had while I was attending the
  59.     University of Iowa, so this program holds a special interest for me.
  60. */
  61.  
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <string.h>
  65. #include <ctype.h>
  66.  
  67. typedef unsigned int word;
  68. typedef unsigned char byte;
  69. typedef unsigned char bool;
  70. #define true  1
  71. #define false 0
  72.  
  73. #define BufSize     16384       /* size of input and output buffers */
  74. #define Sig         0xff02aa55L /* arbitrary signature denotes compressed file */
  75. #define MaxChar     256         /* ordinal of highest character */
  76. #define EofChar     256         /* used to mark end of compressed file */
  77. #define PredMax     255         /* MaxChar - 1 */
  78. #define TwiceMax    512         /* 2 * MaxChar */
  79. #define Root        0           /* index of root node */
  80.  
  81. /* Used to unpack bits and bytes */
  82. byte BitMask[8]={1, 2, 4, 8, 16, 32, 64, 128};
  83.  
  84. typedef struct
  85. {
  86.     unsigned long Signature;
  87.     /* put any other info here like file name and date */
  88. } FileHeader;
  89.  
  90. typedef byte BufferArray[BufSize + 1];
  91. typedef word CodeType;  /* 0..MaxChar */
  92. typedef byte UpIndex;   /* 0..PredMax */
  93. typedef word DownIndex; /* 0..TwiceMax */
  94. typedef DownIndex TreeDownArray[PredMax + 1];  /* UpIndex */
  95. typedef UpIndex TreeUpArray[TwiceMax + 1];     /* DownIndex */
  96.  
  97. BufferArray InBuffer;           /* input file buffer */
  98. BufferArray OutBuffer;          /* output file buffer */
  99. char InName[80];                /* input file name */
  100. char OutName[80];               /* output file name */
  101. char CompStr[4];                /* response from Expand? prompt */
  102. FILE *InF;                      /* input file */
  103. FILE *OutF;                     /* output file */
  104.  
  105. TreeDownArray Left, Right;      /* child branches of code tree */
  106. TreeUpArray Up;                 /* Parent branches of code tree */
  107. bool CompressFlag;              /* true to compress file */
  108. byte BitPos;                    /* current bit in byte */
  109. CodeType InByte;                /* current input byte */
  110. CodeType OutByte;               /* current output byte */
  111. word InSize;                    /* current chars in input buffer */
  112. word OutSize;                   /* Current chars in output buffer */
  113. word Index;                     /* general purpose index */
  114.  
  115. char *Usage = {"Usage: splay [x] infile outfile\n\n"
  116.                "Where 'x' denotes expand infile to outfile\n"
  117.                "Normally compress infile to outfile\n"
  118. };
  119.  
  120. /* function prototypes */
  121. void InitializeSplay(void);
  122. void Splay(CodeType Plain);
  123. void FlushOutBuffer(void);
  124. void WriteByte(void);
  125. void Compress(CodeType Plain);
  126. void ReadHeader(void);
  127. byte GetByte(void);
  128. CodeType Expand(void);
  129. void ExpandFile(void);
  130.  
  131. /* initialize the splay tree - as a balanced tree */
  132. void InitializeSplay(void)
  133. {
  134.     DownIndex I;
  135.     int /*UpIndex*/ J;
  136.     DownIndex K;
  137.     
  138.     for (I = 1; I <= TwiceMax; I++)
  139.         Up[I] = (I - 1) >> 1;
  140.     for (J = 0; J <= PredMax; J++)
  141.     {
  142.         K = ((byte)J + 1) << 1;
  143.         Left[J] = K - 1;
  144.         Right[J] = K;
  145.     }
  146. }
  147.  
  148. /* rearrange the splay tree for each succeeding character */
  149. void Splay(CodeType Plain)
  150. {
  151.     DownIndex A, B;
  152.     UpIndex C, D;
  153.     
  154.     A = Plain + MaxChar;
  155.     
  156.     do
  157.     {
  158.         /* walk up the tree semi-rotating pairs */
  159.         C = Up[A];
  160.         if (C != Root)
  161.         {
  162.             /* a pair remains */
  163.             D = Up[C];
  164.             
  165.             /* exchange children of pair */
  166.             B = Left[D];
  167.             if (C == B)
  168.             {
  169.                 B = Right[D];
  170.                 Right[D] = A;
  171.             }
  172.             else
  173.                 Left[D] = A;
  174.             
  175.             if (A == Left[C])
  176.                 Left[C] = B;
  177.             else
  178.                 Right[C] = B;
  179.             
  180.             Up[A] = D;
  181.             Up[B] = C;
  182.             A = D;
  183.         }
  184.         else
  185.             A = C;
  186.     } while (A != Root);
  187. }
  188.  
  189. /* flush output buffer and reset */
  190. void FlushOutBuffer(void)
  191. {
  192.     if (OutSize > 0)
  193.     {
  194.         fwrite(OutBuffer+1, sizeof(byte), OutSize, OutF);
  195.         OutSize = 0;
  196.     }
  197. }
  198.  
  199. /* output byte in OutByte */
  200. void WriteByte(void)
  201. {
  202.     if (OutSize == BufSize)
  203.         FlushOutBuffer();
  204.     OutSize++;
  205.     OutBuffer[OutSize] = OutByte;
  206. }
  207.  
  208.  
  209. /* compress a single char */
  210. void Compress(CodeType Plain)
  211. {
  212.     DownIndex A;
  213.     UpIndex U;
  214.     word Sp;
  215.     bool Stack[PredMax+1];
  216.     
  217.     A = Plain + MaxChar;
  218.     Sp = 0;
  219.     
  220.     /* walk up the tree pushing bits onto stack */
  221.     do
  222.     {
  223.         U = Up[A];
  224.         Stack[Sp] = (Right[U] == A);
  225.         Sp++;
  226.         A = U;
  227.     } while (A != Root);
  228.     
  229.     /* unstack to transmit bits in correct order */
  230.     do
  231.     {
  232.         Sp--;
  233.         if (Stack[Sp])
  234.             OutByte |= BitMask[BitPos];
  235.         if (BitPos == 7)
  236.         {
  237.             /* byte filled with bits, write it out */
  238.             WriteByte();
  239.             BitPos = 0;
  240.             OutByte = 0;
  241.         }
  242.         else
  243.             BitPos++;
  244.     } while (Sp != 0);
  245.     
  246.     /* update the tree */
  247.     Splay(Plain);
  248. }
  249.  
  250. /* compress input file, writing to outfile */
  251. void CompressFile(void)
  252. {
  253.     FileHeader Header;
  254.     
  255.     /* write header to output */
  256.     Header.Signature = Sig;
  257.     fwrite(&Header, sizeof(FileHeader), 1, OutF);
  258.     
  259.     /* compress file */
  260.     OutSize = 0;
  261.     BitPos = 0;
  262.     OutByte = 0;
  263.     do
  264.     {
  265.         InSize = fread(InBuffer+1, sizeof(byte), BufSize, InF);
  266.         for (Index = 1; Index <= InSize; Index++)
  267.             Compress(InBuffer[Index]);
  268.     } while (InSize >= BufSize);
  269.     
  270.     /* Mark end of file */
  271.     Compress(EofChar);
  272.     
  273.     /* Flush buffers */
  274.     if (BitPos != 0)
  275.         WriteByte();
  276.     FlushOutBuffer();
  277. }
  278.  
  279. /* read a compressed file header */
  280. void ReadHeader(void)
  281. {
  282.     FileHeader Header;
  283.     
  284.     fread(&Header, sizeof(FileHeader), 1, InF);
  285.     if (Header.Signature != Sig)
  286.     {
  287.         printf("Unrecognized file format!\n");
  288.         exit(1);
  289.     }
  290. }
  291.  
  292. /* return next byte from compressed input */
  293. byte GetByte(void)
  294. {
  295.     Index++;
  296.     if (Index > InSize)
  297.     {
  298.         /* reload file buffer */
  299.         InSize = fread(InBuffer+1, sizeof(byte), BufSize, InF);
  300.         Index = 1;
  301.         /* end of file handled by special marker in compressed file */
  302.     }
  303.     
  304.     /* get next byte from buffer */
  305.     return InBuffer[Index];
  306. }
  307.  
  308. /* return next char from compressed input */
  309. CodeType Expand(void)
  310. {
  311.     DownIndex A;
  312.     
  313.     /* scan the tree to a leaf, which determines the character */
  314.     A = Root;
  315.     do
  316.     {
  317.         if (BitPos == 7)
  318.         {
  319.             /* used up bits in current byte, get another */
  320.             InByte = GetByte();
  321.             BitPos = 0;
  322.         }
  323.         else
  324.             BitPos++;
  325.         
  326.         if ((InByte & BitMask[BitPos]) == 0)
  327.             A = Left[A];
  328.         else
  329.             A = Right[A];
  330.     } while (A <= PredMax);
  331.     
  332.     /* Update the code tree */
  333.     A -= MaxChar;
  334.     Splay(A);
  335.     
  336.     /* return the character */
  337.     return A;
  338. }
  339.  
  340. /* uncompress the file and write output */
  341. void ExpandFile(void)
  342. {
  343.     /* force buffer load first time */
  344.     Index = 0;
  345.     InSize = 0;
  346.     /* nothing in output buffer */
  347.     OutSize = 0;
  348.     /* force bit buffer load first time */
  349.     BitPos = 7;
  350.     
  351.     /* read and expand the compressed input */
  352.     OutByte = Expand();
  353.     while (OutByte != EofChar)
  354.     {
  355.         WriteByte();
  356.         OutByte = Expand();
  357.     }
  358.     
  359.     /* flush the output buffer */
  360.     FlushOutBuffer();
  361. }
  362.  
  363. int main(int argc, char *argv[])
  364. {
  365.  
  366.     if (argc < 3)
  367.     {
  368.         printf(Usage);
  369.         exit(1);
  370.     }
  371.     
  372.     if (argc == 4 && (strlen(argv[1]) == 1) && toupper(argv[1][0]) == 'X')
  373.     {
  374.         strcpy(InName, argv[2]);
  375.         strcpy(OutName, argv[3]);
  376.         CompressFlag = false;
  377.     }
  378.     else
  379.     {
  380.         if (argc == 4)
  381.         {
  382.             printf(Usage);
  383.             exit(1);
  384.         }
  385.         CompressFlag = true;
  386.         strcpy(InName, argv[1]);
  387.         strcpy(OutName, argv[2]);
  388.     }
  389.         
  390.     InitializeSplay();
  391.     
  392.     if ((InF = fopen(InName, "rb")) == NULL)
  393.     {
  394.         printf("Unable to open input file: %s\n", InName);
  395.         exit(1);
  396.     }
  397.     if ((OutF = fopen(OutName, "wb")) == NULL)
  398.     {
  399.         printf("Unable to open output file: %s\n", OutName);
  400.         exit(1);
  401.     }
  402.     
  403.     if (CompressFlag)
  404.         CompressFile();
  405.     else
  406.     {
  407.         ReadHeader();
  408.         ExpandFile();
  409.     }
  410.     
  411.     fclose(InF);
  412.     fclose(OutF);
  413.     
  414.     return 0;
  415. }
  416.