Context Navigation

match.S @ 8198f69

4.115

Last change on this file since 8198f69 was 8198f69, checked in by Ralf Corsepius <ralf.corsepius@…>, on 03/18/11 at 10:10:55
Import zlib-1.2.3
Property mode set to `100644`
File size: 10.6 KB

Line
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

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

Download in other formats:

Original Format