Don't understand CarryRippler

[mvanthoor]

The wrapping reference the number, not the bits which are discarded aswell. From the rust documentation:
"Wrapping (modular) subtraction. Computes self - rhs, wrapping around at the boundary of the type."

Yes, i understand now.

I know a number wraps around at the boundary:

u8 255 + 1 = 0
u8 0 - 1 = 255

I didn't realize the carry rippler expects this, and that C implicitly allows it when using unsigned variables. Thanks for the help

[petero2]

Yes, i understand now.

I know a number wraps around at the boundary:

u8 255 + 1 = 0
u8 0 - 1 = 255

I didn't realize the carry rippler expects this, and that C implicitly allows it when using unsigned variables. Thanks for the help

This is actually explicitly allowed by the C language specification. Section 6.2.5.9 of the C99 standard says:

The range of nonnegative values of a signed integer type is a subrange of the
corresponding unsigned integer type, and the representation of the same value in each
type is the same.31) A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned integer type is
reduced modulo the number that is one greater than the largest value that can be
represented by the resulting type.

If you use a correctly implemented C compiler, it will make unsigned arithmetic behave as specified, regardless of what hardware the compiled program will run on. If the hardware cannot perform the required modulo arithmetic in one machine instruction, the compiler would have to generate extra instructions to produce the correct result.

For sufficiently non-standard hardware, the compiler writer could of course decide that supporting the C language is not a good idea, so they could instead build a compiler for a similar but different language C' and define the C' language however they want to.

[Gerd Isenberg]

Unary minus operator of unsigned integers (short, long) in C/C++ is defined as two's complement, which is the increment of the ones' complement. If you add a value and its ones' complement, the sum has all bits set without any intermediate bitwise overflows. If you further add 1, an overflow occurs with results in zero. So even if there are no negative unsigned integers, overflows may occur by adding the two's complement.

Code: Select all

x + ~x == ~0 = 111...111B
x + ~x + 1 == x + -x = x - x = 0

Today most ALUs work that way, one may interprete results as signed or unsigned, see x86 flags after add, sub etc..., i.e. jc, jo, js ...

However two's complement arithmetic is not strictly defined for signed integers in C (but in Java, as de facto in C/C++), due to former machines with ones' complement negative values in hardware.

[JohnWoe]

It seems to overflow nicely but shifting gives warnings propably UB.

Code: Select all

  int j = 23;
  j <<= 32;
  Print("%i", j);

  BITBOARD i = 0xFFFFFFFFFFFFFFFFULL;
  i <<= 65;
  Print("%llx", i);

  j = INT_MAX;
  Print("%i , %i", j, j + 1);

  i = 0xFFFFFFFFFFFFFFFFULL;
  Print("%llx , %llx", i, i + 1);

  j = INT_MIN;
  Print("%i , %i", j, j - 1);

  i = 0x0ULL;
  Print("%llx , %llx", i, i - 1);

Results:

Code: Select all

Sapeli.c:4015:5: warning: left shift count >= width of type [-Wshift-count-overflow]
   j <<= 32;
     ^~~
Sapeli.c:4019:5: warning: left shift count >= width of type [-Wshift-count-overflow]
   i <<= 65;
     ^~~
At top level:
Sapeli.c:4000:13: warning: ‘Go’ defined but not used [-Wunused-function]
 static void Go()
             ^~
0
0
2147483647 , -2147483648
ffffffffffffffff , 0
-2147483648 , 2147483647
0 , ffffffffffffffff

[mar]

It seems to overflow nicely but shifting gives warnings propably UB.

This is because the hardware (x86 since 286, not sure about ARM) does mask before shift.
so uint32 << 33 gives the same result as uint32 << (33 & 31), which is left shift by two, instead of 0.
for 64-bit integers the mask is obviously 63.
I don't know what the standard states (whether UB or implementation-defined), but the compiler does what the HW would do but gives you a warning.
I find this reasonable.