tommath.tex

tommath库

\end{small}
\caption{The mp\_int Structure}
\label{fig:mpint}
\end{center}
\end{figure}

The mp\_int structure (fig. \ref{fig:mpint}) can be broken down as follows.

\begin{enumerate}
\item The \textbf{used} parameter denotes how many digits of the array \textbf{dp} contain the digits used to represent
a given integer.  The \textbf{used} count must be positive (or zero) and may not exceed the \textbf{alloc} count.  

\item The \textbf{alloc} parameter denotes how 
many digits are available in the array to use by functions before it has to increase in size.  When the \textbf{used} count 
of a result would exceed the \textbf{alloc} count all of the algorithms will automatically increase the size of the 
array to accommodate the precision of the result.  

\item The pointer \textbf{dp} points to a dynamically allocated array of digits that represent the given multiple 
precision integer.  It is padded with $(\textbf{alloc} - \textbf{used})$ zero digits.  The array is maintained in a least 
significant digit order.  As a pencil and paper analogy the array is organized such that the right most digits are stored
first starting at the location indexed by zero\footnote{In C all arrays begin at zero.} in the array.  For example, 
if \textbf{dp} contains $\lbrace a, b, c, \ldots \rbrace$ where \textbf{dp}$_0 = a$, \textbf{dp}$_1 = b$, \textbf{dp}$_2 = c$, $\ldots$ then 
it would represent the integer $a + b\beta + c\beta^2 + \ldots$  

\index{MP\_ZPOS} \index{MP\_NEG}
\item The \textbf{sign} parameter denotes the sign as either zero/positive (\textbf{MP\_ZPOS}) or negative (\textbf{MP\_NEG}).  
\end{enumerate}

\subsubsection{Valid mp\_int Structures}
Several rules are placed on the state of an mp\_int structure and are assumed to be followed for reasons of efficiency.  
The only exceptions are when the structure is passed to initialization functions such as mp\_init() and mp\_init\_copy().

\begin{enumerate}
\item The value of \textbf{alloc} may not be less than one.  That is \textbf{dp} always points to a previously allocated
array of digits.
\item The value of \textbf{used} may not exceed \textbf{alloc} and must be greater than or equal to zero.
\item The value of \textbf{used} implies the digit at index $(used - 1)$ of the \textbf{dp} array is non-zero.  That is, 
leading zero digits in the most significant positions must be trimmed.
   \begin{enumerate}
   \item Digits in the \textbf{dp} array at and above the \textbf{used} location must be zero.
   \end{enumerate}
\item The value of \textbf{sign} must be \textbf{MP\_ZPOS} if \textbf{used} is zero; 
this represents the mp\_int value of zero.
\end{enumerate}

\section{Argument Passing}
A convention of argument passing must be adopted early on in the development of any library.  Making the function 
prototypes consistent will help eliminate many headaches in the future as the library grows to significant complexity.  
In LibTomMath the multiple precision integer functions accept parameters from left to right as pointers to mp\_int 
structures.  That means that the source (input) operands are placed on the left and the destination (output) on the right.   
Consider the following examples.

\begin{verbatim}
   mp_mul(&a, &b, &c);   /* c = a * b */
   mp_add(&a, &b, &a);   /* a = a + b */
   mp_sqr(&a, &b);       /* b = a * a */
\end{verbatim}

The left to right order is a fairly natural way to implement the functions since it lets the developer read aloud the
functions and make sense of them.  For example, the first function would read ``multiply a and b and store in c''.

Certain libraries (\textit{LIP by Lenstra for instance}) accept parameters the other way around, to mimic the order
of assignment expressions.  That is, the destination (output) is on the left and arguments (inputs) are on the right.  In 
truth, it is entirely a matter of preference.  In the case of LibTomMath the convention from the MPI library has been 
adopted.  

Another very useful design consideration, provided for in LibTomMath, is whether to allow argument sources to also be a 
destination.  For example, the second example (\textit{mp\_add}) adds $a$ to $b$ and stores in $a$.  This is an important 
feature to implement since it allows the calling functions to cut down on the number of variables it must maintain.  
However, to implement this feature specific care has to be given to ensure the destination is not modified before the 
source is fully read.

\section{Return Values}
A well implemented application, no matter what its purpose, should trap as many runtime errors as possible and return them 
to the caller.  By catching runtime errors a library can be guaranteed to prevent undefined behaviour.  However, the end 
developer can still manage to cause a library to crash.  For example, by passing an invalid pointer an application may
fault by dereferencing memory not owned by the application.

In the case of LibTomMath the only errors that are checked for are related to inappropriate inputs (division by zero for 
instance) and memory allocation errors.  It will not check that the mp\_int passed to any function is valid nor 
will it check pointers for validity.  Any function that can cause a runtime error will return an error code as an 
\textbf{int} data type with one of the following values (fig \ref{fig:errcodes}).

\index{MP\_OKAY} \index{MP\_VAL} \index{MP\_MEM}
\begin{figure}[here]
\begin{center}
\begin{tabular}{|l|l|}
\hline \textbf{Value} & \textbf{Meaning} \\
\hline \textbf{MP\_OKAY} & The function was successful \\
\hline \textbf{MP\_VAL}  & One of the input value(s) was invalid \\
\hline \textbf{MP\_MEM}  & The function ran out of heap memory \\
\hline
\end{tabular}
\end{center}
\caption{LibTomMath Error Codes}
\label{fig:errcodes}
\end{figure}

