25,161
edits
Changes
Created page with "'''Home * Programming * Data * Nibble''' A '''Nibble''', also called Nybble, is a term for a four-bit aggregation. It is the half of a Byte...."
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * Nibble'''
A '''Nibble''', also called Nybble, is a term for a four-[[Bit|bit]] aggregation. It is the half of a [[Byte]]. With four bits one can distinct 16 states, 0000B to 1111B as [https://en.wikipedia.org/wiki/Binary_code binary code], representing [https://en.wikipedia.org/wiki/Decimal decimal] numbers from 0 to 15.
One [https://en.wikipedia.org/wiki/Hexadecimal hexadecimal] digit {'0'..'9', 'A' ..'F'} exactly covers one nibble. Since bytes are considered atomic items, nibble [[Endianness|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|big-endian]] notation, e.g. in 0x3F, '3' is the most significant nibble (digit) and 'F' the least significant one.
=Nibble as Type=
A nibble is appropriate to hold the value ranges of
* [[Pieces]]
* [[Files]] (3 bits, but see [[0x88]])
* [[Ranks]] (3 bits, but see [[0x88]])
* [[Diagonals]]
* [[Anti-Diagonals]]
* [[Distance]] (3 bits)
* [[Manhattan-Distance]]
* [[Knight-Distance]] (3 bits)
* [[Direction#MoveDirections|Move Directions]]
=Signed Nibbles=
In a signed nibble [[Two's Complement]] representation, bit 3 is interpreted as sign bit.
{| class="wikitable"
|-
! binary
! hex
! unsigned
! signed
|-
! 0000B
| style="text-align:right;" | 0x0
| style="text-align:right;" | 0
| style="text-align:right;" | 0
|-
! 0001B
| style="text-align:right;" | 0x1
| style="text-align:right;" | 1
| style="text-align:right;" | 1
|-
! 0010B
| style="text-align:right;" | 0x2
| style="text-align:right;" | 2
| style="text-align:right;" | 2
|-
! 0011B
| style="text-align:right;" | 0x3
| style="text-align:right;" | 3
| style="text-align:right;" | 3
|-
! 0100B
| style="text-align:right;" | 0x4
| style="text-align:right;" | 4
| style="text-align:right;" | 4
|-
! 0101B
| style="text-align:right;" | 0x5
| style="text-align:right;" | 5
| style="text-align:right;" | 5
|-
! 0110B
| style="text-align:right;" | 0x6
| style="text-align:right;" | 6
| style="text-align:right;" | 6
|-
! 0111B
| style="text-align:right;" | 0x7
| style="text-align:right;" | 7
| style="text-align:right;" | 7
|-
! 1000B
| style="text-align:right;" | 0x8
| style="text-align:right;" | 8
| style="text-align:right;" | -8
|-
! 1001B
| style="text-align:right;" | 0x9
| style="text-align:right;" | 9
| style="text-align:right;" | -7
|-
! 1010B
| style="text-align:right;" | 0xA
| style="text-align:right;" | 10
| style="text-align:right;" | -6
|-
! 1011B
| style="text-align:right;" | 0xB
| style="text-align:right;" | 11
| style="text-align:right;" | -5
|-
! 1100B
| style="text-align:right;" | 0xC
| style="text-align:right;" | 12
| style="text-align:right;" | -4
|-
! 1101B
| style="text-align:right;" | 0xD
| style="text-align:right;" | 13
| style="text-align:right;" | -3
|-
! 1110B
| style="text-align:right;" | 0xE
| style="text-align:right;" | 14
| style="text-align:right;" | -2
|-
! 1111B
| style="text-align:right;" | 0xF
| style="text-align:right;" | 15
| style="text-align:right;" | -1
|}
<span id="ArrayOfNibbles"></span>
=Array of Nibbles=
An [[Array|array]] of N nibbles can be declared as array of (N+1)/2 bytes, for instance for a dense [[Board Representation]].
<pre>
BYTE nibbleBoard[32];
</pre>
And this is how to extract piece-codes from a that board:
<pre>
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);
}
</pre>
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|stack]], but updated incrementally during [[Make Move|make]] and [[Unmake Move|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 <ref>[[Vladan Vučković]] ('''2008'''). ''The Compact Chessboard Representation''. [[ICGA Journal#31_3|ICGA Journal, Vol. 31, No. 3]]</ref> <ref>[[Vladan Vučković]] ('''2012'''). ''An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding''. [http://www.doiserbia.nb.rs/issue.aspx?issueid=1761 Yugoslav Journal of Operations Research, Vol. 22, No. 1], [http://www.doiserbia.nb.rs/img/doi/0354-0243/2012/0354-02431200011V.pdf pdf]</ref>.
=SWAR Nibbles=
To apply 'add' or 'sub' on vectors of nibbles (or any arbitrary structure) [[SIMD and SWAR Techniques#SWAR|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.
<pre>
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)
</pre>
=See also=
* [[Byte]]
* [[Quad-Bitboards]] containing "vertical" nibbles
* [[SIMD and SWAR Techniques#SWAR|SWAR]]
* [[Population Count#SWARPopcount|SWAR Population Count]]
=Publications=
* [[Vladan Vučković]] ('''2008'''). ''The Compact Chessboard Representation''. [[ICGA Journal#31_3|ICGA Journal, Vol. 31, No. 3]]
* [[Vladan Vučković]] ('''2012'''). ''An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding''. [http://www.doiserbia.nb.rs/issue.aspx?issueid=1761 Yugoslav Journal of Operations Research, Vol. 22, No. 1], [http://www.doiserbia.nb.rs/img/doi/0354-0243/2012/0354-02431200011V.pdf pdf]
=External Links=
* [https://en.wikipedia.org/wiki/Nibble Nibble from Wikipedia]
=References=
<references />
'''[[Data|Up one Level]]'''
A '''Nibble''', also called Nybble, is a term for a four-[[Bit|bit]] aggregation. It is the half of a [[Byte]]. With four bits one can distinct 16 states, 0000B to 1111B as [https://en.wikipedia.org/wiki/Binary_code binary code], representing [https://en.wikipedia.org/wiki/Decimal decimal] numbers from 0 to 15.
One [https://en.wikipedia.org/wiki/Hexadecimal hexadecimal] digit {'0'..'9', 'A' ..'F'} exactly covers one nibble. Since bytes are considered atomic items, nibble [[Endianness|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|big-endian]] notation, e.g. in 0x3F, '3' is the most significant nibble (digit) and 'F' the least significant one.
=Nibble as Type=
A nibble is appropriate to hold the value ranges of
* [[Pieces]]
* [[Files]] (3 bits, but see [[0x88]])
* [[Ranks]] (3 bits, but see [[0x88]])
* [[Diagonals]]
* [[Anti-Diagonals]]
* [[Distance]] (3 bits)
* [[Manhattan-Distance]]
* [[Knight-Distance]] (3 bits)
* [[Direction#MoveDirections|Move Directions]]
=Signed Nibbles=
In a signed nibble [[Two's Complement]] representation, bit 3 is interpreted as sign bit.
{| class="wikitable"
|-
! binary
! hex
! unsigned
! signed
|-
! 0000B
| style="text-align:right;" | 0x0
| style="text-align:right;" | 0
| style="text-align:right;" | 0
|-
! 0001B
| style="text-align:right;" | 0x1
| style="text-align:right;" | 1
| style="text-align:right;" | 1
|-
! 0010B
| style="text-align:right;" | 0x2
| style="text-align:right;" | 2
| style="text-align:right;" | 2
|-
! 0011B
| style="text-align:right;" | 0x3
| style="text-align:right;" | 3
| style="text-align:right;" | 3
|-
! 0100B
| style="text-align:right;" | 0x4
| style="text-align:right;" | 4
| style="text-align:right;" | 4
|-
! 0101B
| style="text-align:right;" | 0x5
| style="text-align:right;" | 5
| style="text-align:right;" | 5
|-
! 0110B
| style="text-align:right;" | 0x6
| style="text-align:right;" | 6
| style="text-align:right;" | 6
|-
! 0111B
| style="text-align:right;" | 0x7
| style="text-align:right;" | 7
| style="text-align:right;" | 7
|-
! 1000B
| style="text-align:right;" | 0x8
| style="text-align:right;" | 8
| style="text-align:right;" | -8
|-
! 1001B
| style="text-align:right;" | 0x9
| style="text-align:right;" | 9
| style="text-align:right;" | -7
|-
! 1010B
| style="text-align:right;" | 0xA
| style="text-align:right;" | 10
| style="text-align:right;" | -6
|-
! 1011B
| style="text-align:right;" | 0xB
| style="text-align:right;" | 11
| style="text-align:right;" | -5
|-
! 1100B
| style="text-align:right;" | 0xC
| style="text-align:right;" | 12
| style="text-align:right;" | -4
|-
! 1101B
| style="text-align:right;" | 0xD
| style="text-align:right;" | 13
| style="text-align:right;" | -3
|-
! 1110B
| style="text-align:right;" | 0xE
| style="text-align:right;" | 14
| style="text-align:right;" | -2
|-
! 1111B
| style="text-align:right;" | 0xF
| style="text-align:right;" | 15
| style="text-align:right;" | -1
|}
<span id="ArrayOfNibbles"></span>
=Array of Nibbles=
An [[Array|array]] of N nibbles can be declared as array of (N+1)/2 bytes, for instance for a dense [[Board Representation]].
<pre>
BYTE nibbleBoard[32];
</pre>
And this is how to extract piece-codes from a that board:
<pre>
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);
}
</pre>
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|stack]], but updated incrementally during [[Make Move|make]] and [[Unmake Move|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 <ref>[[Vladan Vučković]] ('''2008'''). ''The Compact Chessboard Representation''. [[ICGA Journal#31_3|ICGA Journal, Vol. 31, No. 3]]</ref> <ref>[[Vladan Vučković]] ('''2012'''). ''An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding''. [http://www.doiserbia.nb.rs/issue.aspx?issueid=1761 Yugoslav Journal of Operations Research, Vol. 22, No. 1], [http://www.doiserbia.nb.rs/img/doi/0354-0243/2012/0354-02431200011V.pdf pdf]</ref>.
=SWAR Nibbles=
To apply 'add' or 'sub' on vectors of nibbles (or any arbitrary structure) [[SIMD and SWAR Techniques#SWAR|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.
<pre>
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)
</pre>
=See also=
* [[Byte]]
* [[Quad-Bitboards]] containing "vertical" nibbles
* [[SIMD and SWAR Techniques#SWAR|SWAR]]
* [[Population Count#SWARPopcount|SWAR Population Count]]
=Publications=
* [[Vladan Vučković]] ('''2008'''). ''The Compact Chessboard Representation''. [[ICGA Journal#31_3|ICGA Journal, Vol. 31, No. 3]]
* [[Vladan Vučković]] ('''2012'''). ''An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding''. [http://www.doiserbia.nb.rs/issue.aspx?issueid=1761 Yugoslav Journal of Operations Research, Vol. 22, No. 1], [http://www.doiserbia.nb.rs/img/doi/0354-0243/2012/0354-02431200011V.pdf pdf]
=External Links=
* [https://en.wikipedia.org/wiki/Nibble Nibble from Wikipedia]
=References=
<references />
'''[[Data|Up one Level]]'''
