Hacker News Reader

Comment by zimmerfrei | Hacker News Reader

One reason this cannot be translated into a portable C version while retaining its compactness (and readability) is the lack of support for carry/borrow chains.

In Go, bits.Add64 takes as input and returns the carry.

In C, there are some constructs that modern compilers will recognize as patterns people use to extract the carry, but it is a hit-and-miss.

Even compiler-specific intrinsics are a few and far between, inefficient or even broken.

View on HN

If you look into the implementations of Add64/Sub64/Mul64 you'll see that it's not a lot of code and that there is nothing magical about them. They can just as easily be implemented in C in some 30 lines of code. Because they concern unsigned integers only there is no UB to consider on overflow/carry.

Actually, those functions are intrinsics in the Go compiler on many platforms, so the compiler generates a single ADD / ADC opcode. The source code that you see is a fallback for backends that have not implemented them as intrinsics yet.

gcc can optimize generic code for a carry check. To be fair both clang and msvc fails to optimize this specific case.

https://godbolt.org/z/6WXfnL

Edit: OK, I have much worse time generating "adc" instructions, and only gcc sees the opportunity to emit "setc" where appropriate. I see the issue now.

Correct, gcc can generate "setc" but not "adc", AFAIK.

That's true, but I'm specifically addressing the compactness and readability concern.

With respect to efficiency and particularly timing, Go and C seems to be in the same boat here in that depending on your compiler and platform it may either compile to a constant time chain of add/adc equivalent instructions or something sub-optimal and branchy.

Careful with this: the default/fallback implementations are not constant-time.

Not intuitively, but it's generally good to be wary of optimizing compilers in such cases. I don't know what the Go compiler outputs, but a straight forward translation to C didn't compile to a constant time operation with (recent) gcc -O3. For all I know might with some other compiler. This didn't result in any branches in gcc, though:

    static uint64_t
    add64(uint64_t x, uint64_t y, uint64_t *carry)
    {
     uint64_t yc, sum;
     yc = y + *carry;
     sum = x + yc;
     *carry = (sum < x || yc < y);
     return sum;
    }

But again, some other compiler on some other platform may have another idea of what to output.

Anyway I agree to be careful. On platforms that have to use the fallback implementations, if they aren't optimized to constant time operations, this will lose one of the important properties of Poly1305.

They can be, though: https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/symcipher...

Reply on news.ycombinator.com