diff options
Diffstat (limited to 'match.S')
| -rw-r--r-- | match.S | 407 |
1 files changed, 407 insertions, 0 deletions
@@ -0,0 +1,407 @@ +/* + Copyright (c) 1990-2005 Info-ZIP. All rights reserved. + + See the accompanying file LICENSE, version 2004-May-22 or later + (the contents of which are also included in zip.h) for terms of use. + If, for some reason, both of these files are missing, the Info-ZIP license + also may be found at: ftp://ftp.info-zip.org/pub/infozip/license.html +*/ + +/* + * match.s by Jean-loup Gailly. Translated to 32 bit code by Kai Uwe Rommel. + * The 68020 version has been written by Francesco Potorti` <pot@cnuce.cnr.it> + * with adaptations by Carsten Steger <stegerc@informatik.tu-muenchen.de>, + * Andreas Schwab <schwab@lamothe.informatik.uni-dortmund.de> and + * Kristoffer Eriksson <ske@pkmab.se> + */ + +/* This file is NOT used in conjunction with zlib. */ +#ifndef USE_ZLIB + +/* Preprocess with -DNO_UNDERLINE if your C compiler does not prefix + * external symbols with an underline character '_'. + */ +#if defined(NO_UNDERLINE) || defined(__ELF__) +# define _prev prev +# define _window window +# define _match_start match_start +# define _prev_length prev_length +# define _good_match good_match +# define _nice_match nice_match +# define _strstart strstart +# define _max_chain_length max_chain_length + +# define _match_init match_init +# define _longest_match longest_match +#endif + +#ifdef DYN_ALLOC + error: DYN_ALLOC not yet supported in match.s +#endif + +/* Use 16-bytes alignment if your assembler supports it. Warning: gas + * uses a log(x) parameter (.align 4 means 16-bytes alignment). On SVR4 + * the parameter is a number of bytes. + */ +#ifndef ALIGNMENT +# define ALIGNMENT 4 +#endif + + +#ifndef WSIZE +# define WSIZE 32768 +#endif +#define MIN_MATCH 3 +#define MAX_MATCH 258 +#define MIN_LOOKAHEAD (MAX_MATCH + MIN_MATCH + 1) +#define MAX_DIST (WSIZE - MIN_LOOKAHEAD) + +#if defined(i386) || defined(_I386) || defined(_i386) || defined(__i386) + +/* This version is for 386 Unix or OS/2 in 32 bit mode. + * Warning: it uses the AT&T syntax: mov source,dest + * This file is only optional. If you want to force the C version, + * add -DNO_ASM to CFLAGS in Makefile and set OBJA to an empty string. + * If you have reduced WSIZE in (g)zip.h, then make sure this is + * assembled with an equivalent -DWSIZE=<whatever>. + * This version assumes static allocation of the arrays (-DDYN_ALLOC not used). + */ + + .file "match.S" + + .globl _match_init + .globl _longest_match + + .text + +_match_init: + ret + +/*----------------------------------------------------------------------- + * Set match_start to the longest match starting at the given string and + * return its length. Matches shorter or equal to prev_length are discarded, + * in which case the result is equal to prev_length and match_start is + * garbage. + * IN assertions: cur_match is the head of the hash chain for the current + * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 + */ + + .align ALIGNMENT + +_longest_match: /* int longest_match(cur_match) */ + +#define cur_match 20(%esp) + /* return address */ /* esp+16 */ + push %ebp /* esp+12 */ + push %edi /* esp+8 */ + push %esi /* esp+4 */ + push %ebx /* esp */ + +/* + * match equ esi + * scan equ edi + * chain_length equ ebp + * best_len equ ebx + * limit equ edx + */ + mov cur_match,%esi + mov _strstart,%edx + mov _max_chain_length,%ebp /* chain_length = max_chain_length */ + mov %edx,%edi + sub $(MAX_DIST),%edx /* limit = strstart-MAX_DIST */ + cld /* string ops increment si and di */ + jae limit_ok + sub %edx,%edx /* limit = NIL */ +limit_ok: + add $2+_window,%edi /* edi = offset(window+strstart+2) */ + mov _prev_length,%ebx /* best_len = prev_length */ + movw -2(%edi),%cx /* cx = scan[0..1] */ + movw -3(%ebx,%edi),%ax /* ax = scan[best_len-1..best_len] */ + cmp _good_match,%ebx /* do we have a good match already? */ + jb do_scan + shr $2,%ebp /* chain_length >>= 2 */ + jmp do_scan + + .align ALIGNMENT +long_loop: +/* at this point, edi == scan+2, esi == cur_match */ + movw -3(%ebx,%edi),%ax /* ax = scan[best_len-1..best_len] */ + movw -2(%edi),%cx /* cx = scan[0..1] */ +short_loop: +/* + * at this point, di == scan+2, si == cur_match, + * ax = scan[best_len-1..best_len] and cx = scan[0..1] + */ + and $(WSIZE-1), %esi + dec %ebp /* --chain_length */ + movw _prev(,%esi,2),%si /* cur_match = prev[cur_match] */ + /* top word of esi is still 0 */ + jz the_end + cmp %edx,%esi /* cur_match <= limit ? */ + jbe the_end +do_scan: + cmpw _window-1(%ebx,%esi),%ax/* check match at best_len-1 */ + jne short_loop + cmpw _window(%esi),%cx /* check min_match_length match */ + jne short_loop + + add $2+_window,%esi /* si = match */ + mov $((MAX_MATCH>>1)-1),%ecx/* scan for at most MAX_MATCH bytes */ + mov %edi,%eax /* ax = scan+2 */ + repe; cmpsw /* loop until mismatch */ + je maxmatch /* match of length MAX_MATCH? */ +mismatch: + movb -2(%edi),%cl /* mismatch on first or second byte? */ + xchg %edi,%eax /* edi = scan+2, eax = end of scan */ + subb -2(%esi),%cl /* cl = 0 if first bytes equal */ + sub %edi,%eax /* eax = len */ + sub $2+_window,%esi /* esi = cur_match + len */ + sub %eax,%esi /* esi = cur_match */ + subb $1,%cl /* set carry if cl == 0 (cannot use DEC) */ + adc $0,%eax /* eax = carry ? len+1 : len */ + cmp %ebx,%eax /* len > best_len ? */ + jle long_loop + mov %esi,_match_start /* match_start = cur_match */ + mov %eax,%ebx /* ebx = best_len = len */ +#ifdef FULL_SEARCH + cmp $(MAX_MATCH),%eax /* len >= MAX_MATCH ? */ +#else + cmp _nice_match,%eax /* len >= nice_match ? */ +#endif + jl long_loop +the_end: + mov %ebx,%eax /* result = eax = best_len */ + pop %ebx + pop %esi + pop %edi + pop %ebp + ret + .align ALIGNMENT +maxmatch: + cmpsb + jmp mismatch + +#else /* !(i386 || _I386 || _i386 || __i386) */ + +/* ======================== 680x0 version ================================= */ + +#if defined(m68k)||defined(mc68k)||defined(__mc68000__)||defined(__MC68000__) +# ifndef mc68000 +# define mc68000 +# endif +#endif + +#if defined(__mc68020__) || defined(__MC68020__) || defined(sysV68) +# ifndef mc68020 +# define mc68020 +# endif +#endif + +#if defined(mc68020) || defined(mc68000) + +#if (defined(mc68020) || defined(NeXT)) && !defined(UNALIGNED_OK) +# define UNALIGNED_OK +#endif + +#ifdef sysV68 /* Try Motorola Delta style */ + +# define GLOBAL(symbol) global symbol +# define TEXT text +# define FILE(filename) file filename +# define invert_maybe(src,dst) dst,src +# define imm(data) &data +# define reg(register) %register + +# define addl add.l +# define addql addq.l +# define blos blo.b +# define bhis bhi.b +# define bras bra.b +# define clrl clr.l +# define cmpmb cmpm.b +# define cmpw cmp.w +# define cmpl cmp.l +# define lslw lsl.w +# define lsrl lsr.l +# define movel move.l +# define movew move.w +# define moveb move.b +# define moveml movem.l +# define subl sub.l +# define subw sub.w +# define subql subq.l + +# define IndBase(bd,An) (bd,An) +# define IndBaseNdxl(bd,An,Xn) (bd,An,Xn.l) +# define IndBaseNdxw(bd,An,Xn) (bd,An,Xn.w) +# define predec(An) -(An) +# define postinc(An) (An)+ + +#else /* default style (Sun 3, NeXT, Amiga, Atari) */ + +# define GLOBAL(symbol) .globl symbol +# define TEXT .text +# define FILE(filename) .even +# define invert_maybe(src,dst) src,dst +# if defined(sun) || defined(mc68k) +# define imm(data) #data +# else +# define imm(data) \#data +# endif +# define reg(register) register + +# define blos bcss +# if defined(sun) || defined(mc68k) +# define movel movl +# define movew movw +# define moveb movb +# endif +# define IndBase(bd,An) An@(bd) +# define IndBaseNdxl(bd,An,Xn) An@(bd,Xn:l) +# define IndBaseNdxw(bd,An,Xn) An@(bd,Xn:w) +# define predec(An) An@- +# define postinc(An) An@+ + +#endif /* styles */ + +#define Best_Len reg(d0) /* unsigned */ +#define Cur_Match reg(d1) /* Ipos */ +#define Loop_Counter reg(d2) /* int */ +#define Scan_Start reg(d3) /* unsigned short */ +#define Scan_End reg(d4) /* unsigned short */ +#define Limit reg(d5) /* IPos */ +#define Chain_Length reg(d6) /* unsigned */ +#define Scan_Test reg(d7) +#define Scan reg(a0) /* *uch */ +#define Match reg(a1) /* *uch */ +#define Prev_Address reg(a2) /* *Pos */ +#define Scan_Ini reg(a3) /* *uch */ +#define Match_Ini reg(a4) /* *uch */ +#define Stack_Pointer reg(sp) + + GLOBAL (_match_init) + GLOBAL (_longest_match) + + TEXT + + FILE ("match.S") + +_match_init: + rts + +/*----------------------------------------------------------------------- + * Set match_start to the longest match starting at the given string and + * return its length. Matches shorter or equal to prev_length are discarded, + * in which case the result is equal to prev_length and match_start is + * garbage. + * IN assertions: cur_match is the head of the hash chain for the current + * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 + */ + +/* int longest_match (cur_match) */ + +#ifdef UNALIGNED_OK +# define pushreg 15928 /* d2-d6/a2-a4 */ +# define popreg 7292 +#else +# define pushreg 16184 /* d2-d7/a2-a4 */ +# define popreg 7420 +#endif + +_longest_match: + movel IndBase(4,Stack_Pointer),Cur_Match + moveml imm(pushreg),predec(Stack_Pointer) + movel _max_chain_length,Chain_Length + movel _prev_length,Best_Len + movel imm(_prev),Prev_Address + movel imm(_window+MIN_MATCH),Match_Ini + movel _strstart,Limit + movel Match_Ini,Scan_Ini + addl Limit,Scan_Ini + subw imm(MAX_DIST),Limit + bhis L__limit_ok + clrl Limit +L__limit_ok: + cmpl invert_maybe(_good_match,Best_Len) + blos L__length_ok + lsrl imm(2),Chain_Length +L__length_ok: + subql imm(1),Chain_Length +#ifdef UNALIGNED_OK + movew IndBase(-MIN_MATCH,Scan_Ini),Scan_Start + movew IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End +#else + moveb IndBase(-MIN_MATCH,Scan_Ini),Scan_Start + lslw imm(8),Scan_Start + moveb IndBase(-MIN_MATCH+1,Scan_Ini),Scan_Start + moveb IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End + lslw imm(8),Scan_End + moveb IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End +#endif + bras L__do_scan + +L__long_loop: +#ifdef UNALIGNED_OK + movew IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End +#else + moveb IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End + lslw imm(8),Scan_End + moveb IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End +#endif + +L__short_loop: + lslw imm(1),Cur_Match + movew IndBaseNdxl(0,Prev_Address,Cur_Match),Cur_Match + cmpw invert_maybe(Limit,Cur_Match) + dbls Chain_Length,L__do_scan + bras L__return + +L__do_scan: + movel Match_Ini,Match + addl Cur_Match,Match +#ifdef UNALIGNED_OK + cmpw invert_maybe(IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_End) + bne L__short_loop + cmpw invert_maybe(IndBase(-MIN_MATCH,Match),Scan_Start) + bne L__short_loop +#else + moveb IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_Test + lslw imm(8),Scan_Test + moveb IndBaseNdxw(-MIN_MATCH,Match,Best_Len),Scan_Test + cmpw invert_maybe(Scan_Test,Scan_End) + bne L__short_loop + moveb IndBase(-MIN_MATCH,Match),Scan_Test + lslw imm(8),Scan_Test + moveb IndBase(-MIN_MATCH+1,Match),Scan_Test + cmpw invert_maybe(Scan_Test,Scan_Start) + bne L__short_loop +#endif + + movew imm((MAX_MATCH-MIN_MATCH+1)-1),Loop_Counter + movel Scan_Ini,Scan +L__scan_loop: + cmpmb postinc(Match),postinc(Scan) + dbne Loop_Counter,L__scan_loop + + subl Scan_Ini,Scan + addql imm(MIN_MATCH-1),Scan + cmpl invert_maybe(Best_Len,Scan) + bls L__short_loop + movel Scan,Best_Len + movel Cur_Match,_match_start +#ifdef FULL_SEARCH + cmpl invert_maybe(imm(MAX_MATCH),Best_Len) +#else + cmpl invert_maybe(_nice_match,Best_Len) +#endif + blos L__long_loop +L__return: + moveml postinc(Stack_Pointer),imm(popreg) + rts + +#else + error: this asm version is for 386 or 680x0 only +#endif /* mc68000 || mc68020 */ +#endif /* i386 || _I386 || _i386 || __i386 */ + +#endif /* !USE_ZLIB */ |