[C++] C++11 Signature Scanning

[DMichael]

Originally Posted by atom0s

Here is a benchmark of mine vs the original typical FindPattern you posted:

FindPattern Benchmark Example
(c) 2014 atom0s

================================================
Test Name   : FindPattern
Test Author : dom1n1k & Patrick (GameDeception)
Test Time   : 0.681074

================================================
Test Name   : FindPattern (C++11) w/ Async
Test Author : atom0s
Test Time   : 0.235662

In this benchmark app, I am scanning a total of 26 patterns. The way I have the benchmark setup is each test is given 3 functions:
- Initialize
- Release
- RunTest

Initialize is used to simply handle the basic stuff that the test may need to prepare itself for the test to be ran. Things that are not specific to the scanning directly. Such as any object creation and so on.
Release is to allow the test to cleanup anything it created etc.
RunTest is to allow the test to do its work to scan for all the signature in the given test data.

About The Tests
The test data is the Final Fantasy XI's main game file 'FFXiMain.dll'. I load the unpacked file into memory as the raw bytes, I do not actually load the game in any manner, so these are static scans from the files raw data.

Each test is given a total of 26 signatures to scan for within the same memory data.
So the benchmark is entirely fair in terms of what to look for and what it is looking within.

I created the C++11 / async method I use solely for this game and decided to share it since others may find it useful for faster and threaded scans. In an application where you only need to scan for a few signatures and do not need threading, then yeah mine may not be the best bet however, so far it has performed the best for me outside of some other methods I discussed on my personal site that a friend of mine (devnull) and I came up with.

There is definitely room for improvement and speed increases, this is just the fastest and cleanest method that devnull and I came up with so far that was easy to read and maintain while keeping speed and performance.

interesting conclusion but it not matter
is more about hardware and btw scanning speed won't be noticeable when the difference is measured only in millisecond
plus another thing is about compiler optimization which affects most on the speed(after hardware of course)

[mr.exodia]

Originally Posted by DMichael

interesting conclusion but it not matter

I don't agree with you here. Maybe it doesn't matter for searching a few MBs of data, but it will start to matter if you have to find 20 patterns in 2GB of data

[Carbon]

I think both your implementations are still not perfect. Think about this: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
or at least
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
This algorithm is even more efficient for byte search. Skip as many bytes as possible...

[atom0s]

Originally Posted by Carbon

I think both your implementations are still not perfect. Think about this: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
or at least
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
This algorithm is even more efficient for byte search. Skip as many bytes as possible...

Yeah there is a lot of room for improvement. My method was more aimed towards making use of C++11 features (to try them out and such) as well as being more maintainable as well as async which I needed for my project that I use it in.

Implementing Boyer Moore will definitely be a bit faster though.

Comparing my FindPattern to the original posted above, mine sees a lot of improvement when the data being scanned within is large and the number of scans being done is high. For low amounts of scanning and where async is not required, then the original will tend to outperform mine.

Overall it really depends on some specific factors:
- The data size being scanned within.
- The number of patterns being looked for.
- Threading; is it required or not, (along with thread-safety).
- Hardware can land up playing a roll as well etc.

Another implementation that could make use of different hardware would be a GPU implementation, which could also have a handful of speed benefits depending on similar factors above.

[Nukem]

Originally Posted by atom0s

Yeah there is a lot of room for improvement. My method was more aimed towards making use of C++11 features (to try them out and such) as well as being more maintainable as well as async which I needed for my project that I use it in.

Implementing Boyer Moore will definitely be a bit faster though.

Actually a couple of those methods have been tested here: https://github.com/learn-more/findpattern-bench

BMH was second place when I checked (57ms):

FindPattern benchmark
Page size: 4096, allocating 22 pages (including 2 guard pages).
Running tests on 9 different implementations
===========
Running M-i-K-e
ran outside the area
FAILED
===========
Running Trippeh
Finding pattern 0 x 1000 took 1774.23 ms.
Finding pattern 1 x 1000 took 1905.49 ms.
===========
Running Trippeh v2
Finding pattern 0 x 1000 took 81.864 ms.
Finding pattern 1 x 1000 took 81.937 ms.
===========
Running Trippeh v3
Failed, cheating with the pattern length!
FAILED
===========
Running learn_more
Finding pattern 0 x 1000 took 204.665 ms.
Finding pattern 1 x 1000 took 164.068 ms.
===========
Running learn_more v2
Finding pattern 0 x 1000 took 82.226 ms.
Finding pattern 1 x 1000 took 82.679 ms.
===========
Running afffsdd
Finding pattern 0 x 1000 took 40.943 ms.
Finding pattern 1 x 1000 took 40.968 ms.
===========
Running DarthTon
Finding pattern 0 x 1000 took 56.974 ms.
Finding pattern 1 x 1000 took 57.045 ms.
===========
Running kokole
Finding pattern 0 x 1000 took 122.41 ms.
Finding pattern 1 x 1000 took 122.646 ms.
Done.
Press any key to continue . . .

Although it really does depend on what you're scanning/how long it is. I prefer a linear search because the code is shorter and it's still pretty fast.