1 /* match.s -- optional optimized asm version of longest match in deflate.c
2 * Copyright (C) 2002 Free Software Foundation, Inc.
3 * Copyright (C) 1992-1993 Jean-loup Gailly
4 * This is free software; you can redistribute it and/or modify it under the
5 * terms of the GNU General Public License, see the file COPYING.
7 * The 68020 version has been written by Francesco Potorti` <pot@cnuce.cnr.it>
8 * with adaptations by Carsten Steger <stegerc@informatik.tu-muenchen.de>,
9 * Andreas Schwab <schwab@lamothe.informatik.uni-dortmund.de> and
10 * Kristoffer Eriksson <ske@pkmab.se>
13 /* $Id: match.S,v 0.14 1993/06/11 18:33:24 jloup Exp $ */
15 /* Preprocess with -DNO_UNDERLINE if your C compiler does not prefix
16 * external symbols with an underline character '_'.
20 # define _window window
21 # define _match_start match_start
22 # define _prev_length prev_length
23 # define _good_match good_match
24 # define _nice_match nice_match
25 # define _strstart strstart
26 # define _max_chain_length max_chain_length
28 # define _match_init match_init
29 # define _longest_match longest_match
33 error: DYN_ALLOC not yet supported in match.s
36 #if defined(i386) || defined(_I386) || defined(__i386) || defined(__i386__)
38 /* This version is for 386 Unix or OS/2 in 32 bit mode.
39 * Warning: it uses the AT&T syntax: mov source,dest
40 * This file is only optional. If you want to force the C version,
41 * add -DNO_ASM to CFLAGS in Makefile and set OBJA to an empty string.
42 * If you have reduced WSIZE in gzip.h, then change its value below.
43 * This version assumes static allocation of the arrays (-DDYN_ALLOC not used).
49 #define MAX_MATCH2 $128 /* MAX_MATCH/2-1 */
52 #define MAX_DIST WSIZE - MAX_MATCH - MIN_MATCH - 1
62 /*-----------------------------------------------------------------------
63 * Set match_start to the longest match starting at the given string and
64 * return its length. Matches shorter or equal to prev_length are discarded,
65 * in which case the result is equal to prev_length and match_start is
67 * IN assertions: cur_match is the head of the hash chain for the current
68 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
71 _longest_match: /* int longest_match(cur_match) */
73 #define cur_match 20(%esp)
74 /* return address */ /* esp+16 */
75 push %ebp /* esp+12 */
83 * chain_length equ ebp
88 mov _max_chain_length,%ebp /* chain_length = max_chain_length */
91 sub MAX_DIST,%edx /* limit = strstart-MAX_DIST */
93 sub %edx,%edx /* limit = NIL */
95 add $2+_window,%edi /* edi = offset(window+strstart+2) */
96 mov _prev_length,%ebx /* best_len = prev_length */
97 movw -3(%ebx,%edi),%ax /* ax = scan[best_len-1..best_len] */
98 movw -2(%edi),%cx /* cx = scan[0..1] */
99 cmp _good_match,%ebx /* do we have a good match already? */
101 shr $2,%ebp /* chain_length >>= 2 */
106 /* at this point, edi == scan+2, esi == cur_match */
107 movw -3(%ebx,%edi),%ax /* ax = scan[best_len-1..best_len] */
108 movw -2(%edi),%cx /* cx = scan[0..1] */
111 * at this point, di == scan+2, si == cur_match,
112 * ax = scan[best_len-1..best_len] and cx = scan[0..1]
115 movw _prev(%esi,%esi),%si /* cur_match = prev[cur_match] */
116 /* top word of esi is still 0 */
117 cmp %edx,%esi /* cur_match <= limit ? */
119 dec %ebp /* --chain_length */
122 cmpw _window-1(%ebx,%esi),%ax/* check match at best_len-1 */
124 cmpw _window(%esi),%cx /* check min_match_length match */
127 lea _window+2(%esi),%esi /* si = match */
128 mov %edi,%eax /* ax = scan+2 */
129 mov MAX_MATCH2,%ecx /* scan for at most MAX_MATCH bytes */
130 rep; cmpsw /* loop until mismatch */
131 je maxmatch /* match of length MAX_MATCH? */
133 movb -2(%edi),%cl /* mismatch on first or second byte? */
134 subb -2(%esi),%cl /* cl = 0 if first bytes equal */
135 xchg %edi,%eax /* edi = scan+2, eax = end of scan */
136 sub %edi,%eax /* eax = len */
137 sub %eax,%esi /* esi = cur_match + 2 + offset(window) */
138 sub $2+_window,%esi /* esi = cur_match */
139 subb $1,%cl /* set carry if cl == 0 (cannot use DEC) */
140 adc $0,%eax /* eax = carry ? len+1 : len */
141 cmp %ebx,%eax /* len > best_len ? */
143 mov %esi,_match_start /* match_start = cur_match */
144 mov %eax,%ebx /* ebx = best_len = len */
145 cmp _nice_match,%eax /* len >= nice_match ? */
148 mov %ebx,%eax /* result = eax = best_len */
160 /* ======================== 680x0 version ================================= */
162 #if defined(m68k)||defined(mc68k)||defined(__mc68000__)||defined(__MC68000__)
168 #if defined(__mc68020__) || defined(__MC68020__) || defined(sysV68)
174 #if defined(mc68020) || defined(mc68000)
176 #if (defined(mc68020) || defined(NeXT)) && !defined(UNALIGNED_OK)
177 # define UNALIGNED_OK
180 #ifdef sysV68 /* Try Motorola Delta style */
182 # define GLOBAL(symbol) global symbol
184 # define FILE(filename) file filename
185 # define invert_maybe(src,dst) dst,src
186 # define imm(data) &data
187 # define reg(register) %register
190 # define addql addq.l
195 # define cmpmb cmpm.b
200 # define movel move.l
201 # define movew move.w
202 # define moveb move.b
203 # define moveml movem.l
206 # define subql subq.l
208 # define IndBase(bd,An) (bd,An)
209 # define IndBaseNdxl(bd,An,Xn) (bd,An,Xn.l)
210 # define IndBaseNdxw(bd,An,Xn) (bd,An,Xn.w)
211 # define predec(An) -(An)
212 # define postinc(An) (An)+
214 #else /* default style (Sun 3, NeXT, Amiga, Atari) */
216 # define GLOBAL(symbol) .globl symbol
218 # define FILE(filename) .even
219 # define invert_maybe(src,dst) src,dst
220 # if defined(sun) || defined(mc68k)
221 # define imm(data) #data
223 # define imm(data) \#data
225 # define reg(register) register
228 # if defined(sun) || defined(mc68k)
233 # define IndBase(bd,An) An@(bd)
234 # define IndBaseNdxl(bd,An,Xn) An@(bd,Xn:l)
235 # define IndBaseNdxw(bd,An,Xn) An@(bd,Xn:w)
236 # define predec(An) An@-
237 # define postinc(An) An@+
241 #define Best_Len reg(d0) /* unsigned */
242 #define Cur_Match reg(d1) /* Ipos */
243 #define Loop_Counter reg(d2) /* int */
244 #define Scan_Start reg(d3) /* unsigned short */
245 #define Scan_End reg(d4) /* unsigned short */
246 #define Limit reg(d5) /* IPos */
247 #define Chain_Length reg(d6) /* unsigned */
248 #define Scan_Test reg(d7)
249 #define Scan reg(a0) /* *uch */
250 #define Match reg(a1) /* *uch */
251 #define Prev_Address reg(a2) /* *Pos */
252 #define Scan_Ini reg(a3) /* *uch */
253 #define Match_Ini reg(a4) /* *uch */
254 #define Stack_Pointer reg(sp)
256 #define MAX_MATCH 258
259 #define MAX_DIST (WSIZE - MAX_MATCH - MIN_MATCH - 1)
262 GLOBAL (_longest_match)
271 /*-----------------------------------------------------------------------
272 * Set match_start to the longest match starting at the given string and
273 * return its length. Matches shorter or equal to prev_length are discarded,
274 * in which case the result is equal to prev_length and match_start is
276 * IN assertions: cur_match is the head of the hash chain for the current
277 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
280 /* int longest_match (cur_match) */
283 # define pushreg 15928 /* d2-d6/a2-a4 */
286 # define pushreg 16184 /* d2-d7/a2-a4 */
291 movel IndBase(4,Stack_Pointer),Cur_Match
292 moveml imm(pushreg),predec(Stack_Pointer)
293 movel _max_chain_length,Chain_Length
294 movel _prev_length,Best_Len
295 movel imm(_prev),Prev_Address
296 movel imm(_window+MIN_MATCH),Match_Ini
297 movel _strstart,Limit
298 movel Match_Ini,Scan_Ini
300 subw imm(MAX_DIST),Limit
304 cmpl invert_maybe(_good_match,Best_Len)
306 lsrl imm(2),Chain_Length
308 subql imm(1),Chain_Length
310 movew IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
311 movew IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
313 moveb IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
314 lslw imm(8),Scan_Start
315 moveb IndBase(-MIN_MATCH+1,Scan_Ini),Scan_Start
316 moveb IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
318 moveb IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End
324 movew IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
326 moveb IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
328 moveb IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End
332 lslw imm(1),Cur_Match
333 movew IndBaseNdxl(0,Prev_Address,Cur_Match),Cur_Match
334 cmpw invert_maybe(Limit,Cur_Match)
335 dbls Chain_Length,L__do_scan
339 movel Match_Ini,Match
342 cmpw invert_maybe(IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_End)
344 cmpw invert_maybe(IndBase(-MIN_MATCH,Match),Scan_Start)
347 moveb IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_Test
348 lslw imm(8),Scan_Test
349 moveb IndBaseNdxw(-MIN_MATCH,Match,Best_Len),Scan_Test
350 cmpw invert_maybe(Scan_Test,Scan_End)
352 moveb IndBase(-MIN_MATCH,Match),Scan_Test
353 lslw imm(8),Scan_Test
354 moveb IndBase(-MIN_MATCH+1,Match),Scan_Test
355 cmpw invert_maybe(Scan_Test,Scan_Start)
359 movew imm((MAX_MATCH-MIN_MATCH+1)-1),Loop_Counter
362 cmpmb postinc(Match),postinc(Scan)
363 dbne Loop_Counter,L__scan_loop
366 addql imm(MIN_MATCH-1),Scan
367 cmpl invert_maybe(Best_Len,Scan)
370 movel Cur_Match,_match_start
371 cmpl invert_maybe(_nice_match,Best_Len)
374 moveml postinc(Stack_Pointer),imm(popreg)
378 error: this asm version is for 386 or 680x0 only
379 #endif /* mc68000 || mc68020 */
380 #endif /* i386 || _I386 */