shift operator questions

[bob]

Semantics
3 The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

That seems pretty clear.

Yes this is clear but I wonder why not to define it when the right operand is negative.

In order to define it, they would have to state what the relationship is between the bits being shifted, the number that the left operand represented before the shift operation, and the number represented by the result. In other words, what number is meant by a particular pattern of bits? Nowadays pretty much all machines use a 2's-complement representation for their integer numbers, but when C was invented there were other machines around that used 1's complement or other representations. So the C standard couldn't really define it without making C impossible to implement sanely on some of the machines it was being used on. Instead, programmers were expected to know how their machine worked and use the operators accordingly. Widely-portable low-level software was not as common back then, I guess.

Here's another example: what is a NULL pointer? If you were to answer "a pointer value that consists of all zero bits" then you would be wrong. The NULL pointer is a unique value per pointer type that means "points to nothing", but the implementation can choose how to represent it. The fact that NULL is a macro that expands to a (maybe type-casted) literal 0 token has nothing to do with the value; that 0 token tells the compiler to make a NULL pointer, that's all.

Nearly all C implementations for the last 15+ years use an all-zero-bits value for the NULL pointer for every type. Because of that, there is a lot of code out there that does things like, memset a structure with 0 bytes and assume that that initializes any pointers in the structure with NULL. Nowadays, no one would make a C or C++ implementation that behaved differently, because there is so much code out there which would not work on it. I'm not sure if newer versions of the C or C++ standards have specified that NULL pointers now use an all-zero-bits representation, but I doubt it. In practice, go right ahead and assume that its true, because it is true on any implementation of C or C++ you'll ever use. But the C and C++ specs are filled with things like this---behaviour which is undefined, or implementation-defined, even though it works in a consistent and sane way across 99% of the machines in the world, because somewhere there is an oddball machine type which C runs on where that particular thing works totally differently.

I do not understand much about hardware but I think that it could be better to have definition for every possibility instead of having undefined cases.

If the fastest implementation of << that works correct for positive is dependent on the compiler then it is possible to have also another symbol to represent the faster operation that does not work for negative.

The reason for the definition that I thought about has nothing to do with hardware and it is simply a trivial mathematical generalization.

It is trivial that every hardware can support translation of << for negative number to >> and the compiler simply can translate
a<<b to
(b>=0)? (a<<b):(a>>(-b));

Uri

Actually very little is actually "undefined" with respect to hardware. It always has some action that is predictable 100% of the time. Unfortunately, vendors can't agree on some things (shift is a good example) where some machines allow negative shift amounts, some do not. So the compiler standard was left as vague for those cases.

Some standards were stupidly left to the vendor, such as is a char signed or unsigned, but that is another issue...

[Uri Blass]

The problem is that I want to have pawns[side]>>8 for white pawns and pawn[side]<<8 for black pawns and I want to use simply
pawn[side]>>advanced[side] when advanced[White]=8 and advanced[Black]=-8 and I cannot write things in that way.

Uri

You can!

If general code is more important than a few cycles, I recommend the general shift by x86 rotate/mask. If you pass let say -1 (0xff..ff) as left shift, it becomes 63 (0x3f) due to the internal unsigned modulo of the processor. Rotate left 63 is in fact equal to rotate right 1. To clear the unwanted bits by a mask can be combined with the wrap-ands you need for horizontal directions anyway.

Code: Select all

// positve left, negative right shifts
int shift[8] = {9, 1,-7,-8,-9,-1, 7, 8};
 
U64 avoidWrap[8] =
{
   0xfefefefefefefe00,
   0xfefefefefefefefe,
   0x00fefefefefefefe,
   0x00ffffffffffffff,
   0x007f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f00,
   0xffffffffffffff00,
};
 
U64 shiftOne (U64 b, unsigned int dir8) {
   return _rotl64(b, shift[dir8]) & avoidWrap[dir8];
}

Or this one:

Code: Select all

/**
 * generalized shift
 * @author Gerd Isenberg
 * @param x any bitboard
 * @param s shift amount -64 < s < +64
 *          left if positive
 *          right if negative
 * @return shifted bitboard
 */
