You're talking about a different method than the one I proposed. I don't know where you got it from, but yes, it does suffer a gross performance degradation when there are initial wildcards in a signature.
The method I'm describing doesn't check against initial wildcards to determine whether to do a full signature check. It only checks against the first non-wildcard character of a signature, not just the first character regardless. My method never uses a wildcard character to determine if we should examine the whole signature. This gives fewer or no false positives, while also maintaining the speed advantage of not checking every signature in it's entirety.
If we have the signature {-1, 'f', 'o', 'o'}, my method requires that we also specify the first non-wildcard character, which exists at offset 1 in the signature. The very rough pseudo code looks like this:
Notice that this code allows for initial wild cards by ensuring that the first character matched ('f') is not at offset 0 in the data, but is at least at offset 1. It only calls check_full_signature if it matched a specific, non-wildcard character.Code:signature = {-1, 'f', 'o', 'o'}; first_non_wild_card = 1; // this can and should be precomputed for (i = 0; i < data_length - signature_length; i++) // match data[1] to signature[1], an 'f', not a wildcard if (data[i + first_non_wild_card] == signature[first_non_wild_card]) check_full_signature(&data[i], signature)
Furthermore, my original proposal, in post #12 doesn't even use explicit wildcard items in the signature. Thus, it would be impossible for that method to use a wildcard match to determine whether to do a full signature check. It simply checks that the mandatory bytes exist with the right gaps between them. It would only check the full signature if it had good cause, being a matching byte in an appropriate place. Heck, that method will be noticeably faster than yours if there are large chunks of wildcards in a signature, because I don't check wildcard bytes individually, I just skip over them.
I am done arguing this point. I am content that my method runs with the same or better time complexity as yours while providing more accurate matching.
