3.2.1 Copying an mp_int

Assigning the value that a given mp_int structure represents to another mp_int structure shall be known as making a copy for the purposes of this text. The copy of the mp_int will be a separate entity that represents the same value as the mp_int it was copied from. The mp_copy algorithm provides this functionality (Figure 3.1).

Algorithm mp_copy. This algorithm copies the mp_int a such that upon successful termination of the algorithm, the mp_int b will represent the same integer as the mp_int a. The mp_int b shall be a complete and distinct copy of the mp_int a, meaning that the mp_int a can be modified and it shall not affect the value of the mp_int b.

If b does not have enough room for the digits of a, it must first have its precision augmented via the mp_grow algorithm. The digits of a are copied over the digits of b, and any excess digits of b are set to zero (steps two and three). The used and sign members of a are finally copied over the respective members of b.

Remark. This algorithm also introduces a new idiosyncrasy that will be used throughout the rest of the text. The error return codes of other algorithms are not explicitly checked in the pseudo-code presented. For example, in step one of the mp_copy algorithm, the return of mp_grow is not explicitly checked to ensure it succeeded. Text space is limited so it is assumed that if an algorithm fails it will clear all temporarily allocated mp_ints and return the error code itself. However, the C code presented will demonstrate all of the error handling logic required to implement the pseudo-code.

Occasionally, a dependent algorithm may copy an mp_int effectively into itself such as when the input and output mp_int structures passed to a function are one and the same. For this case, it is optimal to return immediately without copying digits (Line 25).

The mp_int b must have enough digits to accommodate the used digits of the mp_int a. If b.alloc is less than a.used, the algorithm mp_grow is used to augment the precision of b (lines 30 to 33). To simplify the inner loop that copies the digits from a to b, two aliases tmpa and tmpb point directly at the digits of the mp_ints a and b, respectively. These aliases (lines 43 and 46) allow the compiler to access the digits without first dereferencing the mp_int pointers and then subsequently the pointer to the digits.

After the aliases are established, the digits from a are copied into b(lines 49 to 51) and then the excess digits of b are set to zero (lines 54 to 56). Both “for” loops make use of the pointer aliases, and in fact the alias for b is carried through into the second “for” loop to clear the excess digits. This optimization allows the alias to stay in a machine register fairly easy between the two loops.

Remarks. The use of pointer aliases is an implementation methodology first introduced in this function that will be used considerably in other functions. Technically, a pointer alias is simply a shorthand alias used to lower the number of pointer dereferencing operations required to access data. For example, a for loop may resemble

This could be re-written using aliases as

In this case, an alias is used to access the array of digits within an mp_int structure directly. It may seem that a pointer alias is strictly not required, as a compiler may optimize out the redundant pointer operations. However, there are two dominant reasons to use aliases.

The first reason is that most compilers will not effectively optimize pointer arithmetic. For example, some optimizations may work for the Microsoft Visual C++ compiler (MSVC) and not for the GNU C Compiler (GCC). Moreover, some optimizations may work for GCC and not MSVC. As such it is ideal to find a common ground for as many compilers as possible. Pointer aliases optimize the code considerably before the compiler even reads the source code, which means the end compiled code stands a better chance of being faster.

The second reason is that pointer aliases often can make an algorithm simpler to read. Consider the first “for” loop of the function mp_copy() re-written to not use pointer aliases.

Whether this code is harder to read depends strongly on the individual. However, it is quantifiably slightly more complicated, as there are four variables within the statement instead of just two.

3.2.2 Creating a Clone

Another common operation is to make a local temporary copy of an mp_int argument. To initialize an mp_int and then copy another existing mp_int into the newly initialized mp_int will be known as creating a clone. This is useful within functions that need to modify an argument but do not wish to modify the original copy. The mp_init_copy algorithm has been designed to help perform this task (Figure 3.2).

Algorithm mp_init_copy. This algorithm will initialize an mp_int variable and copy another previously initialized mp_int variable into it. As such, this algorithm will perform two operations in one step.

This will initialize a and make it a verbatim copy of the contents of b. Note that a will have its own memory allocated, which means that b may be cleared after the call and a will be left intact.

3.4.1 Absolute Value

With the mp_int representation of an integer, calculating the absolute value is trivial. The mp_abs algorithm will compute the absolute value of an mp_int (Figure 3.4).

Algorithm mp_abs. This algorithm computes the absolute of an mp_int input. First, it copies a over b. This is an example of an algorithm where the check in mp_copy that determines if the source and destination are equal proves useful. This allows, for instance, the developer to pass the same mp_int as the source and destination to this function without additional logic to handle it.

This fairly trivial algorithm first eliminates non-required duplications (Line 28) and then sets the sign flag to MP_ZPOS.

3.4.2 Integer Negation

With the mp_int representation of an integer, calculating the negation is also trivial. The mp_neg algorithm will compute the negative of an mp_int input (Figure 3.5).

Algorithm mp_neg. This algorithm computes the negation of an input. First, it copies a over b. If a has no used digits, then the algorithm returns immediately. Otherwise, it flips the sign flag and stores the result in b. Note that if a had no digits, then it must be positive by definition. Had step three been omitted, the algorithm would return zero as negative.

