From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received-SPF: Pass (sender SPF authorized) identity=mailfrom; client-ip=67.231.154.164; 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 [67.231.154.164]) (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 54DAD210F156A for ; Tue, 3 Jul 2018 02:47:59 -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-us4.ppe-hosted.com (Proofpoint Essentials ESMTP Server) with ESMTPS id D8775140059; Tue, 3 Jul 2018 09:47:57 +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; Tue, 3 Jul 2018 02:47:54 -0700 To: Evan Lloyd , "edk2-devel@lists.01.org" References: <737e881b-e3fc-1523-2b11-f324e1d398a7@solarflare.com> From: "Tomas Pilar (tpilar)" Message-ID: Date: Tue, 3 Jul 2018 10:47:53 +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: 1530611278-IgkDG6RkRhPV 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: Tue, 03 Jul 2018 09:47:59 -0000 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Content-Language: en-US Thanks for suggestions. The answer to your comments is that I copied the look and feel of the other bitfield functions. The extra assert is mentioned in the documentation for the other bitfield functions even though it just follows from the other two asserts - for clarity I suppose. I agree that a pure function would be simpler and more elegant, but the rest of the bitfield functions allow you to operate on a specific part of the operand (e.g. BitFieldAnd32(Operand, StartBit, EndBit, AndData)), so I reasoned that the API should be kept similar. I found two names for this functionality, population count and hamming weight and both are used (Linux kernel uses hamming weight). I don't mind using PopCount if you think it's more clear. The other issue seems a problem with line endings. Cheers, Tom On 02/07/18 19:57, Evan Lloyd wrote: > Hi Tomas > I'm not a maintainer here, so my comments are just that and carry no weight beyond making suggestions that you may wish to consider. > >> -----Original Message----- >> From: edk2-devel On Behalf Of Tomas >> Pilar (tpilar) >> Sent: 29 June 2018 10:42 >> 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 >> + ); >> + > [[Evan Lloyd]] I can see the benefit of a "CountOnes" function, but why not call it that (or similar)? (I had to look up "HammingWeight") > Also, why conflate BitField access and CountOnes in one function? A "pure" function to count ones might be used in other ways, and it is fairly clear if you write: > CountOnes(BitFieldRead64 (Operand, StartBit, 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(). > [[Evan Lloyd]] This ASSERT is not in the code and is redundant given the next two. > >> + 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; > [[Evan Lloyd]] CCS has (in 3.2.2) "Never put more than one statement per line." - or is this a CRLF problem? > >> + >> + 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(). > [[Evan Lloyd]] This doesn't quite reflect the actual code. >> + >> + @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 > IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.