7.1 Shift Operations

Team-Fly

Necessity devises all manner of shifts.

—Rabelais

The simplest way to multiply a number a with the representation a = (a_n−1 a_n−2 ... a₀)_B to the base B by a power B^e 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:

where

For B = 2 this corresponds to multiplication of a number in binary representation by 2^e, 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 2^e, 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 2^e are simple, and they require at most e ⌈log_B a⌉ shift operations to shift each USHORT value by one binary digit. Multiplication and division of a by a power B^e uses only ⌈log_B 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 2^e. 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) ⌈log_B a⌉ operations on USHORT values.

All three functions operate modulo (N_max + 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:	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

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

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"

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

 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;

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 2^noofbits. 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 2^noofbits. If the number shorts of digits to be shifted is greater than MAX_B, 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 + MAX_B 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; }

Team-Fly