Subversion Repositories Kolibri OS

Rev

Rev 6847 | 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.                 rb 2 ;for align
  150.         strategy dw ? ;int ;favor or force Huffman coding
  151.                 rb 2 ;for align
  152.  
  153.         good_match dd ? ;uInt
  154.         ; Use a faster search when the previous match is longer than this
  155.  
  156.         nice_match dd ? ;int ;Stop searching when current match exceeds this
  157.  
  158. ; used by trees.asm:
  159.         ; Didn't use ct_data typedef below to suppress compiler warning
  160.         dyn_ltree rb sizeof.ct_data * HEAP_SIZE ;literal and length tree
  161.         dyn_dtree rb sizeof.ct_data * (2*D_CODES+1) ;distance tree
  162.         bl_tree   rb sizeof.ct_data * (2*BL_CODES+1) ;Huffman tree for bit lengths
  163.  
  164.         l_desc  tree_desc ;desc. for literal tree
  165.         d_desc  tree_desc ;desc. for distance tree
  166.         bl_desc tree_desc ;desc. for bit length tree
  167.  
  168.         bl_count rw MAX_BITS+1 ;uint_16[]
  169.         ; number of codes at each bit length for an optimal tree
  170.  
  171.         heap     rd 2*L_CODES+1 ;int[] ;heap used to build the Huffman trees
  172.         heap_len dd ? ;int ;number of elements in the heap
  173.         heap_max dd ? ;int ;element of largest frequency
  174.         ; The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  175.         ; The same heap array is used to build all trees.
  176.  
  177.         depth rb ((2*L_CODES+1)+3) and (not 3) ;uch[]
  178.         ; Depth of each subtree used as tie breaker for trees of equal frequency
  179.  
  180.         l_buf dd ? ;uchf * ;buffer for literals or lengths
  181.  
  182.         lit_bufsize dd ? ;uInt
  183.         ; Size of match buffer for literals/lengths.  There are 4 reasons for
  184.         ; limiting lit_bufsize to 64K:
  185.         ;   - frequencies can be kept in 16 bit counters
  186.         ;   - if compression is not successful for the first block, all input
  187.         ;     data is still in the window so we can still emit a stored block even
  188.         ;     when input comes from standard input.  (This can also be done for
  189.         ;     all blocks if lit_bufsize is not greater than 32K.)
  190.         ;   - if compression is not successful for a file smaller than 64K, we can
  191.         ;     even emit a stored file instead of a stored block (saving 5 bytes).
  192.         ;     This is applicable only for zip (not gzip or zlib).
  193.         ;   - creating new Huffman trees less frequently may not provide fast
  194.         ;     adaptation to changes in the input data statistics. (Take for
  195.         ;     example a binary file with poorly compressible code followed by
  196.         ;     a highly compressible string table.) Smaller buffer sizes give
  197.         ;     fast adaptation but have of course the overhead of transmitting
  198.         ;     trees more frequently.
  199.         ;   - I can't count above 4
  200.  
  201.         last_lit dd ? ;uInt ;running index in l_buf
  202.  
  203.         d_buf dd ? ;uint_16p
  204.         ; Buffer for distances. To simplify the code, d_buf and l_buf have
  205.         ; the same number of elements. To use different lengths, an extra flag
  206.         ; array would be necessary.
  207.  
  208.         opt_len dd ? ;ulg ;bit length of current block with optimal trees
  209.         static_len dd ? ;ulg ;bit length of current block with static trees
  210.         matches dd ? ;uInt ;number of string matches in current block
  211.         insert  dd ? ;uInt ;bytes at end of window left to insert
  212.  
  213. if DEBUG eq 1
  214.         ;compressed_len dd ? ;ulg ;total bit length of compressed file mod 2^32
  215.         ;bits_sent      dd ? ;ulg ;bit length of compressed data sent mod 2^32
  216. end if
  217.  
  218.         bi_buf dw ? ;uint_16
  219.                 rb 2 ;for align
  220.         ; Output buffer. bits are inserted starting at the bottom (least
  221.         ; significant bits).
  222.  
  223.         bi_valid dd ? ;int
  224.         ; Number of valid bits in bi_buf.  All bits above the last valid bit
  225.         ; are always zero.
  226.  
  227.         high_water dd ? ;ulg
  228.         ; High water mark offset in window for initialized bytes -- bytes above
  229.         ; this are set to zero in order to avoid memory check warnings when
  230.         ; longest match routines access bytes past the input.  This is then
  231.         ; updated to the new high water mark.
  232. ends
  233.  
  234. deflate_state.max_insert_length equ deflate_state.max_lazy_match
  235. ; Insert new strings in the hash table only if the match length is not
  236. ; greater than this length. This saves time but degrades compression.
  237. ; max_insert_length is used only for compression levels <= 3.
  238.  
  239. ; Output a byte on the stream.
  240. ; IN assertion: there is enough room in pending_buf.
  241.  
  242. macro put_byte s, c
  243. {
  244.         mov eax,[s+deflate_state.pending]
  245.         add eax,[s+deflate_state.pending_buf]
  246.         mov byte[eax],c
  247.         inc dword[s+deflate_state.pending]
  248. }
  249. macro put_dword s, d
  250. {
  251.         mov eax,[s+deflate_state.pending]
  252.         add eax,[s+deflate_state.pending_buf]
  253.         mov dword[eax],d
  254.         add dword[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.         ja .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. if DEBUG eq 0
  293. ; Inline versions of _tr_tally for speed:
  294. if c eq eax
  295. else
  296.         mov eax,c
  297. end if
  298.         push ecx
  299.         mov ecx,[s+deflate_state.last_lit]
  300.         shl ecx,1
  301.         add ecx,[s+deflate_state.d_buf]
  302.         mov word[ecx],0
  303.         mov ecx,[s+deflate_state.last_lit]
  304.         add ecx,[s+deflate_state.l_buf]
  305.         mov byte[ecx],al
  306.         inc dword[s+deflate_state.last_lit]
  307.         and eax,0xff
  308.         inc word[s+sizeof.ct_data*eax+deflate_state.dyn_ltree+Freq]
  309.         xor eax,eax
  310.         mov ecx,[s+deflate_state.lit_bufsize]
  311.         dec ecx
  312.         cmp [s+deflate_state.last_lit],ecx
  313.         sete al ;flush = (..==..)
  314.         mov flush, eax
  315.         pop ecx
  316. else
  317.         stdcall _tr_tally, s, 0, c
  318.         mov flush, eax
  319. end if
  320. }
  321. macro _tr_tally_dist s, distance, length, flush
  322. {
  323. if DEBUG eq 0
  324.         push ecx
  325.  
  326.     ;s.d_buf[s.last_lit] = dist
  327.         mov ecx,[s+deflate_state.last_lit]
  328.         shl ecx,1
  329.         add ecx,[s+deflate_state.d_buf]
  330. if distance eq eax
  331.         mov [ecx],ax
  332. else
  333.         mov word[ecx],distance
  334. end if
  335.  
  336.     ;s.l_buf[s.last_lit++] = len
  337.         mov ecx,[s+deflate_state.last_lit]
  338.         add ecx,[s+deflate_state.l_buf]
  339. if length eq eax
  340.         mov [ecx],al
  341. else if length eq ebx
  342.         mov [ecx],bl
  343. else
  344.         ... ;mov byte[ecx],length
  345. end if
  346.         inc dword[s+deflate_state.last_lit]
  347.  
  348.         ;dist--
  349. if distance eq eax
  350. else
  351.         mov eax,distance
  352. end if
  353.         dec eax
  354.  
  355.         ;s.dyn_ltree[_length_code[len]+LITERALS+1].Freq++
  356.         movzx ecx,byte[ecx]
  357.         movzx ecx,byte[ecx+_length_code]
  358.         inc word[s+sizeof.ct_data*ecx+deflate_state.dyn_ltree+sizeof.ct_data*(LITERALS+1)+Freq]
  359.  
  360.         ;s.dyn_dtree[d_code(dist)].Freq++
  361.         d_code eax
  362.         inc word[s+sizeof.ct_data*eax+deflate_state.dyn_dtree+Freq]
  363.  
  364.         ;flush = (s.last_lit == s.lit_bufsize-1)
  365.         mov ecx,[s+deflate_state.lit_bufsize]
  366.         dec ecx
  367.         xor eax,eax
  368.         cmp [s+deflate_state.last_lit],ecx
  369.         sete al
  370.         mov flush,eax
  371.         pop ecx
  372. else
  373.         stdcall _tr_tally, s, distance, length
  374.         mov flush, eax
  375. end if
  376. }
  377.