* [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods
@ 2018-06-29 9:41 Tomas Pilar (tpilar)
2018-07-02 8:22 ` Gao, Liming
2018-07-02 18:57 ` Evan Lloyd
0 siblings, 2 replies; 7+ messages in thread
From: Tomas Pilar (tpilar) @ 2018-06-29 9:41 UTC (permalink / raw)
To: edk2-devel@lists.01.org
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
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods
2018-06-29 9:41 [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods Tomas Pilar (tpilar)
@ 2018-07-02 8:22 ` Gao, Liming
2018-07-02 9:31 ` Tomas Pilar (tpilar)
2018-07-02 18:57 ` Evan Lloyd
1 sibling, 1 reply; 7+ messages in thread
From: Gao, Liming @ 2018-07-02 8:22 UTC (permalink / raw)
To: Tomas Pilar (tpilar), edk2-devel@lists.01.org
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 <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
>
>_______________________________________________
>edk2-devel mailing list
>edk2-devel@lists.01.org
>https://lists.01.org/mailman/listinfo/edk2-devel
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods
2018-07-02 8:22 ` Gao, Liming
@ 2018-07-02 9:31 ` Tomas Pilar (tpilar)
2018-07-02 9:32 ` Tomas Pilar (tpilar)
0 siblings, 1 reply; 7+ messages in thread
From: Tomas Pilar (tpilar) @ 2018-07-02 9:31 UTC (permalink / raw)
To: Gao, Liming, edk2-devel@lists.01.org
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 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 <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
>>
>> _______________________________________________
>> edk2-devel mailing list
>> edk2-devel@lists.01.org
>> https://lists.01.org/mailman/listinfo/edk2-devel
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods
2018-07-02 9:31 ` Tomas Pilar (tpilar)
@ 2018-07-02 9:32 ` Tomas Pilar (tpilar)
0 siblings, 0 replies; 7+ messages in thread
From: Tomas Pilar (tpilar) @ 2018-07-02 9:32 UTC (permalink / raw)
To: edk2-devel
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 <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
>>>
>>> _______________________________________________
>>> 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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods
2018-06-29 9:41 [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods Tomas Pilar (tpilar)
2018-07-02 8:22 ` Gao, Liming
@ 2018-07-02 18:57 ` Evan Lloyd
2018-07-03 9:47 ` Tomas Pilar (tpilar)
1 sibling, 1 reply; 7+ messages in thread
From: Evan Lloyd @ 2018-07-02 18:57 UTC (permalink / raw)
To: Tomas Pilar (tpilar), edk2-devel@lists.01.org
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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods
2018-07-02 18:57 ` Evan Lloyd
@ 2018-07-03 9:47 ` Tomas Pilar (tpilar)
2018-07-03 13:25 ` Gao, Liming
0 siblings, 1 reply; 7+ messages in thread
From: Tomas Pilar (tpilar) @ 2018-07-03 9:47 UTC (permalink / raw)
To: Evan Lloyd, edk2-devel@lists.01.org
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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods
2018-07-03 9:47 ` Tomas Pilar (tpilar)
@ 2018-07-03 13:25 ` Gao, Liming
0 siblings, 0 replies; 7+ messages in thread
From: Gao, Liming @ 2018-07-03 13:25 UTC (permalink / raw)
To: Tomas Pilar (tpilar), Evan Lloyd, edk2-devel@lists.01.org
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
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2018-07-03 13:25 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2018-06-29 9:41 [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods Tomas Pilar (tpilar)
2018-07-02 8:22 ` Gao, Liming
2018-07-02 9:31 ` Tomas Pilar (tpilar)
2018-07-02 9:32 ` Tomas Pilar (tpilar)
2018-07-02 18:57 ` Evan Lloyd
2018-07-03 9:47 ` Tomas Pilar (tpilar)
2018-07-03 13:25 ` Gao, Liming
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox