Best BitBoard LSB funktion?

[Reinhard Scharnagl]

Your Rand() generator is a tad slow by the way. See in the highend forums the ranrot postings i did. I had optimized to 64 bits
the ranrot generator which produces each 3.1 nanoseconds a new random number.

The goal of my posting has not been to vote for a special pseudo random number generator. I simply modified a testing program posted here short time before, simply to demonstrate the dependancy to set bits' density.

In Smirf I use a very different random number generator. In the context of a chess engine moreover neither the speed of such a generator is relevant nor the quality of randomness. It is instead the average signal distance between elementary hash keys' creation patterns - as I have written already several times ago. Good randomness of course is helping to reach that target, but it is distinct from it. As an example also random numbers will be generated having very few or very much bits set.

Regards, Reinhard.

[Gerd Isenberg]

..
Would the following simpler solution not be just as good?

Code: Select all

#if ((-1 & 0xFFFF) != 0xFFFF)
   #error(no two's-complement);
#endif


Remember, -1 is 111...111 in two's complement and
111...110 in one's complement. As you can see, the above
code tests whether the least significant 16 bits of -1 are all equal to 1.
Leen

Yes, but it assumes at least 16bit ints what is most likely true.
For runtime asserts with some int : 13 for instance, -1 is only 0x1fff - so it might be more general to use the definition of two's complement, one's complement plus one, or some derivered relations:

Code: Select all

#define checkIntegralTypeHasTwosComplement(x) assert(-x != ~x+1)

-x ==  ~x + 1
-x == ~(x - 1)
~x + y == ~(x - y)


Of course two's complement is guaranteed for integer types. So there i no need to do such things.

Gerd

[Sune Fischer]

In Smirf I use a very different random number generator. In the context of a chess engine moreover neither the speed of such a generator is relevant nor the quality of randomness. It is instead the average signal distance between elementary hash keys' creation patterns - as I have written already several times ago. Good randomness of course is helping to reach that target, but it is distinct from it.
Regards, Reinhard.

You keep stating this as though it is a fact,
but you have not proven that is better in anyway AFAIK.

-S.
[/u]

[Reinhard Scharnagl]

Hi Sune,

You keep stating this as though it is a fact,
but you have not proven that is better in anyway AFAIK.

despite of the possibilty to do that, why should I? during the last weeks I have shown in a very detailed way that already established X-FEN http://www.chessbox.de/xfen_e.html is a compatible method to extend FEN e.g. to cover also Chess960. But in contrast to this nearly everybody involved is welcoming Shredders new incompatible FEN 'invention'.

So when seeing arguments and proofs having no value at all, finally I would save a lot of time keeping it private, also remaining less frustrated.

Reinhard.

[diepeveen]

Your Rand() generator is a tad slow by the way. See in the highend forums the ranrot postings i did. I had optimized to 64 bits
the ranrot generator which produces each 3.1 nanoseconds a new random number.

The goal of my posting has not been to vote for a special pseudo random number generator. I simply modified a testing program posted here short time before, simply to demonstrate the dependancy to set bits' density.

In Smirf I use a very different random number generator. In the context of a chess engine moreover neither the speed of such a generator is relevant nor the quality of randomness. It is instead the average signal distance between elementary hash keys' creation patterns - as I have written already several times ago. Good randomness of course is helping to reach that target, but it is distinct from it. As an example also random numbers will be generated having very few or very much bits set.

Regards, Reinhard.

Oh well a few points:
a) don't post a RNG if it is not relevant as i'll post a better one as shown
b) the average signal distance is not interesting, what matters is
whether there is a multiple lineair relationship between the
numbers. In case of the code snippet posted by you, it is there,
as you combine 16/32 bits values to a bigger value.

Vincent

[Reinhard Scharnagl]

Hi Vincent,

a) don't post a RNG if it is not relevant as i'll post a better one as shown

it is simply a misinterpretation of yours to regard that posting as if I would have tried to introduce an RNG. That has not been the case, so I made that clear. That is all.

b) the average signal distance is not interesting ...

Of course you have the freedom to select what is interesting to you and what is not. But give also me the right to have a different point of view.

Reinhard.

[Sune Fischer]

Hi Sune,
despite of the possibilty to do that, why should I? during the last weeks I have shown in a very detailed way that already established X-FEN http://www.chessbox.de/xfen_e.html is a compatible method to extend FEN e.g. to cover also Chess960. But in contrast to this nearly everybody involved is welcoming Shredders new incompatible FEN 'invention'.

So when seeing arguments and proofs having no value at all, finally I would save a lot of time keeping it private, also remaining less frustrated.

Reinhard.

Reinhard,

What on God's green planet does the X-FEN discussion have to do with anything??

You stipulate something as though it was a known fact. Were I come from such claims will be challenged if you don't supply a proof.

-S

[Reinhard Scharnagl]

Hi Sune,

What on God's green planet does the X-FEN discussion have to do with anything??

well, I want to explain, that proving some things could be wasted time, if the other side is not willing to objectively work with it. And - as a result of that - I am actually not really motivated to repeatedly produce well thought postings, without having any effect. If you are interested in serious discussions, why not proof your point of view first? Then we may see. Concerning X-FEN it has been (and still is) a question of compatibility thus being relevant to everybody. Therefore I continued arguing for a long time, even when there have been personal attacks. That question here now is not that relevant, because it does not really touch me, if others would not agree. So I do not see why I have to prove anything as the first one. It of course could be irrelevant to you, what I just have tried to explain, but for me it is relevant.

You stipulate something as though it was a known fact. Were I come from such claims will be challenged if you don't supply a proof.

What I regard to be facts will be noticed in the way I am talking about. If you feel 'challenged' (I am not fighting), try your arguments. But demanding a proof at first, supposes that I am not telling the truth. That is not a motivating base for a serious discussion. Well, I could prove my theories, but I don't let me be forced to do this. Normally you always have the chance to falsify my statements, especially if you feel 'challenged'.

Reinhard.

[Sune Fischer]

Hi Sune, well, I want to explain, that proving some things could be wasted time, if the other side is not willing to objectively work with it. And - as a result of that - I am actually not really motivated to repeatedly produce well thought postings, without having any effect.

Just because people disagrees with you doesn't mean they are wrong.

Regarding the X-FEN there is no right or wrong, it's just a matter of taste and we have to weigh the pros and cons. You can voice your aguments but eventully people will make their own decisions about which is better.
Shredder-fen, which has been proposed many times over the years by a lot of people incl. me, has the advantage that it is easy to understand. There is no reason to write entire books explaining the deeper philosophy behind it, it's just a down to earth logical choice.

If you are interested in serious discussions, why not proof your point of view first? Then we may see.

I only _believe_ random numbers to be better, I'm not claiming to know anything for a fact as that would require stringient mathematical proof beyond my skills.
But then again I'm not the one claiming to know anything for certain.

Concerning X-FEN it has been (and still is) a question of compatibility thus being relevant to everybody.

No compability is only one of the things to consider, just as important is it that it is logical, easy to implement and generally appeals to people.

One can hardly understand X-FEN without reading a 15 page document with 31 different examples and exceptions - this is bad Reinhard!

What I regard to be facts will be noticed in the way I am talking about. If you feel 'challenged' (I am not fighting), try your arguments. But demanding a proof at first, supposes that I am not telling the truth. That is not a motivating base for a serious discussion.

I suppose that you think you are telling the truth, but I doubt you really known the truth anymore than me.

Well, I could prove my theories, but I don't let me be forced to do this. Normally you always have the chance to falsify my statements, especially if you feel 'challenged'.
Reinhard.

Nothing wrong with having a theory, but to become more than that you have to prove it.

-S.

[Anonymous]

Yes, but it assumes at least 16bit ints what is most likely true.

It is true for all C-compilers. Even short has at least 16 bits.

Of course two's complement is guaranteed for integer types. So there i no need to do such things.

Two's complement is guaranteed in C (from programmers point of view, even when the internal machine format is different) for all *unsigned* integer types, not for signed ones. Of course with such bit tricks, one should almost always use unsigned integer types anyway.

Regards,
Dieter

[Gerd Isenberg]

Yes, but it assumes at least 16bit ints what is most likely true.

It is true for all C-compilers. Even short has at least 16 bits.

Of course two's complement is guaranteed for integer types. So there i no need to do such things.

Two's complement is guaranteed in C (from programmers point of view, even when the internal machine format is different) for all *unsigned* integer types, not for signed ones. Of course with such bit tricks, one should almost always use unsigned integer types anyway.

Regards,
Dieter

Hi Dieter,

i am aware of the 16-bit int issue - operations on hand wired odd bit sized ints should also not be a problem, since it may be expanded to native int size by zero or sign extensions before the operation occurs. Before writing/oring back to memory the result gets masked by the appropriate (2**n)-1.

I wonder that for signed int two's complement is not guaranteed in C.
So you say theoretical C compiler may implement signed int with sign bit and absolute value, so that -1 becomes 0x100...01 and we have +- zero?

Guess preprocessor expressions are implicitly signed int and the mentioned preprocessor check for two's complement may really fail for some compilers - even if unsigned int works fine.

Code: Select all

#if (~(USHRT_MAX+UCHAR_MAX) != ~USHRT_MAX-UCHAR_MAX)
    #error(no two's-complement);
#endif


I thought the only signed/unsigned issue unsafe for bitfrickling is arithmentic shift right versus logical shift right - but not bitwise operations.
And for amd64 to use unsigned int as index due to implicite zero extension to 64-bit.

Regards,
Gerd

[Gian-Carlo Pascutto]

Does anyone have a good MSB function?

As far as I understand there is no trivial transformation from findLSB to findMSB?

[Gerd Isenberg]

Does anyone have a good MSB function?

As far as I understand there is no trivial transformation from findLSB to findMSB?

Hi Gian-Carlo,

Eugene Nalimov's lookup based routines are quite good portable alternative for x86-bsr pairs:

Code: Select all

int bitScanReverse8(BitBoard bb)
{
 int result = 0;
 if (bb > 0xFFFFFFFF) {
  bb >>= 32;
  result = 32;
 }
 if (bb > 0xFFFF) {
  bb >>= 16;
  result += 16;
 }
 if (bb > 0xFF) {
  bb >>= 8;
  result += 8;
 }
 return result + table8[bb];
}


int bitScanReverse16(BitBoard bb)
{
 int result = 0;
 if (bb > 0xFFFFFFFF) {
  bb >>= 32;
  result = 32;
 }
 if (bb > 0xFFFF) {
  bb >>= 16;
  result += 16;
 }
 return result + table16[bb];
}


Branchless MSB-bit isolation is a bit harder and more expensive, since there is no reverse arithmetic.
One idea is to parallel prefix set all lower bits with log2(N bits) steps:

Code: Select all

   bb |= bb >> 1;
   bb |= bb >> 2;
   bb |= bb >> 4;
   bb |= bb >> 8;
   bb |= bb >> 16;
   bb |= bb >> 32;


This is already fine for an appropriate De Bruijn Multiplication.
To really get the isolated MSB, shifting right and adding one is necessary:

Code: Select all

   MSB = (bb >> 1)  + 1;


Since leading zero count is also necessary to convert ints to floats/double there are also some more or less portable tricks to interprete the binary representation of a double, the base two exponent of a normalized mantissa.

Gerd

[Pradu]

Does anyone have a good MSB function?

As far as I understand there is no trivial transformation from findLSB to findMSB?

Here's one that I wrote... I'm not really sure how good it is but it works well enough for me.

http://wbforum.volker-pittlik.name/view ... 5379#15379

It works faster than the deBruijn bitscan as far as my tests go (too lazy to post them).

[Dann Corbit]

[snip]
I wonder that for signed int two's complement is not guaranteed in C.
So you say theoretical C compiler may implement signed int with sign bit and absolute value, so that -1 becomes 0x100...01 and we have +- zero?

Yes. One's complement can have +/- zero, and I have seen it occur.

If your hardware is not physically a 2's complement machine, then forcing that behavior would be very bad for performance. C is intended to be very close to the machine.

The only assumptions that you should make are those guaranteed by the C standard.

[Anonymous]

Hi Gerd,

> I wonder that for signed int two's complement is not guaranteed in C.
> So you say theoretical C compiler may implement signed int with sign
> bit and absolute value, so that -1 becomes 0x100...01 and we have +-
> zero?

Correct. From the Standard:

---
6.2.6 Representations of types
6.2.6.1 General

The representations of all types are unspecified except as stated in this subclause.

[...]

6.2.6.2 Integer types

[...]
For unsigned integer types other than unsigned char, the bits of the object
representation shall be divided into two groups: value bits and padding its (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2N-1, so that objects of that type shall be capable of representing values from 0 to 2N - 1 using a pure binary representation; this shall be known as the value representation. The values of any padding bits are unspecified.

For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. There need not be any padding bits; there shall be exactly one sign bit. Each bit that is a value bit shall have the same value as the same bit in the object representation of the corresponding unsigned type (if there are M value bits in the signed type and N in the unsigned type, then M ? N). If the sign bit is zero, it shall not affect the resulting value. If the sign bit is one, then the value shall be modified in one of the following ways:

? the corresponding value with sign bit 0 is negated;
? the sign bit has the value -2N ;
? the sign bit has the value 1 - 2N .

---

So, I think this leaves two's complement, one's complement and sign magnitude. Of course, in practice we will have two's complement representation. However (IMHO), when there is no good reason to depend on it, one shouldn't.

> Guess preprocessor expressions are implicitly signed int and the
> mentioned preprocessor check for two's complement may really fail for
> some compilers - even if unsigned int works fine.

I was too lazy to carefully read the Standard about this. My guess: On a 32-bit int system, 0xffff is type int; on a 16-bit int system it is type unsigned int.

I'd use 0xffffU instead of 0xffff.

> I thought the only signed/unsigned issue unsafe for bitfrickling is
> arithmentic shift right versus logical shift right - but not bitwise
> operations.

If we have two complement representation, I think this is correct. Right shift is not an unlikely operation on bitboards in chess engines. (Andrew Williams posted once a code snippet in CCC, that failed exactly because of using right shift on signed integer.)

I am not sure, whether it is undefined behaviour, when signed integer operations overflow (sometimes we may use arithmetic operands with bitboards). Unsigned integers certainly have well defined results here (with the obvious exceptions of / 0 and % 0) .

Cheers,
Dieter

[Anonymous]

Since leading zero count is also necessary to convert ints to floats/double there are also some more or less portable tricks to interprete the binary representation of a double, the base two exponent of a normalized mantissa.

Interesting thought. Especially in C99, it should be very portable for 32-bit integers. C99 has the ilogb() function (it was available since long on many systems). ilogb() should even get inlined by a good compiler. I think, it will not work on 64 bit integers, however. We can pretty much assume IEEE 754 floating point representation (and it can even be checked), but we cannot assume, that we have a floating point type, that has enough accuracy for 64 bit numbers.

Cheers,
Dieter

[Dann Corbit]

Hi Gerd,
[snip]
> I thought the only signed/unsigned issue unsafe for bitfrickling is
> arithmentic shift right versus logical shift right - but not bitwise
> operations.

If we have two complement representation, I think this is correct. Right shift is not an unlikely operation on bitboards in chess engines. (Andrew Williams posted once a code snippet in CCC, that failed exactly because of using right shift on signed integer.)

I am not sure, whether it is undefined behaviour, when signed integer operations overflow (sometimes we may use arithmetic operands with bitboards). Unsigned integers certainly have well defined results here (with the obvious exceptions of / 0 and % 0) .

Cheers,
Dieter

For bit shift, the direction is important with signed values as to whether the behavior may be implementation defined or undefined.

"ISO/IEC 9899:1999 (E) ?ISO/IEC
6.5.7 Bitwise shift operators
Syntax
1 shift-expression:
additive-expression
shift-expression << additive-expression
shift-expression >> additive-expression
Constraints
2 Each of the operands shall have integer type.
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.
88) Another way to approach pointer arithmetic is first to convert the pointer(s) to character pointer(s): In this scheme the integer expression added to or subtracted from the converted pointer is first multiplied by the size of the object originally pointed to, and the resulting pointer is converted back to the original type. For pointer subtraction, the result of the difference between the character pointers is similarly divided by the size of the object originally pointed to. When viewed in this way, an implementation need only provide one extra byte (which may overlap another object in the program) just after the end of the object in order to satisfy the ??one past the last element?? requirements.
4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 ? 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 ? 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined."

The behavior with integer overflow might be implementation defined, or it may result in undefined behavior, depending on whether the hardware uses modular arithmetic:

"?ISO/IEC ISO/IEC 9899:1999 (E)
Annex H
(informative)
Language independent arithmetic

H.2.2 Integer types
1 The signed C integer types int, long int, long long int, and the corresponding unsigned types are compatible with LIA-1. If an implementation adds support or the LIA-1 exceptional values ??integer_overflow?? and ??undefined??, then those types are LIA-1 conformant types. C?s unsigned integer types are ??modulo?? in the LIA-1 sense in that overflows or out-of-bounds results silently wrap. An implementation that defines signed integer types as also being modulo need not detect integer overflow, in which case, only integer divide-by-zero need be detected."

[Anonymous]

Dann, thanks for elaboborating on this.

I fear, this is drifting very offtopic for this forum now, and it is certainly my fault. Allow few more comment.

> For bit shift, the direction is important with signed values as to whether the behavior may be implementation defined or undefined.

They way, you say this, is a bit confusing for me, now. You refer to signed values. Isn't the undefined behaviour independent of the signedness? As I understand it, undefined behaviour can only be the result of shift count "out of bounds".

> The behavior with integer overflow might be implementation defined, or
> it may result in undefined behavior, depending on whether the
> hardware uses modular arithmetic:

I am confused a bit, here as well. Isn't "might be implementation defined" superflouos to mention here? When an overflow can result in undefined behaviour, unless specific conditions are given, where it won't result in undefined behaviour, I cannot see, how the undefined behaviour can be weakened to implementation defined behaviour.

Even, if it was the case, why should it depend on modular arithmetic. If I built a C-Compiler, and I write in the manual: "every signed integer overflow will evaluate to 0xffffffffffffffffLLU casted to the appropriate result type". That would clearly not be modular arithmetic. Still a rather implementation defined result, not?

I thought the annexes do not really belong to the Standard (in the sense, that a conforming C implementation can ignore the annexes).

Can you find fast, where in the main text of the Standard integer overflows are shown to be undefined behaviour?

Regards,
Dieter

[Dann Corbit]

Dann, thanks for elaboborating on this.

I fear, this is drifting very offtopic for this forum now, and it is certainly my fault. Allow few more comment.

> For bit shift, the direction is important with signed values as to whether the behavior may be implementation defined or undefined.

They way, you say this, is a bit confusing for me, now. You refer to signed values. Isn't the undefined behaviour independent of the signedness? As I understand it, undefined behaviour can only be the result of shift count "out of bounds".

> The behavior with integer overflow might be implementation defined, or
> it may result in undefined behavior, depending on whether the
> hardware uses modular arithmetic:

I am confused a bit, here as well. Isn't "might be implementation defined" superflouos to mention here? When an overflow can result in undefined behaviour, unless specific conditions are given, where it won't result in undefined behaviour, I cannot see, how the undefined behaviour can be weakened to implementation defined behaviour.

Even, if it was the case, why should it depend on modular arithmetic. If I built a C-Compiler, and I write in the manual: "every signed integer overflow will evaluate to 0xffffffffffffffffLLU casted to the appropriate result type". That would clearly not be modular arithmetic. Still a rather implementation defined result, not?

I thought the annexes do not really belong to the Standard (in the sense, that a conforming C implementation can ignore the annexes).

Can you find fast, where in the main text of the Standard integer overflows are shown to be undefined behaviour?

Regards,
Dieter

This is from the body of the standard:
"3.4.3
1 undefined behavior
behavior, upon use of a nonportable or erroneous program construct or of erroneous data,
for which this International Standard imposes no requirements
2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable
results, to behaving during translation or program execution in a documented manner characteristic of the
environment (with or without the issuance of a diagnostic message), to terminating a translation or
execution (with the issuance of a diagnostic message).
3 EXAMPLE An example of undefined behavior is the behavior on integer overflow."

But it is just an example.

From section "J.2 Undefined behavior" we do have this:
"? The value of the result of an integer arithmetic or conversion function cannot be represented (7.8.2.1, 7.8.2.2, 7.8.2.3, 7.8.2.4, 7.20.6.1, 7.20.6.2, 7.20.1)."

But the annex H (apparently) softens the result if the hardware platform defined the results of signed integer operations to be modular arithmetic (see the informative Annex H). At least that is how I read it.

As for the sifts... left shift of signed is undefined if negative:
"4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 ? 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 ? 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined."

but the right shift of negative numbers is implementation defined:
"5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined."

Or so I would interpret it.