faster shift left circular (rotate)

**Kenneth Lantrip** · Nov 20 '05, 10:07 AM

Re: faster shift left circular (rotate)

On Mon, 22 Dec 2003 12:43:07 -0600, Kenneth Lantrip
<vip01@mindspri ng.com> wrote:
[color=blue]
>Anyone got any ideas as to how this process could be improved for speed?
>
>this is what I have...
>
> Dim j, q As Integer
> Dim x(16), y(16) As Byte
>
>[ not all code is shown ... only the relevant parts ]
>
> x.CopyTo(y, 0) ' shift left circular 24 bits
> For j = 0 To 15
> q = (j + 3) And 15
> x(j + 1) = y(q + 1)
> Next
> ' shift left circular 1 more bit
> If x(1) And &H80 Then q = True Else q = False
> For j = 1 To 16
> x(j) = (x(j) * 2) And &HFF
> If j < 16 Then
> If x(j + 1) And &H80 Then x(j) += 1
> Else
> If q Then x(j) += 1
> End If
> Next
>
>I need to shift shift all the bits in the array [x] 25 bits to the left
>(circular) as quickly as possible.
>
>I don't "have" to have an array. I could use a 64 bit integer if needed.[/color]

OK just to answer my own question... I have unrolled the loops and
optimized just a little...

dim x(16), y(4) in integer

' shift left circular 25 bits
y(1) = x(1)
y(2) = x(2)
y(3) = x(3)
y(4) = x(4)
x(1) = (x(4) * 2 - ((x(5) And &H80) <> 0)) And &HFF
x(2) = (x(5) * 2 - ((x(6) And &H80) <> 0)) And &HFF
x(3) = (x(6) * 2 - ((x(7) And &H80) <> 0)) And &HFF
x(4) = (x(7) * 2 - ((x(8) And &H80) <> 0)) And &HFF
x(5) = (x(8) * 2 - ((x(9) And &H80) <> 0)) And &HFF
x(6) = (x(9) * 2 - ((x(10) And &H80) <> 0)) And &HFF
x(7) = (x(10) * 2 - ((x(11) And &H80) <> 0)) And &HFF
x(8) = (x(11) * 2 - ((x(12) And &H80) <> 0)) And &HFF
x(9) = (x(12) * 2 - ((x(13) And &H80) <> 0)) And &HFF
x(10) = (x(13) * 2 - ((x(14) And &H80) <> 0)) And &HFF
x(11) = (x(14) * 2 - ((x(15) And &H80) <> 0)) And &HFF
x(12) = (x(15) * 2 - ((x(16) And &H80) <> 0)) And &HFF
x(13) = (x(16) * 2 - ((y(1) And &H80) <> 0)) And &HFF
x(14) = (y(1) * 2 - ((y(2) And &H80) <> 0)) And &HFF
x(15) = (y(2) * 2 - ((y(3) And &H80) <> 0)) And &HFF
x(16) = (y(3) * 2 - ((y(4) And &H80) <> 0)) And &HFF

**Jay B. Harlow [MVP - Outlook]** · Nov 20 '05, 10:12 AM

Re: faster shift left circular (rotate)

Kenneth,
In addition to unrolling the loop, I would consider using the bit shift
operators in VS.NET 2003. Plus I would consider using the longest integer
available (Long instead of Integer).

However I would "profile" Long verses Integer to ensure that the Long is
giving me a speed boost.

Hope this helps
Jay

"Kenneth Lantrip" <bothersome@min dspring.com> wrote in message
news:s06fuvs0go ekcu40saovt552e vtqm9bvfe@4ax.c om...[color=blue]
> On Mon, 22 Dec 2003 12:43:07 -0600, Kenneth Lantrip
> <vip01@mindspri ng.com> wrote:
>[color=green]
> >Anyone got any ideas as to how this process could be improved for speed?
> >
> >this is what I have...
> >
> > Dim j, q As Integer
> > Dim x(16), y(16) As Byte
> >
> >[ not all code is shown ... only the relevant parts ]
> >
> > x.CopyTo(y, 0) ' shift left circular 24 bits
> > For j = 0 To 15
> > q = (j + 3) And 15
> > x(j + 1) = y(q + 1)
> > Next
> > ' shift left circular 1 more bit
> > If x(1) And &H80 Then q = True Else q = False
> > For j = 1 To 16
> > x(j) = (x(j) * 2) And &HFF
> > If j < 16 Then
> > If x(j + 1) And &H80 Then x(j) += 1
> > Else
> > If q Then x(j) += 1
> > End If
> > Next
> >
> >I need to shift shift all the bits in the array [x] 25 bits to the left
> >(circular) as quickly as possible.
> >
> >I don't "have" to have an array. I could use a 64 bit integer if needed.[/color]
>
> OK just to answer my own question... I have unrolled the loops and
> optimized just a little...
>
> dim x(16), y(4) in integer
>
> ' shift left circular 25 bits
> y(1) = x(1)
> y(2) = x(2)
> y(3) = x(3)
> y(4) = x(4)
> x(1) = (x(4) * 2 - ((x(5) And &H80) <> 0)) And &HFF
> x(2) = (x(5) * 2 - ((x(6) And &H80) <> 0)) And &HFF
> x(3) = (x(6) * 2 - ((x(7) And &H80) <> 0)) And &HFF
> x(4) = (x(7) * 2 - ((x(8) And &H80) <> 0)) And &HFF
> x(5) = (x(8) * 2 - ((x(9) And &H80) <> 0)) And &HFF
> x(6) = (x(9) * 2 - ((x(10) And &H80) <> 0)) And &HFF
> x(7) = (x(10) * 2 - ((x(11) And &H80) <> 0)) And &HFF
> x(8) = (x(11) * 2 - ((x(12) And &H80) <> 0)) And &HFF
> x(9) = (x(12) * 2 - ((x(13) And &H80) <> 0)) And &HFF
> x(10) = (x(13) * 2 - ((x(14) And &H80) <> 0)) And &HFF
> x(11) = (x(14) * 2 - ((x(15) And &H80) <> 0)) And &HFF
> x(12) = (x(15) * 2 - ((x(16) And &H80) <> 0)) And &HFF
> x(13) = (x(16) * 2 - ((y(1) And &H80) <> 0)) And &HFF
> x(14) = (y(1) * 2 - ((y(2) And &H80) <> 0)) And &HFF
> x(15) = (y(2) * 2 - ((y(3) And &H80) <> 0)) And &HFF
> x(16) = (y(3) * 2 - ((y(4) And &H80) <> 0)) And &HFF
>
>[/color]

**Jay B. Harlow [MVP - Outlook]** · Nov 20 '05, 10:12 AM

Re: faster shift left circular (rotate)

Kenneth,
I have not tested this 100%, I believe the following does what you want
using VS.NET 2003:

Dim x(15) As Byte ' 16 bytes
Dim y(3) As Integer ' 4 integers

System.Buffer.B lockCopy(x, 0, y, 0, 16)

Dim y4 As Integer = y(3)

y(3) = y(3) << 25 Or y(2) >> 32 - 25
y(2) = y(2) << 25 Or y(1) >> 32 - 25
y(1) = y(1) << 25 Or y(0) >> 32 - 25
y(0) = y(0) << 25 Or y4 >> 32 - 25

System.Buffer.B lockCopy(y, 0, x, 0, 16)

Instead of bit shifts you should be able to use multiplication & division in
VS.NET 2002 with the appropriate power of 2, something like:

Const leftshift As Integer = &H2000000
Const rightshift As Integer = &H80

Dim x(15) As Byte
Dim y(3) As Integer

System.Buffer.B lockCopy(x, 0, y, 0, 16)

Dim y4 As Integer = y(3)

y(3) = (y(3) And &H3F) * leftshift Or y(2) \ rightshift
y(2) = (y(2) And &H3F) * leftshift Or y(1) \ rightshift
y(1) = (y(1) And &H3F) * leftshift Or y(0) \ rightshift
y(0) = (y(0) And &H3F) * leftshift Or y4 \ rightshift

System.Buffer.B lockCopy(y, 0, x, 0, 16)

Remember that arrays start with element 0, hence my array of 15 & 3 are
upper bounds.

Hope this helps
Jay

