How to "reverse" a byte?

[MrSwiss]

@I3I2UI/I0,

yep, you're right, the check __FB_64BIT__ is valid.
Thanks for the validity explanation about the REG e** stuff.
I've must have read some nonsense, about that, somewhere on the INET.
I'm also quite a bit "rusted in", on Assembly coding however, I still remember what the
Author of my *self education* Book on Assembly wrote: "I'm NOT teaching you, just to
code Assembly, I'm going to teach you, how to code FAST Assembly!" (a german guy)

Your code optimized for speed:

Code: Select all

#Macro mirror64(Variable)
If SizeOf(Variable) = 8 Then
  #Ifdef __FB_64BIT__
    Asm
        mov rax, qword Ptr[Variable]
        Xor rbx, rbx ' faster than: mov rbx, 0
        mov rcx, 64
      1:
        rcr rax
        rcl rbx
        dec rcx
        jnz 1b
        mov qword Ptr[Variable], rbx
    End Asm
  #Else
    Asm
        mov eax, dword Ptr[Variable]
        Xor ebx, ebx ' mov ebx, 0
        mov ecx, 32
        mov edx, ecx ' save it to unused reg (for next run)
      1:
        rcr eax
        rcl ebx
        dec ecx
        jnz 1b
        mov eax, dword Ptr[Variable + 4]
        mov dword Ptr[Variable + 4], ebx
        Xor ebx, ebx ' mov ebx, 0
        mov ecx, edx ' restore '32'
      2:             ' <--- diff. label
        rcr eax
        rcl ebx
        dec ecx
        jnz 2b
        mov dword Ptr[Variable], ebx
    End Asm
  #EndIf
EndIf
#EndMacro

Dim As ULongInt zahl = &h2233445566778899
Print Bin(zahl, 64), Hex(zahl, 16)
mirror64(zahl)
Print Bin(zahl, 64), Hex(zahl, 16)
mirror64(zahl)
Print Bin(zahl, 64), Hex(zahl, 16)

Sleep

[grindstone]

Now that the chessprogramming - wiki is accessible again let me make an attempt to transcode the posted function to FB:

Code: Select all

Type smsk
	bitMask As ULongInt
	diagonalMaskEx As ULongInt
	antidiagMaskEx As ULongInt
	fileMaskEx As ULongInt
End Type

Dim Shared As String byteswap
Dim Shared As smsk mask(64)
Dim Shared As ULongInt singleBitboard(64)

byteswap = String(256,Chr(0)) 'allocate the memory and fill with "0"s

'initialize the table
For x As Integer = 0 To 255
	For y As Integer = 0 To 7
		If Bit(x,y) Then
			byteswap[x] = BitSet(byteswap[x],7 - y)
		EndIf
	Next
Next

Function diagonalAttacks(occ As ULongInt, sqOfSlider As ULong) As ULongInt
	Dim As ULongInt forward, reverse, slider, lineMask

	lineMask = mask(sqOfSlider).diagonalMaskEx ' excludes square of slider
	slider   = singleBitboard(sqOfSlider) ' single bit 1 << sq, 2^sq

	forward  = occ And lineMask 'also performs the first subtraction by clearing the s in o
	reverse  = byteswap[forward] ' o'-s'
	forward -= slider ' o -2s
	reverse -= byteswap[slider] ' o'-2s'
	forward Xor= byteswap[reverse]

	Return forward And lineMask 'mask the line again
End Function

[Stonemonkey]

Another way to reverse bits in a byte in FB, I dont know if there's ways to optimise it more or not.

Code: Select all

#macro reverse_byte(b)
    if (b and 1)<>((b shr 7)and 1) then b xor=129
    if (b and 2)<>((b shr 5)and 2) then b xor=66
    if (b and 4)<>((b shr 3)and 4) then b xor=36
    if (b and 8)<>((b shr 1)and 8) then b xor=24
#endmacro

[Stonemonkey]

Or there's this mess

Code: Select all

#macro reverse_byte(b)
    b xor=(((b and 1)<>((b shr 7)and 1))*-129)or _
    (((b and 2)<>((b shr 5)and 2))*-66)or _
    (((b and 4)<>((b shr 3)and 4))*-36)or _
    (((b and 8)<>((b shr 1)and 8))*-24)
#endmacro

or

Code: Select all

#macro reverse_byte(b)
    b xor=((((b shr 7)xor b)and 1)*129)or((((b shr 6)xor(b shr 1))and 1)*66)or((((b shr 5)xor(b shr 2))and 1)*36)or((((b shr 4)xor(b shr 3))and 1)*24)
#endmacro

EDIT: tested and first version in previous post with If's is faster, but a look up table is faster

Code: Select all

dim shared as ubyte reverse_byte(0 to 255)
sub build_reverse_table()
    for i as integer=0 to 255
        dim as ubyte b=i
        if (b and 1)<>((b shr 7)and 1) then b xor=129
        if (b and 2)<>((b shr 5)and 2) then b xor=66
        if (b and 4)<>((b shr 3)and 4) then b xor=36
        if (b and 8)<>((b shr 1)and 8) then b xor=24
        reverse_byte(i)=b
    next
end sub
build_reverse_table


sub test()
    for i as integer=0 to 20
        dim as ubyte b=rnd*255
        dim as ubyte rb=reverse_byte(b)
        print bin$(b,8);"  ";bin$(rb,8)
    next
end sub

test
sleep
end

[Stonemonkey]

Another method:

Code: Select all

#macro reverse_byte(b)
    b=((b and &haa)shr 1)or((b and &h55)shl 1)
    b=((b and &hcc)shr 2)or((b and &h33)shl 2)
    b=((b and &hf0)shr 4)or((b and &h0f)shl 4)
#endmacro

[MrSwiss]

OK, just in case the chess stuff requires Byte SWAPPING of a x64 INT (U/LongInt).
Here is a MACRO using inline ASM to do that:

Code: Select all

#Macro swap64(LI)
If SizeOf(LI) = 8 Then
  #Ifdef __FB_64BIT__
    Asm
        mov     rax, qword Ptr[LI]
        bswap   rax
        mov     qword Ptr[LI], rax
    End Asm
  #Else
    Asm
        mov     eax, dword Ptr[LI]
        mov     ebx, dword Ptr[LI + 4]
        bswap   eax
        bswap   ebx
        mov     dword Ptr[LI + 4], eax
        mov     dword Ptr[LI], ebx
    End Asm
  #EndIf
EndIf
#EndMacro

Dim As LongInt  a = &hFFEEDDCCBBAA9988
Dim As ULongInt b = a

Print "INT64:  "; Hex(a, 16), Str(a)
Print "UINT64: "; Hex(b, 16), Str(b)
Print
swap64(a) : swap64(b)
Print "swap64() here, for a and b"
Print
Print "INT64:  "; Hex(a, 16), Str(a)
Print "UINT64: "; Hex(b, 16), Str(b)
Print

Sleep

The MACRO works like a Sub with a ByRef parameter (see testing code).

[Stonemonkey]

That last one I posted could be written in assembly like this with a bit of messing around with the rotates and masks:

Code: Select all

#macro reverse_byte(b)
     asm
        mov al,[b]
        mov ah,al
        and ax,&haa55
        ror ah,2
        or al,ah
        mov ah,al
        and ax,&h9966
        rol al,3
        ror ah,1
        or al,ah
        mov [b],al
    end asm
#endmacro

[D.J.Peters]

how i reverse numbers, strings and operators :lol:
b = mirroring(d)
"[" = mirroring("]")
\ = mirroring(/)

[Stonemonkey]

how i reverse numbers, strings and operators :lol:
b = mirroring(d)
"[" = mirroring("]")
\ = mirroring(/)

Small things matter, or should. I think I drive my boss nuts.

[Luis Babboni]

Now that the chessprogramming - wiki is accessible again let me make an attempt to transcode the posted function to FB:

Code: Select all

Type smsk
	bitMask As ULongInt
	diagonalMaskEx As ULongInt
	antidiagMaskEx As ULongInt
	fileMaskEx As ULongInt
End Type

Dim Shared As String byteswap
Dim Shared As smsk mask(64)
Dim Shared As ULongInt singleBitboard(64)

byteswap = String(256,Chr(0)) 'allocate the memory and fill with "0"s

'initialize the table
For x As Integer = 0 To 255
	For y As Integer = 0 To 7
		If Bit(x,y) Then
			byteswap[x] = BitSet(byteswap[x],7 - y)
		EndIf
	Next
Next

Function diagonalAttacks(occ As ULongInt, sqOfSlider As ULong) As ULongInt
	Dim As ULongInt forward, reverse, slider, lineMask

	lineMask = mask(sqOfSlider).diagonalMaskEx ' excludes square of slider
	slider   = singleBitboard(sqOfSlider) ' single bit 1 << sq, 2^sq

	forward  = occ And lineMask 'also performs the first subtraction by clearing the s in o
	reverse  = byteswap[forward] ' o'-s'
	forward -= slider ' o -2s
	reverse -= byteswap[slider] ' o'-2s'
	forward Xor= byteswap[reverse]

	Return forward And lineMask 'mask the line again
End Function

BIG THANKS!!!! Now I need time to understand it! :-D

[counting_pine]

Here's a one-line approach, using a 256-byte lookup table encoded in a string:

Code: Select all

#define BYTEREV(n) (!"\0\128\64\192\32\160\96\224\16\144\80\208\48\176\112\240\8\136\72\200\40\168\104\232\24\152\88\216\56\184\120\248\4\132\68\196\36\164\100\228\20\148\84\212\52\180\116\244\12\140\76\204\44\172\108\236\28\156\92\220\60\188\124\252\2\130\66\194\34\162\98\226\18\146\82\210\50\178\114\242\10\138\74\202\42\170\106\234\26\154\90\218\58\186\122\250\6\134\70\198\38\166\102\230\22\150\86\214\54\182\118\246\14\142\78\206\46\174\110\238\30\158\94\222\62\190\126\254\1\129\65\193\33\161\97\225\17\145\81\209\49\177\113\241\9\137\73\201\41\169\105\233\25\153\89\217\57\185\121\249\5\133\69\197\37\165\101\229\21\149\85\213\53\181\117\245\13\141\77\205\45\173\109\237\29\157\93\221\61\189\125\253\3\131\67\195\35\163\99\227\19\147\83\211\51\179\115\243\11\139\75\203\43\171\107\235\27\155\91\219\59\187\123\251\7\135\71\199\39\167\103\231\23\151\87\215\55\183\119\247\15\143\79\207\47\175\111\239\31\159\95\223\63\191\127\255")[cubyte(n)]
print BYTEREV(128) '1

And the code I used to generate it:

Code: Select all

function byterev(n as integer) as integer
  dim ret as integer
  for i as integer = 0 to 7
    ret = ret shl 1 or (n and 1)
    n shr= 1
  next i
  return ret
end function

print "#define BYTEREV(n) (!""";

for i as integer = 0 to 255
  print "\" & byterev(i);
next i

print """)[cubyte(n)]"

[Luis Babboni]

A combination of MrSwiss and counting_pine suggestions seems to work!! :-)


Many thanks to all!!

Code: Select all

#define BYTEREV(n) (!"\0\128\64\192\32\160\96\224\16\144\80\208\48\176\112\240\8\136\72\200\40\168\104\232\24\152\88\216\56\184\120\248\4\132\68\196\36\164\100\228\20\148\84\212\52\180\116\244\12\140\76\204\44\172\108\236\28\156\92\220\60\188\124\252\2\130\66\194\34\162\98\226\18\146\82\210\50\178\114\242\10\138\74\202\42\170\106\234\26\154\90\218\58\186\122\250\6\134\70\198\38\166\102\230\22\150\86\214\54\182\118\246\14\142\78\206\46\174\110\238\30\158\94\222\62\190\126\254\1\129\65\193\33\161\97\225\17\145\81\209\49\177\113\241\9\137\73\201\41\169\105\233\25\153\89\217\57\185\121\249\5\133\69\197\37\165\101\229\21\149\85\213\53\181\117\245\13\141\77\205\45\173\109\237\29\157\93\221\61\189\125\253\3\131\67\195\35\163\99\227\19\147\83\211\51\179\115\243\11\139\75\203\43\171\107\235\27\155\91\219\59\187\123\251\7\135\71\199\39\167\103\231\23\151\87\215\55\183\119\247\15\143\79\207\47\175\111\239\31\159\95\223\63\191\127\255")[cubyte(n)]

' x64_Big_Endian_Lil.bas -- 2017-01-18, MrSwiss

Union Lil_End
    As ULongInt ULInt
    Type
        As UByte _0
        As UByte _1
        As UByte _2
        As UByte _3
        As UByte _4
        As UByte _5
        As UByte _6
        As UByte _7
    End Type
End Union

Union Big_End
    As ULongInt ULInt
    Type
        As UByte _7
        As UByte _6
        As UByte _5
        As UByte _4
        As UByte _3
        As UByte _2
        As UByte _1
        As UByte _0
    End Type
End Union

Function LilToBig(ByVal x As ULongInt) As ULongInt
    Dim As Lil_End L_end
    Dim As Big_End ret
    L_End.ULInt = x : ret.ULInt = 0

    ret._0 = BYTEREV(L_End._0) : ret._1 = BYTEREV(L_End._1)
    ret._2 = BYTEREV(L_End._2) : ret._3 = BYTEREV(L_End._3)
    ret._4 = BYTEREV(L_End._4) : ret._5 = BYTEREV(L_End._5)
    ret._6 = BYTEREV(L_End._6) : ret._7 = BYTEREV(L_End._7)

    LilToBig = ret.ULInt
End Function

Function BigToLil(ByVal x As ULongInt) As ULongInt
    Dim As Big_End B_end
    Dim As Lil_End ret
    B_End.ULInt = x : ret.ULInt = 0

    ret._0 = BYTEREV(B_End._0) : ret._1 = BYTEREV(B_End._1)
    ret._2 = BYTEREV(B_End._2) : ret._3 = BYTEREV(B_End._3)
    ret._4 = BYTEREV(B_End._4) : ret._5 = BYTEREV(B_End._5)
    ret._6 = BYTEREV(B_End._6) : ret._7 = BYTEREV(B_End._7)

    BigToLil = ret.ULInt
End Function

' ======================
' testig code
Dim As ULongInt a = &b1011011101111011111011111101111111011111111011111111101111111111, b = LilToBig(a)

Print "original 'a': "; Bin(a, 64)
Print "inverted 'a': "; Bin(LilToBig(a), 64)
Print
Print "original 'b': "; Bin(b, 64)
Print "inverted 'b': "; Bin(BigToLil(b), 64)

Sleep

[Stonemonkey]

asm version for a 64 bit reverse so not portable to x64. Should be quite fast but I dunno how it'll compare to using a table.

Edit: getting around 20ms for reversing 1,000,000 times with this vs around 70ms using the table.

Code: Select all

#macro reverse64bits(dest,srce)
asm
    mov eax,[srce]
    mov ecx,[srce+4]
    mov ebx,eax
    mov edx,ecx
    and eax,&h55555555
    and ecx,&h55555555
    xor ebx,eax
    xor edx,ecx
    ror ebx,2
    ror edx,2
    or eax,ebx
    or ecx,edx
    mov ebx,eax
    mov edx,ecx
    and eax,&h99999999
    and ecx,&h99999999
    xor ebx,eax
    xor edx,ecx
    ror ebx,4
    ror edx,4
    or eax,ebx
    or ecx,edx
    mov ebx,eax
    mov edx,ecx
    and eax,&he1e1e1e1
    and ecx,&he1e1e1e1
    xor ebx,eax
    xor edx,ecx
    ror ebx,8
    ror edx,8
    or eax,ebx
    or ecx,edx
    rol eax,7
    rol ecx,7
    bswap eax
    bswap ecx
    mov [dest+4],eax
    mov [dest],ecx
end asm
#endmacro


' ======================
' testig code
Dim As ULongInt a = &b1011011101111011111011111101111111011111111011111111101111111111

Print "original 'a': "; Bin(a, 64)
reverse64bits(a,a)
Print "inverted 'a': "; Bin(a, 64)

Sleep

[grindstone]

Here an 8 byte "big endian-to-little endian" conversion FB vs. ASM (asm 32bit only):

Code: Select all

Dim As ZString*9 text = "ABCDEFGH"
Dim As Double timerem, t1, t2

Print "    ";text

timerem = Timer
For x As Integer = 1 To 1000001
	Swap text[0], text[7]
	Swap text[1], text[6]
	Swap text[2], text[5]
	Swap text[3], text[4]
Next
t1 = Timer - timerem
Print "FB  ";text, t1

timerem = Timer
For x As Integer = 1 To 1000001
Asm
	mov eax, [text]
	mov ebx, [text + 4]
	bswap eax
	bswap ebx
	mov [text], ebx
	mov [text + 4], eax
End Asm
Next
t2 = Timer - timerem
Print "ASM ";text, t2
Print
Print "relation: ";t2 / t1

Sleep

[Stonemonkey]

At work atm, what sort of timings do you get?