src/snark/src/algebra/fields/bigint.tcc

   1 /** @file
   2  *****************************************************************************
   3  Implementation of bigint wrapper class around GMP's MPZ long integers.
   4  *****************************************************************************
   5  * @author     This file is part of libsnark, developed by SCIPR Lab
   6  *             and contributors (see AUTHORS).
   7  * @copyright  MIT license (see LICENSE file)
   8  *****************************************************************************/
   9
  10 #ifndef BIGINT_TCC_
  11 #define BIGINT_TCC_
  12 #include <cassert>
  13 #include <climits>
  14 #include <cstring>
  15 #include "sodium.h"
  16
  17 namespace libsnark {
  18
  19 template<mp_size_t n>
  20 bigint<n>::bigint(const unsigned long x) /// Initalize from a small integer
  21 {
  22     static_assert(ULONG_MAX <= GMP_NUMB_MAX, "unsigned long does not fit in a GMP limb");
  23     this->data[0] = x;
  24 }
  25
  26 template<mp_size_t n>
  27 bigint<n>::bigint(const char* s) /// Initialize from a string containing an integer in decimal notation
  28 {
  29     size_t l = strlen(s);
  30     unsigned char* s_copy = new unsigned char[l];
  31
  32     for (size_t i = 0; i < l; ++i)
  33     {
  34         assert(s[i] >= '0' && s[i] <= '9');
  35         s_copy[i] = s[i] - '0';
  36     }
  37
  38     mp_size_t limbs_written = mpn_set_str(this->data, s_copy, l, 10);
  39     assert(limbs_written <= n);
  40
  41     delete[] s_copy;
  42 }
  43
  44 template<mp_size_t n>
  45 bigint<n>::bigint(const mpz_t r) /// Initialize from MPZ element
  46 {
  47     mpz_t k;
  48     mpz_init_set(k, r);
  49
  50     for (size_t i = 0; i < n; ++i)
  51     {
  52         data[i] = mpz_get_ui(k);
  53         mpz_fdiv_q_2exp(k, k, GMP_NUMB_BITS);
  54     }
  55
  56     assert(mpz_sgn(k) == 0);
  57     mpz_clear(k);
  58 }
  59
  60 template<mp_size_t n>
  61 void bigint<n>::print() const
  62 {
  63     gmp_printf("%Nd\n", this->data, n);
  64 }
  65
  66 template<mp_size_t n>
  67 void bigint<n>::print_hex() const
  68 {
  69     gmp_printf("%Nx\n", this->data, n);
  70 }
  71
  72 template<mp_size_t n>
  73 bool bigint<n>::operator==(const bigint<n>& other) const
  74 {
  75     return (mpn_cmp(this->data, other.data, n) == 0);
  76 }
  77
  78 template<mp_size_t n>
  79 bool bigint<n>::operator!=(const bigint<n>& other) const
  80 {
  81     return !(operator==(other));
  82 }
  83
  84 template<mp_size_t n>
  85 void bigint<n>::clear()
  86 {
  87     mpn_zero(this->data, n);
  88 }
  89
  90 template<mp_size_t n>
  91 bool bigint<n>::is_zero() const
  92 {
  93     for (mp_size_t i = 0; i < n; ++i)
  94     {
  95         if (this->data[i])
  96         {
  97             return false;
  98         }
  99     }
 100
 101     return true;
 102 }
 103
 104 template<mp_size_t n>
 105 size_t bigint<n>::num_bits() const
 106 {
 107 /*
 108     for (long i = max_bits(); i >= 0; --i)
 109     {
 110         if (this->test_bit(i))
 111         {
 112             return i+1;
 113         }
 114     }
 115
 116     return 0;
 117 */
 118     for (long i = n-1; i >= 0; --i)
 119     {
 120         mp_limb_t x = this->data[i];
 121         if (x == 0)
 122         {
 123             continue;
 124         }
 125         else
 126         {
 127             return ((i+1) * GMP_NUMB_BITS) - __builtin_clzl(x);
 128         }
 129     }
 130     return 0;
 131 }
 132
 133 template<mp_size_t n>
 134 unsigned long bigint<n>::as_ulong() const
 135 {
 136     return this->data[0];
 137 }
 138
 139 template<mp_size_t n>
 140 void bigint<n>::to_mpz(mpz_t r) const
 141 {
 142     mpz_set_ui(r, 0);
 143
 144     for (int i = n-1; i >= 0; --i)
 145     {
 146         mpz_mul_2exp(r, r, GMP_NUMB_BITS);
 147         mpz_add_ui(r, r, this->data[i]);
 148     }
 149 }
 150
 151 template<mp_size_t n>
 152 bool bigint<n>::test_bit(const std::size_t bitno) const
 153 {
 154     if (bitno >= n * GMP_NUMB_BITS)
 155     {
 156         return false;
 157     }
 158     else
 159     {
 160         const std::size_t part = bitno/GMP_NUMB_BITS;
 161         const std::size_t bit = bitno - (GMP_NUMB_BITS*part);
 162         const mp_limb_t one = 1;
 163         return (this->data[part] & (one<<bit));
 164     }
 165 }
 166
 167
 168 template<mp_size_t n> template<mp_size_t m>
 169 inline void bigint<n>::operator+=(const bigint<m>& other)
 170 {
 171     static_assert(n >= m, "first arg must not be smaller than second arg for bigint in-place add");
 172     mpn_add(data, data, n, other.data, m);
 173 }
 174
 175 template<mp_size_t n> template<mp_size_t m>
 176 inline bigint<n+m> bigint<n>::operator*(const bigint<m>& other) const
 177 {
 178     static_assert(n >= m, "first arg must not be smaller than second arg for bigint mul");
 179     bigint<n+m> res;
 180     mpn_mul(res.data, data, n, other.data, m);
 181     return res;
 182 }
 183
 184 template<mp_size_t n> template<mp_size_t d>
 185 inline void bigint<n>::div_qr(bigint<n-d+1>& quotient, bigint<d>& remainder,
 186                               const bigint<n>& dividend, const bigint<d>& divisor)
 187 {
 188     static_assert(n >= d, "dividend must not be smaller than divisor for bigint::div_qr");
 189     assert(divisor.data[d-1] != 0);
 190     mpn_tdiv_qr(quotient.data, remainder.data, 0, dividend.data, n, divisor.data, d);
 191 }
 192
 193 // Return a copy shortened to m limbs provided it is less than limit, throwing std::domain_error if not in range.
 194 template<mp_size_t n> template<mp_size_t m>
 195 inline bigint<m> bigint<n>::shorten(const bigint<m>& q, const char *msg) const
 196 {
 197     static_assert(m <= n, "number of limbs must not increase for bigint::shorten");
 198     for (mp_size_t i = m; i < n; i++) { // high-order limbs
 199         if (data[i] != 0) {
 200             throw std::domain_error(msg);
 201         }
 202     }
 203     bigint<m> res;
 204     mpn_copyi(res.data, data, m);
 205     res.limit(q, msg);
 206     return res;
 207 }
 208
 209 template<mp_size_t n>
 210 inline void bigint<n>::limit(const bigint<n>& q, const char *msg) const
 211 {
 212     if (!(q > *this)) {
 213         throw std::domain_error(msg);
 214     }
 215 }
 216
 217 template<mp_size_t n>
 218 inline bool bigint<n>::operator>(const bigint<n>& other) const
 219 {
 220     return mpn_cmp(this->data, other.data, n) > 0;
 221 }
 222
 223 template<mp_size_t n>
 224 bigint<n>& bigint<n>::randomize()
 225 {
 226     assert(GMP_NUMB_BITS == sizeof(mp_limb_t) * 8);
 227
 228     randombytes_buf(this->data, sizeof(mp_limb_t) * n);
 229
 230     return (*this);
 231 }
 232
 233
 234 template<mp_size_t n>
 235 std::ostream& operator<<(std::ostream &out, const bigint<n> &b)
 236 {
 237 #ifdef BINARY_OUTPUT
 238     out.write((char*)b.data, sizeof(b.data[0]) * n);
 239 #else
 240     mpz_t t;
 241     mpz_init(t);
 242     b.to_mpz(t);
 243
 244     out << t;
 245
 246     mpz_clear(t);
 247 #endif
 248     return out;
 249 }
 250
 251 template<mp_size_t n>
 252 std::istream& operator>>(std::istream &in, bigint<n> &b)
 253 {
 254 #ifdef BINARY_OUTPUT
 255     in.read((char*)b.data, sizeof(b.data[0]) * n);
 256 #else
 257     std::string s;
 258     in >> s;
 259
 260     size_t l = s.size();
 261     unsigned char* s_copy = new unsigned char[l];
 262
 263     for (size_t i = 0; i < l; ++i)
 264     {
 265         assert(s[i] >= '0' && s[i] <= '9');
 266         s_copy[i] = s[i] - '0';
 267     }
 268
 269     mp_size_t limbs_written = mpn_set_str(b.data, s_copy, l, 10);
 270     assert(limbs_written <= n);
 271
 272     delete[] s_copy;
 273 #endif
 274     return in;
 275 }
 276
 277 } // libsnark
 278 #endif // BIGINT_TCC_