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