Re: [PATCH v3 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib


Yao, Jiewen
 

Acked-by: Jiewen Yao <Jiewen.yao@intel.com>

-----Original Message-----
From: Kuo, IanX <ianx.kuo@intel.com>
Sent: Sunday, October 17, 2021 6:34 AM
To: devel@edk2.groups.io
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kuo, IanX
<ianx.kuo@intel.com>; Yao, Jiewen <jiewen.yao@intel.com>; Wang, Jian J
<jian.j.wang@intel.com>; Lu, XiaoyuX <xiaoyux.lu@intel.com>; Jiang, Guomin
<guomin.jiang@intel.com>
Subject: [PATCH v3 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib

From: IanX Kuo <ianx.kuo@intel.com>

REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675

Use QuickSort instead of QuickSortWorker

Cc: Ray Ni <ray.ni@intel.com>
Cc: Jiewen Yao <jiewen.yao@intel.com>
Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Xiaoyu Lu <xiaoyux.lu@intel.com>
Cc: Guomin Jiang <guomin.jiang@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
.../Library/BaseCryptLib/SysCall/CrtWrapper.c | 92 +------------------
1 file changed, 2 insertions(+), 90 deletions(-)

diff --git a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
index 42235ab96a..33ff0fcdb6 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.



-Copyright (c) 2009 - 2017, Intel Corporation. All rights reserved.<BR>

+Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.<BR>

SPDX-License-Identifier: BSD-2-Clause-Patent



**/

@@ -22,91 +22,6 @@ int
IN VOID *Buffer2

);



-//

-// Duplicated from EDKII BaseSortLib for qsort() wrapper

-//

-STATIC

-VOID

-QuickSortWorker (

- IN OUT VOID *BufferToSort,

- IN CONST UINTN Count,

- IN CONST UINTN ElementSize,

- IN SORT_COMPARE CompareFunction,

- IN VOID *Buffer

- )

-{

- VOID *Pivot;

- UINTN LoopCount;

- UINTN NextSwapLocation;

-

- ASSERT(BufferToSort != NULL);

- ASSERT(CompareFunction != NULL);

- ASSERT(Buffer != NULL);

-

- if (Count < 2 || ElementSize < 1) {

- return;

- }

-

- NextSwapLocation = 0;

-

- //

- // Pick a pivot (we choose last element)

- //

- Pivot = ((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 = 0; LoopCount < Count - 1; LoopCount++)

- {

- //

- // If the element is less than the pivot

- //

- if (CompareFunction ((VOID *)((UINT8 *)BufferToSort + ((LoopCount) *
ElementSize)), Pivot) <= 0) {

- //

- // Swap

- //

- CopyMem (Buffer, (UINT8 *)BufferToSort + (NextSwapLocation *
ElementSize), ElementSize);

- CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize),
(UINT8 *)BufferToSort + ((LoopCount) * ElementSize), ElementSize);

- CopyMem ((UINT8 *)BufferToSort + ((LoopCount) * ElementSize), Buffer,
ElementSize);

-

- //

- // Increment NextSwapLocation

- //

- NextSwapLocation++;

- }

- }

- //

- // Swap pivot to its final position (NextSwapLocation)

- //

- CopyMem (Buffer, Pivot, ElementSize);

- CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize),
ElementSize);

- CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), Buffer,
ElementSize);

-

- //

- // Now recurse on 2 partial lists. Neither of these will have the 'pivot' element.

- // IE list is sorted left half, pivot element, sorted right half...

- //

- QuickSortWorker (

- BufferToSort,

- NextSwapLocation,

- ElementSize,

- CompareFunction,

- Buffer

- );

-

- QuickSortWorker (

- (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,

- Count - NextSwapLocation - 1,

- ElementSize,

- CompareFunction,

- Buffer

- );

-

- return;

-}

-

//---------------------------------------------------------

// Standard C Run-time Library Interface Wrapper

//---------------------------------------------------------

@@ -337,10 +252,7 @@ void qsort (void *base, size_t num, size_t width, int
(*compare)(const void *, c
Buffer = malloc (width);

ASSERT (Buffer != NULL);



- //

- // Re-use PerformQuickSort() function Implementation in EDKII BaseSortLib.

- //

- QuickSortWorker (base, (UINTN)num, (UINTN)width,
(SORT_COMPARE)compare, Buffer);

+ QuickSort (base, (UINTN)num, (UINTN)width, compare, Buffer);



free (Buffer);

return;

--
2.30.0.windows.1

Join devel@edk2.groups.io to automatically receive all group messages.