From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mout02.posteo.de (mout02.posteo.de [185.67.36.66]) by mx.groups.io with SMTP id smtpd.web11.8897.1633352196593395592 for ; Mon, 04 Oct 2021 05:56:37 -0700 Authentication-Results: mx.groups.io; dkim=pass header.i=@posteo.de header.s=2017 header.b=e3rSvaRd; spf=pass (domain: posteo.de, ip: 185.67.36.66, mailfrom: mhaeuser@posteo.de) Received: from submission (posteo.de [89.146.220.130]) by mout02.posteo.de (Postfix) with ESMTPS id D89A7240105 for ; Mon, 4 Oct 2021 14:56:32 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017; t=1633352192; bh=H6PsckKezKeZJOqcuwFxeRQo1AxiKzBL7vgfRRdZ8TE=; h=Date:Subject:To:Cc:From:From; b=e3rSvaRdh68M73TWqp0eD5mLomTDrt/RCJ1VDSn/3MGAkgZ5ZdThaV7gh2keCe5jf taZVs0bI9HyHSRvDrkKg+dM3PSWUTEErbpHEipc6kQlP0+Z9F7cGZzXOiso6gzpADf HdfFPbkxTwgwok5oNEXcojws/5t3HSdQ512Exik80qGBdyTTs2cwIEZIGY/jt7ffQ5 R3NGu8RoAQIsgaA8XInlLwJ+sxfTstug/ZxKEa7fdNby81bp0yVmqdWux0EQwbY+a3 zm8hAkq9EwuomhSUTvo8J/xKckDbQPWvU4hsM1wHFBAh5PE8s0YB5ubnEkn658TUjb Mhp9+YNSqBH9w== Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4HNLM22WBFz9rxY; Mon, 4 Oct 2021 14:56:30 +0200 (CEST) Message-ID: <2b5a17e9-8894-fa95-15d1-a00d8732ff1e@posteo.de> Date: Mon, 4 Oct 2021 12:56:29 +0000 MIME-Version: 1.0 Subject: Re: [edk2-devel] [PATCH v5 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib To: devel@edk2.groups.io, ianx.kuo@intel.com Cc: amy.chan@intel.com, ray.ni@intel.com, Michael D Kinney , Liming Gao , Zhiguang Liu References: <20211004050318.1816-1-ianx.kuo@intel.com> <20211004050318.1816-2-ianx.kuo@intel.com> From: =?UTF-8?B?TWFydmluIEjDpHVzZXI=?= In-Reply-To: <20211004050318.1816-2-ianx.kuo@intel.com> Content-Language: en-GB Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Good day IanX, On 04/10/2021 07:03, IanX Kuo wrote: > From: IanX Kuo > > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 > > Add QuickSort function into BaseLib > > Cc: Ray Ni > Cc: Michael D Kinney > Cc: Liming Gao > Cc: Zhiguang Liu > Signed-off-by: IanX Kuo > --- > 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 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.
> + SPDX-License-Identifier: BSD-2-Clause-Patent > + > +**/ > + > +#include "BaseLibInternals.h" > +#include 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.
> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.
> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.
> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.
> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All rights reserved.
> @@ -33,6 +33,7 @@ > SwapBytes16.c > LongJump.c > SetJump.c > + QuickSort.c > RShiftU64.c > RRotU64.c > RRotU32.c