From mboxrd@z Thu Jan 1 00:00:00 1970 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 Authentication-Results: mx.groups.io; dkim=missing; spf=pass (domain: intel.com, ip: 192.55.52.115, mailfrom: ianx.kuo@intel.com) 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" 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" 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: [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> X-Mailer: git-send-email 2.30.0.windows.1 In-Reply-To: <20211008055017.827-1-ianx.kuo@intel.com> References: <20211008055017.827-1-ianx.kuo@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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=0D Cryptographic Library.=0D =0D -Copyright (c) 2009 - 2017, Intel Corporation. All rights reserved.
=0D +Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
=0D SPDX-License-Identifier: BSD-2-Clause-Patent=0D =0D **/=0D @@ -15,12 +15,6 @@ FILE *stderr =3D NULL; FILE *stdin =3D NULL;=0D FILE *stdout =3D NULL;=0D =0D -typedef=0D -int=0D -(*SORT_COMPARE)(=0D - IN VOID *Buffer1,=0D - IN VOID *Buffer2=0D - );=0D =0D //=0D // Duplicated from EDKII BaseSortLib for qsort() wrapper=0D 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=0D Library used for sorting and comparison routines.=0D =0D - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved.
= =0D + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
= =0D SPDX-License-Identifier: BSD-2-Clause-Patent=0D =0D **/=0D #ifndef __SORT_LIB_H__=0D #define __SORT_LIB_H__=0D =0D +#include =0D +=0D /**=0D Prototype for comparison function for any two element types.=0D =0D 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 ( //=0D // Math Services=0D //=0D +/**=0D + Prototype for comparison function for any two element types.=0D +=0D + @param[in] Buffer1 The pointer to first buffer.=0D + @param[in] Buffer2 The pointer to second buffer.=0D +=0D + @retval 0 Buffer1 equal to Buffer2.=0D + @return <0 Buffer1 is less than Buffer2.=0D + @return >0 Buffer1 is greater than Buffer2.=0D +**/=0D +typedef=0D +INTN=0D +(EFIAPI *SORT_COMPARE)(=0D + IN CONST VOID *Buffer1,=0D + IN CONST VOID *Buffer2=0D + );=0D +=0D +/**=0D + This function is identical to perform QuickSort,=0D + except that is uses the pre-allocated buffer so the in place sorting doe= s not need to=0D + allocate and free buffers constantly.=0D +=0D + Each element must be equal sized.=0D +=0D + if BufferToSort is NULL, then ASSERT.=0D + if CompareFunction is NULL, then ASSERT.=0D + if BufferOneElement is NULL, then ASSERT.=0D + if ElementSize is < 1, then ASSERT.=0D +=0D + if Count is < 2 then perform no action.=0D +=0D + @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele= ments=0D + on return a buffer of sorted elements=0D + @param[in] Count the number of elements in the buffer to s= ort=0D + @param[in] ElementSize Size of an element in bytes=0D + @param[in] CompareFunction The function to call to perform the compa= rison=0D + of any 2 elements=0D + @param[out] BufferOneElement Caller provided buffer whose size equals = to ElementSize.=0D + It's used by QuickSort() for swapping in = sorting.=0D +**/=0D +VOID=0D +EFIAPI=0D +QuickSort (=0D + IN OUT VOID *BufferToSort,=0D + IN CONST UINTN Count,=0D + IN CONST UINTN ElementSize,=0D + IN SORT_COMPARE CompareFunction,=0D + OUT VOID *BufferOneElement=0D + );=0D =0D /**=0D Shifts a 64-bit integer left between 0 and 63 bits. The low bits are fil= led=0D 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=0D LongJump.c=0D SetJump.c=0D + QuickSort.c=0D RShiftU64.c=0D RRotU64.c=0D RRotU32.c=0D 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=0D + Math worker functions.=0D +=0D + Copyright (c) 2021, Intel Corporation. All rights reserved.
=0D + SPDX-License-Identifier: BSD-2-Clause-Patent=0D +=0D +**/=0D +=0D +#include "BaseLibInternals.h"=0D +=0D +/**=0D + This function is identical to perform QuickSort,=0D + except that is uses the pre-allocated buffer so the in place sorting doe= s not need to=0D + allocate and free buffers constantly.=0D +=0D + Each element must be equal sized.=0D +=0D + if BufferToSort is NULL, then ASSERT.=0D + if CompareFunction is NULL, then ASSERT.=0D + if BufferOneElement is NULL, then ASSERT.=0D + if ElementSize is < 1, then ASSERT.=0D +=0D + if Count is < 2 then perform no action.=0D +=0D + @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele= ments=0D + on return a buffer of sorted elements=0D + @param[in] Count the number of elements in the buffer to s= ort=0D + @param[in] ElementSize Size of an element in bytes=0D + @param[in] CompareFunction The function to call to perform the compa= rison=0D + of any 2 elements=0D + @param[out] BufferOneElement Caller provided buffer whose size equals = to ElementSize.=0D + It's used by QuickSort() for swapping in = sorting.=0D +**/=0D +VOID=0D +EFIAPI=0D +QuickSort (=0D + IN OUT VOID *BufferToSort,=0D + IN CONST UINTN Count,=0D + IN CONST UINTN ElementSize,=0D + IN SORT_COMPARE CompareFunction,=0D + OUT VOID *BufferOneElement=0D + )=0D +{=0D + VOID *Pivot;=0D + UINTN LoopCount;=0D + UINTN NextSwapLocation;=0D +=0D + ASSERT (BufferToSort !=3D NULL);=0D + ASSERT (CompareFunction !=3D NULL);=0D + ASSERT (BufferOneElement !=3D NULL);=0D + ASSERT (ElementSize >=3D 1);=0D +=0D + if (Count < 2) {=0D + return;=0D + }=0D +=0D + NextSwapLocation =3D 0;=0D +=0D + //=0D + // pick a pivot (we choose last element)=0D + //=0D + Pivot =3D ((UINT8*) BufferToSort + ((Count - 1) * ElementSize));=0D +=0D + //=0D + // Now get the pivot such that all on "left" are below it=0D + // and everything "right" are above it=0D + //=0D + for (LoopCount =3D 0; LoopCount < Count -1; LoopCount++) {=0D + //=0D + // if the element is less than or equal to the pivot=0D + //=0D + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * E= lementSize)), Pivot) <=3D 0){=0D + //=0D + // swap=0D + //=0D + CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation= * ElementSize), ElementSize);=0D + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (= UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);=0D + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOn= eElement, ElementSize);=0D +=0D + //=0D + // increment NextSwapLocation=0D + //=0D + NextSwapLocation++;=0D + }=0D + }=0D + //=0D + // swap pivot to it's final position (NextSwapLocation)=0D + //=0D + CopyMem (BufferOneElement, Pivot, ElementSize);=0D + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize)= , ElementSize);=0D + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), Buffe= rOneElement, ElementSize);=0D +=0D + //=0D + // Now recurse on 2 partial lists. neither of these will have the 'pivo= t' element=0D + // IE list is sorted left half, pivot element, sorted right half...=0D + //=0D + if (NextSwapLocation >=3D 2) {=0D + QuickSort (=0D + BufferToSort,=0D + NextSwapLocation,=0D + ElementSize,=0D + CompareFunction,=0D + BufferOneElement=0D + );=0D + }=0D +=0D + if ((Count - NextSwapLocation - 1) >=3D 2) {=0D + QuickSort (=0D + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,=0D + Count - NextSwapLocation - 1,=0D + ElementSize,=0D + CompareFunction,=0D + BufferOneElement=0D + );=0D + }=0D +}=0D 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=0D # Base Library implementation for use with host based unit tests.=0D #=0D -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.
= =0D +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.
= =0D # Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.
= =0D # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.
=0D # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All righ= ts reserved.
=0D @@ -33,6 +33,7 @@ SwapBytes16.c=0D LongJump.c=0D SetJump.c=0D + QuickSort.c=0D RShiftU64.c=0D RRotU64.c=0D RRotU32.c=0D --=20 2.30.0.windows.1