AArch64. Fast method to compact bits

[LemonParty]

There is a register x0 with bits
%AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHH...
needed to extract every fourth bit so number become
%ABCDEFGH...
In total 64 bit value should become a 16 bit value
How to do this in ARM64? Is there any fast method to do this? For example x86 has this https://www.felixcloutier.com/x86/pext.

[jamie]

Code: Pascal  [Select][+][-]

1. unit Unit1;
2.  
3. {$mode objfpc}{$H+}
4.  
5. interface
6.  
7. uses
8.   Classes, SysUtils, Forms, Controls, Graphics, Dialogs, StdCtrls;
9.  
10. type
11.  
12.   { TForm1 }
13.  
14.   TForm1 = class(TForm)
15.     Button1: TButton;
16.     procedure Button1Click(Sender: TObject);
17.   private
18.  
19.   public
20.  
21.   end;
22. var
23.   Form1: TForm1;
24.  
25. implementation
26.  
27. {$R *.lfm}
28. Function T64to16bit(aValue:Uint64):Word;Inline;
29. Var
30.   I:Integer;
31. Begin
32.   For I := 1 to 16 do
33.    Begin
34.     Result := Result shr 1;
35.     aValue := AValue shr 3;
36.     IF (Avalue and 1)=1 THen Result := Result or $8000;
37.    end;
38. End;
39.  
40. { TForm1 }
41.  
42. procedure TForm1.Button1Click(Sender: TObject);
43. begin
44.   Caption := T64To16Bit(UInt64($ffffffffffffff00)).ToBinString;
45. end;
46.  
47. end.
48.  
49.  
50.  

Have no idea about arc...
but maybe you can examine the code generation, it looks good here at op-4

[LemonParty]

Thank you jamie.

I found even better solution. I select 2 bits from input value and then shift those two bits per step. In total 8 steps for 64 bit value.

Code: Pascal  [Select][+][-]

1. {$mode ObjFPC}{$H+}
2.  
3. function Extract(Q: QWord): Word;assembler;nostackframe;
4. asm
5.   mov x1,#0x1818181818181818 //selecting two bits from every byte pair
6.   and x0,x0,x1
7.  
8.   lsr x0,x0,#3 //step 1 first 2 bits
9.   and x2,x0,#3
10.  
11.   lsr x1,x0,#6
12.   and x1,x1,#0xC
13.   orr x2,x2,x1 //step 2
14.  
15.   lsr x1,x0,#12
16.   and x1,x1,#0x30
17.   orr x2,x2,x1 //step 3
18.  
19.   lsr x1,x0,#18
20.   and x1,x1,#0xC0
21.   orr x2,x2,x1 //step 4
22.  
23.   lsr x1,x0,#24
24.   and x1,x1,#0x300
25.   orr x2,x2,x1 //step 5
26.  
27.   lsr x1,x0,#30
28.   and x1,x1,#0xC00
29.   orr x2,x2,x1 //step 6
30.  
31.   lsr x1,x0,#36
32.   and x1,x1,#0x3000
33.   orr x2,x2,x1 //step 7
34.  
35.   lsr x1,x0,#42
36.   and x1,x1,#0xC000
37.   orr x2,x2,x1 //step 8
38.  
39.   mov x0,x2
40. end;
41.  
42. begin
43.   Writeln(
44.     BinStr(Extract($F0F0F0F0F0F0F0F0), 16)
45.   );
46. end.

[LemonParty]

The first two instructions are not needed.

Code: Pascal  [Select][+][-]

1. {$mode ObjFPC}{$H+}
2.  
3. function Extract(Q: QWord): Word;assembler;nostackframe;
4. asm
5.   lsr x0,x0,#3 //step 1 first 2 bits
6.   and x2,x0,#3
7.  
8.   lsr x1,x0,#6
9.   and x1,x1,#0xC
10.   orr x2,x2,x1 //step 2
11.  
12.   lsr x1,x0,#12
13.   and x1,x1,#0x30
14.   orr x2,x2,x1 //step 3
15.  
16.   lsr x1,x0,#18
17.   and x1,x1,#0xC0
18.   orr x2,x2,x1 //step 4
19.  
20.   lsr x1,x0,#24
21.   and x1,x1,#0x300
22.   orr x2,x2,x1 //step 5
23.  
24.   lsr x1,x0,#30
25.   and x1,x1,#0xC00
26.   orr x2,x2,x1 //step 6
27.  
28.   lsr x1,x0,#36
29.   and x1,x1,#0x3000
30.   orr x2,x2,x1 //step 7
31.  
32.   lsr x1,x0,#42
33.   and x1,x1,#0xC000
34.   orr x2,x2,x1 //step 8
35.  
36.   mov x0,x2
37. end;
38.  
39. begin
40.   Writeln(
41.     BinStr(Extract($F0F0F0F0F0F0F0F0), 16)
42.   );
43. end.

