---

multiprec.h

解説を見る。

#ifndef MULTIPREC_H
#define MULTIPREC_H

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <stdarg.h>

#ifndef C99
# if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
#  ifndef __CYGWIN__
#   define C99
#  endif
# endif
#endif

#ifdef C99
# include <stdint.h>
#endif

typedef unsigned digit_t;
#define DIGIT_BIT (sizeof(digit_t)*CHAR_BIT)

#define DIGIT_MAX UINT_MAX
#define DIGIT_HIGHEST_BIT ((digit_t)(1<<(DIGIT_BIT-1)))

typedef unsigned long long double_digit_t;
#define DOUBLE_DIGIT_BIT (sizeof(double_digit_t)*CHAR_BIT)

#define DOUBLE_DIGIT_MAX ULONGLONG_MAX

#define HIGH_DIGIT(dd) ((digit_t)((dd) >> DIGIT_BIT))

#define LOW_DIGIT(dd)  ((digit_t)(dd))

#define LOW_DIGIT_TO_HIGH_DIGIT(dd) ((dd) << DIGIT_BIT)

#define MULTIPREC_RADIX (((double_digit_t)DIGIT_MAX)+1)


enum mp_sign_t { positive_sign=0, negative_sign=1 };

struct multiprec
{
  enum mp_sign_t sign;

  size_t len;

  size_t used;

  digit_t *digits;
};

typedef struct multiprec *mp_ref_t;

typedef const struct multiprec *mp_cref_t;

#define MULTIPREC_INITIALIZER {positive_sign, 0, 0, NULL}


#ifndef MAX
# define MAX(a,b) ( ((a)>(b))?(a):(b) )
#endif


#define UINT_IS_2POW(u) ( ((u) & ((u)-1)) == 0 )

size_t digit_len_to_str_len(size_t len, digit_t r);

extern void *(*ymp_malloc)(size_t size);
extern void *(*ymp_realloc)(void *pv_mem, size_t size);
extern void (*ymp_free)(void *pv_mem);

#define YMP_ALLOCATE(result, type, count)                               \
do {                                                                    \
  register type *ptr_tmp = (type*)ymp_malloc(sizeof(type)*(count));     \
  if (!ptr_tmp)                                                         \
    {                                                                   \
      ymp_alloc_error("確保失敗", sizeof(type)*(count));                \
      break;                                                            \
    }                                                                   \
  (result) = ptr_tmp;                                                   \
} while(0)


#define YMP_REALLOCATE(ptr, type, count)                                    \
do {                                                                        \
  register type *ptr_tmp = (type*)ymp_realloc((ptr), sizeof(type)*(count)); \
  if (!ptr_tmp)                                                             \
   {                                                                        \
     ymp_alloc_error("再確保失敗", sizeof(type)*(count));                   \
     break;                                                                 \
   }                                                                        \
  (ptr) = ptr_tmp;                                                          \
} while(0)


#define YMP_FREE(ptr) \
ymp_free(ptr)



#define YMP_TEMP_ALLOCATE(result, type, count)                  \
do {                                                            \
  register type *ptr_tmp = (type*)alloca(sizeof(type)*(count)); \
  if (!ptr_tmp)                                                 \
    {                                                           \
      ymp_alloc_error("確保失敗", sizeof(type)*(count));        \
      break;                                                    \
    }                                                           \
  (result) = ptr_tmp;                                           \
} while(0)



#define YMP_ALLOC_DIGITS(self, new_len)                 \
do {                                                    \
  YMP_ALLOCATE((self)->digits, digit_t, new_len);       \
  (self)->len = new_len;                                \
} while(0)

#define YMP_REALLOC_DIGITS(self, new_len)               \
do {                                                    \
  YMP_REALLOCATE((self)->digits, digit_t, new_len);     \
  (self)->len = new_len;                                \
} while(0)

#define YMP_FREE_DIGITS(self)                   \
do {                                            \
  YMP_FREE((self)->digits);                     \
  (self)->digits = NULL;                        \
} while(0)


extern void (*ymp_warning)(const char *format, ...);
extern void (*ymp_error)(const char *format, ...);
extern void (*ymp_fatal)(const char *format, ...);
extern void (*ymp_alloc_error)(const char *psz_msg, size_t size);
void ymp_initialize(mp_ref_t self); 
void ymp_destroy(mp_ref_t self);
void ymp_reinitialize(mp_ref_t self);

void ymp_initialize_by_mp(mp_ref_t self, mp_cref_t other);
void ymp_reserve_and_initialize_by_digit(mp_ref_t self, size_t len, digit_t d);
void ymp_reserve_and_initialize(mp_ref_t self, size_t len);

#define ymp_alloca_initialize(self, new_len)                    \
do {                                                            \
  (self)->sign = positive_sign;                                 \
  (self)->len = (self)->used = 0;                               \
  YMP_TEMP_ALLOCATE((self)->digits, digit_t, (new_len));        \
  (self)->len = (new_len);                                      \
} while (0)


void ymp_initialize_by_array(mp_ref_t self, size_t len, const digit_t *array);
void ymp_initialize_by_digit(mp_ref_t self, digit_t d);
void ymp_initialize_by_string(mp_ref_t self, 
                              const char *text, char **endptr, unsigned radix);

void ymp_initialize_by_char(mp_ref_t self, signed char val);
void ymp_initialize_by_short(mp_ref_t self, short val);
void ymp_initialize_by_int(mp_ref_t self, int val);
void ymp_initialize_by_long(mp_ref_t self, long val);
void ymp_initialize_by_uchar(mp_ref_t self, unsigned char val);
void ymp_initialize_by_ushort(mp_ref_t self, unsigned short val);
void ymp_initialize_by_uint(mp_ref_t self, unsigned val);
void ymp_initialize_by_ulong(mp_ref_t self, unsigned long val);
#ifdef C99
void ymp_initialize_by_intmax(mp_ref_t self, intmax_t val);
void ymp_initialize_by_uintmax(mp_ref_t self, uintmax_t val);
#endif
void ymp_initialize_by_double(mp_ref_t self, double val);

mp_ref_t ymp_dup(mp_cref_t orig);

void ymp_reserve(mp_ref_t self, size_t len);
void ymp_cut_down(mp_ref_t self);

void ymp_assign_abs(mp_ref_t self, mp_cref_t other);
void ymp_assign_abs_digit(mp_ref_t self, digit_t other);
void ymp_assign_abs_array(mp_ref_t self, size_t len, const digit_t *array);
void ymp_assign(mp_ref_t self, mp_cref_t other);
void ymp_assign_digit(mp_ref_t self, digit_t other);
void ymp_assign_array(mp_ref_t self, size_t len, const digit_t *array);
void ymp_assign_string(mp_ref_t self, 
                       const char *text, char **endptr, unsigned radix);

void ymp_assign_char(mp_ref_t self, signed char val);
void ymp_assign_short(mp_ref_t self, short val);
void ymp_assign_int(mp_ref_t self, int val);
void ymp_assign_long(mp_ref_t self, long val);
void ymp_assign_uchar(mp_ref_t self, unsigned char val);
void ymp_assign_ushort(mp_ref_t self, unsigned short val);
void ymp_assign_uint(mp_ref_t self, unsigned val);
void ymp_assign_ulong(mp_ref_t self, unsigned long val);
#ifdef C99
void ymp_assign_intmax(mp_ref_t self, intmax_t val);
void ymp_assign_uintmax(mp_ref_t self, uintmax_t val);
#endif
void ymp_assign_double(mp_ref_t self, double val);
void ymp_assign_2exp(mp_ref_t self, size_t pow);


#define ymp_assign_zero(self)                   \
(void)((self)->used = 0)


void ymp_swap(mp_ref_t self, mp_ref_t other);
size_t
ymp_rshiftabs(digit_t *result, const digit_t *source, size_t len, size_t width);
size_t
ymp_lshiftabs(digit_t *result, const digit_t *source, size_t len, size_t width);
size_t ymp_addabs(digit_t *result, const digit_t *lhs, const digit_t *rhs,
                  size_t lhs_len, size_t rhs_len);
size_t ymp_subabs(digit_t *result, const digit_t *lhs, const digit_t *rhs,
                  size_t lhs_len, size_t rhs_len);
size_t ymp_mulabs(digit_t *result, const digit_t *lhs, const digit_t *rhs,
                  size_t lhs_len, size_t rhs_len);
size_t ymp_mulabs_digit(digit_t *result, const digit_t *lhs, digit_t rhs,
                        size_t lhs_len);
size_t ymp_modmulabs(digit_t *result, const digit_t *lhs, const digit_t *rhs, 
                     const digit_t *modulus,
                     size_t lhs_len, size_t rhs_len, size_t modulus_len);
size_t ymp_modmulabs_2exp(digit_t *result,
                          const digit_t *lhs, const digit_t *rhs, 
                          size_t pow, size_t lhs_len, size_t rhs_len);

size_t ymp_modabs_2exp(digit_t *result, const digit_t *self, 
                       size_t len, size_t pow);

size_t ymp_divmodabs(digit_t *quotient, digit_t *remainder,
                     const digit_t *lhs, const digit_t *rhs,
                     size_t lhs_len, size_t rhs_len);
digit_t ymp_divmodabs_digit(digit_t *quotient, const digit_t *lhs, digit_t rhs,
                            size_t lhs_len);




size_t ymp_modpowabs(digit_t *result, 
                     const digit_t *source, const digit_t *modulus, 
                     const digit_t *pow,
                     size_t source_len, size_t modulus_len, size_t pow_len);

