where we assume a ≥ b . For addition this condition represents no restriction, since it can always be achieved by interchanging the two summands. For subtraction it means that the difference is positive or zero and therefore can be represented as a CLINT object without reduction modulo ( N _max + 1).

Addition consists essentially of the following steps.

Algorithm for the addition a + b

1. Set i ← 0 and c ← 0.

2. Set t ← a _i + b _i + c , s _i ← t mod B , and c ← ⌊ t / B ⌋ .

3. Set i ← i + 1; if i ≤ n − 1, go to step 2.

4. Set t ← a _i + c , s _i ← t mod B , and c ← ⌊ t / B ⌋ .

5. Set i ← i + 1; if i ≤ m − 1, go to step 4.

6. Set s _m ← c .

7. Output s = ( s _m s _{m − 1} … s ) _B .

The digits of the summands, together with the carry, are added in step 2, with the less-significant part stored as a digit of the sum, while the more-significant part is carried to the next digit. If the most-significant digit of one of the summands is reached, then in step 4 any remaining digits of the other summand are added to any remaining carries one after the other. Until the last summand digit is processed , the less-significant part is stored as a digit of the sum, and the more-significant part is used as a carry to the next digit. Finally, if there is a leftover carry at the end, it is stored as the most-significant digit of the sum. The output of this digit is suppressed if it has the value zero.

Steps 2 and 4 of the algorithm appear in a similar form in the case of subtraction, multiplication, and division. The associated code, which is illustrated by the following lines, is typical for arithmetic functions: ^[1]

s = (USHORT)(carry = (ULONG)a + (ULONG)b + (ULONG)(USHORT)(carry >> BITPERDGT));

The intermediate value t that appears in the algorithm is represented by the variable carry , of type ULONG , which holds the sum of the digits a _i and b _i as well as the carry of the previous operation. The new summation digit s _i is stored in the less-significant part of carry , from where it is taken by means of a cast as a USHORT . The resulting carry from this operation is held in the more-significant part of carry for the next operation.

The implementation of this algorithm by our function add_l() deals with a possible overflow of the sum, where in this case a reduction of the sum modulo ( N _max + 1) is carried out.

int add_l (CLINT aa_l, CLINT bb_l, CLINT ss_l) { clint ss_l[CLINTMAXSHORT + 1]; clint *msdptra_l, *msdptrb_l; clint *aptr_l, *bptr_l, *sptr_l = LSDPTR_L (ss_l); ULONG carry = 0L; int OFL = E_CLINT_OK;

The pointers for the addition loop are set. Here it is checked which of the two summands has the greater number of digits. The pointers aptr_l and msdaptr_l are initialized such that they point respectively to the least-significant and most-significant digits of the summand that has the most digits, or to those digits of a_l if both summands are of the same length. This holds analogously for the pointers bptr_l and msdbptr_l , which point to the least-significant and most-significant digits of the shorter summand, or to those digits of b_l . The initialization is carried out with the help of the macro LSDPTR_L() for the least-significant digits and MSDPTR_L() for the most-significant digits of a CLINT object. The macro DIGITS_L (a_l) specifies the number of digits of the CLINT object a_l , and with SETDIGITS_L(a_l, n) the number of digits of a_l is set to the value n .

if (DIGITS_L (a_l) < DIGITS_L (b_l)) { aptr_l = LSDPTR_L (b_l); bptr_l = LSDPTR_L (a_l); msdptra_l = MSDPTR_L (b_l); msdptrb_l = MSDPTR_L (a_l); SETDIGITS_L (ss_l, DIGITS_L (b_l)); } else { aptr_l = LSDPTR_L (a_l); bptr_l = LSDPTR_L (b_l); msdptra_l = MSDPTR_L (a_l); msdptrb_l = MSDPTR_L (b_l); SETDIGITS_L (ss_l, DIGITS_L (a_l)); }

In the first loop of add_l the digits of a_l and b_l are added and stored in the result variable ss_l . Any leading zeros cause no problem, and they are simply used in the calculation and filtered out when the result is copied to s_l . The loop runs from the least-significant digit of b_l to the most-significant digit. This corresponds exactly to the process of pencil-and-paper addition as learned at school. As promised , here is the implementation of the carry.

while (bptr_l <= msdptrb_l) { *sptr_l++ = (USHORT)(carry = (ULONG)*aptr_l++ + (ULONG)*bptr_l++ + (ULONG)(USHORT)(carry >> BITPERDGT)); }

The two USHORT values *aptr and *bptr are copied via a cast to ULONG representation and added. To this the carry from the last interation is added. The result is a ULONG value that contains the carry from the addition step in its higher-valued word. This value is allocated to the variable carry and there reserved for the next iteration. The value of the resulting digit is taken from the lower-valued word of the addition result via a cast to the type USHORT . The carry saved in the higher-valued word of carry is included in the next iteration by a shift to the right by the number BITPERDGT of bits used for the representation of USHORT and a cast to USHORT .

In the second loop only the remaining digits of a_l are added to a possible existing carry and stored in s_l .

while (aptr_l <= msdptra_l) { *sptr_l++ = (USHORT)(carry = (ULONG)*aptr_l++ + (ULONG)(USHORT)(carry >> BITPERDGT)); }

If after the second loop there is a carry, the result is one digit longer than a_l . If it is determined that the result exceeds the maximal value N _max representable by the CLINT type, then the result is reduced modulo ( N _max + 1) (see Chapter 5), analogously to the treatment of standard unsigned types. In this case the status announcement of the error code E_CLINT_OFL is returned.

if (carry & BASE) { *sptr_l = 1; SETDIGITS_L (ss_l, DIGITS_L (ss_l) + 1); } if (DIGITS_L (ss_l) > (USHORT)CLINTMAXDIGIT) /* overflow? */ { ANDMAX_L (ss_l); /* reduce modulo (Nmax + 1) */ OFL = E_CLINT_OFL; } cpy_l (s_l, ss_l); return OFL; }

