Subversion Repositories Kolibri OS

; trees.asm -- output deflated data using Huffman coding

; Copyright (C) 1995-2012 Jean-loup Gailly

; detect_data_type() function provided freely by Cosmin Truta, 2006

; For conditions of distribution and use, see copyright notice in zlib.h

;  ALGORITHM

;      The "deflation" process uses several Huffman trees. The more

;      common source values are represented by shorter bit sequences.

;      Each code tree is stored in a compressed form which is itself

; a Huffman encoding of the lengths of all the code strings (in

; ascending order by source values).  The actual code strings are

; reconstructed from the lengths in the inflate process, as described

; in the deflate specification.

;  REFERENCES

;      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".

;      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc

;      Storer, James A.

;          Data Compression:  Methods and Theory, pp. 49-50.

;          Computer Science Press, 1988.  ISBN 0-7167-8156-5.

;      Sedgewick, R.

;          Algorithms, p290.

;          Addison-Wesley, 1983. ISBN 0-201-06672-6.

; ===========================================================================

; Constants

MAX_BL_BITS equ 7

; Bit length codes must not exceed MAX_BL_BITS bits

END_BLOCK equ 256

; end of block literal code

REP_3_6     equ 16

; repeat previous bit length 3-6 times (2 bits of repeat count)

REPZ_3_10   equ 17

; repeat a zero length 3-10 times  (3 bits of repeat count)

REPZ_11_138 equ 18

; repeat a zero length 11-138 times  (7 bits of repeat count)

align 4

extra_lbits dd \ ;int [LENGTH_CODES] ;extra bits for each length code

	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

align 4

extra_dbits dd \ ;int [D_CODES] ;extra bits for each distance code

	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

align 4

extra_blbits dd \ ;int [BL_CODES] ;extra bits for each bit length code

	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7

align 4

bl_order db 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15

; The lengths of the bit length codes are sent in order of decreasing

; probability, to avoid transmitting the lengths for unused bit length codes.

; ===========================================================================

; Local data. These are initialized only once.

DIST_CODE_LEN equ 512 ;see definition of array dist_code below

if GEN_TREES_H eq 1 ;| !(STDC)

; non ANSI compilers may not accept trees.inc

align 4

static_ltree rb sizeof.ct_data * (L_CODES+2)

; The static literal tree. Since the bit lengths are imposed, there is no

; need for the L_CODES extra codes used during heap construction. However

; The codes 286 and 287 are needed to build a canonical tree (see _tr_init

; below).

align 4

static_dtree rb sizeof.ct_data * D_CODES

; The static distance tree. (Actually a trivial tree since all codes use

; 5 bits.)

align 4

_dist_code rb DIST_CODE_LEN ;uch[]

; Distance codes. The first 256 values correspond to the distances

; 3 .. 258, the last 256 values correspond to the top 8 bits of

; the 15 bit distances.

align 4

_length_code rb MAX_MATCH-MIN_MATCH+1 ;uch[]

; length code for each normalized match length (0 == MIN_MATCH)

align 4

base_length rd LENGTH_CODES ;int[]

; First normalized length for each code (0 = MIN_MATCH)

align 4

base_dist rd D_CODES ;int[]

; First normalized distance for each code (0 = distance of 1)

else

include 'trees.inc'

end if ;GEN_TREES_H

struct static_tree_desc ;_s

	static_tree dd ? ;const ct_data * ;static tree or NULL

	extra_bits  dd ? ;const intf * ;extra bits for each code or NULL

	extra_base  dd ? ;int ;base index for extra_bits

	elems       dd ? ;int ;max number of elements in the tree

	max_length  dd ? ;int ;max bit length for the codes

ends

align 4

static_l_desc static_tree_desc static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS

align 4

static_d_desc static_tree_desc static_dtree, extra_dbits, 0, D_CODES, MAX_BITS

align 4

static_bl_desc static_tree_desc 0, extra_blbits, 0, BL_CODES, MAX_BL_BITS

; ===========================================================================

; Local (static) routines in this file.

macro send_code s, c, tree

{

if DEBUG eq 1

;	if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c))

end if

push eax ebx

if c eq eax

else

	mov eax,c

end if

	imul eax,sizeof.ct_data

	add eax,tree

	movzx ebx,word[eax+Len]

	push ebx

	movzx ebx,word[eax+Code]

	push ebx

	stdcall send_bits, s ;tree[c].Code, tree[c].Len

pop ebx eax

}

; Send a code of the given tree[c] and tree must not have side effects

; ===========================================================================

