Multiplication of two packed signed integers in one

Question

The Stockfish chess engine needs to store, for its evaluation, both an endgame score and a middlegame score.

Instead of storing them separately, it packs them into one int. The middlegame score is stored in the lower 16 bits. The endgame score is stored in the higher 16 bits, as-is if the middlegame score is positive or minus one if it is negative.

This has the advantage that operations (addition, subtraction, negation and multiplication) can be done for both numbers in parallel.

Here is the code:

/// Score enum stores a middlegame and an endgame value in a single integer (enum).
/// The least significant 16 bits are used to store the middlegame value and the
/// upper 16 bits are used to store the endgame value. We have to take care to
/// avoid left-shifting a signed int to avoid undefined behavior.
enum Score : int { SCORE_ZERO };

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

/// Extracting the signed lower and upper 16 bits is not so trivial because
/// according to the standard a simple cast to short is implementation defined
/// and so is a right shift of a signed integer.
inline Value eg_value(Score s) {
  union { uint16_t u; int16_t s; } eg = { uint16_t(unsigned(s + 0x8000) >> 16) };
  return Value(eg.s);
}

inline Value mg_value(Score s) {
  union { uint16_t u; int16_t s; } mg = { uint16_t(unsigned(s)) };
  return Value(mg.s);
}

#define ENABLE_BASE_OPERATORS_ON(T)                                \
constexpr T operator+(T d1, int d2) { return T(int(d1) + d2); }    \
constexpr T operator-(T d1, int d2) { return T(int(d1) - d2); }    \
constexpr T operator-(T d) { return T(-int(d)); }                  \
inline T& operator+=(T& d1, int d2) { return d1 = d1 + d2; }       \
inline T& operator-=(T& d1, int d2) { return d1 = d1 - d2; }

ENABLE_BASE_OPERATORS_ON(Score)

/// Only declared but not defined. We don't want to multiply two scores due to
/// a very high risk of overflow. So user should explicitly convert to integer.
Score operator*(Score, Score) = delete;

/// Division of a Score must be handled separately for each term
inline Score operator/(Score s, int i) {
  return make_score(mg_value(s) / i, eg_value(s) / i);
}

/// Multiplication of a Score by an integer. We check for overflow in debug mode.
inline Score operator*(Score s, int i) {

  Score result = Score(int(s) * i);

  assert(eg_value(result) == (i * eg_value(s)));
  assert(mg_value(result) == (i * mg_value(s)));
  assert((i == 0) || (result / i) == s);

  return result;
}

I understand how addition, subtraction and negation work, but what I have trouble understanding is multiplication. How does multiplying the integer multiplies both the endgame and the middlegame scores together correctly?

Answer 1

The reason that multiplication works here, even for negative middlegame score, is, despite the document says:

The least significant 16 bits are used to store the middlegame value and the upper 16 bits are used to store the endgame value.

This statement isn't entirely true.

---

As an example, if you have mg = -10, ed = 3, if we simply take the description in the document, we should get something like:

mg =                     | 1111 1111 1111 0110
ed = 0000 0000 0000 0011 | 
-------------------------+--------------------
     0000 0000 0000 0011 | 1111 1111 1111 0110

However, if we look at the logic in make_score:

Score((int)((unsigned int)eg << 16) + mg)

Note that we are actually promoting the number to int, so what we actually get is:

     1111 1111 1111 1111 | 1111 1111 1111 0110
   + 0000 0000 0000 0011 | 0000 0000 0000 0000
-------------------------+--------------------
 (1) 0000 0000 0000 0010 | 1111 1111 1111 0110
                       ^
             this bit is different

---

Now go back to the math part, what we have is essentially: 3⋅2¹⁶-10.

Now say we multiply it with 37, we will get (3⋅2¹⁶⋅37)-(10⋅37), or 111⋅2¹⁶-370, or in binary:

     0000 0000 0110 1111 | 0000 0000 0000 0000
   - 0000 0000 0000 0000 | 0000 0001 0111 0010
-------------------------+--------------------

Since the lowest 16 bits of 111⋅2¹⁶ are all 0s, this operation is basically having the higher 16 bits -1, and the lower 16 bits will be the bitwise negation of 370 then +1, or:

     0000 0000 0110 1110 | 1111 1110 1000 1110

---

In fact, as long (unsigned)(mg⋅k) is less than 2¹⁶, then doing multiplication in the lower bits will never affect the higher bits.

Answer 2

Multiplying two packed integers doesn't work. But multiplying by a constant works, as long as you have enough padding bits.

Imagine it in base ten, it becomes easier:

23 and 31 packed with a thousand factor: 230031

Let's multiply by 3, we would get 69 and 93

And 230031 * 3 is 690093. So, you can do both multiplication at once, as long as the number in the lowest bits doesn't overflow over the highest-bits number.

