1;===========================================================================
2; Copyright (c) 1990-2005 Info-ZIP.  All rights reserved.
3;
4; See the accompanying file LICENSE, version 2005-Feb-10 or later
5; (the contents of which are also included in zip.h) for terms of use.
6; If, for some reason, all these files are missing, the Info-ZIP license
7; also may be found at:  ftp://ftp.info-zip.org/pub/infozip/license.html
8;===========================================================================
9;
10; match32.asm by Jean-loup Gailly.
11
12; match32.asm, optimized version of longest_match() in deflate.c
13; To be used only with 32 bit flat model. To simplify the code, the option
14; -DDYN_ALLOC is not supported.
15; This file is only optional. If you don't have an assembler, use the
16; C version (add -DNO_ASM to CFLAGS in makefile and remove match.o
17; from OBJI). If you have reduced WSIZE in zip.h, then make sure this is
18; assembled with an equivalent -DWSIZE=<whatever>.
19
20; Caution: this module works for IBM's C/C++ compiler versions 2 and 3
21; and for Watcom's 32-bit C/C++ compiler. Both pass the first (and only)
22; argument for longest_match in the EAX register, not on the stack, with
23; the default calling conventions (_System would use the stack).
24;
25;==============================================================================
26;
27; Do NOT assemble this source if external crc32 routine from zlib gets used.
28;
29    IFNDEF USE_ZLIB
30;
31        .386
32
33        name    match
34
35BSS32   segment  dword USE32 public 'BSS'
36        extrn   window       : byte
37        extrn   prev         : word
38        extrn   prev_length  : dword
39        extrn   strstart     : dword
40        extrn   match_start  : dword
41        extrn   max_chain_length : dword
42        extrn   good_match   : dword
43        extrn   nice_match   : dword
44BSS32   ends
45
46CODE32  segment dword USE32 public 'CODE'
47        assume cs:CODE32, ds:FLAT, ss:FLAT
48
49        public  match_init
50        public  longest_match
51
52    ifndef      WSIZE
53        WSIZE         equ 32768         ; keep in sync with zip.h !
54    endif
55        MIN_MATCH     equ 3
56        MAX_MATCH     equ 258
57        MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
58        MAX_DIST      equ (WSIZE-MIN_LOOKAHEAD)
59
60; initialize or check the variables used in match.asm.
61
62match_init proc near
63        ret
64match_init endp
65
66; -----------------------------------------------------------------------
67; Set match_start to the longest match starting at the given string and
68; return its length. Matches shorter or equal to prev_length are discarded,
69; in which case the result is equal to prev_length and match_start is
70; garbage.
71; IN assertions: cur_match is the head of the hash chain for the current
72;   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
73
74; int longest_match(cur_match)
75
76longest_match proc near
77
78        ; return address                ; esp+16
79        push    ebp                     ; esp+12
80        push    edi                     ; esp+8
81        push    esi                     ; esp+4
82
83        lea     ebx,window
84        add     ebx,2
85        window_off equ dword ptr [esp]
86        push    ebx                     ; esp
87
88;       match        equ esi
89;       scan         equ edi
90;       chain_length equ ebp
91;       best_len     equ ebx
92;       limit        equ edx
93
94        mov     esi,eax                 ; cur_match
95        mov     edx,strstart
96        mov     ebp,max_chain_length    ; chain_length = max_chain_length
97        mov     edi,edx
98        sub     edx,MAX_DIST            ; limit = strstart-MAX_DIST
99        cld                             ; string ops increment esi and edi
100        jae     short limit_ok
101        sub     edx,edx                 ; limit = NIL
102limit_ok:
103        add     edi,window_off          ; edi = offset(window + strstart + 2)
104        mov     ebx,prev_length         ; best_len = prev_length
105        mov     cx,[edi-2]              ; cx = scan[0..1]
106        mov     ax,[ebx+edi-3]          ; ax = scan[best_len-1..best_len]
107        cmp     ebx,good_match          ; do we have a good match already?
108        jb      do_scan
109        shr     ebp,2                   ; chain_length >>= 2
110        jmp     short do_scan
111
112        align   4                       ; align destination of branch
113long_loop:
114; at this point, edi == scan+2, esi == cur_match
115        mov     ax,[ebx+edi-3]          ; ax = scan[best_len-1..best_len]
116        mov     cx,[edi-2]              ; cx = scan[0..1]
117short_loop:
118; at this point, edi == scan+2, esi == cur_match,
119; ax = scan[best_len-1..best_len] and cx = scan[0..1]
120        and     esi,WSIZE-1             ; not needed if WSIZE=32768
121        dec     ebp                     ; --chain_length
122        shl     esi,1                   ; cur_match as word index
123        mov     si,prev[esi]            ; cur_match = prev[cur_match]
124                                        ; top word of esi is still 0
125        jz      the_end
126        cmp     esi,edx                 ; cur_match <= limit ?
127        jbe     short the_end
128do_scan:
129        cmp     ax,word ptr window[ebx+esi-1]   ; check match at best_len-1
130        jne     short_loop
131        cmp     cx,word ptr window[esi]         ; check min_match_length match
132        jne     short_loop
133
134        add     esi,window_off          ; esi = match
135        mov     ecx,(MAX_MATCH-2)/2     ; scan for at most MAX_MATCH bytes
136        mov     eax,edi                 ; eax = scan+2
137        repe    cmpsw                   ; loop until mismatch
138        je      maxmatch                ; match of length MAX_MATCH?
139mismatch:
140        mov     cl,[edi-2]              ; mismatch on first or second byte?
141        xchg    eax,edi                 ; edi = scan+2, eax = end of scan
142        sub     cl,[esi-2]              ; cl = 0 if first bytes equal
143        sub     eax,edi                 ; eax = len
144        sub     esi,window_off          ; esi = match - (2 + offset(window))
145        sub     esi,eax                 ; esi = cur_match (= match - len)
146        sub     cl,1                    ; set carry if cl == 0 (can't use DEC)
147        adc     eax,0                   ; eax = carry ? len+1 : len
148        cmp     eax,ebx                 ; len > best_len ?
149        jle     long_loop
150        mov     match_start,esi         ; match_start = cur_match
151        mov     ebx,eax                 ; ebx = best_len = len
152    ifdef FULL_SEARCH
153        cmp     eax,MAX_MATCH           ; len >= MAX_MATCH ?
154    else
155        cmp     eax,nice_match          ; len >= nice_match ?
156    endif
157        jl      long_loop
158the_end:
159        mov     eax,ebx                 ; result = eax = best_len
160        pop     ebx
161        pop     esi
162        pop     edi
163        pop     ebp
164        ret
165maxmatch:                               ; come here if maximum match
166        cmpsb                           ; increment esi and edi
167        jmp     mismatch                ; force match_length = MAX_LENGTH
168
169longest_match endp
170
171CODE32  ends
172;
173    ENDIF ; !USE_ZLIB
174;
175        end
176