1 The new polylib library combines both the Strasbourg version and IRISA version
2 and includes option to support 32 bit or 64 bit or GNU muti-precision integers.
3 It also includes the recent (April 2001) changes suggested by Doran Wilde and
4 the changes made by Vincent Loechner in polylib4.20. A new feature: computati-
5 ons on Z-polyhedron has been added into the new polylib version.
6 The new version has following changes compared to the polylib version at
9 *******************************************************************************
11 Directory: ./include/polylib
15 * Included "GMP" value-type.
16 eg: #else /* If defined(GNUMP) */
17 #define LINEAR_VALUE_GMP "gmp"
20 * Added macros corresponding to "GMP" value-type :-
21 eg:- ! Basic Macros :- value_init(val), etc..
22 ! Boolean operators on 'Value' :- value_eq(v1,v2), etc...
23 ! Trian operators on 'Value' :- value_sign(val),etc..
24 ! Binary operations on 'Value' :- value_addto(ref,val)
25 ! Conditional operations on 'Value' :- value_pos_p(val), etc...
27 * A few macros are not defined for "GMP" value-types compared to other
28 defined value-types, as there is no way to do so in "GMP".
29 eg:- (i) VALUE_CONST, VALUE_NAN, VALUE_MAX, VALUE_MIN, etc...
30 (ii) ! Cast to value macros :- int_to_value(i), etc....
31 (iii)! Binary operators on 'Value' :- value_plus(v1,v2), etc..
32 (iV) ! Unary operators on 'Value' :- value_not(val), etc...
34 * A few macros not defined for "GMP" value-types compared to other
35 defined value-types, as they seemed redundant in "GMP".
36 eg:- (i) value_direct_product(ref,val) /* No overflow check reqd. */
37 (ii) ! Various macros for protected multiplication :-
38 value_protected_multiply(v,w)
40 * A new set of macro defintions included in every value-type to handle
41 initialization and clear operations in "GMP".
42 eg:- value_init(val), value_assign(v1,v2),value_clear(val), etc ..
44 * A few macro definitions changed.
45 eg:- value_addto(ref,val) -> value_addto(ref,val1,val2)
46 value_increment(ref) -> value_increment(ref,val). etc...
48 * A few function prototype definitions removed as they were redundant.
49 eg:- extern Value abs_ofl_ctrl(...): abs.c
50 extern Value divide_fast(....): divide.c
51 extern Value pgcd_slow(......): pgcd.c
53 * Comments added and modified wherever seemed appropriate.
55 (2) arithmetic_errors.h
57 * added a test on the cygwin flag for CATCH and THROW macros
61 * Changes in function prototype definitions to match with the changes
62 made in the file 'eval_ehrhart.c'.
66 * Changes in function prototype definitions to match with the changes
67 made in the file 'matrix.c'.
72 extern Polyhedron *Stras_DomainSimplify(Polyhedron *Pol1, Polyhedron
73 *Pol2, unsigned NbMaxRays);
75 * Changes in function prototype definitions to match with the changes
76 made in the file 'polyhedron.c'.
80 * Added statement: && !defined(GNUMP)
82 * Removed few statements.
83 eg:- #include <polylib/types_mp.h>
84 #include <polylib/matrix_mp.h>
85 #include <polylib/ehrhart_mp.h>
89 * Changes in function prototype definitions to match with the changes
90 made in the file 'polyparam.c'.
94 * Added macro: #ifdef DGNUMP
98 $define MAXNOOFRAYS 200
100 * Added statement: #else /* Default : GNUMP */
101 #define P_VALUE_FMT "%4s"
104 * Added Data-structures to represent Z-Polyhedron
105 eg: Lattice, LatticeUnion, ZPolyhedron
107 * Deleted a few redundant macros:
112 * Deleted file "types_mp.h", as it is not required now.
114 * Comments added and modified wherever seemed appropriate.
118 * Changes in function prototype definitions to match with the changes
119 made in the file 'vector.c'.
121 (10) Addition of new header files
122 eg: Solvedio.h, Lattice.h, Matop.h, NormalForms.h and Zpolyhedron.h
126 * Changes in Makefile to match with the changes made in the library.
128 *******************************************************************************
130 Directory: ./ArithLib
132 (1) arithmetic_errors.h (copied from ./include/polylib/arithmetic_errors.h)
134 (2) arithmetique.h (copied from ./include/polylib/arithmetique.h)
136 (3) Deleted redundant files "arithmetique-local.h", "abs.c", "divide.c",
137 "doc.h", "exp.c", "io.c", "linear.h" "modulo.c", "pgcd.c", "pgcm.c".
139 *******************************************************************************
145 * Changes in local variable names in function declarations
147 (1) main : Value k -> int k
152 * Programming code changed from K&R C to ANSI C.
154 * Changes in parameter names or return type in function declarations
156 (1) Scan_Vertices : returned type changed to (Value*) from
159 * Changes in local variable names in function declarations
161 (1) cherche_min : j (added)
162 (2) Polyhedron_Preprocess : tmp, size_copy (added)
163 (3) Polyhedron_Preprocess2 : tmp1, tmp2 (added)
164 (4) old_Polyhedron_Preprocess : temp (deleted)
165 abs_a, abs_b, size_copy (added)
166 (5) count_points : result (added)
167 (5) P_Enum : temp (deleted)
168 tmp, lcm_copy (added)
169 (6) Enumerate_NoParametres : j, tmp (added)
170 (7) Polyhedron_Enumerate : i (added)
171 (8) main : i,str (added)
173 * Comments added wherever seemed appropriate.
175 * Changes in almost all the functions in order to make it generic and
176 allow handling of all the 'Value' types including GMP.
178 * Deleted file "ehrhart_mp.c" as it is not required now.
182 * Changes in parameter names or return type in function declarations
184 (1) compute_poly : return type changed to (Value *) from Value
186 * Changes in local variable names in function declarations
188 (1) in_domain : tmp (added)
189 (2) compute_poly : tmp (added)
191 * Changes in almost all the functions in order to make it generic and
192 allow handling of all the 'Value' types including GMP.
196 * Added file "example.c" in ./source directory.
198 * A few macro definitions removed:
199 eg: #include "types.h"
201 #include "vector.h", etc....
203 * A few macro definitions added:
204 eg: #include "polylib/polylib.h"
208 * Added file "Lattice.c" in ./source directory.
210 * Removed macro header definitions
211 eg: #include "types.h"
212 #include "ztypes.h" etc..
214 * Added macro header definitions
215 eg: #include <polylib/polylib.h>
217 * Changes in parameter names or return type in function declarations
220 * Changes in local variable names in function declarations
223 (1) AffineSmith : sum, quo, rem (added)
224 (2) LatticeDifference : int k -> Value k
225 (3) AddLattice : tmp (added)
226 (4) FindHermiteBasisofDomain : fact(added)
228 (5) LatticePreimage : tmp (added)
229 int divisor -> Value divisor
230 (6) Simplify : aux,k,fac, num, tmp, foobar (added)
232 (7) AffinePartSimplify : aux (added)
234 * Comments added wherever seemed appropriate.
236 * Changes in almost all the functions in order to make it generic and
237 allow handling of all the 'Value' types including GMP.
241 * Added file "Matop.c" in ./source directory.
243 * Removed macro header definitions
244 eg: #include "types.h"
245 #include "ztypes.h" etc..
247 * Added macro header definitions
248 eg: #include <polylib/polylib.h>
250 * Changes in parameter names or return type in function declarations
252 (1) Lcm : return type changed to (Value *) from (int)
256 * Changes in local variable names in function declarations
258 (1) Lcm : tmp, aux (added)
259 (2) ExchangeRows : int *temp -> Value *temp
260 (3) ExchangeColumns : int *temp -> Value *temp;
261 (4) isIntegral : int divisor -> Value divisor
263 (5) isinHnf : int rem -> Value rem
264 (6) PutRowLast : int *vector -> Value *vector
265 (7) PutRowFirst : int *vector -> Value *vector
266 (8) PutColumnFirst : int *vector -> Value *vector
267 (9) PutColumnLast : int *vector -> Value *vector
269 * Comments added wherever seemed appropriate.
271 * Changes in almost all the functions in order to make it generic and
272 allow handling of all the 'Value' types including GMP.
277 * Programming code changed from K&R C to ANSI C.
279 * A few functions added:
280 eg: int Matrix_Inverse(Matrix *Mat, Matrix *MatInv)
282 * Changes in parameter names or return type in function declarations
284 (1) MatInverse : M -> Mat
286 (2) Matrix_Vector_Product : mat -> Mat
287 (3) Vector_Matrix_Product : mat -> Mat
288 (4) Matrix_Product : mat1 -> Mat1
292 * Changes in local variable names in function declarations
294 (1) Matrix_Alloc : j (added)
295 (2) Matrix_Free : (i,j,p) (added)
296 (3) Matrix_Read_Input : str (added)
297 (4) hermite : aux (added)
300 (5) MatInverse : g -> gcd
302 li -> j, tmp (deleted)
303 (6) rat_prodmat : denom -> last column_index
307 d -> last_column_entry
308 s -> s1, s2(added), tmp (deleted)
309 (7) Matrix_Vector_Product : s (added)
310 (8) Vector_Matrix_Product : s (added)
311 (9) Matrix_Product : s (added)
313 * Error correction in code
316 if (value_zero_p(dcom)) -> if (value_one_p(dcom))
318 * Deleted file "matrix_mp.c", as it is not required now.
320 * Comments added wherever seemed appropriate.
322 * Changes in almost all the functions in order to make it generic and
323 allow handling of all the 'Value' types including GMP.
327 * Added file "NormalForms.c" in ./source directory.
329 * Programming code changed from K&R C to ANSI C.
331 * Removed macro header definitions
332 eg: #include "types.h"
333 #include "ztypes.h" etc..
335 * Added macro header definitions
336 eg: #include <polylib/polylib.h>
338 * Removed function: static int abs(int x)
340 * Changes in parameter names or return type in function declarations
342 (1) moins_l : int *a -> Value *a
343 (2) moins_c : int *a -> Value *a
344 (3) echange_l : int *a -> Value *a
345 (4) echange_c : int *a -> Value *a
346 (5) ligne : int *a -> Value *a
348 (6) colonne : int *a -> Value *a
350 (7) petit_l : int *a -> Value *a
351 (8) petit_c : int *a -> Value *a
352 (9) identite : int *a -> Value *a
353 (10) transpose: int *a -> Value *a
354 (11) encore : int *a -> Value *a
356 (12) smith : int *a -> Value *a
359 int *b_inverse -> Value *b_inverse
360 int *c_inverse -> Value *c_inverse
361 (13) hermite : int *a, -> Value *a
364 (14) ConvertpolMattoDarMat : return type changed to (Value *)
366 (15) ConvertDarMattoPolMat : int *A -> Value *A
369 * Changes in local variable names in function declarations
371 (1) moins_l : int *c -> Value *c
372 (2) moins_c : int *c -> Value *c
373 (3) echange_l : int s -> Value s
374 int *c1, *c2 -> Value *c1, *c2
375 (4) echange_c : int s -> Value s
376 int *c1, *c2 -> Value *c1, *c2
377 (5) ligne : int *c1, *c2 :-> Value *c1, *c2
379 (6) colonne : int *c1, *c2 -> Value *c1, *c2
381 (7) petit_l : int *c -> Value *c
382 int minus, comp -> Value minus, comp
383 (8) petit_c : int *c -> Value *c
384 int minus, comp -> Value minus, comp
385 (9) identite : int *b -> Value *b
386 (10) transpose : int *b, *c -> Value *b, *c
388 (11) encore : int *c -> Value *c
389 int comp -> Vale comp
391 (12) smith : int *f -> Value *f
392 int x, pivot -> Value x, pivot
394 (13) hermite : int *c1 -> Value *c1
395 int x, pivot -> Value x, pivot
397 (14) ConvertPolMattoDarMat : int *result -> Value *result
398 (15) Smith : int *a, *u, *v, *u_inv, *v_inv ->
399 Value *a, *u, *v, *u_inv, *v_inv
401 (16) Hermite : int *darte_matA -> Value *darte_matA
402 int *darte_identite -> Value *darte_identite
403 int *darte_id_inv -> Value *darte_id_inv
406 * Comments added wherever seemed appropriate.
408 * Changes in almost all the functions in order to make it generic and
409 allow handling of all the 'Value' types including GMP.
413 * Programming code changed from K&R C to ANSI C.
415 * A few function declarations removed.
416 eg: VVPd,IVPd,MPd (functions)
418 * A few function names changed.
420 SatVector_Or -> SatVector_OR
423 * A few functions added
425 (1) Stras_DomainSimplify(Pol1, Pol2, NbMaxRays)
426 (2) SimplifyEqualities(Pol1, Pol2, Filter)
428 * Changes in Macro definition
429 eg: bexchange(a,b,t,l) -> bexchange(a,b,l)
431 * Changes in parameter names in function declarations
433 (1) Combine : temp (deleted)
434 (2) RaySort : Temp1 (deleted), Temp2 (deleted)
435 (3) Gauss : temp (deleted)
436 (4) Rays2Polyhedron : NbMaxRays -> NbMaxConstrs
437 (5) BuildSat : NbCon -> NbConstraints
438 (6) AddConstraints : Con2 -> Con
439 NbCon2 -> NbConstraints
441 (7) AddPolyToDomain : p3 -> Pol
443 (8) SubConstraint : Con2 -> Con
445 (9) AddRays : Ray2 ->AddedRays
446 NbRay2 -> NbAddedRays
448 NbMaxRays -> NbMaxConstrs
449 (10) DomainAddRays : Pol1 -> Pol
451 NbMaxRays -> NbMaxConstrs
452 (11) DomainConvex : Pol1 -> Pol
453 NbMaxRays -> NbMaxConstrs
454 (12) align_context : D -> Pol
457 (13) Polyhedron_Scan : MAXRAYS -> NbMaxRays
458 (14) Polyhedron_Preimage : Pol1 -> Pol
459 (15) DomainPreimage : Pol1 -> Pol
460 (16) Polyhedron_Image : Pol1 -> Pol
461 NbMaxrays -> NbMaxConstrs
462 (17) DomainImage : Pol1 -> Pol
463 NbMaxRays -> NbMaxConstrs
464 (18) DomainCost : Pol1 -> Pol
465 (19) DomainAddConstraints : Pol1 -> Pol
468 * Changes in local variable names in function declarations
470 (1) Combine : a -> gcd
471 abs_a1,abs_a2,neg_a1 (added)
472 (2) TransformSat : nc2 -> sat_nbcolumns
474 (3) Chernikova : nc -> sat_nbcolumns
477 (4) Gauss : col_of_rank -> column_index
480 (5) Remove_Redundants : nc -> sat_nbcolumns
482 tmp1,tmp2,tmp3 (added)
484 (6) Polyhedron_Alloc : j (added)
485 (7) Polyhedron_Free : size,p,NbRows,NbColumns (added)
486 (8) Domain_Free : size,p,NbRows,NbColumns (added)
487 (9) Constraints2Polyhedron : nc -> nbcolumns
488 (10) Rays2Polyhedron: Sat -> SatTranspose
491 (11) BuildSat : nc -> nbcolumns
493 (12) AddConstraints : Pol -> NewPol
494 NbCon1, NbEle1 (deleted)
495 (13) PolyhedronIncludes : tmp (added)
496 (14) AddPolyToDomain : p3end -> p_domain_end
497 (15) SubConstraint : Pol -> NewPol
500 (16) AddRays : Pol -> NewPol
505 (17) FindSimple : tmp (added)
506 (18) SimplifyConstraints : notvid ->notempty
507 (19) SimplifyEqualities : temp (deleted)
508 (20) DomainSimplify : nc -> nbentries
512 (21) DomainConvex : Pol -> NewPol
514 (22) align_context : p1 -> q
516 (23) Polyhedron_Scan : dim2 (deleted)
519 (24) lower_upper_bounds : tmp (added)
520 (25) Polyhedron_Preimage : Pol2 -> NewPol
522 (26) DomainPreimage : p1 -> q
523 (27) Polyhedron_Image : Pol2 -> NewPol
525 (28) DomainImage : p1 -> q
526 (29) DomainCost : tmp1,tmp2,tmp3 (added)
528 * Error correction in code
531 column_index = (int *)malloc(Dimension*sizeof(Value)) ->
532 column_index = (int *)malloc(Dimension*sizeof(int))
535 if (PolyhedronIncludes(p2,p1)) -> if (PolyhedronIncludes(p2,p3))
537 (3) DomainAddConstraints:
538 if (PolyhedronIncludes(p2,p1)) -> if (PolyhedronIncludes(p2,p3))
540 * Comments added wherever seemed appropriate.
542 * Changes in almost all the functions in order to make it generic and
543 allow handling of all the 'Value' types including GMP.
547 * Programming code changed from K&R C to ANSI C.
549 * A few macro definitions removed.
550 eg: Vector_Init (deleted)
552 * A few function declarations removed.
555 * Changes in parametres names in function declarations
557 (1) TestRank : M -> Mat
559 (2) SMaAlloc : m -> matrix
560 (3) Poly2Sat : P -> Pol
561 (4) GenParamPolyhedron : poly -> Pol
562 (5) Param_Domain_Free : PP -> PD
564 * Changes in local variable names in function declarations
566 (1) TestRank : gcd (added)
567 (2) Poly2Sat : Tmp -> Temp
569 (3) Elim_Columns : tmp1, tmp2 (added)
570 (4) Polyhedron2Param_Vertices : res -> result
571 (5) Param_Vertices_Free : n -> next_pv
572 (6) Print_Vertex : t (deleted), tmp (added)
574 (7) Param_Vertices_Print : a -> poly
575 (8) Polyhedron2Param_Domain : res -> result
576 (9) Polyhedron2Param_SimplifiedDomain : res ->result
577 (10) Param_Domain_Free : n -> next_pd
579 * Error correction in code:
581 (1) PDomainIntersection :
582 Uncommented statement - Polyhedron_Free(p3);
584 * Comments added wherever seemed appropriate.
586 * Changes in almost all the functions in order to make it generic and
587 allow handling of all the 'Value' types including GMP.
591 * Programming code changed from K&R C to ANSI C.
593 * Changes in Macro definition
594 eg: bexchange(a,b,t,l) (deleted)
596 * Changes in parameter names or return type in function declarations
598 (1) exist_points : P -> Pol
599 (2) PolyhedronLTQ : P1 -> Pol1
601 MAXRAYS -> NbMaxConstrs
602 (3) GaussSimplify : M -> Mat1
605 * Changes in local variable names or types in function declarations
607 (1) exist_points : tmp (added)
608 (2) Polyhedron_Not_Empty : i (added)
609 (3) PolyhedronLTQ : M -> Mat
610 (4) GaussSimplify : col_of_rank :-> column_index
612 temp,RowSize (deleted)
614 * Error correction in code:
617 if(value_gt(gcd,int_to_value(2))) -> if(value_ge(...))
619 * Comments added wherever seemed appropriate.
621 * Changes in almost all the functions in order to make it generic and
622 allow handling of all the 'Value' types including GMP.
626 * Added file "SolveDio.c" in ./source directory.
628 * Removed macro header definitions
629 eg: #include "types.h"
630 #include "ztypes.h" etc..
632 * Added macro header definitions
633 eg: #include <polylib/polylib.h>
635 * Changes in local variable names or types in function declarations
637 (1) SolveDiophantine : int *C -> Value *C
642 * Comments added wherever seemed appropriate.
644 * Changes in almost all the functions in order to make it generic and
645 allow handling of all the 'Value' types including GMP.
649 * Programming code changed from K&R C to ANSI C.
652 eg: void Vector_Copy(Value *,Value *,unsigned)
653 void Vector_Exchange(Value *,Value *,unsigned)
655 * Changes in parameter names or return type in function declarations
657 (1) Factorial : return type changed to (Value *) from (Value)
658 (2) Binomial : return type changed to (Value *) from (Value)
659 (3) CNP : return type changed to (Value *) from (Value)
660 (4) GCD : return type changed to (Value *) from (Value)
661 (5) Vector_Free : vec -> vector
662 (6) Vector_Print : vec -> vector
663 (7) Vector_Set : Value n -> int n
664 (8) Inner_Product : return type changed to (Value *) from
666 (9) Vector_Max : return type changed to (Value *) from (Value)
667 (10) Vector_Min : return type changed to (Value *) from (Value)
668 (11) Vector_Min_Not_Zero : return type changed to (Value *)
670 (12) Vector_Gcd : return type changed to (Value *) from (Value)
672 (13) Vector_Map : Value (*f)() -> Value *(*f)()
673 (14) Vector_Normalize : q (deleted)
674 (15) Vector_Normalize_Positive : tmp (deleted)
675 (16) Vector_Reduce : return type changed to (Value *) from
677 Value (*f)() -> Value *(*f)()
678 (17) Vector_Sort : Vecv -> vector
680 * Changes in local variable names or types in function declarations
682 (1) Factorial : Value fact -> Value *fact
684 (2) Binomial : Value prod -> Value *result
685 f (deleted), tmp (added)
686 (3) CNP : Value c -> Value *result
688 (4) GCD : Value aux -> Value *result
690 (5) Vector_Alloc : vec -> vector
692 (6) Vector_Free : i (added)
693 (7) Vector_Read : vec -> vector
695 (8) Inner_Product : Value ip -> Value *ip
697 (9) Vector_Max : Value max -> Value *max
698 (10) Vector_Min : Value min -> Value *min
699 (11) Vector_Min_Not_Zero : Value min -> Value *min
701 (12) Vector_Gcd : Value min -> Value *min
703 (13) Vector_Normalize : Value gcd -> Value *gcd
705 (14) Vector_Normalize_positive : Value g -> Value *gcd
706 (15) Vector_Reduce : Value r -> Value *r
708 * Comments added wherever seemed appropriate.
710 * Changes in almost all the functions in order to make it generic and
711 allow handling of all the 'Value' types including GMP.
715 * Changes in local variable names or types in function declarations
717 (1) check_poly : Value k -> int k
719 (2) main : tmp (added)
721 * Changes in almost all the functions in order to make it generic and
722 allow handling of all the 'Value' types including GMP.
724 (15) Zpolyhedron.c ->
726 * Added file "Zpolyhderon.c" in ./source directory.
728 * A few macro definitions removed:
729 eg: #include "types.h"
731 #include "vector.h", etc....
733 * A few macro definitions added:
734 eg: #include "polylib/polylib.h"
736 * Changes in local variable names or types in function declarations
738 (1) CanonicalForm : tmp (added)
740 * Comments added wherever seemed appropriate.
742 * Changes in almost all the functions in order to make it generic and
743 allow handling of all the 'Value' types including GMP.
747 * Added file "Zpolytest.c" in ./source directory.
749 * A few macro definitions removed:
750 eg: #include "types.h"
752 #include "vector.h", etc....
754 * A few macro definitions added:
755 eg: #include "polylib/polylib.h"
757 *******************************************************************************