chiark / gitweb /
Embryonic library reference manual.
[catacomb] / manual / mp-mp.tex
1 %%% -*-latex-*-
2
3 \section{High-level multiprecision integer represention}
4 \label{sec:mp}
5
6 The high-level interface to multiprecision integers is exported by the header
7 file \hdr{<catacomb/mp.h>}.
8
9
10 \subsection{The \code{mp} structure}
11 \label{sec:mp-struct}
12
13 At the high level, a multiprecision integer is represented as an object of
14 type \code{mp}.  Most of the time, programs use pointers to \code{mp} objects
15 which have been dynamically allocated.  (See \code{mp_build},
16 page~\pageref{fn:mp-build}, for the exception to this rule.)
17
18 The \code{mp} type is a structure.  Some of the members are considered
19 internal to the implementation.  However, the following may be used by client
20 programs:
21 \begin{description}
22   \def\makelabel#1{\code{#1}\hfil}
23 \item[mpw *v, *vl] The base and limit of the multiprecision
24   integer array.
25 \item[unsigned f] Various flags describing the current state of the integer.
26 \end{description}
27 Other members are used for keeping track of how much memory has been
28 allocated to the number and for managing the reference counting system.
29 These members should not be accessed directly by application code.  None of
30 the structure members should be modified directly.
31
32 The following flags are defined:
33 \begin{description*}
34   \let\makelabel\code
35 \item[MP_NEG] The integer is negative.
36 \item[MP_BURN] Clear the integer's storage after use.
37 \item[MP_CONST] The integer may not be altered or freed.
38 \item[MP_UNDEF] The integer currently has no interesting value.
39 \item[MP_DESTROYED] The integer has been destroyed.
40 \end{description*}
41
42 The \code{MP_BURN} flag is inherited by the results of calculations.  Thus,
43 setting the flag on a value causes it and all other values calculated from it
44 to be destroyed after use.\footnote{%
45   There are currently a small number of places where the \code{MP_BURN} flag
46   may be lost from a result.  These usually result from performing complex
47   calculations with degenerate arguments (e.g., computing a GCD with zero).
48   Fixing this is not a high priority.} %
49
50 The \code{MP_DESTROYED} flag is used by \code{mp_destroy}
51 (page~\pageref{fn:mp-destroy}) to trap attempts to destroy the same integer
52 more than once, which can otherwise lead to confusing bugs.
53
54
55 \subsubsection{The \code{MP_LEN} macro}
56 \label{fn:MP-LEN}
57
58 \fsec{Synopsis}
59
60 \begin{listinglist}
61 |#include <catacomb/mp.h>| \\
62 |ptrdiff_t MP_LEN(const mp *|$m$|);|
63 \end{listinglist}
64
65 \fsec{Returns}
66
67 The number of words used in the representation of the integer $m$.  Note that
68 the argument $m$ may be evaluated multiple times by this macro.
69
70
71 \subsubsection{The \code{mp_burn} function}
72 \label{fn:mp-burn}
73
74 \fsec{Synopsis}
75
76 \begin{listinglist}
77 |#include <catacomb/mp.h>| \\
78 |void mp_burn(mp *|$m$|);|
79 \end{listinglist}
80
81 \fsec{Description}
82
83 Sets the \code{MP_BURN} flag on the integer $m$.  Whenever memory associated
84 with $m$, or results derived from it, is deallocated, it is overwritten with
85 zeros to prevent traces being found in swap files or core dumps.
86
87
88 \subsection{Multiprecision integer constants}
89 \label{sec:mp-const}
90
91 There are a few commonly-used multiprecision integer constants provided.  All
92 are declared in \hdr{<catacomb/mp.h>}:
93
94 \begin{tabular}[C]
95   {| >{\ttfamily}l | Mr @{\extracolsep{0pt plus 10000fill}\hskip\tabcolsep}
96   | c @{\extracolsep{0pt}} | >{\ttfamily}l | Mr |}         \hlx{c{1,2,4,5}v}
97   \multicolumn{1}{|c|}{\textbf{Constant}} &
98   \multicolumn{1}{c|}{\textbf{Value}} & \qquad &
99   \multicolumn{1}{c|}{\textbf{Constant}} &
100   \multicolumn{1}{c|}{\textbf{Value}}                   \\ \hlx{vc{1,2,4,5}v}
101   MP_ZERO       & 0     && MP_FOUR       & 4            \\
102   MP_ONE        & 1     && MP_FIVE       & 5            \\
103   MP_TWO        & 2     && MP_TEN        & 10           \\
104   MP_THREE      & 3     && MP_MONE       & -1           \\ \hlx{vc{1,2,4,5}}
105 \end{tabular}
106 \goodbreak
107
108 All of the multiprecision constants are actually pointers to the real
109 values.  All have the \code{MP_CONST} flag set, so they cannot be modified or
110 destroyed.
111
112
113 \subsection{Creation and destruction}
114 \label{sec:mp-create}
115
116 Multiprecision integers are reference counted; i.e., each \code{mp} remembers
117 how many references there are to it, and is destroyed only when the last
118 reference disappears.
119
120 New multiprecision integers are created using the functions \code{mp_create}
121 (page~\pageref{fn:mp-create}) or \code{mp_build}
122 (page~\pageref{fn:mp-build}).  A newly created integer has one reference.
123 Additional references are returned by the function \code{mp_copy}
124 (page~\pageref{fn:mp-copy}).  A reference may be removed from an integer by
125 calling \code{mp_drop} (page~\pageref{fn:mp-drop}).
126
127 It isn't usually a good idea to modify an integer to which there are multiple
128 references: the owners of the other references will usually react badly if
129 their number has changed.  A modifiable copy may be made of an integer using
130 the \code{mp_split} function (page~\pageref{fn:mp-split}).  If there are no
131 other references, the integer is returned unchanged; otherwise a real copy is
132 made and returned, and the number of references to the original is
133 decremented by one.
134
135 Most of the arithmetic functions allow the caller to state a preferred
136 location for the result.  This may either be an existing integer or a
137 completely new one, requested by the special value \code{MP_NEW}.  This
138 behaviour is provided by the \code{mp_modify} function
139 (page~\pageref{fn:mp-modify}).
140
141 Note that functions may not actually use the location requested, although if
142 it decides not to overwrite the requested destination, a reference to it is
143 removed.
144
145
146 \subsubsection{The \code{mp_create} function}
147 \label{fn:mp-create}
148
149 \fsec{Synopsis}
150
151 \begin{listinglist}
152 |#include <catacomb/mp.h>| \\
153 |mp *mp_create(size_t |$\sz$|);|
154 \end{listinglist}
155
156 \fsec{Description}
157
158 Allocates a new multiprecision integer, with at least $\sz$ words of storage
159 available for its representation.  The flag \code{MP_UNDEF} is set initially;
160 the other flags are cleared.  The integer's array limit pointer \code{vl} is
161 set to be $\sz$ higher than the base pointer \code{v}.
162
163 \fsec{Returns}
164
165 A pointer to a newly allocated multiprecision integer.
166
167 \subsubsection{The \code{mp_destroy} function}
168 \label{fn:mp-destroy}
169
170 \fsec{Synopsis}
171
172 \begin{listinglist}
173 |#include <catacomb/mp.h>| \\
174 |void mp_destroy(mp *|$m$|);|
175 \end{listinglist}
176
177 \fsec{Description}
178
179 Destroys the multiprecision integer $m$.  All resouces allocated to the
180 integer are freed.  It's most unusual for this to be the function you want:
181 most of the time \code{mp_drop} (page~\pageref{fn:mp-drop}) is much more
182 useful.
183
184 If compiled with debugging support, the \code{mp_destroy} function will abort
185 if requested to destroy an integer whose \code{MP_CONST} or
186 \code{MP_DESTROYED} flags are set.
187
188 \subsubsection{The \code{mp_build} function}
189 \label{fn:mp-build}
190
191 \fsec{Synopsis}
192
193 \begin{listinglist}
194 |#include <catacomb/mp.h>| \\
195 |void mp_build(mp *|$m$|, mpw *|$v$|, mpw *|$\vl$|);|
196 \end{listinglist}
197
198 \fsec{Description}
199
200 Creates a constant multiprecision integer from an array of \code{mpw} words.
201 Storage for the \code{mp} object and the array is provided by the user --
202 \code{mp_build} allocates no memory.  Conversely, it's safe to dispose of the
203 \code{mp} block and \code{mpw} array at any time, as long as there are no
204 live references to them.
205
206 The \code{mp_build} function is particularly useful for constructing small
207 multiprecision integers, and for addressing parts of other integers.  For
208 example, if $x$ is a multiprecision integer, then
209 \begin{listing}
210 mp_build(&m, x->v + 5, x->vl);
211 \end{listing}
212 sets $m$ equal to $\lfloor x / 2^{5 \cdot \code{MPW_BITS}} \rfloor$ without
213 copying any data.\footnote{%
214   This technique is used in the implementation of Barrett reduction
215   (page~\pageref{sec:mp-barrett}), for example.  See the source file
216   \code{mpbarrett.c} for details.} %
217
218 \subsubsection{The \code{mp_copy} function and \code{MP_COPY} macro}
219 \label{fn:mp-copy}
220
221 \fsec{Synopsis}
222
223 \begin{listinglist}
224 |#include <catacomb/mp.h>| \\
225 |mp *mp_copy(mp *|$m$|);| \\
226 |mp *MP_COPY(mp *|$m$|);|
227 \end{listinglist}
228
229 \fsec{Description}
230
231 The function \code{mp_copy} adds a reference to the multiprecision integer
232 $m$.  The integer will not be destroyed until all references to it have been
233 dropped.
234
235 The macro \code{MP_COPY} performs exactly the same action as the
236 \code{mp_copy} function, except that it uses inline code rather than a
237 function call.  It's probably smaller and faster than the function call too.
238
239 \fsec{Returns}
240
241 The address of the new reference.  This will usually be the same as the
242 original argument $m$.
243
244 \subsubsection{The \code{mp_drop} function and \code{MP_DROP} macro}
245 \label{fn:mp-drop}
246
247 \fsec{Synopsis}
248
249 \begin{listinglist}
250 |#include <catacomb/mp.h>| \\
251 |void mp_drop(mp *|$m$|);| \\
252 |void MP_DROP(mp *|$m$|);|
253 \end{listinglist}
254
255 \fsec{Description}
256
257 The function \code{mp_drop} removes (`drops') a reference to the
258 multiprecision integer $m$.  If there are no more references to the integer,
259 it is destroyed, as if by \code{mp_destroy} (page~\pageref{fn:mp-destroy}).
260
261 The macro \code{MP_DROP} performs exactly the same action as the
262 \code{mp_drop} function, except that it uses inline code rather than a
263 function call, so it's slightly faster but uses a little more code.
264
265 \subsubsection{The \code{mp_split} function and \code{MP_SPLIT} macro}
266 \label{fn:mp-split}
267
268 \fsec{Synopsis}
269
270 \begin{listinglist}
271 |#include <catacomb/mp.h>| \\
272 |mp *mp_split(mp *|$m$|);| \\
273 |void MP_SPLIT(mp *|$m$|);|
274 \end{listinglist}
275
276 \fsec{Description}
277
278 If the integer $m$ has only one reference, the \code{mp_split} function
279 returns $m$ unchanged; otherwise, a copy is made and returned, and the
280 reference count of $m$ is decremented.  Thus, either way, \code{mp_split}
281 returns a pointer to an integer with the same value as $m$ and a single
282 refernce.  Thus, the result of \code{mp_split} is therefore safe to modify.
283
284 The macro \code{MP_SPLIT} performs the same action as the \code{mp_split}
285 function except that it uses inline code rather than a function call, and it
286 modifies its argument in place rather than returning the new reference.  The
287 macro \code{MP_SPLIT} may evaluate its argument $m$ multiple times.
288
289 \fsec{Returns}
290
291 The function \code{mp_split} returns a pointer to a copy of its argument $m$
292 which is safe to modify.
293
294 \subsubsection{The \code{mp_modify} function and \code{MP_MODIFY} macro}
295 \label{fn:mp-modify}
296
297 \fsec{Synopsis}
298
299 \begin{listinglist}
300 |#include <catacomb/mp.h>| \\
301 |mp *mp_modify(mp *|$m$|, size_t |$\sz$|);| \\
302 |void MP_MODIFY(mp *|$m$|, size_t |$\sz$|);|
303 \end{listinglist}
304
305 \fsec{Description}
306
307 The function \code{mp_modify} returns a pointer to a suitable destination $d$
308 for a result given a suggested destination $m$ and a required size $\sz$.
309 The actual behaviour is complicated:
310
311 \begin{itemize}
312 \item If $m$ is equal to \code{MP_NEW}, or the \code{MP_CONST} flag is set on
313   $m$, then allocate a new integer $d$ of size $\sz$ by calling
314   \code{mp_create} (page~\pageref{fn:mp-create}).
315 \item Otherwise, if $m$ has more than one reference, a reference is removed
316   asif by \code{mp_drop} (page~\pageref{fn:mp-drop}) and a new integer $d$ of
317   size $\sz$ is allocated as if by \code{mp_create}.
318 \item Otherwise, the integer $m$ is extended to $\sz$ words, as if by calling
319   \code{mp_ensure} (page~\pageref{fn:mp-ensure}), and $d$ is set equal to
320   $m$.
321 \end{itemize}
322
323 The resulting integer $d$ is returned from the function.
324
325 The upshot of all of this is that $d$ has exactly one reference, space for
326 $\sz$ words of data, and no particular value set.  Any other references to
327 the original integer $m$ (whether counted or not) continue to refer to the
328 same value.  The total number of references to $d$ and $m$ after
329 \code{mp_modify} returns is equal to the initial number of references to $m$
330 before the call.
331
332 The macro \code{MP_MODIFY} does the same job using inline code; it sets $m$
333 to the new integer $d$ when it's finished.  The macro expands to a fairly
334 large chunk of code.
335
336 \fsec{Returns}
337
338 The function \code{mp_modify} returns the destination integer $d$ as
339 described above.
340
341
342 \subsection{Resizing multiprecision integers}
343 \label{sec:mp-resize}
344
345 There are a collection of useful functions and macros for changing the size
346 of a multiprecision integer.
347
348 \subsubsection{The \code{mp_resize} function and \code{MP_RESIZE} macro}
349 \label{fn:mp-resize}
350
351 \fsec{Synopsis}
352
353 \begin{listinglist}
354 |#include <catacomb/mp.h>| \\
355 |void mp_resize(mp *|$m$|, size_t |$\sz$|);| \\
356 |void MP_RESIZE(mp *|$m$|, size_t |$\sz$|);|
357 \end{listinglist}
358
359 \fsec{Description}
360
361 The function \code{mp_resize} resizes the array used to hold the value of the
362 integer $m$ such that it has space for $\sz$ words.  No check is made to see
363 whether $m$'s array is already the correct size.  The integer's array limit
364 pointer \code{vl} is set to point $\sz$ words higher than the base pointer
365 \code{v}.
366
367 The macro \code{MP_RESIZE} performs exactly the same action as the
368 \code{mp_resize} function, except that it uses inline code rather than a
369 function call.  It's slightly faster but uses quite a lot more code than the
370 plain function call.
371
372 \subsubsection{The \code{mp_ensure} function and \code{MP_ENSURE} macro}
373 \label{fn:mp-ensure}
374
375 \fsec{Synopsis}
376
377 \begin{listinglist}
378 |#include <catacomb/mp.h>| \\
379 |void mp_ensure(mp *|$m$|, size_t |$\sz$|);| \\
380 |void MP_ENSURE(mp *|$m$|, size_t |$\sz$|);|
381 \end{listinglist}
382
383 \fsec{Description}
384
385 The function \code{mp_ensure} resizes the integer $m$ (as if by calling
386 \code{mp_resize}) if its array is currently smaller than $\sz$ words; if not,
387 the array is left alone.  The integer's array limit pointer \code{vl} is set
388 to point $\sz$ words higher than the base pointer \code{v}.
389
390 The macro \code{MP_ENSURE} performs exactly the same action as the
391 \code{mp_ensure} function, except that it uses inline code rather than a
392 function call.  It's slightly faster but uses considerably more code.
393
394 \subsubsection{The \code{mp_shrink} function and \code{MP_SHRINK} macro}
395 \label{fn:mp-shrink}
396
397 \fsec{Synopsis}
398
399 \begin{listinglist}
400 |#include <catacomb/mp.h>| \\
401 |void mp_shrink(mp *|$m$|);| \\
402 |void MP_SHRINK(mp *|$m$|);|
403 \end{listinglist}
404
405 \fsec{Description}
406
407 The function \code{mp_shrink} shrinks the representation of the integer $m$.
408 It lowers the integer's array limit pointer so that the most significant word
409 in the representation is nonzero.  This improves the efficiency of arithmetic
410 operations on $m$.
411
412 Note that shrinking an integer doesn't release any memory.  Use
413 \code{mp_minimize} (below) for that.
414
415 The macro \code{MP_SHRINK} performs exactly the same operation as
416 \code{mp_shrink} using inline code rather than a function call.
417
418 \subsubsection{The \code{mp_minimize} function}
419 \label{fn:mp-minimize}
420
421 \fsec{Synopsis}
422
423 \begin{listinglist}
424 |#include <catacomb/mp.h>| \\
425 |void mp_minimize(mp *|$m$|);|
426 \end{listinglist}
427
428 \fsec{Description}
429
430 Minimizes the amount of memory used by the represenation of the integer $m$.
431 This isn't usually useful unless $m$ is going to remain constant for a long
432 time, or has become extremely large for some reason.
433
434
435 \subsection{Bit-scanning}
436 \label{sec:mp-scan}
437
438 \subsection{Loading and storing}
439 \label{sec:mp-io}
440
441 \subsection{Simple arithmetic}
442 \label{sec:mp-arith}
443
444 \subsection{More advanced algorithms}
445 \label{sec:mp-adv}
446
447 %%% Local Variables: 
448 %%% mode: latex
449 %%% TeX-master: "catacomb"
450 %%% End: