Date: Fri, 16 Jan 2004 03:49:09 +0000 From: Colin Percival <cperciva@daemonology.net> To: FreeBSD-gnats-submit@FreeBSD.org Subject: bin/61405: A faster ffs(3) Message-ID: <20040116034909.23249.qmail@beastie.daemonology.net> Resent-Message-ID: <200401160400.i0G40Y0f084449@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
>Number: 61405
>Category: bin
>Synopsis: A faster ffs(3)
>Confidential: no
>Severity: non-critical
>Priority: low
>Responsible: freebsd-bugs
>State: open
>Quarter:
>Keywords:
>Date-Required:
>Class: change-request
>Submitter-Id: current-users
>Arrival-Date: Thu Jan 15 20:00:34 PST 2004
>Closed-Date:
>Last-Modified:
>Originator: Colin Percival
>Release: FreeBSD 4.7-SECURITY i386
>Organization:
>Environment:
>Description:
ffs(3) currently loops, testing one bit per iteration until the
least set bit is found. This can be significantly improved.
>How-To-Repeat:
>Fix:
I'm not sure how important this is, since ffs is a single instruction on
many processors, but the following magic is very fast:
--- ffs.c begins here ---
#include <sys/types.h>
static int ffslut32[] = {
32, 1, 23, 2, 29, 24, 14, 3,
30, 27, 25, 18, 20, 15, 10, 4,
31, 22, 28, 13, 26, 17, 19, 9,
21, 12, 16, 8, 11, 7, 6, 5
};
static int ffslut64[] = {
64, 1, 48, 2, 57, 49, 28, 3,
61, 58, 50, 42, 38, 29, 17, 4,
62, 55, 59, 36, 53, 51, 43, 22,
45, 39, 33, 30, 24, 18, 12, 5,
63, 47, 56, 27, 60, 41, 37, 16,
54, 35, 52, 21, 44, 32, 23, 11,
46, 26, 40, 15, 34, 20, 31, 10,
25, 14, 19, 9, 13, 8, 7, 6
};
static int ffs32(uint32_t mask)
{
return mask ? ffslut32[((mask & (-mask)) * 0x0FB9AC52) >> 27] : 0;
}
static int ffs64(uint64_t mask)
{
return mask ? ffslut64[((mask & (-mask)) * 0x07EF3AE369961512) >> 58] : 0;
}
int ffs(int mask)
{
if (sizeof(int) == 8) return ffs64(mask);
if (sizeof(int) == 4) return ffs32(mask);
return -1;
}
int ffsl(long mask)
{
if (sizeof(long) == 8) return ffs64(mask);
if (sizeof(long) == 4) return ffs32(mask);
return -1;
}
--- ffs.c ends here ---
>Release-Note:
>Audit-Trail:
>Unformatted:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040116034909.23249.qmail>