Subversion Repositories Kolibri OS

Rev

Rev 6617 | Rev 6797 | 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 ;ct_data_s
  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 ;tree_desc_s
  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 dw ? ;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.         last_flush dd ? ;int ;value of flush param for previous deflate call
  84.  
  85. ; used by deflate.asm:
  86.  
  87.         w_size dd ? ;uInt ;LZ77 window size (32K by default)
  88.         w_bits dd ? ;uInt ;log2(w_size)  (8..16)
  89.         w_mask dd ? ;uInt ;w_size - 1
  90.  
  91.         window dd ? ;Bytef *
  92.         ; Sliding window. Input bytes are read into the second half of the window,
  93.         ; and move to the first half later to keep a dictionary of at least wSize
  94.         ; bytes. With this organization, matches are limited to a distance of
  95.         ; wSize-MAX_MATCH bytes, but this ensures that IO is always
  96.         ; performed with a length multiple of the block size. Also, it limits
  97.         ; the window size to 64K, which is quite useful on MSDOS.
  98.         ; To do: use the user input buffer as sliding window.
  99.  
  100.         window_size dd ? ;ulg
  101.         ; Actual size of window: 2*wSize, except when the user input buffer
  102.         ; is directly used as sliding window.
  103.  
  104.         prev dd ? ;Posf *
  105.         ; Link to older string with same hash index. To limit the size of this
  106.         ; array to 64K, this link is maintained only for the last 32K strings.
  107.         ; An index in this array is thus a window index modulo 32K.
  108.  
  109.         head      dd ? ;Posf * ;Heads of the hash chains or NIL.
  110.  
  111.         ins_h     dd ? ;uInt ;hash index of string to be inserted
  112.         hash_size dd ? ;uInt ;number of elements in hash table
  113.         hash_bits dd ? ;uInt ;log2(hash_size)
  114.         hash_mask dd ? ;uInt ;hash_size-1
  115.  
  116.         hash_shift dd ? ;uInt
  117.         ; Number of bits by which ins_h must be shifted at each input
  118.         ; step. It must be such that after MIN_MATCH steps, the oldest
  119.         ; byte no longer takes part in the hash key, that is:
  120.         ;   hash_shift * MIN_MATCH >= hash_bits
  121.  
  122.         block_start dd ? ;long
  123.         ; Window position at the beginning of the current output block. Gets
  124.         ; negative when the window is moved backwards.
  125.  
  126.         match_length dd ? ;uInt ;length of best match
  127.         prev_match   dd ? ;IPos ;previous match
  128.         match_available dd ? ;int ;set if previous match exists
  129.         strstart     dd ? ;uInt ;start of string to insert
  130.         match_start  dd ? ;uInt ;start of matching string
  131.         lookahead    dd ? ;uInt ;number of valid bytes ahead in window
  132.  
  133.         prev_length dd ? ;uInt
  134.         ; Length of the best match at previous step. Matches not greater than this
  135.         ; are discarded. This is used in the lazy match evaluation.
  136.  
  137.         max_chain_length dd ? ;uInt
  138.         ; To speed up deflation, hash chains are never searched beyond this
  139.         ; length.  A higher limit improves compression ratio but degrades the
  140.         ; speed.
  141.  
  142.         max_lazy_match dd ? ;uInt
  143.         ; Attempt to find a better match only when the current match is strictly
  144.         ; smaller than this value. This mechanism is used only for compression
  145.         ; levels >= 4.
  146.  
  147. ;#   define max_insert_length  max_lazy_match
  148.         ; Insert new strings in the hash table only if the match length is not
  149.         ; greater than this length. This saves time but degrades compression.
  150.         ; max_insert_length is used only for compression levels <= 3.
  151.  
  152.         level dw ? ;int ;compression level (1..9)
  153.         strategy dw ? ;int ;favor or force Huffman coding
  154.  
  155.         good_match dd ? ;uInt
  156.         ; Use a faster search when the previous match is longer than this
  157.  
  158.         nice_match dd ? ;int ;Stop searching when current match exceeds this
  159.  
  160. ; used by trees.asm:
  161.         ; Didn't use ct_data typedef below to suppress compiler warning
  162.         dyn_ltree rb sizeof.ct_data * HEAP_SIZE ;literal and length tree
  163.         dyn_dtree rb sizeof.ct_data * (2*D_CODES+1) ;distance tree
  164.         bl_tree   rb sizeof.ct_data * (2*BL_CODES+1) ;Huffman tree for bit lengths
  165.  
  166.         l_desc  tree_desc ;desc. for literal tree
  167.         d_desc  tree_desc ;desc. for distance tree
  168.         bl_desc tree_desc ;desc. for bit length tree
  169.  
  170.         bl_count rw MAX_BITS+1 ;uint_16[]
  171.         ; number of codes at each bit length for an optimal tree
  172.  
  173.         heap     rw 2*L_CODES+1 ;int[] ;heap used to build the Huffman trees
  174.         heap_len dd ? ;int ;number of elements in the heap
  175.         heap_max dd ? ;int ;element of largest frequency
  176.         ; The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  177.         ; The same heap array is used to build all trees.
  178.  
  179.         depth rb 2*L_CODES+1 ;uch[]
  180.         ; Depth of each subtree used as tie breaker for trees of equal frequency
  181.  
  182.         l_buf dd ? ;uchf * ;buffer for literals or lengths
  183.  
  184.         lit_bufsize dd ? ;uInt
  185.         ; Size of match buffer for literals/lengths.  There are 4 reasons for
  186.         ; limiting lit_bufsize to 64K:
  187.         ;   - frequencies can be kept in 16 bit counters
  188.         ;   - if compression is not successful for the first block, all input
  189.         ;     data is still in the window so we can still emit a stored block even
  190.         ;     when input comes from standard input.  (This can also be done for
  191.         ;     all blocks if lit_bufsize is not greater than 32K.)
  192.         ;   - if compression is not successful for a file smaller than 64K, we can
  193.         ;     even emit a stored file instead of a stored block (saving 5 bytes).
  194.         ;     This is applicable only for zip (not gzip or zlib).
  195.         ;   - creating new Huffman trees less frequently may not provide fast
  196.         ;     adaptation to changes in the input data statistics. (Take for
  197.         ;     example a binary file with poorly compressible code followed by
  198.         ;     a highly compressible string table.) Smaller buffer sizes give
  199.         ;     fast adaptation but have of course the overhead of transmitting
  200.         ;     trees more frequently.
  201.         ;   - I can't count above 4
  202.  
  203.         last_lit dd ? ;uInt ;running index in l_buf
  204.  
  205.         d_buf dd ? ;uint_16p
  206.         ; Buffer for distances. To simplify the code, d_buf and l_buf have
  207.         ; the same number of elements. To use different lengths, an extra flag
  208.         ; array would be necessary.
  209.  
  210.         opt_len dd ? ;ulg ;bit length of current block with optimal trees
  211.         static_len dd ? ;ulg ;bit length of current block with static trees
  212.         matches dd ? ;uInt ;number of string matches in current block
  213.         insert  dd ? ;uInt ;bytes at end of window left to insert
  214.  
  215. if DEBUG eq 1
  216.         compressed_len dd ? ;ulg ;total bit length of compressed file mod 2^32
  217.         bits_sent      dd ? ;ulg ;bit length of compressed data sent mod 2^32
  218. end if
  219.  
  220.         bi_buf dw ? ;uint_16
  221.         ; Output buffer. bits are inserted starting at the bottom (least
  222.         ; significant bits).
  223.  
  224.         bi_valid dd ? ;int
  225.         ; Number of valid bits in bi_buf.  All bits above the last valid bit
  226.         ; are always zero.
  227.  
  228.         high_water dd ? ;ulg
  229.         ; High water mark offset in window for initialized bytes -- bytes above
  230.         ; this are set to zero in order to avoid memory check warnings when
  231.         ; longest match routines access bytes past the input.  This is then
  232.         ; updated to the new high water mark.
  233. ends
  234.  
  235. ; Output a byte on the stream.
  236. ; IN assertion: there is enough room in pending_buf.
  237.  
  238. macro put_byte s, c
  239. {
  240. ;xor eax,eax
  241. ;mov al,c
  242. ;zlib_debug '(%d)',eax
  243.         movzx eax,word[s+deflate_state.pending]
  244.         add eax,[s+deflate_state.pending_buf]
  245.         mov byte[eax],c
  246.         inc word[s+deflate_state.pending]
  247. }
  248. macro put_dword s, d
  249. {
  250.         zlib_debug '(%d)',d
  251.         movzx eax,word[s+deflate_state.pending]
  252.         add eax,[s+deflate_state.pending_buf]
  253.         mov dword[eax],d
  254.         add word[s+deflate_state.pending],4
  255. }
  256.  
  257. MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
  258. ; Minimum amount of lookahead, except at the end of the input file.
  259. ; See deflate.asm for comments about the MIN_MATCH+1.
  260.  
  261. macro MAX_DIST s
  262. {
  263.         mov eax,[s+deflate_state.w_size]
  264.         sub eax,MIN_LOOKAHEAD
  265. }
  266. ; In order to simplify the code, particularly on 16 bit machines, match
  267. ; distances are limited to MAX_DIST instead of WSIZE.
  268.  
  269. WIN_INIT equ MAX_MATCH
  270. ; Number of bytes after end of data in window to initialize in order to avoid
  271. ; memory checker errors from longest match routines
  272.  
  273. macro d_code dist
  274. {
  275. ;if (dist < 256) _dist_code[dist]
  276. ;else _dist_code[ 256+(dist>>7) ]
  277. local .end0
  278.         mov eax,dist
  279.         cmp eax,256
  280.         jl .end0
  281.                 shr eax,7
  282.                 add eax,256
  283.         .end0:
  284.         movzx eax,byte[eax+_dist_code]
  285. }
  286. ; Mapping from a distance to a distance code. dist is the distance - 1 and
  287. ; must not have side effects. _dist_code[256] and _dist_code[257] are never
  288. ; used.
  289.  
  290. macro _tr_tally_lit s, c, flush
  291. {
  292. local .end0
  293. if DEBUG eq 0
  294. ; Inline versions of _tr_tally for speed:
  295. if c eq eax
  296. else
  297.         mov eax,c
  298. end if
  299.         push ecx
  300.         mov ecx,[s+deflate_state.last_lit]
  301.         shl ecx,1
  302.         add ecx,[s+deflate_state.d_buf]
  303.         mov word[ecx],0
  304.         mov ecx,[s+deflate_state.last_lit]
  305.         add ecx,[s+deflate_state.l_buf]
  306.         mov byte[ecx],al
  307.         inc dword[s+deflate_state.last_lit]
  308.         and eax,0xff
  309.         imul eax,sizeof.ct_data
  310.         add eax,s
  311.         inc word[eax+deflate_state.dyn_ltree+Freq]
  312.         xor eax,eax
  313.         mov ecx,[s+deflate_state.lit_bufsize]
  314.         dec ecx
  315.         cmp [s+deflate_state.last_lit],ecx
  316.         jne .end0
  317.                 inc eax ;flush = (..==..)
  318.         .end0:
  319.         mov flush, eax
  320.         pop ecx
  321. else
  322.         stdcall _tr_tally, s, 0, c
  323.         mov flush, eax
  324. end if
  325. }
  326. macro _tr_tally_dist s, distance, length, flush
  327. {
  328. if 0 ;;;DEBUG eq 0
  329.         push ecx
  330. ;   uch len = (length)
  331. if distance eq eax
  332. else
  333.         mov eax,distance
  334. end if
  335.         mov ecx,[s+deflate_state.last_lit]
  336.         shl ecx,1
  337.         add ecx,[s+deflate_state.d_buf]
  338.         mov word[ecx],ax
  339.         mov ecx,[s+deflate_state.last_lit]
  340.         add ecx,[s+deflate_state.l_buf]
  341.         mov byte[ecx],length
  342.         inc dword[s+deflate_state.last_lit]
  343.         dec eax
  344. ;    s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++;
  345. ;    s->dyn_dtree[d_code(dist)].Freq++;
  346. ;    flush = (s->last_lit == s->lit_bufsize-1);
  347.         pop ecx
  348. else
  349.         stdcall _tr_tally, s, distance, length
  350.         mov flush, eax
  351. end if
  352. }
  353.