It is currently Wed Jan 20, 2021 5:28 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 8:07 am 
Offline
Enthusiast
Enthusiast

Joined: Mon Nov 25, 2013 5:38 am
Posts: 254
Location: Australia
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?


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 8:46 am 
Offline
Enthusiast
Enthusiast
User avatar

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

_________________
“Fear is a reaction. Courage is a decision.” - WC


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 8:48 am 
Offline
Enthusiast
Enthusiast

Joined: Mon Nov 25, 2013 5:38 am
Posts: 254
Location: Australia
Not quite :) I want to shift a WHOLE bunch of memory ALL to the left. And in ASM as fast as possible


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 8:51 am 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Mon Apr 25, 2005 9:28 pm
Posts: 704
Location: $300:20 58 FC 60 - Rennes
Arf yes, just seen we are in Assembly topics :P

_________________
“Fear is a reaction. Courage is a decision.” - WC


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 10:44 am 
Offline
Enthusiast
Enthusiast

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


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 10:50 am 
Offline
Administrator
Administrator

Joined: Fri May 17, 2002 4:39 pm
Posts: 14181
Location: France
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


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 11:02 am 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1807
Location: Uttoxeter, UK
@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


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 11:11 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
Do you need to always shift with 1 bit or should that also be a variable ?

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 11:22 am 
Offline
Enthusiast
Enthusiast

Joined: Mon Nov 25, 2013 5:38 am
Posts: 254
Location: Australia
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 11:46 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
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

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 12:00 pm 
Offline
Enthusiast
Enthusiast

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


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 12:29 pm 
Offline
Enthusiast
Enthusiast

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


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 12:58 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
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.

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Fri Jun 20, 2014 1:17 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
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.

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: Shifting bits in an arbitrary number of bytes
PostPosted: Sat Jun 21, 2014 12:39 am 
Offline
Enthusiast
Enthusiast

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


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye