xor bytes

[Maven]

I was playing around a day or two ago with an xor encryption..... I had a small need to a faster way of doing it, so I went to an asm dll.

I didn't paste everything here, only whats needed. Can you make it better?



SAFEARRAYBOUND struct
cElements DWORD ? ; Number of Elements
lLbound DWORD ? ; Lower Boundary
SAFEARRAYBOUND ends

OLE_SAFEARRAY struct
cDims WORD ? ; Number of dimensions
fFeatures WORD ? ; Bitfield indicating attributes
cbElements DWORD ? ; size of an element of the array
cLocks DWORD ? ; lock counter 0=Locked
pvData DWORD ? ; Pointer to data
rgsabound SAFEARRAYBOUND <> ; Contains info for dimensions
OLE_SAFEARRAY ends




xorbytes proc msg:DWORD, key:DWORD
push ebx
push esi
push edi
push ebp

mov eax, msg
mov ebx, key
movd MM0, esp

mov edx, [eax]
mov ecx, [ebx]

mov ebp, (OLE_SAFEARRAY ptr [edx]).rgsabound.cElements
mov ebx, (OLE_SAFEARRAY ptr [ecx]).rgsabound.cElements
mov edi, (OLE_SAFEARRAY ptr [edx]).pvData
mov esi, (OLE_SAFEARRAY ptr [ecx]).pvData

cmp ebp, 0
je done

cmp ebx, 0
je done

xor ecx, ecx

mov esp, esi
add esp, ebx

jmp For_Loop

SetKeyBack:
sub esi, ebx
jmp lblCon

align 16
For_Loop:
cmp esi, esp
je SetKeyBack

lblCon:

mov al, [esi]
xor byte ptr [edi], al

add edi, 1
add esi, 1
add ecx, 1
cmp ecx, ebp
jne For_Loop

done:
movd esp, MM0
pop ebp
pop edi
pop esi
pop ebx
ret
xorbytes endp

[Maven]

this is the basic algorithm that I converted:

For i = 1 To Len(Message)
plainchar = Asc(Mid(Message, i, 1))
pk = Asc(Mid(key, (i Mod Len(key) + 1), 1))
buffer = buffer & Chr(plainchar Xor pk)
Next i

The only difference is that I got rid of the need for "MOD" (divisons are very epensive and I always try like hell to get rid of them) and buffer as the one in asm just xors the message that is passed to it.

[nkad]

Thats good stuff. I wish I knew ASM. I bought a book but didn't get to far.

Just looking at that code makes you appreciate the greatness of high level languages.

[Maven]

Thats good stuff. I wish I knew ASM. I bought a book but didn't get to far.

Just looking at that code makes you appreciate the greatness of high level languages.

It makes you thankful for all that code it saves you from typing. I must say though, I miss the power of asm in high level languages.

[tailz]

The first comparison in the for loop (cmp esi, esp), can you find an alternative to that?

As you know, comparisons are expensive and to do one for every byte of the message/key may be slowing it down.... still, you must have a massive improvement over that hideous piece of VB code (that Im sure could also be improved)

[Maven]

The first comparison in the for loop (cmp esi, esp), can you find an alternative to that?

As you know, comparisons are expensive and to do one for every byte of the message/key may be slowing it down.... still, you must have a massive improvement over that hideous piece of VB code (that Im sure could also be improved)

Compare instructions aren't too bad on my processor (p4):
Clocks : 0.334644

Anyway it's a lot cheaper then multiply wich is like 18 clock cycles and divide which is like 29 clock cycles.

[Maven]

Here is the latest version.


xorbytes proc msg:DWORD, key:DWORD
.data

align 4
lblPtr dd L0, L1, L2, L3
keyPtr dd 0
keysize dd 0
counter dd 0

.code

push ebx
push esi
push edi
push ebp

mov ebx, msg ; Message Array
mov edx, key ; Key Array

mov eax, [ebx] ; reference Message Array
mov ecx, [edx] ; reference Key Array

mov ebx, (OLE_SAFEARRAY ptr [ecx]).rgsabound.cElements
mov esi, (OLE_SAFEARRAY ptr [ecx]).pvData
mov ebp, (OLE_SAFEARRAY ptr [eax]).rgsabound.cElements
mov edi, (OLE_SAFEARRAY ptr [eax]).pvData

