imm.h
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file imm.h
5  *
6  * operations on immediates, that is elements of F_p, GF, Z, Q
7  * that fit into intrinsic int, long
8 **/
9 
10 #ifndef INCL_IMM_H
11 #define INCL_IMM_H
12 
13 #include <stdint.h>
14 
15 // #include "config.h"
16 
17 #ifndef NOSTREAMIO
18 #ifdef HAVE_IOSTREAM
19 #include <iostream>
20 #define OSTREAM std::ostream
21 #elif defined(HAVE_IOSTREAM_H)
22 #include <iostream.h>
23 #define OSTREAM ostream
24 #endif
25 #endif /* NOSTREAMIO */
26 
27 #include "cf_assert.h"
28 
29 #include "cf_defs.h"
30 #include "cf_globals.h"
31 #include "ffops.h"
32 #include "gfops.h"
33 #include "cf_factory.h"
34 #include "canonicalform.h"
35 #include "int_cf.h"
36 
37 const long INTMARK = 1;
38 const long FFMARK = 2;
39 const long GFMARK = 3;
40 
41 /* define type of your compilers 64 bit integer type */
42 #ifndef FACTORY_INT64
43 #define FACTORY_INT64 long long int
44 #endif
45 
46 #if SIZEOF_LONG == 4
47 const long MINIMMEDIATE = -268435454; // -2^28+2
48 const long MAXIMMEDIATE = 268435454; // 2^28-2
49 #else
50 const long MINIMMEDIATE = -(1L<<60)+2L; // -2^60+2
51 const long MAXIMMEDIATE = (1L<<60)-2L; // 2^60-2
52 #endif
53 
54 #if defined(WINNT) && ! defined(__GNUC__)
55 const FACTORY_INT64 MINIMMEDIATELL = -268435454i64;
56 const FACTORY_INT64 MAXIMMEDIATELL = 268435454i64;
57 #else
58 const FACTORY_INT64 MINIMMEDIATELL = -268435454LL;
59 const FACTORY_INT64 MAXIMMEDIATELL = 268435454LL;
60 #endif
61 
62 //{{{ conversion functions
63 //#ifdef HAS_ARITHMETIC_SHIFT
64 #if 1
65 
66 inline long imm2int ( const InternalCF * const imm )
67 {
68  return ((intptr_t)imm) >> 2;
69 }
70 
71 inline InternalCF * int2imm ( long i )
72 {
73  return (InternalCF*)((i << 2) | INTMARK );
74 }
75 
76 #else
77 
78 inline int imm2int ( const InternalCF * const imm )
79 {
80  // this could be better done by masking the sign bit
81  if ( ((int)((intptr_t)imm)) < 0 )
82  return -((-(intptr_t)imm) >> 2);
83  else
84  return (intptr_t)imm >> 2;
85 }
86 
87 inline InternalCF * int2imm ( long i )
88 {
89  if ( i < 0 )
90  return (InternalCF*)(-(((-i) << 2) | INTMARK));
91  else
92  return (InternalCF*)((i << 2) | INTMARK );
93 }
94 
95 #endif
96 
97 inline InternalCF * int2imm_p ( long i )
98 {
99  return (InternalCF*)((i << 2) | FFMARK );
100 }
101 
102 inline InternalCF * int2imm_gf ( long i )
103 {
104  return (InternalCF*)((i << 2) | GFMARK );
105 }
106 //}}}
107 
108 // predicates
109 #if 0
110 inline int is_imm ( const InternalCF * const ptr )
111 {
112  // returns 0 if ptr is not immediate
113  return ( (intptr_t)ptr & 3 );
114 }
115 #endif
116 
117 //{{{ inline int imm_isone, imm_isone_p, imm_isone_gf ( const InternalCF * const ptr )
118 // docu: see CanonicalForm::isOne()
119 inline int
120 imm_isone ( const InternalCF * const ptr )
121 {
122  return imm2int( ptr ) == 1;
123 }
124 
125 inline int
126 imm_isone_p ( const InternalCF * const ptr )
127 {
128  return imm2int( ptr ) == 1;
129 }
130 
131 inline int
132 imm_isone_gf ( const InternalCF * const ptr )
133 {
134  return gf_isone( imm2int( ptr ) );
135 }
136 //}}}
137 
138 //{{{ inline int imm_iszero, imm_iszero_p, imm_iszero_gf ( const InternalCF * const ptr )
139 // docu: see CanonicalForm::isZero()
140 inline int
141 imm_iszero ( const InternalCF * const ptr )
142 {
143  return imm2int( ptr ) == 0;
144 }
145 
146 inline int
147 imm_iszero_p ( const InternalCF * const ptr )
148 {
149  return imm2int( ptr ) == 0;
150 }
151 
152 inline int
153 imm_iszero_gf ( const InternalCF * const ptr )
154 {
155  return gf_iszero( imm2int( ptr ) );
156 }
157 //}}}
158 
159 //{{{ conversion functions
160 inline long imm_intval ( const InternalCF* const op )
161 {
162  if ( is_imm( op ) == FFMARK )
163  if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
164  return ff_symmetric( imm2int( op ) );
165  else
166  return imm2int( op );
167  else if ( is_imm( op ) == GFMARK ) {
168  ASSERT( gf_isff( imm2int( op ) ), "invalid conversion" );
169  if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
170  return ff_symmetric( gf_gf2ff( imm2int( op ) ) );
171  else
172  return gf_gf2ff( imm2int( op ) );
173  }
174  else
175  return imm2int( op );
176 }
177 //}}}
178 
179 /**
180  *
181  * imm_sign() - return sign of immediate object.
182  *
183  * If CO is an immediate integer, the sign is defined as usual.
184  * If CO is an element of FF(p) and SW_SYMMETRIC_FF is on the
185  * sign of CO is the sign of the symmetric representation of CO.
186  * If CO is in GF(q) or in FF(p) and SW_SYMMETRIC_FF is off, the
187  * sign of CO is zero iff CO is zero, otherwise the sign is one.
188  *
189  * @sa CanonicalForm::sign(), gf_sign()
190  *
191 **/
192 inline int
193 imm_sign ( const InternalCF * const op )
194 {
195  if ( is_imm( op ) == FFMARK )
196  if ( imm2int( op ) == 0 )
197  return 0;
198  else if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
199  if ( ff_symmetric( imm2int( op ) ) > 0 )
200  return 1;
201  else
202  return -1;
203  else
204  return 1;
205  else if ( is_imm( op ) == GFMARK )
206  return gf_sign( imm2int( op ) );
207  else if ( imm2int( op ) == 0 )
208  return 0;
209  else if ( imm2int( op ) > 0 )
210  return 1;
211  else
212  return -1;
213 }
214 
215 /**
216  *
217  * imm_cmp(), imm_cmp_p(), imm_cmp_gf() - compare immediate objects.
218  *
219  * For immediate integers, it is clear how this should be done.
220  * For objects from finite fields, it is not clear since they
221  * are not ordered fields. However, since we want to have a
222  * total well order on polynomials we have to define a total well
223  * order on all coefficients, too. We decided to use simply the
224  * order on the representation as `int's of such objects.
225  *
226  * @sa CanonicalForm::operator <(), CanonicalForm::operator ==()
227  *
228 **/
229 inline int
230 imm_cmp ( const InternalCF * const lhs, const InternalCF * const rhs )
231 {
232  if ( imm2int( lhs ) == imm2int( rhs ) )
233  return 0;
234  else if ( imm2int( lhs ) > imm2int( rhs ) )
235  return 1;
236  else
237  return -1;
238 }
239 
240 inline int
241 imm_cmp_p ( const InternalCF * const lhs, const InternalCF * const rhs )
242 {
243  if ( imm2int( lhs ) == imm2int( rhs ) )
244  return 0;
245  else if ( imm2int( lhs ) > imm2int( rhs ) )
246  return 1;
247  else
248  return -1;
249 }
250 
251 inline int
252 imm_cmp_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
253 {
254  if ( imm2int( lhs ) == imm2int( rhs ) )
255  return 0;
256  // check is done in this way because zero should be minimal
257  else if ( imm2int( lhs ) > imm2int( rhs ) )
258  return -1;
259  else
260  return 1;
261 }
262 //}}}
263 
264 //{{{ arithmetic operators
265 inline InternalCF * imm_add ( const InternalCF * const lhs, const InternalCF * const rhs )
266 {
267  long result = imm2int( lhs ) + imm2int( rhs );
268  if ( ( result > MAXIMMEDIATE ) || ( result < MINIMMEDIATE ) )
269  return CFFactory::basic( result );
270  else
271  return int2imm( result );
272 }
273 
274 inline InternalCF * imm_add_p ( const InternalCF * const lhs, const InternalCF * const rhs )
275 {
276  return int2imm_p( ff_add( imm2int( lhs ), imm2int( rhs ) ) );
277 }
278 
279 inline InternalCF * imm_add_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
280 {
281  return int2imm_gf( gf_add( imm2int( lhs ), imm2int( rhs ) ) );
282 }
283 
284 inline InternalCF * imm_sub ( const InternalCF * const lhs, const InternalCF * const rhs )
285 {
286  long result = imm2int( lhs ) - imm2int( rhs );
287  if ( ( result > MAXIMMEDIATE ) || ( result < MINIMMEDIATE ) )
288  return CFFactory::basic( result );
289  else
290  return int2imm( result );
291 }
292 
293 inline InternalCF * imm_sub_p ( const InternalCF * const lhs, const InternalCF * const rhs )
294 {
295  return int2imm_p( ff_sub( imm2int( lhs ), imm2int( rhs ) ) );
296 }
297 
298 inline InternalCF * imm_sub_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
299 {
300  return int2imm_gf( gf_sub( imm2int( lhs ), imm2int( rhs ) ) );
301 }
302 
303 inline InternalCF *
304 imm_mul ( InternalCF * lhs, InternalCF * rhs )
305 {
306  long a = imm2int( lhs );
307  long b = imm2int( rhs );
308  int sa= 1;
309  unsigned FACTORY_INT64 aa, bb;
310  if (a < 0)
311  {
312  sa= -1;
313  aa= (unsigned FACTORY_INT64) (-a);
314  }
315  else
316  aa= (unsigned FACTORY_INT64) a;
317  if (b < 0)
318  {
319  sa= -sa;
320  bb= (unsigned FACTORY_INT64) (-b);
321  }
322  else
323  bb= (unsigned FACTORY_INT64) b;
324  unsigned FACTORY_INT64 result = aa*bb;
325  #if SIZEOF_LONG == 4
326  if (result>(unsigned FACTORY_INT64)MAXIMMEDIATE)
327  {
329  return res->mulcoeff( rhs );
330  }
331  #else
332  if ( ( a!=0L ) && ((result/aa!=bb) || (result>(unsigned FACTORY_INT64) MAXIMMEDIATE) ))
333  {
335  return res->mulcoeff( rhs );
336  }
337  #endif
338  else
339  return int2imm( sa*result );
340 }
341 
342 inline InternalCF * imm_mul_p ( const InternalCF * const lhs, const InternalCF * const rhs )
343 {
344  return int2imm_p( ff_mul( imm2int( lhs ), imm2int( rhs ) ) );
345 }
346 
347 inline InternalCF * imm_mul_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
348 {
349  return int2imm_gf( gf_mul( imm2int( lhs ), imm2int( rhs ) ) );
350 }
351 
352 inline InternalCF * imm_div ( const InternalCF * const lhs, const InternalCF * const rhs )
353 {
354  long a = imm2int( lhs );
355  long b = imm2int( rhs );
356  if ( a > 0 )
357  return int2imm( a / b );
358  else if ( b > 0 )
359  return int2imm( -((b-a-1)/b) );
360  else
361  return int2imm( (-a-b-1)/(-b) );
362 }
363 
364 inline InternalCF * imm_divrat ( const InternalCF * const lhs, const InternalCF * const rhs )
365 {
366  if ( cf_glob_switches.isOn( SW_RATIONAL ) )
367  return CFFactory::rational( imm2int( lhs ), imm2int( rhs ) );
368  else {
369  long a = imm2int( lhs );
370  long b = imm2int( rhs );
371  if ( a > 0 )
372  return int2imm( a / b );
373  else if ( b > 0 )
374  return int2imm( -((b-a-1)/b) );
375  else
376  return int2imm( (-a-b-1)/(-b) );
377  }
378 }
379 
380 inline InternalCF * imm_div_p ( const InternalCF * const lhs, const InternalCF * const rhs )
381 {
382  return int2imm_p( ff_div( imm2int( lhs ), imm2int( rhs ) ) );
383 }
384 
385 inline InternalCF * imm_div_gf ( const InternalCF * const lhs, const InternalCF * const rhs )
386 {
387  return int2imm_gf( gf_div( imm2int( lhs ), imm2int( rhs ) ) );
388 }
389 
390 inline InternalCF * imm_mod ( const InternalCF * const lhs, const InternalCF * const rhs )
391 {
392  if ( cf_glob_switches.isOn( SW_RATIONAL ) )
393  return int2imm( 0 );
394  else {
395  long a = imm2int( lhs );
396  long b = imm2int( rhs );
397  if ( a > 0 )
398  if ( b > 0 )
399  return int2imm( a % b );
400  else
401  return int2imm( a % (-b) );
402  else
403  if ( b > 0 ) {
404  long r = (-a) % b;
405  return int2imm( (r==0) ? r : b-r );
406  }
407  else {
408  long r = (-a) % (-b);
409  return int2imm( (r==0) ? r : -b-r );
410  }
411  }
412 }
413 
414 inline InternalCF * imm_mod_p ( const InternalCF * const, const InternalCF * const )
415 {
416  return int2imm_p( 0 );
417 }
418 
419 inline InternalCF * imm_mod_gf ( const InternalCF * const, const InternalCF * const )
420 {
421  return int2imm_gf( gf_q );
422 }
423 
424 inline void imm_divrem ( const InternalCF * const lhs, const InternalCF * const rhs, InternalCF * & q, InternalCF * & r )
425 {
426  if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
427  q = imm_divrat( lhs, rhs );
428  r = CFFactory::basic( 0L );
429  }
430  else {
431  q = imm_div( lhs, rhs );
432  r = imm_mod( lhs, rhs );
433  }
434 }
435 
436 inline void imm_divrem_p ( const InternalCF * const lhs, const InternalCF * const rhs, InternalCF * & q, InternalCF * & r )
437 {
438  q = int2imm_p( ff_div( imm2int( lhs ), imm2int( rhs ) ) );
439  r = int2imm_p( 0 );
440 }
441 
442 inline void imm_divrem_gf ( const InternalCF * const lhs, const InternalCF * const rhs, InternalCF * & q, InternalCF * & r )
443 {
444  q = int2imm_gf( gf_div( imm2int( lhs ), imm2int( rhs ) ) );
445  r = int2imm_gf( gf_q );
446 }
447 
448 //{{{ inline InternalCF * imm_neg, imm_neg_p, imm_neg_gf ( const InternalCF * const op )
449 // docu: see CanonicalForm::operator -()
450 inline InternalCF *
451 imm_neg ( const InternalCF * const op )
452 {
453  return int2imm( -imm2int( op ) );
454 }
455 
456 inline InternalCF *
457 imm_neg_p ( const InternalCF * const op )
458 {
459  return int2imm_p( ff_neg( imm2int( op ) ) );
460 }
461 
462 inline InternalCF *
463 imm_neg_gf ( const InternalCF * const op )
464 {
465  return int2imm_gf( gf_neg( imm2int( op ) ) );
466 }
467 //}}}
468 //}}}
469 
470 //{{{ input/output
471 #ifndef NOSTREAMIO
472 inline void imm_print ( OSTREAM & os, const InternalCF * const op, const char * const str )
473 {
474  if ( is_imm( op ) == FFMARK )
475  if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
476  os << ff_symmetric( imm2int( op ) ) << str;
477  else
478  os << imm2int( op ) << str;
479  else if ( is_imm( op ) == GFMARK ) {
480  gf_print( os, imm2int( op ) );
481  os << str;
482  }
483  else
484  os << imm2int( op ) << str;
485 }
486 #endif /* NOSTREAMIO */
487 //}}}
488 
489 #endif /* ! INCL_IMM_H */
int imm_iszero_p(const InternalCF *const ptr)
Definition: imm.h:147
InternalCF * imm_sub(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:284
const long MINIMMEDIATE
Definition: imm.h:50
const poly a
Definition: syzextra.cc:212
const long GFMARK
Definition: imm.h:39
int gf_div(int a, int b)
Definition: gfops.h:185
InternalCF * imm_neg_p(const InternalCF *const op)
Definition: imm.h:457
InternalCF * imm_mod(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:390
int gf_sub(int a, int b)
Definition: gfops.h:158
#define FACTORY_INT64
Definition: factoryconf.h:57
InternalCF * int2imm(long i)
Definition: imm.h:71
void gf_print(OSTREAM &os, int a)
Definition: gfops.h:207
InternalCF * imm_mul_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:347
InternalCF * imm_add_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:279
int ff_mul(const int a, const int b)
Definition: ffops.h:141
long gf_gf2ff(long a)
Definition: gfops.cc:226
const FACTORY_INT64 MAXIMMEDIATELL
Definition: imm.h:59
const long FFMARK
Definition: imm.h:38
const FACTORY_INT64 MINIMMEDIATELL
Definition: imm.h:58
#define OSTREAM
Definition: imm.h:20
InternalCF * imm_div_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:380
assertions for Factory
int imm_cmp_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:241
bool gf_isone(int a)
Definition: gfops.h:53
InternalCF * int2imm_p(long i)
Definition: imm.h:97
InternalCF * imm_div_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:385
int imm_cmp(const InternalCF *const lhs, const InternalCF *const rhs)
imm_cmp(), imm_cmp_p(), imm_cmp_gf() - compare immediate objects.
Definition: imm.h:230
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
#define IntegerDomain
Definition: cf_defs.h:25
int gf_neg(int a)
Definition: gfops.h:123
int gf_q
Definition: gfops.cc:47
int imm_isone_p(const InternalCF *const ptr)
Definition: imm.h:126
int ff_div(const int a, const int b)
Definition: ffops.h:163
poly res
Definition: myNF.cc:322
void imm_divrem(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:424
InternalCF * imm_mod_p(const InternalCF *const, const InternalCF *const)
Definition: imm.h:414
const ring r
Definition: syzextra.cc:208
void imm_divrem_gf(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:442
int imm_iszero_gf(const InternalCF *const ptr)
Definition: imm.h:153
Operations in GF, where GF is a finite field of size less than 2^16 represented by a root of Conway p...
static InternalCF * rational(long num, long den)
Definition: cf_factory.cc:213
InternalCF * imm_div(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:352
int imm_iszero(const InternalCF *const ptr)
Definition: imm.h:141
bool gf_isff(long a)
Definition: gfops.cc:270
int ff_sub(const int a, const int b)
Definition: ffops.h:114
Interface to generate InternalCF&#39;s over various domains from intrinsic types or mpz_t&#39;s.
bool gf_iszero(int a)
Definition: gfops.h:43
long imm_intval(const InternalCF *const op)
Definition: imm.h:160
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
InternalCF * int2imm_gf(long i)
Definition: imm.h:102
int ff_neg(const int a)
Definition: ffops.h:128
int i
Definition: cfEzgcd.cc:123
static InternalCF * basic(long value)
Definition: cf_factory.cc:21
factory switches.
int gf_mul(int a, int b)
Definition: gfops.h:163
InternalCF * imm_sub_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:298
InternalCF * imm_neg(const InternalCF *const op)
Definition: imm.h:451
InternalCF * imm_mul(InternalCF *lhs, InternalCF *rhs)
Definition: imm.h:304
InternalCF * imm_sub_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:293
int ff_add(const int a, const int b)
Definition: ffops.h:99
void imm_print(OSTREAM &os, const InternalCF *const op, const char *const str)
Definition: imm.h:472
long imm2int(const InternalCF *const imm)
Definition: imm.h:66
const long MAXIMMEDIATE
Definition: imm.h:51
InternalCF * imm_mul_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:342
int gf_sign(int a)
Definition: gfops.h:113
InternalCF * imm_divrat(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:364
int imm_sign(const InternalCF *const op)
imm_sign() - return sign of immediate object.
Definition: imm.h:193
InternalCF * imm_neg_gf(const InternalCF *const op)
Definition: imm.h:463
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
int imm_isone_gf(const InternalCF *const ptr)
Definition: imm.h:132
void imm_divrem_p(const InternalCF *const lhs, const InternalCF *const rhs, InternalCF *&q, InternalCF *&r)
Definition: imm.h:436
int imm_isone(const InternalCF *const ptr)
Definition: imm.h:120
const long INTMARK
Definition: imm.h:37
InternalCF * imm_add(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:265
int gf_add(int a, int b)
Definition: gfops.h:133
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75
Factory&#39;s internal CanonicalForm&#39;s.
InternalCF * imm_add_p(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:274
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int imm_cmp_gf(const InternalCF *const lhs, const InternalCF *const rhs)
Definition: imm.h:252
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:30
operations in a finite prime field F_p.
const poly b
Definition: syzextra.cc:213
InternalCF * imm_mod_gf(const InternalCF *const, const InternalCF *const)
Definition: imm.h:419
return result
Definition: facAbsBiFact.cc:76
Header for factory&#39;s main class CanonicalForm.
int ff_symmetric(const int a)
Definition: ffops.h:59