Salsa20 Implementation: Sum of 2 Words with Carries Suppressed

Question

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.

Answer 1

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 2³², the leftmost carry, if there is one, is always suppressed (there isn't space for a 33^rd bit).