Subversion Repositories Kolibri OS

Rev

Rev 6888 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
6617 IgorA 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
6860 IgorA 4
; For conditions of distribution and use, see copyright notice in zlib.inc
6617 IgorA 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
 
6860 IgorA 110
struct static_tree_desc
6617 IgorA 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
{
6741 IgorA 158
	mov eax,[s+deflate_state.pending]
6617 IgorA 159
	add eax,[s+deflate_state.pending_buf]
160
	mov word[eax],w
6741 IgorA 161
	add dword[s+deflate_state.pending],2
6617 IgorA 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
	@@:
6639 IgorA 182
		zlib_assert 'invalid length' ;Assert(..>0 && ..<=15)
6617 IgorA 183
	.end1:
184
	mov edi,[s]
6847 IgorA 185
	;;add [edi+deflate_state.bits_sent],eax
6617 IgorA 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]
6851 IgorA 204
		sar eax,cl
6617 IgorA 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<
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<
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
; ===========================================================================
6860 IgorA 327
; Genererate the file trees.inc describing the static trees.
6617 IgorA 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
 
6847 IgorA 387
;void (deflate_state* s)
6617 IgorA 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
 
6847 IgorA 421
;void (deflate_state* s)
6617 IgorA 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
 
6799 IgorA 449
	mov word[edi+sizeof.ct_data*END_BLOCK+deflate_state.dyn_ltree+Freq],1
6617 IgorA 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
6847 IgorA 468
	add eax,deflate_state.heap+4*SMALLEST
6617 IgorA 469
	movzx top,word[eax]
470
push ebx
471
	mov ebx,[s+deflate_state.heap_len]
6847 IgorA 472
	mov ebx,[s+deflate_state.heap+4*ebx]
473
	mov [eax],ebx
6617 IgorA 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
6847 IgorA 487
	mov eax,n
6617 IgorA 488
	imul eax,sizeof.ct_data
489
	add eax,tree
490
	mov ax,word[eax+Freq]
6847 IgorA 491
	mov ebx,m
6617 IgorA 492
	imul ebx,sizeof.ct_data
493
	add ebx,tree
6860 IgorA 494
	cmp ax,word[ebx+Freq]
6617 IgorA 495
	jl .end0
496
	jne m_end
6847 IgorA 497
	mov eax,n
6815 IgorA 498
	mov al,byte[eax+depth]
6847 IgorA 499
	mov ebx,m
6815 IgorA 500
	cmp al,byte[ebx+depth]
6617 IgorA 501
	jg m_end
502
	.end0:
503
}
504
 
505
; ===========================================================================
506
; Restore the heap property by moving down the tree starting at node k,
507
; exchanging a node with the smallest of its two sons if necessary, stopping
508
; when the heap property is re-established (each father smaller than its
509
; two sons).
510
 
511
;void (s, tree, k)
512
;    deflate_state* s
513
;    ct_data* tree ;the tree to restore
514
;    int      k    ;node to move down
515
align 4
516
proc pqdownheap, s:dword, tree:dword, k:dword
517
pushad
6815 IgorA 518
	;ecx - v dw
6617 IgorA 519
	mov edi,[s]
6815 IgorA 520
	mov esi,[k]
6847 IgorA 521
	mov ecx,[edi+deflate_state.heap+4*esi]
6617 IgorA 522
	shl esi,1
523
	;esi = j ;left son of k
524
	.cycle0: ;while (..<=..)
525
		cmp esi,[edi+deflate_state.heap_len]
526
		jg .cycle0end
527
		; Set j to the smallest of the two sons:
528
		;;cmp esi,[edi+deflate_state.heap_len]
529
		jge .end1 ;if (..<.. &&
6860 IgorA 530
		lea edx,[edi+4*esi+deflate_state.heap]
6847 IgorA 531
		smaller [tree], dword[edx+4], dword[edx], edi+deflate_state.depth, .end1
6617 IgorA 532
			inc esi
533
		.end1:
534
		; Exit if v is smaller than both sons
6847 IgorA 535
		mov edx,[edi+deflate_state.heap+4*esi]
536
		smaller [tree], ecx, edx, edi+deflate_state.depth, .end2
6617 IgorA 537
			jmp .cycle0end ;break
538
		.end2:
539
		; Exchange v with the smallest son
6815 IgorA 540
		;;mov dx,[edi+deflate_state.heap+2*esi]
6617 IgorA 541
		mov eax,[k]
6847 IgorA 542
		mov [edi+deflate_state.heap+4*eax],edx
6617 IgorA 543
		mov [k],esi
544
		; And continue down the tree, setting j to the left son of k
545
		shl esi,1
546
		jmp .cycle0
6815 IgorA 547
align 4
6617 IgorA 548
	.cycle0end:
549
	mov eax,[k]
6847 IgorA 550
	mov [edi+deflate_state.heap+4*eax],ecx
6617 IgorA 551
popad
552
	ret
553
endp
554
 
555
; ===========================================================================
556
; Compute the optimal bit lengths for a tree and update the total bit length
557
; for the current block.
558
; IN assertion: the fields freq and dad are set, heap[heap_max] and
559
;    above are the tree nodes sorted by increasing frequency.
560
; OUT assertions: the field len is set to the optimal bit length, the
561
;     array bl_count contains the frequencies for each bit length.
562
;     The length opt_len is updated; static_len is also updated if stree is
563
;     not null.
564
 
6854 IgorA 565
;void (deflate_state* s, tree_desc* desc)
566
align 16
6617 IgorA 567
proc gen_bitlen, s:dword, desc:dword
568
locals
569
	tree  dd ? ;ct_data* ;= desc.dyn_tree
570
	max_code dd ? ;int   ;= desc.max_code
571
	stree dd ? ;ct_data* ;= desc.stat_desc.static_tree
572
	extra dd ? ;intf*    ;= desc.stat_desc.extra_bits
573
	base  dd ? ;int      ;= desc.stat_desc.extra_base
574
	max_length dd ? ;int ;= desc.stat_desc.max_length
575
	h     dd ? ;int ;heap index
576
	m     dd ? ;int ;iterate over the tree elements
577
	bits  dd ? ;int ;bit length
578
	xbits dd ? ;int ;extra bits
579
	f     dw ? ;uint_16 ;frequency
580
	overflow dd 0 ;int ;number of elements with bit length too large
581
endl
582
pushad
583
	mov edi,[s]
584
	mov edx,[desc]
585
	mov eax,[edx+tree_desc.dyn_tree]
586
	mov [tree],eax
587
	mov eax,[edx+tree_desc.max_code]
588
	mov [max_code],eax
589
	mov ebx,[edx+tree_desc.stat_desc]
590
	mov eax,[ebx+static_tree_desc.static_tree]
591
	mov [stree],eax
592
	mov eax,[ebx+static_tree_desc.extra_bits]
593
	mov [extra],eax
594
	mov eax,[ebx+static_tree_desc.extra_base]
595
	mov [base],eax
596
	mov eax,[ebx+static_tree_desc.max_length]
597
	mov [max_length],eax
598
 
599
	xor ecx,ecx
600
	.cycle0:
601
	cmp ecx,MAX_BITS
602
	jg .cycle0end ;for (..;..<=..;..)
603
		mov word[edi+deflate_state.bl_count+2*ecx],0
604
		inc ecx
605
		jmp .cycle0
606
align 4
607
	.cycle0end:
608
 
609
	; In a first pass, compute the optimal bit lengths (which may
610
	; overflow in the case of the bit length tree).
611
 
612
	mov eax,[edi+deflate_state.heap_max]
6847 IgorA 613
	mov eax,[edi+deflate_state.heap+4*eax]
6617 IgorA 614
	imul eax,sizeof.ct_data
615
	add eax,[tree]
616
	mov word[eax+Len],0 ;root of the heap
617
 
618
	mov eax,[edi+deflate_state.heap_max]
619
	inc eax
620
	mov [h],eax
6854 IgorA 621
	jmp @f
622
align 4
6617 IgorA 623
	.cycle1:
6854 IgorA 624
	inc dword[h]
625
	@@:
6617 IgorA 626
	cmp dword[h],HEAP_SIZE
627
	jge .cycle1end ;for (..;..<..;..)
6860 IgorA 628
		mov eax,[h]
629
		mov ecx,[edi+4*eax+deflate_state.heap]
6617 IgorA 630
		;ecx = n
6854 IgorA 631
		mov edx,[tree]
632
		movzx eax,word[edx+sizeof.ct_data*ecx+Dad]
633
		movzx eax,word[edx+sizeof.ct_data*eax+Len]
6617 IgorA 634
		inc eax
635
		mov [bits],eax ;bits = tree[tree[n].Dad].Len + 1
6860 IgorA 636
		cmp eax,[max_length]
6617 IgorA 637
		jle @f ;if (..>..)
6860 IgorA 638
			mov eax,[max_length]
6617 IgorA 639
			mov [bits],eax
640
			inc dword[overflow]
641
		@@:
6854 IgorA 642
		mov [edx+sizeof.ct_data*ecx+Len],ax
6617 IgorA 643
		; We overwrite tree[n].Dad which is no longer needed
644
 
645
		cmp ecx,[max_code]
6854 IgorA 646
		jg .cycle1 ;if (..>..) continue ;not a leaf node
6617 IgorA 647
 
6854 IgorA 648
		inc word[edi+2*eax+deflate_state.bl_count]
6617 IgorA 649
		mov dword[xbits],0
650
		cmp ecx,[base]
651
		jl @f ;if (..>=..)
652
			mov eax,ecx
653
			sub eax,[base]
654
			shl eax,2 ;*= sizeof.dd
655
			add eax,[extra]
656
			mov eax,[eax]
657
			mov [xbits],eax
658
		@@:
6854 IgorA 659
		movzx eax,word[edx+sizeof.ct_data*ecx+Freq]
6617 IgorA 660
		mov [f],ax
661
		mov esi,[bits]
662
		add esi,[xbits]
663
		imul eax,esi
664
		add [edi+deflate_state.opt_len],eax
665
		cmp dword[stree],0
6870 IgorA 666
		je .cycle1 ;if (..)
6617 IgorA 667
			movzx eax,word[f]
6860 IgorA 668
			mov esi,[stree]
669
			movzx esi,word[esi+sizeof.ct_data*ecx+Len]
6617 IgorA 670
			add esi,[xbits]
671
			imul eax,esi
672
			add [edi+deflate_state.static_len],eax
673
		jmp .cycle1
674
align 4
675
	.cycle1end:
676
	cmp dword[overflow],0
677
	je .end_f ;if (..==0) return
678
 
679
;    Trace((stderr,"\nbit length overflow\n"));
680
	; This happens for example on obj2 and pic of the Calgary corpus
681
 
682
	; Find the first bit length which could increase:
683
	.cycle2: ;do
684
		mov eax,[max_length]
685
		dec eax
686
		mov [bits],eax
687
		shl eax,1 ;*= sizeof.dw
688
		add eax,edi
689
		add eax,deflate_state.bl_count
690
		@@:
691
		cmp word[eax],0
692
		jne @f ;while (..==0) bits--
693
			dec dword[bits]
694
			sub eax,2
695
			jmp @b
6813 IgorA 696
align 4
6617 IgorA 697
		@@:
698
		dec word[eax]     ;move one leaf down the tree
699
		add word[eax+2],2 ;move one overflow item as its brother
700
		mov eax,[max_length]
701
		dec word[edi+deflate_state.bl_count+2*eax]
702
		; The brother of the overflow item also moves one step up,
703
		; but this does not affect bl_count[max_length]
704
 
705
		sub dword[overflow],2
706
		cmp dword[overflow],0
707
		jg .cycle2 ;while (..>0)
708
 
709
	; Now recompute all bit lengths, scanning in increasing frequency.
710
	; h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
711
	; lengths instead of fixing only the wrong ones. This idea is taken
712
	; from 'ar' written by Haruhiko Okumura.)
