1 // Modular integer operations.
4 #include "base/cl_sysdep.h"
7 #include "cln/modinteger.h"
11 #include "integer/cl_I.h"
12 #include "base/digitseq/cl_DS.h"
13 #include "base/digitseq/cl_2DS.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"
21 // MacOS X does "#define _R 0x00040000L"
27 static void cl_modint_ring_destructor (cl_heap* pointer)
29 (*(cl_heap_modint_ring*)pointer).~cl_heap_modint_ring();
32 cl_class cl_class_modint_ring;
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)
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();
41 var uintC b = integer_length(m-1);
42 // m <= 2^b, hence one needs b bits for a representative mod m.
44 log2_bits = 0; bits = 1;
45 } else if (b <= cl_word_size) {
47 integerlengthC(b-1,bb=); // b <= 2^bb with bb minimal
48 log2_bits = bb; bits = 1<<bb;
50 log2_bits = -1; bits = -1;
53 log2_bits = -1; bits = -1;
58 static bool modint_equal (cl_heap_modint_ring* R, const _cl_MI& x, const _cl_MI& y)
61 return equal(x.rep,y.rep);
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"
72 #include "modinteger/cl_MI_fix32.h"
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"
81 static inline cl_heap_modint_ring* make_modint_ring (const cl_I& m) // m >= 0
84 return new cl_heap_modint_ring_int();
87 var uintC log2_m = power2p(m);
89 return new cl_heap_modint_ring_pow2(m,log2_m-1);
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);
102 if (log2_m < 32) // m < 0x100000000
103 return new cl_heap_modint_ring_fix32(m);
107 var uintC m1 = power2p(m+1);
109 return new cl_heap_modint_ring_pow2m1(m,m1-1);
112 var uintC m1 = power2p(m-1);
114 return new cl_heap_modint_ring_pow2p1(m,m1-1);
117 var cl_heap_modint_ring* R = try_make_modint_ring_montgom(m);
121 return new cl_heap_modint_ring_std(m);
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.)
130 #include "integer/hash/cl_I_hashweak_rcpointer.h"
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.
138 static bool maygc_htentry (const cl_htentry_from_integer_to_rcpointer& entry)
140 if (!entry.key.pointer_p() || (entry.key.heappointer->refcount == 2))
141 if (!entry.val.pointer_p() || (entry.val.heappointer->refcount == 1))
146 class modint_ring_cache
148 static cl_wht_from_integer_to_rcpointer* modint_ring_table;
151 inline cl_modint_ring* get_modint_ring(const cl_I& m)
153 return (cl_modint_ring*) modint_ring_table->get(m);
155 inline void store_modint_ring(const cl_modint_ring& R)
157 modint_ring_table->put(R->modulus,R);
160 ~modint_ring_cache();
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()
168 modint_ring_table = new cl_wht_from_integer_to_rcpointer(maygc_htentry);
171 modint_ring_cache::~modint_ring_cache()
174 delete modint_ring_table;
177 const cl_modint_ring find_modint_ring (const cl_I& 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);
188 throw runtime_exception();
190 return *ring_in_table;
193 const cl_modint_ring cl_modint0_ring = cl_modint0_ring;
195 int cl_MI_init_helper::count = 0;
197 cl_MI_init_helper::cl_MI_init_helper()
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));
206 cl_MI_init_helper::~cl_MI_init_helper()
209 // Nothing to clean up?