From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received-SPF: Pass (sender SPF authorized) identity=mailfrom; client-ip=148.163.129.52; helo=dispatch1-us1.ppe-hosted.com; envelope-from=tpilar@solarflare.com; receiver=edk2-devel@lists.01.org Received: from dispatch1-us1.ppe-hosted.com (dispatch1-us1.ppe-hosted.com [148.163.129.52]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id E6D2D2096FAA4 for ; Mon, 2 Jul 2018 02:32:38 -0700 (PDT) X-Virus-Scanned: Proofpoint Essentials engine Received: from webmail.solarflare.com (webmail.solarflare.com [12.187.104.26]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1-us1.ppe-hosted.com (Proofpoint Essentials ESMTP Server) with ESMTPS id 09083A80070 for ; Mon, 2 Jul 2018 09:32:38 +0000 (UTC) Received: from tp-desktop.uk.solarflarecom.com (10.17.20.51) by ocex03.SolarFlarecom.com (10.20.40.36) with Microsoft SMTP Server (TLS) id 15.0.1044.25; Mon, 2 Jul 2018 02:32:35 -0700 To: References: <737e881b-e3fc-1523-2b11-f324e1d398a7@solarflare.com> <4A89E2EF3DFEDB4C8BFDE51014F606A14E2A0C7F@SHSMSX104.ccr.corp.intel.com> From: "Tomas Pilar (tpilar)" Message-ID: Date: Mon, 2 Jul 2018 10:32:33 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.4.0 MIME-Version: 1.0 In-Reply-To: X-Originating-IP: [10.17.20.51] X-MDID: 1530523958-U0U4PtoqGl0T Subject: Re: [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods X-BeenThere: edk2-devel@lists.01.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: EDK II Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 02 Jul 2018 09:32:39 -0000 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Content-Language: en-US On 02/07/18 10:31, Tomas Pilar (tpilar) wrote: > Hi Liming, > > Using a bitmask to advertise capabilities is a common mechanism in driver APIs (e.g. network link capabilites). In some cases, one needs to allocate a buffer per capability Apologies, I meant 'buffer with size proportional to advertised capabilites'. > and thus they need to count the set bits. The algorithms to do that are fairly well known and generally provided in bitfield libraries. I expect that this will be useful to quite a number of IHV developers (as well as me). > > Cheers, > Tom > > On 02/07/18 09:22, Gao, Liming wrote: >> Tomas: >> Could you share some background what code depends on new added APIs? >> >> Thanks >> Liming >>> -----Original Message----- >>> From: edk2-devel [mailto:edk2-devel-bounces@lists.01.org] On Behalf Of >>> Tomas Pilar (tpilar) >>> Sent: Friday, June 29, 2018 5:42 PM >>> To: edk2-devel@lists.01.org >>> Subject: [edk2] [PATCH] MdePkg/BaseLib: Add bit field Hamming weight >>> calculation methods >>> >>> Add 32-bit and 64-bit functions that count number of set bits in a bitfield >>> using the divide-and-count method. >>> >>> Contributed-under: TianoCore Contribution Agreement 1.1 >>> Signed-off-by: Tomas Pilar >>> --- >>> MdePkg/Include/Library/BaseLib.h | 56 +++++++++++++++++++++++++++ >>> MdePkg/Library/BaseLib/BitField.c | 79 >>> +++++++++++++++++++++++++++++++++++++++ >>> 2 files changed, 135 insertions(+) >>> >>> diff --git a/MdePkg/Include/Library/BaseLib.h >>> b/MdePkg/Include/Library/BaseLib.h >>> index 1db3a04..7eb0488 100644 >>> --- a/MdePkg/Include/Library/BaseLib.h >>> +++ b/MdePkg/Include/Library/BaseLib.h >>> @@ -4609,6 +4609,62 @@ BitFieldAndThenOr64 ( >>> IN UINT64 OrData >>> ); >>> >>> +/** >>> + Reads a bit field from a 32-bit value, counts and returns >>> + the number of set bits. >>> + >>> + Counts the number of set bits in the bit field specified by >>> + StartBit and EndBit in Operand. The count is returned. >>> + >>> + If StartBit is greater than 31, then ASSERT(). >>> + If EndBit is greater than 31, then ASSERT(). >>> + If EndBit is less than StartBit, then ASSERT(). >>> + >>> + @param Operand Operand on which to perform the bitfield operation. >>> + @param StartBit The ordinal of the least significant bit in the bit field. >>> + Range 0..31. >>> + @param EndBit The ordinal of the most significant bit in the bit field. >>> + Range 0..31. >>> + >>> + @return The number of bits set between StartBit and EndBit. >>> + >>> +**/ >>> +UINT8 >>> +EFIAPI >>> +BitFieldHammingWeight32 ( >>> + IN UINT32 Operand, >>> + IN UINTN StartBit, >>> + IN UINTN EndBit >>> + ); >>> + >>> +/** >>> + Reads a bit field from a 64-bit value, counts and returns >>> + the number of set bits. >>> + >>> + Counts the number of set bits in the bit field specified by >>> + StartBit and EndBit in Operand. The count is returned. >>> + >>> + If StartBit is greater than 63, then ASSERT(). >>> + If EndBit is greater than 63, then ASSERT(). >>> + If EndBit is less than StartBit, then ASSERT(). >>> + >>> + @param Operand Operand on which to perform the bitfield operation. >>> + @param StartBit The ordinal of the least significant bit in the bit field. >>> + Range 0..63. >>> + @param EndBit The ordinal of the most significant bit in the bit field. >>> + Range 0..63. >>> + >>> + @return The number of bits set between StartBit and EndBit. >>> + >>> +**/ >>> +UINT8 >>> +EFIAPI >>> +BitFieldHammingWeight64 ( >>> + IN UINT64 Operand, >>> + IN UINTN StartBit, >>> + IN UINTN EndBit >>> + ); >>> + >>> // >>> // Base Library Checksum Functions >>> // >>> diff --git a/MdePkg/Library/BaseLib/BitField.c >>> b/MdePkg/Library/BaseLib/BitField.c >>> index d2d3150..af06db8 100644 >>> --- a/MdePkg/Library/BaseLib/BitField.c >>> +++ b/MdePkg/Library/BaseLib/BitField.c >>> @@ -920,3 +920,82 @@ BitFieldAndThenOr64 ( >>> OrData >>> ); >>> } >>> + >>> +/** >>> + Reads a bit field from a 32-bit value, counts and returns >>> + the number of set bits. >>> + >>> + Counts the number of set bits in the bit field specified by >>> + StartBit and EndBit in Operand. The count is returned. >>> + >>> + If StartBit is greater than 31, then ASSERT(). >>> + If EndBit is greater than 31, then ASSERT(). >>> + If EndBit is less than StartBit, then ASSERT(). >>> + >>> + @param Operand Operand on which to perform the bitfield operation. >>> + @param StartBit The ordinal of the least significant bit in the bit field. >>> + Range 0..31. >>> + @param EndBit The ordinal of the most significant bit in the bit field. >>> + Range 0..31. >>> + >>> + @return The number of bits set between StartBit and EndBit. >>> + >>> +**/ >>> +UINT8 >>> +EFIAPI >>> +BitFieldHammingWeight32 ( >>> + IN UINT32 Operand, >>> + IN UINTN StartBit, >>> + IN UINTN EndBit >>> + ) >>> +{ >>> + ASSERT (EndBit < 32); >>> + ASSERT (StartBit <= EndBit); >>> + >>> + UINT32 Count = BitFieldRead32 (Operand, StartBit, EndBit); >>> + Count -= ((Count >> 1) & 0x55555555); >>> + Count = (Count & 0x33333333) + ((Count >> 2) & 0x33333333); >>> + Count += Count >> 4; >>> + Count &= 0x0F0F0F0F; >>> + Count += Count >> 8; >>> + Count += Count >> 16; >>> + >>> + return (UINT8) Count & 0x3F; >>> +} >>> + >>> +/** >>> + Reads a bit field from a 64-bit value, counts and returns >>> + the number of set bits. >>> + >>> + Counts the number of set bits in the bit field specified by >>> + StartBit and EndBit in Operand. The count is returned. >>> + >>> + If StartBit is greater than 63, then ASSERT(). >>> + If EndBit is greater than 63, then ASSERT(). >>> + If EndBit is less than StartBit, then ASSERT(). >>> + >>> + @param Operand Operand on which to perform the bitfield operation. >>> + @param StartBit The ordinal of the least significant bit in the bit field. >>> + Range 0..63. >>> + @param EndBit The ordinal of the most significant bit in the bit field. >>> + Range 0..63. >>> + >>> + @return The number of bits set between StartBit and EndBit. >>> + >>> +**/ >>> +UINT8 >>> +EFIAPI >>> +BitFieldHammingWeight64 ( >>> + IN UINT64 Operand, >>> + IN UINTN StartBit, >>> + IN UINTN EndBit >>> + ) >>> +{ >>> + ASSERT (EndBit < 64); >>> + ASSERT (StartBit <= EndBit); >>> + >>> + UINT64 BitField = BitFieldRead64 (Operand, StartBit, EndBit); >>> + UINT8 Count = BitFieldHammingWeight32 (BitField, 0, 31); >>> + return Count + BitFieldHammingWeight32(RShiftU64(BitField, 32), 0, 31); >>> +} >>> + >>> -- >>> 2.9.5 >>> >>> _______________________________________________ >>> edk2-devel mailing list >>> edk2-devel@lists.01.org >>> https://lists.01.org/mailman/listinfo/edk2-devel > _______________________________________________ > edk2-devel mailing list > edk2-devel@lists.01.org > https://lists.01.org/mailman/listinfo/edk2-devel