大整數算法（1）：數據結構定義與核心約定

大整數庫基石：類型定義、bignum 結構與工程約定

工欲善其事，必先利其器。本文確立大整數庫的數據類型體系、核心結構 bignum、參數傳遞規範、錯誤處理機制，為後續所有算法奠定堅實基礎。

基礎數據類型定義（跨平台）

// 編譯器相關類型別名
#ifdef _MSC_VER
    typedef __int8 int8;      typedef __int16 int16;
    typedef __int32 int32;    typedef __int64 int64;
    typedef unsigned __int8  uint8;  typedef unsigned __int16 uint16;
    typedef unsigned __int32 uint32; typedef unsigned __int64 uint64;
#else
    typedef signed char int8;       typedef signed short int16;
    typedef signed int int32;       typedef signed long long int64;
    typedef unsigned char uint8;    typedef unsigned short uint16;
    typedef unsigned int uint32;    typedef unsigned long long uint64;
#endif

// 布爾類型
typedef uint8 boolean;
#define TRUE  1
#define FALSE 0

大整數核心類型：單精度與雙精度

typedef uint32 bn_digit;   // 單精度數位，32 位系統對應 32 位，即 2^32 進制
typedef uint64 bn_udbl;    // 雙精度，用於乘法中間結果，32 位系統為 64 位

// 移植輔助宏
#define ciL  (sizeof(bn_digit))      // 每數位字節數 (4)
#define biL  (ciL << 3)              // 每數位比特數 (32)
#define biLH (ciL << 2)              // 半數位比特數 (16)，模運算用
#define BN_MALLOC malloc
#define BN_FREE   free

設計考量： 64 位系統下 bn_digit 為 64 位（2^64 進制），此時 bn_udbl 無定義，需擴展為 128 位或改用其他策略。

bignum 結構體定義

typedef struct {
    int sign;           // 符號：1 非負，-1 負
    size_t alloc;       // 已分配數位容量（上限 BN_MAX_LIMB）
    size_t used;        // 實際使用數位數（高位無前導零）
    bn_digit *dp;       // 數位數組指針，LSB 低地址在前（小端序）
} bignum;

有效 bignum 狀態規則（不變量）

1. alloc >= 0，dp == NULL 或指向有效內存。
2. 0 <= used <= alloc。
3. used > 0 時 dp[used-1] != 0（無前導零）；dp[used...alloc-1] == 0。
4. used == 0 時 sign == 1（零值非負），dp 可為 NULL 或指向已歸零內存。

這些規則簡化了算法邊界判斷，保證操作安全。

參數傳遞約定：輸出參數在前

// c = a + b
int bn_add_bn(bignum *c, const bignum *a, const bignum *b);
// 返回 0 成功，非 0 錯誤碼

所有二元運算遵循 結果 = 操作數1 操作 操作數2 形式，便於鏈式調用與閱讀。

錯誤碼體系

#define BN_MEMORY_ALLOCATE_FAIL  -0x0001
#define BN_EXCEED_MAX_LIMB       -0x0002
#define BN_EXCEED_MAX_BITS       -0x0003
#define BN_NEGATIVE_VALUE_ERROR  -0x0004
#define BN_INVALID_INPUT         -0x0005
#define BN_DIVISION_BY_ZERO      -0x0006
#define BN_BUFFER_TOO_SMALL      -0x0007
#define BN_READ_FILE_ERROR       -0x0008
#define BN_WRITE_FILE_ERROR      -0x0009
#define BN_NO_MODULAR_INVERSE    -0x000A

統一負數編碼，便於 if (ret != 0) 判斷。

錯誤檢查宏：BN_CHECK

#define BN_CHECK(x)  if ((ret = (x)) != 0) { goto clean; }

標準函數模板：

int bn_function(bignum *b, const bignum *a) {
    int ret;
    bignum tmp;
    bn_init(&tmp);
    BN_CHECK(bn_sub_step(&tmp, a, b));
    // ... 核心邏輯 ...
clean:
    bn_free(&tmp);
    return ret;
}

為何用 goto？ 統一清理臨時變量內存，避免多處重複 bn_free，在 C 語言無 RAII 情況下是經典且安全的模式。

數位上限常量

#define BN_MAX_LIMB 25600  // 32位系統下約 819200 bits，遠超 RSA 4096 需求