#include <assert.h>
#include <polylib/polylib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

Classes
struct	SatMatrix

Macros
#define	WSIZE (8 * sizeof(int))

#define	bexchange(a, b, l)

#define	exchange(a, b, t)

#define	SMVector_Copy(p1, p2, length) memcpy((char )(p2), (char )(p1), (int)((length) * sizeof(int)))

#define	SMVector_Init(p1, length) memset((char )(p1), 0, (int)((length) sizeof(int)))

Functions
void	errormsg1 (const char f, const char msgname, const char *msg)

static SatMatrix *	SMAlloc (int rows, int cols)

static void	SMFree (SatMatrix **matrix)

static void	SatVector_OR (int p1, int p2, int *p3, unsigned length)

static void	Combine (Value p1, Value p2, Value *p3, int pos, unsigned length)

static SatMatrix *	TransformSat (Matrix Mat, Matrix Ray, SatMatrix *Sat)

static void	RaySort (Matrix Ray, SatMatrix Sat, int NbBid, int NbRay, int equal_bound, int sup_bound, unsigned RowSize1, unsigned RowSize2, unsigned bx, unsigned jx)

static void	SatMatrix_Extend (SatMatrix *Sat, unsigned rows, unsigned cols)

static int	Chernikova (Matrix Mat, Matrix Ray, SatMatrix *Sat, unsigned NbBid, unsigned NbMaxRays, unsigned FirstConstraint, unsigned dual)

static int	Gauss4 (Value **p, int NbEq, int NbRows, int Dimension)

int	Gauss (Matrix *Mat, int NbEq, int Dimension)

static Polyhedron *	Remove_Redundants (Matrix Mat, Matrix Ray, SatMatrix Sat, unsigned Filter)

Polyhedron *	Polyhedron_Alloc (unsigned Dimension, unsigned NbConstraints, unsigned NbRays)

void	Polyhedron_Free (Polyhedron *Pol)

void	Domain_Free (Polyhedron *Pol)

void	Polyhedron_Print (FILE Dst, const char Format, const Polyhedron *Pol)

void	PolyPrint (Polyhedron *Pol)

Polyhedron *	Empty_Polyhedron (unsigned Dimension)

Polyhedron *	Universe_Polyhedron (unsigned Dimension)

static void	SortConstraints (Matrix *Constraints, unsigned NbEq)

static int	ImplicitEqualities (Matrix *Constraints, unsigned NbEq)

Polyhedron *	Constraints2Polyhedron (Matrix *Constraints, unsigned NbMaxRays)
	Given a matrix of constraints ('Constraints'), construct and return a polyhedron. More...

Matrix *	Polyhedron2Constraints (Polyhedron *Pol)

Polyhedron *	Rays2Polyhedron (Matrix *Ray, unsigned NbMaxConstrs)
	Given a matrix of rays 'Ray', create and return a polyhedron. More...

void	Polyhedron_Compute_Dual (Polyhedron *P)

static SatMatrix *	BuildSat (Matrix Mat, Matrix Ray, unsigned NbConstraints, unsigned NbMaxRays)

Polyhedron *	AddConstraints (Value Con, unsigned NbConstraints, Polyhedron Pol, unsigned NbMaxRays)

int	PolyhedronIncludes (Polyhedron Pol1, Polyhedron Pol2)

Polyhedron *	AddPolyToDomain (Polyhedron Pol, Polyhedron PolDomain)

Polyhedron *	SubConstraint (Value Con, Polyhedron Pol, unsigned NbMaxRays, int Pass)

Polyhedron *	DomainIntersection (Polyhedron Pol1, Polyhedron Pol2, unsigned NbMaxRays)

Matrix *	Polyhedron2Rays (Polyhedron *Pol)
	Given a polyhedron 'Pol', return a matrix of rays. More...

Polyhedron *	AddRays (Value AddedRays, unsigned NbAddedRays, Polyhedron Pol, unsigned NbMaxConstrs)
	Add 'NbAddedRays' rays to polyhedron 'Pol'. More...

Polyhedron *	DomainAddRays (Polyhedron Pol, Matrix Ray, unsigned NbMaxConstrs)
	Add rays pointed by 'Ray' to each and every polyhedron in the polyhedral domain 'Pol'. More...

Polyhedron *	Polyhedron_Copy (Polyhedron *Pol)

Polyhedron *	Domain_Copy (Polyhedron *Pol)

static void	addToFilter (int k, unsigned Filter, SatMatrix Sat, int tmpR, int tmpC, int NbRays, int NbConstraints)

static void	FindSimple (Polyhedron P1, Polyhedron P2, unsigned *Filter, unsigned NbMaxRays)

static int	SimplifyConstraints (Polyhedron Pol1, Polyhedron Pol2, unsigned *Filter, unsigned NbMaxRays)

static void	SimplifyEqualities (Polyhedron Pol1, Polyhedron Pol2, unsigned *Filter)

Polyhedron *	DomainSimplify (Polyhedron Pol1, Polyhedron Pol2, unsigned NbMaxRays)

Polyhedron *	Stras_DomainSimplify (Polyhedron Pol1, Polyhedron Pol2, unsigned NbMaxRays)

Polyhedron *	DomainUnion (Polyhedron Pol1, Polyhedron Pol2, unsigned NbMaxRays)

Polyhedron *	DomainConvex (Polyhedron *Pol, unsigned NbMaxConstrs)

Polyhedron *	DomainDifference (Polyhedron Pol1, Polyhedron Pol2, unsigned NbMaxRays)

Polyhedron *	align_context (Polyhedron *Pol, int align_dimension, int NbMaxRays)

Polyhedron *	Polyhedron_Scan (Polyhedron D, Polyhedron C, unsigned NbMaxRays)

int	lower_upper_bounds (int pos, Polyhedron P, Value context, Value LBp, Value UBp)

static void	Rays_Mult (Value *A, Matrix B, Value **C, unsigned NbRays)

static void	Rays_Mult_Transpose (Value *A, Matrix B, Value **C, unsigned NbRays)

Polyhedron *	Polyhedron_Preimage (Polyhedron Pol, Matrix Func, unsigned NbMaxRays)

Polyhedron *	DomainPreimage (Polyhedron Pol, Matrix Func, unsigned NbMaxRays)

Polyhedron *	Polyhedron_Image (Polyhedron Pol, Matrix Func, unsigned NbMaxConstrs)

Polyhedron *	DomainImage (Polyhedron Pol, Matrix Func, unsigned NbMaxConstrs)

Interval *	DomainCost (Polyhedron Pol, Value Cost)

Polyhedron *	DomainAddConstraints (Polyhedron Pol, Matrix Mat, unsigned NbMaxRays)

Polyhedron *	Disjoint_Domain (Polyhedron *P, int flag, unsigned NbMaxRays)

void	Polyhedron_PrintConstraints (FILE Dst, const char Format, Polyhedron *Pol)

void	Domain_PrintConstraints (FILE Dst, const char Format, Polyhedron *Pol)

static Polyhedron *	p_simplify_constraints (Polyhedron P, Vector row, Value *g, unsigned MaxRays)

Polyhedron *	DomainConstraintSimplify (Polyhedron *P, unsigned MaxRays)

void	polylib_close ()
	Free all cache allocated memory: call this function before exiting in a memory checker environment like valgrind. More...

Variables
int	Pol_status

Macro Definition Documentation

◆ bexchange

#define bexchange	(	a,
		b,
		l
	)

Value:

  {                                                                          \
    for(int _i = 0; _i < (l); _i++) {                                        \
      char _c;                                                               \
      _c = *((char *)(a) + _i);                                              \
      *((char *)(a) + _i) = *((char *)(b) + _i);                             \
      *((char *)(b) + _i) = _c;                                              \
    }                                                                        \
  }

Definition at line 50 of file polyhedron.c.

◆ exchange

#define exchange	(	a,
		b,
		t
	)

Value:

  {                                                                          \
    (t) = (a);                                                               \
    (a) = (b);                                                               \
    (b) = (t);                                                               \
  }

Definition at line 60 of file polyhedron.c.

◆ SMVector_Copy

#define SMVector_Copy	(	p1,
		p2,
		length
	)	memcpy((char )(p2), (char )(p1), (int)((length) * sizeof(int)))

Definition at line 186 of file polyhedron.c.

◆ SMVector_Init

#define SMVector_Init	(	p1,
		length
	)	memset((char )(p1), 0, (int)((length) sizeof(int)))

Definition at line 192 of file polyhedron.c.

◆ WSIZE

#define WSIZE (8 * sizeof(int))

Definition at line 48 of file polyhedron.c.

Function Documentation

◆ AddConstraints()

Polyhedron * AddConstraints	(	Value *	Con,
		unsigned	NbConstraints,
		Polyhedron *	Pol,
		unsigned	NbMaxRays
	)

Definition at line 2311 of file polyhedron.c.

References any_exception_error, BuildSat(), CATCH, Chernikova(), polyhedron::Constraint, Constraints2Polyhedron(), polyhedron::Dimension, errormsg1(), Matrix_Alloc(), Matrix_Free(), polyhedron::NbBid, polyhedron::NbConstraints, polyhedron::NbRays, matrix::p, POL_ENSURE_INEQUALITIES, POL_ENSURE_VERTICES, POL_ISSET, POL_NO_DUAL, Pol_status, Polyhedron_Copy(), Polyhedron_Free(), polyhedron::Ray, Remove_Redundants(), RETHROW, Sat, SMFree(), TRY, UNCATCH, and Vector_Copy().

Referenced by Add_CEqualities(), Disjoint_Domain(), Domain_Remove_Integer_Empty(), DomainAddConstraints(), DomainIntersection(), FindSimple(), old_Polyhedron_Preprocess(), p_simplify_constraints(), PDomainIntersection(), polyhedron_dark_source(), Polyhedron_Image_Enumerate(), PolyhedronLTQ(), and sLBLIntersection().

◆ AddPolyToDomain()

Polyhedron * AddPolyToDomain	(	Polyhedron *	Pol,
		Polyhedron *	PolDomain
	)

Definition at line 2460 of file polyhedron.c.

References emptyQ, polyhedron::next, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, Polyhedron_Free(), and PolyhedronIncludes().

Referenced by CanonicalLBL(), Disjoint_Domain(), domain_dark_shadow(), DomainDifference(), DomainImage(), DomainIntersection(), DomainPreimage(), DomainSimplify(), PDomainDifference(), PDomainIntersection(), Polyhedron_Image_Enumerate(), Scan_RestAP(), sLBLCompute_holes(), sLBLIntersection(), and Stras_DomainSimplify().

◆ AddRays()

Polyhedron * AddRays	(	Value *	AddedRays,
		unsigned	NbAddedRays,
		Polyhedron *	Pol,
		unsigned	NbMaxConstrs
	)

Add 'NbAddedRays' rays to polyhedron 'Pol'.

Rays are pointed by 'AddedRays' and the maximum allowed constraints in the new polyhedron is 'NbMaxConstrs'.

Definition at line 2707 of file polyhedron.c.

References any_exception_error, BuildSat(), CATCH, Chernikova(), polyhedron::Constraint, polyhedron::Dimension, errormsg1(), Matrix_Alloc(), Matrix_Free(), polyhedron::NbConstraints, polyhedron::NbEq, polyhedron::NbRays, matrix::NbRows, matrix::p_Init, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, POL_ISSET, POL_NO_DUAL, Pol_status, Polyhedron_Free(), polyhedron::Ray, Remove_Redundants(), RETHROW, Sat, SMFree(), TransformSat(), TRY, UNCATCH, and Vector_Copy().

Referenced by DomainAddRays(), DomainConvex(), and PolyhedronLTQ().

◆ addToFilter()

static void addToFilter	(	int	k,
		unsigned *	Filter,
		SatMatrix *	Sat,
		int *	tmpR,
		int *	tmpC,
		int	NbRays,
		int	NbConstraints
	)

static

Definition at line 2918 of file polyhedron.c.

References MSB, NEXT, SatMatrix::p, Sat, and WSIZE.

Referenced by FindSimple().

◆ align_context()

Polyhedron * align_context	(	Polyhedron *	Pol,
		int	align_dimension,
		int	NbMaxRays
	)

Definition at line 3704 of file polyhedron.c.

References any_exception_error, CATCH, polyhedron::Constraint, polyhedron::Dimension, Domain_Copy(), Domain_Free(), errormsg1(), F_ISSET, polyhedron::flags, polyhedron::NbBid, polyhedron::NbConstraints, polyhedron::NbEq, polyhedron::NbRays, polyhedron::next, POL_INEQUALITIES, POL_POINTS, POL_VALID, Polyhedron_Alloc(), Polyhedron_Free(), polyhedron::Ray, RETHROW, TRY, UNCATCH, value_assign, value_set_si, and Vector_Copy().

Referenced by Find_m_faces(), main(), Polyhedron_Scan(), sLBLIntersection(), sLBLPreimage(), test_Constraints_Remove_parm_eqs(), and test_Polyhedron_Remove_parm_eqs().

◆ BuildSat()

static SatMatrix * BuildSat	(	Matrix *	Mat,
		Matrix *	Ray,
		unsigned	NbConstraints,
		unsigned	NbMaxRays
	)

static

Definition at line 2251 of file polyhedron.c.

References any_exception_error, CATCH, MSB, matrix::NbColumns, matrix::NbRows, SatMatrix::NbRows, NEXT, matrix::p, SatMatrix::p, SatMatrix::p_init, RETHROW, Sat, SMAlloc(), SMFree(), SMVector_Init, TRY, UNCATCH, value_addmul, value_notzero_p, and value_set_si.

Referenced by AddConstraints(), AddRays(), SimplifyConstraints(), and SubConstraint().

◆ Chernikova()

static int Chernikova	(	Matrix *	Mat,
		Matrix *	Ray,
		SatMatrix *	Sat,
		unsigned	NbBid,
		unsigned	NbMaxRays,
		unsigned	FirstConstraint,
		unsigned	dual
	)

static

Definition at line 392 of file polyhedron.c.

References any_exception_error, CATCH, Combine(), errormsg1(), m, Matrix_Extend(), Matrix_Print(), MSB, matrix::NbColumns, SatMatrix::NbColumns, matrix::NbRows, SatMatrix::NbRows, NEXT, matrix::p, SatMatrix::p, P_VALUE_FMT, RaySort(), RETHROW, Sat, SatMatrix_Extend(), SatVector_OR(), SMVector_Copy, TRY, UNCATCH, value_addmul, value_multiply, value_neg_p, value_notzero_p, value_oppose, value_print, value_zero_p, Vector_Copy(), Vector_Exchange(), and WSIZE.

Referenced by AddConstraints(), AddRays(), Constraints2Polyhedron(), Rays2Polyhedron(), SimplifyConstraints(), and SubConstraint().

◆ Combine()

static void Combine	(	Value *	p1,
		Value *	p2,
		Value *	p3,
		int	pos,
		unsigned	length
	)

static

Definition at line 205 of file polyhedron.c.

References value_absolute, value_assign, value_clear, value_divexact, value_gcd, value_init, value_oppose, Vector_Combine(), and Vector_Normalize().

Referenced by Chernikova(), and Gauss4().

◆ Constraints2Polyhedron()

Polyhedron * Constraints2Polyhedron	(	Matrix *	Constraints,
		unsigned	NbMaxRays
	)

Given a matrix of constraints ('Constraints'), construct and return a polyhedron.

Parameters

Constraints	Constraints (may be modified!)
NbMaxRays	Estimated number of rays in the ray matrix of the polyhedron.

Returns: newly allocated Polyhedron

Definition at line 1912 of file polyhedron.c.

References any_exception_error, CATCH, Chernikova(), polyhedron::Constraint, ConstraintSimplify(), Empty_Polyhedron(), errormsg1(), ExchangeRows(), F_SET, First_Non_Zero(), Gauss(), ImplicitEqualities(), Matrix_Alloc(), Matrix_Free(), Matrix_Print(), matrix::NbColumns, polyhedron::NbEq, matrix::NbRows, SatMatrix::NbRows, matrix::p, matrix::p_Init, SatMatrix::p_init, POL_INEQUALITIES, POL_INTEGER, POL_ISSET, POL_NO_DUAL, POL_VALID, Polyhedron_Alloc(), Polyhedron_Free(), Polyhedron_Print(), polyhedron::Ray, Remove_Redundants(), RETHROW, Sat, SMAlloc(), SMFree(), SMVector_Init, SortConstraints(), TRY, UNCATCH, Universe_Polyhedron(), value_clear, value_init, value_notzero_p, value_set_si, value_zero_p, Vector_Copy(), and Vector_Set().

Referenced by AddConstraints(), dehomogenize_polyhedron(), DomainSimplify(), Ehrhart_Quick_Apx(), Elim_Columns(), eliminable_vars(), Enumeration_zero(), Find_m_faces(), homogenize(), LexSmaller(), main(), Param_Vertices_Print(), Polyhedron_Compute_Dual(), Polyhedron_Preimage(), Polyhedron_Preprocess(), Polyhedron_Preprocess2(), Polyhedron_Remove_parm_eqs(), Recession_Cone(), Stras_DomainSimplify(), test_Constraints_fullDimensionize(), test_Constraints_Remove_parm_eqs(), test_Polyhedron_Remove_parm_eqs(), and Union_Read().

◆ Disjoint_Domain()

Polyhedron * Disjoint_Domain	(	Polyhedron *	P,
		int	flag,
		unsigned	NbMaxRays
	)

Definition at line 4503 of file polyhedron.c.

References AddConstraints(), AddPolyToDomain(), polyhedron::Constraint, Domain_Free(), emptyQ, errormsg1(), polyhedron::NbConstraints, polyhedron::next, Polyhedron_Copy(), Polyhedron_Free(), SubConstraint(), and value_zero_p.

Referenced by Domain_Enumerate(), main(), and sLBLCompute_holes().

◆ Domain_Copy()

Polyhedron * Domain_Copy ( Polyhedron * Pol )

Definition at line 2878 of file polyhedron.c.

References Domain_Copy(), polyhedron::next, and Polyhedron_Copy().

Referenced by align_context(), Domain_Copy(), DomainAddRays(), DomainDifference(), DomainUnion(), and LBLAlloc().

◆ Domain_Free()

void Domain_Free ( Polyhedron * Pol )

Definition at line 1633 of file polyhedron.c.

References polyhedron::next, and Polyhedron_Free().

Referenced by Add_CEqualities(), align_context(), Compute_PDomains(), Disjoint_Domain(), Domain_Enumerate(), Domain_Remove_Integer_Empty(), DomainDifference(), Ehrhart_Quick_Apx_Full_Dim(), Enumerate_NoParameters(), Enumeration_Free(), Find_m_faces(), LBL_Remove_Empty(), LBL_simple_inclusion_check(), LBLSimplify(), main(), Param_Domain_Free(), Param_Vertices_Print(), PDomainDifference(), Polyhedron_Enumerate(), Polyhedron_LexSmallerEnumerate(), Polyhedron_Not_Empty(), Polyhedron_Preprocess(), Polyhedron_Scan(), PolyhedronLTQ(), sLBL2ZDomain(), sLBL_Lat_Normalize(), sLBL_Simplify_Zero_Dimensions(), sLBLCanonical(), sLBLComplement(), sLBLComplement2(), sLBLCompute_holes(), sLBLFree(), sLBLIntersection(), sLBLMake_lattice_equal_to(), sLBLPreimage(), and sLBLSimplify_equalities().

◆ Domain_PrintConstraints()

void Domain_PrintConstraints	(	FILE *	Dst,
		const char *	Format,
		Polyhedron *	Pol
	)

Definition at line 4715 of file polyhedron.c.

References polyhedron::next, and Polyhedron_PrintConstraints().

◆ DomainAddConstraints()

Polyhedron * DomainAddConstraints	(	Polyhedron *	Pol,
		Matrix *	Mat,
		unsigned	NbMaxRays
	)

Definition at line 4448 of file polyhedron.c.

References AddConstraints(), polyhedron::Dimension, errormsg1(), matrix::NbColumns, matrix::NbRows, polyhedron::next, matrix::p_Init, Polyhedron_Free(), and PolyhedronIncludes().

Referenced by sLBLMake_lattice_equal_to(), and sLBLPreimage().

◆ DomainAddRays()

Polyhedron * DomainAddRays	(	Polyhedron *	Pol,
		Matrix *	Ray,
		unsigned	NbMaxConstrs
	)

Add rays pointed by 'Ray' to each and every polyhedron in the polyhedral domain 'Pol'.

'NbMaxConstrs' is maximum allowed constraints in the constraint set of a polyhedron.

Definition at line 2805 of file polyhedron.c.

References AddRays(), polyhedron::Dimension, Domain_Copy(), errormsg1(), matrix::NbColumns, matrix::NbRows, polyhedron::next, matrix::p, Polyhedron_Free(), and PolyhedronIncludes().

Referenced by domain_project(), Find_m_faces(), Polyhedron_Scan(), and sLBLCompute_holes().

◆ DomainConstraintSimplify()

Polyhedron * DomainConstraintSimplify	(	Polyhedron *	P,
		unsigned	MaxRays
	)

Definition at line 4760 of file polyhedron.c.

References polyhedron::Dimension, emptyQ, polyhedron::next, Vector::p, p_simplify_constraints(), Polyhedron_Free(), value_clear, value_init, value_set_si, Vector_Alloc(), and Vector_Free().

Referenced by LBLSimplify(), sLBL_Simplify_Zero_Dimensions(), sLBLCanonical(), and sLBLCompute_holes().

◆ DomainConvex()

Polyhedron * DomainConvex	(	Polyhedron *	Pol,
		unsigned	NbMaxConstrs
	)

Definition at line 3606 of file polyhedron.c.

