Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 14 Jul 2011 21:40:57 +0400
From: Solar Designer <>
Subject: Re: Some thoughts on hard to compute hashes


On Fri, Jul 01, 2011 at 06:36:11PM -0400, Anthony Ferrara wrote:
> For i = 0 ... N - 1
>     j <-- Integerify(x) mod N
>     If j > (N / B)
>         X <-- H(X xor V_j)
>     Elseif j > (N / 2B)
>         V_i <-- H(X xor V_j)
>     Elseif j > (N / 4B)
>         V_j <-- H(X xor V_i)
>     Else
>         X <-- H(X xor V_i)

In your example, the branching may be avoided by turning the "j > (N / B)",
etc. comparison results into all-zero and all-ones bitmasks (which is
trivial to do without branching), then applying those in expressions on
X, V_j, V_i variables.  H() is then invoked from just one place,
unconditionally.  Its output is similarly put into the right variable or
memory location using several expressions involving ANDs with the
bitmasks.  So all of X, V_i, and V_j are written to, but only one of
those writes actually changes the value at the target location.

Here's another example of a branching algorithm turned into non-branching:

So it'll take some more effort to make branch-avoidance costly - e.g.,
you could use very different H() functions in different cases, so a
branch-less implementation would have to compute each of them, whereas a
branching one would compute just one needed for the current iteration.
In that variation of your example, you'd achieve a 4x slowdown for a GPU
that has to avoid branching.


Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.