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