Page 1 of 2
Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 8:07 am
by coco2
Does anyone have any code to do this?
For eg-
Procedure.i ShiftLeftBuffer(*data, length.i)
Which would shift *data left by 1? It would need to return a 1 if there was a carry. I'm working on a few ideas of my own but just wondering if anyone already has done it?
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 8:46 am
by flaith
Something like this?
Code used for byte only:
Code: Select all
#Flag_Carry = 1 << 7
Procedure.i ShiftLeftBuffer(val.c, length.i)
Debug "Before = %"+RSet(Bin(val,#PB_Byte),8,"0")
val << length
Debug "After = %"+RSet(Bin(val,#PB_Byte),8,"0")
If val & #Flag_Carry ;bit 7 = 1 ?
ProcedureReturn #True
Else
ProcedureReturn #False
EndIf
EndProcedure
val.c = %01000101
Debug ShiftLeftBuffer(val, 1) ; Should return True
val.c = %10001011
Debug ShiftLeftBuffer(val, 1) ; Should return False
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 8:48 am
by coco2
Not quite
I want to shift a WHOLE bunch of memory ALL to the left. And in ASM as fast as possible
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 8:51 am
by flaith
Arf yes, just seen we are in Assembly topics
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 10:44 am
by coco2
I'm trying to make an optimised version of this:
Code: Select all
Procedure.i ShiftLeftData(*d, length.i)
Define carry.i = 0, old_carry.i
While length
length = length - 1
old_carry = carry
carry = 0
If PeekA(*d+length) = 128
carry = 1
EndIf
PokeA(*d+length, (PeekA(*d+length) << 1) | old_carry)
Wend
ProcedureReturn carry
EndProcedure
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 10:50 am
by Fred
You should try to optimize it in PB before going to ASM. There is plenty room left for improvement here. A few clue:
- 2 different loops: one which work with integer to process 4 bytes (on x86) or 8 bytes (on x64) at once.
The second loop which works with byte for the remaining data (if not a multiple of 4 or
- Use real pointer instead of PeekX() functions
- Avoid an If in a inner loop if possible
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 11:02 am
by davido
@
coco2
Could you not simply increment the *pointer and then PeekS(*pointer) ?
Seems a lot quicker.
You could also hope for
wilbert to offer a turbo-charged assembly method.
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 11:11 am
by wilbert
Do you need to always shift with 1 bit or should that also be a variable ?
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 11:22 am
by coco2
Hi Fred that is what I was imagining in ASM but I thought I would skip the PB part Edit: I am trying your suggestions now
Hi Davido I'm not sure what you mean, although I wont be using strings as this is the most called procedure in an RSA encryption routine that gets called about 50000 times per 64 bytes of data :/
Wilbert it's part of my big number multiplication and division so always shifts by 1 bit, and if there is a carry I need to increase the buffer by 1 byte, or 4/8 bytes depending on the optimisiation.
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 11:46 am
by wilbert
Here's a very simple implementation.
It could be made faster by working with 4 bytes at once instead of 1 but that will make the code more complicated and maybe this simple version is fast enough for you.
Code: Select all
Procedure ShiftLeftBuffer(*data, length.l)
!clc
!mov ecx, [p.v_length]
!jecxz slb_exit
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!mov rdx, [p.p_data]
!slb_loop:
!rcl byte [rdx + rcx - 1], 1
CompilerElse
!mov edx, [p.p_data]
!slb_loop:
!rcl byte [edx + ecx - 1], 1
CompilerEndIf
!dec ecx
!jnz slb_loop
!slb_exit:
!sbb eax, eax
!neg eax
ProcedureReturn
EndProcedure
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 12:00 pm
by coco2
Wow that was fast Wilbert, thanks I'll have a play with it
Here is what I have done with Fred's suggestion, thanks guys I am such a noob I'm glad to have such experts to help me learn.
Code: Select all
Structure AArray
a.a[0]
EndStructure
Procedure ShiftLeft1(*d.AArray, length.i)
Define carry.i = 0, old_carry.i
While length
length = length - 1
old_carry = carry
carry = (*d\a[length] & $80) >> 7 ; Carry = $01 if bit $80 is set, else = $00
*d\a[length] = (*d\a[length] << 1) | old_carry
Wend
ProcedureReturn carry
EndProcedure
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 12:29 pm
by coco2
Hi Wilbert
The code is ~40% faster than the PB code, but shouldn't the LSB also be set for each byte depending on the last carry? Since RCL *rotates*
EDIT: my bad, I tested it and it works perfectly, output:
ShiftLeft()
00000001 10000001 00000001
00000011 00000010 00000010
ShiftLeftBuffer() <-- Wilbert version
00000001 10000001 00000001
00000011 00000010 00000010
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 12:58 pm
by wilbert
coco2 wrote:Hi Wilbert
The code is ~40% faster than the PB code, but shouldn't the LSB also be set for each byte depending on the last carry? Since RCL *rotates*
RCL rotates with Carry so when you use RCL the current carry flag becomes bit0, all bits are shifted 1 to the left and what was bit7 becomes the new carry flag.
Re: Shifting bits in an arbitrary number of bytes
Posted: Fri Jun 20, 2014 1:17 pm
by wilbert
If you could modify your program so that the length of the buffer to shift is always a multiple of 4, you could make it much faster, both ASM and PB.
Re: Shifting bits in an arbitrary number of bytes
Posted: Sat Jun 21, 2014 12:39 am
by coco2
Yes I will modify the code for 4 byte blocks, I want to add negative number support and also ECC support too. I am having trouble trying to make a shift right version of the ASM code, when I try the following I get an invalid memory error, do you know why?
Code: Select all
Procedure ShiftRightBuffer(*data, length.l)
!clc ; clear carry flag
!mov ecx, [p.v_length] ; set counter
!jecxz srb_exit ; if ecx zero jump to srb_exit
!xor eax, eax ; set eax to zero
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!mov rdx, [p.p_data] ; x64: move the pointer into rdx
!srb_loop:
!rcr byte [rdx + rax], 1 ; rotate the byte with the last bit placed in carry
CompilerElse
!mov edx, [p.p_data] ; x84: move the pointer into edx
!srb_loop:
!rcr byte [edx + eax], 1 ; rotate the byte with the last bit placed in carry
CompilerEndIf
!dec ecx ; decrement ecx
!inc eax
!jnz srb_loop
!srb_exit:
!sbb eax, eax ; move carry into eax
!neg eax ; eax = 0 - eax
ProcedureReturn ; return eax
EndProcedure