Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!decwrl!labrea!agate!pasteur!ames!ll-xn!mit-eddie!uw-beaver!microsoft!jangr
From: jangr@microsoft.UUCP (Jan Gray)
Newsgroups: comp.sys.m68k
Subject: Re: 68000 Tricks
Message-ID: <1200@microsoft.UUCP>
Date: 26 Feb 88 06:06:14 GMT
References: <326@rose3.rosemount.com>
Reply-To: jangr@microsoft.UUCP (Jan Gray)
Distribution: na
Organization: Microsoft Corporation, Redmond, WA
Lines: 62
Keywords: 68000 Tricks Speed bitcount strlen

In article <326@rose3.rosemount.com> kent@rose3.rosemount.com (Kent Schnaith) writes:
>Sounds like the beginning of a contest ?
>!*	pop1cnt: Count 1 bits in a long.

(Assuming you can't afford a 256 byte lookup table...)

Bitcount using an adder tree.  (My thanks to some clever people here for
their various improvements to the basic algorithm, which was posted to the
net years ago.)

; 32 bit bitcount, input in d0.l
	movl	#0xaaaaaaaa,d1
	andl	d0,d1
	xorl	d1,d0
	lsrl	#1,d1
	addl	d1,d0		; d0.l = 16 two bit counters.
	movl	#0xcccccccc,d1
	andl	d0,d1
	xorl	d1,d0
	lsrl	#2,d1
	addl	d1,d0		; d0.l = 8 four bit counters.
	movl	#0xf0f0f0f0,d1
	andl	d0,d1
	xorl	d1,d0
	lsrl	#4,d1
	addl	d1,d0		; d0.l = 4 eight bit counters.
	movl	d0,d1
	swap	d1
	addw	d1,d0		; d0.w = 2 eight bit counters.
	movw	d0,-(sp)	; trick to extract upper byte of d0.w
	addb	(sp)+,d0	; d0.b = 1 eight bit sum of all bits.


>!*	strlen: Find length of a 0 terminated string.

On a '020, the four bytes at a time strlen should be about twice as fast as
an unrolled "tst (a0)+; beq done" loop.

; strlen, string in a0, 68020 only (a0 need not be longword aligned)
	movl	a0,a1
	movl	#$01010101,d2
	movl	#$80808080,d3

next4:	movl	(a0)+,d0	; ((l - 0x01010101) & ~l & 0x80808080) != 0 iff
	movl	d0,d1		; l contains a zero byte.
	subl	d2,d0
	notl	d1
	andl	d1,d0
	andl	d3,d0
	beq	next4

	subq	#4,a0
	tstb	(a0)+
	beq	adj
	tstb	(a0)+
	beq	adj
	tstb	(a0)+
	bne	noadj
adj:	subq	#1,a0
noadj:	subl	a1,a0
	movl	a0,d0
; result in d0

Jan Gray   uunet!microsoft!jangr   Microsoft Corp., Redmond Wash.   206-882-8080