faster shift left circular (rotate)

  • Thread starter Thread starter Kenneth Lantrip
  • Start date Start date
K

Kenneth Lantrip

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.
 
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.
Click to expand...

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
 
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 said:
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.
Click to expand...

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
Click to expand...
 
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.BlockCopy(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.BlockCopy(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.BlockCopy(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.BlockCopy(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 said:
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.
Click to expand...

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
Click to expand...
 
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.BlockCopy(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.BlockCopy(y, 0, x, 0, 16)

Hope this helps
Jay

Kenneth Lantrip said:
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.
Click to expand...

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
Click to expand...
 
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
 
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.
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.BlockCopy(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.BlockCopy(y, 0, x, 0, 16)

Hope this helps
Jay

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.
Click to expand...

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
Click to expand...
Click to expand...
 
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 said:
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 said:
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.
Click to expand...
Click to expand...
 
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 said:
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 said:
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 said:
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.
Click to expand...
Click to expand...
Click to expand...
 
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 said:
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 said:
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 said:
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.
Click to expand...
Click to expand...
Click to expand...
 
Kenneth,
I see other great tips in your source too!!
Click to expand...

If you like System.Buffer you might be interested in System.BitConverter
also.

Hope this helps
Jay

Kenneth Lantrip said:
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.
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.BlockCopy(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.BlockCopy(y, 0, x, 0, 16)

Hope this helps
Jay

On Mon, 22 Dec 2003 12:43:07 -0600, Kenneth Lantrip


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.

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
Click to expand...
Click to expand...
Click to expand...
 
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. ;)


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 said:
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.
Click to expand...
Click to expand...
 
Back
Top