From owner-freebsd-numerics@freebsd.org Wed Nov 13 22:43:13 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 D501A1BE611 for ; Wed, 13 Nov 2019 22:43:13 +0000 (UTC) (envelope-from jwalden@mit.edu) Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 47D04w3Wjpz3Cmp for ; Wed, 13 Nov 2019 22:43:11 +0000 (UTC) (envelope-from jwalden@mit.edu) Received: from [10.252.25.189] (corp-nat.fw1.untrust.mtv2.mozilla.net [63.245.221.198]) (authenticated bits=0) (User authenticated as jwalden@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id xADMh5S5023770 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT) for ; Wed, 13 Nov 2019 17:43:08 -0500 To: freebsd-numerics@freebsd.org From: Jeff Walden Subject: UB in various hypot() implementations (left-shifting a negative number) Openpgp: preference=signencrypt Message-ID: Date: Wed, 13 Nov 2019 14:43:04 -0800 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.1 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-Rspamd-Queue-Id: 47D04w3Wjpz3Cmp X-Spamd-Bar: ----- Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=pass (mx1.freebsd.org: domain of jwalden@mit.edu designates 18.9.28.11 as permitted sender) smtp.mailfrom=jwalden@mit.edu X-Spamd-Result: default: False [-5.34 / 15.00]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; FROM_HAS_DN(0.00)[]; R_SPF_ALLOW(-0.20)[+ip4:18.9.28.0/24]; TO_MATCH_ENVRCPT_ALL(0.00)[]; MIME_GOOD(-0.10)[text/plain]; PREVIOUSLY_DELIVERED(0.00)[freebsd-numerics@freebsd.org]; TO_DN_NONE(0.00)[]; RCPT_COUNT_ONE(0.00)[1]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; RCVD_TLS_LAST(0.00)[]; RCVD_IN_DNSWL_MED(-0.20)[11.28.9.18.list.dnswl.org : 127.0.11.2]; DMARC_NA(0.00)[mit.edu]; IP_SCORE(-2.84)[ip: (-9.55), ipnet: 18.9.0.0/16(-4.62), asn: 3(0.01), country: US(-0.05)]; FROM_EQ_ENVFROM(0.00)[]; R_DKIM_NA(0.00)[]; MIME_TRACE(0.00)[0:+]; ASN(0.00)[asn:3, ipnet:18.9.0.0/16, country:US]; MID_RHS_MATCH_FROM(0.00)[]; RCVD_COUNT_TWO(0.00)[2] 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: Wed, 13 Nov 2019 22:43:13 -0000 Hi all, 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 From owner-freebsd-numerics@freebsd.org Wed Nov 13 23:22:36 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 48F651BF16C for ; Wed, 13 Nov 2019 23:22:36 +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 47D0yM2HCFz47df for ; Wed, 13 Nov 2019 23:22:34 +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 xADNMXmr096268 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO); Wed, 13 Nov 2019 15:22:33 -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 xADNMXCO096267; Wed, 13 Nov 2019 15:22:33 -0800 (PST) (envelope-from sgk) Date: Wed, 13 Nov 2019 15:22:33 -0800 From: Steve Kargl To: Jeff Walden Cc: freebsd-numerics@freebsd.org Subject: Re: UB in various hypot() implementations (left-shifting a negative number) Message-ID: <20191113232233.GA64847@troutmask.apl.washington.edu> Reply-To: sgk@troutmask.apl.washington.edu References: 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: 47D0yM2HCFz47df X-Spamd-Bar: - Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=none (mx1.freebsd.org: domain of sgk@troutmask.apl.washington.edu has no SPF policy when checking 128.95.76.21) smtp.mailfrom=sgk@troutmask.apl.washington.edu X-Spamd-Result: default: False [-1.24 / 15.00]; ARC_NA(0.00)[]; HAS_REPLYTO(0.00)[sgk@troutmask.apl.washington.edu]; NEURAL_HAM_MEDIUM(-0.92)[-0.922,0]; FROM_HAS_DN(0.00)[]; TO_DN_SOME(0.00)[]; IP_SCORE(-0.22)[ip: (0.06), ipnet: 128.95.0.0/16(-0.29), asn: 73(-0.83), country: US(-0.05)]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(0.00)[washington.edu]; REPLYTO_ADDR_EQ_FROM(0.00)[]; AUTH_NA(1.00)[]; NEURAL_HAM_LONG(-1.00)[-0.998,0]; TO_MATCH_ENVRCPT_SOME(0.00)[]; RCPT_COUNT_TWO(0.00)[2]; R_SPF_NA(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; R_DKIM_NA(0.00)[]; MIME_TRACE(0.00)[0:+]; ASN(0.00)[asn:73, ipnet:128.95.0.0/16, country:US]; MID_RHS_MATCH_FROM(0.00)[]; RCVD_TLS_ALL(0.00)[]; RCVD_COUNT_TWO(0.00)[2] 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: Wed, 13 Nov 2019 23:22:36 -0000 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 From owner-freebsd-numerics@freebsd.org Sat Nov 16 15:03:37 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 445811C7263 for ; Sat, 16 Nov 2019 15:03:37 +0000 (UTC) (envelope-from lwhsu.freebsd@gmail.com) Received: from mail-yb1-f176.google.com (mail-yb1-f176.google.com [209.85.219.176]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1O1" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 47FdlC3S84z4DlH for ; Sat, 16 Nov 2019 15:03:34 +0000 (UTC) (envelope-from lwhsu.freebsd@gmail.com) Received: by mail-yb1-f176.google.com with SMTP id i15so5296402ybq.0 for ; Sat, 16 Nov 2019 07:03:34 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=4GjbzrDvfH5reXrzeZ+IXM5mUKcm4dlTAQ2IcyDM1as=; b=pQn+TxWcobIVLzYMUmyVKUGva/DbspCtlBeBwArchEcj5xVJCKlRSONrCmVOiHVZ1C mTp1BydKcaA/gu1vvj+84hgtFYQrJZKz0Qiau2cWkZM4IppJ++Cy4hPj9d/CWqZBY+Mq sKYA6KbQdoY2AK8WMUacAsxNNJuy+SdnZ1kZfQPhpZCpPVAuknk4Emcv8hUGq2JSCloq 9E/9pg2f1Nw3lZ5QOQlrR5LR8yX98amMHAwz+Pz5RG+1emkE5XR/6tgU2Wb6+cFqLtWD eGL9Ho+eykwDuq4I8XtuwrGSHO61hie4N5XMZIXzn3HO+FXqUkkpdfFlVbdS+dnjhP2G eE/w== X-Gm-Message-State: APjAAAU7t+CfxGCtty1fmrJBTeTkRe7Y9hJWcZaO6mvOr9oUo35cNXbW v6JnzOKSsgzVma+DPjk9Aa5fYUezuXaL60PdJrk= X-Google-Smtp-Source: APXvYqwwCwfRLEsE32ILkSEfHhRfoYJCvLZ2gywSb51b0hWYvWtqyGpglfelzYKxcuIg1KQt/oZhmK4VM+s1vYrgd7k= X-Received: by 2002:a25:4b03:: with SMTP id y3mr16618595yba.497.1573916611845; Sat, 16 Nov 2019 07:03:31 -0800 (PST) MIME-Version: 1.0 References: <20191113232233.GA64847@troutmask.apl.washington.edu> In-Reply-To: <20191113232233.GA64847@troutmask.apl.washington.edu> From: Li-Wen Hsu Date: Sat, 16 Nov 2019 23:03:19 +0800 Message-ID: Subject: Re: UB in various hypot() implementations (left-shifting a negative number) To: sgk@troutmask.apl.washington.edu Cc: Jeff Walden , freebsd-numerics@freebsd.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Rspamd-Queue-Id: 47FdlC3S84z4DlH X-Spamd-Bar: ---- Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=pass (mx1.freebsd.org: domain of lwhsufreebsd@gmail.com designates 209.85.219.176 as permitted sender) smtp.mailfrom=lwhsufreebsd@gmail.com X-Spamd-Result: default: False [-4.78 / 15.00]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; RCVD_TLS_ALL(0.00)[]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[3]; R_SPF_ALLOW(-0.20)[+ip4:209.85.128.0/17:c]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; MIME_GOOD(-0.10)[text/plain]; PREVIOUSLY_DELIVERED(0.00)[freebsd-numerics@freebsd.org]; DMARC_NA(0.00)[freebsd.org]; TO_DN_SOME(0.00)[]; MIME_TRACE(0.00)[0:+]; TO_MATCH_ENVRCPT_SOME(0.00)[]; RCVD_IN_DNSWL_NONE(0.00)[176.219.85.209.list.dnswl.org : 127.0.5.0]; IP_SCORE(-2.78)[ip: (-8.69), ipnet: 209.85.128.0/17(-3.18), asn: 15169(-1.98), country: US(-0.05)]; FORGED_SENDER(0.30)[lwhsu@freebsd.org,lwhsufreebsd@gmail.com]; R_DKIM_NA(0.00)[]; FREEMAIL_ENVFROM(0.00)[gmail.com]; ASN(0.00)[asn:15169, ipnet:209.85.128.0/17, country:US]; FROM_NEQ_ENVFROM(0.00)[lwhsu@freebsd.org,lwhsufreebsd@gmail.com]; TAGGED_FROM(0.00)[]; RCVD_COUNT_TWO(0.00)[2] 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 15:03:37 -0000 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) =3D=3D 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=3D6) 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=3D, file=3D, line=3D, failedexpr=3D) at /usr/src/lib/libc/gen/assert.c:51 #4 0x00000000002040bd in test_overflow (maxexp=3D16384) 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/D2235= 4 to fix a bit of undefined behavior in the hypot() function implementation= s. > > > > `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 multiplyin= g the numbers by a very large (or very small) power of two, then the multip= lication 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 t= ake `t1=3D0.0`, extract the high word, add `k<<20` or `k<<23` to it to appr= opriately bump the exponent, then overwrite `t1`'s high word. But it seems= equally effective to take `t1=3D0.0`, then write `(1023+k)<<20` or `(127+k= )<<23` to it for identical effect -- and `k` is never so negative to comput= e a negative value. My changes do this. (I wish there were named constant= s I could use for all these numbers, but as there don't seem to be any, mag= ic 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 inv= oke 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 manua= lly) tested. Eyeballs on the other functions' changes especially appreciat= ed! > > > > 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=3DVWUpyCsUKR4 > 20161221 https://www.youtube.com/watch?v=3DIbCHE-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.or= g" 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 From owner-freebsd-numerics@freebsd.org Sat Nov 16 20:40:57 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 89B6A1ADB93 for ; Sat, 16 Nov 2019 20:40:57 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from smtp.freebsd.org (smtp.freebsd.org [IPv6:2610:1c1:1:606c::24b:4]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "smtp.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 47FnDT1hFhz3Cxs for ; Sat, 16 Nov 2019 20:40:57 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from tensor.andric.com (tensor.andric.com [IPv6:2001:470:7a58:1::1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "tensor.andric.com", Issuer "Let's Encrypt Authority X3" (verified OK)) (Authenticated sender: dim) by smtp.freebsd.org (Postfix) with ESMTPSA id BC64E16021 for ; Sat, 16 Nov 2019 20:40:56 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from [IPv6:2001:470:7a58:0:2452:2375:71a2:2897] (unknown [IPv6:2001:470:7a58:0:2452:2375:71a2:2897]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by tensor.andric.com (Postfix) with ESMTPSA id 4E4132C5C4 for ; Sat, 16 Nov 2019 21:40:41 +0100 (CET) To: freebsd-numerics@freebsd.org From: Dimitry Andric Subject: Re: UB in various hypot() implementations (left-shifting a negative, number) Message-ID: Date: Sat, 16 Nov 2019 21:40:40 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Thunderbird/68.2.2 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit 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 20:40:57 -0000 On 2019-11-16 18:02:29 UTC, Steve Kargl wrote: > 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? Yes, it passes. > 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. What about t1 changing from 1.0 to 0? If I revert just that line, all tests do pass, including the csqrt test. -Dimitry PS: Apologies for any missing References: header in this mail, which might mess up threading in your mail client. I just subscribed to this list. From owner-freebsd-numerics@freebsd.org Sat Nov 16 21:14:24 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 7CE631AE676 for ; Sat, 16 Nov 2019 21:14:24 +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 47Fnz22zKwz4fvN; Sat, 16 Nov 2019 21:14:21 +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 xAGLEJ6X040078 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO); Sat, 16 Nov 2019 13:14:20 -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 xAGLEJjE040077; Sat, 16 Nov 2019 13:14:19 -0800 (PST) (envelope-from sgk) Date: Sat, 16 Nov 2019 13:14:19 -0800 From: Steve Kargl To: Dimitry Andric Cc: freebsd-numerics@freebsd.org Subject: Re: UB in various hypot() implementations (left-shifting a negative, number) Message-ID: <20191116211419.GA40056@troutmask.apl.washington.edu> Reply-To: sgk@troutmask.apl.washington.edu References: 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: 47Fnz22zKwz4fvN X-Spamd-Bar: - Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=none (mx1.freebsd.org: domain of sgk@troutmask.apl.washington.edu has no SPF policy when checking 128.95.76.21) smtp.mailfrom=sgk@troutmask.apl.washington.edu X-Spamd-Result: default: False [-1.19 / 15.00]; ARC_NA(0.00)[]; HAS_REPLYTO(0.00)[sgk@troutmask.apl.washington.edu]; NEURAL_HAM_MEDIUM(-0.88)[-0.885,0]; FROM_HAS_DN(0.00)[]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; NEURAL_HAM_LONG(-0.98)[-0.983,0]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(0.00)[washington.edu]; REPLYTO_ADDR_EQ_FROM(0.00)[]; AUTH_NA(1.00)[]; IP_SCORE(-0.22)[ip: (0.06), ipnet: 128.95.0.0/16(-0.28), asn: 73(-0.83), country: US(-0.05)]; RCPT_COUNT_TWO(0.00)[2]; R_SPF_NA(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; R_DKIM_NA(0.00)[]; MIME_TRACE(0.00)[0:+]; ASN(0.00)[asn:73, ipnet:128.95.0.0/16, country:US]; MID_RHS_MATCH_FROM(0.00)[]; RCVD_TLS_ALL(0.00)[]; RCVD_COUNT_TWO(0.00)[2] 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 21:14:24 -0000 On Sat, Nov 16, 2019 at 09:40:40PM +0100, Dimitry Andric wrote: > On 2019-11-16 18:02:29 UTC, Steve Kargl wrote: > > 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? > > Yes, it passes. > > > 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. > > What about t1 changing from 1.0 to 0? If I revert just that line, all > tests do pass, including the csqrt test. > Well, clearly, the patch to e_hypotl.c is wrong. It clear the significand when t1 = 0 whereas t1 = 1 leaves one bit set in the significand. Simply looking at the value of t1 under a poor man's debugger shows the difference. Adding "printf("%Le %La\n", t1, t1);" after the SET_HIGH_WORD gives 2.962347e-2493 0x1p-8280 <-- t1 = 1 0.000000e+00 0x1p-8280 <-- t1 = 0 for hypotl(ldexpl(1.1,-16000), ldexpl(2.1, -16000)). -- Steve 20170425 https://www.youtube.com/watch?v=VWUpyCsUKR4 20161221 https://www.youtube.com/watch?v=IbCHE-hONow