allow ffs & co. a binary search

[Richard Yao]

On 06/11/2015 09:59 PM, Hans Petter Selasky wrote:
> 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]);
> }

There is a way to do that on the stanford page too:

https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

Using it, we would have:

int ffs_A(uint32_t v)
{
unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
return MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U))
>> 27];
}

That accomplishes ffs() in 1 less operation.

These techniques can be extended to 64-bit too.

> --HPS


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.freebsd.org/pipermail/freebsd-hackers/attachments/20150612/9855ac10/attachment.sig>