7.2 All or Nothing: Bitwise Relations

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.

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.

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).