4
$\begingroup$

I'm working on the 2nd part of the Salsa20 spec, and I want to implement a closure for the exclusive-or of two words(u32). The author defines the operation as the sum of two words with carries suppressed, but what does "carries suppressed" mean. Then I come across some summation notation:

$u=\sum_i2^iu_i$

What does the variable "i" mean in this context exactly? I understand summation notation and the index variable, but the context of the spec doesn't elaborate enough for me to know what "i" indexes.

I realize this all may be very rudimentary, but I am a programmer first.

$\endgroup$
  • 2
    $\begingroup$ $$\bigoplus{}$$ $\endgroup$ – kelalaka Feb 27 at 16:43
10
$\begingroup$

The sum of two words with carries suppressed is just a convoluted way of saying XOR. You don't need to implement any kind of complicated summation operation. Just perform a bitwise-exclusive OR.


If you're performing modular addition, just like with paper-and-pen mathematics, you need to use carries. When adding binary, you're doing the same, but each digit is taken modulo 2 instead of modulo 10.

  1 1   ⟵ carries
0 0 0 1
0 0 1 1 +
⸻⸻
0 1 0 0

We see that decimal 1 (binary 0001) added to decimal 3 (binary 0011) equals decimal 4 (binary 0100). That is, 1 + 3 = 4. So, what happens if we drop the carries, i.e. perform carryless addition in binary?

0 0 0 1
0 0 1 1 ⊕
⸻⸻
0 0 1 0

This is the same as decimal 1 XORed with decimal 3, and the result is decimal 2 (0010)! So 1 ⊕ 3 = 2. Salsa20 does the same thing, but with 32-bit words instead of 4-bit words. Because the addition is done modulo 232, the leftmost carry, if there is one, is always suppressed (there isn't space for a 33rd bit).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.