From patchwork Fri Sep 2 07:53:24 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Marc_Poulhi=C3=A8s?= X-Patchwork-Id: 919 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp611203wro; Fri, 2 Sep 2022 00:56:42 -0700 (PDT) X-Google-Smtp-Source: AA6agR7xkBEJYx7dEQ11PlhNhwD3V4EDCZJfBc69rarKZqEUpMffUx73eN6W5P//rfkFitwi8bBb X-Received: by 2002:a17:906:cc4a:b0:73d:d3b9:b263 with SMTP id mm10-20020a170906cc4a00b0073dd3b9b263mr24950442ejb.130.1662105402525; Fri, 02 Sep 2022 00:56:42 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1662105402; cv=none; d=google.com; s=arc-20160816; b=vJ4OwMTiFRyqK/WM83p6K14+PMTMQAyk6HM8fWcJmh4ZEQydZpyMeLEqtF4WaKLOHw WQW+ki0yGlk3H9hM6rV/888sSNyvsjnF2R1KReAd/F3Zn5VED8nGEDO1ve8ZXtEGOIdg WIKuEC29FAcDNrg4/wPJk2TgRgN1JwHwhvoIwwCeej1M30t/HjAN5Oyokj+6se3eeuJO qoXMHY5OdYy0/6+/Sybduv9vf/6BTz6YOgGZt1NziuW6krvDWFvjLDkH+GBr/ccjjGoL ZIlLJkgPk2OpLCuxINV5B3yusNCDNUlPBoCCE+9xQ105v6tduhFYLlnCvHjWp+M/ItjU acOQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :content-disposition:mime-version:message-id:subject:to:date :dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=83t4pscxReVrJzF8HIsRaPQs/Q4Y2Q6w6amuIyawGXA=; b=mI7nO2Ka+ON8WUqnfsfkDgeoIUEqVJHBGMOis7sjuaDAC7DXW5wPJ3zHOGp2jH+bh2 4gYt4z+D92gVNfcJB9jwXBuJ7hPIiWWSsy6Oc3aawbCvASWUFWRY7/moyOPlpeSID4Q4 iVHKcuEOut4KL13rk+aOlUYRrPeTz96FOCKLgUh35YRTexqIJrI0iWgvdc9v7MlOl0yk EPQcmuwo3SK90YIFh17FcMyxQSO+wYkzR2cgTxrsv7DmKr4MXg0ZNy2X8RdzpGVZtqmn CQpA3EQdX6Q3vzosAFm8hYCcCYK7jXJyLhbejAsi2dWGPx+LZb7Fy7pyMRPGO/8/zflK 3LCg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=pvWMjA9L; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id y4-20020a50e604000000b004478e283f05si1167871edm.104.2022.09.02.00.56.42 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 02 Sep 2022 00:56:42 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=pvWMjA9L; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2537F3857BAE for ; Fri, 2 Sep 2022 07:55:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2537F3857BAE DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1662105321; bh=83t4pscxReVrJzF8HIsRaPQs/Q4Y2Q6w6amuIyawGXA=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=pvWMjA9LpUhbAO/Vh2psZHXfHkRaSEWUAS7O9eAzouK74ZaPSN2TBFGulBUNwVdut OSbZX7lQbmFoN4Q0dg46bXyLdtF9qkFscz2BYvCoolYpGaS4SHmJhsC0oaiyTlIKgB 9rh5aW4lAhx/L2ebYuF7mVdypSRaPGq1omyywYq8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wr1-x432.google.com (mail-wr1-x432.google.com [IPv6:2a00:1450:4864:20::432]) by sourceware.org (Postfix) with ESMTPS id 607BA3858C00 for ; Fri, 2 Sep 2022 07:53:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 607BA3858C00 Received: by mail-wr1-x432.google.com with SMTP id k9so1281583wri.0 for ; Fri, 02 Sep 2022 00:53:27 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-disposition:mime-version:message-id:subject:cc:to:from:date :x-gm-message-state:from:to:cc:subject:date; bh=83t4pscxReVrJzF8HIsRaPQs/Q4Y2Q6w6amuIyawGXA=; b=R/6306WuAEOnezmigGXJJEkxTHbrxmvdbt+FhJPhZhQpgBzERh7zuH37QLvSvZjRLP O3RTSXIQuyDiQFCF9bUbHyJNmSUZsU5iB5TKHNyKp7IIz1PTnc1gBo4C2Dlsj0xCrv/D 9JYdLhDZCe04SI0hSGzDS8rxEu5q0J9mZvG7CcwJO8/SUMMEyR+MTH7PtazKq6SYiO7Y 4JYkH0ksX9h13nAChCmVLdSB1imfcZANOgcId5suFrtC9vK16VEDU6JyynEkkOM5LjCM WOb/+3TjeiNfj9PZpSXJN3y8SXAwD6rSvbVQtw8U59l1j7qcDyrjJcUFRKXlI4BW+ig0 ndqg== X-Gm-Message-State: ACgBeo2+R4yt/9S+IeiEkYPq/1uKMO+WA3uyMhvDqUk0NNtIJWOVYgPb fPbeGn68G10M3gjnUEju4CE9bOMmUrMFLQ== X-Received: by 2002:adf:f450:0:b0:226:eacb:2dc6 with SMTP id f16-20020adff450000000b00226eacb2dc6mr6809589wrp.231.1662105206270; Fri, 02 Sep 2022 00:53:26 -0700 (PDT) Received: from poulhies-Precision-5550 (static-176-191-105-132.ftth.abo.bbox.fr. [176.191.105.132]) by smtp.gmail.com with ESMTPSA id g11-20020a05600c310b00b003a5ea1cc63csm7958708wmo.39.2022.09.02.00.53.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 02 Sep 2022 00:53:25 -0700 (PDT) Date: Fri, 2 Sep 2022 09:53:24 +0200 To: gcc-patches@gcc.gnu.org Subject: [Ada] Fix proof of runtime unit System.Exp_Mod Message-ID: <20220902075324.GA1121046@poulhies-Precision-5550> MIME-Version: 1.0 Content-Disposition: inline X-Spam-Status: No, score=-11.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: =?utf-8?q?Marc_Poulhi=C3=A8s_via_Gcc-patches?= From: =?utf-8?q?Marc_Poulhi=C3=A8s?= Reply-To: Marc =?iso-8859-1?q?Poulhi=E8s?= Cc: Claire Dross Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1742843834507039506?= X-GMAIL-MSGID: =?utf-8?q?1742843834507039506?= Regain the proof of System.Exp_Mod after changes in provers and Why3. Tested on x86_64-pc-linux-gnu, committed on trunk gcc/ada/ * libgnat/s-expmod.adb (Lemma_Add_Mod): Add new lemma to factor out a complex sub-proof. (Exp_Modular): Add assertion to help proof. diff --git a/gcc/ada/libgnat/s-expmod.adb b/gcc/ada/libgnat/s-expmod.adb --- a/gcc/ada/libgnat/s-expmod.adb +++ b/gcc/ada/libgnat/s-expmod.adb @@ -106,6 +106,13 @@ is ------------------- procedure Lemma_Add_Mod (X, Y : Big_Natural; B : Big_Positive) is + + procedure Lemma_Euclidean_Mod (Q, F, R : Big_Natural) with + Pre => F /= 0, + Post => (Q * F + R) mod F = R mod F; + + procedure Lemma_Euclidean_Mod (Q, F, R : Big_Natural) is null; + Left : constant Big_Natural := (X + Y) mod B; Right : constant Big_Natural := ((X mod B) + (Y mod B)) mod B; XQuot : constant Big_Natural := X / B; @@ -119,6 +126,8 @@ is (Left = ((XQuot + YQuot) * B + X mod B + Y mod B) mod B); pragma Assert (X mod B + Y mod B = AQuot * B + Right); pragma Assert (Left = ((XQuot + YQuot + AQuot) * B + Right) mod B); + Lemma_Euclidean_Mod (XQuot + YQuot + AQuot, B, Right); + pragma Assert (Left = (Right mod B)); pragma Assert (Left = Right); end if; end Lemma_Add_Mod; @@ -259,6 +268,7 @@ is pragma Assert (Equal_Modulo ((Big (Result) * Big (Factor)) * Big (Factor) ** (Exp - 1), Big (Left) ** Right)); + pragma Assert (Big (Factor) >= 0); Lemma_Mult_Mod (Big (Result) * Big (Factor), Big (Factor) ** (Exp - 1), Big (Modulus));