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