Re:There are no good constant-time data structures
by tedunangst on Tuesday December 02, 2014 @09:31PM
(#8691556)
This is very similar to the algorithm OpenBSD uses in timingsafe_memcmp().
http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string...
Re:There are no good constant-time data structures
by pbsd on Tuesday December 02, 2014 @10:09PM
(#8691686)
Indeed. The two main differences are that I didn't care about returning {-1, 0, 1} to emulate `memcmp`, and that I don't rely on implementation-defined behavior (signed shifts being arithmetic).
Re:There are no good constant-time data structures
by mirabilos on Wednesday December 03, 2014 @04:46AM
(#8692765)
Right-shift of signed integer values is implementation-defined behaviour though. If (x - y) is unsigned, the comments are wrong, they would return 1, not -1.
Re:There are no good constant-time data structures
by pbsd on Wednesday December 03, 2014 @11:46AM
(#8694716)
The `-` is there to turn 1 into -1 (mod 2^n), and 0 into 0. I use `- (x >> (sizeof(x)*8-1))` to get arithmetic shift semantics while only using unsigned arithmetic.
Re:There are no good constant-time data structures
by DannyBee on Tuesday December 02, 2014 @07:31PM
(#8691117)
Why not just use xor instead of "or + subtraction" in your "ne" function.
Re:There are no good constant-time data structures
by pbsd on Tuesday December 02, 2014 @07:40PM
(#8691143)
I'm not sure I understand what you're suggesting. x ^ y will obviously never be 0 when x != y, but there is no quick way to locate where they differ to turn it into a mask. When x != y, either x - y or y - x will be negative and therefore have the MSB set.
The following should be constant-time relatively to the contents of its inputs: