What operation does the function perform?

问题:

int function(uint32_t *r, const uint32_t *a, const uint32_t *b, int n)
{
 int i;
 uint32_t ri, c=0;
 for (i = 0; i < n; i ++)
 {
   ri = a[i] + b[i] + c;
   c = ((ri < a[i]) || ((ri == a[i]) && c));
   r[i] = ri;
 }
   return ((int) c);
}

The C function given below has four arguments: r, a, and b are pointers to arrays of type uint32_t. The integer n specifies the length of these arrays (i.e. all three arrays contain the same number of elements). The return value is of type int. Can anyone could help me to understand the operation performed by this function?

回答1:

It is performing multi-precision addition with carry propagation. The a and b arguments are pointers to multi-precision integers with n digits each. In this case, the digits are 32-bits. The least-significant digits are in the lowest array indices.

The inputs are added, and the result is placed into the array pointed to by r (also containing n 32-bit digits). It works by adding a digit from a to a digit from b with the carry-in c, which is initialized to zero. A carry out is detected when the resulting digit is less than one of the input digits, or is equal to one of the digits when the carry-in is 1. The return value is the carry-out from the whole operation.

Imagine we are adding with base-10 digits. If we compute 9+9+0 mod 10, we get 8. Since 8 is less than 9, we infer that there must have been a carry-out. If we compute 9+9+1 modulo 10, we get 9; we infer a carry-out because the carry-in was set. If we compute 9+0+0, we get 9, but there was no carry-out because carry-in was 0.

回答2:

Over each element of the loop, a temporary variable stores the sum of two corresponding elements in a and b, and adds 1 if a flag is set. Then the flag is set when the result is less than the element in a, and reset if it is greater. This result is stored in a new array. Obviously, we can see that the result is less (greater) than the element in a if b[i] + c < 0 (>). However, both indices must be positive; if the sum of the three addends total less than one of them, then there's a wraparound. The variable c, therefore, holds whether the addition overflowed, and it is equivalent to carrying a 1 to the next pair of elements. Therefore, this function adds the arbitrary-precision unsigned numbers a and b (represented as little-endian arrays), copies the result to r, and returns whether an overflow exists.