References AddRays(), any_exception_error, CATCH, polyhedron::NbRays, polyhedron::next, POL_ENSURE_VERTICES, Polyhedron_Copy(), Polyhedron_Free(), polyhedron::Ray, RETHROW, TRY, and UNCATCH.

Referenced by Compute_PDomains(), and main().

◆ DomainCost()

Interval * DomainCost	(	Polyhedron *	Pol,
		Value *	Cost
	)

Definition at line 4303 of file polyhedron.c.

References any_exception_error, CATCH, polyhedron::Dimension, errormsg1(), interval::MaxD, interval::MaxI, interval::MaxN, interval::MinD, interval::MinI, interval::MinN, polyhedron::NbRays, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, polyhedron::Ray, RETHROW, TRY, UNCATCH, value_addto, value_assign, value_clear, value_eq, value_gt, value_init, value_lt, value_multiply, value_ne, value_oppose, value_set_si, and value_zero_p.

◆ DomainDifference()

Polyhedron * DomainDifference	(	Polyhedron *	Pol1,
		Polyhedron *	Pol2,
		unsigned	NbMaxRays
	)

Definition at line 3641 of file polyhedron.c.

References AddPolyToDomain(), polyhedron::Constraint, polyhedron::Dimension, Domain_Copy(), Domain_Free(), Empty_Polyhedron(), emptyQ, errormsg1(), polyhedron::NbConstraints, polyhedron::next, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, Polyhedron_Copy(), SubConstraint(), and value_notzero_p.

Referenced by Domain_Enumerate(), LBL_simple_inclusion_check(), sLBL2ZDomain(), sLBL_Simplify_Zero_Dimensions(), sLBLComplement(), sLBLComplement2(), and sLBLCompute_holes().

◆ DomainImage()

Polyhedron * DomainImage	(	Polyhedron *	Pol,
		Matrix *	Func,
		unsigned	NbMaxConstrs
	)

Definition at line 4266 of file polyhedron.c.

References AddPolyToDomain(), any_exception_error, CATCH, polyhedron::next, Polyhedron_Free(), Polyhedron_Image(), RETHROW, TRY, and UNCATCH.

Referenced by Polyhedron_Image_Enumerate(), sLBLComplement(), and sLBLIntersection().

◆ DomainIntersection()

Polyhedron * DomainIntersection	(	Polyhedron *	Pol1,
		Polyhedron *	Pol2,
		unsigned	NbMaxRays
	)

Definition at line 2648 of file polyhedron.c.

References AddConstraints(), AddPolyToDomain(), polyhedron::Constraint, polyhedron::Dimension, Empty_Polyhedron(), errormsg1(), polyhedron::NbConstraints, and polyhedron::next.

Referenced by Domain_Enumerate(), Ehrhart_Quick_Apx_Full_Dim(), Enumerate_NoParameters(), Find_m_faces(), main(), Polyhedron_Enumerate(), Polyhedron_Scan(), PolyhedronLTQ(), sLBLCompute_holes(), sLBLIntersection(), test_Constraints_Remove_parm_eqs(), and test_Polyhedron_Remove_parm_eqs().

◆ DomainPreimage()

Polyhedron * DomainPreimage	(	Polyhedron *	Pol,
		Matrix *	Func,
		unsigned	NbMaxRays
	)

Definition at line 4138 of file polyhedron.c.

References AddPolyToDomain(), any_exception_error, CATCH, polyhedron::next, Polyhedron_Free(), Polyhedron_Preimage(), RETHROW, TRY, and UNCATCH.

Referenced by sLBL_Lat_Normalize(), sLBLIntersection(), and sLBLSimplify_equalities().

◆ DomainSimplify()

Polyhedron * DomainSimplify	(	Polyhedron *	Pol1,
		Polyhedron *	Pol2,
		unsigned	NbMaxRays
	)

Definition at line 3291 of file polyhedron.c.

References AddPolyToDomain(), polyhedron::Constraint, Constraints2Polyhedron(), polyhedron::Dimension, Empty_Polyhedron(), emptyQ, errormsg1(), Matrix_Alloc(), Matrix_Free(), MSB, polyhedron::NbConstraints, matrix::NbRows, NEXT, polyhedron::next, matrix::p, POL_ENSURE_VERTICES, Pol_status, SimplifyConstraints(), SimplifyEqualities(), SMVector_Init, and Vector_Copy().

Referenced by Ehrhart_Quick_Apx_Full_Dim(), Find_m_faces(), main(), Polyhedron_Enumerate(), and Polyhedron_Scan().

◆ DomainUnion()

Polyhedron * DomainUnion	(	Polyhedron *	Pol1,
		Polyhedron *	Pol2,
		unsigned	NbMaxRays
	)

Definition at line 3530 of file polyhedron.c.

References polyhedron::Dimension, Domain_Copy(), errormsg1(), polyhedron::next, Polyhedron_Copy(), and PolyhedronIncludes().

Referenced by DMUnion(), LBLSimplify(), and main().

◆ Empty_Polyhedron()

Polyhedron * Empty_Polyhedron ( unsigned Dimension )

Definition at line 1728 of file polyhedron.c.

References polyhedron::Constraint, errormsg1(), F_SET, polyhedron::NbBid, polyhedron::NbEq, POL_FACETS, POL_INEQUALITIES, POL_POINTS, POL_VALID, POL_VERTICES, Polyhedron_Alloc(), value_set_si, and Vector_Set().

Referenced by Constraints2Polyhedron(), DomainDifference(), DomainIntersection(), DomainSimplify(), p_simplify_constraints(), Polyhedron_Image(), Polyhedron_Preimage(), Rays2Polyhedron(), Remove_Redundants(), and Stras_DomainSimplify().

