match.s

采用 LZ77 运算规则 压缩及解压工具

/* 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.
 */
 
/* $Id: match.S,v 0.8 1993/02/10 16:07:22 jloup Exp $ */

#ifdef 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).
 *
 * Preprocess with -DNO_UNDERLINE if your C compiler does not prefix
 * external symbols with an underline character '_'.
 */

	.file   "match.s"

#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

#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	$ _window+2,%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	$ _window+2,%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
#if 0 /* not yet tested */

/* 68020 version, written by Francesco Potorti <[e-mail]> */

#define MAX_MATCH 	0x102
#define MIN_MATCH	3
#define WSIZE 		0x8000
#define MAX_DIST 	(WSIZE - MAX_MATCH - MIN_MATCH - 1)

	file	"match.S"

	global	match_init
	global	longest_match

	text

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) */

#define	best_len	d0		/* unsigned */
#define	cur_match	d1		/* Ipos */
#define	tmp		d2		/* int */
#define	scan_start	d3		/* unsigned */
#define	scan_end	d4		/* unsigned */
#define	limit		d5		/* IPos */
#define	chain_length	d6		/* unsigned */
#define	scan		a0		/* *uch */
#define	match		a1		/* *uch */
#define prev_address	a2		/* *Pos */
#define	scan_init	a3		/* *uch */
#define	match_init	a4		/* *uch */
set	pushreg,0x3e38
set	popreg,0x1c7c


longest_match:
	mov.l	0x4(%sp),%cur_match
	movm.l	&pushreg,-(%sp)
	mov.l	max_chain_length,%chain_length
	mov.l	prev_length,%best_len
	move.l	&prev,%prev_address
	move.l	&(window+MIN_MATCH),%match_init
	mov.l	strstart,%limit
	mov.l	%match_init,%scan_init
	add.l	%limit,%scan_init
	sub.l	&MAX_DIST,%limit
	bhi.b	limit_ok
	clr.l	%limit
limit_ok:
	mov.l	good_match,%tmp
	cmp.l	%tmp,prev_length
	bhi.b	length_ok
	lsr.l	&2,%chain_length
length_ok:
	sub.l	&1,%chain_length
	move.w	-MIN_MATCH(%scan_init),%scan_start
	move.w	-MIN_MATCH-1(%scan_init,%best_len.l),%scan_end
	bra.b	do_scan

long_loop:
	move.w	-MIN_MATCH-1(%scan_init,%best_len.l),%scan_end

short_loop:
	lsl.w	&1,%cur_match
	mov.w	(%prev_address,%cur_match.l),%cur_match
	cmp.w	%cur_match,%limit
	dbls	%chain_length,do_scan
	bra.b	return

do_scan:
	move.l	%match_init,%match
	add.l	%cur_match,%match
	cmp.w	%scan_end,-MIN_MATCH-1(%match,%best_len.l)
	bne	short_loop
	cmp.w	%scan_start,-MIN_MATCH(%match)
	bne	short_loop

	move.w	&(MAX_MATCH-MIN_MATCH+1)-1,%tmp
	move.l	%scan_init,%scan
scan_loop:
	cmp.b	(%match)+,(%scan)+
	dbne	%tmp,scan_loop

	sub.l	%scan_init,%scan
	add.l	&MIN_MATCH-1,%scan
	cmp.l	%scan,%best_len
	bls	short_loop
	mov.l	%scan,%best_len
	mov.l	%cur_match,match_start
	cmp.l	%best_len,nice_match
	blo	long_loop
return:
	movm.l	(%sp)+,&popreg
	rts
#else
 error: this asm version is for 386 or 68020 only
#endif
#endif