Don't understand CarryRippler

[mvanthoor]

Hi

While implementing magic bitboards, I found the CarryRippler information on ChessProgramming Wiki to calculate all permuations. It's this function:

Code: Select all

void enumerateAllSubsets(U64 d) {
   U64 n = 0;
   do {
      doSomeThingWithSubset(n);
      n = (n - d) & d;
   } while ( n );
}

I rewrote this function in Rust:

Code: Select all

fn enumerate(d: u64) {
    let mut n: u64 = 0;
    let mut stop = false;

    while !stop {
        // doSomeThingWithSubset(n);
        n = (n - d) & d;
        stop = n == 0;
    }
}

The problem I have with this while reading the function on the Wiki (and seeing the same function in Stockfish), is that "n" is an unsigned 64-bit number, and "d" is as well.

This line:

n = (n - d) & d;

It substracts d from n, but for any d greater than 0, the outcome of "n - d" will be negative, which is not possible when working with unsigned characters. Rust confirms:

"thread 'main' panicked at 'attempt to subtract with overflow'."

Still, stockfish and other engines use this technique almost verbatim from the wiki. Is there something C does that I don't know about, such as internally casting to an unsigned number, and then cast back again? Rust doesn't do things like that because it's possibly unsafe. Actually, it won't ever implicitly cast any type to another, not even from u8 to u64 for example.

Any thoughts on this?

(Also, I often see techniques in chess programming that actually take advantage of C/C++'s undefined behavior. An example is shifting more bits than are available in a number. Rust does not allow things like that.)

[hgm]

C doesn't check unsigned arithmetic for overflow. You could say that unsigned arithmetic is defined as modulo 2^N arithmetic (because virtually all existing hardware defines it that way).

But that doesn't help you much getting something that works in Rust, obviously. If Rust would complain about any kind of overflow, carry-propagation techniques will in general be problematic, because you would have to pre-empt the overflow. If you want to use all bits of the word you have no room to put a guard bit somewhere to prevent it.

One way of looping through all subsets of a given set d could be

Code: Select all

Process(0); // empty set is always subset
if(d) { // prevent disaster if d=0
  i = ~d + 1; n = 0;
  do {
    n = n + i; // the ~d part of i sets all unused bits in n, so carry propagates all across those to the next used bit
    n &= d;    // squash all unused bits again
    Process(n);
  } while(n != d); // stop after we did the complete set, because incrementing that would overflow
}

[fabianVDW]

Rust obviously also supports addition with overflow. You can use the wrapping_add/wrapping_sub function to prevent the checking.



In release mode, there will also be no checking of overflows, Rust just does this in debug mode to help find potential bugs.

[mvanthoor]

Thanks. I suspected something like that. Even so, I feel it's strange to define two variables as unsigned, then do something that makes one of them signed, and the compiler allows it (edit: by default).

Now I also start to understand the huge amounts of unsafe code I'm seeing in Cicada and Crabby.

Those are older chess engines written in Rust. They implement existing code and techniques that take advantage of specific unsafe or undefined behavior of C/C++, and then use unsafe { } to force the compiler to accept it. When using current Rust, Cicada now only compiles with a lot of warnings. Crabby doesn't even compile anymore except when using some very old nightly browsers.

I'll have a look at what's possible, but I'm not going to use unsafe { } to specifically force the compiler to accept C-like code.

[mar]

This line:

n = (n - d) & d;

It substracts d from n, but for any d greater than 0, the outcome of "n - d" will be negative, which is not possible when working with unsigned characters. Rust confirms:

"thread 'main' panicked at 'attempt to subtract with overflow'."

It seems that Rust is really serious about safety. even though the check seems to be present in debug mode only.

it could be easily fixed with something like this (I never wrote anything in rust before so take it with a grain of salt):

Code: Select all

fn modsub(a: u64, b:u64) -> u64
{
    return if b>a {std::u64::MAX-(b-a)+1} else {a-b}
}

I've tried a similar function across all mainstream C/C++ compilers and they all get it and compile this into sub a,b

[mvanthoor]

Yes. The speed of C, while maintaining safety, is one of the spear points of Rust.

The check is only done in debug mode. You can enable it for release mode as well, but it'll slow down the program.

That's a pity, because in this case, it's still possible to test the program in debug mode, find nothing wrong with it, and in the end, STILL calculate using a wrong value because something unforseen happens.

[mar]

Rust obviously also supports addition with overflow. You can use the wrapping_add/wrapping_sub function to prevent the checking.



In release mode, there will also be no checking of overflows, Rust just does this in debug mode to help find potential bugs.

I missed your reply when I was writing mine, using a standard way should be the preferred way indeed.
What I don't understand is why they didn't implement the wrapping functions as free functions, I find the syntax x.wrapping_sub(y) very ugly,
perhaps there was a reason for that (to support custom types? - but if rust supports ADL, this should work as well, I don't know)

[fabianVDW]

Rust obviously also supports addition with overflow. You can use the wrapping_add/wrapping_sub function to prevent the checking.



In release mode, there will also be no checking of overflows, Rust just does this in debug mode to help find potential bugs.

I missed your reply when I was writing mine, using a standard way should be the preferred way indeed.
What I don't understand is why they didn't implement the wrapping functions as free functions, I find the syntax x.wrapping_sub(y) very ugly,
perhaps there was a reason for that (to support custom types? - but if rust supports ADL, this should work as well, I don't know)

I think they want to discourage using those functions, since they are rarely what you need. I think I have one wrapping_mul in my whole engine (for magic bitboards).

[mvanthoor]

fabianVDW: Thanks, I've just tried it. using wrapping_sub() works. I didn't know it would work when wrapping the bits. I suspected C would discard the bits.

Good luck with your engine by the way

@mar:
https://docs.rs/num-traits/0.2.11/num_traits/

Rust has traits. Those are basically interfaces. If you implement a trait, you have to have an implementation for each function in the trait. This is the trait WrappingSub, which requires a method wrapping_sub() to be implemented on each type that implements this trait:

https://docs.rs/num-traits/0.2.11/num_t ... ngSub.html

A function implemented on a type is then called with the dot-syntax, similar to what Javascript does:

Code: Select all

var str = "Please locate where 'locate' occurs!";
var pos = str.indexOf("locate");

[fabianVDW]

I didn't know it would work when wrapping the bits. I suspected C would discard the bits.

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."