◆ errormsg1()

void errormsg1	(	const char *	f,
		const char *	msgname,
		const char *	msg
	)

◆ FindSimple()

static void FindSimple	(	Polyhedron *	P1,
		Polyhedron *	P2,
		unsigned *	Filter,
		unsigned	NbMaxRays
	)

static

Definition at line 2963 of file polyhedron.c.

References AddConstraints(), addToFilter(), any_exception_error, CATCH, polyhedron::Constraint, polyhedron::Dimension, emptyQ, errormsg1(), Inner_Product(), Matrix_Alloc(), Matrix_Free(), MSB, polyhedron::NbConstraints, polyhedron::NbRays, matrix::NbRows, NEXT, matrix::p, SatMatrix::p, matrix::p_Init, SatMatrix::p_init, Polyhedron_Copy(), Polyhedron_Free(), polyhedron::Ray, RETHROW, Sat, SatMatrix_Extend(), SMAlloc(), SMFree(), SMVector_Init, TRY, UNCATCH, value_clear, value_init, value_notzero_p, value_pos_p, value_zero_p, and Vector_Copy().

Referenced by SimplifyConstraints().

◆ Gauss()

int Gauss	(	Matrix *	Mat,
		int	NbEq,
		int	Dimension
	)

Definition at line 834 of file polyhedron.c.

References Gauss4(), Matrix_Print(), matrix::NbRows, and matrix::p.

Referenced by Constraints2Polyhedron(), P_Enum(), Remove_Redundants(), and SimplifyEqualities().

◆ Gauss4()

static int Gauss4	(	Value **	p,
		int	NbEq,
		int	NbRows,
		int	Dimension
	)

static

Definition at line 740 of file polyhedron.c.

References any_exception_error, CATCH, Combine(), errormsg1(), RETHROW, TRY, UNCATCH, value_clear, value_cmp_si, value_init, value_neg_p, value_notzero_p, Vector_AntiScale(), Vector_Exchange(), Vector_Gcd(), and Vector_Oppose().

Referenced by Gauss(), and Polyhedron_Image().

◆ ImplicitEqualities()

static int ImplicitEqualities	(	Matrix *	Constraints,
		unsigned	NbEq
	)

static

Definition at line 1843 of file polyhedron.c.

References First_Non_Zero(), matrix::NbColumns, matrix::NbRows, matrix::p, value_abs_ne, value_addto, value_clear, value_eq, value_init, value_neg_p, value_pos_p, value_set_si, value_sign, value_zero_p, and Vector_Set().

Referenced by Constraints2Polyhedron().

◆ lower_upper_bounds()

int lower_upper_bounds	(	int	pos,
		Polyhedron *	P,
		Value *	context,
		Value *	LBp,
		Value *	UBp
	)

Definition at line 3859 of file polyhedron.c.

References polyhedron::Constraint, polyhedron::Dimension, Inner_Product(), LB_INFINITY, n, polyhedron::NbConstraints, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, UB_INFINITY, value_add_int, value_addto, value_assign, value_clear, value_division, value_gt, value_init, value_lt, value_modulus, value_neg_p, value_notzero_p, value_oppose, value_pos_p, value_set_si, value_sub_int, and value_zero_p.

Referenced by cherche_min(), count_points(), exist_points(), P_Enum(), polyhedron_int_solution(), and Scan_RestAP().

◆ p_simplify_constraints()

static Polyhedron * p_simplify_constraints	(	Polyhedron *	P,
		Vector *	row,
		Value *	g,
		unsigned	MaxRays
	)

static

Definition at line 4721 of file polyhedron.c.

References AddConstraints(), polyhedron::Constraint, ConstraintSimplify(), polyhedron::Dimension, Empty_Polyhedron(), F_CLR, polyhedron::NbConstraints, Vector::p, POL_FACETS, POL_ISSET, POL_NO_DUAL, POL_POINTS, POL_VERTICES, Polyhedron_Copy(), Polyhedron_Free(), value_zero_p, and Vector_Copy().

Referenced by DomainConstraintSimplify().

◆ Polyhedron2Constraints()

Matrix * Polyhedron2Constraints ( Polyhedron * Pol )

Definition at line 2067 of file polyhedron.c.

References polyhedron::Constraint, polyhedron::Dimension, errormsg1(), Matrix_Alloc(), polyhedron::NbConstraints, matrix::p_Init, POL_ENSURE_INEQUALITIES, and Vector_Copy().

Referenced by dehomogenize_polyhedron(), Elim_Columns(), Find_m_faces(), GenParamPolyhedron(), main(), Polyhedron_Remove_parm_eqs(), and traite_m_face().

◆ Polyhedron2Rays()

Matrix * Polyhedron2Rays ( Polyhedron * Pol )

Given a polyhedron 'Pol', return a matrix of rays.

Definition at line 2683 of file polyhedron.c.

References polyhedron::Dimension, errormsg1(), Matrix_Alloc(), polyhedron::NbRays, matrix::p_Init, POL_ENSURE_POINTS, polyhedron::Ray, and Vector_Copy().

Referenced by main().

◆ Polyhedron_Alloc()

Polyhedron * Polyhedron_Alloc	(	unsigned	Dimension,
		unsigned	NbConstraints,
		unsigned	NbRays
	)

Definition at line 1573 of file polyhedron.c.

References polyhedron::Constraint, polyhedron::Dimension, errormsg1(), polyhedron::flags, polyhedron::NbBid, polyhedron::NbConstraints, polyhedron::NbEq, polyhedron::NbRays, polyhedron::next, polyhedron::p_Init, polyhedron::p_Init_size, polyhedron::Ray, and value_alloc().

Referenced by align_context(), Constraints2Polyhedron(), domain_insert_dim(), Empty_Polyhedron(), Polyhedron_Copy(), Polyhedron_Image(), Remove_Redundants(), and Universe_Polyhedron().

◆ Polyhedron_Compute_Dual()

void Polyhedron_Compute_Dual ( Polyhedron * P )

Definition at line 2213 of file polyhedron.c.

References assert, polyhedron::Constraint, Constraints2Polyhedron(), polyhedron::Dimension, F_ISSET, matrix::NbColumns, polyhedron::NbConstraints, matrix::NbRows, polyhedron::next, matrix::p, matrix::p_Init, polyhedron::p_Init, POL_FACETS, POL_INEQUALITIES, POL_VALID, POL_VERTICES, and Polyhedron_Free().

◆ Polyhedron_Copy()

Polyhedron * Polyhedron_Copy ( Polyhedron * Pol )

Definition at line 2851 of file polyhedron.c.

References polyhedron::Constraint, polyhedron::Dimension, errormsg1(), polyhedron::flags, polyhedron::NbBid, polyhedron::NbConstraints, polyhedron::NbEq, polyhedron::NbRays, Polyhedron_Alloc(), polyhedron::Ray, and Vector_Copy().

Referenced by Add_CEqualities(), AddConstraints(), Disjoint_Domain(), Domain_Copy(), DomainConvex(), DomainDifference(), DomainUnion(), FindSimple(), p_simplify_constraints(), and Polyhedron_Image_Enumerate().

◆ Polyhedron_Free()

void Polyhedron_Free ( Polyhedron * Pol )

Definition at line 1621 of file polyhedron.c.

References polyhedron::Constraint, polyhedron::p_Init, polyhedron::p_Init_size, and value_free().

Referenced by AddConstraints(), AddPolyToDomain(), AddRays(), align_context(), ComputeNPLinesRays(), Constraints2Polyhedron(), dehomogenize_enumeration(), Disjoint_Domain(), domain_dark_shadow(), Domain_Free(), Domain_Remove_Integer_Empty(), DomainAddConstraints(), DomainAddRays(), DomainConstraintSimplify(), DomainConvex(), DomainImage(), DomainPreimage(), Ehrhart_Quick_Apx(), Ehrhart_Quick_Apx_Full_Dim(), eliminable_vars(), Enumerate_NoParameters(), Enumeration_zero(), Find_m_faces(), FindSimple(), main(), p_simplify_constraints(), PDomainDifference(), PDomainIntersection(), Polyhedron2Param_Domain(), Polyhedron_Compute_Dual(), Polyhedron_Enumerate(), Polyhedron_Image(), Polyhedron_Image_Enumerate(), Polyhedron_LexSmallerEnumerate(), Polyhedron_Preimage(), Polyhedron_Preprocess(), Polyhedron_Remove_parm_eqs(), Rays2Polyhedron(), Remove_Redundants(), SimplifyConstraints(), sLBLCompute_holes(), sLBLIntersection(), Stras_DomainSimplify(), SubConstraint(), test_Constraints_fullDimensionize(), test_Constraints_Remove_parm_eqs(), test_Polyhedron_Remove_parm_eqs(), and traite_m_face().

◆ Polyhedron_Image()

Polyhedron * Polyhedron_Image	(	Polyhedron *	Pol,
		Matrix *	Func,
		unsigned	NbMaxConstrs
	)

Definition at line 4167 of file polyhedron.c.

References any_exception_error, CATCH, polyhedron::Constraint, polyhedron::Dimension, Empty_Polyhedron(), errormsg1(), Gauss4(), Matrix_Alloc(), Matrix_Copy(), Matrix_Free(), Matrix_Inverse(), polyhedron::NbBid, matrix::NbColumns, polyhedron::NbConstraints, polyhedron::NbEq, polyhedron::NbRays, matrix::NbRows, matrix::p, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, Polyhedron_Alloc(), Polyhedron_Free(), polyhedron::Ray, Rays2Polyhedron(), Rays_Mult(), Rays_Mult_Transpose(), RETHROW, TRY, and UNCATCH.

Referenced by DomainImage(), and main().

◆ Polyhedron_Preimage()

Polyhedron * Polyhedron_Preimage	(	Polyhedron *	Pol,
		Matrix *	Func,
		unsigned	NbMaxRays
	)

Definition at line 4076 of file polyhedron.c.

References any_exception_error, CATCH, polyhedron::Constraint, Constraints2Polyhedron(), polyhedron::Dimension, Empty_Polyhedron(), errormsg1(), Matrix_Alloc(), Matrix_Free(), matrix::NbColumns, polyhedron::NbConstraints, matrix::NbRows, matrix::p, POL_ENSURE_INEQUALITIES, Pol_status, Polyhedron_Free(), Rays_Mult(), RETHROW, TRY, and UNCATCH.

Referenced by DomainPreimage(), Ehrhart_Quick_Apx_Full_Dim(), Enumerate_NoParameters(), main(), Param_Polyhedron_Scale_Integer(), and Polyhedron_Enumerate().

◆ Polyhedron_Print()

void Polyhedron_Print	(	FILE *	Dst,
		const char *	Format,
		const Polyhedron *	Pol
	)

Definition at line 1646 of file polyhedron.c.

References polyhedron::Constraint, polyhedron::Dimension, polyhedron::NbBid, polyhedron::NbConstraints, polyhedron::NbEq, polyhedron::NbRays, polyhedron::next, Polyhedron_Print(), polyhedron::Ray, VALUE_FMT, value_notzero_p, and value_print.

Referenced by Compute_PDomains(), Constraints2Polyhedron(), domain_project(), Domain_Remove_Integer_Empty(), Ehrhart_Quick_Apx_Full_Dim(), Elim_Columns(), Enumerate_NoParameters(), Find_m_faces(), main(), polyhedron_dark_source(), Polyhedron_Enumerate(), Polyhedron_Preprocess(), Polyhedron_Print(), PolyhedronLTQ(), PolyPrint(), PreElim_Columns(), Rays2Polyhedron(), sLBL2ZDomain(), sLBL_Lat_Normalize(), sLBLCanonical(), sLBLComplement(), sLBLComplement2(), sLBLCompute_holes(), sLBLHomogenize_equalities(), sLBLIntersection(), sLBLPrint(), sLBLSimplify_equalities(), and traite_m_face().

◆ Polyhedron_PrintConstraints()

void Polyhedron_PrintConstraints	(	FILE *	Dst,
		const char *	Format,
		Polyhedron *	Pol
	)

Definition at line 4702 of file polyhedron.c.

References polyhedron::Constraint, polyhedron::Dimension, polyhedron::NbConstraints, and value_print.

Referenced by AffConstraints(), AffContraintes(), and Domain_PrintConstraints().

◆ Polyhedron_Scan()

Polyhedron * Polyhedron_Scan	(	Polyhedron *	D,
		Polyhedron *	C,
		unsigned	NbMaxRays
	)

Definition at line 3791 of file polyhedron.c.

References align_context(), assert, polyhedron::Dimension, Domain_Free(), DomainAddRays(), DomainIntersection(), DomainSimplify(), errormsg1(), Matrix_Alloc(), Matrix_Free(), matrix::NbRows, polyhedron::next, matrix::p, matrix::p_Init, POL_ENSURE_FACETS, POL_ENSURE_VERTICES, value_set_si, and Vector_Set().

Referenced by Domain_Remove_Integer_Empty(), Ehrhart_Quick_Apx_Full_Dim(), Enumerate_NoParameters(), main(), Polyhedron_Enumerate(), Polyhedron_Not_Empty(), Polyhedron_Preprocess(), and sLBLCompute_holes().

◆ PolyhedronIncludes()

int PolyhedronIncludes	(	Polyhedron *	Pol1,
		Polyhedron *	Pol2
	)

◆ polylib_close()

void polylib_close ( void )

Free all cache allocated memory: call this function before exiting in a memory checker environment like valgrind.

Notice that, in a multithreaded environment, all your threads have to call this function

Definition at line 4807 of file polyhedron.c.

References free_exception_stack(), and free_value_cache().

Referenced by main().

◆ PolyPrint()

void PolyPrint ( Polyhedron * Pol )

Definition at line 1717 of file polyhedron.c.

References Polyhedron_Print().

◆ Rays2Polyhedron()

Polyhedron * Rays2Polyhedron	(	Matrix *	Ray,
		unsigned	NbMaxConstrs
	)

Given a matrix of rays 'Ray', create and return a polyhedron.

Parameters

Ray	Rays (may be modified!)
NbMaxConstrs	Estimated number of constraints in the polyhedron.

Returns: newly allocated Polyhedron

Definition at line 2094 of file polyhedron.c.

References any_exception_error, CATCH, Chernikova(), Empty_Polyhedron(), errormsg1(), Matrix_Alloc(), Matrix_Free(), Matrix_Print(), matrix::NbColumns, matrix::NbRows, matrix::p, matrix::p_Init, POL_ISSET, POL_NO_DUAL, Polyhedron_Free(), Polyhedron_Print(), Remove_Redundants(), RETHROW, Sat, SMAlloc(), SMFree(), SMVector_Init, TransformSat(), TRY, UNCATCH, value_set_si, and Vector_Set().

Referenced by bound_polyhedron(), GenPoly(), main(), Polyhedron_Image(), and traite_m_face().

◆ Rays_Mult()

static void Rays_Mult	(	Value **	A,
		Matrix *	B,
		Value **	C,
		unsigned	NbRays
	)

static

Definition at line 3990 of file polyhedron.c.

References any_exception_error, CATCH, matrix::NbColumns, matrix::NbRows, matrix::p, RETHROW, TRY, UNCATCH, value_addmul, value_assign, value_clear, value_init, value_notone_p, value_set_si, Vector_AntiScale(), and Vector_Gcd().

Referenced by Polyhedron_Image(), and Polyhedron_Preimage().

◆ Rays_Mult_Transpose()

static void Rays_Mult_Transpose	(	Value **	A,
		Matrix *	B,
		Value **	C,
		unsigned	NbRays
	)

static

Definition at line 4031 of file polyhedron.c.

References any_exception_error, CATCH, matrix::NbColumns, matrix::NbRows, matrix::p, RETHROW, TRY, UNCATCH, value_addmul, value_assign, value_clear, value_init, value_notone_p, value_set_si, Vector_AntiScale(), and Vector_Gcd().

Referenced by Polyhedron_Image().

◆ RaySort()

static void RaySort	(	Matrix *	Ray,
		SatMatrix *	Sat,
		int	NbBid,
		int	NbRay,
		int *	equal_bound,
		int *	sup_bound,
		unsigned	RowSize1,
		unsigned	RowSize2,
		unsigned	bx,
		unsigned	jx
	)