From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from NAM10-DM6-obe.outbound.protection.outlook.com (mail-dm6nam10on2075.outbound.protection.outlook.com [40.107.93.75]) by sourceware.org (Postfix) with ESMTPS id 98DDC3858C53 for ; Fri, 6 May 2022 15:42:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 98DDC3858C53 ARC-Seal: i=2; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=fail; b=M7I/ihbwnfxPIZhes+DFXeOCe/I/Yhcue7RM5FGHJlo7btCwlsHUqFtUwMVxYJWzpGiUZYA1HtjMsrRzsI93xzomA0n8a26grWG/hPTH0w6cDVX/qfmbA6OpbdikxQA6CWuVPNmpICxog6UwlYHuN7N6Aj8PHCBXDYHlbp/QHoRMlnYSXvMjcdu7XJ9guAkWAcjPtzt7Pri47+Nb0JzVOwTcbSphvqZwbOQDanqOkpyPqghI9EvgAiD7fWjekuQbxit6xKI+uy7ov4h4ZYvwKHcNYC0wJfgoCFrfn4EA/rsb3gyxZGtZ4UWuJcr6MMN2QWbIeFBGhMCl062xUntvBA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=yupyFr/EuuClQeMr6NCrpTP5lryA1vxyG1QPBT9LTwo=; b=Z9ZFsscL/Gy9AXs/2f0Hi5+SssWU8/tE602VU1kwxA/x19ge8dmgIhkNvYy5egVhGVuQhxTJlj1AoJY16XRb1YMdV2W58HOkbNXpJL7xldiGrAEM7GRY2xlQzgxIsqyzO+JMjLK+XkGQkW0rmP/m45UD5mqzHoRo90mKLONc7T1g3OL0vupnfLxf+9pqkHVWYes9iEs9KhsQHS2IsfhL2f7EJ71HiVtze2gN4RynmYUmaa10JCWvQ1J36OlmkCb44KHh08VatJC7RdO4dQoQBdEXWONj6oeGsUtUuzcPIQ3o9Y+QtUh3IpqQGC2UjLUSYxzT6EtRrEWgo8lmyr3I1g== ARC-Authentication-Results: i=2; mx.microsoft.com 1; spf=pass (sender ip is 20.83.241.18) smtp.rcpttodomain=gcc.gnu.org smtp.mailfrom=amd.com; dmarc=pass (p=quarantine sp=quarantine pct=100) action=none header.from=amd.com; dkim=none (message not signed); arc=fail (48) Received: from MW4PR03CA0247.namprd03.prod.outlook.com (2603:10b6:303:b4::12) by MW5PR12MB5683.namprd12.prod.outlook.com (2603:10b6:303:1a0::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5186.20; Fri, 6 May 2022 15:42:18 +0000 Received: from CO1NAM11FT059.eop-nam11.prod.protection.outlook.com (2603:10b6:303:b4:cafe::dc) by MW4PR03CA0247.outlook.office365.com (2603:10b6:303:b4::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5206.24 via Frontend Transport; Fri, 6 May 2022 15:42:18 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 20.83.241.18) smtp.mailfrom=amd.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=amd.com; Received-SPF: Pass (protection.outlook.com: domain of amd.com designates 20.83.241.18 as permitted sender) receiver=protection.outlook.com; client-ip=20.83.241.18; helo=mailrelay000000.14r1f435wfvunndds3vy4cdalc.xx.internal.cloudapp.net; Received: from mailrelay000000.14r1f435wfvunndds3vy4cdalc.xx.internal.cloudapp.net (20.83.241.18) by CO1NAM11FT059.mail.protection.outlook.com (10.13.174.160) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5227.15 via Frontend Transport; Fri, 6 May 2022 15:42:18 +0000 Received: from NAM10-MW2-obe.outbound.protection.outlook.com (mail-mw2nam10lp2106.outbound.protection.outlook.com [104.47.55.106]) by mailrelay000000.14r1f435wfvunndds3vy4cdalc.xx.internal.cloudapp.net (Postfix) with ESMTPS id 5FFAA3F030; Fri, 6 May 2022 15:42:18 +0000 (UTC) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=EiaqonXjqijvnHdjObo3foAvprDeOh/fJ27iSF7LB1vivxfOSrRHrHAOcqnKhpUpNMZ/NvHXgeuJTxto4JHqEFI7ZcnuDE/bC9sI93Lx36sbad4y8JWSmvp5PnYkXEJA8G77m2AAybmtI6+FCMQulWOWTLMWDo26AoclIcre5LKRuMtotO5LnYHHo04PF7s8gAamPn8GL3WOkHmX81+l27q8ytNQioe2dyfdaYftFD2rrSP1GEmATn0snAtWgAFW5laoUFUDQeRND/BJmdqdRZxREtwRFWOb+4NimqaJKLeSIK3KV3w32T3ljys66BRmswv4IT2cXabAM/l0OpxlaA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=yupyFr/EuuClQeMr6NCrpTP5lryA1vxyG1QPBT9LTwo=; b=Wslui1cy5a37y8ogAFg7qYbfTyHstqeDHT/b9UWSumt3i9vls9oD1em3OIILC8BOnqQQIGScH8QG00F9t8eDjjgZYE1ntt5yseyNuIrQhSUIFee+EPEVqedwjkQflPshiuZATtSxU+xFgqlZBKp601viQ1fH+SZTAkp7lx0mxGEmAP38N7Lrg1sX4CamxmHWyhC+LkvijOzqpNNlHnkzkAowtkuJ5wpSbArufHMvLo5XXvNt7QCkfidWd+ypJwgfWiDk4j6vXxltmvPraDALSlfd5BdXR6NOjAF185JJ58zvr6CBySL+O45hf2X8p022dfxpPIxwsQoxPVkczfCpmw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=xilinx.com; dmarc=pass action=none header.from=xilinx.com; dkim=pass header.d=xilinx.com; arc=none Received: from SA1PR02MB8573.namprd02.prod.outlook.com (2603:10b6:806:1f9::6) by BL3PR02MB8002.namprd02.prod.outlook.com (2603:10b6:208:359::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5227.18; Fri, 6 May 2022 15:42:16 +0000 Received: from SA1PR02MB8573.namprd02.prod.outlook.com ([fe80::c49e:581f:82a7:793e]) by SA1PR02MB8573.namprd02.prod.outlook.com ([fe80::c49e:581f:82a7:793e%5]) with mapi id 15.20.5206.025; Fri, 6 May 2022 15:42:16 +0000 From: Matthias Gehre To: Jakub Jelinek CC: "gcc@gcc.gnu.org" Subject: =?iso-8859-1?Q?AW:_[RFC]_Adding_division/modulo_on_arbitrary_precision=A0?= =?iso-8859-1?Q?integers=A0to=A0libgcc?= Thread-Topic: =?iso-8859-1?Q?[RFC]_Adding_division/modulo_on_arbitrary_precision=A0inte?= =?iso-8859-1?Q?gers=A0to=A0libgcc?= Thread-Index: AQHYYU4a9FkoAhn8nEqcH9kllQqdeK0R7dqAgAAKMQI= Date: Fri, 6 May 2022 15:42:16 +0000 Message-ID: References: In-Reply-To: Accept-Language: de-DE, en-US Content-Language: de-DE X-MS-Has-Attach: X-MS-TNEF-Correlator: msip_labels: X-MS-Office365-Filtering-Correlation-Id: 639d2fbb-346d-4b1a-33f1-08da2f7700b9 x-ms-traffictypediagnostic: BL3PR02MB8002:EE_|CO1NAM11FT059:EE_|MW5PR12MB5683:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: bdoYlGKIO0uEU/MQi5wORZUisSxq8KafgAz0ieHoLH+7apvnOehAdr3siDSrm43cFIAi/TmSKBHYPpoXmmdadb0xUx57sUF4PLKrLui54in0yvPQez9HUhZG9HZ2vgHFsx9NAz6ef4/BBsdCzJLskDH/9p0Q09v1cIhvB1qFKDlM/qU96BxmGsyJeSGEwkiFf4hnICTSvpggNI9dkHK5xzTaO1zdp+PAzIn1ThyM9ODPBDqFTQn+HvgmsRQrkioUk96XuAT4iJsPS/w0sJDSYDIPf4REyOJkN5Jk3S1s6EnLOKAUNMHcjoyAq2D7lozCR7+KGbBt0xEUjNTFpgRtAIfrN0dwYTRLJK7XYksw/tRXz0gLSwptmmujLNxiRw8iF/9+L3bxVc/TsRugg+HnwKnnxH3DvEx4Pc1Y1/+OWx/xTY/al5kMagKI+UzOjekpvwZ7KH8Ci7TIbP2IEK8im7PikQgOKPc61TGjfsCQVYJiXy+DvGK9ay3GzFhndXdolK38ix6QmE4JNJbQbYXwcDS/N2Hut34nGRGT7B5JqXrYpizxQUP1Jo5jn2sH2k6k8JHSosMBttUGhlIMCzbl55EJo49XBDQ0Lr+yVncAu3nhfehIYSvMoSQ2qss42GNLQn037huf7sn547mLl5Ks5gFj1u9ctOy+lKqhL+dqRz+4qTG2maLrnE0oMLFo5QA9XI53TIuY4afSaNbmp5zgTw== X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:SA1PR02MB8573.namprd02.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(26005)(86362001)(71200400001)(9686003)(186003)(2906002)(33656002)(66946007)(66556008)(66476007)(66446008)(64756008)(76116006)(91956017)(4326008)(6916009)(122000001)(6506007)(83380400001)(508600001)(8936002)(7696005)(38100700002)(55016003)(38070700005)(316002)(52536014)(5660300002); DIR:OUT; SFP:1101; Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL3PR02MB8002 X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: CO1NAM11FT059.eop-nam11.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: 7b3f7b7b-27f6-442c-47c8-08da2f76ffb2 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 0XuVFMv/rpLHuvLRKdN7/lgefTKmZUy50wblUP0KJpKTR2Ox+V6e3w+sSWr/LtGWKPpV0wuB3idi9Rhy90UBpBlODIhR5h7a6g7xg2X6rTXZtqYRope192XcHvsJ2WcJkhgR4bH/EEUKBhON2Qst413+xNvnoDmaN7Heorh4WZiZ/4bYRm75+JY302A+xKgoH6fnZZRKs1SmUu2SncVb5K1aLIrzpvYHcsB6B7eH7YaGJq0dVnOB2cXLUHLqm1grmarEHmUxgwgptedT40T53nnSV9vfqy+Z9fs3sutMXLU1ZdrZGMc+lMOsuDuboXFQkqnmjtYJoYwIwwMMgPWPEnTxb1ONsQLK63tzzyF8Uj1j13EhgheqvExkKjB/54YE0tnLDqSRPr1pYOK7hrX+LkBeKlfCGeap2PLfPt5adV9o7blFTtQfh/LPJHH0RIERSQRMlgsORGF5C8UyE/AHc5dWtjdU0eAIV79I+kQxjcnmBtNln6vOl3VPMLt5jEgJAs1F3ngaT8T7OpZ0fADFdqkblfD3jbqPmzVjd0wQVyxEp2bLSyYtb9MzW1MWdMGDFgwvF8vGOZc5taVDOX7Si25U0prsHk1DtvYwJ4n8VVrZiD/PaC55TOuF+6Vp2jqJ/Tm0mg+9/gjskIdssXPZoCfs3zFWCYWDbKDK+GGkx8ATscjOs8D3HgJXmdaJRCm9Dm04Nry96SeQa40ZP2E0jg== X-Forefront-Antispam-Report: CIP:20.83.241.18; CTRY:US; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:mailrelay000000.14r1f435wfvunndds3vy4cdalc.xx.internal.cloudapp.net; PTR:InfoDomainNonexistent; CAT:NONE; SFS:(13230001)(4636009)(46966006)(40470700004)(36840700001)(40460700003)(8936002)(186003)(55016003)(2906002)(7696005)(52536014)(9686003)(36860700001)(33656002)(356005)(44832011)(86362001)(81166007)(6506007)(6916009)(508600001)(82310400005)(5660300002)(70206006)(83380400001)(47076005)(336012)(316002)(26005)(4326008)(36900700001); DIR:OUT; SFP:1101; X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 May 2022 15:42:18.5941 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 639d2fbb-346d-4b1a-33f1-08da2f7700b9 X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=3dd8961f-e488-4e60-8e11-a82d994e183d; Ip=[20.83.241.18]; Helo=[mailrelay000000.14r1f435wfvunndds3vy4cdalc.xx.internal.cloudapp.net] X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: TreatMessagesAsInternal-CO1NAM11FT059.eop-nam11.prod.protection.outlook.com X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW5PR12MB5683 X-Spam-Status: No, score=-0.6 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 06 May 2022 15:42:24 -0000 On Fri, May 06, 2022 at 02:09:21PM +0000, Matthias Gehre via Gcc wrote:=0A= > /// \param quo The quotient represented by n words. Must be non-null.=0A= > /// \param rem The remainder represented by n words. Must be non-null.=0A= > /// \param a The dividend represented by n + 1 words. Must be non-null.= =0A= > /// \param b The divisor represented by n words. Must be non-null.=0A= >=0A= > /// \note The word order is in host endianness.=0A= > /// \note Might modify a and b.=0A= > /// \note The storage of 'a' needs to hold n + 1 elements because some=0A= > ///=A0=A0=A0=A0=A0=A0 implementations need extra scratch space in the mos= t significant word.=0A= > ///=A0=A0=A0=A0=A0=A0 The value of that word is ignored.=0A= > void __udivmodei5(uint32_t *quo, uint32_t *rem, uint32_t *a,=0A= >=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 uint32_t *b, unsigned n);=0A= >=0A= > /// Computes the signed division of a / b.=0A= > /// See __udivmodei5 for details.=0A= > void __divmodei5(uint32_t *quo, uint32_t *rem, uint32_t *a, uint32_t *b,= =0A= >=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0 unsigned n);=0A= =0A= > Sizes certainly should be with size_t, not unsigned type.=0A= Agreed=0A= =0A= > Rather than uint32_t, wouldn't using the word size (64-bit for lp64, 32-b= it=0A= for ilp32) be better?=0A= Is there a portable way to specify this in C? (size_t, uintptr_t?) And is t= he word size=0A= clearly defined for each target? (I'm not a backend expert).=0A= =0A= > And I really don't like the N + 1 stuff you're proposing, at least for=0A= > _BigInts that would be represented as an array of those word etc. element= s=0A= > from least to most significant (or vice versa?=A0 That really needs to be= =0A= > specified too), if they are same precision having to copy one of them jus= t=0A= > to get the extra scratch is bad.=0A= Yes, that's a trade-off. Knuth algorithm is generally a good choice, but = =0A= not having the extra scratch space would introduce more branches into it.= =0A= Also, the proposed __udivmodei5 is allowed to overwrite the inputs, so you = might=0A= need to copy them anyways.=0A= =0A= I actually didn't have this N + 1 initially, but then I got a comment on th= e=0A= compiler-rt review, and added it subsequently. Personally, I don't mind eit= her=0A= way.=