TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Gerd Isenberg

Joined: 08 Mar 2006
Posts: 1802
Location: Hattingen, Germany

Post subject: Re: Resource for bit twiddlers    Posted: Mon Jun 04, 2007 2:58 pm

Gerd Isenberg wrote:
 jwes wrote: I just ran accross this. It is a preprint of part of Knuth's Art of Computer Programming, Vol 4, and covers bit twiddling tricks and techniques. http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz

This is really a great ressource - thanks for providing the link.

"tweaking several bytes at once" (page 19), nicely explains some SWAR (SIMD within a regsiter) tricks suggested by H.G. Dietz.

 Code: 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)

For bytewise math, H = 0x8080808080808080 and L = 0x0101010101010101. But one can use arbitrary masks for other sizes such as 6*10 or 5*12 bit as well - or even 64-bit structures with mixed "word"-sizes.

Performing bytewise or rankwise sub using the o ^(o-2r)-trick saves some instructions compared to one Kogge-Stone attack getter, even with general purpose registers:
 Code: u64 eastAttacks(u64 rooks, u64 empty) {     empty  = empty &  0xfefefefefefefefe;     rooks |= empty & (rooks << 1);     empty  = empty & (empty << 1);     rooks |= empty & (rooks << 2);     empty  = empty & (empty << 2);     rooks |= empty & (rooks << 4);     return (rooks << 1) & 0xfefefefefefefefe; }

 Code: u64 eastAttacks(u64 rooks, u64 empty) {     const u64 H     = 0x8080808080808080;     u64 occupied    = rooks | ~empty;     u64 occNoRook   = rooks ^ occupied;     u64 difference  = ((occNoRook | H) - (rooks & ~H))                     ^  (~occupied & H);     return occupied ^ difference; }

Gerd

I'll hope the attack-getter does not violate any United States Patent

http://aggregate.org/MAGIC/#SIMD%20Within%20A%20Register%20(SWAR)%20Operations
by Dr. Henry G. (Hank) Dietz

 Quote: SIMD Within A Register (SWAR) Operations Before we coined the name SWAR in Fall 1996, we already had defined a complete set of basic operations and described how they could be implemented with good efficiency. On February 4, 1997, we posted this fairly complete overview document and there also are slides from a seminar presentation I gave at Purdue. These methods were used in our SWARC compiler and were detailed in a number of our publications throughout the 1990s. We hadn't posted them on this page because they were so prominently published elsewhere. However, much to our surprize, United States Patent 7039906, "Compiler for enabling multiple signed independent data elements per register," was filed October 20, 2000 and was issued to IBM on May 2, 2006! By our reading, this patent appears to seriously overlap my and Randy Fisher's earlier published work -- much of which was cited by the patent examiner. I am posting this note here so that people who happen to hear about the IBM patent will not be discouraged from using the prior art technologies developed by us, which, by being cited in the patent, are explicitly not covered by the patent.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
J. Wesley Cleveland Fri May 04, 2007 1:55 am
Gerd Isenberg Mon May 28, 2007 12:40 pm
Gerd Isenberg Mon May 28, 2007 3:16 pm
Gerd Isenberg Mon May 28, 2007 4:35 pm
Gerd Isenberg Wed May 30, 2007 5:55 pm
Pradu Kannan Wed May 30, 2007 10:51 pm
Gerd Isenberg Thu May 31, 2007 6:17 am
Pradu Kannan Fri Jun 01, 2007 12:16 am
Gerd Isenberg Fri Jun 01, 2007 8:19 am
Re: Resource for bit twiddlers Gerd Isenberg Mon Jun 04, 2007 2:58 pm

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
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