Debian Codegraph @

msdos/match.asm

raw
1 ;===========================================================================
2 ; Copyright (c) 1990-2008 Info-ZIP. All rights reserved.
3 ;
4 ; See the accompanying file LICENSE, version 2007-Mar-04 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 ; match.asm by Jean-loup Gailly.
11
12 ; match.asm, optimized version of longest_match() in deflate.c
13 ; Must be assembled with masm -ml. To be used only with C compact model
14 ; or large model. (For large model, assemble with -D__LARGE__).
15 ; This file is only optional. If you don't have masm or tasm, use the
16 ; C version (add -DNO_ASM to CFLAGS in makefile.msc and remove match.obj
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 ; The code has been prepared for two different C compiler calling conventions
21 ; and contains some support for dynamically allocated working space.
22 ; The different environments are selected by two conditional flags:
23 ; DYN_ALLOC : select support for malloc'ed working space
24 ; SS_NEQ_DS : relaxes assumption that stack and default data segments
25 ; are identical
26 ; When SS_NEQ_DS is defined, the code segment is used to store some
27 ; local variables. This (bad) coding practice is very likely to break any
28 ; `segment protection scheme', it will most probably only work for real
29 ; mode programs.
30 ;
31 ; Turbo C 2.0 does not support static allocation of more than 64K bytes per
32 ; file, and does not have SS == DS. So TC and BC++ users must use:
33 ; tasm -ml -DDYN_ALLOC -DSS_NEQ_DS match;
34 ;
35 ; To simplify the code, the option -DDYN_ALLOC is supported for OS/2
36 ; only if the arrays are guaranteed to have zero offset (allocated by
37 ; halloc). We also require SS==DS. This is satisfied for MSC but not Turbo C.
38 ;
39 ; Per default, test code is included to check if the above requirements are
40 ; fulfilled. This test code can be disabled by defining the compile time
41 ; option flag NO_SECURE_TESTS when compiling for a production executable.
42 ; This shortens the code size (but the performance gain is neglectable).
43 ; The security tests should remain enabled, when a new C compiler
44 ; and/or a new set of compilation options is tried.
45
46 name match
47
48 ; Do NOT assemble this source if external crc32 routine from zlib gets used.
49 ;
50 ifndef USE_ZLIB
51
52 ifdef DEBUG
53 VERBOSE_INFO EQU 1
54 else
55 ifdef _AS_MSG_
56 VERBOSE_INFO EQU 1
57 else
58 VERBOSE_INFO EQU 0
59 endif
60 endif
61
62 ifndef __SMALL__
63 ifndef __COMPACT__
64 ifndef __MEDIUM__
65 ifndef __LARGE__
66 ifndef __HUGE__
67 ; __SMALL__ EQU 1
68 endif
69 endif
70 endif
71 endif
72 endif
73
74 ifdef __HUGE__
75 ; .MODEL Huge
76 ifndef @CodeSize
77 @CodeSize EQU 1
78 endif
79 ifndef @DataSize
80 @DataSize EQU 1
81 endif
82 Save_DS EQU 1
83 if VERBOSE_INFO
84 if1
85 %out Assembling for C, Huge memory model
86 endif
87 endif
88 else
89 ifdef __LARGE__
90 ; .MODEL Large
91 ifndef @CodeSize
92 @CodeSize EQU 1
93 endif
94 ifndef @DataSize
95 @DataSize EQU 1
96 endif
97 if VERBOSE_INFO
98 if1
99 %out Assembling for C, Large memory model
100 endif
101 endif
102 else
103 ifdef __COMPACT__
104 ; .MODEL Compact
105 ifndef @CodeSize
106 @CodeSize EQU 0
107 endif
108 ifndef @DataSize
109 @DataSize EQU 1
110 endif
111 if VERBOSE_INFO
112 if1
113 %out Assembling for C, Compact memory model
114 endif
115 endif
116 else
117 ifdef __MEDIUM__
118 ; .MODEL Medium
119 ifndef @CodeSize
120 @CodeSize EQU 1
121 endif
122 ifndef @DataSize
123 @DataSize EQU 0
124 endif
125 if VERBOSE_INFO
126 if1
127 %out Assembling for C, Medium memory model
128 endif
129 endif
130 else
131 ; .MODEL Small
132 ifndef @CodeSize
133 @CodeSize EQU 0
134 endif
135 ifndef @DataSize
136 @DataSize EQU 0
137 endif
138 if VERBOSE_INFO
139 if1
140 %out Assembling for C, Small memory model
141 endif
142 endif
143 endif
144 endif
145 endif
146 endif
147
148 if @CodeSize
149 LCOD_OFS EQU 2
150 else
151 LCOD_OFS EQU 0
152 endif
153
154 IF @DataSize
155 LDAT_OFS EQU 2
156 else
157 LDAT_OFS EQU 0
158 endif
159
160 ifdef Save_DS
161 ; (di,si,ds)+(size, return address)
162 SAVE_REGS EQU 6+(4+LCOD_OFS)
163 else
164 ; (di,si)+(size, return address)
165 SAVE_REGS EQU 4+(4+LCOD_OFS)
166 endif
167
168 ;
169 ; Selection of the supported CPU instruction set and initialization
170 ; of CPU type related macros:
171 ;
172 ifdef __586
173 Use_286_code EQU 1
174 Align_Size EQU 16 ; paragraph alignment on Pentium
175 Alig_PARA EQU 1 ; paragraph aligned code segment
176 else
177 ifdef __486
178 Use_286_code EQU 1
179 Align_Size EQU 4 ; dword alignment on 32 bit processors
180 Alig_PARA EQU 1 ; paragraph aligned code segment
181 else
182 ifdef __386
183 Use_286_code EQU 1
184 Align_Size EQU 4 ; dword alignment on 32 bit processors
185 Alig_PARA EQU 1 ; paragraph aligned code segment
186 else
187 ifdef __286
188 Use_286_code EQU 1
189 Align_Size EQU 2 ; word alignment on 16 bit processors
190 Alig_PARA EQU 0 ; word aligned code segment
191 else
192 ifdef __186
193 Use_186_code EQU 1
194 Align_Size EQU 2 ; word alignment on 16 bit processors
195 Alig_PARA EQU 0 ; word aligned code segment
196 else
197 Align_Size EQU 2 ; word alignment on 16 bit processors
198 Alig_PARA EQU 0 ; word aligned code segment
199 endif ;?__186
200 endif ;?__286
201 endif ;?__386
202 endif ;?__486
203 endif ;?__586
204
205 ifdef Use_286_code
206 .286
207 Have_80x86 EQU 1
208 else
209 ifdef Use_186_code
210 .186
211 Have_80x86 EQU 1
212 else
213 .8086
214 Have_80x86 EQU 0
215 endif ;?Use_186_code
216 endif ;?Use_286_code
217
218 ifndef DYN_ALLOC
219 extrn _prev : word
220 extrn _window : byte
221 prev equ _prev ; offset part
222 window equ _window
223 endif
224
225 _DATA segment word public 'DATA'
226 extrn _nice_match : word
227 extrn _match_start : word
228 extrn _prev_length : word
229 extrn _good_match : word
230 extrn _strstart : word
231 extrn _max_chain_length : word
232 ifdef DYN_ALLOC
233 extrn _prev : word
234 extrn _window : word
235 prev equ 0 ; offset forced to zero
236 window equ 0
237 window_seg equ _window[2]
238 window_off equ 0
239 else
240 wseg dw seg _window
241 window_seg equ wseg
242 window_off equ offset _window
243 endif
244 _DATA ends
245
246 DGROUP group _DATA
247
248 if @CodeSize
249 if Alig_PARA
250 MATCH_TEXT SEGMENT PARA PUBLIC 'CODE'
251 else
252 MATCH_TEXT SEGMENT WORD PUBLIC 'CODE'
253 endif
254 assume cs: MATCH_TEXT, ds: DGROUP
255 else ;!@CodeSize
256 if Alig_PARA
257 _TEXT segment para public 'CODE'
258 else
259 _TEXT segment word public 'CODE'
260 endif
261 assume cs: _TEXT, ds: DGROUP
262 endif ;?@CodeSize
263
264 public _match_init
265 public _longest_match
266
267 ifndef WSIZE
268 WSIZE equ 32768 ; keep in sync with zip.h !
269 endif
270 MIN_MATCH equ 3
271 MAX_MATCH equ 258
272 MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
273 MAX_DIST equ (WSIZE-MIN_LOOKAHEAD)
274
275 ifdef DYN_ALLOC
276 ifdef SS_NEQ_DS
277 prev_ptr dw seg _prev ; pointer to the prev array
278 endif
279 else
280 prev_ptr dw seg _prev ; pointer to the prev array
281 endif
282 ifdef SS_NEQ_DS
283 match_start dw 0 ; copy of _match_start if SS != DS
284 nice_match dw 0 ; copy of _nice_match if SS != DS
285 endif
286
287 ; initialize or check the variables used in match.asm.
288
289 if @CodeSize
290 _match_init proc far ; 'proc far' for large model
291 else
292 _match_init proc near ; 'proc near' for compact model
293 endif
294 ifdef SS_NEQ_DS
295 ma_start equ cs:match_start ; does not work on OS/2
296 nice equ cs:nice_match
297 else
298 assume ss: DGROUP
299 ma_start equ ss:_match_start
300 nice equ ss:_nice_match
301 ifndef NO_SECURE_TESTS
302 mov ax,ds
303 mov bx,ss
304 cmp ax,bx ; SS == DS?
305 jne fatal_err
306 endif
307 endif
308 ifdef DYN_ALLOC
309 ifndef NO_SECURE_TESTS
310 cmp _prev[0],0 ; verify zero offset
311 jne fatal_err
312 cmp _window[0],0
313 jne fatal_err
314 endif
315 ifdef SS_NEQ_DS
316 mov ax,_prev[2] ; segment value
317 mov cs:prev_ptr,ax ; ugly write to code, crash on OS/2
318 prev_seg equ cs:prev_ptr
319 else
320 prev_seg equ ss:_prev[2] ; works on OS/2 if SS == DS
321 endif
322 else
323 prev_seg equ cs:prev_ptr
324 endif
325 ret
326 ifndef NO_SECURE_TESTS
327 if @CodeSize
328 extrn _exit : far ; 'far' for large model
329 else
330 extrn _exit : near ; 'near' for compact model
331 endif
332 fatal_err: ; (quiet) emergency stop:
333 call _exit ; incompatible "global vars interface"
334 endif
335
336 _match_init endp
337
338 ; -----------------------------------------------------------------------
339 ; Set match_start to the longest match starting at the given string and
340 ; return its length. Matches shorter or equal to prev_length are discarded,
341 ; in which case the result is equal to prev_length and match_start is
342 ; garbage.
343 ; IN assertions: cur_match is the head of the hash chain for the current
344 ; string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
345
346 ; int longest_match(cur_match)
347
348 align Align_Size
349
350 if @CodeSize
351 _longest_match proc far ; 'proc far' for large model
352 else
353 _longest_match proc near ; 'proc near' for compact model
354 endif
355 push bp
356 mov bp,sp
357 push di
358 push si
359 push ds
360
361 if @CodeSize
362 cur_match equ word ptr [bp+6] ; [bp+6] for large model
363 else
364 cur_match equ word ptr [bp+4] ; [bp+4] for compact model
365 endif
366
367 ; window equ es:window (es:0 for DYN_ALLOC)
368 ; prev equ ds:prev
369 ; match equ es:si
370 ; scan equ es:di
371 ; chain_length equ bp
372 ; best_len equ bx
373 ; limit equ dx
374
375 mov si,cur_match ; use bp before it is destroyed
376 ifdef SS_NEQ_DS
377 mov ax,_nice_match
378 mov nice,ax ; ugly write to code, crash on OS/2
379 endif
380 mov dx,_strstart
381 mov bp,_max_chain_length ; chain_length = max_chain_length
382 mov di,dx
383 sub dx,MAX_DIST ; limit = strstart-MAX_DIST
384 cld ; string ops increment si and di
385 jae limit_ok
386 sub dx,dx ; limit = NIL
387 limit_ok:
388 add di,2+window_off ; di = offset(window + strstart + 2)
389 mov bx,_prev_length ; best_len = prev_length
390 mov es,window_seg
391 mov ax,es:[bx+di-3] ; ax = scan[best_len-1..best_len]
392 mov cx,es:[di-2] ; cx = scan[0..1]
393 cmp bx,_good_match ; do we have a good match already?
394 mov ds,prev_seg ; (does not destroy the flags)
395 assume ds: nothing
396 jb do_scan ; good match?
397 if Have_80x86
398 shr bp,2 ; chain_length >>= 2
399 else
400 shr bp,1 ; chain_length >>= 2
401 shr bp,1
402 endif
403 jmp short do_scan
404
405 align Align_Size ; align destination of branch
406 long_loop:
407 ; at this point, ds:di == scan+2, ds:si == cur_match
408 mov ax,[bx+di-3] ; ax = scan[best_len-1..best_len]
409 mov cx,[di-2] ; cx = scan[0..1]
410 mov ds,prev_seg ; reset ds to address the prev array
411 short_loop:
412 ; at this point, di == scan+2, si = cur_match,
413 ; ax = scan[best_len-1..best_len] and cx = scan[0..1]
414 if (WSIZE-32768)
415 and si,WSIZE-1 ; not needed if WSIZE=32768
416 endif
417 shl si,1 ; cur_match as word index
418 dec bp ; --chain_length
419 mov si,prev[si] ; cur_match = prev[cur_match]
420 jz the_end
421 cmp si,dx ; cur_match <= limit ?
422 jbe the_end
423 do_scan:
424 cmp ax,word ptr es:window[bx+si-1] ; check match at best_len-1
425 jne short_loop
426 cmp cx,word ptr es:window[si] ; check min_match_length match
427 jne short_loop
428
429 mov cx,es
430 add si,2+window_off ; si = match
431 mov ds,cx ; ds = es = window
432 mov cx,(MAX_MATCH-2)/2 ; scan for at most MAX_MATCH bytes
433 mov ax,di ; ax = scan+2
434 repe cmpsw ; loop until mismatch
435 je maxmatch ; match of length MAX_MATCH?
436 mismatch:
437 mov cl,[di-2] ; mismatch on first or second byte?
438 xchg ax,di ; di = scan+2, ax = end of scan
439 sub cl,[si-2] ; cl = 0 if first bytes equal
440 sub ax,di ; ax = len
441 sub si,2+window_off ; si = cur_match + len
442 sub si,ax ; si = cur_match
443 sub cl,1 ; set carry if cl == 0 (can't use DEC)
444 adc ax,0 ; ax = carry ? len+1 : len
445 cmp ax,bx ; len > best_len ?
446 jle long_loop
447 mov ma_start,si ; match_start = cur_match
448 mov bx,ax ; bx = best_len = len
449 cmp ax,nice ; len >= nice_match ?
450 jl long_loop
451 the_end:
452 pop ds
453 assume ds: DGROUP
454 ifdef SS_NEQ_DS
455 mov ax,ma_start ; garbage if no match found
456 mov ds:_match_start,ax
457 endif
458 pop si
459 pop di
460 pop bp
461 mov ax,bx ; result = ax = best_len
462 ret
463 maxmatch: ; come here if maximum match
464 cmpsb ; increment si and di
465 jmp mismatch ; force match_length = MAX_LENGTH
466
467 _longest_match endp
468
469 if @CodeSize
470 MATCH_TEXT ENDS
471 else
472 _TEXT ENDS
473 endif
474 ;
475 endif ;!USE_ZLIB
476 ;
477 end