postfix.c File Reference

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "dbDefs.h"
#include "epicsAssert.h"
#include "epicsStdlib.h"
#include "epicsString.h"
#include "epicsTypes.h"
#include "postfix.h"
#include "postfixPvt.h"
#include "libComAPI.h"

Include dependency graph for postfix.c:

Go to the source code of this file.

Classes
struct	expression_element

Typedefs
typedef struct expression_element	ELEMENT

Enumerations
enum	element_type {   OPERAND, LITERAL_OPERAND, STORE_OPERATOR, UNARY_OPERATOR,   VARARG_OPERATOR, BINARY_OPERATOR, SEPERATOR, CLOSE_PAREN,   CONDITIONAL, EXPR_TERMINATOR }

Functions
LIBCOM_API long	postfix (const char *psrc, char *pout, short *perror)
	Compile an infix expression into postfix byte-code. More...
LIBCOM_API const char *	calcErrorStr (short error)
	Convert an error code to a string. More...
LIBCOM_API void	calcExprDump (const char *pinst)
	Disassemble a postfix expression. More...

Typedef Documentation

typedef struct expression_element ELEMENT

Enumeration Type Documentation

enum element_type

Enumerator
OPERAND
LITERAL_OPERAND
STORE_OPERATOR
UNARY_OPERATOR
VARARG_OPERATOR
BINARY_OPERATOR
SEPERATOR
CLOSE_PAREN
CONDITIONAL
EXPR_TERMINATOR

Definition at line 33 of file postfix.c.

             {
        OPERAND,
        LITERAL_OPERAND,
        STORE_OPERATOR,
        UNARY_OPERATOR,
        VARARG_OPERATOR,
        BINARY_OPERATOR,
        SEPERATOR,
        CLOSE_PAREN,
        CONDITIONAL,
        EXPR_TERMINATOR,
} element_type;

Function Documentation

LIBCOM_API const char* calcErrorStr

(

short

error

)

Convert an error code to a string.

Gives out a printable version of an individual error code. The error codes are macros defined here with names starting CALC_ERR_

Parameters

error

Error code

Returns

A string representation of the error code

Definition at line 493 of file postfix.c.

{
    static const char *errStrs[] = {
        "No error",
        "Too many results returned",
        "Badly formed numeric literal",
        "Bad assignment target",
        "Comma without enclosing parentheses",
        "Close parenthesis found without open",
        "Parenthesis still open at end of expression",
        "Unbalanced conditional ?: operators",
        "Incomplete expression, operand missing",
        "Not enough operands provided",
        "Runtime stack overflow",
        "Syntax error, unknown operator/operand",
        "NULL or empty input argument to postfix()",
        "Internal error, unknown element type",
    };

    if (error < CALC_ERR_NONE || error > CALC_ERR_INTERNAL)
        return NULL;
    return errStrs[error];
}

LIBCOM_API void calcExprDump

(

const char *

pinst

)

Disassemble a postfix expression.

Convert the byte-code stream to text and print to stdout.

Parameters

pinst

postfix instructions

Definition at line 523 of file postfix.c.

