[BACK]Return to ffs.S CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / lib / libc / arch / sh3 / string

File: [cvs.NetBSD.org] / src / lib / libc / arch / sh3 / string / Attic / ffs.S (download)

Revision 1.4, Sun Sep 1 13:14:53 2002 UTC (19 years, 9 months ago) by itohy
Branch: MAIN
CVS Tags: netbsd-3-base, netbsd-3-1-RELEASE, netbsd-3-1-RC4, netbsd-3-1-RC3, netbsd-3-1-RC2, netbsd-3-1-RC1, netbsd-3-1-1-RELEASE, netbsd-3-1, netbsd-3-0-RELEASE, netbsd-3-0-RC6, netbsd-3-0-RC5, netbsd-3-0-RC4, netbsd-3-0-RC3, netbsd-3-0-RC2, netbsd-3-0-RC1, netbsd-3-0-3-RELEASE, netbsd-3-0-2-RELEASE, netbsd-3-0-1-RELEASE, netbsd-3-0, netbsd-3, netbsd-2-base, netbsd-2-1-RELEASE, netbsd-2-1-RC6, netbsd-2-1-RC5, netbsd-2-1-RC4, netbsd-2-1-RC3, netbsd-2-1-RC2, netbsd-2-1-RC1, netbsd-2-1, netbsd-2-0-base, netbsd-2-0-RELEASE, netbsd-2-0-RC5, netbsd-2-0-RC4, netbsd-2-0-RC3, netbsd-2-0-RC2, netbsd-2-0-RC1, netbsd-2-0-3-RELEASE, netbsd-2-0-2-RELEASE, netbsd-2-0-1-RELEASE, netbsd-2-0, netbsd-2, nathanw_sa_before_merge, nathanw_sa_base, fvdl_fs64_base
Changes since 1.3: +23 -30 lines

Save 1-4 instructions on all cases except for the ret=0 case.

This is probably the last version from me. :)
You are welcome to speed it up, of course. :)

Here's a benchmark on SH-4 200MHz.
9.2% faster if all the cases occur evenly.

return value	C version	previous vers	this version	speed ratio
of ffs()	(ns/call) *1	(ns/call)	(ns/call) *2	(*1/*2)
------------	------------	-------------	------------	-----------
 0		  86		 81		 81		1.06
 1		 110		106		 91		1.21
 2		 132		106		 92		1.43
 3		 165		117		 96		1.72
 4		 201		116		 95		2.12
 5		 237		107		 99		2.39
 6		 271		106		101		2.68
 7		 307		116		107		2.87
 8		 342		116		105		3.26
 9		 376		126		111		3.39
10		 410		127		110		3.73
11		 446		136		115		3.88
12		 483		134		116		4.16
13		 518		125		119		4.35
14		 551		126		120		4.59
15		 587		135		127		4.62
16		 624		136		126		4.95
17		 658		139		126		5.22
18		 694		140		126		5.51
19		 727		148		131		5.55
20		 764		150		131		5.83
21		 799		141		135		5.92
22		 834		142		135		6.18
23		 868		152		140		6.20
24		 903		153		142		6.36
25		 939		140		127		7.39
26		 974		141		126		7.73
27		1009		152		131		7.70
28		1044		148		130		8.03
29		1080		141		136		7.94
30		1115		141		136		8.20
31		1151		151		141		8.16
32		1185		151		140		8.46

/*	$NetBSD: ffs.S,v 1.4 2002/09/01 13:14:53 itohy Exp $	*/

/*-
 * Copyright (c) 2002 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by ITOH Yasufumi.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the NetBSD
 *	Foundation, Inc. and its contributors.
 * 4. Neither the name of The NetBSD Foundation nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <machine/asm.h>

#if defined(LIBC_SCCS) && !defined(lint)
	RCSID("$NetBSD: ffs.S,v 1.4 2002/09/01 13:14:53 itohy Exp $")
#endif

/*
 * ffs - find first bit set
 *
 * This code makes use of ``test 8bit'' and ``shift 8bit'' instructions.
 * The remaining 8bit is tested in every 2bit.
 */

ENTRY(ffs)
	mov	r4,r0		! using r0 specific instructions
	tst	#0xff,r0
	bf/s	L8bit
	mov	#0+1,r1		! ret = 1..8

	tst	r0,r0		! ffs(0) is 0
	bt	Lzero		! testing here to accelerate ret=1..8 cases

	shlr8	r0
	tst	#0xff,r0
	bf/s	L8bit
	mov	#8+1,r1		! ret = 9..16

	shlr8	r0
	tst	#0xff,r0
	bf/s	L8bit
	mov	#16+1,r1	! ret = 17..24

	shlr8	r0
	mov	#24+1,r1	! ret = 25..32

L8bit:
	tst	#0x0f,r0
	bt	4f

	tst	#0x03,r0
	bt	2f
	tst	#0x01,r0	! not bit 0 -> T
	mov	#0,r0
	rts
	 addc	r1,r0		! 0 + r1 + T -> r0

2:	tst	#0x04,r0
	mov	#2,r0
	rts
	 addc	r1,r0

4:	tst	#0x30,r0
	bt	6f
	tst	#0x10,r0
	mov	#4,r0
	rts
	 addc	r1,r0

6:	tst	#0x40,r0
	mov	#6,r0
	rts
	 addc	r1,r0

Lzero:	rts
	 nop