And sprinkled just a bit Over each banana split.
"Contrariwise," continued Tweedledee, "if it was so, it might be; and if it were so, it would be: but as it isn't, it ain't. That's logic."
In this chapter we shall present functions that carry out bitwise operations on CLINT
objects, and we shall also introduce functions for determining the equality and size of CLINT
objects, which we have already used quite a bit.
Among the bitwise functions are to be found the shift operations, which shift a CLINT
argument in its binary representation by individual bit positions, and certain other functions taking two CLINT
arguments that enable the direct manipulation of the binary representation of CLINT
objects. How such operations can be applied to arithmetic purposes is most clearly seen in the shift operations described below, but we have also seen, in Section 4.3, how the bitwise AND operation can be used in reduction modulo a power of two.
Necessity devises all manner of shifts.
The simplest way to multiply a number a with the representation a = (an−1an−2 . . . a0)B to the base B by a power Be is to "shift a to the left by e digits." This works with the binary representation exactly as it does in our familiar decimal system:
For B = 2 this corresponds to multiplication of a number in binary representation by 2e, while for B = 10 it corresponds to multiplication by a power of ten in the decimal system.
In the analogous procedure for whole-number division by powers of B the digits of a number are "shifted to the right":
where
For B = 2 this corresponds to integer division of a number in binary representation by 2e, and the analogous result holds for other bases.
Since the digits of CLINT
objects are represented in memory in binary form, CLINT
objects can easily be multiplied by powers of two by shifting left, where the next digit to the right is shifted into each place where a digit has been shifted left, and the binary digits left over on the right are filled with zeros.
In an analogous way CLINT
objects can be divided by powers of two by shifting each binary digit to the right into the next lower-valued digit. Digits left free at the end are either filled with zeros or ignored as leading zeros, and at each stage in the process (shifting by one digit) the lowest-valued digit is lost.
The advantage of this process is clear: Multiplication and division of a CLINT
object a by a power of two 2e are simple, and they require at most e [logB a] shift operations to shift each USHORT
value by one binary digit. Multiplication and division of a by a power Be uses only [logB a] operations for storing USHORT
values.
In the following we shall present three functions. The function shl_l()
executes a rapid multiplication of a CLINT
number by 2, while the function shr_l()
divides a CLINT
number by 2 and returns the integer quotient.
Lastly, the function shift_l()
multiplies or divides a CLINT
type a by a power of two 2e. Which operation is executed is determined by the sign of the exponent e of the power of two that is passed as argument. If the exponent is positive, then the operation is multiplication, while if it negative, then division is carried out. If e has the representation e = Bk + l, l < B, then shift_l()
carries out the multiplication or division in (l + 1) [logB a] operations on USHORT
values.
All three functions operate modulo (Nmax + 1) on objects of CLINT
type. They are implemented as accumulator functions, and thus they change their CLINT
operands in that they overwrite the operand with the result of the operation. The functions test for overflow, respectively underflow. However, in shifting, underflow cannot really arise, since in those cases where more positions are to be shifted than there are digits the result is simply zero, almost as it is in real life. The status value E_CLINT_UFL
for underflow then merely indicates that there was less to shift than was required, or, in other words, that the power of two by which division was to be carried out was larger than the dividend, and so the quotient is zero. The three functions are implemented in the following manner.
Function: | |
Syntax: | |
Input: |
|
Output: |
|
Return: |
|
int shl_l (CLINT a_l) { clint *ap_l, *msdptra_l; ULONG carry = 0L; int error = E_CLINT_OK; RMLDZRS_L (a_l); if (ld_l (a_l) >= (USHORT)CLINTMAXBIT) { SETDIGITS_L (a_l, CLINTMAXDIGIT); error = E_CLINT_OFL; } msdptra_l = MSDPTR_L (a_l); for (ap_l = LSDPTR_L (a_l); ap_l <= msdptra_l; ap_l++) { *ap_l = (USHORT)(carry = ((ULONG)*ap_l << 1) | (carry >> BITPERDGT)); } if (carry >> BITPERDGT) { if (DIGITS_L (a_l) < CLINTMAXDIGIT) { *ap_l = 1; SETDIGITS_L (a_l, DIGITS_L (a_l) + 1); error = E_CLINT_OK; }
else { error = E_CLINT_OFL; } } RMLDZRS_L (a_l); return error; }
shift right (integer division by 2) | |
Syntax: |
|
Input: |
|
Output: | |
Return: |
|
int shr_l (CLINT a_l) { clint *ap_l; USHORT help, carry = 0; if (EQZ_L (a_l)) return E_CLINT_UFL; for (ap_l = MSDPTR_L (a_l); ap_l > a_l; ap_l--) { help = (USHORT)((USHORT)(*ap_l >> 1) | (USHORT)(carry << (BITPERDGT - 1))); carry = (USHORT)(*ap_l & 1U); *ap_l = help; } RMLDZRS_L (a_l); return E_CLINT_OK; }
Function: | left/right shift (multiplication and division by powers of two) |
Syntax: | |
Input: |
|
Output: |
|
Return: |
|
int shift_l (CLINT n_l, long int noofbits) { USHORT shorts = (USHORT)((ULONG)(noofbits < 0 ? -noofbits : noofbits) / BITPERDGT); USHORT bits = (USHORT)((ULONG)(noofbits < 0 ? -noofbits : noofbits) % BITPERDGT); long int resl; USHORT i; int error = E_CLINT_OK; clint *nptr_l; clint *msdptrn_l; RMLDZRS_L (n_l); resl = (int) ld_l (n_l) + noofbits;
If n_l == 0
, we need only set the error code correctly, and we are done. The same holds if noofbits == 0
.
if (*n_l == 0) { return ((resl < 0) ? E_CLINT_UFL : E_CLINT_OK); } if (noofbits == 0) { return E_CLINT_OK; }
Next it is checked whether there is an overflow or underflow to announce. Then a branch is taken depending on the sign of noofbits
to shift either to the left or to the right.
if ((resl < 0) || (resl > (long) CLINTMAXBIT)) { error = ((resl < 0) ? E_CLINT_UFL : E_CLINT_OFL); /*underflow or overflow*/ } msdptrn_l = MSDPTR_L (n_l); if (noofbits < 0) {
If noofbits < 0
, then n_l
is divided by 2noofbits
. The number of digits of n_l
to shift is bounded by DIGITS_L
(n_l
). First the whole digits are shifted, and then the remaining bits with shr_l()
.
shorts = MIN (DIGITS_L (n_l), shorts); msdptrn_l = MSDPTR_L (n_l) - shorts; for (nptr_l = LSDPTR_L (n_l); nptr_l <= msdptrn_l; nptr_l++) { *nptr_l = *(nptr_l + shorts); } SETDIGITS_L (n_l, DIGITS_L (n_l) - (USHORT)shorts); for (i = 0; i < bits; i++) { shr_l (n_l); } } else {
If noofbits >
0, then n_l
is multiplied by 2noofbits
. If the number shorts
of digits to be shifted is greater than MAXB, then the result is zero. Otherwise, first the number of digits of the new value is determined and stored, and then the whole digits are shifted, and the freed-up digits filled with zeros. To avoid an overflow the start position is limited by n_l
+ MAXB and stored in nptr_l
. As before, the last bits are shifted individually, here with shl_l()
.
if (shorts < CLINTMAXDIGIT) { SETDIGITS_L (n_l, MIN (DIGITS_L (n_l) + shorts, CLINTMAXDIGIT)); nptr_l = n_l + DIGITS_L (n_l); msdptrn_l = n_l + shorts; while (nptr_l > msdptrn_l) { *nptr_l = *(nptr_l - shorts); --nptr_l; } while (nptr_l > n_l) { *nptr_l-- = 0; } RMLDZRS_L (n_l); for (i = 0; i < bits; i++) { shl_l (n_l); } } else { SETZERO_L (n_l); } } return error; }
The FLINT/C package contains functions that allow the built-in bitwise C operators &
, |
, and ˆ to be used for the type CLINT
as well. However, before we program these functions we would like to understand what their implementation will net us.
From a mathematical viewpoint we are looking at relations of the generalized Boolean functions f : { 0, 1 }k → { 0, 1 } that map a k-tuple (x1, . . . , xk) € { 0, 1 }k to the value 0 or 1. The effect of a Boolean function is usually presented in the form of a table of values such as that shown in Table 7-1.
For the bitwise relations between CLINT
types we first regard the variables as bit vectors (x1, . . . , xn), and furthermore, the function values of the Boolean functions will be formed into a sequence. Thus we have functions
that map n-bit variables
with
Decisive for the operation of the function fmacr is the definition of the partial functions fi, each of which is defined in terms of a Boolean function f. For the CLINT
functions and_l()
, or_l()
, and xor_l()
the Boolean functions that are implemented are defined as in Tables 7-2 through 7-4.
The implementations of these Boolean functions in the three C functions and_l()
, or_l()
, and xor_l()
do not actually proceed bitwise, but process the digits of CLINT
variables by means of the standard C operators &
, |
, and ˆ
. Each of these functions accepts three arguments of CLINT
type, where the first two are the operands and the last the result variable.
Function: | operating by bitwise AND |
Syntax: |
|
Input: |
|
Output: |
|
void and_l (CLINT a_l, CLINT b_l, CLINT c_l) { CLINT d_l; clint *r_l, *s_l, *t_l; clint *lastptr_l;
First pointers r_l
and s_l
are set to the respective digits of the arguments. If the arguments have different numbers of digits, then s_l
points to the shorter of the two. The pointer msdptra_l
points to the last digit of a_l
.
if (DIGITS_L (a_l) < DIGITS_L (b_l)) { r_l = LSDPTR_L (b_l); s_l = LSDPTR_L (a_l); lastptr_l = MSDPTR_L (a_l); } else { r_l = LSDPTR_L (a_l); s_l = LSDPTR_L (b_l); lastptr_l = MSDPTR_L (b_l); }
Now the pointer t_l
is set to point to the first digit of the result, and the maximal length of the result is stored in d_l[0]
.
t_l = LSDPTR_L (d_l); SETDIGITS_L (d_l, DIGITS_L (s_l - 1));
The actual operation runs in the following loop over the digits of the shorter argument. The result cannot have a larger number of digits.
while (s_l <= lastptr_l) { *t_l++ = *r_l++ & *s_l++; }
After the result is copied to c_l
, where any leading zeros are expunged, the function is ended.
cpy_l (c_l, d_l); }
Function: | operating by bitwise OR |
Syntax: |
|
Input: |
|
Output: |
|
void or_l (CLINT a_l, CLINT b_l, CLINT c_l) { CLINT d_l; clint *r_l, *s_l, *t_l; clint *msdptrr_l; clint *msdptrs_l;
The pointers r_l
and s_l
are set as above.
if (DIGITS_L (a_l) < DIGITS_L (b_l)) { r_l = LSDPTR_L (b_l); s_l = LSDPTR_L (a_l); msdptrr_l = MSDPTR_L (b_l); msdptrs_l = MSDPTR_L (a_l); } else { r_l = LSDPTR_L (a_l); s_l = LSDPTR_L (b_l); msdptrr_l = MSDPTR_L (a_l); msdptrs_l = MSDPTR_L (b_l); } t_l = LSDPTR_L (d_l); SETDIGITS_L (d_l, DIGITS_L (r_l - 1));
The actual operation takes place within a loop over the digits of the shorter of the two arguments.
while (s_l <= msdptrs_l) { *t_l++ = *r_l++ | *s_l++; }
The remaining digits of the longer argument are taken into the result. After the result is copied to c_l
, where any leading zeros are eliminated, the function is terminated.
while (r_l <= msdptrr_l) { *t_l++ = *r_l++; } cpy_l (c_l, d_l); }
operating by bitwise exclusive OR (XOR) | |
Syntax: |
|
Input: |
|
Output: |
|
void xor_l (CLINT a_l, CLINT b_l, CLINT c_l) { CLINT d_l; clint *r_l, *s_l, *t_l; clint *msdptrr_l; clint *msdptrs_l; if (DIGITS_L (a_l) < DIGITS_L (b_l)) { r_l = LSDPTR_L (b_l); s_l = LSDPTR_L (a_l); msdptrr_l = MSDPTR_L (b_l); msdptrs_l = MSDPTR_L (a_l); } else { r_l = LSDPTR_L (a_l); s_l = LSDPTR_L (b_l); msdptrr_l = MSDPTR_L (a_l); msdptrs_l = MSDPTR_L (b_l); } t_l = LSDPTR_L (d_l); SETDIGITS_L (d_l, DIGITS_L (r_l - 1));
Now the actual operation takes place. The loop runs over the digits of the shorter of the two arguments.
while (s_l <= msdptrs_l) { *t_l++ = *r_l++ ^ *s_l++; }
The remaining digits of the other argument are copied as above.
while (r_l <= msdptrr_l) { *t_l++ = *r_l++; } cpy_l (c_l, d_l); }
The function and_l()
can be used to reduce a number a modulo a power of two 2k by setting a CLINT
variable a_l
to the value a, a CLINT
variable b_l
to the value 2k − 1, and executing and_l(a_l, b_l, c_l)
. However, this operation executes faster with the function mod2_l()
created for this purpose, which takes into account that the binary representation of 2k − 1 consists exclusively of ones (see Section 4.3).
Occasionally, it is useful to be able to access individual binary digits of a number in order to read or change them. As an example of this we might mention the initialization of a CLINT
object as a power of 2, which can be accomplished easily by setting a single bit.
In the following we shall develop three functions, setbit_l()
, testbit_l()
, and clearbit_l()
, which set an individual bit, test a particular bit, and delete a single bit. The functions setbit_l()
and clearbit_l()
each return the state of the specified bit before the operation. The bit positions are counted from 0, and thus the specified positions can be understood as logarithms of powers of two: If n_l
is equal to 0, then setbit_l(n_l, 0)
returns the value 0, and afterwards, n_l
has the value 20= 1; after a call to setbit_l(n_l, 512)
, n_l
has the value 2512.
Function: | test and set a bit in a |
Syntax: | |
Input: |
|
Output: |
|
Return: | 1 if the bit at position 0 if the bit at position
|
int setbit_l (CLINT a_l, unsigned int pos) { int res = 0; unsigned int i; USHORT shorts = (USHORT)(pos >> LDBITPERDGT); USHORT bitpos = (USHORT)(pos & (BITPERDGT - 1)); USHORT m = 1U << bitpos; if (pos >= CLINTMAXBIT) { return E_CLINT_OFL; } if (shorts >= DIGITS_L (a_l)) {
If necessary, a_l
is zero filled word by word, and the new length is stored in a_l[0]
.
for (i = DIGITS_L (a_l) + 1; i <= shorts + 1; i++) { a_l[i] = 0; } SETDIGITS_L (a_l, shorts + 1); }
The digit of a_l
that contains the specified bit position is tested by means of the mask prepared in m
, and then the bit position is set to 1 via an OR of the relevant digit with m
. The function ends by returning the previous status.
if (a_l[shorts + 1] & m) { res = 1; } a_l[shorts + 1] |= m; return res; }
test a binary digit of a CLINT object | |
Syntax: |
|
Input: |
|
Output: |
|
Return: | 1 if bit at position 0 otherwise |
int testbit_l (CLINT a_l, unsigned int pos) { int res = 0; USHORT shorts = (USHORT)(pos >> LDBITPERDGT); USHORT bitpos = (USHORT)(pos & (BITPERDGT - 1)); if (shorts < DIGITS_L (a_l)) { if (a_l[shorts + 1] & (USHORT)(1U << bitpos)) res = 1; } return res; }
Function: | test and delete a bit in a |
Syntax: |
|
Input: |
|
Output: |
|
Return: | 1 if bit at position 0 otherwise |
int clearbit_l (CLINT a_l, unsigned int pos) { int res = 0; USHORT shorts = (USHORT)(pos >> LDBITPERDGT); USHORT bitpos = (USHORT)(pos & (BITPERDGT - 1)); USHORT m = 1U << bitpos; if (shorts < DIGITS_L (a_l)) {
If a_l
has enough digits, then the digit of a_l
that contains the specified bit position is tested by means of the mask prepared in m, and then the bit position is set to 0 by an AND of the corresponding digit with the complement of m
. The previous status of the bit position is returned at the termination of the function.
if (a_l[shorts + 1] & m) { res = 1; } a_l[shorts + 1] &= (USHORT)(~m); RMLDZRS_L (a_l); } return res; }
Every program requires the ability to make assertions about the equality or inequality or the size relationship of arithmetic variables, and this holds as well for our dealings with CLINT
objects. Here, too, the principle is obeyed that the programmer does not need knowledge of the internal structure of the CLINT
type, and the determination of how two CLINT
objects are related to each other is left to functions designed for such purposes.
The primary function that accomplishes these tasks is the function cmp_l()
. It determines which of the relations a_l < b_l
, a_l == b_l
, or a_l > b_l
holds for two CLINT
values a_l
and b_l
. To this end, first the numbers of digits of the CLINT
objects, which have been liberated from any leading zeros, are compared. If the number of digits of the operands is the same, then the process begins with a comparison of the most-significant digits; as soon as a difference is detected, the comparison is terminated.
Function: | comparison of two |
Syntax: | |
Input: |
|
Return: | −1 if (value of 0 if (value of 1 if (value of |
int cmp_l (CLINT a_l, CLINT b_l) { clint *msdptra_l, *msdptrb_l; int la = DIGITS_L (a_l); int lb = DIGITS_L (b_l);
The first test checks whether both arguments have length, and hence value, 0. Then any leading zeros are eliminated, and a decision is attempted on the basis of the number of digits.
if (la == 0 && lb == 0) { return 0; } while (a_l[la] == 0 && la > 0) { --la; } while (b_l[lb] == 0 && lb > 0) { --lb; } if (la == 0 && lb == 0) { return 0; } if (la > lb) { return 1; }
if (la < lb) { return −1; }
If the operands have the same number of digits, then the actual values must be compared. For this we begin with a comparison of the most-significant digits and proceed digit by digit until two digits are found that are unequal or until the least-significant digits are reached.
msdptra_l = a_l + la; msdptrb_l = b_l + lb; while ((*msdptra_l == *msdptrb_l) && (msdptra_l > a_l)) { msdptra_l--; msdptrb_l--; }
Now we compare the two digits and make our determination, and the corresponding function value is returned.
if (msdptra_l == a_l) { return 0; } if (*msdptra_l > *msdptrb_l) { return 1; } else { return −1; } }
If we are interested in the equality of two CLINT
values, then the application of the function cmp_l()
is a bit more than is necessary. In this case there is a simpler variant, which avoids the size comparison.
Function: | comparison of two |
Syntax: | |
Input: |
|
Return: | 0 if (value of 1 if (value of |
int equ_l (CLINT a_l, CLINT b_l) { clint *msdptra_l, *msdptrb_l; int la = DIGITS_L (a_l); int lb = DIGITS_L (b_l); if (la == 0 && lb == 0) { return 1; } while (a_l[la] == 0 && la > 0) { --la; } while (b_l[lb] == 0 && lb > 0) { --lb; } if (la == 0 && lb == 0) { return 1; } if (la != lb) { return 0; } msdptra_l = a_l + la; msdptrb_l = b_l + lb;
while ((*msdptra_l == *msdptrb_l) && (msdptra_l > a_l)) { msdptra_l--; msdptrb_l--; } return (msdptra_l > a_l ? 0 : 1); }
These two functions in their raw form can easily lead the user into the thickets of error. In particular, the meaning of the function values of cmp_l()
must be kept constantly in mind or looked up repeatedly. As a measure against errors a number of macros have been created by means of which comparisons can be formulated in a more mnemonically satisfactory way (see in this regard Appendix C, "Macros with Parameters"). For example, we have the following macros, where we equate the objects a_l
and b_l
with the values they represent:
GE_L (a_l, b_l) returns 1 if a_l ≥ b_l, and 0 otherwise; EQZ_L (a_l) returns 1 if a_l == 0, and 0 if a_l > 0.
18.119.253.31