; Output a short LSB first on the stream.

; IN assertion: there is enough room in pendingBuf.

macro put_short s, w

{

	mov eax,[s+deflate_state.pending]

	add eax,[s+deflate_state.pending_buf]

	mov word[eax],w

	add dword[s+deflate_state.pending],2

}

; ===========================================================================

; Send a value on a given number of bits.

; IN assertion: length <= 16 and value fits in length bits.

;void (s, value, length)

;    deflate_state* s

;    int value  ;value to send

;    int length ;number of bits

align 4

proc send_bits uses eax ecx edi, s:dword, value:dword, length:dword

;    Tracevv((stderr," l %2d v %4x ", length, value));

	zlib_debug 'send_bits value = %d',[value]

;if DEBUG eq 1

	mov eax,[length]

	cmp eax,0

	jle @f

	cmp eax,15

	jle .end1

	@@:

		zlib_assert 'invalid length' ;Assert(..>0 && ..<=15)

	.end1:

	mov edi,[s]

	add [edi+deflate_state.bits_sent],eax

	; If not enough room in bi_buf, use (valid) bits from bi_buf and

	; (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))

	; unused bits in value.

	mov ecx,Buf_size

	sub ecx,eax

	cmp [edi+deflate_state.bi_valid],ecx

	jle @f ;if (..>..)

		mov eax,[value]

		mov ecx,[edi+deflate_state.bi_valid]

		shl eax,cl

		or [edi+deflate_state.bi_buf],ax

		mov cx,[edi+deflate_state.bi_buf]

		put_short edi, cx

		mov eax,[value]

		mov ecx,Buf_size

		sub ecx,[edi+deflate_state.bi_valid]

		shr eax,cl

		mov [edi+deflate_state.bi_buf],ax

		mov eax,[length]

		sub eax,Buf_size

		jmp .end0

	@@: ;else

		mov eax,[value]

		mov ecx,[edi+deflate_state.bi_valid]

		shl eax,cl

		or [edi+deflate_state.bi_buf],ax

		mov eax,[length]

	.end0:

	add [edi+deflate_state.bi_valid],eax

;else ;!DEBUG

;{ int len = length;

;  if (s->bi_valid > (int)Buf_size - len) {

;    int val = value;

;    s->bi_buf |= (uint_16)val << s->bi_valid;

;    put_short(s, s->bi_buf);

;    s->bi_buf = (uint_16)val >> (Buf_size - s->bi_valid);

;    s->bi_valid += len - Buf_size;

;  } else {

;    s->bi_buf |= (uint_16)(value) << s->bi_valid;

;    s->bi_valid += len;

;  }

;}

;end if ;DEBUG

	ret

endp

; the arguments must not have side effects

; ===========================================================================

; Initialize the various 'constant' tables.

;int static_init_done = 0

;void ()

align 4

proc tr_static_init

if GEN_TREES_H eq 1

;    int n      ;iterates over tree elements

;    int bits   ;bit counter

;    int length ;length value

;    int code   ;code value

;    int dist   ;distance index

;    uint_16 bl_count[MAX_BITS+1];

	; number of codes at each bit length for an optimal tree

;    if (static_init_done) return;

	; For some embedded targets, global variables are not initialized:

;if NO_INIT_GLOBAL_POINTERS

;    static_l_desc.static_tree = static_ltree;

;    static_l_desc.extra_bits = extra_lbits;

;    static_d_desc.static_tree = static_dtree;

;    static_d_desc.extra_bits = extra_dbits;

;    static_bl_desc.extra_bits = extra_blbits;

;end if

	; Initialize the mapping length (0..255) -> length code (0..28)

;    length = 0;

