src/modinteger/cl_MI.cc

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