mathexpr.cc revision 11527
12SN/A/* 21762SN/A * Copyright (c) 2016 ARM Limited 32SN/A * All rights reserved 42SN/A * 52SN/A * The license below extends only to copyright in the software and shall 62SN/A * not be construed as granting a license to any other intellectual 72SN/A * property including but not limited to intellectual property relating 82SN/A * to a hardware implementation of the functionality of the software 92SN/A * licensed hereunder. You may use the software subject to the license 102SN/A * terms below provided that you ensure that this notice is replicated 112SN/A * unmodified and in its entirety in all distributions of the software, 122SN/A * modified or unmodified, in source code or in binary form. 132SN/A * 142SN/A * Redistribution and use in source and binary forms, with or without 152SN/A * modification, are permitted provided that the following conditions are 162SN/A * met: redistributions of source code must retain the above copyright 172SN/A * notice, this list of conditions and the following disclaimer; 182SN/A * redistributions in binary form must reproduce the above copyright 192SN/A * notice, this list of conditions and the following disclaimer in the 202SN/A * documentation and/or other materials provided with the distribution; 212SN/A * neither the name of the copyright holders nor the names of its 222SN/A * contributors may be used to endorse or promote products derived from 232SN/A * this software without specific prior written permission. 242SN/A * 252SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 262SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 272665Ssaidi@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 282665Ssaidi@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 292665Ssaidi@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 302SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 312SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 322SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 332SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 342SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 352SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 362SN/A * 372SN/A * Authors: David Guillen Fandos 382SN/A */ 392SN/A 4056SN/A#include "sim/mathexpr.hh" 412SN/A 42229SN/A#include <algorithm> 43229SN/A#include <regex> 44229SN/A#include <string> 45229SN/A 46229SN/A#include "base/misc.hh" 47160SN/A 48160SN/AMathExpr::MathExpr(std::string expr) 49160SN/A : ops( 50160SN/A std::array<OpSearch, uNeg + 1> { 51160SN/A OpSearch {true, bAdd, 0, '+', [](double a, double b) { return a + b; }}, 52160SN/A OpSearch {true, bSub, 0, '-', [](double a, double b) { return a - b; }}, 53160SN/A OpSearch {true, bMul, 1, '*', [](double a, double b) { return a * b; }}, 54160SN/A OpSearch {true, bDiv, 1, '/', [](double a, double b) { return a / b; }}, 552SN/A OpSearch {false,uNeg, 2, '-', [](double a, double b) { return -b; }}, 562SN/A OpSearch {true, bPow, 3, '^', [](double a, double b) { 572SN/A return std::pow(a,b); } 58160SN/A }, 59160SN/A }) 60160SN/A{ 61160SN/A // Cleanup 622SN/A expr.erase(remove_if(expr.begin(), expr.end(), isspace), expr.end()); 632SN/A 64160SN/A root = MathExpr::parse(expr); 65160SN/A panic_if(!root, "Invalid expression\n"); 662SN/A} 672SN/A 68160SN/A/** 692SN/A * This function parses a string expression into an expression tree. 702SN/A * It will look for operators in priority order to recursively build the 712SN/A * tree, respecting parenthesization. 722SN/A * Constants can be expressed in any format accepted by std::stod, whereas 732SN/A * variables are essentially [A-Za-z0-9\.$\\]+ 74160SN/A */ 752SN/AMathExpr::Node * 762SN/AMathExpr::parse(std::string expr) { 77160SN/A if (expr.size() == 0) 782SN/A return NULL; 792SN/A 80160SN/A // From low to high priority 812SN/A int par = 0; 82160SN/A for (unsigned p = 0; p < MAX_PRIO; p++) { 83160SN/A for (int i = expr.size() - 1; i >= 0; i--) { 84160SN/A if (expr[i] == ')') 85160SN/A par++; 86160SN/A if (expr[i] == '(') 87160SN/A par--; 88160SN/A 892SN/A if (par < 0) return NULL; 902SN/A if (par > 0) continue; 91160SN/A 92160SN/A for (unsigned opt = 0; opt < ops.size(); opt++) { 93160SN/A if (ops[opt].priority != p) continue; 942SN/A if (ops[opt].c == expr[i]) { 952SN/A // Try to parse each side 96160SN/A Node *l = NULL; 972SN/A if (ops[opt].binary) 982SN/A l = parse(expr.substr(0, i)); 99160SN/A Node *r = parse(expr.substr(i + 1)); 100160SN/A if ((l && r) || (!ops[opt].binary && r)) { 1012SN/A // Match! 1022SN/A Node *n = new Node(); 103160SN/A n->op = ops[opt].op; 1042SN/A n->l = l; 1052SN/A n->r = r; 1062SN/A return n; 1072SN/A } 1082SN/A } 109160SN/A } 1102SN/A } 1112SN/A } 112160SN/A 113160SN/A // Remove trivial parenthesis 114160SN/A if (expr.size() >= 2 && expr[0] == '(' && expr[expr.size() - 1] == ')') 115160SN/A return parse(expr.substr(1, expr.size() - 2)); 116160SN/A 117160SN/A // Match a number 118160SN/A { 119160SN/A char *sptr; 120160SN/A double v = strtod(expr.c_str(), &sptr); 121160SN/A if (sptr != expr.c_str()) { 122160SN/A Node *n = new Node(); 123160SN/A n->op = sValue; 124160SN/A n->value = v; 125160SN/A return n; 126160SN/A } 127160SN/A } 1282SN/A 1292SN/A // Match a variable 130160SN/A { 131160SN/A bool contains_non_alpha = false; 132160SN/A for (auto & c: expr) 133160SN/A contains_non_alpha = contains_non_alpha or 134160SN/A !( (c >= 'a' && c <= 'z') || 1352SN/A (c >= 'A' && c <= 'Z') || 136160SN/A (c >= '0' && c <= '9') || 137160SN/A c == '$' || c == '\\' || c == '.' || c == '_'); 1382SN/A 1392SN/A if (!contains_non_alpha) { 1402SN/A Node * n = new Node(); 141160SN/A n->op = sVariable; 142160SN/A n->variable = expr; 1432SN/A return n; 1442SN/A } 145160SN/A } 146160SN/A 1472SN/A return NULL; 148160SN/A} 149160SN/A 150160SN/Adouble 1512SN/AMathExpr::eval(const Node *n, EvalCallback fn) const { 152160SN/A if (!n) 153160SN/A return 0; 154160SN/A else if (n->op == sValue) 1552SN/A return n->value; 1562SN/A else if (n->op == sVariable) 1572SN/A return fn(n->variable); 158160SN/A 1592SN/A for (auto & opt : ops) 160160SN/A if (opt.op == n->op) 161160SN/A return opt.fn( eval(n->l, fn), eval(n->r, fn) ); 1622SN/A 1632SN/A panic("Invalid node!\n"); 1641046SN/A return 0; 1651046SN/A} 1661046SN/A 1671046SN/Astd::string 1681046SN/AMathExpr::toStr(Node *n, std::string prefix) const { 1691046SN/A std::string ret; 170160SN/A ret += prefix + "|-- " + n->toStr() + "\n"; 171160SN/A if (n->r) 172160SN/A ret += toStr(n->r, prefix + "| "); 173160SN/A if (n->l) 174160SN/A ret += toStr(n->l, prefix + "| "); 175160SN/A return ret; 1762SN/A} 177160SN/A 178160SN/A