使用C语言SIMD内联函数实现无符号整数数组加法（进位处理疑问）

要解决大整数数组的SIMD加法进位问题，核心是处理块内的进位传递和块间的进位传递，以下是具体实现方案：

核心思路 #

1. 块内进位：一次处理4个uint32_t元素（SSE的128位寄存器刚好容纳4个32位值），计算元素相加的溢出进位，再将进位传递到高位元素。
2. 块间进位：每个块处理完成后，提取最高位元素的进位，作为下一个块的输入进位。
3. 剩余元素处理：数组长度不是4的倍数时，用标量处理剩余元素，确保进位传递完整。

完整实现代码 #

#include <emmintrin.h>
#include <stdint.h>

// 假设num1、num2是包含uint32_t数组的结构体，result_buf为结果数组，max_len为数组长度
typedef struct {
    uint32_t* num_arr;
} BigInt;

void bigint_add(const BigInt* num1, const BigInt* num2, uint32_t* result_buf, int max_len) {
    uint32_t carry = 0;
    int full_blocks = max_len / 4;
    int remaining = max_len % 4;

    // 处理完整的128位块（每块4个uint32_t）
    for (int i = 0; i < full_blocks * 4; i += 4) {
        // 加载未对齐的数组数据
        __m128i a = _mm_loadu_si128((__m128i_u*)&num1->num_arr[i]);
        __m128i b = _mm_loadu_si128((__m128i_u*)&num2->num_arr[i]);

        // 1. 计算初始无符号加法结果
        __m128i sum = _mm_add_epi32(a, b);

        // 2. 计算初始溢出进位：sum < a（无符号）说明a+b溢出，生成0xFFFFFFFF/0的mask
        __m128i carry_mask = _mm_cmplt_epu32(sum, a);
        __m128i carry_bits = _mm_srli_epi32(carry_mask, 31); // 转换为0或1的进位值

        // 3. 加入上一个块的输入进位
        if (carry != 0) {
            __m128i carry_in_vec = _mm_set_epi32(0, 0, 0, carry);
            sum = _mm_add_epi32(sum, carry_in_vec);
            // 更新第一个元素的进位（因输入进位可能导致溢出）
            __m128i cin_carry_mask = _mm_cmplt_epu32(sum, carry_in_vec);
            __m128i cin_carry_bits = _mm_srli_epi32(cin_carry_mask, 31);
            carry_bits = _mm_blendv_epi8(carry_bits, cin_carry_bits, _mm_set_epi32(0, 0, 0, 0xFFFFFFFF));
        }

        // 4. 传递进位到高位元素（第一次移位）
        __m128i carry_shifted = _mm_slli_si128(carry_bits, 4); // 左移4字节，将第n位进位传递到第n+1位
        sum = _mm_add_epi32(sum, carry_shifted);
        // 计算此次加法产生的新进位
        __m128i new_carry_mask = _mm_cmplt_epu32(sum, carry_shifted);
        __m128i new_carry_bits = _mm_srli_epi32(new_carry_mask, 31);

        // 5. 再次传递进位（处理第一次传递后的溢出）
        carry_shifted = _mm_slli_si128(new_carry_bits, 4);
        sum = _mm_add_epi32(sum, carry_shifted);
        // 计算最终进位，提取块的输出进位（最高位元素的进位）
        __m128i final_carry_mask = _mm_cmplt_epu32(sum, carry_shifted);
        __m128i final_carry_bits = _mm_srli_epi32(final_carry_mask, 31);
        carry = _mm_extract_epi32(final_carry_bits, 3);

        // 保存当前块的结果
        _mm_storeu_si128((__m128i*)&result_buf[i], sum);
    }

    // 处理剩余不足4个的元素（标量处理）
    for (int i = full_blocks * 4; i < max_len; i++) {
        uint64_t total = (uint64_t)num1->num_arr[i] + num2->num_arr[i] + carry;
        result_buf[i] = (uint32_t)total;
        carry = (total >> 32) & 1;
    }

    // 如果最后还有进位，说明结果多一位（需确保result_buf有足够空间）
    if (carry != 0) {
        result_buf[max_len] = carry;
    }
}

关键细节说明 #

• 无符号溢出判断：使用_mm_cmplt_epu32(sum, a)判断无符号加法溢出——当a + b超过UINT32_MAX时，sum会被截断为a + b - 2^32，此时sum必然小于a（无符号比较）。
• 进位传递：通过_mm_slli_si128将进位左移4字节（一个uint32_t的长度），实现将低位元素的进位传递到高位元素，重复两次确保所有进位都被处理。
• 对齐处理：使用_mm_loadu_si128和_mm_storeu_si128支持未对齐的数组，如果数组是16字节对齐的，可以替换为_mm_load_si128和_mm_store_si128提升性能。
• 数组顺序：假设数组的索引0对应大整数的最低32位（低位在前），如果你的数组是高位在前，需要反向循环处理。

内容的提问来源于stack exchange，提问作者Silent Tree