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 _ipcomp_match_init
11
#define longest_match _ipcomp_longest_match
13
#define match_init ipcomp_match_init
14
#define longest_match ipcomp_longest_match
17
#define MAX_MATCH (258)
19
#define MIN_LOOKAHEAD (MAX_MATCH + MIN_MATCH + 1)
20
#define MAX_MATCH_8 ((MAX_MATCH + 7) & ~7)
22
/* stack frame offsets */
24
#define wmask 0 /* local copy of s->wmask */
25
#define window 4 /* local copy of s->window */
26
#define windowbestlen 8 /* s->window + bestlen */
27
#define chainlenscanend 12 /* high word: current chain len */
28
/* low word: last bytes sought */
29
#define scanstart 16 /* first two bytes of string */
30
#define scanalign 20 /* dword-misalignment of string */
31
#define nicematch 24 /* a good enough match size */
32
#define bestlen 28 /* size of best match so far */
33
#define scan 32 /* ptr to string wanting match */
35
#define LocalVarsSize (36)
40
/* return address 52 */
41
#define deflatestate 56 /* the function arguments */
44
/* Offsets for fields in the deflate_state structure. These numbers
45
* are calculated from the definition of deflate_state, with the
46
* assumption that the compiler will dword-align the fields. (Thus,
47
* changing the definition of deflate_state could easily cause this
48
* program to crash horribly, without so much as a warning at
49
* compile time. Sigh.)
56
#define dsPrevMatch 92
57
#define dsStrStart 100
58
#define dsMatchStart 104
59
#define dsLookahead 108
61
#define dsMaxChainLen 116
62
#define dsGoodMatch 132
63
#define dsNiceMatch 136
68
.globl match_init, longest_match
72
/* uInt longest_match(deflate_state *deflatestate, IPos curmatch) */
76
/* Save registers that the compiler may be using, and adjust %esp to */
77
/* make room for our stack frame. */
83
subl $LocalVarsSize, %esp
85
/* Retrieve the function arguments. %ecx will hold cur_match */
86
/* throughout the entire function. %edx will hold the pointer to the */
87
/* deflate_state structure during the function's setup (before */
88
/* entering the main loop). */
90
movl deflatestate(%esp), %edx
91
movl curmatch(%esp), %ecx
93
/* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; */
95
movl dsNiceMatch(%edx), %eax
96
movl dsLookahead(%edx), %ebx
100
LookaheadLess: movl %ebx, nicematch(%esp)
102
/* register Bytef *scan = s->window + s->strstart; */
104
movl dsWindow(%edx), %esi
105
movl %esi, window(%esp)
106
movl dsStrStart(%edx), %ebp
107
lea (%esi,%ebp), %edi
108
movl %edi, scan(%esp)
110
/* Determine how many bytes the scan ptr is off from being */
116
movl %eax, scanalign(%esp)
118
/* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */
119
/* s->strstart - (IPos)MAX_DIST(s) : NIL; */
121
movl dsWSize(%edx), %eax
122
subl $MIN_LOOKAHEAD, %eax
128
/* unsigned chain_length = s->max_chain_length; */
129
/* if (s->prev_length >= s->good_match) { */
130
/* chain_length >>= 2; */
133
movl dsPrevLen(%edx), %eax
134
movl dsGoodMatch(%edx), %ebx
136
movl dsMaxChainLen(%edx), %ebx
141
/* chainlen is decremented once beforehand so that the function can */
142
/* use the sign flag instead of the zero flag for the exit test. */
143
/* It is then shifted into the high word, to make room for the scanend */
144
/* scanend value, which it will always accompany. */
149
/* int best_len = s->prev_length; */
151
movl dsPrevLen(%edx), %eax
152
movl %eax, bestlen(%esp)
154
/* Store the sum of s->window + best_len in %esi locally, and in %esi. */
157
movl %esi, windowbestlen(%esp)
159
/* register ush scan_start = *(ushf*)scan; */
160
/* register ush scan_end = *(ushf*)(scan+best_len-1); */
163
movw %bx, scanstart(%esp)
164
movw -1(%edi,%eax), %bx
165
movl %ebx, chainlenscanend(%esp)
167
/* Posf *prev = s->prev; */
168
/* uInt wmask = s->w_mask; */
170
movl dsPrev(%edx), %edi
171
movl dsWMask(%edx), %edx
172
mov %edx, wmask(%esp)
174
/* Jump into the main loop. */
181
* match = s->window + cur_match;
182
* if (*(ushf*)(match+best_len-1) != scan_end ||
183
* *(ushf*)match != scan_start) continue;
185
* } while ((cur_match = prev[cur_match & wmask]) > limit
186
* && --chain_length != 0);
188
* Here is the inner loop of the function. The function will spend the
189
* majority of its time in this loop, and majority of that time will
190
* be spent in the first ten instructions.
193
* %ebx = chainlenscanend - i.e., ((chainlen << 16) | scanend)
195
* %edx = curmatch & wmask
196
* %esi = windowbestlen - i.e., (window + bestlen)
200
* Two optimization notes on the choice of instructions:
202
* The first instruction uses a 16-bit address, which costs an extra,
203
* unpairable cycle. This is cheaper than doing a 32-bit access and
204
* zeroing the high word, due to the 3-cycle misalignment penalty which
205
* would occur half the time. This also turns out to be cheaper than
206
* doing two separate 8-bit accesses, as the memory is so rarely in the
209
* The window buffer, however, apparently spends a lot of time in the
210
* cache, and so it is faster to retrieve the word at the end of the
211
* match string with two 8-bit loads. The instructions that test the
212
* word at the beginning of the match string, however, are executed
213
* much less frequently, and there it was cheaper to use 16-bit
214
* instructions, which avoided the necessity of saving off and
215
* subsequently reloading one of the other registers.
219
movw (%edi,%edx,2), %cx /* 2 U pipe */
220
movl wmask(%esp), %edx /* 2 V pipe */
221
cmpl %ebp, %ecx /* 3 U pipe */
222
jbe LeaveNow /* 3 V pipe */
223
subl $0x00010000, %ebx /* 4 U pipe */
224
js LeaveNow /* 4 V pipe */
225
LoopEntry: movb -1(%esi,%ecx), %al /* 5 U pipe */
226
andl %ecx, %edx /* 5 V pipe */
227
cmpb %bl, %al /* 6 U pipe */
228
jnz LookupLoop /* 6 V pipe */
229
movb (%esi,%ecx), %ah
232
movl window(%esp), %eax
233
movw (%eax,%ecx), %ax
234
cmpw scanstart(%esp), %ax
237
/* Store the current value of chainlen. */
239
movl %ebx, chainlenscanend(%esp)
241
/* Point %edi to the string under scrutiny, and %esi to the string we */
242
/* are hoping to match it up with. In actuality, %esi and %edi are */
243
/* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is */
244
/* initialized to -(MAX_MATCH_8 - scanalign). */
246
movl window(%esp), %esi
247
movl scan(%esp), %edi
249
movl scanalign(%esp), %eax
250
movl $(-MAX_MATCH_8), %edx
251
lea MAX_MATCH_8(%edi,%eax), %edi
252
lea MAX_MATCH_8(%esi,%eax), %esi
254
/* Test the strings for equality, 8 bytes at a time. At the end,
255
* adjust %edx so that it is offset to the exact byte that mismatched.
257
* We already know at this point that the first three bytes of the
258
* strings match each other, and they can be safely passed over before
259
* starting the compare loop. So what this code does is skip over 0-3
260
* bytes, as much as necessary in order to dword-align the %edi
261
* pointer. (%esi will still be misaligned three times out of four.)
263
* It should be confessed that this loop usually does not represent
264
* much of the total running time. Replacing it with a more
265
* straightforward "rep cmpsb" would not drastically degrade
269
movl (%esi,%edx), %eax
270
movl (%edi,%edx), %ebx
273
movl 4(%esi,%edx), %eax
274
movl 4(%edi,%edx), %ebx
280
LeaveLoopCmps4: addl $4, %edx
281
LeaveLoopCmps: testl $0x0000FFFF, %eax
285
LenLower: subb $1, %al
288
/* Calculate the length of the match. If it is longer than MAX_MATCH, */
289
/* then automatically accept it as the best possible match and leave. */
291
lea (%edi,%edx), %eax
292
movl scan(%esp), %edi
294
cmpl $MAX_MATCH, %eax
297
/* If the length of the match is not longer than the best match we */
298
/* have so far, then forget it and return to the lookup loop. */
300
movl deflatestate(%esp), %edx
301
movl bestlen(%esp), %ebx
304
movl chainlenscanend(%esp), %ebx
305
movl windowbestlen(%esp), %esi
306
movl dsPrev(%edx), %edi
307
movl wmask(%esp), %edx
311
/* s->match_start = cur_match; */
312
/* best_len = len; */
313
/* if (len >= nice_match) break; */
314
/* scan_end = *(ushf*)(scan+best_len-1); */
316
LongerMatch: movl nicematch(%esp), %ebx
317
movl %eax, bestlen(%esp)
318
movl %ecx, dsMatchStart(%edx)
321
movl window(%esp), %esi
323
movl %esi, windowbestlen(%esp)
324
movl chainlenscanend(%esp), %ebx
325
movw -1(%edi,%eax), %bx
326
movl dsPrev(%edx), %edi
327
movl %ebx, chainlenscanend(%esp)
328
movl wmask(%esp), %edx
332
/* Accept the current string, with the maximum possible length. */
334
LenMaximum: movl deflatestate(%esp), %edx
335
movl $MAX_MATCH, bestlen(%esp)
336
movl %ecx, dsMatchStart(%edx)
338
/* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */
339
/* return s->lookahead; */
342
movl deflatestate(%esp), %edx
343
movl bestlen(%esp), %ebx
344
movl dsLookahead(%edx), %eax
350
/* Restore the stack and return from whence we came. */
352
addl $LocalVarsSize, %esp