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