"Kenneth Lantrip" <bothersome@min dspring.com> wrote in message
news:s06fuvs0go ekcu40saovt552e vtqm9bvfe@4ax.c om...[color=blue]
> On Mon, 22 Dec 2003 12:43:07 -0600, Kenneth Lantrip
> <vip01@mindspri ng.com> wrote:
>[color=green]
> >Anyone got any ideas as to how this process could be improved for speed?
> >
> >this is what I have...
> >
> > Dim j, q As Integer
> > Dim x(16), y(16) As Byte
> >
> >[ not all code is shown ... only the relevant parts ]
> >
> > x.CopyTo(y, 0) ' shift left circular 24 bits
> > For j = 0 To 15
> > q = (j + 3) And 15
> > x(j + 1) = y(q + 1)
> > Next
> > ' shift left circular 1 more bit
> > If x(1) And &H80 Then q = True Else q = False
> > For j = 1 To 16
> > x(j) = (x(j) * 2) And &HFF
> > If j < 16 Then
> > If x(j + 1) And &H80 Then x(j) += 1
> > Else
> > If q Then x(j) += 1
> > End If
> > Next
> >
> >I need to shift shift all the bits in the array [x] 25 bits to the left
> >(circular) as quickly as possible.
> >
> >I don't "have" to have an array. I could use a 64 bit integer if needed.[/color]
>
> OK just to answer my own question... I have unrolled the loops and
> optimized just a little...
>
> dim x(16), y(4) in integer
>
> ' shift left circular 25 bits
> y(1) = x(1)
> y(2) = x(2)
> y(3) = x(3)
> y(4) = x(4)
> x(1) = (x(4) * 2 - ((x(5) And &H80) <> 0)) And &HFF
> x(2) = (x(5) * 2 - ((x(6) And &H80) <> 0)) And &HFF
> x(3) = (x(6) * 2 - ((x(7) And &H80) <> 0)) And &HFF
> x(4) = (x(7) * 2 - ((x(8) And &H80) <> 0)) And &HFF
> x(5) = (x(8) * 2 - ((x(9) And &H80) <> 0)) And &HFF
> x(6) = (x(9) * 2 - ((x(10) And &H80) <> 0)) And &HFF
> x(7) = (x(10) * 2 - ((x(11) And &H80) <> 0)) And &HFF
> x(8) = (x(11) * 2 - ((x(12) And &H80) <> 0)) And &HFF
> x(9) = (x(12) * 2 - ((x(13) And &H80) <> 0)) And &HFF
> x(10) = (x(13) * 2 - ((x(14) And &H80) <> 0)) And &HFF
> x(11) = (x(14) * 2 - ((x(15) And &H80) <> 0)) And &HFF
> x(12) = (x(15) * 2 - ((x(16) And &H80) <> 0)) And &HFF
> x(13) = (x(16) * 2 - ((y(1) And &H80) <> 0)) And &HFF
> x(14) = (y(1) * 2 - ((y(2) And &H80) <> 0)) And &HFF
> x(15) = (y(2) * 2 - ((y(3) And &H80) <> 0)) And &HFF
> x(16) = (y(3) * 2 - ((y(4) And &H80) <> 0)) And &HFF
>
>[/color]

**Jay B. Harlow [MVP - Outlook]** · Nov 20 '05, 10:13 AM

Re: faster shift left circular (rotate)

Kenneth,
Here's a VS.NET 2003 variation of my earlier post using Longs.

Dim x(15) As Byte
Dim y(1) As Long
System.Buffer.B lockCopy(x, 0, y, 0, 16)

Dim y2 As Long = y(1)

y(1) = y(1) << 25 Or y(0) >> 64 - 25
y(0) = y(0) << 25 Or y2 >> 64 - 25

System.Buffer.B lockCopy(y, 0, x, 0, 16)

Hope this helps
Jay

"Kenneth Lantrip" <bothersome@min dspring.com> wrote in message
news:s06fuvs0go ekcu40saovt552e vtqm9bvfe@4ax.c om...[color=blue]
> On Mon, 22 Dec 2003 12:43:07 -0600, Kenneth Lantrip
> <vip01@mindspri ng.com> wrote:
>[color=green]
> >Anyone got any ideas as to how this process could be improved for speed?
> >
> >this is what I have...
> >
> > Dim j, q As Integer
> > Dim x(16), y(16) As Byte
> >
> >[ not all code is shown ... only the relevant parts ]
> >
> > x.CopyTo(y, 0) ' shift left circular 24 bits
> > For j = 0 To 15
> > q = (j + 3) And 15
> > x(j + 1) = y(q + 1)
> > Next
> > ' shift left circular 1 more bit
> > If x(1) And &H80 Then q = True Else q = False
> > For j = 1 To 16
> > x(j) = (x(j) * 2) And &HFF
> > If j < 16 Then
> > If x(j + 1) And &H80 Then x(j) += 1
> > Else
> > If q Then x(j) += 1
> > End If
> > Next
> >
> >I need to shift shift all the bits in the array [x] 25 bits to the left
> >(circular) as quickly as possible.
> >
> >I don't "have" to have an array. I could use a 64 bit integer if needed.[/color]
>
> OK just to answer my own question... I have unrolled the loops and
> optimized just a little...
>
> dim x(16), y(4) in integer
>
> ' shift left circular 25 bits
> y(1) = x(1)
> y(2) = x(2)
> y(3) = x(3)
> y(4) = x(4)
> x(1) = (x(4) * 2 - ((x(5) And &H80) <> 0)) And &HFF
> x(2) = (x(5) * 2 - ((x(6) And &H80) <> 0)) And &HFF
> x(3) = (x(6) * 2 - ((x(7) And &H80) <> 0)) And &HFF
> x(4) = (x(7) * 2 - ((x(8) And &H80) <> 0)) And &HFF
> x(5) = (x(8) * 2 - ((x(9) And &H80) <> 0)) And &HFF
> x(6) = (x(9) * 2 - ((x(10) And &H80) <> 0)) And &HFF
> x(7) = (x(10) * 2 - ((x(11) And &H80) <> 0)) And &HFF
> x(8) = (x(11) * 2 - ((x(12) And &H80) <> 0)) And &HFF
> x(9) = (x(12) * 2 - ((x(13) And &H80) <> 0)) And &HFF
> x(10) = (x(13) * 2 - ((x(14) And &H80) <> 0)) And &HFF
> x(11) = (x(14) * 2 - ((x(15) And &H80) <> 0)) And &HFF
> x(12) = (x(15) * 2 - ((x(16) And &H80) <> 0)) And &HFF
> x(13) = (x(16) * 2 - ((y(1) And &H80) <> 0)) And &HFF
> x(14) = (y(1) * 2 - ((y(2) And &H80) <> 0)) And &HFF
> x(15) = (y(2) * 2 - ((y(3) And &H80) <> 0)) And &HFF
> x(16) = (y(3) * 2 - ((y(4) And &H80) <> 0)) And &HFF
>
>[/color]

