[PATCH v5 0/4] Add function QuickSort into MdePkg/BaseLib

[PATCH v5 0/4] Add function QuickSort into MdePkg/BaseLib

[IanX Kuo]

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

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

1. MdePkg/BaseLib: Add QuickSort function
2. MdeModulePkg/SortLib: Use QuickSort instead of QuickSortWorker
3. CryptLib/CryptLib: Remove duplicate QuickSortWorker
4. CpuCacheInfoLib: Remove MdeModulePkg dependency

IanX Kuo (4):
  MdePkg/BaseLib: Add QuickSort function on BaseLib
  MdeModulePkg/SortLib: Add QuickSort function on BaseLib
  CryptoPkg/CryptLib: Add QuickSort function on BaseLib
  UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib

 .../Library/BaseCryptLib/SysCall/CrtWrapper.c |  92 +-------------
 .../Library/BaseSortLib/BaseSortLib.c         | 117 +----------------
 .../Library/UefiSortLib/UefiSortLib.c         | 118 +-----------------
 MdePkg/Include/Library/BaseLib.h              |  49 ++++++++
 MdePkg/Library/BaseLib/BaseLib.inf            |   1 +
 MdePkg/Library/BaseLib/QuickSort.c            | 117 +++++++++++++++++
 .../Library/BaseLib/UnitTestHostBaseLib.inf   |   3 +-
 .../Library/CpuCacheInfoLib/CpuCacheInfoLib.c |   5 +-
 .../CpuCacheInfoLib/DxeCpuCacheInfoLib.inf    |   2 -
 .../CpuCacheInfoLib/InternalCpuCacheInfoLib.h |   2 -
 .../CpuCacheInfoLib/PeiCpuCacheInfoLib.inf    |   2 -
 11 files changed, 185 insertions(+), 323 deletions(-)
 create mode 100644 MdePkg/Library/BaseLib/QuickSort.c

-- 
2.30.0.windows.1

[PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib

[IanX Kuo]

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

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

Add QuickSort function into BaseLib

Cc: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 MdePkg/Include/Library/BaseLib.h              |  49 ++++++++
 MdePkg/Library/BaseLib/BaseLib.inf            |   1 +
 MdePkg/Library/BaseLib/QuickSort.c            | 117 ++++++++++++++++++
 .../Library/BaseLib/UnitTestHostBaseLib.inf   |   3 +-
 4 files changed, 169 insertions(+), 1 deletion(-)
 create mode 100644 MdePkg/Library/BaseLib/QuickSort.c

diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
index 2452c1d92e..2423169be4 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
 
 #ifndef __BASE_LIB__
 #define __BASE_LIB__
+#include <Uefi/UefiBaseType.h>
 
 //
 // Definitions for architecture-specific types
@@ -2856,6 +2857,54 @@ 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 *BASE_SORT_COMPARE)(
+  IN CONST VOID                 *Buffer1,
+  IN CONST VOID                 *Buffer2
+  );
+
+/**
+  Worker function for QuickSorting.  This function is identical to perform QuickSort,
+  except that is uses the pre-allocated buffer so the in place sorting does not need to
+  allocate and free buffers constantly.
+
+  Each element must be equal sized.
+
+  if Count is < 2 then perform no action.
+  if Size is < 1 then perform no action.
+
+  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
+                                 on return a buffer of sorted elements
+  @param[in] Count               the number of elements in the buffer to sort
+  @param[in] ElementSize         Size of an element in bytes
+  @param[in] CompareFunction     The function to call to perform the comparison
+                                 of any 2 elements
+  @param [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
+                                 It's used by QuickSort() for swapping in sorting.
+
+  @retval EFI_SUCCESS            The quick sort is finished.
+  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL, CompareFunction is NULL or Buffer is NULL
+**/
+EFI_STATUS
+EFIAPI
+QuickSort (
+  IN OUT VOID                           *BufferToSort,
+  IN CONST UINTN                        Count,
+  IN CONST UINTN                        ElementSize,
+  IN       BASE_SORT_COMPARE            CompareFunction,
+  IN VOID                               *BufferOneElement
+  );
 
 /**
   Shifts a 64-bit integer left between 0 and 63 bits. The low bits are filled
diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/BaseLib.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/QuickSort.c
new file mode 100644
index 0000000000..f95af9e238
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,117 @@
+/** @file
+  Math worker functions.
+
+  Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
+  SPDX-License-Identifier: BSD-2-Clause-Patent
+
+**/
+
+#include "BaseLibInternals.h"
+#include <Uefi/UefiBaseType.h>
+
+/**
+  Worker function for QuickSorting.  This function is identical to perform QuickSort,
+  except that is uses the pre-allocated buffer so the in place sorting does not need to
+  allocate and free buffers constantly.
+
+  Each element must be equal sized.
+
+  if Count is < 2 then perform no action.
+  if Size is < 1 then perform no action.
+
+  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
+                                 on return a buffer of sorted elements
+  @param[in] Count               the number of elements in the buffer to sort
+  @param[in] ElementSize         Size of an element in bytes
+  @param[in] CompareFunction     The function to call to perform the comparison
+                                 of any 2 elements
+  @param [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
+                                 It's used by QuickSort() for swapping in sorting.
+
+  @retval EFI_SUCCESS            The quick sort is finished.
+  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL, CompareFunction is NULL, or BufferOneElement is NULL
+
+**/
+EFI_STATUS
+EFIAPI
+QuickSort (
+  IN OUT VOID                           *BufferToSort,
+  IN CONST UINTN                        Count,
+  IN CONST UINTN                        ElementSize,
+  IN       BASE_SORT_COMPARE            CompareFunction,
+  IN VOID                               *BufferOneElement
+  )
+{
+  VOID        *Pivot;
+  UINTN       LoopCount;
+  UINTN       NextSwapLocation;
+
+  if ((BufferToSort == NULL) || (CompareFunction == NULL) || (BufferOneElement == NULL)) {
+    return EFI_INVALID_PARAMETER;
+  }
+
+  if (Count < 2 || ElementSize  < 1) {
+    return EFI_SUCCESS;
+  }
+
+  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 (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
+      CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);
+      CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, 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), BufferOneElement, 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...
+  //
+  if (NextSwapLocation >= 2) {
+    QuickSort (
+      BufferToSort,
+      NextSwapLocation,
+      ElementSize,
+      CompareFunction,
+      BufferOneElement
+      );
+  }
+
+  if ((Count - NextSwapLocation - 1) >= 2) {
+    QuickSort (
+      (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
+      Count - NextSwapLocation - 1,
+      ElementSize,
+      CompareFunction,
+      BufferOneElement
+      );
+  }
+  return EFI_SUCCESS;
+}
diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Library/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.<BR>
+#  Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
 #  Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
 #  Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
 #  Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All rights reserved.<BR>
@@ -33,6 +33,7 @@
   SwapBytes16.c
   LongJump.c
   SetJump.c
+  QuickSort.c
   RShiftU64.c
   RRotU64.c
   RRotU32.c
-- 
2.30.0.windows.1

[PATCH v5 2/4] MdeModulePkg/SortLib: Add QuickSort function on BaseLib

[IanX Kuo]

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: Jian J Wang <jian.j.wang@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 .../Library/BaseSortLib/BaseSortLib.c         | 117 +----------------
 .../Library/UefiSortLib/UefiSortLib.c         | 118 +-----------------
 2 files changed, 10 insertions(+), 225 deletions(-)

diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..b33339ac7c 100644
--- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
+++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
@@ -1,7 +1,7 @@
 /** @file
   Library used for sorting routines.
 
-  Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>
+  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
 **/
@@ -13,114 +13,6 @@
 #include <Library/MemoryAllocationLib.h>
 #include <Library/SortLib.h>
 
-/**
-  Worker function for QuickSorting.  This function is identical to PerformQuickSort,
-  except that is uses the pre-allocated buffer so the in place sorting does 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 Buffer is NULL, then ASSERT.
-
-  if Count is < 2 then perform no action.
-  if Size is < 1 then perform no action.
-
-  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
-                                 on return a buffer of sorted elements
-  @param[in] Count               the number of elements in the buffer to sort
-  @param[in] ElementSize         Size of an element in bytes
-  @param[in] CompareFunction     The function to call to perform the comparison
-                                 of any 2 elements
-  @param[in] Buffer              Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-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 it's final position (NextSwapLocaiton)
-  //
-  CopyMem (Buffer, Pivot, ElementSize);
-  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
-  //
-  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
-  // IE list is sorted left half, pivot element, sorted right half...
-  //
-  if (NextSwapLocation >= 2) {
-    QuickSortWorker(
-      BufferToSort,
-      NextSwapLocation,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  if ((Count - NextSwapLocation - 1) >= 2) {
-    QuickSortWorker(
-      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
-      Count - NextSwapLocation - 1,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-  return;
-}
 /**
   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 
@@ -156,12 +48,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);
   ASSERT(Buffer != NULL);
 
-  QuickSortWorker(
+  QuickSort (
     BufferToSort,
     Count,
     ElementSize,
-    CompareFunction,
-    Buffer);
+    (SORT_COMPARE) CompareFunction,
+    Buffer
+    );
 
   FreePool(Buffer);
   return;
diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc443638..151a5a9ac3 100644
--- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
+++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
@@ -1,7 +1,7 @@
 /** @file
   Library used for sorting routines.
 
-  Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>
+  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
 **/
@@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;
   }                                   \
 }
 
