3471ebd1 |
1 | %%% -*-latex-*- |
2 | |
3 | \section{Low-level details: MPX} |
4 | \label{sec:mpx} |
5 | |
6 | |
7 | \subsection{Data types for low-level arithmetic} |
8 | |
9 | The header file \hdr{<catacomb/mpw.h>} defines two types, \code{mpw} and |
10 | \code{mpd}, and a collection of macros describing them. |
11 | |
12 | The `multiprecision word' type, \code{mpw}, is an unsigned integer type whose |
13 | representation uses \code{MPW_BITS}. The largest value representable in an |
14 | \code{mpw} is $\code{MPW_MAX} = 2^{\code{MPW_BITS}} - 1$. |
15 | The value of \code{MPW_BITS} is at least 16. Note that, on some |
16 | architectures, an \code{mpw} may be capable of representing values larger |
17 | than \code{MPW_MAX}. The expression \code{MPW($x$)} returns the value of $x |
18 | \bmod \code{MPW_MAX}$ cast to type \code{mpw}. |
19 | |
20 | The `multiprecision doubleword' type, \code{mpd}, is an unsigned integer type |
21 | with at least double the width of \code{mpw}. Hence, an \code{mpd} is |
22 | capable of representing the product of two \code{mpw}s, and is useful when |
23 | performing multiplications and divisions. The constants \code{MPD_BITS} and |
24 | \code{MPD_MAX} are defined to be the number of bits used in the |
25 | representation of an \code{mpd} and the largest value representable in an |
26 | \code{mpd} respectively. |
27 | |
28 | A few macros useful for manipulating \code{mpw}s are defined. |
29 | |
30 | \subsubsection{The \code{MPW} macro} |
31 | \label{fn:MPW} |
32 | |
33 | \fsec{Synopsis} |
34 | |
35 | \begin{listinglist} |
36 | |#include <catacomb/mpw.h>| \\ |
37 | |mpw MPW(|$x$|);| |
38 | \end{listinglist} |
39 | |
40 | \fsec{Returns} |
41 | |
42 | The value of $x \bmod 2^{\code{MPW_BITS}}$, as an \code{mpw}. This is a |
43 | frequently used abbreviation for |(mpw)(|$x$| & MPW_MAX)|. |
44 | |
45 | \subsubsection{The \code{MPWS} macro} |
46 | \label{fn:MPWS} |
47 | |
48 | \fsec{Synopsis} |
49 | |
50 | \begin{listinglist} |
51 | |#include <catacomb/mpw.h>| \\ |
52 | |size_t MPWS(size_t |$n$|);| |
53 | \end{listinglist} |
54 | |
55 | \fsec{Returns} |
56 | |
57 | The number of bytes occupied by an array of $n$ \code{mpw}s (i.e., $n \cdot |
58 | |sizeof(mpw)|$). |
59 | |
60 | \subsubsection{The \code{MPW_RQ} macro} |
61 | \label{fn:MPW-RQ} |
62 | |
63 | \fsec{Synopsis} |
64 | |
65 | \begin{listinglist} |
66 | |#include <catacomb/mpw.h>| \\ |
67 | |size_t MPW_RQ(size_t |$\sz$|);| |
68 | \end{listinglist} |
69 | |
70 | \fsec{Returns} |
71 | |
72 | The number of \code{mpw}s required to represent a multiprecision integer |
73 | occupying $\sz$ octets in an external representation. |
74 | |
75 | |
76 | \subsection{Low-level multiprecision integer representation} |
77 | |
78 | The low-level multiprecision definitions are exported in the header file |
79 | \hdr{<catacomb/mpx.h>}. This header includes \hdr{<catacomb/mpw.h>}, so |
80 | there's usually no need to include it explicitly. |
81 | |
82 | A multiprecision integer is represented as an array of \code{mpw}s, |
83 | least-significant first. The array's bounds are described by a a pair of |
84 | pointers to the array's \emph{base} (i.e., its first element) and |
85 | \emph{limit} (i.e., the location immediately following its last element). |
86 | |
87 | Let $v$ be the base and $\vl$ the limit of a multiprecision integer array. |
88 | The array itself is notated as $v .. \vl$. The array's size in words may be |
89 | computed as $\vl - v$ in the normal C fashion. The integer represented by |
90 | the array, denoted $\mp(v .. \vl)$, is defined to be |
91 | \[ |
92 | \mp(v .. \vl) = |
93 | \sum_{0 \le i < \vl - v} |
94 | 2^{\code{MPW_BITS} \cdot i} v[i] |
95 | \] |
96 | If the array is empty (i.e., $v = \vl$) then the number is zero. If the |
97 | array is empty, or the final word is nonzero, then the representation is said |
98 | to be \emph{shrunken}. Shrunken representations are more efficient, since |
99 | the arithmetic algorithms don't need to consider high-order words which make |
100 | no difference to the final result anyway. |
101 | |
102 | Whenever a result is too large to be represented in the memory allocated for |
103 | it, high-order bits are discarded. Thus, a result written to an array of $k$ |
104 | words is reduced modulo $2^{\code{MPW_BITS} \cdot k}$. |
105 | |
106 | |
107 | \subsection{Low-level macros} |
108 | \label{sec:mpx-macro} |
109 | |
110 | The following macros perform various simple operations useful for |
111 | manipulating multiprecision integers at the MPX level. |
112 | |
113 | \subsubsection{The \code{MPX_SHRINK} macro} |
114 | \label{fn:MPX-SHRINK} |
115 | |
116 | \fsec{Synopsis} |
117 | |
118 | \begin{listinglist} |
119 | |#include <catacomb/mpx.h>| \\ |
120 | |MPX_SHRINK(const mpw *|$v$|, const mpw *|$\vl$|);| |
121 | \end{listinglist} |
122 | |
123 | \fsec{Description} |
124 | |
125 | The \code{MPX_SHRINK} macro reduces the limit $\vl$ of a multiprecision |
126 | integer array so that either $v = \vl$ or $\vl[-1] \ne 0$. The $\vl$ |
127 | argument must be an lvalue, since the macro writes the result back when it |
128 | finishes. |
129 | |
130 | \subsubsection{The \code{MPX_BITS} macro} |
131 | \label{fn:MPX-BITS} |
132 | |
133 | \fsec{Synopsis} |
134 | |
135 | \begin{listinglist} |
136 | |#include <catacomb/mpx.h>| \\ |
137 | |MPX_BITS(unsigned long |$b$|, const mpw *|$v$|, const mpw *|$\vl$|);| |
138 | \end{listinglist} |
139 | |
140 | \fsec{Description} |
141 | |
142 | Determines the smallest number of bits which could represent the number |
143 | $\mp(v .. \vl)$, and writes the answer to $b$, which must therefore be an |
144 | lvalue. The result is zero if the number is zero; otherwise $b$ is the |
145 | largest integer such that |
146 | \[ \mp(v .. \vl) \ge 2^{(b - 1) \bmod \code{MPW_BITS}}.\] |
147 | |
148 | \subsubsection{The \code{MPX_OCTETS} macro} |
149 | \label{fn:MPX-OCTETS} |
150 | |
151 | \fsec{Synopsis} |
152 | |
153 | \begin{listinglist} |
154 | |#include <catacomb/mpx.h>| \\ |
155 | |MPX_OCTETS(size_t |$o$|,| |
156 | |const mpw *|$v$|, const mpw *|$\vl$|);| |
157 | \end{listinglist} |
158 | |
159 | \fsec{Description} |
160 | |
161 | Determines the smallest number of octets which could represent the number |
162 | $\mp(v .. \vl)$, and writes the answer to $o$, which must therefore be an |
163 | lvalue. This is useful for determining appropriate buffer sizes for the |
164 | results of \code{mpx_storel} and \code{mpx_storeb}. |
165 | |
166 | The result $o$ can be calculated from the number of bits $b$ reported by |
167 | \code{MPX_BITS} as $o = \lceil b / 8 \rceil$; the algorithm used by |
168 | \code{MPX_OCTETS} is more efficient than this, however. |
169 | |
170 | \subsubsection{The \code{MPX_COPY} macro} |
171 | \label{fn:MPX-COPY} |
172 | |
173 | \fsec{Synopsis} |
174 | |
175 | \begin{listinglist} |
176 | |#include <catacomb/mpx.h>| \\ |
177 | |MPX_COPY(mpw *|$\dv$|, mpw *|$\dvl$|,| |
178 | |const mpw *|$\av$|, const mpw *|$\avl$|);| |
179 | \end{listinglist} |
180 | |
181 | \fsec{Description} |
182 | |
183 | Copies a multiprecision integer from the source array $\av .. \avl$ to the |
184 | destination array $\dv .. \dvl$. If the destination array is large enough, |
185 | the result is equal to the source; otherwise, high-order bits are discarded |
186 | as usual. |
187 | |
188 | \subsubsection{The \code{MPX_ZERO} macro} |
189 | \label{fn:MPX-ZERO} |
190 | |
191 | \fsec{Synopsis} |
192 | |
193 | \begin{listinglist} |
194 | |#include <catacomb/mpx.h>| \\ |
195 | |MPX_ZERO(mpw *|$v$|, mpw *|$\vl$|);| |
196 | \end{listinglist} |
197 | |
198 | \fsec{Description} |
199 | |
200 | Sets the integer $\mp(v .. \vl)$ to zero. |
201 | |
202 | |
203 | \subsection{Transfer formats: loading and storing} |
204 | \label{sec:mpx-io} |
205 | |
206 | The MPX layer can translate between internal representations of integers as |
207 | arrays of \code{mpw}s and external formats where integers are stored as |
208 | arrays of octets. Both little- and big-endian orders are supported. |
209 | |
210 | If $a_0, a_1, \ldots, a_{k - 1}$ is an array of $k$ octets, with |
211 | $0 \le a_i < 256$ for all $0 \le i < k$, then the number $n$ represented by |
212 | $a$ in little-endian byte order is |
213 | \[ n = \sum_{0 \le i < k} 256^i a_i .\] |
214 | Similarly, the number $n'$ represented by $a$ in big-endian byte order is |
215 | \[ n' = \sum_{0 \le i < k} 256^{k - i - 1} a_i .\] |
216 | |
217 | If, in a store operation, the destination octet array is not large enough to |
218 | represent the number to be stored, high-order octets are discarded; hence, |
219 | the number is reduced modulo $2^{8k}$, where $k$ is the size of the |
220 | destination array in octets. |
221 | |
222 | Two useful macros help when working out how much memory is needed for |
223 | translation between internal and transfer formats for multiprecision |
224 | integers. The macro \code{MPX_OCTETS} (page~\pageref{fn:MPX-OCTETS}) |
225 | calculates the smallest octet array size which can represent a multiprecision |
226 | integer. The macro \code{MPW_RQ} (page~\pageref{fn:MPW-RQ}) calculates the |
227 | smallest \code{mpw} array which can represent a multiprecision integer held |
228 | in an octet array of a particular size. |
229 | |
230 | \subsubsection{The \code{mpx_storel} function} |
231 | \label{fn:mpx-storel} |
232 | |
233 | \fsec{Synopsis} |
234 | |
235 | \begin{listinglist} |
236 | |#include <catacomb/mpx.h>| \\ |
237 | |void mpx_storel(const mpw *|$v$|, const mpw *|$\vl$|,| |
238 | |void *|$p$|, size_t |$\sz$|);| |
239 | \end{listinglist} |
240 | |
241 | \fsec{Description} |
242 | |
243 | Stores the number held in the array $v .. \vl$ to the array of $\sz$ octets |
244 | starting at address $p$ in little-endian byte order (i.e., least significant |
245 | byte first). |
246 | |
247 | \subsubsection{The \code{mpx_loadl} function} |
248 | \label{fn:mpx-loadl} |
249 | |
250 | \fsec{Synopsis} |
251 | |
252 | \begin{listinglist} |
253 | |#include <catacomb/mpx.h>| \\ |
254 | |void mpx_loadl(mpw *|$v$|, mpw *|$\vl$|,| |
255 | |const void *|$p$|, size_t |$\sz$|);| |
256 | \end{listinglist} |
257 | |
258 | \fsec{Description} |
259 | |
260 | Loads into the array $v .. \vl$ the number represented in the array of $\sz$ |
261 | octets starting at address $p$ in little-endian byte order (i.e., least |
262 | significant byte first). |
263 | |
264 | \subsubsection{The \code{mpx_storeb} function} |
265 | \label{fn:mpx-storeb} |
266 | |
267 | \fsec{Synopsis} |
268 | |
269 | \begin{listinglist} |
270 | |#include <catacomb/mpx.h>| \\ |
271 | |void mpx_storeb(const mpw *|$v$|, const mpw *|$\vl$|,| |
272 | |void *|$p$|, size_t |$\sz$|);| |
273 | \end{listinglist} |
274 | |
275 | \fsec{Description} |
276 | |
277 | Stores the number held in the array $v .. \vl$ to the array of $\sz$ octets |
278 | starting at address $p$ in big-endian byte order (i.e., least significant |
279 | byte last). |
280 | |
281 | \subsubsection{The \code{mpx_loadb} function} |
282 | \label{fn:mpx-loadb} |
283 | |
284 | \fsec{Synopsis} |
285 | |
286 | \begin{listinglist} |
287 | |#include <catacomb/mpx.h>| \\ |
288 | |void mpx_loadb(mpw *|$v$|, mpw *|$\vl$|,| |
289 | |const void *|$p$|, size_t |$\sz$|);| |
290 | \end{listinglist} |
291 | |
292 | \fsec{Description} |
293 | |
294 | Loads into the array $v .. \vl$ the number represented in the array of $\sz$ |
295 | octets starting at address $p$ in big-endian byte order (i.e., least |
296 | significant byte last). |
297 | |
298 | |
299 | \subsection{Bit shifting operations} |
300 | \label{sec:mpx-shift} |
301 | |
302 | The MPX layer provides functions for efficient multiplication and division of |
303 | multiprecision integers by powers of two, performed simply by shifting the |
304 | binary representation left or right by a number of bits. Shifts by one bit |
305 | and by a multiple of \code{MPW_BITS} are particularly fast. |
306 | |
307 | There are two shift functions, one for left shifts (multiplications) and one |
308 | for right shifts (divisions). Each function is passed an array containing |
309 | the number to be shifted, a destination array for the result (which may be |
310 | the source array), and the number of bits to be shifted as an unsigned |
311 | integer. |
312 | |
313 | |
314 | \subsubsection{The \code{mpx_lsl} function} |
315 | \label{fn:mpx-lsl} |
316 | |
317 | \fsec{Synopsis} |
318 | |
319 | \begin{listinglist} |
320 | \begin{tabbing} |
321 | |#include <catacomb/mpx.h>| \\ |
322 | |void mpx_lsl(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
323 | \>|const mpw *|$\av$|, const mpw *|$\avl$|, size_t |$n$|);| |
324 | \end{tabbing} |
325 | \end{listinglist} |
326 | |
327 | \fsec{Description} |
328 | |
329 | Stores in $\dv .. \dvl$ the result of shifting $\mp(\av .. \avl)$ left by $n$ |
330 | bits (i.e., multiplying it by $2^n$). |
331 | |
332 | \subsubsection{The \code{mpx_lsr} function} |
333 | \label{fn:mpx-lsr} |
334 | |
335 | \fsec{Synopsis} |
336 | |
337 | \begin{listinglist} |
338 | \begin{tabbing} |
339 | |#include <catacomb/mpx.h>| \\ |
340 | |void mpx_lsr(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
341 | \>|const mpw *|$\av$|, const mpw *|$\avl$|, size_t |$n$|);| |
342 | \end{tabbing} |
343 | \end{listinglist} |
344 | |
345 | \fsec{Description} |
346 | |
347 | Stores in $\dv .. \dvl$ the result of shifting $\mp(\av .. \avl)$ right by |
348 | $n$ bits (i.e., dividing it by $2^n$, rounding towards zero). |
349 | |
350 | |
351 | \subsection{Low level arithmetic} |
352 | |
353 | The remaining functions perform standard arithmetic operations on large |
354 | integers. The form for the arguments is fairly well-standardized: |
355 | destination arrays are given first, followed by the source arrays in the |
356 | conventional order. (This ordering reflects the usual order in a C |
357 | assignment expression, the \code{strcpy} and \code{memcpy} functions, and the |
358 | order of operands in many assembly languages.) |
359 | |
360 | Some functions allow the destination array to be the same as one (or both) |
361 | source arrays; others forbid this. Under no circumstances may the |
362 | destination partially overlap the sources. |
363 | |
364 | |
365 | \subsubsection{The \code{mpx_2c} function} |
366 | \label{fn:mpx-2c} |
367 | |
368 | \fsec{Synopsis} |
369 | |
370 | \begin{listinglist} |
371 | |#include <catacomb/mpx.h>| \\ |
372 | |void mpx_2c(mpw *|$\dv$|, mpw *|$\dvl$|,| |
373 | |const mpw *|$v$|, const mpw *|$\vl$|);| |
374 | \end{listinglist} |
375 | |
376 | \fsec{Description} |
377 | |
378 | Computes the two's complement of the number $\mp(v .. \vl)$ and stores it in |
379 | $\dv .. \dvl$. The two arrays $v .. \vl$ and $\dv .. \dvl$ may be the same. |
380 | |
381 | \subsubsection{The \code{mpx_ucmp} function and \code{MPX_UCMP} macro} |
382 | \label{fn:mpx-ucmp} |
383 | |
384 | \fsec{Synopsis} |
385 | \begin{listinglist} |
386 | \begin{tabbing} |
387 | |#include <catacomb/mpx.h>| \\ |
388 | |int mpx_ucmp(|\=|const mpw *|$\av$|, const mpw *|$\avl$|,| \\ |
389 | \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| \\ |
390 | |int MPX_UCMP(|\=|const mpw *|$\av$|, const mpw *|$\avl$|, |\synt{rel-op}|,| |
391 | \\ \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| |
392 | \end{tabbing} |
393 | \end{listinglist} |
394 | |
395 | \fsec{Description} |
396 | |
397 | The function \code{mpx_ucmp} performs an unsigned comparison of two unsigned |
398 | multiprecision integers $a$ and $b$, passed in the arrays $\av .. \avl$ and |
399 | $\bv .. \bvl$ respectively. |
400 | |
401 | The macro \code{MPX_UCMP} provides a slightly more readable interface for |
402 | comparing integers. The \synt{rel-op} may be any C relational operator |
403 | (e.g., |!=|, or |<=|). The macro tests whether |
404 | $a \mathrel{\synt{rel-op}} b$. |
405 | |
406 | \fsec{Returns} |
407 | |
408 | The function \code{mpx_ucmp} returns a value less then, equal to, or |
409 | greater than zero depending on whether $a$ is less than, equal to or greater |
410 | than $b$. |
411 | |
412 | The macro \code{MPX_UCMP} returns a nonzero result if $a |
413 | \mathrel{\synt{rel-op}} b$ is true, and zero if false. |
414 | |
415 | \subsubsection{The \code{mpx_uadd} function} |
416 | \label{fn:mpx-uadd} |
417 | |
418 | \fsec{Synopsis} |
419 | |
420 | \begin{listinglist} |
421 | \begin{tabbing} |
422 | |#include <catacomb/mpx.h>| \\ |
423 | |void mpx_uadd(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| |
424 | |const mpw *|$\av$|, const mpw *|$\avl$|,| \\ |
425 | \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| |
426 | \end{tabbing} |
427 | \end{listinglist} |
428 | |
429 | \fsec{Description} |
430 | |
431 | Adds two multiprecision integers. The sum of the two arguments |
432 | $\mp(\av .. \avl) + \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$. The |
433 | destination array may be equal to either or both source arrays.\footnote{% |
434 | Adding a number to itself is a poor way of doubling. A call to |
435 | \code{mpx_lsl} (page~\pageref{fn:mpx-lsl}) is much more efficient.} % |
436 | |
437 | \subsubsection{The \code{mpx_uaddn} function and \code{MPX_UADDN} macro} |
438 | \label{fn:mpx-uaddn} |
439 | |
440 | \fsec{Synopsis} |
441 | |
442 | \begin{listinglist} |
443 | |#include <catacomb/mpx.h>| \\ |
444 | |void mpx_uaddn(mpw *|$\dv$|, mpw *|$\dvl$|, mpw |$n$|);| \\ |
445 | |void MPX_UADDN(mpw *|$\dv$|, mpw *|$\dvl$|, mpw |$n$|);| |
446 | \end{listinglist} |
447 | |
448 | \fsec{Description} |
449 | |
450 | The function \code{mpx_uaddn} adds a small integer $n$ (expressed as a single |
451 | \code{mpw}) to the multiprecision integer held in $\dv .. \dvl$. |
452 | |
453 | The macro \code{MPX_UADDN} performs exactly the same operation, but uses |
454 | inline code rather than calling a function. |
455 | |
456 | \subsubsection{The \code{mpx_usub} function} |
457 | \label{fn:mpx-usub} |
458 | |
459 | \fsec{Synopsis} |
460 | |
461 | \begin{listinglist} |
462 | \begin{tabbing} |
463 | |#include <catacomb/mpx.h>| \\ |
464 | |void mpx_usub(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| |
465 | |const mpw *|$\av$|, const mpw *|$\avl$|,| \\ |
466 | \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| |
467 | \end{tabbing} |
468 | \end{listinglist} |
469 | |
470 | \fsec{Description} |
471 | |
472 | Subtracts one multiprecision integer from another. The difference of the two |
473 | arguments $\mp(\av .. \avl) - \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$. |
474 | The destination array may be equal to either or both source |
475 | arrays.\footnote{% |
476 | Subtracting a number from itself is a particularly poor way of clearing an |
477 | integer to zero. A call to \code{MPX_ZERO} (page~\pageref{fn:MPX-ZERO}) is |
478 | much more efficient.} % |
479 | |
480 | Because overly large results are truncated to fit the destination array, if |
481 | the second argument is larger than the first, a two's-complement result is |
482 | obtained. |
483 | |
484 | \subsubsection{The \code{mpx_usubn} function and \code{MPX_USUBN} macro} |
485 | \label{fn:mpx-usubn} |
486 | |
487 | \fsec{Synopsis} |
488 | |
489 | \begin{listinglist} |
490 | |#include <catacomb/mpx.h>| \\ |
491 | |void mpx_usubn(mpw *|$\dv$|, mpw *|$\dvl$|, mpw |$n$|);| \\ |
492 | |void MPX_USUBN(mpw *|$\dv$|, mpw *|$\dvl$|, mpw |$n$|);| |
493 | \end{listinglist} |
494 | |
495 | \fsec{Description} |
496 | |
497 | The function \code{mpx_usubn} subtracts a small integer $n$ (expressed as a |
498 | single \code{mpw}) from the multiprecision integer held in $\dv .. \dvl$. |
499 | |
500 | The macro \code{MPX_USUBN} performs exactly the same operation, but uses |
501 | inline code rather than calling a function. |
502 | |
503 | \subsubsection{The \code{mpx_umul} function} |
504 | \label{fn:mpx-umul} |
505 | |
506 | \fsec{Synopsis} |
507 | |
508 | \begin{listinglist} |
509 | \begin{tabbing} |
510 | |#include <catacomb/mpx.h>| \\ |
511 | |void mpx_umul(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| |
512 | |const mpw *|$\av$|, const mpw *|$\avl$|,| \\ |
513 | \>|const mpw *|$\bv$|, const mpw *|$\bvl$|);| |
514 | \end{tabbing} |
515 | \end{listinglist} |
516 | |
517 | \fsec{Description} |
518 | |
519 | Multiplies two multiprecision integers. The product of the two arguments |
520 | $\mp(\av .. \avl) \times \mp(\bv .. \bvl)$ is stored in $\dv .. \dvl$. The |
521 | destination array may not be equal to either source array. |
522 | |
523 | \subsubsection{The \code{mpx_umuln} function and \code{MPX_UMULN} macro} |
524 | \label{fn:mpx-umuln} |
525 | |
526 | \fsec{Synopsis} |
527 | |
528 | \begin{listinglist} |
529 | \begin{tabbing} |
530 | |#include <catacomb/mpx.h>| \\ |
531 | |void mpx_umuln(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
532 | \> |const mpw *|$\av$|, const mpw *|$\avl$|, mpw |$n$|);| \\ |
533 | |void MPX_UMULN(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
534 | \> |const mpw *|$\av$|, const mpw *|$\avl$|, mpw |$n$|);| |
535 | \end{tabbing} |
536 | \end{listinglist} |
537 | |
538 | \fsec{Description} |
539 | |
540 | The function \code{mpx_umuln} multiplies the multiprecision integer passed in |
541 | $\av .. \avl$ by a small integer $n$ (expressed as a single \code{mpw}), |
542 | writing the product $n \cdot \mp(\av .. \avl)$ to the destination array $\dv |
543 | .. \dvl$. The destination array may be equal to the source array $\av |
544 | .. \avl$. |
545 | |
546 | The macro \code{MPX_UMULN} performs exactly the same operation, but uses |
547 | inline code rather than calling a function. |
548 | |
549 | \subsubsection{The \code{mpx_umlan} function and \code{MPX_UMLAN} macro} |
550 | \label{fn:mpx-umlan} |
551 | |
552 | \fsec{Synopsis} |
553 | |
554 | \begin{listinglist} |
555 | \begin{tabbing} |
556 | |#include <catacomb/mpx.h>| \\* |
557 | |void mpx_umlan(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\* |
558 | \> |const mpw *|$\av$|, const mpw *|$\avl$|, mpw |$n$|);| \\ |
559 | |void MPX_UMLAN(|\=|mpw *|$\dv$|, mpw *|$\dvl$|,| \\ |
560 | \> |const mpw *|$\av$|, const mpw *|$\avl$|, mpw |$n$|);| |
561 | \end{tabbing} |
562 | \end{listinglist} |
563 | |
564 | \fsec{Description} |
565 | |
566 | The function \code{mpx_umlan} multiplies the multiprecision integer passed in |
567 | $\av .. \avl$ by a small integer $n$ (expressed as a single \code{mpw}), and |
568 | adds it to the value already stored in the destination array $\dv .. \dvl$. |
569 | The destination array may be equal to the source array $\av .. \avl$, |
570 | although this isn't very useful. |
571 | |
572 | The macro \code{MPX_UMLAN} performs exactly the same operation, but uses |
573 | inline code rather than calling a function. |
574 | |
575 | \subsubsection{The \code{mpx_usqr} function} |
576 | \label{fn:mpx-usqr} |
577 | |
578 | \fsec{Synopsis} |
579 | |
580 | \begin{listinglist} |
581 | |#include <catacomb/mpx.h>| \\ |
582 | |void mpx_usqr(mpw *|$\dv$|, mpw *|$\dvl$|,| |
583 | |const mpw *|$\av$|, const mpw *|$\avl$|);| |
584 | \end{listinglist} |
585 | |
586 | \fsec{Description} |
587 | |
588 | Squares a multiprecision integer. The result $\mp(\av .. \avl)^2$ is stored |
589 | in $\dv .. \dvl$. The destination array may not be equal to the source |
590 | array. |
591 | |
592 | Squaring a number is approximately twice as fast as multiplying a number by |
593 | itself. |
594 | |
595 | \subsubsection{The \code{mpx_udiv} function} |
596 | \label{fn:mpx-udiv} |
597 | |
598 | \fsec{Synopsis} |
599 | |
600 | \begin{listinglist} |
601 | \begin{tabbing} |
602 | |#include <catacomb/mpx.h>| \\ |
603 | |void mpx_udiv(|\=|mpw *|$\qv$|, mpw *|$\qvl$|, mpw *|$\rv$|, mpw *|$\rvl$|,| |
604 | \\ \>|const mpw *|$\dv$|, const mpw *|$\dvl$|,| |
605 | |mpw *|$\mathit{sv}$|, mpw *|$\mathit{svl}$|);| |
606 | \end{tabbing} |
607 | \end{listinglist} |
608 | |
609 | \fsec{Description} |
610 | |
611 | Calculates the quotient and remainder when one multiprecision integer is |
612 | divided by another. |
613 | |
614 | The calling convention is slightly strange. The dividend and divisor are |
615 | passed in the arrays $\rv .. \rvl$ and $\dv .. \dvl$ respectively. The |
616 | quotient is written to the array $\qv .. \qvl$; the remainder is left in $\rv |
617 | .. \rvl$. |
618 | |
619 | The division function requires some workspace. The `scratch' array |
620 | $\mathit{sv} .. \mathit{svl}$ must be at least one word longer than the |
621 | divisor array $\dv .. \dvl$. The scratch array'sfinal contents are not |
622 | useful. Also, the remainder array $\rv .. \rvl$ must have at least two |
623 | words' headroom. |
624 | |
625 | \unverb\| |
626 | Given a dividend $x$ and a divisor $y$, the function calculates a quotient |
627 | $q$ and remainder $r$ such that $q = \lfloor x / y \rfloor$ and $x = qy + r$. |
628 | In particular, this definition implies that $r$ has the same sign as $y$, |
629 | which is a useful property when performing modular reductions. |
630 | \shortverb\| |
631 | |
632 | %%% Local Variables: |
633 | %%% mode: latex |
634 | %%% TeX-master: "catacomb" |
635 | %%% End: |