Bit duplication

maachal · Post by **maachal** » Feb 16, 2019 23:59

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

'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 · Post by **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 · Post by **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

dodicat · Post by **dodicat** » Feb 17, 2019 2:04

You should reset t for Badidea B

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

bla
bla

jj2007 · Post by **jj2007** » Feb 17, 2019 3:13

dodicat wrote:You should reset t for Badidea B

Done, thanks.

maachal · Post by **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.

Post by **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 · Post by **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. ;-)

jj2007 · Post by **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 · Post by **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

Post by **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 · Post by **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 · Post by **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 · Post by **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 · Post by **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.

Bit duplication

Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication

Re: Bit duplication