From owner-freebsd-bugs@FreeBSD.ORG Thu Jan 15 20:00:40 2004 Return-Path: Delivered-To: freebsd-bugs@hub.freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 6BC5216A4CE for ; Thu, 15 Jan 2004 20:00:40 -0800 (PST) Received: from freefall.freebsd.org (freefall.freebsd.org [216.136.204.21]) by mx1.FreeBSD.org (Postfix) with ESMTP id DC9DB43D5E for ; Thu, 15 Jan 2004 20:00:37 -0800 (PST) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (gnats@localhost [127.0.0.1]) i0G40YFR084450 for ; Thu, 15 Jan 2004 20:00:34 -0800 (PST) (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.12.10/8.12.10/Submit) id i0G40Y0f084449; Thu, 15 Jan 2004 20:00:34 -0800 (PST) (envelope-from gnats) Resent-Date: Thu, 15 Jan 2004 20:00:34 -0800 (PST) Resent-Message-Id: <200401160400.i0G40Y0f084449@freefall.freebsd.org> Resent-From: FreeBSD-gnats-submit@FreeBSD.org (GNATS Filer) Resent-To: freebsd-bugs@FreeBSD.org Resent-Reply-To: FreeBSD-gnats-submit@FreeBSD.org, Colin Percival Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id E9A4016A4CE for ; Thu, 15 Jan 2004 19:53:44 -0800 (PST) Received: from pd4mo3so.prod.shaw.ca (shawidc-mo1.cg.shawcable.net [24.71.223.10]) by mx1.FreeBSD.org (Postfix) with ESMTP id 7F8F243D1D for ; Thu, 15 Jan 2004 19:53:42 -0800 (PST) (envelope-from cperciva@beastie.daemonology.net) Received: from pd2mr1so.prod.shaw.ca (pd2mr1so-ser.prod.shaw.ca [10.0.141.110])2003))FreeBSD-gnats-submit@freebsd.org; Thu, 15 Jan 2004 20:49:10 -0700 (MST) Received: from pn2ml8so.prod.shaw.ca (pn2ml8so-qfe0.prod.shaw.ca [10.0.121.152]) by l-daemon (iPlanet Messaging Server 5.2 HotFix 1.18 (built Jul 28 2003)) with ESMTP id <0HRK00LDLD9Y1I@l-daemon> for FreeBSD-gnats-submit@freebsd.org; Thu, 15 Jan 2004 20:49:10 -0700 (MST) Received: from beastie.daemonology.net (h24-87-233-42.vc.shawcable.net [24.87.233.42]) by l-daemon (iPlanet Messaging Server 5.2 HotFix 1.18 (built Jul 28 2003)) with SMTP id <0HRK0033BD9XFA@l-daemon> for FreeBSD-gnats-submit@freebsd.org; Thu, 15 Jan 2004 20:49:10 -0700 (MST) Received: (qmail 23250 invoked by uid 1001); Fri, 16 Jan 2004 03:49:09 +0000 Message-Id: <20040116034909.23249.qmail@beastie.daemonology.net> Date: Fri, 16 Jan 2004 03:49:09 +0000 From: Colin Percival To: FreeBSD-gnats-submit@FreeBSD.org X-Send-Pr-Version: 3.113 Subject: bin/61405: A faster ffs(3) X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list Reply-To: Colin Percival List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 16 Jan 2004 04:00:40 -0000 >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 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: