# PureBasic Forum

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

 All times are UTC + 1 hour

 Page 1 of 2 [ 20 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 8:07 am
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 8:46 am
 Enthusiast

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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 8:48 am
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 8:51 am
 Enthusiast

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

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

Top

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 10:44 am
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 10:50 am

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
- Use real pointer instead of PeekX() functions
- Avoid an If in a inner loop if possible

Top

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 11:02 am

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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 11:11 am
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 11:22 am
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 11:46 am
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 12:00 pm
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 12:29 pm
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 12:58 pm
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Fri Jun 20, 2014 1:17 pm
 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

 Post subject: Re: Shifting bits in an arbitrary number of bytesPosted: Sat Jun 21, 2014 12:39 am
 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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 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 forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ PureBasic    Coding Questions    Game Programming    3D Programming    Assembly Programming    The PureBasic Editor    The PureBasic Form Designer    General Discussion    Feature Requests and Wishlists    Tricks 'n' Tips Bug Reports    Bugs - Windows    Bugs - Linux    Bugs - Mac OSX    Bugs - IDE    Bugs - Documentation OS Specific    AmigaOS    Linux    Windows    Mac OSX Miscellaneous    Announcement    Off Topic Showcase    Applications - Feedback and Discussion    PureFORM & JaPBe    TailBite