Bit duplication

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
maachal
Posts: 32
Joined: Jul 21, 2017 21:11
Location: czech

Bit duplication

Postby maachal » Feb 16, 2019 23:59

Duplicate bits 0->00, 1->11.
Example: 1001 0001 -> 11000011 00000011

Code: Select all

'similarly rr and test carry
cls
dim as ubyte i
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
print "in: " & i & " - " & bin(i, 8)
do
  'print i & " - " & i mod 2 & " - " & i \ 2 'small debug
  o = o + ((i mod 2) * 2 ^ c)
  c = c + 1
  o = o + ((i mod 2) * 2 ^ c)
  c = c + 1
  i = i \ 2
loop until i = 0
print "out: " & o & " - " & bin(o, 16)
sleep
Can you write it faster / more elegantly, in FreeBASIC? Without ASM...
badidea
Posts: 1368
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Bit duplication

Postby badidea » Feb 17, 2019 0:13

Without "^", "mod", "\" :

Code: Select all

'similarly rr and test carry
cls
dim as ubyte i
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
print "in: " & i & " - " & bin(i, 8)
do
   o += ((i and 1) * (1 shl c))
   c += 1
   o += ((i and 1) * (1 shl c))
   c += 1
   i shr= 1
loop until i = 0
print "out: " & o & " - " & bin(o, 16)
sleep

Have a look at Bit and Bitset for a more elegant version.
https://freebasic.net/wiki/wikka.php?wakka=KeyPgBit and https://freebasic.net/wiki/wikka.php?wakka=KeyPgBitset

Update, better:

Code: Select all

cls
dim as ubyte i
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
print "in: " & i & " - " & bin(i, 8)
dim as integer bitNum = 0
do
   c = i and 1 'least significant bit of i
   o or= (c shl bitNum) 'set bit at bitnum
   bitNum += 1
   o or= (c shl bitNum) 'set bit at bitnum
   bitNum += 1
   i shr= 1
loop until i = 0
print "out: " & o & " - " & bin(o, 16)
sleep

Or:

Code: Select all

cls
dim as ubyte i
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
print "in: " & i & " - " & bin(i, 8)
dim as integer bitNum = 0
do
   c = i and 1 'least significant bit of i
   c = (c shl 1) or c 'duplicate lsb
   o or= (c shl bitNum) 'set bit at bitnum
   bitNum += 2
   i shr= 1
loop until i = 0
print "out: " & o & " - " & bin(o, 16)
sleep

This is all still freebasic syntax, but it looks suspiciously like asm :-)
jj2007
Posts: 1161
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Bit duplication

Postby jj2007 » Feb 17, 2019 1:10

maachal wrote:Duplicate bits 0->00, 1->11.
Example: 1001 0001 -> 11000011 00000011

What's wrong with assembly? You want it fast, right?

Code: Select all

function duplicate naked cdecl (byval inbyte as long) as integer
  asm
  .align 4
  mov edx, [esp+4]
  xor eax, eax
  mov ecx, -1073741824
L0:
  rol ecx, 2
  shr edx, 1
  je L1
  jnc L0
  or eax, ecx
  jmp L0
L1:
  jnc Lx2
  or eax, ecx
Lx2:
  ret
  end asm
end function

cls
dim as ubyte i, i0
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
i0=i   ' keep a copy
print "in: " & i & " - " & bin(i, 8)
dim as integer bitNum = 0
Dim as double t=timer
#define loops 100000000
print "testing ";loops;" iterations"

' ************* badidea A *************
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 1
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea A"; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* badidea B *************
t=timer
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 0
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea B"; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* jj2007 *************
t=timer
For n as integer=1 to loops
   o=duplicate(i0)
Next
print using "##.### seconds, assembly"; timer-t;
print ",  out: " & o & " - " & bin(o, 16)

sleep

Output:

Code: Select all

Number 0-255: 255
in: 255 - 11111111
testing  100000000 iterations
 1.626 seconds, badidea A, out: 65535 - 1111111111111111
 2.096 seconds, badidea B, out: 65535 - 1111111111111111
 1.005 seconds, assembly,  out: 65535 - 1111111111111111
 
Number 0-255: 170
in: 170 - 10101010
testing  100000000 iterations
 1.611 seconds, badidea A, out: 52428 - 1100110011001100
 2.097 seconds, badidea B, out: 52428 - 1100110011001100
 1.052 seconds, assembly,  out: 52428 - 1100110011001100
Last edited by jj2007 on Feb 17, 2019 3:16, edited 2 times in total.
dodicat
Posts: 5772
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Bit duplication

Postby dodicat » Feb 17, 2019 2:04

You should reset t for Badidea B

' ************* badidea B *************
t=timer

bla
bla
jj2007
Posts: 1161
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Bit duplication

Postby jj2007 » Feb 17, 2019 3:13

dodicat wrote:You should reset t for Badidea B
Done, thanks.
maachal
Posts: 32
Joined: Jul 21, 2017 21:11
Location: czech

Re: Bit duplication

Postby maachal » Feb 17, 2019 18:18

badidea wrote:This is all still freebasic syntax, but it looks suspiciously like asm :-)
Yes. :-) Nice piece of code, thank you.
jj2007 wrote:What's wrong with assembly? You want it fast, right?
Yes, fast. Nice piece of code, thank you. ;-)
But if the other people in the group are working on the code who do not understand the assembler, it's a problem.
Very good work, thank you.
coderJeff
Site Admin
Posts: 2882
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Bit duplication

Postby coderJeff » Feb 17, 2019 23:02

Don't know if you would call it elegant, due the bit fiddling... and assuming input is only 8 bits at most.

Code: Select all

function dup8bits( byval x as ulong ) as ulong
   '' spread the bits out
   dim r as ulong = x   and &h00ff
   r = (r or (r shl 4)) and &h0f0f
   r = (r or (r shl 2)) and &h3333
   r = (r or (r shl 1)) and &h5555
   '' duplicate the bits ( r or (r shl 1))
   return r * 3
end function


Assembly version, it's pretty fast. Though, I don't do much ASM programming, but seems to work OK for 32 & 64 bit:

Code: Select all

function dup8bits naked cdecl ( byval x as ulong ) as ulong
   asm
#ifdef __FB_64BIT__
   .align 16
   #ifdef __FB_LINUX__
      mov rax, rdi
   #else
      mov rax, rcx
   #endif
#else
      .align 4
      mov eax, [esp+4]
#endif
      '' r and &h00ff
      and eax, &h00ff
      
      '' r = (r or (r shl 4)) and &h0f0f
      mov edx, eax
      shl edx, 4
      or  eax, edx
      and eax, &h0f0f
      
      '' r = (r or (r shl 2)) and &h3333
      mov edx, eax
      shl edx, 2
      or  eax, edx
      and eax, &h3333
      
      '' r = (r or (r shl 1)) and &h5555
      mov edx, eax
      shl edx, 1
      or  eax, edx
      and eax, &h5555
      
      '' return r * 3
      mov edx, eax
      shl edx, 1
      or eax, edx
      ret
   end asm
end function
maachal
Posts: 32
Joined: Jul 21, 2017 21:11
Location: czech

Re: Bit duplication

Postby maachal » Feb 17, 2019 23:48

@coderJeff
Speed at 100 million iterations:

Code: Select all

X:\fb\doublebits>doublebits-other32.exe
Number 0-255: 170
in: 170 - 10101010
testing  100000000 iterations
 3.825298 seconds, badidea freeBASIC 1, out: 52428 - 1100110011001100
 5.056277 seconds, badidea freeBASIC 2, out: 52428 - 1100110011001100
 1.040516 seconds, jj2007 assembly,  out: 52428 - 1100110011001100
 0.643643 seconds, coderJeff freeBASIC,  out: 52428 - 1100110011001100
 0.334655 seconds, coderJeff assembly,  out: 52428 - 1100110011001100

X:\fb\doublebits>doublebits-other64.exe
Number 0-255: 170
in: 170 - 10101010
testing  100000000 iterations
 1.096447 seconds, badidea freeBASIC 1, out: 52428 - 1100110011001100
 0.962556 seconds, badidea freeBASIC 2, out: 52428 - 1100110011001100
 0.356543 seconds, jj2007 assembly,  out: 0 - 0000000000000000
 0.000005 seconds, coderJeff freeBASIC,  out: 52428 - 1100110011001100
 0.260108 seconds, coderJeff assembly,  out: 52428 - 1100110011001100
Unbelievable and excellent ...
I have to study your code. Thank you very much. ;-)
Last edited by maachal on Feb 17, 2019 23:53, edited 1 time in total.
jj2007
Posts: 1161
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Bit duplication

Postby jj2007 » Feb 17, 2019 23:49

coderJeff wrote:Assembly version, it's pretty fast.
That's an understatement, it's almost three times as fast as mine ;-)

Code: Select all

function dup8bits naked cdecl ( byval x as ulong ) as ulong   'CoderJeff
   asm
#ifdef __FB_64BIT__
   .align 16
   #ifdef __FB_LINUX__
      mov rax, rdi
   #else
      mov rax, rcx
   #endif
