NibbleArrayOfNibbles

Home * Programming * Data * Nibble

A Nibble, also called Nybble, is a term for a four- bit aggregation. It is the half of a Byte. With four bits one can distinct 16 states, 0000B to 1111B as binary code, representing decimal numbers from 0 to 15.

One hexadecimal digit {‘0’..‘9’, ‘A’ ..‘F’} exactly covers one nibble. Since bytes are considered atomic items, nibble endianness is no issue. Per definition a least significant nibble covers the least significant bits 0..3 of a byte, the most significant nibble the bits 4..7 of a byte. If we write the value of a byte with two hexadecimal digits, we use the usual big-endian notation, e.g. in 0x3F, ‘3’ is the most significant nibble (digit) and ‘F’ the least significant one.

Signed Nibbles#

In a signed nibble Two’s Complement representation, bit 3 is interpreted as sign bit.

| binary | hex | unsigned | signed

Array of Nibbles#

An array of N nibbles can be declared as array of (N+1)/2 bytes, for instance for a dense Board Representation.

BYTE nibbleBoard[32];

And this is how to extract piece-codes from a that board:

int getPiece(int square) {
   int shift = (square & 1)  << 2; // 4 or 0
   return nibbleBoard[square >> 1] >> shift) & 15;
}

void setPiece(int square, int piece) {
   int shift = (square & 1) << 2; // 4 or 0
   nibbleBoard[square >> 1] &= (BYTE)(  240 >> shift);
   nibbleBoard[square >> 1] |= (BYTE)(piece << shift);
}

This is considerable more effort than simple array access with at least byte granulation, in both code size and runtime - and array board representations are likely not member of a search stack, but updated incrementally during make and unmake, it does not seem to make sense to use nibbleBoards as mentioned to save some data bytes. However, Vladan Vučković proposed the Nibble-Board as used in his program Axon and its parallel version Achilles, dubbed Compact Chessboard Representation, declared as array of eight 32-bit or four 64-bit integers, intended for register processing [1] [2] [3].

SWAR Nibbles#

To apply ‘add’ or ‘sub’ on vectors of nibbles (or any arbitrary structure) SWAR-wise within a 32-bit or 64-bit register, we have to take care carries and borrows don’t wrap around. Thus we apply a mask of all most significant bits (H) and ‘add’ in two steps, one ‘add’ with MSB clear and one add modulo 2 aka ‘xor’ for the MSB itself. For nibble-wise math of a vector of eight nibbles inside a 32-bit register, H is 0x88888888 and L is 0x11111111.

SWAR add z = x + y
    z = ((x &~H) + (y &~H)) ^ ((x ^ y) & H)
 
SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)
 
SWAR average z = (x+y)/2 based on x + y = (x^y) + 2*(x&y)
    z = (x & y) + (((x ^ y) & ~L) >> 1)

See also#

• Byte
• Quad-Bitboards containing “vertical” nibbles
• SWAR
• SWAR Population Count

Publications#

• Vladan Vučković (2008). The Compact Chessboard Representation. ICGA Journal, Vol. 31, No. 3
• Vladan Vučković (2012). An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding. Yugoslav Journal of Operations Research, Vol. 22, No. 1, pdf

Forum Posts#

• CCR board representation by Maksim Korzh, CCC, November 25, 2018 » Array of Nibbles

External Links#

• Nibble from Wikipedia

References#

1. ↑ Vladan Vučković (2008). The Compact Chessboard Representation. ICGA Journal, Vol. 31, No. 3
2. ↑ Vladan Vučković (2012). An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding. Yugoslav Journal of Operations Research, Vol. 22, No. 1, pdf
3. ↑ CCR board representation by Maksim Korzh, CCC, November 25, 2018

Up one Level