Vigenere (xor version) cipher

[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?

 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:

input(i) = input(i) Xor key(i mod key.Length)

[Ivenesco]

Maybe somebody can write it using pointers? It may be faster then...

[Milk]

I know VB6 not net but have you tried

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.

[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.

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

[Ivenesco]

I know VB6 not net but have you tried

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.

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.)

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.

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

[Ivenesco]

Ok:

input(i) = input(i) Xor key(i mod x2)

Is slower 4x times.... Strange.

[Ivenesco]

    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.

[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. http://www.codeguru.com/vb/gen/vb_mi...cle.php/c7495/

You might want to try benchmarking working through the array in reverse.

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

[Milk]

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.

[leinad31]

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).

[Atheist]

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.

[Ivenesco]

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.

[Atheist]

Alright, here it is then.
(appears i didnt create a C file when writing this dll, so technically its a C++ dll , but anyhow..)

I hope it works well

[Ivenesco]

Thanks, I'll change it to work with my application (C++ file and key read), and probably tomorow I'll post comment about efficiency.

[Ivenesco]

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:

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.

[storm5510]

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?

 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:

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.

[Ivenesco]

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 ;-)