TalkChess.com :: View topic - Resource for bit twiddlers

TalkChess.com
Hosted by Your Move Chess & Games

FAQ

Memberlist

Usergroups

Profile

Resource for bit twiddlers

TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

View previous topic :: View next topic

Author

Message

Pradu Kannan

Joined: 11 Mar 2006
Posts: 287
Location: Atlanta, GA

Post subject: Re: Resource for bit twiddlers Posted: Wed May 30, 2007 10:51 pm

Gerd Isenberg wrote:

Some further optimization by using common sub-expressions. One operation less, and more importantly, only three scratch registers used. The compiler prefers 10 byte opcode loading rax with an 64-bit immediate, while there is already the one's complement in rax, where a 3-byte "not rax" would result in 7 bytes shorter opcode but higher alu-pressure. With 64-bit immediate moves, the 32-byte prefetch of the K10 makes sense.

Code:

u64 eastAttacks(u64 rooks, u64 empty)
{
const u64 H = 0x8080808080808080;
u64 inclRook = rooks | H | ~empty;
u64 exclRook = (rooks &= ~H ) ^ inclRook;
u64 attacks = (exclRook - rooks) ^ inclRook;
return attacks;
}

rooks$ = 8
empty$ = 16
?eastAttacks@@YA_K_K0@Z PROC
00000 48 f7 d2 not rdx
00003 48 b8 80 80 80
80 80 80 80 80 mov rax, 8080808080808080H
0000d 48 0b d1 or rdx, rcx
00010 48 0b d0 or rdx, rax
00013 48 b8 7f 7f 7f ; not rax would also possible here
7f 7f 7f 7f 7f mov rax, 7f7f7f7f7f7f7f7fH
0001d 48 23 c8 and rcx, rax
00020 48 8b c2 mov rax, rdx
00023 48 33 c1 xor rax, rcx
00026 48 2b c1 sub rax, rcx
00029 48 33 c2 xor rax, rdx
0002c c3 ret 0

If one passes already the occupied set, and guarantee that rooks are subset of occupied, one safes another two instructions of course, but that loses a bit flexibility and tends to confuse due to the prototype and semantic of the Kogge-Stone getters.

Gerd

From what I can understand this subtraction technique can only be used for right fills and left fills. Here's what I could infer from your filling algorithm:

I'll term rooks as squares.

so basically the concept is to use the fact that

Code:

(LSB at left, looking at only first rank for now)
HFile "rooks" Result
00000001 - 00001000 = 00001110
Result HFile Fill
00001110 ^ 00000001 = 00001111

Now lets add an occupancy to see if it still works:

Code:

(LSB at left like for the first rank)
HFile|occ "rooks" Result
00000011 - 00001000 = 00001101
Result HFile|occ Fill
00001101 ^ 00000011 = 00001110

Works perfect! But because of the subtraction, we have to make sure the occupancy and the rook don't coinside eg:

Code:

(LSB at left like for the first rank)
HFile|occ "rooks" Result
00001001 - 00001000 = 00000001 (BAD)
Result HFile|occ Fill
00000001 ^ 00000011 = 00000010 (WRONG)

So we have to make sure we take the rooks out of the occupancy. Assuming the same occupancy as before:

Code:

((HFile|occ)&~rooks) - "rooks" Result
00000001 - 00001000 = 00001110
Result ^ ((HFile|occ)&~rooks) = Fill
00001110 00000001 = 00001110

From the above we can make an easy right fill:

Code:

U64 rightFill(U64 squares, U64 occ)
{
occ = (occ|FILEHBB)&~squares; //occupancy without squares
return ((occ - squares)^occ) | squares; //xor to get rid of unused occupancy
}

I hope my iterpretation is correct? Is it also possible to to do fills other than left and right with the subtraction technique?

Display posts from previous:

Subject	Author	Date/Time
Resource for bit twiddlers	J. Wesley Cleveland	Fri May 04, 2007 1:55 am
Re: Resource for bit twiddlers	Gerd Isenberg	Mon May 28, 2007 12:40 pm
Re: Resource for bit twiddlers	Gerd Isenberg	Mon May 28, 2007 3:16 pm
Re: Resource for bit twiddlers	Gerd Isenberg	Mon May 28, 2007 4:35 pm
Re: Resource for bit twiddlers	Gerd Isenberg	Wed May 30, 2007 5:55 pm
Re: Resource for bit twiddlers	Pradu Kannan	Wed May 30, 2007 10:51 pm
Re: Resource for bit twiddlers	Gerd Isenberg	Thu May 31, 2007 6:17 am
Re: Resource for bit twiddlers	Pradu Kannan	Fri Jun 01, 2007 12:16 am
Re: Resource for bit twiddlers	Gerd Isenberg	Fri Jun 01, 2007 8:19 am
Re: Resource for bit twiddlers	Gerd Isenberg	Mon Jun 04, 2007 2:58 pm

TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum