Shifting bits in an arbitrary number of bytes

coco2 · **Posted:** Fri Jun 20, 2014 8:07 am

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?

flaith · **Posted:** Fri Jun 20, 2014 8:46 am

Something like this?
Code used for byte only:

Code:

#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

coco2 · **Posted:** Fri Jun 20, 2014 8:48 am

Not quite

I want to shift a WHOLE bunch of memory ALL to the left. And in ASM as fast as possible

flaith · **Posted:** Fri Jun 20, 2014 8:51 am

Arf yes, just seen we are in Assembly topics

coco2 · **Posted:** Fri Jun 20, 2014 10:44 am

I'm trying to make an optimised version of this:

Code:

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

Fred · **Posted:** Fri Jun 20, 2014 10:50 am

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

davido · **Posted:** Fri Jun 20, 2014 11:02 am

@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.

wilbert · **Posted:** Fri Jun 20, 2014 11:11 am

Do you need to always shift with 1 bit or should that also be a variable ?

coco2 · **Posted:** Fri Jun 20, 2014 11:22 am

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.

wilbert · **Posted:** Fri Jun 20, 2014 11:46 am

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:

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

coco2 · **Posted:** Fri Jun 20, 2014 12:00 pm

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:

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

coco2 · **Posted:** Fri Jun 20, 2014 12:29 pm

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

wilbert · **Posted:** Fri Jun 20, 2014 12:58 pm

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.

wilbert · **Posted:** Fri Jun 20, 2014 1:17 pm

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.

coco2 · **Posted:** Sat Jun 21, 2014 12:39 am

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:

  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

PureBasic Forum

Shifting bits in an arbitrary number of bytes

Who is online