| 1 | ; match.asm -- optional optimized asm version of longest match in deflate.c
|
|---|
| 2 | ; Copyright (C) 1992-1993 Jean-loup Gailly
|
|---|
| 3 | ; This is free software; you can redistribute it and/or modify it under the
|
|---|
| 4 | ; terms of the GNU General Public License, see the file COPYING.
|
|---|
| 5 | ;
|
|---|
| 6 | ; Must be assembled with masm -ml. To be used only with C compact model
|
|---|
| 7 | ; or large model. (For large model, assemble with -D__LARGE__).
|
|---|
| 8 | ; This file is only optional. If you don't have masm or tasm, use the
|
|---|
| 9 | ; C version (add -DNO_ASM to CFLAGS in makefile.msc and remove match.obj
|
|---|
| 10 | ; from OBJI). If you have reduced WSIZE in zip.h, then change its value
|
|---|
| 11 | ; below.
|
|---|
| 12 | ;
|
|---|
| 13 | ; Turbo C 2.0 does not support static allocation of more than 64K bytes per
|
|---|
| 14 | ; file, and does not have SS == DS. So TC and BC++ users must use:
|
|---|
| 15 | ; tasm -ml -DDYN_ALLOC -DSS_NEQ_DS match;
|
|---|
| 16 | ;
|
|---|
| 17 | ; To simplify the code, the option -DDYN_ALLOC is supported for OS/2
|
|---|
| 18 | ; only if the arrays are guaranteed to have zero offset (allocated by
|
|---|
| 19 | ; halloc). We also require SS==DS. This is satisfied for MSC but not Turbo C.
|
|---|
| 20 |
|
|---|
| 21 | ; $Id: match.asm,v 0.6 1993/01/21 18:49:05 jloup Exp $
|
|---|
| 22 |
|
|---|
| 23 | name match
|
|---|
| 24 |
|
|---|
| 25 | ifndef DYN_ALLOC
|
|---|
| 26 | extrn _prev : word
|
|---|
| 27 | extrn _window : byte
|
|---|
| 28 | prev equ _prev ; offset part
|
|---|
| 29 | window equ _window
|
|---|
| 30 | endif
|
|---|
| 31 |
|
|---|
| 32 | _DATA segment word public 'DATA'
|
|---|
| 33 | extrn _nice_match : word
|
|---|
| 34 | extrn _match_start : word
|
|---|
| 35 | extrn _prev_length : word
|
|---|
| 36 | extrn _good_match : word
|
|---|
| 37 | extrn _strstart : word
|
|---|
| 38 | extrn _max_chain_length : word
|
|---|
| 39 | ifdef DYN_ALLOC
|
|---|
| 40 | extrn _prev : word
|
|---|
| 41 | extrn _window : word
|
|---|
| 42 | prev equ 0 ; offset forced to zero
|
|---|
| 43 | window equ 0
|
|---|
| 44 | window_seg equ _window[2]
|
|---|
| 45 | window_off equ 0
|
|---|
| 46 | else
|
|---|
| 47 | wseg dw seg _window
|
|---|
| 48 | window_seg equ wseg
|
|---|
| 49 | window_off equ offset _window
|
|---|
| 50 | endif
|
|---|
| 51 | _DATA ends
|
|---|
| 52 |
|
|---|
| 53 | DGROUP group _DATA
|
|---|
| 54 |
|
|---|
| 55 | _TEXT segment word public 'CODE'
|
|---|
| 56 | assume cs: _TEXT, ds: DGROUP
|
|---|
| 57 |
|
|---|
| 58 | public _match_init
|
|---|
| 59 | public _longest_match
|
|---|
| 60 |
|
|---|
| 61 | MIN_MATCH equ 3
|
|---|
| 62 | MAX_MATCH equ 258
|
|---|
| 63 | WSIZE equ 32768 ; keep in sync with zip.h !
|
|---|
| 64 | MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
|
|---|
| 65 | MAX_DIST equ (WSIZE-MIN_LOOKAHEAD)
|
|---|
| 66 |
|
|---|
| 67 | prev_ptr dw seg _prev ; pointer to the prev array
|
|---|
| 68 | ifdef SS_NEQ_DS
|
|---|
| 69 | match_start dw 0 ; copy of _match_start if SS != DS
|
|---|
| 70 | nice_match dw 0 ; copy of _nice_match if SS != DS
|
|---|
| 71 | endif
|
|---|
| 72 |
|
|---|
| 73 | ; initialize or check the variables used in match.asm.
|
|---|
| 74 |
|
|---|
| 75 | ifdef __LARGE__
|
|---|
| 76 | _match_init proc far ; 'proc far' for large model
|
|---|
| 77 | else
|
|---|
| 78 | _match_init proc near ; 'proc near' for compact model
|
|---|
| 79 | endif
|
|---|
| 80 | ifdef SS_NEQ_DS
|
|---|
| 81 | ma_start equ cs:match_start ; does not work on OS/2
|
|---|
| 82 | nice equ cs:nice_match
|
|---|
| 83 | mov ax,_nice_match
|
|---|
| 84 | mov cs:nice_match,ax ; ugly write to code, crash on OS/2
|
|---|
| 85 | else
|
|---|
| 86 | assume ss: DGROUP
|
|---|
| 87 | ma_start equ ss:_match_start
|
|---|
| 88 | nice equ ss:_nice_match
|
|---|
| 89 | mov ax,ds
|
|---|
| 90 | mov bx,ss
|
|---|
| 91 | cmp ax,bx ; SS == DS?
|
|---|
| 92 | jne error
|
|---|
| 93 | endif
|
|---|
| 94 | ifdef DYN_ALLOC
|
|---|
| 95 | cmp _prev[0],0 ; verify zero offset
|
|---|
| 96 | jne error
|
|---|
| 97 | cmp _window[0],0
|
|---|
| 98 | jne error
|
|---|
| 99 | ifdef SS_NEQ_DS
|
|---|
| 100 | mov ax,_prev[2] ; segment value
|
|---|
| 101 | mov cs:prev_ptr,ax ; ugly write to code, crash on OS/2
|
|---|
| 102 | prev_seg equ cs:prev_ptr
|
|---|
| 103 | else
|
|---|
| 104 | prev_seg equ ss:_prev[2] ; works on OS/2 if SS == DS
|
|---|
| 105 | endif
|
|---|
| 106 | else
|
|---|
| 107 | prev_seg equ cs:prev_ptr
|
|---|
| 108 | endif
|
|---|
| 109 | ret
|
|---|
| 110 | ifdef __LARGE__
|
|---|
| 111 | extrn _exit : far ; 'far' for large model
|
|---|
| 112 | else
|
|---|
| 113 | extrn _exit : near ; 'near' for compact model
|
|---|
| 114 | endif
|
|---|
| 115 | error: call _exit
|
|---|
| 116 |
|
|---|
| 117 | _match_init endp
|
|---|
| 118 |
|
|---|
| 119 | ; -----------------------------------------------------------------------
|
|---|
| 120 | ; Set match_start to the longest match starting at the given string and
|
|---|
| 121 | ; return its length. Matches shorter or equal to prev_length are discarded,
|
|---|
| 122 | ; in which case the result is equal to prev_length and match_start is
|
|---|
| 123 | ; garbage.
|
|---|
| 124 | ; IN assertions: cur_match is the head of the hash chain for the current
|
|---|
| 125 | ; string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
|
|---|
| 126 |
|
|---|
| 127 | ; int longest_match(cur_match)
|
|---|
| 128 |
|
|---|
| 129 | ifdef __LARGE__
|
|---|
| 130 | _longest_match proc far ; 'proc far' for large model
|
|---|
| 131 | else
|
|---|
| 132 | _longest_match proc near ; 'proc near' for compact model
|
|---|
| 133 | endif
|
|---|
| 134 | push bp
|
|---|
| 135 | mov bp,sp
|
|---|
| 136 | push di
|
|---|
| 137 | push si
|
|---|
| 138 | push ds
|
|---|
| 139 |
|
|---|
| 140 | ifdef __LARGE__
|
|---|
| 141 | cur_match equ word ptr [bp+6] ; [bp+6] for large model
|
|---|
| 142 | else
|
|---|
| 143 | cur_match equ word ptr [bp+4] ; [bp+4] for compact model
|
|---|
| 144 | endif
|
|---|
| 145 |
|
|---|
| 146 | ; window equ es:window (es:0 for DYN_ALLOC)
|
|---|
| 147 | ; prev equ ds:prev
|
|---|
| 148 | ; match equ es:si
|
|---|
| 149 | ; scan equ es:di
|
|---|
| 150 | ; chain_length equ bp
|
|---|
| 151 | ; best_len equ bx
|
|---|
| 152 | ; limit equ dx
|
|---|
| 153 |
|
|---|
| 154 | mov si,cur_match ; use bp before it is destroyed
|
|---|
| 155 | mov bp,_max_chain_length ; chain_length = max_chain_length
|
|---|
| 156 | mov di,_strstart
|
|---|
| 157 | mov dx,di
|
|---|
| 158 | sub dx,MAX_DIST ; limit = strstart-MAX_DIST
|
|---|
| 159 | jae limit_ok
|
|---|
| 160 | sub dx,dx ; limit = NIL
|
|---|
| 161 | limit_ok:
|
|---|
| 162 | add di,2+window_off ; di = offset(window + strstart + 2)
|
|---|
| 163 | mov bx,_prev_length ; best_len = prev_length
|
|---|
| 164 | mov es,window_seg
|
|---|
| 165 | mov ax,es:[bx+di-3] ; ax = scan[best_len-1..best_len]
|
|---|
| 166 | mov cx,es:[di-2] ; cx = scan[0..1]
|
|---|
| 167 | cmp bx,_good_match ; do we have a good match already?
|
|---|
| 168 | mov ds,prev_seg ; (does not destroy the flags)
|
|---|
| 169 | assume ds: nothing
|
|---|
| 170 | jb do_scan ; good match?
|
|---|
| 171 | shr bp,1 ; chain_length >>= 2
|
|---|
| 172 | shr bp,1
|
|---|
| 173 | jmp short do_scan
|
|---|
| 174 |
|
|---|
| 175 | even ; align destination of branch
|
|---|
| 176 | long_loop:
|
|---|
| 177 | ; at this point, ds:di == scan+2, ds:si == cur_match
|
|---|
| 178 | mov ax,[bx+di-3] ; ax = scan[best_len-1..best_len]
|
|---|
| 179 | mov cx,[di-2] ; cx = scan[0..1]
|
|---|
| 180 | mov ds,prev_seg ; reset ds to address the prev array
|
|---|
| 181 | short_loop:
|
|---|
| 182 | ; at this point, di == scan+2, si = cur_match,
|
|---|
| 183 | ; ax = scan[best_len-1..best_len] and cx = scan[0..1]
|
|---|
| 184 | if (WSIZE-32768)
|
|---|
| 185 | and si,WSIZE-1 ; not needed if WSIZE=32768
|
|---|
| 186 | endif
|
|---|
| 187 | shl si,1 ; cur_match as word index
|
|---|
| 188 | mov si,prev[si] ; cur_match = prev[cur_match]
|
|---|
| 189 | cmp si,dx ; cur_match <= limit ?
|
|---|
| 190 | jbe the_end
|
|---|
| 191 | dec bp ; --chain_length
|
|---|
| 192 | jz the_end
|
|---|
| 193 | do_scan:
|
|---|
| 194 | cmp ax,word ptr es:window[bx+si-1] ; check match at best_len-1
|
|---|
| 195 | jne short_loop
|
|---|
| 196 | cmp cx,word ptr es:window[si] ; check min_match_length match
|
|---|
| 197 | jne short_loop
|
|---|
| 198 |
|
|---|
| 199 | lea si,window[si+2] ; si = match
|
|---|
| 200 | mov ax,di ; ax = scan+2
|
|---|
| 201 | mov cx,es
|
|---|
| 202 | mov ds,cx ; ds = es = window
|
|---|
| 203 | mov cx,(MAX_MATCH-2)/2 ; scan for at most MAX_MATCH bytes
|
|---|
| 204 | repe cmpsw ; loop until mismatch
|
|---|
| 205 | je maxmatch ; match of length MAX_MATCH?
|
|---|
| 206 | mismatch:
|
|---|
| 207 | mov cl,[di-2] ; mismatch on first or second byte?
|
|---|
| 208 | sub cl,[si-2] ; cl = 0 if first bytes equal
|
|---|
| 209 | xchg ax,di ; di = scan+2, ax = end of scan
|
|---|
| 210 | sub ax,di ; ax = len
|
|---|
| 211 | sub si,ax ; si = cur_match + 2 + offset(window)
|
|---|
| 212 | sub si,2+window_off ; si = cur_match
|
|---|
| 213 | sub cl,1 ; set carry if cl == 0 (can't use DEC)
|
|---|
| 214 | adc ax,0 ; ax = carry ? len+1 : len
|
|---|
| 215 | cmp ax,bx ; len > best_len ?
|
|---|
| 216 | jle long_loop
|
|---|
| 217 | mov ma_start,si ; match_start = cur_match
|
|---|
| 218 | mov bx,ax ; bx = best_len = len
|
|---|
| 219 | cmp ax,nice ; len >= nice_match ?
|
|---|
| 220 | jl long_loop
|
|---|
| 221 | the_end:
|
|---|
| 222 | pop ds
|
|---|
| 223 | assume ds: DGROUP
|
|---|
| 224 | ifdef SS_NEQ_DS
|
|---|
| 225 | mov ax,ma_start ; garbage if no match found
|
|---|
| 226 | mov ds:_match_start,ax
|
|---|
| 227 | endif
|
|---|
| 228 | pop si
|
|---|
| 229 | pop di
|
|---|
| 230 | pop bp
|
|---|
| 231 | mov ax,bx ; result = ax = best_len
|
|---|
| 232 | ret
|
|---|
| 233 | maxmatch: ; come here if maximum match
|
|---|
| 234 | cmpsb ; increment si and di
|
|---|
| 235 | jmp mismatch ; force match_length = MAX_LENGTH
|
|---|
| 236 |
|
|---|
| 237 | _longest_match endp
|
|---|
| 238 |
|
|---|
| 239 | _TEXT ends
|
|---|
| 240 | end
|
|---|
