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
|