Subversion Repositories Kolibri OS

Rev

Rev 6797 | Rev 6851 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. ; deflate.inc -- internal compression state
  2. ; Copyright (C) 1995-2012 Jean-loup Gailly
  3. ; For conditions of distribution and use, see copyright notice in zlib.inc
  4.  
  5. ; WARNING: this file should *not* be used by applications. It is
  6. ; part of the implementation of the compression library and is
  7. ; subject to change. Applications should only use zlib.inc.
  8.  
  9. include 'zutil.inc'
  10.  
  11. ; ===========================================================================
  12. ; Internal compression state.
  13.  
  14.  
  15. LENGTH_CODES equ 29
  16. ; number of length codes, not counting the special END_BLOCK code
  17.  
  18. LITERALS equ 256
  19. ; number of literal bytes 0..255
  20.  
  21. L_CODES equ (LITERALS+1+LENGTH_CODES)
  22. ; number of Literal or Length codes, including the END_BLOCK code
  23.  
  24. D_CODES  equ 30
  25. ; number of distance codes
  26.  
  27. BL_CODES equ 19
  28. ; number of codes used to transfer the bit lengths
  29.  
  30. HEAP_SIZE equ (2*L_CODES+1)
  31. ; maximum heap size
  32.  
  33. MAX_BITS equ 15
  34. ; All codes must not exceed MAX_BITS bits
  35.  
  36. Buf_size equ 16
  37. ; size of bit buffer in bi_buf
  38.  
  39. INIT_STATE   equ 42
  40. EXTRA_STATE  equ 69
  41. NAME_STATE   equ 73
  42. COMMENT_STATE equ 91
  43. HCRC_STATE   equ 103
  44. BUSY_STATE   equ 113
  45. FINISH_STATE equ 800
  46. ; Stream status
  47.  
  48. ; Data structure describing a single value and its code string.
  49. struct ct_data
  50.         fc dw ? ;union
  51.                 ;uint_16 freq ;frequency count
  52.                 ;uint_16 code ;bit string
  53.         dale dw ? ;union
  54.                 ;uint_16 dad  ;father node in Huffman tree
  55.                 ;uint_16 len  ;length of bit string
  56. ends
  57.  
  58. Freq equ ct_data.fc ;.freq
  59. Code equ ct_data.fc ;.code
  60. Dad  equ ct_data.dale ;.dad
  61. Len  equ ct_data.dale ;.len
  62.  
  63. struct tree_desc
  64.         dyn_tree  dd ? ;ct_data * ;the dynamic tree
  65.         max_code  dd ? ;int ;largest code with non zero frequency
  66.         stat_desc dd ? ;static_tree_desc * ;the corresponding static tree
  67. ends
  68.  
  69. ; A Pos is an index in the character window. We use short instead of int to
  70. ; save space in the various tables. IPos is used only for parameter passing.
  71.  
  72. struct deflate_state ;internal_state
  73.         strm   dd ? ;z_streamp ;pointer back to this zlib stream
  74.         status dd ? ;int ;as the name implies
  75.         pending_buf dd ? ;Bytef *;output still pending
  76.         pending_buf_size dd ? ;ulg ;size of pending_buf
  77.         pending_out dd ? ;Bytef * ;next pending byte to output to the stream
  78.         pending dd ? ;uInt ;nb of bytes in the pending buffer
  79.         wrap    dd ? ;int ;bit 0 true for zlib, bit 1 true for gzip
  80.         gzhead  dd ? ;gz_headerp ;gzip header information to write
  81.         gzindex dd ? ;uInt ;where in extra, name, or comment
  82.         method  db ? ;Byte ;can only be DEFLATED
  83.                 rb 3 ;for align
  84.         last_flush dd ? ;int ;value of flush param for previous deflate call
  85.  
  86. ; used by deflate.asm:
  87.  
  88.         w_size dd ? ;uInt ;LZ77 window size (32K by default)
  89.         w_bits dd ? ;uInt ;log2(w_size)  (8..16)
  90.         w_mask dd ? ;uInt ;w_size - 1
  91.  
  92.         window dd ? ;Bytef *
  93.         ; Sliding window. Input bytes are read into the second half of the window,
  94.         ; and move to the first half later to keep a dictionary of at least wSize
  95.         ; bytes. With this organization, matches are limited to a distance of
  96.         ; wSize-MAX_MATCH bytes, but this ensures that IO is always
  97.         ; performed with a length multiple of the block size. Also, it limits
  98.         ; the window size to 64K, which is quite useful on MSDOS.
  99.         ; To do: use the user input buffer as sliding window.
  100.  
  101.         window_size dd ? ;ulg
  102.         ; Actual size of window: 2*wSize, except when the user input buffer
  103.         ; is directly used as sliding window.
  104.  
  105.         prev dd ? ;Posf *
  106.         ; Link to older string with same hash index. To limit the size of this
  107.         ; array to 64K, this link is maintained only for the last 32K strings.
  108.         ; An index in this array is thus a window index modulo 32K.
  109.  
  110.         head      dd ? ;Posf * ;Heads of the hash chains or NIL.
  111.  
  112.         ins_h     dd ? ;uInt ;hash index of string to be inserted
  113.         hash_size dd ? ;uInt ;number of elements in hash table
  114.         hash_bits dd ? ;uInt ;log2(hash_size)
  115.         hash_mask dd ? ;uInt ;hash_size-1
  116.  
  117.         hash_shift dd ? ;uInt
  118.         ; Number of bits by which ins_h must be shifted at each input
  119.         ; step. It must be such that after MIN_MATCH steps, the oldest
  120.         ; byte no longer takes part in the hash key, that is:
  121.         ;   hash_shift * MIN_MATCH >= hash_bits
  122.  
  123.         block_start dd ? ;long
  124.         ; Window position at the beginning of the current output block. Gets
  125.         ; negative when the window is moved backwards.
  126.  
  127.         match_length dd ? ;uInt ;length of best match
  128.         prev_match   dd ? ;IPos ;previous match
  129.         match_available dd ? ;int ;set if previous match exists
  130.         strstart     dd ? ;uInt ;start of string to insert
  131.         match_start  dd ? ;uInt ;start of matching string
  132.         lookahead    dd ? ;uInt ;number of valid bytes ahead in window
  133.  
  134.         prev_length dd ? ;uInt
  135.         ; Length of the best match at previous step. Matches not greater than this
  136.         ; are discarded. This is used in the lazy match evaluation.
  137.  
  138.         max_chain_length dd ? ;uInt
  139.         ; To speed up deflation, hash chains are never searched beyond this
  140.         ; length.  A higher limit improves compression ratio but degrades the
  141.         ; speed.
  142.  
  143.         max_lazy_match dd ? ;uInt
  144.         ; Attempt to find a better match only when the current match is strictly
  145.         ; smaller than this value. This mechanism is used only for compression
  146.         ; levels >= 4.
  147.  
  148.         level dw ? ;int ;compression level (1..9)
  149.         strategy dw ? ;int ;favor or force Huffman coding
  150.  
  151.         good_match dd ? ;uInt
  152.         ; Use a faster search when the previous match is longer than this
  153.  
  154.         nice_match dd ? ;int ;Stop searching when current match exceeds this
  155.  
  156. ; used by trees.asm:
  157.         ; Didn't use ct_data typedef below to suppress compiler warning
  158.         dyn_ltree rb sizeof.ct_data * HEAP_SIZE ;literal and length tree
  159.         dyn_dtree rb sizeof.ct_data * (2*D_CODES+1) ;distance tree
  160.         bl_tree   rb sizeof.ct_data * (2*BL_CODES+1) ;Huffman tree for bit lengths
  161.  
  162.         l_desc  tree_desc ;desc. for literal tree
  163.         d_desc  tree_desc ;desc. for distance tree
  164.         bl_desc tree_desc ;desc. for bit length tree
  165.  
  166.         bl_count rw MAX_BITS+1 ;uint_16[]
  167.         ; number of codes at each bit length for an optimal tree
  168.  
  169.         heap     rw 2*L_CODES+1 ;int[] ;heap used to build the Huffman trees
  170.         heap_len dd ? ;int ;number of elements in the heap
  171.         heap_max dd ? ;int ;element of largest frequency
  172.         ; The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  173.         ; The same heap array is used to build all trees.
  174.  
  175.         depth rb ((2*L_CODES+1)+3) and (not 3) ;uch[]
  176.         ; Depth of each subtree used as tie breaker for trees of equal frequency
  177.  
  178.         l_buf dd ? ;uchf * ;buffer for literals or lengths
  179.  
  180.         lit_bufsize dd ? ;uInt
  181.         ; Size of match buffer for literals/lengths.  There are 4 reasons for
  182.         ; limiting lit_bufsize to 64K:
  183.         ;   - frequencies can be kept in 16 bit counters
  184.         ;   - if compression is not successful for the first block, all input
  185.         ;     data is still in the window so we can still emit a stored block even
  186.         ;     when input comes from standard input.  (This can also be done for
  187.         ;     all blocks if lit_bufsize is not greater than 32K.)
  188.         ;   - if compression is not successful for a file smaller than 64K, we can
  189.         ;     even emit a stored file instead of a stored block (saving 5 bytes).
  190.         ;     This is applicable only for zip (not gzip or zlib).
  191.         ;   - creating new Huffman trees less frequently may not provide fast
  192.         ;     adaptation to changes in the input data statistics. (Take for
  193.         ;     example a binary file with poorly compressible code followed by
  194.         ;     a highly compressible string table.) Smaller buffer sizes give
  195.         ;     fast adaptation but have of course the overhead of transmitting
  196.         ;     trees more frequently.
  197.         ;   - I can't count above 4
  198.  
  199.         last_lit dd ? ;uInt ;running index in l_buf
  200.  
  201.         d_buf dd ? ;uint_16p
  202.         ; Buffer for distances. To simplify the code, d_buf and l_buf have
  203.         ; the same number of elements. To use different lengths, an extra flag
  204.         ; array would be necessary.
  205.  
  206.         opt_len dd ? ;ulg ;bit length of current block with optimal trees
  207.         static_len dd ? ;ulg ;bit length of current block with static trees
  208.         matches dd ? ;uInt ;number of string matches in current block
  209.         insert  dd ? ;uInt ;bytes at end of window left to insert
  210.  
  211. if DEBUG eq 1
  212.         compressed_len dd ? ;ulg ;total bit length of compressed file mod 2^32
  213.         bits_sent      dd ? ;ulg ;bit length of compressed data sent mod 2^32
  214. end if
  215.  
  216.         bi_buf dw ? ;uint_16
  217.         ; Output buffer. bits are inserted starting at the bottom (least
  218.         ; significant bits).
  219.  
  220.         bi_valid dd ? ;int
  221.         ; Number of valid bits in bi_buf.  All bits above the last valid bit
  222.         ; are always zero.
  223.  
  224.         high_water dd ? ;ulg
  225.         ; High water mark offset in window for initialized bytes -- bytes above
  226.         ; this are set to zero in order to avoid memory check warnings when
  227.         ; longest match routines access bytes past the input.  This is then
  228.         ; updated to the new high water mark.
  229. ends
  230.  
  231. deflate_state.max_insert_length equ deflate_state.max_lazy_match
  232. ; Insert new strings in the hash table only if the match length is not
  233. ; greater than this length. This saves time but degrades compression.
  234. ; max_insert_length is used only for compression levels <= 3.
  235.  
  236. ; Output a byte on the stream.
  237. ; IN assertion: there is enough room in pending_buf.
  238.  
  239. macro put_byte s, c
  240. {
  241.         movzx eax,word[s+deflate_state.pending]
  242.         add eax,[s+deflate_state.pending_buf]
  243.         mov byte[eax],c
  244.         inc word[s+deflate_state.pending]
  245. }
  246. macro put_dword s, d
  247. {
  248.         zlib_debug '(%d)',d
  249.         movzx eax,word[s+deflate_state.pending]
  250.         add eax,[s+deflate_state.pending_buf]
  251.         mov dword[eax],d
  252.         add word[s+deflate_state.pending],4
  253. }
  254.  
  255. MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
  256. ; Minimum amount of lookahead, except at the end of the input file.
  257. ; See deflate.asm for comments about the MIN_MATCH+1.
  258.  
  259. macro MAX_DIST s
  260. {
  261.         mov eax,[s+deflate_state.w_size]
  262.         sub eax,MIN_LOOKAHEAD
  263. }
  264. ; In order to simplify the code, particularly on 16 bit machines, match
  265. ; distances are limited to MAX_DIST instead of WSIZE.
  266.  
  267. WIN_INIT equ MAX_MATCH
  268. ; Number of bytes after end of data in window to initialize in order to avoid
  269. ; memory checker errors from longest match routines
  270.  
  271. macro d_code dist
  272. {
  273. ;if (dist < 256) _dist_code[dist]
  274. ;else _dist_code[ 256+(dist>>7) ]
  275. local .end0
  276.         mov eax,dist
  277.         cmp eax,256
  278.         jl .end0
  279.                 shr eax,7
  280.                 add eax,256
  281.         .end0:
  282.         movzx eax,byte[eax+_dist_code]
  283. }
  284. ; Mapping from a distance to a distance code. dist is the distance - 1 and
  285. ; must not have side effects. _dist_code[256] and _dist_code[257] are never
  286. ; used.
  287.  
  288. macro _tr_tally_lit s, c, flush
  289. {
  290. local .end0
  291. if DEBUG eq 0
  292. ; Inline versions of _tr_tally for speed:
  293. if c eq eax
  294. else
  295.         mov eax,c
  296. end if
  297.         push ecx
  298.         mov ecx,[s+deflate_state.last_lit]
  299.         shl ecx,1
  300.         add ecx,[s+deflate_state.d_buf]
  301.         mov word[ecx],0
  302.         mov ecx,[s+deflate_state.last_lit]
  303.         add ecx,[s+deflate_state.l_buf]
  304.         mov byte[ecx],al
  305.         inc dword[s+deflate_state.last_lit]
  306.         and eax,0xff
  307.         imul eax,sizeof.ct_data
  308.         add eax,s
  309.         inc word[eax+deflate_state.dyn_ltree+Freq]
  310.         xor eax,eax
  311.         mov ecx,[s+deflate_state.lit_bufsize]
  312.         dec ecx
  313.         cmp [s+deflate_state.last_lit],ecx
  314.         jne .end0
  315.                 inc eax ;flush = (..==..)
  316.         .end0:
  317.         mov flush, eax
  318.         pop ecx
  319. else
  320.         stdcall _tr_tally, s, 0, c
  321.         mov flush, eax
  322. end if
  323. }
  324. macro _tr_tally_dist s, distance, length, flush
  325. {
  326. if 0 ;;;DEBUG eq 0
  327.         push ecx
  328. ;   uch len = (length)
  329. if distance eq eax
  330. else
  331.         mov eax,distance
  332. end if
  333.         mov ecx,[s+deflate_state.last_lit]
  334.         shl ecx,1
  335.         add ecx,[s+deflate_state.d_buf]
  336.         mov word[ecx],ax
  337.         mov ecx,[s+deflate_state.last_lit]
  338.         add ecx,[s+deflate_state.l_buf]
  339.         mov byte[ecx],length
  340.         inc dword[s+deflate_state.last_lit]
  341.         dec eax
  342. ;    s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++;
  343. ;    s->dyn_dtree[d_code(dist)].Freq++;
  344. ;    flush = (s->last_lit == s->lit_bufsize-1);
  345.         pop ecx
  346. else
  347.         stdcall _tr_tally, s, distance, length
  348.         mov flush, eax
  349. end if
  350. }
  351.