home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / FREEZE-2.ZIP / README < prev    next >
Text File  |  1992-07-18  |  8KB  |  204 lines
  1.         FREEZE / MELT COMPRESSION PROGRAM
  2.  
  3. This is Alpha version. It is tested under ISC 2.2, Xenix, SunOS.
  4.  
  5. The following preprocessor symbols control the compilation of Freeze
  6. package:
  7.  
  8.     o BITS                  The size of hash table (default is 16,
  9.                 reducing to 14 gives some speeddown).
  10.     o COMPAT                Turns on backwards compatibility
  11.                 with Freeze 1.0
  12.     o M_XENIX & !M_I386     Makes arrays < 65536 bytes each
  13.     o BSD                   Allow long filenames ( > 14 characters) &
  14.                 Call setlinebuf(stderr)
  15.     o INT_SIG               signal is int (*)() unstead of void
  16.     o MSDOS                 Turns off some UNIX-dependencies
  17.                 and MSDOS' ones - vice versa
  18.                 !!! It's important !!!
  19.                 If your MSDOS' C compiler does support
  20.                 inline functions, define DO_INLINE.
  21.                 This will cause the main loop to be
  22.                 replaced with a call of memcmp, which
  23.                 will be represented as 'repz cmpsb'.
  24.     o FAST                  Forces the Get_Next_Match routine
  25.                 to be inline. This gives additional
  26.                 percents of speedup.
  27.     o __TURBOC__            For compiling under TURBO C
  28.     o __i386__              When compiling under GNU C causes
  29.                 some fixed register allocations,
  30.                 which give better code.
  31.     o TEXT_DEFAULT          (For MS-DOS only!) Define, if you
  32.                 freeze text files more often than binary
  33.                 ones. In this case don't forget to use "-i"
  34.                 to freeze binary files!!
  35.         o UTIMES        For using the utimes() function
  36.                 instead of utime(), which is obsolete
  37.                 on some systems (most notably BSD
  38.                 4.3).
  39.  
  40. Please! If your computer supports the string operations, try to write
  41. "asm" instructions (GNU style) which realize the right-to-left memory
  42. comparison (s1, s2, length) in minimum number of clock cycles.
  43. If a noticeable (5% or more) speedup is gained, please send me a message.
  44.  
  45. Other preprocessor symbols (DEBUG, GATHER_STAT) are for internal use
  46. only.
  47.  
  48. The format of frozen (2.X) file is incompatible with that of frozen (1.0),
  49. but if this package is compiled with -DCOMPAT switch, you will able to
  50. unpack frozen (1.0) files, if you have them.
  51.  
  52. ----
  53.  
  54.     The format of a frozen file is as follows:
  55.     (version 1.0 had only 2-bytes header)
  56.  
  57. offset    type      value    comment
  58.   0       byte       037     2 byte magic header
  59.   1       byte       0237    (version 1.0 - 0236)
  60.   2       short       X      (little endian)
  61.   4       byte        Y
  62.  
  63. X = 0 e e e e e d d d d c c c b b a   \
  64.                        > [a-f] are binary digits
  65. Y = 0 0 f f f f f f                   /
  66.  
  67. a - number of 1-bit static Huffman codes in the `matching positions'
  68. table (see freeze.1)
  69. bb - number of 2-bit codes,
  70.     etc.
  71.  
  72. The numbers of 7- and 8-bits codes are evaluated from the
  73. conditions: sum(codes) = 62(dec), max code = 1111111(bin).
  74.  
  75. The default values are: 0 1 1 1 4 10 27 18, what means:
  76. no 1-bit codes,
  77. one 2-bit, 3-bit and 4-bit codes, etc., so Huffman codes are:
  78. 00, 010, 0110, 01110, 01111, 10000, .... , 11111111.
  79.  
  80. ------------------- !!!!!!!!!! -----------------
  81.  
  82. (If you do not deal with compression algorithms, you may skip
  83. until asterisks.)
  84.  
  85. General format of frozen file is:
  86.  
  87. magic header - table description - stream of bits
  88.  
  89. The stream of bits is considered as a sequence of variable length dynamic
  90. Huffman codes (if their values are in the range of 0-255, they mean single
  91. bytes, special value of 256 means EOF, and further values mean the lengths
  92. of matched string.) If we have the value greater than 256, we get a static
  93. Huffman code from the stream (his value is 6 higher bits of matched
  94. string's position in the buffer), and then we get 7 bits literally.
  95.  
  96. Because buffer length is 8192 bytes and maximum match length is 256 bytes,
  97. the position of matched string cannot be greater than 8192-256, that's why
  98. there is only (8192-256)/2^7 = 62 static codes.
  99.  
  100.             *        *       *
  101.  
  102. The default table is tuned for both C texts and executable files (as in
  103. LHARC). If you freeze any other files (databases, images, fonts,
  104. etc.) you can calculate the matching positions distribution using the
  105. `statist' program, which calculates and displays the mentioned
  106. distribution for the given file. It is useful for large (100K or more)
  107. files.
  108.  
  109. Though the built-in position table is polyvalent, the tuning can increase
  110. the compression rate up to one additional percent.  (Or even more, if the
  111. matching strings distribution is very bizarre!)
  112.  
  113. Usage: statist < sample_file ; you can also see the intermediate values
  114. and watch their changes by pressing INTR key when you wish.
  115.  
  116. Note: If you use "gensample | statist", remember that INTR influence BOTH
  117. processes !!
  118.  
  119. You may create the /etc/default/freeze file (if you don't like
  120. /etc/default/ directory, choose another - in MS-DOS it is FREEZE.CNF in
  121. the directory of FREEZE.EXE), which has the following format:  name =
  122. ``statist's output (8 numbers)'', f.ex.:
  123.  
  124. ---------- cut here -----------
  125. # This is freeze's defaults file
  126. gif =   0 0 0 0 2 60 0 0        # This is NOT! optimal data
  127.                 # for GIF files
  128. doc=0 0 1 2 7 16 36 0           # The sample was gcc.lp
  129. # End of file
  130. ---------- cut here -----------
  131.  
  132. If you find values which are better THAN DEFAULT both for text (C
  133. programs) and binary (executable) files, please send them to me.
  134.  
  135. Important note: statist.c is NOT a part of freeze package, it is an
  136. additional feature.
  137.  
  138. ------------------- LINT ----------------------------
  139.  
  140. Some lint's complaints about `used/declared inconsistently' are (in my
  141. case) due to inconsistencies of /usr/include/* and /usr/lib/llib*ln. It
  142. isn't dangerous.
  143.  
  144. ------------------- BUGS ----------------------------
  145.  
  146. Please send descriptions of found bugs, incompatibilities, etc.  to
  147. leo@s514.ipmce.su.  MS-DOS version will not be supported in future
  148. versions !!  (If they will be :-) )
  149.  
  150. ------------ SPEED & COMPRESSION RATE ---------------
  151.  
  152. When using 18 bits table (about 600K) and gcc, the speed of freeze is more
  153. than the same of ARJ 1.00, but is less than of LHA 2.05.
  154. On SPARCs freeze works faster than ZIP 1.0.
  155.  
  156. Note: the percents mean 'relatively to compressed size', if you want
  157. to have them relatively to original size, divide them to 2-2.5.
  158.  
  159. Compression rate is *INDEPENDENT* of the hash table size, but may vary
  160. with different static Huffman tables.  It is about 2% worse than the same
  161. of ARJ 1.00 and LHA 2.05, but ARJ 2.00 beats Freeze on 8%.
  162.  
  163. Note: if you see Compress works nearly as Freeze (on some files), this
  164. means the maximum is gained, so LHA and ARJ won't better more than
  165. 1-1.5%. There are some files (I have one) that freeze compresses better
  166. than ARJ 2.20.
  167.  
  168. --------------- POSSIBLE IMPROVEMENTS ---------------
  169.  
  170. The high-level routines (freeze, melt) are almost independent from
  171. low-level routines (Get_Next_Match, Insert/Delete_Node,
  172. Encode/Decode_Char/Position), so if you want the speed and/or compression
  173. rate `a la vogue' you may replace the low-level routines with the homebrew
  174. (f. ex.) ones and enjoy the results.
  175.  
  176. (I tried to implement splay trees instead of Huffman ones and instead of
  177. static table for position information, but this gives nothing, alas.)
  178.  
  179. --------- CALGARY COMPRESSION CORPUS RESULTS --------
  180.  
  181. total 2308
  182.    41515 May  9  1990 bib.F
  183.   344793 May  9  1990 book1.F
  184.   230861 May  9  1990 book2.F
  185.    68626 May  9  1990 geo.F
  186.   155783 May  9  1990 news.F
  187.    10453 May  9  1990 obj1.F
  188.    85500 May  9  1990 obj2.F
  189.    20021 May  9  1990 paper1.F
  190.    32693 May  9  1990 paper2.F
  191.    19430 May  9  1990 paper3.F
  192.     5771 May  9  1990 paper4.F
  193.     5170 May  9  1990 paper5.F
  194.    14091 May  9  1990 paper6.F
  195.    53291 May  9  1990 pic.F
  196.    14143 May  9  1990 progc.F
  197.    17064 May  9  1990 progl.F
  198.    11686 May  9  1990 progp.F
  199.    22861 May  9  1990 trans.F
  200.  
  201. Average bits/byte on the standard set (except paper3-6) =
  202.     1109290 * 8 / 3141622 = 2.825
  203.     (With the "-g" flag = 2.892)
  204.