src/sim/mathexpr.cc

   1 /*
   2  * Copyright (c) 2015 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions are
  16  * met: redistributions of source code must retain the above copyright
  17  * notice, this list of conditions and the following disclaimer;
  18  * redistributions in binary form must reproduce the above copyright
  19  * notice, this list of conditions and the following disclaimer in the
  20  * documentation and/or other materials provided with the distribution;
  21  * neither the name of the copyright holders nor the names of its
  22  * contributors may be used to endorse or promote products derived from
  23  * this software without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  *
  37  * Authors: David Guillen Fandos
  38  */
  39
  40 #include "sim/mathexpr.hh"
  41
  42 #include <algorithm>
  43 #include <regex>
  44 #include <string>
  45
  46 #include "base/misc.hh"
  47
  48 MathExpr::MathExpr(std::string expr)
  49  : ops(
  50     std::array<OpSearch, uNeg + 1> {
  51       OpSearch {true, bAdd, 0, '+', [] (double a, double b) { return a + b; } },
  52       OpSearch {true, bSub, 0, '-', [] (double a, double b) { return a - b; } },
  53       OpSearch {true, bMul, 1, '*', [] (double a, double b) { return a * b; } },
  54       OpSearch {true, bDiv, 1, '/', [] (double a, double b) { return a / b; } },
  55       OpSearch {false,uNeg, 2, '-', [] (double a, double b) { return -b; } },
  56       OpSearch {true, bPow, 3, '^', [] (double a, double b) { return std::pow(a,b); } },
  57     })
  58 {
  59     // Cleanup
  60     expr.erase(remove_if(expr.begin(), expr.end(), isspace), expr.end());
  61
  62     root = MathExpr::parse(expr);
  63     panic_if(!root, "Invalid expression\n");
  64 }
  65
  66 /**
  67  * This function parses a string expression into an expression tree.
  68  * It will look for operators in priority order to recursively build the
  69  * tree, respecting parenthesization.
  70  * Constants can be expressed in any format accepted by std::stod, whereas
  71  * variables are essentially [A-Za-z0-9\.$\\]+
  72  */
  73 MathExpr::Node *
  74 MathExpr::parse(std::string expr) {
  75     if (expr.size() == 0)
  76         return NULL;
  77
  78     // From low to high priority
  79     int par = 0;
  80     for (unsigned p = 0; p < MAX_PRIO; p++) {
  81         for (int i = expr.size() - 1; i >= 0; i--) {
  82             if (expr[i] == ')')
  83                 par++;
  84             if (expr[i] == '(')
  85                 par--;
  86
  87             if (par < 0) return NULL;
  88             if (par > 0) continue;
  89
  90             for (unsigned opt = 0; opt < ops.size(); opt++) {
  91                 if (ops[opt].priority != p) continue;
  92                 if (ops[opt].c == expr[i]) {
  93                     // Try to parse each side
  94                     Node *l = NULL;
  95                     if (ops[opt].binary)
  96                         l = parse(expr.substr(0, i));
  97                     Node *r = parse(expr.substr(i + 1));
  98                     if ((l && r) || (!ops[opt].binary && r)) {
  99                         // Match!
 100                         Node *n = new Node();
 101                         n->op = ops[opt].op;
 102                         n->l = l;
 103                         n->r = r;
 104                         return n;
 105                     }
 106                 }
 107             }
 108         }
 109     }
 110
 111     // Remove trivial parenthesis
 112     if (expr.size() >= 2 && expr[0] == '(' && expr[expr.size() - 1] == ')')
 113         return parse(expr.substr(1, expr.size() - 2));
 114
 115     // Match a number
 116     {
 117         char *sptr;
 118         double v = strtod(expr.c_str(), &sptr);
 119         if (sptr != expr.c_str()) {
 120             Node *n = new Node();
 121             n->op = sValue;
 122             n->value = v;
 123             return n;
 124         }
 125     }
 126
 127     // Match a variable
 128     {
 129         bool contains_non_alpha = false;
 130         for (auto & c: expr)
 131             contains_non_alpha = contains_non_alpha or
 132                 !( (c >= 'a' && c <= 'z') ||
 133                    (c >= 'A' && c <= 'Z') ||
 134                    (c >= '0' && c <= '9') ||
 135                    c == '$' || c == '\\' || c == '.' || c == '_');
 136
 137         if (!contains_non_alpha) {
 138             Node * n = new Node();
 139             n->op = sVariable;
 140             n->variable = expr;
 141             return n;
 142         }
 143     }
 144
 145     return NULL;
 146 }
 147
 148 double
 149 MathExpr::eval(const Node *n, EvalCallback fn) const {
 150     if (!n)
 151         return 0;
 152     else if (n->op == sValue)
 153         return n->value;
 154     else if (n->op == sVariable)
 155         return fn(n->variable);
 156
 157     for (auto & opt : ops)
 158         if (opt.op == n->op)
 159             return opt.fn( eval(n->l, fn), eval(n->r, fn) );
 160
 161     panic("Invalid node!\n");
 162     return 0;
 163 }
 164
 165 std::string
 166 MathExpr::toStr(Node *n, std::string prefix) const {
 167     std::string ret;
 168     ret += prefix + "|-- " + n->toStr() + "\n";
 169     if (n->r)
 170         ret += toStr(n->r, prefix + "|   ");
 171     if (n->l)
 172         ret += toStr(n->l, prefix + "|   ");
 173     return ret;
 174 }
 175