match.S
上传用户:zhongxx05
上传日期:2007-06-06
资源大小:33641k
文件大小:10k
源码类别:

Symbian

开发平台:

C/C++

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