CRC32 - Fastest Implementation Available VB6

[vbaddicts]

The implementation I have written achieves its speed through use of x86 assembly code. In fact, the entire implementation of the CRC32 algorithm is written in assembly.

I use assembly via some tricks involving class modules and the object's vtable. I allocate a block of memory, write the machine code to the memory, then rewrite the functions vtable entry to point to my block of code.

It is roughly 25x faster than the current "fastest" implementation found on pscode.con that gets its speed through asm assisted bitshifting (which was written by me too) and probably 100x to 150x faster than a pure VB approach.

The project and code file(s) can be found here:
http://www27.brinkster.com/wsckvbupdates/CRC32.zip

P.S. because it is hosted on a free web server, you might have to copy the link and manually paste it rather than clicking on it.
Also, look forward to more hashing algorithms, encryptions, and etc to be written in asm taylored for use with vb6 to be released in the future!

[Joacim Andersson]

I've had a look through your code and to be honest I'm not very impressed. I don't understand how you came up with the numbers of being 25x faster than anything else, how did you messure that? I messured your code against CRC32 web service calculator and your code was only slightly faster after I compiled it, and that is comparing to some code available on the Net where network traffic is involved.

I don't understand how you can think that reading binary data from a resource file and changing the vtable before you can even start the execution of calculation wouldn't take much longer than to just start doing the CRC32 calculation against the data directly.

The assembly doesn't seem to be optimized either. How do you know that that code is better than the code the VB compiler can create?

I do find your code interesting though, as a way to inject compiled assembly to a VB project so please don't take my earlier criticism to harshly I only doubt your telemetry data when it comes to the speed gain.

[dilettante]

"Injection" techniques don't usually work due to DEP which tries to protect against such things. This can also trigger malware alerts - antivirus software looks for such things because it is so often used nefariously.

A safer alternative might be to just create a C or assembler DLL and call that, or look at tools like ThunderVB.

[vbaddicts]

Joacim Andersson: sorry if I might have brought any confusion about this... i simply meant to state this is the fastest implementation of CRC32 in VB6 without the use of a third party dll/api written in another language. Also, you state that it is only slightly faster than some website that returns the result. You have to keep in mind, in order for me to get a time in ms I have to execute the CRC32 hash 10,000 times. So, basically in 15ms I can execute my CRC32 routine 10,000 times and its still faster than executing a CRC32 on a webserver one time. So, one operation of my CRC32 on the data "Hello World!" takes ~ 15ms/10,000 or 0.0015ms per operation! So, I would have to say 0.0015ms, or if converted from milliseconds to seconds it would be fifteen ten-millionths of a second, per hash, that is pretty damn fast for being in VB6 and not using a third party dll/api?

I don't understand how you can think that reading binary data from a resource file and changing the vtable before you can even start the execution of calculation wouldn't take much longer than to just start doing the CRC32 calculation against the data directly.

Answer: The vtable redirection and reading data from the resource file is only done on class_initialization, so its only done ONCE. Every call to the function is routed to the assembly code that is located in memory because the vtable contains the pointer already (which was done on class_initialize). So, its just as fast as calling the function normally. If that makes sense to you?

So, to finish my point, Joacim Andersson you stated that you looked over my code, but to be honest I think you skimmed over it at best. If you had looked over it and truely understood most of it then maybe you wouldn't have made these statements which were honestly wrong. Like you don't take my criticism to harshly , but your criticism is based on something you loosely understood and maybe thats my fault for not making my claim of speed more precise when I meant it was 25x to 100x faster than any other VB6 implementation. But, your claim about it only being slightly faster than some website's calculator is totally wrong, but I've already touched on that above.

However, it is indeed faster than the code outputted by the vb6 compiler. As far as optimizing goes, I did optimize it some... if you check out the CRC32_GENERATE_TABLE routine you will see that I unrolled the loop instead of writing a for loop in assembly. Also I tried my best to keep every operation contained to the general purpose registers and not use the stack or heap, but can it be optimized a little more? Sure it can!

dilettante: As far a DEP goes, you're correct in that DEP is designed to prevent such things. However, I'm not too worried about that as DEP is mostly implemented on newer 64-bit operating systems and VB6 is designed to run on a 32-bit processor. As far as it being 'detected' by anti-virus software, I highly doubt this because it is not using any apis that would cause any alarms to go off. RtlMoveMemory is what i'm using and because it only allows moving data from one local address to another local address then antivirus software doesn't care. It's looking for things such as CreateRemoteThread, WriteProcessMemory, OpenThread, SetWindowsHookEx, etc... etc..

[dilettante]

As far a DEP goes, you're correct in that DEP is designed to prevent such things. However, I'm not too worried about that as DEP is mostly implemented on newer 64-bit operating systems and VB6 is designed to run on a 32-bit processor.

Really? Well DEP is alive and active on my 5 year old 32-bit development system (see screen shot).

In general it is far better to avoid anything that might trigger antivirus software. Since we have "legitimate" techniques available to us there is really no need to resort to self-modifying code anyway.

But I'm a bit curious what kind of software needs to calculate CRC32s much anyway, or for that matter needs to checksum so much data that a straight VB6 function isn't fast enough.

[vbaddicts]

dilettante, notice how mostly is bolded but thats besides the point... you two seem to really be trying to find and point out flaws with this. As to why? I dunno? I just wrote it to be the fastest out there for visual basic 6, by no means did I say it was better or safer than any other method or that you had to use it. So instead of pointing out problems you have personally with the code, go do something useful

Also, I do have to agree with you that ThunderVB is probably a safer alternative as the asm code you write is compiled and linked in directly, but thats a whole different approach. I chose this one and i did so because it required no third-party add-in on my part. And look forward to more algorithms written in asm taylored for vb using this method in the future. I'm currently working on an MD5 implementation.

[wqweto]

But I'm a bit curious what kind of software needs to calculate CRC32s much anyway, or for that matter needs to checksum so much data that a straight VB6 function isn't fast enough.

Actually recently refactored an unzipping class and noticed that calculating CRC32 reduced speed a lot (probably in half). That's when I decided to skip it altogether with a conditional compilation option.

Unfortunately OP code is too bloated to be easily plugged in my skinny class. I doubt that he can beat a for cycle and a XOR for brevity

For lIdx = 0 To lSize - 1
    lOutputCrc32 = (((lOutputCrc32 And &HFFFFFF00) \ &H100) And &HFFFFFF) Xor (m_lCrc32Table((lOutputCrc32 And &HFF) Xor uCtx.baInStream(lOffset + lIdx)))
Next

cheers,
</wqw>

[vbaddicts]

For lIdx = 0 To lSize - 1
    lOutputCrc32 = (((lOutputCrc32 And &HFFFFFF00) \ &H100) And &HFFFFFF) Xor (m_lCrc32Table((lOutputCrc32 And &HFF) Xor uCtx.baInStream(lOffset + lIdx)))
Next

If this is the code you are referring to that you DOUBT my code can beat, then you're wrong. I would be willing to bet a lot of money that mine still executes faster than that, but only because of how vb compiles that to native code and its heavy use of the vbruntime. My class may LOOK bloated, but in fact the code that actually performs the CRC calculation is quite compact compared to what VB would spit out.

[Joacim Andersson]

because of how vb compiles that to native code and its heavy use of the vbruntime

Native code and vbruntime doesn't really go together. Yes, the run-time libraries are needed even when compiled to native code but that's because all the VB intrinsic controls are located there. The run-time is never used for a for loop and a math equation when compiled to native code.

[vbaddicts]

The run-time is never used for a for loop and a math equation when compiled to native code.

lol, you are SOOO wrong here. Maybe even the most basic for loop that does nothing still has one or two calls to the run-time. And a for loop like the one you showed iwth that math equation definantely uses the run-time, probably atleast 6-8 calls per iteration.

that's because all the VB intrinsic controls are located there

Well, i hate to tell you but the vb runtime is used a lot more than you think. Every call to Mid, InStr, Len, Abs, Cos, Sin, Chr, Asc, Hex$, etc is a call to the vb runtime. You call CStr, CLng, CByte, VarPtr, StrPtr, LngPtr, etc that's a call the vb runtime. Also there are many other calls to the vb runtime like calls to check the hresult of a call to a method located in an object (class or form, etc). There is a call to the vbruntime when errors occur, there is a call to the vbruntime to keep track of variables on the stack. lots and lots and lots of calls to the vbruntime! Even the most basic function makes a couple calls.

[Joacim Andersson]

I'm sorry but it's you that is wrong. If you compile to native code the runtime is not used for a simple for loop since the for loop is compiled to native code! But you're correct that the functions you mention also exist in the runtime library but we are not talking about those, we are talking about a loop and a math expression. When compiled to native code those are in fact compiled to native code, what else do you think native code means?

Also stack and heap memory management is not controlled by the run-time after you've compiled to native code. They are assign to the process by Windows. You can also remove the integer overflow check and the code will run even faster.

[Joacim Andersson]

I created this simple VB6 application that produces nothing but contains a loop and some simple math expression.

Public Sub Main()
    Dim i As Integer
    Dim x As Integer
    
    For i = 0 To 10
        x = x + i
    Next
End Sub

After I compiled this to native code and decompiled the exe I got this result:

  loc_00401540: xor ecx, ecx
  loc_00401542: xor eax, eax
  loc_00401544: add ecx, eax
  loc_00401546: inc eax
  loc_00401547: cmp ax, 000Ah
  loc_0040154B: jle 401544h
  loc_0040154D: ret

As you can see there is no call to the vb-runtime. The whole loop is compiled to native code, and the stack in this case is simply the eax and ecx registers.

[vbaddicts]

Right, thats probably one of the few instances when your for loop doesn't use the vb runtime

here is almost identical code that uses the runtime:

Public Sub Form_Load()
    Dim i As Integer
    Dim x As Integer
    
    For i = 0 To 10
        x = x ^ i
    Next
End Sub

and here is the asm code

.text:00401939 loc_401939:                             ; CODE XREF: .text:00401973j
.text:00401939                 movsx   ecx, si
.text:0040193C                 mov     [ebp-30h], ecx
.text:0040193F                 fild    dword ptr [ebp-30h]
.text:00401942                 fstp    qword ptr [ebp-38h]
.text:00401945                 mov     edx, [ebp-34h]
.text:00401948                 mov     ecx, [ebp-38h]
.text:0040194B                 push    edx
.text:0040194C                 push    ecx
.text:0040194D                 movsx   edx, ax
.text:00401950                 mov     [ebp-3Ch], edx
.text:00401953                 fild    dword ptr [ebp-3Ch]
.text:00401956                 fstp    qword ptr [ebp-44h]
.text:00401959                 mov     eax, [ebp-40h]
.text:0040195C                 mov     ecx, [ebp-44h]
.text:0040195F                 push    eax
.text:00401960                 push    ecx
.text:00401961                 call    ds:__vbaPowerR8 <-- runtime
.text:00401967                 call    edi ; __vbaFpI2  <-- runtime
.text:00401969                 add     si, 1
.text:0040196D                 jo      short loc_40199B
.text:0040196F                 cmp     si, 0Ah
.text:00401973                 jle     short loc_401939

see how bloated that code is, and its a simple for loop with x = x ^ i. most for loops are going to do more than simple math operations though. so an average for loop, like i said, is going to make atleast 6-8 calls to the vbruntime.

[dilettante]

Unlike C or assembler, where you can use the hardware "power" operator hmm?

Note to anyone wandering in here later: That was sarcasm. There is no "power" operator and you normally perform this operation by calling a library no matter what language you use.

[Joacim Andersson]

When would you need a "to the power of" calculation for a CRC32 checksum?

[vbaddicts]

That was just an example of how the vbruntime is used in a for loop, but I can show you many more if you would like. The point i'm trying to make is generally speaking vb code is bloated and thats what makes my code so fast. It is not bloated and it doesn't rely on the vbruntime. I'm done discussing this topic because were going no where and arguing over trivial stuff.

Joacim Andersson: you wouldn't need it for crc32.