U64 genShift&#40;U64 x, int s&#41; &#123;
   char left  =   &#40;char&#41; s;
   char right = -(&#40;char&#41;&#40;s >> 8&#41; & left&#41;;
   return &#40;x >> right&#41; << &#40;right + left&#41;;
&#125;

or Russel's proposal for generalized pawn push:

Code: Select all

enum { white, black };
 
U64 singlePushTargets(U64 pawns, U64 empty, int color) {
    return (&#40;pawns << 8&#41; >> &#40;color << 4&#41;) & empty;
&#125;

Gerd

My question is, why would that be any better than what I did for my first cut at this, namely:

padvances1 = ((wtm) ? Pawns(wtm) << 8 : Pawns(wtm) >> 8) & target;

What I obviously way, and had on many machines, was :

padvances1 = (Pawns(wtm) << shift8[wtm]) & target;

where int shift8[2] = { -8, 8 }: is used...

Back to my question above. Both approaches still have the ugly wtm. I test and shift the right way, the other way shifts both ways 1/2 the time, and shifts left and 0 the other half of the time. Reading them is not particularly clear and I prefer the (wtm) test myself for at least some clarity on what is going on...

BTW the above will not work on all machines. There have been some where shifting 0 did not noop as that code hopes, but was treated as a shift n bits where n was the wordsize of the machine, effectively zeroing the whole mess.

1)I think that the simpler code is the second code that you wrote:
padvances1 = (Pawns(wtm) << shift8[wtm]) & target;

Unfotunately it is not correct C when shift8 can get negative values

2)Another note is that I think that it is better not to use the number 8 because it is not clear to me that 8 is better than 1 and
more general solution is something like the following

padvances1 = ((wtm) ? Pawns(wtm) << a1a2_dir : Pawns(wtm) >> a1a2_dir ) & target;

a1a2_dir can be 8 or 1 or maybe 10 if I want to generalize the program to 10*8 board.

My only comment is that 8 is pretty obvious. If I ever intended to support other non 8x8 chess variants, 8 would be an ugly thing to deal with. But Crafty will only be normal chess (perhaps with chess960 now since the castling is a bit more generalized and it would not be hard to make it work for 960 castling as well).

most variables in Crafty are named to represent what they contain. For example "plus1dir[sq]" is an array of bit masks that give the squares in the +1 direction from the current square, not wrapping around the board anywhere... And it might make it a bit more readable to use something other than 8, but then that introduces confusion when you do this:

x = (wtm) ? pawns << plus8 : pawns >> minus8;

Because plus8 and minus8 both need to be +8, which might be more confusing than just using the number 8...

8 is not obvious even for normal chess.

Chess programs can also use a1=0,a2=1,a8=7,b1=8
I do not know if a1=0,b1=1,h1=7 is faster and I think that it is better to do the code more easy to change.

Uri

[Gerd Isenberg]

My question is, why would that be any better than what I did for my first cut at this, namely:

padvances1 = ((wtm) ? Pawns(wtm) << 8 : Pawns(wtm) >> 8) & target;

What I obviously way, and had on many machines, was :

padvances1 = (Pawns(wtm) << shift8[wtm]) & target;

where int shift8[2] = { -8, 8 }: is used...

It was a proposal, since I generate only white moves, I actually don't use it. It is also about delegation to a generalized shift routine and better readable source:

Code: Select all

U64 pushtargets = pushOne(pawn[wtm], wtm) & emptysquares;

Then you can do your branches or whatever else, e.g.:

Code: Select all

U64 pushOne (U64 b, unsigned int wtm) {
   return _rotl64(b, shift[wtm]) & avoidWrap[wtm];
}

I guess the branches are good predictable, so your proposal is very likely the fastest. Otherwise, instead of speculative execution of both shifts and conditional move, I guess the generalized shift might be faster - at least with it's intended assembly and "variable" shift by cl:

Code: Select all

 ; input
 ;     ecx - shift amount,
 ;           left if positive
 ;           right if negative
 ;     rax - bitboard to shift
 mov   dl,  cl
 and   cl,  ch
 neg   cl
 shr   rax, cl
 add   cl,  dl
 shl   rax, cl

On shifting by zero - well if that happens, my programs crashes anyway

[bob]

In your case, any shift amount is going to be non-obvious. Mainly because as a chess player I am used to sitting either on the white side, or on the black side. I would not play a game sitting on either of the other two sides of the board so that pawns are moving left or right, rather than up or down the board.