Bit duplication

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

Bit duplication

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

Code: Select all

`'similarly rr and test carryclsdim as ubyte idim as ushort o = 0, c = 0input "Number 0-255: ", iprint "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 \ 2loop until i = 0print "out: " & o & " - " & bin(o, 16)sleep`
Can you write it faster / more elegantly, in FreeBASIC? Without ASM...
Posts: 1368
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Bit duplication

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

Code: Select all

`'similarly rr and test carryclsdim as ubyte idim as ushort o = 0, c = 0input "Number 0-255: ", iprint "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= 1loop until i = 0print "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

`clsdim as ubyte idim as ushort o = 0, c = 0input "Number 0-255: ", iprint "in: " & i & " - " & bin(i, 8)dim as integer bitNum = 0do   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= 1loop until i = 0print "out: " & o & " - " & bin(o, 16)sleep`

Or:

Code: Select all

`clsdim as ubyte idim as ushort o = 0, c = 0input "Number 0-255: ", iprint "in: " & i & " - " & bin(i, 8)dim as integer bitNum = 0do   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= 1loop until i = 0print "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

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, -1073741824L0:  rol ecx, 2  shr edx, 1  je L1  jnc L0  or eax, ecx  jmp L0L1:  jnc Lx2  or eax, ecxLx2:  ret  end asmend functionclsdim as ubyte i, i0dim as ushort o = 0, c = 0input "Number 0-255: ", ii0=i   ' keep a copyprint "in: " & i & " - " & bin(i, 8)dim as integer bitNum = 0Dim as double t=timer#define loops 100000000print "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   #endifNextprint using "##.### seconds, badidea A"; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* badidea B *************t=timerFor 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   #endifNextprint using "##.### seconds, badidea B"; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* jj2007 *************t=timerFor n as integer=1 to loops   o=duplicate(i0)Nextprint using "##.### seconds, assembly"; timer-t;print ",  out: " & o & " - " & bin(o, 16)sleep`

Output:

Code: Select all

`Number 0-255: 255in: 255 - 11111111testing  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: 170in: 170 - 10101010testing  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

You should reset t for Badidea B

t=timer

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

Re: Bit duplication

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

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
Posts: 2882
Joined: Nov 04, 2005 14:23
Contact:

Re: Bit duplication

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 * 3end 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 asmend function`
maachal
Posts: 32
Joined: Jul 21, 2017 21:11
Location: czech

Re: Bit duplication

@coderJeff
Speed at 100 million iterations:

Code: Select all

`X:\fb\doublebits>doublebits-other32.exeNumber 0-255: 170in: 170 - 10101010testing  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 - 1100110011001100X:\fb\doublebits>doublebits-other64.exeNumber 0-255: 170in: 170 - 10101010testing  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

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 asmend functionfunction duplicate naked cdecl (byval inbyte as long) as integer   ' jj2007  asm  .align 4  mov edx, [esp+4]  xor eax, eax  mov ecx, -1073741824L0:  rol ecx, 2  shr edx, 1  je L1  jnc L0  or eax, ecx  jmp L0L1:  jnc Lx2  or eax, ecxLx2:  ret  end asmend functionclsdim as ubyte i, i0dim as ushort o = 0, c = 0input "Number 0-255: ", ii0=i   ' keep a copyprint "in: " & i & " - " & bin(i, 8)dim as integer bitNum = 0Dim as double t=timer#define loops 100000000print "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   #endifNextprint using "##.### seconds, badidea A"; timer-t;print ",  out: " & o & " - " & bin(o, 16)' ************* badidea B *************t=timerFor 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   #endifNextprint using "##.### seconds, badidea B"; timer-t;print ",  out: " & o & " - " & bin(o, 16)' ************* jj2007 *************t=timerFor n as integer=1 to loops   o=duplicate(i0)Nextprint using "##.### seconds, asm jj2007"; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* CoderJeff *************t=timerFor n as integer=1 to loops   o=dup8bits(i0)Nextprint 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

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
Posts: 2882
Joined: Nov 04, 2005 14:23
Contact:

Re: Bit duplication

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

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

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, -1073741824L0:  rol ecx, 2  shr edx, 1  je L1  jnc L0  or eax, ecx  jmp L0L1:  jnc Lx2  or eax, ecxLx2:  ret  end asmend functionFunction 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 Functionsub create(a() as longint,n as long=255) redim a(n) for i as long=0 to n a(i)=doublebitter(i) nextend subredim 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 asmend functionclsdim as ubyte i, i0dim as ushort o = 0, c = 0input "Number 0-255: ", ii0=i   ' keep a copyprint "in: " & i & " - " & bin(i, 8)dim as integer bitNum = 0Dim as double t=timer#define loops 100000000print "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   #endifNextprint using "##.### seconds, badidea A     "; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* badidea B *************t=timerFor 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   #endifNextprint using "##.### seconds, badidea B     "; timer-t;print ", out: " & o & " - " & bin(o, 16)' ************* jj2007 *************t=timerFor n as integer=1 to loops   o=duplicate(i0)Nextprint using "##.### seconds, assembly      "; timer-t;print ", out: " & o & " - " & bin(o, 16)'dodicatt=timercreate(dbitters(),i0)For n as integer=1 to loops   o=dbitters(i0)Nextprint using "##.### seconds, lookup        "; timer-t;print ", out: " & o & " - " & bin(o, 16)'coder jefft=timerFor n as integer=1 to loops   o= dup8bits(i0)Nextprint 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

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

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.