Like mp_abs(), this function avoids non-required duplications (Line 22) and then sets the sign. We have to make sure that only non-zero values get a sign of MP_NEG. If the mp_int is zero, the sign is hard-coded to MP_ZPOS.

3.5.1 Setting Small Constants

Often, a mp_int must be set to a relatively small value such as 1 or 2. For these cases, the mp_set algorithm is useful (Figure 3.6).

Algorithm mp_set. This algorithm sets a mp_int to a small single digit value. Step number 1 ensures that the integer is reset to the default state. The single digit is set (modulo β) and the used count is adjusted accordingly.

First, we zero (Line 21) the mp_int to make sure the other members are initialized for a small positive constant. mp_zero() ensures that the sign is positive and the used count is zero. Next, we set the digit and reduce it modulo β(Line 22). After this step, we have to check if the resulting digit is zero or not. If it is not, we set the used count to one, otherwise to zero.

We can quickly reduce modulo β since it is of the form 2^k, and a quick binary AND operation with 2^k −1 will perform the same operation.

One important limitation of this function is that it will only set one digit. The size of a digit is not fixed, meaning source that uses this function should take that into account. Only trivially small constants can be set using this function.

3.5.2 Setting Large Constants

To overcome the limitations of the mp_set algorithm, the mp_set_int algorithm is ideal. It accepts a “long” data type as input and will always treat it as a 32-bit integer (Figure 3.7).

Algorithm mp_set_int. The algorithm performs eight iterations of a simple loop where in each iteration, four bits from the source are added to the mp_int. Step 2.1 will multiply the current result by sixteen, making room for four more bits in the less significant positions. In Step 2.2, the next four bits from the source are extracted and are added to the mp_int. The used digit count is incremented to reflect the addition. The used digit counter is incremented since if any of the leading digits were zero, the mp_int would have zero digits used and the newly added four bits would be ignored.

Excess zero digits are trimmed in steps 2.1 and 3 by using higher level algorithms mp_mul2d and mp_clamp.

This function sets four bits of the number at a time to handle all practical DIGIT_BIT sizes. The addition on Line 39 ensures that the newly added in bits are added to the number of digits. While it may not seem obvious as to why the digit counter does not grow exceedingly large, it is because of the shift on Line 28 and the call to mp_clamp() on Line 41. Both functions will clamp excess leading digits, which keeps the number of used digits low.

3.6.1 Unsigned Comparisons

Comparing a multiple precision integer is performed with the same algorithm used to compare two decimal numbers. For example, to compare 1, 234 to 1, 264, the digits are extracted by their positions. That is, we compare 1 · 10³ + 2 · 10² + 3 · 10¹ + 4 · 10⁰ to 1 · 10³ + 2 · 10² + 6 · 10¹ +4 · 10⁰ by comparing single digits at a time, starting with the highest magnitude positions. If any leading digit of one integer is greater than a digit in the same position of another integer, then obviously it must be greater.

The first comparison routine that will be developed is the unsigned magnitude compare, which will perform a comparison based on the digits of two mp_int variables alone. It will ignore the sign of the two inputs. Such a function is useful when an absolute comparison is required or if the signs are known to agree in advance.

To facilitate working with the results of the comparison functions, three constants are required (Figure 3.8).

Algorithm mp_cmp_mag. By saying “ a to the left of b,” it is meant that the comparison is with respect to a. That is, if a is greater than b it will return MP_GT and similar with respect to when a = b and a > b. The first two steps compare the number of digits used in both a and b. Obviously, if the digit counts differ there would be an imaginary zero digit in the smaller number where the leading digit of the larger number is. If both have the same number of digits, the actual digits themselves must be compared starting at the leading digit (Figure 3.9).

By step three, both inputs must have the same number of digits so, it is safe to start from either a.used − 1 or b.used − 1 and count down to the zero′th digit. If after all of the digits have been compared and no difference is found, the algorithm returns MP_EQ.

The two if statements (lines 25 and 29) compare the number of digits in the two inputs. These two are performed before all the digits are compared, since it is a very cheap test to perform and can potentially save considerable time. The implementation given is also not valid without those two statements. b.alloc may be smaller than a.used, meaning that undefined values will be read from b past the end of the array of digits.

3.6.2 Signed Comparisons

Comparing with sign comparisons is also fairly critical in several routines (division, for example). Based on an unsigned magnitude comparison, a trivial signed comparison algorithm can be written.

Algorithm mp_cmp. The first two steps compare the signs of the two inputs. If the signs do not agree, then it can return right away with the appropriate comparison code. When the signs are equal, the digits of the inputs must be compared to determine the correct result. In step three, the unsigned comparison flips the order of the arguments since they are both negative. For instance, if –a > – b then |a| >|b|. Step four will compare the two when they are both positive (Figure 3.10).

The two if statements (lines 23 and 24) perform the initial sign comparison. If the signs are not equal, then whichever has the positive sign is larger. The inputs are compared (Line 32) based on magnitudes. If the signs were both negative, then the unsigned comparison is performed in the opposite direction (Line 34). Otherwise, the signs are assumed to be positive and a forward direction unsigned comparison is performed.

Exercises