Path: utzoo!utgpu!watserv1!watmath!att!bellcore!rutgers!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!usc!snorkelwacker!bu.edu!orc!inews!iwarp.intel.com!psueea!eecs!kirkenda
From: kirkenda@eecs.cs.pdx.edu (Steve Kirkendall)
Newsgroups: comp.os.minix
Subject: Re: Comic
Summary: 68000 assembler version of memrchr() cuts time in half
Keywords: 68000 assembler
Message-ID: <3117@psueea.UUCP>
Date: 10 Jul 90 19:24:15 GMT
References: <228@sun13.scri.fsu.edu>
Sender: news@psueea.UUCP
Reply-To: kirkenda@eecs.UUCP (Steve Kirkendall)
Organization: Portland State University, Portland, OR
Lines: 105

In article <228@sun13.scri.fsu.edu> nall@sun8.scri.fsu.edu (John Nall) writes:
>
>The fairly significant increase in the compression ratio of
>Comic is attractive, so I played with it some on our Cray Y-MP
>to see how it does there.  It is horrible!  (In terms of speed.
>Worked OK, though, with no changes, under Unicos).
					   ^^^^^^
Damn, I was hoping you had ported Minix to your Cray.   :-) of course.

The biggest bottleneck is the memrchr() function -- which has already been
converted to assembler for the intel crowd.  I wrote a version in 68000
assembler (included below) and this cut the compression time in half. It still
runs like a one-legged cow, but at least now its a HEALTHIER one-legged cow.

The next problem is that comic outputs the compressed data one bit at a time,
via the putbit() function.  It uses a 1024-byte output buffer, so we don't have
a huge system overhead, but still we invest a lot of computing time to the
processing of each individual bit.  There is also a function for outputting
several bits at once, but it just call putbit() repeatedly, in a loop.
I suspect that we could gain something by rewriting putnbits() (or whatever
its called) to do the bit stuffing directly instead of calling putbit().
-------------------------------------------------------------------------------
Steve Kirkendall    kirkenda@cs.pdx.edu    uunet!tektronix!psueea!eecs!kirkenda

echo x - memrchr68.s
sed '/^X/s///' > memrchr68.s << '/'
X	.sect	.text
X	.sect	.rom
X	.sect	.data
X	.sect	.bss
X	.list
X	.sect	.text
X
X!-------------------------------------------------------------------------!
X! Minix-68k version of the memrchr() function, in 68000 assembly language !
X! Written by Steve Kirkendall, 1990 July 10                               !
X!-------------------------------------------------------------------------!
X
XSTART	=	4		! stack offsets of arguments
XSTOP	=	8		!
XCH	=	13		!
X
X_memrchr:			! start function
X	.globl	_memrchr	!
X				!-
X	move.l	START(sp),a0	! a0 is "start"
X	move.l	STOP(sp),a1	! a1 is "stop"
X	move.b	CH(sp),d0	! d0 is "ch"
X				!-
X	move.b	(a1),d1		! d1 holds the value that the sentinal clobbers
X				!-
X	move.b	d0,(a1)		! install the sentinal
X				!-
X	add.w	#1,a0		! compensate for the initial predecrement
X				!-
Xloop:				!
X	cmp.b	-(a0),d0	! unrolled search loop
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	beq	found		!
X	cmp.b	-(a0),d0	!
X	bne	loop		!
X				!-
Xfound:				! we've found a match, or the sentinel
X				!-
X	move.b	d1,(a1)		! remove the sentinel
X				!-
X	cmp.l	a0,a1		! did we hit the sentinel?
X	beq	notfound	!
X				!-
X	move.l	a0,d0		! we found a match, so return a pointer to it
X	rts			!
X				!-
Xnotfound:			! we hit the sentinel, so return NULL
X	clr.l	d0		!
X	rts			!
/
-------------------------------------------------------------------------------
Steve Kirkendall    kirkenda@cs.pdx.edu    uunet!tektronix!psueea!eecs!kirkenda