8 #include "cl_proplist.h"
13 // This file defines the general layout of rings, ring elements, and
14 // operations available on ring elements. Any subclass of `cl_ring'
15 // must implement these operations, with the same memory layout.
16 // (Because generic packages like the polynomial rings access the base
17 // ring's operation vectors through inline functions defined in this file.)
21 // Rings are reference counted, but not freed immediately when they aren't
22 // used any more. Hence they inherit from `cl_rcpointer'.
24 // Vectors of function pointers are more efficient than virtual member
25 // functions. But it constrains us not to use multiple or virtual inheritance.
27 // Note! We are passing raw `cl_heap_ring*' pointers to the operations
28 // for efficiency (compared to passing `const cl_ring&', we save a memory
29 // access, and it is easier to cast to a `cl_heap_ring_specialized*').
30 // These raw pointers are meant to be used downward (in the dynamic extent
31 // of the call) only. If you need to save them in a data structure, cast
32 // to `cl_ring'; this will correctly increment the reference count.
33 // (This technique is safe because the inline wrapper functions make sure
34 // that we have a `cl_ring' somewhere containing the pointer, so there
35 // is no danger of dangling pointers.)
37 // Note! Because the `cl_heap_ring*' -> `cl_ring' conversion increments
38 // the reference count, you have to use the `cl_private_thing' -> `cl_ring'
39 // conversion if the reference count is already incremented.
41 class cl_ring : public cl_rcpointer {
43 // Constructor. Takes a cl_heap_ring*, increments its refcount.
44 cl_ring (cl_heap_ring* r);
45 // Private constructor. Doesn't increment the refcount.
46 cl_ring (cl_private_thing);
48 cl_ring (const cl_ring&);
49 // Assignment operator.
50 cl_ring& operator= (const cl_ring&);
51 // Default constructor.
53 // Automatic dereferencing.
54 cl_heap_ring* operator-> () const
55 { return (cl_heap_ring*)heappointer; }
57 CL_DEFINE_COPY_CONSTRUCTOR2(cl_ring,cl_rcpointer)
58 CL_DEFINE_ASSIGNMENT_OPERATOR(cl_ring,cl_ring)
60 // Normal constructor for `cl_ring'.
61 inline cl_ring::cl_ring (cl_heap_ring* r)
62 { cl_inc_pointer_refcount((cl_heap*)r); pointer = r; }
63 // Private constructor for `cl_ring'.
64 inline cl_ring::cl_ring (cl_private_thing p)
67 inline bool operator== (const cl_ring& R1, const cl_ring& R2)
68 { return (R1.pointer == R2.pointer); }
69 inline bool operator!= (const cl_ring& R1, const cl_ring& R2)
70 { return (R1.pointer != R2.pointer); }
71 inline bool operator== (const cl_ring& R1, cl_heap_ring* R2)
72 { return (R1.pointer == R2); }
73 inline bool operator!= (const cl_ring& R1, cl_heap_ring* R2)
74 { return (R1.pointer != R2); }
76 // Representation of an element of a ring.
78 // In order to support true polymorphism (without C++ templates), all
79 // ring elements share the same basic layout:
80 // cl_ring ring; // the ring
81 // cl_gcobject rep; // representation of the element
82 // The representation of the element depends on the ring, of course,
83 // but we constrain it to be a single pointer into the heap or an immediate
86 // Any arithmetic operation on a ring R (like +, -, *) must return a value
87 // with ring = R. This is
88 // a. necessary if the computation is to proceed correctly (e.g. in cl_RA,
89 // ((3/4)*4 mod 3) is 0, simplifying it to ((cl_I)4 mod (cl_I)3) = 1
90 // wouldn't be correct),
91 // b. possible even if R is an extension ring of some ring R1 (e.g. cl_N
92 // being an extension ring of cl_R). Automatic retraction from R to R1
93 // can be done through dynamic typing: An element of R which happens
94 // to lie in R1 is stored using the internal representation of R1,
95 // but with ring = R. Elements of R1 and R\R1 can be distinguished
96 // through rep's type.
97 // c. an advantage for the implementation of polynomials and other
98 // entities which contain many elements of the same ring. They need
99 // to store only the elements' representations, and a single pointer
102 // The ring operations exist in two versions:
103 // - Low-level version, which only operates on the representation.
104 // - High-level version, which operates on full cl_ring_elements.
105 // We make this distinction for performance: Multiplication of polynomials
106 // over Z/nZ, operating on the high-level operations, spends 40% of its
107 // computing time with packing and unpacking of cl_ring_elements.
108 // The low-level versions have an underscore prepended and are unsafe.
110 class _cl_ring_element {
112 cl_gcobject rep; // representation of the element
113 // Default constructor.
117 _cl_ring_element (const cl_heap_ring* R, const cl_gcobject& r) : rep (as_cl_private_thing(r)) { (void)R; }
118 _cl_ring_element (const cl_ring& R, const cl_gcobject& r) : rep (as_cl_private_thing(r)) { (void)R; }
119 public: // Ability to place an object at a given address.
120 void* operator new (size_t size) { return cl_malloc_hook(size); }
121 void* operator new (size_t size, _cl_ring_element* ptr) { (void)size; return ptr; }
122 void operator delete (void* ptr) { cl_free_hook(ptr); }
125 class cl_ring_element : public _cl_ring_element {
127 cl_ring _ring; // ring
129 const cl_ring& ring () const { return _ring; }
130 // Default constructor.
134 cl_ring_element (const cl_ring& R, const cl_gcobject& r) : _cl_ring_element (R,r), _ring (R) {}
135 cl_ring_element (const cl_ring& R, const _cl_ring_element& r) : _cl_ring_element (r), _ring (R) {}
136 public: // Debugging output.
137 void debug_print () const;
138 // Ability to place an object at a given address.
139 void* operator new (size_t size) { return cl_malloc_hook(size); }
140 void* operator new (size_t size, cl_ring_element* ptr) { (void)size; return ptr; }
141 void operator delete (void* ptr) { cl_free_hook(ptr); }
144 // The ring operations are encoded as vectors of function pointers. You
145 // can add more operations to the end of each vector or add new vectors,
146 // but you must not reorder the operations nor reorder the vectors nor
147 // change the functions' signatures incompatibly.
149 // There should ideally be a template class for each vector, but unfortunately
150 // you lose the ability to initialize the vector using "= { ... }" syntax
151 // when you subclass it.
153 struct _cl_ring_setops {
155 void (* fprint) (cl_heap_ring* R, cl_ostream stream, const _cl_ring_element& x);
157 cl_boolean (* equal) (cl_heap_ring* R, const _cl_ring_element& x, const _cl_ring_element& y);
160 struct _cl_ring_addops {
162 const _cl_ring_element (* zero) (cl_heap_ring* R);
163 cl_boolean (* zerop) (cl_heap_ring* R, const _cl_ring_element& x);
165 const _cl_ring_element (* plus) (cl_heap_ring* R, const _cl_ring_element& x, const _cl_ring_element& y);
167 const _cl_ring_element (* minus) (cl_heap_ring* R, const _cl_ring_element& x, const _cl_ring_element& y);
169 const _cl_ring_element (* uminus) (cl_heap_ring* R, const _cl_ring_element& x);
172 struct _cl_ring_mulops {
174 const _cl_ring_element (* one) (cl_heap_ring* R);
175 // canonical homomorphism
176 const _cl_ring_element (* canonhom) (cl_heap_ring* R, const cl_I& x);
178 const _cl_ring_element (* mul) (cl_heap_ring* R, const _cl_ring_element& x, const _cl_ring_element& y);
180 const _cl_ring_element (* square) (cl_heap_ring* R, const _cl_ring_element& x);
182 const _cl_ring_element (* expt_pos) (cl_heap_ring* R, const _cl_ring_element& x, const cl_I& y);
185 #if defined(__GNUC__) && (__GNUC__ == 2) && (__GNUC_MINOR__ < 8) // workaround two g++-2.7.0 bugs
186 #define cl_ring_setops _cl_ring_setops
187 #define cl_ring_addops _cl_ring_addops
188 #define cl_ring_mulops _cl_ring_mulops
190 typedef const _cl_ring_setops cl_ring_setops;
191 typedef const _cl_ring_addops cl_ring_addops;
192 typedef const _cl_ring_mulops cl_ring_mulops;
195 // Representation of a ring in memory.
197 class cl_heap_ring : public cl_heap {
200 void* operator new (size_t size) { return cl_malloc_hook(size); }
202 void operator delete (void* ptr) { cl_free_hook(ptr); }
204 cl_property_list properties;
206 cl_ring_setops* setops;
207 cl_ring_addops* addops;
208 cl_ring_mulops* mulops;
210 // More information comes here.
213 // Low-level operations.
214 void _fprint (cl_ostream stream, const _cl_ring_element& x)
215 { setops->fprint(this,stream,x); }
216 cl_boolean _equal (const _cl_ring_element& x, const _cl_ring_element& y)
217 { return setops->equal(this,x,y); }
218 const _cl_ring_element _zero ()
219 { return addops->zero(this); }
220 cl_boolean _zerop (const _cl_ring_element& x)
221 { return addops->zerop(this,x); }
222 const _cl_ring_element _plus (const _cl_ring_element& x, const _cl_ring_element& y)
223 { return addops->plus(this,x,y); }
224 const _cl_ring_element _minus (const _cl_ring_element& x, const _cl_ring_element& y)
225 { return addops->minus(this,x,y); }
226 const _cl_ring_element _uminus (const _cl_ring_element& x)
227 { return addops->uminus(this,x); }
228 const _cl_ring_element _one ()
229 { return mulops->one(this); }
230 const _cl_ring_element _canonhom (const cl_I& x)
231 { return mulops->canonhom(this,x); }
232 const _cl_ring_element _mul (const _cl_ring_element& x, const _cl_ring_element& y)
233 { return mulops->mul(this,x,y); }
234 const _cl_ring_element _square (const _cl_ring_element& x)
235 { return mulops->square(this,x); }
236 const _cl_ring_element _expt_pos (const _cl_ring_element& x, const cl_I& y)
237 { return mulops->expt_pos(this,x,y); }
238 // High-level operations.
239 void fprint (cl_ostream stream, const cl_ring_element& x)
241 if (!(x.ring() == this)) cl_abort();
244 cl_boolean equal (const cl_ring_element& x, const cl_ring_element& y)
246 if (!(x.ring() == this)) cl_abort();
247 if (!(y.ring() == this)) cl_abort();
250 const cl_ring_element zero ()
252 return cl_ring_element(this,_zero());
254 cl_boolean zerop (const cl_ring_element& x)
256 if (!(x.ring() == this)) cl_abort();
259 const cl_ring_element plus (const cl_ring_element& x, const cl_ring_element& y)
261 if (!(x.ring() == this)) cl_abort();
262 if (!(y.ring() == this)) cl_abort();
263 return cl_ring_element(this,_plus(x,y));
265 const cl_ring_element minus (const cl_ring_element& x, const cl_ring_element& y)
267 if (!(x.ring() == this)) cl_abort();
268 if (!(y.ring() == this)) cl_abort();
269 return cl_ring_element(this,_minus(x,y));
271 const cl_ring_element uminus (const cl_ring_element& x)
273 if (!(x.ring() == this)) cl_abort();
274 return cl_ring_element(this,_uminus(x));
276 const cl_ring_element one ()
278 return cl_ring_element(this,_one());
280 const cl_ring_element canonhom (const cl_I& x)
282 return cl_ring_element(this,_canonhom(x));
284 const cl_ring_element mul (const cl_ring_element& x, const cl_ring_element& y)
286 if (!(x.ring() == this)) cl_abort();
287 if (!(y.ring() == this)) cl_abort();
288 return cl_ring_element(this,_mul(x,y));
290 const cl_ring_element square (const cl_ring_element& x)
292 if (!(x.ring() == this)) cl_abort();
293 return cl_ring_element(this,_square(x));
295 const cl_ring_element expt_pos (const cl_ring_element& x, const cl_I& y)
297 if (!(x.ring() == this)) cl_abort();
298 return cl_ring_element(this,_expt_pos(x,y));
300 // Property operations.
301 cl_property* get_property (const cl_symbol& key)
302 { return properties.get_property(key); }
303 void add_property (cl_property* new_property)
304 { properties.add_property(new_property); }
306 cl_heap_ring (cl_ring_setops* setopv, cl_ring_addops* addopv, cl_ring_mulops* mulopv)
307 : setops (setopv), addops (addopv), mulops (mulopv)
308 { refcount = 0; } // will be incremented by the `cl_ring' constructor
310 #define SUBCLASS_cl_heap_ring() \
313 void* operator new (size_t size) { return cl_malloc_hook(size); } \
314 /* Deallocation. */ \
315 void operator delete (void* ptr) { cl_free_hook(ptr); }
317 // Operations on ring elements.
320 inline void fprint (cl_ostream stream, const cl_ring_element& x)
321 { x.ring()->fprint(stream,x); }
322 CL_DEFINE_PRINT_OPERATOR(cl_ring_element)
325 inline const cl_ring_element operator+ (const cl_ring_element& x, const cl_ring_element& y)
326 { return x.ring()->plus(x,y); }
329 inline const cl_ring_element operator- (const cl_ring_element& x)
330 { return x.ring()->uminus(x); }
333 inline const cl_ring_element operator- (const cl_ring_element& x, const cl_ring_element& y)
334 { return x.ring()->minus(x,y); }
337 inline bool operator== (const cl_ring_element& x, const cl_ring_element& y)
338 { return x.ring()->equal(x,y); }
339 inline bool operator!= (const cl_ring_element& x, const cl_ring_element& y)
340 { return !x.ring()->equal(x,y); }
342 // Compare against 0.
343 inline cl_boolean zerop (const cl_ring_element& x)
344 { return x.ring()->zerop(x); }
347 inline const cl_ring_element operator* (const cl_ring_element& x, const cl_ring_element& y)
348 { return x.ring()->mul(x,y); }
351 inline const cl_ring_element square (const cl_ring_element& x)
352 { return x.ring()->square(x); }
354 // Exponentiation x^y, where y > 0.
355 inline const cl_ring_element expt_pos (const cl_ring_element& x, const cl_I& y)
356 { return x.ring()->expt_pos(x,y); }
358 // Scalar multiplication.
359 // [Is this operation worth being specially optimized for the case of
360 // polynomials?? Polynomials have a faster scalar multiplication.
361 // We should use it.??]
362 inline const cl_ring_element operator* (const cl_I& x, const cl_ring_element& y)
363 { return y.ring()->mul(y.ring()->canonhom(x),y); }
364 inline const cl_ring_element operator* (const cl_ring_element& x, const cl_I& y)
365 { return x.ring()->mul(x.ring()->canonhom(y),x); }
368 // Ring of uninitialized elements.
369 // Any operation results in a run-time error.
371 extern const cl_ring cl_no_ring;
372 extern cl_class cl_class_no_ring;
373 CL_REQUIRE(cl_no_ring)
375 inline cl_ring::cl_ring ()
376 : cl_rcpointer (as_cl_private_thing(cl_no_ring)) {}
377 inline _cl_ring_element::_cl_ring_element ()
378 : rep ((cl_private_thing) cl_combine(cl_FN_tag,0)) {}
379 inline cl_ring_element::cl_ring_element ()
380 : _cl_ring_element (), _ring () {}
383 // Support for built-in number rings.
384 // Beware, they are not optimally efficient.
387 struct cl_number_ring_ops {
388 cl_boolean (* contains) (const cl_number&);
389 cl_boolean (* equal) (const T&, const T&);
390 cl_boolean (* zerop) (const T&);
391 const T (* plus) (const T&, const T&);
392 const T (* minus) (const T&, const T&);
393 const T (* uminus) (const T&);
394 const T (* mul) (const T&, const T&);
395 const T (* square) (const T&);
396 const T (* expt_pos) (const T&, const cl_I&);
398 class cl_heap_number_ring : public cl_heap_ring {
400 cl_number_ring_ops<cl_number>* ops;
402 cl_heap_number_ring (cl_ring_setops* setopv, cl_ring_addops* addopv, cl_ring_mulops* mulopv, cl_number_ring_ops<cl_number>* opv)
403 : cl_heap_ring (setopv,addopv,mulopv), ops (opv) {}
406 class cl_number_ring : public cl_ring {
408 cl_number_ring (cl_heap_number_ring* r)
413 class cl_specialized_number_ring : public cl_number_ring {
415 cl_specialized_number_ring ();
419 inline cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
421 return ((cl_heap_number_ring*) R.heappointer)->ops->contains(x);
427 // Conversions to subtypes without checking:
428 // The2(cl_MI)(x) converts x to a cl_MI, without change of representation!
429 #define The(type) *(const type *) & cl_identity
430 #define The2(type) *(const type *) & cl_identity2
431 // This inline function is for type checking purposes only.
432 inline const cl_ring& cl_identity (const cl_ring& r) { return r; }
433 inline const cl_ring_element& cl_identity2 (const cl_ring_element& x) { return x; }
434 inline const cl_gcobject& cl_identity (const _cl_ring_element& x) { return x.rep; }
437 // Debugging support.
439 extern int cl_ring_debug_module;
440 static void* const cl_ring_debug_dummy[] = { &cl_ring_debug_dummy,
441 &cl_ring_debug_module
446 #endif /* _CL_RING_H */