couple of questions about stockfish code ?

[syzygy]

well if the goal was to remove the union and avoid umpteen bajillion casts, the tradeoff is doing a manual sign extension and perhaps that'd make it slower (maybe the compiler would recognise what you're doing though and it'd be the same) though i'd argue more readable...

So now let's have a look at what the compiler does (gcc-6.2 on x86-64, Linux).

SF's current code using a union for casting (cleaned up by me for readability):

Code: Select all

_Z10make_scoreii:
	sall	$16, %esi
	leal	(%rsi,%rdi), %eax
	ret
_Z8eg_value5Score:
	leal	32768(%rdi), %eax
	sarl	$16, %eax
	ret
_Z8mg_value5Score:
	movswl	%di, %eax
	ret

Not much to improve here.

Your manual sign-shift code:

Code: Select all

_Z10make_scorejj:
	sall	$16, %esi
	leal	(%rsi,%rdi), %eax
	ret
_Z8eg_Value5Score:
	leal	-2147450880(%rdi), %eax
	shrl	$16, %eax
	subl	$32768, %eax
	ret
_Z8mg_Value5Score:
	movswl	%di, %eax
	ret

Not bad at all!
Only eg_value() has one instruction extra.

The direct casting method:

Code: Select all

_Z10make_scoreii:
	sall	$16, %esi
	leal	(%rsi,%rdi), %eax
	ret
_Z8eg_value5Score:
	leal	32768(%rdi), %eax
	sarl	$16, %eax
	ret
_Z8mg_value5Score:
	movswl	%di, %eax
	ret

Identical to SF's union-cast code.

Oliver's code:

Code: Select all

_Z10make_scoreii:
	sall	$16, %esi
	leal	(%rsi,%rdi), %eax
	ret
_Z8eg_value5Score:
	leal	32768(%rdi), %eax
	sarl	$16, %eax
	ret
_Z8mg_value5Score:
	leal	32768(%rdi), %eax
	movzwl	%ax, %eax
	subl	$32768, %eax
	ret

eg_value() is optimal (but relies on signed right-shift working as expected).
mg_value() has two instructions extra.

Once you start inlining these functions the different implementations seem to have different effects on how the rest of the code is compiled, but that is beyond the programmer's control and will have to be ignored.

[syzygy]

http://stackoverflow.com/questions/1315 ... d-behavior

See the top answer. This leads to the following solution (I don't think there is any reason to use static_cast here, but I don't speak C++):

Code: Select all

enum Score : uint32_t { SCORE_ZERO };

inline int16_t to_int16_t(uint16_t v)
{
    if (v <= INT16_MAX)
        return int16_t(v);

    if (v >= INT16_MIN)
        return int16_t(v - INT16_MIN) + INT16_MIN;

    exit(EXIT_FAILURE);
}

Score make_score(int mg, int eg) {
    return Score((unsigned(eg) << 16) + mg);
}

Value eg_value(Score s) {
    return Value(to_int16_t((s + 0x8000) >> 16));
}

Value mg_value(Score s) {
    return Value(to_int16_t(s));
}

As the answer explains, the v >= INT16_MIN condition really compares v with uint16_t(INT16_MIN), which on decent platforms will be INT16_MAX + 1. So the compiler should be able to simplify to_int16() to a no-op. (To persuade Microsoft's compiler not to do anything stupid, it is apparently necessary to test for v > INT16_MIN - 1u.)

And indeed:

Code: Select all

_Z10make_scoreii:
	sall	$16, %esi
	leal	(%rsi,%rdi), %eax
	ret
_Z8eg_value5Score:
	leal	32768(%rdi), %eax
	sarl	$16, %eax
	ret
_Z8mg_value5Score:
	movswl	%di, %eax
	ret

[Rein Halbersma]

http://stackoverflow.com/questions/1315 ... d-behavior

See the top answer. This leads to the following solution (I don't think there is any reason to use static_cast here, but I don't speak C++):

In C++ static_cast is preferred because of 1) greppability, and 2) in general C-style casts might do a reinterpret_cast under the covers (not in this case, but see #1). It just makes the intent explicit, so it's a good idiom to use.

[syzygy]

I think this line is not correct:

Code: Select all

    if (v >= INT16_MIN)

Since both uint16_t and int16_t fit in int, INT16_MIN will be cast to int (and remain negative) instead of being cast to uint16_t.

So it should be:

Code: Select all

    if (v >= uint16_t(INT16_MIN))

The first attempt still gives the right result, but for the wrong reason.

[syzygy]

http://stackoverflow.com/questions/1315 ... d-behavior

See the top answer. This leads to the following solution (I don't think there is any reason to use static_cast here, but I don't speak C++):

In C++ static_cast is preferred because of 1) greppability, and 2) in general C-style casts might do a reinterpret_cast under the covers (not in this case, but see #1). It just makes the intent explicit, so it's a good idiom to use.

OK, so it is a matter of taste rather than compliance with the C++ standard.

What do you think of this:

Code: Select all

/// Score enum stores a middlegame and an endgame value in a single integer
/// (enum). The most significant 16 bits are used to store the endgame value
/// and the lower 16 bits are used to store the middlegame value. Take some
/// care to avoid undefined behavior (such as left-shifting a negative int)
/// and relying on implementation-defined behavior (such as casting to signed
/// ints).
enum Score : uint32_t { SCORE_ZERO };

inline Score make_score(int mg, int eg) {
  return Score(((unsigned int)eg << 16) + mg);
}

/// Make sure the platform is reasonable.
static_assert(uint16_t(INT16_MIN) == INT16_MAX + 1, "Range of int16_t is unsupported.");

/// Helper function for correctly casting uint16_t to int16_t.
/// The compiler will optimize this to a no-operation.
inline int16_t cast_to_int16_t(uint16_t v) {
  return v <= INT16_MAX ? int16_t(v) : int16_t(v - INT16_MIN) + INT16_MIN;
}

inline Value eg_value(Score s) {
  return Value(cast_to_int16_t((s + 0x8000U) >> 16));
}

inline Value mg_value(Score s) {
  return Value(cast_to_int16_t(s));
}

[syzygy]

There is still a problem with INT_MIN not converting to unsigned. So a new attempt:

Code: Select all

inline int16_t cast_to_int16_t(uint16_t v) {
  return v <= INT16_MAX ? int16_t(v) : int16_t(v - INT16_MAX - 1) + INT16_MIN;
}

Value eg_value(Score s) {
  return Value(cast_to_int16_t((s + 0x8000U) >> 16));
}

Value mg_value(Score s) {
  return Value(cast_to_int16_t(s));
}

[kbhearn]

I think this line is not correct:

Code: Select all

    if (v >= INT16_MIN)

Since both uint16_t and int16_t fit in int, INT16_MIN will be cast to int (and remain negative) instead of being cast to uint16_t.

So it should be:

Code: Select all

    if (v >= uint16_t(INT16_MIN))

The first attempt still gives the right result, but for the wrong reason.

deleted... too early in the day - let me think more later :) (but certainly with the cast to uint16_t it's right, i just have to look at the definition of INT16_MIN, and promotion rules to see what was going on there.

[syzygy]

http://en.cppreference.com/w/cpp/langua ... conversion

Conversion from signed to unsigned is fully defined by the standard:

If the destination type is unsigned, the resulting value is the smallest unsigned value equal to the source value modulo 2^n where n is the number of bits used to represent the destination type.

That is, depending on whether the destination type is wider or narrower, signed integers are sign-extended or truncated and unsigned integers are zero-extended or truncated respectively.

So the following function is perfectly well defined:

Code: Select all

inline int16_to_uint16(int16_t v) {
    return uint16_t(v);
}

We expect it to do nothing at the machine-code level, but in theory it could, for example, swap the high byte with the low byte.

Conversion from unsigned to signed is the problematic part:

If the destination type is signed, the value does not change if the source integer can be represented in the destination type. Otherwise the result is implementation-defined. (Note that this is different from signed integer arithmetic overflow, which is undefined).

We want to create the inverse of the int16_to_uint16 function without UB and without relying on implementation-defined behavior. So basically, we are only allowed to cast to int16_t values that are within the range 0..INT16_MAX.

So if v is an uint16_t and v <= INT16_MAX, then we can simply take int16_t(v).

Code: Select all

    if (v <= INT16_MAX) return int16_t(v);

If v > INT16_MAX, then we can safely subtract INT16_MAX + 1 from v to get something smaller (i.e. without wrapping around).

If we then have (v - INT16_MAX - 1) <= INT16_MAX, we can safely convert to int16_t. We must then subtract another number such that we subtract 2^16 = 65536 in total. We do this by adding INT16_MIN:

Code: Select all

    if (v - INT16_MAX - 1 <= INT16_MAX)
        return int16_t(v - INT16_MAX - 1) + INT16_MIN;

This works if indeed INT16_MAX + 1 - INT16_MIN = 65536.

We would like the second step to be the last step, i.e. we want that v - INT16_MAX -1 <= INT16_MAX for all uint16_t v > INT16_MAX. This means we want that v <= 2 * INT16_MAX + 1 for all uint16_t v.

In other words, we need that 65535 <= 2 * INT16_MAX + 1, so INT16_MAX >= 32767.

And we need that INT16_MIN = INT16_MAX + 1 - 65536.

The normal values are INT16_MAX = 32767 and INT16_MIN = -32768, which makes everything work. And I really don't see how they could have any other values given that int16_t must be 16 bits wide with no padding bits and use 2's complement for negative values.

So putting things together we get:

Code: Select all

inline uint16_to_int16(uint16_t v) {
    return v <= INT16_MAX ? int16_t(v)
                          : int16_t(v - INT16_MAX - 1) + INT16_MIN;
}

And I don't think there is a need for testing whether INT16_MIN and INT16_MAX are sane...

[kbhearn]

yes, it appears you're right - 16 bit integers signed or unsigned get promoted to signed int before operations because operations smaller than int never happen directly on them, so converting the signed quantity to uint16_t first is necessary to ensure INT16_MIN is expressed as the correct positive quantity for unsigned math (INT16_MIN was of type int to begin with anyways). In the linked solution they were dealing with unsigned int and thus the automatic promotion was int to unsigned int and the desired behavior was obtained without explicit casts.

Your latest solution looks correct as well i think if it still compiles to the desired code :)

could also be written as i think...

Code: Select all

inline int16_t cast_to_int16_t(uint16_t v) { 
  return v <= INT16_MAX ? v : v - (uint16_t)INT16_MIN + INT16_MIN; 
}

the casts to int16_t being implicit from return type, and the promotion of v to int also being implicit because operations always happen on int or larger apparently even if both operands are the same type and smaller than int.

[syzygy]

the casts to int16_t being implicit from return type

I thought C++ did not like that, but g++ is not complaining now... (It does complain when I don't cast to Value, I guess because that's an enum.)

Yes, since we are working with small values and everything will be promoted to int anyway, we can simply subtract 65536 directly, uint16_t(INT16_MIN) - INT16_MIN being a fancy way of writing 65536.

So actually it is really simple if we don't bother with INT16_MIN/MAX:

Code: Select all

    return v <= 0x7fff ? v : v - 0x10000;