713
 
714
	mov eax,[max_length]
715
	mov [bits],eax
716
	.cycle3:
717
	cmp dword[bits],0
718
	je .end_f ;for (..;..!=0;..)
719
		mov eax,[bits]
6854 IgorA 720
		movzx ecx,word[edi+2*eax+deflate_state.bl_count]
6617 IgorA 721
		.cycle4: ;while (..!=0)
6854 IgorA 722
		test ecx,ecx
723
		jz .cycle4end
6617 IgorA 724
			dec dword[h]
725
			mov eax,[h]
6854 IgorA 726
			mov eax,[edi+4*eax+deflate_state.heap]
6617 IgorA 727
			mov [m],eax ;m = s.heap[--h]
728
			cmp eax,[max_code]
6813 IgorA 729
			jg .cycle4 ;if (..>..) continue
6617 IgorA 730
			mov esi,[m]
6860 IgorA 731
			imul esi,sizeof.ct_data
732
			add esi,edx ;esi = &tree[m]
6617 IgorA 733
			mov eax,[bits]
6860 IgorA 734
			cmp word[esi+Len],ax
6617 IgorA 735
			je @f ;if (..!=..)
736
;                Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
737
				movzx ebx,word[esi+Len]
738
				sub eax,ebx
739
				movzx ebx,word[esi+Freq]
740
				imul eax,ebx ;eax = (bits - tree[m].Len) * tree[m].Freq
741
				add [edi+deflate_state.opt_len],eax
742
				mov eax,[bits]
743
				mov word[esi+Len],ax
744
			@@:
745
			dec ecx
746
			jmp .cycle4
6813 IgorA 747
align 4
6617 IgorA 748
		.cycle4end:
749
		dec dword[bits]
750
		jmp .cycle3
6813 IgorA 751
align 4
6617 IgorA 752
.end_f:
753
popad
754
	ret
755
endp
756
 
757
; ===========================================================================
758
; Generate the codes for a given tree and bit counts (which need not be
759
; optimal).
760
; IN assertion: the array bl_count contains the bit length statistics for
761
; the given tree and the field len is set for all tree elements.
762
; OUT assertion: the field code is set for all tree elements of non
763
;     zero code length.
764
 
765
;void (tree, max_code, bl_count)
766
;    ct_data *tree     ;the tree to decorate
767
;    int max_code      ;largest code with non zero frequency
768
;    uint_16p bl_count ;number of codes at each bit length
769
align 4
770
proc gen_codes uses eax ebx ecx edx edi, tree:dword, max_code:dword, bl_count:dword
771
locals
772
	u_code dw 0 ;uint_16 ;running code value
773
	bits   dd 1 ;int ;bit index
774
	next_code rw MAX_BITS+1 ;uint_16[] ;next code value for each bit length
775
endl
776
	; The distribution counts are first used to generate the code values
777
	; without bit reversal.
778
	mov ebx,ebp
779
	sub ebx,2*(MAX_BITS+1)
780
 
781
	.cycle0: ;for (..;..<=..;..)
782
	cmp dword[bits],MAX_BITS
783
	jg .cycle0end
784
		mov eax,[bits]
785
		dec eax
786
		shl eax,1
787
		add eax,[bl_count]
788
		mov ax,word[eax]
789
		add ax,[u_code]
790
		shl ax,1 ;ax = (u_code + bl_count[bits-1]) << 1
791
		mov [u_code],ax
792
		mov ecx,[bits]
793
		mov word[ebx+2*ecx],ax ;next_code[bits] = u_code
794
		inc dword[bits]
795
		jmp .cycle0
796
	.cycle0end:
797
	; Check that the bit counts in bl_count are consistent. The last code
798
	; must be all ones.
799
 
800
	mov eax,[bl_count]
801
	mov ax,word[eax+2*MAX_BITS]
802
	add ax,[u_code]
803
	dec ax
804
	cmp ax,(1 shl MAX_BITS)-1
805
	je @f
6639 IgorA 806
		zlib_assert 'inconsistent bit counts' ;Assert(..==..)
6617 IgorA 807
	@@:
808
;    Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
809
 
810
	xor ecx,ecx ;n = 0
811
	.cycle1: ;for (..;..<=..;..)
812
	cmp ecx,[max_code]
813
	jg .cycle1end
814
		mov edx,sizeof.ct_data
815
		imul edx,ecx
816
		add edx,[tree] ;edx = &tree[n]
817
		movzx edi,word[edx+Len]
818
		cmp edi,0
819
		jne @f ;if (..==0) continue
820
			inc ecx
821
			jmp .cycle1
822
		@@:
823
		; Now reverse the bits
824
		movzx eax,word[ebx+2*edi]
825
		stdcall bi_reverse, eax, edi
826
		mov word[edx+Code],ax
827
		inc word[ebx+2*edi]
828
 
829
;        Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
830
;             n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
831
		inc ecx
832
		jmp .cycle1
833
	.cycle1end:
834
	ret
835
endp
836
 
837
; ===========================================================================
838
; Construct one Huffman tree and assigns the code bit strings and lengths.
839
; Update the total bit length for the current block.
840
; IN assertion: the field freq is set for all tree elements.
841
; OUT assertions: the fields len and code are set to the optimal bit length
842
;     and corresponding code. The length opt_len is updated; static_len is
843
;     also updated if stree is not null. The field max_code is set.
844
 
845
;void (s, desc)
846
;    deflate_state* s
847
;    tree_desc *desc ;the tree descriptor
848
align 4
849
proc build_tree uses eax ebx ecx edx edi, s:dword, desc:dword
850
locals
851
	tree     dd  ? ;ct_data* ;= desc.dyn_tree
852
	stree    dd  ? ;ct_data* ;= desc.stat_desc.static_tree
853
	elems    dd  ? ;int      ;= desc.stat_desc.elems
854
	m        dd  ? ;int ;iterate over heap elements
855
	max_code dd -1 ;int ;largest code with non zero frequency
856
	node     dd  ? ;int ;new node being created
857
endl
858
	; Construct the initial heap, with least frequent element in
859
	; heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
860
	; heap[0] is not used.
861
	mov ebx,[desc]
862
	mov eax,[ebx+tree_desc.dyn_tree]
863
	mov [tree],eax
864
	mov ecx,[ebx+tree_desc.stat_desc]
865
	mov eax,[ecx+static_tree_desc.static_tree]
866
	mov [stree],eax
867
	mov ecx,[ecx+static_tree_desc.elems]
868
	mov [elems],ecx
869
	mov edi,[s]
6639 IgorA 870
	zlib_debug 'build_tree cycle0 ecx = %d',ecx
6617 IgorA 871
 
872
	mov dword[edi+deflate_state.heap_len],0
873
	mov dword[edi+deflate_state.heap_max],HEAP_SIZE
874
 
6813 IgorA 875
	mov edx,[tree]
876
	xor ecx,ecx
6617 IgorA 877
	.cycle0: ;for (..;..<..;..)
6813 IgorA 878
	cmp ecx,[elems]
6854 IgorA 879
	jge .cycle1
6813 IgorA 880
		cmp word[edx+Freq],0
6617 IgorA 881
		je @f ;if (..!=0)
882
			inc dword[edi+deflate_state.heap_len]
883
			mov eax,[edi+deflate_state.heap_len]
6813 IgorA 884
			mov [max_code],ecx
6847 IgorA 885
			mov dword[edi+deflate_state.heap+4*eax],ecx
6813 IgorA 886
			mov byte[edi+deflate_state.depth+ecx],0
6617 IgorA 887
			jmp .end0
888
align 4
889
		@@: ;else
6813 IgorA 890
			mov word[edx+Len],0
6617 IgorA 891
		.end0:
6813 IgorA 892
		add edx,sizeof.ct_data
893
		inc ecx
894
		jmp .cycle0
6617 IgorA 895
 
896
	; The pkzip format requires that at least one distance code exists,
897
	; and that at least one bit should be sent even if there is only one
898
	; possible code. So to avoid special checks later on we force at least
899
	; two codes of non zero frequency.
900
 
6854 IgorA 901
align 4
6617 IgorA 902
	.cycle1: ;while (..<..)
903
		cmp dword[edi+deflate_state.heap_len],2
904
		jge .cycle1end
905
		inc dword[edi+deflate_state.heap_len]
906
		xor eax,eax
907
		cmp dword[max_code],2
908
		jge @f
909
			inc dword[max_code]
910
			mov eax,[max_code]
911
		@@:
912
		mov ecx,[edi+deflate_state.heap_len]
6847 IgorA 913
		mov [edi+deflate_state.heap+4*ecx],eax
6617 IgorA 914
		mov [node],eax
915
		imul eax,sizeof.ct_data
916
		add eax,[tree]
917
		mov word[eax+Freq],1
918
		mov eax,[node]
919
		mov byte[edi+deflate_state.depth+eax],0
920
		dec dword[edi+deflate_state.opt_len]
921
		cmp dword[stree],0
922
		je .cycle1 ;if (..)
923
			mov eax,[node]
924
			imul eax,sizeof.ct_data
925
			add eax,[stree]
926
			movzx eax,word[eax+Len]
927
			sub [edi+deflate_state.static_len],eax
928
		; node is 0 or 1 so it does not have extra bits
929
		jmp .cycle1
930
align 4
931
	.cycle1end:
932
	mov eax,[max_code]
933
	mov [ebx+tree_desc.max_code],eax
934
 
935
	; The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
936
	; establish sub-heaps of increasing lengths:
937
 
938
	mov ecx,[edi+deflate_state.heap_len]
6854 IgorA 939
	sar ecx,1
6617 IgorA 940
	.cycle2: ;for (..;..>=..;..)
941
		cmp ecx,1
942
		jl .cycle2end
943
		stdcall pqdownheap, edi, [tree], ecx
944
		dec ecx
945
		jmp .cycle2
946
align 4
947
	.cycle2end:
948
 
949
	; Construct the Huffman tree by repeatedly combining the least two
950
	; frequent nodes.
951
 
952
	mov eax,[elems]
953
	mov [node],eax ;next internal node of the tree
954
	.cycle3: ;do
955
		pqremove edi, [tree], ecx ;n = node of least frequency
956
		movzx edx,word[eax]
957
		mov [m],edx ;m = node of next least frequency
958
 
959
		mov eax,[edi+deflate_state.heap_max]
960
		dec eax
6847 IgorA 961
		mov [edi+deflate_state.heap+4*eax],ecx ;keep the nodes sorted by frequency
6617 IgorA 962
		dec eax
963
		mov [edi+deflate_state.heap_max],eax
6847 IgorA 964
		mov [edi+deflate_state.heap+4*eax],edx
6617 IgorA 965
 
966
		; Create a new node father of n and m
967
		;;mov edx,[m]
968
		imul edx,sizeof.ct_data
969
		add edx,[tree]
970
		mov ax,word[edx+Freq]
6860 IgorA 971
		mov edx,[tree]
972
		add ax,word[edx+sizeof.ct_data*ecx+Freq]
6617 IgorA 973
		mov edx,[node]
974
		imul edx,sizeof.ct_data
975
		add edx,[tree]
976
		mov word[edx+Freq],ax
977
 
978
		mov eax,ecx
979
		add eax,edi
6813 IgorA 980
		mov al,byte[eax+deflate_state.depth]
6617 IgorA 981
		mov edx,[m]
982
		add edx,edi
6813 IgorA 983
		mov ah,byte[edx+deflate_state.depth]
6617 IgorA 984
		cmp al,ah
6815 IgorA 985
		jge @f ;if (al>=ah) al=al : al=ah
6617 IgorA 986
			mov al,ah
987
		@@:
988
		inc al
989
		mov edx,[node]
990
		add edx,edi
6813 IgorA 991
		mov byte[edx+deflate_state.depth],al
6617 IgorA 992
 
993
		mov eax,[node]
994
		mov edx,[m]
995
		imul edx,sizeof.ct_data
996
		add edx,[tree]
997
		mov [edx+Dad],ax
998
		mov edx,ecx
999
		imul edx,sizeof.ct_data
1000
		add edx,[tree]
1001
		mov [edx+Dad],ax
1002
;if DUMP_BL_TREE eq 1
1003
;        if (tree == s->bl_tree) {
1004
;            fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
1005
;                    node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
1006
;        }
1007
;end if
1008
		; and insert the new node in the heap
1009
		mov ecx,[node]
6847 IgorA 1010
		mov [edi+deflate_state.heap+4*SMALLEST],ecx
6617 IgorA 1011
		inc dword[node]
1012
		stdcall pqdownheap, edi, [tree], SMALLEST
1013
		cmp dword[edi+deflate_state.heap_len],2
1014
		jge .cycle3 ;while (..>=..)
1015
 
6847 IgorA 1016
	mov ecx,[edi+deflate_state.heap+4*SMALLEST]
6617 IgorA 1017
	dec dword[edi+deflate_state.heap_max]
1018
	mov eax,[edi+deflate_state.heap_max]
6847 IgorA 1019
	mov [edi+deflate_state.heap+4*eax],ecx
6617 IgorA 1020
 
1021
	; At this point, the fields freq and dad are set. We can now
1022
	; generate the bit lengths.
1023
 