{
    static const char *opcodes[] = {
        "End Expression",
    /* Operands */
        "LITERAL_DOUBLE", "LITERAL_INT", "VAL",
        "FETCH_A", "FETCH_B", "FETCH_C", "FETCH_D", "FETCH_E", "FETCH_F",
        "FETCH_G", "FETCH_H", "FETCH_I", "FETCH_J", "FETCH_K", "FETCH_L",
    /* Assignment */
        "STORE_A", "STORE_B", "STORE_C", "STORE_D", "STORE_E", "STORE_F",
        "STORE_G", "STORE_H", "STORE_I", "STORE_J", "STORE_K", "STORE_L",
    /* Trigonometry Constants */
        "CONST_PI",
        "CONST_D2R",
        "CONST_R2D",
    /* Arithmetic */
        "UNARY_NEG",
        "ADD",
        "SUB",
        "MULT",
        "DIV",
        "MODULO",
        "POWER",
    /* Algebraic */
        "ABS_VAL",
        "EXP",
        "LOG_10",
        "LOG_E",
        "MAX",
        "MIN",
        "SQU_RT",
    /* Trigonometric */
        "ACOS",
        "ASIN",
        "ATAN",
        "ATAN2",
        "COS",
        "COSH",
        "SIN",
        "SINH",
        "TAN",
        "TANH",
    /* Numeric */
        "CEIL",
        "FLOOR",
        "FINITE",
        "ISINF",
        "ISNAN",
        "NINT",
        "RANDOM",
    /* Boolean */
        "REL_OR",
        "REL_AND",
        "REL_NOT",
    /* Bitwise */
        "BIT_OR",
        "BIT_AND",
        "BIT_EXCL_OR",
        "BIT_NOT",
        "RIGHT_SHIFT_ARITH",
        "LEFT_SHIFT_ARITH",
        "RIGHT_SHIFT_LOGIC",
    /* Relationals */
        "NOT_EQ",
        "LESS_THAN",
        "LESS_OR_EQ",
        "EQUAL",
        "GR_OR_EQ",
        "GR_THAN",
    /* Conditional */
        "COND_IF",
        "COND_ELSE",
        "COND_END",
    /* Misc */
        "NOT_GENERATED"
    };
    char op;
    double lit_d;
    epicsInt32 lit_i;

    while ((op = *pinst) != END_EXPRESSION) {
        switch (op) {
        case LITERAL_DOUBLE:
            memcpy(&lit_d, ++pinst, sizeof(double));
            printf("\tDouble %g\n", lit_d);
            pinst += sizeof(double);
            break;
        case LITERAL_INT:
            memcpy(&lit_i, ++pinst, sizeof(epicsInt32));
            printf("\tInteger %d (0x%x)\n", lit_i, lit_i);
            pinst += sizeof(epicsInt32);
            break;
        case MIN:
        case MAX:
        case FINITE:
        case ISNAN:
            printf("\t%s, %d arg(s)\n", opcodes[(int) op], *++pinst);
            pinst++;
            break;
        default:
            printf("\t%s\n", opcodes[(int) op]);
            pinst++;
        }
    }
}

LIBCOM_API long postfix	(	const char *	pinfix,
		char *	ppostfix,
		short *	perror
	)

Compile an infix expression into postfix byte-code.

Converts an expression from an infix string to postfix byte-code

Parameters

pinfix	Pointer to the infix string
ppostfix	Pointer to the postfix buffer
perror	Place to return an error code

Returns

Non-zero value in event of error

It is the callers's responsibility to ensure that ppostfix points to sufficient storage to hold the postfix expression. The macro INFIX_TO_POSTFIX_SIZE(n) can be used to calculate an appropriate postfix buffer size from the length of the infix buffer.

Note

"n" must count the terminating nil byte too.

1. The infix expressions that can be used are very similar to the C expression syntax, but with some additions and subtle differences in operator meaning and precedence. The string may contain a series of expressions separated by a semi-colon character ';' any one of which may actually provide the calculation result; however all of the other expressions included must assign their result to a variable. All alphabetic elements described below are case independent, so upper and lower case letters may be used and mixed in the variable and function names as desired. Spaces may be used anywhere within an expression except between the characters that make up a single expression element.
2. ***Numeric Literals*** The simplest expression element is a numeric literal, any (positive) number expressed using the standard floating point syntax that can be stored as a double precision value. This now includes the values Infinity and NaN (not a number). Note that negative numbers will be encoded as a positive literal to which the unary negate operator is applied.
   • Examples:
     • 1
     • 2.718281828459
     • Inf
3. ***Constants*** There are three trigonometric constants available to any expression which return a value:
   • pi returns the value of the mathematical constant pi.
   • D2R evaluates to pi/180 which, when used as a multiplier, converts an angle from degrees to radians.
   • R2D evaluates to 180/pi which as a multiplier converts an angle from radians to degrees.
4. ***Variables*** Variables are used to provide inputs to an expression, and are named using the single letters A through L inclusive or the keyword VAL which refers to the previous result of this calculation. The software that makes use of the expression evaluation code should document how the individual variables are given values; for the calc record type the input links INPA through INPL can be used to obtain these from other record fields, and VAL refers to the the VAL field (which can be overwritten from outside the record via Channel Access or a database link).
5. ***Variable Assignment Operator*** Recently added is the ability to assign the result of a sub-expression to any of the single letter variables, which can then be used in another sub-expression. The variable assignment operator is the character pair := and must immediately follow the name of the variable to receive the expression value. Since the infix string must return exactly one value, every expression string must have exactly one sub-expression that is not an assignment, which can appear anywhere in the string. Sub-expressions within the string are separated by a semi-colon character.
   • Examples:
     • B; B:=A
     • i:=i+1; a*sin(i*D2R)

6. ***Arithmetic Operators*** The usual binary arithmetic operators are provided: + - * and / with their usual relative precedence and left-to-right associativity, and - may also be used as a unary negate operator where it has a higher precedence and associates from right to left. There is no unary plus operator, so numeric literals cannot begin with a + sign.

   • Examples:
     • a*b + c
     • a/-4 - b

   Three other binary operators are also provided: % is the integer modulo operator, while the synonymous operators ** and ^ raise their left operand to the power of the right operand. % has the same precedence and associativity as * and /, while the power operators associate left-to-right and have a precedence in between * and unary minus.

   • Examples:
     • e:=a%10;
     • d:=a/10%10;
     • c:=a/100%10;
     • b:=a/1000%10;
     • b*4096+c*256+d*16+e
     • sqrt(a**2 + b**2)
7. ***Algebraic Functions*** Various algebraic functions are available which take parameters inside parentheses. The parameter seperator is a comma.
   • Absolute value: abs(a)
   • Exponential ea: exp(a)
   • Logarithm, base 10: log(a)
   • Natural logarithm (base e): ln(a) or loge(a)
   • n parameter maximum value: max(a, b, ...)
   • n parameter minimum value: min(a, b, ...)
   • Square root: sqr(a) or sqrt(a)
8. ***Trigonometric Functions*** Standard circular trigonometric functions, with angles expressed in radians:
   • Sine: sin(a)
   • Cosine: cos(a)
   • Tangent: tan(a)
   • Arcsine: asin(a)
   • Arccosine: acos(a)
   • Arctangent: atan(a)
   • 2 parameter arctangent: atan2(a, b)

     Note

     Note that these arguments are the reverse of the ANSI C function, so while C would return arctan(a/b) the calc expression engine returns arctan(b/a)

9. ***Hyperbolic Trigonometry*** The basic hyperbolic functions are provided, but no inverse functions (which are not provided by the ANSI C math library either).
   • Hyperbolic sine: sinh(a)
   • Hyperbolic cosine: cosh(a)
   • Hyperbolic tangent: tanh(a)
10. ***Numeric Functions*** The numeric functions perform operations related to the floating point numeric representation and truncation or rounding.
    • Round up to next integer: ceil(a)
    • Round down to next integer: floor(a)
    • Round to nearest integer: nint(a)
    • Test for infinite result: isinf(a)
    • Test for any non-numeric values: isnan(a, ...)
    • Test for all finite, numeric values: finite(a, ...)
    • Random number between 0 and 1: rndm
11. ***Boolean Operators*** These operators regard their arguments as true or false, where 0.0 is false and any other value is true.
    • Boolean and: a && b
    • Boolean or: a || b
    • Boolean not: !a
12. ***Bitwise Operators*** The bitwise operators convert their arguments to an integer (by truncation), perform the appropriate bitwise operation and convert back to a floating point value. Unlike in C though, ^ is not a bitwise exclusive-or operator.
    • Bitwise and: a & b or a and b
    • Bitwise or: a | b or a or b
    • Bitwise exclusive or: a xor b
    • Bitwise not (ones complement): ~a or not a
    • Bitwise left shift: a << b
    • Bitwise right shift: a >> b
13. ***Relational Operators*** Standard numeric comparisons between two values:
    • Less than: a < b
    • Less than or equal to: a <= b
    • Equal to: a = b or a == b
    • Greater than or equal to: a >= b
    • Greater than: a > b
    • Not equal to: a != b or a # b
14. ***Conditional Operator*** Expressions can use the C conditional operator, which has a lower precedence than all of the other operators except for the assignment operator.
    • condition ? true result : false result
      • Example:
        • a < 360 ? a+1 : 0
15. ***Parentheses*** Sub-expressions can be placed within parentheses to override operator precence rules. Parentheses can be nested to any depth, but the intermediate value stack used by the expression evaluation engine is limited to 80 results (which require an expression at least 321 characters long to reach).

Definition at line 209 of file postfix.c.

{
    ELEMENT stack[80];
    ELEMENT *pstacktop = stack;
    const ELEMENT *pel;
    int operand_needed = TRUE;
    int runtime_depth = 0;
    int cond_count = 0;
    char * const pdest = pout;
    char *pnext;

    if (psrc == NULL || *psrc == '\0' ||
        pout == NULL || perror == NULL) {
        if (perror) *perror = CALC_ERR_NULL_ARG;
        if (pout) *pout = END_EXPRESSION;
        return -1;
    }

    /* place the expression elements into postfix */
    *pout = END_EXPRESSION;
    *perror = CALC_ERR_NONE;

    while (get_element(operand_needed, &psrc, &pel)) {
        switch (pel->type) {

        case OPERAND:
            *pout++ = pel->code;
            runtime_depth += pel->runtime_effect;
            operand_needed = FALSE;
            break;

        case LITERAL_OPERAND:
            runtime_depth += pel->runtime_effect;

            psrc -= strlen(pel->name);
            if (pel->code == LITERAL_DOUBLE) {
                double lit_d;
                epicsInt32 lit_i;

                if (epicsParseDouble(psrc, &lit_d, &pnext)) {
                    *perror = CALC_ERR_BAD_LITERAL;
                    goto bad;
                }
                psrc = pnext;
                lit_i = (epicsInt32) lit_d;
                if (lit_d != (double) lit_i) {
                    *pout++ = pel->code;
                    memcpy(pout, &lit_d, sizeof(double));
                    pout += sizeof(double);
                } else {
                    *pout++ = LITERAL_INT;
                    memcpy(pout, &lit_i, sizeof(epicsInt32));
                    pout += sizeof(epicsInt32);
                }
            }
            else {
                epicsUInt32 lit_ui;

                assert(pel->code == LITERAL_INT);
                if (epicsParseUInt32(psrc, &lit_ui, 0, &pnext)) {
                    *perror = CALC_ERR_BAD_LITERAL;
                    goto bad;
                }
                psrc = pnext;
                *pout++ = LITERAL_INT;
                memcpy(pout, &lit_ui, sizeof(epicsUInt32));
                pout += sizeof(epicsUInt32);
            }

            operand_needed = FALSE;
            break;

        case STORE_OPERATOR:
            if (pout == pdest || pstacktop > stack ||
                *--pout < FETCH_A || *pout > FETCH_L) {
                *perror = CALC_ERR_BAD_ASSIGNMENT;
                goto bad;
            }
            /* Convert fetch into a store on the stack */
            *++pstacktop = *pel;
            pstacktop->code = STORE_A + *pout - FETCH_A;
            runtime_depth -= 1;
            operand_needed = TRUE;
            break;

        case UNARY_OPERATOR:
        case VARARG_OPERATOR:
            /* Move operators of >= priority to the output */
            while ((pstacktop > stack) &&
                   (pstacktop->in_stack_pri >= pel->in_coming_pri)) {
                *pout++ = pstacktop->code;
                if (pstacktop->type == VARARG_OPERATOR) {
                    *pout++ = 1 - pstacktop->runtime_effect;
                }
                runtime_depth += pstacktop->runtime_effect;
                pstacktop--;
            }

            /* Push new operator onto stack */
            pstacktop++;
            *pstacktop = *pel;
            break;

        case BINARY_OPERATOR:
            /* Move operators of >= priority to the output */
            while ((pstacktop > stack) &&
                   (pstacktop->in_stack_pri >= pel->in_coming_pri)) {
                *pout++ = pstacktop->code;
                if (pstacktop->type == VARARG_OPERATOR) {
                    *pout++ = 1 - pstacktop->runtime_effect;
                }
                runtime_depth += pstacktop->runtime_effect;
                pstacktop--;
            }

            /* Push new operator onto stack */
            pstacktop++;
            *pstacktop = *pel;

            operand_needed = TRUE;
            break;

        case SEPERATOR:
            /* Move operators to the output until open paren */
            while (pstacktop->name[0] != '(') {
                if (pstacktop <= stack+1) {
                    *perror = CALC_ERR_BAD_SEPERATOR;
                    goto bad;
                }
                *pout++ = pstacktop->code;
                if (pstacktop->type == VARARG_OPERATOR) {
                    *pout++ = 1 - pstacktop->runtime_effect;
                }
                runtime_depth += pstacktop->runtime_effect;
                pstacktop--;
            }
            operand_needed = TRUE;
            pstacktop->runtime_effect -= 1;
            break;

        case CLOSE_PAREN:
            /* Move operators to the output until matching paren */
            while (pstacktop->name[0] != '(') {
                if (pstacktop <= stack+1) {
                    *perror = CALC_ERR_PAREN_NOT_OPEN;
                    goto bad;
                }
                *pout++ = pstacktop->code;
                if (pstacktop->type == VARARG_OPERATOR) {
                    *pout++ = 1 - pstacktop->runtime_effect;
                }
                runtime_depth += pstacktop->runtime_effect;
                pstacktop--;
            }
            pstacktop--;        /* remove ( from stack */
            /* if there is a vararg operator before the opening paren,
               it inherits the (opening) paren's stack effect */
            if ((pstacktop > stack) &&
                pstacktop->type == VARARG_OPERATOR) {
                pstacktop->runtime_effect = (pstacktop+1)->runtime_effect;
                /* check for no arguments */
                if (pstacktop->runtime_effect > 0) {
                    *perror = CALC_ERR_INCOMPLETE;
                    goto bad;
                }
            }
            break;

        case CONDITIONAL:
            /* Move operators of > priority to the output */
            while ((pstacktop > stack) &&
                   (pstacktop->in_stack_pri > pel->in_coming_pri)) {
                *pout++ = pstacktop->code;
                if (pstacktop->type == VARARG_OPERATOR) {
                    *pout++ = 1 - pstacktop->runtime_effect;
                }
                runtime_depth += pstacktop->runtime_effect;
                pstacktop--;
            }

            /* Add new element to the output */
            *pout++ = pel->code;
            runtime_depth += pel->runtime_effect;

            /* For : operator, also push COND_END code to stack */
            if (pel->name[0] == ':') {
                if (--cond_count < 0) {
                    *perror = CALC_ERR_CONDITIONAL;
                    goto bad;
                }
                pstacktop++;
                *pstacktop = *pel;
                pstacktop->code = COND_END;
                pstacktop->runtime_effect = 0;
            } else {
                cond_count++;
            }

            operand_needed = TRUE;
            break;

        case EXPR_TERMINATOR:
            /* Move everything from stack to the output */
            while (pstacktop > stack) {
                if (pstacktop->name[0] == '(') {
                    *perror = CALC_ERR_PAREN_OPEN;
                    goto bad;
                }
                *pout++ = pstacktop->code;
                if (pstacktop->type == VARARG_OPERATOR) {
                    *pout++ = 1 - pstacktop->runtime_effect;
                }
                runtime_depth += pstacktop->runtime_effect;
                pstacktop--;
            }

            if (cond_count != 0) {
                *perror = CALC_ERR_CONDITIONAL;
                goto bad;
            }
            if (runtime_depth > 1) {
                *perror = CALC_ERR_TOOMANY;
                goto bad;
            }

            operand_needed = TRUE;
            break;

        default:
            *perror = CALC_ERR_INTERNAL;
            goto bad;
        }

        if (runtime_depth < 0) {
            *perror = CALC_ERR_UNDERFLOW;
            goto bad;
        }
        if (runtime_depth >= CALCPERFORM_STACK) {
            *perror = CALC_ERR_OVERFLOW;
            goto bad;
        }
    }

    if (*psrc != '\0') {
        *perror = CALC_ERR_SYNTAX;
        goto bad;
    }

    /* Move everything from stack to the output */
    while (pstacktop > stack) {
        if (pstacktop->name[0] == '(') {
            *perror = CALC_ERR_PAREN_OPEN;
            goto bad;
        }
        *pout++ = pstacktop->code;
        if (pstacktop->type == VARARG_OPERATOR) {
            *pout++ = 1 - pstacktop->runtime_effect;
        }
        runtime_depth += pstacktop->runtime_effect;
        pstacktop--;
    }
    *pout = END_EXPRESSION;

    if (cond_count != 0) {
        *perror = CALC_ERR_CONDITIONAL;
        goto bad;
    }
    if (operand_needed || runtime_depth != 1) {
        *perror = CALC_ERR_INCOMPLETE;
        goto bad;
    }
    return 0;

bad:
    *pdest = END_EXPRESSION;
    return -1;
}