![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to match.S CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / g / usr / bin / gzip|
Return to match.S CVS log | Up to [MW Coherent from dump] / coherent / g / usr / bin / gzip |
1.1 root 1: /* match.s -- optional optimized asm version of longest match in deflate.c
2: * Copyright (C) 1992-1993 Jean-loup Gailly
3: * This is free software; you can redistribute it and/or modify it under the
4: * terms of the GNU General Public License, see the file COPYING.
5: */
6:
7: /* $Id: match.S,v 0.9 1993/02/24 18:23:13 jloup Exp $ */
8:
9: /* Preprocess with -DNO_UNDERLINE if your C compiler does not prefix
10: * external symbols with an underline character '_'.
11: */
12: #ifdef NO_UNDERLINE
13: # define _prev prev
14: # define _window window
15: # define _match_start match_start
16: # define _prev_length prev_length
17: # define _good_match good_match
18: # define _nice_match nice_match
19: # define _strstart strstart
20: # define _max_chain_length max_chain_length
21:
22: # define _match_init match_init
23: # define _longest_match longest_match
24: #endif
25:
26: #ifdef DYN_ALLOC
27: error: DYN_ALLOC not yet supported in match.s
28: #endif
29:
30: #if defined(i386) || defined(_I386)
31:
32: /* This version is for 386 Unix or OS/2 in 32 bit mode.
33: * Warning: it uses the AT&T syntax: mov source,dest
34: * This file is only optional. If you want to force the C version,
35: * add -DNO_ASM to CFLAGS in Makefile and set OBJA to an empty string.
36: * If you have reduced WSIZE in gzip.h, then change its value below.
37: * This version assumes static allocation of the arrays (-DDYN_ALLOC not used).
38: */
39:
40: .file "match.S"
41:
42: #define MAX_MATCH 258
43: #define MAX_MATCH2 128 /* MAX_MATCH/2-1 */
44: #define MIN_MATCH 3
45: #define WSIZE 32768
46: #define MAX_DIST WSIZE - MAX_MATCH - MIN_MATCH - 1
47:
48: .globl _match_init
49: .globl _longest_match
50:
51: .text
52:
53: _match_init:
54: ret
55:
56: /*-----------------------------------------------------------------------
57: * Set match_start to the longest match starting at the given string and
58: * return its length. Matches shorter or equal to prev_length are discarded,
59: * in which case the result is equal to prev_length and match_start is
60: * garbage.
61: * IN assertions: cur_match is the head of the hash chain for the current
62: * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
63: */
64:
65: _longest_match: /* int longest_match(cur_match) */
66:
67: #define cur_match 20(%esp)
68: /* return address */ /* esp+16 */
69: push %ebp /* esp+12 */
70: push %edi /* esp+8 */
71: push %esi /* esp+4 */
72: push %ebx /* esp */
73:
74: /*
75: * match equ esi
76: * scan equ edi
77: * chain_length equ ebp
78: * best_len equ ebx
79: * limit equ edx
80: */
81: mov cur_match,%esi
82: mov _max_chain_length,%ebp /* chain_length = max_chain_length */
83: mov _strstart,%edi
84: mov %edi,%edx
85: sub $ MAX_DIST,%edx /* limit = strstart-MAX_DIST */
86: jae limit_ok
87: sub %edx,%edx /* limit = NIL */
88: limit_ok:
89: add $ _window+2,%edi /* edi = offset(window+strstart+2) */
90: mov _prev_length,%ebx /* best_len = prev_length */
91: movw -3(%ebx,%edi),%ax /* ax = scan[best_len-1..best_len] */
92: movw -2(%edi),%cx /* cx = scan[0..1] */
93: cmp _good_match,%ebx /* do we have a good match already? */
94: jb do_scan
95: shr $2,%ebp /* chain_length >>= 2 */
96: jmp do_scan
97:
98: .align 4
99: long_loop:
100: /* at this point, edi == scan+2, esi == cur_match */
101: movw -3(%ebx,%edi),%ax /* ax = scan[best_len-1..best_len] */
102: movw -2(%edi),%cx /* cx = scan[0..1] */
103: short_loop:
104: /*
105: * at this point, di == scan+2, si == cur_match,
106: * ax = scan[best_len-1..best_len] and cx = scan[0..1]
107: */
108: and $ WSIZE-1, %esi
109: movw _prev(%esi,%esi),%si /* cur_match = prev[cur_match] */
110: /* top word of esi is still 0 */
111: cmp %edx,%esi /* cur_match <= limit ? */
112: jbe the_end
113: dec %ebp /* --chain_length */
114: jz the_end
115: do_scan:
116: cmpw _window-1(%ebx,%esi),%ax/* check match at best_len-1 */
117: jne short_loop
118: cmpw _window(%esi),%cx /* check min_match_length match */
119: jne short_loop
120:
121: lea _window+2(%esi),%esi /* si = match */
122: mov %edi,%eax /* ax = scan+2 */
123: mov $ MAX_MATCH2,%ecx /* scan for at most MAX_MATCH bytes */
124: rep; cmpsw /* loop until mismatch */
125: je maxmatch /* match of length MAX_MATCH? */
126: mismatch:
127: movb -2(%edi),%cl /* mismatch on first or second byte? */
128: subb -2(%esi),%cl /* cl = 0 if first bytes equal */
129: xchg %edi,%eax /* edi = scan+2, eax = end of scan */
130: sub %edi,%eax /* eax = len */
131: sub %eax,%esi /* esi = cur_match + 2 + offset(window) */
132: sub $ _window+2,%esi /* esi = cur_match */
133: subb $1,%cl /* set carry if cl == 0 (cannot use DEC) */
134: adc $0,%eax /* eax = carry ? len+1 : len */
135: cmp %ebx,%eax /* len > best_len ? */
136: jle long_loop
137: mov %esi,_match_start /* match_start = cur_match */
138: mov %eax,%ebx /* ebx = best_len = len */
139: cmp _nice_match,%eax /* len >= nice_match ? */
140: jl long_loop
141: the_end:
142: mov %ebx,%eax /* result = eax = best_len */
143: pop %ebx
144: pop %esi
145: pop %edi
146: pop %ebp
147: ret
148: maxmatch:
149: cmpsb
150: jmp mismatch
151:
152: #else
153: #if defined(m68k) || defined(mc68020)
154:
155: /* 68020 version, written by Francesco Potorti` <[email protected]> */
156:
157: #ifdef m68k /* Try 'delta' style */
158:
159: # define GLOBAL(symbol) global symbol
160: # define TEXT text
161: # define FILE(filename) file filename
162: # define invert_maybe(src,dst) dst,src
163: # define imm(data) &data
164: # define reg(register) %register
165:
166: # define addl add.l
167: # define addql addq.l
168: # define blos blo.b
169: # define bhis bhi.b
170: # define bras bra.b
171: # define clrl clr.l
172: # define cmpmb cmpm.b
173: # define cmpw cmp.w
174: # define cmpl cmp.l
175: # define lslw lsl.w
176: # define lsrl lsr.l
177: # define movel move.l
178: # define movew move.w
179: # define moveml movem.l
180: # define subl sub.l
181: # define subw sub.w
182: # define subql subq.l
183:
184: # define IndBase(bd,An) (bd,An)
185: # define IndBaseNdxl(bd,An,Xn) (bd,An,Xn.l)
186: # define IndBaseNdxw(bd,An,Xn) (bd,An,Xn.w)
187: # define predec(An) -(An)
188: # define postinc(An) (An)+
189:
190: #else /* Try Sun 3 or Amiga style */
191:
192: # define GLOBAL(symbol) .globl symbol
193: # define TEXT .text
194: # define FILE(filename) .even
195: # define invert_maybe(src,dst) src,dst
196: # ifdef sun
197: # define imm(data) #data
198: # else
199: # define imm(data) \#data
200: # endif
201: # define reg(register) register
202:
203: # define blos bcss
204: # ifdef sun
205: # define movel movl
206: # define movew movw
207: # endif
208: # define IndBase(bd,An) An@(bd)
209: # define IndBaseNdxl(bd,An,Xn) An@(bd,Xn:l)
210: # define IndBaseNdxw(bd,An,Xn) An@(bd,Xn:w)
211: # define predec(An) An@-
212: # define postinc(An) An@+
213:
214: #endif /* styles */
215:
216: #define Best_Len reg(d0) /* unsigned */
217: #define Cur_Match reg(d1) /* Ipos */
218: #define Loop_Counter reg(d2) /* int */
219: #define Scan_Start reg(d3) /* unsigned short */
220: #define Scan_End reg(d4) /* unsigned short */
221: #define Limit reg(d5) /* IPos */
222: #define Chain_Length reg(d6) /* unsigned */
223: #define Scan reg(a0) /* *uch */
224: #define Match reg(a1) /* *uch */
225: #define Prev_Address reg(a2) /* *Pos */
226: #define Scan_Ini reg(a3) /* *uch */
227: #define Match_Ini reg(a4) /* *uch */
228: #define Stack_Pointer reg(sp)
229:
230: #define MAX_MATCH 258
231: #define MIN_MATCH 3
232: #define WSIZE 32768
233: #define MAX_DIST (WSIZE - MAX_MATCH - MIN_MATCH - 1)
234:
235: GLOBAL (_match_init)
236: GLOBAL (_longest_match)
237:
238: TEXT
239:
240: FILE ("match.S")
241:
242: _match_init:
243: rts
244:
245: /*-----------------------------------------------------------------------
246: * Set match_start to the longest match starting at the given string and
247: * return its length. Matches shorter or equal to prev_length are discarded,
248: * in which case the result is equal to prev_length and match_start is
249: * garbage.
250: * IN assertions: cur_match is the head of the hash chain for the current
251: * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
252: */
253:
254: /* int longest_match (cur_match) */
255: #define pushreg 15928 /* d2-d6/a2-a4 */
256: #define popreg 7292
257:
258: _longest_match:
259: movel IndBase(4,Stack_Pointer),Cur_Match
260: moveml imm(pushreg),predec(Stack_Pointer)
261: movel _max_chain_length,Chain_Length
262: movel _prev_length,Best_Len
263: movel imm(_prev),Prev_Address
264: movel imm(_window+MIN_MATCH),Match_Ini
265: movel _strstart,Limit
266: movel Match_Ini,Scan_Ini
267: addl Limit,Scan_Ini
268: subw imm(MAX_DIST),Limit
269: bhis L__limit_ok
270: clrl Limit
271: L__limit_ok:
272: cmpl invert_maybe(_good_match,Best_Len)
273: blos L__length_ok
274: lsrl imm(2),Chain_Length
275: L__length_ok:
276: subql imm(1),Chain_Length
277: movew IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
278: movew IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
279: bras L__do_scan
280:
281: L__long_loop:
282: movew IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
283:
284: L__short_loop:
285: lslw imm(1),Cur_Match
286: movew IndBaseNdxl(0,Prev_Address,Cur_Match),Cur_Match
287: cmpw invert_maybe(Limit,Cur_Match)
288: dbls Chain_Length,L__do_scan
289: bras L__return
290:
291: L__do_scan:
292: movel Match_Ini,Match
293: addl Cur_Match,Match
294: cmpw invert_maybe(IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_End)
295: bne L__short_loop
296: cmpw invert_maybe(IndBase(-MIN_MATCH,Match),Scan_Start)
297: bne L__short_loop
298:
299: movew imm((MAX_MATCH-MIN_MATCH+1)-1),Loop_Counter
300: movel Scan_Ini,Scan
301: L__scan_loop:
302: cmpmb postinc(Match),postinc(Scan)
303: dbne Loop_Counter,L__scan_loop
304:
305: subl Scan_Ini,Scan
306: addql imm(MIN_MATCH-1),Scan
307: cmpl invert_maybe(Best_Len,Scan)
308: bls L__short_loop
309: movel Scan,Best_Len
310: movel Cur_Match,_match_start
311: cmpl invert_maybe(_nice_match,Best_Len)
312: blos L__long_loop
313: L__return:
314: moveml postinc(Stack_Pointer),imm(popreg)
315: rts
316:
317: #else
318: error: this asm version is for 386 or 68020 only
319: #endif /* m68k || mc68020 */
320: #endif /* i386 || _I386 */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.