home *** CD-ROM | disk | FTP | other *** search
/ Freelog 11 / Freelog011.iso / Bas / Compression / ZLib / contrib / asm686 / match.S next >
Text File  |  1998-06-19  |  9KB  |  328 lines
  1. /* match.s -- Pentium-Pro-optimized version of longest_match()
  2.  * Written for zlib 1.1.2
  3.  * Copyright (C) 1998 Brian Raiter <breadbox@muppetlabs.com>
  4.  *
  5.  * This is free software; you can redistribute it and/or modify it
  6.  * under the terms of the GNU General Public License.
  7.  */
  8.  
  9. #ifndef NO_UNDERLINE
  10. #define    match_init    _match_init
  11. #define    longest_match    _longest_match
  12. #endif
  13.  
  14. #define    MAX_MATCH    (258)
  15. #define    MIN_MATCH    (3)
  16. #define    MIN_LOOKAHEAD    (MAX_MATCH + MIN_MATCH + 1)
  17. #define    MAX_MATCH_8    ((MAX_MATCH + 7) & ~7)
  18.  
  19. /* stack frame offsets */
  20.  
  21. #define    chainlenwmask        0    /* high word: current chain len    */
  22.                     /* low word: s->wmask        */
  23. #define    window            4    /* local copy of s->window    */
  24. #define    windowbestlen        8    /* s->window + bestlen        */
  25. #define    scanstart        16    /* first two bytes of string    */
  26. #define    scanend            12    /* last two bytes of string    */
  27. #define    scanalign        20    /* dword-misalignment of string    */
  28. #define    nicematch        24    /* a good enough match size    */
  29. #define    bestlen            28    /* size of best match so far    */
  30. #define    scan            32    /* ptr to string wanting match    */
  31.  
  32. #define    LocalVarsSize        (36)
  33. /*    saved ebx        36 */
  34. /*    saved edi        40 */
  35. /*    saved esi        44 */
  36. /*    saved ebp        48 */
  37. /*    return address        52 */
  38. #define    deflatestate        56    /* the function arguments    */
  39. #define    curmatch        60
  40.  
  41. /* Offsets for fields in the deflate_state structure. These numbers
  42.  * are calculated from the definition of deflate_state, with the
  43.  * assumption that the compiler will dword-align the fields. (Thus,
  44.  * changing the definition of deflate_state could easily cause this
  45.  * program to crash horribly, without so much as a warning at
  46.  * compile time. Sigh.)
  47.  */
  48. #define    dsWSize            36
  49. #define    dsWMask            44
  50. #define    dsWindow        48
  51. #define    dsPrev            56
  52. #define    dsMatchLen        88
  53. #define    dsPrevMatch        92
  54. #define    dsStrStart        100
  55. #define    dsMatchStart        104
  56. #define    dsLookahead        108
  57. #define    dsPrevLen        112
  58. #define    dsMaxChainLen        116
  59. #define    dsGoodMatch        132
  60. #define    dsNiceMatch        136
  61.  
  62.  
  63. .file "match.S"
  64.  
  65. .globl    match_init, longest_match
  66.  
  67. .text
  68.  
  69. /* uInt longest_match(deflate_state *deflatestate, IPos curmatch) */
  70.  
  71. longest_match:
  72.  
  73. /* Save registers that the compiler may be using, and adjust %esp to    */
  74. /* make room for our stack frame.                    */
  75.  
  76.         pushl    %ebp
  77.         pushl    %edi
  78.         pushl    %esi
  79.         pushl    %ebx
  80.         subl    $LocalVarsSize, %esp
  81.  
  82. /* Retrieve the function arguments. %ecx will hold cur_match        */
  83. /* throughout the entire function. %edx will hold the pointer to the    */
  84. /* deflate_state structure during the function's setup (before        */
  85. /* entering the main loop).                        */
  86.  
  87.         movl    deflatestate(%esp), %edx
  88.         movl    curmatch(%esp), %ecx
  89.  
  90. /* uInt wmask = s->w_mask;                        */
  91. /* unsigned chain_length = s->max_chain_length;                */
  92. /* if (s->prev_length >= s->good_match) {                */
  93. /*     chain_length >>= 2;                        */
  94. /* }                                    */
  95.  
  96.         movl    dsPrevLen(%edx), %eax
  97.         movl    dsGoodMatch(%edx), %ebx
  98.         cmpl    %ebx, %eax
  99.         movl    dsWMask(%edx), %eax
  100.         movl    dsMaxChainLen(%edx), %ebx
  101.         jl    LastMatchGood
  102.         shrl    $2, %ebx
  103. LastMatchGood:
  104.  
  105. /* chainlen is decremented once beforehand so that the function can    */
  106. /* use the sign flag instead of the zero flag for the exit test.    */
  107. /* It is then shifted into the high word, to make room for the wmask    */
  108. /* value, which it will always accompany.                */
  109.  
  110.         decl    %ebx
  111.         shll    $16, %ebx
  112.         orl    %eax, %ebx
  113.         movl    %ebx, chainlenwmask(%esp)
  114.  
  115. /* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;    */
  116.  
  117.         movl    dsNiceMatch(%edx), %eax
  118.         movl    dsLookahead(%edx), %ebx
  119.         cmpl    %eax, %ebx
  120.         jl    LookaheadLess
  121.         movl    %eax, %ebx
  122. LookaheadLess:    movl    %ebx, nicematch(%esp)
  123.  
  124. /* register Bytef *scan = s->window + s->strstart;            */
  125.  
  126.         movl    dsWindow(%edx), %esi
  127.         movl    %esi, window(%esp)
  128.         movl    dsStrStart(%edx), %ebp
  129.         lea    (%esi,%ebp), %edi
  130.         movl    %edi, scan(%esp)
  131.  
  132. /* Determine how many bytes the scan ptr is off from being        */
  133. /* dword-aligned.                            */
  134.  
  135.         movl    %edi, %eax
  136.         negl    %eax
  137.         andl    $3, %eax
  138.         movl    %eax, scanalign(%esp)
  139.  
  140. /* IPos limit = s->strstart > (IPos)MAX_DIST(s) ?            */
  141. /*     s->strstart - (IPos)MAX_DIST(s) : NIL;                */
  142.  
  143.         movl    dsWSize(%edx), %eax
  144.         subl    $MIN_LOOKAHEAD, %eax
  145.         subl    %eax, %ebp
  146.         jg    LimitPositive
  147.         xorl    %ebp, %ebp
  148. LimitPositive:
  149.  
  150. /* int best_len = s->prev_length;                    */
  151.  
  152.         movl    dsPrevLen(%edx), %eax
  153.         movl    %eax, bestlen(%esp)
  154.  
  155. /* Store the sum of s->window + best_len in %esi locally, and in %esi.    */
  156.  
  157.         addl    %eax, %esi
  158.         movl    %esi, windowbestlen(%esp)
  159.  
  160. /* register ush scan_start = *(ushf*)scan;                */
  161. /* register ush scan_end   = *(ushf*)(scan+best_len-1);            */
  162. /* Posf *prev = s->prev;                        */
  163.  
  164.         movzwl    (%edi), %ebx
  165.         movl    %ebx, scanstart(%esp)
  166.         movzwl    -1(%edi,%eax), %ebx
  167.         movl    %ebx, scanend(%esp)
  168.         movl    dsPrev(%edx), %edi
  169.  
  170. /* Jump into the main loop.                        */
  171.  
  172.         movl    chainlenwmask(%esp), %edx
  173.         jmp    LoopEntry
  174.  
  175. .balign 16
  176.  
  177. /* do {
  178.  *     match = s->window + cur_match;
  179.  *     if (*(ushf*)(match+best_len-1) != scan_end ||
  180.  *         *(ushf*)match != scan_start) continue;
  181.  *     [...]
  182.  * } while ((cur_match = prev[cur_match & wmask]) > limit
  183.  *          && --chain_length != 0);
  184.  *
  185.  * Here is the inner loop of the function. The function will spend the
  186.  * majority of its time in this loop, and majority of that time will
  187.  * be spent in the first ten instructions.
  188.  *
  189.  * Within this loop:
  190.  * %ebx = scanend
  191.  * %ecx = curmatch
  192.  * %edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)
  193.  * %esi = windowbestlen - i.e., (window + bestlen)
  194.  * %edi = prev
  195.  * %ebp = limit
  196.  */
  197. LookupLoop:
  198.         andl    %edx, %ecx
  199.         movzwl    (%edi,%ecx,2), %ecx
  200.         cmpl    %ebp, %ecx
  201.         jbe    LeaveNow
  202.         subl    $0x00010000, %edx
  203.         js    LeaveNow
  204. LoopEntry:    movzwl    -1(%esi,%ecx), %eax
  205.         cmpl    %ebx, %eax
  206.         jnz    LookupLoop
  207.         movl    window(%esp), %eax
  208.         movzwl    (%eax,%ecx), %eax
  209.         cmpl    scanstart(%esp), %eax
  210.         jnz    LookupLoop
  211.  
  212. /* Store the current value of chainlen.                    */
  213.  
  214.         movl    %edx, chainlenwmask(%esp)
  215.  
  216. /* Point %edi to the string under scrutiny, and %esi to the string we    */
  217. /* are hoping to match it up with. In actuality, %esi and %edi are    */
  218. /* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is    */
  219. /* initialized to -(MAX_MATCH_8 - scanalign).                */
  220.  
  221.         movl    window(%esp), %esi
  222.         movl    scan(%esp), %edi
  223.         addl    %ecx, %esi
  224.         movl    scanalign(%esp), %eax
  225.         movl    $(-MAX_MATCH_8), %edx
  226.         lea    MAX_MATCH_8(%edi,%eax), %edi
  227.         lea    MAX_MATCH_8(%esi,%eax), %esi
  228.  
  229. /* Test the strings for equality, 8 bytes at a time. At the end,
  230.  * adjust %edx so that it is offset to the exact byte that mismatched.
  231.  *
  232.  * We already know at this point that the first three bytes of the
  233.  * strings match each other, and they can be safely passed over before
  234.  * starting the compare loop. So what this code does is skip over 0-3
  235.  * bytes, as much as necessary in order to dword-align the %edi
  236.  * pointer. (%esi will still be misaligned three times out of four.)
  237.  *
  238.  * It should be confessed that this loop usually does not represent
  239.  * much of the total running time. Replacing it with a more
  240.  * straightforward "rep cmpsb" would not drastically degrade
  241.  * performance.
  242.  */
  243. LoopCmps:
  244.         movl    (%esi,%edx), %eax
  245.         xorl    (%edi,%edx), %eax
  246.         jnz    LeaveLoopCmps
  247.         movl    4(%esi,%edx), %eax
  248.         xorl    4(%edi,%edx), %eax
  249.         jnz    LeaveLoopCmps4
  250.         addl    $8, %edx
  251.         jnz    LoopCmps
  252.         jmp    LenMaximum
  253. LeaveLoopCmps4:    addl    $4, %edx
  254. LeaveLoopCmps:    testl    $0x0000FFFF, %eax
  255.         jnz    LenLower
  256.         addl    $2, %edx
  257.         shrl    $16, %eax
  258. LenLower:    subb    $1, %al
  259.         adcl    $0, %edx
  260.  
  261. /* Calculate the length of the match. If it is longer than MAX_MATCH,    */
  262. /* then automatically accept it as the best possible match and leave.    */
  263.  
  264.         lea    (%edi,%edx), %eax
  265.         movl    scan(%esp), %edi
  266.         subl    %edi, %eax
  267.         cmpl    $MAX_MATCH, %eax
  268.         jge    LenMaximum
  269.  
  270. /* If the length of the match is not longer than the best match we    */
  271. /* have so far, then forget it and return to the lookup loop.        */
  272.  
  273.         movl    deflatestate(%esp), %edx
  274.         movl    bestlen(%esp), %ebx
  275.         cmpl    %ebx, %eax
  276.         jg    LongerMatch
  277.         movl    windowbestlen(%esp), %esi
  278.         movl    dsPrev(%edx), %edi
  279.         movl    scanend(%esp), %ebx
  280.         movl    chainlenwmask(%esp), %edx
  281.         jmp    LookupLoop
  282.  
  283. /*         s->match_start = cur_match;                    */
  284. /*         best_len = len;                        */
  285. /*         if (len >= nice_match) break;                */
  286. /*         scan_end = *(ushf*)(scan+best_len-1);            */
  287.  
  288. LongerMatch:    movl    nicematch(%esp), %ebx
  289.         movl    %eax, bestlen(%esp)
  290.         movl    %ecx, dsMatchStart(%edx)
  291.         cmpl    %ebx, %eax
  292.         jge    LeaveNow
  293.         movl    window(%esp), %esi
  294.         addl    %eax, %esi
  295.         movl    %esi, windowbestlen(%esp)
  296.         movzwl    -1(%edi,%eax), %ebx
  297.         movl    dsPrev(%edx), %edi
  298.         movl    %ebx, scanend(%esp)
  299.         movl    chainlenwmask(%esp), %edx
  300.         jmp    LookupLoop
  301.  
  302. /* Accept the current string, with the maximum possible length.        */
  303.  
  304. LenMaximum:    movl    deflatestate(%esp), %edx
  305.         movl    $MAX_MATCH, bestlen(%esp)
  306.         movl    %ecx, dsMatchStart(%edx)
  307.  
  308. /* if ((uInt)best_len <= s->lookahead) return (uInt)best_len;        */
  309. /* return s->lookahead;                            */
  310.  
  311. LeaveNow:
  312.         movl    deflatestate(%esp), %edx
  313.         movl    bestlen(%esp), %ebx
  314.         movl    dsLookahead(%edx), %eax
  315.         cmpl    %eax, %ebx
  316.         jg    LookaheadRet
  317.         movl    %ebx, %eax
  318. LookaheadRet:
  319.  
  320. /* Restore the stack and return from whence we came.            */
  321.  
  322.         addl    $LocalVarsSize, %esp
  323.         popl    %ebx
  324.         popl    %esi
  325.         popl    %edi
  326.         popl    %ebp
  327. match_init:    ret
  328.