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

["Gao, Liming" <liming.gao@intel.com>]

Tom:
  I think CountOnes is easy to be understood. How about two APIs CountOnes32() and CountOnes64()?

Thanks
Liming
> -----Original Message-----
> From: edk2-devel [mailto:edk2-devel-bounces@lists.01.org] On Behalf Of Tomas Pilar (tpilar)
> Sent: Tuesday, July 3, 2018 5:48 PM
> To: Evan Lloyd <Evan.Lloyd@arm.com>; edk2-devel@lists.01.org
> Subject: Re: [edk2] [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods
> 
> 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.
> 
> _______________________________________________
> edk2-devel mailing list
> edk2-devel@lists.01.org
> https://lists.01.org/mailman/listinfo/edk2-devel