From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received-SPF: Pass (sender SPF authorized) identity=mailfrom; client-ip=192.55.52.136; helo=mga12.intel.com; envelope-from=liming.gao@intel.com; receiver=edk2-devel@lists.01.org Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id EEB20209831E9 for ; Tue, 3 Jul 2018 06:25:27 -0700 (PDT) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga008.jf.intel.com ([10.7.209.65]) by fmsmga106.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 03 Jul 2018 06:25:27 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,303,1526367600"; d="scan'208";a="54111777" Received: from fmsmsx105.amr.corp.intel.com ([10.18.124.203]) by orsmga008.jf.intel.com with ESMTP; 03 Jul 2018 06:25:15 -0700 Received: from shsmsx101.ccr.corp.intel.com (10.239.4.153) by FMSMSX105.amr.corp.intel.com (10.18.124.203) with Microsoft SMTP Server (TLS) id 14.3.319.2; Tue, 3 Jul 2018 06:25:14 -0700 Received: from shsmsx104.ccr.corp.intel.com ([169.254.5.87]) by SHSMSX101.ccr.corp.intel.com ([169.254.1.82]) with mapi id 14.03.0319.002; Tue, 3 Jul 2018 21:25:12 +0800 From: "Gao, Liming" To: "Tomas Pilar (tpilar)" , Evan Lloyd , "edk2-devel@lists.01.org" Thread-Topic: [edk2] [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods Thread-Index: AQHUD41wxdKOt+iKDkeramiFx9WXY6R7x7+AgAD43ICAAMH7kA== Date: Tue, 3 Jul 2018 13:25:11 +0000 Message-ID: <4A89E2EF3DFEDB4C8BFDE51014F606A14E2A16E4@SHSMSX104.ccr.corp.intel.com> References: <737e881b-e3fc-1523-2b11-f324e1d398a7@solarflare.com> In-Reply-To: Accept-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ctpclassification: CTP_NT x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZTQ0ODhmZGMtNTZlYS00NTU3LTg0MTUtYTM0YjVhZmI3Njk0IiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiR2hRbXArSGdDRUl5UXhFTXR1Vm5oTzN3XC9qWGFNRmd6Vm5PMEdPeHdIT1puR0NnTnNGV0JvMmUrS01oRzdVeWkifQ== dlp-product: dlpe-windows dlp-version: 11.0.200.100 dlp-reaction: no-action x-originating-ip: [10.239.127.40] MIME-Version: 1.0 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 13:25:28 -0000 Content-Language: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Tom: I think CountOnes is easy to be understood. How about two APIs CountOnes3= 2() and CountOnes64()? Thanks Liming > -----Original Message----- > From: edk2-devel [mailto:edk2-devel-bounces@lists.01.org] On Behalf Of To= mas Pilar (tpilar) > Sent: Tuesday, July 3, 2018 5:48 PM > To: Evan Lloyd ; edk2-devel@lists.01.org > Subject: Re: [edk2] [PATCH] MdePkg/BaseLib: Add bit field Hamming weight = calculation methods >=20 > Thanks for suggestions. The answer to your comments is that I copied the = look and feel of the other bitfield functions. >=20 > 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. >=20 > I agree that a pure function would be simpler and more elegant, but the r= est of the bitfield functions allow you to operate on a specific > part of the operand (e.g. BitFieldAnd32(Operand, StartBit, EndBit, AndDat= a)), so I reasoned that the API should be kept similar. >=20 > I found two names for this functionality, population count and hamming we= ight and both are used (Linux kernel uses hamming weight). > I don't mind using PopCount if you think it's more clear. >=20 > The other issue seems a problem with line endings. >=20 > Cheers, > Tom >=20 >=20 > 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 we= ight 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 bit= field > >> 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 operatio= n. > >> + @param StartBit The ordinal of the least significant bit in the b= it field. > >> + Range 0..31. > >> + @param EndBit The ordinal of the most significant bit in the bi= t 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 wh= y not call it that (or similar)? (I had to look up > "HammingWeight") > > Also, why conflate BitField access and CountOnes in one function? A "p= ure" 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 operati= on. > >> + @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 b= it 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 t= he 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 operatio= n. > >> + @param StartBit The ordinal of the least significant bit in the b= it field. > >> + Range 0..31. > >> + @param EndBit The ordinal of the most significant bit in the bi= t 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 <=3D EndBit); > >> + > >> + UINT32 Count =3D BitFieldRead32 (Operand, StartBit, EndBit); Count= -=3D > >> + ((Count >> 1) & 0x55555555); Count =3D (Count & 0x33333333) + ((Cou= nt > >> + >> 2) & 0x33333333); Count +=3D Count >> 4; Count &=3D 0x0F0F0F0F; > >> + Count +=3D Count >> 8; Count +=3D Count >> 16; > > [[Evan Lloyd]] CCS has (in 3.2.2) "Never put more than one statement p= er 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 operati= on. > >> + @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 b= it 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 <=3D EndBit); > >> + > >> + UINT64 BitField =3D BitFieldRead64 (Operand, StartBit, EndBit); > >> + UINT8 Count =3D 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 co= nfidential and may also be privileged. If you are not the > intended recipient, please notify the sender immediately and do not discl= ose the contents to any other person, use it for any purpose, > or store or copy the information in any medium. Thank you. >=20 > _______________________________________________ > edk2-devel mailing list > edk2-devel@lists.01.org > https://lists.01.org/mailman/listinfo/edk2-devel