home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / pascal / LZRW.ZIP / LZRW3-A.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-01-19  |  48.3 KB  |  856 lines
  1. /******************************************************************************/
  2. /*                                                                            */
  3. /*                                   LZRW3-A.C                                */
  4. /*                                                                            */
  5. /******************************************************************************/
  6. /*                                                                            */
  7. /* Author  : Ross Williams.                                                   */
  8. /* Date    : 15-Jul-1991.                                                     */
  9. /* Release : 1.                                                               */
  10. /*                                                                            */
  11. /******************************************************************************/
  12. /*                                                                            */
  13. /* This file contains an implementation of the LZRW3-A data compression       */
  14. /* algorithm in the C programming language.                                   */
  15. /*                                                                            */
  16. /* The LZRW3-A algorithm has the following features:                          */
  17. /*                                                                            */
  18. /*    1 Requires only 16K of memory (for both compression and decompression). */
  19. /*    2 The compressor   runs about two   times faster than Unix compress's.  */
  20. /*    3 The decompressor runs about three times faster than Unix compress's.  */
  21. /*    4 Yields a few percent better compression than Unix compress for        */
  22. /*      most files.                                                           */
  23. /*    5 Allows you to dial up extra compression at a speed cost in the        */
  24. /*      compressor. The speed of the decompressor is not affected.            */
  25. /*    6 Algorithm is deterministic.                                           */
  26. /*    7 Algorithm is free of patent problems. The algorithm has not been      */
  27. /*      patented (nor will it be) and is of the LZ77 class which is fairly    */
  28. /*      clear of patents.                                                     */
  29. /*    8 This implementation in C is in the public domain.                     */
  30. /*                                                                            */
  31. /* (Timing tests for the speed comparison were performed on a Pyramid 9820.)  */
  32. /*                                                                            */
  33. /* LZRW3-A is LZRW3 with a deepened hash table. This simple change yields     */
  34. /* about a 6% (absolute) improvement in compression.                          */
  35. /*                                                                            */
  36. /* Here are the results of applying this code, compiled under THINK C 4.0     */
  37. /* and running on a Mac-SE (8MHz 68000), to the standard calgary corpus.      */
  38. /*                                                                            */
  39. /*     +----------------------------------------------------------------+     */
  40. /*     | DATA COMPRESSION TEST                                          |     */
  41. /*     | =====================                                          |     */
  42. /*     | Time of run     : Mon 15-Jul-1991 05:29PM                      |     */
  43. /*     | Timing accuracy : One part in 100                              |     */
  44. /*     | Context length  : 262144 bytes (= 256.0000K)                   |     */
  45. /*     | Test suite      : Calgary Corpus Suite                         |     */
  46. /*     | Files in suite  : 14                                           |     */
  47. /*     | Algorithm       : LZRW3-A                                      |     */
  48. /*     | Note: All averages are calculated from the un-rounded values.  |     */
  49. /*     +----------------------------------------------------------------+     */
  50. /*     | File Name   Length  CxB  ComLen  %Remn  Bits  Com K/s  Dec K/s |     */
  51. /*     | ----------  ------  ---  ------  -----  ----  -------  ------- |     */
  52. /*     | rpus:Bib.D  111261    1   49044   44.1  3.53     8.47    31.19 |     */
  53. /*     | us:Book1.D  768771    3  420464   54.7  4.38     7.27    30.07 |     */
  54. /*     | us:Book2.D  610856    3  277955   45.5  3.64     8.51    33.40 |     */
  55. /*     | rpus:Geo.D  102400    1   84218   82.2  6.58     4.23    15.04 |     */
  56. /*     | pus:News.D  377109    2  192880   51.1  4.09     7.08    25.89 |     */
  57. /*     | pus:Obj1.D   21504    1   12651   58.8  4.71     5.23    17.44 |     */
  58. /*     | pus:Obj2.D  246814    1  108044   43.8  3.50     8.01    28.11 |     */
  59. /*     | s:Paper1.D   53161    1   24526   46.1  3.69     8.11    30.24 |     */
  60. /*     | s:Paper2.D   82199    1   39483   48.0  3.84     8.11    32.04 |     */
  61. /*     | rpus:Pic.D  513216    2  111622   21.7  1.74    10.64    49.31 |     */
  62. /*     | us:Progc.D   39611    1   17923   45.2  3.62     8.06    29.01 |     */
  63. /*     | us:Progl.D   71646    1   24362   34.0  2.72    10.74    39.51 |     */
  64. /*     | us:Progp.D   49379    1   16805   34.0  2.72    10.64    37.58 |     */
  65. /*     | us:Trans.D   93695    1   30296   32.3  2.59    11.02    38.06 |     */
  66. /*     +----------------------------------------------------------------+     */
  67. /*     | Average     224401    1  100733   45.8  3.67     8.29    31.21 |     */
  68. /*     +----------------------------------------------------------------+     */
  69. /*                                                                            */
  70. /******************************************************************************/
  71.  
  72.                             /* INCLUDE FILES                                  */
  73.                             /* =============                                  */
  74. #include "port.h"           /* Defines symbols for the non portable stuff.    */
  75. #include "compress.h"       /* Defines single exported function "compress".   */
  76. #include "fast_copy.h"      /* Fast memory copy routine.                      */
  77.  
  78. /******************************************************************************/
  79.  
  80. /* The following structure is returned by the "compress" function below when  */
  81. /* the user asks the function to return identifying information.              */
  82. /* The most important field in the record is the working memory field which   */
  83. /* tells the calling program how much working memory should be passed to      */
  84. /* "compress" when it is called to perform a compression or decompression.    */
  85. /* LZRW3-A uses the same amount of memory during compression and              */
  86. /* decompression. For more information on this structure see "compress.h".    */
  87. /* The alignment fudge below really only needs to be 4 (but I play it safe!). */
  88. /* The id looks non-random, but it really was generated by coin tossing!      */
  89.  
  90. #define U(X)            ((ULONG) X)
  91. #define SIZE_P_BYTE     (U(sizeof(UBYTE *)))
  92. #define ALIGNMENT_FUDGE (U(16))
  93. #define MEM_REQ ( U(4096)*(SIZE_P_BYTE) + ALIGNMENT_FUDGE )
  94.  
  95. static struct compress_identity identity =
  96. {
  97.  U(0x01B90B91),                           /* Algorithm identification number. */
  98.  MEM_REQ,                                 /* Working memory (bytes) required. */
  99.  "LZRW3-A",                               /* Name of algorithm.               */
  100.  "1.0",                                   /* Version number of algorithm.     */
  101.  "15-Jul-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 LZRW3-A ALGORITHM                                 */
  143. /* ==========================================                                 */
  144. /* Note: Before attempting to understand this algorithm, you should first     */
  145. /* understand the LZRW3 algorithm from which this algorithm is derived.       */
  146. /*                                                                            */
  147. /* The LZRW3-A algorithm is identical to the LZRW3 algorithm except that the  */
  148. /* hash table has been "deepened". The LZRW3 algorithm has a hash table of    */
  149. /* 4096 pointers which point to strings in the buffer. LZRW3-A generalizes    */
  150. /* this to 4096/(2^n) partitions each of which contains (2^n) pointers.       */
  151. /* In LZRW3-A, the hash function hashes to a partition number.                */
  152. /*                                                                            */
  153. /* During the processing of each phrase, LZRW3 overwrites the pointer in the  */
  154. /* position selected by the hash function. LZRW3-A overwrites one of the      */
  155. /* pointers in the partition that was selected by the hash function.          */
  156. /*                                                                            */
  157. /* When searching for a match, LZRW3-A matches against all (2^n) strings      */
  158. /* pointed to by the pointers in the target partition.                        */
  159. /*                                                                            */
  160. /* Deep hash tables were used in early versions of LZRW1 in late 1989, but    */
  161. /* were discarded in an effort to increase speed (which was the primary       */
  162. /* requirement for LZRW1). They were revived for use in LZRW3-A in order to   */
  163. /* produce an algorithm with compression performance competitive with Unix    */
  164. /* compress.                                                                  */
  165. /*                                                                            */
  166. /* Until 14-Jul-1991, deep hash tables used in prototype LZRW* algorithms     */
  167. /* used a queue discipline within each partition. Upon the arrival of a new   */
  168. /* pointer, the pointers in the partition would be block copied back one      */
  169. /* position (with the oldest pointer being overwritten) and the new pointer   */
  170. /* being inserted in the space at the front (the youngest position).          */
  171. /* This meant that pointers to the (2^n) most recent phrases corresponding to */
  172. /* each hash was kept. The only flaw in this system was the time-consuming    */
  173. /* block copy operation which was cheap for shallow tables but expensive for  */
  174. /* deep tables.                                                               */
  175. /*                                                                            */
  176. /* The traditional solution to ring buffer block copy problems is to maintain */
  177. /* a cyclic counter which points to the "head" of the queue. However, this    */
  178. /* would have required one counter to be stored for each partition and would  */
  179. /* have been slightly messy. After some thought (on 14-Jul-1991) a better     */
  180. /* solution was found. Instead of maintaining a counter for each partition,   */
  181. /* LZRW3-A maintains a single counter for all partitions! This counter is     */
  182. /* maintained in both the compressor and decompressor and means that the      */
  183. /* algorithm (effectively) overwrites a RANDOM element of the partition to be */
  184. /* updated. The result was to increase the speed of the compressor and        */
  185. /* decompressor, to make the decompressor's speed independent from whatever   */
  186. /* depth was selected, and to impair compression by less than 1% absolute.    */
  187. /*                                                                            */
  188. /* Setting the depth is a speed/compression tradeoff. The table below gives   */
  189. /* the tradeoff observed for a typical 50K text file on a Mac-SE.             */
  190. /* Note: %Rem=Percentage Remaining (after compression).                       */
  191. /*                                                                            */
  192. /*      Depth    %Rem    CmpK/s  DecK/s                                       */
  193. /*          1    45.2    14.77   32.24                                        */
  194. /*          2    42.6    12.12   31.26                                        */
  195. /*          4    40.9    10.28   31.91                                        */
  196. /*          8    40.0     7.81   32.36                                        */
  197. /*         16    39.5     5.30   32.47                                        */
  198. /*         32    39.0     3.23   32.59                                        */
  199. /*                                                                            */
  200. /* I have chosen a depth of 8 as the "default" depth for LZRW3-A. If you use  */
  201. /* a depth different to this (e.g. 4), you should use the name LZRW3-A(4) to  */
  202. /* indicate that a different depth is being used. LZRW3-A(8) is an acceptable */
  203. /* longhand for LZRW3-A.                                                      */
  204. /*                                                                            */
  205. /* To change the depth, search for "HERE IT IS" in the rest of this file.     */
  206. /*                                                                            */
  207. /*                                  +---+                                     */
  208. /*                                  |___|4095                                 */
  209. /*                                  |===|                                     */
  210. /*              +---------------------*_|<---+   /----+---\                   */
  211. /*              |                   |___|    +---|Hash    |                   */
  212. /*              |    512 partitions |___|        |Function|                   */
  213. /*              |    of 8 pointers  |===|        \--------/                   */
  214. /*              |    each (or any   |___|0            ^                       */
  215. /*              |    a*b=4096)      +---+             |                       */
  216. /*              |                   Hash        +-----+                       */
  217. /*              |                   Table       |                             */
  218. /*              |                              ---                            */
  219. /*              v                              ^^^                            */
  220. /*      +-------------------------------------|----------------+              */
  221. /*      ||||||||||||||||||||||||||||||||||||||||||||||||||||||||              */
  222. /*      +-------------------------------------|----------------+              */
  223. /*      |                                     |1......18|      |              */
  224. /*      |<------- Lempel=History ------------>|<--Ziv-->|      |              */
  225. /*      |     (=bytes already processed)      |<-Still to go-->|              */
  226. /*      |<-------------------- INPUT BLOCK ------------------->|              */
  227. /*                                                                            */
  228. /*                                                                            */
  229. /******************************************************************************/
  230. /*                                                                            */
  231. /*                     DEFINITION OF COMPRESSED FILE FORMAT                   */
  232. /*                     ====================================                   */
  233. /*  * A compressed file consists of a COPY FLAG followed by a REMAINDER.      */
  234. /*  * The copy flag CF uses up four bytes with the first byte being the       */
  235. /*    least significant.                                                      */
  236. /*  * If CF=1, then the compressed file represents the remainder of the file  */
  237. /*    exactly. Otherwise CF=0 and the remainder of the file consists of zero  */
  238. /*    or more GROUPS, each of which represents one or more bytes.             */
  239. /*  * Each group consists of two bytes of CONTROL information followed by     */
  240. /*    sixteen ITEMs except for the last group which can contain from one      */
  241. /*    to sixteen items.                                                       */
  242. /*  * An item can be either a LITERAL item or a COPY item.                    */
  243. /*  * Each item corresponds to a bit in the control bytes.                    */
  244. /*  * The first control byte corresponds to the first 8 items in the group    */
  245. /*    with bit 0 corresponding to the first item in the group and bit 7 to    */
  246. /*    the eighth item in the group.                                           */
  247. /*  * The second control byte corresponds to the second 8 items in the group  */
  248. /*    with bit 0 corresponding to the ninth item in the group and bit 7 to    */
  249. /*    the sixteenth item in the group.                                        */
  250. /*  * A zero bit in a control word means that the corresponding item is a     */
  251. /*    literal item. A one bit corresponds to a copy item.                     */
  252. /*  * A literal item consists of a single byte which represents itself.       */
  253. /*  * A copy item consists of two bytes that represent from 3 to 18 bytes.    */
  254. /*  * The first  byte in a copy item will be denoted C1.                      */
  255. /*  * The second byte in a copy item will be denoted C2.                      */
  256. /*  * Bits will be selected using square brackets.                            */
  257. /*    For example: C1[0..3] is the low nibble of the first control byte.      */
  258. /*    of copy item C1.                                                        */
  259. /*  * The LENGTH of a copy item is defined to be C1[0..3]+3 which is a number */
  260. /*    in the range [3,18].                                                    */
  261. /*  * The INDEX of a copy item is defined to be C1[4..7]*256+C2[0..8] which   */
  262. /*    is a number in the range [0,4095].                                      */
  263. /*  * A copy item represents the sequence of bytes                            */
  264. /*       text[POS-OFFSET..POS-OFFSET+LENGTH-1] where                          */
  265. /*          text   is the entire text of the uncompressed string.             */
  266. /*          POS    is the index in the text of the character following the    */
  267. /*                   string represented by all the items preceeding the item  */
  268. /*                   being defined.                                           */
  269. /*          OFFSET is obtained from INDEX by looking up the hash table.       */
  270. /*                                                                            */
  271. /******************************************************************************/
  272.  
  273. /* When I first started to get concerned about the portability of my C code,  */
  274. /* I switched over to using only macro defined types UBYTE, UWORD, ULONG and  */
  275. /* one or two others. While, these are useful for most purposes, they impair  */
  276. /* efficiency as, if I have a variable whose range will be [0,1000], I will   */
  277. /* declare it as a UWORD. This will translate into (say) "short int" and      */
  278. /* hence may be less efficient than just an "int" which represents the        */
  279. /* natural size of the machine. Before releasing LZRW3-A, I realized this     */
  280. /* mistake. Unfortunately, I can't access the ftp archive with my portability */
  281. /* header in it in time for this algorithm's release and so I am including an */
  282. /* extra definition. The definition UCARD stands for an unsigned (cardinal)   */
  283. /* type that can hold values in the range [0,32767]. This is within the ANSI  */
  284. /* range of a standard int or unsigned. No assumption about overflow of this  */
  285. /* type is made in the code (i.e. all usages are within range and I do not    */
  286. /* use the value -1 to detect the end of loops.).                             */
  287. /* You can use either "unsigned" or just "int" here depending on which is     */
  288. /* more efficient in your environment (both the same probably).               */
  289. #define UCARD unsigned
  290.  
  291. /* The following #define defines the length of the copy flag that appears at  */
  292. /* the start of the compressed file. The value of four bytes was chosen       */
  293. /* because the fast_copy routine on my Macintosh runs faster if the source    */
  294. /* and destination blocks are relatively longword aligned.                    */
  295. /* The actual flag data appears in the first byte. The rest are zeroed so as  */
  296. /* to normalize the compressed representation (i.e. not non-deterministic).   */
  297. #define FLAG_BYTES 4
  298.  
  299. /* The following #defines define the meaning of the values of the copy        */
  300. /* flag at the start of the compressed file.                                  */
  301. #define FLAG_COMPRESS 0     /* Signals that output was result of compression. */
  302. #define FLAG_COPY     1     /* Signals that output was simply copied over.    */
  303.  
  304. /* The 68000 microprocessor (on which this algorithm was originally developed */
  305. /* is fussy about non-aligned arrays of words. To avoid these problems the    */
  306. /* following macro can be used to "waste" from 0 to 3 bytes so as to align    */
  307. /* the argument pointer.                                                      */
  308. #define ULONG_ALIGN_UP(X) ((((ULONG)X)+3)&~3)
  309.  
  310. /* The following constant defines the maximum length of an uncompressed item. */
  311. /* This definition must not be changed; its value is hardwired into the code. */
  312. /* The longest number of bytes that can be spanned by a single item is 18     */
  313. /* for the longest copy item.                                                 */
  314. #define MAX_RAW_ITEM (18)
  315.  
  316. /* The following constant defines the maximum length of an uncompressed group.*/
  317. /* This definition must not be changed; its value is hardwired into the code. */
  318. /* A group contains at most 16 items which explains this definition.          */
  319. #define MAX_RAW_GROUP (16*MAX_RAW_ITEM)
  320.  
  321. /* The following constant defines the maximum length of a compressed group.   */
  322. /* This definition must not be changed; its value is hardwired into the code. */
  323. /* A compressed group consists of two control bytes followed by up to 16      */
  324. /* compressed items each of which can have a maximum length of two bytes.     */
  325. #define MAX_CMP_GROUP (2+16*2)
  326.  
  327. /* This constant defines the number of pointers in the hash table. The number */
  328. /* of partitions multiplied by the number of pointers in each partition must  */
  329. /* multiply out to this value of 4096. In LZRW1, LZRW1-A, and LZRW2, this     */
  330. /* table length value can be changed. However, in LZRW3-A (and LZRW3), the    */
  331. /* table length cannot be changed because it is connected directly to the     */
  332. /* coding scheme which is hardwired (the table index of a single pointer is   */
  333. /* transmitted in the 12-bit index field). So don't change this constant!     */
  334. #define HASH_TABLE_LENGTH (4096)
  335.  
  336. /* HERE IT IS: THE PLACE TO CHANGE THE HASH TABLE DEPTH!                      */
  337. /* The following definition is the log_2 of the depth of the hash table. This */
  338. /* constant can be in the range [0,1,2,3,...,12]. Increasing the depth        */
  339. /* increases compression at the expense of speed. However, you are not likely */
  340. /* to see much of a compression improvement (e.g. not more than 0.5%) above a */
  341. /* value of 6 and the algorithm will start to get very slow. See the table in */
  342. /* the earlier comments block for an idea of the trade-off involved.          */
  343. /* Note: The parentheses are to avoid macro substitution funnies.             */
  344. /* Note: The LZRW3-A default is a value of (3).                               */
  345. /* Note: If you end up choosing a value of 0, you should use LZRW3 instead.   */
  346. /* Note: Changing the value of HASH_TABLE_DEPTH_BITS is the ONLY thing you    */
  347. /* have to do to change the depth, so go ahead and recompile now!             */
  348. /* Note: I have tested LZRW3-A for DEPTH_BITS=0,1,2,3,4 and a few other       */
  349. /* values. However, I have not tested it for 12 as I can't wait that long!    */
  350. #define HASH_TABLE_DEPTH_BITS (3)      /* Must be in range [0,12].            */
  351.  
  352. /* The following definitions are all self-explanatory and follow from the     */
  353. /* definition of HASH_TABLE_DEPTH_BITS and the hardwired requirement that the */
  354. /* hash table contain exactly 4096 pointers.                                  */
  355. #define PARTITION_LENGTH_BITS (12-HASH_TABLE_DEPTH_BITS)
  356. #define PARTITION_LENGTH      (1<<PARTITION_LENGTH_BITS)
  357. #define HASH_TABLE_DEPTH      (1<<HASH_TABLE_DEPTH_BITS )
  358. #define HASH_MASK             (PARTITION_LENGTH-1)
  359. #define DEPTH_MASK            (HASH_TABLE_DEPTH-1)
  360.  
  361. /* LZRW3-A, unlike LZRW1(-A), must initialize its hash table so as to enable  */
  362. /* the compressor and decompressor to stay in step maintaining identical hash */
  363. /* tables. In an early version of LZRW3, the tables were simply               */
  364. /* initialized to zero and a check for zero was included just before the      */
  365. /* matching code. However, this test costs time. A better solution is to      */
  366. /* initialize all the entries in the hash table to point to a constant        */
  367. /* string. The decompressor does the same. This solution requires no extra    */
  368. /* test. The contents of the string do not matter so long as the string is    */
  369. /* the same for the compressor and decompressor and contains at least         */
  370. /* MAX_RAW_ITEM bytes. I chose consecutive decimal digits because they do not */
  371. /* have white space problems (e.g. there is no chance that the compiler will  */
  372. /* replace more than one space by a TAB) and because they make the length of  */
  373. /* the string obvious by inspection.                                          */
  374. #define START_STRING_18 ((UBYTE *) "123456789012345678")
  375.  
  376. /* The following macro accepts a pointer PTR to three consecutive bytes in    */
  377. /* memory and hashes them into an integer that is a hash table index that     */
  378. /* points to the zeroth (first) element of a partition. Thus, the hash        */
  379. /* function really hashes to a partition number but, for convenience,         */
  380. /* multiplies it up to yield a hash table index. From all this, we see that   */
  381. /* the resultant number is in the range [0,HASH_TABLE_LENGTH-1] and is a      */
  382. /* multiple of HASH_TABLE_DEPTH.                                              */
  383. /* A macro is used, because in LZRW3-A we have to hash more than once.        */
  384. #define HASH(PTR) \
  385.  ( \
  386.      (((40543*(((*(PTR))<<8)^((*((PTR)+1))<<4)^(*((PTR)+2))))>>4) & HASH_MASK) \
  387.   << HASH_TABLE_DEPTH_BITS \
  388.  )
  389.  
  390. /* Another operation that is performed more than once is the updating of the  */
  391. /* hash table. Here two macros are defined to simplify update operations.     */
  392. /* Updating consists of identifying and overwriting a pointer in a partition  */
  393. /* with a newer pointer and then updating the global cycle value.             */
  394. /* These macros accept the new pointer (NEWPTR) and either a pointer to       */
  395. /* (P_BASE) or the index of (I_BASE) the zeroth (first, or base) pointer in   */
  396. /* the partition that is to be updated. The macros use the 'cycle' variable   */
  397. /* to locate and overwrite a pointer and then update the cycle value.         */
  398. /* Note: Hardcoding 'cycle' in this macro is naughty (it should really be a   */
  399. /* macro parameter), but I have done so because it neatens up the code.       */
  400. #define UPDATE_P(P_BASE,NEWPTR) \
  401. {(P_BASE)[cycle++]=(NEWPTR); cycle&=DEPTH_MASK;}
  402.  
  403. #define UPDATE_I(I_BASE,NEWPTR) \
  404. {hash[(I_BASE)+cycle++]=(NEWPTR); cycle&=DEPTH_MASK;}
  405.  
  406. /* This constant supplies a legal (in-range) hash table index for use when    */
  407. /* a legal-but-don't-care index is required.                                  */
  408. #define ANY_HASH_INDEX (0)
  409.  
  410. /******************************************************************************/
  411.  
  412. LOCAL void compress_compress
  413.            (p_wrk_mem,p_src_first,src_len,p_dst_first,p_dst_len)
  414. /* Input  : Hand over the required amount of working memory in p_wrk_mem.     */
  415. /* Input  : Specify input block using p_src_first and src_len.                */
  416. /* Input  : Point p_dst_first to the start of the output zone (OZ).           */
  417. /* Input  : Point p_dst_len to a ULONG to receive the output length.          */
  418. /* Input  : Input block and output zone must not overlap.                     */
  419. /* Output : Length of output block written to *p_dst_len.                     */
  420. /* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1]. May   */
  421. /* Output : write in OZ=Mem[p_dst_first..p_dst_first+src_len+MAX_CMP_GROUP-1].*/
  422. /* Output : Upon completion guaranteed *p_dst_len<=src_len+FLAG_BYTES.        */
  423. UBYTE *p_wrk_mem;
  424. UBYTE *p_src_first;
  425. ULONG  src_len;
  426. UBYTE *p_dst_first;
  427. ULONG *p_dst_len;
  428. {
  429.  /* p_src and p_dst step through the source and destination blocks.           */
  430.  UBYTE *p_src = p_src_first;
  431.  UBYTE *p_dst = p_dst_first;
  432.  
  433.  /* The following variables are never modified and are used in the            */
  434.  /* calculations that determine when the main loop terminates.                */
  435.  UBYTE *p_src_post  = p_src_first+src_len;
  436.  UBYTE *p_dst_post  = p_dst_first+src_len;
  437.  UBYTE *p_src_max1  = p_src_first+src_len-MAX_RAW_ITEM;
  438.  UBYTE *p_src_max16 = p_src_first+src_len-MAX_RAW_ITEM*16;
  439.  
  440.  /* The variables 'p_control' and 'control' are used to buffer control bits.  */
  441.  /* Before each group is processed, the next two bytes of the output block    */
  442.  /* are set aside for the control word for the group about to be processed.   */
  443.  /* 'p_control' is set to point to the first byte of that word. Meanwhile,    */
  444.  /* 'control' buffers the control bits being generated during the processing  */
  445.  /* of the group. Instead of having a counter to keep track of how many items */
  446.  /* have been processed (=the number of bits in the control word), at the     */
  447.  /* start of each group, the top word of 'control' is filled with 1 bits.     */
  448.  /* As 'control' is shifted for each item, the 1 bits in the top word are     */
  449.  /* absorbed or destroyed. When they all run out (i.e. when the top word is   */
  450.  /* all zero bits, we know that we are at the end of a group.                 */
  451.  #define TOPWORD 0xFFFF0000
  452.  UBYTE *p_control;
  453.  ULONG control=TOPWORD;
  454.  
  455.  /* The variable 'hash' always points to the first element of the hash table. */
  456.  UBYTE **hash= (UBYTE **) ULONG_ALIGN_UP(p_wrk_mem);
  457.  
  458.  /* The following two variables represent the literal buffer. p_h1 points to  */
  459.  /* the partition (i.e. the zero'th (first) element of the partition)         */
  460.  /* corresponding to the youngest literal. p_h2 points to the partition       */
  461.  /* corresponding to the second youngest literal.                             */
  462.  /* The value zero denotes an "empty" buffer value with p_h1=0 => p_h2=0.     */
  463.  UBYTE **p_h1=0;
  464.  UBYTE **p_h2=0;
  465.  
  466.  /* The following variable holds the current 'cycle' value. This value cycles */
  467.  /* through the range [0,HASH_TABLE_DEPTH-1], being incremented every time    */
  468.  /* the hash table is updated. The value gives the within-partition number of */
  469.  /* the next pointer to be overwritten. The decompressor maintains a cycle    */
  470.  /* value in synchrony.                                                       */
  471.  UCARD cycle=0;
  472.  
  473.  /* To start, we write the flag bytes. Being optimistic, we set the flag to   */
  474.  /* FLAG_COMPRESS. The remaining flag bytes are zeroed so as to keep the      */
  475.  /* algorithm deterministic.                                                  */
  476.  *p_dst++=FLAG_COMPRESS;
  477.  {UCARD i; for (i=2;i<=FLAG_BYTES;i++) *p_dst++=0;}
  478.  
  479.  /* Reserve the first word of output as the control word for the first group. */
  480.  /* Note: This is undone at the end if the input block is empty.              */
  481.  p_control=p_dst; p_dst+=2;
  482.  
  483.  /* Initialize all elements of the hash table to point to a constant string.  */
  484.  /* Use of an unrolled loop speeds this up considerably.                      */
  485.  /* These variables should really be declared "register", but I am worried    */
  486.  /* about the possibility that extra register declarations will tempt stupid  */
  487.  /* compilers to allocate all registers before they get to the innermostloop. */
  488.  {UCARD i; UBYTE **p_h=hash;
  489.   #define ZH *p_h++=START_STRING_18
  490.   for (i=0;i<256;i++)     /* 256=HASH_TABLE_LENGTH/16. */
  491.     {ZH;ZH;ZH;ZH;
  492.      ZH;ZH;ZH;ZH;
  493.      ZH;ZH;ZH;ZH;
  494.      ZH;ZH;ZH;ZH;}
  495.  }
  496.  
  497.  /* The main loop processes either 1 or 16 items per iteration. As its        */
  498.  /* termination logic is complicated, I have opted for an infinite loop       */
  499.  /* structure containing 'break' and 'goto' statements.                       */
  500.  while (TRUE)
  501.    {/* Begin main processing loop. */
  502.  
  503.     /* Note: All the variables here except unroll should be defined within    */
  504.     /*       the inner loop. Unfortunately the loop hasn't got a block.       */
  505.      UBYTE *p_ziv;              /* Points to first byte of current Ziv.       */
  506.      UCARD unroll;              /* Loop counter for unrolled inner loop.      */
  507.      UCARD index;               /* Index of current partition.                */
  508.      UBYTE **p_h0;              /* Pointer to current partition.              */
  509.      register UCARD d;          /* Depth looping variable.                    */
  510.      register UCARD bestlen;    /* Holds the best length seen so far.         */
  511.      register UCARD bestpos;    /* Holds number of best pointer seen so far.  */
  512.  
  513.     /* Test for overrun and jump to overrun code if necessary.                */
  514.     if (p_dst>p_dst_post)
  515.        goto overrun;
  516.  
  517.     /* The following cascade of if statements efficiently catches and deals   */
  518.     /* with varying degrees of closeness to the end of the input block.       */
  519.     /* When we get very close to the end, we stop updating the table and      */
  520.     /* code the remaining bytes as literals. This makes the code simpler.     */
  521.     unroll=16;
  522.     if (p_src>p_src_max16)
  523.       {
  524.        unroll=1;
  525.        if (p_src>p_src_max1)
  526.          {
  527.           if (p_src==p_src_post)
  528.              break;
  529.           else
  530.              {p_h0=&hash[ANY_HASH_INDEX]; /* Avoid undefined pointer. */
  531.               goto literal;}
  532.          }
  533.       }
  534.  
  535.     /* This inner unrolled loop processes 'unroll' (whose value is either 1   */
  536.     /* or 16) items. I have chosen to implement this loop with labels and     */
  537.     /* gotos to heighten the ease with which the loop may be implemented with */
  538.     /* a single decrement and branch instruction in assembly language and     */
  539.     /* also because the labels act as highly readable place markers.          */
  540.     /* (Also because we jump into the loop for endgame literals (see above)). */
  541.  
  542.     begin_unrolled_loop:
  543.  
  544.        p_ziv=p_src;
  545.  
  546.        /* To process the next phrase, we hash the next three bytes to obtain  */
  547.        /* an index to the zeroth (first) pointer in a target partition. We    */
  548.        /* get the pointer.                                                    */
  549.        index=HASH(p_src);
  550.        p_h0=&hash[index];
  551.  
  552.        /* This next part runs through the pointers in the partition matching  */
  553.        /* the bytes they point to in the Lempel with the bytes in the Ziv.    */
  554.        /* The length (bestlen) and within-partition pointer number (bestpos)  */
  555.        /* of the longest match so far is maintained and is the output of this */
  556.        /* segment of code. The s[bestlen]==... is an optimization only.       */
  557.        bestlen=0;
  558.        bestpos=0;
  559.        for (d=0;d<HASH_TABLE_DEPTH;d++)
  560.          {
  561.           register UBYTE *s=p_src;
  562.           register UBYTE *p=p_h0[d];
  563.           register UCARD len;
  564.           if (s[bestlen] == p[bestlen])
  565.             {
  566.              #define PS *p++!=*s++
  567.              PS || PS || PS || PS || PS || PS || PS || PS || PS ||
  568.              PS || PS || PS || PS || PS || PS || PS || PS || PS || s++;
  569.              len=s-p_src-1;
  570.              if (len>bestlen)
  571.                {
  572.                 bestpos=d;
  573.                 bestlen=len;
  574.                }
  575.             }
  576.          }
  577.  
  578.        /* The length of the longest match determines whether we code a */
  579.        /* literal item or a copy item.                                 */
  580.  
  581.        if (bestlen<3)
  582.          {
  583.           /* Literal. */
  584.  
  585.           /* Code the literal byte as itself and a zero control bit.          */
  586.           literal: *p_dst++=*p_src++; control&=0xFFFEFFFF;
  587.  
  588.           /* We have just coded a literal. If we had two pending ones, that   */
  589.           /* makes three and we can update the hash table.                    */
  590.           if (p_h2!=0)
  591.              {UPDATE_P(p_h2,p_ziv-2);}
  592.  
  593.           /* In any case, rotate the hash table pointers for next time. */
  594.           p_h2=p_h1; p_h1=p_h0;
  595.  
  596.          }
  597.        else
  598.          {
  599.           /* Copy */
  600.  
  601.           /* To code a copy item, we construct a hash table index of the      */
  602.           /* winning pointer (index+=bestpos) and code it and the best length */
  603.           /* into a 2 byte code word. Bump up p_src.                          */
  604.           index+=bestpos;
  605.           *p_dst++=((index&0xF00)>>4)|(bestlen-3);
  606.           *p_dst++=index&0xFF;
  607.           p_src+=bestlen;
  608.  
  609.           /* As we have just coded three bytes, we are now in a position to   */
  610.           /* update the hash table with the literal bytes that were pending   */
  611.           /* upon the arrival of extra context bytes.                         */
  612.           if (p_h1!=0)
  613.             {
  614.              if (p_h2!=0)
  615.                {UPDATE_P(p_h2,p_ziv-2); p_h2=0;}
  616.              UPDATE_P(p_h1,p_ziv-1); p_h1=0;
  617.             }
  618.  
  619.           /* In any case, we can update the hash table based on the current   */
  620.           /* position as we just coded at least three bytes in a copy items.  */
  621.           UPDATE_P(p_h0,p_ziv);
  622.          }
  623.        control>>=1;
  624.  
  625.        /* This loop is all set up for a decrement and jump instruction! */
  626.     end_unrolled_loop: if (--unroll) goto begin_unrolled_loop;
  627.  
  628.     /* At this point it will nearly always be the end of a group in which     */
  629.     /* case, we have to do some control-word processing. However, near the    */
  630.     /* end of the input block, the inner unrolled loop is only executed once. */
  631.     /* This necessitates the 'if' test.                                       */
  632.     if ((control&TOPWORD)==0)
  633.       {
  634.        /* Write the control word to the place we saved for it in the output. */
  635.        *p_control++=  control     &0xFF;
  636.        *p_control  = (control>>8) &0xFF;
  637.  
  638.        /* Reserve the next word in the output block for the control word */
  639.        /* for the group about to be processed.                           */
  640.        p_control=p_dst; p_dst+=2;
  641.  
  642.        /* Reset the control bits buffer. */
  643.        control=TOPWORD;
  644.       }
  645.  
  646.    } /* End main processing loop. */
  647.  
  648.  /* After the main processing loop has executed, all the input bytes have     */
  649.  /* been processed. However, the control word has still to be written to the  */
  650.  /* word reserved for it in the output at the start of the most recent group. */
  651.  /* Before writing, the control word has to be shifted so that all the bits   */
  652.  /* are in the right place. The "empty" bit positions are filled with 1s      */
  653.  /* which partially fill the top word.                                        */
  654.  while(control&TOPWORD) control>>=1;
  655.  *p_control++= control     &0xFF;
  656.  *p_control++=(control>>8) &0xFF;
  657.  
  658.  /* If the last group contained no items, delete the control word too.        */
  659.  if (p_control==p_dst) p_dst-=2;
  660.  
  661.  /* Write the length of the output block to the dst_len parameter and return. */
  662.  *p_dst_len=p_dst-p_dst_first;
  663.  return;
  664.  
  665.  /* Jump here as soon as an overrun is detected. An overrun is defined to     */
  666.  /* have occurred if p_dst>p_dst_first+src_len. That is, the moment the       */
  667.  /* length of the output written so far exceeds the length of the input block.*/
  668.  /* The algorithm checks for overruns at least at the end of each group       */
  669.  /* which means that the maximum overrun is MAX_CMP_GROUP bytes.              */
  670.  /* Once an overrun occurs, the only thing to do is to set the copy flag and  */
  671.  /* copy the input over.                                                      */
  672.  overrun:
  673.  *p_dst_first=FLAG_COPY;
  674.  fast_copy(p_src_first,p_dst_first+FLAG_BYTES,src_len);
  675.  *p_dst_len=src_len+FLAG_BYTES;
  676. }
  677.  
  678. /******************************************************************************/
  679.  
  680. LOCAL void compress_decompress
  681.            (p_wrk_mem,p_src_first,src_len,p_dst_first,p_dst_len)
  682. /* Input  : Hand over the required amount of working memory in p_wrk_mem.     */
  683. /* Input  : Specify input block using p_src_first and src_len.                */
  684. /* Input  : Point p_dst_first to the start of the output zone.                */
  685. /* Input  : Point p_dst_len to a ULONG to receive the output length.          */
  686. /* Input  : Input block and output zone must not overlap. User knows          */
  687. /* Input  : upperbound on output block length from earlier compression.       */
  688. /* Input  : In any case, maximum expansion possible is nine times.            */
  689. /* Output : Length of output block written to *p_dst_len.                     */
  690. /* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1].       */
  691. /* Output : Writes only  in Mem[p_dst_first..p_dst_first+*p_dst_len-1].       */
  692. UBYTE *p_wrk_mem;
  693. UBYTE *p_src_first;
  694. ULONG  src_len;
  695. UBYTE *p_dst_first;
  696. ULONG *p_dst_len;
  697. {
  698.  /* Byte pointers p_src and p_dst scan through the input and output blocks.   */
  699.  register UBYTE *p_src = p_src_first+FLAG_BYTES;
  700.  register UBYTE *p_dst = p_dst_first;
  701.  
  702.  /* The following two variables are never modified and are used to control    */
  703.  /* the main loop.                                                            */
  704.  UBYTE *p_src_post  = p_src_first+src_len;
  705.  UBYTE *p_src_max16 = p_src_first+src_len-(MAX_CMP_GROUP-2);
  706.  
  707.  /* The hash table is the only resident of the working memory. The hash table */
  708.  /* contains HASH_TABLE_LENGTH=4096 pointers to positions in the history. To  */
  709.  /* keep Macintoshes happy, it is longword aligned.                           */
  710.  UBYTE **hash = (UBYTE **) ULONG_ALIGN_UP(p_wrk_mem);
  711.  
  712.  /* The variable 'control' is used to buffer the control bits which appear in */
  713.  /* groups of 16 bits (control words) at the start of each compressed group.  */
  714.  /* When each group is read, bit 16 of the register is set to one. Whenever   */
  715.  /* a new bit is needed, the register is shifted right. When the value of the */
  716.  /* register becomes 1, we know that we have reached the end of a group.      */
  717.  /* Initializing the register to 1 thus instructs the code to follow that it  */
  718.  /* should read a new control word immediately.                               */
  719.  register ULONG control=1;
  720.  
  721.  /* The value of 'literals' is always in the range 0..3. It is the number of  */
  722.  /* consecutive literal items just seen. We have to record this number so as  */
  723.  /* to know when to update the hash table. When literals gets to 3, there     */
  724.  /* have been three consecutive literals and we can update at the position of */
  725.  /* the oldest of the three.                                                  */
  726.  register UCARD literals=0;
  727.  
  728.  /* The following variable holds the current 'cycle' value. This value cycles */
  729.  /* through the range [0,HASH_TABLE_DEPTH-1], being incremented every time    */
  730.  /* the hash table is updated. The value give the within-partition number of  */
  731.  /* the next pointer to be overwritten. The compressor maintains a cycle      */
  732.  /* value in synchrony.                                                       */
  733.  UCARD cycle=0;
  734.  
  735.  /* Check the leading copy flag to see if the compressor chose to use a copy  */
  736.  /* operation instead of a compression operation. If a copy operation was     */
  737.  /* used, then all we need to do is copy the data over, set the output length */
  738.  /* and return.                                                               */
  739.  if (*p_src_first==FLAG_COPY)
  740.    {
  741.     fast_copy(p_src_first+FLAG_BYTES,p_dst_first,src_len-FLAG_BYTES);
  742.     *p_dst_len=src_len-FLAG_BYTES;
  743.     return;
  744.    }
  745.  
  746.  /* Initialize all elements of the hash table to point to a constant string.  */
  747.  /* Use of an unrolled loop speeds this up considerably.                      */
  748.  /* The comment about register declarations above similar code in the         */
  749.  /* compressor applies here too.                                              */
  750.  {UCARD i; UBYTE **p_h=hash;
  751.   #define ZJ *p_h++=START_STRING_18
  752.   for (i=0;i<256;i++)     /* 256=HASH_TABLE_LENGTH/16. */
  753.     {ZJ;ZJ;ZJ;ZJ;
  754.      ZJ;ZJ;ZJ;ZJ;
  755.      ZJ;ZJ;ZJ;ZJ;
  756.      ZJ;ZJ;ZJ;ZJ;}
  757.  }
  758.  
  759.  /* The outer loop processes either 1 or 16 items per iteration depending on  */
  760.  /* how close p_src is to the end of the input block.                         */
  761.  while (p_src!=p_src_post)
  762.    {/* Start of outer loop */
  763.  
  764.     register UCARD unroll;   /* Counts unrolled loop executions.              */
  765.  
  766.     /* When 'control' has the value 1, it means that the 16 buffered control  */
  767.     /* bits that were read in at the start of the current group have all been */
  768.     /* shifted out and that all that is left is the 1 bit that was injected   */
  769.     /* into bit 16 at the start of the current group. When we reach the end   */
  770.     /* of a group, we have to load a new control word and inject a new 1 bit. */
  771.     if (control==1)
  772.       {
  773.        control=0x10000|*p_src++;
  774.        control|=(*p_src++)<<8;
  775.       }
  776.  
  777.     /* If it is possible that we are within 16 groups from the end of the     */
  778.     /* input, execute the unrolled loop only once, else process a whole group */
  779.     /* of 16 items by looping 16 times.                                       */
  780.     unroll= p_src<=p_src_max16 ? 16 : 1;
  781.  
  782.     /* This inner loop processes one phrase (item) per iteration. */
  783.     while (unroll--)
  784.       { /* Begin unrolled inner loop. */
  785.  
  786.        /* Process a literal or copy item depending on the next control bit. */
  787.        if (control&1)
  788.          {
  789.           /* Copy item. */
  790.  
  791.           register UBYTE *p;           /* Points to place from which to copy. */
  792.           register UCARD lenmt;        /* Length of copy item minus three.    */
  793.           register UBYTE *p_ziv=p_dst; /* Pointer to start of current Ziv.    */
  794.           register UCARD index;        /* Index of hash table copy pointer.   */
  795.  
  796.           /* Read and dismantle the copy word. Work out from where to copy.   */
  797.           lenmt=*p_src++;
  798.           index=((lenmt&0xF0)<<4)|*p_src++;
  799.           p=hash[index];
  800.           lenmt&=0xF;
  801.  
  802.           /* Now perform the copy using a half unrolled loop. */
  803.           *p_dst++=*p++;
  804.           *p_dst++=*p++;
  805.           *p_dst++=*p++;
  806.           while (lenmt--)
  807.              *p_dst++=*p++;
  808.  
  809.           /* Because we have just received 3 or more bytes in a copy item     */
  810.           /* (whose bytes we have just installed in the output), we are now   */
  811.           /* in a position to flush all the pending literal hashings that had */
  812.           /* been postponed for lack of bytes.                                */
  813.           if (literals>0)
  814.             {
  815.              register UBYTE *r=p_ziv-literals;;
  816.              UPDATE_I(HASH(r),r);
  817.              if (literals==2)
  818.                 {r++; UPDATE_I(HASH(r),r);}
  819.              literals=0;
  820.             }
  821.  
  822.           /* In any case, we can immediately update the hash table with the   */
  823.           /* current position. We don't need to do a HASH(...) to work out    */
  824.           /* where to put the pointer, as the compressor just told us!!!      */
  825.           UPDATE_I(index&(~DEPTH_MASK),p_ziv);
  826.          }
  827.        else
  828.          {
  829.           /* Literal item. */
  830.  
  831.           /* Copy over the literal byte. */
  832.           *p_dst++=*p_src++;
  833.  
  834.           /* If we now have three literals waiting to be hashed into the hash */
  835.           /* table, we can do one of them now (because there are three).      */
  836.           if (++literals == 3)
  837.              {register UBYTE *p=p_dst-3;
  838.               UPDATE_I(HASH(p),p); literals=2;}
  839.          }
  840.  
  841.        /* Shift the control buffer so the next control bit is in bit 0. */
  842.        control>>=1;
  843.  
  844.       } /* End unrolled inner loop. */
  845.  
  846.    } /* End of outer loop */
  847.  
  848.  /* Write the length of the decompressed data before returning. */
  849.  *p_dst_len=p_dst-p_dst_first;
  850. }
  851.  
  852. /******************************************************************************/
  853. /*                              End of LZRW3-A.C                              */
  854. /******************************************************************************/
  855.  
  856.