上一篇博文簡單介紹了大整數的表示方法，這次開始介紹一些基本的算法。
★ 初始化和清除
編寫大整數函數的出發點是bignum結構的初始化和清除，在其他大部分算法當中，這兩個算法都會用到。
對於給定的bignum結構，初始化有兩種情況：一是僅僅把bignum結構的dp指向NULL，二是初始化的時候順便分配一定的動態內存，並讓dp指針指向這塊內存。其實我本來打算只用第二種方式進行初始化，不過考慮到初始內存可能分配過多導致內存浪費，於是決定兩種方式一起使用。第一種方式的優點是在後面編程中你不必考慮到底要預先分配多少內存，內存分配的工作交給bn_grow函數去做，減少了工作量，不過它的缺陷也比較明顯，如果一開始的內存分配過少，在後面可能需要多次的內存分配來增加精度，效率降低，要知道堆上面的操作還是挺費時間的。
如果bignum結構中的dp指針已經被初始化（NULL或者是指向某一分配好的內存），就必須對結構的其他成員進行初始化。bignum初始化後默認是0，所以sign = 1， used = 0。如果dp為NULL，alloc = 0，否則alloc = 分配的數位（nlimbs）。
為了避免內存的無限制分配，這裡給數位設了一個上限值BN_MAX_LIMB， 在頭文件中定義是：
#define BN_MAX_LIMB 25600
也就是說bignum結構的最大數位不能超過25600，在32位環境下，每一個數位長度32bit，所以bignum最大長度是819200bit，對於加密算法來說綽綽有余了。
為了便於移植，有如下宏被定義（參考了PolarSSL的定義，比較好理解）：
#define ciL (sizeof(bn_digit)) //chars in limb （每個數位的字節大小）
#define biL (ciL << 3) //bits in limb （每個數位的bit大小）
#define biLH (ciL << 2) //half bits in limb （每個數位的bit大小的一半，這個後面的模運算會用到）
#define BN_MALLOC malloc
#define BN_FREE free
/**
* bignum結構初始化，未分配內存。
*/
void bn_init(bignum *x)
{
if(x != NULL)
{
x->sign = 1;
x->alloc = 0;
x->used = 0;
x->dp = NULL;
}
}
/**
* bignum結構初始化並分配內存。
* 若初始化失敗（內存分配錯誤），返回BN_MEMORY_ALLOCATE_FAIL
* 若超出數位上限，返回BN_EXCEED_MAX_LIMB
*/
int bn_init_size(bignum *x, size_t nlimbs)
{
bn_digit *p;
if(nlimbs > BN_MAX_LIMB)
return BN_EXCEED_MAX_LIMB;
if(x != NULL)
{
p = (bn_digit *)BN_MALLOC(nlimbs * ciL);
if(p == NULL) return BN_MEMORY_ALLOCATE_FAIL;
memset(p, 0x00, nlimbs * ciL); //初始化後bignum默認為0，所以必須把p指向的內存的所有值置為0.
x->sign = 1;
x->alloc = nlimbs;
x->used = 0;
x->dp = p;
}
return 0;
}
當不再需要使用bignum時，就應該使用bn_free函數及時釋放其分配的內存。bn_free函數有兩個作用：一是清除bignum的數位和其他成員，這樣即使不小心使用了已經清除的bignum也不會出問題，二是釋放已經分配的內存。
將已經清除的bignum的dp置為NULL，這樣後面再次調用該函數時函數就可以檢測到該bignum已經被清除，避免多次內存釋放。
void bn_free(bignum *x)
{
if(x != NULL)
{
if(x->dp != NULL)
{
memset(x->dp, 0x00, x->alloc * ciL);
BN_FREE(x->dp);
}
x->sign = 1;
x->alloc = 0;
x->used = 0;
x->dp = NULL;
}
}
★ 精度增加
當在bignum中存儲一個值的時候，必須要有足夠多的位數才能無損地存放一個完整的大整數。如果alloc足夠大，那麼只需要增加used即可，否則就需要重新分配內存增大alloc以滿足要求。
bn_grow函數首先檢查需要的數位（nlimbs）是否大於alloc，如果不是，那無需增加精度，函數調用結束，這樣就避免了內存重新分配，節約了時間。如果nlimbs大於alloc，那麼就要重新分配一段長度為nlimbs的內存空間，初始化為0後把原來dp指向的內存中的內容復制到新的空間中，並且釋放原先dp指向的內存。
int bn_grow(bignum *x, size_t nlimbs)
{
bn_digit *p;
if(nlimbs > BN_MAX_LIMB)
return BN_EXCEED_MAX_LIMB;
if(nlimbs > x->alloc)
{
p = (bn_digit *)BN_MALLOC(nlimbs * ciL);
if(p == NULL) return BN_MEMORY_ALLOCATE_FAIL;
memset(p, 0, nlimbs * ciL);
if(x->dp != NULL) //這裡判斷bignum結構的dp之前是否分配了內存，如果有分配才進行復制和內存釋放操作。
{
memcpy(p, x->dp, x->alloc * ciL);
memset(x->dp, 0, x->alloc * ciL);
BN_FREE(x->dp);
}
x->dp = p;
x->alloc = nlimbs;
}
return 0;
}
★ 復制操作
這個就很簡單了，把bignum y復制給bignum x，注意這裡的x->dp指向新的內存，而不是指向y->dp。
int bn_copy(bignum *x, const bignum *y)
{
int ret;
size_t nlimbs;
if(x == y) return 0; //x == y，表明 x 跟 y 是同一個數，此時無需任何操作，直接返回。注意這裡 x 跟 y 都是指針
x->sign = y->sign;
x->used = y->used;
nlimbs = (y->used == 0) ? 1 : y->used; //如果 y 為0，默認給 x 分配一位的空間
BN_CHECK(bn_grow(x, nlimbs));
memset(x->dp, 0x00, x->alloc * ciL); //初始化內存
if(y->dp != NULL && y->used > 0)
memcpy(x->dp, y->dp, y->used * ciL);
clean:
return ret;
}
★ 單精度賦值操作
有時候我們想把bignum設置成一個相對較小的單精度數，比如1， 2^32 - 1等等。 通過分配1個數位的內存，把單精度數賦值給數組的首個單元即可。在這裡我默認的單精度數是無符號的（即非負整數），如果想要賦值一個負數，可以直接把sign設為-1即可。
int bn_set_word(bignum *x, const bn_digit word)
{
int ret;
BN_CHECK(bn_grow(x, 1)); //分配一個數位的內存
memset(x->dp, 0, x->alloc * ciL); //初始化
x->dp[0] = word;
x->used = (word != 0) ? 1 : 0;
x->sign = 1; //如果是負數，在函數調用完後把sign設成-1即可
clean:
return ret;
}
★ 交換操作
這函數的作用很簡單，就是交換兩個大整數 x 和 y，具體的實現原理也很簡單，交換結構體中的每個成員即可。
void bn_swap(bignum *x, bignum *y)
{
int tmp_sign;
size_t tmp_alloc;
size_t tmp_used;
bn_digit *tmp_dp;
tmp_sign = x->sign;
tmp_alloc = x->alloc;
tmp_used = x->used;
tmp_dp = x->dp;
y->sign = x->sign;
y->alloc = x->alloc;
y->used = x->used;
y->dp = x->dp;
x->sign = tmp_sign;
x->alloc = tmp_alloc;
x->used = tmp_used;
x->dp = tmp_dp;
}
★ 總結
本文介紹的這些算法都是大整數庫中的最基本算法，雖然很簡單，但它們都是其他算法的基石，後面的算法將會頻繁使用到這些算法。下一篇文章將談談如何比較兩個大整數，包括絕對值比較，有符號大整數比較和大整數與單精度數的比較。
