/* Basic Affine Arithmetic definitions and operations */ /* Last edited on 2003-07-29 00:45:40 by stolfi */ #ifndef AA_H #define AA_H #include #include #include #include #include /*** TYPES ***/ typedef unsigned long VarId; /* ID number of a noise symbol (positive). */ typedef struct AATerm /* A 1st degree term of an affine form. */ { VarId id; /* ID number of noise symbol. */ Float coef; /* Coefficient of noise symbol. */ } AATerm; typedef AATerm *AATermP; typedef unsigned long AATermCount; #define MIXED 0 typedef struct AAHead /* Head of an affine form. */ { #if MIXED Interval range; /* Ordinary interval for the quantity. */ #endif AATermCount nterms; /* Number of 1st degree terms. */ Float center; /* Center value of affine form. */ } AAHead; typedef AAHead *AAP; /* An affine form is an {AAHead} immediately followed in memory by zero or more {AATerm}s. */ /*** INITIALIZATION ***/ void aa_init (void); /* Initializes the AA module (the AA stack, {aa_next_id}, etc.) */ /*** CONSTANTS AND PREDICATES ***/ AAP aa_full(void); /* The "anything" form */ int aa_is_full (AAP x); /* True iff {x} is "anything" */ AAP aa_zero(void); /* An affine form for "0" */ AAP aa_one(void); /* An affine form for "1" */ int aa_is_zero (AAP x); /* True iff {x} is precisely zero. */ /*** ARITHMETIC ***/ /* The following routines usually allocate space for the result from the AA stack. They may sometimes return a pointer to one of their arguments, or to some constant affine form. Thus it is never wise to modify a computed affine form. */ AAP aa_add (AAP x, AAP y); AAP aa_sub (AAP x, AAP y); AAP aa_neg (AAP x); AAP aa_scale (AAP x, Float alpha, Float zeta); /* {\alpha x / \zeta} */ AAP aa_shift (AAP x, Float gamma); /* {x + \gamma} */ AAP aa_mul (AAP x, AAP y); AAP aa_div (AAP x, AAP y); AAP aa_sqr (AAP x); /* same as aa_mul(x,x), only better */ AAP aa_inv (AAP x); /* 1/x */ AAP aa_sqrt(AAP x); AAP aa_alt_sqrt(AAP x); AAP aa_exp(AAP x); AAP aa_abs(AAP x); AAP aa_max(AAP x, AAP y); AAP aa_min(AAP x, AAP y); AAP aa_affine(AAP x, Float alpha, Float zeta, Float gamma, Float delta); /* Returns {\alpha x / \zeta + \gamma \pm \delta}. The {\pm \delta} term and all rounding errors are lumped in a new noise symbol. */ AAP aa_affine_2 ( AAP x, Float alpha, AAP y, Float beta, Float zeta, Float gamma, Float delta ); /* Returns {(\alpha x + \beta y)/ \zeta + \gamma \pm \delta}. The {\pm \delta} term and all rounding errors are lumped in a new noise symbol. */ AAP aa_join (AAP x, AAP y); /* Returns an affine form that describes an arbitrary convex combination of {x} and {y}; that is, a quantity that is known to lie between some value of {x} and some value of {y}. */ AAP aa_fix_eps(AAP x, AATermCount neps, AATerm eps[]); /* Returns an affine form obtained from {x} by fixing the value of all noise symbols with {id = eps[i].id} ({i=0,..neps-1}) to {eps[i].coef}. Any noise symbols that appear in {x} but not in {eps} are retained in the result. A new noise symbol is added, if necessary, to account for rounding errors. The fields {eps[i].id} must be sorted in increasing order. The values {eps[i].coef} need not be in [-1 __ +1]. */ void aa_collapse_pair(AAP x, AAP y, AAP *xr, AAP *yr); /* Returns in {*xr} and {*yr} two affine forms that describe the same quantities described by {x} and {y}, but share at most two noise symbols (possibly new ones). */ /*** CONVERSION ***/ Interval aa_range (AAP x); /* Returns the range of {x}, considering {x->range} (if any). */ AAP aa_const(Float c, Float err); /* Makes a new affine form with center value {c} and an independent error term {err}. */ AAP aa_int_const (int i); /* Makes an affine form for the integer {i}. If the integer is too big, the form may not be exact. */ AAP aa_from_interval (Interval x); /* Makes a new affine form from the given interval, using a brand-new noise variable. */ /*** MISCELLANEOUS TOOLS ***/ void aa_print (FILE *f, AAP x); /* Prints out {x} on file {f}. */ void aa_move (AAP source, AAP destination); /* Copies the affine form {*source} to {*destination}. It is up to the client to ensure that there is enough space there. */ Float aa_sum_abs_terms (AATermP xp, AATermCount n); /* Returns the sum of the absolute values of the deviations {xp[0..n-1].coef}, rounded up. */ Float aa_max_abs_term (AATermP xp, AATermCount n); /* Returns the maximum absolute magnitude of the partial deviations {xp[0..n-1].coef}. */ Interval aa_implicit_range (AAP x); /* Returns the range of {x}, considering only the affine form. */ AAP aa_throw (int nterms); /* Returns a random affine form with up to {nterms} terms, suitable for testing. The {VarId}s of the terms will be 0 through {nterms-1}, but some of the terms may be zero (i.e. missing). The client must have called {srandom()}. */ /*** STACK ALLOCATION ***/ MemP aa_top (void); /* Returns the current top-of-stack pointer */ AAP aa_alloc_head(void); /* Reserves space at the top of the AA stack for inserting another AAHead; returns pointer to it. */ void aa_pop_head(void); /* Assumes an AAHead is at the top of the stack; removes it. */ AATermP aa_alloc_term(void); /* Reserves space at the top of the stack for inserting another AATerm; returns pointer to it. */ AATermP aa_push_term(Float coef, VarId id); /* Pushes a new AATerm on top of the stack, with given fields. */ void aa_pop_term(void); /* Assumes a AATerm is at the top of the AA stack; removes it. */ void aa_append_error_term (AATermCount *znp, Float err); /* If {err} is not zero, pushes an extra AATerm on the stack, with {err} as the coefficient and with a newly allocated noise symbol {id}, and increments {*znp}. Otherwise does nothing. */ void aa_flush (MemP frame); /* Ends the logical scope started at the given {frame} (and all inner blocks), freeing any AA stack storage allocated within their scope. */ AAP aa_return (MemP frame, AAP result); /* If the {result} is not on the stack, does {aa_flush(frame)}. Else saves {*result}, does a {aa_flush(frame)}, then pushes back the saved result onto the AA stack. In either case, returns the result's final address. */ /*** HEAP ALLOCATION ***/ AAP aa_heap_alloc (AATermCount n); /* Allocates new space for a new affine form with {n} terms (from the {faralloc} pool). Bombs out if it runs out of memory. */ AAP aa_heap_realloc (AAP x, AATermCount n); /* Re-allocates space for the affine form {x} (which must have been allocated with {aa_heap_alloc}), for {n} terms, and copies {x}'s current contents there, and frees the old storage. Returns a pointer to the new area (which may be the same as {x}). Bombs out if it runs out of memory. */ void aa_heap_free (AAP x); /* Releases space used by the affine form {x} (which must have been allocated by {aa_heap_alloc}. */ #endif