X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/836e0c19dceaad96151e7f7f42898d1263130ba4..3471ebd194145da52d419c6315459237b076e18d:/manual/mp-mp.tex diff --git a/manual/mp-mp.tex b/manual/mp-mp.tex new file mode 100644 index 0000000..4f3aa67 --- /dev/null +++ b/manual/mp-mp.tex @@ -0,0 +1,450 @@ +%%% -*-latex-*- + +\section{High-level multiprecision integer represention} +\label{sec:mp} + +The high-level interface to multiprecision integers is exported by the header +file \hdr{}. + + +\subsection{The \code{mp} structure} +\label{sec:mp-struct} + +At the high level, a multiprecision integer is represented as an object of +type \code{mp}. Most of the time, programs use pointers to \code{mp} objects +which have been dynamically allocated. (See \code{mp_build}, +page~\pageref{fn:mp-build}, for the exception to this rule.) + +The \code{mp} type is a structure. Some of the members are considered +internal to the implementation. However, the following may be used by client +programs: +\begin{description} + \def\makelabel#1{\code{#1}\hfil} +\item[mpw *v, *vl] The base and limit of the multiprecision + integer array. +\item[unsigned f] Various flags describing the current state of the integer. +\end{description} +Other members are used for keeping track of how much memory has been +allocated to the number and for managing the reference counting system. +These members should not be accessed directly by application code. None of +the structure members should be modified directly. + +The following flags are defined: +\begin{description*} + \let\makelabel\code +\item[MP_NEG] The integer is negative. +\item[MP_BURN] Clear the integer's storage after use. +\item[MP_CONST] The integer may not be altered or freed. +\item[MP_UNDEF] The integer currently has no interesting value. +\item[MP_DESTROYED] The integer has been destroyed. +\end{description*} + +The \code{MP_BURN} flag is inherited by the results of calculations. Thus, +setting the flag on a value causes it and all other values calculated from it +to be destroyed after use.\footnote{% + There are currently a small number of places where the \code{MP_BURN} flag + may be lost from a result. These usually result from performing complex + calculations with degenerate arguments (e.g., computing a GCD with zero). + Fixing this is not a high priority.} % + +The \code{MP_DESTROYED} flag is used by \code{mp_destroy} +(page~\pageref{fn:mp-destroy}) to trap attempts to destroy the same integer +more than once, which can otherwise lead to confusing bugs. + + +\subsubsection{The \code{MP_LEN} macro} +\label{fn:MP-LEN} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|ptrdiff_t MP_LEN(const mp *|$m$|);| +\end{listinglist} + +\fsec{Returns} + +The number of words used in the representation of the integer $m$. Note that +the argument $m$ may be evaluated multiple times by this macro. + + +\subsubsection{The \code{mp_burn} function} +\label{fn:mp-burn} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_burn(mp *|$m$|);| +\end{listinglist} + +\fsec{Description} + +Sets the \code{MP_BURN} flag on the integer $m$. Whenever memory associated +with $m$, or results derived from it, is deallocated, it is overwritten with +zeros to prevent traces being found in swap files or core dumps. + + +\subsection{Multiprecision integer constants} +\label{sec:mp-const} + +There are a few commonly-used multiprecision integer constants provided. All +are declared in \hdr{}: + +\begin{tabular}[C] + {| >{\ttfamily}l | Mr @{\extracolsep{0pt plus 10000fill}\hskip\tabcolsep} + | c @{\extracolsep{0pt}} | >{\ttfamily}l | Mr |} \hlx{c{1,2,4,5}v} + \multicolumn{1}{|c|}{\textbf{Constant}} & + \multicolumn{1}{c|}{\textbf{Value}} & \qquad & + \multicolumn{1}{c|}{\textbf{Constant}} & + \multicolumn{1}{c|}{\textbf{Value}} \\ \hlx{vc{1,2,4,5}v} + MP_ZERO & 0 && MP_FOUR & 4 \\ + MP_ONE & 1 && MP_FIVE & 5 \\ + MP_TWO & 2 && MP_TEN & 10 \\ + MP_THREE & 3 && MP_MONE & -1 \\ \hlx{vc{1,2,4,5}} +\end{tabular} +\goodbreak + +All of the multiprecision constants are actually pointers to the real +values. All have the \code{MP_CONST} flag set, so they cannot be modified or +destroyed. + + +\subsection{Creation and destruction} +\label{sec:mp-create} + +Multiprecision integers are reference counted; i.e., each \code{mp} remembers +how many references there are to it, and is destroyed only when the last +reference disappears. + +New multiprecision integers are created using the functions \code{mp_create} +(page~\pageref{fn:mp-create}) or \code{mp_build} +(page~\pageref{fn:mp-build}). A newly created integer has one reference. +Additional references are returned by the function \code{mp_copy} +(page~\pageref{fn:mp-copy}). A reference may be removed from an integer by +calling \code{mp_drop} (page~\pageref{fn:mp-drop}). + +It isn't usually a good idea to modify an integer to which there are multiple +references: the owners of the other references will usually react badly if +their number has changed. A modifiable copy may be made of an integer using +the \code{mp_split} function (page~\pageref{fn:mp-split}). If there are no +other references, the integer is returned unchanged; otherwise a real copy is +made and returned, and the number of references to the original is +decremented by one. + +Most of the arithmetic functions allow the caller to state a preferred +location for the result. This may either be an existing integer or a +completely new one, requested by the special value \code{MP_NEW}. This +behaviour is provided by the \code{mp_modify} function +(page~\pageref{fn:mp-modify}). + +Note that functions may not actually use the location requested, although if +it decides not to overwrite the requested destination, a reference to it is +removed. + + +\subsubsection{The \code{mp_create} function} +\label{fn:mp-create} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|mp *mp_create(size_t |$\sz$|);| +\end{listinglist} + +\fsec{Description} + +Allocates a new multiprecision integer, with at least $\sz$ words of storage +available for its representation. The flag \code{MP_UNDEF} is set initially; +the other flags are cleared. The integer's array limit pointer \code{vl} is +set to be $\sz$ higher than the base pointer \code{v}. + +\fsec{Returns} + +A pointer to a newly allocated multiprecision integer. + +\subsubsection{The \code{mp_destroy} function} +\label{fn:mp-destroy} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_destroy(mp *|$m$|);| +\end{listinglist} + +\fsec{Description} + +Destroys the multiprecision integer $m$. All resouces allocated to the +integer are freed. It's most unusual for this to be the function you want: +most of the time \code{mp_drop} (page~\pageref{fn:mp-drop}) is much more +useful. + +If compiled with debugging support, the \code{mp_destroy} function will abort +if requested to destroy an integer whose \code{MP_CONST} or +\code{MP_DESTROYED} flags are set. + +\subsubsection{The \code{mp_build} function} +\label{fn:mp-build} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_build(mp *|$m$|, mpw *|$v$|, mpw *|$\vl$|);| +\end{listinglist} + +\fsec{Description} + +Creates a constant multiprecision integer from an array of \code{mpw} words. +Storage for the \code{mp} object and the array is provided by the user -- +\code{mp_build} allocates no memory. Conversely, it's safe to dispose of the +\code{mp} block and \code{mpw} array at any time, as long as there are no +live references to them. + +The \code{mp_build} function is particularly useful for constructing small +multiprecision integers, and for addressing parts of other integers. For +example, if $x$ is a multiprecision integer, then +\begin{listing} +mp_build(&m, x->v + 5, x->vl); +\end{listing} +sets $m$ equal to $\lfloor x / 2^{5 \cdot \code{MPW_BITS}} \rfloor$ without +copying any data.\footnote{% + This technique is used in the implementation of Barrett reduction + (page~\pageref{sec:mp-barrett}), for example. See the source file + \code{mpbarrett.c} for details.} % + +\subsubsection{The \code{mp_copy} function and \code{MP_COPY} macro} +\label{fn:mp-copy} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|mp *mp_copy(mp *|$m$|);| \\ +|mp *MP_COPY(mp *|$m$|);| +\end{listinglist} + +\fsec{Description} + +The function \code{mp_copy} adds a reference to the multiprecision integer +$m$. The integer will not be destroyed until all references to it have been +dropped. + +The macro \code{MP_COPY} performs exactly the same action as the +\code{mp_copy} function, except that it uses inline code rather than a +function call. It's probably smaller and faster than the function call too. + +\fsec{Returns} + +The address of the new reference. This will usually be the same as the +original argument $m$. + +\subsubsection{The \code{mp_drop} function and \code{MP_DROP} macro} +\label{fn:mp-drop} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_drop(mp *|$m$|);| \\ +|void MP_DROP(mp *|$m$|);| +\end{listinglist} + +\fsec{Description} + +The function \code{mp_drop} removes (`drops') a reference to the +multiprecision integer $m$. If there are no more references to the integer, +it is destroyed, as if by \code{mp_destroy} (page~\pageref{fn:mp-destroy}). + +The macro \code{MP_DROP} performs exactly the same action as the +\code{mp_drop} function, except that it uses inline code rather than a +function call, so it's slightly faster but uses a little more code. + +\subsubsection{The \code{mp_split} function and \code{MP_SPLIT} macro} +\label{fn:mp-split} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|mp *mp_split(mp *|$m$|);| \\ +|void MP_SPLIT(mp *|$m$|);| +\end{listinglist} + +\fsec{Description} + +If the integer $m$ has only one reference, the \code{mp_split} function +returns $m$ unchanged; otherwise, a copy is made and returned, and the +reference count of $m$ is decremented. Thus, either way, \code{mp_split} +returns a pointer to an integer with the same value as $m$ and a single +refernce. Thus, the result of \code{mp_split} is therefore safe to modify. + +The macro \code{MP_SPLIT} performs the same action as the \code{mp_split} +function except that it uses inline code rather than a function call, and it +modifies its argument in place rather than returning the new reference. The +macro \code{MP_SPLIT} may evaluate its argument $m$ multiple times. + +\fsec{Returns} + +The function \code{mp_split} returns a pointer to a copy of its argument $m$ +which is safe to modify. + +\subsubsection{The \code{mp_modify} function and \code{MP_MODIFY} macro} +\label{fn:mp-modify} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|mp *mp_modify(mp *|$m$|, size_t |$\sz$|);| \\ +|void MP_MODIFY(mp *|$m$|, size_t |$\sz$|);| +\end{listinglist} + +\fsec{Description} + +The function \code{mp_modify} returns a pointer to a suitable destination $d$ +for a result given a suggested destination $m$ and a required size $\sz$. +The actual behaviour is complicated: + +\begin{itemize} +\item If $m$ is equal to \code{MP_NEW}, or the \code{MP_CONST} flag is set on + $m$, then allocate a new integer $d$ of size $\sz$ by calling + \code{mp_create} (page~\pageref{fn:mp-create}). +\item Otherwise, if $m$ has more than one reference, a reference is removed + asif by \code{mp_drop} (page~\pageref{fn:mp-drop}) and a new integer $d$ of + size $\sz$ is allocated as if by \code{mp_create}. +\item Otherwise, the integer $m$ is extended to $\sz$ words, as if by calling + \code{mp_ensure} (page~\pageref{fn:mp-ensure}), and $d$ is set equal to + $m$. +\end{itemize} + +The resulting integer $d$ is returned from the function. + +The upshot of all of this is that $d$ has exactly one reference, space for +$\sz$ words of data, and no particular value set. Any other references to +the original integer $m$ (whether counted or not) continue to refer to the +same value. The total number of references to $d$ and $m$ after +\code{mp_modify} returns is equal to the initial number of references to $m$ +before the call. + +The macro \code{MP_MODIFY} does the same job using inline code; it sets $m$ +to the new integer $d$ when it's finished. The macro expands to a fairly +large chunk of code. + +\fsec{Returns} + +The function \code{mp_modify} returns the destination integer $d$ as +described above. + + +\subsection{Resizing multiprecision integers} +\label{sec:mp-resize} + +There are a collection of useful functions and macros for changing the size +of a multiprecision integer. + +\subsubsection{The \code{mp_resize} function and \code{MP_RESIZE} macro} +\label{fn:mp-resize} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_resize(mp *|$m$|, size_t |$\sz$|);| \\ +|void MP_RESIZE(mp *|$m$|, size_t |$\sz$|);| +\end{listinglist} + +\fsec{Description} + +The function \code{mp_resize} resizes the array used to hold the value of the +integer $m$ such that it has space for $\sz$ words. No check is made to see +whether $m$'s array is already the correct size. The integer's array limit +pointer \code{vl} is set to point $\sz$ words higher than the base pointer +\code{v}. + +The macro \code{MP_RESIZE} performs exactly the same action as the +\code{mp_resize} function, except that it uses inline code rather than a +function call. It's slightly faster but uses quite a lot more code than the +plain function call. + +\subsubsection{The \code{mp_ensure} function and \code{MP_ENSURE} macro} +\label{fn:mp-ensure} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_ensure(mp *|$m$|, size_t |$\sz$|);| \\ +|void MP_ENSURE(mp *|$m$|, size_t |$\sz$|);| +\end{listinglist} + +\fsec{Description} + +The function \code{mp_ensure} resizes the integer $m$ (as if by calling +\code{mp_resize}) if its array is currently smaller than $\sz$ words; if not, +the array is left alone. The integer's array limit pointer \code{vl} is set +to point $\sz$ words higher than the base pointer \code{v}. + +The macro \code{MP_ENSURE} performs exactly the same action as the +\code{mp_ensure} function, except that it uses inline code rather than a +function call. It's slightly faster but uses considerably more code. + +\subsubsection{The \code{mp_shrink} function and \code{MP_SHRINK} macro} +\label{fn:mp-shrink} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_shrink(mp *|$m$|);| \\ +|void MP_SHRINK(mp *|$m$|);| +\end{listinglist} + +\fsec{Description} + +The function \code{mp_shrink} shrinks the representation of the integer $m$. +It lowers the integer's array limit pointer so that the most significant word +in the representation is nonzero. This improves the efficiency of arithmetic +operations on $m$. + +Note that shrinking an integer doesn't release any memory. Use +\code{mp_minimize} (below) for that. + +The macro \code{MP_SHRINK} performs exactly the same operation as +\code{mp_shrink} using inline code rather than a function call. + +\subsubsection{The \code{mp_minimize} function} +\label{fn:mp-minimize} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_minimize(mp *|$m$|);| +\end{listinglist} + +\fsec{Description} + +Minimizes the amount of memory used by the represenation of the integer $m$. +This isn't usually useful unless $m$ is going to remain constant for a long +time, or has become extremely large for some reason. + + +\subsection{Bit-scanning} +\label{sec:mp-scan} + +\subsection{Loading and storing} +\label{sec:mp-io} + +\subsection{Simple arithmetic} +\label{sec:mp-arith} + +\subsection{More advanced algorithms} +\label{sec:mp-adv} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "catacomb" +%%% End: