Лучшая производительность сложения по модулю 2 ^ 32 реализации - PullRequest
Новая
       9

Лучшая производительность сложения по модулю 2 ^ 32 реализации

0 голосов
/ 08 октября 2018

Я работаю над реализацией SHA-256 и дошел до того, что требуется сложение по модулю 2^32 чисел без знака.

Моей первой мыслью было использование поведения переполнения: 

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

Но у меня есть две проблемы:

  • Является ли переполнение всегда определяемым поведением, и если я могу полагать, что оно будет работать как сложение по модулю sizeof(_operand_), если оба операнда и переменная результата имеют одинаковыетип?
  • Как правильно избавиться от предупреждений компилятора о возможном переполнении?

Моя вторая мысль состояла в том, чтобы реализовать его, используя переменную более длинного типа: 

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);

Но для этого решения требуется несколько дополнительных переменных, их инициализация и дополнительная побитовая операция AND.

Какая из этих реализаций (если таковая имеется) верна с точки зрения C принципов программирования и производительности?Если ни один из них, какова правильная реализация?

1 Ответ

0 голосов
/ 08 октября 2018

uint32_t - это тип по модулю 2 ^ 32.Это не только тип с диапазоном, по крайней мере, до 2 ^ 32-1, но, возможно, больше в зависимости от требований к оборудованию;это было бы uint32least_t.

Таким образом, добавление к uint32_t всегда является сложением по модулю, и оно не подходит для операций, где требуется концепция переполнения.Лучшее решение - просто a+b.

...