NTL(Number Theory Library)源码剖析(1.1)__内存管理

本文讲解NTL源码中关于内存管理的部分，下面提到源码文件a.h时同时指a.cpp。一个二进制数最低位为第0位。主要在<lip.h>, <ctools.h>中。NTL的重要的类ZZ存储任意长的有符号数。

常用数与函数

typedef unsigned long _ntl_limb_t;
typedef long _ntl_signed_limb_t;
typedef _ntl_limb_t *_ntl_limb_t_ptr;

_ntl_limb_t用于表示数据单元，即高精度运算中使用的数据单元。

NTL中有一些常用宏

#define NTL_BITS_PER_LONG (32)

#define NTL_OVFBND (1L << (NTL_BITS_PER_LONG-4))

#define NTL_SNS std ::

NTL_OVFBND通常当作界限，NTL_ZZ_NBITS是30。

下面的_ntl_count_bits用于统计x的有效位数，例如x=2有2个有效位，x=4有3个有效位。

inline long 
_ntl_count_bits(unsigned long x)
{
   if (!x) return 0;
   long res = NTL_BITS_PER_LONG;
   while (x < (1UL << (NTL_BITS_PER_LONG-1))) {
      x <<= 1;
      res--;
   }
   return res;
}

下面的函数封装了_ntl_count_bits，

static
inline long COUNT_BITS(_ntl_limb_t x)
{
   return _ntl_count_bits(x);
}

下面函数计算有n个分配单元的vector扩展后的单元数，这里扩容系数为1.5

// vectors are grown by a factor of 1.5
inline long _ntl_vec_grow(long n)
{ return n + n/2; }

下面是1个字典序比较函数

_ntl_signed_limb_t 
_ntl_mpn_cmp(const _ntl_limb_t *s1p, const _ntl_limb_t *s2p, long n)
{
   for (long i = n-1; i >= 0; i--) {
      _ntl_signed_limb_t diff = _ntl_signed_limb_t(s1p[i]) - _ntl_signed_limb_t(s2p[i]);
      if (diff) return diff;
   }

   return 0;
}

下面是结构体_ntl_gbigint_body，用于管理存储big integer的空间

struct _ntl_gbigint_body {
   long alloc_;
   long size_;
};

typedef _ntl_gbigint_body *_ntl_gbigint;

alloc_取值最低位是frozen_flag，第1位为continue_flag，(alloc_ >> 2)表示分配的_ntl_limb_t的个数。frozen_flag影响内存管理方式。size_表示实际使用的_ntl_limb_t个数。NTL中1个大整数通常保存_ntl_gbigint_body，后接vector DATA。一个大整数0通常size_为0. 

这里特别注意1个_ntl_gbigint是1个指向_ntl_gbigint_body的指针，但是后面的内存也可能使用到，如此就能表示1个大整数。这里体现了指针的灵活性，指向的数据有何意义完全由用户去解释，而不拘泥于指针的类型。

下面是作为工具出现的函数，

static
inline long& ALLOC(_ntl_gbigint p) 
   { return p->alloc_; }

static
inline long& SIZE(_ntl_gbigint p) 
   { return p->size_; }

static
inline _ntl_limb_t * DATA(_ntl_gbigint p) 
   { return (_ntl_limb_t *) (p+1); }

static
inline long STORAGE(long len)
   { return ((long)(sizeof(_ntl_gbigint_body) + (len)*sizeof(_ntl_limb_t))); }

static
inline long MustAlloc(_ntl_gbigint c, long len)  
   { return (!(c) || (ALLOC(c) >> 2) < (len)); }

DATA获取指针指向数据起始地址，

STORAGE(len)返回存储len个_ntl_limb_t需要的字节数。

MustAlloc判断是否需要分配内存，参数len表示需要的_ntl_limb_t个数。

下面是一个工具宏

#define NTL_OVERFLOW(n, a, b) \
   (((b) >= NTL_OVFBND) || (((long) (n)) > 0 && (((a) >= NTL_OVFBND) || \
    (((long) (n)) >= (NTL_OVFBND-((long)(b))+((long)(a))-1)/((long)(a))))))

/*
 * NTL_OVERFLOW(n, a, b) returns 1 if n*a + b >= NTL_OVFBND,
 * and returns 0 otherwise...
*/

#define STORAGE_OVF(len) NTL_OVERFLOW(len, sizeof(_ntl_limb_t), 2*sizeof(long))

#define NTL_SNS_REALLOC(p, n, a, b) \
   (NTL_OVERFLOW1(n, a, b) ? ((void *) 0) : \
    ((void *) NTL_SNS realloc((p), ((long)(n))*((long)(a)) + ((long)(b)))))

STORAGE_OVF(len) 判断有len个数据单元是否会占用太多内存。

