How to "reverse" a byte?

New to FreeBASIC? Post your questions here.
MrSwiss
Posts: 3634
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: How to "reverse" a byte?

Postby MrSwiss » Jan 20, 2017 16:17

@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
Posts: 755
Joined: May 05, 2015 5:35
Location: Germany

Re: How to "reverse" a byte?

Postby grindstone » Jan 20, 2017 18:09

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
Posts: 649
Joined: Jun 09, 2005 0:08

Re: How to "reverse" a byte?

Postby Stonemonkey » Jan 20, 2017 21:06

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
Posts: 649
Joined: Jun 09, 2005 0:08

Re: How to "reverse" a byte?

Postby Stonemonkey » Jan 20, 2017 21:27

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
Posts: 649
Joined: Jun 09, 2005 0:08

Re: How to "reverse" a byte?

Postby Stonemonkey » Jan 21, 2017 0:55

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
Posts: 3634
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: How to "reverse" a byte?

Postby MrSwiss » Jan 21, 2017 2:07

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
Posts: 649
Joined: Jun 09, 2005 0:08

Re: How to "reverse" a byte?

Postby Stonemonkey » Jan 21, 2017 8:31

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
Posts: 8189
Joined: May 28, 2005 3:28
Contact:

Re: How to "reverse" a byte?

Postby D.J.Peters » Jan 21, 2017 11:39

how i reverse numbers, strings and operators :lol:
b = mirroring(d)
"[" = mirroring("]")
\ = mirroring(/)
Stonemonkey
Posts: 649
Joined: Jun 09, 2005 0:08

Re: How to "reverse" a byte?

Postby Stonemonkey » Jan 21, 2017 12:20

D.J.Peters wrote: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
Posts: 303
Joined: Mar 15, 2015 12:41

Re: How to "reverse" a byte?

Postby Luis Babboni » Jan 21, 2017 13:59

grindstone wrote: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
Site Admin
Posts: 6229
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: How to "reverse" a byte?

Postby counting_pine » Jan 21, 2017 17:36

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
Posts: 303
Joined: Mar 15, 2015 12:41

Re: How to "reverse" a byte?

Postby Luis Babboni » Jan 23, 2017 1:16

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
Posts: 649
Joined: Jun 09, 2005 0:08

Re: How to "reverse" a byte?

Postby Stonemonkey » Jan 23, 2017 1:34

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
Posts: 755
Joined: May 05, 2015 5:35
Location: Germany

Re: How to "reverse" a byte?

Postby grindstone » Jan 23, 2017 10:32

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
Posts: 649
Joined: Jun 09, 2005 0:08

Re: How to "reverse" a byte?

Postby Stonemonkey » Jan 23, 2017 12:53

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

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 8 guests