bin/61405: A faster ffs(3)

[Colin Percival]

>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: