home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / zip21.zip / os2 / match32.asm < prev    next >
Assembly Source File  |  1996-04-01  |  6KB  |  162 lines
  1. ;
  2. ; Copyright (C) 1990-1995 Mark Adler, Richard B. Wales, Jean-loup Gailly,
  3. ; Kai Uwe Rommel, Onno van der Linden and Igor Mandrichenko.
  4. ; Permission is granted to any individual or institution to use, copy, or
  5. ; redistribute this software so long as all of the original files are included,
  6. ; that it is not sold for profit, and that this copyright notice is retained.
  7. ;
  8. ; match32.asm by Jean-loup Gailly.
  9.  
  10. ; match32.asm, optimized version of longest_match() in deflate.c
  11. ; To be used only with 32 bit flat model. To simplify the code, the option
  12. ; -DDYN_ALLOC is not supported.
  13. ; This file is only optional. If you don't have an assembler, use the
  14. ; C version (add -DNO_ASM to CFLAGS in makefile and remove match.o
  15. ; from OBJI). If you have reduced WSIZE in zip.h, then make sure this is
  16. ; assembled with an equivalent -DWSIZE=<whatever>.
  17.  
  18. ; Caution: this module works for IBM's C/C++ compiler versions 2 and 3 
  19. ; and for Watcom's 32-bit C/C++ compiler. Both pass the first (and only)
  20. ; argument for longest_match in the EAX register, not on the stack, with
  21. ; the default calling conventions (_System would use the stack).
  22.  
  23.         .386
  24.  
  25.         name    match
  26.  
  27. BSS32   segment  dword USE32 public 'BSS'
  28.         extrn   window       : byte
  29.         extrn   prev         : word
  30.         extrn   prev_length  : dword
  31.         extrn   strstart     : dword
  32.         extrn   match_start  : dword
  33.         extrn   max_chain_length : dword
  34.         extrn   good_match   : dword
  35.         extrn   nice_match   : dword
  36. BSS32   ends
  37.  
  38. CODE32  segment dword USE32 public 'CODE'
  39.         assume cs:CODE32, ds:FLAT, ss:FLAT
  40.  
  41.         public  match_init
  42.         public  longest_match
  43.  
  44.     ifndef      WSIZE
  45.         WSIZE         equ 32768         ; keep in sync with zip.h !
  46.     endif
  47.         MIN_MATCH     equ 3
  48.         MAX_MATCH     equ 258
  49.         MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
  50.         MAX_DIST      equ (WSIZE-MIN_LOOKAHEAD)
  51.  
  52. ; initialize or check the variables used in match.asm.
  53.  
  54. match_init proc near
  55.         ret
  56. match_init endp
  57.  
  58. ; -----------------------------------------------------------------------
  59. ; Set match_start to the longest match starting at the given string and
  60. ; return its length. Matches shorter or equal to prev_length are discarded,
  61. ; in which case the result is equal to prev_length and match_start is
  62. ; garbage.
  63. ; IN assertions: cur_match is the head of the hash chain for the current
  64. ;   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  65.  
  66. ; int longest_match(cur_match)
  67.  
  68. longest_match proc near
  69.  
  70.         ; return address                ; esp+16
  71.         push    ebp                     ; esp+12
  72.         push    edi                     ; esp+8
  73.         push    esi                     ; esp+4
  74.  
  75.     lea    ebx,window
  76.     add    ebx,2
  77.         window_off equ dword ptr [esp]
  78.         push    ebx                     ; esp
  79.  
  80. ;       match        equ esi
  81. ;       scan         equ edi
  82. ;       chain_length equ ebp
  83. ;       best_len     equ ebx
  84. ;       limit        equ edx
  85.  
  86.         mov     esi,eax                    ; cur_match
  87.         mov     edx,strstart
  88.         mov     ebp,max_chain_length    ; chain_length = max_chain_length
  89.     mov    edi,edx
  90.         sub     edx,MAX_DIST            ; limit = strstart-MAX_DIST
  91.         cld                             ; string ops increment si and di
  92.         jae     short limit_ok
  93.         sub     edx,edx                 ; limit = NIL
  94. limit_ok:
  95.         add     edi,window_off          ; edi = offset(window + strstart + 2)
  96.         mov     ebx,prev_length         ; best_len = prev_length
  97.         mov     cx,[edi-2]              ; cx = scan[0..1]
  98.         mov     ax,[ebx+edi-3]          ; ax = scan[best_len-1..best_len]
  99.         cmp     ebx,good_match          ; do we have a good match already?
  100.         jb      do_scan
  101.         shr     ebp,2                   ; chain_length >>= 2
  102.         jmp     short do_scan
  103.  
  104.         align   4                       ; align destination of branch
  105. long_loop:
  106. ; at this point, edi == scan+2, esi == cur_match
  107.         mov     ax,[ebx+edi-3]          ; ax = scan[best_len-1..best_len]
  108.         mov     cx,[edi-2]              ; cx = scan[0..1]
  109. short_loop:
  110. ; at this point, edi == scan+2, esi == cur_match,
  111. ; ax = scan[best_len-1..best_len] and cx = scan[0..1]
  112.         and     esi,WSIZE-1             ; not needed if WSIZE=32768
  113.         dec     ebp                     ; --chain_length
  114.         shl     esi,1                   ; cur_match as word index
  115.         mov     si,prev[esi]            ; cur_match = prev[cur_match]
  116.                                     ; top word of esi is still 0
  117.         jz      the_end
  118.         cmp     esi,edx                 ; cur_match <= limit ?
  119.         jbe     short the_end
  120. do_scan:
  121.         cmp     ax,word ptr window[ebx+esi-1]   ; check match at best_len-1
  122.         jne     short_loop
  123.         cmp     cx,word ptr window[esi]         ; check min_match_length match
  124.         jne     short_loop
  125.  
  126.         add     esi,window_off          ; si = match
  127.         mov     ecx,(MAX_MATCH-2)/2     ; scan for at most MAX_MATCH bytes
  128.         mov     eax,edi                 ; ax = scan+2
  129.         repe    cmpsw                   ; loop until mismatch
  130.         je      maxmatch                ; match of length MAX_MATCH?
  131. mismatch:
  132.         mov     cl,[edi-2]              ; mismatch on first or second byte?
  133.         xchg    eax,edi                 ; edi = scan+2, eax = end of scan
  134.         sub     cl,[esi-2]              ; cl = 0 if first bytes equal
  135.         sub     eax,edi                 ; eax = len
  136.         sub     esi,window_off          ; esi = cur_match
  137.         sub     esi,eax                 ; esi = cur_match + 2 + offset(window)
  138.         sub     cl,1                    ; set carry if cl == 0 (can't use DEC)
  139.         adc     eax,0                   ; eax = carry ? len+1 : len
  140.         cmp     eax,ebx                 ; len > best_len ?
  141.         jle     long_loop
  142.         mov     match_start,esi         ; match_start = cur_match
  143.         mov     ebx,eax                 ; ebx = best_len = len
  144.         cmp     eax,nice_match          ; len >= MAX_MATCH ?
  145.         jl      long_loop
  146. the_end:
  147.         mov     eax,ebx                 ; result = eax = best_len
  148.         pop     ebx
  149.         pop     esi
  150.         pop     edi
  151.         pop     ebp
  152.         ret
  153. maxmatch:                               ; come here if maximum match
  154.         cmpsb                           ; increment esi and edi
  155.         jmp     mismatch                ; force match_length = MAX_LENGTH
  156.  
  157. longest_match endp
  158.  
  159. CODE32  ends
  160.  
  161.     end
  162.