summaryrefslogtreecommitdiff
path: root/Build/source/utils/gzip/msdos/match.asm
blob: cee59c5962dc57852764a957979fc5ca7022827c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
; match.asm -- optional optimized asm version of longest match in deflate.c
; Copyright (C) 1992-1993 Jean-loup Gailly
; This is free software; you can redistribute it and/or modify it under the
; terms of the GNU General Public License, see the file COPYING.
;
; Must be assembled with masm -ml. To be used only with C compact model
; or large model. (For large model, assemble with -D__LARGE__).
; This file is only optional. If you don't have masm or tasm, use the
; C version (add -DNO_ASM to CFLAGS in makefile.msc and remove match.obj
; from OBJI). If you have reduced WSIZE in zip.h, then change its value
; below.
;
; Turbo C 2.0 does not support static allocation of more than 64K bytes per
; file, and does not have SS == DS. So TC and BC++ users must use:
;   tasm -ml -DDYN_ALLOC -DSS_NEQ_DS match;
;
; To simplify the code, the option -DDYN_ALLOC is supported for OS/2
; only if the arrays are guaranteed to have zero offset (allocated by
; halloc). We also require SS==DS. This is satisfied for MSC but not Turbo C.

; $Id: match.asm,v 0.6 1993/01/21 18:49:05 jloup Exp $

        name    match

ifndef DYN_ALLOC
        extrn   _prev         : word
        extrn   _window       : byte
        prev    equ  _prev    ; offset part
        window  equ  _window
endif

_DATA    segment  word public 'DATA'
        extrn   _nice_match   : word
        extrn   _match_start  : word
        extrn   _prev_length  : word
        extrn   _good_match   : word
        extrn   _strstart     : word
        extrn   _max_chain_length : word
ifdef DYN_ALLOC
        extrn   _prev         : word
        extrn   _window       : word
        prev    equ 0         ; offset forced to zero
        window  equ 0
        window_seg equ _window[2]
	window_off equ 0
else
	wseg    dw seg _window
        window_seg equ wseg
	window_off equ offset _window
endif
_DATA    ends

DGROUP  group _DATA

_TEXT   segment word public 'CODE'
        assume  cs: _TEXT, ds: DGROUP

	public _match_init
        public _longest_match

	MIN_MATCH     equ 3
        MAX_MATCH     equ 258
	WSIZE         equ 32768		; keep in sync with zip.h !
	MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
	MAX_DIST      equ (WSIZE-MIN_LOOKAHEAD)

prev_ptr    dw  seg _prev		; pointer to the prev array
ifdef SS_NEQ_DS
    match_start dw  0			; copy of _match_start if SS != DS
    nice_match  dw  0			; copy of _nice_match  if SS != DS
endif

; initialize or check the variables used in match.asm.

ifdef __LARGE__
_match_init proc far			; 'proc far' for large model
else
_match_init proc near			; 'proc near' for compact model
endif
ifdef SS_NEQ_DS
        ma_start equ cs:match_start	; does not work on OS/2
        nice     equ cs:nice_match
	mov	ax,_nice_match
	mov     cs:nice_match,ax       	; ugly write to code, crash on OS/2
else
	assume ss: DGROUP
        ma_start equ ss:_match_start
        nice     equ ss:_nice_match
        mov     ax,ds
        mov     bx,ss
        cmp     ax,bx                   ; SS == DS?
        jne     error
endif
ifdef DYN_ALLOC
	cmp	_prev[0],0		; verify zero offset
	jne	error
	cmp	_window[0],0
	jne	error
  ifdef SS_NEQ_DS
	mov	ax,_prev[2]		; segment value
	mov     cs:prev_ptr,ax		; ugly write to code, crash on OS/2
        prev_seg  equ cs:prev_ptr
  else
        prev_seg  equ ss:_prev[2]	; works on OS/2 if SS == DS
  endif
else
        prev_seg  equ cs:prev_ptr
endif
	ret
ifdef __LARGE__
	extrn   _exit : far		; 'far' for large model
else
	extrn   _exit : near		; 'near' for compact model
endif
error:  call    _exit

_match_init endp

; -----------------------------------------------------------------------
; Set match_start to the longest match starting at the given string and
; return its length. Matches shorter or equal to prev_length are discarded,
; in which case the result is equal to prev_length and match_start is
; garbage.
; IN assertions: cur_match is the head of the hash chain for the current
;   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1