[Martin_fr]

You should be able to merge in groups

Not tested / just the concept

Code: Text  [Select][+][-]

1.   lsr x0,x0,#3  // remove lowest 3
2.   // the lower 32 (same will happen for the upper 32
3.   // ....A AAAB BBBC CCCD DDDE EEEF FFFG GGGH
4.   mov x2,#0x0003000300030003  // select 1,2, 5,6, ...
5.   and x1,x0,x2
6.   //  .... __CD ____ ____ __GH
7.  
8.   mov x2,#0x0300030003000300 // select 3,4, 7,8, ....  // you can shift X2 if that is faster???
9.   and x0,x0,x2
10.   //  ..AB ____ ____ __EF ____ ____
11.   lsr x0,x0,#6
12.  
13.   orr x0,x0, x1
14.   //  .... __CD ____ ____ __GH
15.   //  .... AB ____ ____ __EF __
16.   // will OR to
17.   // ....  ABCD ___ ____ EFGH
18.  
19.  
20.   // repeat
21.   mov x2,#0x0000000F0000000F
22.   and x1,x0,x2
23.  
24.   mov x2,#0x000F0000000F0000
25.   and x1,x1,x2
26.   lsr x1,x1,
27.  
28.   lsr x1,x1,12
29.   orr x0,x0, x1
30.  
31.   // repeat once more
32.  
33.  

[MathMan]

@Martin_fr

Does ARM64 have an equivalent of x86_64's clmul? If so, it should be possible to bring this down to a simple 'mul' ...

[LemonParty]

Yes, Martin_fr, it is a great idea. Here is a realization:

Code: Pascal  [Select][+][-]

1. function Extract2(Q: QWord): Word;assembler;nostackframe;
2. asm
3.   mov x1,#0x1818181818181818
4.   and x0,x0,x1
5.  
6.   lsr x0,x0,#3
7.  
8.   lsr x1,x0,#6
9.   orr x0,x0,x1//after this we have 4 bits
10.  
11.   lsr x1,x0,#12
12.   orr x0,x0,x1//after this we have 8 bits
13.  
14.   lsr x1,x0,#24
15.   orr x0,x0,x1//after this we have 16 bits
16. end;

Only 9 instructions, which is really good.

[Thaddy]

With some help by codex, asked for review:

Code: Pascal  [Select][+][-]

1. function Extract2(Q: QWord): Word; assembler; nostackframe;
2. asm
3.   and x0, x0, #$1818181818181818
4.   lsr x0, x0, #3
5.   orr x0, x0, x0, lsr #6
6.   orr x0, x0, x0, lsr #12
7.   orr x0, x0, x0, lsr #24
8.   //and x0, x0, #$ffff  // if only word as result, you can drop this too
9. end;

Tested RaspBerry Pi 4.
Reference function:

Code: Pascal  [Select][+][-]

1. function Extract2Ref(Q: QWord): Word;
2. var
3.   i: Integer;
4. begin
5.   Result := 0;
6.   for i := 0 to 7 do
7.     Result := Result or Word(((Q shr (i * 8 + 3)) and 3) shl (i * 2));
8. end;

Both output with reply#3 program code:

Code: Bash  [Select][+][-]

1. 1010101010101010

Transforms to $AAAA from $F0F0F0F0F0F0F0F0 in 5 operations.

[LemonParty]

Thank you, Thaddy. I forgot that orr can do shifts too. 5 instuctions are absolutely suitable for hot loops.

[Thaddy]

Deekseek says no improvement possible for word output  Beat A.I....
I just had to drop my and mask. Which Codex provided and I forgot....
Note for any other output than word you will need additional masks in between the orr's.

You are not the only one to forget things, mind you, the reference implementation I wrote is also already fast when inlined, but you gain over a 4X speed. People on other platforms than AARCH64 based can safely use it, and examine the assembler output for improvement.

Quite a nice subject. I really liked it.