From owner-freebsd-hackers@freebsd.org Thu Jul 6 13:47:31 2017 Return-Path: Delivered-To: freebsd-hackers@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 96339DAE138 for ; Thu, 6 Jul 2017 13:47:31 +0000 (UTC) (envelope-from sebastian.huber@embedded-brains.de) Received: from dedi548.your-server.de (dedi548.your-server.de [85.10.215.148]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 53EF76FFE8; Thu, 6 Jul 2017 13:47:30 +0000 (UTC) (envelope-from sebastian.huber@embedded-brains.de) Received: from [88.198.220.130] (helo=sslproxy01.your-server.de) by dedi548.your-server.de with esmtpsa (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.85_2) (envelope-from ) id 1dT6m0-0001jM-Jz; Thu, 06 Jul 2017 15:24:48 +0200 Received: from [82.135.62.35] (helo=mail.embedded-brains.de) by sslproxy01.your-server.de with esmtpsa (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.84_2) (envelope-from ) id 1dT6lv-0005Vk-C9; Thu, 06 Jul 2017 15:24:43 +0200 Received: from localhost (localhost.localhost [127.0.0.1]) by mail.embedded-brains.de (Postfix) with ESMTP id 174332A004F; Thu, 6 Jul 2017 15:24:53 +0200 (CEST) Received: from mail.embedded-brains.de ([127.0.0.1]) by localhost (zimbra.eb.localhost [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id 8edlrieEalKl; Thu, 6 Jul 2017 15:24:52 +0200 (CEST) Received: from localhost (localhost.localhost [127.0.0.1]) by mail.embedded-brains.de (Postfix) with ESMTP id A07CA2A160A; Thu, 6 Jul 2017 15:24:52 +0200 (CEST) X-Virus-Scanned: amavisd-new at zimbra.eb.localhost Received: from mail.embedded-brains.de ([127.0.0.1]) by localhost (zimbra.eb.localhost [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id wciEhVGC3FxC; Thu, 6 Jul 2017 15:24:52 +0200 (CEST) Received: from linux-diu0.suse (unknown [192.168.96.129]) by mail.embedded-brains.de (Postfix) with ESMTP id 7CAFE2A004F; Thu, 6 Jul 2017 15:24:52 +0200 (CEST) From: Sebastian Huber To: freebsd-hackers@freebsd.org Cc: kib@freebsd.org Subject: [PATCH] bitset(9): Add BIT_FLS() Date: Thu, 6 Jul 2017 15:24:40 +0200 Message-Id: <20170706132440.18520-1-sebastian.huber@embedded-brains.de> X-Mailer: git-send-email 2.12.3 X-Authenticated-Sender: smtp-embedded@poldinet.de X-Virus-Scanned: Clear (ClamAV 0.99.2/23539/Thu Jul 6 14:09:54 2017) X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 06 Jul 2017 13:47:31 -0000 Add BIT_FLS() analogous to BIT_FFS(). The benefit of BIT_FLS() is that ffsl() can be implemented with a count leading zeros instruction which is more widespread available. --- share/man/man9/bitset.9 | 22 +++++++++++++++++++++- sys/sys/bitset.h | 15 +++++++++++++++ 2 files changed, 36 insertions(+), 1 deletion(-) diff --git a/share/man/man9/bitset.9 b/share/man/man9/bitset.9 index d4060ace24c..f7f8a502b04 100644 --- a/share/man/man9/bitset.9 +++ b/share/man/man9/bitset.9 @@ -24,7 +24,7 @@ .\" .\" $FreeBSD$ .\" -.Dd May 24, 2017 +.Dd July 6, 2017 .Dt BITSET 9 .Os .Sh NAME @@ -43,6 +43,7 @@ .Nm BIT_EMPTY , .Nm BIT_ISFULLSET , .Nm BIT_FFS , +.Nm BIT_FLS , .Nm BIT_COUNT , .Nm BIT_SUBSET , .Nm BIT_OVERLAP , @@ -85,6 +86,8 @@ .Ft int .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset" .Ft int +.Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset" +.Ft int .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset" .\" .Ft bool @@ -282,6 +285,23 @@ index parameter to any other macro, you must subtract one from the result. .Pp The +.Fn BIT_FLS +macro returns the 1-index of the last (highest) set bit in +.Fa bitset , +or zero if +.Fa bitset +is empty. +Like with +.Xr fls 3 , +to use the non-zero result of +.Fn BIT_FLS +as a +.Fa bit +index parameter to any other +.Nm +macro, you must subtract one from the result. +.Pp +The .Fn BIT_COUNT macro returns the total number of set bits in .Fa bitset . diff --git a/sys/sys/bitset.h b/sys/sys/bitset.h index 8bc9e3d87a0..1ed19531b3b 100644 --- a/sys/sys/bitset.h +++ b/sys/sys/bitset.h @@ -213,6 +213,21 @@ __bit; \ }) +#define BIT_FLS(_s, p) __extension__ ({ \ + __size_t __i; \ + int __bit; \ + \ + __bit = 0; \ + for (__i = __bitset_words((_s)) - 1; __i >= 0; __i--) { \ + if ((p)->__bits[__i] != 0) { \ + __bit = flsl((p)->__bits[__i]); \ + __bit += __i * _BITSET_BITS; \ + break; \ + } \ + } \ + __bit; \ +}) + #define BIT_COUNT(_s, p) __extension__ ({ \ __size_t __i; \ int __count; \ -- 2.12.3