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>