; -------------------------------------------------------------------------
; EBX = Len of Key
; ESI = Pointer to key data.
; EBP = Len of msg
; EDI = Pointer to msg data.
; -------------------------------------------------------------------------
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

mov keyPtr, esi
mov keysize, ebx

cmp ebx, 4
jb singlebyte ; If keysize < 4 then load by single bytes only.


xor edx, edx ; Clear edx for unsigned divison.
mov eax, ebp ; Copy msgsize into eax
div ebx ; Divide by keysize.

push edx ; Save remainder

mov ebp, eax ; ebp = number of times to loop through message


mov ecx, ebx
shr ecx, 2 ; Shift right 2 places (keeps it 4 byte alinged)
mov eax, ecx
shl eax, 2
sub ebx, eax ; Remainder bytes (Odd bytes)

mov counter, ecx ; Save counter.

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

Loop1:
jmp dword ptr [lblPtr + ebx * 4] ; Jump Table, will jump instantly to the correct label.

L1: ; 1 odd Byte.
mov al, byte ptr [esi]
xor byte ptr [edi], al
add esi, 1
add edi, 1
jmp L0

L2: ; 2 odd bytes
mov ax, word ptr [esi]
xor word ptr [edi], ax
add esi, 2
add edi, 2
jmp L0

L3: ;3 odd bytes
mov ax, word ptr [esi]
mov dl, byte ptr [esi+2]
xor word ptr [edi], ax
xor byte ptr [edi+2], dl
add esi, 3
add edi, 3

L0: ; Aligned by 4
mov eax, DWORD PTR [esi]
xor DWORD PTR [edi], eax
add esi, 4
add edi, 4
sub ecx, 1
jnz L0

mov ecx, counter ; Count used for L0 loop.
mov esi, keyPtr ; Move to start pos of the key.

sub ebp, 1
jnz Loop1
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

pop ebp ; Number of bytes left in msg to xor.

cmp ebp, 0 ; If none then goto done.
je done

mov ebx, keysize ; Move keysize into ebx.

singlebyte:
xor ecx, ecx ; Clear ecx (used for counter).
sub ebx, 1
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

looper:

mov al, byte ptr [esi+ecx] ; Load key byte.
xor byte ptr [edi], al ; xor msg byte with key byte and save.
add edi, 1 ; Point to next byte in msg.

cmp ecx, ebx ; if counter = keysize then
jne S1

xor ecx, ecx

jmp S2

S1: ;else
add ecx, 1 ; add 1 to counter.

S2:
sub ebp, 1
jnz looper

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

done:
xor eax, eax ; Clear Return
pop ebp ; Restore Registers
pop edi
pop esi
pop ebx

ret ; Exit Function
xorbytes endp

[Merri]

I had to optimize the VB version:


'for comparison:
' For i = 1 To Len(Message)
' plainchar = Asc(Mid(Message, i, 1))
' pk = Asc(Mid(key, (i Mod Len(key) + 1), 1))
' buffer = buffer & Chr(plainchar Xor pk)
' Next i

Public Function XorEncode(ByVal strMessage As String, ByVal strKey As String) As String
Dim bArrMessage() As Byte, bArrKey() As Byte, bArrOutput() As Byte
Dim msgSize As Long, keySize As Long
Dim I As Long

'convert strings to byte arrays
bArrMessage = strMessage
bArrKey = strKey

msgSize = UBound(bArrMessage) 'upper bound
keySize = LenB(strKey) 'actual size (due to the way used with Mod)

'prepare output buffer
ReDim bArrOutput(msgSize)

'without Unicode string support (step by two)
For I = 0 To msgSize Step 2
'simple Xor based on given key
bArrOutput(I) = bArrMessage(I) Xor bArrKey(I Mod keySize)
Next I

'convert byte array to string
XorEncode = bArrOutput
End Function


I don't know how well this can be compared to the ASM version, but shouldn't be too bad (considering it has to do string conversions, taking that functionality out and working with pure byte arrays would make it superb).


To make this faster:
- use SafeArray trick
- with a small trick, you can get rid of extra math required to use Mod, and so result in less overall math

[Merri]

And here is the one with the later trick:


Public Function XorEncode2(ByVal strMessage As String, ByVal strKey As String) As String
Dim bArrMessage() As Byte, bArrKey() As Byte, bArrOutput() As Byte
Dim msgSize As Long, keySize As Long
Dim I As Long, A As Long, B As Byte

'convert strings to byte arrays
bArrMessage = strMessage
bArrKey = strKey

msgSize = UBound(bArrMessage) 'upper bound
keySize = LenB(strKey) 'actual size (due to the way used with Mod)

'prepare output buffer
ReDim bArrOutput(msgSize)

'without Unicode string support (step by two)
For A = 0 To keySize - 1 Step 2
B = bArrKey(A)
For I = A To msgSize Step keySize
bArrOutput(I) = bArrMessage(I) Xor B
Next I
Next A

'convert byte array to string
XorEncode2 = bArrOutput
End Function



Comparison on my machine (compiled, all advanced optimizations) with 100 000 iterations:
- XorEncode: 320 ms
- XorEncode2: 275 ms
- just the string conversion stuff, reserving of memory and function call: 260 ms


Note I really had a long pause between coding it, I did it because I had nothing better to do at the time :D


Another note for those who might come and claim using For...Next loops are slower than Do loops: in this case and use, For loops are slightly faster. No major speed difference can be gained using Do loops instead.

Edit Simplified it a bit while the speed remained the same.
Edit Slight optimization, increase in overall speed by 10ms.

[Maven]

And here is the one with the later trick:


Public Function XorEncode2(ByVal strMessage As String, ByVal strKey As String) As String
Dim bArrMessage() As Byte, bArrKey() As Byte, bArrOutput() As Byte
Dim msgSize As Long, keySize As Long
Dim I As Long, A As Long, B As Byte

'convert strings to byte arrays
bArrMessage = strMessage
bArrKey = strKey

msgSize = UBound(bArrMessage) 'upper bound
keySize = LenB(strKey) 'actual size (due to the way used with Mod)

'prepare output buffer
ReDim bArrOutput(msgSize)

'without Unicode string support (step by two)
For A = 0 To keySize - 1 Step 2
B = bArrKey(A)
For I = A To msgSize Step keySize
bArrOutput(I) = bArrMessage(I) Xor B
Next I
Next A

'convert byte array to string
XorEncode2 = bArrOutput
End Function



Comparison on my machine (compiled, all advanced optimizations) with 100 000 iterations:
- XorEncode: 320 ms
- XorEncode2: 275 ms
- just the string conversion stuff, reserving of memory and function call: 260 ms


Note I really had a long pause between coding it, I did it because I had nothing better to do at the time :D


Another note for those who might come and claim using For...Next loops are slower than Do loops: in this case and use, For loops are slightly faster. No major speed difference can be gained using Do loops instead.

Edit Simplified it a bit while the speed remained the same.
Edit Slight optimization, increase in overall speed by 10ms.


right now I'm doing 1,000,001 iterations at:

90-130

Reason for such a big difference is because I don't have the algorithm testing for miss-aligned data. So its running 90 on aligned bytes and 130 on unalinged. =/ You get kicked in the balls if you don't align your data when loading 4 bytes at a time.

I also need to get it running in Parallel. Get another nice little speed boast doing that. Definitely need to get rid of that 2nd loop.

Anyway we'll be some xoring mofo's if I ever get that done. Setting up the loop to do all that is the trouble.

[Maven]

I'm growing board with this so this will be the final version. I've attached the source and exe's.


xorbytes proc msg:DWORD, key:DWORD
.data
align 4
byte_4_counter dd 0

.code

push ebx
push esi
push edi
push ebp

mov ebx, msg ; Message Array
mov edx, key ; Key Array

mov eax, [ebx] ; reference Message Array
mov ecx, [edx] ; reference Key Array

mov ebx, (OLE_SAFEARRAY ptr [ecx]).rgsabound.cElements
mov esi, (OLE_SAFEARRAY ptr [ecx]).pvData
mov ebp, (OLE_SAFEARRAY ptr [eax]).rgsabound.cElements
mov edi, (OLE_SAFEARRAY ptr [eax]).pvData

; -------------------------------------------------------------------------
; EBX = Len of Key
; ESI = Pointer to key data.
; EBP = Len of msg
; EDI = Pointer to msg data.
; -------------------------------------------------------------------------
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

xor edx, edx ; Clear Edx
mov eax, ebp ; Set eax to size of msg
div ebx ; Divide by keysize

sub ebp, edx ; Minus odd bytes
push edx ; Save Remainder (Odd bytes).