-/**
-  Worker function for QuickSorting.  This function is identical to PerformQuickSort,
-  except that is uses the pre-allocated buffer so the in place sorting does 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 Buffer is NULL, then ASSERT.
-
-  if Count is < 2 then perform no action.
-  if Size is < 1 then perform no action.
-
-  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
-                                 on return a buffer of sorted elements
-  @param[in] Count               the number of elements in the buffer to sort
-  @param[in] ElementSize         Size of an element in bytes
-  @param[in] CompareFunction     The function to call to perform the comparison
-                                 of any 2 elements
-  @param[in] Buffer              Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-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 it's final position (NextSwapLocaiton)
-  //
-  CopyMem (Buffer, Pivot, ElementSize);
-  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
-  //
-  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
-  // IE list is sorted left half, pivot element, sorted right half...
-  //
-  if (NextSwapLocation >= 2) {
-    QuickSortWorker(
-      BufferToSort,
-      NextSwapLocation,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  if ((Count - NextSwapLocation - 1) >= 2) {
-    QuickSortWorker(
-      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
-      Count - NextSwapLocation - 1,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  return;
-}
 /**
   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 
@@ -173,12 +64,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);
   ASSERT(Buffer != NULL);
 
-  QuickSortWorker(
+  QuickSort (
     BufferToSort,
     Count,
     ElementSize,
-    CompareFunction,
-    Buffer);
+    (SORT_COMPARE) CompareFunction,
+    Buffer
+    );
 
   FreePool(Buffer);
   return;
-- 
2.30.0.windows.1

[PATCH v5 3/4] CryptoPkg/CryptLib: Add QuickSort function on BaseLib

[IanX Kuo]

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

[PATCH v5 4/4] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib

[IanX Kuo]

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

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

Remove MdeModulePkg dependency

Cc: Eric Dong <eric.dong@intel.com>
Cc: Ray Ni <ray.ni@intel.com>
Cc: Rahul Kumar <rahul1.kumar@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c         | 5 ++++-
 UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf    | 2 --
 UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 2 --
 UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf    | 2 --
 4 files changed, 4 insertions(+), 7 deletions(-)

diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
index c0077d6770..b5ed05bd43 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
@@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData (
   UINTN                     LocalCacheInfoCount;
   UINTN                     Index;
   UINTN                     NextIndex;
+  VOID                      *QuickSortBuffer;
 
   //
   // Get number of Packages and Package ID.
@@ -369,7 +370,9 @@ CpuCacheInfoCollectCpuCacheInfoData (
     //
     // Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type.
     //
-    PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
+    QuickSortBuffer = AllocateZeroPool (sizeof (*LocalCacheInfo));
+    ASSERT (QuickSortBuffer != NULL);
+    QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (BASE_SORT_COMPARE) CpuCacheInfoCompare, QuickSortBuffer);
     CopyMem (CacheInfo, LocalCacheInfo, sizeof (*CacheInfo) * LocalCacheInfoCount);
     DEBUG_CODE (
       CpuCacheInfoPrintCpuCacheInfoTable (CacheInfo, LocalCacheInfoCount);
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
index c3d3f1e799..fdd79970f9 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
@@ -25,7 +25,6 @@
 
 [Packages]
   MdePkg/MdePkg.dec
-  MdeModulePkg/MdeModulePkg.dec
   UefiCpuPkg/UefiCpuPkg.dec
 
 [LibraryClasses]
@@ -34,7 +33,6 @@
   BaseMemoryLib
   MemoryAllocationLib
   UefiBootServicesTableLib
-  SortLib
 
 [Protocols]
   gEfiMpServiceProtocolGuid
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
index 26e1f46516..af60588e34 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
@@ -13,11 +13,9 @@
 #include <Register/Cpuid.h>
 #include <Ppi/MpServices2.h>
 #include <Protocol/MpService.h>
-#include <Library/BaseLib.h>
 #include <Library/DebugLib.h>
 #include <Library/BaseMemoryLib.h>
 #include <Library/MemoryAllocationLib.h>
-#include <Library/SortLib.h>
 #include <Library/CpuCacheInfoLib.h>
 
 typedef union {
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
index 0864497849..c643fc89be 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
@@ -25,7 +25,6 @@
 
 [Packages]
   MdePkg/MdePkg.dec
-  MdeModulePkg/MdeModulePkg.dec
   UefiCpuPkg/UefiCpuPkg.dec
 
 [LibraryClasses]
@@ -34,7 +33,6 @@
   BaseMemoryLib
   MemoryAllocationLib
   PeiServicesTablePointerLib
-  SortLib
 
 [Ppis]
   gEdkiiPeiMpServices2PpiGuid
-- 
2.30.0.windows.1

Re: [edk2-devel] [PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib

[Marvin Häuser]

Good day IanX,

On 04/10/2021 07:03, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Add QuickSort function into BaseLib
>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
>   MdePkg/Include/Library/BaseLib.h              |  49 ++++++++
>   MdePkg/Library/BaseLib/BaseLib.inf            |   1 +
>   MdePkg/Library/BaseLib/QuickSort.c            | 117 ++++++++++++++++++
>   .../Library/BaseLib/UnitTestHostBaseLib.inf   |   3 +-
>   4 files changed, 169 insertions(+), 1 deletion(-)
>   create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
>
> diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
> index 2452c1d92e..2423169be4 100644
> --- a/MdePkg/Include/Library/BaseLib.h
> +++ b/MdePkg/Include/Library/BaseLib.h
> @@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
>   
>   #ifndef __BASE_LIB__
>   #define __BASE_LIB__
> +#include <Uefi/UefiBaseType.h>

Accidental change?

>   
>   //
>   // Definitions for architecture-specific types
> @@ -2856,6 +2857,54 @@ 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 *BASE_SORT_COMPARE)(
> +  IN CONST VOID                 *Buffer1,
> +  IN CONST VOID                 *Buffer2
> +  );
> +
> +/**
> +  Worker function for QuickSorting.

"Worker" functions are usually private.

> This function is identical to perform QuickSort,
> +  except that is uses the pre-allocated buffer so the in place sorting does not need to
> +  allocate and free buffers constantly.
> +
> +  Each element must be equal sized.
> +
> +  if Count is < 2 then perform no action.

This follows directly from the definition of sorting.

> +  if Size is < 1 then perform no action.

It would be perfectly valid to ASSERT on this in my opinion, so I would 
not hardcode the behaviour in the function spec.

> +
> +  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
> +                                 on return a buffer of sorted elements
> +  @param[in] Count               the number of elements in the buffer to sort
> +  @param[in] ElementSize         Size of an element in bytes
> +  @param[in] CompareFunction     The function to call to perform the comparison
> +                                 of any 2 elements
> +  @param [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
> +                                 It's used by QuickSort() for swapping in sorting.

This is out, not in. Maybe add a note its content is undefined on return?

> +
> +  @retval EFI_SUCCESS            The quick sort is finished.
> +  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL, CompareFunction is NULL or Buffer is NULL

These constraints are all caller constraints and not constraints on e.g. 
untrusted, external data. Hence, in my opinion it is perfectly valid to 
ASSERT them rather than runtime-check and emit status codes. This would 
mean the function could return VOID, there'd be no need to check status 
codes, and there'd be no need to worry about intermediate states (e.g. 
what is the content of BufferToSort when an error is returned?).

> +**/
> +EFI_STATUS
> +EFIAPI
> +QuickSort (
> +  IN OUT VOID                           *BufferToSort,
> +  IN CONST UINTN                        Count,
> +  IN CONST UINTN                        ElementSize,
> +  IN       BASE_SORT_COMPARE            CompareFunction,
> +  IN VOID                               *BufferOneElement

This is OUT, not IN.

> +  );
>   
>   /**
>     Shifts a 64-bit integer left between 0 and 63 bits. The low bits are filled
> diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/BaseLib.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/QuickSort.c
> new file mode 100644
> index 0000000000..f95af9e238
> --- /dev/null
> +++ b/MdePkg/Library/BaseLib/QuickSort.c
> @@ -0,0 +1,117 @@
> +/** @file
> +  Math worker functions.
> +
> +  Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
> +  SPDX-License-Identifier: BSD-2-Clause-Patent
> +
> +**/
> +
> +#include "BaseLibInternals.h"
> +#include <Uefi/UefiBaseType.h>

