tommath.tex

tommath库

One immediate observation of this initializtion function is that it does not return a pointer to a mp\_int structure.  It 
is assumed that the caller has already allocated memory for the mp\_int structure, typically on the application stack.  The 
call to mp\_init() is used only to initialize the members of the structure to a known default state.  

Here we see (line 23) the memory allocation is performed first.  This allows us to exit cleanly and quickly
if there is an error.  If the allocation fails the routine will return \textbf{MP\_MEM} to the caller to indicate there
was a memory error.  The function XMALLOC is what actually allocates the memory.  Technically XMALLOC is not a function
but a macro defined in ``tommath.h``.  By default, XMALLOC will evaluate to malloc() which is the C library's built--in
memory allocation routine.

In order to assure the mp\_int is in a known state the digits must be set to zero.  On most platforms this could have been
accomplished by using calloc() instead of malloc().  However,  to correctly initialize a integer type to a given value in a 
portable fashion you have to actually assign the value.  The for loop (line 29) performs this required
operation.

After the memory has been successfully initialized the remainder of the members are initialized 
(lines 33 through 34) to their respective default states.  At this point the algorithm has succeeded and
a success code is returned to the calling function.  If this function returns \textbf{MP\_OKAY} it is safe to assume the 
mp\_int structure has been properly initialized and is safe to use with other functions within the library.  

\subsection{Clearing an mp\_int}
When an mp\_int is no longer required by the application, the memory that has been allocated for its digits must be 
returned to the application's memory pool with the mp\_clear algorithm.

\begin{figure}[here]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_clear}. \\
\textbf{Input}.   An mp\_int $a$ \\
\textbf{Output}.  The memory for $a$ shall be deallocated.  \\
\hline \\
1.  If $a$ has been previously freed then return(\textit{MP\_OKAY}). \\
2.  for $n$ from 0 to $a.used - 1$ do \\
\hspace{3mm}2.1  $a_n \leftarrow 0$ \\
3.  Free the memory allocated for the digits of $a$. \\
4.  $a.used \leftarrow 0$ \\
5.  $a.alloc \leftarrow 0$ \\
6.  $a.sign \leftarrow MP\_ZPOS$ \\
7.  Return(\textit{MP\_OKAY}). \\
\hline
\end{tabular}
\end{center}
\caption{Algorithm mp\_clear}
\end{figure}

\textbf{Algorithm mp\_clear.}
This algorithm accomplishes two goals.  First, it clears the digits and the other mp\_int members.  This ensures that 
if a developer accidentally re-uses a cleared structure it is less likely to cause problems.  The second goal
is to free the allocated memory.

The logic behind the algorithm is extended by marking cleared mp\_int structures so that subsequent calls to this
algorithm will not try to free the memory multiple times.  Cleared mp\_ints are detectable by having a pre-defined invalid 
digit pointer \textbf{dp} setting.

Once an mp\_int has been cleared the mp\_int structure is no longer in a valid state for any other algorithm
with the exception of algorithms mp\_init, mp\_init\_copy, mp\_init\_size and mp\_clear.

\vspace{+3mm}\begin{small}
\hspace{-5.1mm}{\bf File}: bn\_mp\_clear.c
\vspace{-3mm}
\begin{alltt}
016   
017   /* clear one (frees)  */
018   void
019   mp_clear (mp_int * a)
020   \{
021     int i;
022   
023     /* only do anything if a hasn't been freed previously */
024     if (a->dp != NULL) \{
025       /* first zero the digits */
026       for (i = 0; i < a->used; i++) \{
027           a->dp[i] = 0;
028       \}
029   
030       /* free ram */
031       XFREE(a->dp);
032   
033       /* reset members to make debugging easier */
034       a->dp    = NULL;
035       a->alloc = a->used = 0;
036       a->sign  = MP_ZPOS;
037     \}
038   \}
039   #endif
\end{alltt}
\end{small}

The algorithm only operates on the mp\_int if it hasn't been previously cleared.  The if statement (line 24)
checks to see if the \textbf{dp} member is not \textbf{NULL}.  If the mp\_int is a valid mp\_int then \textbf{dp} cannot be
\textbf{NULL} in which case the if statement will evaluate to true.

The digits of the mp\_int are cleared by the for loop (line 26) which assigns a zero to every digit.  Similar to mp\_init()
the digits are assigned zero instead of using block memory operations (such as memset()) since this is more portable.  

The digits are deallocated off the heap via the XFREE macro.  Similar to XMALLOC the XFREE macro actually evaluates to
a standard C library function.  In this case the free() function.  Since free() only deallocates the memory the pointer
still has to be reset to \textbf{NULL} manually (line 34).  

Now that the digits have been cleared and deallocated the other members are set to their final values (lines 35 and 36).

\section{Maintenance Algorithms}

The previous sections describes how to initialize and clear an mp\_int structure.  To further support operations
that are to be performed on mp\_int structures (such as addition and multiplication) the dependent algorithms must be
able to augment the precision of an mp\_int and 
initialize mp\_ints with differing initial conditions.  

