The last of the three arithmetic interfaces, MP, exports functions that implement multiple-precision arithmetic on unsigned and two’s-complement integers. Like XP, MP reveals its representation for n-bit integers, and the MP functions operate on integers of a given size. Unlike XP, the lengths of MP’s integers are given in bits, and MP’s functions implement both signed and unsigned arithmetic. Like the AP functions, the MP functions enforce the usual suite of checked runtime errors.
MP is intended for applications that need extended-precision arithmetic, but want finer control over allocations, need both unsigned and signed operations, or must mimic two’s-complement n-bit arithmetic. Examples include compilers and applications that use encryption. Some modern encryption algorithms involve manipulating fixed-precision integers with hundreds of digits.
Some compilers must use multiple-precision integers. A cross-compiler runs on platform X and generates code for platform Y. If Y has integers bigger than X, the compiler can use MP to manipulate Y-sized integers. Also, compilers must use multiple-precision arithmetic to convert floating-point constants to the closest floating-point values they specify.
The MP interface is large — 49 functions and two exceptions — because it exports a complete suite of arithmetic functions on n-bit signed and unsigned integers.
<mp.h>≡ #ifndef MP_INCLUDED #define MP_INCLUDED #include <stdarg.h> #include <stddef.h> #include "except.h" #define T MP_T typedef unsigned char *T; <exported exceptions 359> <exported functions 358> #undef T #endif
Like XP, MP reveals that an n-bit integer is represented by ⌈n/8⌉ bytes, stored least significant byte first. MP uses the two’s-complement representation for signed integers; bit n − 1 is the sign bit.
Unlike the XP functions, the MP functions implement the usual checked runtime errors; for example, it is a checked runtime error to pass a null MP_T to any function in this interface. However, it is an unchecked runtime error to pass an MP_T that is too small to hold an n-bit integer.
MP is initialized automatically to do arithmetic on 32-bit integers. Calling
<exported functions 358>≡
extern int MP_set(int n);changes MP so that subsequent calls do n-bit arithmetic. MP_set returns the previous size. It is a checked runtime error for n to be less than two. Once initialized, most applications use only one size of extended integer. For example, a cross-compiler might manipulate constants using 128-bit arithmetic. This design caters to these kinds of applications; it simplifies the use of the other MP functions, and simplifies their argument lists as well. Omitting n is the obvious simplification, but a more important simplification is that there are no restrictions on the source and destination arguments: The same MP_T can always appear as both a source and a destination. Eliminating these restrictions is possible because the temporary space needed by some of the functions depends only on n and thus can be allocated once by MP_set.
This design also avoids allocations. MP_set can raise Mem_Failed, but only four of the other 48 MP functions do allocations. One of those is
<exported functions 358>+≡
extern T MP_new(unsigned long u);which allocates an MP_T of the appropriate size, initializes it to u, and returns it.
<exported functions 358>+≡
extern T MP_fromint (T z, long v);
extern T MP_fromintu(T z, unsigned long u);set z to v or u and return z. MP_new, MP_fromint, and MP_fromintu raise
<exported exceptions 359>≡
extern const Except_T MP_Overflow;if u or v don’t fit in n bits. MP_new and MP_fromintu raise MP_Overflow when u exceeds 2n − 1, and MP_fromint raises MP_Overflow when v is less than −2n − 1 or exceeds 2n − 1 − 1.
All of the MP functions compute their results before they raise an exception. The extraneous bits are simply discarded. For example,
MP_T z; MP_set(8); z = MP_new(0); MP_fromintu(z, 0xFFF);
sets z to 0xFF and raises MP_Overflow. Clients can use a TRY-EXCEPT statement to ignore the exception when that is the appropriate action. For example,
MP_T z;
MP_set(8);
z = MP_new(0);
TRY
MP_fromintu(z, 0xFFF);
EXCEPT(MP_Overflow) ;
END_TRY;sets z to 0xFF and discards the overflow exception.
This convention does not apply to
<exported functions 358>+≡
extern unsigned long MP_tointu(T x);
extern long MP_toint (T x);which return the value of x as a signed or unsigned long. These functions raise MP_Overflow when x doesn’t fit in the return type, and there’s no way to capture the result when an exception occurs. Clients can use
<exported functions 358>+≡
extern T MP_cvt (int m, T z, T x);
extern T MP_cvtu(int m, T z, T x);to convert x to an MP_T of the appropriate size. MP_cvt and MP_cvtu convert x to an m-bit signed or unsigned MP_T in z and return z. They raise MP_Overflow when x doesn’t fit in the m-bit destination, but they set z before doing so. Thus,
unsigned char z[sizeof (unsigned)];
TRY
MP_cvtu(8*sizeof (unsigned), z, x);
EXCEPT(MP_Overflow) ;
END_TRY;sets z to the least significant 8·sizeof (unsigned) bits from x regardless of the size of x.
When m exceeds the number of bits in x, MP_cvtu extends the result with zeros, and MP_cvt extends the result with x’s sign bit. It is a checked runtime error for m to be less than two, and it is an unchecked runtime error for z to be too small to hold an m-bit integer.
The arithmetic functions are
<exported functions 358>+≡
extern T MP_add (T z, T x, T y);
extern T MP_sub (T z, T x, T y);
extern T MP_mul (T z, T x, T y);
extern T MP_div (T z, T x, T y);
extern T MP_mod (T z, T x, T y);
extern T MP_neg (T z, T x);
extern T MP_addu(T z, T x, T y);
extern T MP_subu(T z, T x, T y);
extern T MP_mulu(T z, T x, T y);
extern T MP_divu(T z, T x, T y);
extern T MP_modu(T z, T x, T y);Those with names ending in u do unsigned arithmetic; the others do two’s-complement signed arithmetic. Overflow semantics are the only difference between the unsigned and signed operations, as detailed below. MP_add, MP_sub, MP_mul, MP_div, and MP_mod and their unsigned counterparts compute z = x + y, z = x − y, z = x·y, z = x/y, and z = x mod y, respectively, and return z. Italics denote the values of x, y, and z. MP_neg sets to z to the negative of x and returns z. If x and y have different signs, MP_div and MP_mod truncate toward minus infinity; thus x mod y is always positive.
All these functions, except MP_divu and MP_modu, raise MP_Overflow if the result does not fit. MP_subu raises MP_Overflow when x < y, and MP_sub raises MP_Overflow when x and y have different signs and the sign of the result is different from x’s sign. MP_div, MP_divu, MP_mod, and MP_modu raise
<exported exceptions 359>+≡
extern const Except_T MP_Dividebyzero;when y is zero.
<exported functions 358>+≡
extern T MP_mul2u(T z, T x, T y);
extern T MP_mul2 (T z, T x, T y);return double-length products: They both compute z = x·y, where z has 2n bits, and return z. Thus, the result cannot overflow. It is an unchecked runtime error for z to be too small to hold 2n bits. Note that since z must accommodate 2n bits, it cannot be allocated by MP_new.
The convenience functions accept an immediate unsigned long or long for their second operand:
<exported functions 358>+≡
extern T MP_addi (T z, T x, long y);
extern T MP_subi (T z, T x, long y);
extern T MP_muli (T z, T x, long y);
extern T MP_divi (T z, T x, long y);
extern T MP_addui(T z, T x, unsigned long y);
extern T MP_subui(T z, T x, unsigned long y);
extern T MP_mului(T z, T x, unsigned long y);
extern T MP_divui(T z, T x, unsigned long y);
extern long MP_modi (T x, long y);
extern unsigned long MP_modui(T x, unsigned long y);These functions are equivalent to their more general counterparts when their second operands are initialized to y, and they raise similar exceptions. For example,
MP_T z, x; long y; MP_muli(z, x, y);
is equivalent to
MP_T z, x;
long y;
{
MP_T t = MP_new(0);
int overflow = 0;
TRY
MP_fromint(t, y);
EXCEPT(MP_Overflow)
overflow = 1;
END_TRY;
MP_mul(z, x, t);
if (overflow)
RAISE(MP_Overflow);
}The convenience functions do no allocations, however. Notice that these convenience functions, including MP_divui and MP_modui, raise MP_Overflow if y is too big, but they do so after computing z.
<exported functions 358>+≡
extern int MP_cmp (T x, T y);
extern int MP_cmpi (T x, long y);
extern int MP_cmpu (T x, T y);
extern int MP_cmpui(T x, unsigned long y);compare x and y and return a value less than zero, equal to zero, or greater than zero, if, respectively x < y, x = y, or x > y. MP_cmpi and MP_cmpui don’t insist that y fit in an MP_T; they simply compare x and y.
The following functions treat their input MP_Ts as strings of n bits:
<exported functions 358>+≡
extern T MP_and (T z, T x, T y);
extern T MP_or (T z, T x, T y);
extern T MP_xor (T z, T x, T y);
extern T MP_not (T z, T x);
extern T MP_andi(T z, T x, unsigned long y);
extern T MP_ori (T z, T x, unsigned long y);
extern T MP_xori(T z, T x, unsigned long y);MP_and, MP_or, MP_xor and their immmediate counterparts set z to the bitwise AND, inclusive OR, and exclusive OR of x and y and return z. MP_not sets z to the one’s complement of x and returns z. These functions never raise exceptions, and the convenience variants ignore the overflow that would usually occur when y is too big. For example,
MP_T z, x; unsigned long y; MP_andi(z, x, y);
is equivalent to
MP_T z, x;
unsigned long y;
{
MP_T t = MP_new(0);
TRY
MP_fromintu(t, y);
EXCEPT(MP_Overflow) ;
END_TRY;
MP_and(z, x, t);
}None of these functions do any allocations, however.
The three shift functions
<exported functions 358>+≡
extern T MP_lshift(T z, T x, int s);
extern T MP_rshift(T z, T x, int s);
extern T MP_ashift(T z, T x, int s);implement logical and arithmetic shifts. MP_lshift sets z to x shifted left s bits, and MP_rshift sets z to x shifted right s bits. Both functions fill the vacated bits with zeros and return z. MP_ashift is like MP_rshift, but the vacated bits are filled with x’s sign bit. It is a checked runtime error for s to be negative.
The following functions convert between MP_Ts and strings.
<exported functions 358>+≡
extern T MP_fromstr(T z, const char *str,
int base, char **end);
extern char *MP_tostr (char *str, int size,
int base, T x);
extern void MP_fmt (int code, va_list *app,
int put(int c, void *cl), void *cl,
unsigned char flags[], int width, int precision);
extern void MP_fmtu (int code, va_list *app,
int put(int c, void *cl), void *cl,
unsigned char flags[], int width, int precision);MP_fromstr interprets the string in str as an unsigned integer in base, sets z to that integer, and returns z. It ignores leading white space, and consumes one or more digits in base. For bases greater than 10, the lowercase and uppercase letters specify the digits beyond nine. MP_fromstr is like strtoul: If end is nonnull, MP_fromstr sets *end to the address of the character that terminated the scan. If str does not specify a valid integer, MP_fromstr sets *end to str, if end is nonnull, and returns null. MP_fromstr raises MP_Overflow if the string in str specifies an integer that is too big. It is a checked runtime error for str to be null, or for base to be less than two or more than 36.
MP_tostr fills str[0..size-1] with a null-terminated string representing x in base, and returns str. If str is null, MP_tostr ignores size and allocates the necessary string; it is the client’s responsibility to deallocate the string. It is a checked runtime error for str to be nonnull, for size to be too small to hold the null-terminated result, or for base to be less than two or more than 36. When str is null, MP_tostr can raise Mem_Failed.
MP_fmt and MP_fmtu are Fmt-style conversion functions for printing MP_Ts. Both consume an MP_T and a base; MP_fmt converts the signed MP_T to a string using the same conventions as printf’s %d conversion, and MP_fmtu converts the unsigned MP_T using conventions of printf’s %u conversion. Both functions can raise Mem_Failed. It is a checked runtime error for app or flags to be null.
mpcalc is like calc, except that it does signed and unsigned computations on n-bit integers. It illustrates the use of the MP interface. Like calc, mpcalc uses Polish suffix notation: Values are pushed onto a stack, and operators pop their operands from the stack and push their results. A value is one or more consecutive digits in the current input base, and the operators are as follows.
| negation |
| addition |
| subtraction |
| multiplication |
| division |
| remainder |
| set the input base |
| set the precision |
| AND |
| inclusive OR |
| exclusive OR |
| left shift |
| right shift |
| not |
| set the output base |
| clear the stack |
duplicate the value at the top of the stack | |
| print the value at the top of the stack |
| print all the values on the stack from the top down |
| quit |
White-space characters separate values but are otherwise ignored; other characters are announced as unrecognized operators. The size of the stack is limited only by available memory, but a diagnostic announces stack underflow.
The command nk, where n is at least two, specifies the size of the integers manipulated by mpcalc; the default is 32. The stack must be empty when the k operator is executed. The i and o operators specify the input and output bases; the defaults are both 10. When the input base exceeds 10, the leading digit of a value must be between zero and nine inclusive.
If the output base is two, eight, or 16, the +=*/ and % operators do unsigned arithmetic, and the p and f operators print unsigned values. For all other bases, +=*/ and % do signed arithmetic, and p and f print signed values. The ~ operator always does signed arithmetic, and the &|^! < and > operators always interpret their operands as unsigned numbers.
mpcalc announces overflow and division by zero when they occur. For overflow, the result in this case is the n least significant bits of the value. For division by zero, the result is zero.
The overall structure of mpcalc is much like that of calc: It interprets the input, computes values, and manages a stack.
<mpcalc.c>≡ #include <ctype.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include "mem.h" #include "seq.h" #include "fmt.h" #include "mp.h" <mpcalc data 367> <mpcalc functions 367>
As the inclusion of seq.h suggests, mpcalc uses a sequence for its stack:
<mpcalc data 367>≡ Seq_T sp; <initialization 367>≡ sp = Seq_new(0);
Values are pushed by calling Seq_addhi, and they’re popped by calling Seq_remhi. mpcalc must not call Seq_remhi when the sequence is empty, so it wraps all pop operations in a function that checks for underflow:
<mpcalc functions 367>≡
MP_T pop(void) {
if (Seq_length(sp) > 0)
return Seq_remhi(sp);
else {
Fmt_fprint(stderr, "?stack underflow
");
return MP_new(0);
}
}Like calc’s pop, mpcalc’s pop always returns an MP_T, even when the stack is empty, because this simplifies error-checking.
Dealing with MP’s exceptions makes mpcalc’s main loop a bit more complicated than calc’s. Like calc’s main loop, mpcalc’s reads the next value or operator and switches on it. But it also sets up some MP_Ts for operands and results, and it uses a TRY-EXCEPT statement to catch the exceptions.
<mpcalc functions 367>+≡ int main(int argc, char *argv[]) { int c; <initialization 367> while ((c = getchar()) != EOF) { volatile MP_T x = NULL, y = NULL, z = NULL; TRY switch (c) { <cases 368> } EXCEPT(MP_Overflow) Fmt_fprint(stderr, "?overflow "); EXCEPT(MP_Dividebyzero) Fmt_fprint(stderr, "?divide by 0 "); END_TRY; if (z) Seq_addhi(sp, z); FREE(x); FREE(y); } <clean up and exit 368> } <clean up and exit 368>≡ <clear the stack 368> Seq_free(&sp); return EXIT_SUCCESS;
x and y are used for operands, and z is used for the result. If x and y are nonnull after switching on an operator, they hold operands that were popped from the stack and thus must be deallocated. If z is nonnull, it holds the result, which must be pushed. This approach permits the TRY-EXCEPT statement to appear only once, instead of around the code for each operator.
An input character is either white space, the first digit of a value, an operator, or something else, which is an error. Here are the easy cases:
<cases 368>≡ default: if (isprint(c)) Fmt_fprint(stderr, "?'%c'", c); else Fmt_fprint(stderr, "?'\%03o'", c); Fmt_fprint(stderr, " is unimplemented "); break; case ' ': case ' ': case ' ': case 'f': case ' ': break; case 'c': <clear the stack 368> break; case 'q': <clean up and exit 368> <clear the stack 368>≡ while (Seq_length(sp) > 0) { MP_T x = Seq_remhi(sp); FREE(x); }
A digit identifies the beginning of a value; calc gathers up the digits and calls MP_fromstr to convert them to an MP_T. ibase is the current input base.
<cases 368>≡ case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': { char buf[512]; z = MP_new(0); <gather up digits into buf 369> MP_fromstr(z, buf, ibase, NULL); break; } <gather up digits into buf 369>≡ { int i = 0; for ( ; <c is a digit in ibase 369>; c = getchar(), i++) if (i < (int)sizeof (buf) - 1) buf[i] = c; if (i > (int)sizeof (buf) - 1) { i = (int)sizeof (buf) - 1; Fmt_fprint(stderr, "?integer constant exceeds %d digits ", i); } buf[i] = ' '; if (c != EOF) ungetc(c, stdin); }
Excessively long values are announced and truncated. A character is a digit in ibase if
<c is a digit in ibase 369>≡
strchr(&"zyxwvutsrqponmlkjihgfedcba9876543210"[36-ibase],
tolower(c))The cases for most of the arithmetic operators have the same form:
<cases 368>+≡ case '+': <pop x & y, set z 370> (*f->add)(z, x, y); break; case '-': <pop x & y, set z 370> (*f->sub)(z, x, y); break; case '*': <pop x & y, set z 370> (*f->mul)(z, x, y); break; case '/': <pop x & y, set z 370> (*f->div)(z, x, y); break; case '%': <pop x & y, set z 370> (*f->mod)(z, x, y); break; case '&': <pop x & y, set z 370> MP_and(z, x, y); break; case '|': <pop x & y, set z 370> MP_or (z, x, y); break; case '^': <pop x & y, set z 370> MP_xor(z, x, y); break; case '!': z = pop(); MP_not(z, z); break; case '~': z = pop(); MP_neg(z, z); break; <pop x & y, set z 370>≡ y = pop(); x = pop(); z = MP_new(0);
f points to a structure that holds pointers to functions for those operations that depend on whether mpcalc is doing signed or unsigned arithmetic.
<mpcalc data 367>+≡
int ibase = 10;
int obase = 10;
struct {
const char *fmt;
MP_T (*add)(MP_T, MP_T, MP_T);
MP_T (*sub)(MP_T, MP_T, MP_T);
MP_T (*mul)(MP_T, MP_T, MP_T);
MP_T (*div)(MP_T, MP_T, MP_T);
MP_T (*mod)(MP_T, MP_T, MP_T);
} s = { "%D
",
MP_add, MP_sub, MP_mul, MP_div, MP_mod },
u = { "%U
",
MP_addu, MP_subu, MP_mulu, MP_divu, MP_modu },
*f = &s;obase is the output base. Initially, the bases are both 10, and f points to s, which holds pointers to the MP functions for signed arithmetic. The i operator changes ibase, the o operator changes obase, and both operators reaim f at either u or s:
<cases 369>+≡
case 'i': case 'o': {
long n;
x = pop();
n = MP_toint(x);
if (n < 2 || n > 36)
Fmt_fprint(stderr, "?%d is an illegal base
",n);
else if (c == 'i')
ibase = n;
else
obase = n;
if (obase == 2 || obase == 8 || obase == 16)
f = &u;
else
f = &s;
break;
}The base isn’t changed if y can’t be converted to a long (that is, if MP_toint raises MP_Overflow), or if the resulting integer isn’t a legal base.
The s and u structures also hold a Fmt-style format string that is used to print MP_Ts. mpcalc registers MP_fmt with %D and MP_fmtu with %U:
<initialization 367>+≡
Fmt_register('D', MP_fmt);
Fmt_register('U', MP_fmtu);f->fmt thus accesses the appropriate format string, which the p and f operators use to print MP_Ts. Note that p pops its operand into z — the code in the main loop pushes that value back onto the stack.
<cases 369>+≡
case 'p':
Fmt_print(f->fmt, z = pop(), obase);
break;
case 'f': {
int n = Seq_length(sp);
while (--n >= 0)
Fmt_print(f->fmt, Seq_get(sp, n), obase);
break;
}Compare the code for f with calc’s code on page 332; it’s easy to print all of the values on the stack when it’s represented with a Seq_T.
The shift operators guard against illegal shift amounts, and shift their operand in place:
<cases 369>+≡ case '<': {<get s & z 372>; MP_lshift(z, z, s); break; } case '>': {<get s & z 372>; MP_rshift(z, z, s); break; } <get s & z 372>≡ long s; y = pop(); z = pop(); s = MP_toint(y); if (s < 0 || s > INT_MAX) { Fmt_fprint(stderr, "?%d is an illegal shift amount ", s); break; }
If MP_toint raises MP_Overflow, or s is negative or exceeds the largest int, the operand, z, is simply pushed back onto the stack.
The remaining cases are for the k and d operators:
<cases 369>+≡
case 'k': {
long n;
x = pop();
n = MP_toint(x);
if (n < 2 || n > INT_MAX)
Fmt_fprint(stderr,
"?%d is an illegal precision
", n);
else if (Seq_length(sp) > 0)
Fmt_fprint(stderr, "?nonempty stack
");
else
MP_set(n);
break;
}
case 'd': {
MP_T x = pop();
z = MP_new(0);
Seq_addhi(sp, x);
MP_addui(z, x, 0);
break;
}Again, setting z causes that value to be pushed by the code in the main loop.
<mp.c>≡ #include <ctype.h> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <limits.h> #include "assert.h" #include "fmt.h" #include "mem.h" #include "xp.h" #include "mp.h" #define T MP_T <macros 374> <data 373> <static functions 389> <functions 374> <data 373>≡ const Except_T MP_Dividebyzero = { "Division by zero" }; const Except_T MP_Overflow = { "Overflow" };
XP represents an n-bit number as ⌈n/8⌉ = (n − 1)/8 + 1 bytes, least significant byte first (n is always positive). The following figure shows how MP interprets these bytes. The least significant byte is on the right, and addresses increase to the left.
The sign bit is bit n − 1, that is, bit (n − 1) mod 8 in byte (n − 1)/8. Given n, MP computes three values of interest in addition to saving n as nbits: nbytes, the number of bytes required to hold n bits; shift, the number of bits the most significant byte must be shifted right to isolate the sign bit; and msb, a mask of shift+1 ones, which is used to detect overflow. When n is 32, these values are:
<data 373>+≡
static int nbits = 32;
static int nbytes = (32-1)/8 + 1;
static int shift = (32-1)%8;
static unsigned char msb = 0xFF;As suggested above, MP uses nbytes and shift to access the sign bit:
<macros 374>≡ #define sign(x) ((x)[nbytes-1]>>shift)
These values are changed by MP_set:
<functions 374>≡ int MP_set(int n) { int prev = nbits; assert(n > 1); <initialize 375> return prev; } <initialize 375>≡ nbits = n; nbytes = (n-1)/8 + 1; shift = (n-1)%8; msb = ones(n); <macros 374>+≡ #define ones(n) (~(~0UL<<(((n)-1)%8+1)))
Shifting ~0 left (n-1)%8+1 bits forms a mask of ones followed by (n − 1) mod 8 + 1 zeros; complementing it yields (n − 1) mod 8 + 1 ones in the least significant bits. ones is defined this way because it is used for other values of n besides the values passed to MP_set.
MP_set also allocates some temporary space for use in the arithmetic functions, like MP_div. The allocation is thus done once in MP_set instead of repeatedly in the arithmetic functions. MP_set allocates enough space for one 2·nbyte+2 temporary and three nbyte temporaries.
<data 373>+≡ static unsigned char temp[16 + 16 + 16 + 2*16+2]; static T tmp[] = {temp, temp+1*16, temp+2*16, temp+3*16}; <initialize 375>+≡ if (tmp[0] != temp) FREE(tmp[0]); if (nbytes <= 16) tmp[0] = temp; else tmp[0] = ALLOC(3*nbytes + 2*nbytes + 2); tmp[1] = tmp[0] + 1*nbytes; tmp[2] = tmp[0] + 2*nbytes; tmp[3] = tmp[0] + 3*nbytes;
MP_set can use the statically allocated temp when nbytes doesn’t exceed 16, or when n doesn’t exceed 128. Otherwise, it must allocate space for the temporary. temp is necessary because MP must be initialized as if MP_set(32) had been executed.
Most of the MP functions call XP functions to do the actual arithmetic on nbyte numbers, then check whether the result exceeds nbits bits. MP_new and MP_fromintu illustrate this strategy.
<functions 374>+≡ T MP_new(unsigned long u) { return MP_fromintu(ALLOC(nbytes), u); } T MP_fromintu(T z, unsigned long u) { unsigned long carry; assert(z); <set z to u 376> <test for unsigned overflow 376> return z; } <set z to u 376>≡ carry = XP_fromint(nbytes, z, u); carry |= z[nbytes-1]&~msb; z[nbytes-1] &= msb;
If XP_fromint returns a nonzero carry, u doesn’t fit in nbytes. If carry is zero, u fits in nbytes, but it might not fit in nbits bits. MP_fromintu must ensure that the 8-(shift+1) most significant bits in z’s most significant byte are zeros. MP_set has arranged for msb to hold a mask of shift+1 ones, so ~msb isolates the desired bits, which are OR’ed into carry before they’re discarded. The test for unsigned overflow simply tests carry:
<test for unsigned overflow 376>≡
if (carry)
RAISE(MP_Overflow);Notice that MP_fromintu sets z before testing for overflow; as specified by the interface, all of the MP functions must set their results before raising an exception.
Testing for signed overflow is a bit more complicated, because it depends on the operation involved. MP_fromint illustrates an easy case.
<functions 374>+≡ T MP_fromint(T z, long v) { assert(z); <set z to v 377> if (<v is too big 377>) RAISE(MP_Overflow); return z; }
First, MP_fromint initializes z to the value of v, taking care to pass only positive values to XP_fromint:
<set z to v 377>≡ if (v == LONG_MIN) { XP_fromint(nbytes, z, LONG_MAX + 1UL); XP_neg(nbytes, z, z, 1); } else if (v < 0) { XP_fromint(nbytes, z, -v); XP_neg(nbytes, z, z, 1); } else XP_fromint(nbytes, z, v); z[nbytes-1] &= msb;
The first two if clauses handle negative values: z is set to the absolute value of v, and then to its two’s complement, which is accomplished by passing a one as the fourth argument to XP_neg. MP_fromint must treat the most negative integer specially, because it can’t negate it. If v is negative, z’s most significant bits will be ones, and the excess bits must be discarded. Many of the MP functions use the z[nbytes-1] &= msb idiom shown above to discard the excess bits in z’s most significant byte.
For MP_fromint, signed overflow occurs when nbits is less than the number of bits in a long and v is outside z’s range.
<v is too big 377>≡
(nbits < 8*(int)sizeof (v) &&
(v < -(1L<<(nbits-1)) || v >= (1L<<(nbits-1))))The two shift expressions compute the most negative and most positive nbits-long signed integer.
MP_toint and MP_cvt illustrate another instance of checking for signed overflow:
<functions 374>+≡
long MP_toint(T x) {
unsigned char d[sizeof (unsigned long)];
assert(x);
MP_cvt(8*sizeof d, d, x);
return XP_toint(sizeof d, d);
}MP_cvt raises MP_Overflow if d can’t hold x; if d can hold x, XP_toint returns the desired value.
MP_cvt does both kinds of conversions: It converts an MP_T to an MP_T with either fewer or more bits.
<functions 374>+≡ T MP_cvt(int m, T z, T x) { int fill, i, mbytes = (m - 1)/8 + 1; assert(m > 1); <checked runtime errors for unary functions 378> fill = sign(x) ? 0xFF : 0; if (m < nbits) { <narrow signed x 379> } else { <widen signed x 379> } return z; } <checked runtime errors for unary functions 378>≡ assert(x); assert(z);
If m is less than nbits, MP_cvt “narrows” the value of x and assigns it to z. This case must check for signed overflow. x fits in m bits if bits m through nbits−1 in x are either all zeros or all ones; that is, if the excess bits in x are equal to the sign bit of x when it’s treated as an m-bit integer. In the chunk below, fill is FF if x is negative and zero otherwise, so x[i]^fill should be zero if the bits x[m..nbits-1] are all ones or all zeros.
<narrow signed x 379>≡
int carry = (x[mbytes-1]^fill)&~ones(m);
for (i = mbytes; i < nbytes; i++)
carry |= x[i]^fill;
memcpy(z, x, mbytes);
z[mbytes-1] &= ones(m);
if (carry)
RAISE(MP_Overflow);If x is in range, carry will be zero; otherwise, some of carry’s bits will be ones. The initial assignment to carry ignores the bits that will be part of z’s nonsign bits.
If m is at least nbits, MP_cvt “widens” the value of x and assigns it to z. Overflow cannot occur in this case, but MP_cvt must propagate x’s sign bit, which is given by fill.
<widen signed x 379>≡
memcpy(z, x, nbytes);
z[nbytes-1] |= fill&~msb;
for (i = nbytes; i < mbytes; i++)
z[i] = fill;
z[mbytes-1] &= ones(m);MP_tointu uses a similar approach: It calls MP_cvtu to convert x to an MP_T with the number of bits in an unsigned long, then calls XP_toint to return the value.
<functions 374>+≡
unsigned long MP_tointu(T x) {
unsigned char d[sizeof (unsigned long)];
assert(x);
MP_cvtu(8*sizeof d, d, x);
return XP_toint(sizeof d, d);
}Again, MP_cvtu either narrows or widens the value of x and assigns it to z.
<functions 374>+≡ T MP_cvtu(int m, T z, T x) { int i, mbytes = (m - 1)/8 + 1; assert(m > 1); <checked runtime errors for unary functions 378> if (m < nbits) { <narrow unsigned x 380> } else { <widen unsigned x 380> } return z; }
When m is less than nbits, overflow occurs if any of x’s bits m through nbits−1 are ones, which is checked with code that is similar to, but simpler than, the code in MP_cvt:
<narrow unsigned x 380>≡ int carry = x[mbytes-1]&~ones(m); for (i = mbytes; i < nbytes; i++) carry |= x[i]; memcpy(z, x, mbytes); z[mbytes-1] &= ones(m); <test for unsigned overflow 376>
When m is at least nbits, overflow cannot occur, and the excess bits in z are set to zeros:
<widen unsigned x 380>≡
memcpy(z, x, nbytes);
for (i = nbytes; i < mbytes; i++)
z[i] = 0;As the code for MP_cvtu and MP_cvt suggests, the unsigned arithmetic functions are easier to implement than their signed counterparts, because they don’t need to handle signs and testing for overflow is simpler. Unsigned addition illustrates an easy case; XP_add does all the work.
<functions 374>+≡ T MP_addu(T z, T x, T y) { int carry; <checked runtime errors for binary functions 381> carry = XP_add(nbytes, z, x, y, 0); carry |= z[nbytes-1]&~msb; z[nbytes-1] &= msb; <test for unsigned overflow 376> return z; } <checked runtime errors for binary functions 381>≡ assert(x); assert(y); assert(z);
Subtraction is just as easy, but MP_Overflow is raised when there’s an outstanding borrow:
<functions 374>+≡ T MP_subu(T z, T x, T y) { int borrow; <checked runtime errors for binary functions 381> borrow = XP_sub(nbytes, z, x, y, 0); borrow |= z[nbytes-1]&~msb; z[nbytes-1] &= msb; <test for unsigned underflow 381> return z; } <test for unsigned underflow 381>≡ if (borrow) RAISE(MP_Overflow);
MP_mul2u is the simplest of the multiplication functions, because overflow cannot occur.
<functions 374>+≡ T MP_mul2u(T z, T x, T y) { <checked runtime errors for binary functions 381> memset(tmp[3], ' ', 2*nbytes); XP_mul(tmp[3], nbytes, x, nbytes, y); memcpy(z, tmp[3], (2*nbits - 1)/8 + 1); return z; }
MP_mul2u computes the result into tmp[3] and copies tmp[3] to z so that x or y can be used as z, which would not work if MP_mul2u computed the result directly into z. Allocating the temporary space in MP_set thus not only isolates the allocations, but avoids restrictions on x and y.
MP_mul also calls XP_mul to compute a double-length result in tmp[3], and then narrows that result to nbits and assigns it to z.
<functions 374>+≡ T MP_mulu(T z, T x, T y) { <checked runtime errors for binary functions 381> memset(tmp[3], ' ', 2*nbytes); XP_mul(tmp[3], nbytes, x, nbytes, y); memcpy(z, tmp[3], nbytes); z[nbytes-1] &= msb; <test for unsigned multiplication overflow 382> return z; }
The product overflows if any of the bits nbits through 2·nbits−1 in tmp[3] are ones. This condition can be tested much the way the similar condition in MP_cvtu is tested:
<test for unsigned multiplication overflow 382>≡
{
int i;
if (tmp[3][nbytes-1]&~msb)
RAISE(MP_Overflow);
for (i = 0; i < nbytes; i++)
if (tmp[3][i+nbytes] != 0)
RAISE(MP_Overflow);
}MP_divu avoids XP_div’s restrictions on its arguments by copying y to a temporary:
<functions 374>+≡ T MP_divu(T z, T x, T y) { <checked runtime errors for binary functions 381> <copy y to a temporary 383> if (!XP_div(nbytes, z, x, nbytes, y, tmp[2], tmp[3])) RAISE(MP_Dividebyzero); return z; } <copy y to a temporary 383>≡ { memcpy(tmp[1], y, nbytes); y = tmp[1]; }
tmp[2] holds the remainder, which is discarded; tmp[1] holds y, and y is reaimed at tmp[1]. tmp[3] is the 2·nbyte+2 temporary needed by XP_div. MP_modu is similar, but it uses tmp[2] to hold the quotient:
<functions 374>+≡ T MP_modu(T z, T x, T y) { <checked runtime errors for binary functions 381> <copy y to a temporary 383> if (!XP_div(nbytes, tmp[2], x, nbytes, y, z, tmp[3])) RAISE(MP_Dividebyzero); return z; }
AP’s sign-magnitude representation forces AP_add to consider the signs x of y. The properties of the two’s-complement representation permit MP_add to avoid this case analysis and simply call XP_add regardless of the signs of x and y. Thus, signed addition is nearly identical to unsigned addition; the only important difference is the test for overflow.
<functions 374>+≡ T MP_add(T z, T x, T y) { int sx, sy; <checked runtime errors for binary functions 381> sx = sign(x); sy = sign(y); XP_add(nbytes, z, x, y, 0); z[nbytes-1] &= msb; <test for signed overflow 384> return z; }
Overflow occurs in addition when x and y have the same signs. When the sum overflows, its sign is different from that of x and y:
<test for signed overflow 384>≡
if (sx == sy && sy != sign(z))
RAISE(MP_Overflow);Signed subtraction has the same form as addition, but the test for overflow is different.
<functions 374>+≡ T MP_sub(T z, T x, T y) { int sx, sy; <checked runtime errors for binary functions 381> sx = sign(x); sy = sign(y); XP_sub(nbytes, z, x, y, 0); z[nbytes-1] &= msb; <test for signed underflow 384> return z; }
For subtraction, underflow occurs when x and y have different signs. When x is positive and y is negative, the result should be positive; when x is negative and y is positive, the result should be negative. Thus, if x and y have different signs, and the result has the same sign as y, underflow has occurred.
<test for signed underflow 384>≡
if (sx != sy && sy == sign(z))
RAISE(MP_Overflow);Negating x is equivalent to subtracting it from zero: Overflow can occur only when x is negative, and when the result overflows, it’s still negative.
<functions 374>+≡ T MP_neg(T z, T x) { int sx; <checked runtime errors for unary functions 378> sx = sign(x); XP_neg(nbytes, z, x, 1); z[nbytes-1] &= msb; if (sx && sx == sign(z)) RAISE(MP_Overflow); return z; }
MP_neg must clear the excess bits in z’s most significant byte because they will be ones when x is positive.
The easiest way to implement signed multiplication is to negate negative operands, do an unsigned multiplication, and negate the result when the operands have different signs. For MP_mul2, overflow can never occur because it computes a double-length result, and the details are easy to fill in:
<functions 374>+≡ T MP_mul2(T z, T x, T y) { int sx, sy; <checked runtime errors for binary functions 381> <tmp[3] ← x·y 385> if (sx != sy) XP_neg((2*nbits - 1)/8 + 1, z, tmp[3], 1); else memcpy(z, tmp[3], (2*nbits - 1)/8 + 1); return z; } <tmp[3] ← x·y 385>≡ sx = sign(x); sy = sign(y); <if x < 0, negate x 386> <if y < 0, negate y 386> memset(tmp[3], ' ', 2*nbytes); XP_mul(tmp[3], nbytes, x, nbytes, y);
The product has 2·nbits, which needs only (2·nbits − 1)/8 + 1 bytes of z. x and y are negated, when necessary, by forming the negated values in an appropriate temporary, and reaiming x or y at that temporary.
<if x < 0, negate x 386>≡ if (sx) { XP_neg(nbytes, tmp[0], x, 1); x = tmp[0]; x[nbytes-1] &= msb; } <if y < 0, negate y 386>≡ if (sy) { XP_neg(nbytes, tmp[1], y, 1); y = tmp[1]; y[nbytes-1] &= msb; }
By convention, x and y are negated or copied, when necessary, into tmp[0] and tmp[1] by the MP functions.
MP_mul is similar to MP_mul2, but only the least significant nbits of the 2·nbit result are copied to z, and overflow occurs when the result doesn’t fit in nbits, or when the operands have the same signs and the result is negative.
<functions 374>+≡ T MP_mul(T z, T x, T y) { int sx, sy; <checked runtime errors for binary functions 381> <tmp[3] ← x·y 385> if (sx != sy) XP_neg(nbytes, z, tmp[3], 1); else memcpy(z, tmp[3], nbytes); z[nbytes-1] &= msb; <test for unsigned multiplication overflow 382> if (sx == sy && sign(z)) RAISE(MP_Overflow); return z; }
Signed division is much like unsigned division when the operands have the same signs, because both the quotient and the remainder are nonnegative. Overflow occurs only when the dividend is the most negative n-bit value and the divisor is −1; in this case, the quotient will be negative.
<functions 374>+≡ T MP_div(T z, T x, T y) { int sx, sy; <checked runtime errors for binary functions 381> sx = sign(x); sy = sign(y); <if x <0, negate x 386> <if y <0, negate y 386> else <copy y to a temporary 383> if (!XP_div(nbytes, z, x, nbytes, y, tmp[2], tmp[3])) RAISE(MP_Dividebyzero); if (sx != sy) { <adjust the quotient 388> } else if (sx && sign(z)) RAISE(MP_Overflow); return z; }
MP_div either negates y into its temporary or copies it there, because y and z might the same MP_T, and it uses tmp[2] to hold the remainder.
The complicated case for signed division and modulus is when the operands have different signs. In this case, the quotient is negative but must be truncated toward minus infinity, and the remainder is positive. The required adjustments are the same ones that AP_div and AP_mod do: The quotient is negated and, if the remainder is nonzero, the quotient is decremented. Also, if the unsigned remainder is nonzero, y minus that remainder is the correct value.
<adjust the quotient 388>≡ XP_neg(nbytes, z, z, 1); if (!iszero(tmp[2])) XP_diff(nbytes, z, z, 1); z[nbytes-1] &= msb; <macros 374>+≡ #define iszero(x) (XP_length(nbytes,(x))==1 && (x)[0]==0)
MP_div doesn’t bother adjusting the remainder, because it’s discarded. MP_mod does just the opposite: It adjusts only the remainder, and uses tmp[2] to hold the quotient.
<functions 374>+≡ T MP_mod(T z, T x, T y) { int sx, sy; <checked runtime errors for binary functions 381> sx = sign(x); sy = sign(y); <if x <0, negate x 386> <if y <0, negate y 386> else <copy y to a temporary 383> if (!XP_div(nbytes, tmp[2], x, nbytes, y, z, tmp[3])) RAISE(MP_Dividebyzero); if (sx != sy) { if (!iszero(z)) XP_sub(nbytes, z, y, z, 0); } else if (sx && sign(tmp[2])) RAISE(MP_Overflow); return z; }
The arithmetic convenience functions take a long or unsigned long immediate operand, convert it to an MP_T, if necessary, and perform the corresponding arithmetic operation. When y is a single digit in base 28, these functions can use the single-digit functions exported by XP. But there are two opportunities for overflow: y might be too big, and the operation itself might overflow. If y is too big, these functions must complete the operation and the assignment to z before raising an exception. MP_addui illustrates the approach used by all the convenience functions:
<functions 374>+≡ T MP_addui(T z, T x, unsigned long y) { <checked runtime errors for unary functions 378> if (y < BASE) { int carry = XP_sum(nbytes, z, x, y); carry |= z[nbytes-1]&~msb; z[nbytes-1] &= msb; <test for unsigned overflow 376> } else if (applyu(MP_addu, z, x, y)) RAISE(MP_Overflow); return z; } <macros 374>+≡ #define BASE (1<<8)
If y is one digit, XP_sum can compute x + y. This code also detects overflow when nbits is less than eight and y is too big, because the sum will be too big for any value of x. Otherwise, MP_addui calls applyu to convert y to an MP_T and to apply the more general function MP_addu. applyu returns a one if y is too big, but only after it computes z:
<static functions 389>≡ static int applyu(T op(T, T, T), T z, T x, unsigned long u) { unsigned long carry; { T z = tmp[2]; <set z to u 376> } op(z, x, tmp[2]); return carry != 0; }
applyu uses the code from MP_fromintu to convert the unsigned long operand into tmp[2]. It saves the carry from the conversion because the conversion might overflow. It then calls the function specified by its first argument, and returns one if the saved carry is nonzero, or zero otherwise. The function op might raise an exception, too, but only after it sets z.
The convenience functions for unsigned subtraction and multiplication are similar. When y is less than 28, MP_subui calls MP_diff.
<functions 381>+≡ T MP_subui(T z, T x, unsigned long y) { <checked runtime errors for unary functions 381> if (y < BASE) { int borrow = XP_diff(nbytes, z, x, y); borrow |= z[nbytes-1]&~msb; z[nbytes-1] &= msb; <test for unsigned underflow 381> } else if (applyu(MP_subu, z, x, y)) RAISE(MP_Overflow); return z; }
When y is too big, x − y underflows for all x, so MP_subui doesn’t need to check whether y is too big before calling XP_diff.
MP_mului calls MP_product, but MP_mului must explicitly check whether y is too big when nbits is less than eight, because XP_product won’t catch that error when x is zero. This check is made after computing z.
T MP_mului(T z, T x, unsigned long y) {
<checked runtime errors for unary functions 381>
if (y < BASE) {
int carry = XP_product(nbytes, z, x, y);
carry |= z[nbytes-1]&~msb;
z[nbytes-1] &= msb;
<test for unsigned overflow 376>
<check if unsigned y is too big 390>
} else if (applyu(MP_mulu, z, x, y))
RAISE(MP_Overflow);
return z;
}
<check if unsigned y is too big 390>≡
if (nbits < 8 && y >= (1U<<nbits))
RAISE(MP_Overflow);MP_divui and MP_modui use XP_quotient, but they must test for a zero divisor themselves (because XP_quotient accepts only nonzero, single-digit divisors), and they must test for overflow when nbits is less than eight and y is too big.
<functions 381>+≡ T MP_divui(T z, T x, unsigned long y) { <checked runtime errors for unary functions 381> if (y == 0) RAISE(MP_Dividebyzero); else if (y < BASE) { XP_quotient(nbytes, z, x, y); <check if unsigned y is too big 390> } else if (applyu(MP_divu, z, x, y)) RAISE(MP_Overflow); return z; }
MP_modui calls XP_quotient, but only to compute the remainder. It discards the quotient computed into tmp[2]:
<functions 381>+≡ unsigned long MP_modui(T x, unsigned long y) { assert(x); if (y == 0) RAISE(MP_Dividebyzero); else if (y < BASE) { int r = XP_quotient(nbytes, tmp[2], x, y); <check if unsigned y is too big 390> return r; } else if (applyu(MP_modu, tmp[2], x, y)) RAISE(MP_Overflow); return XP_toint(nbytes, tmp[2]); }
The signed arithmetic convenience functions use the same approach, but call a different apply function, which uses MP_fromint’s code to convert a long to a signed MP_T in tmp[2], calls the desired function, and returns one if the immediate operand is too big, or zero otherwise.
<static functions 389>+≡ static int apply(T op(T, T, T), T z, T x, long v) { { T z = tmp[2]; <set z to v 377> } op(z, x, tmp[2]); return <v is too big 377>; }
When |y| is less than 28, the signed convenience functions have a bit more work to do than their unsigned counterparts, because they must deal with signed operands. The single-digit XP functions take only positive single-digit operands, so the signed convenience functions must use the signs of their operands to determine which function to call. The analysis is similar to that done by the AP functions (see page 338), but MP’s two’s-complement representation simplifies the details. Here are the cases for addition.
y < 0 | y ≥ 0 | |
x < 0 | −(|x| + |y|) = x − |y| | −(|x| − |y|) = x + |y| |
x ≥ 0 | |x| − |y| = x − |y| | |x| + |y| = x + |y| |
When y is negative, x + y is equal to x − |y| for any x, so MP_addi can use XP_diff to compute the sum; it can use XP_sum when y is nonnegative.
<functions 381>+≡ T MP_addi(T z, T x, long y) { <checked runtime errors for unary functions 381> if (-BASE < y && y < BASE) { int sx = sign(x), sy = y < 0; if (sy) XP_diff(nbytes, z, x, -y); else XP_sum (nbytes, z, x, y); z[nbytes-1] &= msb; <test for signed overflow 384> <check if signed y is too big 393> } else if (apply(MP_add, z, x, y)) RAISE(MP_Overflow); return z; } <check if signed y is too big 393>≡ if (nbits < 8 && (y < -(1<<(nbits-1)) || y >= (1<<(nbits-1)))) RAISE(MP_Overflow);
The cases for signed subtraction are just the opposite of those for addition (see page 340 for AP_sub’s case):
y < 0 | y ≥ 0 | |
x < 0 | −(|x| − |y|) = x + |y| | −(|x| + |y|) = x − |y| |
x ≥ 0 | |x| + |y| = x + |y| | |x| − |y| = x − | y| |
So, MP_subi calls XP_sum to add |y| to any x when y is negative, and calls XP_diff when y is nonnegative.
<functions 381>+≡ T MP_subi(T z, T x, long y) { <checked runtime errors for unary functions 381> if (-BASE < y && y < BASE) { int sx = sign(x), sy = y < 0; if (sy) XP_sum (nbytes, z, x, -y); else XP_diff(nbytes, z, x, y); z[nbytes-1] &= msb; <test for signed underflow 384> <check if signed y is too big 393> } else if (apply(MP_sub, z, x, y)) RAISE(MP_Overflow); return z; }
MP_muli uses MP_mul’s strategy: It negates negative operands, computes the product by calling XP_product, and negates the product when the operands have different signs.
<functions 381>+≡ T MP_muli(T z, T x, long y) { <checked runtime errors for unary functions 381> if (-BASE < y && y < BASE) { int sx = sign(x), sy = y < 0; <if x <0, negate x 386> XP_product(nbytes, z, x, sy ? -y : y); if (sx != sy) XP_neg(nbytes, z, x, 1); z[nbytes-1] &= msb; if (sx == sy && sign(z)) RAISE(MP_Overflow); <check if signed y is too big 393> } else if (apply(MP_mul, z, x, y)) RAISE(MP_Overflow); return z; }
MP_divi and MP_modi must check for a zero divisor, because they call XP_quotient to compute the quotient and remainder. MP_divi discards the remainder, and MP_modi discards the quotient:
<functions>+≡ T MP_divi(T z, T x, long y) { <checked runtime errors for unary functions 381> if (y == 0) RAISE(MP_Dividebyzero); else if (-BASE < y && y < BASE) { int r; <z ← x/y, r ← x mod y 395> <check if signed y is too big 393> } else if (apply(MP_div, z, x, y)) RAISE(MP_Overflow); return z; } long MP_modi(T x, long y) { assert(x); if (y == 0) RAISE(MP_Dividebyzero); else if (-BASE < y && y < BASE) { T z = tmp[2]; int r; <z ← x/y, r ← x mod y 395> <check if signed y is too big 393> return r; } else if (apply(MP_mod, tmp[2], x, y)) RAISE(MP_Overflow); return MP_toint(tmp[2]); }
MP_modi calls MP_toint instead of XP_toint to ensure that the sign is extended properly.
The chunk common to both MP_divi and MP_modi computes the quotient and the remainder, and adjusts the quotient and remainder when x and y have different signs and the remainder is nonzero.
<z ← x/y, r ← x mod y 395>≡ int sx = sign(x), sy = y < 0; <if x <0, negate x 386> r = XP_quotient(nbytes, z, x, sy ? -y : y); if (sx != sy) { XP_neg(nbytes, z, z, 1); if (r != 0) { XP_diff(nbytes, z, z, 1); r = y - r; } z[nbytes-1] &= msb; } else if (sx && sign(z)) RAISE(MP_Overflow);
Unsigned comparison is easy — MP_cmp can just call XP_cmp:
<functions 381>+≡
int MP_cmpu(T x, T y) {
assert(x);
assert(y);
return XP_cmp(nbytes, x, y);
}When x and y have different signs, MP_cmp(x,y) simply returns the difference of the signs of y and x:
<functions 381>+≡
int MP_cmp(T x, T y) {
int sx, sy;
assert(x);
assert(y);
sx = sign(x);
sy = sign(y);
if (sx != sy)
return sy - sx;
else
return XP_cmp(nbytes, x, y);
}When x and y have the same signs, MP_cmp can treat them as unsigned numbers and call XP_cmp to compare them.
The comparison convenience functions can’t use applyu and apply, because they compute integer results, and because they don’t insist that their long or unsigned long operands fit in an MP_T. These functions simply compare an MP_T with an immediate value; when the value is too big, that will be reflected in the outcome of the comparison. When an unsigned long has at least nbits bits, MP_cmpui converts the MP_T to an unsigned long and uses the usual C comparisons. Otherwise, it converts the immediate value to an MP_T in tmp[2] and calls XP_cmp.
<functions 381>+≡ int MP_cmpui(T x, unsigned long y) { assert(x); if ((int)sizeof y >= nbytes) { unsigned long v = XP_toint(nbytes, x); <return − 1, 0, + 1, if v < y, v = y, v > y 396> } else { XP_fromint(nbytes, tmp[2], y); return XP_cmp(nbytes, x, tmp[2]); } } <return −1, 0, +1, if v < y, v = y, v > y 396>≡ if (v < y) return -1; else if (v > y) return 1; else return 0;
MP_cmpui doesn’t have to check for overflow after it calls XP_fromint, because that call is made only when y has fewer bits than an MP_T.
MP_cmpi can avoid comparisons altogether when x and y have different signs. Otherwise, it uses MP_cmpui’s approach: If the immediate value has at least as many bits as an MP_T, the comparison can be done with C comparisons.
<functions 374>+≡ int MP_cmpi(T x, long y) { int sx, sy = y < 0; assert(x); sx = sign(x); if (sx != sy) return sy - sx; else if ((int)sizeof y >= nbytes) { long v = MP_toint(x); <return −1, 0, +1, if v < y, v = y, v > y 396> } else { MP_fromint(tmp[2], y); return XP_cmp(nbytes, x, tmp[2]); } }
When x and y have the same signs and y has fewer bits than an MP_T, MP_cmpi can safely convert y to an MP_T in tmp[2], and then call XP_cmp to compare x and tmp[2]. MP_cmpi calls MP_fromint instead of XP_fromint in order to handle negative values of y correctly.
The binary logical functions — MP_and, MP_or, and MP_xor — are the easiest MP functions to implement because each byte of the result is a bitwise operation on the corresponding bytes in the operands:
<macros 374>+≡ #define bitop(op) int i; assert(z); assert(x); assert(y); for (i = 0; i < nbytes; i++) z[i] = x[i] op y[i]; return z <functions 374>+≡ T MP_and(T z, T x, T y) { bitop(&); } T MP_or (T z, T x, T y) { bitop(|); } T MP_xor(T z, T x, T y) { bitop(^); }
MP_not is the oddball that doesn’t fit bitop’s pattern:
<functions 374>+≡ T MP_not(T z, T x) { int i; <checked runtime errors for unary functions 378> for (i = 0; i < nbytes; i++) z[i] = ~x[i]; z[nbytes-1] &= msb; return z; }
There’s little to be gained from writing special-case code for single-digit operands to the three logical convenience functions, and immediate operands to these functions don’t cause an exception. applyu can still be used; its return value is simply ignored.
<macros 374>+≡ #define bitopi(op) assert(z); assert(x); applyu(op, z, x, y); return z <functions 374>+≡ T MP_andi(T z, T x, unsigned long y) { bitopi(MP_and); } T MP_ori (T z, T x, unsigned long y) { bitopi(MP_or); } T MP_xori(T z, T x, unsigned long y) { bitopi(MP_xor); }
The three shift functions call XP_lshift or XP_rshift, after enforcing their checked runtime errors, and after checking for the easy case when s exceeds or is equal to nbits, in which case, the result is all zeroes or all ones. XP_ashift fills with ones and thus implements an arithmetic right shift.
<macros 374>+≡ #define shft(fill, op) assert(x); assert(z); assert(s >= 0); if (s >= nbits) memset(z, fill, nbytes); else op(nbytes, z, nbytes, x, s, fill); z[nbytes-1] &= msb; return z <functions 374>+≡ T MP_lshift(T z, T x, int s) { shft(0, XP_lshift); } T MP_rshift(T z, T x, int s) { shft(0, XP_rshift); } T MP_ashift(T z, T x, int s) { shft(sign(x),XP_rshift); }
The last four functions convert between strings and MP_Ts. MP_fromstr is like strtoul; it interprets the string as an unsigned number in a base between two and 36, inclusive. Letters specify the digits above nine in bases that exceed 10.
<functions 374>+≡ T MP_fromstr(T z, const char *str, int base, char **end){ int carry; assert(z); memset(z, ' ', nbytes); carry = XP_fromstr(nbytes, z, str, base, end); carry |= z[nbytes-1]&~msb; z[nbytes-1] &= msb; <test for unsigned overflow 376> return z; }
XP_fromstr does the conversion and sets *end to the address of the character that terminated the conversion, if end is nonnull. z is initialized to zero because XP_fromint adds the converted value to z.
MP_tostr performs the opposite conversion: It takes an MP_T and fills a string with the string representation of the MP_T’s value in a base between two and 36, inclusive.
<functions 374>+≡ char *MP_tostr(char *str, int size, int base, T x) { assert(x); assert(base >= 2 && base <= 36); assert(str == NULL || size > 1); if (str == NULL) { <size ← number of characters to represent x in base 400> str = ALLOC(size); } memcpy(tmp[1], x, nbytes); XP_tostr(str, size, base, nbytes, tmp[1]); return str; }
If str is null, MP_tostr allocates a string long enough to hold x’s representation in base. MP_tostr uses AP_tostr’s trick for computing the size of the string: str must have at least ⌈nbits/k⌉ characters, where k is chosen so that 2k is the largest power of two less than or equal to base (see page 352), plus one for the terminating null character.
<size ← number of characters to represent x in base 400>≡
{
int k;
for (k = 5; (1<<k) > base; k--)
;
size = nbits/k + 1 + 1;
}The Fmt-style conversion functions format an unsigned or signed MP_T. Each consumes two arguments: an MP_T and a base between two and 36, inclusive. MP_fmtu calls MP_tostr to convert its MP_T, and calls Fmt_putd to emit the converted result. Recall that Fmt_putd emits a number in the style of printf’s %d conversion.
<functions 374>+≡
void MP_fmtu(int code, va_list *app,
int put(int c, void *cl), void *cl,
unsigned char flags[], int width, int precision) {
T x;
char *buf;
assert(app && flags);
x = va_arg(*app, T);
assert(x);
buf = MP_tostr(NULL, 0, va_arg(*app, int), x);
Fmt_putd(buf, strlen(buf), put, cl, flags,
width, precision);
FREE(buf);
}MP_fmt has a bit more work to do, because it interprets an MP_T as a signed number, but MP_tostr accepts only unsigned MP_Ts. Thus, MP_fmt itself allocates the buffer, so that it can include a leading sign, if necessary.
<functions 374>+≡ void MP_fmt(int code, va_list *app, int put(int c, void *cl), void *cl, unsigned char flags[], int width, int precision) { T x; int base, size, sx; char *buf; assert(app && flags); x = va_arg(*app, T); assert(x); base = va_arg(*app, int); assert(base >= 2 && base <= 36); sx = sign(x); <if x <0, negate x 386> <size ← number of characters to represent x in base 400> buf = ALLOC(size+1); if (sx) { buf[0] = '-'; MP_tostr(buf + 1, size, base, x); } else MP_tostr(buf, size + 1, base, x); Fmt_putd(buf, strlen(buf), put, cl, flags, width, precision); FREE(buf); }
Multiple-precision arithmetic is often used in compilers, and sometimes it must be used. For example, Clinger (1990) shows that converting floating-point literals to their corresponding IEEE floating-point representations sometimes requires multiple-precision arithmetic to achieve the best accuracy.
Schneier (1996) is a comprehensive survey of cryptography. This book is practical, and includes C implementations for some of the algorithms it describes. It also has extensive bibliography that is a good starting point for deeper investigations.
As shown on page 308, multiplying two n-digit numbers takes time proportional to n2. Section 20.6 in Press et al. (1992) shows how to use the fast Fourier transform to implement multiplication in time proportional to n lg n lg lg n. It also implements x/y by computing the reciprocal 1/y and multiplying it by x. This approach requires multiple-precision numbers with fractional parts.
19.1 | The |
19.2 | For many applications, once chosen, |
19.3 | Design and implement an interface for arithmetic on fixed-point, multiple-precision numbers; that is, numbers with a whole part and a fractional part. Clients should be able to specify the number of digits in both parts. Be sure to specify the details of rounding. Section 20.6 in Press et al. (1992) includes some useful algorithms for this exercise. |
19.4 | Design and implement an interface for arithmetic on floating-point numbers in which clients can specify the number of bits in the exponent and in the significand. Read Goldberg (1991) before attempting this exercise. |
19.5 | The typedef unsigned char T[]; then “ unsigned char *MP_add(T z, const T x, const T y); In typedef unsigned char T; With this definition, the declaration for T *MP_add(T z[], const T x[], const T y[]); T *MP_add(T *z, T *x, T *y); Reimplement |