#else
      .align 4
      mov eax, [esp+4]
#endif
      '' r and &h00ff
      and eax, &h00ff
     
      '' r = (r or (r shl 4)) and &h0f0f
      mov edx, eax
      shl edx, 4
      or  eax, edx
      and eax, &h0f0f
     
      '' r = (r or (r shl 2)) and &h3333
      mov edx, eax
      shl edx, 2
      or  eax, edx
      and eax, &h3333
     
      '' r = (r or (r shl 1)) and &h5555
      mov edx, eax
      shl edx, 1
      or  eax, edx
      and eax, &h5555
     
      '' return r * 3
      mov edx, eax
      shl edx, 1
      or eax, edx
      ret
   end asm
end function

function duplicate naked cdecl (byval inbyte as long) as integer   ' jj2007
  asm
  .align 4
  mov edx, [esp+4]
  xor eax, eax
  mov ecx, -1073741824
L0:
  rol ecx, 2
  shr edx, 1
  je L1
  jnc L0
  or eax, ecx
  jmp L0
L1:
  jnc Lx2
  or eax, ecx
Lx2:
  ret
  end asm
end function

cls
dim as ubyte i, i0
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
i0=i   ' keep a copy
print "in: " & i & " - " & bin(i, 8)
dim as integer bitNum = 0
Dim as double t=timer
#define loops 100000000
print "testing ";loops;" iterations"

' ************* badidea A *************
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 1
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea A"; timer-t;
print ",  out: " & o & " - " & bin(o, 16)

' ************* badidea B *************
t=timer
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 0
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea B"; timer-t;
print ",  out: " & o & " - " & bin(o, 16)

' ************* jj2007 *************
t=timer
For n as integer=1 to loops
   o=duplicate(i0)
Next
print using "##.### seconds, asm jj2007"; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* CoderJeff *************
t=timer
For n as integer=1 to loops
   o=dup8bits(i0)
Next
print using "##.### seconds, asm CoderJ"; timer-t;
print ", out: " & o & " - " & bin(o, 16)

sleep
maachal
Posts: 32
Joined: Jul 21, 2017 21:11
Location: czech

Re: Bit duplication

Postby maachal » Feb 18, 2019 0:05

X:\fb\doublebits>doublebits-other32.exe
Number 0-255: 170
in: 170 - 10101010
testing 100000000 iterations
3.825298 seconds, badidea freeBASIC 1, out: 52428 - 1100110011001100
5.056277 seconds, badidea freeBASIC 2, out: 52428 - 1100110011001100
1.040516 seconds, jj2007 assembly, out: 52428 - 1100110011001100
0.643643 seconds, coderJeff freeBASIC, out: 52428 - 1100110011001100
0.334655 seconds, coderJeff assembly, out: 52428 - 1100110011001100

X:\fb\doublebits>doublebits-other64.exe
Number 0-255: 170
in: 170 - 10101010
testing 100000000 iterations
1.096447 seconds, badidea freeBASIC 1, out: 52428 - 1100110011001100
0.962556 seconds, badidea freeBASIC 2, out: 52428 - 1100110011001100
0.356543 seconds, jj2007 assembly, out: 0 - 0000000000000000
0.000005 seconds, coderJeff freeBASIC, out: 52428 - 1100110011001100
0.260108 seconds, coderJeff assembly, out: 52428 - 1100110011001100

What? 64bit exe. Measured several times. Hell was frozen? :-D
coderJeff
Site Admin
Posts: 2882
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Bit duplication

Postby coderJeff » Feb 18, 2019 1:01

Yeah, don't trust that timing because gcc is optimizing the loop away. Even though the program says to loop 100000000 times, only the last result is actually used, and the procedure called has no side effects (and it's not asm), so gcc determines that it only really needs to call the procedure once. And it probably doesn't even do that, just takes the guts out of the procedure and uses that directly.

To force a reasonable timing test, the code to be tested can be placed in one module that's optimized, and call it from another module that's doing the timing loop. You just have to compile the modules separately, being sure to specify a low optimization level like '-O 1' or '-O 0' for the main module calling the other.

Something like:
fbc.exe -O 3 -c somefunc.bas
fbc.exe -O 0 main.bas somefunc.o
jj2007
Posts: 1161
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Bit duplication

Postby jj2007 » Feb 18, 2019 8:59

coderJeff wrote:specify a low optimization level
That distorts the result in favour of the "naked" assembly routines. What often works instead is to fake an interest in the results generated in the loop by adding them up and displaying the sum after the loop has finished.
dodicat
Posts: 5772
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Bit duplication

Postby dodicat » Feb 18, 2019 18:53

Here is a string variety.

Please use 32 bits (jj2007's assembler included)

Code: Select all

function duplicate naked cdecl (byval inbyte as long) as integer
  asm
  .align 4
  mov edx, [esp+4]
  xor eax, eax
  mov ecx, -1073741824
L0:
  rol ecx, 2
  shr edx, 1
  je L1
  jnc L0
  or eax, ecx
  jmp L0
L1:
  jnc Lx2
  or eax, ecx
Lx2:
  ret
  end asm
end function

Function doublebitter(Byval n As Long) As longint
 Var b=Bin(n),position=0
 position=Instr(b,"1")
 While position>0
 b=Mid(b,1,position-1) & "11" & Mid(b,position+Len("1"))
 position=Instr(position+Len("11"),b,"1")
 Wend
 position=Instr(b,"0")
 While position>0
 b=Mid(b,1,position-1) & "00" & Mid(b,position+Len("0"))
 position=Instr(position+Len("00"),b,"0")
 Wend
 Return culngint("&b" + b)
End Function


sub create(a() as longint,n as long=255)
 redim a(n)
 for i as long=0 to n
 a(i)=doublebitter(i)
 next
end sub

redim as longint dbitters()

function dup8bits naked cdecl ( byval x as ulong ) as ulong
   asm
#ifdef __FB_64BIT__
   .align 16
   #ifdef __FB_LINUX__
      mov rax, rdi
   #else
      mov rax, rcx
   #endif
#else
      .align 4
      mov eax, [esp+4]
#endif
      '' r and &h00ff
      and eax, &h00ff
     
      '' r = (r or (r shl 4)) and &h0f0f
      mov edx, eax
      shl edx, 4
      or  eax, edx
      and eax, &h0f0f
     
      '' r = (r or (r shl 2)) and &h3333
      mov edx, eax
      shl edx, 2
      or  eax, edx
      and eax, &h3333
     
      '' r = (r or (r shl 1)) and &h5555
      mov edx, eax
      shl edx, 1
      or  eax, edx
      and eax, &h5555
     
      '' return r * 3
      mov edx, eax
      shl edx, 1
      or eax, edx
      ret
   end asm
end function
cls
dim as ubyte i, i0
dim as ushort o = 0, c = 0
input "Number 0-255: ", i
i0=i   ' keep a copy
print "in: " & i & " - " & bin(i, 8)
dim as integer bitNum = 0
Dim as double t=timer
#define loops 100000000
print "testing ";loops;" iterations"

' ************* badidea A *************
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 1
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea A     "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* badidea B *************
t=timer
For n as integer=1 to loops
   i=i0
   o=0
   bitNum = 0
   #if 0
      do
         c = i and 1 'least significant bit of i
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 1
         i shr= 1
      loop until i = 0
   #else
      do
         c = i and 1 'least significant bit of i
         c = (c shl 1) or c 'duplicate lsb
         o or= (c shl bitNum) 'set bit at bitnum
         bitNum += 2
         i shr= 1
      loop until i = 0
   #endif
Next
print using "##.### seconds, badidea B     "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

' ************* jj2007 *************
t=timer
For n as integer=1 to loops
   o=duplicate(i0)
Next
print using "##.### seconds, assembly      "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

'dodicat
t=timer
create(dbitters(),i0)
For n as integer=1 to loops
   o=dbitters(i0)
Next
print using "##.### seconds, lookup        "; timer-t;
print ", out: " & o & " - " & bin(o, 16)
'coder jeff
t=timer
For n as integer=1 to loops
   o= dup8bits(i0)
Next
print using "##.### seconds, coder jeff    "; timer-t;
print ", out: " & o & " - " & bin(o, 16)

sleep
   
jj2007
Posts: 1161
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Bit duplication

Postby jj2007 » Feb 18, 2019 21:46

dodicat wrote:Here is a string variety.
What do you mean with "string variety"? The lookup code? It's blazingly fast, nice idea...
Lost Zergling
Posts: 213
Joined: Dec 02, 2011 22:51
Location: France

Re: Bit duplication

Postby Lost Zergling » Feb 19, 2019 12:35

I am completely ignorant of assembler programming. I'm not sure, but I think maybe, there's a way to speed up LZLE by incorporating assembler functions. The most usual and critical functions in terms of speed are HashStep and HashTag (iteration and mapping). This would make FB an even more credible and relevant alternative to other languages. If one day I will stop my activity on the forum, or even before, I would be honored and happy that CoderJeff or Dodicat can improve the speed of the tool thanks to an asm function.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: Google [Bot] and 3 guests