1 // Modular integer operations.
9 #include "cln/modinteger.h"
18 #include "cln/integer_io.h"
21 #include "cln/abort.h"
22 #include "cl_alloca.h"
24 // MacOS X does "#define _R 0x00040000L"
30 static void cl_modint_ring_destructor (cl_heap* pointer)
32 (*(cl_heap_modint_ring*)pointer).~cl_heap_modint_ring();
35 cl_class cl_class_modint_ring = {
36 cl_modint_ring_destructor,
37 cl_class_flags_modint_ring
40 cl_heap_modint_ring::cl_heap_modint_ring (cl_I m, cl_modint_setops* setopv, cl_modint_addops* addopv, cl_modint_mulops* mulopv)
41 : setops (setopv), addops (addopv), mulops (mulopv), modulus (m)
43 refcount = 0; // will be incremented by the `cl_modint_ring' constructor
44 type = &cl_class_modint_ring;
45 if (minusp(m)) cl_abort();
47 var uintL b = integer_length(m-1);
48 // m <= 2^b, hence one needs b bits for a representative mod m.
50 log2_bits = 0; bits = 1;
51 } else if (b <= cl_word_size) {
53 integerlength32(b-1,bb=); // b <= 2^bb with bb minimal
54 log2_bits = bb; bits = 1<<bb;
56 log2_bits = -1; bits = -1;
59 log2_bits = -1; bits = -1;
64 static cl_boolean modint_equal (cl_heap_modint_ring* R, const _cl_MI& x, const _cl_MI& y)
67 return equal(x.rep,y.rep);
71 #include "cl_MI_int.h"
72 #include "cl_MI_std.h"
73 #include "cl_MI_fix16.h"
74 #if (cl_value_len <= 32)
75 #include "cl_MI_fix29.h"
76 #include "cl_MI_int32.h"
78 #include "cl_MI_fix32.h"
80 #include "cl_MI_pow2.h"
81 #include "cl_MI_pow2m1.h"
82 #include "cl_MI_pow2p1.h"
83 #include "cl_MI_montgom.h"
87 static inline cl_heap_modint_ring* make_modint_ring (const cl_I& m) // m >= 0
90 return new cl_heap_modint_ring_int();
93 var uintL log2_m = power2p(m);
95 return new cl_heap_modint_ring_pow2(m,log2_m-1);
99 var uintL log2_m = integer_length(m); // = integerlength(m-1)
100 if (log2_m < 16) // m < 0x10000
101 return new cl_heap_modint_ring_fix16(m);
102 #if (cl_value_len <= 32)
103 if (log2_m < cl_value_len)
104 return new cl_heap_modint_ring_fix29(m);
105 if (log2_m < 32) // m < 0x100000000
106 return new cl_heap_modint_ring_int32(m);
108 if (log2_m < 32) // m < 0x100000000
109 return new cl_heap_modint_ring_fix32(m);
113 var uintL m1 = power2p(m+1);
115 return new cl_heap_modint_ring_pow2m1(m,m1-1);
118 var uintL m1 = power2p(m-1);
120 return new cl_heap_modint_ring_pow2p1(m,m1-1);
123 var cl_heap_modint_ring* R = try_make_modint_ring_montgom(m);
127 return new cl_heap_modint_ring_std(m);
131 // The table of modular integer rings.
132 // A weak hash table cl_I -> cl_modint_ring.
133 // (It could also be a weak hashuniq table cl_I -> cl_modint_ring.)
136 #include "cl_I_hashweak_rcpointer.h"
139 // An entry can be collected when the value (the ring) isn't referenced any more
140 // except from the hash table, and when the key (the modulus) isn't referenced
141 // any more except from the hash table and the ring. Note that the ring contains
142 // exactly one reference to the modulus.
144 static cl_boolean maygc_htentry (const cl_htentry_from_integer_to_rcpointer& entry)
146 if (!entry.key.pointer_p() || (entry.key.heappointer->refcount == 2))
147 if (!entry.val.pointer_p() || (entry.val.heappointer->refcount == 1))
152 static const cl_wht_from_integer_to_rcpointer modint_ring_table = cl_wht_from_integer_to_rcpointer(maygc_htentry);
154 static inline cl_modint_ring* get_modint_ring (const cl_I& m)
156 return (cl_modint_ring*) modint_ring_table.get(m);
159 static inline void store_modint_ring (const cl_modint_ring& R)
161 modint_ring_table.put(R->modulus,R);
165 const cl_modint_ring find_modint_ring (const cl_I& m)
169 var cl_modint_ring* ring_in_table = get_modint_ring(m);
170 if (!ring_in_table) {
171 var cl_modint_ring R = make_modint_ring(m);
172 store_modint_ring(R);
173 ring_in_table = get_modint_ring(m);
177 return *ring_in_table;
181 const cl_modint_ring cl_modint0_ring = find_modint_ring(0);
185 CL_PROVIDE_END(cl_MI)