Re: [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods

["Tomas Pilar (tpilar)" <tpilar@solarflare.com>]

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 <edk2-devel-bounces@lists.01.org> 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 <tpilar@solarflare.com>
>> ---
>>  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.