开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Linux/Unix编程 > 查看源码
lzrw3.c
资源名称：linux-2.4.20.tar.gz　[点击查看]
上传用户：jlfgdled
上传日期：2013-04-10
资源大小：33168k
文件大小：41k
源码类别：

Linux/Unix编程

开发平台：

Unix_Linux

lzrw3.c：源码内容
  1. /*
  2.  * $Source: /homes/cvs/ftape-stacked/ftape/compressor/lzrw3.c,v $
  3.  * $Revision: 1.1 $
  4.  * $Date: 1997/10/05 19:12:29 $
  5.  *
  6.  * Implementation of Ross Williams lzrw3 algorithm. Adaption for zftape.
  7.  *
  8.  */
  10. #include "../compressor/lzrw3.h"       /* Defines single exported function "compress".   */
  12. /******************************************************************************/
  13. /*                                                                            */
  14. /*                                    LZRW3.C                                 */
  15. /*                                                                            */
  16. /******************************************************************************/
  17. /*                                                                            */
  18. /* Author  : Ross Williams.                                                   */
  19. /* Date    : 30-Jun-1991.                                                     */
  20. /* Release : 1.                                                               */
  21. /*                                                                            */
  22. /******************************************************************************/
  23. /*                                                                            */
  24. /* This file contains an implementation of the LZRW3 data compression         */
  25. /* algorithm in C.                                                            */
  26. /*                                                                            */
  27. /* The algorithm is a general purpose compression algorithm that runs fast    */
  28. /* and gives reasonable compression. The algorithm is a member of the Lempel  */
  29. /* Ziv family of algorithms and bases its compression on the presence in the  */
  30. /* data of repeated substrings.                                               */
  31. /*                                                                            */
  32. /* This algorithm is unpatented and the code is public domain. As the         */
  33. /* algorithm is based on the LZ77 class of algorithms, it is unlikely to be   */
  34. /* the subject of a patent challenge.                                         */
  35. /*                                                                            */
  36. /* Unlike the LZRW1 and LZRW1-A algorithms, the LZRW3 algorithm is            */
  37. /* deterministic and is guaranteed to yield the same compressed               */
  38. /* representation for a given file each time it is run.                       */
  39. /*                                                                            */
  40. /* The LZRW3 algorithm was originally designed and implemented                */
  41. /* by Ross Williams on 31-Dec-1990.                                           */
  42. /*                                                                            */
  43. /* Here are the results of applying this code, compiled under THINK C 4.0     */
  44. /* and running on a Mac-SE (8MHz 68000), to the standard calgary corpus.      */
  45. /*                                                                            */
  46. /*    +----------------------------------------------------------------+      */
  47. /*    | DATA COMPRESSION TEST                                          |      */
  48. /*    | =====================                                          |      */
  49. /*    | Time of run     : Sun 30-Jun-1991 09:31PM                      |      */
  50. /*    | Timing accuracy : One part in 100                              |      */
  51. /*    | Context length  : 262144 bytes (= 256.0000K)                   |      */
  52. /*    | Test suite      : Calgary Corpus Suite                         |      */
  53. /*    | Files in suite  : 14                                           |      */
  54. /*    | Algorithm       : LZRW3                                        |      */
  55. /*    | Note: All averages are calculated from the un-rounded values.  |      */
  56. /*    +----------------------------------------------------------------+      */
  57. /*    | File Name   Length  CxB  ComLen  %Remn  Bits  Com K/s  Dec K/s |      */
  58. /*    | ----------  ------  ---  ------  -----  ----  -------  ------- |      */
  59. /*    | rpus:Bib.D  111261    1   55033   49.5  3.96    19.46    32.27 |      */
  60. /*    | us:Book1.D  768771    3  467962   60.9  4.87    17.03    31.07 |      */
  61. /*    | us:Book2.D  610856    3  317102   51.9  4.15    19.39    34.15 |      */
  62. /*    | rpus:Geo.D  102400    1   82424   80.5  6.44    11.65    18.18 |      */
  63. /*    | pus:News.D  377109    2  205670   54.5  4.36    17.14    27.47 |      */
  64. /*    | pus:Obj1.D   21504    1   13027   60.6  4.85    13.40    18.95 |      */
  65. /*    | pus:Obj2.D  246814    1  116286   47.1  3.77    19.31    30.10 |      */
  66. /*    | s:Paper1.D   53161    1   27522   51.8  4.14    18.60    31.15 |      */
  67. /*    | s:Paper2.D   82199    1   45160   54.9  4.40    18.45    32.84 |      */
  68. /*    | rpus:Pic.D  513216    2  122388   23.8  1.91    35.29    51.05 |      */
  69. /*    | us:Progc.D   39611    1   19669   49.7  3.97    18.87    30.64 |      */
  70. /*    | us:Progl.D   71646    1   28247   39.4  3.15    24.34    40.66 |      */
  71. /*    | us:Progp.D   49379    1   19377   39.2  3.14    23.91    39.23 |      */
  72. /*    | us:Trans.D   93695    1   33481   35.7  2.86    25.48    40.37 |      */
  73. /*    +----------------------------------------------------------------+      */
  74. /*    | Average     224401    1  110953   50.0  4.00    20.17    32.72 |      */
  75. /*    +----------------------------------------------------------------+      */
  76. /*                                                                            */
  77. /******************************************************************************/
  79. /******************************************************************************/
  81. /* The following structure is returned by the "compress" function below when  */
  82. /* the user asks the function to return identifying information.              */
  83. /* The most important field in the record is the working memory field which   */
  84. /* tells the calling program how much working memory should be passed to      */
  85. /* "compress" when it is called to perform a compression or decompression.    */
  86. /* LZRW3 uses the same amount of memory during compression and decompression. */
  87. /* For more information on this structure see "compress.h".                   */
  88.   
  89. #define U(X)            ((ULONG) X)
  90. #define SIZE_P_BYTE     (U(sizeof(UBYTE *)))
  91. #define SIZE_WORD       (U(sizeof(UWORD  )))
  92. #define ALIGNMENT_FUDGE (U(16))
  93. #define MEM_REQ ( U(4096)*(SIZE_P_BYTE) + ALIGNMENT_FUDGE )
  95. static struct compress_identity identity =
  96. {
  97.  U(0x032DDEA8),                           /* Algorithm identification number. */
  98.  MEM_REQ,                                 /* Working memory (bytes) required. */
  99.  "LZRW3",                                 /* Name of algorithm.               */
  100.  "1.0",                                   /* Version number of algorithm.     */
  101.  "31-Dec-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. LOCAL void compress_compress  (UBYTE *,UBYTE *,ULONG,UBYTE *, LONG *);
  109. LOCAL void compress_decompress(UBYTE *,UBYTE *,LONG, UBYTE *, ULONG *);
  111. /******************************************************************************/
  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".     */
  118. EXPORT void lzrw3_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. LONG     src_len;      /* Length  of input data.                              */
  123. UBYTE   *dst_adr;      /* Address to put output data.                         */
  124. void  *p_dst_len;      /* Address of longword for length of output data.      */
  125. {
  126.  switch (action)
  127.    {
  128.     case COMPRESS_ACTION_IDENTITY:
  129.        *((struct compress_identity **)p_dst_len)= &identity;
  130.        break;
  131.     case COMPRESS_ACTION_COMPRESS:
  132.        compress_compress(wrk_mem,src_adr,src_len,dst_adr,(LONG *)p_dst_len);
  133.        break;
  134.     case COMPRESS_ACTION_DECOMPRESS:
  135.        compress_decompress(wrk_mem,src_adr,src_len,dst_adr,(LONG *)p_dst_len);
  136.        break;
  137.    }
  138. }
  140. /******************************************************************************/
  141. /*                                                                            */
  142. /* BRIEF DESCRIPTION OF THE LZRW3 ALGORITHM                                   */
  143. /* ========================================                                   */
  144. /* The LZRW3 algorithm is identical to the LZRW1-A algorithm except that      */
  145. /* instead of transmitting history offsets, it transmits hash table indexes.  */
  146. /* In order to decode the indexes, the decompressor must maintain an          */
  147. /* identical hash table. Copy items are straightforward:when the decompressor */
  148. /* receives a copy item, it simply looks up the hash table to translate the   */
  149. /* index into a pointer into the data already decompressed. To update the     */
  150. /* hash table, it replaces the same table entry with a pointer to the start   */
  151. /* of the newly decoded phrase. The tricky part is with literal items, for at */
  152. /* the time that the decompressor receives a literal item the decompressor    */
  153. /* does not have the three bytes in the Ziv (that the compressor has) to      */
  154. /* perform the three-byte hash. To solve this problem, in LZRW3, both the     */
  155. /* compressor and decompressor are wired up so that they "buffer" these       */
  156. /* literals and update their hash tables only when three bytes are available. */
  157. /* This makes the maximum buffering 2 bytes.                                  */
  158. /*                                                                            */
  159. /* Replacement of offsets by hash table indexes yields a few percent extra    */
  160. /* compression at the cost of some speed. LZRW3 is slower than LZRW1, LZRW1-A */
  161. /* and LZRW2, but yields better compression.                                  */
  162. /*                                                                            */
  163. /* Extra compression could be obtained by using a hash table of depth two.    */
  164. /* However, increasing the depth above one incurs a significant decrease in   */
  165. /* compression speed which was not considered worthwhile. Another reason for  */
  166. /* keeping the depth down to one was to allow easy comparison with the        */
  167. /* LZRW1-A and LZRW2 algorithms so as to demonstrate the exact effect of the  */
  168. /* use of direct hash indexes.                                                */
  169. /*                                                                            */
  170. /*                                  +---+                                     */
  171. /*                                  |___|4095                                 */
  172. /*                                  |___|                                     */
  173. /*              +---------------------*_|<---+   /----+---                   */
  174. /*              |                   |___|    +---|Hash    |                   */
  175. /*              |                   |___|        |Function|                   */
  176. /*              |                   |___|        --------/                   */
  177. /*              |                   |___|0            ^                       */
  178. /*              |                   +---+             |                       */
  179. /*              |                   Hash        +-----+                       */
  180. /*              |                   Table       |                             */
  181. /*              |                              ---                            */
  182. /*              v                              ^^^                            */
  183. /*      +-------------------------------------|----------------+              */
  184. /*      ||||||||||||||||||||||||||||||||||||||||||||||||||||||||              */
  185. /*      +-------------------------------------|----------------+              */
  186. /*      |                                     |1......18|      |              */
  187. /*      |<------- Lempel=History ------------>|<--Ziv-->|      |              */
  188. /*      |     (=bytes already processed)      |<-Still to go-->|              */
  189. /*      |<-------------------- INPUT BLOCK ------------------->|              */
  190. /*                                                                            */
  191. /* The diagram above for LZRW3 looks almost identical to the diagram for      */
  192. /* LZRW1. The difference is that in LZRW3, the compressor transmits hash      */
  193. /* table indices instead of Lempel offsets. For this to work, the             */
  194. /* decompressor must maintain a hash table as well as the compressor and both */
  195. /* compressor and decompressor must "buffer" literals, as the decompressor    */
  196. /* cannot hash phrases commencing with a literal until another two bytes have */
  197. /* arrived.                                                                   */
  198. /*                                                                            */
  199. /*  LZRW3 Algorithm Execution Summary                                         */
  200. /*  ---------------------------------                                         */
  201. /*  1. Hash the first three bytes of the Ziv to yield a hash table index h.   */
  202. /*  2. Look up the hash table yielding history pointer p.                     */
  203. /*  3. 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. /*  4. Update the hash table as possible subject to the constraint that only  */
  207. /*     phrases commencing three bytes back from the Ziv can be hashed and     */
  208. /*     entered into the hash table. (This enables the decompressor to keep    */
  209. /*     pace). See the description and code for more details.                  */
  210. /*                                                                            */
  211. /******************************************************************************/
  212. /*                                                                            */
  213. /*                     DEFINITION OF COMPRESSED FILE FORMAT                   */
  214. /*                     ====================================                   */
  215. /*  * A compressed file consists of a COPY FLAG followed by a REMAINDER.      */
  216. /*  * The copy flag CF uses up four bytes with the first byte being the       */
  217. /*    least significant.                                                      */
  218. /*  * If CF=1, then the compressed file represents the remainder of the file  */
  219. /*    exactly. Otherwise CF=0 and the remainder of the file consists of zero  */
  220. /*    or more GROUPS, each of which represents one or more bytes.             */
  221. /*  * Each group consists of two bytes of CONTROL information followed by     */
  222. /*    sixteen ITEMs except for the last group which can contain from one      */
  223. /*    to sixteen items.                                                       */
  224. /*  * An item can be either a LITERAL item or a COPY item.                    */
  225. /*  * Each item corresponds to a bit in the control bytes.                    */
  226. /*  * The first control byte corresponds to the first 8 items in the group    */
  227. /*    with bit 0 corresponding to the first item in the group and bit 7 to    */
  228. /*    the eighth item in the group.                                           */
  229. /*  * The second control byte corresponds to the second 8 items in the group  */
  230. /*    with bit 0 corresponding to the ninth item in the group and bit 7 to    */
  231. /*    the sixteenth item in the group.                                        */
  232. /*  * A zero bit in a control word means that the corresponding item is a     */
  233. /*    literal item. A one bit corresponds to a copy item.                     */
  234. /*  * A literal item consists of a single byte which represents itself.       */
  235. /*  * A copy item consists of two bytes that represent from 3 to 18 bytes.    */
  236. /*  * The first  byte in a copy item will be denoted C1.                      */
  237. /*  * The second byte in a copy item will be denoted C2.                      */
  238. /*  * Bits will be selected using square brackets.                            */
  239. /*    For example: C1[0..3] is the low nibble of the first control byte.      */
  240. /*    of copy item C1.                                                        */
  241. /*  * The LENGTH of a copy item is defined to be C1[0..3]+3 which is a number */
  242. /*    in the range [3,18].                                                    */
  243. /*  * The INDEX of a copy item is defined to be C1[4..7]*256+C2[0..8] which   */
  244. /*    is a number in the range [0,4095].                                      */
  245. /*  * A copy item represents the sequence of bytes                            */
  246. /*       text[POS-OFFSET..POS-OFFSET+LENGTH-1] where                          */
  247. /*          text   is the entire text of the uncompressed string.             */
  248. /*          POS    is the index in the text of the character following the    */
  249. /*                   string represented by all the items preceeding the item  */
  250. /*                   being defined.                                           */
  251. /*          OFFSET is obtained from INDEX by looking up the hash table.       */
  252. /*                                                                            */
  253. /******************************************************************************/
  255. /* The following #define defines the length of the copy flag that appears at  */
  256. /* the start of the compressed file. The value of four bytes was chosen       */
  257. /* because the fast_copy routine on my Macintosh runs faster if the source    */
  258. /* and destination blocks are relatively longword aligned.                    */
  259. /* The actual flag data appears in the first byte. The rest are zeroed so as  */
  260. /* to normalize the compressed representation (i.e. not non-deterministic).   */
  261. #define FLAG_BYTES 4
  263. /* The following #defines define the meaning of the values of the copy        */
  264. /* flag at the start of the compressed file.                                  */
  265. #define FLAG_COMPRESS 0     /* Signals that output was result of compression. */
  266. #define FLAG_COPY     1     /* Signals that output was simply copied over.    */
  268. /* The 68000 microprocessor (on which this algorithm was originally developed */
  269. /* is fussy about non-aligned arrays of words. To avoid these problems the    */
  270. /* following macro can be used to "waste" from 0 to 3 bytes so as to align    */
  271. /* the argument pointer.                                                      */
  272. #define ULONG_ALIGN_UP(X) ((((ULONG)X)+sizeof(ULONG)-1)&~(sizeof(ULONG)-1))
  275. /* The following constant defines the maximum length of an uncompressed item. */
  276. /* This definition must not be changed; its value is hardwired into the code. */
  277. /* The longest number of bytes that can be spanned by a single item is 18     */
  278. /* for the longest copy item.                                                 */
  279. #define MAX_RAW_ITEM (18)
  281. /* The following constant defines the maximum length of an uncompressed group.*/
  282. /* This definition must not be changed; its value is hardwired into the code. */
  283. /* A group contains at most 16 items which explains this definition.          */
  284. #define MAX_RAW_GROUP (16*MAX_RAW_ITEM)
  286. /* The following constant defines the maximum length of a compressed group.   */
  287. /* This definition must not be changed; its value is hardwired into the code. */
  288. /* A compressed group consists of two control bytes followed by up to 16      */
  289. /* compressed items each of which can have a maximum length of two bytes.     */
  290. #define MAX_CMP_GROUP (2+16*2)
  292. /* The following constant defines the number of entries in the hash table.    */
  293. /* This definition must not be changed; its value is hardwired into the code. */
  294. #define HASH_TABLE_LENGTH (4096)
  296. /* LZRW3, unlike LZRW1(-A), must initialize its hash table so as to enable    */
  297. /* the compressor and decompressor to stay in step maintaining identical hash */
  298. /* tables. In an early version of the algorithm, the tables were simply       */
  299. /* initialized to zero and a check for zero was included just before the      */
  300. /* matching code. However, this test costs time. A better solution is to      */
  301. /* initialize all the entries in the hash table to point to a constant        */
  302. /* string. The decompressor does the same. This solution requires no extra    */
  303. /* test. The contents of the string do not matter so long as the string is    */
  304. /* the same for the compressor and decompressor and contains at least         */
  305. /* MAX_RAW_ITEM bytes. I chose consecutive decimal digits because they do not */
  306. /* have white space problems (e.g. there is no chance that the compiler will  */
  307. /* replace more than one space by a TAB) and because they make the length of  */
  308. /* the string obvious by inspection.                                          */
  309. #define START_STRING_18 ((UBYTE *) "123456789012345678")
  311. /* In this algorithm, hash values have to be calculated at more than one      */
  312. /* point. The following macro neatens the code up for this.                   */
  313. #define HASH(PTR) 
  314.    (((40543*(((*(PTR))<<8)^((*((PTR)+1))<<4)^(*((PTR)+2))))>>4) & 0xFFF)
  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. LONG  *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.  register ULONG control=TOPWORD;
  360.  
  361.  /* THe variable 'hash' always points to the first element of the hash table. */
  362.  UBYTE **hash= (UBYTE **)  ULONG_ALIGN_UP(p_wrk_mem);
  363.  
  364.  /* The following two variables represent the literal buffer. p_h1 points to  */
  365.  /* the hash table entry corresponding to the youngest literal. p_h2 points   */
  366.  /* to the hash table entry corresponding to the second youngest literal.     */
  367.  /* Note: p_h1=0=>p_h2=0 because zero values denote absence of a pending      */
  368.  /* literal. The variables are initialized to zero meaning an empty "buffer". */
  369.  UBYTE **p_h1=0;
  370.  UBYTE **p_h2=0;
  371.   
  372.  /* To start, we write the flag bytes. Being optimistic, we set the flag to   */
  373.  /* FLAG_COMPRESS. The remaining flag bytes are zeroed so as to keep the      */
  374.  /* algorithm deterministic.                                                  */
  375.  *p_dst++=FLAG_COMPRESS;
  376.  {UWORD i; for (i=2;i<=FLAG_BYTES;i++) *p_dst++=0;}
  378.  /* Reserve the first word of output as the control word for the first group. */
  379.  /* Note: This is undone at the end if the input block is empty.              */
  380.  p_control=p_dst; p_dst+=2;
  381.  
  382.  /* Initialize all elements of the hash table to point to a constant string.  */
  383.  /* Use of an unrolled loop speeds this up considerably.                      */
  384.  {UWORD i; UBYTE **p_h=hash;
  385. #  define ZH *p_h++=START_STRING_18
  386.   for (i=0;i<256;i++)     /* 256=HASH_TABLE_LENGTH/16. */
  387.     {ZH;ZH;ZH;ZH;
  388.      ZH;ZH;ZH;ZH;
  389.      ZH;ZH;ZH;ZH;
  390.      ZH;ZH;ZH;ZH;}
  391.  }
  393.  /* The main loop processes either 1 or 16 items per iteration. As its        */
  394.  /* termination logic is complicated, I have opted for an infinite loop       */
  395.  /* structure containing 'break' and 'goto' statements.                       */
  396.  while (TRUE)
  397.    {/* Begin main processing loop. */
  398.    
  399.     /* Note: All the variables here except unroll should be defined within    */
  400.     /*       the inner loop. Unfortunately the loop hasn't got a block.       */
  401.      register UBYTE *p;         /* Scans through targ phrase during matching. */
  402.      register UBYTE *p_ziv= NULL ;     /* Points to first byte of current Ziv.       */
  403.      register UWORD unroll;     /* Loop counter for unrolled inner loop.      */
  404.      register UWORD index;      /* Index of current hash table entry.         */
  405.      register UBYTE **p_h0 = NULL ;     /* Pointer to current hash table entry.       */
  406.      
  407.     /* Test for overrun and jump to overrun code if necessary.                */
  408.     if (p_dst>p_dst_post)
  409.        goto overrun;
  410.        
  411.     /* The following cascade of if statements efficiently catches and deals   */
  412.     /* with varying degrees of closeness to the end of the input block.       */
  413.     /* When we get very close to the end, we stop updating the table and      */
  414.     /* code the remaining bytes as literals. This makes the code simpler.     */
  415.     unroll=16;
  416.     if (p_src>p_src_max16)
  417.       {
  418.        unroll=1;
  419.        if (p_src>p_src_max1)
  420.          {
  421.           if (p_src==p_src_post)
  422.              break;
  423.           else
  424.              goto literal;
  425.          }
  426.       }
  427.          
  428.     /* This inner unrolled loop processes 'unroll' (whose value is either 1   */
  429.     /* or 16) items. I have chosen to implement this loop with labels and     */
  430.     /* gotos to heighten the ease with which the loop may be implemented with */
  431.     /* a single decrement and branch instruction in assembly language and     */
  432.     /* also because the labels act as highly readable place markers.          */
  433.     /* (Also because we jump into the loop for endgame literals (see above)). */
  434.     
  435.     begin_unrolled_loop:
  436.     
  437.        /* To process the next phrase, we hash the next three bytes and use    */
  438.        /* the resultant hash table index to look up the hash table. A pointer */
  439.        /* to the entry is stored in p_h0 so as to avoid an array lookup. The  */
  440.        /* hash table entry *p_h0 is looked up yielding a pointer p to a       */
  441.        /* potential match of the Ziv in the history.                          */
  442.        index=HASH(p_src);
  443.        p_h0=&hash[index];
  444.        p=*p_h0;
  445.        
  446.        /* Having looked up the candidate position, we are in a position to    */
  447.        /* attempt a match. The match loop has been unrolled using the PS      */
  448.        /* macro so that failure within the first three bytes automatically    */
  449.        /* results in the literal branch being taken. The coding is simple.    */
  450.        /* p_ziv saves p_src so we can let p_src wander.                       */
  451. #       define PS *p++!=*p_src++
  452.        p_ziv=p_src;
  453.        if (PS || PS || PS)
  454.          {
  455.           /* Literal. */
  456.           
  457.           /* Code the literal byte as itself and a zero control bit.          */
  458.           p_src=p_ziv; literal: *p_dst++=*p_src++; control&=0xFFFEFFFF;
  459.           
  460.           /* We have just coded a literal. If we had two pending ones, that   */
  461.           /* makes three and we can update the hash table.                    */
  462.           if (p_h2!=0)
  463.              {*p_h2=p_ziv-2;}
  464.              
  465.           /* In any case, rotate the hash table pointers for next time. */
  466.           p_h2=p_h1; p_h1=p_h0;
  467.           
  468.          }
  469.        else
  470.          {
  471.           /* Copy */
  472.           
  473.           /* Match up to 15 remaining bytes using an unrolled loop and code. */
  474. #if 0
  475.           PS || PS || PS || PS || PS || PS || PS || PS ||
  476.           PS || PS || PS || PS || PS || PS || PS || p_src++;
  477. #else     
  478.           if (
  479.                !( PS || PS || PS || PS || PS || PS || PS || PS ||
  480.                   PS || PS || PS || PS || PS || PS || PS ) 
  481.              ) p_src++;
  482. #endif
  483.           *p_dst++=((index&0xF00)>>4)|(--p_src-p_ziv-3);
  484.           *p_dst++=index&0xFF;
  485.           
  486.           /* As we have just coded three bytes, we are now in a position to   */
  487.           /* update the hash table with the literal bytes that were pending   */
  488.           /* upon the arrival of extra context bytes.                         */
  489.           if (p_h1!=0)
  490.             {
  491.              if (p_h2!=0)
  492.                {*p_h2=p_ziv-2; p_h2=0;}
  493.              *p_h1=p_ziv-1; p_h1=0;
  494.             }
  495.             
  496.           /* In any case, we can update the hash table based on the current   */
  497.           /* position as we just coded at least three bytes in a copy items.  */
  498.           *p_h0=p_ziv;
  499.           
  500.          }
  501.        control>>=1;
  502.                 
  503.        /* This loop is all set up for a decrement and jump instruction! */
  504. #ifndef linux
  505. `    end_unrolled_loop: if (--unroll) goto begin_unrolled_loop;
  506. #else
  507.     /* end_unrolled_loop: */ if (--unroll) goto begin_unrolled_loop;
  508. #endif
  510.     /* At this point it will nearly always be the end of a group in which     */
  511.     /* case, we have to do some control-word processing. However, near the    */
  512.     /* end of the input block, the inner unrolled loop is only executed once. */
  513.     /* This necessitates the 'if' test.                                       */
  514.     if ((control&TOPWORD)==0)
  515.       {
  516.        /* Write the control word to the place we saved for it in the output. */
  517.        *p_control++=  control     &0xFF;
  518.        *p_control  = (control>>8) &0xFF;
  520.        /* Reserve the next word in the output block for the control word */
  521.        /* for the group about to be processed.                           */
  522.        p_control=p_dst; p_dst+=2;
  523.        
  524.        /* Reset the control bits buffer. */
  525.        control=TOPWORD;
  526.       }
  527.           
  528.    } /* End main processing loop. */
  529.    
  530.  /* After the main processing loop has executed, all the input bytes have     */
  531.  /* been processed. However, the control word has still to be written to the  */
  532.  /* word reserved for it in the output at the start of the most recent group. */
  533.  /* Before writing, the control word has to be shifted so that all the bits   */
  534.  /* are in the right place. The "empty" bit positions are filled with 1s      */
  535.  /* which partially fill the top word.                                        */
  536.  while(control&TOPWORD) control>>=1;
  537.  *p_control++= control     &0xFF;
  538.  *p_control++=(control>>8) &0xFF;
  539.  
  540.  /* If the last group contained no items, delete the control word too.        */
  541.  if (p_control==p_dst) p_dst-=2;
  542.  
  543.  /* Write the length of the output block to the dst_len parameter and return. */
  544.  *p_dst_len=p_dst-p_dst_first;                           
  545.  return;
  546.  
  547.  /* Jump here as soon as an overrun is detected. An overrun is defined to     */
  548.  /* have occurred if p_dst>p_dst_first+src_len. That is, the moment the       */
  549.  /* length of the output written so far exceeds the length of the input block.*/
  550.  /* The algorithm checks for overruns at least at the end of each group       */
  551.  /* which means that the maximum overrun is MAX_CMP_GROUP bytes.              */
  552.  /* Once an overrun occurs, the only thing to do is to set the copy flag and  */
  553.  /* copy the input over.                                                      */
  554.  overrun:
  555. #if 0
  556.  *p_dst_first=FLAG_COPY;
  557.  fast_copy(p_src_first,p_dst_first+FLAG_BYTES,src_len);
  558.  *p_dst_len=src_len+FLAG_BYTES;
  559. #else
  560.  fast_copy(p_src_first,p_dst_first,src_len);
  561.  *p_dst_len= -src_len; /* return a negative number to indicate uncompressed data */
  562. #endif
  563. }
  565. /******************************************************************************/
  567. LOCAL void compress_decompress
  568.            (p_wrk_mem,p_src_first,src_len,p_dst_first,p_dst_len)
  569. /* Input  : Hand over the required amount of working memory in p_wrk_mem.     */
  570. /* Input  : Specify input block using p_src_first and src_len.                */
  571. /* Input  : Point p_dst_first to the start of the output zone.                */
  572. /* Input  : Point p_dst_len to a ULONG to receive the output length.          */
  573. /* Input  : Input block and output zone must not overlap. User knows          */
  574. /* Input  : upperbound on output block length from earlier compression.       */
  575. /* Input  : In any case, maximum expansion possible is nine times.            */
  576. /* Output : Length of output block written to *p_dst_len.                     */
  577. /* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1].       */
  578. /* Output : Writes only  in Mem[p_dst_first..p_dst_first+*p_dst_len-1].       */
  579. UBYTE *p_wrk_mem;
  580. UBYTE *p_src_first;
  581. LONG   src_len;
  582. UBYTE *p_dst_first;
  583. ULONG *p_dst_len;
  584. {
  585.  /* Byte pointers p_src and p_dst scan through the input and output blocks.   */
  586.  register UBYTE *p_src = p_src_first+FLAG_BYTES;
  587.  register UBYTE *p_dst = p_dst_first;
  588.  /* we need to avoid a SEGV when trying to uncompress corrupt data */
  589.  register UBYTE *p_dst_post = p_dst_first + *p_dst_len;
  591.  /* The following two variables are never modified and are used to control    */
  592.  /* the main loop.                                                            */
  593.  UBYTE *p_src_post  = p_src_first+src_len;
  594.  UBYTE *p_src_max16 = p_src_first+src_len-(MAX_CMP_GROUP-2);
  595.  
  596.  /* The hash table is the only resident of the working memory. The hash table */
  597.  /* contains HASH_TABLE_LENGTH=4096 pointers to positions in the history. To  */
  598.  /* keep Macintoshes happy, it is longword aligned.                           */
  599.  UBYTE **hash = (UBYTE **) ULONG_ALIGN_UP(p_wrk_mem);
  601.  /* The variable 'control' is used to buffer the control bits which appear in */
  602.  /* groups of 16 bits (control words) at the start of each compressed group.  */
  603.  /* When each group is read, bit 16 of the register is set to one. Whenever   */
  604.  /* a new bit is needed, the register is shifted right. When the value of the */
  605.  /* register becomes 1, we know that we have reached the end of a group.      */
  606.  /* Initializing the register to 1 thus instructs the code to follow that it  */
  607.  /* should read a new control word immediately.                               */
  608.  register ULONG control=1;
  609.  
  610.  /* The value of 'literals' is always in the range 0..3. It is the number of  */
  611.  /* consecutive literal items just seen. We have to record this number so as  */
  612.  /* to know when to update the hash table. When literals gets to 3, there     */
  613.  /* have been three consecutive literals and we can update at the position of */
  614.  /* the oldest of the three.                                                  */
  615.  register UWORD literals=0;
  616.  
  617.  /* Check the leading copy flag to see if the compressor chose to use a copy  */
  618.  /* operation instead of a compression operation. If a copy operation was     */
  619.  /* used, then all we need to do is copy the data over, set the output length */
  620.  /* and return.                                                               */
  621. #if 0
  622.  if (*p_src_first==FLAG_COPY)
  623.    {
  624.     fast_copy(p_src_first+FLAG_BYTES,p_dst_first,src_len-FLAG_BYTES);
  625.     *p_dst_len=src_len-FLAG_BYTES;
  626.     return;
  627.    }
  628. #else
  629.   if ( src_len < 0 )
  630.   {                                            
  631.    fast_copy(p_src_first,p_dst_first,-src_len );
  632.    *p_dst_len = (ULONG)-src_len;
  633.    return;
  634.   }
  635. #endif
  636.    
  637.  /* Initialize all elements of the hash table to point to a constant string.  */
  638.  /* Use of an unrolled loop speeds this up considerably.                      */
  639.  {UWORD i; UBYTE **p_h=hash;
  640. #  define ZJ *p_h++=START_STRING_18
  641.   for (i=0;i<256;i++)     /* 256=HASH_TABLE_LENGTH/16. */
  642.     {ZJ;ZJ;ZJ;ZJ;
  643.      ZJ;ZJ;ZJ;ZJ;
  644.      ZJ;ZJ;ZJ;ZJ;
  645.      ZJ;ZJ;ZJ;ZJ;}
  646.  }
  648.  /* The outer loop processes either 1 or 16 items per iteration depending on  */
  649.  /* how close p_src is to the end of the input block.                         */
  650.  while (p_src!=p_src_post)
  651.    {/* Start of outer loop */
  652.    
  653.     register UWORD unroll;   /* Counts unrolled loop executions.              */
  654.     
  655.     /* When 'control' has the value 1, it means that the 16 buffered control  */
  656.     /* bits that were read in at the start of the current group have all been */
  657.     /* shifted out and that all that is left is the 1 bit that was injected   */
  658.     /* into bit 16 at the start of the current group. When we reach the end   */
  659.     /* of a group, we have to load a new control word and inject a new 1 bit. */
  660.     if (control==1)
  661.       {
  662.        control=0x10000|*p_src++;
  663.        control|=(*p_src++)<<8;
  664.       }
  666.     /* If it is possible that we are within 16 groups from the end of the     */
  667.     /* input, execute the unrolled loop only once, else process a whole group */
  668.     /* of 16 items by looping 16 times.                                       */
  669.     unroll= p_src<=p_src_max16 ? 16 : 1;
  671.     /* This inner loop processes one phrase (item) per iteration. */
  672.     while (unroll--)
  673.       { /* Begin unrolled inner loop. */
  674.       
  675.        /* Process a literal or copy item depending on the next control bit. */
  676.        if (control&1)
  677.          {
  678.           /* Copy item. */
  679.           
  680.           register UBYTE *p;           /* Points to place from which to copy. */
  681.           register UWORD lenmt;        /* Length of copy item minus three.    */
  682.           register UBYTE **p_hte;      /* Pointer to current hash table entry.*/
  683.           register UBYTE *p_ziv=p_dst; /* Pointer to start of current Ziv.    */
  684.           
  685.           /* Read and dismantle the copy word. Work out from where to copy.   */
  686.           lenmt=*p_src++;
  687.           p_hte=&hash[((lenmt&0xF0)<<4)|*p_src++];
  688.           p=*p_hte;
  689.           lenmt&=0xF;
  690.           
  691.           /* Now perform the copy using a half unrolled loop. */
  692.           *p_dst++=*p++;
  693.           *p_dst++=*p++;
  694.           *p_dst++=*p++;
  695.           while (lenmt--)
  696.              *p_dst++=*p++;
  697.                  
  698.           /* Because we have just received 3 or more bytes in a copy item     */
  699.           /* (whose bytes we have just installed in the output), we are now   */
  700.           /* in a position to flush all the pending literal hashings that had */
  701.           /* been postponed for lack of bytes.                                */
  702.           if (literals>0)
  703.             {
  704.              register UBYTE *r=p_ziv-literals;;
  705.              hash[HASH(r)]=r;
  706.              if (literals==2)
  707.                 {r++; hash[HASH(r)]=r;}
  708.              literals=0;
  709.             }
  710.             
  711.           /* In any case, we can immediately update the hash table with the   */
  712.           /* current position. We don't need to do a HASH(...) to work out    */
  713.           /* where to put the pointer, as the compressor just told us!!!      */
  714.           *p_hte=p_ziv;
  715.           
  716.          }
  717.        else
  718.          {
  719.           /* Literal item. */
  720.           
  721.           /* Copy over the literal byte. */
  722.           *p_dst++=*p_src++;
  723.           
  724.           /* If we now have three literals waiting to be hashed into the hash */
  725.           /* table, we can do one of them now (because there are three).      */
  726.           if (++literals == 3)
  727.              {register UBYTE *p=p_dst-3; hash[HASH(p)]=p; literals=2;}
  728.          }
  729.           
  730.        /* Shift the control buffer so the next control bit is in bit 0. */
  731.        control>>=1;
  732. #if 1
  733.        if (p_dst > p_dst_post) 
  734.        {
  735.        /* Shit: we tried to decompress corrupt data */
  736.        *p_dst_len = 0;
  737.        return;
  738.        }
  739. #endif
  740.       } /* End unrolled inner loop. */
  741.                
  742.    } /* End of outer loop */
  743.    
  744.  /* Write the length of the decompressed data before returning. */
  745.   *p_dst_len=p_dst-p_dst_first;
  746. }
  748. /******************************************************************************/
  749. /*                               End of LZRW3.C                               */
  750. /******************************************************************************/