Re: "Neagtive overflow" & other flaws in binary operations.

[Eduardo Bustamante]

On Sun, Mar 12, 2017 at 4:15 AM,  <ma9ik@interia.pl> wrote:
> Hello,
>
> Recently I've tried to use BASH to do some binary operations, that task
> turned out to be far more difficult, that I could ever imagined.

Bash has limited support for arithmetic operations on fixed width
signed integer numbers. Furthermore, it does not support floating
point numbers. I'd advise against using Bash for serious mathematical
tasks.

Here's the official Bash documentation on the support for shell
arithmetics: 
https://www.gnu.org/software/bash/manual/html_node/Shell-Arithmetic.html#Shell-Arithmetic

    Evaluation is done in *fixed-width integers with no check for
overflow*, though
    division by 0 is trapped and flagged as an error. The operators and their
    precedence, associativity, and values are the same as in the C language. The
    following list of operators is grouped into levels of equal-precedence
    operators. The levels are listed in order of decreasing precedence.

If you're interested in the actual implementation of the left and
right shift operations, you can read:
http://git.savannah.gnu.org/cgit/bash.git/tree/expr.c?h=devel#n794

Which as you can tell, just performs the C operations on intmax_t values.

>
> First of all, I've found out that 2 shifted to the left edge of boundary
> (2**63) produces as a result a negative number "-9223372036854775808"
> ("funny" thing is, when you substract "1" from this value, it gives positive
> value as a result), this problem is of course related to "u2 code" [...]

    dualbus@debian:~$ echo $((2<<64))
    2
    dualbus@debian:~$ echo $((2<<63))
    0
    dualbus@debian:~$ echo $((2<<62))
    -9223372036854775808

Yes, Bash does that. C does too:

    dualbus@debian:~$ cat main.c
    #include <stdio.h>
    #include <stdint.h>
    int main() {
        printf("%ld\n", (int64_t)2 << (int64_t)62);
    }
    dualbus@debian:~$ gcc -o main main.c; ./main
    -9223372036854775808

This is what happens when you perform bitwise shifts on signed fixed
width integers.

> Another thing, which doesn't behave exactly the way it should, is bit
> shifting. While shifting positive value to the right gives 0 at the end,
> then shifting negative value gives "-1" at the end, again it's related to
> "u2 code". I.e. try to shift "1", 63 times to the left (it will turn into
> negative value), then shift it back to the right, you'll never guess it
> won't evaluate to "0" but to "-1"! This is error in "logic", which lays
> beneath this whole idea. Bit operations shouldn't be sensitive to "u2
> coding", as coding is on higher abstract level then any of bit operations,
> which deals with "raw bits" on lowest level!

What is this "u2 code" you keep referring to?

Bash is not the right tool for the job. Please use a language that has
full support for integer and floating point arithmetic. Bash will let
values silently overflow, and do all the kinds of crazy things you
found out. But that's okay: it behaves as documented (i.e it's not
meant to be used in the way you're trying to).

> I can see two solutions (one dosen't exclude the other) to this problem.

Feel free to submit patches. Start by looking into
http://git.savannah.gnu.org/cgit/bash.git/tree/expr.c?h=devel (the
current implementation of arithmetical evaluation) and
http://git.savannah.gnu.org/cgit/bash.git/tree/examples/loadables/hello.c?h=devel
which should give you a rough idea of what you need to do to implement
a new builtin shell command that allows for arbitrary precision
integer arithmetic which fulfills your needs.