include/cln/ring.h

   1 // Ring operations.
   2
   3 #ifndef _CL_RING_H
   4 #define _CL_RING_H
   5
   6 #include "cln/object.h"
   7 #include "cln/malloc.h"
   8 #include "cln/proplist.h"
   9 #include "cln/number.h"
  10 #include "cln/io.h"
  11
  12 namespace cln {
  13
  14 class cl_I;
  15
  16 // This file defines the general layout of rings, ring elements, and
  17 // operations available on ring elements. Any subclass of `cl_ring'
  18 // must implement these operations, with the same memory layout.
  19 // (Because generic packages like the polynomial rings access the base
  20 // ring's operation vectors through inline functions defined in this file.)
  21
  22 class cl_heap_ring;
  23
  24 // Rings are reference counted, but not freed immediately when they aren't
  25 // used any more. Hence they inherit from `cl_rcpointer'.
  26
  27 // Vectors of function pointers are more efficient than virtual member
  28 // functions. But it constrains us not to use multiple or virtual inheritance.
  29 //
  30 // Note! We are passing raw `cl_heap_ring*' pointers to the operations
  31 // for efficiency (compared to passing `const cl_ring&', we save a memory
  32 // access, and it is easier to cast to a `cl_heap_ring_specialized*').
  33 // These raw pointers are meant to be used downward (in the dynamic extent
  34 // of the call) only. If you need to save them in a data structure, cast
  35 // to `cl_ring'; this will correctly increment the reference count.
  36 // (This technique is safe because the inline wrapper functions make sure
  37 // that we have a `cl_ring' somewhere containing the pointer, so there
  38 // is no danger of dangling pointers.)
  39 //
  40 // Note! Because the `cl_heap_ring*' -> `cl_ring' conversion increments
  41 // the reference count, you have to use the `cl_private_thing' -> `cl_ring'
  42 // conversion if the reference count is already incremented.
  43
  44 class cl_ring : public cl_rcpointer {
  45 public:
  46         // Constructor. Takes a cl_heap_ring*, increments its refcount.
  47         cl_ring (cl_heap_ring* r);
  48         // Private constructor. Doesn't increment the refcount.
  49         cl_ring (cl_private_thing);
  50         // Copy constructor.
  51         cl_ring (const cl_ring&);
  52         // Assignment operator.
  53         cl_ring& operator= (const cl_ring&);
  54         // Default constructor.
  55         cl_ring ();
  56         // Automatic dereferencing.
  57         cl_heap_ring* operator-> () const
  58         { return (cl_heap_ring*)heappointer; }
  59 };
  60 CL_DEFINE_COPY_CONSTRUCTOR2(cl_ring,cl_rcpointer)
  61 CL_DEFINE_ASSIGNMENT_OPERATOR(cl_ring,cl_ring)
  62
  63 // Normal constructor for `cl_ring'.
  64 inline cl_ring::cl_ring (cl_heap_ring* r)
  65 { cl_inc_pointer_refcount((cl_heap*)r); pointer = r; }
  66 // Private constructor for `cl_ring'.
  67 inline cl_ring::cl_ring (cl_private_thing p)
  68 { pointer = p; }
  69
  70 inline bool operator== (const cl_ring& R1, const cl_ring& R2)
  71 { return (R1.pointer == R2.pointer); }
  72 inline bool operator!= (const cl_ring& R1, const cl_ring& R2)
  73 { return (R1.pointer != R2.pointer); }
  74 inline bool operator== (const cl_ring& R1, cl_heap_ring* R2)
  75 { return (R1.pointer == R2); }
  76 inline bool operator!= (const cl_ring& R1, cl_heap_ring* R2)
  77 { return (R1.pointer != R2); }
  78
  79 // Representation of an element of a ring.
  80 //
  81 // In order to support true polymorphism (without C++ templates), all
  82 // ring elements share the same basic layout:
  83 //      cl_ring ring;     // the ring
  84 //      cl_gcobject rep;  // representation of the element
  85 // The representation of the element depends on the ring, of course,
  86 // but we constrain it to be a single pointer into the heap or an immediate
  87 // value.
  88 //
  89 // Any arithmetic operation on a ring R (like +, -, *) must return a value
  90 // with ring = R. This is
  91 // a. necessary if the computation is to proceed correctly (e.g. in cl_RA,
  92 //    ((3/4)*4 mod 3) is 0, simplifying it to ((cl_I)4 mod (cl_I)3) = 1
  93 //    wouldn't be correct),
  94 // b. possible even if R is an extension ring of some ring R1 (e.g. cl_N
  95 //    being an extension ring of cl_R). Automatic retraction from R to R1
  96 //    can be done through dynamic typing: An element of R which happens
  97 //    to lie in R1 is stored using the internal representation of R1,
  98 //    but with ring = R. Elements of R1 and R\R1 can be distinguished
  99 //    through rep's type.
 100 // c. an advantage for the implementation of polynomials and other
 101 //    entities which contain many elements of the same ring. They need
 102 //    to store only the elements' representations, and a single pointer
 103 //    to the ring.
 104 //
 105 // The ring operations exist in two versions:
 106 // - Low-level version, which only operates on the representation.
 107 // - High-level version, which operates on full cl_ring_elements.
 108 // We make this distinction for performance: Multiplication of polynomials
 109 // over Z/nZ, operating on the high-level operations, spends 40% of its
 110 // computing time with packing and unpacking of cl_ring_elements.
 111 // The low-level versions have an underscore prepended and are unsafe.
 112
 113 class _cl_ring_element {
 114 public:
 115         cl_gcobject rep;        // representation of the element
 116         // Default constructor.
 117         _cl_ring_element ();
 118 public: /* ugh */
 119         // Constructor.
 120         _cl_ring_element (const cl_heap_ring* R, const cl_gcobject& r) : rep (as_cl_private_thing(r)) { (void)R; }
 121         _cl_ring_element (const cl_ring& R, const cl_gcobject& r) : rep (as_cl_private_thing(r)) { (void)R; }
 122 public: // Ability to place an object at a given address.
 123         void* operator new (size_t size) { return malloc_hook(size); }
 124         void* operator new (size_t size, void* ptr) { (void)size; return ptr; }
 125         void operator delete (void* ptr) { free_hook(ptr); }
 126 };
 127
 128 class cl_ring_element : public _cl_ring_element {
 129 protected:
 130         cl_ring _ring;                  // ring
 131 public:
 132         const cl_ring& ring () const { return _ring; }
 133         // Default constructor.
 134         cl_ring_element ();
 135 public: /* ugh */
 136         // Constructor.
 137         cl_ring_element (const cl_ring& R, const cl_gcobject& r) : _cl_ring_element (R,r), _ring (R) {}
 138         cl_ring_element (const cl_ring& R, const _cl_ring_element& r) : _cl_ring_element (r), _ring (R) {}
 139 public: // Debugging output.
 140         void debug_print () const;
 141         // Ability to place an object at a given address.
 142         void* operator new (size_t size) { return malloc_hook(size); }
 143         void* operator new (size_t size, void* ptr) { (void)size; return ptr; }
 144         void operator delete (void* ptr) { free_hook(ptr); }
 145 };
 146
 147 // The ring operations are encoded as vectors of function pointers. You
 148 // can add more operations to the end of each vector or add new vectors,
 149 // but you must not reorder the operations nor reorder the vectors nor
 150 // change the functions' signatures incompatibly.
 151
 152 // There should ideally be a template class for each vector, but unfortunately
 153 // you lose the ability to initialize the vector using "= { ... }" syntax
 154 // when you subclass it.
 155
 156 struct _cl_ring_setops {
 157         // print
 158         void (* fprint) (cl_heap_ring* R, std::ostream& stream, const _cl_ring_element& x);
 159         // equality
 160         cl_boolean (* equal) (cl_heap_ring* R, const _cl_ring_element& x, const _cl_ring_element& y);
 161         // ...
 162 };
 163 struct _cl_ring_addops {
 164         // 0
 165         const _cl_ring_element (* zero) (cl_heap_ring* R);
 166         cl_boolean (* zerop) (cl_heap_ring* R, const _cl_ring_element& x);
 167         // x+y
 168         const _cl_ring_element (* plus) (cl_heap_ring* R, const _cl_ring_element& x, const _cl_ring_element& y);
 169         // x-y
 170         const _cl_ring_element (* minus) (cl_heap_ring* R, const _cl_ring_element& x, const _cl_ring_element& y);
 171         // -x
 172         const _cl_ring_element (* uminus) (cl_heap_ring* R, const _cl_ring_element& x);
 173         // ...
 174 };
 175 struct _cl_ring_mulops {
 176         // 1
 177         const _cl_ring_element (* one) (cl_heap_ring* R);
 178         // canonical homomorphism
 179         const _cl_ring_element (* canonhom) (cl_heap_ring* R, const cl_I& x);
 180         // x*y
 181         const _cl_ring_element (* mul) (cl_heap_ring* R, const _cl_ring_element& x, const _cl_ring_element& y);
 182         // x^2
 183         const _cl_ring_element (* square) (cl_heap_ring* R, const _cl_ring_element& x);
 184         // x^y, y Integer >0
 185         const _cl_ring_element (* expt_pos) (cl_heap_ring* R, const _cl_ring_element& x, const cl_I& y);
 186         // ...
 187 };
 188   typedef const _cl_ring_setops  cl_ring_setops;
 189   typedef const _cl_ring_addops  cl_ring_addops;
 190   typedef const _cl_ring_mulops  cl_ring_mulops;
 191
 192 // Representation of a ring in memory.
 193
 194 class cl_heap_ring : public cl_heap {
 195 public:
 196         // Allocation.
 197         void* operator new (size_t size) { return malloc_hook(size); }
 198         // Deallocation.
 199         void operator delete (void* ptr) { free_hook(ptr); }
 200 private:
 201         cl_property_list properties;
 202 protected:
 203         cl_ring_setops* setops;
 204         cl_ring_addops* addops;
 205         cl_ring_mulops* mulops;
 206 public:
 207         // More information comes here.
 208         // ...
 209 public:
 210         // Low-level operations.
 211         void _fprint (std::ostream& stream, const _cl_ring_element& x)
 212                 { setops->fprint(this,stream,x); }
 213         cl_boolean _equal (const _cl_ring_element& x, const _cl_ring_element& y)
 214                 { return setops->equal(this,x,y); }
 215         const _cl_ring_element _zero ()
 216                 { return addops->zero(this); }
 217         cl_boolean _zerop (const _cl_ring_element& x)
 218                 { return addops->zerop(this,x); }
 219         const _cl_ring_element _plus (const _cl_ring_element& x, const _cl_ring_element& y)
 220                 { return addops->plus(this,x,y); }
 221         const _cl_ring_element _minus (const _cl_ring_element& x, const _cl_ring_element& y)
 222                 { return addops->minus(this,x,y); }
 223         const _cl_ring_element _uminus (const _cl_ring_element& x)
 224                 { return addops->uminus(this,x); }
 225         const _cl_ring_element _one ()
 226                 { return mulops->one(this); }
 227         const _cl_ring_element _canonhom (const cl_I& x)
 228                 { return mulops->canonhom(this,x); }
 229         const _cl_ring_element _mul (const _cl_ring_element& x, const _cl_ring_element& y)
 230                 { return mulops->mul(this,x,y); }
 231         const _cl_ring_element _square (const _cl_ring_element& x)
 232                 { return mulops->square(this,x); }
 233         const _cl_ring_element _expt_pos (const _cl_ring_element& x, const cl_I& y)
 234                 { return mulops->expt_pos(this,x,y); }
 235         // High-level operations.
 236         void fprint (std::ostream& stream, const cl_ring_element& x)
 237         {
 238                 if (!(x.ring() == this)) cl_abort();
 239                 _fprint(stream,x);
 240         }
 241         cl_boolean equal (const cl_ring_element& x, const cl_ring_element& y)
 242         {
 243                 if (!(x.ring() == this)) cl_abort();
 244                 if (!(y.ring() == this)) cl_abort();
 245                 return _equal(x,y);
 246         }
 247         const cl_ring_element zero ()
 248         {
 249                 return cl_ring_element(this,_zero());
 250         }
 251         cl_boolean zerop (const cl_ring_element& x)
 252         {
 253                 if (!(x.ring() == this)) cl_abort();
 254                 return _zerop(x);
 255         }
 256         const cl_ring_element plus (const cl_ring_element& x, const cl_ring_element& y)
 257         {
 258                 if (!(x.ring() == this)) cl_abort();
 259                 if (!(y.ring() == this)) cl_abort();
 260                 return cl_ring_element(this,_plus(x,y));
 261         }
 262         const cl_ring_element minus (const cl_ring_element& x, const cl_ring_element& y)
 263         {
 264                 if (!(x.ring() == this)) cl_abort();
 265                 if (!(y.ring() == this)) cl_abort();
 266                 return cl_ring_element(this,_minus(x,y));
 267         }
 268         const cl_ring_element uminus (const cl_ring_element& x)
 269         {
 270                 if (!(x.ring() == this)) cl_abort();
 271                 return cl_ring_element(this,_uminus(x));
 272         }
 273         const cl_ring_element one ()
 274         {
 275                 return cl_ring_element(this,_one());
 276         }
 277         const cl_ring_element canonhom (const cl_I& x)
 278         {
 279                 return cl_ring_element(this,_canonhom(x));
 280         }
 281         const cl_ring_element mul (const cl_ring_element& x, const cl_ring_element& y)
 282         {
 283                 if (!(x.ring() == this)) cl_abort();
 284                 if (!(y.ring() == this)) cl_abort();
 285                 return cl_ring_element(this,_mul(x,y));
 286         }
 287         const cl_ring_element square (const cl_ring_element& x)
 288         {
 289                 if (!(x.ring() == this)) cl_abort();
 290                 return cl_ring_element(this,_square(x));
 291         }
 292         const cl_ring_element expt_pos (const cl_ring_element& x, const cl_I& y)
 293         {
 294                 if (!(x.ring() == this)) cl_abort();
 295                 return cl_ring_element(this,_expt_pos(x,y));
 296         }
 297         // Property operations.
 298         cl_property* get_property (const cl_symbol& key)
 299                 { return properties.get_property(key); }
 300         void add_property (cl_property* new_property)
 301                 { properties.add_property(new_property); }
 302 // Constructor.
 303         cl_heap_ring (cl_ring_setops* setopv, cl_ring_addops* addopv, cl_ring_mulops* mulopv)
 304                 : setops (setopv), addops (addopv), mulops (mulopv)
 305                 { refcount = 0; } // will be incremented by the `cl_ring' constructor
 306 };
 307 #define SUBCLASS_cl_heap_ring() \
 308 public:                                                                   \
 309         /* Allocation. */                                                 \
 310         void* operator new (size_t size) { return malloc_hook(size); } \
 311         /* Deallocation. */                                               \
 312         void operator delete (void* ptr) { free_hook(ptr); }
 313
 314 // Operations on ring elements.
 315
 316 // Output.
 317 inline void fprint (std::ostream& stream, const cl_ring_element& x)
 318         { x.ring()->fprint(stream,x); }
 319 CL_DEFINE_PRINT_OPERATOR(cl_ring_element)
 320
 321 // Add.
 322 inline const cl_ring_element operator+ (const cl_ring_element& x, const cl_ring_element& y)
 323         { return x.ring()->plus(x,y); }
 324
 325 // Negate.
 326 inline const cl_ring_element operator- (const cl_ring_element& x)
 327         { return x.ring()->uminus(x); }
 328
 329 // Subtract.
 330 inline const cl_ring_element operator- (const cl_ring_element& x, const cl_ring_element& y)
 331         { return x.ring()->minus(x,y); }
 332
 333 // Equality.
 334 inline bool operator== (const cl_ring_element& x, const cl_ring_element& y)
 335         { return x.ring()->equal(x,y); }
 336 inline bool operator!= (const cl_ring_element& x, const cl_ring_element& y)
 337         { return !x.ring()->equal(x,y); }
 338
 339 // Compare against 0.
 340 inline cl_boolean zerop (const cl_ring_element& x)
 341         { return x.ring()->zerop(x); }
 342
 343 // Multiply.
 344 inline const cl_ring_element operator* (const cl_ring_element& x, const cl_ring_element& y)
 345         { return x.ring()->mul(x,y); }
 346
 347 // Squaring.
 348 inline const cl_ring_element square (const cl_ring_element& x)
 349         { return x.ring()->square(x); }
 350
 351 // Exponentiation x^y, where y > 0.
 352 inline const cl_ring_element expt_pos (const cl_ring_element& x, const cl_I& y)
 353         { return x.ring()->expt_pos(x,y); }
 354
 355 // Scalar multiplication.
 356 // [Is this operation worth being specially optimized for the case of
 357 // polynomials?? Polynomials have a faster scalar multiplication.
 358 // We should use it.??]
 359 inline const cl_ring_element operator* (const cl_I& x, const cl_ring_element& y)
 360         { return y.ring()->mul(y.ring()->canonhom(x),y); }
 361 inline const cl_ring_element operator* (const cl_ring_element& x, const cl_I& y)
 362         { return x.ring()->mul(x.ring()->canonhom(y),x); }
 363
 364
 365 // Ring of uninitialized elements.
 366 // Any operation results in a run-time error.
 367
 368 extern const cl_ring cl_no_ring;
 369 extern cl_class cl_class_no_ring;
 370 CL_REQUIRE(cl_no_ring)
 371
 372 inline cl_ring::cl_ring ()
 373         : cl_rcpointer (as_cl_private_thing(cl_no_ring)) {}
 374 inline _cl_ring_element::_cl_ring_element ()
 375         : rep ((cl_private_thing) cl_combine(cl_FN_tag,0)) {}
 376 inline cl_ring_element::cl_ring_element ()
 377         : _cl_ring_element (), _ring () {}
 378
 379
 380 // Support for built-in number rings.
 381 // Beware, they are not optimally efficient.
 382
 383 template <class T>
 384 struct cl_number_ring_ops {
 385         cl_boolean (* contains) (const cl_number&);
 386         cl_boolean (* equal) (const T&, const T&);
 387         cl_boolean (* zerop) (const T&);
 388         const T (* plus) (const T&, const T&);
 389         const T (* minus) (const T&, const T&);
 390         const T (* uminus) (const T&);
 391         const T (* mul) (const T&, const T&);
 392         const T (* square) (const T&);
 393         const T (* expt_pos) (const T&, const cl_I&);
 394 };
 395 class cl_heap_number_ring : public cl_heap_ring {
 396 public:
 397         cl_number_ring_ops<cl_number>* ops;
 398         // Constructor.
 399         cl_heap_number_ring (cl_ring_setops* setopv, cl_ring_addops* addopv, cl_ring_mulops* mulopv, cl_number_ring_ops<cl_number>* opv)
 400                 : cl_heap_ring (setopv,addopv,mulopv), ops (opv) {}
 401 };
 402
 403 class cl_number_ring : public cl_ring {
 404 public:
 405         cl_number_ring (cl_heap_number_ring* r)
 406                 : cl_ring (r) {}
 407 };
 408
 409 template <class T>
 410 class cl_specialized_number_ring : public cl_number_ring {
 411 public:
 412         cl_specialized_number_ring ();
 413 };
 414
 415 // Type test.
 416 inline cl_boolean instanceof (const cl_number& x, const cl_number_ring& R)
 417 {
 418         return ((cl_heap_number_ring*) R.heappointer)->ops->contains(x);
 419 }
 420
 421
 422 // Hack section.
 423
 424 // Conversions to subtypes without checking:
 425 // The2(cl_MI)(x) converts x to a cl_MI, without change of representation!
 426   #define The(type)  *(const type *) & cl_identity
 427   #define The2(type)  *(const type *) & cl_identity2
 428 // This inline function is for type checking purposes only.
 429   inline const cl_ring& cl_identity (const cl_ring& r) { return r; }
 430   inline const cl_ring_element& cl_identity2 (const cl_ring_element& x) { return x; }
 431   inline const cl_gcobject& cl_identity (const _cl_ring_element& x) { return x.rep; }
 432
 433
 434 // Debugging support.
 435 #ifdef CL_DEBUG
 436 extern int cl_ring_debug_module;
 437 CL_FORCE_LINK(cl_ring_debug_dummy, cl_ring_debug_module)
 438 #endif
 439
 440 }  // namespace cln
 441
 442 #endif /* _CL_RING_H */