From nobody Thu Apr 25 07:25:17 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of groups.io designates 66.175.222.108 as permitted sender) client-ip=66.175.222.108; envelope-from=bounce+27952+81655+1787277+3901457@groups.io; helo=mail02.groups.io; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of groups.io designates 66.175.222.108 as permitted sender) smtp.mailfrom=bounce+27952+81655+1787277+3901457@groups.io; dmarc=fail(p=none dis=none) header.from=intel.com ARC-Seal: i=1; a=rsa-sha256; t=1633672228; cv=none; d=zohomail.com; s=zohoarc; b=g8ngVv00Xui0kpYqkVbrZ3Ack08T+JAcMGLpnFVaZs09jxsmaNdjUOSvzMbhnfmzSb1lr4qKDVIetJ+Y3c5bjEjTr9pLW8li4ZSqBEV47nG0KUB0TPpI3IAlQQHqyO5D4M4oUf+8vYiFcxomPC4y4eyLSWrJvnmALlgo5AZbbQ4= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1633672228; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Id:List-Help:List-Unsubscribe:MIME-Version:Message-ID:Reply-To:References:Sender:Subject:To; bh=fVx8J/NJHSMkvJ8lxRr6PRK3e2uuedVMuS0dQaHNOXc=; b=RzYzQJFCXRtfNiO9mtJ1OwRr302c2b10mcFqe8HGrZegzBq/iLFx6Xt2egUl6h7pZN2qXwRaZAvsFYFB3nhWmVnlacUngoRe3GlIXLZY6YLLDABzoNikOj0ffkKM7n7bBfpZHKJ0KPk3J0/P8GqPW2PnEC37RPjfp+7YOnJ251Q= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of groups.io designates 66.175.222.108 as permitted sender) smtp.mailfrom=bounce+27952+81655+1787277+3901457@groups.io; dmarc=fail header.from= (p=none dis=none) Received: from mail02.groups.io (mail02.groups.io [66.175.222.108]) by mx.zohomail.com with SMTPS id 1633672228965535.3951315748037; Thu, 7 Oct 2021 22:50:28 -0700 (PDT) Return-Path: X-Received: by 127.0.0.2 with SMTP id K936YY1788612xAGo7Yj4wmA; Thu, 07 Oct 2021 22:50:28 -0700 X-Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by mx.groups.io with SMTP id smtpd.web12.5420.1633672226445692749 for ; Thu, 07 Oct 2021 22:50:28 -0700 X-IronPort-AV: E=McAfee;i="6200,9189,10130"; a="226727448" X-IronPort-AV: E=Sophos;i="5.85,356,1624345200"; d="scan'208";a="226727448" X-Received: from orsmga007.jf.intel.com ([10.7.209.58]) by fmsmga103.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 07 Oct 2021 22:50:24 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.85,356,1624345200"; d="scan'208";a="478850405" X-Received: from ikuox-desk1.gar.corp.intel.com ([10.227.107.18]) by orsmga007.jf.intel.com with ESMTP; 07 Oct 2021 22:50:22 -0700 From: "IanX Kuo" To: devel@edk2.groups.io Cc: amy.chan@intel.com, ray.ni@intel.com, IanX Kuo , Michael D Kinney , Liming Gao , Zhiguang Liu Subject: [edk2-devel] [PATCH v8 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib Date: Fri, 8 Oct 2021 13:50:17 +0800 Message-Id: <20211008055017.827-2-ianx.kuo@intel.com> In-Reply-To: <20211008055017.827-1-ianx.kuo@intel.com> References: <20211008055017.827-1-ianx.kuo@intel.com> MIME-Version: 1.0 Precedence: Bulk List-Unsubscribe: List-Subscribe: List-Help: Sender: devel@edk2.groups.io List-Id: Mailing-List: list devel@edk2.groups.io; contact devel+owner@edk2.groups.io Reply-To: devel@edk2.groups.io,ianx.kuo@intel.com X-Gm-Message-State: E5kYaGonJ3TH4FyEb55qMhhCx1787277AA= Content-Transfer-Encoding: quoted-printable DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=groups.io; q=dns/txt; s=20140610; t=1633672228; bh=LikaHvZRMN4EvR9im47sQYws1qSmte5Sd2w67E2FYYk=; h=Cc:Date:From:Reply-To:Subject:To; b=a1mHUgOGcGPGAJUU9UO99huFcAR1g09MCYOjafDn0pWoQgOpgBAto9914bEqCn78UyO NPoYvB4KWw7LanSHidQk2+0Ta2XPEzF6ioGwYKcZvgHmoAArWyan2Z02MUdTWJJ9tUeX+ 8qUH29WR3tUCBIA0Du6QSqU8HSl5qgG2i3k= X-ZohoMail-DKIM: pass (identity @groups.io) X-ZM-MESSAGEID: 1633672229567100004 Content-Type: text/plain; charset="utf-8" From: IanX Kuo REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 Add QuickSort function into BaseLib Cc: Ray Ni Cc: Michael D Kinney Cc: Liming Gao Cc: Zhiguang Liu Signed-off-by: IanX Kuo --- .../Library/BaseCryptLib/SysCall/CrtWrapper.c | 8 +- MdeModulePkg/Include/Library/SortLib.h | 4 +- MdePkg/Include/Library/BaseLib.h | 49 ++++++++ MdePkg/Library/BaseLib/BaseLib.inf | 1 + MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++ .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +- 6 files changed, 172 insertions(+), 9 deletions(-) create mode 100644 MdePkg/Library/BaseLib/QuickSort.c diff --git a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c b/CryptoPk= g/Library/BaseCryptLib/SysCall/CrtWrapper.c index 42235ab96a..d279ae7852 100644 --- a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c +++ b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c @@ -2,7 +2,7 @@ C Run-Time Libraries (CRT) Wrapper Implementation for OpenSSL-based Cryptographic Library. =20 -Copyright (c) 2009 - 2017, Intel Corporation. All rights reserved.
+Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
SPDX-License-Identifier: BSD-2-Clause-Patent =20 **/ @@ -15,12 +15,6 @@ FILE *stderr =3D NULL; FILE *stdin =3D NULL; FILE *stdout =3D NULL; =20 -typedef -int -(*SORT_COMPARE)( - IN VOID *Buffer1, - IN VOID *Buffer2 - ); =20 // // Duplicated from EDKII BaseSortLib for qsort() wrapper diff --git a/MdeModulePkg/Include/Library/SortLib.h b/MdeModulePkg/Include/= Library/SortLib.h index 70789709a7..a152016510 100644 --- a/MdeModulePkg/Include/Library/SortLib.h +++ b/MdeModulePkg/Include/Library/SortLib.h @@ -1,13 +1,15 @@ /** @file Library used for sorting and comparison routines. =20 - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved.
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
SPDX-License-Identifier: BSD-2-Clause-Patent =20 **/ #ifndef __SORT_LIB_H__ #define __SORT_LIB_H__ =20 +#include + /** Prototype for comparison function for any two element types. =20 diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/Base= Lib.h index 2452c1d92e..8234478377 100644 --- a/MdePkg/Include/Library/BaseLib.h +++ b/MdePkg/Include/Library/BaseLib.h @@ -2856,6 +2856,55 @@ RemoveEntryList ( // // Math Services // +/** + Prototype for comparison function for any two element types. + + @param[in] Buffer1 The pointer to first buffer. + @param[in] Buffer2 The pointer to second buffer. + + @retval 0 Buffer1 equal to Buffer2. + @return <0 Buffer1 is less than Buffer2. + @return >0 Buffer1 is greater than Buffer2. +**/ +typedef +INTN +(EFIAPI *SORT_COMPARE)( + IN CONST VOID *Buffer1, + IN CONST VOID *Buffer2 + ); + +/** + This function is identical to perform QuickSort, + except that is uses the pre-allocated buffer so the in place sorting doe= s not need to + allocate and free buffers constantly. + + Each element must be equal sized. + + if BufferToSort is NULL, then ASSERT. + if CompareFunction is NULL, then ASSERT. + if BufferOneElement is NULL, then ASSERT. + if ElementSize is < 1, then ASSERT. + + if Count is < 2 then perform no action. + + @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele= ments + on return a buffer of sorted elements + @param[in] Count the number of elements in the buffer to s= ort + @param[in] ElementSize Size of an element in bytes + @param[in] CompareFunction The function to call to perform the compa= rison + of any 2 elements + @param[out] BufferOneElement Caller provided buffer whose size equals = to ElementSize. + It's used by QuickSort() for swapping in = sorting. +**/ +VOID +EFIAPI +QuickSort ( + IN OUT VOID *BufferToSort, + IN CONST UINTN Count, + IN CONST UINTN ElementSize, + IN SORT_COMPARE CompareFunction, + OUT VOID *BufferOneElement + ); =20 /** Shifts a 64-bit integer left between 0 and 63 bits. The low bits are fil= led diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/Ba= seLib.inf index 6efa5315b6..cebda3b210 100644 --- a/MdePkg/Library/BaseLib/BaseLib.inf +++ b/MdePkg/Library/BaseLib/BaseLib.inf @@ -32,6 +32,7 @@ SwapBytes16.c LongJump.c SetJump.c + QuickSort.c RShiftU64.c RRotU64.c RRotU32.c diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/Qu= ickSort.c new file mode 100644 index 0000000000..1bdedf8e53 --- /dev/null +++ b/MdePkg/Library/BaseLib/QuickSort.c @@ -0,0 +1,116 @@ +/** @file + Math worker functions. + + Copyright (c) 2021, Intel Corporation. All rights reserved.
+ SPDX-License-Identifier: BSD-2-Clause-Patent + +**/ + +#include "BaseLibInternals.h" + +/** + This function is identical to perform QuickSort, + except that is uses the pre-allocated buffer so the in place sorting doe= s not need to + allocate and free buffers constantly. + + Each element must be equal sized. + + if BufferToSort is NULL, then ASSERT. + if CompareFunction is NULL, then ASSERT. + if BufferOneElement is NULL, then ASSERT. + if ElementSize is < 1, then ASSERT. + + if Count is < 2 then perform no action. + + @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele= ments + on return a buffer of sorted elements + @param[in] Count the number of elements in the buffer to s= ort + @param[in] ElementSize Size of an element in bytes + @param[in] CompareFunction The function to call to perform the compa= rison + of any 2 elements + @param[out] BufferOneElement Caller provided buffer whose size equals = to ElementSize. + It's used by QuickSort() for swapping in = sorting. +**/ +VOID +EFIAPI +QuickSort ( + IN OUT VOID *BufferToSort, + IN CONST UINTN Count, + IN CONST UINTN ElementSize, + IN SORT_COMPARE CompareFunction, + OUT VOID *BufferOneElement + ) +{ + VOID *Pivot; + UINTN LoopCount; + UINTN NextSwapLocation; + + ASSERT (BufferToSort !=3D NULL); + ASSERT (CompareFunction !=3D NULL); + ASSERT (BufferOneElement !=3D NULL); + ASSERT (ElementSize >=3D 1); + + if (Count < 2) { + return; + } + + NextSwapLocation =3D 0; + + // + // pick a pivot (we choose last element) + // + Pivot =3D ((UINT8*) BufferToSort + ((Count - 1) * ElementSize)); + + // + // Now get the pivot such that all on "left" are below it + // and everything "right" are above it + // + for (LoopCount =3D 0; LoopCount < Count -1; LoopCount++) { + // + // if the element is less than or equal to the pivot + // + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * E= lementSize)), Pivot) <=3D 0){ + // + // swap + // + CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation= * ElementSize), ElementSize); + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (= UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize); + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOn= eElement, ElementSize); + + // + // increment NextSwapLocation + // + NextSwapLocation++; + } + } + // + // swap pivot to it's final position (NextSwapLocation) + // + CopyMem (BufferOneElement, Pivot, ElementSize); + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize)= , ElementSize); + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), Buffe= rOneElement, ElementSize); + + // + // Now recurse on 2 partial lists. neither of these will have the 'pivo= t' element + // IE list is sorted left half, pivot element, sorted right half... + // + if (NextSwapLocation >=3D 2) { + QuickSort ( + BufferToSort, + NextSwapLocation, + ElementSize, + CompareFunction, + BufferOneElement + ); + } + + if ((Count - NextSwapLocation - 1) >=3D 2) { + QuickSort ( + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize, + Count - NextSwapLocation - 1, + ElementSize, + CompareFunction, + BufferOneElement + ); + } +} diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Librar= y/BaseLib/UnitTestHostBaseLib.inf index eae1a7158d..d09bd12bef 100644 --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf @@ -1,7 +1,7 @@ ## @file # Base Library implementation for use with host based unit tests. # -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.
+# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.
# Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.
# Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.
# Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All righ= ts reserved.
@@ -33,6 +33,7 @@ SwapBytes16.c LongJump.c SetJump.c + QuickSort.c RShiftU64.c RRotU64.c RRotU32.c --=20 2.30.0.windows.1 -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#81655): https://edk2.groups.io/g/devel/message/81655 Mute This Topic: https://groups.io/mt/86164172/1787277 Group Owner: devel+owner@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [importer@patchew.org] -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-