From owner-freebsd-numerics@freebsd.org Mon Jan 14 12:52:30 2019 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 952BF149F561 for ; Mon, 14 Jan 2019 12:52:30 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail106.syd.optusnet.com.au (mail106.syd.optusnet.com.au [211.29.132.42]) by mx1.freebsd.org (Postfix) with ESMTP id BC28787735; Mon, 14 Jan 2019 12:52:26 +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 mail106.syd.optusnet.com.au (Postfix) with ESMTPS id DD3523CEF39; Mon, 14 Jan 2019 23:52:15 +1100 (AEDT) Date: Mon, 14 Jan 2019 23:52:14 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Pedro Giffuni cc: sgk@troutmask.apl.washington.edu, freebsd-numerics@freebsd.org Subject: Re: Undefined Behavior in lib/msun/src/e_pow.c (was Re: New math library from ARM) In-Reply-To: Message-ID: <20190114231414.K1062@besplex.bde.org> References: <797a7755-db93-1b9c-f3b9-8850d948e098@FreeBSD.org> <20181231151904.GB823@troutmask.apl.washington.edu> <20181231152230.GC823@troutmask.apl.washington.edu> <06c8b6a2-ed26-f255-3947-c79b593a9dea@FreeBSD.org> <20190101045425.GA5767@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=DZtnkrlW c=1 sm=1 tr=0 a=PalzARQSbocsUSjMRkwAPg==:117 a=PalzARQSbocsUSjMRkwAPg==:17 a=kj9zAlcOel0A:10 a=5KEJ3k9QAAAA:8 a=LyluLOMXfiYpJ-Na4xIA:9 a=CjuIK1q_8ugA:10 a=olg2BfGzmf2haRflzj8J:22 X-Rspamd-Queue-Id: BC28787735 X-Spamd-Bar: ------ Authentication-Results: mx1.freebsd.org; spf=pass (mx1.freebsd.org: domain of brde@optusnet.com.au designates 211.29.132.42 as permitted sender) smtp.mailfrom=brde@optusnet.com.au X-Spamd-Result: default: False [-6.63 / 15.00]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; RCVD_IN_DNSWL_LOW(-0.10)[42.132.29.211.list.dnswl.org : 127.0.5.1]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[3]; R_SPF_ALLOW(-0.20)[+ip4:211.29.132.0/23]; FREEMAIL_FROM(0.00)[optusnet.com.au]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(0.00)[optusnet.com.au]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_SOME(0.00)[]; MX_GOOD(-0.01)[extmail.optusnet.com.au]; NEURAL_HAM_SHORT(-0.96)[-0.958,0]; IP_SCORE(-3.36)[ip: (-9.40), ipnet: 211.28.0.0/14(-4.11), asn: 4804(-3.26), country: AU(-0.03)]; RCVD_NO_TLS_LAST(0.10)[]; FROM_EQ_ENVFROM(0.00)[]; R_DKIM_NA(0.00)[]; FREEMAIL_ENVFROM(0.00)[optusnet.com.au]; ASN(0.00)[asn:4804, ipnet:211.28.0.0/14, country:AU]; MIME_TRACE(0.00)[0:+]; 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: Mon, 14 Jan 2019 12:52:30 -0000 On Tue, 1 Jan 2019, Pedro Giffuni wrote: > On 31/12/2018 23:54, Steve Kargl wrote: >> On Mon, Dec 31, 2018 at 10:32:06PM -0500, Pedro Giffuni wrote: >>> Hmm ... >>> >>> Looking at the changes in musl's libc I found this issue which seems >>> real (although somewhat theoretical): >>> >>> https://git.musl-libc.org/cgit/musl/commit/src/math?id=688d3da0f1730daddbc954bbc2d27cc96ceee04c >>> >>> Is the attached patch acceptable? >>> >>> Also, their code is bit different here: >>> >>> https://git.musl-libc.org/cgit/musl/commit/src/math?id=282b1cd26649d69de038111f5876853df6ddc345 >>> >>> but we may also have to check fmaf(-0x1.26524ep-54, -0x1.cb7868p+11, >>> 0x1.d10f5ep-29). >>> >>> Cheers, >>> >>> Pedro. >>> >>> Index: lib/msun/src/e_pow.c >>> =================================================================== >>> --- lib/msun/src/e_pow.c (revision 342665) >>> +++ lib/msun/src/e_pow.c (working copy) >>> @@ -130,6 +130,7 @@ >>> if(hx<0) { >>> if(iy>=0x43400000) yisint = 2; /* even integer y */ >>> else if(iy>=0x3ff00000) { >>> + uint32_t j; /* Avoid UB in bit operations below. */ >>> k = (iy>>20)-0x3ff; /* exponent */ >>> if(k>20) { >>> j = ly>>(52-k); I was away. I see you committed a better version (with a cast). The correct fix is more like the changing the file scope i and j from int32_t to u[_]int32_t. j is mostly used as a temporary to hold pure bits. Its top bit is usually not set, so plain int32_t works for it. The only other place where its top bit can obviously be set is in an EXTRACT_WORDS(j,i,z). Then both j and i can have their top bit set. EXTRACT_WORDS() into h[xy] and l[xy] is also sloppy. There l[xy] is unsigned, but h[xy] is signed. The top bit in the high word is soon discarded using ix = hx&0x7fffffff, etc. Later, the sign is tested using hx<0 and this is the only excuse for hx being signed. fdlibm does this quite often. It is a manual optimization for ~30-40 year old compilers that couldn't turn (hx&8000000) != 0 into a sign test iff the sign test is optimal. Other style bugs in the above: >> I'll defer to Bruce on this. My only comments are >> 1) declarations belong at the top of the file where all declarations occur 1a) missing blank line after declaration. > Modern standards let you declare variables within blocks. For style we do > prefer to start the function with them but in this case we can't. K&R 1978 C allows declaring variables within blocks. You can't declare j again in function scope since it is already there with a different type. >> 2) j is already declared as int32_t > And it has to be a signed integer: we later check for negative values. I think that is only when j is misused later for EXTRACT_WORDS(). 2a,2b) Redeclaring j with a different type in an inner block is an even larger style bug/obfuscation than declaring a new variable or redeclaring j with the same type there. Redeclaring shadows it and this bug is detected by Wshadow. Redeclaring it with a different type (as needed to work) is especially obscure shadowing. >> 3) uint32_t should be written as u_int32_t. > > No, uint32_t is the standard type, u_int32_t is a BSDism. Also, the file > consistently uses uint32_t. No, see previous replies. 3) is correct. >> Are you sure that UB occurs? Or, is this an attempt to >> placate a static analysis tool that only see shifting of >> a signed type? Do you need to make a similar change to >> e_powf.c? > > The point of the Undefined Behavior is precisely that it doesn't occur: we > are lucky and the compiler behaves as it always has but the standard will let > a different compiler behave differently and then we will have surprises. No, UB does occur, but is harmless. ly is unsigned and can have its top bit set. j=ly>>(52-k) shifts right a few bits so doesn't overflow on assignment to signed j. But then j<<(52-k) gives UB attempting to recover the top bit of ly gives UB in all cases where the top bit is nonzero. The else clause doesn't have this problem, since it shifts iy instead of ly and iy never has its top bit set. e_powf.c doesn't have this problem, since there is only 1 32-bit word for float precision and it is handled like the top word for double precision (only its mantissa bits are shifted). However, it is easier to use unsigned shifts than to see that signed shifts have defined behaviour. musl did well to only detect and/or fix the 1 case where UB behaviour clearly occurs. Bruce From owner-freebsd-numerics@freebsd.org Mon Jan 14 13:43:14 2019 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 A4A6114A092E for ; Mon, 14 Jan 2019 13:43:14 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail106.syd.optusnet.com.au (mail106.syd.optusnet.com.au [211.29.132.42]) by mx1.freebsd.org (Postfix) with ESMTP id 6D7D6891F5; Mon, 14 Jan 2019 13:43:12 +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 mail106.syd.optusnet.com.au (Postfix) with ESMTPS id 630723CF3C8; Tue, 15 Jan 2019 00:43:08 +1100 (AEDT) Date: Tue, 15 Jan 2019 00:43:07 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Steve Kargl cc: Pedro Giffuni , freebsd-numerics@freebsd.org Subject: Re: Undefined Behavior in lib/msun/src/e_pow.c (was Re: New math library from ARM) In-Reply-To: <20190101183226.GA11443@troutmask.apl.washington.edu> Message-ID: <20190114235426.I1062@besplex.bde.org> References: <797a7755-db93-1b9c-f3b9-8850d948e098@FreeBSD.org> <20181231151904.GB823@troutmask.apl.washington.edu> <20181231152230.GC823@troutmask.apl.washington.edu> <06c8b6a2-ed26-f255-3947-c79b593a9dea@FreeBSD.org> <20190101045425.GA5767@troutmask.apl.washington.edu> <20190101055225.GA5982@troutmask.apl.washington.edu> <9cdce84b-2cff-d752-67a9-4c9ef391cc2c@FreeBSD.org> <20190101183226.GA11443@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=FNpr/6gs c=1 sm=1 tr=0 a=PalzARQSbocsUSjMRkwAPg==:117 a=PalzARQSbocsUSjMRkwAPg==:17 a=kj9zAlcOel0A:10 a=oRHHkTnlz5SPpp-4SwMA:9 a=CjuIK1q_8ugA:10 X-Rspamd-Queue-Id: 6D7D6891F5 X-Spamd-Bar: ------ Authentication-Results: mx1.freebsd.org; spf=pass (mx1.freebsd.org: domain of brde@optusnet.com.au designates 211.29.132.42 as permitted sender) smtp.mailfrom=brde@optusnet.com.au X-Spamd-Result: default: False [-6.51 / 15.00]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; RCVD_IN_DNSWL_LOW(-0.10)[42.132.29.211.list.dnswl.org : 127.0.5.1]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[3]; R_SPF_ALLOW(-0.20)[+ip4:211.29.132.0/23]; FREEMAIL_FROM(0.00)[optusnet.com.au]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(0.00)[optusnet.com.au]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_SOME(0.00)[]; MX_GOOD(-0.01)[cached: extmail.optusnet.com.au]; NEURAL_HAM_SHORT(-0.83)[-0.825,0]; IP_SCORE(-3.37)[ip: (-9.41), ipnet: 211.28.0.0/14(-4.13), asn: 4804(-3.28), country: AU(-0.04)]; RCVD_NO_TLS_LAST(0.10)[]; FROM_EQ_ENVFROM(0.00)[]; R_DKIM_NA(0.00)[]; FREEMAIL_ENVFROM(0.00)[optusnet.com.au]; ASN(0.00)[asn:4804, ipnet:211.28.0.0/14, country:AU]; MIME_TRACE(0.00)[0:+]; 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: Mon, 14 Jan 2019 13:43:15 -0000 On Tue, 1 Jan 2019, Steve Kargl wrote: > On Tue, Jan 01, 2019 at 10:01:45AM -0500, Pedro Giffuni wrote: >> >>>> This would be easy >>>> to see if all declarations are grouped together. In additional, >>>> don't you need to include stdint.h to get uint32_t? >>> >>> Well, my patch did compile, but I will match the existing style if >>> the change is accepted/desired. > > Yeah, I found that out myself. I cannot find where stdint.h is > being pulled into the build. It seems that one of the included > headers may have some namespace pollution. Both u_int32_t and uint32_t are standard [Free]BSD pollution in . The library can reasonably depend on this. stdint.h should rarely be included when compiling msun. It is currently included directly in about 6 source files but never as pollution. Some of the standard pollution in is implemented by including . This is now excessive and results in declaring all standard integer types (which is permitted to declare) and some macros (WCHAR_MAX, WCHAR_MIN, and sometimes RSIZE_MAX which depends on SIZE_MAX which is not defined via pollution) which is not permitted to declare. The extras for the standard integer types are not even under __BSD_VISIBLE. The 6 includes of seem to be just style bugs for using uint64_t. Even FreeBSD-4 declares both u_int64_t and uint64_t. Also, most includes of including all the ones in msun are excessive. Standard integer types are declared in . includes and adds mistakes like PRI* support and non-mistakes like prototypes for strto[u]imax(). msun now uses (signed) int32_t a lot, and this depends on more than the old u_foo_t pollution in , so msun has required FreeBSD features for a long time and is less portable than fdlibm. Including and changing all the u_foo_t's to ufoo_t's would be a lot of churn and would break portability to C90. should be included in at most math.private.h and math_private.h should provide consistent spellings more like ufoo_t than u_foo_t Bruce From owner-freebsd-numerics@freebsd.org Mon Jan 14 14:35:58 2019 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 4840014A190C for ; Mon, 14 Jan 2019 14:35:58 +0000 (UTC) (envelope-from brde@optusnet.com.au) Received: from mail105.syd.optusnet.com.au (mail105.syd.optusnet.com.au [211.29.132.249]) by mx1.freebsd.org (Postfix) with ESMTP id B38248AC0E; Mon, 14 Jan 2019 14:35:56 +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 mail105.syd.optusnet.com.au (Postfix) with ESMTPS id 96C5D1052E23; Tue, 15 Jan 2019 01:35:45 +1100 (AEDT) Date: Tue, 15 Jan 2019 01:35:42 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: Steve Kargl cc: Pedro Giffuni , freebsd-numerics@freebsd.org Subject: Re: New math library from ARM In-Reply-To: <20181231152230.GC823@troutmask.apl.washington.edu> Message-ID: <20190115005528.H1450@besplex.bde.org> References: <797a7755-db93-1b9c-f3b9-8850d948e098@FreeBSD.org> <20181231151904.GB823@troutmask.apl.washington.edu> <20181231152230.GC823@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=DZtnkrlW c=1 sm=1 tr=0 a=PalzARQSbocsUSjMRkwAPg==:117 a=PalzARQSbocsUSjMRkwAPg==:17 a=kj9zAlcOel0A:10 a=XkRKQH6RAAAA:8 a=nZ40scU-AAAA:20 a=UhYP2Ixlx5ZvnBeClZwA:9 a=CjuIK1q_8ugA:10 a=1gUyE30hU_ULiMxJiLUW:22 X-Rspamd-Queue-Id: B38248AC0E X-Spamd-Bar: ------ Authentication-Results: mx1.freebsd.org; spf=pass (mx1.freebsd.org: domain of brde@optusnet.com.au designates 211.29.132.249 as permitted sender) smtp.mailfrom=brde@optusnet.com.au X-Spamd-Result: default: False [-6.15 / 15.00]; ARC_NA(0.00)[]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; RCVD_IN_DNSWL_LOW(-0.10)[249.132.29.211.list.dnswl.org : 127.0.5.1]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[3]; R_SPF_ALLOW(-0.20)[+ip4:211.29.132.0/23]; FREEMAIL_FROM(0.00)[optusnet.com.au]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(0.00)[optusnet.com.au]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_SOME(0.00)[]; MX_GOOD(-0.01)[cached: extmail.optusnet.com.au]; NEURAL_HAM_SHORT(-0.78)[-0.780,0]; IP_SCORE(-3.06)[ip: (-7.83), ipnet: 211.28.0.0/14(-4.16), asn: 4804(-3.29), country: AU(-0.04)]; RCVD_NO_TLS_LAST(0.10)[]; FROM_EQ_ENVFROM(0.00)[]; R_DKIM_NA(0.00)[]; FREEMAIL_ENVFROM(0.00)[optusnet.com.au]; ASN(0.00)[asn:4804, ipnet:211.28.0.0/14, country:AU]; MIME_TRACE(0.00)[0:+]; 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: Mon, 14 Jan 2019 14:35:58 -0000 On Mon, 31 Dec 2018, Steve Kargl wrote: > On Mon, Dec 31, 2018 at 07:19:04AM -0800, Steve Kargl wrote: >> On Mon, Dec 31, 2018 at 10:06:57AM -0500, Pedro Giffuni wrote: >>> Hi; >>> >>> Just noted a recent initiative from musl-libc: >>> >>> https://www.openwall.com/lists/musl/2018/12/08/1 >>> >>> It appears they plan to replace their (FreeBSD) math code with a new ARM >>> implementation: >>> >>> https://github.com/ARM-software/optimized-routines >> >> The Copyright on this code is unclear. For example, in >> single/e_rem_pio2.c lines 1-6: >> >> /* >> * e_rem_pio2.c >> * >> * Copyright (c) 1999-2018, Arm Limited. >> * SPDX-License-Identifier: MIT >> */ >> >> Then lines 16-18: >> >> /* >> * Simple cases: all nicked from the fdlibm version for speed. >> */ >> >> The original fdlibm licenses applies ot the nicked lines. Really? The fdlibm version is quite slow, especially for simple cases. In FreeBSD, most of the optimizations were written by me, especially for "simple" cases: - arrange not to call here for |arg| < Pi/4 - special optiimizations for |arg| < 9*PI/4 (1 case for every pair of quadrants. These optimizations are fairly generic. - special optimizations for "medium" args. These optimizations are mostly to to hide the high latency of float to integer conversions on older i386 x86's. Lots of functions use similar code with many ifdefs. My current version has the details for this in inline functions in math_private.g It is possible to do better for arches with extra precision, but this is not done and is still too hard for i386 on FreeBSD since extra precision is unavailable by default, and gcc and clang have different bugs in their support for extra precision. But all of these optimizations work very well for newer x86's with newer compilers. This is because newer x86's and compilers have lower latency and/or better scheduling. I don't know what is best for arm. > There is also some interesting uses of float literal constants > with 80 digits when at most 9 are relevant. That might be to inspire (negative) confidence :-). Why does the arm e_rem_pio2.c even have any float constants? The fdlibm version has tables of small hex constants representing high-precision FP constants. FreeBSD moved these tables to k_rem_pio2.c. IIRC, these constants are loaded as FP values and the can probably be optimized better using not float constants more directly, or better double constants more directly. These tables are only used for large args, and the fdlibm code is quite slow for large args, but FreeBSD doesn't optimize this case. I used to think that x86 hardware handled this case much better than the slow fdlibm code, but on newer x86 the fdlibm code is sometimes faster than the hardware. On older x86, the hardware was only a few times faster. Versions optimized for extended precision would use some long double constants in e_rem_pio2.c. e_rem_pio2f.c already uses extra precision by using double precision for almost everything. However, on newer x86, this class of optimizations is barely worth doing, since the more generic code in e_rem_pio2.c is fast enough (the throughput is 1 cos() per 20-30 cycles on modern x86). Bruce From owner-freebsd-numerics@freebsd.org Mon Jan 14 15:05:03 2019 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 9D94114A24F6 for ; Mon, 14 Jan 2019 15:05:03 +0000 (UTC) (envelope-from pfg@FreeBSD.org) Received: from sonic316-13.consmr.mail.bf2.yahoo.com (sonic316-13.consmr.mail.bf2.yahoo.com [74.6.130.123]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id C5FCA8BA6A for ; Mon, 14 Jan 2019 15:05:02 +0000 (UTC) (envelope-from pfg@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1547478301; bh=NqN7qHCvbyu6VaXZ6APTtAtVMMqWPbtG3M/qXwMpFyU=; h=Subject:To:Cc:References:From:Date:In-Reply-To:From:Subject; b=agL/LeWy6lN/M8tQpUxrXN44X05c5WsYRFoN0FkfgEhKlCurCk9+ymi/00iJohonZW9hmBd35a+Inew1u4s1hXC/+lnDPRLxyWINMNW67i/HrnQtBuOIohFzAasCi7NROAlpYeK4AYzDC3G7bMVZuycERzxLPHWJDBJBV3dzWthdwfZBmVp/oe9rAy0zFarolGI1rri16P9bj9sL0UyFw6S6CAhbdK6nPcJsKYpOXClQpT6unXCgwsbl9S0uZazMhxpTTj+6kLNDLfPSMDVJiHFoY2z9D2oAdgZP3Zon10nNNtqImoGp+4qidIKbHGs1hVVTzPBCZQfm2ZsLTdAqAA== X-YMail-OSG: DDah2KAVM1mAnOSvac_dJtu0UwYzJwVfFiv.2oy3le57OPc4FrIyj6f4nNXFwd_ oiqSDhp77t7Hawp2cwMJH28IWf7z3FVZxXy0JZMFCN7BQPUHAYGl05oint_jAvzbkUxJj4TjxkkU zX0Hv72WRiUB3u8AuAz8dLWbpevbJl3hQqP4l6KKRL83Bb6.IllH.GhDFQKtFbDUi5qiF1NXjrez EGx1JHu.TQkJStGkSW3Em0q1IZofBnQuyEUa8Dq034iJ52MZHYckpf9OwbalwCqRwmsISFmS223A vv0_FUXmjAHJW9F5IwZVIpfLpIEC1vFRce3xxzUZbBWkZacntwC.2Ew93KBOLTIyT_aiK7VPZpzQ VOAJfqU9.twxdJelWNm3MCTVVxyz6o6E.cEC2E3Klra53mg18BTAhbnnwyuElk4zI6Csoot5gWVN xsIq4hYgeXjTXqXvxUiIidzigsvYF81hK7j6h8j040I8r.TFr1ulNHcWITA.xa.lXFJPSu4az_Mi L8I7IFd6GM7IXBLiPkOxAbkPaX539taundgzxCUKLSAbPaKqnykPRQW__LAL3eGkG8aFUPH6KhW9 Kaimx44rCHmvgvyqYEoeueYm8J9r0.V8MdgWtUPA_5l1F0b8vvFN7O4VQpE4i529_f0MxwAYYWqB TvoWLmssJHWf5SdONKwafXDEp2n5v7vViACQwZf8EJqFb6YiGtAL5PXog7gkjLqhbgxxuNc3tB6h lvAAZWDZALRWnemwl0yvajathjjxM4nJcogS6ByJkLbUGA9txjhOnWOXB1WatvOmygltgvAedCSz HAxXOjHUIanXYQdJRyWJJPs2BfFKW9rOUkEx.3QI_0opX0gR0FmZ.ypgA4tmGw7X5gzr4om8VxQa Fwul3s3dJ4QBfWLu0Q5S.mmLYvH6zMwW2v1DiLi93rFL88tAp1bryrfqc4JQmDevrVgEpuzlUBM8 nzkaY6BAAy33DxDGj3.lUs212SL.SQuy54jO1MGW8vEglghff5zBvWvOOYVYv.8yfZZvLt7geP46 TTg888I925Ql3IXtVFbigSjOSrbtcP2obYklTDC.vqw-- Received: from sonic.gate.mail.ne1.yahoo.com by sonic316.consmr.mail.bf2.yahoo.com with HTTP; Mon, 14 Jan 2019 15:05:01 +0000 Received: from 181.52.72.201 (EHLO [192.168.0.5]) ([181.52.72.201]) by smtp424.mail.bf1.yahoo.com (Oath Hermes SMTP Server) with ESMTPA ID ded112821fa4e84f06a8547ab2ce0e2a; Mon, 14 Jan 2019 15:05:00 +0000 (UTC) Subject: Re: Undefined Behavior in lib/msun/src/e_pow.c (was Re: New math library from ARM) To: Bruce Evans Cc: sgk@troutmask.apl.washington.edu, freebsd-numerics@freebsd.org References: <797a7755-db93-1b9c-f3b9-8850d948e098@FreeBSD.org> <20181231151904.GB823@troutmask.apl.washington.edu> <20181231152230.GC823@troutmask.apl.washington.edu> <06c8b6a2-ed26-f255-3947-c79b593a9dea@FreeBSD.org> <20190101045425.GA5767@troutmask.apl.washington.edu> <20190114231414.K1062@besplex.bde.org> From: Pedro Giffuni Message-ID: <6de27877-aad0-71f3-e118-25174a69b9b1@FreeBSD.org> Date: Mon, 14 Jan 2019 10:05:00 -0500 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 MIME-Version: 1.0 In-Reply-To: <20190114231414.K1062@besplex.bde.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-US X-Rspamd-Queue-Id: C5FCA8BA6A X-Spamd-Bar: -- Authentication-Results: mx1.freebsd.org X-Spamd-Result: default: False [-2.99 / 15.00]; local_wl_from(0.00)[FreeBSD.org]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; NEURAL_HAM_SHORT(-0.99)[-0.994,0]; ASN(0.00)[asn:26101, ipnet:74.6.128.0/21, country:US]; 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: Mon, 14 Jan 2019 15:05:04 -0000 On 1/14/19 7:52 AM, Bruce Evans wrote: > On Tue, 1 Jan 2019, Pedro Giffuni wrote: > >> On 31/12/2018 23:54, Steve Kargl wrote: >>> On Mon, Dec 31, 2018 at 10:32:06PM -0500, Pedro Giffuni wrote: >>>> Hmm ... >>>> >>>> Looking at the changes in musl's libc I found this issue which seems >>>> real (although somewhat theoretical): >>>> >>>> https://git.musl-libc.org/cgit/musl/commit/src/math?id=688d3da0f1730daddbc954bbc2d27cc96ceee04c >>>> >>>> >>>> Is the attached patch acceptable? >>>> >>>> Also, their code is bit different here: >>>> >>>> https://git.musl-libc.org/cgit/musl/commit/src/math?id=282b1cd26649d69de038111f5876853df6ddc345 >>>> >>>> >>>> but we may also have to check fmaf(-0x1.26524ep-54, -0x1.cb7868p+11, >>>> 0x1.d10f5ep-29). >>>> >>>> Cheers, >>>> >>>> Pedro. >>>> >>>> Index: lib/msun/src/e_pow.c >>>> =================================================================== >>>> --- lib/msun/src/e_pow.c    (revision 342665) >>>> +++ lib/msun/src/e_pow.c    (working copy) >>>> @@ -130,6 +130,7 @@ >>>>       if(hx<0) { >>>>           if(iy>=0x43400000) yisint = 2; /* even integer y */ >>>>           else if(iy>=0x3ff00000) { >>>> +        uint32_t j;    /* Avoid UB in bit operations below. */ >>>>           k = (iy>>20)-0x3ff;       /* exponent */ >>>>           if(k>20) { >>>>               j = ly>>(52-k); > > I was away. > > I see you committed a better version (with a cast). > Yes, I did what seemed to be the least invasive change, but then the problem with duct tape is that it may work well enough to forget about the issue. I haven't MFC'd it while you guys decided on a better solution. > The correct fix is more like the changing the file scope i and j from > int32_t > to u[_]int32_t.  j is mostly used as a temporary to hold pure bits.  > Its top > bit is usually not set, so plain int32_t works for it.  The only other > place > where its top bit can obviously be set is in an EXTRACT_WORDS(j,i,z).  > Then > both j and i can have their top bit set.  EXTRACT_WORDS() into h[xy] and > l[xy] is also sloppy.  There l[xy] is unsigned, but h[xy] is signed.  The > top bit in the high word is soon discarded using ix = hx&0x7fffffff, etc. > Later, the sign is tested using hx<0 and this is the only excuse for hx > being signed.  fdlibm does this quite often.  It is a manual optimization > for ~30-40 year old compilers that couldn't turn (hx&8000000) != 0 into a > sign test iff the sign test is optimal. > The duct-tape cast still looks good enough ;). > Other style bugs in the above: > >>> I'll defer to Bruce on this.  My only comments are >>> 1) declarations belong at the top of the file where all declarations >>> occur > > 1a) missing blank line after declaration. > >> Modern standards let you declare variables within blocks. For style >> we do prefer to start the function with them but in this case we can't. > > K&R 1978 C allows declaring variables within blocks. > > You can't declare j again in function scope since it is already there > with > a different type. > >>> 2) j is already declared as int32_t >> And it has to be a signed integer: we later check for negative values. > > I think that is only when j is misused later for EXTRACT_WORDS(). > > 2a,2b) Redeclaring j with a different type in an inner block is an even > larger style bug/obfuscation than declaring a new variable or redeclaring > j with the same type there.  Redeclaring shadows it and this bug is > detected by Wshadow.  Redeclaring it with a different type (as needed to > work) is especially obscure shadowing. > >>> 3) uint32_t should be written as u_int32_t. >> >> No, uint32_t is the standard type, u_int32_t is a BSDism. Also, the >> file consistently uses uint32_t. > > No, see previous replies.  3) is correct. > Yes, I acknowledged this. I was looking at the musl version which replaced all the u_int32_t's. >>> Are you sure that UB occurs?  Or, is this an attempt to >>> placate a static analysis tool that only see shifting of >>> a signed type?  Do you need to make a similar change to >>> e_powf.c? >> >> The point of the Undefined Behavior is precisely that it doesn't >> occur: we are lucky and the compiler behaves as it always has but the >> standard will let a different compiler behave differently and then we >> will have surprises. > > No, UB does occur, but is harmless.  ly is unsigned and can have its top > bit set.  j=ly>>(52-k) shifts right a few bits so doesn't overflow on > assignment to signed j.  But then j<<(52-k) gives UB attempting to > recover > the top bit of ly gives UB in all cases where the top bit is nonzero. > > The else clause doesn't have this problem, since it shifts iy instead > of ly > and iy never has its top bit set. > > e_powf.c doesn't have this problem, since there is only 1 32-bit word for > float precision and it is handled like the top word for double precision > (only its mantissa bits are shifted). > > However, it is easier to use unsigned shifts than to see that signed > shifts > have defined behaviour.  musl did well to only detect and/or fix the 1 > case > where UB behaviour clearly occurs. > Thanks for the feedback! For now I would prefer we focus more on whatever the ARM lib does better. Pedro. From owner-freebsd-numerics@freebsd.org Mon Jan 14 15:19:38 2019 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 8A03914A2805 for ; Mon, 14 Jan 2019 15:19:38 +0000 (UTC) (envelope-from pfg@FreeBSD.org) Received: from sonic308-3.consmr.mail.bf2.yahoo.com (sonic308-3.consmr.mail.bf2.yahoo.com [74.6.130.42]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 010128BF4E for ; Mon, 14 Jan 2019 15:19:37 +0000 (UTC) (envelope-from pfg@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1547479171; bh=FDFuIL6TdjXOCwD+b5358NTtDsHU3+TJMMpz7oSgxzM=; h=Subject:To:Cc:References:From:Date:In-Reply-To:From:Subject; b=UY5ByJuKLo0ojgHBYcd/JJZAzWgRFVBG6VhgK7gEWuGfmK1/QyJhqDx7F/L7njD3abKVHIIqy1eRWK4JM8kc5FhGaUyZJFloNViS79ioLrgRifuhAH0XAG5CuMeFA5ZrIwTGpo3p4oTo2ju9tiMK8yklGK8JjDVtXnl4LkcauaW5gl7cRB8pp0P7/ahlv13FjH+ruZn9R8PKSXPrUGsdBcrTpRNkaactt+pGWrptE+00pTBRsJQlApcjxx3LaaaGZfAquggy3XiT6H+Pt1ri5RsVVKKrR3KHO0xBeoKdiUYA/Ax+GtuD5+PLa35IwoweHzPSEqS1ibdEzyEDpTatrQ== X-YMail-OSG: QWOEvvsVM1ln_rY67_7.4whWzzQaejq5FavQ4E9k6ByisGzKFt.9hIrGNDMuIuc cuojZfh9UQyM7jgKVFzsrTSFANTj8rOO6hPhWDqppxWzMJ_YmX.6OSfROTOgwxntRfrMmES60EUy oFWbP90XXPjossa3RubLJRxyX6JrQmPY4uvUu4sP87qcV1VWCnWCGZpIl5EFAASABRc87NQYArH6 HaBP8RKe7Fy4VKMRPI9PS1nV4s6748inRz.Trm9tNFbfXvV_5v_CibSvar0eXYgY6Y3JtQcsJD6v mZ2dlv9stph1IUjTyE_s8IqJdIIElfDmPoLUkvqgCZTsYx2QqEbUF9iBOP6J8Yl_XbNAv2TCFNtK iwxtyTPFqVEUv5snSBbnIxa9nyryzIX0XmVM9556ME46rtewsfIe1vkwmfAfGtLpMIvDMfDGmJbr ThTUiX2N3AxN7OCqcg_RGFNHj2MKWeKax.n8A_iKV8JeXhwxK239rPVaBu4Fh3jwjdKs7gmN0opX ObK4T91SI7D6pFm1hXIURerqXVeqDvDMTfTswLu0YFy3ZzgnMVspMoEDZSPgBHFltovQWLO5DNgo YOS14ShsurmkUtjPdeWk6lSDUb8J1dst7kPS2OtrKDVzWwhATYJDglnUUG8lCNjSrFETdVCi5H1y Ot8AObZRm5Iq1WKWO8uSASmISoMvPZhKyHq6yPEJWnE08vXzLrjLB7m73qfi4XwAnrpDDyHmiCCE 6vXb_ZrZbKQw9J0b06yHMViZ4Hb8wBcMB9fWC0DKsLgeYxaGmF_hmJtmoOo_oplopmm5LfvJNg7l _xhJbNxYlTTjgUcKMKnVxegzkCz0L.jIBLpD.lg3V5WC8nVlhp_6WA.u4a61CUgUfs0wwfDqhaFQ JlGGrqtT2Lb.A_HAkBtpjO6CLlvt4tr_2w9GOcjXdDfAaTbY6ZLy5xh49IPtKZwp3GhT6wT8vGr3 unTkRTzZR5ZScPbeJoDBWhNuA84MMM3XAfPi0qHBqyK2SjOXmlnt4dAZefcwQEY9iJAIxkhriLKv zYazyhAlTdre.y9nuHzw7iC2prz3kn.bOcI3oKgbVmg-- Received: from sonic.gate.mail.ne1.yahoo.com by sonic308.consmr.mail.bf2.yahoo.com with HTTP; Mon, 14 Jan 2019 15:19:31 +0000 Received: from 181.52.72.201 (EHLO [192.168.0.5]) ([181.52.72.201]) by smtp424.mail.bf1.yahoo.com (Oath Hermes SMTP Server) with ESMTPA ID 1d2b2dbabf4b9b5baef4c98bbe141344; Mon, 14 Jan 2019 15:19:26 +0000 (UTC) Subject: Re: New math library from ARM To: sgk@troutmask.apl.washington.edu Cc: freebsd-numerics@freebsd.org References: <797a7755-db93-1b9c-f3b9-8850d948e098@FreeBSD.org> <20181231151904.GB823@troutmask.apl.washington.edu> <20181231152230.GC823@troutmask.apl.washington.edu> From: Pedro Giffuni Message-ID: Date: Mon, 14 Jan 2019 10:19:27 -0500 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 MIME-Version: 1.0 In-Reply-To: <20181231152230.GC823@troutmask.apl.washington.edu> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Content-Language: en-US X-Rspamd-Queue-Id: 010128BF4E X-Spamd-Bar: -- Authentication-Results: mx1.freebsd.org X-Spamd-Result: default: False [-2.98 / 15.00]; local_wl_from(0.00)[FreeBSD.org]; NEURAL_HAM_MEDIUM(-1.00)[-1.000,0]; NEURAL_HAM_SHORT(-0.98)[-0.985,0]; NEURAL_HAM_LONG(-1.00)[-1.000,0]; ASN(0.00)[asn:26101, ipnet:74.6.128.0/21, country:US] 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: Mon, 14 Jan 2019 15:19:38 -0000 On 12/31/18 10:22 AM, Steve Kargl wrote: > On Mon, Dec 31, 2018 at 07:19:04AM -0800, Steve Kargl wrote: >> On Mon, Dec 31, 2018 at 10:06:57AM -0500, Pedro Giffuni wrote: >>> Hi; >>> >>> Just noted a recent initiative from musl-libc: >>> >>> https://www.openwall.com/lists/musl/2018/12/08/1 >>> >>> It appears they plan to replace their (FreeBSD) math code with a new ARM >>> implementation: >>> >>> https://github.com/ARM-software/optimized-routines >>> >> The Copyright on this code is unclear. For example, in >> single/e_rem_pio2.c lines 1-6: >> >> /* >> * e_rem_pio2.c >> * >> * Copyright (c) 1999-2018, Arm Limited. >> * SPDX-License-Identifier: MIT >> */ >> >> Then lines 16-18: >> >> /* >> * Simple cases: all nicked from the fdlibm version for speed. >> */ >> >> The original fdlibm licenses applies ot the nicked lines. >> FWIW, I opened a ticket about the license issue. > There is also some interesting uses of float literal constants > with 80 digits when at most 9 are relevant. > I noticed, and really like, that they have a testsuite that Android's bionic just merged: https://android.googlesource.com/platform/external/arm-optimized-routines/+/4ced35fcfcda5baddd092390103b7370827b9429 Pedro.