/* 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` * with adaptations by Carsten Steger , * Andreas Schwab and * Kristoffer Eriksson */ /* 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=. * 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 */