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