src/modinteger/cl_MI.cc

   1 // Modular integer operations.
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 CL_PROVIDE(cl_MI)
   7
   8 // Specification.
   9 #include "cl_modinteger.h"
  10
  11
  12 // Implementation.
  13
  14 #include "cl_I.h"
  15 #include "cl_DS.h"
  16 #include "cl_2DS.h"
  17 #include "cl_io.h"
  18 #include "cl_integer_io.h"
  19 #include "cl_N.h"
  20 #include "cl_MI.h"
  21 #include "cl_abort.h"
  22 #include "cl_alloca.h"
  23
  24
  25 cl_heap_modint_ring::cl_heap_modint_ring (cl_I m, cl_modint_setops* setopv, cl_modint_addops* addopv, cl_modint_mulops* mulopv)
  26         : setops (setopv), addops (addopv), mulops (mulopv), modulus (m)
  27 {
  28         refcount = 0; // will be incremented by the `cl_modint_ring' constructor
  29         type = &cl_class_modint_ring;
  30         if (minusp(m)) cl_abort();
  31         if (!::zerop(m)) {
  32                 var uintL b = integer_length(m-1);
  33                 // m <= 2^b, hence one needs b bits for a representative mod m.
  34                 if (b <= 1) {
  35                         log2_bits = 0; bits = 1;
  36                 } else if (b <= cl_word_size) {
  37                         var uintL bb;
  38                         integerlength32(b-1,bb=); // b <= 2^bb with bb minimal
  39                         log2_bits = bb; bits = 1<<bb;
  40                 } else {
  41                         log2_bits = -1; bits = -1;
  42                 }
  43         } else {
  44                 log2_bits = -1; bits = -1;
  45         }
  46 }
  47
  48 static void cl_modint_ring_destructor (cl_heap* pointer)
  49 {
  50         (*(cl_heap_modint_ring*)pointer).~cl_heap_modint_ring();
  51 }
  52
  53 cl_class cl_class_modint_ring = {
  54         cl_modint_ring_destructor,
  55         0
  56 };
  57
  58 // This tells the compiler to put the `cl_heap_modint_ring' vtable
  59 // into this file.
  60 void cl_heap_modint_ring::dummy () {}
  61
  62
  63 static cl_boolean modint_equal (cl_heap_modint_ring* R, const _cl_MI& x, const _cl_MI& y)
  64 {
  65         unused R;
  66         return cl_equal(x.rep,y.rep);
  67 }
  68
  69 #include "cl_MI_int.h"
  70 #include "cl_MI_std.h"
  71 #include "cl_MI_fix16.h"
  72 #if (cl_value_len <= 32)
  73 #include "cl_MI_fix29.h"
  74 #include "cl_MI_int32.h"
  75 #else
  76 #include "cl_MI_fix32.h"
  77 #endif
  78 #include "cl_MI_pow2.h"
  79 #include "cl_MI_pow2m1.h"
  80 #include "cl_MI_pow2p1.h"
  81 #include "cl_MI_montgom.h"
  82
  83
  84 static inline cl_heap_modint_ring* make_modint_ring (const cl_I& m) // m >= 0
  85 {
  86         if (m == 0)
  87                 return new cl_heap_modint_ring_int();
  88         // Now m > 0.
  89         {
  90                 var uintL log2_m = power2p(m);
  91                 if (log2_m)
  92                         return new cl_heap_modint_ring_pow2(m,log2_m-1);
  93         }
  94         // Now m > 1.
  95         {
  96                 var uintL log2_m = integer_length(m); // = integerlength(m-1)
  97                 if (log2_m < 16) // m < 0x10000
  98                         return new cl_heap_modint_ring_fix16(m);
  99                 #if (cl_value_len <= 32)
 100                 if (log2_m < cl_value_len)
 101                         return new cl_heap_modint_ring_fix29(m);
 102                 if (log2_m < 32) // m < 0x100000000
 103                         return new cl_heap_modint_ring_int32(m);
 104                 #else
 105                 if (log2_m < 32) // m < 0x100000000
 106                         return new cl_heap_modint_ring_fix32(m);
 107                 #endif
 108         }
 109         {
 110                 var uintL m1 = power2p(m+1);
 111                 if (m1)
 112                         return new cl_heap_modint_ring_pow2m1(m,m1-1);
 113         }
 114         {
 115                 var uintL m1 = power2p(m-1);
 116                 if (m1)
 117                         return new cl_heap_modint_ring_pow2p1(m,m1-1);
 118         }
 119         {
 120                 var cl_heap_modint_ring* R = try_make_modint_ring_montgom(m);
 121                 if (R)
 122                         return R;
 123         }
 124         return new cl_heap_modint_ring_std(m);
 125 }
 126
 127
 128 // The table of modular integer rings.
 129 // A weak hash table cl_I -> cl_modint_ring.
 130 // (It could also be a weak hashuniq table cl_I -> cl_modint_ring.)
 131
 132 #include "cl_I_hashweak_rcpointer.h"
 133
 134 // An entry can be collected when the value (the ring) isn't referenced any more
 135 // except from the hash table, and when the key (the modulus) isn't referenced
 136 // any more except from the hash table and the ring. Note that the ring contains
 137 // exactly one reference to the modulus.
 138
 139 static cl_boolean maygc_htentry (const cl_htentry_from_integer_to_rcpointer& entry)
 140 {
 141         if (!entry.key.pointer_p() || (entry.key.heappointer->refcount == 2))
 142                 if (!entry.val.pointer_p() || (entry.val.heappointer->refcount == 1))
 143                         return cl_true;
 144         return cl_false;
 145 }
 146
 147 static const cl_wht_from_integer_to_rcpointer modint_ring_table = cl_wht_from_integer_to_rcpointer(maygc_htentry);
 148
 149 static inline cl_modint_ring* get_modint_ring (const cl_I& m)
 150 {
 151         return (cl_modint_ring*) modint_ring_table.get(m);
 152 }
 153
 154 static inline void store_modint_ring (const cl_modint_ring& R)
 155 {
 156         modint_ring_table.put(R->modulus,R);
 157 }
 158
 159
 160 const cl_modint_ring cl_find_modint_ring (const cl_I& m)
 161 {
 162  {      Mutable(cl_I,m);
 163         m = abs(m);
 164         var cl_modint_ring* ring_in_table = get_modint_ring(m);
 165         if (!ring_in_table) {
 166                 var cl_modint_ring R = make_modint_ring(m);
 167                 store_modint_ring(R);
 168                 ring_in_table = get_modint_ring(m);
 169                 if (!ring_in_table)
 170                         cl_abort();
 171         }
 172         return *ring_in_table;
 173 }}
 174
 175
 176 const cl_modint_ring cl_modint0_ring = cl_find_modint_ring(0);
 177
 178 CL_PROVIDE_END(cl_MI)