From owner-freebsd-hackers@FreeBSD.ORG  Fri Jun 12 01:58:31 2015
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: freebsd-hackers@hub.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115])
 (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))
 (No client certificate requested)
 by hub.freebsd.org (Postfix) with ESMTPS id EA84A186;
 Fri, 12 Jun 2015 01:58:31 +0000 (UTC) (envelope-from hps@selasky.org)
Received: from mail.turbocat.net (mail.turbocat.net
 [IPv6:2a01:4f8:d16:4514::2])
 (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
 (Client did not present a certificate)
 by mx1.freebsd.org (Postfix) with ESMTPS id AB8D810CF;
 Fri, 12 Jun 2015 01:58:31 +0000 (UTC) (envelope-from hps@selasky.org)
Received: from laptop015.home.selasky.org
 (cm-176.74.213.204.customer.telag.net [176.74.213.204])
 (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits))
 (No client certificate requested)
 by mail.turbocat.net (Postfix) with ESMTPSA id F2CFA1FE023;
 Fri, 12 Jun 2015 03:58:26 +0200 (CEST)
Message-ID: <557A3CF3.3050603@selasky.org>
Date: Fri, 12 Jun 2015 03:59:15 +0200
From: Hans Petter Selasky <hps@selasky.org>
User-Agent: Mozilla/5.0 (X11; FreeBSD amd64;
 rv:31.0) Gecko/20100101 Thunderbird/31.7.0
MIME-Version: 1.0
To: Richard Yao <ryao@gentoo.org>, Ian Lepore <ian@freebsd.org>
CC: "freebsd-hackers@freebsd.org" <freebsd-hackers@FreeBSD.org>, 
 Erich Dollansky <erichsfreebsdlist@alogt.com>
Subject: Re: allow ffs & co. a binary search
References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com>	
 <5579A016.4040800@gentoo.org> <1434034373.1415.3.camel@freebsd.org>
 <5579A235.80609@gentoo.org>
In-Reply-To: <5579A235.80609@gentoo.org>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.20
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
 <freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/options/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers/>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
 <mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 12 Jun 2015 01:58:32 -0000

On 06/11/15 16:59, Richard Yao wrote:
> On 06/11/2015 10:52 AM, Ian Lepore wrote:
>> On Thu, 2015-06-11 at 10:49 -0400, Richard Yao wrote:
>>> On 06/06/2015 08:13 PM, Erich Dollansky wrote:
>> [...]
>>>
>>> The fastest portable way of calculating highest bit set is to use a
>>> debrujin sequence:
>>>
>>> https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
>>>
>>> The binary approach is inferior, especially on Pentium 4 processors.
>>
>> And of course it's crucial that we optimize for Pentium 4 processors in
>> 2015.
>
> The debrujin approach is fast regardless of the architecture. Anyway,
> this is a solved problem. There is no need to reinvent the wheel when
> the portable solutions are listed on that page at Stanford.
>

Hi Richard,

ffs() can be implemented like this simply:

int ffs_A(uint32_t v)
{
static const int MultiplyDeBruijnBitPosition[32] =
{
   0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
   8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v = ~(v - 1) & v;
return (MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]);
}


--HPS