GNU Multiple Precision Arithmetic Library

在開發程式的過程中，程式設計師不一定每一個原件都會純手工打造，事實上，很多東西會直接使用現有的工具。一來可以節省開發的成本，二來自己實作可能也比不上現有工具的功用跟效能（或許還會產生不少BUG）。所以在這裡也會介紹一些好用的工具或是函式庫。當然，前提這些東西都是自由或是能免費取得的。

名稱：GMP~GNU Multiple Precision Arithmetic Library
網址：http://gmplib.org/
功能：提供大數運算

大數運算是一個很重要的功能，特別是在處理數學問題、密碼學演算法上面。傳統C語言所能提供的數字運算，最多是到 double （以 32-bit 的機器來說，通常是 64-bit），但這對動不動就要 128 bit 的密碼學演算法來說，根本不敷使用。今天介紹的這一套 GMP，就是一套提供大數運算的函式庫。這套函式庫很有意思，他還把計算RSA的速率跟 Openssl
進行比較，結果呢，當然是樂勝囉～

這套函式庫提供了整數、分數、小數的型態，下面「稍微」看一下人家是怎麼設計的。我們只看看整數的部分，並且看一下人家的加法是如何處理的。

typedef struct
{
  int _mp_alloc;        /* Number of *limbs* allocated and pointed
                 to by the _mp_d field.  */
  int _mp_size;            /* abs(_mp_size) is the number of limbs the
                 last field points to.  If _mp_size is
                 negative this is a negative number.  */
  mp_limb_t *_mp_d;        /* Pointer to the limbs.  */
} __mpz_struct;

mpz 就是GMP中的整數型態。簡單來說，他是拿一串 limb 串起來來當作大數， limb 就是一般程式中所使用的數學型態。（根據平台不同，可能是 unsigned int or unsigned long），然後他還會記錄 size。

我認為，mp_alloc 跟 mp_size 的不同，在於一個是已經 alloc 出來的空間個數，另一個是計算上結果所需的空間個數（不一定一樣，因為可能多 alloc，或是出現進位造成 alloc 不夠），對了，還順便表示正負號。

至於加減法，程式碼在下面。有註解以後還挺好懂得，所以就不說明了。（有些定義沒放上來，但，看命名也知道那是什麼吧）

void
FUNCTION (ARGUMENTS)
{
  mp_srcptr up, vp;
  mp_ptr wp;
  mp_size_t usize, vsize, wsize;
  mp_size_t abs_usize;
  mp_size_t abs_vsize;

  usize = u->_mp_size;
  vsize = VARIATION v->_mp_size;
  abs_usize = ABS (usize);
  abs_vsize = ABS (vsize);

  if (abs_usize < abs_vsize)
    {
      /* Swap U and V. */
      MPZ_SRCPTR_SWAP (u, v);
      MP_SIZE_T_SWAP (usize, vsize);
      MP_SIZE_T_SWAP (abs_usize, abs_vsize);
    }

  /* True: ABS_USIZE >= ABS_VSIZE.  */

  /* If not space for w (and possible carry), increase space.  */
  wsize = abs_usize + 1;
  if (w->_mp_alloc < wsize)
    _mpz_realloc (w, wsize);

  /* These must be after realloc (u or v may be the same as w).  */
  up = u->_mp_d;
  vp = v->_mp_d;
  wp = w->_mp_d;

  if ((usize ^ vsize) < 0)
    {
      /* U and V have different sign.  Need to compare them to determine
  which operand to subtract from which.  */

      /* This test is right since ABS_USIZE >= ABS_VSIZE.  */
      if (abs_usize != abs_vsize)
 {
   mpn_sub (wp, up, abs_usize, vp, abs_vsize);
   wsize = abs_usize;
   MPN_NORMALIZE (wp, wsize);
   if (usize < 0)
     wsize = -wsize;
 }
      else if (mpn_cmp (up, vp, abs_usize) < 0)
 {
   mpn_sub_n (wp, vp, up, abs_usize);
   wsize = abs_usize;
   MPN_NORMALIZE (wp, wsize);
   if (usize >= 0)
     wsize = -wsize;
 }
      else
 {
   mpn_sub_n (wp, up, vp, abs_usize);
   wsize = abs_usize;
   MPN_NORMALIZE (wp, wsize);
   if (usize < 0)
     wsize = -wsize;
 }
    }
  else
    {
      /* U and V have same sign.  Add them.  */
      mp_limb_t cy_limb = mpn_add (wp, up, abs_usize, vp, abs_vsize);
      wp[abs_usize] = cy_limb;
      wsize = abs_usize + cy_limb;
      if (usize < 0)
 wsize = -wsize;
    }

  w->_mp_size = wsize;
}