From owner-freebsd-numerics@freebsd.org Sat Nov 16 18:02:29 2019 Return-Path: Delivered-To: freebsd-numerics@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id D31081AABF1 for ; Sat, 16 Nov 2019 18:02:29 +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.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "troutmask", Issuer "troutmask" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 47Fjjd4qlZz3DJ5; Sat, 16 Nov 2019 18:02:29 +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 xAGI2MhZ039435 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO); Sat, 16 Nov 2019 10:02:22 -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 xAGI2LwD039434; Sat, 16 Nov 2019 10:02:21 -0800 (PST) (envelope-from sgk) Date: Sat, 16 Nov 2019 10:02:21 -0800 From: Steve Kargl To: Li-Wen Hsu Cc: Jeff Walden , freebsd-numerics@freebsd.org Subject: Re: UB in various hypot() implementations (left-shifting a negative number) Message-ID: <20191116180221.GA39224@troutmask.apl.washington.edu> Reply-To: sgk@troutmask.apl.washington.edu References: <20191113232233.GA64847@troutmask.apl.washington.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.12.2 (2019-09-21) X-Rspamd-Queue-Id: 47Fjjd4qlZz3DJ5 X-Spamd-Bar: ----- Authentication-Results: mx1.freebsd.org; none X-Spamd-Result: default: False [-5.99 / 15.00]; NEURAL_HAM_MEDIUM(-0.99)[-0.991,0]; REPLY(-4.00)[]; NEURAL_HAM_LONG(-1.00)[-1.000,0] X-BeenThere: freebsd-numerics@freebsd.org X-Mailman-Version: 2.1.29 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: Sat, 16 Nov 2019 18:02:29 -0000 The patch for hypotl() is likely unneeded as there is no shifting of a negative integer in the code being changed. Does csqrt_test.c pass without Jeff's patch? This is the original code u_int32_t high; t1 = 1.0; GET_HIGH_WORD(high,t1); SET_HIGH_WORD(t1,high+DESW(k)); high + DESW(k) = high + k = 16383 + k and this is the code after the patch t1 = 0.0; SET_HIGH_WORD(t1,ESW(k)); ESW(k) = MAX_EXP - 1 + k = LDBL_MAX_EXP - 1 + k = 16384 - 1 + k = 16383 + k So, in principle there is no functional change. -- steve On Sat, Nov 16, 2019 at 11:03:19PM +0800, Li-Wen Hsu wrote: > I did a quick test, it seems one regression test fails: > > lwhsu@x1c:/usr/tests/lib/msun > kyua debug csqrt_test:main > 1..18 > ok 1 - csqrt > ok 2 - csqrt > ok 3 - csqrt > ok 4 - csqrt > ok 5 - csqrt > ok 6 - csqrt > ok 7 - csqrt > ok 8 - csqrt > ok 9 - csqrt > ok 10 - csqrt > ok 11 - csqrt > ok 12 - csqrt > ok 13 - csqrt > ok 14 - csqrt > ok 15 - csqrt > ok 16 - csqrt > Assertion failed: (creall(result) == ldexpl(14 * 0x1p-4, exp / 2)), > function test_overflow, file > /usr/home/lwhsu/freebsd-src/lib/msun/tests/csqrt_test.c, line 236. > Process with PID 18700 exited with signal 6 and dumped core; > attempting to gather stack trace > [New LWP 101179] > Core was generated by `/usr/tests/lib/msun/csqrt_test'. > Program terminated with signal SIGABRT, Aborted. > #0 thr_kill () at thr_kill.S:3 > 3 RSYSCALL(thr_kill) > #0 thr_kill () at thr_kill.S:3 > #1 0x00000008004543a4 in __raise (s=6) at /usr/src/lib/libc/gen/raise.c:52 > #2 0x00000008003c3029 in abort () at /usr/src/lib/libc/stdlib/abort.c:67 > #3 0x0000000800440e71 in __assert (func=, > file=, line=, failedexpr= out>) at /usr/src/lib/libc/gen/assert.c:51 > #4 0x00000000002040bd in test_overflow (maxexp=16384) at > /usr/home/lwhsu/freebsd-src/lib/msun/tests/csqrt_test.c:236 > #5 0x0000000000202a91 in main () at > /usr/home/lwhsu/freebsd-src/lib/msun/tests/csqrt_test.c:363 > GDB exited successfully > Files left in work directory after failure: csqrt_test.core > csqrt_test:main -> broken: Received signal 6 > > I haven't checked the details, but I definitely need experts in this > field to help. > > Thanks, > Li-Wen > > > On Thu, Nov 14, 2019 at 7:22 AM Steve Kargl > wrote: > > > > Looks good to me. Just need to convince someone to commit it. > > > > -- > > steve > > > > > > On Wed, Nov 13, 2019 at 02:43:04PM -0800, Jeff Walden wrote: > > > > > > Just wanted to note here that I filed https://reviews.freebsd.org/D22354 to fix a bit of undefined behavior in the hypot() function implementations. > > > > > > `hypot(x, y)` computes `sqrt(x*x + y*y)`, with IEEE-754-aware precision. For very large or small `x` or `y`, the naive implementation would lose precision -- so in such cases the calculation is performed after multiplying the numbers by a very large (or very small) power of two, then the multiplication is undone at end. > > > > > > Undoing the multiplication involves multiplying a quantity `w` by `2**k`, where `k` (which may be positive or negative) was computed depending on the particular `x` and `y` values provided. Current algorithms generally take `t1=0.0`, extract the high word, add `k<<20` or `k<<23` to it to appropriately bump the exponent, then overwrite `t1`'s high word. But it seems equally effective to take `t1=0.0`, then write `(1023+k)<<20` or `(127+k)<<23` to it for identical effect -- and `k` is never so negative to compute a negative value. My changes do this. (I wish there were named constants I could use for all these numbers, but as there don't seem to be any, magic numbers seems like the best I can do.) > > > > > > Errors in these changes would most likely produce a power of two off by a factor of two, so *probably* testing any inputs that would happen to invoke these code paths should be adequate testing. I'm fixing this in order to upstream a likely fix in the SpiderMonkey JavaScript engine for this, so the (double, double) algorithm/change is the only one I have (purely manually) tested. Eyeballs on the other functions' changes especially appreciated! > > > > > > Jeff > > > _______________________________________________ > > > freebsd-numerics@freebsd.org mailing list > > > https://lists.freebsd.org/mailman/listinfo/freebsd-numerics > > > To unsubscribe, send any mail to "freebsd-numerics-unsubscribe@freebsd.org" > > > > -- > > Steve > > 20170425 https://www.youtube.com/watch?v=VWUpyCsUKR4 > > 20161221 https://www.youtube.com/watch?v=IbCHE-hONow > > _______________________________________________ > > freebsd-numerics@freebsd.org mailing list > > https://lists.freebsd.org/mailman/listinfo/freebsd-numerics > > To unsubscribe, send any mail to "freebsd-numerics-unsubscribe@freebsd.org" -- Steve 20170425 https://www.youtube.com/watch?v=VWUpyCsUKR4 20161221 https://www.youtube.com/watch?v=IbCHE-hONow