These algorithms complete the set of low level algorithms required to work with mp\_int structures in the higher level
algorithms such as addition, multiplication and modular exponentiation.

\subsection{Augmenting an mp\_int's Precision}
When storing a value in an mp\_int structure, a sufficient number of digits must be available to accomodate the entire 
result of an operation without loss of precision.  Quite often the size of the array given by the \textbf{alloc} member 
is large enough to simply increase the \textbf{used} digit count.  However, when the size of the array is too small it 
must be re-sized appropriately to accomodate the result.  The mp\_grow algorithm will provide this functionality.

\newpage\begin{figure}[here]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_grow}. \\
\textbf{Input}.   An mp\_int $a$ and an integer $b$. \\
\textbf{Output}.  $a$ is expanded to accomodate $b$ digits. \\
\hline \\
1.  if $a.alloc \ge b$ then return(\textit{MP\_OKAY}) \\
2.  $u \leftarrow b\mbox{ (mod }MP\_PREC\mbox{)}$ \\
3.  $v \leftarrow b + 2 \cdot MP\_PREC - u$ \\
4.  Re-allocate the array of digits $a$ to size $v$ \\
5.  If the allocation failed then return(\textit{MP\_MEM}). \\
6.  for n from a.alloc to $v - 1$ do  \\
\hspace{+3mm}6.1  $a_n \leftarrow 0$ \\
7.  $a.alloc \leftarrow v$ \\
8.  Return(\textit{MP\_OKAY}) \\
\hline
\end{tabular}
\end{center}
\caption{Algorithm mp\_grow}
\end{figure}

\textbf{Algorithm mp\_grow.}
It is ideal to prevent re-allocations from being performed if they are not required (step one).  This is useful to 
prevent mp\_ints from growing excessively in code that erroneously calls mp\_grow.  

The requested digit count is padded up to next multiple of \textbf{MP\_PREC} plus an additional \textbf{MP\_PREC} (steps two and three).  
This helps prevent many trivial reallocations that would grow an mp\_int by trivially small values.  

It is assumed that the reallocation (step four) leaves the lower $a.alloc$ digits of the mp\_int intact.  This is much 
akin to how the \textit{realloc} function from the standard C library works.  Since the newly allocated digits are 
assumed to contain undefined values they are initially set to zero.

\vspace{+3mm}\begin{small}
\hspace{-5.1mm}{\bf File}: bn\_mp\_grow.c
\vspace{-3mm}
\begin{alltt}
016   
017   /* grow as required */
018   int mp_grow (mp_int * a, int size)
019   \{
020     int     i;
021     mp_digit *tmp;
022   
023     /* if the alloc size is smaller alloc more ram */
024     if (a->alloc < size) \{
025       /* ensure there are always at least MP_PREC digits extra on top */
026       size += (MP_PREC * 2) - (size % MP_PREC);
027   
028       /* reallocate the array a->dp
029        *
030        * We store the return in a temporary variable
031        * in case the operation failed we don't want
032        * to overwrite the dp member of a.
033        */
034       tmp = OPT_CAST(mp_digit) XREALLOC (a->dp, sizeof (mp_digit) * size);
035       if (tmp == NULL) \{
036         /* reallocation failed but "a" is still valid [can be freed] */
037         return MP_MEM;
038       \}
039   
040       /* reallocation succeeded so set a->dp */
041       a->dp = tmp;
042   
043       /* zero excess digits */
044       i        = a->alloc;
045       a->alloc = size;
046       for (; i < a->alloc; i++) \{
047         a->dp[i] = 0;
048       \}
049     \}
050     return MP_OKAY;
051   \}
052   #endif
\end{alltt}
\end{small}

A quick optimization is to first determine if a memory re-allocation is required at all.  The if statement (line 23) checks
if the \textbf{alloc} member of the mp\_int is smaller than the requested digit count.  If the count is not larger than \textbf{alloc}
the function skips the re-allocation part thus saving time.

When a re-allocation is performed it is turned into an optimal request to save time in the future.  The requested digit count is
padded upwards to 2nd multiple of \textbf{MP\_PREC} larger than \textbf{alloc} (line 26).  The XREALLOC function is used
to re-allocate the memory.  As per the other functions XREALLOC is actually a macro which evaluates to realloc by default.  The realloc
function leaves the base of the allocation intact which means the first \textbf{alloc} digits of the mp\_int are the same as before
the re-allocation.  All	that is left is to clear the newly allocated digits and return.

Note that the re-allocation result is actually stored in a temporary pointer $tmp$.  This is to allow this function to return
an error with a valid pointer.  Earlier releases of the library stored the result of XREALLOC into the mp\_int $a$.  That would
result in a memory leak if XREALLOC ever failed.  

\subsection{Initializing Variable Precision mp\_ints}
Occasionally the number of digits required will be known in advance of an initialization, based on, for example, the size 
of input mp\_ints to a given algorithm.  The purpose of algorithm