**DumberThanSnot** · Nov 20 '05, 10:13 AM

Re: faster shift left circular (rotate)

if you don't "have" to have an array, then this might be what your looking
for using an integer.

\\\\\
Dim iVal as Integer

iVal = 234524523 ' bin = 0000 1101 1111 1010 1000 1111 0110 1011

iVal = (iVal * 2) Xor ((iVal / 2 ^ 30) And 1)

iVal = 469049046 ' bin = 0001 1011 1111 0101 0001 1110 1101 0110
/////

you could replace the 2 ^ 30 with a 2 ^ 25 for your example. 2 ^ 25 takes
more time for the computer to calculate, so I would replace the 2 ^ 25 with
&h2000000 for faster compute times.

-brian

"Kenneth Lantrip" <vip01@mindspri ng.com> wrote in message
news:OKUoDtLyDH A.2556@TK2MSFTN GP10.phx.gbl...[color=blue]
> Anyone got any ideas as to how this process could be improved for speed?
>
> this is what I have...
>
> Dim j, q As Integer
> Dim x(16), y(16) As Byte
>
> [ not all code is shown ... only the relevant parts ]
>
> x.CopyTo(y, 0) ' shift left circular 24 bits
> For j = 0 To 15
> q = (j + 3) And 15
> x(j + 1) = y(q + 1)
> Next
> ' shift left circular 1 more bit
> If x(1) And &H80 Then q = True Else q = False
> For j = 1 To 16
> x(j) = (x(j) * 2) And &HFF
> If j < 16 Then
> If x(j + 1) And &H80 Then x(j) += 1
> Else
> If q Then x(j) += 1
> End If
> Next
>
> I need to shift shift all the bits in the array [x] 25 bits to the left
> (circular) as quickly as possible.
>
> I don't "have" to have an array. I could use a 64 bit integer if needed.
>[/color]

**Kenneth Lantrip** · Nov 20 '05, 10:13 AM

Re: faster shift left circular (rotate)

Thanks Jay... It looks like I'll need to upgrade to 2003 pretty soon
now. Cause I just love these shift bit operations... Coming from a C
world and all! :)

It still boggles the mind as to why they didn't think they'd need these
since version .000001 pre-alpha-just-an-idea-stage???

I see other great tips in your source too!!

Many thanks Jay.

Jay B. Harlow [MVP - Outlook] wrote:[color=blue]
> Kenneth,
> Here's a VS.NET 2003 variation of my earlier post using Longs.
>
> Dim x(15) As Byte
> Dim y(1) As Long
> System.Buffer.B lockCopy(x, 0, y, 0, 16)
>
> Dim y2 As Long = y(1)
>
> y(1) = y(1) << 25 Or y(0) >> 64 - 25
> y(0) = y(0) << 25 Or y2 >> 64 - 25
>
> System.Buffer.B lockCopy(y, 0, x, 0, 16)
>
> Hope this helps
> Jay
>
> "Kenneth Lantrip" <bothersome@min dspring.com> wrote in message
> news:s06fuvs0go ekcu40saovt552e vtqm9bvfe@4ax.c om...
>[color=green]
>>On Mon, 22 Dec 2003 12:43:07 -0600, Kenneth Lantrip
>><vip01@mindsp ring.com> wrote:
>>
>>[color=darkred]
>>>Anyone got any ideas as to how this process could be improved for speed?
>>>
>>>this is what I have...
>>>
>>> Dim j, q As Integer
>>> Dim x(16), y(16) As Byte
>>>
>>>[ not all code is shown ... only the relevant parts ]
>>>
>>> x.CopyTo(y, 0) ' shift left circular 24 bits
>>> For j = 0 To 15
>>> q = (j + 3) And 15
>>> x(j + 1) = y(q + 1)
>>> Next
>>> ' shift left circular 1 more bit
>>> If x(1) And &H80 Then q = True Else q = False
>>> For j = 1 To 16
>>> x(j) = (x(j) * 2) And &HFF
>>> If j < 16 Then
>>> If x(j + 1) And &H80 Then x(j) += 1
>>> Else
>>> If q Then x(j) += 1
>>> End If
>>> Next
>>>
>>>I need to shift shift all the bits in the array [x] 25 bits to the left
>>>(circular) as quickly as possible.
>>>
>>>I don't "have" to have an array. I could use a 64 bit integer if needed.[/color]
>>
>>OK just to answer my own question... I have unrolled the loops and
>>optimized just a little...
>>
>>dim x(16), y(4) in integer
>>
>> ' shift left circular 25 bits
>> y(1) = x(1)
>> y(2) = x(2)
>> y(3) = x(3)
>> y(4) = x(4)
>> x(1) = (x(4) * 2 - ((x(5) And &H80) <> 0)) And &HFF
>> x(2) = (x(5) * 2 - ((x(6) And &H80) <> 0)) And &HFF
>> x(3) = (x(6) * 2 - ((x(7) And &H80) <> 0)) And &HFF
>> x(4) = (x(7) * 2 - ((x(8) And &H80) <> 0)) And &HFF
>> x(5) = (x(8) * 2 - ((x(9) And &H80) <> 0)) And &HFF
>> x(6) = (x(9) * 2 - ((x(10) And &H80) <> 0)) And &HFF
>> x(7) = (x(10) * 2 - ((x(11) And &H80) <> 0)) And &HFF
>> x(8) = (x(11) * 2 - ((x(12) And &H80) <> 0)) And &HFF
>> x(9) = (x(12) * 2 - ((x(13) And &H80) <> 0)) And &HFF
>> x(10) = (x(13) * 2 - ((x(14) And &H80) <> 0)) And &HFF
>> x(11) = (x(14) * 2 - ((x(15) And &H80) <> 0)) And &HFF
>> x(12) = (x(15) * 2 - ((x(16) And &H80) <> 0)) And &HFF
>> x(13) = (x(16) * 2 - ((y(1) And &H80) <> 0)) And &HFF
>> x(14) = (y(1) * 2 - ((y(2) And &H80) <> 0)) And &HFF
>> x(15) = (y(2) * 2 - ((y(3) And &H80) <> 0)) And &HFF
>> x(16) = (y(3) * 2 - ((y(4) And &H80) <> 0)) And &HFF
>>
>>[/color]
>
>
>[/color]

