From patchwork Wed Dec 5 10:51:11 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Arnaud Charlet X-Patchwork-Id: 203841 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 4A8E82C00C2 for ; Wed, 5 Dec 2012 21:51:27 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1355309487; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Date:From:To:Cc:Subject:Message-ID: MIME-Version:Content-Type:Content-Disposition:User-Agent: Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:Sender:Delivered-To; bh=MTk88lBbYMEiWEY+bbBy 7YdDJIs=; b=hPAkaiJ/aDx3bYKjKQJNJwdG2SY+iWp66ArkMGidoX8XuOOdGJJT qze/dMeBSF2aYvvOCRBdmCFP9Gq1NMSGK/OrMdOxQq++2RQemn+ExDrIaQY8VnK/ LHE9pelaoyugQp54EIOyQpjMeEgyTTQeeveWkWF5sHZY/eWuQ52KSOQ= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Received:Date:From:To:Cc:Subject:Message-ID:MIME-Version:Content-Type:Content-Disposition:User-Agent:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=Ed4CdxYtNVSSC1oYKyAfVPr2Hii45byPfrut2MoTFcaj/DaZJbIFopzUc5azYU khP5B6Dgztnu9kRR8itWg4SiwMP9/poN8GIaVU5r7mGCZ+mj1I/X5HALmuxHanF8 yGp3kLhXNtwHdRhL9SHyaB1z7r5py3BIT1disAA8HIvjc=; Received: (qmail 5326 invoked by alias); 5 Dec 2012 10:51:22 -0000 Received: (qmail 5314 invoked by uid 22791); 5 Dec 2012 10:51:19 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL, BAYES_00, RCVD_IN_HOSTKARMA_NO X-Spam-Check-By: sourceware.org Received: from rock.gnat.com (HELO rock.gnat.com) (205.232.38.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 05 Dec 2012 10:51:12 +0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id BF9362E0E6; Wed, 5 Dec 2012 05:51:11 -0500 (EST) 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 Jjc4x9uBlJHY; Wed, 5 Dec 2012 05:51:11 -0500 (EST) Received: from kwai.gnat.com (kwai.gnat.com [205.232.38.4]) by rock.gnat.com (Postfix) with ESMTP id A4C622E2C8; Wed, 5 Dec 2012 05:51:11 -0500 (EST) Received: by kwai.gnat.com (Postfix, from userid 4192) id A3750919E3; Wed, 5 Dec 2012 05:51:11 -0500 (EST) Date: Wed, 5 Dec 2012 05:51:11 -0500 From: Arnaud Charlet To: gcc-patches@gcc.gnu.org Cc: Yannick Moy Subject: [Ada] Correct multi-precision division algorithm used for universal integers Message-ID: <20121205105111.GA12333@adacore.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) 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 The version of multi-precision division algorithm used was based on Algorithm D published in 2nd edition of Donald Knuth's "The Art of Computer Programming". This algorithm was corrected twice, in 1995 and 2005, to protect against a possible overflow. Although this problem may not be present in this code, due to the value of Base used with respect to the underlying machine integers, it is preferable to use the corrected version of the algorithm. Tested on x86_64-pc-linux-gnu, committed on trunk 2012-12-05 Yannick Moy * uintp.adb (UI_Div_Rem): Correct algorithm D to remove potential overflow. Index: uintp.adb =================================================================== --- uintp.adb (revision 194188) +++ uintp.adb (working copy) @@ -1165,6 +1165,7 @@ Divisor_Dig1 : Int; Divisor_Dig2 : Int; Q_Guess : Int; + R_Guess : Int; begin -- [ NORMALIZE ] (step D1 in the algorithm). First calculate the @@ -1218,30 +1219,26 @@ -- Note: this version of step D3 is from the original published -- algorithm, which is known to have a bug causing overflows. - -- See: http://www-cs-faculty.stanford.edu/~uno/err2-2e.ps.gz. - -- In this code we are safe since our representation of double - -- length numbers allows an expanded range. + -- See: http://www-cs-faculty.stanford.edu/~uno/err2-2e.ps.gz + -- and http://www-cs-faculty.stanford.edu/~uno/all2-pre.ps.gz. + -- The code below is the fixed version of this step. - -- We don't have a proof of this claim, but the only cases we - -- have found that show the bug in step D3 work fine here. - Tmp_Int := Dividend (J) * Base + Dividend (J + 1); -- Initial guess - if Dividend (J) = Divisor_Dig1 then - Q_Guess := Base - 1; - else - Q_Guess := Tmp_Int / Divisor_Dig1; - end if; + Q_Guess := Tmp_Int / Divisor_Dig1; + R_Guess := Tmp_Int rem Divisor_Dig1; -- Refine the guess - while Divisor_Dig2 * Q_Guess > - (Tmp_Int - Q_Guess * Divisor_Dig1) * Base + - Dividend (J + 2) + while Q_Guess >= Base + or else Divisor_Dig2 * Q_Guess > + R_Guess * Base + Dividend (J + 2) loop Q_Guess := Q_Guess - 1; + R_Guess := R_Guess + Divisor_Dig1; + exit when R_Guess >= Base; end loop; -- [ MULTIPLY & SUBTRACT ] (step D4). Q_Guess * Divisor is