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

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

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
+  );
+
+/**
+   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