mov eax, ebx ; Move eax len of key
shr eax, 2 ; Divide by 4
mov byte_4_counter, eax ; Save how many times to load by 4
shl eax, 2 ; shift it back
mov ecx, ebx
sub ecx, eax ; Subtract
xor edx, edx

; -------------------------------------------------------------------------
; Ecx now has the odd byte count for our key
; -------------------------------------------------------------------------


cmp ecx, 0 ; If no odd bytes
je byte_4

cmp ecx, 2 ; If 2 odd bytes
je byte_2

cmp ecx, 3 ; if 3 odd bytes
je byte_3



; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

; -------------------------------------------------------------------------
; XOR ONE BYTE AT A TIME.
; -------------------------------------------------------------------------

byte_1:
xor ecx, ecx ; Clear counter
movzx eax, byte ptr [esi] ; Load the key char into al
L1:
xor byte ptr [edi+ecx], al ; Xor msg by key char
add ecx, ebx ; add keysize to msg
cmp ecx, ebp
jb L1
mov edx, 1
jmp byte_4


; -------------------------------------------------------------------------
; XOR TWO BYTES AT A TIME.
; -------------------------------------------------------------------------

byte_2:
xor ecx, ecx ; Clear Counter
mov dx, word ptr [esi]

L2:
xor word ptr [edi+ecx], dx ; Xor msg by key charecters


add ecx, ebx ; add keysize to counter
cmp ecx, ebp ; if ecx >= msg then goto byte_4
jb L2
mov edx, 2
jmp byte_4

; -------------------------------------------------------------------------
; XOR THREE BYTES AT A TIME.
; -------------------------------------------------------------------------

byte_3:
xor ecx, ecx ; Clear Counter
mov ax, word ptr [esi] ; Load 2 bytes into ax
mov dl, byte ptr [esi+2] ; load 1 byte into dl
L3:
xor word ptr [edi+ecx], ax ; xor 3 bytes
xor byte ptr [edi+ecx+2], dl
add ecx, ebx
cmp ecx, ebp ; if ecx >= msg then goto byte_4
jb L3
mov edx, 3
; -------------------------------------------------------------------------
; XOR FOUR BYTES AT A TIME.
; -------------------------------------------------------------------------
byte_4:
mov ecx, byte_4_counter ; Get number of times to load by 4.
cmp ecx, 0 ; If 0 then jump to byte_8
je PassTwo

L4:
mov ecx, edx ; Clear Ecx
mov eax, dword ptr [esi+edx] ; load 4 bytes

L5:
xor dword ptr [edi+ecx], eax ; xor 4 bytes of msg.
add ecx, ebx ; add keysize to ecx
cmp ecx, ebp
jb L5

add edx, 4

sub byte_4_counter, 1 ; For each load of 4 bytes, loop.
jnz L4
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

PassTwo:

pop edx ; Get odd bytes in message
cmp edx, 0 ; If none then we are finished.
je done



;comment * -----------------------------------------------------

oddbytes:
mov al, byte ptr [esi] ; Load key byte.
add esi, 1
xor byte ptr [edi+ebp], al ; xor msg byte with key byte and save.
add ebp, 1 ; Point to next byte in msg.
sub edx, 1
jnz oddbytes

;------------------------------------------------------- *

done:
xor eax, eax
pop ebp
pop edi
pop esi
pop ebx
ret
xorbytes endp

[Merri]

