msdos/match.asm

   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$
  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