From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mout01.posteo.de (mout01.posteo.de [185.67.36.65])
 by mx.groups.io with SMTP id smtpd.web12.11198.1633361621482024492
 for <devel@edk2.groups.io>;
 Mon, 04 Oct 2021 08:33:42 -0700
Authentication-Results: mx.groups.io;
 dkim=pass header.i=@posteo.de header.s=2017 header.b=L5UTlaID;
 spf=pass (domain: posteo.de, ip: 185.67.36.65, mailfrom: mhaeuser@posteo.de)
Received: from submission (posteo.de [89.146.220.130]) 
	by mout01.posteo.de (Postfix) with ESMTPS id 05CAD240026
	for <devel@edk2.groups.io>; Mon,  4 Oct 2021 17:33:38 +0200 (CEST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017;
	t=1633361619; bh=b4MxxQ/wQ/lfe/qda39oEiNmlA5Pb5uahaWie4m6fWM=;
	h=Date:From:To:Cc:Subject:From;
	b=L5UTlaID0KN5uC29dO7uOv2j32UYDo8dL7l8EP9kujkYX/bFBf3RN7GoTwN0LeFqn
	 a0GQYJ/87Xwg2Nl5jmcu88E246BseTC1EMfLKkpvWHtpGw3hkvwiyH4jGY/lLmuhCm
	 jyEad0hFAZtdFOwxFUlP3l5RGSsx2dOZGrlHqnlngjeaDKerIdKwH9QnZNJ7Lhlv4f
	 rkSG7r7XxLkAP7BqVJDkelLLhg27urea1Bwvf+OW4/jdsDZ3xPH9eOFcYpTSdFNQeN
	 5LQb7ktVkhfIUKI3jkrMUrdK4opy7usDa60AEDkA6VzGzDECS83P1tKKlom+XfkJlv
	 mlGFVpamVOPTQ==
Received: from customer (localhost [127.0.0.1])
	by submission (posteo.de) with ESMTPSA id 4HNPrJ5jNVz9rxj;
	Mon,  4 Oct 2021 17:33:36 +0200 (CEST)
Date: Mon, 4 Oct 2021 15:33:35 +0000 (UTC)
From: =?UTF-8?B?TWFydmluIEjDpHVzZXI=?= <mhaeuser@posteo.de>
To: "Kuo, IanX" <ianx.kuo@intel.com>
Cc: devel@edk2.groups.io, "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>
Message-ID: <19e50a32-21ad-433e-8cb9-0d27981f3a83@posteo.de>
In-Reply-To: <PH0PR11MB5174E630C97928CBA659C82A8EAE9@PH0PR11MB5174.namprd11.prod.outlook.com>
References: <20211004050318.1816-1-ianx.kuo@intel.com> <20211004050318.1816-2-ianx.kuo@intel.com> <2b5a17e9-8894-fa95-15d1-a00d8732ff1e@posteo.de> <PH0PR11MB5174E630C97928CBA659C82A8EAE9@PH0PR11MB5174.namprd11.prod.outlook.com>
Subject: Re: [edk2-devel] [PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib
MIME-Version: 1.0
X-Correlation-ID: <19e50a32-21ad-433e-8cb9-0d27981f3a83@posteo.de>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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=C3=A4user <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, M=
ichael 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 fu=
nction 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=3D3675
>>
>> 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>
>> ---
>> =C2=A0 MdePkg/Include/Library/BaseLib.h=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 |=C2=A0 49 ++++++++
>> =C2=A0 MdePkg/Library/BaseLib/BaseLib.inf=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 |=C2=A0=C2=A0 1 +
>> =C2=A0 MdePkg/Library/BaseLib/QuickSort.c=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 | 117 ++++++++++++++++++
>> =C2=A0 .../Library/BaseLib/UnitTestHostBaseLib.inf=C2=A0=C2=A0 |=C2=A0=
=C2=A0 3 +-
>> =C2=A0 4 files changed, 169 insertions(+), 1 deletion(-)
>> =C2=A0 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
>> =C2=A0
>> =C2=A0 #ifndef __BASE_LIB__
>> =C2=A0 #define __BASE_LIB__
>> +#include <Uefi/UefiBaseType.h>
>
> Accidental change?
> Ian: No,=C2=A0 Without it, it won't find type "EFI_STATUS" and will cause=
 build error. Origin return type is "VOID" on function "VOID QuickSortWorke=
r".
> And my change "EFI_STATUS QuickSort", so "EFI_STATUS" depends on "UefiBas=
eType.h"

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

Thanks for considering the rest!

Best regards,
Marvin

>
>
>> =C2=A0
>> =C2=A0 //
>> =C2=A0 // Definitions for architecture-specific types @@ -2856,6 +2857,5=
4
>> @@ RemoveEntryList (
>> =C2=A0 //
>> =C2=A0 // Math Services
>> =C2=A0 //
>> +/**
>> +=C2=A0 Prototype for comparison function for any two element types.
>> +
>> +=C2=A0 @param[in] Buffer1=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 The pointer to fi=
rst buffer.
>> +=C2=A0 @param[in] Buffer2=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 The pointer to se=
cond buffer.
>> +
>> +=C2=A0 @retval 0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0 Buffer1 equal to Buffer2.
>> +=C2=A0 @return <0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 Buffer1 is less than Buffer2.
>> +=C2=A0 @return >0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 Buffer1 is greater than Buffer2.
>> +**/
>> +typedef
>> +INTN
>> +(EFIAPI *BASE_SORT_COMPARE)(
>> +=C2=A0 IN CONST VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 *Buffer1,
>> +=C2=A0 IN CONST VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 *Buffer2
>> +=C2=A0 );
>> +
>> +/**
>> +=C2=A0 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,
>> +=C2=A0 except that is uses the pre-allocated buffer so the in place
>> + sorting does not need to=C2=A0 allocate and free buffers constantly.
>> +
>> +=C2=A0 Each element must be equal sized.
>> +
>> +=C2=A0 if Count is < 2 then perform no action.
>
> This follows directly from the definition of sorting.
>
>> +=C2=A0 if Size is < 1 then perform no action.
>
> It would be perfectly valid to ASSERT on this in my opinion, so I would n=
ot hardcode the behaviour in the function spec.
>
>> +
>> +=C2=A0 @param[in, out] BufferToSort=C2=A0=C2=A0 on call a Buffer of (po=
ssibly sorted) elements
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 on return a buffer of sort=
ed elements
>> +=C2=A0 @param[in] Count=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 the number of elements in the buffer t=
o sort
>> +=C2=A0 @param[in] ElementSize=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0 Size of an element in bytes
>> +=C2=A0 @param[in] CompareFunction=C2=A0=C2=A0=C2=A0=C2=A0 The function =
to call to perform the comparison
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 of any 2 elements
>> +=C2=A0 @param [in] BufferOneElement=C2=A0=C2=A0 Caller provided buffer =
whose size equals to ElementSize.
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 It's used by QuickSort() f=
or 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.
>
>> +
>> +=C2=A0 @retval EFI_SUCCESS=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 The quick sort is finished.
>> +=C2=A0 @retval EFI_INVALID_PARAMETER=C2=A0 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 A=
SSERT 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 ne=
xt patch.
>
>> +**/
>> +EFI_STATUS
>> +EFIAPI
>> +QuickSort (
>> +=C2=A0 IN OUT VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 *BufferToSort,
>> +=C2=A0 IN CONST UINTN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 Count,
>> +=C2=A0 IN CONST UINTN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 ElementSize,
>> +=C2=A0 IN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BASE_SORT_COMPARE=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 CompareFunctio=
n,
>> +=C2=A0 IN VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 *BufferOneElement
>
> This is OUT, not IN.
> Ian: Got it, will change it in my next patch.
>
>> +=C2=A0 );
>> =C2=A0
>> =C2=A0 /**
>> =C2=A0=C2=A0=C2=A0 Shifts a 64-bit integer left between 0 and 63 bits. T=
he 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 @@
>> =C2=A0=C2=A0=C2=A0 SwapBytes16.c
>> =C2=A0=C2=A0=C2=A0 LongJump.c
>> =C2=A0=C2=A0=C2=A0 SetJump.c
>> +=C2=A0 QuickSort.c
>> =C2=A0=C2=A0=C2=A0 RShiftU64.c
>> =C2=A0=C2=A0=C2=A0 RRotU64.c
>> =C2=A0=C2=A0=C2=A0 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
>> +=C2=A0 Math worker functions.
>> +
>> +=C2=A0 Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
>> +=C2=A0 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.
>
>> +
>> +/**
>> +=C2=A0 Worker function for QuickSorting.=C2=A0 This function is identic=
al to
>> +perform QuickSort,
>> +=C2=A0 except that is uses the pre-allocated buffer so the in place
>> +sorting does not need to
>> +=C2=A0 allocate and free buffers constantly.
>> +
>> +=C2=A0 Each element must be equal sized.
>> +
>> +=C2=A0 if Count is < 2 then perform no action.
>> +=C2=A0 if Size is < 1 then perform no action.
>> +
>> +=C2=A0 @param[in, out] BufferToSort=C2=A0=C2=A0 on call a Buffer of (po=
ssibly sorted) elements
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 on return a buffer of sort=
ed elements
>> +=C2=A0 @param[in] Count=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 the number of elements in the buffer t=
o sort
>> +=C2=A0 @param[in] ElementSize=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0 Size of an element in bytes
>> +=C2=A0 @param[in] CompareFunction=C2=A0=C2=A0=C2=A0=C2=A0 The function =
to call to perform the comparison
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 of any 2 elements
>> +=C2=A0 @param [in] BufferOneElement=C2=A0=C2=A0 Caller provided buffer =
whose size equals to ElementSize.
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 It's used by QuickSort() f=
or swapping in sorting.
>> +
>> +=C2=A0 @retval EFI_SUCCESS=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 The quick sort is finished.
>> +=C2=A0 @retval EFI_INVALID_PARAMETER=C2=A0 When BufferToSort is NULL,
>> + CompareFunction is NULL, or BufferOneElement is NULL
>> +
>> +**/
>> +EFI_STATUS
>> +EFIAPI
>> +QuickSort (
>> +=C2=A0 IN OUT VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 *BufferToSort,
>> +=C2=A0 IN CONST UINTN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 Count,
>> +=C2=A0 IN CONST UINTN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 ElementSize,
>> +=C2=A0 IN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BASE_SORT_COMPARE=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 CompareFunctio=
n,
>> +=C2=A0 IN VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 *BufferOneElement
>> +=C2=A0 )
>> +{
>> +=C2=A0 VOID=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 *Pivot;
>> +=C2=A0 UINTN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 LoopCount;
>> +=C2=A0 UINTN=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 NextSwapLocation;
>> +
>> +=C2=A0 if ((BufferToSort =3D=3D NULL) || (CompareFunction =3D=3D NULL) =
|| (BufferOneElement =3D=3D NULL)) {
>> +=C2=A0=C2=A0=C2=A0 return EFI_INVALID_PARAMETER;
>> +=C2=A0 }
>> +
>> +=C2=A0 if (Count < 2 || ElementSize=C2=A0 < 1) {
>> +=C2=A0=C2=A0=C2=A0 return EFI_SUCCESS;
>> +=C2=A0 }
>> +
>> +=C2=A0 NextSwapLocation =3D 0;
>> +
>> +=C2=A0 //
>> +=C2=A0 // pick a pivot (we choose last element)=C2=A0 //=C2=A0 Pivot =
=3D ((UINT8*)
>> + BufferToSort + ((Count - 1) * ElementSize));
>> +
>> +=C2=A0 //
>> +=C2=A0 // Now get the pivot such that all on "left" are below it=C2=A0 =
// and
>> + everything "right" are above it=C2=A0 //=C2=A0 for (LoopCount =3D 0; L=
oopCount <
>> + Count -1; LoopCount++) {
>> +=C2=A0=C2=A0=C2=A0 //
>> +=C2=A0=C2=A0=C2=A0 // if the element is less than the pivot
>> +=C2=A0=C2=A0=C2=A0 //
>> +=C2=A0=C2=A0=C2=A0 if (CompareFunction ((VOID*) ((UINT8*) BufferToSort =
+
>> + ((LoopCount) * ElementSize)), Pivot) <=3D 0){
>
> Comment mismatches logic, logic swaps on equality too.
>
> Best regards,
> Marvin
>
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 //
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 // swap
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 //
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 CopyMem (BufferOneElement, (UINT8*) Buff=
erToSort + (NextSwapLocation * ElementSize), ElementSize);
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 CopyMem ((UINT8*) BufferToSort + (NextSw=
apLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSi=
ze), ElementSize);
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 CopyMem ((UINT8*) BufferToSort + ((LoopC=
ount)*ElementSize),
>> + BufferOneElement, ElementSize);
>> +
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 //
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 // increment NextSwapLocation
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 //
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 NextSwapLocation++;
>> +=C2=A0=C2=A0=C2=A0 }
>> +=C2=A0 }
>> +=C2=A0 //
>> +=C2=A0 // swap pivot to it's final position (NextSwapLocation)=C2=A0 //=
=C2=A0
>> + CopyMem (BufferOneElement, Pivot, ElementSize);=C2=A0 CopyMem (Pivot,
>> + (UINT8*) BufferToSort + (NextSwapLocation * ElementSize),
>> + ElementSize);=C2=A0 CopyMem ((UINT8*) BufferToSort + (NextSwapLocation=
 *
>> + ElementSize), BufferOneElement, ElementSize);
>> +
>> +=C2=A0 //
>> +=C2=A0 // Now recurse on 2 partial lists.=C2=A0 neither of these will h=
ave the
>> + 'pivot' element=C2=A0 // IE list is sorted left half, pivot element, s=
orted right half...
>> +=C2=A0 //
>> +=C2=A0 if (NextSwapLocation >=3D 2) {
>> +=C2=A0=C2=A0=C2=A0 QuickSort (
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BufferToSort,
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 NextSwapLocation,
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ElementSize,
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 CompareFunction,
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BufferOneElement
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 );
>> +=C2=A0 }
>> +
>> +=C2=A0 if ((Count - NextSwapLocation - 1) >=3D 2) {
>> +=C2=A0=C2=A0=C2=A0 QuickSort (
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 (UINT8 *)BufferToSort + (NextSwapLocatio=
n + 1) * ElementSize,
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Count - NextSwapLocation - 1,
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ElementSize,
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 CompareFunction,
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BufferOneElement
>> +=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 );
>> +=C2=A0 }
>> +=C2=A0 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 @@
>> =C2=A0 ## @file
>> =C2=A0 #=C2=A0 Base Library implementation for use with host based unit =
tests.
>> =C2=A0 #
>> -#=C2=A0 Copyright (c) 2007 - 2020, Intel Corporation. All rights
>> reserved.<BR>
>> +#=C2=A0 Copyright (c) 2007 - 2021, Intel Corporation. All rights
>> +reserved.<BR>
>> =C2=A0 #=C2=A0 Portions copyright (c) 2008 - 2009, Apple Inc. All rights=
 reserved.<BR>
>> =C2=A0 #=C2=A0 Portions copyright (c) 2011 - 2013, ARM Ltd. All rights r=
eserved.<BR>
>> =C2=A0 #=C2=A0 Copyright (c) 2020, Hewlett Packard Enterprise Developmen=
t LP.
>> All rights reserved.<BR> @@ -33,6 +33,7 @@
>> =C2=A0=C2=A0=C2=A0 SwapBytes16.c
>> =C2=A0=C2=A0=C2=A0 LongJump.c
>> =C2=A0=C2=A0=C2=A0 SetJump.c
>> +=C2=A0 QuickSort.c
>> =C2=A0=C2=A0=C2=A0 RShiftU64.c
>> =C2=A0=C2=A0=C2=A0 RRotU64.c
>> =C2=A0=C2=A0=C2=A0 RRotU32.c