1024
	stdcall gen_bitlen, edi, [desc]
1025
 
1026
	; The field len is now set, we can generate the bit codes
1027
	mov eax,edi
1028
	add eax,deflate_state.bl_count
1029
	stdcall gen_codes, [tree], [max_code], eax
1030
	ret
1031
endp
1032
 
1033
; ===========================================================================
1034
; Scan a literal or distance tree to determine the frequencies of the codes
1035
; in the bit length tree.
1036
 
1037
;void (s, tree, max_code)
1038
;    deflate_state* s
1039
;    ct_data *tree ;the tree to be scanned
1040
;    int max_code  ;and its largest code of non zero frequency
1041
align 4
1042
proc scan_tree uses eax ebx ecx edi, s:dword, tree:dword, max_code:dword
1043
locals
1044
	n dd ? ;int ;iterates over all tree elements
1045
	prevlen  dd -1 ;int ;last emitted length
1046
	curlen    dd ? ;int ;length of current code
1047
	nextlen   dd ? ;int ;= tree[0].Len ;length of next code
1048
	count     dd 0 ;int ;repeat count of the current code
1049
	max_count dd 7 ;int ;max repeat count
1050
	min_count dd 4 ;int ;min repeat count
1051
endl
1052
	mov edi,[s]
1053
	mov eax,[tree]
1054
	movzx eax,word[eax+Len]
1055
	mov [nextlen],eax
6815 IgorA 1056
	test eax,eax
1057
	jnz @f ;if (..==0)
6617 IgorA 1058
		mov dword[max_count],138
1059
		mov dword[min_count],3
1060
	@@:
1061
	mov eax,[max_code]
1062
	inc eax
1063
	imul eax,sizeof.ct_data
1064
	add eax,[tree]
1065
	mov word[eax+Len],0xffff ;guard
1066
 
1067
	xor ecx,ecx
6815 IgorA 1068
align 4
6617 IgorA 1069
	.cycle0:
1070
		cmp ecx,[max_code]
1071
		jg .cycle0end ;for (..;..<=..;..)
1072
		mov eax,[nextlen]
1073
		mov [curlen],eax
6815 IgorA 1074
		inc ecx
1075
		mov eax,sizeof.ct_data
1076
		imul eax,ecx
6617 IgorA 1077
		add eax,[tree]
1078
		movzx eax,word[eax+Len]
1079
		mov [nextlen],eax
1080
		inc dword[count]
1081
		mov ebx,[count]
1082
		cmp ebx,[max_count]
1083
		jge .end0
1084
		mov eax,[nextlen]
1085
		cmp [curlen],eax
6815 IgorA 1086
		je .cycle0 ;if (..<.. && ..==..) continue
1087
align 4
6617 IgorA 1088
		.end0:
1089
		cmp ebx,[min_count]
1090
		jge .end1 ;else if (..<..)
1091
			mov eax,[curlen]
1092
			imul eax,sizeof.ct_data
1093
			add eax,edi
6813 IgorA 1094
			add word[eax+deflate_state.bl_tree+Freq],bx
6617 IgorA 1095
			jmp .end4
6815 IgorA 1096
align 4
6617 IgorA 1097
		.end1:
1098
		cmp dword[curlen],0
1099
		je .end2 ;else if (..!=0)
1100
			mov eax,[curlen]
1101
			cmp eax,[prevlen]
1102
			je @f ;if (..!=..)
1103
				imul eax,sizeof.ct_data
1104
				add eax,edi
6813 IgorA 1105
				inc word[eax+deflate_state.bl_tree+Freq]
6617 IgorA 1106
			@@:
1107
			mov eax,REP_3_6
1108
			imul eax,sizeof.ct_data
1109
			add eax,edi
6813 IgorA 1110
			inc word[eax+deflate_state.bl_tree+Freq]
6617 IgorA 1111
			jmp .end4
6815 IgorA 1112
align 4
6617 IgorA 1113
		.end2:
1114
		cmp ebx,10
1115
		jg .end3 ;else if (..<=..)
1116
			mov eax,REPZ_3_10
1117
			imul eax,sizeof.ct_data
1118
			add eax,edi
6813 IgorA 1119
			inc word[eax+deflate_state.bl_tree+Freq]
6617 IgorA 1120
			jmp .end4
6815 IgorA 1121
align 4
6617 IgorA 1122
		.end3: ;else
1123
			mov eax,REPZ_11_138
1124
			imul eax,sizeof.ct_data
1125
			add eax,edi
6813 IgorA 1126
			inc word[eax+deflate_state.bl_tree+Freq]
6617 IgorA 1127
		.end4:
1128
		mov eax,[curlen]
1129
		mov [prevlen],eax
6855 IgorA 1130
		xor eax,eax
1131
		mov dword[count],eax
1132
		cmp dword[nextlen],eax
6617 IgorA 1133
		jne .end5 ;if (..==0)
1134
			mov dword[max_count],138
1135
			mov dword[min_count],3
6815 IgorA 1136
			jmp .cycle0
1137
align 4
6617 IgorA 1138
		.end5:
1139
		cmp eax,[nextlen]
1140
		jne .end6 ;else if (..==..)
1141
			mov dword[max_count],6
1142
			mov dword[min_count],3
6815 IgorA 1143
			jmp .cycle0
1144
align 4
6617 IgorA 1145
		.end6: ;else
1146
			mov dword[max_count],7
1147
			mov dword[min_count],4
1148
		jmp .cycle0
6815 IgorA 1149
align 4
6617 IgorA 1150
	.cycle0end:
1151
	ret
1152
endp
1153
 
1154
; ===========================================================================
1155
; Send a literal or distance tree in compressed form, using the codes in
1156
; bl_tree.
1157
 
1158
;void (s, tree, max_code)
1159
;    deflate_state* s
1160
;    ct_data *tree ;the tree to be scanned
1161
;    int max_code  ;and its largest code of non zero frequency
6855 IgorA 1162
align 16
6617 IgorA 1163
proc send_tree uses eax ebx ecx edi, s:dword, tree:dword, max_code:dword
1164
locals
1165
	n dd ? ;int ;iterates over all tree elements
1166
	prevlen  dd -1 ;int ;last emitted length
1167
	curlen    dd ? ;int ;length of current code
1168
	nextlen   dd ? ;int ;= tree[0].Len ;length of next code
1169
	count     dd 0 ;int ;repeat count of the current code
1170
	max_count dd 7 ;int ;max repeat count
1171
	min_count dd 4 ;int ;min repeat count
1172
endl
1173
	mov edi,[s]
1174
	; *** tree[max_code+1].Len = -1 ;guard already set
1175
	mov eax,[tree]
1176
	movzx eax,word[eax+Len]
1177
	mov [nextlen],eax
6813 IgorA 1178
	xor ecx,ecx
1179
	test eax,eax
1180
	jnz .cycle0 ;if (..==0)
6617 IgorA 1181
		mov dword[max_count],138
1182
		mov dword[min_count],3
6813 IgorA 1183
align 4
6617 IgorA 1184
	.cycle0: ;for (..;..<=..;..)
1185
	cmp ecx,[max_code]
1186
	jg .cycle0end
1187
		mov eax,[nextlen]
1188
		mov [curlen],eax
1189
		mov eax,ecx
1190
		inc eax
1191
		imul eax,sizeof.ct_data
1192
		add eax,[tree]
1193
		movzx eax,word[eax+Len]
1194
		mov [nextlen],eax
1195
		inc dword[count]
1196
		mov ebx,[count]
1197
		cmp ebx,[max_count]
1198
		jge .end0
1199
		mov eax,[nextlen]
1200
		cmp [curlen],eax
1201
		jne .end0 ;if (..<.. && ..==..)
1202
			inc ecx
1203
			jmp .cycle0 ;continue
6813 IgorA 1204
align 4
6617 IgorA 1205
		.end0:
1206
		cmp ebx,[min_count]
1207
		jge .end1 ;else if (..<..)
1208
			@@: ;do
1209
				mov ebx,edi
1210
				add ebx,deflate_state.bl_tree
1211
				send_code edi, [curlen], ebx
1212
				dec dword[count]
6813 IgorA 1213
				jnz @b ;while (..!=0)
6617 IgorA 1214
			jmp .end4
1215
align 4
1216
		.end1:
1217
		cmp dword[curlen],0
1218
		je .end2 ;else if (..!=0)
1219
			mov eax,[curlen]
1220
			cmp eax,[prevlen]
