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>
5 * This is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License.
10 #define match_init _match_init
11 #define longest_match _longest_match
14 #define MAX_MATCH (258)
16 #define MIN_LOOKAHEAD (MAX_MATCH + MIN_MATCH + 1)
17 #define MAX_MATCH_8 ((MAX_MATCH + 7) & ~7)
19 /* stack frame offsets */
21 #define wmask 0 /* local copy of s->wmask */
22 #define window 4 /* local copy of s->window */
23 #define windowbestlen 8 /* s->window + bestlen */
24 #define chainlenscanend 12 /* high word: current chain len */
25 /* low word: last bytes sought */
26 #define scanstart 16 /* first 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 */
32 #define LocalVarsSize (36)
37 /* return address 52 */
38 #define deflatestate 56 /* the function arguments */
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.)
53 #define dsPrevMatch 92
54 #define dsStrStart 100
55 #define dsMatchStart 104
56 #define dsLookahead 108
58 #define dsMaxChainLen 116
59 #define dsGoodMatch 132
60 #define dsNiceMatch 136
65 .globl match_init, longest_match
69 /* uInt longest_match(deflate_state *deflatestate, IPos curmatch) */
73 /* Save registers that the compiler may be using, and adjust %esp to */
74 /* make room for our stack frame. */
80 subl $LocalVarsSize, %esp
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). */
87 movl deflatestate(%esp), %edx
88 movl curmatch(%esp), %ecx
90 /* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; */
92 movl dsNiceMatch(%edx), %eax
93 movl dsLookahead(%edx), %ebx
97 LookaheadLess: movl %ebx, nicematch(%esp)
99 /* register Bytef *scan = s->window + s->strstart; */
101 movl dsWindow(%edx), %esi
102 movl %esi, window(%esp)
103 movl dsStrStart(%edx), %ebp
104 lea (%esi,%ebp), %edi
105 movl %edi, scan(%esp)
107 /* Determine how many bytes the scan ptr is off from being */
113 movl %eax, scanalign(%esp)
115 /* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */
116 /* s->strstart - (IPos)MAX_DIST(s) : NIL; */
118 movl dsWSize(%edx), %eax
119 subl $MIN_LOOKAHEAD, %eax
125 /* unsigned chain_length = s->max_chain_length; */
126 /* if (s->prev_length >= s->good_match) { */
127 /* chain_length >>= 2; */
130 movl dsPrevLen(%edx), %eax
131 movl dsGoodMatch(%edx), %ebx
133 movl dsMaxChainLen(%edx), %ebx
138 /* chainlen is decremented once beforehand so that the function can */
139 /* use the sign flag instead of the zero flag for the exit test. */
140 /* It is then shifted into the high word, to make room for the scanend */
141 /* scanend value, which it will always accompany. */
146 /* int best_len = s->prev_length; */
148 movl dsPrevLen(%edx), %eax
149 movl %eax, bestlen(%esp)
151 /* Store the sum of s->window + best_len in %esi locally, and in %esi. */
154 movl %esi, windowbestlen(%esp)
156 /* register ush scan_start = *(ushf*)scan; */
157 /* register ush scan_end = *(ushf*)(scan+best_len-1); */
160 movw %bx, scanstart(%esp)
161 movw -1(%edi,%eax), %bx
162 movl %ebx, chainlenscanend(%esp)
164 /* Posf *prev = s->prev; */
165 /* uInt wmask = s->w_mask; */
167 movl dsPrev(%edx), %edi
168 movl dsWMask(%edx), %edx
169 mov %edx, wmask(%esp)
171 /* Jump into the main loop. */
178 * match = s->window + cur_match;
179 * if (*(ushf*)(match+best_len-1) != scan_end ||
180 * *(ushf*)match != scan_start) continue;
182 * } while ((cur_match = prev[cur_match & wmask]) > limit
183 * && --chain_length != 0);
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.
190 * %ebx = chainlenscanend - i.e., ((chainlen << 16) | scanend)
192 * %edx = curmatch & wmask
193 * %esi = windowbestlen - i.e., (window + bestlen)
197 * Two optimization notes on the choice of instructions:
199 * The first instruction uses a 16-bit address, which costs an extra,
200 * unpairable cycle. This is cheaper than doing a 32-bit access and
201 * zeroing the high word, due to the 3-cycle misalignment penalty which
202 * would occur half the time. This also turns out to be cheaper than
203 * doing two separate 8-bit accesses, as the memory is so rarely in the
206 * The window buffer, however, apparently spends a lot of time in the
207 * cache, and so it is faster to retrieve the word at the end of the
208 * match string with two 8-bit loads. The instructions that test the
209 * word at the beginning of the match string, however, are executed
210 * much less frequently, and there it was cheaper to use 16-bit
211 * instructions, which avoided the necessity of saving off and
212 * subsequently reloading one of the other registers.
216 movw (%edi,%edx,2), %cx /* 2 U pipe */
217 movl wmask(%esp), %edx /* 2 V pipe */
218 cmpl %ebp, %ecx /* 3 U pipe */
219 jbe LeaveNow /* 3 V pipe */
220 subl $0x00010000, %ebx /* 4 U pipe */
221 js LeaveNow /* 4 V pipe */
222 LoopEntry: movb -1(%esi,%ecx), %al /* 5 U pipe */
223 andl %ecx, %edx /* 5 V pipe */
224 cmpb %bl, %al /* 6 U pipe */
225 jnz LookupLoop /* 6 V pipe */
226 movb (%esi,%ecx), %ah
229 movl window(%esp), %eax
230 movw (%eax,%ecx), %ax
231 cmpw scanstart(%esp), %ax
234 /* Store the current value of chainlen. */
236 movl %ebx, chainlenscanend(%esp)
238 /* Point %edi to the string under scrutiny, and %esi to the string we */
239 /* are hoping to match it up with. In actuality, %esi and %edi are */
240 /* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is */
241 /* initialized to -(MAX_MATCH_8 - scanalign). */
243 movl window(%esp), %esi
244 movl scan(%esp), %edi
246 movl scanalign(%esp), %eax
247 movl $(-MAX_MATCH_8), %edx
248 lea MAX_MATCH_8(%edi,%eax), %edi
249 lea MAX_MATCH_8(%esi,%eax), %esi
251 /* Test the strings for equality, 8 bytes at a time. At the end,
252 * adjust %edx so that it is offset to the exact byte that mismatched.
254 * We already know at this point that the first three bytes of the
255 * strings match each other, and they can be safely passed over before
256 * starting the compare loop. So what this code does is skip over 0-3
257 * bytes, as much as necessary in order to dword-align the %edi
258 * pointer. (%esi will still be misaligned three times out of four.)
260 * It should be confessed that this loop usually does not represent
261 * much of the total running time. Replacing it with a more
262 * straightforward "rep cmpsb" would not drastically degrade
266 movl (%esi,%edx), %eax
267 movl (%edi,%edx), %ebx
270 movl 4(%esi,%edx), %eax
271 movl 4(%edi,%edx), %ebx
277 LeaveLoopCmps4: addl $4, %edx
278 LeaveLoopCmps: testl $0x0000FFFF, %eax
282 LenLower: subb $1, %al
285 /* Calculate the length of the match. If it is longer than MAX_MATCH, */
286 /* then automatically accept it as the best possible match and leave. */
288 lea (%edi,%edx), %eax
289 movl scan(%esp), %edi
291 cmpl $MAX_MATCH, %eax
294 /* If the length of the match is not longer than the best match we */
295 /* have so far, then forget it and return to the lookup loop. */
297 movl deflatestate(%esp), %edx
298 movl bestlen(%esp), %ebx
301 movl chainlenscanend(%esp), %ebx
302 movl windowbestlen(%esp), %esi
303 movl dsPrev(%edx), %edi
304 movl wmask(%esp), %edx
308 /* s->match_start = cur_match; */
309 /* best_len = len; */
310 /* if (len >= nice_match) break; */
311 /* scan_end = *(ushf*)(scan+best_len-1); */
313 LongerMatch: movl nicematch(%esp), %ebx
314 movl %eax, bestlen(%esp)
315 movl %ecx, dsMatchStart(%edx)
318 movl window(%esp), %esi
320 movl %esi, windowbestlen(%esp)
321 movl chainlenscanend(%esp), %ebx
322 movw -1(%edi,%eax), %bx
323 movl dsPrev(%edx), %edi
324 movl %ebx, chainlenscanend(%esp)
325 movl wmask(%esp), %edx
329 /* Accept the current string, with the maximum possible length. */
331 LenMaximum: movl deflatestate(%esp), %edx
332 movl $MAX_MATCH, bestlen(%esp)
333 movl %ecx, dsMatchStart(%edx)
335 /* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */
336 /* return s->lookahead; */
339 movl deflatestate(%esp), %edx
340 movl bestlen(%esp), %ebx
341 movl dsLookahead(%edx), %eax
347 /* Restore the stack and return from whence we came. */
349 addl $LocalVarsSize, %esp