Shell arithmetic handles integers as floats, breaking integer arithmetic

[McDutchie]

The C standard says (1, 2):

When a value of integer type is converted to a real floating type, if the value being converted can be represented exactly in the new type, it is unchanged. If the value being converted is in the range of values that can be represented but cannot be represented exactly, the result is either the nearest higher or nearest lower representable value, chosen in an implementation-defined manner. If the value being converted is outside the range of values that can be represented, the behavior is undefined.

Thing is, ksh internally typecasts all values for shell arithmetic to Sfdouble_t, a.k.a. _ast_fltmax_t as derived by the features/float test, i.e., the system's maximum-size float type.

So, all arithmetic is internally done with long double or double values (depending on the system). See streval.c and arith.c. This breaks long integers, as their values may be too large to be represented exactly by the Sfdouble_t type, in which case we hit the implementation-defined behaviour case and the number will be somehow approximated. This is disastrous, because integer calculations that remain within type range must always be exact.

The problem is particularly terrible on ARM systems, whose hardware does not support long double, so Sfdouble_t is double. E.g., on my Mac with an M1 processor:

$ getconf LLONG_MAX
9223372036854775807
$ typeset -lui i=9223372036854775807   # long unsigned int; this value should be only half its max
$ echo $i 
9223372036854775807
$ echo $((i - 1))
9223372036854775807
$ echo $((i - 2))
9223372036854775807
$ echo $((i - 100))
9223372036854775807
$ echo $((i - 1000))
9223372036854774784
$ echo $((i - 100000))
9223372036854675456
$ echo $((i - 1000000))
9223372036853775360
$ echo $((i - 10000000))
9223372036844775424
$ echo $((i - 100000000))
9223372036754776064

Whereas, on x86_64, we get inexact representations when we go beyond LLONG_MAX:

$ typeset -lui i=9223372036854775807
$ echo $((i+1))
9.22337203685477581e+18
$ echo $((i-1))
9223372036854775806

What this shows is that the whole arithmetic subsystem is broken by design. Internally converting integers to floats and back is bogus, because even the largest float type cannot store all the possible integer values. Integers must be stored and calculated as integers, and nothing else.

We need to find a way, somehow, of making that happen, while still supporting floating point arithmetic as well. But the streval.c and arith.c code is so inscrutable, I'm not very much closer to understanding it now than I was when I forked ksh four years ago.

[McDutchie]

Just some links to remember when debugging this later:

• https://stackoverflow.com/a/70797617
• https://stackoverflow.com/a/45927313
• https://www.sciencedirect.com/science/article/pii/S1571066115000468?ref=pdf_download&fr=RR-2&rr=8a8ffe6538f663c8

[hyenias]

To help clarify the extent of impact of ksh's use of double (64bit) floats for integer operations, here are some observations:

From Double-precision floating-point format, the following is stated:

Precision limitations on integer values

• Integers from −2⁵³ to 2⁵³ (−9,007,199,254,740,992 to 9,007,199,254,740,992) can be exactly represented.
• Integers between 2⁵³ and 2⁵⁴ = 18,014,398,509,481,984 round to a multiple of 2 (even number).
• Integers between 2⁵⁴ and 2⁵⁵ = 36,028,797,018,963,968 round to a multiple of 4.
• Integers between 2ⁿ and 2ⁿ⁺¹ round to a multiple of 2ⁿ⁻⁵².

Let's test that on various hardware.

Intel x86_64 having 80bit long doubles having extended presicion:

~$ bash -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9
~$ zsh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9
~$ ksh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: -9.22337203685477581e+18, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9

Aarch64 with 128bit long doubles ARMv8:

~$ bash -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9
~$ zsh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9
$ ksh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: -9223372036854775809, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9

ARMv7l with 64bit doubles:

~$ bash -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: -1, 0, 1
66 bits: -1, 0, 1
67 bits: -1, 0, 1
68 bits: -1, 0, 1
~$ zsh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: -1, 0, 1
66 bits: -1, 0, 1
67 bits: -1, 0, 1
68 bits: -1, 0, 1
~$ ksh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740992
55 bits: 18014398509481984, 18014398509481984, 18014398509481984
56 bits: 36028797018963968, 36028797018963968, 36028797018963968
57 bits: 72057594037927936, 72057594037927936, 72057594037927936
58 bits: 144115188075855872, 144115188075855872, 144115188075855872
59 bits: 288230376151711744, 288230376151711744, 288230376151711744
60 bits: 576460752303423488, 576460752303423488, 576460752303423488
61 bits: 1152921504606846976, 1152921504606846976, 1152921504606846976
62 bits: 2305843009213693952, 2305843009213693952, 2305843009213693952
63 bits: 4611686018427387904, 4611686018427387904, 4611686018427387904
64 bits: -9223372036854775808, -9223372036854775808, -9223372036854775808
65 bits: -1, 0, 1
66 bits: -1, 0, 1
67 bits: -1, 0, 1
68 bits: -1, 0, 1