; int longest_match(cur_match)

ifdef __LARGE__
_longest_match  proc far		 ; 'proc far' for large model
else
_longest_match  proc near		 ; 'proc near' for compact model
endif
        push    bp
        mov     bp,sp
        push    di
	push	si
	push	ds

ifdef __LARGE__
        cur_match    equ word ptr [bp+6] ; [bp+6] for large model
else
        cur_match    equ word ptr [bp+4] ; [bp+4] for compact model
endif

;       window	     equ es:window (es:0 for DYN_ALLOC)
;       prev	     equ ds:prev
;       match        equ es:si
;       scan         equ es:di
;       chain_length equ bp
;       best_len     equ bx
;       limit        equ dx

	mov	si,cur_match            ; use bp before it is destroyed
        mov     bp,_max_chain_length    ; chain_length = max_chain_length
	mov	di,_strstart
	mov	dx,di
	sub	dx,MAX_DIST             ; limit = strstart-MAX_DIST
	jae	limit_ok
	sub	dx,dx			; limit = NIL
limit_ok:
        add     di,2+window_off         ; di = offset(window + strstart + 2)
        mov     bx,_prev_length         ; best_len = prev_length
	mov     es,window_seg
        mov     ax,es:[bx+di-3]         ; ax = scan[best_len-1..best_len]
        mov     cx,es:[di-2]            ; cx = scan[0..1]
	cmp	bx,_good_match		; do we have a good match already?
        mov     ds,prev_seg    		; (does not destroy the flags)
        assume  ds: nothing
        jb      do_scan			; good match?
	shr	bp,1			; chain_length >>= 2
	shr	bp,1
        jmp     short do_scan

        even                            ; align destination of branch
long_loop:
; at this point, ds:di == scan+2, ds:si == cur_match
        mov     ax,[bx+di-3]            ; ax = scan[best_len-1..best_len]
        mov     cx,[di-2]               ; cx = scan[0..1]
        mov     ds,prev_seg    		; reset ds to address the prev array
short_loop:
; at this point, di == scan+2, si = cur_match,
; ax = scan[best_len-1..best_len] and cx = scan[0..1]
if (WSIZE-32768)
        and     si,WSIZE-1              ; not needed if WSIZE=32768
endif
        shl     si,1                    ; cur_match as word index
        mov     si,prev[si]             ; cur_match = prev[cur_match]
        cmp     si,dx			; cur_match <= limit ?
        jbe     the_end
        dec     bp                      ; --chain_length
        jz      the_end
do_scan:
        cmp     ax,word ptr es:window[bx+si-1] ; check match at best_len-1
        jne     short_loop
        cmp     cx,word ptr es:window[si]      ; check min_match_length match
        jne     short_loop

        lea     si,window[si+2]         ; si = match
        mov     ax,di                   ; ax = scan+2
        mov     cx,es
        mov     ds,cx			; ds = es = window
        mov     cx,(MAX_MATCH-2)/2      ; scan for at most MAX_MATCH bytes
        repe    cmpsw                   ; loop until mismatch
        je      maxmatch                ; match of length MAX_MATCH?
mismatch:
        mov     cl,[di-2]               ; mismatch on first or second byte?
        sub     cl,[si-2]               ; cl = 0 if first bytes equal
        xchg    ax,di                   ; di = scan+2, ax = end of scan
        sub     ax,di                   ; ax = len
	sub	si,ax			; si = cur_match + 2 + offset(window)
	sub	si,2+window_off         ; si = cur_match
        sub     cl,1                    ; set carry if cl == 0 (can't use DEC)
        adc     ax,0                    ; ax = carry ? len+1 : len
        cmp     ax,bx                   ; len > best_len ?
        jle     long_loop
        mov     ma_start,si             ; match_start = cur_match
        mov     bx,ax                   ; bx = best_len = len
        cmp     ax,nice                 ; len >= nice_match ?
        jl      long_loop
the_end:
	pop	ds
        assume  ds: DGROUP
ifdef SS_NEQ_DS
	mov	ax,ma_start		; garbage if no match found
	mov	ds:_match_start,ax
endif
        pop     si
        pop     di
        pop     bp
        mov     ax,bx                   ; result = ax = best_len
        ret
maxmatch:                               ; come here if maximum match
        cmpsb                           ; increment si and di
        jmp     mismatch                ; force match_length = MAX_LENGTH
        
_longest_match  endp

_TEXT   ends
end