Supplying negative left-hand oparand to bit-shift operators produces an error (or undefined behavior)

[matthewmartin295]

Tested versions

Reproducible in 4.2.1

System information

Godot v4.2.1.stable - Linux Mint 21.2

Issue description

Bit shift operators (>> and <<) in GDScript throw an error when providing a negative number as the left-operand:

This makes it difficult to treat ints (signed int64s in GDScript) as raw bit data, and complicates accessing bit data directly (specifically, the left-most bit of an int).

There is no reason to prevent negative signed int64s ("negative" doesn't mean much in terms of a bit-field such as ~0 ie. all 1 bits) from having bitwise operations performed on them: -1 >> 1 or equivalent ~0 >> 1 (ie. 0xFFFF_FFFF_FFFF_FFFF >> 1) should simply return 0x7FFF_FFFF_FFFF_FFFF.

Godot allows the treatment of ints as raw bit data in all regards (with bitwise operations: |, &, ~, etc), but prevents this for negative numbers (ie. ints with a 1 in the left-most bit position) for bit shifting. A bitwise operation doesn't operate on a number so much as it operates on the raw bit data of the int. The use of bitwise operations in the first place generally assumes that the user would no longer like to treat the int as a number, but rather operate on the inner bit data.

I understand that C++ does not support a negative value as either operand of a bitshift operator either, but in GDScript we have no unsigned int type to work with. To implement shifting of negative int64s in the engine, the GDScript int64 can simply be converted to uint64 if it's negative before shifting.

To make matters worse, the error that prevents this in the editor does not produce an error at runtime, and instead produces what I assume is undefined behavior (if the behavior is the same as supplying negative signed-ints to bitshift operators in C++):

var num: int = 0
num -= 1
print(num)
print(num >> 1)

Prints:

-1
-1 # Something is wrong here. Undefined behavior?

Screenshot of explanation above:

Common use-case that this error prevents

Say I have 2 32-bit ints that I would like to pack into a single GDScript int to save space. I can do this easily with:

var num1 := 0xFFFFFFFF
var num2 := 0xFFFFFFFF
var packed_data: int = num2 << 32 | num1

Now, I would like to extract these values. The following intuitive code does not work when num2 has a 1-bit in the left-most (for a 32-bit int) position:

# Trim off the front 32-bits to extract num1. Works.
var unpacked_num1 := packed_data & 0xFFFFFFFF
# Shift the high 32-bits back to the right to extract num2. Not only does this not work, it produces
# undefined behavior as explained above (I am getting -1).
var unpacked_num2 := packed_data >> 32 # Not 0xFFFFFFFF

The only approach I can think of to avoid shifting negative values in this case is:

var unpacked_num1 := packed_data & 0xFFFFFFFF
var unpacked_num2: int
if packed_data >= 0:
  # For positive int64s, there is no issue.
  unpacked_num2 = (packed_data >> 32)
else:
  # For negative int64s, we have to shift the packed data to the right. Since we can't shift negative values:
  # 1. Invert the packed data and shift it right.
  # 2. The data is now successfully shifted, but all values are inverted, so invert them back.
  # 3. The data is now correct, but 32 left bits are 1s instead of 0s. Trim them off by bitwise-and of 0xFFFFFFFF.
  unpacked_num2 = ~(~packed_data >> 32) & 0xFFFFFFFF

Steps to reproduce

# Editor error. Expected value of `i` is `0x7FFFF_FFFF_FFFF_FFFF` (`9223372036854775807`).
var i = -1 >> 1

# Runtime issue. Undefined behavior with no error.
var num: int = 0
num -= 1
print(num)
print(num >> 1) # Undefined behavior?

Minimal reproduction project (MRP)

N/A

[Malcolmnixon]

Godot's implementation of right-shifting of negative signed integers follows that of C/C++ - specifically it is expected to perform an Arithmetic Right Shift operation and extend the sign bit. The observed behavior is expected, and can be replicated in C++:

#include <cstdio>

int main()
{
    int i = -1;
    printf("%d\n", i);
    printf("%d\n", i >> 1);
    return 0;
}

Produces:

-1
-1

In some regards Godot mirrors Java where only signed integer types are exposed to the user with arithmetic shifting rules applied. For Java (and for Godot) the solution is to do a bit-mask operation after the shift.

I'm not sure why a check for right-shifting of negative constants has been added - possibly for some older non-compliant systems, or perhaps in an attempt to prevent receiving unexpected results.

[matthewmartin295]

According to the C++ standard, bit-shifting negative values is (undefined). You and I both get -1, but it is not guaranteed to return -1 (or return at all). However, I wasn't able to find the shift operation in the Godot engine code (I not familiar enough with the codebase and doing any sort of search for "<<" or ">>" predictably returns way too many results - please link if possible if you know where it is) so I'm not sure if it's directly feeding the operation to C++.

Thanks for the info on logical vs arithmetic shifting! But I'd be surprised if this is intended due to the error message: that occurs whenever the editor can detect that there is a 1 in the left-most bit.

Can you explain what you mean by

For Java (and for Godot) the solution is to do a bit-mask operation after the shift.

I would love to know a viable workaround!

Edit:

I think I figured out what you mean: something like print("%x" % ((~0 >> 1) & 0x7FFF_FFFF_FFFF_FFFF)) This code would work if not for the editor's complaint about negative operands. Instead the following does work as expected:

var i := 0
i -= 1
print("%x" % ((i >> 1) & 0x7FFF_FFFF_FFFF_FFFF))

Using it in this way still makes me nervous due to the editor error from before, but maybe the error is extraneous in which case I would be happy using this.

Assuming that GDScript shouldn't have undefined behavior, it should either:

1. Allow negatives on the left side (eg ~0 >> 1) without an editor error, and have the arithmetic bit shift explanation included in the docs.

or

2. Disallow negatives on the left side at run-time to prevent undefined/unintended behavior.

[Malcolmnixon]

I tracked down the changes to https://github.com/godotengine/godot/pull/35245 and the reasoning appears to be a C recommendation from ISO/IEC 9899:2011 which originates from C supporting older processors where Two's Complement or Arithmetic Shift support is not guaranteed. The Arithmetic Shift article on Wikipedia has a nice breakdown by language.

C++ gave up on ancient integer formats in the C++20 spec - mandated support for Two's Complement and Arithmetic Shift.

Interestingly C23 still leaves it undefined in a vain attempt to support legacy systems. If we try running Godot on a UNIVAC 1100/2200 computer with 36-bit integers and a maximum of 2096K of RAM we'd have some porting issues.

I suggest we try relaxing this - the worst that may occur is an overly pedantic compiler warning of undefined behavior on ancient silicon.

[matthewmartin295]

Awesome! Thanks for digging into this. Nice find on #35245 - I missed it. I agree, relaxing this would make sense to keep editor vs run-time behavior consistent.

Adding a note to the docs about arithmetic shift (and possibly a warning of undefined behavior on very old systems, if anyone is concerned?) would help tremendously too.