From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received-SPF: Pass (sender SPF authorized) identity=mailfrom; client-ip=40.107.0.48; helo=eur02-am5-obe.outbound.protection.outlook.com; envelope-from=evan.lloyd@arm.com; receiver=edk2-devel@lists.01.org Received: from EUR02-AM5-obe.outbound.protection.outlook.com (mail-eopbgr00048.outbound.protection.outlook.com [40.107.0.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id B9A28203B99D3 for ; Mon, 2 Jul 2018 11:57:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=5fJBUKVlv9bO2jKpNzCoMY6eeDOtSwENUf96KK9PDPs=; b=b2PryQgy2eKKuz6YbjMkdDeJC4EHt5VOCJoEgIfVWefyYErbbTACLKRMdA1lvv3y+ATqlwnt+IcHkS673Ck4emiyXr9l3aAa4kxRDrA5MIWpCOIi4532C+/5Z0ewRx7/1pRGYK4DYM/qwS3nq39vmovBNSMUEJ68TcDBPere8EU= Received: from DB6PR08MB2806.eurprd08.prod.outlook.com (10.170.222.149) by DB6PR08MB2936.eurprd08.prod.outlook.com (10.175.235.32) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.906.25; Mon, 2 Jul 2018 18:57:11 +0000 Received: from DB6PR08MB2806.eurprd08.prod.outlook.com ([fe80::3914:1294:dd8f:bdc]) by DB6PR08MB2806.eurprd08.prod.outlook.com ([fe80::3914:1294:dd8f:bdc%4]) with mapi id 15.20.0906.026; Mon, 2 Jul 2018 18:57:11 +0000 From: Evan Lloyd To: "Tomas Pilar (tpilar)" , "edk2-devel@lists.01.org" Thread-Topic: [edk2] [PATCH] MdePkg/BaseLib: Add bit field Hamming weight calculation methods Thread-Index: AQHUD41mH0+wbmPicUOq6c1tGyOIYqR412Gw Date: Mon, 2 Jul 2018 18:57:11 +0000 Message-ID: References: <737e881b-e3fc-1523-2b11-f324e1d398a7@solarflare.com> In-Reply-To: <737e881b-e3fc-1523-2b11-f324e1d398a7@solarflare.com> Accept-Language: en-GB, en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Evan.Lloyd@arm.com; x-originating-ip: [217.140.96.140] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; DB6PR08MB2936; 7:5puTtzp5ogBCzGoxMLugv9Nhpcu5LjsRJ++MyDe63BVwf6DUe/0u/Vq/m3c21BOxmiAZkb1i+9byOXqUf6roE6w7LQ0WeOcAr3MrCNfuilq1VtfXuASqVbEfMpkcftYZUsX6Od2lI7DI7dzc0Lz+cAmPdXem7eLkRRIODryHknsA+5Zf1+TEc/q9yf179pupgKOC7Cg2jtBR3U4oZXEi5OHjfAVAlJ93l+Z5HX8jkHBqt9vatPYAYYaGqYTW9+m8 x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: a1cc5101-fa29-4645-2ecb-08d5e04d9e4a x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989117)(5600053)(711020)(48565401081)(4534165)(4627221)(201703031133081)(201702281549075)(8990107)(2017052603328)(7153060)(7193020); SRVR:DB6PR08MB2936; x-ms-traffictypediagnostic: DB6PR08MB2936: x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(223705240517415)(162533806227266); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3231254)(944501410)(52105095)(10201501046)(3002001)(93006095)(93001095)(6055026)(149027)(150027)(6041310)(20161123562045)(20161123558120)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(6072148)(201708071742011)(7699016); SRVR:DB6PR08MB2936; BCL:0; PCL:0; RULEID:; SRVR:DB6PR08MB2936; x-forefront-prvs: 07215D0470 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(39860400002)(396003)(346002)(366004)(136003)(376002)(13464003)(199004)(189003)(40434004)(486006)(25786009)(476003)(81166006)(81156014)(6506007)(8936002)(6436002)(53936002)(102836004)(68736007)(55016002)(6306002)(53546011)(305945005)(316002)(33656002)(186003)(229853002)(99286004)(6116002)(106356001)(3846002)(74316002)(7736002)(14454004)(26005)(5250100002)(105586002)(6246003)(478600001)(966005)(72206003)(76176011)(66066001)(8676002)(446003)(11346002)(97736004)(256004)(2501003)(86362001)(575784001)(14444005)(5024004)(5660300001)(110136005)(2906002)(2900100001)(9686003)(7696005)(16393002)(19627235001); DIR:OUT; SFP:1101; SCL:1; SRVR:DB6PR08MB2936; H:DB6PR08MB2806.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: xg9eYPozwRGKvxZBCPEsP0vqizRr40YtmnUgkfL1Oc0vCzYJcphGghy7PLUJBJLGsyDDIbGMleQ3DjFNXns70b2HuXTDEYeYBKwBX5Mwp3imNHyhHhrThEwN/QzgaSzrBqFbxBo9LyV7hsQoS3vdDPCUFFkdXHJyWLmSPwd6nDszD2i1Yfn+LiUzfle5KbPj+10cQF7K39l5koWLDI6T2QvoqQQeZtDof8l6KMehwI/ZliEC0JPfIqyR2yvK0aCtt8nMOdOs+o9n3vu4Wi7Bn6i8lBg6Y40b43Bv90eWTAc08tuKHDpgNbDaImIy5OsvdDLdiZCwe4E9EA77DNrKtqhWOj/JU+HHwc+XEboYmXk= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: a1cc5101-fa29-4645-2ecb-08d5e04d9e4a X-MS-Exchange-CrossTenant-originalarrivaltime: 02 Jul 2018 18:57:11.4621 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR08MB2936 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: Mon, 02 Jul 2018 18:57:15 -0000 Content-Language: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable 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 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 bitfie= ld > 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 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 f= ield. > + 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 no= t 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 n= ext 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 f= ield. > + 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) + ((Count > + >> 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 per l= ine." - 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 <=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 confid= ential and may also be privileged. If you are not the intended recipient, p= lease 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.