---

shift.c

解説を見る。

#include "multiprec.h"
#include <string.h>

size_t
ymp_rshiftabs(digit_t *result, const digit_t *source, size_t len, size_t width)
{
  register size_t i;
  size_t n_digits = width / DIGIT_BIT;
  size_t n_bits = width % DIGIT_BIT;
  digit_t prev;

  if (len <= n_digits) return 0;

  i=len; prev=0;
  while (i-- > n_digits)
    {
      double_digit_t tmp = LOW_DIGIT_TO_HIGH_DIGIT((double_digit_t)prev);
      prev = source[i];
      tmp += source[i];
      result[i-n_digits] = LOW_DIGIT(tmp >> n_bits);
    }


  /* 要素数の調整 */ 
  len -= n_digits;                /* 今、len > n_digits */
  if (result[len-1]==0) --len;

  return len;
}

size_t
ymp_lshiftabs(digit_t *result, const digit_t *source, size_t len, size_t width)
{
  register size_t i;
  size_t n_digits = width / DIGIT_BIT;
  size_t n_bits = width % DIGIT_BIT;
  double_digit_t tmp;

  if (len == 0) return 0;
  
  i = len; tmp = source[--i];
  tmp <<= n_bits;
  if (HIGH_DIGIT(tmp)) result[len++ + n_digits] = HIGH_DIGIT(tmp);

  tmp = source[i];
  while (i-- > 0)
    {
      tmp = LOW_DIGIT_TO_HIGH_DIGIT(tmp);
      tmp += source[i];
      result[i+n_digits+1] = HIGH_DIGIT(tmp << n_bits);
      tmp = source[i];
    }
  result[n_digits] = source[0] << n_bits;

  i = n_digits;
  while (i-- > 0) result[i] = 0;
  
  return len + n_digits;
}


size_t 
ymp_modabs_2exp(digit_t *result, const digit_t *self, size_t len, size_t pow)
{
  size_t n_digits = pow / DIGIT_BIT;
  size_t n_bits = pow % DIGIT_BIT;

  if (n_digits < len)
    {
      len = n_digits;
      if (n_bits)
        {
          result[n_digits] = self[n_digits] & ( (1u << n_bits) - 1u );
          ++n_digits;
        }
    }
  else if (n_digits > len)
    {
      n_digits = len;
    }

  if (result != self) memcpy(result, self, len*sizeof(digit_t));

  while (n_digits-- > 0)
    {
      if (self[n_digits] != 0) break;
    }
  return n_digits+1;
}

void ymp_mul_2exp(mp_ref_t result, mp_cref_t self, size_t pow)
{
  result->sign = self->sign;
  ymp_reserve(result, self->used+pow/DIGIT_BIT+1);
  result->used = ymp_lshiftabs(result->digits, self->digits, self->used, pow);
}


void ymp_div_2exp(mp_ref_t result, mp_cref_t self, size_t pow)
{
  size_t n_shift_digits = pow/DIGIT_BIT;

  if (self->used > n_shift_digits)
    {
      result->sign = self->sign;
      ymp_reserve(result, self->used - n_shift_digits);
      result->used
        = ymp_rshiftabs(result->digits, self->digits, self->used, pow);
    }
  else
    {
      result->used = 0;
    }
}


void ymp_mod_2exp(mp_ref_t result, mp_cref_t self, size_t pow)
{
  size_t n_digits = pow / DIGIT_BIT;
  ymp_reserve(result, n_digits>self->used ? self->used : n_digits);
  result->sign = self->sign;
  result->used = ymp_modabs_2exp(result->digits, self->digits, self->used, pow);
}

---