home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / ZIP19P1.ZIP / match.s < prev    next >
Text File  |  1993-01-23  |  5KB  |  147 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. / match.s by Jean-loup Gailly. Translated to 32 bit code by Kai Uwe Rommel.
  10.  
  11. / match.s, optimized version of longest_match() in deflate.c
  12. / This version is for 386 Unix or OS/2 in 32 bit mode.
  13. / Warning: it uses the AT&T syntax: mov source,dest
  14. / This file is only optional. If you want to force the C version,
  15. / add -DNO_ASM to CFLAGS in makefile and remove match.o from OBJI).
  16. / If you have reduced WSIZE in zip.h, then change its value below.
  17. / This version assumes static allocation of the arrays (-DDYN_ALLOC not used).
  18.  
  19.     .file   "match.s"
  20.  
  21. #if defined(__GO32__) && defined(unix)
  22. #  undef unix
  23. #endif
  24.  
  25. #ifdef unix
  26. #  define _prev             prev
  27. #  define _window           window
  28. #  define _match_start        match_start
  29. #  define _prev_length        prev_length
  30. #  define _good_match        good_match
  31. #  define _strstart        strstart
  32. #  define _max_chain_length max_chain_length
  33.  
  34. #  define _match_init       match_init
  35. #  define _longest_match    longest_match
  36. #endif
  37.  
  38. #define MAX_MATCH     258
  39. #define MAX_MATCH2      128     /* MAX_MATCH/2-1 */
  40. #define MIN_MATCH    3
  41. #define WSIZE         32768
  42. #define MAX_DIST     WSIZE - MAX_MATCH - MIN_MATCH - 1
  43.  
  44.     .globl    _match_init
  45.     .globl  _longest_match
  46.  
  47.     .text
  48.  
  49. _match_init:
  50.     ret
  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. _longest_match:    /* int longest_match(cur_match) */
  61.  
  62. #define cur_match   20(%esp)
  63.         / return address                / esp+16
  64.         push    %ebp                    / esp+12
  65.         push    %edi                    / esp+8
  66.     push    %esi                    / esp+4
  67.     push    %ebx            / esp
  68.  
  69. /       match        equ esi
  70. /       scan         equ edi
  71. /       chain_length equ ebp
  72. /       best_len     equ ebx
  73. /       limit        equ edx
  74.  
  75.     mov     cur_match,%esi
  76.         mov     _max_chain_length,%ebp  / chain_length = max_chain_length
  77.     mov     _strstart,%edi
  78.     mov     %edi,%edx
  79.     sub    $ MAX_DIST,%edx         / limit = strstart-MAX_DIST
  80.     jae    limit_ok
  81.     sub    %edx,%edx               / limit = NIL
  82. limit_ok:
  83.         add    $_window+2,%edi         / edi = offset(window + strstart + 2)
  84.         mov    _prev_length,%ebx       / best_len = prev_length
  85.         movw     -3(%ebx,%edi),%ax       / ax = scan[best_len-1..best_len]
  86.         movw     -2(%edi),%cx            / cx = scan[0..1]
  87.     cmp    _good_match,%ebx        / do we have a good match already?
  88.         jb      do_scan
  89.     shr     $2,%ebp                 / chain_length >>= 2
  90.         jmp     do_scan
  91.  
  92.         .align  4
  93. long_loop:
  94. / at this point, edi == scan+2, esi == cur_match
  95.         movw    -3(%ebx,%edi),%ax       / ax = scan[best_len-1..best_len]
  96.         movw     -2(%edi),%cx            / cx = scan[0..1]
  97. short_loop:
  98.         dec     %ebp                    / --chain_length
  99.         jz      the_end
  100. / at this point, di == scan+2, si == cur_match,
  101. / ax = scan[best_len-1..best_len] and cx = scan[0..1]
  102.         and     $ WSIZE-1, %esi
  103.         movw     _prev(%esi,%esi),%si    / cur_match = prev[cur_match]
  104.                                         / top word of esi is still 0
  105.         cmp     %edx,%esi        / cur_match <= limit ?
  106.         jbe     the_end
  107. do_scan:
  108.         cmpw    _window-1(%ebx,%esi),%ax /check match at best_len-1
  109.         jne     short_loop
  110.         cmpw    _window(%esi),%cx       / check min_match_length match
  111.         jne     short_loop
  112.  
  113.         lea     _window+2(%esi),%esi    / si = match
  114.         mov     %edi,%eax               / ax = scan+2
  115.         mov     $ MAX_MATCH2,%ecx       / scan for at most MAX_MATCH bytes
  116. #ifdef unix
  117.         repz;   cmpsw                   / loop until mismatch
  118. #else
  119.         repe;   cmpsw
  120. #endif
  121.         je      maxmatch                / match of length MAX_MATCH?
  122. mismatch:
  123.         movb    -2(%edi),%cl            / mismatch on first or second byte?
  124.         subb    -2(%esi),%cl            / cl = 0 if first bytes equal
  125.         xchg    %edi,%eax               / edi = scan+2, eax = end of scan
  126.         sub     %edi,%eax               / eax = len
  127.     sub    %eax,%esi               / esi = cur_match + 2 + offset(window)
  128.     sub    $_window+2,%esi         / esi = cur_match
  129.         subb    $1,%cl                  / set carry if cl == 0 (cannot use DEC)
  130.         adc     $0,%eax                 / eax = carry ? len+1 : len
  131.         cmp     %ebx,%eax               / len > best_len ?
  132.         jle     long_loop
  133.         mov     %esi,_match_start       / match_start = cur_match
  134.         mov     %eax,%ebx               / ebx = best_len = len
  135.         cmp     $ MAX_MATCH,%eax        / len >= MAX_MATCH ?
  136.         jl      long_loop
  137. the_end:
  138.         mov     %ebx,%eax               / result = eax = best_len
  139.     pop     %ebx
  140.         pop     %esi
  141.         pop     %edi
  142.         pop     %ebp
  143.         ret
  144. maxmatch:
  145.         cmpsb
  146.         jmp     mismatch
  147.