home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / pascal / LZRW.ZIP / LZRW2.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-01-19  |  39.4 KB  |  676 lines
  1. /******************************************************************************/
  2. /*                                                                            */
  3. /*                                    LZRW2.C                                 */
  4. /*                                                                            */
  5. /******************************************************************************/
  6. /*                                                                            */
  7. /* Author  : Ross Williams.                                                   */
  8. /* Date    : 29-Jun-1991.                                                     */
  9. /* Release : 1.                                                               */
  10. /*                                                                            */
  11. /******************************************************************************/
  12. /*                                                                            */
  13. /* This file contains an implementation of the LZRW2 data compression         */
  14. /* algorithm in C.                                                            */
  15. /*                                                                            */
  16. /* The algorithm is a general purpose compression algorithm that runs fast    */
  17. /* and gives reasonable compression. The algorithm is a member of the Lempel  */
  18. /* Ziv family of algorithms and bases its compression on the presence in the  */
  19. /* data of repeated substrings.                                               */
  20. /*                                                                            */
  21. /* This algorithm is unpatented and the code is public domain. As the         */
  22. /* algorithm is based on the LZ77 class of algorithms, it is unlikely to be   */
  23. /* the subject of a patent challenge.                                         */
  24. /*                                                                            */
  25. /* Unlike the LZRW1 and LZRW1-A algorithms, the LZRW2 algorithm is            */
  26. /* deterministic and is guaranteed to yield the same compressed               */
  27. /* representation for a given file each time it is run.                       */
  28. /*                                                                            */
  29. /* The LZRW2 algorithm was originally designed and implemented                */
  30. /* by Ross Williams on 25-Nov-1990.                                           */
  31. /*                                                                            */
  32. /* Here are the results of applying this code compiled under THINK C 4.0 and  */
  33. /* running on a Mac-SE (8MHz 68000) to the standard calgary corpus.           */
  34. /*                                                                            */
  35. /*    +----------------------------------------------------------------+      */
  36. /*    | DATA COMPRESSION TEST                                          |      */
  37. /*    | =====================                                          |      */
  38. /*    | Time of run     : Sat 29-Jun-1991 01:24PM                      |      */
  39. /*    | Timing accuracy : One part in 100                              |      */
  40. /*    | Context length  : 262144 bytes (= 256.0000K)                   |      */
  41. /*    | Test suite      : Calgary Corpus Suite                         |      */
  42. /*    | Files in suite  : 14                                           |      */
  43. /*    | Algorithm       : LZRW2                                        |      */
  44. /*    | Note: All averages are calculated from the un-rounded values.  |      */
  45. /*    +----------------------------------------------------------------+      */
  46. /*    | File Name   Length  CxB  ComLen  %Remn  Bits  Com K/s  Dec K/s |      */
  47. /*    | ----------  ------  ---  ------  -----  ----  -------  ------- |      */
  48. /*    | rpus:Bib.D  111261    1   58726   52.8  4.22    16.98    52.36 |      */
  49. /*    | us:Book1.D  768771    3  491413   63.9  5.11    14.82    47.04 |      */
  50. /*    | us:Book2.D  610856    3  331932   54.3  4.35    17.10    51.28 |      */
  51. /*    | rpus:Geo.D  102400    1   84118   82.1  6.57    10.81    41.67 |      */
  52. /*    | pus:News.D  377109    2  215652   57.2  4.57    15.20    50.68 |      */
  53. /*    | pus:Obj1.D   21504    1   13032   60.6  4.85    13.13    50.15 |      */
  54. /*    | pus:Obj2.D  246814    1  119078   48.2  3.86    17.81    55.01 |      */
  55. /*    | s:Paper1.D   53161    1   28269   53.2  4.25    17.16    51.92 |      */
  56. /*    | s:Paper2.D   82199    1   46789   56.9  4.55    16.58    49.96 |      */
  57. /*    | rpus:Pic.D  513216    2  123311   24.0  1.92    33.17    71.63 |      */
  58. /*    | us:Progc.D   39611    1   19959   50.4  4.03    17.65    53.36 |      */
  59. /*    | us:Progl.D   71646    1   28571   39.9  3.19    22.63    59.13 |      */
  60. /*    | us:Progp.D   49379    1   19544   39.6  3.17    22.52    59.45 |      */
  61. /*    | us:Trans.D   93695    1   35364   37.7  3.02    22.87    60.89 |      */
  62. /*    +----------------------------------------------------------------+      */
  63. /*    | Average     224401    1  115411   51.5  4.12    18.46    53.89 |      */
  64. /*    +----------------------------------------------------------------+      */
  65. /*                                                                            */
  66. /******************************************************************************/
  67.  
  68.                             /* INCLUDE FILES                                  */
  69.                             /* =============                                  */
  70. #include "port.h"           /* Defines symbols for the non portable stuff.    */
  71. #include "compress.h"       /* Defines single exported function "compress".   */
  72. #include "fast_copy.h"      /* Fast memory copy routine.                      */
  73.  
  74. /******************************************************************************/
  75.  
  76. /* The following structure is returned by the "compress" function below when  */
  77. /* the user asks the function to return identifying information.              */
  78. /* The most important field in the record is the working memory field which   */
  79. /* tells the calling program how much working memory should be passed to      */
  80. /* "compress" when it is called to perform a compression or decompression.    */
  81. /* For the LZRW2 algorithm, the decompressor requires less memory than the    */
  82. /* decompressor (so I have defined two constants) but the interface standard  */
  83. /* I am using only allows a single memory size for both compression and       */
  84. /* decompression so I put in the larger: CMP_MEM_REQ.                         */
  85. /* Note: CMP_MEM_REQ~=24K, DEC_MEM_REQ~=16K.                                  */
  86. /* For more information on this structure see "compress.h".                   */
  87.   
  88. #define U(X)            ((ULONG) X)
  89. #define SIZE_P_BYTE     (U(sizeof(UBYTE *)))
  90. #define SIZE_WORD       (U(sizeof(UWORD  )))
  91. #define ALIGNMENT_FUDGE (U(100))
  92. #define CMP_MEM_REQ ( U(4096)*(SIZE_P_BYTE+SIZE_WORD) + ALIGNMENT_FUDGE )
  93. #define DEC_MEM_REQ ( U(4096)*(SIZE_P_BYTE          ) + ALIGNMENT_FUDGE )
  94.  
  95. static struct compress_identity identity =
  96. {
  97.  U(0x3D8F733A),                           /* Algorithm identification number. */
  98.  CMP_MEM_REQ,                             /* Working memory (bytes) required. */
  99.  "LZRW2",                                 /* Name of algorithm.               */
  100.  "1.0",                                   /* Version number of algorithm.     */
  101.  "25-Nov-1990",                           /* Date of algorithm.               */
  102.  "Public Domain",                         /* Copyright notice.                */
  103.  "Ross N. Williams",                      /* Author of algorithm.             */
  104.  "Renaissance Software",                  /* Affiliation of author.           */
  105.  "Public Domain"                          /* Vendor of algorithm.             */
  106. };
  107.  
  108. void compress_compress  (UBYTE *,UBYTE *,ULONG,UBYTE *,ULONG *);
  109. void compress_decompress(UBYTE *,UBYTE *,ULONG,UBYTE *,ULONG *);
  110.  
  111. /******************************************************************************/
  112.  
  113. /* This function is the only function exported by this module.                */
  114. /* Depending on its first parameter, the function can be requested to         */
  115. /* compress a block of memory, decompress a block of memory, or to identify   */
  116. /* itself. For more information, see the specification file "compress.h".     */
  117.  
  118. EXPORT void compress(action,wrk_mem,src_adr,src_len,dst_adr,p_dst_len)
  119. UWORD     action;      /* Action to be performed.                             */
  120. UBYTE   *wrk_mem;      /* Address of working memory we can use.               */
  121. UBYTE   *src_adr;      /* Address of input data.                              */
  122. ULONG    src_len;      /* Length  of input data.                              */
  123. UBYTE   *dst_adr;      /* Address to put output data.                         */
  124. ULONG *p_dst_len;      /* Address of longword for length of output data.      */
  125. {
  126.  switch (action)
  127.    {
  128.     case COMPRESS_ACTION_IDENTITY:
  129.        *p_dst_len=(ULONG) &identity;
  130.        break;
  131.     case COMPRESS_ACTION_COMPRESS:
  132.        compress_compress(wrk_mem,src_adr,src_len,dst_adr,p_dst_len);
  133.        break;
  134.     case COMPRESS_ACTION_DECOMPRESS:
  135.        compress_decompress(wrk_mem,src_adr,src_len,dst_adr,p_dst_len);
  136.        break;
  137.    }
  138. }
  139.  
  140. /******************************************************************************/
  141. /*                                                                            */
  142. /* BRIEF DESCRIPTION OF THE LZRW2 ALGORITHM                                   */
  143. /* ========================================                                   */
  144. /* The LZRW2 algorithm is identical to the LZRW1-A algorithm except that it   */
  145. /* employs a PHRASE TABLE. The phrase table contains pointers to the first    */
  146. /* byte of the most recent 4096 phrases processed. A phrase is defined to be  */
  147. /* a sequence of one or more bytes that are coded as a single literal or copy */
  148. /* item. Instead of coding a copy item as a length and an offset as LZRW1     */
  149. /* does, LZRW2 codes a copy item as a length and a phrase table index. The    */
  150. /* result is that LZRW2 can point far further back than LZRW1 but without     */
  151. /* increasing the number of bits allocated to the 'offset' in the coding. The */
  152. /* phrase table is incapable of pointing within phrases, but LZRW1 was        */
  153. /* incapabale of doing that anyway because it only ever updated its hash      */
  154. /* table on phrase boundaries.                                                */
  155. /*                                                                            */
  156. /* Updating the phrase table involves just writing a pointer to the next      */
  157. /* position (which circulates) in the phrase table after each literal or      */
  158. /* copy item is coded. The decompressor needs to maintain a phrase table but  */
  159. /* not a hash table.                                                          */
  160. /*                                                                            */
  161. /* Use of the phrase table yields a 3% absolute to 5% absolute improvement    */
  162. /* over LZRW1-A in compression, does not affect compression speed, but        */
  163. /* reduces decompression speed by about 30%. Thus LZRW2 does not dominate     */
  164. /* LZRW1-A, as LZRW1-A does LZRW1.                                            */
  165. /*                                                                            */
  166. /* An extra 3% absolute compression can be obtained by using a hash table of  */
  167. /* depth two. However, increasing the depth above one incurs a 40% decrease   */
  168. /* in compression speed which was not considered worthwhile. Another reason   */
  169. /* for keeping the depth down to one was to allow easy comparison with the    */
  170. /* LZRW1-A algorithm so as to demonstrate the exact effect of the phrase      */
  171. /* table.                                                                     */
  172. /*                                                                            */
  173. /*                +---+             +---+                                     */
  174. /*                |___|4095         |___|4095                                 */
  175. /*                |___|             |___|                                     */
  176. /*         Next-->|___|       +-------*_|<---+   /----+---\                   */
  177. /*     (circles   |___|       |     |___|    +---|Hash    |                   */
  178. /*      through +---*_|<------+     |___|        |Function|                   */
  179. /*      phrase  | |___|             |___|        \--------/                   */
  180. /*      table)  | |___|0            |___|0            ^                       */
  181. /*              | +---+             +---+             |                       */
  182. /*              | Phrase            Hash        +-----+                       */
  183. /*              | Table             Table       |                             */
  184. /*              |                              ---                            */
  185. /*              v                              ^^^                            */
  186. /*      +-------------------------------------|----------------+              */
  187. /*      ||||||||||||||||||||||||||||||||||||||||||||||||||||||||              */
  188. /*      +-------------------------------------|----------------+              */
  189. /*      |                                     |1......18|      |              */
  190. /*      |<------- Lempel=History ------------>|<--Ziv-->|      |              */
  191. /*      |     (=bytes already processed)      |<-Still to go-->|              */
  192. /*      |<-------------------- INPUT BLOCK ------------------->|              */
  193. /*                                                                            */
  194. /*  LZRW2 Algorithm Execution Summary                                         */
  195. /*  ---------------------------------                                         */
  196. /*  1. Hash the first three bytes of the Ziv to yield a hash table index h.   */
  197. /*  2. Look up the hash table yielding phrase table index i.                  */
  198. /*  3. Look up phrase i yielding a pointer p to the Lempel.                   */
  199. /*  4. Overwrite the 'next' cyclic entry in the phrase table with a pointer   */
  200. /*     to the Ziv. Increment the 'next' index (mod 4096).                     */
  201. /*  5. Overwrite hash table entry h with the index of the overwritten         */
  202. /*     position of step 4.                                                    */
  203. /*  6. Match where p points with the Ziv. If there is a match of three or     */
  204. /*     more bytes, code those bytes (in the Ziv) as a copy item, otherwise    */
  205. /*     code the next byte in the Ziv as a literal item.                       */
  206. /*                                                                            */
  207. /******************************************************************************/
  208. /*                                                                            */
  209. /*                     DEFINITION OF COMPRESSED FILE FORMAT                   */
  210. /*                     ====================================                   */
  211. /*  * A compressed file consists of a COPY FLAG followed by a REMAINDER.      */
  212. /*  * The copy flag CF uses up four bytes with the first byte being the       */
  213. /*    least significant.                                                      */
  214. /*  * If CF=1, then the compressed file represents the remainder of the file  */
  215. /*    exactly. Otherwise CF=0 and the remainder of the file consists of zero  */
  216. /*    or more GROUPS, each of which represents one or more bytes.             */
  217. /*  * Each group consists of two bytes of CONTROL information followed by     */
  218. /*    sixteen ITEMs except for the last group which can contain from one      */
  219. /*    to sixteen items.                                                       */
  220. /*  * An item can be either a LITERAL item or a COPY item.                    */
  221. /*  * Each item corresponds to a bit in the control bytes.                    */
  222. /*  * The first control byte corresponds to the first 8 items in the group    */
  223. /*    with bit 0 corresponding to the first item in the group and bit 7 to    */
  224. /*    the eighth item in the group.                                           */
  225. /*  * The second control byte corresponds to the second 8 items in the group  */
  226. /*    with bit 0 corresponding to the ninth item in the group and bit 7 to    */
  227. /*    the sixteenth item in the group.                                        */
  228. /*  * A zero bit in a control word means that the corresponding item is a     */
  229. /*    literal item. A one bit corresponds to a copy item.                     */
  230. /*  * A literal item consists of a single byte which represents itself.       */
  231. /*  * A copy item consists of two bytes that represent from 3 to 18 bytes.    */
  232. /*  * The first  byte in a copy item will be denoted C1.                      */
  233. /*  * The second byte in a copy item will be denoted C2.                      */
  234. /*  * Bits will be selected using square brackets.                            */
  235. /*    For example: C1[0..3] is the low nibble of the first control byte.      */
  236. /*    of copy item C1.                                                        */
  237. /*  * The LENGTH of a copy item is defined to be C1[0..3]+3 which is a number */
  238. /*    in the range [3,18].                                                    */
  239. /*  * The INDEX of a copy item is defined to be C1[4..7]*256+C2[0..8] which   */
  240. /*    is a number in the range [0,4095].                                      */
  241. /*  * A copy item represents the sequence of bytes                            */
  242. /*       text[POS-OFFSET..POS-OFFSET+LENGTH-1] where                          */
  243. /*          text   is the entire text of the uncompressed string.             */
  244. /*          POS    is the index in the text of the character following the    */
  245. /*                   string represented by all the items preceeding the item  */
  246. /*                   being defined.                                           */
  247. /*          OFFSET is obtained from INDEX by looking up the phrase table.     */
  248. /*                                                                            */
  249. /******************************************************************************/
  250.  
  251. /* Stylistic note: The LZRW1 algorithm was written in an extremely terse      */
  252. /* style because it had to fit on a single page in a paper. This style        */
  253. /* carried over to the LZRW1-A algorithm.  However, LZRW2 has not been        */
  254. /* published and so I have reverted to my normal programming style.           */
  255.  
  256. /* Stylistic note: This code could be considerably neated by the use of       */
  257. /* dependent declarations such as {int a=3,b=a+1;}. However I can't locate a  */
  258. /* clause in K&R that guarantees that declarations are evaluated in order.    */
  259.    
  260. /* The following #define defines the length of the copy flag that appears at  */
  261. /* the start of the compressed file. The value of four bytes was chosen       */
  262. /* because the fast_copy routine on my Macintosh runs faster if the source    */
  263. /* and destination blocks are relatively longword aligned.                    */
  264. /* The actual flag data appears in the first byte. The rest are zeroed so as  */
  265. /* to normalize the compressed representation (i.e. not non-deterministic).   */
  266. #define FLAG_BYTES 4
  267.  
  268. /* The following #defines define the meaning of the values of the copy        */
  269. /* flag at the start of the compressed file.                                  */
  270. #define FLAG_COMPRESS 0     /* Signals that output was result of compression. */
  271. #define FLAG_COPY     1     /* Signals that output was simply copied over.    */
  272.  
  273. /* The 68000 microprocessor (on which this algorithm was originally developed */
  274. /* is fussy about non-aligned arrays of words. To avoid these problems the    */
  275. /* following macro can be used to "waste" from 0 to 3 bytes so as to align    */
  276. /* the argument pointer.                                                      */
  277. #define ULONG_ALIGN_UP(X) ((((ULONG)X)+3)&~3)
  278.  
  279. /* The following constant defines the maximum length of an uncompressed item. */
  280. /* This definition must not be changed; its value is hardwired into the code. */
  281. /* The longest number of bytes that can be spanned by a single item is 18     */
  282. /* for the longest copy item.                                                 */
  283. #define MAX_RAW_ITEM (18)
  284.  
  285. /* The following constant defines the maximum length of an uncompressed group.*/
  286. /* This definition must not be changed; its value is hardwired into the code. */
  287. /* A group contains at most 16 items which explains this definition.          */
  288. #define MAX_RAW_GROUP (16*MAX_RAW_ITEM)
  289.  
  290. /* The following constant defines the maximum length of a compressed group.   */
  291. /* This definition must not be changed; its value is hardwired into the code. */
  292. /* A compressed group consists of two control bytes followed by up to 16      */
  293. /* compressed items each of which can have a maximum length of two bytes.     */
  294. #define MAX_CMP_GROUP (2+16*2)
  295.  
  296. /* The following constant defines the number of entries in the phrase table.  */
  297. /* This definition must not be changed; its value is hardwired into the code. */
  298. #define PHRASE_TABLE_LENGTH (4096)
  299.  
  300. /* The following constant defines the number of entries in the hash table.    */
  301. /* This definition must not be changed; its value is hardwired into the code. */
  302. #define HASH_TABLE_LENGTH (4096)
  303.  
  304. /* At initialization, the hash table entries are all set to point to element  */
  305. /* zero of the phrase table. In order for the algorithm to start up,          */
  306. /* phrase[0] needs to point to a well defined string of at least 18 bytes. At */
  307. /* startup, there is no already-transmitted source text to point to and so    */
  308. /* we have to invent some dummy text to point to. It doesn't matter what is   */
  309. /* in this string so long as it is at least MAX_RAW_ITEM bytes long and is    */
  310. /* the same in the compressor and decompressor. I chose consecutive decimal   */
  311. /* digits because they do not have white space problems (e.g. there is no     */
  312. /* chance that the compiler will replace more than one space by a TAB) and    */
  313. /* because they make the length of the string obvious by inspection.          */
  314. #define START_STRING_18 "123456789012345678"
  315.  
  316. /******************************************************************************/
  317.                             
  318. LOCAL void compress_compress
  319.            (p_wrk_mem,p_src_first,src_len,p_dst_first,p_dst_len)
  320. /* Input  : Hand over the required amount of working memory in p_wrk_mem.     */
  321. /* Input  : Specify input block using p_src_first and src_len.                */
  322. /* Input  : Point p_dst_first to the start of the output zone (OZ).           */
  323. /* Input  : Point p_dst_len to a ULONG to receive the output length.          */
  324. /* Input  : Input block and output zone must not overlap.                     */
  325. /* Output : Length of output block written to *p_dst_len.                     */
  326. /* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. May   */
  327. /* Output : write in OZ=Mem[p_dst_first..p_dst_first+src_len+MAX_CMP_GROUP-1].*/
  328. /* Output : Upon completion guaranteed *p_dst_len<=src_len+FLAG_BYTES.        */
  329. UBYTE *p_wrk_mem;
  330. UBYTE *p_src_first;
  331. ULONG  src_len;
  332. UBYTE *p_dst_first;
  333. ULONG *p_dst_len;
  334. {
  335.  /* p_src and p_dst step through the source and destination blocks.           */
  336.  register UBYTE *p_src = p_src_first;
  337.  register UBYTE *p_dst = p_dst_first;
  338.  
  339.  /* The following variables are never modified and are used in the            */
  340.  /* calculations that determine when the main loop terminates.                */
  341.  UBYTE *p_src_post  = p_src_first+src_len;
  342.  UBYTE *p_dst_post  = p_dst_first+src_len;
  343.  UBYTE *p_src_max1  = p_src_first+src_len-MAX_RAW_ITEM;
  344.  UBYTE *p_src_max16 = p_src_first+src_len-MAX_RAW_ITEM*16;
  345.  
  346.  /* The variables 'p_control' and 'control' are used to buffer control bits.  */
  347.  /* Before each group is processed, the next two bytes of the output block    */
  348.  /* are set aside for the control word for the group about to be processed.   */
  349.  /* 'p_control' is set to point to the first byte of that word. Meanwhile,    */
  350.  /* 'control' buffers the control bits being generated during the processing  */
  351.  /* of the group. Instead of having a counter to keep track of how many items */
  352.  /* have been processed (=the number of bits in the control word), at the     */
  353.  /* start of each group, the top word of 'control' is filled with 1 bits.     */
  354.  /* As 'control' is shifted for each item, the 1 bits in the top word are     */
  355.  /* absorbed or destroyed. When they all run out (i.e. when the top word is   */
  356.  /* all zero bits, we know that we are at the end of a group.                 */
  357.  #define TOPWORD 0xFFFF0000
  358.  UBYTE *p_control;
  359.  ULONG  control=TOPWORD;
  360.  
  361.  UWORD  *hash;           /* Points to the first element of the hash table.    */
  362.  UBYTE **phrase;         /* Points to the first element of the phrase table.  */
  363.  register UWORD next;    /* Index of next phrase entry to be overwritten.     */
  364.  
  365.  /* Set up the hash table and the phrase table in the memory given to         */
  366.  /* the algorithm. These tables are the only occupants of the memory.         */
  367.  hash          = (UWORD *)  ULONG_ALIGN_UP(p_wrk_mem); 
  368.  phrase        = (UBYTE **) ULONG_ALIGN_UP(&hash[HASH_TABLE_LENGTH]);
  369.  
  370.  /* The variable 'next' cycles through the phrase table indicating the next   */
  371.  /* position in the table to write a new phrase pointer.                      */
  372.  next=0; 
  373.  
  374.  /* To start, we write the flag bytes. Being optimistic, we set the flag to   */
  375.  /* FLAG_COMPRESS. The remaining flag bytes are zeroed so as to keep the      */
  376.  /* algorithm deterministic.                                                  */
  377.  *p_dst++=FLAG_COMPRESS;
  378.  {UWORD i; for (i=2;i<=FLAG_BYTES;i++) *p_dst++=0;}
  379.  
  380.  /* Reserve the first word of output as the control word for the first group. */
  381.  /* Note: This is undone at the end if the input block is empty.              */
  382.  p_control=p_dst; p_dst+=2;
  383.  
  384.  /* Initialize the hash table and the phrase table. The hash table entries    */
  385.  /* all point to element zero of the phrase table which in turn points to     */
  386.  /* a constant string. The remainder of the phrase table does not need to     */
  387.  /* be initialized as the algorithm is arranged so that no element of the     */
  388.  /* phrase table is ever read before it has been written.                     */
  389.  /* In theory, either the hash table or the phrase table has to be            */
  390.  /* initialized. I chose the hash table as this choice yields determinism.    */
  391.  {register UWORD i,*t=hash;
  392.   #define ZH *t++=0; *t++=0; *t++=0; *t++=0 
  393.   for (i=0;i<256;i++) {ZH;ZH;ZH;ZH;}  /* 256=HASH_TABLE_LENGTH/16 */
  394.  }
  395.  phrase[0]=(UBYTE *) START_STRING_18;
  396.  
  397.  /* The main loop processes either 1 or 16 items per iteration. As its        */
  398.  /* termination logic is complicated, I have opted for an infinite loop       */
  399.  /* structure containing 'break' and 'goto' statements.                       */
  400.  while (TRUE)
  401.    {/* Begin main processing loop. */
  402.    
  403.      register UBYTE *p;         /* Scans through targ phrase during matching. */
  404.      register UBYTE *p_ziv;     /* Points to first byte of current Ziv.       */
  405.      register UWORD phrase_num; /* Current phrase number (index in phr tab).  */
  406.      register UWORD unroll;     /* Loop counter for unrolled inner loop.      */
  407.      register UWORD *p_hte;     /* Pointer to the current hash table entry.   */
  408.  
  409.     /* Test for overrun and jump to overrun code if necessary. */
  410.     if (p_dst>p_dst_post)
  411.        goto overrun;
  412.        
  413.     /* The following cascade of if statements efficiently catches and deals   */
  414.     /* with varying degrees of closeness to the end of the input block.       */
  415.     /* When we get very close to the end, we stop updating the tables and     */
  416.     /* code the remaining bytes as literals. This makes the code simpler.     */
  417.     unroll=16;
  418.     if (p_src>p_src_max16)
  419.       {
  420.        unroll=1;
  421.        if (p_src>p_src_max1)
  422.          {
  423.           if (p_src==p_src_post)
  424.              break;
  425.           else
  426.              goto literal;
  427.          }
  428.       }
  429.          
  430.     /* This inner unrolled loop processes 'unroll' (whose value is either 1   */
  431.     /* or 16) items. I have chosen to implement this loop with labels and     */
  432.     /* gotos to heighten the ease with which the loop may be implemented with */
  433.     /* a single decrement and branch instruction in assembly language and     */
  434.     /* also because the labels act as highly readable place markers.          */
  435.     /* (Also because we jump into the loop for endgame literals (see above)). */
  436.     
  437.     begin_unrolled_loop:
  438.     
  439.        /* To process the next phrase, we hash the next three bytes and use    */
  440.        /* the resultant hash table index to look up the hash table. A pointer */
  441.        /* to the entry is stored in p_he. We store a pointer instead of an    */
  442.        /* index so as to avoid array lookups. The hash table entry contains a */
  443.        /* phrase number 'phrase_num' which we use to look up the phrase table */
  444.        /* and get a pointer 'p' to a potential match in the history.          */
  445.        p_hte=&hash[((40543*((p_src[0]<<8)^(p_src[1]<<4)^p_src[2]))>>4) & 0xFFF];
  446.        phrase_num=*p_hte;
  447.        p=phrase[phrase_num];
  448.        
  449.        /* Update the hash table and phrase table. The next element of the     */
  450.        /* phrase table points to the first byte of the current Ziv and the    */
  451.        /* hash table entry we looked up gets overwritten with the phrase      */
  452.        /* table entry number. Wraparound of 'next' is done elsewhere.         */
  453.        *p_hte=next;
  454.        phrase[next++]=p_src;
  455.  
  456.        /* Having looked up the candidate position, we are in a position to    */
  457.        /* attempt a match. The match loop has been unrolled using the PS      */
  458.        /* macro so that failure within the first three bytes automatically    */
  459.        /* results in the literal branch being taken. The coding is simple.    */
  460.        /* p_ziv saves p_src so we can let p_src wander.                       */
  461.        #define PS *p++!=*p_src++
  462.        p_ziv=p_src;
  463.        if (PS || PS || PS)
  464.          {p_src=p_ziv; literal:*p_dst++=*p_src++; control&=0xFFFEFFFF;}
  465.        else
  466.          {
  467.           PS || PS || PS || PS || PS || PS || PS || PS ||
  468.           PS || PS || PS || PS || PS || PS || PS || p_src++;
  469.           *p_dst++=((phrase_num&0xF00)>>4)|(--p_src-p_ziv-3);
  470.           *p_dst++=phrase_num&0xFF;
  471.          }
  472.        control>>=1;
  473.                 
  474.        /* This loop is all set up for a decrement and jump instruction! */
  475.     end_unrolled_loop: if (--unroll) goto begin_unrolled_loop;
  476.  
  477.     /* At this point it will nearly always be the end of a group in which     */
  478.     /* case, we have to do some control-word processing. However, near the    */
  479.     /* end of the input block, the inner unrolled loop is only executed once. */
  480.     /* This necessitates the 'if' test.                                       */
  481.     if ((control&TOPWORD)==0)
  482.       {
  483.        /* Write the control word to the place we saved for it in the output. */
  484.        *p_control++=  control     &0xFF;
  485.        *p_control  = (control>>8) &0xFF;
  486.  
  487.        /* Reserve the next word in the output block for the control word */
  488.        /* for the group about to be processed.                           */
  489.        p_control=p_dst; p_dst+=2;
  490.        
  491.        /* Reset the control bits buffer. */
  492.        control=TOPWORD;
  493.        
  494.        /* The following statement makes sure that the 'next' phrase table     */
  495.        /* index cycles when it comes to the end of the phrase table. This     */
  496.        /* can be included here within the control word processing because the */
  497.        /* control word processing happens once every 16 items processed and   */
  498.        /* 4096 (the num of entries in the phrase table) is a multiple of 16.  */
  499.        next&=0xFFF;
  500.       }
  501.           
  502.    } /* End main processing loop. */
  503.    
  504.  /* After the main processing loop has executed, all the input bytes have     */
  505.  /* been processed. However, the control word has still to be written to the  */
  506.  /* word reserved for it in the output at the start of the most recent group. */
  507.  /* Before writing, the control word has to be shifted so that all the bits   */
  508.  /* are in the right place. The "empty" bit positions are filled with 1s      */
  509.  /* which partially fill the top word.                                        */
  510.  while(control&TOPWORD) control>>=1;
  511.  *p_control++= control     &0xFF;
  512.  *p_control++=(control>>8) &0xFF;
  513.  
  514.  /* If the last group contained no items, delete the control word too.        */
  515.  if (p_control==p_dst) p_dst-=2;
  516.  
  517.  /* Write the length of the output block to the dst_len parameter and return. */
  518.  *p_dst_len=p_dst-p_dst_first;                           
  519.  return;
  520.  
  521.  /* Jump here as soon as an overrun is detected. An overrun is defined to     */
  522.  /* have occurred if p_dst>p_dst_first+src_len. That is, the moment the       */
  523.  /* length of the output written so far exceeds the length of the input block.*/
  524.  /* The algorithm checks for overruns at least at the end of each group       */
  525.  /* which means that the maximum overrun is MAX_CMP_GROUP bytes.              */
  526.  /* Once an overrun occurs, the only thing to do is to set the copy flag and  */
  527.  /* copy the input over.                                                      */
  528.  overrun:
  529.  *p_dst_first=FLAG_COPY;
  530.  fast_copy(p_src_first,p_dst_first+FLAG_BYTES,src_len);
  531.  *p_dst_len=src_len+FLAG_BYTES;
  532. }
  533.  
  534. /******************************************************************************/
  535.  
  536. LOCAL void compress_decompress
  537.            (p_wrk_mem,p_src_first,src_len,p_dst_first,p_dst_len)
  538. /* Input  : Hand over the required amount of working memory in p_wrk_mem.     */
  539. /* Input  : Specify input block using p_src_first and src_len.                */
  540. /* Input  : Point p_dst_first to the start of the output zone.                */
  541. /* Input  : Point p_dst_len to a ULONG to receive the output length.          */
  542. /* Input  : Input block and output zone must not overlap. User knows          */
  543. /* Input  : upperbound on output block length from earlier compression.       */
  544. /* Input  : In any case, maximum expansion possible is nine times.            */
  545. /* Output : Length of output block written to *p_dst_len.                     */
  546. /* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1].       */
  547. /* Output : Writes only  in Mem[p_dst_first..p_dst_first+*p_dst_len-1].       */
  548. UBYTE *p_wrk_mem;
  549. UBYTE *p_src_first;
  550. ULONG  src_len;
  551. UBYTE *p_dst_first;
  552. ULONG *p_dst_len;
  553. {
  554.  /* Byte pointers p_src and p_dst scan through the input and output blocks.   */
  555.  register UBYTE *p_src = p_src_first+FLAG_BYTES;
  556.  register UBYTE *p_dst = p_dst_first;
  557.  
  558.  /* The following two variables are never modified and are used to control    */
  559.  /* the main loop.                                                            */
  560.  UBYTE *p_src_post  = p_src_first+src_len;
  561.  UBYTE *p_src_max16 = p_src_first+src_len-(MAX_CMP_GROUP-2);
  562.  
  563.  /* The variable 'control' is used to buffer the control bits which appear in */
  564.  /* groups of 16 bits (control words) at the start of each compressed group.  */
  565.  /* When each group is read, bit 16 of the register is set to one. Whenever   */
  566.  /* a new bit is needed, the register is shifted right. When the value of the */
  567.  /* register becomes 1, we know that we have reached the end of a group.      */
  568.  /* Initializing the register to 1 thus instructs the code to follow that it  */
  569.  /* should read a new control word immediately.                               */
  570.  register ULONG control=1;
  571.  
  572.  /* The phrase table is the same as in the compressor. The decompressor does  */
  573.  /* not need to maintain a hash table, only a phrase table.                   */
  574.  /* The phrase table is the only occupant of the working memory.              */
  575.  UBYTE **phrase = (UBYTE **) ULONG_ALIGN_UP(p_wrk_mem);
  576.  
  577.  /* The next variable cycles through the phrase table always containing the   */
  578.  /* index of the next phrase pointer to be overwritten in the phrase table.   */
  579.  /* Optimization note: I tried using a pointer to cycle through the table but */
  580.  /* this went more slowly than using an explicit index.                       */
  581.  register UWORD next=0;
  582.       
  583.  /* Check the leading copy flag to see if the compressor chose to use a copy  */
  584.  /* operation instead of a compression operation. If a copy operation was     */
  585.  /* used, then all we need to do is copy the data over, set the output length */
  586.  /* and return.                                                               */
  587.  if (*p_src_first==FLAG_COPY)
  588.    {
  589.     fast_copy(p_src_first+FLAG_BYTES,p_dst_first,src_len-FLAG_BYTES);
  590.     *p_dst_len=src_len-FLAG_BYTES;
  591.     return;
  592.    }
  593.    
  594.  /* Whereas the compressor needs to maintain a hash table and a phrase table  */
  595.  /* the decompressor needs to maintain only the phrase table. Only the first  */
  596.  /* entry of the phrase table needs initializing as, apart from this entry,   */
  597.  /* the compressor guarantees not to refer to a table entry until the entry   */
  598.  /* has been written.                                                         */
  599.  phrase[0]=(UBYTE *) START_STRING_18;
  600.     
  601.  /* The outer loop processes either 1 or 16 items per iteration depending on  */
  602.  /* how close p_src is to the end of the input block.                         */
  603.  while (p_src!=p_src_post)
  604.    {/* Start of outer loop */
  605.    
  606.     register UWORD unroll;   /* Counts unrolled loop executions.              */
  607.     
  608.     /* When 'control' has the value 1, it means that the 16 buffered control  */
  609.     /* bits that were read in at the start of the current group have all been */
  610.     /* shifted out and that all that is left is the 1 bit that was injected   */
  611.     /* into bit 16 at the start of the current group. When we reach the end   */
  612.     /* of a group, we have to load a new control word and inject a new 1 bit. */
  613.     if (control==1)
  614.       {
  615.        control=0x10000|*p_src++;
  616.        control|=(*p_src++)<<8;
  617.       
  618.        /* Because 4096 (the number of entries in the phrase table) is a       */
  619.        /* multiple of 16 (the loop unrolling), and 'unroll' has the value 1   */
  620.        /* or 16 and never increases its initial value, this wraparound check  */
  621.        /* need only be done once per main loop. In fact it can even reside    */
  622.        /* within this 'if'.                                                   */
  623.        next&=0xFFF;
  624.       }
  625.  
  626.     /* If it is possible that we are within 16 groups from the end of the     */
  627.     /* input, execute the unrolled loop only once, else process a whole group */
  628.     /* of 16 items by looping 16 times.                                       */
  629.     unroll= p_src<=p_src_max16 ? 16 : 1;
  630.  
  631.     /* This inner loop processes one phrase (item) per iteration. */
  632.     while (unroll--)
  633.       { /* Begin unrolled inner loop. */
  634.       
  635.        /* Process a literal or copy item depending on the next control bit. */
  636.        if (control&1)
  637.          { /* Copy item. */
  638.           register UWORD lenmt; /* Length of copy item minus three.           */
  639.           register UBYTE *p;    /* Points to history posn from which to copy. */
  640.           
  641.           /* Read and dismantle the copy word. Work out from where to copy.   */
  642.           lenmt=*p_src++;
  643.           p=phrase[((lenmt&0xF0)<<4)|*p_src++];
  644.           lenmt&=0xF;
  645.  
  646.           /* Update the phrase table. Don't do this before p=phrase[...]. */
  647.           phrase[next++]=p_dst;
  648.           
  649.           /* Now perform the copy using a half unrolled loop. */
  650.           *p_dst++=*p++;
  651.           *p_dst++=*p++;
  652.           *p_dst++=*p++;
  653.           while (lenmt--)
  654.              *p_dst++=*p++;
  655.          }
  656.        else
  657.          { /* Literal item. */
  658.           phrase[next++]=p_dst;  /* Update the phrase table.    */
  659.           *p_dst++=*p_src++;     /* Copy over the literal byte. */
  660.           }
  661.           
  662.        /* Shift the control buffer so the next control bit is in bit 0. */
  663.        control>>=1;
  664.        
  665.       } /* End unrolled inner loop. */
  666.                
  667.    } /* End of outer loop */
  668.    
  669.  /* Write the length of the decompressed data before returning. */
  670.  *p_dst_len=p_dst-p_dst_first;
  671. }
  672.  
  673. /******************************************************************************/
  674. /*                               End of LZRW2.C                               */
  675. /******************************************************************************/
  676.