**Jay B. Harlow [MVP - Outlook]** · Nov 20 '05, 10:13 AM

Re: faster shift left circular (rotate)

Brian,
I would avoid both ^ & / in your example, as they involve floating point
math...

In addition to using the constant &h2000000 as you suggested I would
recommend using integer division \ instead. This way floating point numbers
are avoided entirely!

Hope this helps
Jay

"DumberThanSnot " <DumberThanSnot @nospam.com> wrote in message
news:eJbka2YyDH A.2620@TK2MSFTN GP09.phx.gbl...[color=blue]
> if you don't "have" to have an array, then this might be what your looking
> for using an integer.
>
> \\\\\
> Dim iVal as Integer
>
> iVal = 234524523 ' bin = 0000 1101 1111 1010 1000 1111 0110 1011
>
> iVal = (iVal * 2) Xor ((iVal / 2 ^ 30) And 1)
>
> iVal = 469049046 ' bin = 0001 1011 1111 0101 0001 1110 1101 0110
> /////
>
> you could replace the 2 ^ 30 with a 2 ^ 25 for your example. 2 ^ 25 takes
> more time for the computer to calculate, so I would replace the 2 ^ 25[/color]
with[color=blue]
> &h2000000 for faster compute times.
>
> -brian
>
>
> "Kenneth Lantrip" <vip01@mindspri ng.com> wrote in message
> news:OKUoDtLyDH A.2556@TK2MSFTN GP10.phx.gbl...[color=green]
> > Anyone got any ideas as to how this process could be improved for speed?
> >
> > this is what I have...
> >
> > Dim j, q As Integer
> > Dim x(16), y(16) As Byte
> >
> > [ not all code is shown ... only the relevant parts ]
> >
> > x.CopyTo(y, 0) ' shift left circular 24 bits
> > For j = 0 To 15
> > q = (j + 3) And 15
> > x(j + 1) = y(q + 1)
> > Next
> > ' shift left circular 1 more bit
> > If x(1) And &H80 Then q = True Else q = False
> > For j = 1 To 16
> > x(j) = (x(j) * 2) And &HFF
> > If j < 16 Then
> > If x(j + 1) And &H80 Then x(j) += 1
> > Else
> > If q Then x(j) += 1
> > End If
> > Next
> >
> > I need to shift shift all the bits in the array [x] 25 bits to the left
> > (circular) as quickly as possible.
> >
> > I don't "have" to have an array. I could use a 64 bit integer if[/color][/color]
needed.[color=blue][color=green]
> >[/color]
>
>[/color]

**DumberThanSnot** · Nov 20 '05, 10:13 AM

Re: faster shift left circular (rotate)

oops... habit type-o that I typed "/" instead if "\". I have 2003, so I
used "<<" and ">>". I gave a Framework independent example... That's what I
get for not rechecking my typing.

Thanks for pointing it out! ;-)

-brian

"Jay B. Harlow [MVP - Outlook]" <Jay_Harlow_MVP @msn.com> wrote in message
news:uCujYGZyDH A.2304@TK2MSFTN GP12.phx.gbl...[color=blue]
> Brian,
> I would avoid both ^ & / in your example, as they involve floating point
> math...
>
> In addition to using the constant &h2000000 as you suggested I would
> recommend using integer division \ instead. This way floating point[/color]
numbers[color=blue]
> are avoided entirely!
>
> Hope this helps
> Jay
>
> "DumberThanSnot " <DumberThanSnot @nospam.com> wrote in message
> news:eJbka2YyDH A.2620@TK2MSFTN GP09.phx.gbl...[color=green]
> > if you don't "have" to have an array, then this might be what your[/color][/color]
looking[color=blue][color=green]
> > for using an integer.
> >
> > \\\\\
> > Dim iVal as Integer
> >
> > iVal = 234524523 ' bin = 0000 1101 1111 1010 1000 1111 0110 1011
> >
> > iVal = (iVal * 2) Xor ((iVal / 2 ^ 30) And 1)
> >
> > iVal = 469049046 ' bin = 0001 1011 1111 0101 0001 1110 1101 0110
> > /////
> >
> > you could replace the 2 ^ 30 with a 2 ^ 25 for your example. 2 ^ 25[/color][/color]
takes[color=blue][color=green]
> > more time for the computer to calculate, so I would replace the 2 ^ 25[/color]
> with[color=green]
> > &h2000000 for faster compute times.
> >
> > -brian
> >
> >
> > "Kenneth Lantrip" <vip01@mindspri ng.com> wrote in message
> > news:OKUoDtLyDH A.2556@TK2MSFTN GP10.phx.gbl...[color=darkred]
> > > Anyone got any ideas as to how this process could be improved for[/color][/color][/color]
speed?[color=blue][color=green][color=darkred]
> > >
> > > this is what I have...
> > >
> > > Dim j, q As Integer
> > > Dim x(16), y(16) As Byte
> > >
> > > [ not all code is shown ... only the relevant parts ]
> > >
> > > x.CopyTo(y, 0) ' shift left circular 24 bits
> > > For j = 0 To 15
> > > q = (j + 3) And 15
> > > x(j + 1) = y(q + 1)
> > > Next
> > > ' shift left circular 1 more bit
> > > If x(1) And &H80 Then q = True Else q = False
> > > For j = 1 To 16
> > > x(j) = (x(j) * 2) And &HFF
> > > If j < 16 Then
> > > If x(j + 1) And &H80 Then x(j) += 1
> > > Else
> > > If q Then x(j) += 1
> > > End If
> > > Next
> > >
> > > I need to shift shift all the bits in the array [x] 25 bits to the[/color][/color][/color]
left[color=blue][color=green][color=darkred]
> > > (circular) as quickly as possible.
> > >
> > > I don't "have" to have an array. I could use a 64 bit integer if[/color][/color]
> needed.[color=green][color=darkred]
> > >[/color]
> >
> >[/color]
>
>[/color]

**Jay B. Harlow [MVP - Outlook]** · Nov 20 '05, 10:13 AM

Re: faster shift left circular (rotate)

Doh!
Because "2 ^ 25" is a constant the compiler uses &h2000000 in the IL that is
created.

So in this example using ^ is ok.

Jay

"Jay B. Harlow [MVP - Outlook]" <Jay_Harlow_MVP @msn.com> wrote in message
news:uCujYGZyDH A.2304@TK2MSFTN GP12.phx.gbl...[color=blue]
> Brian,
> I would avoid both ^ & / in your example, as they involve floating point
> math...
>
> In addition to using the constant &h2000000 as you suggested I would
> recommend using integer division \ instead. This way floating point[/color]
numbers[color=blue]
> are avoided entirely!
>
> Hope this helps
> Jay
>
> "DumberThanSnot " <DumberThanSnot @nospam.com> wrote in message
> news:eJbka2YyDH A.2620@TK2MSFTN GP09.phx.gbl...[color=green]
> > if you don't "have" to have an array, then this might be what your[/color][/color]
looking[color=blue][color=green]
> > for using an integer.
> >
> > \\\\\
> > Dim iVal as Integer
> >
> > iVal = 234524523 ' bin = 0000 1101 1111 1010 1000 1111 0110 1011
> >
> > iVal = (iVal * 2) Xor ((iVal / 2 ^ 30) And 1)
> >
> > iVal = 469049046 ' bin = 0001 1011 1111 0101 0001 1110 1101 0110
> > /////
> >
> > you could replace the 2 ^ 30 with a 2 ^ 25 for your example. 2 ^ 25[/color][/color]
takes[color=blue][color=green]
> > more time for the computer to calculate, so I would replace the 2 ^ 25[/color]
> with[color=green]
> > &h2000000 for faster compute times.
> >
> > -brian
> >
> >
> > "Kenneth Lantrip" <vip01@mindspri ng.com> wrote in message
> > news:OKUoDtLyDH A.2556@TK2MSFTN GP10.phx.gbl...[color=darkred]
> > > Anyone got any ideas as to how this process could be improved for[/color][/color][/color]
speed?[color=blue][color=green][color=darkred]
> > >
> > > this is what I have...
> > >
> > > Dim j, q As Integer
> > > Dim x(16), y(16) As Byte
> > >
> > > [ not all code is shown ... only the relevant parts ]
> > >
> > > x.CopyTo(y, 0) ' shift left circular 24 bits
> > > For j = 0 To 15
> > > q = (j + 3) And 15
> > > x(j + 1) = y(q + 1)
> > > Next
> > > ' shift left circular 1 more bit
> > > If x(1) And &H80 Then q = True Else q = False
> > > For j = 1 To 16
> > > x(j) = (x(j) * 2) And &HFF
> > > If j < 16 Then
> > > If x(j + 1) And &H80 Then x(j) += 1
> > > Else
> > > If q Then x(j) += 1
> > > End If
> > > Next
> > >
> > > I need to shift shift all the bits in the array [x] 25 bits to the[/color][/color][/color]
left[color=blue][color=green][color=darkred]
> > > (circular) as quickly as possible.
> > >
> > > I don't "have" to have an array. I could use a 64 bit integer if[/color][/color]
> needed.[color=green][color=darkred]
> > >[/color]
> >
> >[/color]
>
>[/color]

