Author: Dann Corbit
Date: 03:09:22 01/22/03
Go up one level in this thread
On January 22, 2003 at 05:33:20, Matt Taylor wrote:
>On January 22, 2003 at 04:27:16, Dann Corbit wrote:
>
>>On January 22, 2003 at 03:29:05, Matt Taylor wrote:
>>
>>>On January 21, 2003 at 17:03:33, Dann Corbit wrote:
>>>
>>>>On January 21, 2003 at 15:48:57, Sander de Zoete wrote:
>>>>
>>>>>The following instruction I found for the new architecture of Intel Chips
>>>>>
>>>>>BSWAP—Byte Swap
>>>>>
>>>>>Description
>>>>>Reverses the byte order of a 32-bit (destination) register:
>>>>>
>>>>>Operation
>>>>>TEMP ¬ DEST
>>>>>DEST(7..0) ¬ TEMP(31..24)
>>>>>DEST(15..8) ¬ TEMP(23..16)
>>>>>DEST(23..16) ¬ TEMP(15..8)
>>>>>DEST(31..24) ¬ TEMP(7..0)
>>>>>Flags Affected
>>>>>None.
>>>>>Opcode Instruction Description
>>>>>0F C8+ rd BSWAP r32 Reverses the byte order of a 32-bit register.
>>>>>
>>>>>It is only valid for 486 architecture.
>>>>>
>>>>>If this instruction can be used, it should be very easy to reverse Reverse
>>>>>BitBoards into Forward Boards again. Saving a lot of updating in make and unmake
>>>>>move and also be much faster using the bitboards for generating attack
>>>>>board for evaluation purposes, incheck checks etc.
>>>>>
>>>>>The thing left to do is to reverse the bits per byte.
>>>>>
>>>>>I use the following trick, but it doesn't seem to work voor the value 9. Let me
>>>>>show you what I mean: (and ofcourse, can you help me?)
>>>>>
>>>>>In C code, it looks like this:
>>>>>
>>>>>typedef unsigned __int64 BITBOARD;
>>>>>
>>>>>void ReverseBitsPerByte(BITBOARD bitboard)
>>>>>{
>>>>>// 1. Load the constant, k = 5555555555555555h
>>>>>BITBOARD k = 0x5555555555555555;
>>>>>
>>>>>// 2. x = [(x shl 1) and k] or [(x and k) shr 1] result is: EFCDAB8967452301
>>>>>bitboard = ((bitboard<<1) & k) | ((bitboard & k)>>1 );
>>>>>}
>>>>>
>>>>>Initial bitboard:
>>>>>11111110
>>>>>11011100
>>>>>10111010
>>>>>10011000
>>>>>01110110
>>>>>01010100
>>>>>00110010
>>>>>00010000
>>>>>
>>>>>Result of ReverseBitsPerByte(bitboard):
>>>>>01111111
>>>>>00111011
>>>>>01011101
>>>>>00011000<--what the ^*&* goes wrong here? Should be 00011001.
>>>>>01101110
>>>>>00101010
>>>>>01001100
>>>>>00001000
>>>>>
>>>>>Thanks for any help or suggestions.
>>>>
>>><snip code>
>>>
>>>These are all basically the same algorithm. It's going to take a while to
>>>rearrange everything when you do it bit-by-bit. Sander has the right idea by
>>>first swapping bytes and then trying to reverse the bits within the bytes (8*2
>>>ops + the swap as opposed to 64*2 ops).
>>
>>The algorithms don't perform identically.
>>They don't require 64 ops.
>>Once you get the "Sander" algorithm completed, compare the two (and also the
>>COBRA algorithm).
>
>Yes, breverse5 is a divide-and-conquer algorithm. The others all iterate 64
>times. Assuming 2 ops/iteration was a gross underestimate as they use heavy
>masking and shifting.
>
>2 bswaps (and probably a mov, too) will reverse the bytes; afterward, the bits
>can be reversed as well.
>
>Not sure when or if I can have a look at COBRA and think about the algorithm --
>I've got more than enough mandatory work right now.
The COBRA algorithm is designed for big bit sequences. I don't know how well it
adapts to 64 bits. I have only just downloaded the paper.
This algorithm:
typedef unsigned long ling Bitboard;
Bitboard breverse5(Bitboard n)
{
int i = 64;
Bitboard m = -1;
while (i /= 2)
m ^= m << i, n = n >> i & m | (n & m) << i;
return n;
}
iterates 6 times. I suspect it will be faster than something table driven.
Perhaps also faster than 8 mask and shift operations.
I'll be surprised if anything can beat it by 20%.
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.