;    for (code = 0; code < LENGTH_CODES-1; code++) {

;        base_length[code] = length;

;        for (n = 0; n < (1<

;            _length_code[length++] = (uch)code;

;        }

;    }

;    Assert (length == 256, "tr_static_init: length != 256");

	; Note that the length 255 (match length 258) can be represented

	; in two different ways: code 284 + 5 bits or code 285, so we

	; overwrite length_code[255] to use the best encoding:

;    _length_code[length-1] = (uch)code;

	; Initialize the mapping dist (0..32K) -> dist code (0..29)

;    dist = 0;

;    for (code = 0 ; code < 16; code++) {

;        base_dist[code] = dist;

;        for (n = 0; n < (1<

;            _dist_code[dist++] = (uch)code;

;        }

;    }

;    Assert (dist == 256, "tr_static_init: dist != 256");

;    dist >>= 7; /* from now on, all distances are divided by 128 */

;    for ( ; code < D_CODES; code++) {

;        base_dist[code] = dist << 7;

;        for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {

;            _dist_code[256 + dist++] = (uch)code;

;        }

;    }

;    Assert (dist == 256, "tr_static_init: 256+dist != 512");

	; Construct the codes of the static literal tree

;    for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;

;    n = 0;

;    while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;

;    while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;

;    while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;

;    while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;

	; Codes 286 and 287 do not exist, but we must include them in the

	; tree construction to get a canonical Huffman tree (longest code

	; all ones)

;    gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);

	; The static distance tree is trivial:

;    for (n = 0; n < D_CODES; n++) {

;        static_dtree[n].Len = 5;

;        static_dtree[n].Code = bi_reverse((unsigned)n, 5);

;    }

;    static_init_done = 1;

if GEN_TREES_H eq 1

	call gen_trees_header

end if

end if ;(GEN_TREES_H) | !(STDC)

	ret

endp

; ===========================================================================

; Genererate the file trees.h describing the static trees.

;#  define SEPARATOR(i, last, width) \

;      ((i) == (last)? "\n};\n\n" :    \

;       ((i) % (width) == (width)-1 ? ",\n" : ", "))

;void ()

align 4

proc gen_trees_header

;    FILE *header = fopen("trees.inc", "w");

;    int i;

;    Assert (header != NULL, "Can't open trees.inc");

;    fprintf(header,

;            "/* header created automatically with -DGEN_TREES_H */\n\n");

;    fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");

;    for (i = 0; i < L_CODES+2; i++) {

;        fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,

;                static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));

;    }

;    fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");

;    for (i = 0; i < D_CODES; i++) {

;        fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,

;                static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));

;    }

;    fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");

;    for (i = 0; i < DIST_CODE_LEN; i++) {

;        fprintf(header, "%2u%s", _dist_code[i],

;                SEPARATOR(i, DIST_CODE_LEN-1, 20));

;    }

;    fprintf(header,

;        "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");

;    for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {

;        fprintf(header, "%2u%s", _length_code[i],

;                SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));

;    }

;    fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");

;    for (i = 0; i < LENGTH_CODES; i++) {

;        fprintf(header, "%1u%s", base_length[i],

;                SEPARATOR(i, LENGTH_CODES-1, 20));

;    }

;    fprintf(header, "local const int base_dist[D_CODES] = {\n");

;    for (i = 0; i < D_CODES; i++) {

;        fprintf(header, "%5u%s", base_dist[i],

;                SEPARATOR(i, D_CODES-1, 10));

;    }

;    fclose(header);

	ret

endp

; ===========================================================================

; Initialize the tree data structures for a new zlib stream.

;void (s)

;    deflate_state* s

align 4

proc _tr_init uses eax edi, s:dword

	mov edi,[s]

	zlib_debug '_tr_init'

	call tr_static_init

	mov eax,edi

	add eax,deflate_state.dyn_ltree

	mov [edi+deflate_state.l_desc.dyn_tree],eax

	mov [edi+deflate_state.l_desc.stat_desc],static_l_desc

	add eax,deflate_state.dyn_dtree-deflate_state.dyn_ltree

	mov [edi+deflate_state.d_desc.dyn_tree],eax

	mov [edi+deflate_state.d_desc.stat_desc],static_d_desc

	add eax,deflate_state.bl_tree-deflate_state.dyn_dtree

	mov [edi+deflate_state.bl_desc.dyn_tree],eax

	mov [edi+deflate_state.bl_desc.stat_desc],static_bl_desc;

	mov word[edi+deflate_state.bi_buf],0

	mov dword[edi+deflate_state.bi_valid],0

if DEBUG eq 1

	mov dword[edi+deflate_state.compressed_len],0

	mov dword[edi+deflate_state.bits_sent],0

end if

	; Initialize the first block of the first file:

	stdcall init_block,edi

	ret

endp

; ===========================================================================

; Initialize a new block.

;void (s)

;    deflate_state* s

align 4

proc init_block uses eax ecx edi, s:dword

	mov edi,[s]

	; Initialize the trees.

	mov eax,edi

	add eax,deflate_state.dyn_ltree+Freq

	mov ecx,L_CODES

	@@:

		mov word[eax],0

		add eax,sizeof.ct_data

		loop @b

	mov eax,edi

	add eax,deflate_state.dyn_dtree+Freq

	mov ecx,D_CODES

	@@:

		mov word[eax],0

		add eax,sizeof.ct_data

		loop @b

	mov eax,edi

	add eax,deflate_state.bl_tree+Freq

	mov ecx,BL_CODES

	@@:

		mov word[eax],0

		add eax,sizeof.ct_data

		loop @b

	mov word[edi+sizeof.ct_data*END_BLOCK+deflate_state.dyn_ltree+Freq],1

	mov dword[edi+deflate_state.static_len],0

	mov dword[edi+deflate_state.opt_len],0

	mov dword[edi+deflate_state.matches],0

	mov dword[edi+deflate_state.last_lit],0

	ret

endp

SMALLEST equ 1

; Index within the heap array of least frequent node in the Huffman tree

; ===========================================================================

; Remove the smallest element from the heap and recreate the heap with

; one less element. Updates heap and heap_len.

macro pqremove s, tree, top

{

	mov eax,s

	add eax,deflate_state.heap+2*SMALLEST

	movzx top,word[eax]

push ebx

	mov ebx,[s+deflate_state.heap_len]

	mov bx,[s+deflate_state.heap+2*ebx]

	mov word[eax],bx

	dec dword[s+deflate_state.heap_len]

pop ebx

	stdcall pqdownheap, s, tree, SMALLEST

}

; ===========================================================================

; Compares to subtrees, using the tree depth as tie breaker when

; the subtrees have equal frequency. This minimizes the worst case length.

macro smaller tree, n, m, depth, m_end

{

;if (..<.. || (..==.. && depth[n] <= depth[m]))

local .end0

	movzx eax,n

	imul eax,sizeof.ct_data

	add eax,tree

	mov ax,word[eax+Freq]

	movzx ebx,m

	imul ebx,sizeof.ct_data

	add ebx,tree

	mov bx,word[ebx+Freq]

	cmp ax,bx

	jl .end0

	jne m_end

	movzx eax,n

	add eax,depth

	mov al,byte[eax]

	movzx ebx,m

	add ebx,depth

	mov bl,byte[ebx]

	cmp al,bl

	jg m_end

	.end0:

}

; ===========================================================================

; Restore the heap property by moving down the tree starting at node k,

; exchanging a node with the smallest of its two sons if necessary, stopping

; when the heap property is re-established (each father smaller than its

; two sons).

;void (s, tree, k)

;    deflate_state* s

;    ct_data* tree ;the tree to restore

;    int      k    ;node to move down

align 4

proc pqdownheap, s:dword, tree:dword, k:dword

locals

	v dw ?

endl

