/* Basic definitions and operations of Affine Arithmetic (AA). */ /****************************************************************************/ /* (C) Copyright 1993 Universidade Estadual de Campinas (UNICAMP) */ /* Campinas, SP, Brazil */ /* */ /* This file can be freely distributed, modified, and used for any */ /* non-commercial purpose, provided that this copyright and authorship */ /* notice be included in any copy or derived version of this file. */ /* */ /* DISCLAIMER: This software is offered ``as is'', without any guarantee */ /* as to fitness for any particular purpose. Neither the copyright */ /* holder nor the authors or their employers can be held responsible for */ /* any damages that may result from its use. */ /****************************************************************************/ #ifndef AA_H #define AA_H #include #include #include #include #include /*** TYPES ***/ typedef unsigned long VarId; typedef struct { VarId id; Float coef; } AATerm; typedef AATerm *AATermP; typedef unsigned long AATermCount; #define MIXED 0 typedef struct { #if MIXED Interval range; #endif AATermCount nterms; Float center; } AAHead; typedef AAHead *AAP; /*** INITIALIZATION ***/ void aa_init (void); /* Initializes the AA module (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 zero */ int aa_is_zero (AAP x); /* True iff $x$ is precisely zero. */ /*** ARITHMETIC ***/ /* The following routines allocate space for the result from the stack */ /* They may return a pointer to one of their arguments, or a constant */ 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_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 their storage. */ 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