Board index » delphi » Bit counting problem
Erik Turner
Delphi Developer |
Bit counting problem2006-12-09 07:58:55 AM delphi127 I would like to count the differences between two "image thumbnails". These thumbnails are 16 rows x 16 columns x 1 bit. The fastest algorithm that I have been able to come up with is in Pascal. I can not seem to leverage any of the {*word*118} MMX/SSE/whatever instructions to make it run faster. I tried an SSE implementation using 128 bit XOR which worked but extracting the results and adding up the set bits actually took longer than the pascal implementation. So, I thought I would run the problem by the readers of this newsgroup. Any improvements would be most welcome. My pascal implementation follows: // DEFINITIONS // type PImageData16x16x1 = ^TImageData16x16x1; TImageData16x16x1 = Array[0..8-1] of UInt32; const ImageAddrExtent = 4000000; type TImageAddrEntry = packed record case Byte of 1: (ImageData16x16x1: PImageData16x16x1); 2: (ImageData16x16x8: PImageData16x16x8); end; TImageAddrVector = Array[0..ImageAddrExtent] of TImageAddrEntry; var G_ImageAddrVector: TImageAddrVector; // COMPARE // procedure PerformCompare; var Outer: Integer; OuterP: PImageData16x16x1; Inner: Integer; InnerP: PImageData16x16x1; Sum: Integer; CompareVal: Longword; begin while CompareManager.AllocWorkPacket(Outer) do begin OuterP := G_ImageAddrVector[Outer].ImageData16x16x1; for Inner := Outer+1 to ImageCount do begin InnerP := G_ImageAddrVector[Inner].ImageData16x16x1; Sum := 0; CompareVal := OuterP^[0] XOR InnerP^[0]; Inc(Sum, G_BitCountWL[CompareVal AND $FFFF]); Inc(Sum, G_BitCountWL[CompareVal SHR 16]); CompareVal := OuterP^[1] XOR InnerP^[1]; Inc(Sum, G_BitCountWL[CompareVal AND $FFFF]); Inc(Sum, G_BitCountWL[CompareVal SHR 16]); CompareVal := OuterP^[2] XOR InnerP^[2]; Inc(Sum, G_BitCountWL[CompareVal AND $FFFF]); Inc(Sum, G_BitCountWL[CompareVal SHR 16]); CompareVal := OuterP^[3] XOR InnerP^[3]; Inc(Sum, G_BitCountWL[CompareVal AND $FFFF]); Inc(Sum, G_BitCountWL[CompareVal SHR 16]); CompareVal := OuterP^[4] XOR InnerP^[4]; Inc(Sum, G_BitCountWL[CompareVal AND $FFFF]); Inc(Sum, G_BitCountWL[CompareVal SHR 16]); CompareVal := OuterP^[5] XOR InnerP^[5]; Inc(Sum, G_BitCountWL[CompareVal AND $FFFF]); Inc(Sum, G_BitCountWL[CompareVal SHR 16]); CompareVal := OuterP^[6] XOR InnerP^[6]; Inc(Sum, G_BitCountWL[CompareVal AND $FFFF]); Inc(Sum, G_BitCountWL[CompareVal SHR 16]); CompareVal := OuterP^[7] XOR InnerP^[7]; Inc(Sum, G_BitCountWL[CompareVal AND $FFFF]); Inc(Sum, G_BitCountWL[CompareVal SHR 16]); if (Sum>Threshold) then AddResult(Outer, Inner); end; end; end; |