pushad

	mov edi,[s]

	mov eax,[k]

	zlib_debug 'pqdownheap k = %d',eax

	mov esi,eax

	shl esi,1

	mov ax,[edi+deflate_state.heap+2*eax]

	mov [v],ax

	;esi = j ;left son of k

	.cycle0: ;while (..<=..)

		cmp esi,[edi+deflate_state.heap_len]

		jg .cycle0end

		; Set j to the smallest of the two sons:

		;;cmp esi,[edi+deflate_state.heap_len]

		jge .end1 ;if (..<.. &&

		mov ecx,edi

		add ecx,deflate_state.depth

		mov edx,esi

		shl edx,1

		add edx,edi

		add edx,deflate_state.heap

		smaller [tree], word[edx+2], word[edx], ecx, .end1

			inc esi

		.end1:

		; Exit if v is smaller than both sons

		mov ecx,edi

		add ecx,deflate_state.depth

		mov dx,[edi+deflate_state.heap+2*esi]

		smaller [tree], [v], dx, ecx, .end2

			jmp .cycle0end ;break

		.end2:

		; Exchange v with the smallest son

		mov dx,[edi+deflate_state.heap+2*esi]

		mov eax,[k]

		mov [edi+deflate_state.heap+2*eax],dx

		mov [k],esi

		; And continue down the tree, setting j to the left son of k

		shl esi,1

		jmp .cycle0

	.cycle0end:

	mov eax,[k]

	mov bx,[v]

	mov [edi+deflate_state.heap+2*eax],bx

popad

	ret

endp

; ===========================================================================

; Compute the optimal bit lengths for a tree and update the total bit length

; for the current block.

; IN assertion: the fields freq and dad are set, heap[heap_max] and

;    above are the tree nodes sorted by increasing frequency.

; OUT assertions: the field len is set to the optimal bit length, the

;     array bl_count contains the frequencies for each bit length.

;     The length opt_len is updated; static_len is also updated if stree is

;     not null.

;void (s, desc)

;    deflate_state* s

;    tree_desc* desc ;the tree descriptor

align 4

proc gen_bitlen, s:dword, desc:dword

locals

	tree  dd ? ;ct_data* ;= desc.dyn_tree

	max_code dd ? ;int   ;= desc.max_code

	stree dd ? ;ct_data* ;= desc.stat_desc.static_tree

	extra dd ? ;intf*    ;= desc.stat_desc.extra_bits

	base  dd ? ;int      ;= desc.stat_desc.extra_base

	max_length dd ? ;int ;= desc.stat_desc.max_length

	h     dd ? ;int ;heap index

	m     dd ? ;int ;iterate over the tree elements

	bits  dd ? ;int ;bit length

	xbits dd ? ;int ;extra bits

	f     dw ? ;uint_16 ;frequency

	overflow dd 0 ;int ;number of elements with bit length too large

endl

pushad

	zlib_debug 'gen_bitlen'

	mov edi,[s]

	mov edx,[desc]

	mov eax,[edx+tree_desc.dyn_tree]

	mov [tree],eax

	mov eax,[edx+tree_desc.max_code]

	mov [max_code],eax

	mov ebx,[edx+tree_desc.stat_desc]

	mov eax,[ebx+static_tree_desc.static_tree]

	mov [stree],eax

	mov eax,[ebx+static_tree_desc.extra_bits]

	mov [extra],eax

	mov eax,[ebx+static_tree_desc.extra_base]

	mov [base],eax

	mov eax,[ebx+static_tree_desc.max_length]

	mov [max_length],eax

	xor ecx,ecx

	.cycle0:

	cmp ecx,MAX_BITS

	jg .cycle0end ;for (..;..<=..;..)

		mov word[edi+deflate_state.bl_count+2*ecx],0

		inc ecx

		jmp .cycle0

align 4

	.cycle0end:

	; In a first pass, compute the optimal bit lengths (which may

	; overflow in the case of the bit length tree).

	mov eax,[edi+deflate_state.heap_max]

	movzx eax,word[edi+deflate_state.heap+2*eax]

	imul eax,sizeof.ct_data

	add eax,[tree]

	mov word[eax+Len],0 ;root of the heap

	mov eax,[edi+deflate_state.heap_max]

	inc eax

	mov [h],eax

	.cycle1:

	cmp dword[h],HEAP_SIZE

	jge .cycle1end ;for (..;..<..;..)

		mov eax,[h]

		movzx ecx,word[edi+deflate_state.heap+2*eax]

		;ecx = n

		mov eax,sizeof.ct_data

		imul eax,ecx

		add eax,[tree]

		movzx eax,word[eax+Dad]

		imul eax,sizeof.ct_data

		add eax,[tree]

		movzx eax,word[eax+Len]

		inc eax

		mov [bits],eax ;bits = tree[tree[n].Dad].Len + 1

		mov eax,[max_length]

		cmp [bits],eax

		jle @f ;if (..>..)

			mov [bits],eax

			inc dword[overflow]

		@@:

		mov esi,[bits]

		mov eax,sizeof.ct_data

		imul eax,ecx

		add eax,[tree]

		mov word[eax+Len],si

		; We overwrite tree[n].Dad which is no longer needed

		cmp ecx,[max_code]

		jle @f

			inc dword[h]

			jmp .cycle1 ;if (..>..) continue ;not a leaf node

		@@:

		mov eax,[bits]

		shl eax,1 ;*= sizeof.uint_16

		inc word[eax+edi+deflate_state.bl_count]

		mov dword[xbits],0

		cmp ecx,[base]

		jl @f ;if (..>=..)

			mov eax,ecx

			sub eax,[base]

			shl eax,2 ;*= sizeof.dd

			add eax,[extra]

			mov eax,[eax]

			mov [xbits],eax

		@@:

		mov eax,sizeof.ct_data

		imul eax,ecx

		add eax,[tree]

		movzx eax,word[eax+Freq]

		mov [f],ax

		mov esi,[bits]

		add esi,[xbits]

		imul eax,esi

		add [edi+deflate_state.opt_len],eax

		cmp dword[stree],0

		je @f ;if (..)

			movzx eax,word[f]

			mov esi,sizeof.ct_data

			imul esi,ecx

			add esi,[tree]

			movzx esi,word[esi+Len]

			add esi,[xbits]

			imul eax,esi

			add [edi+deflate_state.static_len],eax

		@@:

		inc dword[h]

		jmp .cycle1

align 4

	.cycle1end:

	cmp dword[overflow],0

	je .end_f ;if (..==0) return

;    Trace((stderr,"\nbit length overflow\n"));

	; This happens for example on obj2 and pic of the Calgary corpus

	; Find the first bit length which could increase:

	.cycle2: ;do

		mov eax,[max_length]

		dec eax

		mov [bits],eax

		shl eax,1 ;*= sizeof.dw

		add eax,edi

		add eax,deflate_state.bl_count

		@@:

		cmp word[eax],0

		jne @f ;while (..==0) bits--

			dec dword[bits]

			sub eax,2

			jmp @b

		@@:

		dec word[eax]     ;move one leaf down the tree

		add word[eax+2],2 ;move one overflow item as its brother

		mov eax,[max_length]

		dec word[edi+deflate_state.bl_count+2*eax]

		; The brother of the overflow item also moves one step up,

		; but this does not affect bl_count[max_length]

		sub dword[overflow],2

		cmp dword[overflow],0

		jg .cycle2 ;while (..>0)

	; Now recompute all bit lengths, scanning in increasing frequency.

	; h is still equal to HEAP_SIZE. (It is simpler to reconstruct all

	; lengths instead of fixing only the wrong ones. This idea is taken

	; from 'ar' written by Haruhiko Okumura.)

	mov eax,[max_length]

	mov [bits],eax

	.cycle3:

	cmp dword[bits],0

	je .end_f ;for (..;..!=0;..)

		mov eax,[bits]

		shl eax,1 ;*= sizeof.dw

		movzx ecx,word[eax+edi+deflate_state.bl_count]

		.cycle4: ;while (..!=0)

		cmp ecx,0

		je .cycle4end

			dec dword[h]

			mov eax,[h]

			movzx eax,word[edi+deflate_state.heap+2*eax]

			mov [m],eax ;m = s.heap[--h]

			cmp eax,[max_code]

			jle @f ;if (..>..) continue

				dec ecx

				jmp .cycle4

			@@:

			mov esi,[m]

			imul esi,sizeof.ct_data

			add esi,[tree] ;esi = &tree[m]

			mov eax,[bits]

			cmp word[esi+Len],ax

			je @f ;if (..!=..)

;                Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));

				movzx ebx,word[esi+Len]

				sub eax,ebx

				movzx ebx,word[esi+Freq]

				imul eax,ebx ;eax = (bits - tree[m].Len) * tree[m].Freq

				add [edi+deflate_state.opt_len],eax

				mov eax,[bits]

				mov word[esi+Len],ax

			@@:

			dec ecx

			jmp .cycle4

		.cycle4end:

		dec dword[bits]

		jmp .cycle3

.end_f:

popad

	ret

endp

; ===========================================================================

; Generate the codes for a given tree and bit counts (which need not be

; optimal).

; IN assertion: the array bl_count contains the bit length statistics for

; the given tree and the field len is set for all tree elements.

; OUT assertion: the field code is set for all tree elements of non

;     zero code length.

;void (tree, max_code, bl_count)

;    ct_data *tree     ;the tree to decorate

;    int max_code      ;largest code with non zero frequency

;    uint_16p bl_count ;number of codes at each bit length

align 4

proc gen_codes uses eax ebx ecx edx edi, tree:dword, max_code:dword, bl_count:dword

locals

	u_code dw 0 ;uint_16 ;running code value

	bits   dd 1 ;int ;bit index

	next_code rw MAX_BITS+1 ;uint_16[] ;next code value for each bit length

endl

	; The distribution counts are first used to generate the code values

	; without bit reversal.

	zlib_debug 'gen_codes'

	mov ebx,ebp

	sub ebx,2*(MAX_BITS+1)

	.cycle0: ;for (..;..<=..;..)

	cmp dword[bits],MAX_BITS

	jg .cycle0end

		mov eax,[bits]

		dec eax

		shl eax,1

		add eax,[bl_count]

		mov ax,word[eax]

		add ax,[u_code]

		shl ax,1 ;ax = (u_code + bl_count[bits-1]) << 1

		mov [u_code],ax

		mov ecx,[bits]

		mov word[ebx+2*ecx],ax ;next_code[bits] = u_code

		inc dword[bits]

		jmp .cycle0

	.cycle0end:

	; Check that the bit counts in bl_count are consistent. The last code

	; must be all ones.

	mov eax,[bl_count]

	mov ax,word[eax+2*MAX_BITS]

	add ax,[u_code]

	dec ax

	cmp ax,(1 shl MAX_BITS)-1

	je @f

		zlib_assert 'inconsistent bit counts' ;Assert(..==..)

	@@:

