home *** CD-ROM | disk | FTP | other *** search
/ High Voltage Shareware / high1.zip / high1 / DIR40 / GNUZIP_.ZIP / MATCH.ASM < prev    next >
Assembly Source File  |  1993-03-28  |  8KB  |  241 lines
  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
  241.