Another way to left shift a 32 bit data?

[Ioannis]

Looking to left shift as fast as possible a 32 bit variable by n times.

Obviously the first thought is by a PBP for-next loop n times. Slow.

The second thought in Assembly loop. Much faster.

Any other idea? Something like XOR etc?

The 32 bit variable start always as 1 and this maybe can help finding a fast alternative to left shift the number.

Thanks,
Ioannis

[towlerg]

Not sure if I've understood your problem but how about a fixed array of 32bit numbers, each a constant with 1 bit shifted left. Use n to index into the array.

So the array would be initialised as 1,2,4,8,16,32,64 etc etc

Code would look like Answer=Array[n]

I guess you could do it as a table in code memory if you can find a way to index it.

George

[HenrikOlsson]

How about the DCD operator? Is that what you're looking for? Is it fast enough?

DCD returns the decoded value of a bit number. It changes a bit number (0 - 31) into a binary number with only that bit set to 1. All other bits are set to 0.

B0 = DCD 2  ' Sets B0 to %00000100

/Henrik.

[Ioannis]

Thanks for the ideas!

About the time they take, I have to test it. But the George's idea I guess it needs a fixed time. The DCD may need different time for setting the first or last bit using a loop.

Thanks for the replies.

Ioannis

[Art]

Where did you get a 32 bit variable that PBP knows about? Is this a feature of PBP3?
Can you alias and access the same variable as the four bytes?
Since towerg mentioned “array” I’m not sure. a single variable of a datatype isn’t an array.

[Art]

You didn’t say what you want to do with the bit that drops off the end.
Assuming you want what PBP shift would do with a byte, and just drop the end bit,
and feed in a zero to the right.

dis var byte [4]

BitwiseRotateLeft:						' bitwise rotate array
  @ rlf 	_dis+3		,F				; ditching the first bit
  @ rlf		_dis+2		,F				;
  @ rlf		_dis+1		,F				;
  @ rlf		_dis+0		,F				;
  @ bcf		_dis+3		,0				;clear MSB
return

So long as you can access the first byte by aliasing it, I’m sure the assembler is a continuous 4 bytes.

[Ioannis]

Well, yes, it is a PBP3 feature. But besides that, even if you are on a previous version, you may still face the fact of 32 bit variables.

At the cost of 4x8x32 bytes, George's approach is obviously the fastest because n (times a shiftmust happen) can be anywhere between 1 and 32.

Thanks for the post.

Ioannis

[Art]

Oh I get it, the 32 bit var always has 31 clear bits and 1 set bit.

[Ioannis]

Yes, thats right.

In case you wonder is part of the Microchip Keeloq algo. A really intense algo...

Ioannis

[Art]

Can LOOKUP/2 now contain enough elements,
or you'd need to use 4 lookups? (One for each byte element of the 32 bit val).
It does sound like reading program memory would be economical for that.

[Ioannis]

Since using LONGs in the program will slow down the execution of the program, I am reluctant to use longs. Also the PIC that curretly is used is 16F series.

So, seems better to spend some bytes in RAM or FLASH and have immediate response.

Ioannis

[Art]

That’s what I mean. Still a more difficult problem than appears, or more than it intuitively feels like it should be, if speed is the goal.
The extra 6 bits returned by a single 14 bit READCODE are useless to you because of the time taken to extract them.
The word variable you get to use to address program memory is also useless to you because you only needed a 32 bit index (or 32x4).
I’d be interested to hear how you end up tackling it.

[Ioannis]

It is indeed a complex problem. In any option chosen, there would be some overhead lower or higher I guess.

I think I will end up in the asm code to rotate the variables.

Ioannis

[richard]

you can set or clr any bit in an array
dis var byte [4]

dis.0[x] = 1 ; will set bit x in array dis where x=0 to 31

or make a user command something like this (untested)
USERCOMMAND "SETBIT" ; BIT,VALUE

SETBIT?CC macro Bitin,Val
if Bitin <32
  if Bitin > 23
k=3
  elseif  Bitin > 15
k=2
  elseif  Bitin > 7
k=1
  elseif  Bitin <8
k=0
  endif
b=Bitin-k*8


  if Val >0
  bsf _dis+k,b
  else
  bcf  _dis+k,b
  endif
endif
endm

not sure if user cmd is really useful here

[Ioannis]

Thanks Richard.

Interesting approach!

Ioannis

[Art]

I don’t yet know if I’ve wrecked it in basic.

shifter byte
offset byte
array byte[7]


shifter = 11
offset = shifter >> 3            // byte in array to pass to whatever needs the 4 byte result, in this case 2
array[3] = 1<<(shifter & 7)      // Set it to 00000000 (00000000 00000000 00001000 00000000) 00000000 00000000
‘dostuff with array[offset]

[Ioannis]

I could not follow that...

Ioannis

[Art]

So long as I have not ruined the way a C pointer will work...

Before any input, the 32 bits you want could be anywhere within the 7 byte array.
After computation, the memory location of the four bytes of the 32 bit value begins at array[offset].

[Ioannis]

Oh, I see. Thanks for the ideas.

Still, asm rotate will be faster.

Ioannis

[Art]

I have my doubts, You only have to call it once.
Assuming there is equal chance the input is 0-31, an assembler rotate routine will be called mean of 15 times.
For a shift in either language the overhead is in finding the byte you want to shift.

Again, assuming it’s still working. I’ll be able to try in PBP soon.

If I’m mistaken and it’s not another trick you’ve worked out because of the known state of the array at the beginning, that would be helpful.
It is currently taking me the equal number of assembler instructions as there are bytes in the array to bitwise rotate an array
that has unknown contents at the beginning, which is the same as in the sixth post of this thread.

[Ioannis]

I have a problem (what a surprise, huh?) with the MPLAB. It has a tool or something that helps to measure the exact time it takes for a routine to execute. No Osciloscopes, no pins to make high / low etc.

Yes, the asm way will take from 1 to 32 times since we do not know the times to shift. But as you showed in #6, it takes give or take 5 asm instructions for one shift, max 32x5. Basic I think cannot beat that.

Ioannis

[Art]

The code in post 16 that will easily beat that, and take the same duration no matter what the input.
I’ve only measured PBP by disassembly and then counting the assembler instruction time.
Bitwise rotation of each byte is one instruction, shifting and other bitwise operations that have an input value should be two assembler instructions.

But yes, using the same technique as post #16 expressed in PBP will beat the assembler in post #6.

Consider the value you begin with begins at array location 0,
and your input is 16, so you need to rotate it 16 times:

00000000 00000000 00000000 00000001
^
arraylocation[0]

Divide the 16 by 8, and result is 2. Add 2 to the array location index and bingo:



The reason your 4 byte array has values around it is so you can still use the four bit value



The only thing that complicates it is that your input won’t often be evenly divisible by 2.
The rest of the code shifts the byte by the modulus.
You could still easily beat the asm rotation with a single PBP divide with modulus,
but PBP might not beat the particular implementation of asm divide and modulus!

I edited images in there because I wasn’t getting fixed width for spaces.