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