goo/st-large-integer.c

   1 /*
   2  * st-large-integer.c
   3  *
   4  * Copyright (C) 2008 Vincent Geddes
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a copy
   7  * of this software and associated documentation files (the "Software"), to deal
   8  * in the Software without restriction, including without limitation the rights
   9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10  * copies of the Software, and to permit persons to whom the Software is
  11  * furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in
  14  * all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22  * THE SOFTWARE.
  23 */
  24
  25 #include "st-large-integer.h"
  26 #include "st-universe.h"
  27 #include "st-types.h"
  28 #include "math.h"
  29
  30 #define VALUE(oop)             (&(ST_LARGE_INTEGER(oop)->value))
  31
  32
  33 /* useful macros to avoid duplication of error-handling code */
  34
  35 #define OP_PROLOGUE                      \
  36 {                                        \
  37     mp_int value;                        \
  38     int result;                          \
  39     *error = false;                      \
  40                                          \
  41     result = mp_init (&value);           \
  42     if (result != MP_OKAY)               \
  43         goto out;
  44
  45
  46 #define OP_EPILOGUE                         \
  47     if (result != MP_OKAY)                  \
  48         goto out;                           \
  49     return st_large_integer_new (&value);   \
  50                                             \
  51 out:                                        \
  52     mp_clear (&value);                      \
  53     *error = true;                          \
  54     return st_nil;                          \
  55  }
  56
  57 #define BINARY_OP(op, a, b)                     \
  58 OP_PROLOGUE                                     \
  59     result = op (VALUE (a), VALUE (b), &value); \
  60 OP_EPILOGUE
  61
  62 #define BINARY_DIV_OP(op, a, b)                       \
  63 OP_PROLOGUE                                           \
  64     result = op (VALUE (a), VALUE (b), &value, NULL); \
  65 OP_EPILOGUE
  66
  67 #define UNARY_OP(op, a)              \
  68 OP_PROLOGUE                          \
  69     result = op (VALUE (a), &value); \
  70 OP_EPILOGUE
  71
  72 st_oop
  73 st_large_integer_add (st_oop a, st_oop b, bool *error)
  74 {
  75     BINARY_OP (mp_add, a, b);
  76 }
  77
  78 st_oop
  79 st_large_integer_sub (st_oop a, st_oop b, bool *error)
  80 {
  81     BINARY_OP (mp_sub, a, b);
  82 }
  83
  84 st_oop
  85 st_large_integer_mul (st_oop a, st_oop b, bool *error)
  86 {
  87     BINARY_OP (mp_mul, a, b);
  88 }
  89
  90 st_oop
  91 st_large_integer_div (st_oop a, st_oop b, bool *error)
  92 {
  93     BINARY_DIV_OP (mp_div, a, b);
  94 }
  95
  96 st_oop
  97 st_large_integer_mod (st_oop a, st_oop b, bool *error)
  98 {
  99     BINARY_OP (mp_mod, a, b);
 100 }
 101
 102 st_oop
 103 st_large_integer_sqr (st_oop a, bool *error)
 104 {
 105     UNARY_OP (mp_sqr, a);
 106 }
 107
 108 st_oop
 109 st_large_integer_neg (st_oop a, bool *error)
 110 {
 111     UNARY_OP (mp_neg, a);
 112 }
 113
 114 st_oop
 115 st_large_integer_abs (st_oop a, bool *error)
 116 {
 117     UNARY_OP (mp_abs, a);
 118 }
 119
 120 st_oop
 121 st_large_integer_gcd (st_oop a, st_oop b, bool *error)
 122 {
 123     BINARY_OP (mp_gcd, a, b);
 124 }
 125
 126 st_oop
 127 st_large_integer_lcm (st_oop a, st_oop b, bool *error)
 128 {
 129     BINARY_OP (mp_lcm, a, b);
 130 }
 131
 132 st_oop
 133 st_large_integer_bitor (st_oop a, st_oop b, bool *error)
 134 {
 135     BINARY_OP (mp_or, a, b);
 136 }
 137
 138 st_oop
 139 st_large_integer_bitand (st_oop a, st_oop b, bool *error)
 140 {
 141     BINARY_OP (mp_and, a, b);
 142 }
 143
 144 st_oop
 145 st_large_integer_bitxor (st_oop a, st_oop b, bool *error)
 146 {
 147     BINARY_OP (mp_xor, a, b);
 148 }
 149
 150 st_oop
 151 st_large_integer_bitshift (st_oop a, int shift, bool *error)
 152 {
 153     mp_int value;
 154     int result;
 155     *error = false;
 156
 157     result = mp_init (&value);
 158     if (result != MP_OKAY)
 159         goto out;
 160
 161     if (shift >= 0)
 162         result = mp_mul_2d (VALUE (a), shift, &value);
 163     else
 164         result = mp_div_2d (VALUE (a), shift, &value, NULL);
 165
 166     if (result != MP_OKAY)
 167         goto out;
 168
 169     return st_large_integer_new (&value);
 170
 171   out:
 172     mp_clear (&value);
 173     *error = true;
 174     return st_nil;
 175 }
 176
 177
 178 bool
 179 st_large_integer_eq (st_oop a, st_oop b, bool * error)
 180 {
 181     *error = false;
 182     return mp_cmp (VALUE (a), VALUE (b)) == MP_EQ;
 183 }
 184
 185 bool
 186 st_large_integer_lt (st_oop a, st_oop b, bool * error)
 187 {
 188     *error = false;
 189     return mp_cmp (VALUE (a), VALUE (b)) == MP_LT;
 190 }
 191
 192 bool
 193 st_large_integer_gt (st_oop a, st_oop b, bool * error)
 194 {
 195     *error = false;
 196     return mp_cmp (VALUE (a), VALUE (b)) == MP_GT;
 197 }
 198
 199 bool
 200 st_large_integer_le (st_oop a, st_oop b, bool * error)
 201 {
 202     *error = false;
 203     int relation = mp_cmp (VALUE (a), VALUE (b));
 204     return (relation == MP_LT) || (relation == MP_EQ);
 205 }
 206
 207 bool
 208 st_large_integer_ge (st_oop a, st_oop b, bool * error)
 209 {
 210     *error = false;
 211     int relation = mp_cmp (VALUE (a), VALUE (b));
 212     return (relation == MP_GT) || (relation == MP_EQ);
 213 }
 214
 215 bool
 216 st_large_integer_is_positive (st_oop a, bool * error)
 217 {
 218     *error = false;
 219     return SIGN (VALUE (a)) != MP_NEG;
 220 }
 221
 222 bool
 223 st_large_integer_is_prime (st_oop a, bool * error)
 224 {
 225     int result;
 226     int isprime;
 227     *error = false;
 228
 229     int ntrials = mp_prime_rabin_miller_trials (mp_count_bits (VALUE (a)));
 230
 231     result = mp_prime_is_prime (VALUE (a), ntrials, &isprime);
 232     if (result != MP_OKAY) {
 233         *error = true;
 234         return false;
 235     }
 236
 237     return isprime == MP_YES;
 238 }
 239
 240 st_oop
 241 st_large_integer_new_from_string (const char *string, guint radix)
 242 {
 243     mp_int value;
 244     int result;
 245
 246     g_assert (string != NULL);
 247
 248     result = mp_init (&value);
 249     if (result != MP_OKAY)
 250         goto out;
 251
 252     result = mp_read_radix (&value, string, radix);
 253     if (result != MP_OKAY)
 254         goto out;
 255
 256     return st_large_integer_new (&value);
 257
 258   out:
 259     mp_clear (&value);
 260     g_warning (mp_error_to_string (result));
 261     return st_nil;
 262 }
 263
 264 st_oop
 265 st_large_integer_new_from_smi (st_smi integer)
 266 {
 267     mp_int value;
 268     int    result;
 269     bool   negative = integer < 0;
 270     st_smi integer_abs = abs(integer);
 271
 272     result = mp_init_set_int (&value, integer_abs);
 273     if (result != MP_OKAY)
 274         goto out;
 275
 276     if (negative)
 277         mp_neg (&value, &value);
 278
 279     return st_large_integer_new (&value);
 280
 281   out:
 282     mp_clear (&value);
 283     g_warning (mp_error_to_string (result));
 284     return st_nil;
 285 }
 286
 287 char *
 288 st_large_integer_to_string (st_oop integer, guint radix)
 289 {
 290     int result;
 291     int size;
 292
 293     result = mp_radix_size (VALUE (integer), radix, &size);
 294     if (result != MP_OKAY)
 295         goto out;
 296
 297     char *str = g_malloc (size);
 298
 299     mp_toradix (VALUE (integer), str, radix);
 300     if (result != MP_OKAY)
 301         goto out;
 302
 303     return str;
 304
 305   out:
 306     g_warning (mp_error_to_string (result));
 307     return NULL;
 308 }
 309
 310 static st_oop
 311 allocate_with_value (st_oop klass, mp_int * value)
 312 {
 313     st_oop object = st_allocate_object (sizeof (STLargeInteger) / sizeof (st_oop));
 314
 315     st_heap_object_initialize_header (object, klass);
 316
 317     if (value)
 318         *VALUE (object) = *value;
 319     else
 320         mp_init (VALUE (object));
 321
 322     return object;
 323 }
 324
 325 st_oop
 326 st_large_integer_new (mp_int * value)
 327 {
 328     return allocate_with_value (st_large_integer_class, value);
 329
 330 }
 331
 332 static st_oop
 333 allocate (st_oop klass)
 334 {
 335     return allocate_with_value (klass, NULL);
 336 }
 337
 338
 339 static st_oop
 340 large_integer_copy (st_oop object)
 341 {
 342     mp_int value;
 343     int result;
 344
 345     result = mp_init_copy (&value, VALUE (object));
 346     if (result != MP_OKAY)
 347         g_assert_not_reached ();
 348
 349     return st_large_integer_new (&value);
 350 }
 351
 352 const STDescriptor *
 353 st_large_integer_descriptor (void)
 354 {
 355     static const STDescriptor __descriptor =
 356         { .allocate         = allocate,
 357           .allocate_arrayed = NULL,
 358           .copy             = large_integer_copy,
 359         };
 360
 361     return & __descriptor;
 362 }