size_t ymp_modpowabs_z(digit_t *result, 
                       const digit_t *source, const digit_t *modulus,
                       size_t source_len, size_t modulus_len, size_t pow);

size_t ymp_modpowabs_2exp_z(digit_t *result, const digit_t *source,
                            size_t len, size_t emod, size_t pow);

size_t ymp_powabs(digit_t *result, const digit_t *source, 
                  size_t source_len, size_t pow);
void ymp_neg(mp_ref_t result, mp_cref_t orig);
void ymp_add(mp_ref_t result, mp_cref_t self, mp_cref_t other);
void ymp_sub(mp_ref_t result, mp_cref_t self, mp_cref_t other);
void ymp_add_digit(mp_ref_t result, mp_cref_t self, digit_t other);
void ymp_sub_digit(mp_ref_t result, mp_cref_t self, digit_t other);

void ymp_mul(mp_ref_t result, mp_cref_t self, mp_cref_t other);
void ymp_mul_digit(mp_ref_t result, mp_cref_t self, digit_t other);
void ymp_modmul(mp_ref_t result, 
                mp_cref_t self, mp_cref_t other, mp_cref_t modulus);
void ymp_modmul_2exp(mp_ref_t result,
                     mp_cref_t self, mp_cref_t other, size_t pow);

void ymp_mul_2exp(mp_ref_t result, mp_cref_t self, size_t pow);
void ymp_div_2exp(mp_ref_t result, mp_cref_t self, size_t pow);
void ymp_mod_2exp(mp_ref_t result, mp_cref_t self, size_t pow);


void ymp_divmod(mp_ref_t quotient, mp_ref_t remainder, mp_cref_t self, mp_cref_t other);
digit_t ymp_divmod_digit(mp_ref_t quotient, mp_cref_t self, digit_t other);

#define ymp_div(quotient, self, other)          \
ymp_divmod((quotient), NULL, (self), (other))

#define ymp_mod(remainder, self, other)         \
ymp_divmod(NULL, (remainder), (self), (other))

#define ymp_div_digit(quotient, self, other)    \
(void)ymp_divmod_digit((quotient), (self), (other))

#define ymp_mod_digit(self, other)              \
ymp_divmod_digit(NULL, (self), (other))



int ymp_div_if_divisible(mp_ref_t quotient, mp_cref_t self, mp_cref_t other);
int ymp_div_if_divisible_digit(mp_ref_t quotient, 
                               mp_cref_t self, digit_t other);

#define ymp_is_divisible(self, other)           \
ymp_div_if_divisible(NULL, (self), (other))

#define ymp_is_divisible_digit(self, other)             \
ymp_div_if_divisible_digit(NULL, (self), (other))

void ymp_pow(mp_ref_t result, mp_cref_t self, size_t pow);
void ymp_modpow(mp_ref_t result, mp_cref_t self, 
                mp_cref_t modulus, mp_cref_t pow);
void ymp_modpow_z(mp_ref_t result, mp_cref_t self, mp_cref_t modulus, size_t pow);

void ymp_modpow_2exp_z(mp_ref_t result, mp_cref_t self, size_t emod, size_t pow);
void ymp_iroot(mp_ref_t result, mp_cref_t self, size_t pow);

void ymp_euclid(mp_ref_t g, mp_cref_t a, mp_cref_t b);
void ymp_euclid_ex(mp_ref_t g, mp_ref_t s, mp_ref_t t,
                   mp_cref_t a, mp_cref_t b);
void ymp_multi_euclid(mp_ref_t result, 
                      size_t len, const struct multiprec *ary);
int ymp_modinv(mp_ref_t result, mp_cref_t self, mp_cref_t modulus);
int ymp_binary_sunzi(mp_ref_t result, 
                     const mp_cref_t remainders[2], const mp_cref_t moduli[2]);

int ymp_proot(mp_ref_t result, mp_cref_t self, size_t pow);
int ymp_is_perfect_power(mp_cref_t self);

void ymp_dump(FILE *fp, mp_cref_t mz);
int ymp_print_hex(FILE *fp, mp_cref_t mz);

int ymp_snprint(char *buf, size_t len, mp_cref_t mz, digit_t radix);
int ymp_fprint(FILE *fp, mp_cref_t mz, digit_t radix);

int ymp_compare_abs(mp_cref_t lhs, mp_cref_t rhs);
int ymp_compare(mp_cref_t lhs, mp_cref_t rhs);
int ymp_compare_digit(mp_cref_t lhs, digit_t rhs);
int ymp_is_zero(mp_cref_t self);
int ymp_is_even(mp_cref_t self);

#define ymp_is_odd(self) !ymp_is_even((self))

size_t ymp_ilog2(mp_cref_t self);
size_t ymp_abs_clog2(const digit_t *digits, size_t len);

#endif

---