Author: Gerd Isenberg
Date: 18:19:08 09/12/02
Hi all,
My first MMX-Routine (MSC inline asm) that gains considerable performance!
The flood filler, introduced to me by Steffan Westcott.
He answered my "algorithm question", to find a connection between two squares
along a given path with his flood fill c-implementation. With the word
"floodfill" it became immediatly clear to me, that's it.
I heared about flood fill in graphics context before, eg. filling boardered
pixel areas, but had no clue, that it is THE perfect solution to my connection
problem.
As Stefan was so kind, sharing his fine c-code, i like to acknowledge him and
others answered in a very constructive way, by "proudly" presenting this mmx
code. (Any improvement hints are welcome :-)
The routine returns the shortest distance (from, to) along a given path-set, eg.
all squares a king may enter, but zero is no connection. Hopefully usefull in
several endings looking for king distance considering squares controlled by
enemy or occupied by friends. Including bottlenecks - max path distance is 29!
If you prefere an additional boolean function, it may be a good idea to "unroll"
the loop, eg. doing four fill iterations a row without any of these expensive
"is equal" or "is not equal" statements. So you can simultaniously fill from sq1
and sq2 with independend mmx-registers. That gains a lot in average.
cheers,
Gerd
//===========================================================
// int getPathDistanceMMX - mmx flood fill algorithm
// ATHLON version because of pswapd
// path - a set of squares that directs the flood fill
// from - the square the flood fill starts
// !should be member of path,
// or for tempo reasons one adjacent!
// to - the target of the flood fill
// !should be member of path,
// otherwise we never reach it!
// return - 0 (FALSE) if no from,to connection exists
// > 0 the shortest distance(from,to) along the path
//===========================================================
#pragma warning(disable:4035) // no return value (eax)
int getPathDistanceMMX (BitBoard path, int from, int to)
{
static BitBoard notH = 0x7f7f7f7f7f7f7f7f;
static BitBoard notA = 0xfefefefefefefefe;
__asm
{
movd mm0, [path]
punpckldq mm0, [path+4]
mov eax, [from]
mov edx, [to]
movq mm1, [scBBOfBit+8*eax] ; sq1 := initial from-bitboard
movq mm2, [scBBOfBit+8*edx] ; sq2 := initial to-bitboard
xor eax, eax ; distance := 0
movq mm6, [notH] ; makes loop 4 bytes shorter
movq mm7, [notA] ; makes loop 4 bytes shorter, 92(100) in total
floodfill:
// flood fill in left and right direction
movq mm3, mm1 ; := sq1
movq mm4, mm1 ; := sq1
psrlq mm3, 1 ; sq1>>1 shift board left in h->a direction
movq mm5, mm1 ; store sq1 to measure progress later
psllq mm4, 1 ; sq1<<1 shift board right in a->h direction
pand mm3, mm6 ; clear h-file due to wrapped bits from a file
pand mm4, mm7 ; clear a-file due to wrapped bits from h file
por mm1, mm3 ; sq1 |= sq1>>1
por mm1, mm4 ; sq1 |= sq1<<1
// flood fill in up and down direction
movq mm3, mm1 ; := sq1
movq mm4, mm1 ; := sq1
psrlq mm3, 8 ; sq1>>8 shift down in 8->1 direction
psllq mm4, 8 ; sq1<<8 shift up in 1->8 direction
por mm1, mm3 ; sq1 |= sq1>>8
por mm1, mm4 ; sq1 |= sq1<<8
pand mm1, mm0 ; sq1 & path -> drop flood not in path
// if there is a intersection between sq1-flood and sq2,
// shortes connection is found
// if the flood make no progress, there is no connection
// both conditions are processed quite simultaniously
movq mm4, mm2 ; intersec := sq2 ...
pxor mm5, mm1 ; progress := previous sq1 ^ sq1
pand mm4, mm1 ; intersec := sq1 & sq2
inc eax ; distance := distance + 1
pswapd mm3, mm4 ; high(intersec)
por mm3, mm4 ; high(intersec) | low(intersec)
pswapd mm4, mm5 ; high(progress)
movd edx, mm3 ; packed(intersec)
test edx, edx ; intersection ?
por mm4, mm5 ; high(progress) | low(progress)
movd edx, mm4 ; packed(progress)
jnz connected ; intersection ==> connected
test edx, edx ; no progress ?
jz disconnected; yes, disconnected
jmp floodfill ; otherwise do next flood fill iteration
disconnected:
xor eax, eax ; return 0
connected:
femms
}
}
#pragma warning(default:4035)
...
const BitBoard scBBOfBit[64] = {
0x0000000000000001, 0x0000000000000002, .....
};
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.