1221
			je @f ;if (..!=..)
1222
				mov ebx,edi
1223
				add ebx,deflate_state.bl_tree
1224
				send_code edi, eax, ebx
1225
				dec dword[count]
1226
			@@:
1227
			cmp dword[count],3
1228
			jl @f
1229
			cmp dword[count],6
1230
			jle .end8
1231
			@@:
6639 IgorA 1232
				zlib_assert ' 3_6?' ;Assert(..>=.. && ..<=..)
6617 IgorA 1233
			.end8:
1234
			mov ebx,edi
1235
			add ebx,deflate_state.bl_tree
1236
			send_code edi, REP_3_6, ebx
1237
			mov ebx,[count]
1238
			sub ebx,3
1239
			stdcall send_bits, edi, ebx, 2
1240
			jmp .end4
1241
		.end2:
1242
		cmp ebx,10
1243
		jg .end3 ;else if (..<=..)
1244
			mov ebx,edi
1245
			add ebx,deflate_state.bl_tree
1246
			send_code edi, REPZ_3_10, ebx
1247
			mov ebx,[count]
1248
			sub ebx,3
1249
			stdcall send_bits, edi, ebx, 3
1250
			jmp .end4
1251
		.end3: ;else
1252
			mov ebx,edi
1253
			add ebx,deflate_state.bl_tree
1254
			send_code edi, REPZ_11_138, ebx
1255
			mov ebx,[count]
1256
			sub ebx,11
1257
			stdcall send_bits, edi, ebx, 7
1258
		.end4:
1259
		mov eax,[curlen]
1260
		mov [prevlen],eax
6855 IgorA 1261
		xor eax,eax
1262
		mov dword[count],eax
1263
		cmp [nextlen],eax
6617 IgorA 1264
		jne .end5 ;if (..==0)
1265
			mov dword[max_count],138
1266
			mov dword[min_count],3
1267
			jmp .end7
1268
		.end5:
1269
		mov eax,[curlen]
1270
		cmp eax,[nextlen]
1271
		jne .end6 ;else if (..==..)
1272
			mov dword[max_count],6
1273
			mov dword[min_count],3
1274
			jmp .end7
1275
		.end6: ;else
1276
			mov dword[max_count],7
1277
			mov dword[min_count],4
1278
		.end7:
1279
		inc ecx
1280
		jmp .cycle0
1281
align 4
1282
	.cycle0end:
1283
	ret
1284
endp
1285
 
1286
; ===========================================================================
1287
; Construct the Huffman tree for the bit lengths and return the index in
1288
; bl_order of the last bit length code to send.
1289
 
6847 IgorA 1290
;int (deflate_state* s)
6888 IgorA 1291
align 16
6889 IgorA 1292
proc build_bl_tree uses ebx ecx edi, s:dword
1293
	;ebx - max_blindex ;index of last bit length code of non zero freq
1294
 
6617 IgorA 1295
	mov edi,[s]
1296
	; Determine the bit length frequencies for literal and distance trees
1297
	mov eax,edi
1298
	add eax,deflate_state.dyn_ltree
1299
	stdcall scan_tree, edi, eax, [edi+deflate_state.l_desc.max_code]
6799 IgorA 1300
	add eax,deflate_state.dyn_dtree-deflate_state.dyn_ltree
6617 IgorA 1301
	stdcall scan_tree, edi, eax, [edi+deflate_state.d_desc.max_code]
1302
 
1303
	; Build the bit length tree:
6799 IgorA 1304
	add eax,deflate_state.bl_desc-deflate_state.dyn_dtree
6617 IgorA 1305
	stdcall build_tree, edi, eax
1306
	; opt_len now includes the length of the tree representations, except
1307
	; the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
1308
 
1309
	; Determine the number of bit length codes to send. The pkzip format
1310
	; requires that at least 4 bit length codes be sent. (appnote.txt says
1311
	; 3 but the actual value used is 4.)
1312
 
6889 IgorA 1313
	mov ebx,BL_CODES-1
6888 IgorA 1314
	jmp @f
1315
align 4
6617 IgorA 1316
	.cycle0: ;for (..;..>=..;..)
6889 IgorA 1317
		dec ebx
6888 IgorA 1318
		@@:
6889 IgorA 1319
		cmp ebx,3
6617 IgorA 1320
		jl .cycle0end
6889 IgorA 1321
		movzx ecx,byte[ebx+bl_order]
1322
		movzx ecx,word[edi+sizeof.ct_data*ecx+deflate_state.bl_tree+Len]
6888 IgorA 1323
		jecxz .cycle0
6813 IgorA 1324
align 4
6617 IgorA 1325
	.cycle0end:
1326
	; Update opt_len to include the bit length tree and counts
6889 IgorA 1327
	mov eax,ebx
6617 IgorA 1328
	inc eax
1329
	imul eax,3
1330
	add eax,5+5+4
1331
	add [edi+deflate_state.opt_len],eax
1332
;    Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", s->opt_len, s->static_len));
1333
 
6889 IgorA 1334
	mov eax,ebx
6617 IgorA 1335
	ret
1336
endp
1337
 
1338
; ===========================================================================
1339
; Send the header for a block using dynamic Huffman trees: the counts, the
1340
; lengths of the bit length codes, the literal tree and the distance tree.
1341
; IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
1342
 
6889 IgorA 1343
;void (deflate_state* s, lcodes, dcodes, blcodes)
6617 IgorA 1344
;    int lcodes, dcodes, blcodes ;number of codes for each tree
1345
align 4
1346
proc send_all_trees uses eax ebx ecx edi, s:dword, lcodes:dword, dcodes:dword, blcodes:dword
1347
;ecx = index in bl_order
1348
	cmp dword[lcodes],257
1349
	jl @f
1350
	cmp dword[dcodes],1
1351
	jl @f
1352
	cmp dword[blcodes],4
1353
	jge .end0
1354
	@@:
6639 IgorA 1355
		zlib_assert 'not enough codes' ;Assert(..>=.. && ..>=.. && ..>=..)
6617 IgorA 1356
	.end0:
1357
	cmp dword[lcodes],L_CODES
1358
	jg @f
1359
	cmp dword[dcodes],D_CODES
1360
	jg @f
1361
	cmp dword[blcodes],BL_CODES
1362
	jle .end1
1363
	@@:
6639 IgorA 1364
		zlib_assert 'too many codes' ;Assert(..<=.. && ..<=.. && ..<=..)
6617 IgorA 1365
	.end1:
1366
;    Tracev((stderr, "\nbl counts: "));
1367
	mov edi,[s]
1368
	mov eax,[lcodes]
1369
	sub eax,257
1370
	stdcall send_bits, edi, eax, 5 ;not +255 as stated in appnote.txt
1371
	mov eax,[dcodes]
1372
	dec eax
1373
	stdcall send_bits, edi, eax, 5
1374
	mov eax,[blcodes]
1375
	sub eax,4
1376
	stdcall send_bits, edi, eax, 4 ;not -3 as stated in appnote.txt
1377
	xor ecx,ecx
1378
	.cycle0:
1379
		cmp ecx,[blcodes]
1380
		jge .cycle0end ;for (..;..<..;..)
1381
;        Tracev((stderr, "\nbl code %2d ", bl_order[ecx]));
6851 IgorA 1382
		movzx eax,byte[ecx+bl_order]
1383
		movzx eax,word[edi+sizeof.ct_data*eax+deflate_state.bl_tree+Len]
6813 IgorA 1384
		stdcall send_bits, edi, eax, 3
6617 IgorA 1385
		inc ecx
1386
		jmp .cycle0
1387
align 4
1388
	.cycle0end:
1389
;    Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
1390
 
1391
	mov ebx,[lcodes]
1392
	dec ebx
1393
	mov eax,edi
1394
	add eax,deflate_state.dyn_ltree
1395
	stdcall send_tree, edi, eax, ebx ;literal tree
1396
;    Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
1397
 
1398
	mov ebx,[dcodes]
1399
	dec ebx
1400
	add eax,deflate_state.dyn_dtree-deflate_state.dyn_ltree
1401
	stdcall send_tree, edi, eax, ebx ;distance tree
1402
;    Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
1403
	ret
1404
endp
1405
 
1406
; ===========================================================================
1407
; Send a stored block
1408
 
1409
;void (s, buf, stored_len, last)
1410
;    deflate_state* s
1411
;    charf *buf     ;input block
1412
;    ulg stored_len ;length of input block
1413
;    int last       ;one if this is the last block for a file
1414
align 4
1415
proc _tr_stored_block uses eax edi, s:dword, buf:dword, stored_len:dword, last:dword
1416
	mov edi,[s]
1417
	mov eax,[last]
1418
	add eax,STORED_BLOCK shl 1
1419
	stdcall send_bits, edi, eax, 3 ;send block type
1420
if DEBUG eq 1
1421
	mov eax,[edi+deflate_state.compressed_len]
1422
	add eax,3+7
1423
	and eax,not 7
1424
	mov [edi+deflate_state.compressed_len],eax
1425
	mov eax,[stored_len]
1426
	add eax,4
1427
	shl eax,3
1428
	add [edi+deflate_state.compressed_len],eax
1429
end if
1430
	stdcall copy_block, edi, [buf], [stored_len], 1 ;with header
1431
	ret
1432
endp
1433
 
1434
; ===========================================================================
1435
; Flush the bits in the bit buffer to pending output (leaves at most 7 bits)
1436
 
6847 IgorA 1437
;void (deflate_state* s)
1438
;align 4
1439
;proc _tr_flush_bits, s:dword
1440
;	stdcall bi_flush, [s]
1441
;	ret
1442
;endp
6617 IgorA 1443
 
6847 IgorA 1444
_tr_flush_bits equ bi_flush
1445
 
6617 IgorA 1446
; ===========================================================================
1447
; Send one empty static block to give enough lookahead for inflate.
1448
; This takes 10 bits, of which 7 may remain in the bit buffer.
1449
 
6847 IgorA 1450
;void (deflate_state* s)
6617 IgorA 1451
align 4
1452
proc _tr_align uses edi, s:dword
1453
	mov edi,[s]
1454
	stdcall send_bits, edi, STATIC_TREES shl 1, 3
1455
	send_code edi, END_BLOCK, static_ltree
1456
if DEBUG eq 1
1457
	add [edi+deflate_state.compressed_len],10 ;3 for block type, 7 for EOB
1458
end if
1459
	stdcall bi_flush, edi
1460
	ret
1461
endp
1462
 
1463
; ===========================================================================
1464
; Determine the best encoding for the current block: dynamic trees, static
1465
; trees or store, and output the encoded block to the zip file.
1466
 
1467
;void (s, buf, stored_len, last)
1468
;    deflate_state* s
1469
;    charf *buf     ;input block, or NULL if too old
1470
;    ulg stored_len ;length of input block
1471
;    int last       ;one if this is the last block for a file
1472
align 4
1473
proc _tr_flush_block uses eax ebx edi, s:dword, buf:dword, stored_len:dword, last:dword
1474
locals
1475
	opt_lenb dd ? ;ulg
1476
	static_lenb dd ? ;opt_len and static_len in bytes
1477
	max_blindex dd 0 ;int ;index of last bit length code of non zero freq
1478
endl
1479
	; Build the Huffman trees unless a stored block is forced
1480
	mov edi,[s]
1481
	cmp word[edi+deflate_state.level],0
1482
	jle .end0 ;if (..>0)
1483
 
1484
		; Check if the file is binary or text
1485
		mov ebx,[edi+deflate_state.strm]
6797 IgorA 1486
		cmp dword[ebx+z_stream.data_type],Z_UNKNOWN
6617 IgorA 1487
		jne @f ;if (..==..)
1488
			stdcall detect_data_type, edi
6797 IgorA 1489
			mov [ebx+z_stream.data_type],eax
6617 IgorA 1490
		@@:
1491
 
1492
		; Construct the literal and distance trees
1493
		mov eax,edi
1494
		add eax,deflate_state.l_desc
1495
		stdcall build_tree, edi, eax
1496
;        Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, s->static_len));
1497
 
1498
		mov eax,edi
1499
		add eax,deflate_state.d_desc
1500
		stdcall build_tree, edi, eax
1501
;        Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, s->static_len));
1502
		; At this point, opt_len and static_len are the total bit lengths of
1503
		; the compressed block data, excluding the tree representations.
1504
 
1505
		; Build the bit length tree for the above two trees, and get the index
1506
		; in bl_order of the last bit length code to send.
1507
 
1508
		stdcall build_bl_tree, edi
1509
		mov [max_blindex],eax
1510
 
1511
		; Determine the best encoding. Compute the block lengths in bytes.
1512
		mov eax,[edi+deflate_state.opt_len]
1513
		add eax,3+7
1514
		shr eax,3
1515
		mov [opt_lenb],eax
1516
		mov eax,[edi+deflate_state.static_len]
1517
		add eax,3+7
1518
		shr eax,3
1519
		mov [static_lenb],eax
1520
 
1521
;        Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
1522
;                opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
1523
;                s->last_lit));
1524
 
1525
		cmp eax,[opt_lenb]
6851 IgorA 1526
		ja .end1 ;if (..<=..)
6617 IgorA 1527
			mov [opt_lenb],eax
1528
		jmp .end1
1529
	.end0: ;else
1530
		cmp dword[buf],0
1531
		jne @f
6639 IgorA 1532
			zlib_assert 'lost buf' ;Assert(..!=0)
6617 IgorA 1533
		@@:
1534
		mov eax,[stored_len]
1535
		add eax,5
1536
		mov [static_lenb],eax
1537
		mov [opt_lenb],eax ;force a stored block
1538
	.end1:
1539
 
1540
if FORCE_STORED eq 1
1541
	cmp dword[buf],0
1542
	je .end2 ;if (..!=0) ;force stored block
1543
else
1544
	mov eax,[stored_len]
1545
	add eax,4
1546
	cmp eax,[opt_lenb]
6851 IgorA 1547
	ja .end2
6617 IgorA 1548
	cmp dword[buf],0
1549
	je .end2 ;if (..<=.. && ..!=0)
1550
		;4: two words for the lengths
1551
end if
1552
		; The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
1553
		; Otherwise we can't have processed more than WSIZE input bytes since
1554
		; the last block flush, because compression would have been
1555
		; successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
1556
		; transform a block into a stored block.
1557
 
1558
		stdcall _tr_stored_block, edi, [buf], [stored_len], [last]
1559
		jmp .end4
1560
	.end2:
1561
if FORCE_STATIC eq 1
1562
	cmp dword[static_lenb],0
1563
	jl .end3 ;else if (..>=0) ;force static trees
1564
else
1565
	cmp word[edi+deflate_state.strategy],Z_FIXED
1566
	je @f
1567
	mov eax,[opt_lenb]
1568
	cmp [static_lenb],eax
1569
	je @f ;else if (..==.. || ..==..)
1570
		jmp .end3
1571
	@@:
1572
end if
1573
		mov eax,STATIC_TREES shl 1
1574
		add eax,[last]
1575
		stdcall send_bits, edi, eax, 3
1576
		stdcall compress_block, edi, static_ltree, static_dtree
1577
if DEBUG eq 1
1578
		mov eax,[edi+deflate_state.static_len]
1579
		add eax,3
1580
		add [edi+deflate_state.compressed_len],eax
1581
end if
1582
		jmp .end4
1583
	.end3: ;else
1584
		mov eax,DYN_TREES shl 1
1585
		add eax,[last]
1586
		stdcall send_bits, edi, eax, 3
1587
		mov eax,[max_blindex]
1588
		inc eax
1589
		push eax
1590
		mov eax,[edi+deflate_state.d_desc.max_code]
1591
		inc eax
1592
		push eax
1593
		mov eax,[edi+deflate_state.l_desc.max_code]
1594
		inc eax
1595
		stdcall send_all_trees, edi, eax ;, ..., ...
1596
		mov eax,edi
1597
		add eax,deflate_state.dyn_dtree
1598
		push eax
1599
		add eax,deflate_state.dyn_ltree-deflate_state.dyn_dtree
1600
		stdcall compress_block, edi, eax ;, ...
1601
if DEBUG eq 1
1602
		mov eax,[edi+deflate_state.opt_len]
1603
		add eax,3
1604
		add [edi+deflate_state.compressed_len],eax
1605
end if
1606
	.end4:
1607
;    Assert (s->compressed_len == s->bits_sent, "bad compressed size");
1608
	; The above check is made mod 2^32, for files larger than 512 MB
1609
	; and uLong implemented on 32 bits.
1610
 
1611
	stdcall init_block,edi
1612
 
1613
	cmp dword[last],0
1614
	je @f ;if (..)
