shift operator questions

[Uri Blass]

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.

I would like to have a>>(-i) to be defined to be the same as a<<i

It is logical to do it because *2^i is the same as /2^(-i)
The fact that I cannot do it make code that is independent on color harder to write.

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

[Gerd Isenberg]

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

[wgarvin]

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.

[Uri Blass]

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

[wgarvin]

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 point I was trying to get across is more like this: Yes its true that all x86 PCs, and most other modern desktop and server machines, work a certain way. But the C language is used on other kinds of computers too. There are C compilers for 1970's mainframes, for connection machines and for the little embedded processors in your TV or washing machine. C was designed in an era when there were machines with 7-bit or 9-bit bytes, a pointer might have 36 bits in it, etc. It had to accomodate all sorts of weird hardware (and still does to some extent). Nowadays everybody agrees that a byte has 8 bits in it, but even that was not always true around the time C was invented.

The C language is specified in such a way that the compiler implementors can do whatever is fastest for their kind of hardware. So the language doesn't specify something like "function arguments are evaluated in left-to-right order" for example, because for some types of machines, and some programs being compiled for them, there will be a better or faster way. The language tries to give the compiler guys the freedom to do whatever is fastest or smallest or best. The price paid for that, is that all the programmers using C have to remember not to assume that arguments are evaluated in any particular order. So expressions like x++ = ++x + 1 could mean just about anything, because the language does not spell out their One True Meaning(tm).

Whereas a language like Java does try to define the behaviour of everything. That caused a bunch of problems with floating-point math because the Java language specified some things (like the exact precision that was supposed to be used in some situations) that the floating-point hardware on many platforms could not deliver, without using a bunch of extra instructions, like 5x as many. As a result, some modern floating-point hardware has a "Java-compatibility mode" or similar. The Java guys realized their mistake and eventually backed down on the float stuff, nowadays the programmer can choose between "fast-but-not-exactly-the-same-on-all-platforms" floats, and "slow-but-works-the-same-everywhere" floats.

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

Maybe they could put that in the spec. But what if there's some hardware out there that would now need extra instructions? Instead of compiling a shift to one instruction, it might have to compile it to 6 or 10 instructions on this platform, crippling the performance. C tries hard not to do that.

Besides, what do you do if (b) is not a constant? Now the compiler would have to insert extra run-time stuff---a branch, or predicated instructions, or a conditional move, or something. The C language tries to avoid features with a "hidden run-time cost". After all, if (b>=0)? (a<<b):(a>>(-b)) is what you want, you can always put it in a macro or something.

C was invented for systems programming, and took a very pragmatic approach when it came to supporting different hardware and different features and trying to get the best of everything. This is part of what made C so successful, but it does mean that people trying to write portable code have to be very careful not to fall into any of the pitfalls of the language.

I once worked on a team that had C code targeting over 20 different platforms, spanning every popular CPU architecture and a full set of compilers including MSVC, Intel, GCC and several compilers for crazy embedded platforms. Most of my time was spent fixing the weird portability problems that cropped up on one of the lesser-used targets anytime someone on the team changed code. As in, someone would check in their code changes, and the next day the automated builds or tests would fail on these platforms, and we had to figure out why and then change the code so that it worked on all of them. Portable low-level code is possible but the language does not make it easy for you.

[michiguel]

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.

Uri

In the C standard "undefined behavior" actually means STAY AWAY from it. Undefined cases are meant to be out of your code. The C standard is not going to tell you, "this case will give you an error", because it is not in its spirit. The C standard was meant to exist to tell you what you can do safely, not what you cannot do. The rest is "you are on your own" because your are not programming in C anymore.

IMHO, undefined behavior should be assert()'ed out (is that a verb? )

"Implementation defined" are cases were you can use it safely if you are willing to have a code that is less portable.

Miguel

[bob]

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.

[Zach Wegner]

"Implementation defined" are cases were you can use it safely if you are willing to have a code that is less portable.

My favorite example of this is pragmas as used in early GCC versions:

http://www.djmnet.org/humor/gcc-pragma.txt

"GCC's early handling of the ANSI #pragma construct is perhaps worth
noting at this point. Compiler writers are at liberty to deal with
#pragma as they see fit. Paul Rubin, in a bit of whimsy, chose to
start running the Tower-of-Hanoi game under emacs. Where this was
impossible, a session of the hack game was attempted. Failing that, a
rogue session was attempted. When all of these efforts failed, the
compiler printed the error message: "You are in a maze of twisty
compiler features, all different"."

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

[bob]

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