Hi Tjerk,
On Mon, Feb 10, 2014 at 7:36 PM, Tjerk Meesters <[email protected]>wrote:
> I've given this problem some more thought and the following looked
> promising; it would be great to get your feedback on it.
>
> Basically, to remove the modulo and MAX(), I've used a combined buffer
> that's used for the comparison, in two ways:
>
> 1. PAD := known (padded with \0 based on given_len)
> 2. PAD := known CONCAT given
>
> The comparison is straightforward because we already know the buffer is at
> least given_len.
>
> Implementations of above can be found here:
> 1. https://github.com/datibbaw/php-src/compare/master...const-cmp
> 2. https://github.com/datibbaw/php-src/compare/master...const-cmp-2
>
> Bottom line is that this attempts to compromise memory against time
> stability.
>
I think length leak does not matter much.
Therefore, I may ignore length leak as it could know it from other codes
using strlen(), etc.
Our main concern would be performance.
https://github.com/yohgaki/php-src/compare/PHP-5.6-rfc-hash-compare
and the bench mark result of
https://gist.github.com/yohgaki/ede544f290c6cf9fa90d
is
[yohgaki@dev github-php-src]$ ./php-bin t.php
str_siphash_compare Elapsed: 9.450211 Iterations: 1000000 DataSize: 1024
str_xxhash32_compare Elapsed: 3.849933 Iterations: 1000000 DataSize: 1024
str_md5_compare Elapsed: 27.174614 Iterations: 1000000 DataSize: 1024
str_byte_compare Elapsed: 5.874092 Iterations: 1000000 DataSize: 1024
str_byte_compare2 Elapsed: 8.761152 Iterations: 1000000 DataSize: 1024
str_word_compare Elapsed: 1.867914 Iterations: 1000000 DataSize: 1024
str_compare Elapsed: 1.178738 Iterations: 1000000 DataSize: 1024
I had the same idea, but I didn't try as it requires additional memory
allocation.
str_byte_compare Elapsed: 5.874092 Iterations: 1000000 DataSize: 1024
str_byte_compare2 Elapsed: 8.761152 Iterations: 1000000 DataSize: 1024
1st one is simple byte by byte XOR, 2nd one is using modulo as original
patch
proposed. There is obvious difference even with additional modulo.
str_compare Elapsed: 1.178738 Iterations: 1000000 DataSize: 1024
This is the result of simple strncmp() as a reference.
How well your version perform compare to simple strncmp?
Regards,
--
Yasuo Ohgaki
[email protected]