Is the second include not implied by the first?

> +
> +/**
> +  Worker function for QuickSorting.  This function is identical to perform QuickSort,
> +  except that is uses the pre-allocated buffer so the in place sorting does not need to
> +  allocate and free buffers constantly.
> +
> +  Each element must be equal sized.
> +
> +  if Count is < 2 then perform no action.
> +  if Size is < 1 then perform no action.
> +
> +  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
> +                                 on return a buffer of sorted elements
> +  @param[in] Count               the number of elements in the buffer to sort
> +  @param[in] ElementSize         Size of an element in bytes
> +  @param[in] CompareFunction     The function to call to perform the comparison
> +                                 of any 2 elements
> +  @param [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
> +                                 It's used by QuickSort() for swapping in sorting.
> +
> +  @retval EFI_SUCCESS            The quick sort is finished.
> +  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL, CompareFunction is NULL, or BufferOneElement is NULL
> +
> +**/
> +EFI_STATUS
> +EFIAPI
> +QuickSort (
> +  IN OUT VOID                           *BufferToSort,
> +  IN CONST UINTN                        Count,
> +  IN CONST UINTN                        ElementSize,
> +  IN       BASE_SORT_COMPARE            CompareFunction,
> +  IN VOID                               *BufferOneElement
> +  )
> +{
> +  VOID        *Pivot;
> +  UINTN       LoopCount;
> +  UINTN       NextSwapLocation;
> +
> +  if ((BufferToSort == NULL) || (CompareFunction == NULL) || (BufferOneElement == NULL)) {
> +    return EFI_INVALID_PARAMETER;
> +  }
> +
> +  if (Count < 2 || ElementSize  < 1) {
> +    return EFI_SUCCESS;
> +  }
> +
> +  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){

Comment mismatches logic, logic swaps on equality too.

Best regards,
Marvin

> +      //
> +      // swap
> +      //
> +      CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
> +      CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);
> +      CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, 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), BufferOneElement, 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...
> +  //
> +  if (NextSwapLocation >= 2) {
> +    QuickSort (
> +      BufferToSort,
> +      NextSwapLocation,
> +      ElementSize,
> +      CompareFunction,
> +      BufferOneElement
> +      );
> +  }
> +
> +  if ((Count - NextSwapLocation - 1) >= 2) {
> +    QuickSort (
> +      (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
> +      Count - NextSwapLocation - 1,
> +      ElementSize,
> +      CompareFunction,
> +      BufferOneElement
> +      );
> +  }
> +  return EFI_SUCCESS;
> +}
> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Library/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.<BR>
> +#  Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
>   #  Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
>   #  Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
>   #  Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All rights reserved.<BR>
> @@ -33,6 +33,7 @@
>     SwapBytes16.c
>     LongJump.c
>     SetJump.c
> +  QuickSort.c
>     RShiftU64.c
>     RRotU64.c
>     RRotU32.c

Re: [edk2-devel] [PATCH v5 4/4] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib

[Marvin Häuser]

Good day IanX,

On 04/10/2021 07:03, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Remove MdeModulePkg dependency
>
> Cc: Eric Dong <eric.dong@intel.com>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Rahul Kumar <rahul1.kumar@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
>   UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c         | 5 ++++-
>   UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf    | 2 --
>   UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 2 --
>   UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf    | 2 --
>   4 files changed, 4 insertions(+), 7 deletions(-)
>
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> index c0077d6770..b5ed05bd43 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> @@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData (
>     UINTN                     LocalCacheInfoCount;
>     UINTN                     Index;
>     UINTN                     NextIndex;
> +  VOID                      *QuickSortBuffer;
>   
>     //
>     // Get number of Packages and Package ID.
> @@ -369,7 +370,9 @@ CpuCacheInfoCollectCpuCacheInfoData (
>       //
>       // Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type.
>       //
> -    PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
> +    QuickSortBuffer = AllocateZeroPool (sizeof (*LocalCacheInfo));

CPU_CACHE_INFO is just a couple Bytes in size, maybe just allocate it on 
the stack?

> +    ASSERT (QuickSortBuffer != NULL);

Please handle memory allocation failures properly.

Best regards,
Marvin

> +    QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (BASE_SORT_COMPARE) CpuCacheInfoCompare, QuickSortBuffer);
>       CopyMem (CacheInfo, LocalCacheInfo, sizeof (*CacheInfo) * LocalCacheInfoCount);
>       DEBUG_CODE (
>         CpuCacheInfoPrintCpuCacheInfoTable (CacheInfo, LocalCacheInfoCount);
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> index c3d3f1e799..fdd79970f9 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> @@ -25,7 +25,6 @@
>   
>   [Packages]
>     MdePkg/MdePkg.dec
> -  MdeModulePkg/MdeModulePkg.dec
>     UefiCpuPkg/UefiCpuPkg.dec
>   
>   [LibraryClasses]
> @@ -34,7 +33,6 @@
>     BaseMemoryLib
>     MemoryAllocationLib
>     UefiBootServicesTableLib
> -  SortLib
>   
>   [Protocols]
>     gEfiMpServiceProtocolGuid
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> index 26e1f46516..af60588e34 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> @@ -13,11 +13,9 @@
>   #include <Register/Cpuid.h>
>   #include <Ppi/MpServices2.h>
>   #include <Protocol/MpService.h>
> -#include <Library/BaseLib.h>
>   #include <Library/DebugLib.h>
>   #include <Library/BaseMemoryLib.h>
>   #include <Library/MemoryAllocationLib.h>
> -#include <Library/SortLib.h>
>   #include <Library/CpuCacheInfoLib.h>
>   
>   typedef union {
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> index 0864497849..c643fc89be 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> @@ -25,7 +25,6 @@
>   
>   [Packages]
>     MdePkg/MdePkg.dec
> -  MdeModulePkg/MdeModulePkg.dec
>     UefiCpuPkg/UefiCpuPkg.dec
>   
>   [LibraryClasses]
> @@ -34,7 +33,6 @@
>     BaseMemoryLib
>     MemoryAllocationLib
>     PeiServicesTablePointerLib
> -  SortLib
>   
>   [Ppis]
>     gEdkiiPeiMpServices2PpiGuid

Re: [edk2-devel] [PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib

[IanX Kuo]

Hi Marvin

Reply in mail

Thanks,
Ian Kuo

-----Original Message-----
From: Marvin Häuser <mhaeuser@posteo.de> 
Sent: Monday, October 4, 2021 8:56 PM
To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney, Michael D <michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>; Liu, Zhiguang <zhiguang.liu@intel.com>
Subject: Re: [edk2-devel] [PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib

Good day IanX,

On 04/10/2021 07:03, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Add QuickSort function into BaseLib
>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
>   MdePkg/Include/Library/BaseLib.h              |  49 ++++++++
>   MdePkg/Library/BaseLib/BaseLib.inf            |   1 +
>   MdePkg/Library/BaseLib/QuickSort.c            | 117 ++++++++++++++++++
>   .../Library/BaseLib/UnitTestHostBaseLib.inf   |   3 +-
>   4 files changed, 169 insertions(+), 1 deletion(-)
>   create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
>
> diff --git a/MdePkg/Include/Library/BaseLib.h 
> b/MdePkg/Include/Library/BaseLib.h
> index 2452c1d92e..2423169be4 100644
> --- a/MdePkg/Include/Library/BaseLib.h
> +++ b/MdePkg/Include/Library/BaseLib.h
> @@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
>   
>   #ifndef __BASE_LIB__
>   #define __BASE_LIB__
> +#include <Uefi/UefiBaseType.h>

Accidental change?
Ian: No,  Without it, it won't find type "EFI_STATUS" and will cause build error. Origin return type is "VOID" on function "VOID QuickSortWorker". 
And my change "EFI_STATUS QuickSort", so "EFI_STATUS" depends on "UefiBaseType.h"


>   
>   //
>   // Definitions for architecture-specific types @@ -2856,6 +2857,54 
> @@ 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 *BASE_SORT_COMPARE)(
> +  IN CONST VOID                 *Buffer1,
> +  IN CONST VOID                 *Buffer2
> +  );
> +
> +/**
> +  Worker function for QuickSorting.

"Worker" functions are usually private.
Ian: Thank for reply, will remove "Worker" in my next patch.

> This function is identical to perform QuickSort,
> +  except that is uses the pre-allocated buffer so the in place 
> + sorting does not need to  allocate and free buffers constantly.
> +
> +  Each element must be equal sized.
> +
> +  if Count is < 2 then perform no action.

This follows directly from the definition of sorting.

> +  if Size is < 1 then perform no action.

It would be perfectly valid to ASSERT on this in my opinion, so I would not hardcode the behaviour in the function spec.

> +
> +  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
> +                                 on return a buffer of sorted elements
> +  @param[in] Count               the number of elements in the buffer to sort
> +  @param[in] ElementSize         Size of an element in bytes
> +  @param[in] CompareFunction     The function to call to perform the comparison
> +                                 of any 2 elements
> +  @param [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
> +                                 It's used by QuickSort() for swapping in sorting.

This is out, not in. Maybe add a note its content is undefined on return?
Ian: Got it, will change parameter type from "[in]" to "[out]" in my next patch.

> +
> +  @retval EFI_SUCCESS            The quick sort is finished.
> +  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL, 
> + CompareFunction is NULL or Buffer is NULL

These constraints are all caller constraints and not constraints on e.g. 
untrusted, external data. Hence, in my opinion it is perfectly valid to ASSERT them rather than runtime-check and emit status codes. This would mean the function could return VOID, there'd be no need to check status codes, and there'd be no need to worry about intermediate states (e.g. 
what is the content of BufferToSort when an error is returned?).
Ian: Got it, will change return type from "EFI_STATUS" to "VOID" in my next patch.

> +**/
> +EFI_STATUS
> +EFIAPI
> +QuickSort (
> +  IN OUT VOID                           *BufferToSort,
> +  IN CONST UINTN                        Count,
> +  IN CONST UINTN                        ElementSize,
> +  IN       BASE_SORT_COMPARE            CompareFunction,
> +  IN VOID                               *BufferOneElement

This is OUT, not IN.
Ian: Got it, will change it in my next patch.

> +  );
>   
>   /**
>     Shifts a 64-bit integer left between 0 and 63 bits. The low bits 
> are filled diff --git a/MdePkg/Library/BaseLib/BaseLib.inf 
> b/MdePkg/Library/BaseLib/BaseLib.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/QuickSort.c
> new file mode 100644
> index 0000000000..f95af9e238
> --- /dev/null
> +++ b/MdePkg/Library/BaseLib/QuickSort.c
> @@ -0,0 +1,117 @@
> +/** @file
> +  Math worker functions.
> +
> +  Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
> +  SPDX-License-Identifier: BSD-2-Clause-Patent
> +
> +**/
> +
> +#include "BaseLibInternals.h"
> +#include <Uefi/UefiBaseType.h>

Is the second include not implied by the first?
Ian: If we change QuickSort return type from "EFI_STATUS" to "VOID", the include can be removed.

> +
> +/**
> +  Worker function for QuickSorting.  This function is identical to 
> +perform QuickSort,
> +  except that is uses the pre-allocated buffer so the in place 
> +sorting does not need to
> +  allocate and free buffers constantly.
> +
> +  Each element must be equal sized.
> +
> +  if Count is < 2 then perform no action.
> +  if Size is < 1 then perform no action.
> +
> +  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
> +                                 on return a buffer of sorted elements
> +  @param[in] Count               the number of elements in the buffer to sort
> +  @param[in] ElementSize         Size of an element in bytes
> +  @param[in] CompareFunction     The function to call to perform the comparison
> +                                 of any 2 elements
> +  @param [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
> +                                 It's used by QuickSort() for swapping in sorting.
> +
> +  @retval EFI_SUCCESS            The quick sort is finished.
> +  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL, 
> + CompareFunction is NULL, or BufferOneElement is NULL
> +
> +**/
> +EFI_STATUS
> +EFIAPI
> +QuickSort (
> +  IN OUT VOID                           *BufferToSort,
> +  IN CONST UINTN                        Count,
> +  IN CONST UINTN                        ElementSize,
> +  IN       BASE_SORT_COMPARE            CompareFunction,
> +  IN VOID                               *BufferOneElement
> +  )
> +{
> +  VOID        *Pivot;
> +  UINTN       LoopCount;
> +  UINTN       NextSwapLocation;
> +
> +  if ((BufferToSort == NULL) || (CompareFunction == NULL) || (BufferOneElement == NULL)) {
> +    return EFI_INVALID_PARAMETER;
> +  }
> +
> +  if (Count < 2 || ElementSize  < 1) {
> +    return EFI_SUCCESS;
> +  }
> +
> +  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){

Comment mismatches logic, logic swaps on equality too.

Best regards,
Marvin

> +      //
> +      // swap
> +      //
> +      CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
> +      CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);
> +      CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), 
> + BufferOneElement, 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), BufferOneElement, 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...
> +  //
> +  if (NextSwapLocation >= 2) {
> +    QuickSort (
> +      BufferToSort,
> +      NextSwapLocation,
> +      ElementSize,
> +      CompareFunction,
> +      BufferOneElement
> +      );
> +  }
> +
> +  if ((Count - NextSwapLocation - 1) >= 2) {
> +    QuickSort (
> +      (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
> +      Count - NextSwapLocation - 1,
> +      ElementSize,
> +      CompareFunction,
> +      BufferOneElement
> +      );
> +  }
> +  return EFI_SUCCESS;
> +}
> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf 
> b/MdePkg/Library/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.<BR>
> +#  Copyright (c) 2007 - 2021, Intel Corporation. All rights 
> +reserved.<BR>
>   #  Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
>   #  Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
>   #  Copyright (c) 2020, Hewlett Packard Enterprise Development LP. 
> All rights reserved.<BR> @@ -33,6 +33,7 @@
>     SwapBytes16.c
>     LongJump.c
>     SetJump.c
> +  QuickSort.c
>     RShiftU64.c
>     RRotU64.c
>     RRotU32.c

Re: [edk2-devel] [PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib

[Marvin Häuser]

04.10.2021 17:23:47 Kuo, IanX <ianx.kuo@intel.com>:

> Hi Marvin
>
> Reply in mail
>
> Thanks,
> Ian Kuo
>
> -----Original Message-----
> From: Marvin Häuser <mhaeuser@posteo.de>
> Sent: Monday, October 4, 2021 8:56 PM
> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>
> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney, Michael D <michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>; Liu, Zhiguang <zhiguang.liu@intel.com>
> Subject: Re: [edk2-devel] [PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib
>
> Good day IanX,
>
> On 04/10/2021 07:03, IanX Kuo wrote:
>> From: IanX Kuo <ianx.kuo@intel.com>
>>
>> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>>
>> Add QuickSort function into BaseLib
>>
>> Cc: Ray Ni <ray.ni@intel.com>
>> Cc: Michael D Kinney <michael.d.kinney@intel.com>
>> Cc: Liming Gao <gaoliming@byosoft.com.cn>
>> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
>> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
>> ---
>>   MdePkg/Include/Library/BaseLib.h              |  49 ++++++++
>>   MdePkg/Library/BaseLib/BaseLib.inf            |   1 +
>>   MdePkg/Library/BaseLib/QuickSort.c            | 117 ++++++++++++++++++
>>   .../Library/BaseLib/UnitTestHostBaseLib.inf   |   3 +-
>>   4 files changed, 169 insertions(+), 1 deletion(-)
>>   create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
>>
>> diff --git a/MdePkg/Include/Library/BaseLib.h
>> b/MdePkg/Include/Library/BaseLib.h
>> index 2452c1d92e..2423169be4 100644
>> --- a/MdePkg/Include/Library/BaseLib.h
>> +++ b/MdePkg/Include/Library/BaseLib.h
>> @@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
>>  
>>   #ifndef __BASE_LIB__
>>   #define __BASE_LIB__
>> +#include <Uefi/UefiBaseType.h>
>
> Accidental change?
> Ian: No,  Without it, it won't find type "EFI_STATUS" and will cause build error. Origin return type is "VOID" on function "VOID QuickSortWorker".
> And my change "EFI_STATUS QuickSort", so "EFI_STATUS" depends on "UefiBaseType.h"

Riiight, I think that is why RETURN_STATUS was introduced. :)

Thanks for considering the rest!

Best regards,
Marvin

>
>
>>  
>>   //
>>   // Definitions for architecture-specific types @@ -2856,6 +2857,54
>> @@ 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 *BASE_SORT_COMPARE)(
>> +  IN CONST VOID                 *Buffer1,
>> +  IN CONST VOID                 *Buffer2
>> +  );
>> +
>> +/**
>> +  Worker function for QuickSorting.
>
> "Worker" functions are usually private.
> Ian: Thank for reply, will remove "Worker" in my next patch.
>
>> This function is identical to perform QuickSort,
>> +  except that is uses the pre-allocated buffer so the in place
>> + sorting does not need to  allocate and free buffers constantly.
>> +
>> +  Each element must be equal sized.
>> +
>> +  if Count is < 2 then perform no action.
>
> This follows directly from the definition of sorting.
>
>> +  if Size is < 1 then perform no action.
>
> It would be perfectly valid to ASSERT on this in my opinion, so I would not hardcode the behaviour in the function spec.
>
>> +
>> +  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
>> +                                 on return a buffer of sorted elements
>> +  @param[in] Count               the number of elements in the buffer to sort
>> +  @param[in] ElementSize         Size of an element in bytes
>> +  @param[in] CompareFunction     The function to call to perform the comparison
>> +                                 of any 2 elements
>> +  @param [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
>> +                                 It's used by QuickSort() for swapping in sorting.
>
> This is out, not in. Maybe add a note its content is undefined on return?
> Ian: Got it, will change parameter type from "[in]" to "[out]" in my next patch.
>
>> +
>> +  @retval EFI_SUCCESS            The quick sort is finished.
>> +  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL,
>> + CompareFunction is NULL or Buffer is NULL
>
> These constraints are all caller constraints and not constraints on e.g.
> untrusted, external data. Hence, in my opinion it is perfectly valid to ASSERT them rather than runtime-check and emit status codes. This would mean the function could return VOID, there'd be no need to check status codes, and there'd be no need to worry about intermediate states (e.g.
> what is the content of BufferToSort when an error is returned?).
> Ian: Got it, will change return type from "EFI_STATUS" to "VOID" in my next patch.
>
>> +**/
>> +EFI_STATUS
>> +EFIAPI
>> +QuickSort (
>> +  IN OUT VOID                           *BufferToSort,
>> +  IN CONST UINTN                        Count,
>> +  IN CONST UINTN                        ElementSize,
>> +  IN       BASE_SORT_COMPARE            CompareFunction,
>> +  IN VOID                               *BufferOneElement
>
> This is OUT, not IN.
> Ian: Got it, will change it in my next patch.
>
>> +  );
>>  
>>   /**
>>     Shifts a 64-bit integer left between 0 and 63 bits. The low bits
>> are filled diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
>> b/MdePkg/Library/BaseLib/BaseLib.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/QuickSort.c
>> new file mode 100644
>> index 0000000000..f95af9e238
>> --- /dev/null
>> +++ b/MdePkg/Library/BaseLib/QuickSort.c
>> @@ -0,0 +1,117 @@
>> +/** @file
>> +  Math worker functions.
>> +
>> +  Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
>> +  SPDX-License-Identifier: BSD-2-Clause-Patent
>> +
>> +**/
>> +
>> +#include "BaseLibInternals.h"
>> +#include <Uefi/UefiBaseType.h>
>
> Is the second include not implied by the first?
> Ian: If we change QuickSort return type from "EFI_STATUS" to "VOID", the include can be removed.
>
>> +
>> +/**
>> +  Worker function for QuickSorting.  This function is identical to
>> +perform QuickSort,
>> +  except that is uses the pre-allocated buffer so the in place
>> +sorting does not need to
>> +  allocate and free buffers constantly.
>> +
>> +  Each element must be equal sized.
>> +
>> +  if Count is < 2 then perform no action.
>> +  if Size is < 1 then perform no action.
>> +
>> +  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
>> +                                 on return a buffer of sorted elements
>> +  @param[in] Count               the number of elements in the buffer to sort
>> +  @param[in] ElementSize         Size of an element in bytes
>> +  @param[in] CompareFunction     The function to call to perform the comparison
>> +                                 of any 2 elements
>> +  @param [in] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
>> +                                 It's used by QuickSort() for swapping in sorting.
>> +
>> +  @retval EFI_SUCCESS            The quick sort is finished.
>> +  @retval EFI_INVALID_PARAMETER  When BufferToSort is NULL,
>> + CompareFunction is NULL, or BufferOneElement is NULL
>> +
>> +**/
>> +EFI_STATUS
>> +EFIAPI
>> +QuickSort (
>> +  IN OUT VOID                           *BufferToSort,
>> +  IN CONST UINTN                        Count,
>> +  IN CONST UINTN                        ElementSize,
>> +  IN       BASE_SORT_COMPARE            CompareFunction,
>> +  IN VOID                               *BufferOneElement
>> +  )
>> +{
>> +  VOID        *Pivot;
>> +  UINTN       LoopCount;
>> +  UINTN       NextSwapLocation;
>> +
>> +  if ((BufferToSort == NULL) || (CompareFunction == NULL) || (BufferOneElement == NULL)) {
>> +    return EFI_INVALID_PARAMETER;
>> +  }
>> +
>> +  if (Count < 2 || ElementSize  < 1) {
>> +    return EFI_SUCCESS;
>> +  }
>> +
>> +  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){
>
> Comment mismatches logic, logic swaps on equality too.
>
> Best regards,
> Marvin
>
>> +      //
>> +      // swap
>> +      //
>> +      CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
>> +      CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);
>> +      CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
>> + BufferOneElement, 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), BufferOneElement, 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...
>> +  //
>> +  if (NextSwapLocation >= 2) {
>> +    QuickSort (
>> +      BufferToSort,
>> +      NextSwapLocation,
>> +      ElementSize,
>> +      CompareFunction,
>> +      BufferOneElement
>> +      );
>> +  }
>> +
>> +  if ((Count - NextSwapLocation - 1) >= 2) {
>> +    QuickSort (
>> +      (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
>> +      Count - NextSwapLocation - 1,
>> +      ElementSize,
>> +      CompareFunction,
>> +      BufferOneElement
>> +      );
>> +  }
>> +  return EFI_SUCCESS;
>> +}
>> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
>> b/MdePkg/Library/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.<BR>
>> +#  Copyright (c) 2007 - 2021, Intel Corporation. All rights
>> +reserved.<BR>
>>   #  Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
>>   #  Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
>>   #  Copyright (c) 2020, Hewlett Packard Enterprise Development LP.
>> All rights reserved.<BR> @@ -33,6 +33,7 @@
>>     SwapBytes16.c
>>     LongJump.c
>>     SetJump.c
>> +  QuickSort.c
>>     RShiftU64.c
>>     RRotU64.c
>>     RRotU32.c