Confirmed. Integer operations are safe up to the 53bits (2⁵³) on machines that do not possess a greater precision for long double than 64bits as pointed out being Apple M1, M2, and M3 and ARMv7 chips. Not sure if Apple M4 still only has 64bit max precision as M4 maybe ARMv9 compatiable chipset. Almost all ARMv8 chips have supported 128bit floats for many years. For Intel, since forever. I hope Apple closes this gap and includes a floating point processor that supports a better precision than Intel such as 128bit or better.

Since Intel's significand is 63bits in size, ksh should be able to support at least signed 64bit integers with a high probability of unsigned 64 bit integers as sign bit is available in addition to the significand.

On the above output for Intel using ksh, the following is displayed, 64 bits: -9.22337203685477581e+18, -9223372036854775808, -9223372036854775807. For whatever reason, scientific notation is being used to output the value on the first column. As noted by @McDutchie, similar situation also occurs possibly on the same 64bit boundary. Perhaps there is some sort of conditional statement or such resetting things or providing a ceiling or floor messing up when crossing the 64 bit boundary.

Please also note the difference in output when output goes beyond 64 bits, 32bit system was "-1, 0, 1" but for 64bit systems was "0, 1, 2".

[BetterScripts]

Recently discovered this independently - been a long time since I found such a... um... fun(?)... bug!

Not sure it adds much, but for the record (on x86_64):

$ i=9223372036854775807
$ echo $i
9223372036854775807

$ j=$((i+1))
$ echo $j
9.22337203685477581e+18

$ printf '%d\n' $j
ksh93: printf: warning: 9.22337203685477581e+18: overflow exception
9223372036854775807

$ echo $((j-1))
9.22337203685477581e+18

$ echo $((j-i))
3

$ echo $((j-3))
9223372036854775807

$ while test j -gt i; do j=$((j - 1)); done # <- Infinite loop

FWIW also verified this affects 93u+ 2012-08-01 (the earliest version I had available) - which is as you likely expected anyway.

[McDutchie]

Related issues: #777, #781, #789

[dnewhall]

Since I'm looking at some of the math code right now, in theory, if I were to get integers and floats computing separately, what would be the correct behavior for both integer and float overflows? Wrap around on ints? Devolve to long floats and pray? Inf?

[BetterScripts]

FWIW the only shell I'm aware of that has any guaranteed behavior for integer overflow is mksh, but it limits integer math to 32 bits on all platforms - I suspect the limits here are required to make it portable without significant performance issues. (Note that the related lksh has no such guarantee and allows for larger values, while explicitly stating overflow is "undefined behavior").

I don't have access to much hardware, but I've tested a large number of shells on various OSes, and from what I've seen they almost exclusively fall into "undefined behavior" territory for overflow (many explicitly state this in documentation). Since these shells all seem to use an integer for the underlying data type, this often results in wrapping anyway.

IMO I'm not sure the mksh approach is the right way - seems like potentially a lot of work for not much gain (and possibly significant losses), but *shrug* I'm really just providing what info I can.

Edit: Re-written for clarity.

[McDutchie]

I don't think you're understanding the issue. For long (64-bit) integer types, calculations are wrong long before an integer overflow occurs.

[dnewhall]

So, my first experiment with this was to add a type like this:

typedef struct Mathval {
  int type;  // MV_INT or MV_FLOAT
  union {
    Sflong_t    i;
    Sfdouble_t  f;
  };
} Mathval_t;

And then have macros/functions to translate a Mathval_t to the needed type: MV2I, MV2F, etc. These check if its current type is the one needed and then converts it if its not. While I was implementing these I thought "what if this conversion fails horribly?", and that prompted the comment on overflow behavior.

It's worth noting that it appears doing the above will make all math at least twice as slow (since it always needs to check the type and then maybe convert a value multiple times, versus just doing an operation with doubles which are already the fastest math ops on most processors). I don't know if that will be a deal-breaker once its timing is added to all the other parsing/executing the shell needs to do, but it is there.

There is another method I've seen in language VMs that might be more efficient but has its own tradeoffs:

typedef union Mathval {
  Sflong      i;
  Sfdouble  *fp;
} Mathval_t;

You then have all values marked as ints by having the low-bit set which you need to shift off (because the double pointer will always be even byte aligned). This would keep integer math still fast, but make double math slower (since you have to deref the pointer and then do the pointer management for the values). It's also not easily portable, because this is officially undefined behavior. (There is intptr_t, which can be used to make the behavior defined, but is still listed as optional in the C standard.)

Then there's what Tcl does, which is keep a copy of all values that might be needed. This works well for Tcl because it's converting from strings to integers and floats all the time depending on context, but I don't know if this will work here.