From owner-freebsd-numerics@freebsd.org Tue Feb 13 06:25:31 2018 Return-Path: Delivered-To: freebsd-numerics@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 4E7B6F02165 for ; Tue, 13 Feb 2018 06:25:31 +0000 (UTC) (envelope-from lists@eitanadler.com) Received: from mail-yw0-x231.google.com (mail-yw0-x231.google.com [IPv6:2607:f8b0:4002:c05::231]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id E834F86C57 for ; Tue, 13 Feb 2018 06:25:27 +0000 (UTC) (envelope-from lists@eitanadler.com) Received: by mail-yw0-x231.google.com with SMTP id z82so5212418ywb.1 for ; Mon, 12 Feb 2018 22:25:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=eitanadler.com; s=0xdeadbeef; h=mime-version:from:date:message-id:subject:to; bh=7wYj1+TjJxOGS9ia+D9Hu6zbNR2MnAAIeIymhia0lAE=; b=D9NgudLJxmFFI+MIlhVGfdH86NXFZYKt/VnPZLMXPmCrFbcJY+HTOviUx3qX2IaZFW OAHUlfGehFLAeHVD5eSo8C2Ma03GaTPvlR0/kY8app4RT3Ht7Y8P58iVmUdDKo20lxFM iouieul6DJPy87qsm0LaBHaJMD8Kj9P4h/+eY= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=7wYj1+TjJxOGS9ia+D9Hu6zbNR2MnAAIeIymhia0lAE=; b=YCxMH4iuyvEH4yYG1YqHKz4Kf82MYnbBpDVRBB+9xM8CC4t/9RR9mEfv+K3GqBggwq Zl5xctVAeXNXKrnT2VLZWmTfSJFfceDWKFTdPyJYfh6zuGlRqnaGDsEcdxBPLJLSU1MZ Tz3Zi728rSauU1zmfEtCpP/BL9jaKNZzlP2Rhvy7h3K0+LwUIIeABkHM+lzvc3SziA2E CCui/pAjERliH99safPHCNk++VRbNRKVpatgdmz3c3CEo54n+H05MqT7+l6LgBtv9DDA 8hj+YfrLAWCPxjTIgY76vJm1w4+e8gnwd/O+R1PU2sgVlPgNuHsqOKapfxSUkDoQ5O/7 qf3w== X-Gm-Message-State: APf1xPAYbsCXgEHkau1lMGX6q328v2/VqvMPlzpNNUJprZHn7N95jBeq uVWk8NAaGiRbPcZOXK18WaKTaQGmtutTOfObzlK7+YZn X-Google-Smtp-Source: AH8x227V05yNM2MAultd/PMFOMch2/x9z+C5Ry1TzyA38uK6uVnWADP3Bm5zTDu7rYeN0yWBgQ2oeFENGmlejfyC8ao= X-Received: by 10.37.38.8 with SMTP id m8mr83783ybm.97.1518503126819; Mon, 12 Feb 2018 22:25:26 -0800 (PST) MIME-Version: 1.0 Received: by 10.37.113.7 with HTTP; Mon, 12 Feb 2018 22:24:56 -0800 (PST) From: Eitan Adler Date: Mon, 12 Feb 2018 22:24:56 -0800 Message-ID: Subject: signed overflow in atan2 To: freebsd-numerics@freebsd.org Content-Type: text/plain; charset="UTF-8" X-BeenThere: freebsd-numerics@freebsd.org X-Mailman-Version: 2.1.25 Precedence: list List-Id: "Discussions of high quality implementation of libm functions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 13 Feb 2018 06:25:31 -0000 source: https://github.com/freebsd/freebsd/pull/130 `atan2(y, x)`'s special case for `x == 1.0` (in which case the result must be `atan(y)`) is unnecessarily complicated #130 As a component of atan2(y, x), the case of x == 1.0 is farmed out to atan(y). The current implementation of this comparison is vulnerable to signed integer underflow (that is, undefined behavior), and it's performed in a somewhat more complicated way than it need be. Change it to not be quite so cute, rather directly comparing the high/low bits of x to the specific IEEE-754 bit pattern that encodes 1.0. Note that while there are three different e_atan* files in the relevant directory, only this one needs fixing. e_atan2f.c already compares against the full bit pattern encoding 1.0f, while e_atan2l.cuses bitwise-ands/ors/nots and so doesn't require a change. (I ran into this in Mozilla's SpiderMonkey embedding of fdlibm, where a test of the behavior of Math.atan2(1, -0) triggered clang's signed-overflow-sanitizer runtime error.) ----- patch: if(((ix|((lx|-lx)>>31))>0x7ff00000)|| ((iy|((ly|-ly)>>31))>0x7ff00000)) /* x or y is NaN */ return x+y; - if((hx-0x3ff00000|lx)==0) return atan(y); /* x=1.0 */ + if(hx==0x3ff00000&&lx==0) return atan(y); /* x=1.0 */ m = ((hy>>31)&1)|((hx>>30)&2); /* 2*sign(x)+sign(y) */ /* when y = 0 */ ---- Is this correct? Any objections to be committing ? -- Eitan Adler From owner-freebsd-numerics@freebsd.org Tue Feb 13 09:23:05 2018 Return-Path: Delivered-To: freebsd-numerics@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id ADD7DF0E51B for ; Tue, 13 Feb 2018 09:23:05 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail104.syd.optusnet.com.au (mail104.syd.optusnet.com.au [211.29.132.246]) by mx1.freebsd.org (Postfix) with ESMTP id 2AA7B6DD24 for ; Tue, 13 Feb 2018 09:23:04 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from [192.168.0.102] (c110-21-101-228.carlnfd1.nsw.optusnet.com.au [110.21.101.228]) by mail104.syd.optusnet.com.au (Postfix) with ESMTPS id D93FF429C40; Tue, 13 Feb 2018 20:23:02 +1100 (AEDT) Date: Tue, 13 Feb 2018 20:23:01 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Eitan Adler cc: freebsd-numerics@freebsd.org Subject: Re: signed overflow in atan2 In-Reply-To: Message-ID: <20180213192144.N1911@besplex.bde.org> References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Optus-CM-Score: 0 X-Optus-CM-Analysis: v=2.2 cv=DIX/22Fb c=1 sm=1 tr=0 a=PalzARQSbocsUSjMRkwAPg==:117 a=PalzARQSbocsUSjMRkwAPg==:17 a=kj9zAlcOel0A:10 a=NEAV23lmAAAA:8 a=Sjz6Rct6sMvockCiqwcA:9 a=CjuIK1q_8ugA:10 X-BeenThere: freebsd-numerics@freebsd.org X-Mailman-Version: 2.1.25 Precedence: list List-Id: "Discussions of high quality implementation of libm functions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 13 Feb 2018 09:23:05 -0000 On Mon, 12 Feb 2018, Eitan Adler wrote: > source: https://github.com/freebsd/freebsd/pull/130 > > `atan2(y, x)`'s special case for `x == 1.0` (in which case the result > must be `atan(y)`) is unnecessarily complicated #130 > > As a component of atan2(y, x), the case of x == 1.0 is farmed out to > atan(y). The current implementation of this comparison is vulnerable > to signed integer underflow (that is, undefined behavior), and it's > performed in a somewhat more complicated way than it need be. Change > it to not be quite so cute, rather directly comparing the high/low > bits of x to the specific IEEE-754 bit pattern that encodes 1.0. > > Note that while there are three different e_atan* files in the > relevant directory, only this one needs fixing. e_atan2f.c already > compares against the full bit pattern encoding 1.0f, while > e_atan2l.cuses bitwise-ands/ors/nots and so doesn't require a change. > > (I ran into this in Mozilla's SpiderMonkey embedding of fdlibm, where > a test of the behavior of Math.atan2(1, -0) triggered clang's > signed-overflow-sanitizer runtime error.) > > ----- > > patch: > > if(((ix|((lx|-lx)>>31))>0x7ff00000)|| > ((iy|((ly|-ly)>>31))>0x7ff00000)) /* x or y is NaN */ > return x+y; > - if((hx-0x3ff00000|lx)==0) return atan(y); /* x=1.0 */ > + if(hx==0x3ff00000&&lx==0) return atan(y); /* x=1.0 */ > m = ((hy>>31)&1)|((hx>>30)&2); /* 2*sign(x)+sign(y) */ > /* when y = 0 */ Seems reasonable. Probably hx and hy should be uint32_t, but that would be a much larger change (fdlibm+Cygnus fixes does it wrong in almost all places. Cygnus changed lots of types to fixed-width, but didn't change many from signed to unsigned). The next line that does ((hy>31&1) to extract the sign bit is also unportable. 5 other files in msun/src have a similar test. 3 of these are OK because they test ix instead of hx. e_acosh.c is OK because it only tests hx in a clause where hx > 0 is known. e_pow.c is OK because it already uses the && form of the test. I don't see how clang can usefully warn about this. In the tests with ix, it can only print the harmful warning that it proved that integer overflow is impossible. In the above, it can't know that hx is negative enough to cause overflow, just like it can't know if overflow occurs for x-1 because x might be INT_MIN. Bruce From owner-freebsd-numerics@freebsd.org Tue Feb 13 20:35:44 2018 Return-Path: Delivered-To: freebsd-numerics@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 0CAF6F22485 for ; Tue, 13 Feb 2018 20:35:44 +0000 (UTC) (envelope-from sgk@troutmask.apl.washington.edu) Received: from troutmask.apl.washington.edu (troutmask.apl.washington.edu [128.95.76.21]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "troutmask", Issuer "troutmask" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 3EB3C6FC86 for ; Tue, 13 Feb 2018 20:35:43 +0000 (UTC) (envelope-from sgk@troutmask.apl.washington.edu) Received: from troutmask.apl.washington.edu (localhost [127.0.0.1]) by troutmask.apl.washington.edu (8.15.2/8.15.2) with ESMTPS id w1DKLemw000646 (version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Tue, 13 Feb 2018 12:21:40 -0800 (PST) (envelope-from sgk@troutmask.apl.washington.edu) Received: (from sgk@localhost) by troutmask.apl.washington.edu (8.15.2/8.15.2/Submit) id w1DKLe4r000645; Tue, 13 Feb 2018 12:21:40 -0800 (PST) (envelope-from sgk) Date: Tue, 13 Feb 2018 12:21:40 -0800 From: Steve Kargl To: Bruce Evans Cc: Eitan Adler , freebsd-numerics@freebsd.org Subject: Re: signed overflow in atan2 Message-ID: <20180213202140.GA636@troutmask.apl.washington.edu> Reply-To: sgk@troutmask.apl.washington.edu References: <20180213192144.N1911@besplex.bde.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20180213192144.N1911@besplex.bde.org> User-Agent: Mutt/1.9.2 (2017-12-15) X-BeenThere: freebsd-numerics@freebsd.org X-Mailman-Version: 2.1.25 Precedence: list List-Id: "Discussions of high quality implementation of libm functions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 13 Feb 2018 20:35:44 -0000 On Tue, Feb 13, 2018 at 08:23:01PM +1100, Bruce Evans wrote: > On Mon, 12 Feb 2018, Eitan Adler wrote: > > > source: https://github.com/freebsd/freebsd/pull/130 > > > > `atan2(y, x)`'s special case for `x == 1.0` (in which case the result > > must be `atan(y)`) is unnecessarily complicated #130 > > > > As a component of atan2(y, x), the case of x == 1.0 is farmed out to > > atan(y). The current implementation of this comparison is vulnerable > > to signed integer underflow (that is, undefined behavior), and it's > > performed in a somewhat more complicated way than it need be. Change > > it to not be quite so cute, rather directly comparing the high/low > > bits of x to the specific IEEE-754 bit pattern that encodes 1.0. > > > > Note that while there are three different e_atan* files in the > > relevant directory, only this one needs fixing. e_atan2f.c already > > compares against the full bit pattern encoding 1.0f, while > > e_atan2l.cuses bitwise-ands/ors/nots and so doesn't require a change. > > > > (I ran into this in Mozilla's SpiderMonkey embedding of fdlibm, where > > a test of the behavior of Math.atan2(1, -0) triggered clang's > > signed-overflow-sanitizer runtime error.) > > > > ----- > > > > patch: > > > > if(((ix|((lx|-lx)>>31))>0x7ff00000)|| > > ((iy|((ly|-ly)>>31))>0x7ff00000)) /* x or y is NaN */ > > return x+y; > > - if((hx-0x3ff00000|lx)==0) return atan(y); /* x=1.0 */ > > + if(hx==0x3ff00000&&lx==0) return atan(y); /* x=1.0 */ > > m = ((hy>>31)&1)|((hx>>30)&2); /* 2*sign(x)+sign(y) */ > > /* when y = 0 */ > > Seems reasonable. > > Probably hx and hy should be uint32_t, but that would be a much larger > change (fdlibm+Cygnus fixes does it wrong in almost all places. Cygnus > changed lots of types to fixed-width, but didn't change many from signed > to unsigned). The next line that does ((hy>31&1) to extract the sign > bit is also unportable. > > 5 other files in msun/src have a similar test. 3 of these are OK because > they test ix instead of hx. e_acosh.c is OK because it only tests hx in > a clause where hx > 0 is known. e_pow.c is OK because it already uses the > && form of the test. > > I don't see how clang can usefully warn about this. In the tests with ix, > it can only print the harmful warning that it proved that integer overflow > is impossible. In the above, it can't know that hx is negative enough to > cause overflow, just like it can't know if overflow occurs for x-1 because > x might be INT_MIN. > I've had the following in my msun tree for awhile. --- math_private.h.orig 2017-05-30 09:22:20.565401000 -0700 +++ math_private.h 2017-12-14 13:05:54.128219000 -0800 @@ -84,7 +84,7 @@ #endif -/* Get two 32 bit ints from a double. */ +/* Get two unsigned 32 bit ints from a double. */ #define EXTRACT_WORDS(ix0,ix1,d) \ do { \ @@ -166,8 +166,7 @@ typedef union { float value; - /* FIXME: Assumes 32 bit int. */ - unsigned int word; + uint32_t word; } ieee_float_shape_type; /* Get a 32 bit int from a float. */ -- Steve From owner-freebsd-numerics@freebsd.org Wed Feb 14 05:34:44 2018 Return-Path: Delivered-To: freebsd-numerics@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 67D62F02016 for ; Wed, 14 Feb 2018 05:34:44 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail104.syd.optusnet.com.au (mail104.syd.optusnet.com.au [211.29.132.246]) by mx1.freebsd.org (Postfix) with ESMTP id CDABE8500B for ; Wed, 14 Feb 2018 05:34:43 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from [192.168.0.102] (c110-21-101-228.carlnfd1.nsw.optusnet.com.au [110.21.101.228]) by mail104.syd.optusnet.com.au (Postfix) with ESMTPS id CFD52425790; Wed, 14 Feb 2018 16:34:34 +1100 (AEDT) Date: Wed, 14 Feb 2018 16:34:33 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Steve Kargl cc: Bruce Evans , Eitan Adler , freebsd-numerics@freebsd.org Subject: Re: signed overflow in atan2 In-Reply-To: <20180213202140.GA636@troutmask.apl.washington.edu> Message-ID: <20180214162050.I1500@besplex.bde.org> References: <20180213192144.N1911@besplex.bde.org> <20180213202140.GA636@troutmask.apl.washington.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Optus-CM-Score: 0 X-Optus-CM-Analysis: v=2.2 cv=cIaQihWN c=1 sm=1 tr=0 a=PalzARQSbocsUSjMRkwAPg==:117 a=PalzARQSbocsUSjMRkwAPg==:17 a=kj9zAlcOel0A:10 a=NEAV23lmAAAA:8 a=2jNcl6kaKsOu3xXVZPsA:9 a=CjuIK1q_8ugA:10 X-BeenThere: freebsd-numerics@freebsd.org X-Mailman-Version: 2.1.25 Precedence: list List-Id: "Discussions of high quality implementation of libm functions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 14 Feb 2018 05:34:44 -0000 On Tue, 13 Feb 2018, Steve Kargl wrote: > On Tue, Feb 13, 2018 at 08:23:01PM +1100, Bruce Evans wrote: >> On Mon, 12 Feb 2018, Eitan Adler wrote: >> >>> source: https://github.com/freebsd/freebsd/pull/130 >>> >>> `atan2(y, x)`'s special case for `x == 1.0` (in which case the result >>> must be `atan(y)`) is unnecessarily complicated #130 >>> >>> As a component of atan2(y, x), the case of x == 1.0 is farmed out to >>> atan(y). The current implementation of this comparison is vulnerable >>> to signed integer underflow (that is, undefined behavior), and it's >>> performed in a somewhat more complicated way than it need be. Change >>> it to not be quite so cute, rather directly comparing the high/low >>> bits of x to the specific IEEE-754 bit pattern that encodes 1.0. >>> ... >>> ----- >>> >>> patch: >>> >>> if(((ix|((lx|-lx)>>31))>0x7ff00000)|| >>> ((iy|((ly|-ly)>>31))>0x7ff00000)) /* x or y is NaN */ >>> return x+y; >>> - if((hx-0x3ff00000|lx)==0) return atan(y); /* x=1.0 */ >>> + if(hx==0x3ff00000&&lx==0) return atan(y); /* x=1.0 */ >>> m = ((hy>>31)&1)|((hx>>30)&2); /* 2*sign(x)+sign(y) */ >>> /* when y = 0 */ >> >> Seems reasonable. >> >> Probably hx and hy should be uint32_t, but that would be a much larger >> change (fdlibm+Cygnus fixes does it wrong in almost all places. Cygnus >> changed lots of types to fixed-width, but didn't change many from signed >> to unsigned). The next line that does ((hy>31&1) to extract the sign >> bit is also unportable. > > I've had the following in my msun tree for awhile. > > --- math_private.h.orig 2017-05-30 09:22:20.565401000 -0700 > +++ math_private.h 2017-12-14 13:05:54.128219000 -0800 > @@ -84,7 +84,7 @@ > > #endif > > -/* Get two 32 bit ints from a double. */ > +/* Get two unsigned 32 bit ints from a double. */ > > #define EXTRACT_WORDS(ix0,ix1,d) \ > do { \ > @@ -166,8 +166,7 @@ > typedef union > { > float value; > - /* FIXME: Assumes 32 bit int. */ > - unsigned int word; > + uint32_t word; > } ieee_float_shape_type; > > /* Get a 32 bit int from a float. */ So it is a type hack that is usually negatively useful to use signed types for the output of these macros. (Usually, for EXTRACT_WORDS(hx, lx, x), lx is u_int32_t but hx is int32_t so that "hx < 0" works right but everything else tends to be unportable. The variable hx is converted by assignment of the top word in the struct, so the sign mismatch is hard to see. For ld80, the top bits in the struct are only 16 bits and buggy code cloned from double precision might still use int32_t for hx; then the conversion or rather the use of hx is more magic.) Bruce