The run time t of all the procedures given here for addition and subtraction is t = O ( n ), and thus proportional to the number of digits of the larger of the two operands.

Now that we have seen addition, we shall present the algorithm for subtraction of two numbers a and b with representations

to base B .

Algorithm for the subtraction a − b

1. Set i ← 0 and c ← 1.

2. If c = 1, set t ← B + a _i − b _i ; otherwise , set t ← B − 1 + a _i − b _i .

3. Set s _i ← t mod B and c ← ⌊ t / B ⌋ .

4. Set i ← i + 1; if i ≤ n − 1, go to step 2.

5. If c = 1, set t ← B + a _i ; otherwise, set t ← B − 1 + a _i .

6. Set s _i ← t mod B and c ← ⌊ t / B ⌋ .

7. Set i ← i + 1; if i ≤ m − 1, go to step 5.

8. Output s = ( s _{m − 1} s _{m − 2} … s ) _B .

The implementation of subtraction is identical to that of addition, with the following exceptions:

• The ULONG variable carry is used to " borrow " from the next-higher digit of the minuend if a digit of the minuend is smaller than the corresponding digit of the subtrahend.

• Instead of an overflow one must be on the lookout for a possible underflow, in which case the result of the subtraction would actually be negative; however, since CLINT is an unsigned type, there will be a reduction modulo ( N _max + 1) (see Chapter 5). The function returns the error code E_CLINT_UFL to indicate this situation.

• Finally, any existing leading zeros are eliminated.

Thus we obtain the following function, which subtracts a CLINT number b_l from a number a_l .

int sub_l (CLINT aa_l, CLINT bb_l, CLINT d_l) { CLINT b_l; clint a_l[CLINTMAXSHORT + 1]; /* allow 1 additional digit in a_l */ clint *msdptra_l, *msdptrb_l; clint *aptr_l = LSDPTR_L (a_l); clint *bptr_l = LSDPTR_L (b_l); clint *dptr_l = LSDPTR_L (d_l); ULONG carry = 0L; int UFL = E_CLINT_OK; cpy_l (a_l, aa_l); cpy_l (b_l, bb_l); msdptra_l = MSDPTR_L (a_l); msdptrb_l = MSDPTR_L (b_l);

In the following the case a_l < b_l is considered , in which b_l is subtracted not from a_l , but from the largest possible value, N _max . Later, the value (minuend+1) is added to this difference, so that altogether the calculation is carried out modulo ( N _max + 1). To generate the value N _max the auxiliary function setmax_l() is used.

if (LT_L (a_l, b_l)) { setmax_l (a_l); msdptra_l = a_l + CLINTMAXDIGIT; SETDIGITS_L (d_l, CLINTMAXDIGIT); UFL = E_CLINT_UFL; } else { SETDIGITS_L (d_l, DIGITS_L (a_l)); } while (bptr_l <= msdptrb_l) { *dptr_l++ = (USHORT)(carry = (ULONG)*aptr_l++ - (ULONG)*bptr_l++ - ((carry & BASE) >> BITPERDGT)); } while (aptr_l <= msdptra_l) { *dptr_l++ = (USHORT)(carry = (ULONG)*aptr_l++ - ((carry & BASE) >> BITPERDGT)); } RMLDZRS_L (d_l);

The required addition of (minuend + 1) to the difference N _max − b_l stored in d_l is carried out before the output of d_l .

if (UFL) { add_l (d_l, aa_l, d_l); inc_l (d_l); } return UFL; }

In addition to the functions add_l() and sub_l() two special functions for addition and subtraction are available, which operate on a USHORT as the second argument instead of a CLINT . These are called mixed functions and identified by a function name with a prefixed " u ," as in the functions uadd_l() and usub_l() to follow. The use of the function u2clint_l() for converting a USHORT value into a CLINT object follows in anticipation of its discussion in Chapter 8.

int uadd_l (CLINT a_l, USHORT b, CLINT s_l) { int err; CLINT tmp_l; u2clint_l (tmp_l, b); err = add_l (a_l, tmp_l, s_l); return err; }

{% if main.adsdop %}{% include 'adsenceinline.tpl' %}{% endif %}

int usub_l (CLINT a_l, USHORT b, CLINT d_l) { int err; CLINT tmp_l; u2clint_l (tmp_l, b); err = sub_l (a_l, tmp_l, d_l); return err; }

Two further useful special cases of addition and subtraction are realized in the functions inc_l() and dec_l() , which increase or decrease a CLINT value by 1. These functions are designed as accumulator routines: The operand is overwritten with the return value, which has proved practical in the implementation of many algorithms.

It is not surprising that the implementations of inc_l() and dec_l() are similar to those of the functions add_l() and sub_l() . They test for overflow and underflow, respectively, and return the corresponding error codes E_CLINT_OFL and E_CLINT_UFL .

int inc_l (CLINT a_l) { clint *msdptra_l, *aptr_l = LSDPTR_L (a_l); ULONG carry = BASE; int OFL = E_CLINT_OK; msdptra_l = MSDPTR_L (a_l); while ((aptr_l <= msdptra_l) && (carry & BASE)) { *aptr_l = (USHORT)(carry = 1UL + (ULONG)*aptr_l); aptr_l++; } if ((aptr_l > msdptra_l) && (carry & BASE)) { *aptr_l = 1; SETDIGITS_L (a_l, DIGITS_L (a_l) + 1); if (DIGITS_L (a_l) > (USHORT) CLINTMAXDIGIT) /* overflow ? */ { SETZERO_L (a_l); /* reduce modulo (Nmax + 1) */ OFL = E_CLINT_OFL; } } return OFL; }

int dec_l (CLINT a_l) { clint *msdptra_l, *aptr_l = LSDPTR_L (a_l); ULONG carry = DBASEMINONE; if (EQZ_L (a_l)) /* underflow ? */ { setmax_l (a_l); /* reduce modulo max_l */ return E_CLINT_UFL; } msdptra_l = MSDPTR_L (a_l); while ((aptr_l <= msdptra_l) && (carry & (BASEMINONEL << BITPERDGT))) { *aptr_l = (USHORT)(carry = (ULONG)*aptr_l - 1L); aptr_l++; } RMLDZRS_L (a_l); return E_CLINT_OK; }

^[1] The C expression in this compact form is due to my colleague Robert Hammelrath.

---

Team-Fly