1. Patchew
  2. EDK2
  3. [edk2-devel] [PATCH v6 0/3] Add function QuickSort into MdePkg/BaseLib
  4. View patch

[edk2-devel] [PATCH v6 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib

IanX Kuo posted 3 patches 4 years, 3 months ago
There is a newer version of this series
[edk2-devel] [PATCH v6 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
Posted by IanX Kuo 4 years, 3 months ago 
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..b10edaae5b 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, (BASE_SORT_COMPARE)compare, Buffer);
 
   free (Buffer);
   return;
-- 
2.30.0.windows.1



-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#82206): https://edk2.groups.io/g/devel/message/82206
Mute This Topic: https://groups.io/mt/86406845/1787277
Group Owner: devel+owner@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [importer@patchew.org]
-=-=-=-=-=-=-=-=-=-=-=-
Re: [edk2-devel] [PATCH v6 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
Posted by Guomin Jiang 4 years, 3 months ago 
Reviewed-by: Guomin Jiang <guomin.jiang@intel.com>

> -----Original Message-----
> From: Kuo, IanX <ianx.kuo@intel.com>
> Sent: Monday, October 18, 2021 12:21 PM
> 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 v6 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..b10edaae5b 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,
> (BASE_SORT_COMPARE)compare, Buffer);
> 
> 
> 
>    free (Buffer);
> 
>    return;
> 
> --
> 2.30.0.windows.1



-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#82450): https://edk2.groups.io/g/devel/message/82450
Mute This Topic: https://groups.io/mt/86406845/1787277
Group Owner: devel+owner@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [importer@patchew.org]
-=-=-=-=-=-=-=-=-=-=-=-

Patchew 2.1-devel-b67e4c2

© 2016 - 2026 Red Hat, Inc.