大整數算法系列（六）：絕對值加法核心實現——雙精度暫存器技巧與跨平台移植宏設計

多精度加法：高效能大整數庫的基石運算

絕對值加法 z = |x| + |y| 是有符號加減法、乘法、模運算的核心構建塊。本文深入剖析 bn_add_abs 的演算法邏輯、雙精度暫存器進位技巧、單/雙精度平台統一宏設計、邊界條件處理與 O(n) 複雜度優化。

演算法核心邏輯

1. 對齊：決定較長/較短操作數，max = max(used_x, used_y), min = min(...)
2. 擴容：結果 z 需 max + 1 數位 (最高位可能進位)
3. 主迴圈：i = 0 .. min-1 逐位相加 + 進位傳遞
4. 尾迴圈：i = min .. max-1 僅傳遞進位至較長操作數剩餘位
5. 最終進位：寫入 z->dp[max]
6. 清理：高位歸零、sign=1、bn_clamp 修正 used

關鍵技術：雙精度暫存器消除分支

32 位系統 (bn_digit=uint32, bn_udbl=uint64) 下，兩數位相加最大值：

(2³²-1) + (2³²-1) + 1(進位) = 2³³-1 < 2⁶⁴

完整放入 64-bit 暫存器，無需分支判斷進位：

// 有雙精度型別平台 (x86_64, ARM64, 32-bit with uint64_t)
#define ADDC_INIT   bn_udbl rr = 0;
#define ADDC_CORE   rr += (bn_udbl)*px + *py; \
                    *pz = (bn_digit)(rr & BN_MASK0); \
                    rr >>= biL;
#define ADDC_FINAL  rr += (bn_udbl)tmp->dp[i]; \
                    *pz = (bn_digit)(rr & BN_MASK0); \
                    rr >>= biL;
#define ADDC_STOP   z->dp[max] = (bn_digit)(rr & BN_MASK0);

BN_MASK0 = 0xFFFFFFFF (32-bit) 或 0xFFFFFFFFFFFFFFFF (64-bit)。rr 低 32 位 = 本位結果，高 32 位 = 進位。

單精度平台退化實現 (無 uint64_t，如某些 16-bit MCU 或嚴格 C89)

利用無符號溢位特性：(a + b) < a 當且僅當產生進位 (C 標準保證無符號環繞)。

// 僅有單精度型別平台
#define ADDC_INIT   bn_digit rr, t, c = 0;
#define ADDC_CORE   t = *px; \
                    t = (t + c) & BN_MASK0; \
                    c = (t < c); \
                    rr = (t + *py) & BN_MASK0; \
                    c += (rr < t); \
                    *pz = rr;
#define ADDC_FINAL  t = tmp->dp[i]; \
                    t = (t + c) & BN_MASK0; \
                    c = (t < c); \
                    *pz = t;
#define ADDC_STOP   z->dp[max] = c;

兩次加法各自檢測進位，c 累積 (0, 1, 或 2)，最終進位 ≤ 1。

完整 bn_add_abs 實現

int bn_add_abs(bignum *z, const bignum *x, const bignum *y) {
    int ret;
    const bignum *tmp;
    size_t i, max, min, olduse;
    bn_digit *px, *py, *pz;

    if (x->used > y->used) { max = x->used; min = y->used; tmp = x; }
    else { max = y->used; min = x->used; tmp = y; }

    olduse = z->used;
    z->used = max + 1;
    BN_CHECK(bn_grow(z, z->used));

    px = x->dp; py = y->dp; pz = z->dp;

    ADDC_INIT
    for (i = 0; i < min; i++) {
        ADDC_CORE
        px++; py++; pz++;
    }
    if (min != max) {
        for (; i < max; i++) {
            ADDC_FINAL
            pz++;
        }
    }
    ADDC_STOP

    for (i = z->used; i < olduse; i++) *pz++ = 0;
    z->sign = 1;
    bn_clamp(z);
    return ret;
}

關鍵細節與避坑

1. BN_CHECK 宏統一錯誤處理：if ((ret = x) != 0) goto clean;，clean: 標籤釋放臨時變數
2. bn_grow 內部 memcpy 保留舊資料，memset 新增區域歸零
3. bn_clamp 從高位向低掃描首個非零數位，修正 used，去除前導零
4. used = 0 代表數值 0，sign 強制 = 1

效能優化方向

• 展開迴圈：手動/編譯器 #pragma unroll 減少迴圈開銷
• SIMD 並行：VPADDQ (AVX2) 4×64-bit 並行加法 + 進位傳遞 (需橫向掃描)
• 蒙哥馬利形式：預先轉換至 Montgomery domain，加法合併模約減
• 快速路徑：min == 0 直接複製；x == y 左移 1 位 (乘 2)

測試向量驗證

絕對值加法是大整數運算的「心跳」，其效能直接決定 RSA、ECC、DH 等公開金鑰密碼運算的速度上限。掌握雙精度暫存器技巧、單雙精度統一宏架構、邊界條件嚴謹處理，是打造高效能、可移植多精度庫的關鍵功力。下一篇將介紹絕對值減法：借位傳遞、負數結果處理、比較-減法合併優化。