When an error is detected within a function it should free any memory it allocated, often during the initialization of
temporary mp\_ints, and return as soon as possible.  The goal is to leave the system in the same state it was when the 
function was called.  Error checking with this style of API is fairly simple.

\begin{verbatim}
   int err;
   if ((err = mp_add(&a, &b, &c)) != MP_OKAY) {
      printf("Error: %s\n", mp_error_to_string(err));
      exit(EXIT_FAILURE);
   }
\end{verbatim}

The GMP \cite{GMP} library uses C style \textit{signals} to flag errors which is of questionable use.  Not all errors are fatal 
and it was not deemed ideal by the author of LibTomMath to force developers to have signal handlers for such cases.

\section{Initialization and Clearing}
The logical starting point when actually writing multiple precision integer functions is the initialization and 
clearing of the mp\_int structures.  These two algorithms will be used by the majority of the higher level algorithms.

Given the basic mp\_int structure an initialization routine must first allocate memory to hold the digits of
the integer.  Often it is optimal to allocate a sufficiently large pre-set number of digits even though
the initial integer will represent zero.  If only a single digit were allocated quite a few subsequent re-allocations
would occur when operations are performed on the integers.  There is a tradeoff between how many default digits to allocate
and how many re-allocations are tolerable.  Obviously allocating an excessive amount of digits initially will waste 
memory and become unmanageable.  

If the memory for the digits has been successfully allocated then the rest of the members of the structure must
be initialized.  Since the initial state of an mp\_int is to represent the zero integer, the allocated digits must be set
to zero.  The \textbf{used} count set to zero and \textbf{sign} set to \textbf{MP\_ZPOS}.

\subsection{Initializing an mp\_int}
An mp\_int is said to be initialized if it is set to a valid, preferably default, state such that all of the members of the
structure are set to valid values.  The mp\_init algorithm will perform such an action.

\index{mp\_init}
\begin{figure}[here]
\begin{center}
\begin{tabular}{l}
\hline Algorithm \textbf{mp\_init}. \\
\textbf{Input}.   An mp\_int $a$ \\
\textbf{Output}.  Allocate memory and initialize $a$ to a known valid mp\_int state.  \\
\hline \\
1.  Allocate memory for \textbf{MP\_PREC} digits. \\
2.  If the allocation failed return(\textit{MP\_MEM}) \\
3.  for $n$ from $0$ to $MP\_PREC - 1$ do  \\
\hspace{3mm}3.1  $a_n \leftarrow 0$\\
4.  $a.sign \leftarrow MP\_ZPOS$\\
5.  $a.used \leftarrow 0$\\
6.  $a.alloc \leftarrow MP\_PREC$\\
7.  Return(\textit{MP\_OKAY})\\
\hline
\end{tabular}
\end{center}
\caption{Algorithm mp\_init}
\end{figure}

\textbf{Algorithm mp\_init.}
The purpose of this function is to initialize an mp\_int structure so that the rest of the library can properly
manipulte it.  It is assumed that the input may not have had any of its members previously initialized which is certainly
a valid assumption if the input resides on the stack.  

Before any of the members such as \textbf{sign}, \textbf{used} or \textbf{alloc} are initialized the memory for
the digits is allocated.  If this fails the function returns before setting any of the other members.  The \textbf{MP\_PREC} 
name represents a constant\footnote{Defined in the ``tommath.h'' header file within LibTomMath.} 
used to dictate the minimum precision of newly initialized mp\_int integers.  Ideally, it is at least equal to the smallest
precision number you'll be working with.

Allocating a block of digits at first instead of a single digit has the benefit of lowering the number of usually slow
heap operations later functions will have to perform in the future.  If \textbf{MP\_PREC} is set correctly the slack 
memory and the number of heap operations will be trivial.

Once the allocation has been made the digits have to be set to zero as well as the \textbf{used}, \textbf{sign} and
\textbf{alloc} members initialized.  This ensures that the mp\_int will always represent the default state of zero regardless
of the original condition of the input.

\textbf{Remark.}
This function introduces the idiosyncrasy that all iterative loops, commonly initiated with the ``for'' keyword, iterate incrementally
when the ``to'' keyword is placed between two expressions.  For example, ``for $a$ from $b$ to $c$ do'' means that
a subsequent expression (or body of expressions) are to be evaluated upto $c - b$ times so long as $b \le c$.  In each
iteration the variable $a$ is substituted for a new integer that lies inclusively between $b$ and $c$.  If $b > c$ occured
the loop would not iterate.  By contrast if the ``downto'' keyword were used in place of ``to'' the loop would iterate 
decrementally.

\vspace{+3mm}\begin{small}
\hspace{-5.1mm}{\bf File}: bn\_mp\_init.c
\vspace{-3mm}
\begin{alltt}
016   
017   /* init a new mp_int */
018   int mp_init (mp_int * a)
019   \{
020     int i;
021   
022     /* allocate memory required and clear it */
023     a->dp = OPT_CAST(mp_digit) XMALLOC (sizeof (mp_digit) * MP_PREC);
024     if (a->dp == NULL) \{
025       return MP_MEM;
026     \}
027   
028     /* set the digits to zero */
029     for (i = 0; i < MP_PREC; i++) \{
030         a->dp[i] = 0;
031     \}
032   
033     /* set the used to zero, allocated digits to the default precision
034      * and sign to positive */
035     a->used  = 0;
036     a->alloc = MP_PREC;
037     a->sign  = MP_ZPOS;
038   
039     return MP_OKAY;
040   \}
041   #endif
\end{alltt}
\end{small}