The same magic happens if you look at your number in hexadecimal. But, to me, it is easier to understand in decimal.

Answer 3

Here's a proof, assuming addition works which you already understand.

It involves some algebra, so here's some handy notation for that. All variables are signed 16-bit values, 2's complement representation, unless stated otherwise.

S(eg,mg) = [eg - neg(mg), mg]

Here eg is an endgame score, and mg is a midgame score and [,] shows the bits of values packed into a 32-bit 2's complement signed integer. Most significant bits are to the left. S(eg,mg) is the representation of those scores. Here neg(x) is 1 if x is negative and 0 otherwise, so that the requirement that the representation of eg in the upper bits has one subtracted if mg is negative is satisfied.

This is what make_score should do (bug — for example it is not consistent with eg_value for negative mg).

We want to show that for any 32-bit signed integer i, multiplying S(eg,mg) by i just models multiplying eg and mg by i, which can be precisely stated as

(T) i*S(eg,mg) = S(i*eg, i*mg) where 16-bit multiplications are used in the arguments.

Proof: If i=0 this is obvious. Suppose that i>0 and that addition works, i.e. adding representations adds their endgame scores and adds their midgame scores. i.e. suppose

(A) S(eg1,mg1) + S(eg2,mg2) = S(eg1+eg2,mg1+mg2) for any arguments.

Then repeated use of (A) establishes (T) as follows.

i*S(eg,mg) 
        // sum of i copies of S(eq,mq)
    = S(eg,mg) + S(eg,mg) + S(eg,mg) + ... + S(eg,mg)
        // (A) on first two terms
    = S(eg+eg,mg+mg) + S(eg,mg) + ... + S(eg,mg)
    = S(2*eg,2*mg) + S(eg,mg) + ... + S(eg,mg)
        // (A) on first two remaining terms
    = S(2*eg+eg,2*mg+mg) + ... + S(eg,mg)
    = S(3*eg,3*mg) + ... + S(eg,mg)
        // ...
    = S(i*eg,i*mg)

So now (T) is established for all but negative i values.

Suppose i < 0, and let i = -j. Then

i*S(eg,mg) 
    = (-1)*j*S(eg,mg)
        // j is positive
    = (-1)*S(j*eg,j*mg)
       // if (T) works for (-1)
    = S((-1)*j*eg,(-1)*j*mg)
    = S((-j)*eg,(-j)*mg)
    = S(i*eg,i*mg)

so (T) is true for negative i provided it is true for i = -1, which is proved below.

This is the crux of the matter: working for scaling by (-1), i.e. proving that -S(eg,mg) = S(-eg,-mg). The proof below completes the proof of (T), solving the problem. Here's the argument:

-S(eq,mq) = -[eg - neg(mg), mg]

and we want to show this equal to

S(-eg,-mg) = [(-eg) - neg(-mg), (-mg)]

and here's some algebra that does just that. It makes liberal use of the well known 2's complement identity that -a = ~a + 1, i.e. the arithmetic negation is one more than the bitwise negation.

-[eg - neg(mg), mg]
            // `-a = ~a + 1`
        = ~[eg - neg(mg), mg] + 1
            // ~ is bitwise
        = [~(eg - neg(mg)), ~mg] + 1
            // if mg=0 the carry on adding 1 will propagate to the upper bits
case1: mg=0
[~(eg - neg(mg)), ~mg] + 1
           // neg(mg) = 0
        = [~eg, ~mg] + 1
            // ~mg is a bit pattern of all ones
        = [~eg + 1, ~mg + 1]
            // `~a = -a - 1`
        = [-eg, -mg]
            // neg(-mg)=0 because mg=0
        = [(-eg) - neg(-mg), (-mg)] 
        = S(-eg,-mg) as desired.
case2: mg≠0
[~(eg - neg(mg)), ~mg] + 1
            // carry does not propagate to upper bits
        = [~(eg - neg(mg)), ~mg + 1]
            // `~a = -a - 1`
        = [-(eg - neg(mg)) - 1, -mg]
        = [-eg - (1 - neg(mg)), -mg]
            // neg(-mg) = 1 - neg(mg) for mg≠0
        = [(-eg) - neg(-mg), (-mg)]
        = S(-eg,-mg) as desired.

Answer 4

Let's take a look at the important Code-Snippet (which I commented for easier reading purposes):

inline Score operator*(Score s, int i) {
  // Multiply the 'Score' value by the integer and store the result in 'result'
  Score result = Score(int(s) * i);

  // Assert that the endgame and middlegame scores in 'result' are correct
  assert(eg_value(result) == (i * eg_value(s)));
  assert(mg_value(result) == (i * mg_value(s)));

  // Assert that the 'result' value can be correctly divided by 'i' to obtain the original 'Score' value
  assert((i == 0) || (result / i) == s);

  // Return the 'result' value
  return result;
}

In the following, I'll go through how to code works exactly for the Score s being 0x00001234 and multiplying by an Integer of i = 2:

1. The Score value 0x00001234 is multiplied by 2, resulting in the value 0x00002468. This value is stored in the result variable.
2. The eg_value() function is called to extract the endgame score from the result value. In this case, the endgame score is 0x0024, which is then multiplied by 2. The result is compared to the expected value of 0x0048 using the assert() function. If the values do not match, an assertion failure occurs.
3. The mg_value() function is called to extract the middlegame score from the result value. In this case, the middlegame score is 0x0068, which is then multiplied by 2. The result is compared to the expected value of 0x00D0 using the assert() function. If the values do not match, an assertion failure occurs.
4. The result value is divided by 2 using the result / i expression. The result of this division should be the original Score value of 0x00001234. This result is compared to the expected value using the assert() function. If the values do not match, an assertion failure occurs.
5. If all of the assert() checks pass, the result value is returned. In this case, the returned value would be 0x00002468.

All in all, Stockfish correctly multiplies the Score value by 2 by shifting the bits representing the middlegame and endgame scores to the left by one position. This effectively multiplies both scores by 2, resulting in the correct result value!

Example 1: A second more in-depth explanation with the help of each assertion step: In the following let's consider s = make_score(4, 8) and i = 2 being called with operator*(s, i).

First, the result will be calculated as follows:

Score result = Score(int(s) * i);
// result = Score(int(make_score(4, 8)) * 2);
// result = Score(int(0x00080004) * 2);
// result = Score(0x0010 * 2);
// result = Score(0x0020);
// result = make_score(0, 32);

Next, we will assert() - as explained above - to prevent e.g. an Overflow:

assert(eg_value(result) == (i * eg_value(s)));
// assert(eg_value(make_score(0, 32)) == (2 * eg_value(make_score(4, 8))));
// assert(32 == (2 * 8));
// assert(true);

assert(mg_value(result) == (i * mg_value(s)));
// assert(mg_value(make_score(0, 32)) == (2 * mg_value(make_score(4, 8))));
// assert(0 == (2 * 4));
// assert(true);

assert((i == 0) || (result / i) == s);
// assert((2 == 0) || (make_score(0, 32) / 2) == make_score(4, 8));
// assert((false) || (make_score(0, 16) == make_score(4, 8)));
// assert(true);

As all of those assert() statements evaluated to true, the function will return the result.

Example 2: As you mentioned in another reply that you struggled with understanding a negative middlegame score and a positive endgame score, here is a visualization of this situation:

Same play as above - e.g. going through the code with annotations to visualize each step (including the needed assertions to verify the code). In this example I just flipped four to being negative: s = make_score(-4, 8)!

Again, start with calculating result:

Score result = Score(int(s) * i);
// result = Score(int(make_score(-4, 8)) * 2);
// result = Score(int(0x000800FB) * 2); // special treatment for negative mg value
// result = Score(0x0010 * 2);
// result = Score(0x0020);
// result = make_score(0, 32);

Note that in this case, the middlegame score is negative, so the make_score() function stores the endgame score as -1 instead of the actual value in order to correctly handle negation. This means that the multiplication applied to the underlying integer value of the Score does not affect the endgame score, and only affects the middlegame score, which is stored in the lower 16 bits.

And for the sake of completeness here are the assert()s:

assert(eg_value(result) == (i * eg_value(s)));
// assert(eg_value(make_score(0, 32)) == (2 * eg_value(make_score(-4, 8))));
// assert(32 == (2 * 8));
// assert(true);

assert(mg_value(result) == (i * mg_value(s)));
// assert(mg_value(make_score(0, 32)) == (2 * mg_value(make_score(-4, 8))));
// assert(0 == (2 * -4));
// assert(true);

assert((i == 0) || (result / i) == s);
// assert((2 == 0) || (make_score(0, 32) / 2) == make_score(-4, 8));
// assert((false) || (make_score(0, 16) == make_score(-4, 8)));
// assert(true);

In order to tackle a mathematical "proof" we have to consider the representation of the Score enum as a single integer value with the lower 16 bits representing the middlegame value and the upper 16 bits representing the endgame value. Let's assume that the original Score value s is represented as an integer with the following binary representation:

s = a[31]a[30]...a[16]b[15]...b[0]

where a[31]a[30]...a[16] is the binary representation of the endgame value, and b[15]...b[0] is the binary representation of the middlegame value.

If we now multiply this value by an integer i, the result will be a new integer with the following binary representation:

s * i = c[31]c[30]...c[16]d[15]...d[0]

