7.2 All or Nothing: Bitwise Relations

Team-Fly

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 (x₁,..., x_k) Î { 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.

Table 7.1: Values of a Boolean function
x₁	x₂	...	x_k	f (x₁, ..., x_k)
0	0	...	0	0
1	0	...	0	1
0	1	...	0	0
⋮	⋮	⋮	⋮	⋮
1	1	...	1	1

For the bitwise relations between CLINT types we first regard the variables as bit vectors (x₁, ..., x_n), and furthermore, the function values of the Boolean functions will be formed into a sequence. Thus we have functions

that map n-bit variables := () and := () by

with f_i () := f (), again to an n-bit variable (x₁, ..., x_n), which is then interpreted as a number of type CLINT.

Decisive for the operation of the function is the definition of the partial functions f_i, 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–7.4.

Table 7.2: Values of the CLINT function and_l()
x₁	x₂	f (x₁, x₂)
0	0	0
0	1	0
1	0	0
1	1	1

Table 7.3: Values of the CLINT function or_l()
x₁	x₂	f (x₁, x₂)
0	0	0
0	1	1
1	0	1
1	1	1

Table 7.4: Values of the CLINT function xor_l()
x₁	x₂	f (x₁, x₂)
0	0	0
0	1	1
1	0	1
1	1	0

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:	void and_l (CLINT a_l, CLINT b_l, CLINT c_l);
Input:	a_l, b_l (arguments to be operated on)
Output:	c_l (value of the AND operation)

 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:	void or_l (CLINT a_l, CLINT b_l, CLINT c_l);
Input:	a_l, b_l (arguments to be operated on)
Output:	c_l (value of the OR operation)

 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); }

Function:	operation by bitwise exclusive OR (XOR)
Syntax:	void xor_l (CLINT a_l, CLINT b_l, CLINT c_l);
Input:	a_l, b_l (arguments to be operated on)
Output:	c_l (value of the XOR operation)

 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 2^k by setting a CLINT variable a_l to the value a, a CLINT variable b_l to the value 2^k − 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 2^k − 1 consists exclusively of ones (see Section 4.3).

Team-Fly