Subversion Repositories Kolibri OS

Rev

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

  1. ; trees.asm -- output deflated data using Huffman coding
  2. ; Copyright (C) 1995-2012 Jean-loup Gailly
  3. ; detect_data_type() function provided freely by Cosmin Truta, 2006
  4. ; For conditions of distribution and use, see copyright notice in zlib.h
  5.  
  6. ;  ALGORITHM
  7.  
  8. ;      The "deflation" process uses several Huffman trees. The more
  9. ;      common source values are represented by shorter bit sequences.
  10.  
  11. ;      Each code tree is stored in a compressed form which is itself
  12. ; a Huffman encoding of the lengths of all the code strings (in
  13. ; ascending order by source values).  The actual code strings are
  14. ; reconstructed from the lengths in the inflate process, as described
  15. ; in the deflate specification.
  16.  
  17. ;  REFERENCES
  18.  
  19. ;      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
  20. ;      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
  21.  
  22. ;      Storer, James A.
  23. ;          Data Compression:  Methods and Theory, pp. 49-50.
  24. ;          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
  25.  
  26. ;      Sedgewick, R.
  27. ;          Algorithms, p290.
  28. ;          Addison-Wesley, 1983. ISBN 0-201-06672-6.
  29.  
  30. ; ===========================================================================
  31. ; Constants
  32.  
  33.  
  34. MAX_BL_BITS equ 7
  35. ; Bit length codes must not exceed MAX_BL_BITS bits
  36.  
  37. END_BLOCK equ 256
  38. ; end of block literal code
  39.  
  40. REP_3_6     equ 16
  41. ; repeat previous bit length 3-6 times (2 bits of repeat count)
  42.  
  43. REPZ_3_10   equ 17
  44. ; repeat a zero length 3-10 times  (3 bits of repeat count)
  45.  
  46. REPZ_11_138 equ 18
  47. ; repeat a zero length 11-138 times  (7 bits of repeat count)
  48.  
  49. align 4
  50. extra_lbits dd \ ;int [LENGTH_CODES] ;extra bits for each length code
  51.         0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0
  52.  
  53. align 4
  54. extra_dbits dd \ ;int [D_CODES] ;extra bits for each distance code
  55.         0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13
  56.  
  57. align 4
  58. extra_blbits dd \ ;int [BL_CODES] ;extra bits for each bit length code
  59.         0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7
  60.  
  61. align 4
  62. bl_order db 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
  63. ; The lengths of the bit length codes are sent in order of decreasing
  64. ; probability, to avoid transmitting the lengths for unused bit length codes.
  65.  
  66.  
  67. ; ===========================================================================
  68. ; Local data. These are initialized only once.
  69.  
  70.  
  71. DIST_CODE_LEN equ 512 ;see definition of array dist_code below
  72.  
  73. if GEN_TREES_H eq 1 ;| !(STDC)
  74. ; non ANSI compilers may not accept trees.inc
  75.  
  76. align 4
  77. static_ltree rb sizeof.ct_data * (L_CODES+2)
  78. ; The static literal tree. Since the bit lengths are imposed, there is no
  79. ; need for the L_CODES extra codes used during heap construction. However
  80. ; The codes 286 and 287 are needed to build a canonical tree (see _tr_init
  81. ; below).
  82.  
  83. align 4
  84. static_dtree rb sizeof.ct_data * D_CODES
  85. ; The static distance tree. (Actually a trivial tree since all codes use
  86. ; 5 bits.)
  87.  
  88. align 4
  89. _dist_code rb DIST_CODE_LEN ;uch[]
  90. ; Distance codes. The first 256 values correspond to the distances
  91. ; 3 .. 258, the last 256 values correspond to the top 8 bits of
  92. ; the 15 bit distances.
  93.  
  94. align 4
  95. _length_code rb MAX_MATCH-MIN_MATCH+1 ;uch[]
  96. ; length code for each normalized match length (0 == MIN_MATCH)
  97.  
  98. align 4
  99. base_length rd LENGTH_CODES ;int[]
  100. ; First normalized length for each code (0 = MIN_MATCH)
  101.  
  102. align 4
  103. base_dist rd D_CODES ;int[]
  104. ; First normalized distance for each code (0 = distance of 1)
  105.  
  106. else
  107. include 'trees.inc'
  108. end if ;GEN_TREES_H
  109.  
  110. struct static_tree_desc ;_s
  111.         static_tree dd ? ;const ct_data * ;static tree or NULL
  112.         extra_bits  dd ? ;const intf * ;extra bits for each code or NULL
  113.         extra_base  dd ? ;int ;base index for extra_bits
  114.         elems       dd ? ;int ;max number of elements in the tree
  115.         max_length  dd ? ;int ;max bit length for the codes
  116. ends
  117.  
  118. align 4
  119. static_l_desc static_tree_desc static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS
  120.  
  121. align 4
  122. static_d_desc static_tree_desc static_dtree, extra_dbits, 0, D_CODES, MAX_BITS
  123.  
  124. align 4
  125. static_bl_desc static_tree_desc 0, extra_blbits, 0, BL_CODES, MAX_BL_BITS
  126.  
  127. ; ===========================================================================
  128. ; Local (static) routines in this file.
  129.  
  130.  
  131. macro send_code s, c, tree
  132. {
  133. if DEBUG eq 1
  134. ;       if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c))
  135. end if
  136. push eax ebx
  137. if c eq eax
  138. else
  139.         mov eax,c
  140. end if
  141.         imul eax,sizeof.ct_data
  142.         add eax,tree
  143.         movzx ebx,word[eax+Len]
  144.         push ebx
  145.         movzx ebx,word[eax+Code]
  146.         push ebx
  147.         stdcall send_bits, s ;tree[c].Code, tree[c].Len
  148. pop ebx eax
  149. }
  150. ; Send a code of the given tree[c] and tree must not have side effects
  151.  
  152. ; ===========================================================================
  153. ; Output a short LSB first on the stream.
  154. ; IN assertion: there is enough room in pendingBuf.
  155.  
  156. macro put_short s, w
  157. {
  158.         mov eax,[s+deflate_state.pending]
  159.         add eax,[s+deflate_state.pending_buf]
  160.         mov word[eax],w
  161.         add dword[s+deflate_state.pending],2
  162. }
  163.  
  164. ; ===========================================================================
  165. ; Send a value on a given number of bits.
  166. ; IN assertion: length <= 16 and value fits in length bits.
  167.  
  168. ;void (s, value, length)
  169. ;    deflate_state* s
  170. ;    int value  ;value to send
  171. ;    int length ;number of bits
  172. align 4
  173. proc send_bits uses eax ecx edi, s:dword, value:dword, length:dword
  174. ;    Tracevv((stderr," l %2d v %4x ", length, value));
  175. ;if DEBUG eq 1
  176.         mov eax,[length]
  177.         cmp eax,0
  178.         jle @f
  179.         cmp eax,15
  180.         jle .end1
  181.         @@:
  182.                 zlib_assert 'invalid length' ;Assert(..>0 && ..<=15)
  183.         .end1:
  184.         mov edi,[s]
  185.         ;;add [edi+deflate_state.bits_sent],eax
  186.  
  187.         ; If not enough room in bi_buf, use (valid) bits from bi_buf and
  188.         ; (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
  189.         ; unused bits in value.
  190.  
  191.         mov ecx,Buf_size
  192.         sub ecx,eax
  193.         cmp [edi+deflate_state.bi_valid],ecx
  194.         jle @f ;if (..>..)
  195.                 mov eax,[value]
  196.                 mov ecx,[edi+deflate_state.bi_valid]
  197.                 shl eax,cl
  198.                 or [edi+deflate_state.bi_buf],ax
  199.                 mov cx,[edi+deflate_state.bi_buf]
  200.                 put_short edi, cx
  201.                 mov eax,[value]
  202.                 mov ecx,Buf_size
  203.                 sub ecx,[edi+deflate_state.bi_valid]
  204.                 sar eax,cl
  205.                 mov [edi+deflate_state.bi_buf],ax
  206.                 mov eax,[length]
  207.                 sub eax,Buf_size
  208.                 jmp .end0
  209.         @@: ;else
  210.                 mov eax,[value]
  211.                 mov ecx,[edi+deflate_state.bi_valid]
  212.                 shl eax,cl
  213.                 or [edi+deflate_state.bi_buf],ax
  214.                 mov eax,[length]
  215.         .end0:
  216.         add [edi+deflate_state.bi_valid],eax
  217. ;else ;!DEBUG
  218.  
  219. ;{ int len = length;
  220. ;  if (s->bi_valid > (int)Buf_size - len) {
  221. ;    int val = value;
  222. ;    s->bi_buf |= (uint_16)val << s->bi_valid;
  223. ;    put_short(s, s->bi_buf);
  224. ;    s->bi_buf = (uint_16)val >> (Buf_size - s->bi_valid);
  225. ;    s->bi_valid += len - Buf_size;
  226. ;  } else {
  227. ;    s->bi_buf |= (uint_16)(value) << s->bi_valid;
  228. ;    s->bi_valid += len;
  229. ;  }
  230. ;}
  231. ;end if ;DEBUG
  232.         ret
  233. endp
  234.  
  235. ; the arguments must not have side effects
  236.  
  237. ; ===========================================================================
  238. ; Initialize the various 'constant' tables.
  239.  
  240. ;int static_init_done = 0
  241.  
  242. ;void ()
  243. align 4
  244. proc tr_static_init
  245. if GEN_TREES_H eq 1
  246.  
  247. ;    int n      ;iterates over tree elements
  248. ;    int bits   ;bit counter
  249. ;    int length ;length value
  250. ;    int code   ;code value
  251. ;    int dist   ;distance index
  252. ;    uint_16 bl_count[MAX_BITS+1];
  253.         ; number of codes at each bit length for an optimal tree
  254.  
  255. ;    if (static_init_done) return;
  256.  
  257.         ; For some embedded targets, global variables are not initialized:
  258. ;if NO_INIT_GLOBAL_POINTERS
  259. ;    static_l_desc.static_tree = static_ltree;
  260. ;    static_l_desc.extra_bits = extra_lbits;
  261. ;    static_d_desc.static_tree = static_dtree;
  262. ;    static_d_desc.extra_bits = extra_dbits;
  263. ;    static_bl_desc.extra_bits = extra_blbits;
  264. ;end if
  265.  
  266.         ; Initialize the mapping length (0..255) -> length code (0..28)
  267. ;    length = 0;
  268. ;    for (code = 0; code < LENGTH_CODES-1; code++) {
  269. ;        base_length[code] = length;
  270. ;        for (n = 0; n < (1<<extra_lbits[code]); n++) {
  271. ;            _length_code[length++] = (uch)code;
  272. ;        }
  273. ;    }
  274. ;    Assert (length == 256, "tr_static_init: length != 256");
  275.         ; Note that the length 255 (match length 258) can be represented
  276.         ; in two different ways: code 284 + 5 bits or code 285, so we
  277.         ; overwrite length_code[255] to use the best encoding:
  278.  
  279. ;    _length_code[length-1] = (uch)code;
  280.  
  281.         ; Initialize the mapping dist (0..32K) -> dist code (0..29)
  282. ;    dist = 0;
  283. ;    for (code = 0 ; code < 16; code++) {
  284. ;        base_dist[code] = dist;
  285. ;        for (n = 0; n < (1<<extra_dbits[code]); n++) {
  286. ;            _dist_code[dist++] = (uch)code;
  287. ;        }
  288. ;    }
  289. ;    Assert (dist == 256, "tr_static_init: dist != 256");
  290. ;    dist >>= 7; /* from now on, all distances are divided by 128 */
  291. ;    for ( ; code < D_CODES; code++) {
  292. ;        base_dist[code] = dist << 7;
  293. ;        for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
  294. ;            _dist_code[256 + dist++] = (uch)code;
  295. ;        }
  296. ;    }
  297. ;    Assert (dist == 256, "tr_static_init: 256+dist != 512");
  298.  
  299.         ; Construct the codes of the static literal tree
  300. ;    for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
  301. ;    n = 0;
  302. ;    while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
  303. ;    while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
  304. ;    while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
  305. ;    while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
  306.         ; Codes 286 and 287 do not exist, but we must include them in the
  307.         ; tree construction to get a canonical Huffman tree (longest code
  308.         ; all ones)
  309.  
  310. ;    gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
  311.  
  312.         ; The static distance tree is trivial:
  313. ;    for (n = 0; n < D_CODES; n++) {
  314. ;        static_dtree[n].Len = 5;
  315. ;        static_dtree[n].Code = bi_reverse((unsigned)n, 5);
  316. ;    }
  317. ;    static_init_done = 1;
  318.  
  319. if GEN_TREES_H eq 1
  320.         call gen_trees_header
  321. end if
  322. end if ;(GEN_TREES_H) | !(STDC)
  323.         ret
  324. endp
  325.  
  326. ; ===========================================================================
  327. ; Genererate the file trees.h describing the static trees.
  328.  
  329. ;#  define SEPARATOR(i, last, width) \
  330. ;      ((i) == (last)? "\n};\n\n" :    \
  331. ;       ((i) % (width) == (width)-1 ? ",\n" : ", "))
  332.  
  333. ;void ()
  334. align 4
  335. proc gen_trees_header
  336. ;    FILE *header = fopen("trees.inc", "w");
  337. ;    int i;
  338.  
  339. ;    Assert (header != NULL, "Can't open trees.inc");
  340. ;    fprintf(header,
  341. ;            "/* header created automatically with -DGEN_TREES_H */\n\n");
  342.  
  343. ;    fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
  344. ;    for (i = 0; i < L_CODES+2; i++) {
  345. ;        fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
  346. ;                static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
  347. ;    }
  348.  
  349. ;    fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
  350. ;    for (i = 0; i < D_CODES; i++) {
  351. ;        fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
  352. ;                static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
  353. ;    }
  354.  
  355. ;    fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
  356. ;    for (i = 0; i < DIST_CODE_LEN; i++) {
  357. ;        fprintf(header, "%2u%s", _dist_code[i],
  358. ;                SEPARATOR(i, DIST_CODE_LEN-1, 20));
  359. ;    }
  360.  
  361. ;    fprintf(header,
  362. ;        "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
  363. ;    for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
  364. ;        fprintf(header, "%2u%s", _length_code[i],
  365. ;                SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
  366. ;    }
  367.  
  368. ;    fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
  369. ;    for (i = 0; i < LENGTH_CODES; i++) {
  370. ;        fprintf(header, "%1u%s", base_length[i],
  371. ;                SEPARATOR(i, LENGTH_CODES-1, 20));
  372. ;    }
  373.  
  374. ;    fprintf(header, "local const int base_dist[D_CODES] = {\n");
  375. ;    for (i = 0; i < D_CODES; i++) {
  376. ;        fprintf(header, "%5u%s", base_dist[i],
  377. ;                SEPARATOR(i, D_CODES-1, 10));
  378. ;    }
  379.  
  380. ;    fclose(header);
  381.         ret
  382. endp
  383.  
  384. ; ===========================================================================
  385. ; Initialize the tree data structures for a new zlib stream.
  386.  
  387. ;void (deflate_state* s)
  388. align 4
  389. proc _tr_init uses eax edi, s:dword
  390.         mov edi,[s]
  391.         call tr_static_init
  392.  
  393.         mov eax,edi
  394.         add eax,deflate_state.dyn_ltree
  395.         mov [edi+deflate_state.l_desc.dyn_tree],eax
  396.         mov [edi+deflate_state.l_desc.stat_desc],static_l_desc
  397.  
  398.         add eax,deflate_state.dyn_dtree-deflate_state.dyn_ltree
  399.         mov [edi+deflate_state.d_desc.dyn_tree],eax
  400.         mov [edi+deflate_state.d_desc.stat_desc],static_d_desc
  401.  
  402.         add eax,deflate_state.bl_tree-deflate_state.dyn_dtree
  403.         mov [edi+deflate_state.bl_desc.dyn_tree],eax
  404.         mov [edi+deflate_state.bl_desc.stat_desc],static_bl_desc;
  405.  
  406.         mov word[edi+deflate_state.bi_buf],0
  407.         mov dword[edi+deflate_state.bi_valid],0
  408. if DEBUG eq 1
  409.         mov dword[edi+deflate_state.compressed_len],0
  410.         mov dword[edi+deflate_state.bits_sent],0
  411. end if
  412.  
  413.         ; Initialize the first block of the first file:
  414.         stdcall init_block,edi
  415.         ret
  416. endp
  417.  
  418. ; ===========================================================================
  419. ; Initialize a new block.
  420.  
  421. ;void (deflate_state* s)
  422. align 4
  423. proc init_block uses eax ecx edi, s:dword
  424.         mov edi,[s]
  425.  
  426.         ; Initialize the trees.
  427.         mov eax,edi
  428.         add eax,deflate_state.dyn_ltree+Freq
  429.         mov ecx,L_CODES
  430.         @@:
  431.                 mov word[eax],0
  432.                 add eax,sizeof.ct_data
  433.                 loop @b
  434.         mov eax,edi
  435.         add eax,deflate_state.dyn_dtree+Freq
  436.         mov ecx,D_CODES
  437.         @@:
  438.                 mov word[eax],0
  439.                 add eax,sizeof.ct_data
  440.                 loop @b
  441.         mov eax,edi
  442.         add eax,deflate_state.bl_tree+Freq
  443.         mov ecx,BL_CODES
  444.         @@:
  445.                 mov word[eax],0
  446.                 add eax,sizeof.ct_data
  447.                 loop @b
  448.  
  449.         mov word[edi+sizeof.ct_data*END_BLOCK+deflate_state.dyn_ltree+Freq],1
  450.         mov dword[edi+deflate_state.static_len],0
  451.         mov dword[edi+deflate_state.opt_len],0
  452.         mov dword[edi+deflate_state.matches],0
  453.         mov dword[edi+deflate_state.last_lit],0
  454.         ret
  455. endp
  456.  
  457. SMALLEST equ 1
  458. ; Index within the heap array of least frequent node in the Huffman tree
  459.  
  460.  
  461. ; ===========================================================================
  462. ; Remove the smallest element from the heap and recreate the heap with
  463. ; one less element. Updates heap and heap_len.
  464.  
  465. macro pqremove s, tree, top
  466. {
  467.         mov eax,s
  468.         add eax,deflate_state.heap+4*SMALLEST
  469.         movzx top,word[eax]
  470. push ebx
  471.         mov ebx,[s+deflate_state.heap_len]
  472.         mov ebx,[s+deflate_state.heap+4*ebx]
  473.         mov [eax],ebx
  474.         dec dword[s+deflate_state.heap_len]
  475. pop ebx
  476.         stdcall pqdownheap, s, tree, SMALLEST
  477. }
  478.  
  479. ; ===========================================================================
  480. ; Compares to subtrees, using the tree depth as tie breaker when
  481. ; the subtrees have equal frequency. This minimizes the worst case length.
  482.  
  483. macro smaller tree, n, m, depth, m_end
  484. {
  485. ;if (..<.. || (..==.. && depth[n] <= depth[m]))
  486. local .end0
  487.         mov eax,n
  488.         imul eax,sizeof.ct_data
  489.         add eax,tree
  490.         mov ax,word[eax+Freq]
  491.         mov ebx,m
  492.         imul ebx,sizeof.ct_data
  493.         add ebx,tree
  494.         mov bx,word[ebx+Freq]
  495.         cmp ax,bx
  496.         jl .end0
  497.         jne m_end
  498.         mov eax,n
  499.         mov al,byte[eax+depth]
  500.         mov ebx,m
  501.         cmp al,byte[ebx+depth]
  502.         jg m_end
  503.         .end0:
  504. }
  505.  
  506. ; ===========================================================================
  507. ; Restore the heap property by moving down the tree starting at node k,
  508. ; exchanging a node with the smallest of its two sons if necessary, stopping
  509. ; when the heap property is re-established (each father smaller than its
  510. ; two sons).
  511.  
  512. ;void (s, tree, k)
  513. ;    deflate_state* s
  514. ;    ct_data* tree ;the tree to restore
  515. ;    int      k    ;node to move down
  516. align 4
  517. proc pqdownheap, s:dword, tree:dword, k:dword
  518. pushad
  519.         ;ecx - v dw
  520.         mov edi,[s]
  521.         mov esi,[k]
  522.         mov ecx,[edi+deflate_state.heap+4*esi]
  523.         shl esi,1
  524.         ;esi = j ;left son of k
  525.         .cycle0: ;while (..<=..)
  526.                 cmp esi,[edi+deflate_state.heap_len]
  527.                 jg .cycle0end
  528.                 ; Set j to the smallest of the two sons:
  529.                 ;;cmp esi,[edi+deflate_state.heap_len]
  530.                 jge .end1 ;if (..<.. &&
  531.                 mov edx,esi
  532.                 shl edx,2
  533.                 add edx,edi
  534.                 add edx,deflate_state.heap
  535.                 smaller [tree], dword[edx+4], dword[edx], edi+deflate_state.depth, .end1
  536.                         inc esi
  537.                 .end1:
  538.                 ; Exit if v is smaller than both sons
  539.                 mov edx,[edi+deflate_state.heap+4*esi]
  540.                 smaller [tree], ecx, edx, edi+deflate_state.depth, .end2
  541.                         jmp .cycle0end ;break
  542.                 .end2:
  543.                 ; Exchange v with the smallest son
  544.                 ;;mov dx,[edi+deflate_state.heap+2*esi]
  545.                 mov eax,[k]
  546.                 mov [edi+deflate_state.heap+4*eax],edx
  547.                 mov [k],esi
  548.                 ; And continue down the tree, setting j to the left son of k
  549.                 shl esi,1
  550.                 jmp .cycle0
  551. align 4
  552.         .cycle0end:
  553.         mov eax,[k]
  554.         mov [edi+deflate_state.heap+4*eax],ecx
  555. popad
  556.         ret
  557. endp
  558.  
  559. ; ===========================================================================
  560. ; Compute the optimal bit lengths for a tree and update the total bit length
  561. ; for the current block.
  562. ; IN assertion: the fields freq and dad are set, heap[heap_max] and
  563. ;    above are the tree nodes sorted by increasing frequency.
  564. ; OUT assertions: the field len is set to the optimal bit length, the
  565. ;     array bl_count contains the frequencies for each bit length.
  566. ;     The length opt_len is updated; static_len is also updated if stree is
  567. ;     not null.
  568.  
  569. ;void (s, desc)
  570. ;    deflate_state* s
  571. ;    tree_desc* desc ;the tree descriptor
  572. align 4
  573. proc gen_bitlen, s:dword, desc:dword
  574. locals
  575.         tree  dd ? ;ct_data* ;= desc.dyn_tree
  576.         max_code dd ? ;int   ;= desc.max_code
  577.         stree dd ? ;ct_data* ;= desc.stat_desc.static_tree
  578.         extra dd ? ;intf*    ;= desc.stat_desc.extra_bits
  579.         base  dd ? ;int      ;= desc.stat_desc.extra_base
  580.         max_length dd ? ;int ;= desc.stat_desc.max_length
  581.         h     dd ? ;int ;heap index
  582.         m     dd ? ;int ;iterate over the tree elements
  583.         bits  dd ? ;int ;bit length
  584.         xbits dd ? ;int ;extra bits
  585.         f     dw ? ;uint_16 ;frequency
  586.         overflow dd 0 ;int ;number of elements with bit length too large
  587. endl
  588. pushad
  589.         mov edi,[s]
  590.         mov edx,[desc]
  591.         mov eax,[edx+tree_desc.dyn_tree]
  592.         mov [tree],eax
  593.         mov eax,[edx+tree_desc.max_code]
  594.         mov [max_code],eax
  595.         mov ebx,[edx+tree_desc.stat_desc]
  596.         mov eax,[ebx+static_tree_desc.static_tree]
  597.         mov [stree],eax
  598.         mov eax,[ebx+static_tree_desc.extra_bits]
  599.         mov [extra],eax
  600.         mov eax,[ebx+static_tree_desc.extra_base]
  601.         mov [base],eax
  602.         mov eax,[ebx+static_tree_desc.max_length]
  603.         mov [max_length],eax
  604.  
  605.         xor ecx,ecx
  606.         .cycle0:
  607.         cmp ecx,MAX_BITS
  608.         jg .cycle0end ;for (..;..<=..;..)
  609.                 mov word[edi+deflate_state.bl_count+2*ecx],0
  610.                 inc ecx
  611.                 jmp .cycle0
  612. align 4
  613.         .cycle0end:
  614.  
  615.         ; In a first pass, compute the optimal bit lengths (which may
  616.         ; overflow in the case of the bit length tree).
  617.  
  618.         mov eax,[edi+deflate_state.heap_max]
  619.         mov eax,[edi+deflate_state.heap+4*eax]
  620.         imul eax,sizeof.ct_data
  621.         add eax,[tree]
  622.         mov word[eax+Len],0 ;root of the heap
  623.  
  624.         mov eax,[edi+deflate_state.heap_max]
  625.         inc eax
  626.         mov [h],eax
  627.         .cycle1:
  628.         cmp dword[h],HEAP_SIZE
  629.         jge .cycle1end ;for (..;..<..;..)
  630.                 mov eax,[h]
  631.                 mov ecx,[edi+deflate_state.heap+4*eax]
  632.                 ;ecx = n
  633.                 mov eax,sizeof.ct_data
  634.                 imul eax,ecx
  635.                 add eax,[tree]
  636.                 movzx eax,word[eax+Dad]
  637.                 imul eax,sizeof.ct_data
  638.                 add eax,[tree]
  639.                 movzx eax,word[eax+Len]
  640.                 inc eax
  641.                 mov [bits],eax ;bits = tree[tree[n].Dad].Len + 1
  642.                 mov eax,[max_length]
  643.                 cmp [bits],eax
  644.                 jle @f ;if (..>..)
  645.                         mov [bits],eax
  646.                         inc dword[overflow]
  647.                 @@:
  648.                 mov esi,[bits]
  649.                 mov eax,sizeof.ct_data
  650.                 imul eax,ecx
  651.                 add eax,[tree]
  652.                 mov word[eax+Len],si
  653.                 ; We overwrite tree[n].Dad which is no longer needed
  654.  
  655.                 cmp ecx,[max_code]
  656.                 jle @f
  657.                         inc dword[h]
  658.                         jmp .cycle1 ;if (..>..) continue ;not a leaf node
  659.                 @@:
  660.  
  661.                 mov eax,[bits]
  662.                 shl eax,1 ;*= sizeof.uint_16
  663.                 inc word[eax+edi+deflate_state.bl_count]
  664.                 mov dword[xbits],0
  665.                 cmp ecx,[base]
  666.                 jl @f ;if (..>=..)
  667.                         mov eax,ecx
  668.                         sub eax,[base]
  669.                         shl eax,2 ;*= sizeof.dd
  670.                         add eax,[extra]
  671.                         mov eax,[eax]
  672.                         mov [xbits],eax
  673.                 @@:
  674.                 mov eax,sizeof.ct_data
  675.                 imul eax,ecx
  676.                 add eax,[tree]
  677.                 movzx eax,word[eax+Freq]
  678.                 mov [f],ax
  679.                 mov esi,[bits]
  680.                 add esi,[xbits]
  681.                 imul eax,esi
  682.                 add [edi+deflate_state.opt_len],eax
  683.                 cmp dword[stree],0
  684.                 je @f ;if (..)
  685.                         movzx eax,word[f]
  686.                         mov esi,sizeof.ct_data
  687.                         imul esi,ecx
  688.                         add esi,[tree]
  689.                         movzx esi,word[esi+Len]
  690.                         add esi,[xbits]
  691.                         imul eax,esi
  692.                         add [edi+deflate_state.static_len],eax
  693.                 @@:
  694.                 inc dword[h]
  695.                 jmp .cycle1
  696. align 4
  697.         .cycle1end:
  698.         cmp dword[overflow],0
  699.         je .end_f ;if (..==0) return
  700.  
  701. ;    Trace((stderr,"\nbit length overflow\n"));
  702.         ; This happens for example on obj2 and pic of the Calgary corpus
  703.  
  704.         ; Find the first bit length which could increase:
  705.         .cycle2: ;do
  706.                 mov eax,[max_length]
  707.                 dec eax
  708.                 mov [bits],eax
  709.                 shl eax,1 ;*= sizeof.dw
  710.                 add eax,edi
  711.                 add eax,deflate_state.bl_count
  712.                 @@:
  713.                 cmp word[eax],0
  714.                 jne @f ;while (..==0) bits--
  715.                         dec dword[bits]
  716.                         sub eax,2
  717.                         jmp @b
  718. align 4
  719.                 @@:
  720.                 dec word[eax]     ;move one leaf down the tree
  721.                 add word[eax+2],2 ;move one overflow item as its brother
  722.                 mov eax,[max_length]
  723.                 dec word[edi+deflate_state.bl_count+2*eax]
  724.                 ; The brother of the overflow item also moves one step up,
  725.                 ; but this does not affect bl_count[max_length]
  726.  
  727.                 sub dword[overflow],2
  728.                 cmp dword[overflow],0
  729.                 jg .cycle2 ;while (..>0)
  730.  
  731.         ; Now recompute all bit lengths, scanning in increasing frequency.
  732.         ; h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
  733.         ; lengths instead of fixing only the wrong ones. This idea is taken
  734.         ; from 'ar' written by Haruhiko Okumura.)
  735.  
  736.         mov eax,[max_length]
  737.         mov [bits],eax
  738.         .cycle3:
  739.         cmp dword[bits],0
  740.         je .end_f ;for (..;..!=0;..)
  741.                 mov eax,[bits]
  742.                 shl eax,1 ;*= sizeof.dw
  743.                 movzx ecx,word[eax+edi+deflate_state.bl_count]
  744.                 .cycle4: ;while (..!=0)
  745.                 cmp ecx,0
  746.                 je .cycle4end
  747.                         dec dword[h]
  748.                         mov eax,[h]
  749.                         mov eax,[edi+deflate_state.heap+4*eax]
  750.                         mov [m],eax ;m = s.heap[--h]
  751.                         cmp eax,[max_code]
  752.                         jg .cycle4 ;if (..>..) continue
  753.                         mov esi,[m]
  754.                         imul esi,sizeof.ct_data
  755.                         add esi,[tree] ;esi = &tree[m]
  756.                         mov eax,[bits]
  757.                         cmp word[esi+Len],ax
  758.                         je @f ;if (..!=..)
  759. ;                Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
  760.                                 movzx ebx,word[esi+Len]
  761.                                 sub eax,ebx
  762.                                 movzx ebx,word[esi+Freq]
  763.                                 imul eax,ebx ;eax = (bits - tree[m].Len) * tree[m].Freq
  764.                                 add [edi+deflate_state.opt_len],eax
  765.                                 mov eax,[bits]
  766.                                 mov word[esi+Len],ax
  767.                         @@:
  768.                         dec ecx
  769.                         jmp .cycle4
  770. align 4
  771.                 .cycle4end:
  772.                 dec dword[bits]
  773.                 jmp .cycle3
  774. align 4
  775. .end_f:
  776. popad
  777.         ret
  778. endp
  779.  
  780. ; ===========================================================================
  781. ; Generate the codes for a given tree and bit counts (which need not be
  782. ; optimal).
  783. ; IN assertion: the array bl_count contains the bit length statistics for
  784. ; the given tree and the field len is set for all tree elements.
  785. ; OUT assertion: the field code is set for all tree elements of non
  786. ;     zero code length.
  787.  
  788. ;void (tree, max_code, bl_count)
  789. ;    ct_data *tree     ;the tree to decorate
  790. ;    int max_code      ;largest code with non zero frequency
  791. ;    uint_16p bl_count ;number of codes at each bit length
  792. align 4
  793. proc gen_codes uses eax ebx ecx edx edi, tree:dword, max_code:dword, bl_count:dword
  794. locals
  795.         u_code dw 0 ;uint_16 ;running code value
  796.         bits   dd 1 ;int ;bit index
  797.         next_code rw MAX_BITS+1 ;uint_16[] ;next code value for each bit length
  798. endl
  799.         ; The distribution counts are first used to generate the code values
  800.         ; without bit reversal.
  801.         mov ebx,ebp
  802.         sub ebx,2*(MAX_BITS+1)
  803.  
  804.         .cycle0: ;for (..;..<=..;..)
  805.         cmp dword[bits],MAX_BITS
  806.         jg .cycle0end
  807.                 mov eax,[bits]
  808.                 dec eax
  809.                 shl eax,1
  810.                 add eax,[bl_count]
  811.                 mov ax,word[eax]
  812.                 add ax,[u_code]
  813.                 shl ax,1 ;ax = (u_code + bl_count[bits-1]) << 1
  814.                 mov [u_code],ax
  815.                 mov ecx,[bits]
  816.                 mov word[ebx+2*ecx],ax ;next_code[bits] = u_code
  817.                 inc dword[bits]
  818.                 jmp .cycle0
  819.         .cycle0end:
  820.         ; Check that the bit counts in bl_count are consistent. The last code
  821.         ; must be all ones.
  822.  
  823.         mov eax,[bl_count]
  824.         mov ax,word[eax+2*MAX_BITS]
  825.         add ax,[u_code]
  826.         dec ax
  827.         cmp ax,(1 shl MAX_BITS)-1
  828.         je @f
  829.                 zlib_assert 'inconsistent bit counts' ;Assert(..==..)
  830.         @@:
  831. ;    Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
  832.  
  833.         xor ecx,ecx ;n = 0
  834.         .cycle1: ;for (..;..<=..;..)
  835.         cmp ecx,[max_code]
  836.         jg .cycle1end
  837.                 mov edx,sizeof.ct_data
  838.                 imul edx,ecx
  839.                 add edx,[tree] ;edx = &tree[n]
  840.                 movzx edi,word[edx+Len]
  841.                 cmp edi,0
  842.                 jne @f ;if (..==0) continue
  843.                         inc ecx
  844.                         jmp .cycle1
  845.                 @@:
  846.                 ; Now reverse the bits
  847.                 movzx eax,word[ebx+2*edi]
  848.                 stdcall bi_reverse, eax, edi
  849.                 mov word[edx+Code],ax
  850.                 inc word[ebx+2*edi]
  851.  
  852. ;        Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
  853. ;             n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
  854.                 inc ecx
  855.                 jmp .cycle1
  856.         .cycle1end:
  857.         ret
  858. endp
  859.  
  860. ; ===========================================================================
  861. ; Construct one Huffman tree and assigns the code bit strings and lengths.
  862. ; Update the total bit length for the current block.
  863. ; IN assertion: the field freq is set for all tree elements.
  864. ; OUT assertions: the fields len and code are set to the optimal bit length
  865. ;     and corresponding code. The length opt_len is updated; static_len is
  866. ;     also updated if stree is not null. The field max_code is set.
  867.  
  868. ;void (s, desc)
  869. ;    deflate_state* s
  870. ;    tree_desc *desc ;the tree descriptor
  871. align 4
  872. proc build_tree uses eax ebx ecx edx edi, s:dword, desc:dword
  873. locals
  874.         tree     dd  ? ;ct_data* ;= desc.dyn_tree
  875.         stree    dd  ? ;ct_data* ;= desc.stat_desc.static_tree
  876.         elems    dd  ? ;int      ;= desc.stat_desc.elems
  877.         m        dd  ? ;int ;iterate over heap elements
  878.         max_code dd -1 ;int ;largest code with non zero frequency
  879.         node     dd  ? ;int ;new node being created
  880. endl
  881.         ; Construct the initial heap, with least frequent element in
  882.         ; heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
  883.         ; heap[0] is not used.
  884.         mov ebx,[desc]
  885.         mov eax,[ebx+tree_desc.dyn_tree]
  886.         mov [tree],eax
  887.         mov ecx,[ebx+tree_desc.stat_desc]
  888.         mov eax,[ecx+static_tree_desc.static_tree]
  889.         mov [stree],eax
  890.         mov ecx,[ecx+static_tree_desc.elems]
  891.         mov [elems],ecx
  892.         mov edi,[s]
  893.         zlib_debug 'build_tree cycle0 ecx = %d',ecx
  894.  
  895.         mov dword[edi+deflate_state.heap_len],0
  896.         mov dword[edi+deflate_state.heap_max],HEAP_SIZE
  897.  
  898.         mov edx,[tree]
  899.         xor ecx,ecx
  900.         .cycle0: ;for (..;..<..;..)
  901.         cmp ecx,[elems]
  902.         jge .cycle0end
  903.                 cmp word[edx+Freq],0
  904.                 je @f ;if (..!=0)
  905.                         inc dword[edi+deflate_state.heap_len]
  906.                         mov eax,[edi+deflate_state.heap_len]
  907.                         mov [max_code],ecx
  908.                         mov dword[edi+deflate_state.heap+4*eax],ecx
  909.                         mov byte[edi+deflate_state.depth+ecx],0
  910.                         jmp .end0
  911. align 4
  912.                 @@: ;else
  913.                         mov word[edx+Len],0
  914.                 .end0:
  915.                 add edx,sizeof.ct_data
  916.                 inc ecx
  917.                 jmp .cycle0
  918. align 4
  919.         .cycle0end:
  920.  
  921.         ; The pkzip format requires that at least one distance code exists,
  922.         ; and that at least one bit should be sent even if there is only one
  923.         ; possible code. So to avoid special checks later on we force at least
  924.         ; two codes of non zero frequency.
  925.  
  926.         .cycle1: ;while (..<..)
  927.                 cmp dword[edi+deflate_state.heap_len],2
  928.                 jge .cycle1end
  929.                 inc dword[edi+deflate_state.heap_len]
  930.                 xor eax,eax
  931.                 cmp dword[max_code],2
  932.                 jge @f
  933.                         inc dword[max_code]
  934.                         mov eax,[max_code]
  935.                 @@:
  936.                 mov ecx,[edi+deflate_state.heap_len]
  937.                 mov [edi+deflate_state.heap+4*ecx],eax
  938.                 mov [node],eax
  939.                 imul eax,sizeof.ct_data
  940.                 add eax,[tree]
  941.                 mov word[eax+Freq],1
  942.                 mov eax,[node]
  943.                 mov byte[edi+deflate_state.depth+eax],0
  944.                 dec dword[edi+deflate_state.opt_len]
  945.                 cmp dword[stree],0
  946.                 je .cycle1 ;if (..)
  947.                         mov eax,[node]
  948.                         imul eax,sizeof.ct_data
  949.                         add eax,[stree]
  950.                         movzx eax,word[eax+Len]
  951.                         sub [edi+deflate_state.static_len],eax
  952.                 ; node is 0 or 1 so it does not have extra bits
  953.                 jmp .cycle1
  954. align 4
  955.         .cycle1end:
  956.         mov eax,[max_code]
  957.         mov [ebx+tree_desc.max_code],eax
  958.  
  959.         ; The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
  960.         ; establish sub-heaps of increasing lengths:
  961.  
  962.         mov ecx,[edi+deflate_state.heap_len]
  963.         shr ecx,1
  964.         .cycle2: ;for (..;..>=..;..)
  965.                 cmp ecx,1
  966.                 jl .cycle2end
  967.                 stdcall pqdownheap, edi, [tree], ecx
  968.                 dec ecx
  969.                 jmp .cycle2
  970. align 4
  971.         .cycle2end:
  972.  
  973.         ; Construct the Huffman tree by repeatedly combining the least two
  974.         ; frequent nodes.
  975.  
  976.         mov eax,[elems]
  977.         mov [node],eax ;next internal node of the tree
  978.         .cycle3: ;do
  979.                 pqremove edi, [tree], ecx ;n = node of least frequency
  980.                 movzx edx,word[eax]
  981.                 mov [m],edx ;m = node of next least frequency
  982.  
  983.                 mov eax,[edi+deflate_state.heap_max]
  984.                 dec eax
  985.                 mov [edi+deflate_state.heap+4*eax],ecx ;keep the nodes sorted by frequency
  986.                 dec eax
  987.                 mov [edi+deflate_state.heap_max],eax
  988.                 mov [edi+deflate_state.heap+4*eax],edx
  989.  
  990.                 ; Create a new node father of n and m
  991.                 ;;mov edx,[m]
  992.                 imul edx,sizeof.ct_data
  993.                 add edx,[tree]
  994.                 mov ax,word[edx+Freq]
  995.                 mov edx,ecx
  996.                 imul edx,sizeof.ct_data
  997.                 add edx,[tree]
  998.                 add ax,word[edx+Freq]
  999.                 mov edx,[node]
  1000.                 imul edx,sizeof.ct_data
  1001.                 add edx,[tree]
  1002.                 mov word[edx+Freq],ax
  1003.  
  1004.                 mov eax,ecx
  1005.                 add eax,edi
  1006.                 mov al,byte[eax+deflate_state.depth]
  1007.                 mov edx,[m]
  1008.                 add edx,edi
  1009.                 mov ah,byte[edx+deflate_state.depth]
  1010.                 cmp al,ah
  1011.                 jge @f ;if (al>=ah) al=al : al=ah
  1012.                         mov al,ah
  1013.                 @@:
  1014.                 inc al
  1015.                 mov edx,[node]
  1016.                 add edx,edi
  1017.                 mov byte[edx+deflate_state.depth],al
  1018.  
  1019.                 mov eax,[node]
  1020.                 mov edx,[m]
  1021.                 imul edx,sizeof.ct_data
  1022.                 add edx,[tree]
  1023.                 mov [edx+Dad],ax
  1024.                 mov edx,ecx
  1025.                 imul edx,sizeof.ct_data
  1026.                 add edx,[tree]
  1027.                 mov [edx+Dad],ax
  1028. ;if DUMP_BL_TREE eq 1
  1029. ;        if (tree == s->bl_tree) {
  1030. ;            fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
  1031. ;                    node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
  1032. ;        }
  1033. ;end if
  1034.                 ; and insert the new node in the heap
  1035.                 mov ecx,[node]
  1036.                 mov [edi+deflate_state.heap+4*SMALLEST],ecx
  1037.                 inc dword[node]
  1038.                 stdcall pqdownheap, edi, [tree], SMALLEST
  1039.                 cmp dword[edi+deflate_state.heap_len],2
  1040.                 jge .cycle3 ;while (..>=..)
  1041.  
  1042.         mov ecx,[edi+deflate_state.heap+4*SMALLEST]
  1043.         dec dword[edi+deflate_state.heap_max]
  1044.         mov eax,[edi+deflate_state.heap_max]
  1045.         mov [edi+deflate_state.heap+4*eax],ecx
  1046.  
  1047.         ; At this point, the fields freq and dad are set. We can now
  1048.         ; generate the bit lengths.
  1049.  
  1050.         stdcall gen_bitlen, edi, [desc]
  1051.  
  1052.         ; The field len is now set, we can generate the bit codes
  1053.         mov eax,edi
  1054.         add eax,deflate_state.bl_count
  1055.         stdcall gen_codes, [tree], [max_code], eax
  1056.         ret
  1057. endp
  1058.  
  1059. ; ===========================================================================
  1060. ; Scan a literal or distance tree to determine the frequencies of the codes
  1061. ; in the bit length tree.
  1062.  
  1063. ;void (s, tree, max_code)
  1064. ;    deflate_state* s
  1065. ;    ct_data *tree ;the tree to be scanned
  1066. ;    int max_code  ;and its largest code of non zero frequency
  1067. align 4
  1068. proc scan_tree uses eax ebx ecx edi, s:dword, tree:dword, max_code:dword
  1069. locals
  1070.         n dd ? ;int ;iterates over all tree elements
  1071.         prevlen  dd -1 ;int ;last emitted length
  1072.         curlen    dd ? ;int ;length of current code
  1073.         nextlen   dd ? ;int ;= tree[0].Len ;length of next code
  1074.         count     dd 0 ;int ;repeat count of the current code
  1075.         max_count dd 7 ;int ;max repeat count
  1076.         min_count dd 4 ;int ;min repeat count
  1077. endl
  1078.         mov edi,[s]
  1079.         mov eax,[tree]
  1080.         movzx eax,word[eax+Len]
  1081.         mov [nextlen],eax
  1082.         test eax,eax
  1083.         jnz @f ;if (..==0)
  1084.                 mov dword[max_count],138
  1085.                 mov dword[min_count],3
  1086.         @@:
  1087.         mov eax,[max_code]
  1088.         inc eax
  1089.         imul eax,sizeof.ct_data
  1090.         add eax,[tree]
  1091.         mov word[eax+Len],0xffff ;guard
  1092.  
  1093.         xor ecx,ecx
  1094. align 4
  1095.         .cycle0:
  1096.                 cmp ecx,[max_code]
  1097.                 jg .cycle0end ;for (..;..<=..;..)
  1098.                 mov eax,[nextlen]
  1099.                 mov [curlen],eax
  1100.                 inc ecx
  1101.                 mov eax,sizeof.ct_data
  1102.                 imul eax,ecx
  1103.                 add eax,[tree]
  1104.                 movzx eax,word[eax+Len]
  1105.                 mov [nextlen],eax
  1106.                 inc dword[count]
  1107.                 mov ebx,[count]
  1108.                 cmp ebx,[max_count]
  1109.                 jge .end0
  1110.                 mov eax,[nextlen]
  1111.                 cmp [curlen],eax
  1112.                 je .cycle0 ;if (..<.. && ..==..) continue
  1113. align 4
  1114.                 .end0:
  1115.                 cmp ebx,[min_count]
  1116.                 jge .end1 ;else if (..<..)
  1117.                         mov eax,[curlen]
  1118.                         imul eax,sizeof.ct_data
  1119.                         add eax,edi
  1120.                         add word[eax+deflate_state.bl_tree+Freq],bx
  1121.                         jmp .end4
  1122. align 4
  1123.                 .end1:
  1124.                 cmp dword[curlen],0
  1125.                 je .end2 ;else if (..!=0)
  1126.                         mov eax,[curlen]
  1127.                         cmp eax,[prevlen]
  1128.                         je @f ;if (..!=..)
  1129.                                 imul eax,sizeof.ct_data
  1130.                                 add eax,edi
  1131.                                 inc word[eax+deflate_state.bl_tree+Freq]
  1132.                         @@:
  1133.                         mov eax,REP_3_6
  1134.                         imul eax,sizeof.ct_data
  1135.                         add eax,edi
  1136.                         inc word[eax+deflate_state.bl_tree+Freq]
  1137.                         jmp .end4
  1138. align 4
  1139.                 .end2:
  1140.                 cmp ebx,10
  1141.                 jg .end3 ;else if (..<=..)
  1142.                         mov eax,REPZ_3_10
  1143.                         imul eax,sizeof.ct_data
  1144.                         add eax,edi
  1145.                         inc word[eax+deflate_state.bl_tree+Freq]
  1146.                         jmp .end4
  1147. align 4
  1148.                 .end3: ;else
  1149.                         mov eax,REPZ_11_138
  1150.                         imul eax,sizeof.ct_data
  1151.                         add eax,edi
  1152.                         inc word[eax+deflate_state.bl_tree+Freq]
  1153.                 .end4:
  1154.                 mov dword[count],0
  1155.                 mov eax,[curlen]
  1156.                 mov [prevlen],eax
  1157.                 cmp dword[nextlen],0
  1158.                 jne .end5 ;if (..==0)
  1159.                         mov dword[max_count],138
  1160.                         mov dword[min_count],3
  1161.                         jmp .cycle0
  1162. align 4
  1163.                 .end5:
  1164.                 cmp eax,[nextlen]
  1165.                 jne .end6 ;else if (..==..)
  1166.                         mov dword[max_count],6
  1167.                         mov dword[min_count],3
  1168.                         jmp .cycle0
  1169. align 4
  1170.                 .end6: ;else
  1171.                         mov dword[max_count],7
  1172.                         mov dword[min_count],4
  1173.                 jmp .cycle0
  1174. align 4
  1175.         .cycle0end:
  1176.         ret
  1177. endp
  1178.  
  1179. ; ===========================================================================
  1180. ; Send a literal or distance tree in compressed form, using the codes in
  1181. ; bl_tree.
  1182.  
  1183. ;void (s, tree, max_code)
  1184. ;    deflate_state* s
  1185. ;    ct_data *tree ;the tree to be scanned
  1186. ;    int max_code  ;and its largest code of non zero frequency
  1187. align 4
  1188. proc send_tree uses eax ebx ecx edi, s:dword, tree:dword, max_code:dword
  1189. locals
  1190.         n dd ? ;int ;iterates over all tree elements
  1191.         prevlen  dd -1 ;int ;last emitted length
  1192.         curlen    dd ? ;int ;length of current code
  1193.         nextlen   dd ? ;int ;= tree[0].Len ;length of next code
  1194.         count     dd 0 ;int ;repeat count of the current code
  1195.         max_count dd 7 ;int ;max repeat count
  1196.         min_count dd 4 ;int ;min repeat count
  1197. endl
  1198.         mov edi,[s]
  1199.         ; *** tree[max_code+1].Len = -1 ;guard already set
  1200.         mov eax,[tree]
  1201.         movzx eax,word[eax+Len]
  1202.         mov [nextlen],eax
  1203.         xor ecx,ecx
  1204.         test eax,eax
  1205.         jnz .cycle0 ;if (..==0)
  1206.                 mov dword[max_count],138
  1207.                 mov dword[min_count],3
  1208. align 4
  1209.         .cycle0: ;for (..;..<=..;..)
  1210.         cmp ecx,[max_code]
  1211.         jg .cycle0end
  1212.                 mov eax,[nextlen]
  1213.                 mov [curlen],eax
  1214.                 mov eax,ecx
  1215.                 inc eax
  1216.                 imul eax,sizeof.ct_data
  1217.                 add eax,[tree]
  1218.                 movzx eax,word[eax+Len]
  1219.                 mov [nextlen],eax
  1220.                 inc dword[count]
  1221.                 mov ebx,[count]
  1222.                 cmp ebx,[max_count]
  1223.                 jge .end0
  1224.                 mov eax,[nextlen]
  1225.                 cmp [curlen],eax
  1226.                 jne .end0 ;if (..<.. && ..==..)
  1227.                         inc ecx
  1228.                         jmp .cycle0 ;continue
  1229. align 4
  1230.                 .end0:
  1231.                 cmp ebx,[min_count]
  1232.                 jge .end1 ;else if (..<..)
  1233.                         @@: ;do
  1234.                                 mov ebx,edi
  1235.                                 add ebx,deflate_state.bl_tree
  1236.                                 send_code edi, [curlen], ebx
  1237.                                 dec dword[count]
  1238.                                 jnz @b ;while (..!=0)
  1239.                         jmp .end4
  1240. align 4
  1241.                 .end1:
  1242.                 cmp dword[curlen],0
  1243.                 je .end2 ;else if (..!=0)
  1244.                         mov eax,[curlen]
  1245.                         cmp eax,[prevlen]
  1246.                         je @f ;if (..!=..)
  1247.                                 mov ebx,edi
  1248.                                 add ebx,deflate_state.bl_tree
  1249.                                 send_code edi, eax, ebx
  1250.                                 dec dword[count]
  1251.                         @@:
  1252.                         cmp dword[count],3
  1253.                         jl @f
  1254.                         cmp dword[count],6
  1255.                         jle .end8
  1256.                         @@:
  1257.                                 zlib_assert ' 3_6?' ;Assert(..>=.. && ..<=..)
  1258.                         .end8:
  1259.                         mov ebx,edi
  1260.                         add ebx,deflate_state.bl_tree
  1261.                         send_code edi, REP_3_6, ebx
  1262.                         mov ebx,[count]
  1263.                         sub ebx,3
  1264.                         stdcall send_bits, edi, ebx, 2
  1265.                         jmp .end4
  1266.                 .end2:
  1267.                 cmp ebx,10
  1268.                 jg .end3 ;else if (..<=..)
  1269.                         mov ebx,edi
  1270.                         add ebx,deflate_state.bl_tree
  1271.                         send_code edi, REPZ_3_10, ebx
  1272.                         mov ebx,[count]
  1273.                         sub ebx,3
  1274.                         stdcall send_bits, edi, ebx, 3
  1275.                         jmp .end4
  1276.                 .end3: ;else
  1277.                         mov ebx,edi
  1278.                         add ebx,deflate_state.bl_tree
  1279.                         send_code edi, REPZ_11_138, ebx
  1280.                         mov ebx,[count]
  1281.                         sub ebx,11
  1282.                         stdcall send_bits, edi, ebx, 7
  1283.                 .end4:
  1284.                 mov dword[curlen],0
  1285.                 mov eax,[curlen]
  1286.                 mov [prevlen],eax
  1287.                 mov [nextlen],eax
  1288.                 cmp eax,0
  1289.                 jne .end5 ;if (..==0)
  1290.                         mov dword[max_count],138
  1291.                         mov dword[min_count],3
  1292.                         jmp .end7
  1293.                 .end5:
  1294.                 mov eax,[curlen]
  1295.                 cmp eax,[nextlen]
  1296.                 jne .end6 ;else if (..==..)
  1297.                         mov dword[max_count],6
  1298.                         mov dword[min_count],3
  1299.                         jmp .end7
  1300.                 .end6: ;else
  1301.                         mov dword[max_count],7
  1302.                         mov dword[min_count],4
  1303.                 .end7:
  1304.                 inc ecx
  1305.                 jmp .cycle0
  1306. align 4
  1307.         .cycle0end:
  1308.         ret
  1309. endp
  1310.  
  1311. ; ===========================================================================
  1312. ; Construct the Huffman tree for the bit lengths and return the index in
  1313. ; bl_order of the last bit length code to send.
  1314.  
  1315. ;int (deflate_state* s)
  1316. align 4
  1317. proc build_bl_tree uses edi, s:dword
  1318. locals
  1319.         max_blindex dd ? ;int ;index of last bit length code of non zero freq
  1320. endl
  1321.         mov edi,[s]
  1322.         ; Determine the bit length frequencies for literal and distance trees
  1323.         mov eax,edi
  1324.         add eax,deflate_state.dyn_ltree
  1325.         stdcall scan_tree, edi, eax, [edi+deflate_state.l_desc.max_code]
  1326.         add eax,deflate_state.dyn_dtree-deflate_state.dyn_ltree
  1327.         stdcall scan_tree, edi, eax, [edi+deflate_state.d_desc.max_code]
  1328.  
  1329.         ; Build the bit length tree:
  1330.         add eax,deflate_state.bl_desc-deflate_state.dyn_dtree
  1331.         stdcall build_tree, edi, eax
  1332.         ; opt_len now includes the length of the tree representations, except
  1333.         ; the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
  1334.  
  1335.         ; Determine the number of bit length codes to send. The pkzip format
  1336.         ; requires that at least 4 bit length codes be sent. (appnote.txt says
  1337.         ; 3 but the actual value used is 4.)
  1338.  
  1339.         mov dword[max_blindex],BL_CODES-1
  1340.         .cycle0: ;for (..;..>=..;..)
  1341.                 cmp dword[max_blindex],3
  1342.                 jl .cycle0end
  1343.                 dec dword[max_blindex]
  1344.                 mov eax,[max_blindex]
  1345.                 add eax,bl_order
  1346.                 movzx eax,byte[eax]
  1347.                 imul eax,sizeof.ct_data
  1348.                 add eax,edi
  1349.                 cmp word[eax+deflate_state.bl_tree+Len],0
  1350.                 jne .cycle0end ;if (..!=0) break
  1351.                 jmp .cycle0
  1352. align 4
  1353.         .cycle0end:
  1354.         ; Update opt_len to include the bit length tree and counts
  1355.         mov eax,[max_blindex]
  1356.         inc eax
  1357.         imul eax,3
  1358.         add eax,5+5+4
  1359.         add [edi+deflate_state.opt_len],eax
  1360. ;    Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", s->opt_len, s->static_len));
  1361.  
  1362.         mov eax,[max_blindex]
  1363.         ret
  1364. endp
  1365.  
  1366. ; ===========================================================================
  1367. ; Send the header for a block using dynamic Huffman trees: the counts, the
  1368. ; lengths of the bit length codes, the literal tree and the distance tree.
  1369. ; IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
  1370.  
  1371. ;void (s, lcodes, dcodes, blcodes)
  1372. ;    deflate_state* s
  1373. ;    int lcodes, dcodes, blcodes ;number of codes for each tree
  1374. align 4
  1375. proc send_all_trees uses eax ebx ecx edi, s:dword, lcodes:dword, dcodes:dword, blcodes:dword
  1376. ;ecx = index in bl_order
  1377.         cmp dword[lcodes],257
  1378.         jl @f
  1379.         cmp dword[dcodes],1
  1380.         jl @f
  1381.         cmp dword[blcodes],4
  1382.         jge .end0
  1383.         @@:
  1384.                 zlib_assert 'not enough codes' ;Assert(..>=.. && ..>=.. && ..>=..)
  1385.         .end0:
  1386.         cmp dword[lcodes],L_CODES
  1387.         jg @f
  1388.         cmp dword[dcodes],D_CODES
  1389.         jg @f
  1390.         cmp dword[blcodes],BL_CODES
  1391.         jle .end1
  1392.         @@:
  1393.                 zlib_assert 'too many codes' ;Assert(..<=.. && ..<=.. && ..<=..)
  1394.         .end1:
  1395. ;    Tracev((stderr, "\nbl counts: "));
  1396.         mov edi,[s]
  1397.         mov eax,[lcodes]
  1398.         sub eax,257
  1399.         stdcall send_bits, edi, eax, 5 ;not +255 as stated in appnote.txt
  1400.         mov eax,[dcodes]
  1401.         dec eax
  1402.         stdcall send_bits, edi, eax, 5
  1403.         mov eax,[blcodes]
  1404.         sub eax,4
  1405.         stdcall send_bits, edi, eax, 4 ;not -3 as stated in appnote.txt
  1406.         xor ecx,ecx
  1407.         .cycle0:
  1408.                 cmp ecx,[blcodes]
  1409.                 jge .cycle0end ;for (..;..<..;..)
  1410. ;        Tracev((stderr, "\nbl code %2d ", bl_order[ecx]));
  1411.                 movzx eax,byte[ecx+bl_order]
  1412.                 movzx eax,word[edi+sizeof.ct_data*eax+deflate_state.bl_tree+Len]
  1413.                 stdcall send_bits, edi, eax, 3
  1414.                 inc ecx
  1415.                 jmp .cycle0
  1416. align 4
  1417.         .cycle0end:
  1418. ;    Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
  1419.  
  1420.         mov ebx,[lcodes]
  1421.         dec ebx
  1422.         mov eax,edi
  1423.         add eax,deflate_state.dyn_ltree
  1424.         stdcall send_tree, edi, eax, ebx ;literal tree
  1425. ;    Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
  1426.  
  1427.         mov ebx,[dcodes]
  1428.         dec ebx
  1429.         add eax,deflate_state.dyn_dtree-deflate_state.dyn_ltree
  1430.         stdcall send_tree, edi, eax, ebx ;distance tree
  1431. ;    Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
  1432.         ret
  1433. endp
  1434.  
  1435. ; ===========================================================================
  1436. ; Send a stored block
  1437.  
  1438. ;void (s, buf, stored_len, last)
  1439. ;    deflate_state* s
  1440. ;    charf *buf     ;input block
  1441. ;    ulg stored_len ;length of input block
  1442. ;    int last       ;one if this is the last block for a file
  1443. align 4
  1444. proc _tr_stored_block uses eax edi, s:dword, buf:dword, stored_len:dword, last:dword
  1445.         mov edi,[s]
  1446.         mov eax,[last]
  1447.         add eax,STORED_BLOCK shl 1
  1448.         stdcall send_bits, edi, eax, 3 ;send block type
  1449. if DEBUG eq 1
  1450.         mov eax,[edi+deflate_state.compressed_len]
  1451.         add eax,3+7
  1452.         and eax,not 7
  1453.         mov [edi+deflate_state.compressed_len],eax
  1454.         mov eax,[stored_len]
  1455.         add eax,4
  1456.         shl eax,3
  1457.         add [edi+deflate_state.compressed_len],eax
  1458. end if
  1459.         stdcall copy_block, edi, [buf], [stored_len], 1 ;with header
  1460.         ret
  1461. endp
  1462.  
  1463. ; ===========================================================================
  1464. ; Flush the bits in the bit buffer to pending output (leaves at most 7 bits)
  1465.  
  1466. ;void (deflate_state* s)
  1467. ;align 4
  1468. ;proc _tr_flush_bits, s:dword
  1469. ;       stdcall bi_flush, [s]
  1470. ;       ret
  1471. ;endp
  1472.  
  1473. _tr_flush_bits equ bi_flush
  1474.  
  1475. ; ===========================================================================
  1476. ; Send one empty static block to give enough lookahead for inflate.
  1477. ; This takes 10 bits, of which 7 may remain in the bit buffer.
  1478.  
  1479. ;void (deflate_state* s)
  1480. align 4
  1481. proc _tr_align uses edi, s:dword
  1482.         mov edi,[s]
  1483.         stdcall send_bits, edi, STATIC_TREES shl 1, 3
  1484.         send_code edi, END_BLOCK, static_ltree
  1485. if DEBUG eq 1
  1486.         add [edi+deflate_state.compressed_len],10 ;3 for block type, 7 for EOB
  1487. end if
  1488.         stdcall bi_flush, edi
  1489.         ret
  1490. endp
  1491.  
  1492. ; ===========================================================================
  1493. ; Determine the best encoding for the current block: dynamic trees, static
  1494. ; trees or store, and output the encoded block to the zip file.
  1495.  
  1496. ;void (s, buf, stored_len, last)
  1497. ;    deflate_state* s
  1498. ;    charf *buf     ;input block, or NULL if too old
  1499. ;    ulg stored_len ;length of input block
  1500. ;    int last       ;one if this is the last block for a file
  1501. align 4
  1502. proc _tr_flush_block uses eax ebx edi, s:dword, buf:dword, stored_len:dword, last:dword
  1503. locals
  1504.         opt_lenb dd ? ;ulg
  1505.         static_lenb dd ? ;opt_len and static_len in bytes
  1506.         max_blindex dd 0 ;int ;index of last bit length code of non zero freq
  1507. endl
  1508.         ; Build the Huffman trees unless a stored block is forced
  1509.         mov edi,[s]
  1510.         cmp word[edi+deflate_state.level],0
  1511.         jle .end0 ;if (..>0)
  1512.  
  1513.                 ; Check if the file is binary or text
  1514.                 mov ebx,[edi+deflate_state.strm]
  1515.                 cmp dword[ebx+z_stream.data_type],Z_UNKNOWN
  1516.                 jne @f ;if (..==..)
  1517.                         stdcall detect_data_type, edi
  1518.                         mov [ebx+z_stream.data_type],eax
  1519.                 @@:
  1520.  
  1521.                 ; Construct the literal and distance trees
  1522.                 mov eax,edi
  1523.                 add eax,deflate_state.l_desc
  1524.                 stdcall build_tree, edi, eax
  1525. ;        Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, s->static_len));
  1526.  
  1527.                 mov eax,edi
  1528.                 add eax,deflate_state.d_desc
  1529.                 stdcall build_tree, edi, eax
  1530. ;        Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, s->static_len));
  1531.                 ; At this point, opt_len and static_len are the total bit lengths of
  1532.                 ; the compressed block data, excluding the tree representations.
  1533.  
  1534.                 ; Build the bit length tree for the above two trees, and get the index
  1535.                 ; in bl_order of the last bit length code to send.
  1536.  
  1537.                 stdcall build_bl_tree, edi
  1538.                 mov [max_blindex],eax
  1539.  
  1540.                 ; Determine the best encoding. Compute the block lengths in bytes.
  1541.                 mov eax,[edi+deflate_state.opt_len]
  1542.                 add eax,3+7
  1543.                 shr eax,3
  1544.                 mov [opt_lenb],eax
  1545.                 mov eax,[edi+deflate_state.static_len]
  1546.                 add eax,3+7
  1547.                 shr eax,3
  1548.                 mov [static_lenb],eax
  1549.  
  1550. ;        Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
  1551. ;                opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
  1552. ;                s->last_lit));
  1553.  
  1554.                 cmp eax,[opt_lenb]
  1555.                 ja .end1 ;if (..<=..)
  1556.                         mov [opt_lenb],eax
  1557.                 jmp .end1
  1558.         .end0: ;else
  1559.                 cmp dword[buf],0
  1560.                 jne @f
  1561.                         zlib_assert 'lost buf' ;Assert(..!=0)
  1562.                 @@:
  1563.                 mov eax,[stored_len]
  1564.                 add eax,5
  1565.                 mov [static_lenb],eax
  1566.                 mov [opt_lenb],eax ;force a stored block
  1567.         .end1:
  1568.  
  1569. if FORCE_STORED eq 1
  1570.         cmp dword[buf],0
  1571.         je .end2 ;if (..!=0) ;force stored block
  1572. else
  1573.         mov eax,[stored_len]
  1574.         add eax,4
  1575.         cmp eax,[opt_lenb]
  1576.         ja .end2
  1577.         cmp dword[buf],0
  1578.         je .end2 ;if (..<=.. && ..!=0)
  1579.                 ;4: two words for the lengths
  1580. end if
  1581.                 ; The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
  1582.                 ; Otherwise we can't have processed more than WSIZE input bytes since
  1583.                 ; the last block flush, because compression would have been
  1584.                 ; successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
  1585.                 ; transform a block into a stored block.
  1586.  
  1587.                 stdcall _tr_stored_block, edi, [buf], [stored_len], [last]
  1588.                 jmp .end4
  1589.         .end2:
  1590. if FORCE_STATIC eq 1
  1591.         cmp dword[static_lenb],0
  1592.         jl .end3 ;else if (..>=0) ;force static trees
  1593. else
  1594.         cmp word[edi+deflate_state.strategy],Z_FIXED
  1595.         je @f
  1596.         mov eax,[opt_lenb]
  1597.         cmp [static_lenb],eax
  1598.         je @f ;else if (..==.. || ..==..)
  1599.                 jmp .end3
  1600.         @@:
  1601. end if
  1602.                 mov eax,STATIC_TREES shl 1
  1603.                 add eax,[last]
  1604.                 stdcall send_bits, edi, eax, 3
  1605.                 stdcall compress_block, edi, static_ltree, static_dtree
  1606. if DEBUG eq 1
  1607.                 mov eax,[edi+deflate_state.static_len]
  1608.                 add eax,3
  1609.                 add [edi+deflate_state.compressed_len],eax
  1610. end if
  1611.                 jmp .end4
  1612.         .end3: ;else
  1613.                 mov eax,DYN_TREES shl 1
  1614.                 add eax,[last]
  1615.                 stdcall send_bits, edi, eax, 3
  1616.                 mov eax,[max_blindex]
  1617.                 inc eax
  1618.                 push eax
  1619.                 mov eax,[edi+deflate_state.d_desc.max_code]
  1620.                 inc eax
  1621.                 push eax
  1622.                 mov eax,[edi+deflate_state.l_desc.max_code]
  1623.                 inc eax
  1624.                 stdcall send_all_trees, edi, eax ;, ..., ...
  1625.                 mov eax,edi
  1626.                 add eax,deflate_state.dyn_dtree
  1627.                 push eax
  1628.                 add eax,deflate_state.dyn_ltree-deflate_state.dyn_dtree
  1629.                 stdcall compress_block, edi, eax ;, ...
  1630. if DEBUG eq 1
  1631.                 mov eax,[edi+deflate_state.opt_len]
  1632.                 add eax,3
  1633.                 add [edi+deflate_state.compressed_len],eax
  1634. end if
  1635.         .end4:
  1636. ;    Assert (s->compressed_len == s->bits_sent, "bad compressed size");
  1637.         ; The above check is made mod 2^32, for files larger than 512 MB
  1638.         ; and uLong implemented on 32 bits.
  1639.  
  1640.         stdcall init_block,edi
  1641.  
  1642.         cmp dword[last],0
  1643.         je @f ;if (..)
  1644.                 stdcall bi_windup,edi
  1645. if DEBUG eq 1
  1646.                 add [edi+deflate_state.compressed_len],7 ;align on byte boundary
  1647. end if
  1648.         @@:
  1649. ;    Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
  1650. ;           s->compressed_len-7*last));
  1651.         ret
  1652. endp
  1653.  
  1654. ; ===========================================================================
  1655. ; Save the match info and tally the frequency counts. Return true if
  1656. ; the current block must be flushed.
  1657.  
  1658. ;int (s, dist, lc)
  1659. ;    deflate_state* s
  1660. ;    unsigned dist ;distance of matched string
  1661. ;    unsigned lc   ;match length-MIN_MATCH or unmatched char (if dist==0)
  1662. align 4
  1663. proc _tr_tally uses ebx edi, s:dword, dist:dword, lc:dword
  1664.         mov edi,[s]
  1665.         mov eax,[edi+deflate_state.last_lit]
  1666.         shl eax,1
  1667.         add eax,[edi+deflate_state.d_buf]
  1668.         mov ebx,[dist]
  1669.         mov word[eax],bx
  1670.         mov eax,[edi+deflate_state.last_lit]
  1671.         add eax,[edi+deflate_state.l_buf]
  1672.         mov ebx,[lc]
  1673.         mov byte[eax],bl
  1674.         inc dword[edi+deflate_state.last_lit]
  1675.         cmp dword[dist],0
  1676.         jne @f ;if (..==0)
  1677.                 ; lc is the unmatched char
  1678.                 mov eax,[lc]
  1679.                 inc word[edi+sizeof.ct_data*eax+deflate_state.dyn_ltree+Freq]
  1680.                 jmp .end0
  1681. align 4
  1682.         @@: ;else
  1683.                 inc dword[edi+deflate_state.matches]
  1684.                 ; Here, lc is the match length - MIN_MATCH
  1685.                 dec dword[dist] ;dist = match distance - 1
  1686.                 MAX_DIST edi
  1687.                 cmp word[dist],ax
  1688.                 jge @f
  1689.                 cmp word[lc],MAX_MATCH-MIN_MATCH
  1690.                 jg @f
  1691.                 d_code [dist]
  1692.                 cmp ax,D_CODES
  1693.                 jl .end2
  1694.                 @@:
  1695.                         zlib_assert '_tr_tally: bad match' ;Assert(..<.. && ..<=.. && ..<..)
  1696.                 .end2:
  1697.                 mov eax,[lc]
  1698.                 movzx eax,byte[eax+_length_code]
  1699.                 inc word[edi+sizeof.ct_data*eax+deflate_state.dyn_ltree+sizeof.ct_data*(LITERALS+1)+Freq]
  1700.                 d_code [dist]
  1701.                 inc word[edi+sizeof.ct_data*eax+deflate_state.dyn_dtree+Freq]
  1702.         .end0:
  1703.  
  1704. if TRUNCATE_BLOCK eq 1
  1705.         ; Try to guess if it is profitable to stop the current block here
  1706.         mov eax,[edi+deflate_state.last_lit]
  1707.         and eax,0x1fff
  1708.         jnz .end1
  1709.         cmp word[edi+deflate_state.level],2
  1710.         jle .end1 ;if (..==0 && ..>..)
  1711.         ; Compute an upper bound for the compressed length
  1712. ;        ulg out_length = (ulg)s->last_lit*8L;
  1713. ;        ulg in_length = (ulg)((long)s->strstart - s->block_start);
  1714. ;        int dcode;
  1715. ;        for (dcode = 0; dcode < D_CODES; dcode++) {
  1716. ;            out_length += (ulg)s->dyn_dtree[dcode].Freq *
  1717. ;                (5L+extra_dbits[dcode]);
  1718. ;        }
  1719. ;        out_length >>= 3;
  1720. ;        Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
  1721. ;               s->last_lit, in_length, out_length,
  1722. ;               100L - out_length*100L/in_length));
  1723. ;        if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
  1724.         .end1:
  1725. end if
  1726.         mov ebx,[edi+deflate_state.lit_bufsize]
  1727.         dec ebx
  1728.         xor eax,eax
  1729.         cmp [edi+deflate_state.last_lit],ebx
  1730.         sete al ;return (..==..)
  1731.  
  1732.         ; We avoid equality with lit_bufsize because of wraparound at 64K
  1733.         ; on 16 bit machines and because stored blocks are restricted to
  1734.         ; 64K-1 bytes.
  1735.         ret
  1736. endp
  1737.  
  1738. ; ===========================================================================
  1739. ; Send the block data compressed using the given Huffman trees
  1740.  
  1741. ;void (s, ltree, dtree)
  1742. ;    deflate_state* s
  1743. ;    ct_data *ltree ;literal tree
  1744. ;    ct_data *dtree ;distance tree
  1745. align 4
  1746. proc compress_block uses eax edi, s:dword, ltree:dword, dtree:dword
  1747. locals
  1748.         dist  dd ? ;unsigned ;distance of matched string
  1749.         lc    dd ? ;int      ;match length or unmatched char (if dist == 0)
  1750.         lx    dd 0 ;unsigned ;running index in l_buf
  1751.         u_code dd ? ;unsigned ;the code to send
  1752. endl
  1753.         mov edi,[s]
  1754.         cmp dword[edi+deflate_state.last_lit],0
  1755.         je .end0 ;if (..!=0)
  1756.         .cycle0: ; do
  1757.                 mov eax,[lx]
  1758.                 shl eax,1
  1759.                 add eax,[edi+deflate_state.d_buf]
  1760.                 movzx eax,word[eax]
  1761.                 mov [dist],eax
  1762.                 mov eax,[lx]
  1763.                 add eax,[edi+deflate_state.l_buf]
  1764.                 movzx eax,byte[eax]
  1765.                 mov [lc],eax
  1766.                 inc dword[lx]
  1767.                 cmp dword[dist],0
  1768.                 jne @f ;if (..==0)
  1769.                         send_code edi, [lc], [ltree] ;send a literal byte
  1770. ;            Tracecv(isgraph(lc), (stderr," '%c' ", lc));
  1771.                         jmp .end1
  1772.                 @@: ;else
  1773.                         ; Here, lc is the match length - MIN_MATCH
  1774.                         mov eax,[lc]
  1775.                         add eax,_length_code
  1776.                         movzx eax,byte[eax]
  1777.                         mov [u_code],eax
  1778.                         add eax,LITERALS+1
  1779.                         send_code edi, eax, [ltree] ;send the length code
  1780.                         mov eax,[u_code]
  1781.                         mov eax,[4*eax+extra_lbits]
  1782.                         test eax,eax
  1783.                         jz @f ;if (..!=0)
  1784.                                 push eax ;extra
  1785.                                 mov eax,[u_code]
  1786.                                 mov eax,[4*eax+base_length]
  1787.                                 sub [lc],eax
  1788.                                 stdcall send_bits, edi, [lc] ;, ... ;send the extra length bits
  1789.                         @@:
  1790.                         dec dword[dist] ;dist is now the match distance - 1
  1791.                         d_code [dist]
  1792.                         mov [u_code],eax
  1793.                         cmp eax,D_CODES
  1794.                         jl @f
  1795.                                 zlib_assert 'bad d_code' ;Assert(..<..)
  1796.                         @@:
  1797.                         send_code edi, [u_code], [dtree] ;send the distance code
  1798.                         mov eax,[u_code]
  1799.                         mov eax,[4*eax+extra_dbits]
  1800.                         test eax,eax
  1801.                         jz .end1 ;if (..!=0)
  1802.                                 push eax ;extra
  1803.                                 mov eax,[u_code]
  1804.                                 mov eax,[4*eax+base_dist]
  1805.                                 sub [dist],eax
  1806.                                 stdcall send_bits, edi, [dist] ;, ... ;send the extra distance bits
  1807.                 .end1: ;literal or match pair ?
  1808.  
  1809.                 ; Check that the overlay between pending_buf and d_buf+l_buf is ok:
  1810.                 mov eax,[lx]
  1811.                 shl eax,1
  1812.                 add eax,[edi+deflate_state.lit_bufsize]
  1813.                 cmp [edi+deflate_state.pending],eax
  1814.                 jl @f
  1815.                         zlib_assert 'pendingBuf overflow' ;Assert(..<..)
  1816.                 @@:
  1817.                 mov eax,[edi+deflate_state.last_lit]
  1818.                 cmp [lx],eax
  1819.                 jb .cycle0 ;while (..<..)
  1820. align 4
  1821.         .end0:
  1822.  
  1823.         send_code edi, END_BLOCK, [ltree]
  1824.         ret
  1825. endp
  1826.  
  1827. ; ===========================================================================
  1828. ; Check if the data type is TEXT or BINARY, using the following algorithm:
  1829. ; - TEXT if the two conditions below are satisfied:
  1830. ;    a) There are no non-portable control characters belonging to the
  1831. ;       "black list" (0..6, 14..25, 28..31).
  1832. ;    b) There is at least one printable character belonging to the
  1833. ;       "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
  1834. ; - BINARY otherwise.
  1835. ; - The following partially-portable control characters form a
  1836. ;   "gray list" that is ignored in this detection algorithm:
  1837. ;   (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
  1838. ; IN assertion: the fields Freq of dyn_ltree are set.
  1839.  
  1840. ;int (deflate_state* s)
  1841. align 4
  1842. proc detect_data_type uses ebx ecx edi, s:dword
  1843.         ; black_mask is the bit mask of black-listed bytes
  1844.         ; set bits 0..6, 14..25, and 28..31
  1845.         ; 0xf3ffc07f = binary 11110011111111111100000001111111
  1846. locals
  1847.         black_mask dd 0xf3ffc07f
  1848. endl
  1849.         mov edi,[s]
  1850.  
  1851.         ; Check for non-textual ("black-listed") bytes.
  1852.         xor ecx,ecx
  1853.         mov ebx,edi
  1854.         add ebx,deflate_state.dyn_ltree+Freq
  1855.         .cycle0:
  1856.         cmp ecx,31
  1857.         jg .cycle0end ;for (..;..<=..;..,..)
  1858.                 bt dword[black_mask],0
  1859.                 jnc @f
  1860.                 cmp word[ebx],0
  1861.                 je @f ;if (..&.. && ..!=0)
  1862.                         mov eax,Z_BINARY
  1863.                         jmp .end_f
  1864.                 @@:
  1865.                 shr dword[black_mask],1
  1866.                 add ebx,sizeof.ct_data
  1867.                 inc ecx
  1868.                 jmp .cycle0
  1869.         .cycle0end:
  1870.  
  1871.         ; Check for textual ("white-listed") bytes.
  1872.         mov ebx,edi
  1873.         add ebx,deflate_state.dyn_ltree+Freq+9*sizeof.ct_data
  1874.         cmp word[ebx],0
  1875.         jne @f
  1876.         add ebx,sizeof.ct_data
  1877.         cmp word[ebx],0
  1878.         jne @f
  1879.         add ebx,3*sizeof.ct_data
  1880.         cmp word[ebx],0
  1881.         je .end0
  1882.         @@: ;if (..!=0 || ..!=0 || ..!= 0)
  1883.                 mov eax,Z_TEXT
  1884.                 jmp .end_f
  1885.         .end0:
  1886.         mov ecx,32
  1887.         mov ebx,edi
  1888.         add ebx,deflate_state.dyn_ltree+Freq+32*sizeof.ct_data
  1889.         .cycle1:
  1890.         cmp ecx,LITERALS
  1891.         jge .cycle1end ;for (..;..<..;..,..)
  1892.                 cmp word[ebx],0
  1893.                 je @f ;if (..!=0)
  1894.                         mov eax,Z_TEXT
  1895.                         jmp .end_f
  1896.                 @@:
  1897.                 add ebx,sizeof.ct_data
  1898.                 inc ecx
  1899.                 jmp .cycle1
  1900.         .cycle1end:
  1901.  
  1902.         ; There are no "black-listed" or "white-listed" bytes:
  1903.         ; this stream either is empty or has tolerated ("gray-listed") bytes only.
  1904.  
  1905.         mov eax,Z_BINARY
  1906. .end_f:
  1907.         ret
  1908. endp
  1909.  
  1910. ; ===========================================================================
  1911. ; Reverse the first len bits of a code, using straightforward code (a faster
  1912. ; method would use a table)
  1913. ; IN assertion: 1 <= len <= 15
  1914.  
  1915. ;unsigned (code, len)
  1916. ;    unsigned code ;the value to invert
  1917. ;    int len       ;its bit length
  1918. align 4
  1919. proc bi_reverse uses ebx, p1code:dword, len:dword
  1920.         xor eax,eax
  1921.         @@: ;do
  1922.                 mov ebx,[p1code]
  1923.                 and ebx,1
  1924.                 or eax,ebx
  1925.                 shr dword[p1code],1
  1926.                 shl eax,1
  1927.                 dec dword[len]
  1928.                 cmp dword[len],0
  1929.                 jg @b ;while (..>..)
  1930.         shr eax,1
  1931.         ret
  1932. endp
  1933.  
  1934. ; ===========================================================================
  1935. ; Flush the bit buffer, keeping at most 7 bits in it.
  1936.  
  1937. ;void (deflate_state* s)
  1938. align 4
  1939. proc bi_flush uses eax ecx edi, s:dword
  1940.         mov edi,[s]
  1941.         cmp dword[edi+deflate_state.bi_valid],16
  1942.         jne @f ;if (..==..)
  1943.                 mov cx,[edi+deflate_state.bi_buf]
  1944.                 put_short edi,cx
  1945.                 mov word[edi+deflate_state.bi_buf],0
  1946.                 mov dword[edi+deflate_state.bi_valid],0
  1947.                 jmp .end0
  1948.         @@: ;else if (..>=..)
  1949.                 cmp dword[edi+deflate_state.bi_valid],8
  1950.                 jl .end0
  1951.                 mov cl,byte[edi+deflate_state.bi_buf]
  1952.                 put_byte edi,cl
  1953.                 shr word[edi+deflate_state.bi_buf],8
  1954.                 sub dword[edi+deflate_state.bi_valid],8
  1955.         .end0:
  1956.         ret
  1957. endp
  1958.  
  1959. ; ===========================================================================
  1960. ; Flush the bit buffer and align the output on a byte boundary
  1961.  
  1962. ;void (deflate_state* s)
  1963. align 4
  1964. proc bi_windup uses eax ecx edi, s:dword
  1965.         mov edi,[s]
  1966.         cmp dword[edi+deflate_state.bi_valid],8
  1967.         jle @f ;if (..>..)
  1968.                 mov cx,[edi+deflate_state.bi_buf]
  1969.                 put_short edi, cx
  1970.                 jmp .end0
  1971.         @@: ;else if (..>0)
  1972.                 cmp dword[edi+deflate_state.bi_valid],0
  1973.                 jle .end0
  1974.                 mov cl,byte[edi+deflate_state.bi_buf]
  1975.                 put_byte edi, cl
  1976.         .end0:
  1977.         mov word[edi+deflate_state.bi_buf],0
  1978.         mov dword[edi+deflate_state.bi_valid],0
  1979. if DEBUG eq 1
  1980.         mov eax,[edi+deflate_state.bits_sent]
  1981.         add eax,7
  1982.         and eax,not 7
  1983.         mov [edi+deflate_state.bits_sent],eax
  1984. end if
  1985.         ret
  1986. endp
  1987.  
  1988. ; ===========================================================================
  1989. ; Copy a stored block, storing first the length and its
  1990. ; one's complement if requested.
  1991.  
  1992. ;void (s, buf, len, header)
  1993. ;    deflate_state* s
  1994. ;    charf    *buf   ;the input data
  1995. ;    unsigned len    ;its length
  1996. ;    int      header ;true if block header must be written
  1997. align 4
  1998. proc copy_block uses eax ebx ecx edi esi, s:dword, buf:dword, len:dword, p4header:dword
  1999.         mov edi,[s]
  2000.         stdcall bi_windup,edi ;align on byte boundary
  2001.  
  2002.         cmp dword[p4header],0
  2003.         je @f ;if (..)
  2004.                 mov ecx,[len]
  2005.                 put_short edi, cx
  2006.                 not cx
  2007.                 put_short edi, cx
  2008. if DEBUG eq 1
  2009.                 add dword[edi+deflate_state.bits_sent],2*16
  2010. end if
  2011.         @@:
  2012. if DEBUG eq 1
  2013.         mov ecx,[len]
  2014.         shl ecx,3
  2015.         add [edi+deflate_state.bits_sent],ecx
  2016. end if
  2017.         mov ecx,[len]
  2018. ;       test ecx,ecx
  2019. ;       jz .end_f
  2020.         mov esi,[buf]
  2021.         jmp .end0
  2022. align 4
  2023.         @@: ;while (len--)
  2024.                 lodsb
  2025.                 mov bl,al
  2026.                 put_byte edi, bl
  2027.         .end0:
  2028.                 loop @b
  2029. ;       .end_f:
  2030.         ret
  2031. endp
  2032.