]> www.ginac.de Git - cln.git/blob - src/modinteger/cl_MI.cc
2004-01-01 Richard B. Kreckel <kreckel@ginac.de>
[cln.git] / 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)