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

[Marvin Häuser]

Hey IanX,

On 16.10.21 01:25, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo at intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Use QuickSort instead of QuickSortWorker
>
> Cc: Ray Ni <ray.ni at intel.com>
> Cc: Jiewen Yao <jiewen.yao at intel.com>
> Cc: Jian J Wang <jian.j.wang at intel.com>
> Cc: Xiaoyu Lu <xiaoyux.lu at intel.com>
> Cc: Guomin Jiang <guomin.jiang at intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo at 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);

Same as the other occurrence, can this cast be dropped?

Best regards,
Marvin

>   
>     free (Buffer);
>     return;



-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#82177): https://edk2.groups.io/g/devel/message/82177
Mute This Topic: https://groups.io/mt/86362182/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-