home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 mARCH / PCWK3A99.iso / Archiwiz / Tar320 / SOURCES.ZIP / MATCH.ASM < prev    next >
Assembly Source File  |  1996-07-03  |  7KB  |  189 lines
  1. ; The following sorce code is derived from Info-Zip 'zip' 2.01
  2. ; distribution copyrighted by Mark Adler, Richard B. Wales,
  3. ; Jean-loup Gailly, Kai Uwe Rommel, Igor Mandrichenko and John Bush.
  4.  
  5. ; match.asm is initially written by Jean-loup Gailly.
  6.  
  7. ; match.asm, optimized version of longest_match() in deflate.c
  8. ; Must be assembled with masm -ml. To be used only with C large or
  9. ; compact model. (For compact model, assemble with -D__NEAR__).
  10. ; This file is only optional. If you don't have masm or tasm, use the
  11. ; C version.
  12. ; If you have reduced WSIZE in zip.h, then change its value below.
  13. ;
  14. ; For the C compilers, which allows static allocation of more than 64K
  15. ; bytes per file, it's possible to simplify code by using -DST_ALLOC
  16. ; compilation option.
  17. ;
  18. ; To simplify the code, dynamically allocated arrays must have zero
  19. ; offset (allocated by halloc).
  20.  
  21.         include farnear.inc
  22.  
  23. ifdef ST_ALLOC
  24.         extrn   _prev         : word
  25.         extrn   _scope        : byte
  26.         prev    equ  _prev    ; offset part
  27.         window  equ  _scope
  28. endif
  29.  
  30. _DATA   segment  word public 'DATA'
  31. ifndef ST_ALLOC
  32.         extrn   _prev         : word
  33.         extrn   _scope        : word
  34.         prev    equ 0         ; offset forced to zero
  35.         window  equ 0
  36.         window_seg equ _scope[2]
  37.         window_off equ 0
  38.         prev_seg   equ _prev[2]
  39. else
  40.         window_seg dw  seg _scope
  41.         window_off equ offset _scope
  42.         prev_seg   dw  seg _prev     ; pointer to the prev array
  43. endif
  44.         extrn   _nice_match   : word
  45.         extrn   _match_start  : word
  46.         extrn   _prev_length  : word
  47.         extrn   _good_match   : word
  48.         extrn   _strstart     : word
  49.         extrn   _max_chain_length : word
  50. _DATA   ends
  51.  
  52. DGROUP  group _DATA
  53.  
  54. _TEXT   segment word public 'CODE'
  55.         assume  cs: _TEXT, ds: DGROUP
  56.  
  57.         MIN_MATCH     equ 3
  58.         MAX_MATCH     equ 258
  59.         WSIZE         equ 32768         ; keep in sync with zip.h !
  60.         MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
  61.         MAX_DIST      equ (WSIZE-MIN_LOOKAHEAD)
  62.  
  63. ; initialize or check the variables used in match.asm.
  64.  
  65.         program _match_init
  66. ifndef ST_ALLOC
  67.         mov     ax,_prev[0]
  68.         or      ax,_scope[0]   ; verify zero offset(s) - both in a turn
  69. else
  70.         xor     ax,ax
  71. endif
  72.         ret
  73. _match_init endp
  74.  
  75. ; Set match_start to the longest match starting at the given string and
  76. ; return its length. Matches shorter or equal to prev_length are discarded,
  77. ; in which case the result is equal to prev_length and match_start is
  78. ; garbage.
  79. ; IN assertions: cur_match is the head of the hash chain for the current
  80. ;   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  81.  
  82. ; int longest_match(cur_match)
  83.  
  84.         program _longest_match
  85.  
  86.         push    bp
  87.         mov     bp,sp
  88.         push    di
  89.         push    si
  90.         push    ds
  91.  
  92. ;       window       equ es:0 (es:window for ST_ALLOC)
  93. ;       prev         equ ds:prev
  94. ;       match        equ es:si
  95. ;       scan         equ es:di
  96. ;       chain_length equ bp
  97. ;       best_len     equ bx
  98. ;       limit        equ dx
  99.  
  100.         mov     si,arglist[0]   ; = cur_match (use bp before it is destroyed)
  101.         mov     bp,_max_chain_length    ; chain_length = max_chain_length
  102.         mov     di,_strstart
  103.         mov     dx,di
  104.         sub     dx,MAX_DIST             ; limit = strstart-MAX_DIST
  105.         jae     limit_ok
  106.         sub     dx,dx                   ; limit = NIL
  107. limit_ok:
  108.         add     di,2+window_off         ; di = offset(window + strstart + 2)
  109.         mov     bx,_prev_length         ; best_len = prev_length
  110.         mov     es,window_seg
  111.         mov     ax,es:[bx+di-3]         ; ax = scan[best_len-1..best_len]
  112.         mov     cx,es:[di-2]            ; cx = scan[0..1]
  113.         cmp     bx,_good_match          ; do we have a good match already?
  114. ; Note: DS still points to static data (DGROUP)
  115.         mov     ds,prev_seg             ; (does not destroy the flags)
  116.         jb      do_scan                 ; good match?
  117.         shr     bp,1                    ; chain_length >>= 2
  118.         shr     bp,1
  119.         jmp     short do_scan
  120.  
  121.         even                            ; align destination of branch
  122. long_loop:
  123. ; at this point, es:di == scan+2, es:si == cur_match
  124.         mov     ax,es:[bx+di-3]         ; ax = scan[best_len-1..best_len]
  125.         mov     cx,es:[di-2]            ; cx = scan[0..1]
  126. ; Note: DS always points to static data here
  127.         mov     ds,prev_seg             ; reset ds to address the prev array
  128.         assume  ds: nothing
  129. short_loop:
  130. ; at this point, di == scan+2, si = cur_match,
  131. ; ax = scan[best_len-1..best_len] and cx = scan[0..1]
  132. if (WSIZE-32768)
  133.         and     si,WSIZE-1              ; not needed if WSIZE=32768
  134. endif
  135.         shl     si,1                    ; cur_match as word index
  136.         mov     si,prev[si]             ; cur_match = prev[cur_match]
  137.         cmp     si,dx                   ; cur_match <= limit ?
  138.         jbe     the_end
  139.         dec     bp                      ; --chain_length
  140.         jz      the_end
  141. do_scan:
  142.         cmp     ax,word ptr es:window[bx+si-1] ; check match at best_len-1
  143.         jne     short_loop
  144.         cmp     cx,word ptr es:window[si]      ; check min_match_length match
  145.         jne     short_loop
  146.  
  147.         lea     si,window[si+2]         ; si = match
  148.         mov     ax,di                   ; ax = scan+2
  149.         mov     cx,es
  150.         mov     ds,cx                   ; ds = es = window
  151.         mov     cx,(MAX_MATCH-2)/2      ; scan for at most MAX_MATCH bytes
  152.         repe    cmpsw                   ; loop until mismatch
  153.         je      maxmatch                ; match of length MAX_MATCH?
  154. mismatch:
  155.         mov     cl,[di-2]               ; mismatch on first or second byte?
  156.         sub     cl,[si-2]               ; cl = 0 if first bytes equal
  157.         xchg    ax,di                   ; di = scan+2, ax = end of scan
  158.         sub     ax,di                   ; ax = len
  159.         sub     si,ax                   ; si = cur_match + 2 + offset(window)
  160.         sub     si,2+window_off         ; si = cur_match
  161.         sub     cl,1                    ; set carry if cl == 0 (can't use DEC)
  162.         adc     ax,0                    ; ax = carry ? len+1 : len
  163.         pop     ds                      ; DS now points to static data
  164.         assume  ds: DGROUP
  165.         push    ds                      ; restore stack
  166.         cmp     ax,bx                   ; len > best_len ?
  167.         jle     long_loop
  168.         mov     _match_start,si         ; match_start = cur_match
  169.         mov     bx,ax                   ; bx = best_len = len
  170.         cmp     ax,_nice_match          ; len >= nice_match ?
  171.         jl      long_loop
  172. the_end:
  173.         pop     ds
  174.         pop     si
  175.         pop     di
  176.         pop     bp
  177.         mov     ax,bx                   ; result = ax = best_len
  178.         ret
  179.  
  180.         even
  181. maxmatch:                               ; come here if maximum match
  182.         cmpsb                           ; increment si and di
  183.         jmp     mismatch                ; force match_length = MAX_LENGTH
  184.  
  185. _longest_match  endp
  186.  
  187. _TEXT   ends
  188. end
  189.