;    Tracev((stderr,"\ngen_codes: max_code %d ", max_code));

	xor ecx,ecx ;n = 0

	.cycle1: ;for (..;..<=..;..)

	cmp ecx,[max_code]

	jg .cycle1end

		mov edx,sizeof.ct_data

		imul edx,ecx

		add edx,[tree] ;edx = &tree[n]

		movzx edi,word[edx+Len]

		cmp edi,0

		jne @f ;if (..==0) continue

			inc ecx

			jmp .cycle1

		@@:

		; Now reverse the bits

		movzx eax,word[ebx+2*edi]

		stdcall bi_reverse, eax, edi

		mov word[edx+Code],ax

		inc word[ebx+2*edi]

;        Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",

;             n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));

		inc ecx

		jmp .cycle1

	.cycle1end:

	ret

endp

; ===========================================================================

; Construct one Huffman tree and assigns the code bit strings and lengths.

; Update the total bit length for the current block.

; IN assertion: the field freq is set for all tree elements.

; OUT assertions: the fields len and code are set to the optimal bit length

;     and corresponding code. The length opt_len is updated; static_len is

;     also updated if stree is not null. The field max_code is set.

;void (s, desc)

;    deflate_state* s

;    tree_desc *desc ;the tree descriptor

align 4

proc build_tree uses eax ebx ecx edx edi, s:dword, desc:dword

locals

	tree     dd  ? ;ct_data* ;= desc.dyn_tree

	stree    dd  ? ;ct_data* ;= desc.stat_desc.static_tree

	elems    dd  ? ;int      ;= desc.stat_desc.elems

	m        dd  ? ;int ;iterate over heap elements

	max_code dd -1 ;int ;largest code with non zero frequency

	node     dd  ? ;int ;new node being created

endl

	; Construct the initial heap, with least frequent element in

	; heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].

	; heap[0] is not used.

	mov ebx,[desc]

	mov eax,[ebx+tree_desc.dyn_tree]

	mov [tree],eax

	mov ecx,[ebx+tree_desc.stat_desc]

	mov eax,[ecx+static_tree_desc.static_tree]

	mov [stree],eax

	mov ecx,[ecx+static_tree_desc.elems]

	mov [elems],ecx

	mov edi,[s]

	zlib_debug 'build_tree cycle0 ecx = %d',ecx

	mov dword[edi+deflate_state.heap_len],0

	mov dword[edi+deflate_state.heap_max],HEAP_SIZE

	cmp ecx,0

	jle .cycle0end

	xor edx,edx

	.cycle0: ;for (..;..<..;..)

		mov eax,edx

		imul eax,sizeof.ct_data

		add eax,[tree]

		cmp word[eax+Freq],0

		je @f ;if (..!=0)

			inc dword[edi+deflate_state.heap_len]

			mov eax,[edi+deflate_state.heap_len]

			mov [max_code],edx

			mov [edi+deflate_state.heap+2*eax],dx

			mov eax,edx

			add eax,edi

			add eax,deflate_state.depth

			mov byte[eax],0

			jmp .end0

align 4

		@@: ;else

			mov word[eax+Len],0

		.end0:

		inc edx

		loop .cycle0

align 4

	.cycle0end:

	; The pkzip format requires that at least one distance code exists,

	; and that at least one bit should be sent even if there is only one

	; possible code. So to avoid special checks later on we force at least

	; two codes of non zero frequency.

	.cycle1: ;while (..<..)

		cmp dword[edi+deflate_state.heap_len],2

		jge .cycle1end

		inc dword[edi+deflate_state.heap_len]

		xor eax,eax

		cmp dword[max_code],2

		jge @f

			inc dword[max_code]

			mov eax,[max_code]

		@@:

		mov ecx,[edi+deflate_state.heap_len]

		mov [edi+deflate_state.heap+2*ecx],ax

		mov [node],eax

		imul eax,sizeof.ct_data

		add eax,[tree]

		mov word[eax+Freq],1

		mov eax,[node]

		mov byte[edi+deflate_state.depth+eax],0

		dec dword[edi+deflate_state.opt_len]

		cmp dword[stree],0

		je .cycle1 ;if (..)

			mov eax,[node]

			imul eax,sizeof.ct_data

			add eax,[stree]

			movzx eax,word[eax+Len]

			sub [edi+deflate_state.static_len],eax

		; node is 0 or 1 so it does not have extra bits

		jmp .cycle1

align 4

	.cycle1end:

	mov eax,[max_code]

	mov [ebx+tree_desc.max_code],eax

	; The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,

	; establish sub-heaps of increasing lengths:

	mov ecx,[edi+deflate_state.heap_len]

	shr ecx,1

	.cycle2: ;for (..;..>=..;..)

		cmp ecx,1

		jl .cycle2end

		stdcall pqdownheap, edi, [tree], ecx

		dec ecx

		jmp .cycle2

