/* match.s -- optional optimized asm version of longest match in deflate.c * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. * * The 68020 version has been written by Francesco Potorti` * with adaptations by Carsten Steger , * Andreas Schwab and * Kristoffer Eriksson */ /* $Id: match.S,v 1.2 1996/08/22 01:36:51 deraadt Exp $ */ /* Preprocess with -DNO_UNDERLINE if your C compiler does not prefix * external symbols with an underline character '_'. */ #ifdef NO_UNDERLINE # 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 #if 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 gzip.h, then change its value below. * This version assumes static allocation of the arrays (-DDYN_ALLOC not used). */ .file "match.S" #define MAX_MATCH 258 #define MAX_MATCH2 $128 /* MAX_MATCH/2-1 */ #define MIN_MATCH 3 #define WSIZE $32768 #define MAX_DIST WSIZE - MAX_MATCH - MIN_MATCH - 1 .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 */ _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 _max_chain_length,%ebp /* chain_length = max_chain_length */ mov _strstart,%edi mov %edi,%edx sub MAX_DIST,%edx /* limit = strstart-MAX_DIST */ 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 -3(%ebx,%edi),%ax /* ax = scan[best_len-1..best_len] */ movw -2(%edi),%cx /* cx = scan[0..1] */ cmp _good_match,%ebx /* do we have a good match already? */ jb do_scan shr $2,%ebp /* chain_length >>= 2 */ jmp do_scan .align 4 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 movw _prev(%esi,%esi),%si /* cur_match = prev[cur_match] */ /* top word of esi is still 0 */ cmp %edx,%esi /* cur_match <= limit ? */ jbe the_end dec %ebp /* --chain_length */ jz 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 lea _window+2(%esi),%esi /* si = match */ mov %edi,%eax /* ax = scan+2 */ mov MAX_MATCH2,%ecx /* scan for at most MAX_MATCH bytes */ rep; cmpsw /* loop until mismatch */ je maxmatch /* match of length MAX_MATCH? */ mismatch: movb -2(%edi),%cl /* mismatch on first or second byte? */ subb -2(%esi),%cl /* cl = 0 if first bytes equal */ xchg %edi,%eax /* edi = scan+2, eax = end of scan */ sub %edi,%eax /* eax = len */ sub %eax,%esi /* esi = cur_match + 2 + offset(window) */ sub $2+_window,%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 */ cmp _nice_match,%eax /* len >= nice_match ? */ jl long_loop the_end: mov %ebx,%eax /* result = eax = best_len */ pop %ebx pop %esi pop %edi pop %ebp ret maxmatch: cmpsb jmp mismatch #else /* ======================== 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) || defined(__NetBSD__) || defined(__OpenBSD__) # define imm(data) #data # else # define imm(data) \#data # endif # define reg(register) register # define blos bcss # if defined(sun) || defined(mc68k) || defined(__NetBSD__) || defined(__OpenBSD__) # 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) #define MAX_MATCH 258 #define MIN_MATCH 3 #define WSIZE 32768 #define MAX_DIST (WSIZE - MAX_MATCH - MIN_MATCH - 1) 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 cmpl invert_maybe(_nice_match,Best_Len) 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 */