**Jay B. Harlow [MVP - Outlook]** · Nov 20 '05, 10:13 AM

Re: faster shift left circular (rotate)

Kenneth,[color=blue]
> I see other great tips in your source too!![/color]

If you like System.Buffer you might be interested in System.BitConve rter
also.

Hope this helps
Jay

"Kenneth Lantrip" <vip01@mindspri ng.com> wrote in message
news:eNRo16YyDH A.2084@TK2MSFTN GP09.phx.gbl...[color=blue]
> Thanks Jay... It looks like I'll need to upgrade to 2003 pretty soon
> now. Cause I just love these shift bit operations... Coming from a C
> world and all! :)
>
> It still boggles the mind as to why they didn't think they'd need these
> since version .000001 pre-alpha-just-an-idea-stage???
>
> I see other great tips in your source too!!
>
> Many thanks Jay.
>
> Jay B. Harlow [MVP - Outlook] wrote:[color=green]
> > Kenneth,
> > Here's a VS.NET 2003 variation of my earlier post using Longs.
> >
> > Dim x(15) As Byte
> > Dim y(1) As Long
> > System.Buffer.B lockCopy(x, 0, y, 0, 16)
> >
> > Dim y2 As Long = y(1)
> >
> > y(1) = y(1) << 25 Or y(0) >> 64 - 25
> > y(0) = y(0) << 25 Or y2 >> 64 - 25
> >
> > System.Buffer.B lockCopy(y, 0, x, 0, 16)
> >
> > Hope this helps
> > Jay
> >
> > "Kenneth Lantrip" <bothersome@min dspring.com> wrote in message
> > news:s06fuvs0go ekcu40saovt552e vtqm9bvfe@4ax.c om...
> >[color=darkred]
> >>On Mon, 22 Dec 2003 12:43:07 -0600, Kenneth Lantrip
> >><vip01@mindsp ring.com> wrote:
> >>
> >>
> >>>Anyone got any ideas as to how this process could be improved for[/color][/color][/color]
speed?[color=blue][color=green][color=darkred]
> >>>
> >>>this is what I have...
> >>>
> >>> Dim j, q As Integer
> >>> Dim x(16), y(16) As Byte
> >>>
> >>>[ not all code is shown ... only the relevant parts ]
> >>>
> >>> x.CopyTo(y, 0) ' shift left circular 24 bits
> >>> For j = 0 To 15
> >>> q = (j + 3) And 15
> >>> x(j + 1) = y(q + 1)
> >>> Next
> >>> ' shift left circular 1 more bit
> >>> If x(1) And &H80 Then q = True Else q = False
> >>> For j = 1 To 16
> >>> x(j) = (x(j) * 2) And &HFF
> >>> If j < 16 Then
> >>> If x(j + 1) And &H80 Then x(j) += 1
> >>> Else
> >>> If q Then x(j) += 1
> >>> End If
> >>> Next
> >>>
> >>>I need to shift shift all the bits in the array [x] 25 bits to the left
> >>>(circular) as quickly as possible.
> >>>
> >>>I don't "have" to have an array. I could use a 64 bit integer if[/color][/color][/color]
needed.[color=blue][color=green][color=darkred]
> >>
> >>OK just to answer my own question... I have unrolled the loops and
> >>optimized just a little...
> >>
> >>dim x(16), y(4) in integer
> >>
> >> ' shift left circular 25 bits
> >> y(1) = x(1)
> >> y(2) = x(2)
> >> y(3) = x(3)
> >> y(4) = x(4)
> >> x(1) = (x(4) * 2 - ((x(5) And &H80) <> 0)) And &HFF
> >> x(2) = (x(5) * 2 - ((x(6) And &H80) <> 0)) And &HFF
> >> x(3) = (x(6) * 2 - ((x(7) And &H80) <> 0)) And &HFF
> >> x(4) = (x(7) * 2 - ((x(8) And &H80) <> 0)) And &HFF
> >> x(5) = (x(8) * 2 - ((x(9) And &H80) <> 0)) And &HFF
> >> x(6) = (x(9) * 2 - ((x(10) And &H80) <> 0)) And &HFF
> >> x(7) = (x(10) * 2 - ((x(11) And &H80) <> 0)) And &HFF
> >> x(8) = (x(11) * 2 - ((x(12) And &H80) <> 0)) And &HFF
> >> x(9) = (x(12) * 2 - ((x(13) And &H80) <> 0)) And &HFF
> >> x(10) = (x(13) * 2 - ((x(14) And &H80) <> 0)) And &HFF
> >> x(11) = (x(14) * 2 - ((x(15) And &H80) <> 0)) And &HFF
> >> x(12) = (x(15) * 2 - ((x(16) And &H80) <> 0)) And &HFF
> >> x(13) = (x(16) * 2 - ((y(1) And &H80) <> 0)) And &HFF
> >> x(14) = (y(1) * 2 - ((y(2) And &H80) <> 0)) And &HFF
> >> x(15) = (y(2) * 2 - ((y(3) And &H80) <> 0)) And &HFF
> >> x(16) = (y(3) * 2 - ((y(4) And &H80) <> 0)) And &HFF
> >>
> >>[/color]
> >
> >
> >[/color]
>[/color]