Just for comparison between VB6 and ASM performance (though it is still possible to optimize the VB6 code but I'm too lazy to do it).

I made them as comparable as possible, working just about the same way, removed a sub call from the faster VB one (because calling a sub in VB costs too much time in benchmarking).

VB one is about two times slower.

[Maven]

Just for comparison between VB6 and ASM performance (though it is still possible to optimize the VB6 code but I'm too lazy to do it).

I made them as comparable as possible, working just about the same way, removed a sub call from the faster VB one (because calling a sub in VB costs too much time in benchmarking).

VB one is about two times slower.

You have to convert mine to asci first.

IE:

tmpMsg = StrConv(MAINMSG, vbFromUnicode)
tmpKey = StrConv(MAINKEYWORD, vbFromUnicode)



You'll notice that as you increase the message size, the difference between the vb code and the asm code gets larger.


Just leave everything like it is and set the msg to that quote and you'll see the difference.

[Merri]

Uh, but that's not optimal at all! Doing the extra StrConv just uses extra processing power for nothing. You can actually run it in the Unicode insanely fast (as you can see from the test). No need to use slow StrConv beforehand.

The thing is, the pure VB code is still pretty fast, considering how much extra coding you had to do just to make it do that simple thing. Also, there is no need for an extra DLL (which most people prefer to avoid while making their application). And the one side being, you have to be sure you're making something compatible with all processors while coding in ASM.

I'd understand this if you were making it for something that processes several megabytes of data and you'd need to do it fast. Since you are doing only simple XOR, which pretty much everyone with some knowledge can crack, I see no real point in your project except the possibility to learn ASM.

My general point being here is that you can code fast enough code with VB. I mostly wanted to do the optimized VB code after seeing you were comparing ASM to the String-mode VB6 code with Asc and Mid, which with just one call is slower than calling the ASM code million times... :)

[Maven]

Uh, but that's not optimal at all! Doing the extra StrConv just uses extra processing power for nothing. You can actually run it in the Unicode insanely fast (as you can see from the test). No need to use slow StrConv beforehand.

The thing is, the pure VB code is still pretty fast, considering how much extra coding you had to do just to make it do that simple thing. Also, there is no need for an extra DLL (which most people prefer to avoid while making their application). And the one side being, you have to be sure you're making something compatible with all processors while coding in ASM.

I'd understand this if you were making it for something that processes several megabytes of data and you'd need to do it fast. Since you are doing only simple XOR, which pretty much everyone with some knowledge can crack, I see no real point in your project except the possibility to learn ASM.

My general point being here is that you can code fast enough code with VB. I mostly wanted to do the optimized VB code after seeing you were comparing ASM to the String-mode VB6 code with Asc and Mid, which with just one call is slower than calling the ASM code million times... :)

I wanted to work with it in ascii for a reason actually. When using it with other ciphers you can't have the unicde in there or you would open your message up to a freq attack. Eventually I'd like to create a set of high speed crypto functions. But that I'm afraid is a long ways off. I can program in asm but I can't completely bend it to my will as of yet. There is a whole bunch of stuff you have to know in order to really optimizing the living daylights out of code. You have to worry about latency, cpu cache, memory and code alignment, register dependencies, and various other things. Anyway I've seen people who are great at it take a good c algorithm and just simply smoke it. Eventually I wanna be able to do that lol.

Well it's not really all that much code honestly, you have to remember that ASM is a one to one with machine language. As far as dlls goes, I never did have a problem using them. As long as you don't modify the interface to the dll, you don't even have to re-compile your program.

You have processor directives that keep up with what processor your code will run on. .386 for example, will run on any 32 bit processor. It's when you start using special instructions that you have to test for processors. Examples would be: MMX, SSE, SSE2, SSE3, and 3DNow, etc.

I completely dissagree about visual basic being fast enough. Ask any user in the world, it's never fast enough.

[Merri]

Actually, I just asked on IRC and everyone said something similar to "yes, Visual Basic is fast enough" :) Of course it depends on what you're doing, but on most needs, VB really is enough. And VB6 isn't running all that slow compared to C/C++ as the compiler of VB6 is a hacked C/C++ compiler... :)

[Maven]

Actually, I just asked on IRC and everyone said something similar to "yes, Visual Basic is fast enough" :) Of course it depends on what you're doing, but on most needs, VB really is enough. And VB6 isn't running all that slow compared to C/C++ as the compiler of VB6 is a hacked C/C++ compiler... :)

What irc channel do you hang out in?

I think many people get too hung up in a language. Languages solve different needs and one should always gard against being too conservative in their choices of languages.

Visual basic and C++ works quite a bit differently. In C++ you are responsable for a lot more then what you are in visual basic. That and a very long history of optimization by many people other then microsoft are what make C and C++ so much faster then visual basic. The same is going to be true for the .net enviroment according to Microsoft.

Speed isn't a virtue you look for in visual basic. What you do look for is how easy it is to use. When you're programming in visual basic, you really don't have any worries. Just about every single aspect of visual basic is point and click. I think some visual basic programmer would be shocked to find out how much visual basic actually does for you. That is the best thing about visual basic though and I think microsoft did a great job at it. So if I was going to say visual basic solves a need, I would say it solves the need to do some programming work quickly and easily.

If you want to do a major application though, visual basic isn't really enough.