Shifting bits in an arbitrary number of bytes

Bare metal programming in PureBasic, for experienced users
coco2
Enthusiast
Enthusiast
Posts: 368
Joined: Mon Nov 25, 2013 5:38 am
Location: Australia

Shifting bits in an arbitrary number of bytes

Post 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?
User avatar
flaith
Enthusiast
Enthusiast
Posts: 704
Joined: Mon Apr 25, 2005 9:28 pm
Location: $300:20 58 FC 60 - Rennes
Contact:

Re: Shifting bits in an arbitrary number of bytes

Post 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
“Fear is a reaction. Courage is a decision.” - WC
coco2
Enthusiast
Enthusiast
Posts: 368
Joined: Mon Nov 25, 2013 5:38 am
Location: Australia

Re: Shifting bits in an arbitrary number of bytes

Post by coco2 »

Not quite :) I want to shift a WHOLE bunch of memory ALL to the left. And in ASM as fast as possible
User avatar
flaith
Enthusiast
Enthusiast
Posts: 704
Joined: Mon Apr 25, 2005 9:28 pm
Location: $300:20 58 FC 60 - Rennes
Contact:

Re: Shifting bits in an arbitrary number of bytes

Post by flaith »

Arf yes, just seen we are in Assembly topics :P
“Fear is a reaction. Courage is a decision.” - WC
coco2
Enthusiast
Enthusiast
Posts: 368
Joined: Mon Nov 25, 2013 5:38 am
Location: Australia

Re: Shifting bits in an arbitrary number of bytes

Post 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
Fred
Administrator
Administrator
Posts: 16619
Joined: Fri May 17, 2002 4:39 pm
Location: France
Contact:

Re: Shifting bits in an arbitrary number of bytes

Post 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 8)
- Use real pointer instead of PeekX() functions
- Avoid an If in a inner loop if possible
davido
Addict
Addict
Posts: 1890
Joined: Fri Nov 09, 2012 11:04 pm
Location: Uttoxeter, UK

Re: Shifting bits in an arbitrary number of bytes

Post 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. :)
DE AA EB
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Shifting bits in an arbitrary number of bytes

Post by wilbert »

Do you need to always shift with 1 bit or should that also be a variable ?
Windows (x64)
Raspberry Pi OS (Arm64)
coco2
Enthusiast
Enthusiast
Posts: 368
Joined: Mon Nov 25, 2013 5:38 am
Location: Australia

Re: Shifting bits in an arbitrary number of bytes

Post 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.
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Shifting bits in an arbitrary number of bytes

Post 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
Windows (x64)
Raspberry Pi OS (Arm64)
coco2
Enthusiast
Enthusiast
Posts: 368
Joined: Mon Nov 25, 2013 5:38 am
Location: Australia

Re: Shifting bits in an arbitrary number of bytes

Post 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
coco2
Enthusiast
Enthusiast
Posts: 368
Joined: Mon Nov 25, 2013 5:38 am
Location: Australia

Re: Shifting bits in an arbitrary number of bytes

Post 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
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Shifting bits in an arbitrary number of bytes

Post 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.
Windows (x64)
Raspberry Pi OS (Arm64)
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: Shifting bits in an arbitrary number of bytes

Post 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.
Windows (x64)
Raspberry Pi OS (Arm64)
coco2
Enthusiast
Enthusiast
Posts: 368
Joined: Mon Nov 25, 2013 5:38 am
Location: Australia

Re: Shifting bits in an arbitrary number of bytes

Post 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
Post Reply