align 4

	.cycle2end:

	; Construct the Huffman tree by repeatedly combining the least two

	; frequent nodes.

	mov eax,[elems]

	mov [node],eax ;next internal node of the tree

	.cycle3: ;do

		pqremove edi, [tree], ecx ;n = node of least frequency

		movzx edx,word[eax]

		mov [m],edx ;m = node of next least frequency

		mov eax,[edi+deflate_state.heap_max]

		dec eax

		mov [edi+deflate_state.heap+2*eax],cx ;keep the nodes sorted by frequency

		dec eax

		mov [edi+deflate_state.heap_max],eax

		mov [edi+deflate_state.heap+2*eax],dx

		; Create a new node father of n and m

		;;mov edx,[m]

		imul edx,sizeof.ct_data

		add edx,[tree]

		mov ax,word[edx+Freq]

		mov edx,ecx

		imul edx,sizeof.ct_data

		add edx,[tree]

		add ax,word[edx+Freq]

		mov edx,[node]

		imul edx,sizeof.ct_data

		add edx,[tree]

		mov word[edx+Freq],ax

		mov eax,ecx

		add eax,edi

		add eax,deflate_state.depth

		mov al,byte[eax]

		mov edx,[m]

		add edx,edi

		add edx,deflate_state.depth

		mov ah,byte[edx]

		cmp al,ah

		jl @f ;if (al>=ah) al=al : al=ah

			mov al,ah

		@@:

		inc al

		mov edx,[node]

		add edx,edi

		add edx,deflate_state.depth

		mov byte[edx],al

		mov eax,[node]

		mov edx,[m]

		imul edx,sizeof.ct_data

		add edx,[tree]

		mov [edx+Dad],ax

		mov edx,ecx

		imul edx,sizeof.ct_data

		add edx,[tree]

		mov [edx+Dad],ax

;if DUMP_BL_TREE eq 1

;        if (tree == s->bl_tree) {

;            fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",

;                    node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);

;        }

;end if

		; and insert the new node in the heap

		mov ecx,[node]

		mov [edi+deflate_state.heap+2*SMALLEST],cx

		inc dword[node]

		stdcall pqdownheap, edi, [tree], SMALLEST

		cmp dword[edi+deflate_state.heap_len],2

		jge .cycle3 ;while (..>=..)

	mov cx,[edi+deflate_state.heap+2*SMALLEST]

	dec dword[edi+deflate_state.heap_max]

	mov eax,[edi+deflate_state.heap_max]

	mov [edi+deflate_state.heap+2*eax],cx

	; At this point, the fields freq and dad are set. We can now

	; generate the bit lengths.

	stdcall gen_bitlen, edi, [desc]

	; The field len is now set, we can generate the bit codes

	mov eax,edi

	add eax,deflate_state.bl_count

	stdcall gen_codes, [tree], [max_code], eax

	ret

endp

; ===========================================================================

; Scan a literal or distance tree to determine the frequencies of the codes

; in the bit length tree.

;void (s, tree, max_code)

;    deflate_state* s

;    ct_data *tree ;the tree to be scanned

;    int max_code  ;and its largest code of non zero frequency

align 4

proc scan_tree uses eax ebx ecx edi, s:dword, tree:dword, max_code:dword

locals

	n dd ? ;int ;iterates over all tree elements

	prevlen  dd -1 ;int ;last emitted length

	curlen    dd ? ;int ;length of current code

	nextlen   dd ? ;int ;= tree[0].Len ;length of next code

	count     dd 0 ;int ;repeat count of the current code

	max_count dd 7 ;int ;max repeat count

	min_count dd 4 ;int ;min repeat count

endl

	mov edi,[s]

	zlib_debug 'scan_tree'

	mov eax,[tree]

	movzx eax,word[eax+Len]

	mov [nextlen],eax

	cmp eax,0

	jne @f ;if (..==0)

		mov dword[max_count],138

		mov dword[min_count],3

	@@:

	mov eax,[max_code]

	inc eax

	imul eax,sizeof.ct_data

	add eax,[tree]

	mov word[eax+Len],0xffff ;guard

	xor ecx,ecx

	.cycle0:

		cmp ecx,[max_code]

		jg .cycle0end ;for (..;..<=..;..)

		mov eax,[nextlen]

		mov [curlen],eax

		mov eax,ecx