From patchwork Tue Sep 17 08:06:34 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pierre-Marie de Rodat X-Patchwork-Id: 1163218 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-509085-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=adacore.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="ny2X5ODH"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 46XbPj4Mxbz9sN1 for ; Tue, 17 Sep 2019 18:10:01 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; q=dns; s=default; b=eJmcspKH90SeD5OkcKCn5zULGUVmgaVhd+hUBajN+dC3npznEl gzEfqStIDI3VXQnplU+zJ+/ySXIpPPosK02NJvw8402yHwvjmb9H1YdROmUovEkr pmb+9wFEw9PLI0vXG6v9ZXxCVznb02YuuoM4YxeR4ohgGGb/AcEoo8+oY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:mime-version:content-type; s= default; bh=wGOEXVLQyGdXFdDf6fuEddHVSew=; b=ny2X5ODH0uIjUr0f5MDe J9zXVudFS9cYkBWGGESpbjfCq+lW2TT/wp26vcB5OFeNSedFM0iXWo/WZq5kWANv 5KXOVMb1bTJBwPsgHKcAKvhKKXZyqWC5I2NoUA5RD8YgxBwiKhS+PHlyW1+kkvJ7 cHMpTE2VHBAJvbEkJG8VeMI= Received: (qmail 32112 invoked by alias); 17 Sep 2019 08:06:56 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 30849 invoked by uid 89); 17 Sep 2019 08:06:44 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-11.9 required=5.0 tests=BAYES_00, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.1 spammy=uno, explaining, quantities, Edition X-HELO: rock.gnat.com Received: from rock.gnat.com (HELO rock.gnat.com) (205.232.38.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 17 Sep 2019 08:06:43 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 1A415117C32; Tue, 17 Sep 2019 04:06:37 -0400 (EDT) Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 6c39Wt0+yNon; Tue, 17 Sep 2019 04:06:37 -0400 (EDT) Received: from tron.gnat.com (tron.gnat.com [IPv6:2620:20:4000:0:46a8:42ff:fe0e:e294]) by rock.gnat.com (Postfix) with ESMTP id 29E9F117C34; Tue, 17 Sep 2019 04:06:34 -0400 (EDT) Received: by tron.gnat.com (Postfix, from userid 4862) id 28EFD6AD; Tue, 17 Sep 2019 04:06:34 -0400 (EDT) Date: Tue, 17 Sep 2019 04:06:34 -0400 From: Pierre-Marie de Rodat To: gcc-patches@gcc.gnu.org Cc: Yannick Moy Subject: [Ada] Minor fixes mostly in comments of runtime arithmetic unit Message-ID: <20190917080634.GA37620@adacore.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) X-IsSubscribed: yes Multiple comments in functions Double_Divide and Scaled_Divide were incorrect. Now fixed. Also change the expression (if Zhi /= 0 then Ylo * Zhi else 0) to the simpler equivalent (Ylo * Zhi) in Double_Divide. Also add a comment explaining why the implementation of Algorithm D for multiple-precision division from the 2nd Edition of The Art of Computer Programming does not suffer from two bugs discovered on that version. There is no impact on execution, hence no test. Tested on x86_64-pc-linux-gnu, committed on trunk 2019-09-17 Yannick Moy gcc/ada/ * libgnat/s-arit64.adb (Double_Divide): Simplify needlessly complex computation. Fix comments. (Scaled_Divide): Fix comments. Explain why implementation does not suffer from bugs in Algorithm D from 2nd Edition of TAOCP. --- gcc/ada/libgnat/s-arit64.adb +++ gcc/ada/libgnat/s-arit64.adb @@ -161,7 +161,7 @@ package body System.Arith_64 is end if; else - T2 := (if Zhi /= 0 then Ylo * Zhi else 0); + T2 := Ylo * Zhi; end if; T1 := Ylo * Zlo; @@ -179,7 +179,7 @@ package body System.Arith_64 is Den_Pos := (Y < 0) = (Z < 0); - -- Check overflow case of largest negative number divided by 1 + -- Check overflow case of largest negative number divided by -1 if X = Int64'First and then Du = 1 and then not Den_Pos then Raise_Error; @@ -404,15 +404,16 @@ package body System.Arith_64 is Ru := T2 rem Zlo; end if; - -- If divisor is double digit and too large, raise error + -- If divisor is double digit and dividend is too large, raise error elsif (D (1) & D (2)) >= Zu then Raise_Error; -- This is the complex case where we definitely have a double digit -- divisor and a dividend of at least three digits. We use the classical - -- multiple division algorithm (see section (4.3.1) of Knuth's "The Art - -- of Computer Programming", Vol. 2 for a description (algorithm D). + -- multiple-precision division algorithm (see section (4.3.1) of Knuth's + -- "The Art of Computer Programming", Vol. 2 for a description + -- (algorithm D). else -- First normalize the divisor so that it has the leading bit on. @@ -450,7 +451,7 @@ package body System.Arith_64 is -- Note that when we scale up the dividend, it still fits in four -- digits, since we already tested for overflow, and scaling does - -- not change the invariant that (D (1) & D (2)) >= Zu. + -- not change the invariant that (D (1) & D (2)) < Zu. T1 := Shift_Left (D (1) & D (2), Scale); D (1) := Hi (T1); @@ -485,6 +486,19 @@ package body System.Arith_64 is -- Adjust quotient digit if it was too high + -- We use the version of the algorithm in the 2nd Edition of + -- "The Art of Computer Programming". This had a bug not + -- discovered till 1995, see Vol 2 errata: + -- http://www-cs-faculty.stanford.edu/~uno/err2-2e.ps.gz. + -- Under rare circumstances the expression in the test could + -- overflow. This version was further corrected in 2005, see + -- Vol 2 errata: + -- http://www-cs-faculty.stanford.edu/~uno/all2-pre.ps.gz. + -- This implementation is not impacted by these bugs, due to the + -- use of a word-size comparison done in function Le3 instead of + -- a comparison on two-word integer quantities in the original + -- algorithm. + loop exit when Le3 (S1, S2, S3, D (J + 1), D (J + 2), D (J + 3)); Qd (J + 1) := Qd (J + 1) - 1;