match.S@ 29945

Last change on this file since 29945 was 6392, checked in by vboxsync, 17 years ago
export libpng and zlib so Windows and OS/2 builds cleanly.
Property svn:eol-style set to `native`
File size: 10.0 KB

Line
1	/* match.s -- Pentium-optimized version of longest_match()
2	* Written for zlib 1.1.2
3	* Copyright (C) 1998 Brian Raiter <[email protected]>
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	#define dsWSize 36
49	#define dsWMask 44
50	#define dsWindow 48
51	#define dsPrev 56
52	#define dsMatchLen 88
53	#define dsPrevMatch 92
54	#define dsStrStart 100
55	#define dsMatchStart 104
56	#define dsLookahead 108
57	#define dsPrevLen 112
58	#define dsMaxChainLen 116
59	#define dsGoodMatch 132
60	#define dsNiceMatch 136
61
62
63	.file "match.S"
64
65	.globl match_init, longest_match
66
67	.text
68
69	/* uInt longest_match(deflate_state deflatestate, IPos curmatch) /
70
71	longest_match:
72
73	/* Save registers that the compiler may be using, and adjust %esp to */
74	/* make room for our stack frame. */
75
76	pushl %ebp
77	pushl %edi
78	pushl %esi
79	pushl %ebx
80	subl $LocalVarsSize, %esp
81
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). */
86
87	movl deflatestate(%esp), %edx
88	movl curmatch(%esp), %ecx
89
90	/* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; */
91
92	movl dsNiceMatch(%edx), %eax
93	movl dsLookahead(%edx), %ebx
94	cmpl %eax, %ebx
95	jl LookaheadLess
96	movl %eax, %ebx
97	LookaheadLess: movl %ebx, nicematch(%esp)
98
99	/* register Bytef scan = s->window + s->strstart; /
100
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)
106
107	/* Determine how many bytes the scan ptr is off from being */
108	/* dword-aligned. */
109
110	movl %edi, %eax
111	negl %eax
112	andl $3, %eax
113	movl %eax, scanalign(%esp)
114
115	/* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */
116	/* s->strstart - (IPos)MAX_DIST(s) : NIL; */
117
118	movl dsWSize(%edx), %eax
119	subl $MIN_LOOKAHEAD, %eax
120	subl %eax, %ebp
121	jg LimitPositive
122	xorl %ebp, %ebp
123	LimitPositive:
124
125	/* unsigned chain_length = s->max_chain_length; */
126	/* if (s->prev_length >= s->good_match) { */
127	/* chain_length >>= 2; */
128	/* } */
129
130	movl dsPrevLen(%edx), %eax
131	movl dsGoodMatch(%edx), %ebx
132	cmpl %ebx, %eax
133	movl dsMaxChainLen(%edx), %ebx
134	jl LastMatchGood
135	shrl $2, %ebx
136	LastMatchGood:
137
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. */
142
143	decl %ebx
144	shll $16, %ebx
145
146	/* int best_len = s->prev_length; */
147
148	movl dsPrevLen(%edx), %eax
149	movl %eax, bestlen(%esp)
150
151	/* Store the sum of s->window + best_len in %esi locally, and in %esi. */
152
153	addl %eax, %esi
154	movl %esi, windowbestlen(%esp)
155
156	/* register ush scan_start = (ushf)scan; */
157	/* register ush scan_end = (ushf)(scan+best_len-1); */
158
159	movw (%edi), %bx
160	movw %bx, scanstart(%esp)
161	movw -1(%edi,%eax), %bx
162	movl %ebx, chainlenscanend(%esp)
163
164	/* Posf prev = s->prev; /
165	/* uInt wmask = s->w_mask; */
166
167	movl dsPrev(%edx), %edi
168	movl dsWMask(%edx), %edx
169	mov %edx, wmask(%esp)
170
171	/* Jump into the main loop. */
172
173	jmp LoopEntry
174
175	.balign 16
176
177	/* do {
178	* match = s->window + cur_match;
179	* if ((ushf)(match+best_len-1) != scan_end \|\|
180	* (ushf)match != scan_start) continue;
181	* [...]
182	* } while ((cur_match = prev[cur_match & wmask]) > limit
183	* && --chain_length != 0);
184	*
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.
188	*
189	* Within this loop:
190	* %ebx = chainlenscanend - i.e., ((chainlen << 16) \| scanend)
191	* %ecx = curmatch
192	* %edx = curmatch & wmask
193	* %esi = windowbestlen - i.e., (window + bestlen)
194	* %edi = prev
195	* %ebp = limit
196	*
197	* Two optimization notes on the choice of instructions:
198	*
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
204	* L1 cache.
205	*
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.
213	*/
214	LookupLoop:
215	/* 1 U & V */
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
227	cmpb %bh, %ah
228	jnz LookupLoop
229	movl window(%esp), %eax
230	movw (%eax,%ecx), %ax
231	cmpw scanstart(%esp), %ax
232	jnz LookupLoop
233
234	/* Store the current value of chainlen. */
235
236	movl %ebx, chainlenscanend(%esp)
237
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). */
242
243	movl window(%esp), %esi
244	movl scan(%esp), %edi
245	addl %ecx, %esi
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
250
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.
253	*
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.)
259	*
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
263	* performance.
264	*/
265	LoopCmps:
266	movl (%esi,%edx), %eax
267	movl (%edi,%edx), %ebx
268	xorl %ebx, %eax
269	jnz LeaveLoopCmps
270	movl 4(%esi,%edx), %eax
271	movl 4(%edi,%edx), %ebx
272	xorl %ebx, %eax
273	jnz LeaveLoopCmps4
274	addl $8, %edx
275	jnz LoopCmps
276	jmp LenMaximum
277	LeaveLoopCmps4: addl $4, %edx
278	LeaveLoopCmps: testl $0x0000FFFF, %eax
279	jnz LenLower
280	addl $2, %edx
281	shrl $16, %eax
282	LenLower: subb $1, %al
283	adcl $0, %edx
284
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. */
287
288	lea (%edi,%edx), %eax
289	movl scan(%esp), %edi
290	subl %edi, %eax
291	cmpl $MAX_MATCH, %eax
292	jge LenMaximum
293
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. */
296
297	movl deflatestate(%esp), %edx
298	movl bestlen(%esp), %ebx
299	cmpl %ebx, %eax
300	jg LongerMatch
301	movl chainlenscanend(%esp), %ebx
302	movl windowbestlen(%esp), %esi
303	movl dsPrev(%edx), %edi
304	movl wmask(%esp), %edx
305	andl %ecx, %edx
306	jmp LookupLoop
307
308	/* s->match_start = cur_match; */
309	/* best_len = len; */
310	/* if (len >= nice_match) break; */
311	/* scan_end = (ushf)(scan+best_len-1); */
312
313	LongerMatch: movl nicematch(%esp), %ebx
314	movl %eax, bestlen(%esp)
315	movl %ecx, dsMatchStart(%edx)
316	cmpl %ebx, %eax
317	jge LeaveNow
318	movl window(%esp), %esi
319	addl %eax, %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
326	andl %ecx, %edx
327	jmp LookupLoop
328
329	/* Accept the current string, with the maximum possible length. */
330
331	LenMaximum: movl deflatestate(%esp), %edx
332	movl $MAX_MATCH, bestlen(%esp)
333	movl %ecx, dsMatchStart(%edx)
334
335	/* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */
336	/* return s->lookahead; */
337
338	LeaveNow:
339	movl deflatestate(%esp), %edx
340	movl bestlen(%esp), %ebx
341	movl dsLookahead(%edx), %eax
342	cmpl %eax, %ebx
343	jg LookaheadRet
344	movl %ebx, %eax
345	LookaheadRet:
346
347	/* Restore the stack and return from whence we came. */
348
349	addl $LocalVarsSize, %esp
350	popl %ebx
351	popl %esi
352	popl %edi
353	popl %ebp
354	match_init: ret

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format