NTL_SNS_REALLOC(p, n, a, b)用于分配内存n*a+b字节的内存到指针p.

下面是一个包装类，Deleter类似于仿函数，调用方式为Deleter::apply(rep).

template<class T, class Deleter>
class WrappedPtr {
private:
   WrappedPtr(const WrappedPtr&); // disable
   void operator=(const WrappedPtr&); // disable
public:
   typedef T * raw_ptr;

   raw_ptr rep;

   WrappedPtr() : rep(0) { }
   void operator=(const raw_ptr& _rep)  { rep = _rep; }

   ~WrappedPtr() { if (rep) Deleter::apply(rep); } 

   operator const raw_ptr& () const { return rep; }
   operator raw_ptr& () { return rep; }

   const raw_ptr* operator&() const { return &rep; }
   raw_ptr* operator&() { return &rep; }

   void kill() { if (rep) { Deleter::apply(rep); rep = 0; } }

   void swap(WrappedPtr& other) { _ntl_swap(rep, other.rep); }

   void move(WrappedPtr& other) 
   {
      WrappedPtr tmp;
      tmp.swap(other);
      tmp.swap(*this);
   }

};

_ntl_swap(rep, other.rep)交换2个指针，_ntl_swap有很多重载，功能都是交换2个输入参数。

内存管理

下面_ntl_gsetlength申请len个_ntl_limb_t以及1个_ntl_gbigint_body需要的内存给v，NTL_ZZ_NBITS是30. 其中的错误处理函数最后要么调用cerr，要么调用用户自定义的错误处理函数。

void _ntl_gsetlength(_ntl_gbigint *v, long len)
{
   _ntl_gbigint x = *v;

   if (len < 0)
      LogicError("negative size allocation in _ntl_zgetlength");

   if (NTL_OVERFLOW(len, NTL_ZZ_NBITS, 0))
      ResourceError("size too big in _ntl_gsetlength");


   if (x) {
      long oldlen = ALLOC(x);
      long fixed = oldlen & 1;
      oldlen = oldlen >> 2;

      if (fixed) {
         if (len > oldlen) 
            LogicError("internal error: can't grow this _ntl_gbigint");
         else
            return;
      }

      if (len <= oldlen) return;

      len++;  /* always allocate at least one more than requested */

      oldlen = _ntl_vec_grow(oldlen);
      if (len < oldlen)
         len = oldlen;

      /* round up to multiple of MIN_SETL */
      len = ((len+(MIN_SETL-1))/MIN_SETL)*MIN_SETL; 

      /* test len again */
      if (NTL_OVERFLOW(len, NTL_ZZ_NBITS, 0))
         ResourceError("size too big in _ntl_gsetlength");

      if (STORAGE_OVF(len))
         ResourceError("reallocation failed in _ntl_gsetlength");

      if (!(x = (_ntl_gbigint)NTL_SNS_REALLOC((void *) x, 1, STORAGE(len), 0))) {
         MemoryError();
      }
      ALLOC(x) = len << 2;
   }
   else {
      len++;  /* as above, always allocate one more than explicitly reqested */
      len = ((len+(MIN_SETL-1))/MIN_SETL)*MIN_SETL; 

      /* test len again */
      if (NTL_OVERFLOW(len, NTL_ZZ_NBITS, 0))
         ResourceError("size too big in _ntl_gsetlength");

      if (STORAGE_OVF(len))
         ResourceError("reallocation failed in _ntl_gsetlength");

      if (!(x = (_ntl_gbigint)NTL_SNS_MALLOC(1, STORAGE(len), 0))) {
         MemoryError();
      }
      ALLOC(x) = len << 2;
      SIZE(x) = 0;
   }

   *v = x;
}

下面函数返回(x->alloc_) >> 2，即分配的_ntl_limb_t的个数。

inline long _ntl_gmaxalloc(_ntl_gbigint x)
    {
      if (!x)
         return 0;
      else
         return _ntl_ALLOC(x) >> 2;
    }

下面函数用于释放内存。

void _ntl_gfree(_ntl_gbigint x)
{

   if (!x)
      return;
   if (ALLOC(x) & 1)
      TerminalError("Internal error: can't free this _ntl_gbigint");
   free((void*) x);
   return;
}

ntl_gbigint_body有一个封装为_ntl_gbigint_wrapped. 

class _ntl_gbigint_deleter {
public:
   static void apply(_ntl_gbigint p) { _ntl_gfree(p); }
};

typedef WrappedPtr<_ntl_gbigint_body, _ntl_gbigint_deleter> _ntl_gbigint_wrapped;

static inline void
_ntl_swap(_ntl_gbigint_wrapped& p, _ntl_gbigint_wrapped& q)
{
   p.swap(q);
}

另外有一系列_ntl_swap函数用于交换2个泛型T变量，或者指针。这里不列举。