Team-Fly
Previous Section Next Section

7.1 Shift Operations

Necessity devises all manner of shifts.

—Rabelais

The simplest way to multiply a number a with the representation a = (an−1 an−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:

Click To expand

where

Click To expand

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":

Click To expand

where

Click To expand

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.

Start Sidebar

Function:

shift left (multiplication by 2)

Syntax:

int shl_l (CLINT a_l);

Input:

a_l (multiplicand)

Output:

a_l (product)

Return:

E_CLINT_OK if all is ok

E_CLINT_OFL if overflow
End Sidebar 
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;
}
Start Sidebar

Function:

shift right (integer division by 2)

Syntax:

int shr_l (CLINT a_l);

Input:

a_l (dividend)

Output:

a_l (quotient)

Return:

E_CLINT_OK if all is ok

E_CLINT_UFL if "underflow"
End Sidebar 
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;
}
Start Sidebar

Function:

left/right shift

(multiplication and division by powers of two)

Syntax:

int shift_l (CLINT n_l, long int noofbits);

Input:

n_l (operand)

noofbits (exponent of the power of two)

Output:

n_l (product or quotient, depending on sign of noofbits)

Return:

E_CLINT_OK if all ok

E_CLINT_UFL if "underflow"

E_CLINT_OFL if overflow
End Sidebar 
int
shift_l (CLINT n_l, long int noofbits)
{
  USHORT shorts = (USHORT)((ULONG)(noofbits < 0 ? -notofbits : 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;
Start Sidebar

If n_l == 0, we need only set the error code correctly, and we are done. The same holds if noofbits == 0.

End Sidebar 
 if (*n_l == 0)
   {
     return ((resl < 0) ? E_CLINT_UFL : E_CLINT_OK);
   }

 if (noofbits == 0)
   {
     return E_CLINT_OK;
   }
Start Sidebar

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.

End Sidebar 
  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)
      {
Start Sidebar

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

End Sidebar 
       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
    {
Start Sidebar

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

End Sidebar 
        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;
}
Team-Fly Previous Section Next Section