3
\$\begingroup\$

I have the following code:

function TSliverHelper.SlowNorth: TSlice;
var
  i: integer;
begin
  // Add pixels 0,1,2
  // This means expanding every bit into a byte
  // Or rather every byte into an int64;
  for i:= 0 to 7 do begin
    Result.Data8[i]:= TSuperSlice.Lookup012[Self.bytes[i]];
  end;
end;

This uses a straight forward lookup table, but obviously LUT's are slow and clobber the cache. This takes about 2860 millisecs for 100.000.000 items.

The following approach is a bit faster (1797 MS, or 37% faster):

function TSliverHelper.North: TSlice;
const
  SliverToSliceMask: array[0..7] of byte = ($01,$02,$04,$08,$10,$20,$40,$80);
asm
  //RCX = @Self    (a pointer to an Int64)
  //RDX = @Result  (a pointer to an array[0..63] of byte)
  movq xmm0,[rcx]                       //Get the sliver
  mov r9,$8040201008040201
  movq xmm15,r9 //[rip+SliverToSliceMask] //Get the mask
  movlhps xmm15,xmm15                   //extend it
  mov r8,$0101010101010101              //Shuffle mask
  movq xmm14,r8                         //00 00 00 00 00 00 00 00 01 01 01 01 01 01 01 01
  pslldq xmm14,8                        //01 01 01 01 01 01 01 01 00 00 00 00 00 00 00 00
  movdqa xmm1,xmm0                      //make a copy of the sliver
  //bytes 0,1
  pshufb xmm1,xmm14                     //copy the first two bytes across
  pand xmm1,xmm15                       //Mask off the relevant bits
  pcmpeqb xmm1,xmm15                    //Expand a bit into a byte
  movdqu [rdx],xmm1
  //bytes 2,3
  psrldq xmm0,2                         //shift in the next two bytes
  movdqa xmm2,xmm0
  pshufb xmm2,xmm14                     //copy the next two bytes across
  pand xmm2,xmm15                       //Mask off the relevant bits
  pcmpeqb xmm2,xmm15                    //Expand a bit into a byte
  movdqu [rdx+16],xmm2
  //bytes 4,5
  psrldq xmm0,2                         //shift in the next two bytes
  movdqa xmm3,xmm0
  pshufb xmm3,xmm14                     //copy the next two bytes across
  pand xmm3,xmm15                       //Mask off the relevant bits
  pcmpeqb xmm3,xmm15                    //Expand a bit into a byte
  movdqu [rdx+32],xmm3
  //bytes 6,7
  psrldq xmm0,2                         //shift in the next two bytes
  movdqa xmm4,xmm0
  pshufb xmm4,xmm14                     //copy the final two bytes across
  pand xmm4,xmm15                       //Mask off the relevant bits
  pcmpeqb xmm4,xmm15                    //Expand a bit into a byte
  //Store the data
  movdqu [rdx+48],xmm4
end;

However, that is a lot of code. I'm hoping there's a way to do with less processing that's going to work faster. The way the code works (in prose) is simple.
First we clone the input byte 8 times. Next the bit is masked off using the 01,02,04... mask and an AND operation. Finally this randomish bit is expanded into a byte using the compare-equal-to-mask (pcmpeqb).

The opposite operation is a simple PMSKMOVB.

I can use AVX1 code, but not AVX2.

\$\endgroup\$
  • \$\begingroup\$ Don't you have any other options than Pascal (if I'm right)? \$\endgroup\$ – Calak Nov 12 '18 at 9:30
  • \$\begingroup\$ It's in assembly. The Pascal code is just a wrapper, any language will do. \$\endgroup\$ – Johan Nov 12 '18 at 9:37
  • 1
    \$\begingroup\$ Can't try it for now, but I assume you can reach the ASM's performance, shorter, with plain C. \$\endgroup\$ – Calak Nov 12 '18 at 9:55
1
\$\begingroup\$

Use a multiplication to perform several shifts in a single instruction.

  1. Trim the input to seven bits to avoid overlap in the second step.

  2. Shift by 0, 7, 14, 21, 28, 35, 42 bits and aggregate the results in a 64-bit integer.

  3. Keep only bits 0, 8, 16, 24, 32, 40, 48.

  4. Handle the 8th bit of the input separately. Shift by 49, then add it to the others.

Example code in C#

ulong Expand(byte b)
{
    ulong shift = 0x0000040810204081ul; // bits set: 0, 7, 14, 21, 28, 35, 42
    ulong mask = 0x0001010101010101ul; // bits set: 0, 8, 16, 24, 32, 40, 48
    return (ulong)(b & 127) * shift & mask | (ulong)(b & 128) << 49;
}
\$\endgroup\$
  • \$\begingroup\$ Nice trick for byte to qword. \$\endgroup\$ – W. Chang Nov 27 '18 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.