From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: mx.groups.io; dkim=pass header.i=@armh.onmicrosoft.com header.s=selector2-armh-onmicrosoft-com header.b=ZIPHqpAb; spf=pass (domain: arm.com, ip: 40.107.4.66, mailfrom: krzysztof.koch@arm.com) Received: from EUR03-DB5-obe.outbound.protection.outlook.com (EUR03-DB5-obe.outbound.protection.outlook.com [40.107.4.66]) by groups.io with SMTP; Thu, 16 May 2019 03:11:48 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=q1tN9zSaKkmzm4q3r870q7dH0HnGoM34y6jR2zRQJuY=; b=ZIPHqpAb9fHKAJrdjV0mu4/fIFSOcv0lMDGDARWZ0TWNrayMTVq+qlyFH5DcyMw2/Lc4QkjJWbdYXt4O4zKxS4RbPlFwYkGVGqGIFnu5i1DhOX+uVb15VK+bKZLx0NPjzb7l7f485K4b394STbP1mCshQCvBVGupn4sVMSwUHa8= Received: from VI1PR0802CA0039.eurprd08.prod.outlook.com (2603:10a6:800:a9::25) by VI1PR08MB3982.eurprd08.prod.outlook.com (2603:10a6:803:e0::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1900.16; Thu, 16 May 2019 10:11:43 +0000 Received: from DB5EUR03FT048.eop-EUR03.prod.protection.outlook.com (2a01:111:f400:7e0a::206) by VI1PR0802CA0039.outlook.office365.com (2603:10a6:800:a9::25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id 15.20.1900.16 via Frontend Transport; Thu, 16 May 2019 10:11:43 +0000 Authentication-Results: spf=temperror (sender IP is 40.67.248.234) smtp.mailfrom=arm.com; edk2.groups.io; dkim=none (message not signed) header.d=none;edk2.groups.io; dmarc=temperror action=none header.from=arm.com; Received-SPF: TempError (protection.outlook.com: error in processing during lookup of arm.com: DNS Timeout) Received: from nebula.arm.com (40.67.248.234) by DB5EUR03FT048.mail.protection.outlook.com (10.152.21.28) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256) id 15.20.1856.11 via Frontend Transport; Thu, 16 May 2019 10:11:42 +0000 Received: from AZ-NEU-EX01.Emea.Arm.com (10.251.26.4) by AZ-NEU-EX03.Arm.com (10.251.24.31) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256) id 15.1.1415.2; Thu, 16 May 2019 10:11:41 +0000 Received: from AZ-NEU-EX03.Arm.com (10.251.24.31) by AZ-NEU-EX01.Emea.Arm.com (10.251.26.4) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1415.2; Thu, 16 May 2019 10:11:40 +0000 Received: from E119924.Arm.com (10.1.37.21) by mail.arm.com (10.251.24.31) with Microsoft SMTP Server id 15.1.1415.2 via Frontend Transport; Thu, 16 May 2019 10:11:39 +0000 From: "Krzysztof Koch" To: CC: , , , , , Subject: [PATCH v1 1/3] DynamicTablesPkg: Add code for finding duplicate values in arrays Date: Thu, 16 May 2019 11:11:31 +0100 Message-ID: <20190516101133.34912-2-krzysztof.koch@arm.com> X-Mailer: git-send-email 2.16.2.windows.1 In-Reply-To: <20190516101133.34912-1-krzysztof.koch@arm.com> References: <20190516101133.34912-1-krzysztof.koch@arm.com> Return-Path: Krzysztof.Koch@arm.com MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-Office365-Filtering-HT: Tenant X-Forefront-Antispam-Report: CIP:40.67.248.234;IPV:NLI;CTRY:US;EFV:NLI;SFV:NSPM;SFS:(10009020)(979002)(346002)(136003)(39860400002)(396003)(376002)(2980300002)(189003)(199004)(53936002)(2906002)(336012)(316002)(54906003)(50226002)(5660300002)(72206003)(478600001)(86362001)(2351001)(8936002)(446003)(8676002)(81156014)(81166006)(77096007)(476003)(48376002)(2616005)(36756003)(11346002)(63370400001)(68736007)(63350400001)(305945005)(70206006)(426003)(1076003)(53416004)(26005)(76176011)(186003)(486006)(6916009)(51416003)(47776003)(7696005)(70586007)(16586007)(44832011)(6666004)(50466002)(356004)(126002)(4326008)(969003)(989001)(999001)(1009001)(1019001);DIR:OUT;SFP:1101;SCL:1;SRVR:VI1PR08MB3982;H:nebula.arm.com;FPR:;SPF:TempError;LANG:en;PTR:InfoDomainNonexistent;MX:1;A:1; X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 813c7e7a-68a0-476c-00ed-08d6d9e6e4a2 X-Microsoft-Antispam: BCL:0;PCL:0;RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600141)(711020)(4605104)(2017052603328);SRVR:VI1PR08MB3982; X-MS-TrafficTypeDiagnostic: VI1PR08MB3982: NoDisclaimer: True X-Microsoft-Antispam-PRVS: X-MS-Oob-TLC-OOBClassifiers: OLM:9508; X-Forefront-PRVS: 0039C6E5C5 X-MS-Exchange-SenderADCheck: 1 X-Microsoft-Antispam-Message-Info: RLhQWuQ3xdA59nTbHnZmm0EJjgnNpORAcaTx6Lws+WWiaUKCLBKMnAO/8kxZeSLVqVlVZJiWsqZUOsLG4ZE6TUJx+aXdTTVN2SO7sCYgoIEuO6fsy8kHmxmau+O/1HMNZxLSo/NJPW+A2FV9yLT2AaNiHmfxOT2e4dG7C3CQ59bp2UdrtO6IF030gPd/HiflyWXU7WrvXydgo26pQUjjKVtFNKqvfhSr6zVcOgklB6nnxf4wK9P7QdeYWeTb8yS8KwozlVWOI8VrKHS68P0F9J+S1TWnpgp2pJdckNZ7ZEHnUqc9pHpDIJdJXJkTCvxcEbaYVOwaxPC/qO30M/jpOhdMs50VKxONkPMCw8CFuQZXlbo+8pXie50ZPUZ6B6mp3m+HtY5a8HRVpvo3rPN7IQr0L+E8LtGrtwBbE6IcYSE= X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 May 2019 10:11:42.0911 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 813c7e7a-68a0-476c-00ed-08d6d9e6e4a2 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d;Ip=[40.67.248.234];Helo=[nebula.arm.com] X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR08MB3982 Content-Type: text/plain Added generic function for detecting duplicate values in an array. Also defined a function prototype to test if two objects are equal. The prototype is used as an argument to the 'FindDuplicateValues' function. Signed-off-by: Krzysztof Koch --- Notes: v1: - Add generic code for duplicate detection [Krzysztof] DynamicTablesPkg/Include/Library/TableHelperLib.h | 48 +++++++++++++++ DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c | 64 ++++++++++++++++++++ 2 files changed, 112 insertions(+) diff --git a/DynamicTablesPkg/Include/Library/TableHelperLib.h b/DynamicTablesPkg/Include/Library/TableHelperLib.h index 9c5b3835413f8768ef81ababa932c9f9be7ced82..e4a8dfa046bd97d89f0297ccad521f317bed5c36 100644 --- a/DynamicTablesPkg/Include/Library/TableHelperLib.h +++ b/DynamicTablesPkg/Include/Library/TableHelperLib.h @@ -4,6 +4,9 @@ SPDX-License-Identifier: BSD-2-Clause-Patent + @par Glossary: + - PFN - Pointer to a Function + **/ #ifndef TABLE_HELPER_LIB_H_ @@ -59,4 +62,49 @@ AddAcpiHeader ( IN CONST UINT32 Length ); +/** + Function prototype for testing if two arbitrary objects are equal. + + @param [in] Object1 Pointer to the first object to compare. + @param [in] Object2 Pointer to the second object to compare. + @param [in] Index1 Index of Object1. This value is optional and + can be ignored by the specified implementation. + @param [in] Index2 Index of Object2. This value is optional and + can be ignored by the specified implementation. + + @retval TRUE Object1 and Object2 are equal. + @retval FALSE Object1 and Object2 are NOT equal. +**/ +typedef +BOOLEAN +(EFIAPI *PFN_IS_EQUAL)( + IN CONST VOID * Object1, + IN CONST VOID * Object2, + IN UINTN Index1 OPTIONAL, + IN UINTN Index2 OPTIONAL + ); + +/** + Test and report if a duplicate entry exists in the given array of comparable + elements. + + @param [in] Array Array of elements to test for duplicates. + @param [in] Count Number of elements in Array. + @param [in] ElementSize Size of an element in bytes + @param [in] EqualTestFunction The function to call to check if any two + elements are equal. + + @retval TRUE A duplicate element was found or one of + the input arguments is invalid. + @retval FALSE Every element in Array is unique. +**/ +BOOLEAN +EFIAPI +FindDuplicateValue ( + IN CONST VOID * Array, + IN CONST UINTN Count, + IN CONST UINTN ElementSize, + IN PFN_IS_EQUAL EqualTestFunction + ); + #endif // TABLE_HELPER_LIB_H_ diff --git a/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c b/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c index 3938302b6d770c5bed2bc6c55a51c96ea8316dff..fc6cf3b088da1f7ad89dd4356b414bede9e80575 100644 --- a/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c +++ b/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c @@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent // Module specific include files. #include #include +#include #include /** The GetCgfMgrInfo function gets the CM_STD_OBJ_CONFIGURATION_MANAGER_INFO @@ -180,3 +181,66 @@ AddAcpiHeader ( error_handler: return Status; } + +/** + Test and report if a duplicate entry exists in the given array of comparable + elements. + + @param [in] Array Array of elements to test for duplicates. + @param [in] Count Number of elements in Array. + @param [in] ElementSize Size of an element in bytes + @param [in] EqualTestFunction The function to call to check if any two + elements are equal. + + @retval TRUE A duplicate element was found or one of + the input arguments is invalid. + @retval FALSE Every element in Array is unique. +**/ +BOOLEAN +EFIAPI +FindDuplicateValue ( + IN CONST VOID * Array, + IN CONST UINTN Count, + IN CONST UINTN ElementSize, + IN PFN_IS_EQUAL EqualTestFunction + ) +{ + UINTN Index1; + UINTN Index2; + UINT8 * Element1; + UINT8 * Element2; + + if (Array == NULL) { + DEBUG ((DEBUG_ERROR, "ERROR: FindDuplicateValues: Array is NULL.\n")); + return TRUE; + } + + if (ElementSize == 0) { + DEBUG ((DEBUG_ERROR, "ERROR: FindDuplicateValues: ElementSize is 0.\n")); + return TRUE; + } + + if (EqualTestFunction == NULL) { + DEBUG (( + DEBUG_ERROR, + "ERROR: FindDuplicateValues: EqualTestFunction is NULL.\n" + )); + return TRUE; + } + + if (Count < 2) { + return FALSE; + } + + for (Index1 = 0; Index1 < Count - 1; Index1++) { + for (Index2 = Index1 + 1; Index2 < Count; Index2++) { + Element1 = (UINT8*)Array + (Index1 * ElementSize); + Element2 = (UINT8*)Array + (Index2 * ElementSize); + + if (EqualTestFunction (Element1, Element2, Index1, Index2)) { + return TRUE; + } + } + } + return FALSE; +} -- 'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'