where c[31]c[30]...c[16] is the binary representation of the endgame value multiplied by i, and d[15]...d[0] is the binary representation of the middlegame value multiplied by i.

In order to check that the multiplication is correct, the implementation asserts that the eg_value and mg_value of the result match the expected values. This can be proven by considering the following:

• The eg_value of the result is calculated by first converting the result to an unsigned integer and then right shifting it by 16 bits. This effectively discards the lower 16 bits of the result and only keeps the upper 16 bits, which are the binary representation of the endgame value multiplied by i.

• The mg_value of the result is calculated by converting the result to an unsigned integer and then discarding the upper 16 bits, which leaves only the lower 16 bits, which are the binary representation of the middlegame value multiplied by i.

Since the eg_value and mg_value of the result are calculated in this way, it is guaranteed that they will match the expected values, as long as the multiplication does not overflow the integer representation of the Score enum. This is why the implementation also asserts that the result divided by the original integer is equal to the original Score value, as this is a way to check that the multiplication did not overflow.

Therefore, we can conclude that the operator* implementation for the Score enum is correct and will always produce the expected result, as long as the multiplication does not overflow the integer representation of the Score.

Let's consider the "Overflow":

• The middlegame and endgame values are represented by the lower and upper 16 bits of the Score value, respectively. Therefore, the maximum possible value for the middlegame and endgame values is 2^15 - 1 = 32767, and the minimum possible value is -32768.

• The multiplication of the middlegame and endgame values by the integer i will not overflow if the result is within the range of -2^31 to 2^31 - 1, as this is the range of values that can be represented by the Score enum.

• Since the maximum possible value for the middlegame and endgame values is 32767, the maximum possible result of the multiplication is 32767 * i. Therefore, the multiplication will not overflow if 32767 * i is within the range of -2^31 to 2^31 - 1.

• We can prove that 32767 * i will always be within the range of -2^31 to 2^31 - 1 by considering the following cases:

  1. If i > 0, then 32767 * i will be within the range of 0 to 2^31 - 1. This is because the maximum possible value of i is 2^31 - 1, and therefore 32767 * i will be at most (2^31 - 1) * (2^31 - 1) = 2^62 - 2^31 + 1, which is less than 2^31 - 1.

  2. If i < 0, then 32767 * i will be within the range of -2^31 to 0. This is because the minimum possible value of i is -(2^31 - 1), and therefore 32767 * i will be at least -(2^31 - 1) * (2^31 - 1) = -(2^62 - 2^31 + 1), which is greater than -(2^31 - 1).

Small addition to your comment:

When the middlegame and endgame values of the Score value are extracted by the mg_value and eg_value functions, they are not being multiplied by the integer value. Instead, the functions are simply extracting the lower and upper 16 bits of the Score value, respectively, and then converting them to the corresponding middlegame and endgame values.

In the operator* implementation, the middlegame and endgame values are multiplied by the integer value before they are passed to the make_score function. This means that the resulting Score value will have middlegame and endgame values that are the product of the original values and the integer value.

Regarding the case where the endgame value is stored minus one, this does not affect the multiplication of the endgame value by the integer value. The reason is that the endgame value is first converted to an unsigned integer before it is multiplied by the integer value, which effectively removes the minus one stored in the endgame value. Therefore, the endgame value will be multiplied by the integer value in the same way as if it was stored as a regular positive value.

To illustrate this, let's consider an example where the original Score value has a middlegame value of 5 and an endgame value of -6 (stored as -7 in the Score value). If we multiply this value by 2, the result will be as follows:

s = make_score(5, -7)
s * 2 = make_score(5 * 2, (-7 * 2) + 2^16)
= make_score(10, 2^16 - 14)

As we can see, the endgame value of the result is calculated as (-7 * 2) + 2^16, which is equivalent to (-7 * 2) + 65536. This is because the endgame value is first converted to an unsigned integer (65529) before it is multiplied by 2, and then the resulting value is added to 2^16 to restore the minus one that was stored in the original endgame value. Therefore, the endgame value of the result is 2^16 - 14, which is the correct value that is the product of the original endgame value and the integer value.

EDIT:

The question in the chat-room was why (eg*2^16+mg)/n=(eg*2^16)/n+mg/n=(eg/n)*2^16+mg/n doesn't hold for the division then (in comparison to the unified approach for multiplication). You can write it as (eg2^16)/n+mg/n which yields the same as operator/ does: mg_value(s) / i, eg_value(s) / i. The rest violates PEMDAS due to the order of multiplication and division (in the first two terms you perform multiplication before division and in the third vice-versa)!

So multiplying endgame by 2^16 and then dividing the result by n is in this context not allowed and therefore we solved the issue why operator/ calls it with split parameters (not treating it independently <-> independently treatment of multiplication)!