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