README for libmpi - Public-Domain Multiple Precision Integer Library This library was part of a compiler project -- specifically, part of libcrt, the C runtime library. Suppose one was working on an i86 (which had 16-bit or 2-byte integers) and wanted to emulate a Cray (which had 64-bit or 8-byte integers). One would have to write a multiple-precision integer library to do the 8-byte integer math on the i86. I wrote this library to simplify matters and because the C runtime library of just about any compiler would have something like this under the hood. The compiler would then spit out the assembler to call these functions if the function was more than a few assembler statements. (For example, an assembler routine to do 4-byte division on an i86 is in the mach/i86 directory.) When the compiler needs to perform a mathematical operation on an operand or two or three, if full optimizations are on, it first checks if all operands are constants, in which it could just fold them and put the result where the operation should be. If that doesn't work, then the optimizer could attempt to reduce the strength of the operation; i.e. reduce a multiply or a divide to a shift. If there's still something left to be done, then the compiler's code generator can check if the operation takes just a few assembler instructions, and if so, output them. If the operation takes longer than that, then the code generator looks for an optimized routine in the C runtime library and calls it. Finally, if all else fails, the code generator picks a generic routine to do the operation. This library is a library of generic routines to do the math for any size of integer, signed or unsigned. It assumes that bytes and ints aren't the same size and that an int is at least two bytes long. Some routines unroll loops for speed, but the loop unrolling can be turned off by defining the macro _OPTIMIZED_FOR_SIZE when compiling the library. The library assumes two's-complement integers and can be compiled for one of four byte orderings (PCs normally are little-endian). The main integer type (which can be signed or unsigned) is a simple pointer to the first character in the integer, no matter what the byte ordering. I designed it so that the result pointer (usually c) can be the same as the pointer to the left-hand side of the equation (usually a). This means that the assignment operators besides = can be implemented with calls to the same functions as the normal operators. The = operator can be implemented with _Cpy. I put this library in the public domain because I want it to be used in any program no matter what the license without affecting the license of said program. This library emulates something that would be deep within the system, and probably the programmer would use something like this without even knowing it. The nitty gritty: First, the data type: typedef unsigned char *_MPI_T; _MPI_T is the main data type for multiprecision integers and can point to integers of any size, signed or unsigned. The functions in the library: First, when precision is mentioned, it means the size of an integer in bytes. All these functions take precisions. _MPI_T _Adi (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function implements c = a + b where all integers are signed and have precision prec. It returns c. _MPI_T _Adu (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function implements c = a + b where all integers are unsigned and have precision prec. It returns c. _MPI_T _And (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function implements c = a & b where all integers have precision prec. It returns c. _MPI_T _Cii (_MPI_T c, int cprec, _MPI_T a, int aprec); This function converts a signed integer a with precision aprec to a signed integer c with precision cprec. It returns c. _MPI_T _Ciu (_MPI_T c, int cprec, _MPI_T a, int aprec); This function converts a signed integer a with precision aprec to an unsigned integer c with precision cprec. It returns c. int _Cmp (_MPI_T a, _MPI_T b, int prec); This function does an unsigned comparison of a and b and returns -1 if a < b, 0 if a == b, and +1 if a > b. Both a and b have precision prec. This function is called by the other comparison functions to do that dirty work. void *_Cpy (void *d, const void *s, size_t n); This function is the same as memmove. It copies n bytes from s to d, taking care if the regions overlap. This function exists because this library was not meant to be dependent on the C library. _MPI_T _Cui (_MPI_T c, int cprec, _MPI_T a, int aprec); This function converts a signed integer a with precision aprec to an unsigned integer with precision cprec. It returns c. _MPI_T _Cuu (_MPI_T c, int cprec, _MPI_T a, int aprec); This function converts an unsigned integer a with precision aprec to an unsigned integer with precision cprec. It returns c. _MPI_T _Dec (_MPI_T c, _MPI_T a, int prec); This function computes c = a - 1 in linear time and returns c. The precision of both a and c is prec. int _Div (_MPI_T q, _MPI_T r, _MPI_T a, _MPI_T b, int prec); This function is the backbone of the division and modulus functions. It computes the quotient and remainder of a/b by repeated subtraction. All the _MPI_T parameters are unsigned and have the precision prec. The function returns 0 if everything went okay and 1 if b was initially zero. _MPI_T _Dvi (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a / b unless b was initially zero. The variables a, b, and c are signed integers with precision prec. The function returns c unless b was initially zero, in which case it returns a null pointer. _MPI_T _Dvu (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a / b unless b was initially zero. The variables a, b, and c are unsigned integers with precision prec. The function returns c unless b was initially zero, in which case it returns a null pointer. int _Eqi (_MPI_T a, _MPI_T b, int prec); This function returns a == b. The variables are signed and have the precision prec. int _Equ (_MPI_T a, _MPI_T b, int prec); This function returns a == b. The variables are unsigned and have the precision prec. int _Gei (_MPI_T a, _MPI_T b, int prec); This function returns a >= b. The variables are signed and have the precision prec. int _Geu (_MPI_T a, _MPI_T b, int prec); This function returns a >= b. The variables are unsigned and have the precision prec. int _Gti (_MPI_T a, _MPI_T b, int prec); This function returns a > b. The variables are signed and have the precision prec. int _Gtu (_MPI_T a, _MPI_T b, int prec); This function returns a > b. The variables are unsigned and have the precision prec. _MPI_T _Inc (_MPI_T c, _MPI_T a, int prec); This function computes c = a + 1 in linear time. Both a and c have prec for a precision. The function returns c. _MPI_T _Ior (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a | b (inclusive or). All _MPI_Ts have prec for a precision. The function returns c. int _Lei (_MPI_T a, _MPI_T b, int prec); This function returns a <= b. The variables are signed and have the precision prec. int _Leu (_MPI_T a, _MPI_T b, int prec); This function returns a <= b. The variables are unsigned and have the precision prec. _MPI_T _Lsi (_MPI_T c, _MPI_T a, int b, int prec); This function computes c = a << b and returns c. The variables are signed integers with precision prec. _MPI_T _Lsu (_MPI_T c, _MPI_T a, int b, int prec); This function computes c = a << b and returns c. The variables are unsigned integers with precision prec. int _Lti (_MPI_T a, _MPI_T b, int prec); This function returns a < b. The variables are signed and have the precision prec. int _Ltu (_MPI_T a, _MPI_T b, int prec); This function returns a < b. The variables are unsigned and have the precision prec. _MPI_T _Mdi (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a % b and returns c if b was nonzero and a null pointer if b was initially zero. All three variables are signed and have the precision prec. _MPI_T _Mdu (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a % b and returns c if b was nonzero and a null pointer if b was initially zero. All three variables are unsigned and have the precision prec. _MPI_T _Mli (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a * b and returns c. All variables are signed; the precision for all variables is prec. _MPI_T _Mlu (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a * b and returns c. All variables are unsigned; the precision for all variables is prec. int _Nei (_MPI_T a, _MPI_T b, int prec); This function returns the value of a != b. The variables are signed and have prec for a precision. int _Neu (_MPI_T a, _MPI_T b, int prec); This function returns the value of a != b. The variables are unsigned and have prec for a precision. _MPI_T _Ngi (_MPI_T c, _MPI_T a, int prec); This function computes c = -a and returns c. Strangely enough, negation is defined for unsigned variables as c = 2^prec - a and this function handles that as well. Both a and c have precision prec. _MPI_T _Not (_MPI_T c, _MPI_T a, int prec); This function computes c = ~a and returns c. The precision of both a and c is prec. _MPI_T _Rsi (_MPI_T c, _MPI_T a, int b, int prec); This function computes c = a >> b and returns c. The variables are signed; the sign bit of a propagates through the shifted space. The precision of both a and c is prec. _MPI_T _Rsu (_MPI_T c, _MPI_T a, int b, int prec); This function computes c = a >> b and returns c. The variables are unsigned. The precision of both a and c is prec. _MPI_T _Sbi (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a - b and returns c. The variables are signed and have prec for a precision. _MPI_T _Sbu (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a - b and returns c. The variables are unsigned and have prec for a precision. int _Sgn (_MPI_T x, int prec); This function returns a 1 if the sign bit of x (or the most significant bit of x if x is unsigned) is set, otherwise 0. The precision of x is prec. _MPI_T _Xor (_MPI_T c, _MPI_T a, _MPI_T b, int prec); This function computes c = a ^ b and returns c. The precision of all the variables is prec. int _Zeq (_MPI_T x, int prec); This function returns 1 if x is zero, 0 otherwise. The prec parameter is the precision of x. This is equivalent to the ! operator. void *_Zer (void *c, size_t n); This function zeroes out the memory at c for a size n. It is the equivalent of the memset function with the second parameter being a null character ('\0'). It is in this library because this library should not have a dependence on the Standard C library. int _Zne (_MPI_T x, int prec); This function returns 1 if x is nonzero, 0 otherwise. The prec parameter is the precision of x. This function would be used at the tail end of the && and || operators so that a list of && or || operators in a row could be short- circuited with conditional jumps. Finally, I realize that some of this functionality could be better written in tight assembler than in C. To that end, the mach subdirectory will contain more machine-specific routines for certain situations. These also have to be in the public domain. Gregory Pietsch , 2020-09-02