[Bug libstdc++/110860] New: std::format("{:f}",2e304) invokes undefined behaviour

[Bug libstdc++/110860] New: std::format("{:f}",2e304) invokes undefined behaviour

[gcc at pauldreik dot se]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

            Bug ID: 110860
           Summary: std::format("{:f}",2e304) invokes undefined behaviour
           Product: gcc
           Version: 13.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gcc at pauldreik dot se
  Target Milestone: ---

The following program, compiled with gcc 13.2:

#include <format>
#include <cstdio>

int main() {
std::puts(std::format("{:f}",2e304).c_str());
}

causes ubsan to warn:
/opt/compiler-explorer/gcc-13.2.0/include/c++/13.2.0/format:1489:52: runtime
error: negation of -2147483648 cannot be represented in type 'int'; cast to an
unsigned type to negate this value to itself

I believe the problem is using __builtin_abs() which uses integer, but is fed a
double.


Link to reproducer:

https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:1,endLineNumber:6,positionColumn:1,positionLineNumber:6,selectionStartColumn:1,selectionStartLineNumber:6,startColumn:1,startLineNumber:6),source:'%23include+%3Cformat%3E%0A%23include+%3Ccstdio%3E%0A%0Aint+main()+%7B%0Astd::puts(std::format(%22%7B:f%7D%22,2e304).c_str())%3B%0A%7D'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:33.333333333333336,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g132,deviceViewOpen:'1',filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'0',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-std%3Dgnu%2B%2B2b+-fsanitize%3Daddress,undefined,leak+-g',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+13.2+(Editor+%231)',t:'0')),k:33.333333333333336,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:output,i:(editorid:1,fontScale:14,fontUsePx:'0',j:1,wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+gcc+13.2+(Compiler+%231)',t:'0')),k:33.33333333333333,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-07-31

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed. This code definitely looks questionable:
                __guess += max((int)__builtin_log10(__builtin_abs(__v)) / 2,
1);


So in this case, most likely the author of the above code thought __builtin_abs
was type generic rather than takes an integer type.

The reason why I say that is because below we have:
          if (!__builtin_signbit(__v))


Most likely __builtin_abs(__v) should be replaced with `(__builtin_signbit(__v)
? -__v : __v)` (which does get optimized to just `ABS_EXPR` internally.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
             Status|NEW                         |ASSIGNED
   Target Milestone|---                         |13.3

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Well it should be generic like std::and grumble grumble

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
std::abs

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
__builtin_log10 isn't generic either. I was hoping to avoid including all of
<cmath> here, which is why I used the built-ins.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:bb3ceeb6520c13fc5ca08af7d43fbd3f975e72b0

commit r14-3069-gbb3ceeb6520c13fc5ca08af7d43fbd3f975e72b0
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Aug 7 15:30:03 2023 +0100

    libstdc++: Fix incorrect use of abs and log10 in std::format [PR110860]

    The std::formatter implementation for floating-point types uses
    __builtin_abs and __builtin_log10 to avoid including all of <cmath>, but
    those functions are not generic. The result of abs(2e304) is -INT_MIN
    which is undefined, and then log10(INT_MIN) is NaN. As well as being
    undefined, we fail to grow the buffer correctly, and then loop more
    times than needed to allocate a buffer and try formatting the value into
    it again.

    We can use if-constexpr to choose the correct form of log10 to use for
    the type, and avoid using abs entirely. This avoids the undefined
    behaviour and should mean we only reallocate and retry std::to_chars
    once.

    libstdc++-v3/ChangeLog:

            PR libstdc++/110860
            * include/std/format (__formatter_fp::format): Do not use
            __builtin_abs and __builtin_log10 with arbitrary floating-point
            types.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:a059403794add2934961780662e320ba77798a7e

commit r13-7699-ga059403794add2934961780662e320ba77798a7e
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Aug 7 15:30:03 2023 +0100

    libstdc++: Fix incorrect use of abs and log10 in std::format [PR110860]

    The std::formatter implementation for floating-point types uses
    __builtin_abs and __builtin_log10 to avoid including all of <cmath>, but
    those functions are not generic. The result of abs(2e304) is -INT_MIN
    which is undefined, and then log10(INT_MIN) is NaN. As well as being
    undefined, we fail to grow the buffer correctly, and then loop more
    times than needed to allocate a buffer and try formatting the value into
    it again.

    We can use if-constexpr to choose the correct form of log10 to use for
    the type, and avoid using abs entirely. This avoids the undefined
    behaviour and should mean we only reallocate and retry std::to_chars
    once.

    libstdc++-v3/ChangeLog:

            PR libstdc++/110860
            * include/std/format (__formatter_fp::format): Do not use
            __builtin_abs and __builtin_log10 with arbitrary floating-point
            types.

    (cherry picked from commit bb3ceeb6520c13fc5ca08af7d43fbd3f975e72b0)

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 13.3, thanks for the report.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[gcc at pauldreik dot se]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #8 from Paul Dreik <gcc at pauldreik dot se> ---
I do unfortunately not think the fix is entirely correct.

When 0 is passed, log10 returns -inf, which can not be converted to an integer.

I had a bit of problem to reproduce this with gcc, but it worked with clang.
The following program:

#include <cstdio>
#include <format>
#include <string_view>

int main(int argc, char* argv[]) {
    [[maybe_unused]] auto x = std::format("{:.292f}", 0.f);
}

causes the following output when compiled with clang-16 using
-fsanitize=undefined -fno-sanitize-recover=all -g -O0:

/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/14.0.0/../../../../include/c++/14.0.0/format:1496:15:
runtime error: -inf is outside the range of representable values of type
'unsigned long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior
/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/14.0.0/../../../../include/c++/14.0.0/format:1496:15
in 

Link to reproducer (expected to go stale quick, had to use clang trunk to get a
sufficiently new libstdc++): https://godbolt.org/z/8aGf7YGWs

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|FIXED                       |---
             Status|RESOLVED                    |REOPENED

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Gah!

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
GCC's ubsan doesn't seem to diagnose this rule:

"A prvalue of a floating-point type can be converted to a prvalue of an integer
type. The conversion truncates; that is, the fractional part is discarded. The
behavior is undefined if the truncated value cannot be represented in the
destination type."

There's no ubsan diagnostic for:

unsigned long i = -HUGE_VAL;

So it doesn't complain about adding log10(0) to a size_t.

I can reproduce it with Clang though, and have tested a fix.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:9e33d71834416b7eddadae2b0f68e85f04cd0c7f

commit r14-3159-g9e33d71834416b7eddadae2b0f68e85f04cd0c7f
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Aug 11 18:10:29 2023 +0100

    libstdc++: Do not call log10(0.0) in std::format [PR110860]

    Calling log10(0.0) returns -inf which has undefined behaviour when
    converted to an integer. We only need to use log10 for large values
    anyway. If the value is zero then the larger buffer is only needed due
    to a large precision, so we don't need to use log10 to estimate the
    number of digits for the significand.

    libstdc++-v3/ChangeLog:

            PR libstdc++/110860
            * include/std/format (__formatter_fp::format): Do not call log10
            with zero values.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[gcc at pauldreik dot se]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #12 from Paul Dreik <gcc at pauldreik dot se> ---
The last fix is unfortunately not sufficient either, because for abs(__v)<1
log10 becomes negative and that wont convert gracefully to size_t.

I implemented the following fix, which avoids log10 and uses frexp instead
since we
only need an approximation anyway. That also removes the need for handling the
sign.

The magic constant 4004U / 13301U is obtained from Gnu Octave rats(log10(2),11)
which I chose because it is slightly conservative. I think integer math is good
here, to avoid conversions.

I experimented with bitwise fiddling to get the exponent but I think that is
less portable and readable than frexp. It does however avoid a function call to
frexp and is twice as fast (I benchmarked it).

What do you think of the following patch?

commit a7b133fb073ebd7f6ba686f31530ed20d656bd57
Author: Paul Dreik <github@pauldreik.se>
Date:   Sat Aug 12 13:16:30 2023 +0200

    libstdc++: Avoid problematic use of log10 in std::format [PR110860]

    If abs(__v) is smaller than one, the result will be on the
    form 0.xxxxx. It is only if the magnitude is large that more digits
    are needed before the decimal dot.

    This uses frexp instead of log10 which should be less expensive
    and have sufficient precision for the desired purpose.

    It removes the problematic cases where log10 will be negative or not
    fit in an int.

diff --git a/libstdc++-v3/include/std/format b/libstdc++-v3/include/std/format
index 23da6b008..8d147abe9 100644
--- a/libstdc++-v3/include/std/format
+++ b/libstdc++-v3/include/std/format
@@ -1490,14 +1490,22 @@ namespace __format
              // If the buffer is too small it's probably because of a large
              // precision, or a very large value in fixed format.
              size_t __guess = 8 + __prec;
-             if (__fmt == chars_format::fixed && __v != 0) // +ddd.prec
+             if (__fmt == chars_format::fixed) // +ddd.prec
                {
-                 if constexpr (is_same_v<_Fp, float>)
-                   __guess += __builtin_log10f(__v < 0.0f ? -__v : __v);
-                 else if constexpr (is_same_v<_Fp, double>)
-                   __guess += __builtin_log10(__v < 0.0 ? -__v : __v);
-                 else if constexpr (is_same_v<_Fp, long double>)
-                   __guess += __builtin_log10l(__v < 0.0l ? -__v : __v);
+                 if constexpr (is_same_v<_Fp, float> || is_same_v<_Fp, double>
|| is_same_v<_Fp, long double>)
+                   {
+                     // the number of digits to the left of the decimal point
+                     // is floor(log10(max(abs(__v),1)))+1
+                     int __exp{};
+                     if constexpr (is_same_v<_Fp, float>)
+                       __builtin_frexpf(__v, &__exp);
+                     else if constexpr (is_same_v<_Fp, double>)
+                       __builtin_frexp(__v, &__exp);
+                     else if constexpr (is_same_v<_Fp, long double>)
+                       __builtin_frexpl(__v, &__exp);
+                     if (__exp>0)
+                       __guess += 1U + __exp * 4004U / 13301U; // log10(2)
approx.
+                   }
                  else
                    __guess += numeric_limits<_Fp>::max_exponent10;
                }

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Oh dear, I should stop trying to do so many things at once. I did consider
using __v < some_constant because we only need that code for large values, not
for 0 and not for anything less than 1. We could maybe use
numeric_limits<Fp>::digits10 or something like that.

Your approach looks good though. I'm not sure if frexpf and frexpl are
universally supported on all targets we care about, but maybe they're present
on all targets where our std::to_chars is enabled.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
That portability concern already applied to log10f and log10l anyway.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #15 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Hi Paul, could you please submit the patch to the gcc-patches mailing list for
formal review, CCing the libstdc++@gcc.gnu.org list?

Please either complete a copyright assignment to the FSF or use DCO sign-off as
per https://gcc.gnu.org/dco.html so that we can use your patch in GCC.

Thanks!

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #16 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:2d2b05f0691799f03062bf5c436462f14cad3e7c

commit r14-3202-g2d2b05f0691799f03062bf5c436462f14cad3e7c
Author: Paul Dreik <gccpatches@pauldreik.se>
Date:   Mon Aug 14 15:42:33 2023 +0100

    libstdc++: Avoid problematic use of log10 in std::format [PR110860]

    If abs(__v) is smaller than one, the result will be of the
    form 0.xxxxx. It is only if the magnitude is large that more digits
    are needed before the decimal dot.

    This uses frexp instead of log10 which should be less expensive
    and have sufficient precision for the desired purpose.

    It removes the problematic cases where log10 will be negative or not
    fit in an int.

    Signed-off-by: Paul Dreik <gccpatches@pauldreik.se>

    libstdc++-v3/ChangeLog:

            PR libstdc++/110860
            * include/std/format (__formatter_fp::format): Use frexp instead
            of log10.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #17 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:559341b5b5a30448362f3f205cd1bf043a919945

commit r13-7722-g559341b5b5a30448362f3f205cd1bf043a919945
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Aug 11 18:10:29 2023 +0100

    libstdc++: Avoid problematic use of log10 in std::format [PR110860]

    If abs(__v) is smaller than one, the result will be of the
    form 0.xxxxx. It is only if the magnitude is large that more digits
    are needed before the decimal dot.

    This uses frexp instead of log10 which should be less expensive
    and have sufficient precision for the desired purpose.

    It removes the problematic cases where log10 will be negative or not
    fit in an int.

    Signed-off-by: Paul Dreik <gccpatches@pauldreik.se>

    libstdc++-v3/ChangeLog:

            PR libstdc++/110860
            * include/std/format (__formatter_fp::format): Use frexp instead
            of log10.

    (cherry picked from commit 2d2b05f0691799f03062bf5c436462f14cad3e7c)

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #18 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Should be fixed for real now. Thanks for the report and the patch.

Looks like I managed to mess up the authorship of the gcc-13 backport though
(because I squashed together my incorrect commit and your correct one for the
backport). I'll fix it in the ChangeLog file after that is regenerated
overnight, but it will stay wrong in Git. Sorry.

[Bug libstdc++/110860] std::format("{:f}",2e304) invokes undefined behaviour

[gcc at pauldreik dot se]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110860

--- Comment #19 from Paul Dreik <gcc at pauldreik dot se> ---
Thanks Jonathan!
I am happy to count myself as a gcc contributor now :-D

Never mind the tiny git mistake, that will be forgotten once gcc 14 is out!