Best performance addition modulo 2^32 implemetation

1

I'm working on SHA-256 implementation and I got to the point where addition modulo 2^32 of unsigned numbers is needed.

My first thought was to use an overflow behavior:

uint32_t a = ...;
uint32_t b = ...;
uint32_t c = a + b;

But I have two concerns:

  • Is overflow always defined behavior and if I can rely that it will work as modulo addition sizeof(_operand_) if both operands and result variable are of the same type?
  • How to get rid of compiler warnings about possible overflow, the proper way?

My second thought was to implement it using variable of longer type:

uint32_t a = ...;
uint32_t b = ...;
uint64_t a_64 = a;
uint64_t b_64 = b;
uint64_t c_64 = a_64 + b_64;
uint32_t c = uint32_t(c_64 & 0xFFFFFFFF);

But this solution needs several additional variables, their initialization and additional bitwise AND operation.

Which of these implementations (if any) is correct in terms of C programming principles and performance? If none of them, what is the proper implementation?

c
performance
modulo
addition
asked on Stack Overflow Oct 7, 2018 by elklepo

1 Answer

1

uint32_t is a modulo-2^32 type. It is not only a type with range at least up to 2^32-1, but maybe more per hardware requirements; that would be uint32least_t.

So, addition on uint32_t is always modulo addition, and it is not suitable for operations where a concept of overflow is desired. The best solution is simply a+b.

answered on Stack Overflow Oct 7, 2018 by Potatoswatter

User contributions licensed under CC BY-SA 3.0