1615
		stdcall bi_windup,edi
1616
if DEBUG eq 1
1617
		add [edi+deflate_state.compressed_len],7 ;align on byte boundary
1618
end if
1619
	@@:
1620
;    Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1621
;           s->compressed_len-7*last));
1622
	ret
1623
endp
1624
 
1625
; ===========================================================================
1626
; Save the match info and tally the frequency counts. Return true if
1627
; the current block must be flushed.
1628
 
1629
;int (s, dist, lc)
1630
;    deflate_state* s
1631
;    unsigned dist ;distance of matched string
1632
;    unsigned lc   ;match length-MIN_MATCH or unmatched char (if dist==0)
1633
align 4
1634
proc _tr_tally uses ebx edi, s:dword, dist:dword, lc:dword
1635
	mov edi,[s]
1636
	mov eax,[edi+deflate_state.last_lit]
1637
	shl eax,1
1638
	add eax,[edi+deflate_state.d_buf]
1639
	mov ebx,[dist]
1640
	mov word[eax],bx
1641
	mov eax,[edi+deflate_state.last_lit]
1642
	add eax,[edi+deflate_state.l_buf]
1643
	mov ebx,[lc]
1644
	mov byte[eax],bl
1645
	inc dword[edi+deflate_state.last_lit]
1646
	cmp dword[dist],0
1647
	jne @f ;if (..==0)
1648
		; lc is the unmatched char
1649
		mov eax,[lc]
6851 IgorA 1650
		inc word[edi+sizeof.ct_data*eax+deflate_state.dyn_ltree+Freq]
6617 IgorA 1651
		jmp .end0
6815 IgorA 1652
align 4
6617 IgorA 1653
	@@: ;else
1654
		inc dword[edi+deflate_state.matches]
1655
		; Here, lc is the match length - MIN_MATCH
1656
		dec dword[dist] ;dist = match distance - 1
1657
		MAX_DIST edi
1658
		cmp word[dist],ax
1659
		jge @f
1660
		cmp word[lc],MAX_MATCH-MIN_MATCH
1661
		jg @f
1662
		d_code [dist]
1663
		cmp ax,D_CODES
1664
		jl .end2
1665
		@@:
6639 IgorA 1666
			zlib_assert '_tr_tally: bad match' ;Assert(..<.. && ..<=.. && ..<..)
6617 IgorA 1667
		.end2:
1668
		mov eax,[lc]
6815 IgorA 1669
		movzx eax,byte[eax+_length_code]
6851 IgorA 1670
		inc word[edi+sizeof.ct_data*eax+deflate_state.dyn_ltree+sizeof.ct_data*(LITERALS+1)+Freq]
6617 IgorA 1671
		d_code [dist]
6851 IgorA 1672
		inc word[edi+sizeof.ct_data*eax+deflate_state.dyn_dtree+Freq]
6617 IgorA 1673
	.end0:
1674
 
1675
if TRUNCATE_BLOCK eq 1
1676
	; Try to guess if it is profitable to stop the current block here
1677
	mov eax,[edi+deflate_state.last_lit]
1678
	and eax,0x1fff
6847 IgorA 1679
	jnz .end1
6617 IgorA 1680
	cmp word[edi+deflate_state.level],2
6847 IgorA 1681
	jle .end1 ;if (..==0 && ..>..)
6617 IgorA 1682
	; Compute an upper bound for the compressed length
1683
;        ulg out_length = (ulg)s->last_lit*8L;
1684
;        ulg in_length = (ulg)((long)s->strstart - s->block_start);
1685
;        int dcode;
1686
;        for (dcode = 0; dcode < D_CODES; dcode++) {
1687
;            out_length += (ulg)s->dyn_dtree[dcode].Freq *
1688
;                (5L+extra_dbits[dcode]);
1689
;        }
1690
;        out_length >>= 3;
1691
;        Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1692
;               s->last_lit, in_length, out_length,
1693
;               100L - out_length*100L/in_length));
1694
;        if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
1695
	.end1:
1696
end if
6851 IgorA 1697
	mov ebx,[edi+deflate_state.lit_bufsize]
1698
	dec ebx
6617 IgorA 1699
	xor eax,eax
6851 IgorA 1700
	cmp [edi+deflate_state.last_lit],ebx
1701
	sete al ;return (..==..)
1702
 
6617 IgorA 1703
	; We avoid equality with lit_bufsize because of wraparound at 64K
1704
	; on 16 bit machines and because stored blocks are restricted to
1705
	; 64K-1 bytes.
1706
	ret
1707
endp
1708
 
1709
; ===========================================================================
1710
; Send the block data compressed using the given Huffman trees
1711
 
1712
;void (s, ltree, dtree)
6799 IgorA 1713
;    deflate_state* s
6617 IgorA 1714
;    ct_data *ltree ;literal tree
1715
;    ct_data *dtree ;distance tree
1716
align 4
1717
proc compress_block uses eax edi, s:dword, ltree:dword, dtree:dword
1718
locals
1719
	dist  dd ? ;unsigned ;distance of matched string
1720
	lc    dd ? ;int      ;match length or unmatched char (if dist == 0)
1721
	lx    dd 0 ;unsigned ;running index in l_buf
1722
	u_code dd ? ;unsigned ;the code to send
1723
endl
1724
	mov edi,[s]
1725
	cmp dword[edi+deflate_state.last_lit],0
1726
	je .end0 ;if (..!=0)
1727
	.cycle0: ; do
1728
		mov eax,[lx]
1729
		shl eax,1
1730
		add eax,[edi+deflate_state.d_buf]
1731
		movzx eax,word[eax]
1732
		mov [dist],eax
1733
		mov eax,[lx]
1734
		add eax,[edi+deflate_state.l_buf]
1735
		movzx eax,byte[eax]
1736
		mov [lc],eax
1737
		inc dword[lx]
1738
		cmp dword[dist],0
1739
		jne @f ;if (..==0)
1740
			send_code edi, [lc], [ltree] ;send a literal byte
1741
;            Tracecv(isgraph(lc), (stderr," '%c' ", lc));
1742
			jmp .end1
1743
		@@: ;else
1744
			; Here, lc is the match length - MIN_MATCH
1745
			mov eax,[lc]
1746
			add eax,_length_code
1747
			movzx eax,byte[eax]
1748
			mov [u_code],eax
1749
			add eax,LITERALS+1
1750
			send_code edi, eax, [ltree] ;send the length code
1751
			mov eax,[u_code]
6847 IgorA 1752
			mov eax,[4*eax+extra_lbits]
1753
			test eax,eax
1754
			jz @f ;if (..!=0)
1755
				push eax ;extra
6617 IgorA 1756
				mov eax,[u_code]
6847 IgorA 1757
				mov eax,[4*eax+base_length]
6617 IgorA 1758
				sub [lc],eax
6847 IgorA 1759
				stdcall send_bits, edi, [lc] ;, ... ;send the extra length bits
6617 IgorA 1760
			@@:
1761
			dec dword[dist] ;dist is now the match distance - 1
1762
			d_code [dist]
1763
			mov [u_code],eax
1764
			cmp eax,D_CODES
1765
			jl @f
6639 IgorA 1766
				zlib_assert 'bad d_code' ;Assert(..<..)
6617 IgorA 1767
			@@:
1768
			send_code edi, [u_code], [dtree] ;send the distance code
1769
			mov eax,[u_code]
6847 IgorA 1770
			mov eax,[4*eax+extra_dbits]
1771
			test eax,eax
1772
			jz .end1 ;if (..!=0)
1773
				push eax ;extra
6617 IgorA 1774
				mov eax,[u_code]
6847 IgorA 1775
				mov eax,[4*eax+base_dist]
6617 IgorA 1776
				sub [dist],eax
6847 IgorA 1777
				stdcall send_bits, edi, [dist] ;, ... ;send the extra distance bits
6617 IgorA 1778
		.end1: ;literal or match pair ?
1779
 
1780
		; Check that the overlay between pending_buf and d_buf+l_buf is ok:
1781
		mov eax,[lx]
1782
		shl eax,1
1783
		add eax,[edi+deflate_state.lit_bufsize]
6741 IgorA 1784
		cmp [edi+deflate_state.pending],eax
6617 IgorA 1785
		jl @f
6639 IgorA 1786
			zlib_assert 'pendingBuf overflow' ;Assert(..<..)
6617 IgorA 1787
		@@:
1788
		mov eax,[edi+deflate_state.last_lit]
1789
		cmp [lx],eax
6851 IgorA 1790
		jb .cycle0 ;while (..<..)
6617 IgorA 1791
align 4
1792
	.end0:
1793
 
1794
	send_code edi, END_BLOCK, [ltree]
1795
	ret
1796
endp
1797
 
1798
; ===========================================================================
1799
; Check if the data type is TEXT or BINARY, using the following algorithm:
1800
; - TEXT if the two conditions below are satisfied:
1801
;    a) There are no non-portable control characters belonging to the
1802
;       "black list" (0..6, 14..25, 28..31).
1803
;    b) There is at least one printable character belonging to the
1804
;       "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
1805
; - BINARY otherwise.
1806
; - The following partially-portable control characters form a
1807
;   "gray list" that is ignored in this detection algorithm:
1808
;   (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
1809
; IN assertion: the fields Freq of dyn_ltree are set.
1810
 
6851 IgorA 1811
;int (deflate_state* s)
6617 IgorA 1812
align 4
1813
proc detect_data_type uses ebx ecx edi, s:dword
1814
	; black_mask is the bit mask of black-listed bytes
1815
	; set bits 0..6, 14..25, and 28..31
1816
	; 0xf3ffc07f = binary 11110011111111111100000001111111
1817
locals
1818
	black_mask dd 0xf3ffc07f
1819
endl
1820
	mov edi,[s]
1821
 
1822
	; Check for non-textual ("black-listed") bytes.
1823
	xor ecx,ecx
1824
	mov ebx,edi
1825
	add ebx,deflate_state.dyn_ltree+Freq
1826
	.cycle0:
1827
	cmp ecx,31
1828
	jg .cycle0end ;for (..;..<=..;..,..)
1829
		bt dword[black_mask],0
1830
		jnc @f
1831
		cmp word[ebx],0
1832
		je @f ;if (..&.. && ..!=0)
1833
			mov eax,Z_BINARY
1834
			jmp .end_f
1835
		@@:
1836
		shr dword[black_mask],1
1837
		add ebx,sizeof.ct_data
1838
		inc ecx
1839
		jmp .cycle0
1840
	.cycle0end:
1841
 
1842
	; Check for textual ("white-listed") bytes.
1843
	mov ebx,edi
1844
	add ebx,deflate_state.dyn_ltree+Freq+9*sizeof.ct_data
1845
	cmp word[ebx],0
1846
	jne @f
1847
	add ebx,sizeof.ct_data
1848
	cmp word[ebx],0
1849
	jne @f
1850
	add ebx,3*sizeof.ct_data
1851
	cmp word[ebx],0
1852
	je .end0
1853
	@@: ;if (..!=0 || ..!=0 || ..!= 0)
1854
		mov eax,Z_TEXT
1855
		jmp .end_f
1856
	.end0:
1857
	mov ecx,32
1858
	mov ebx,edi
6799 IgorA 1859
	add ebx,deflate_state.dyn_ltree+Freq+32*sizeof.ct_data
6617 IgorA 1860
	.cycle1:
1861
	cmp ecx,LITERALS
1862
	jge .cycle1end ;for (..;..<..;..,..)
1863
		cmp word[ebx],0
1864
		je @f ;if (..!=0)
1865
			mov eax,Z_TEXT
1866
			jmp .end_f
1867
		@@:
1868
		add ebx,sizeof.ct_data
1869
		inc ecx
1870
		jmp .cycle1
1871
	.cycle1end:
1872
 
1873
	; There are no "black-listed" or "white-listed" bytes:
1874
	; this stream either is empty or has tolerated ("gray-listed") bytes only.
1875
 
1876
	mov eax,Z_BINARY
1877
.end_f:
1878
	ret
1879
endp
1880
 
1881
; ===========================================================================
1882
; Reverse the first len bits of a code, using straightforward code (a faster
1883
; method would use a table)
1884
; IN assertion: 1 <= len <= 15
1885
 
1886
;unsigned (code, len)
1887
;    unsigned code ;the value to invert
1888
;    int len       ;its bit length
1889
align 4
1890
proc bi_reverse uses ebx, p1code:dword, len:dword
1891
	xor eax,eax
1892
	@@: ;do
1893
		mov ebx,[p1code]
1894
		and ebx,1
1895
		or eax,ebx
1896
		shr dword[p1code],1
1897
		shl eax,1
1898
		dec dword[len]
1899
		cmp dword[len],0
1900
		jg @b ;while (..>..)
6813 IgorA 1901
	shr eax,1
6617 IgorA 1902
	ret
1903
endp
1904
 
1905
; ===========================================================================
1906
; Flush the bit buffer, keeping at most 7 bits in it.
1907
 
6851 IgorA 1908
;void (deflate_state* s)
6617 IgorA 1909
align 4
1910
proc bi_flush uses eax ecx edi, s:dword
1911
	mov edi,[s]
1912
	cmp dword[edi+deflate_state.bi_valid],16
1913
	jne @f ;if (..==..)
1914
		mov cx,[edi+deflate_state.bi_buf]
1915
		put_short edi,cx
1916
		mov word[edi+deflate_state.bi_buf],0
1917
		mov dword[edi+deflate_state.bi_valid],0
1918
		jmp .end0
1919
	@@: ;else if (..>=..)
1920
		cmp dword[edi+deflate_state.bi_valid],8
1921
		jl .end0
1922
		mov cl,byte[edi+deflate_state.bi_buf]
1923
		put_byte edi,cl
1924
		shr word[edi+deflate_state.bi_buf],8
1925
		sub dword[edi+deflate_state.bi_valid],8
1926
	.end0:
1927
	ret
1928
endp
1929
 
1930
; ===========================================================================
1931
; Flush the bit buffer and align the output on a byte boundary
1932
 
6847 IgorA 1933
;void (deflate_state* s)
6617 IgorA 1934
align 4
1935
proc bi_windup uses eax ecx edi, s:dword
1936
	mov edi,[s]
1937
	cmp dword[edi+deflate_state.bi_valid],8
1938
	jle @f ;if (..>..)
1939
		mov cx,[edi+deflate_state.bi_buf]
1940
		put_short edi, cx
1941
		jmp .end0
1942
	@@: ;else if (..>0)
1943
		cmp dword[edi+deflate_state.bi_valid],0
1944
		jle .end0
1945
		mov cl,byte[edi+deflate_state.bi_buf]
1946
		put_byte edi, cl
1947
	.end0:
1948
	mov word[edi+deflate_state.bi_buf],0
1949
	mov dword[edi+deflate_state.bi_valid],0
1950
if DEBUG eq 1
1951
	mov eax,[edi+deflate_state.bits_sent]
1952
	add eax,7
1953
	and eax,not 7
1954
	mov [edi+deflate_state.bits_sent],eax
1955
end if
1956
	ret
1957
endp
1958
 
1959
; ===========================================================================
1960
; Copy a stored block, storing first the length and its
1961
; one's complement if requested.
1962
 
1963
;void (s, buf, len, header)
1964
;    deflate_state* s
1965
;    charf    *buf   ;the input data
1966
;    unsigned len    ;its length
1967
;    int      header ;true if block header must be written
1968
align 4
1969
proc copy_block uses eax ebx ecx edi esi, s:dword, buf:dword, len:dword, p4header:dword
1970
	mov edi,[s]
1971
	stdcall bi_windup,edi ;align on byte boundary
1972
 
1973
	cmp dword[p4header],0
1974
	je @f ;if (..)
1975
		mov ecx,[len]
1976
		put_short edi, cx
1977
		not cx
1978
		put_short edi, cx
1979
if DEBUG eq 1
1980
		add dword[edi+deflate_state.bits_sent],2*16
1981
end if
1982
	@@:
1983
if DEBUG eq 1
1984
	mov ecx,[len]
1985
	shl ecx,3
1986
	add [edi+deflate_state.bits_sent],ecx
1987
end if
1988
	mov ecx,[len]
6851 IgorA 1989
;	test ecx,ecx
1990
;	jz .end_f
6617 IgorA 1991
	mov esi,[buf]
6815 IgorA 1992
	jmp .end0
1993
align 4
6617 IgorA 1994
	@@: ;while (len--)
1995
		lodsb
1996
		mov bl,al
1997
		put_byte edi, bl
6815 IgorA 1998
	.end0:
6617 IgorA 1999
		loop @b
6851 IgorA 2000
;	.end_f:
6617 IgorA 2001
	ret
2002
endp