Vigenere (xor version) cipher
Who can improve it? On 1 core 2,8 Ghz it works with speed above 370 MB/s.
Is there any hints, to code it better?
Code:
Function Vigenere(ByRef input() As Byte, ByRef key() As Byte) As Byte()
Dim intKey As Integer = 0
Dim x As Integer = input.Length - 1
Dim x2 As Integer = key.Length
For i As Integer = 0 To x
If intKey = x2 Then
intKey = 0
End If
input(i) = input(i) Xor key(intKey)
intKey += 1
Next
End Function
My improvements to first version (much slower than this):
-'ByRef' instead of 'ByVal'
-for i as integer...(and if ... then) ended with variable (x or x2) instead of length calculating each time
-'if intKey = 0' statement to choose key from array is much faster than:
Code:
input(i) = input(i) Xor key(i mod key.Length)
Re: Vigenere (xor version) cipher
Maybe somebody can write it using pointers? It may be faster then...
Re: Vigenere (xor version) cipher
I know VB6 not net but have you tried
Code:
input(i) = input(i) Xor key(i mod x2)
It's more likely that the .length property is slow rather than Mod. If this was vb6 I could use a safearray hack to work the bytes as 32bit integers which should in theory be four times faster. I've also toyed with the idea of using the graphics card to Xor data using a bit block transfer with the Xor raster code, i.e. fool it into thinking input() is a bitmap. I don't know if it would be faster or not but I like the idea.
Re: Vigenere (xor version) cipher
Simple arithmetic and conditions are faster than function calls in terms of CPU register usage (think assembly). You can minimize incidence of increments followed by reset/overwrite to zero, or assign value just once per pass; a lot for long messages with short keys.
Code:
Function Vigenere(ByRef input() As Byte, ByRef key() As Byte) As Byte()
Dim intKey As Integer = 0
Dim x As Integer = input.Length - 1
Dim x2 As Integer = key.Length - 1
For i As Integer = 0 To x
input(i) = input(i) Xor key(intKey)
If intKey < x2 Then
intKey += 1
Else
intKey = 0
End If
Next
End Function
Re: Vigenere (xor version) cipher
Quote:
Originally Posted by Milk
I know VB6 not net but have you tried
Code:
input(i) = input(i) Xor key(i mod x2)
It's more likely that the .length property is slow rather than Mod. If this was vb6 I could use a safearray hack to work the bytes as 32bit integers which should in theory be four times faster. I've also toyed with the idea of using the graphics card to Xor data using a bit block transfer with the Xor raster code, i.e. fool it into thinking input() is a bitmap. I don't know if it would be faster or not but I like the idea.
As I wrote, I tried it.
Code:
input(i) = input(i) Xor key(i mod key.Length)
Mod is much slower in this case. (I found it, .length is as fast as variable... It's a bit strange, but true.)
Quote:
Originally Posted by leinad31
Simple arithmetic and conditions are faster than function calls in terms of CPU register usage (think assembly). You can minimize incidence of increments followed by reset/overwrite to zero, or assign value just once per pass; a lot for long messages with short keys.
Code:
Function Vigenere(ByRef input() As Byte, ByRef key() As Byte) As Byte()
Dim intKey As Integer = 0
Dim x As Integer = input.Length - 1
Dim x2 As Integer = key.Length - 1
For i As Integer = 0 To x
input(i) = input(i) Xor key(intKey)
If intKey < x2 Then
intKey += 1
Else
intKey = 0
End If
Next
End Function
Thanks for this hint, I'll try it today evening, and post comment here about results ;)
Re: Vigenere (xor version) cipher
Ok:
Code:
input(i) = input(i) Xor key(i mod x2)
Is slower 4x times.... Strange.
Re: Vigenere (xor version) cipher
Code:
Function Vigenere(ByRef input() As Byte, ByRef key() As Byte) As Byte()
Dim intKey As Integer = 0
Dim x As Integer = input.Length - 1
Dim x2 As Integer = key.Length - 2
For i As Integer = 0 To x
input(i) = input(i) Xor key(intKey)
If intKey > x2 Then
intKey = 0
Else
intKey += 1
End If
Next
End Function
Now, it's fastest one.
Re: Vigenere (xor version) cipher
Length isn't slow... for strings the length is stored before the string value (BSTR), for arrays the dimensions/boundaries are also stored before the array data. http://www.codeguru.com/vb/gen/vb_mi...cle.php/c7495/
You might want to try benchmarking working through the array in reverse.
Code:
Function Vigenere(ByRef input() As Byte, ByRef key() As Byte) As Byte()
Dim x As Integer = input.Length - 1
Dim x2 As Integer = key.Length
Dim intKey As Integer = x Mod x2
For i As Integer = x To 0 Step -1
input(i) = input(i) Xor key(intKey)
If intKey Then
intKey -= 1
Else
intKey = x2
End If
Next
End Function
Re: Vigenere (xor version) cipher
Quote:
Originally Posted by leinad31
Length isn't slow... for strings the length is stored before the string value (BSTR), for arrays the dimensions/boundaries are also stored before the array data.
I can't comment on .Net but in VB6 and below the total number of elements is stored, the element size is stored, and the lowerbound is stored. The upperbound is calculated as is the memory location of each element as it's referenced. As a rule with VB6 properties are slower than local variables so storing them locally if they are accessed often is quicker even if the property is just a memory lookup.
Mod is really slow compared to If n > m so I'm taking that one on board.
I still think if the 8 bit integer arrays could be coerced into 32 bit integer arrays the code will run 4x faster. (even with the DWord alignment issues)
I also would like to test a GDI bit block Xor transfer, although I think that could become complex.
Re: Vigenere (xor version) cipher
Quote:
Originally Posted by Milk
Mod is really slow compared to If n > m so I'm taking that one on board.
Yup. I'm glad I cam across this thread... it made me appreciate fact that we were made to learn assembly even with more advance languages around (this was several years ago, I don't think it's being taught anymore).
Re: Vigenere (xor version) cipher
Ivenesco.
This optimization question has really got me interested.
Ive created yet another DLL, this time in C, not C++/CLI. (So it cant be added as a reference, but its called like an API).
Perhaps it'll perform even better. If you're interested I can upload the entire project here.
Re: Vigenere (xor version) cipher
Off course, I'm interested ;) I'm writing my own version in c++, but due to my C++ knowledge (I'm beginner), and lack of time, it'll be finished in few days.
1 Attachment(s)
Re: Vigenere (xor version) cipher
Alright, here it is then.
(appears i didnt create a C file when writing this dll, so technically its a C++ dll :blush:, but anyhow..)
I hope it works well :thumb:
Re: Vigenere (xor version) cipher
Thanks, I'll change it to work with my application (C++ file and key read), and probably tomorow I'll post comment about efficiency.
Re: Vigenere (xor version) cipher
Ok, first test of new Vigenere (C++ version).
I expected a bit better result, but it's still much faster than VB.NET version: about 800 MB/s.
Thanks Atheist, I've used your code, to write new version.
If anybody can write it better, please post here code/hints.
Code:
Code:
void Vigenere(unsigned char input[], int nInput, unsigned char key[], int nKeys)
{
int intKey = 0;
int x = nInput - 1;
int x2 = nKeys - 2;
for(int i = 0; i <= x; i++)
{
input[i] ^= key[intKey];
if(intKey > x2)
{
intKey = 0;
}
else
{
intKey++;
}
}
}
Edit: Pointers didn't change anyting: (speed same as for arrays, but now more precisely) 830 MB/s.
Re: Vigenere (xor version) cipher
Quote:
Originally Posted by
Ivenesco
Who can improve it? On 1 core 2,8 Ghz it works with speed above 370 MB/s.
Is there any hints, to code it better?
Code:
Function Vigenere(ByRef input() As Byte, ByRef key() As Byte) As Byte()
Dim intKey As Integer = 0
Dim x As Integer = input.Length - 1
Dim x2 As Integer = key.Length
For i As Integer = 0 To x
If intKey = x2 Then
intKey = 0
End If
input(i) = input(i) Xor key(intKey)
intKey += 1
Next
End Function
My improvements to first version (much slower than this):
-'ByRef' instead of 'ByVal'
-for i as integer...(and if ... then) ended with variable (x or x2) instead of length calculating each time
-'if intKey = 0' statement to choose key from array is much faster than:
Code:
input(i) = input(i) Xor key(i mod key.Length)
Why just one character at a time? Does this go both directions?
I'm working on a different variation. Note the use of the word "working". No success yet.
Re: Vigenere (xor version) cipher
It's very old post, and I don't have this project, but If you will succeed with faster version, don't hesitate to post solution here ;-)