5 ms·

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.

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.

boomlinde 8y ago
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.
- giovannibajo1 8y ago
  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.
  - leni536 8y ago
    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 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.
    - giovannibajo1 8y ago
      Correct, gcc can generate "setc" but not "adc", AFAIK.
  - boomlinde 8y ago
    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.
- dchest 8y ago
  Careful with this: the default/fallback implementations are not constant-time.
  - wahern 8y ago
    They can be, though: https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/symcipher/poly1305_ctmul.c https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/symcipher...
  - boomlinde 8y ago
    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.

boomlinde 8y ago

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.

giovannibajo1 8y ago
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.
- leni536 8y ago
  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 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.
  - giovannibajo1 8y ago
    Correct, gcc can generate "setc" but not "adc", AFAIK.
- boomlinde 8y ago
  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.
dchest 8y ago
Careful with this: the default/fallback implementations are not constant-time.
- wahern 8y ago
  They can be, though: https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/symcipher/poly1305_ctmul.c https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/symcipher...
- boomlinde 8y ago
  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.