**Kenneth Lantrip** · Nov 20 '05, 10:15 AM

Re: faster shift left circular (rotate)

I'm not really following you on this... it look like you're rotating
what is in only one integer. I need to rotate 128 bits of data 25
bits to the left in a circular pattern. I see that you have rotated
an integer 1 bit circular. Doing that 25 times would be... Time
consuming.

Perhaps you ment something along...

iVal(x) = iVal(x) * &H2000000... . but I'm seeing a serious overflow
coming. :)

Jay has come up with the most elegant solution for VB.NET 2003 that
I've seen.

In case you're curios.. The program is just a play-thing that
searches IDEA encryption keys until it finds a certain pattern
encryped. Just for fun you understand... With my code for rotate in
place, I'm getting about 138000 keys tried per second. This is with
100% managed VB.NET code. I still need to "optimize" another routine
in the multiply algorithm. This running on an AMD 1.2GHz machine.

This same "test" proggie running from optimized C code on the same
machine, runs about 680000 keys per second. Does that sound about
right for native C compared to VB.NET?

Once I get all this set, I'm probably going to make my own light
saber. Just be safe. ;)

On Tue, 23 Dec 2003 11:47:32 -0800, "DumberThanSnot "
<DumberThanSnot @nospam.com> wrote:
[color=blue]
>if you don't "have" to have an array, then this might be what your looking
>for using an integer.
>
>\\\\\
>Dim iVal as Integer
>
>iVal = 234524523 ' bin = 0000 1101 1111 1010 1000 1111 0110 1011
>
>iVal = (iVal * 2) Xor ((iVal / 2 ^ 30) And 1)
>
>iVal = 469049046 ' bin = 0001 1011 1111 0101 0001 1110 1101 0110
>/////
>
>you could replace the 2 ^ 30 with a 2 ^ 25 for your example. 2 ^ 25 takes
>more time for the computer to calculate, so I would replace the 2 ^ 25 with
>&h2000000 for faster compute times.
>
>-brian
>
>
>"Kenneth Lantrip" <vip01@mindspri ng.com> wrote in message
>news:OKUoDtLyD HA.2556@TK2MSFT NGP10.phx.gbl.. .[color=green]
>> Anyone got any ideas as to how this process could be improved for speed?
>>
>> this is what I have...
>>
>> Dim j, q As Integer
>> Dim x(16), y(16) As Byte
>>
>> [ not all code is shown ... only the relevant parts ]
>>
>> x.CopyTo(y, 0) ' shift left circular 24 bits
>> For j = 0 To 15
>> q = (j + 3) And 15
>> x(j + 1) = y(q + 1)
>> Next
>> ' shift left circular 1 more bit
>> If x(1) And &H80 Then q = True Else q = False
>> For j = 1 To 16
>> x(j) = (x(j) * 2) And &HFF
>> If j < 16 Then
>> If x(j + 1) And &H80 Then x(j) += 1
>> Else
>> If q Then x(j) += 1
>> End If
>> Next
>>
>> I need to shift shift all the bits in the array [x] 25 bits to the left
>> (circular) as quickly as possible.
>>
>> I don't "have" to have an array. I could use a 64 bit integer if needed.
>>[/color]
>[/color]

faster shift left circular (rotate)

faster shift left circular (rotate)

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment