Bug in OpenCL bn_subb_word() macro

[mladenmarkov]

Hey

I'm using parts of the excellent OpenCL bn_* code in another project, and I believe I found a bug in the unsigned subtraction routine.

Subtracting the following numbers gives an incorrect result. 0x6142036f1b5d75c79466cc64fc3d6a0c5b - 0x5642036f1bb4ceb22d8ae3101cbbd8271b = 0bffffffffa8a71566dbe954df8191e540

Clearly, the correct answer is 0x0affffffffa8a71566dbe954df8191e540. The problem occurs when current words of the two terms are equal and there's a carry (borrow) from the previous pair of words. Then the current word becomes zero and there should be another borrow from the next word. The second borrow is missing.

This illustrates the subtraction and the problem:

  00000061 42036f1b 5d75c794 66cc64fc 3d6a0c5b
- 00000056 42036f1b b4ceb22d 8ae3101c bbd8271b
  --------------------------------------------
  0000000a ffffffff a8a71566 dbe954df 8191e540
                  ^borrow
         ^borrow (missing)

I have a fix in my copy of the code and it's working correctly with various tests. I can provide a pull request, if you want.

#define bn_subb_word_original(r, a, b, t, c) do {   \
        t = a - (b + c);            \
        c = (!(a) && c) ? 1 : 0;            \
        c |= (a < b) ? 1 : 0;           \
        r = t;                  \
    } while (0)

#define bn_subb_word(r, a, b, t, c) do {        \
        t = a - (b + c);            \
        c = ((!a | (a == b)) & c) ? 1 : 0;  \
        c |= (a < b) ? 1 : 0;           \
        r = t;                  \
    } while (0)

Cheers Mladen

[10gic]

Thank you for finding this problem, pull requests are welcome.