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>
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 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 */
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
/* 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; */
96
movl dsPrevLen(%edx), %eax
97
movl dsGoodMatch(%edx), %ebx
99
movl dsWMask(%edx), %eax
100
movl dsMaxChainLen(%edx), %ebx
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. */
113
movl %ebx, chainlenwmask(%esp)
115
/* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; */
117
movl dsNiceMatch(%edx), %eax
118
movl dsLookahead(%edx), %ebx
122
LookaheadLess: movl %ebx, nicematch(%esp)
124
/* register Bytef *scan = s->window + s->strstart; */
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)
132
/* Determine how many bytes the scan ptr is off from being */
138
movl %eax, scanalign(%esp)
140
/* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */
141
/* s->strstart - (IPos)MAX_DIST(s) : NIL; */
143
movl dsWSize(%edx), %eax
144
subl $MIN_LOOKAHEAD, %eax
150
/* int best_len = s->prev_length; */
152
movl dsPrevLen(%edx), %eax
153
movl %eax, bestlen(%esp)
155
/* Store the sum of s->window + best_len in %esi locally, and in %esi. */
158
movl %esi, windowbestlen(%esp)
160
/* register ush scan_start = *(ushf*)scan; */
161
/* register ush scan_end = *(ushf*)(scan+best_len-1); */
162
/* Posf *prev = s->prev; */
165
movl %ebx, scanstart(%esp)
166
movzwl -1(%edi,%eax), %ebx
167
movl %ebx, scanend(%esp)
168
movl dsPrev(%edx), %edi
170
/* Jump into the main loop. */
172
movl chainlenwmask(%esp), %edx
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.
192
* %edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)
193
* %esi = windowbestlen - i.e., (window + bestlen)
199
movzwl (%edi,%ecx,2), %ecx
202
subl $0x00010000, %edx
204
LoopEntry: movzwl -1(%esi,%ecx), %eax
207
movl window(%esp), %eax
208
movzwl (%eax,%ecx), %eax
209
cmpl scanstart(%esp), %eax
212
/* Store the current value of chainlen. */
214
movl %edx, chainlenwmask(%esp)
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). */
221
movl window(%esp), %esi
222
movl scan(%esp), %edi
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
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.
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.)
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
244
movl (%esi,%edx), %eax
245
xorl (%edi,%edx), %eax
247
movl 4(%esi,%edx), %eax
248
xorl 4(%edi,%edx), %eax
253
LeaveLoopCmps4: addl $4, %edx
254
LeaveLoopCmps: testl $0x0000FFFF, %eax
258
LenLower: subb $1, %al
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. */
264
lea (%edi,%edx), %eax
265
movl scan(%esp), %edi
267
cmpl $MAX_MATCH, %eax
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. */
273
movl deflatestate(%esp), %edx
274
movl bestlen(%esp), %ebx
277
movl windowbestlen(%esp), %esi
278
movl dsPrev(%edx), %edi
279
movl scanend(%esp), %ebx
280
movl chainlenwmask(%esp), %edx
283
/* s->match_start = cur_match; */
284
/* best_len = len; */
285
/* if (len >= nice_match) break; */
286
/* scan_end = *(ushf*)(scan+best_len-1); */
288
LongerMatch: movl nicematch(%esp), %ebx
289
movl %eax, bestlen(%esp)
290
movl %ecx, dsMatchStart(%edx)
293
movl window(%esp), %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
302
/* Accept the current string, with the maximum possible length. */
304
LenMaximum: movl deflatestate(%esp), %edx
305
movl $MAX_MATCH, bestlen(%esp)
306
movl %ecx, dsMatchStart(%edx)
308
/* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */
309
/* return s->lookahead; */
312
movl deflatestate(%esp), %edx
313
movl bestlen(%esp), %ebx
314
movl dsLookahead(%edx), %eax
320
/* Restore the stack and return from whence we came. */
322
addl $LocalVarsSize, %esp