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