111527Sdavid.guillen@arm.com/* 211527Sdavid.guillen@arm.com * Copyright (c) 2016 ARM Limited 311527Sdavid.guillen@arm.com * All rights reserved 411527Sdavid.guillen@arm.com * 511527Sdavid.guillen@arm.com * The license below extends only to copyright in the software and shall 611527Sdavid.guillen@arm.com * not be construed as granting a license to any other intellectual 711527Sdavid.guillen@arm.com * property including but not limited to intellectual property relating 811527Sdavid.guillen@arm.com * to a hardware implementation of the functionality of the software 911527Sdavid.guillen@arm.com * licensed hereunder. You may use the software subject to the license 1011527Sdavid.guillen@arm.com * terms below provided that you ensure that this notice is replicated 1111527Sdavid.guillen@arm.com * unmodified and in its entirety in all distributions of the software, 1211527Sdavid.guillen@arm.com * modified or unmodified, in source code or in binary form. 1311527Sdavid.guillen@arm.com * 1411527Sdavid.guillen@arm.com * Redistribution and use in source and binary forms, with or without 1511527Sdavid.guillen@arm.com * modification, are permitted provided that the following conditions are 1611527Sdavid.guillen@arm.com * met: redistributions of source code must retain the above copyright 1711527Sdavid.guillen@arm.com * notice, this list of conditions and the following disclaimer; 1811527Sdavid.guillen@arm.com * redistributions in binary form must reproduce the above copyright 1911527Sdavid.guillen@arm.com * notice, this list of conditions and the following disclaimer in the 2011527Sdavid.guillen@arm.com * documentation and/or other materials provided with the distribution; 2111527Sdavid.guillen@arm.com * neither the name of the copyright holders nor the names of its 2211527Sdavid.guillen@arm.com * contributors may be used to endorse or promote products derived from 2311527Sdavid.guillen@arm.com * this software without specific prior written permission. 2411527Sdavid.guillen@arm.com * 2511527Sdavid.guillen@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2611527Sdavid.guillen@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2711527Sdavid.guillen@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2811527Sdavid.guillen@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2911527Sdavid.guillen@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3011527Sdavid.guillen@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3111527Sdavid.guillen@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3211527Sdavid.guillen@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3311527Sdavid.guillen@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3411527Sdavid.guillen@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3511527Sdavid.guillen@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3611527Sdavid.guillen@arm.com * 3711527Sdavid.guillen@arm.com * Authors: David Guillen Fandos 3811527Sdavid.guillen@arm.com */ 3911527Sdavid.guillen@arm.com 4011527Sdavid.guillen@arm.com#include "sim/mathexpr.hh" 4111527Sdavid.guillen@arm.com 4211527Sdavid.guillen@arm.com#include <algorithm> 4311532Sandreas.hansson@arm.com#include <cmath> 4411527Sdavid.guillen@arm.com#include <regex> 4511527Sdavid.guillen@arm.com#include <string> 4611527Sdavid.guillen@arm.com 4712334Sgabeblack@google.com#include "base/logging.hh" 4811527Sdavid.guillen@arm.com 4911527Sdavid.guillen@arm.comMathExpr::MathExpr(std::string expr) 5011527Sdavid.guillen@arm.com : ops( 5111532Sandreas.hansson@arm.com std::array<OpSearch, uNeg + 1> {{ 5211527Sdavid.guillen@arm.com OpSearch {true, bAdd, 0, '+', [](double a, double b) { return a + b; }}, 5311527Sdavid.guillen@arm.com OpSearch {true, bSub, 0, '-', [](double a, double b) { return a - b; }}, 5411527Sdavid.guillen@arm.com OpSearch {true, bMul, 1, '*', [](double a, double b) { return a * b; }}, 5511527Sdavid.guillen@arm.com OpSearch {true, bDiv, 1, '/', [](double a, double b) { return a / b; }}, 5611527Sdavid.guillen@arm.com OpSearch {false,uNeg, 2, '-', [](double a, double b) { return -b; }}, 5711527Sdavid.guillen@arm.com OpSearch {true, bPow, 3, '^', [](double a, double b) { 5811527Sdavid.guillen@arm.com return std::pow(a,b); } 5911532Sandreas.hansson@arm.com }}, 6011527Sdavid.guillen@arm.com }) 6111527Sdavid.guillen@arm.com{ 6211527Sdavid.guillen@arm.com // Cleanup 6311527Sdavid.guillen@arm.com expr.erase(remove_if(expr.begin(), expr.end(), isspace), expr.end()); 6411527Sdavid.guillen@arm.com 6511527Sdavid.guillen@arm.com root = MathExpr::parse(expr); 6611527Sdavid.guillen@arm.com panic_if(!root, "Invalid expression\n"); 6711527Sdavid.guillen@arm.com} 6811527Sdavid.guillen@arm.com 6911527Sdavid.guillen@arm.com/** 7011527Sdavid.guillen@arm.com * This function parses a string expression into an expression tree. 7111527Sdavid.guillen@arm.com * It will look for operators in priority order to recursively build the 7211527Sdavid.guillen@arm.com * tree, respecting parenthesization. 7311527Sdavid.guillen@arm.com * Constants can be expressed in any format accepted by std::stod, whereas 7411527Sdavid.guillen@arm.com * variables are essentially [A-Za-z0-9\.$\\]+ 7511527Sdavid.guillen@arm.com */ 7611527Sdavid.guillen@arm.comMathExpr::Node * 7711527Sdavid.guillen@arm.comMathExpr::parse(std::string expr) { 7811527Sdavid.guillen@arm.com if (expr.size() == 0) 7911527Sdavid.guillen@arm.com return NULL; 8011527Sdavid.guillen@arm.com 8111527Sdavid.guillen@arm.com // From low to high priority 8211527Sdavid.guillen@arm.com int par = 0; 8311527Sdavid.guillen@arm.com for (unsigned p = 0; p < MAX_PRIO; p++) { 8411527Sdavid.guillen@arm.com for (int i = expr.size() - 1; i >= 0; i--) { 8511527Sdavid.guillen@arm.com if (expr[i] == ')') 8611527Sdavid.guillen@arm.com par++; 8711527Sdavid.guillen@arm.com if (expr[i] == '(') 8811527Sdavid.guillen@arm.com par--; 8911527Sdavid.guillen@arm.com 9011527Sdavid.guillen@arm.com if (par < 0) return NULL; 9111527Sdavid.guillen@arm.com if (par > 0) continue; 9211527Sdavid.guillen@arm.com 9311527Sdavid.guillen@arm.com for (unsigned opt = 0; opt < ops.size(); opt++) { 9411527Sdavid.guillen@arm.com if (ops[opt].priority != p) continue; 9511527Sdavid.guillen@arm.com if (ops[opt].c == expr[i]) { 9611527Sdavid.guillen@arm.com // Try to parse each side 9711527Sdavid.guillen@arm.com Node *l = NULL; 9811527Sdavid.guillen@arm.com if (ops[opt].binary) 9911527Sdavid.guillen@arm.com l = parse(expr.substr(0, i)); 10011527Sdavid.guillen@arm.com Node *r = parse(expr.substr(i + 1)); 10111527Sdavid.guillen@arm.com if ((l && r) || (!ops[opt].binary && r)) { 10211527Sdavid.guillen@arm.com // Match! 10311527Sdavid.guillen@arm.com Node *n = new Node(); 10411527Sdavid.guillen@arm.com n->op = ops[opt].op; 10511527Sdavid.guillen@arm.com n->l = l; 10611527Sdavid.guillen@arm.com n->r = r; 10711527Sdavid.guillen@arm.com return n; 10811527Sdavid.guillen@arm.com } 10911527Sdavid.guillen@arm.com } 11011527Sdavid.guillen@arm.com } 11111527Sdavid.guillen@arm.com } 11211527Sdavid.guillen@arm.com } 11311527Sdavid.guillen@arm.com 11411527Sdavid.guillen@arm.com // Remove trivial parenthesis 11511527Sdavid.guillen@arm.com if (expr.size() >= 2 && expr[0] == '(' && expr[expr.size() - 1] == ')') 11611527Sdavid.guillen@arm.com return parse(expr.substr(1, expr.size() - 2)); 11711527Sdavid.guillen@arm.com 11811527Sdavid.guillen@arm.com // Match a number 11911527Sdavid.guillen@arm.com { 12011527Sdavid.guillen@arm.com char *sptr; 12111527Sdavid.guillen@arm.com double v = strtod(expr.c_str(), &sptr); 12211527Sdavid.guillen@arm.com if (sptr != expr.c_str()) { 12311527Sdavid.guillen@arm.com Node *n = new Node(); 12411527Sdavid.guillen@arm.com n->op = sValue; 12511527Sdavid.guillen@arm.com n->value = v; 12611527Sdavid.guillen@arm.com return n; 12711527Sdavid.guillen@arm.com } 12811527Sdavid.guillen@arm.com } 12911527Sdavid.guillen@arm.com 13011527Sdavid.guillen@arm.com // Match a variable 13111527Sdavid.guillen@arm.com { 13211527Sdavid.guillen@arm.com bool contains_non_alpha = false; 13311527Sdavid.guillen@arm.com for (auto & c: expr) 13411527Sdavid.guillen@arm.com contains_non_alpha = contains_non_alpha or 13511527Sdavid.guillen@arm.com !( (c >= 'a' && c <= 'z') || 13611527Sdavid.guillen@arm.com (c >= 'A' && c <= 'Z') || 13711527Sdavid.guillen@arm.com (c >= '0' && c <= '9') || 13811527Sdavid.guillen@arm.com c == '$' || c == '\\' || c == '.' || c == '_'); 13911527Sdavid.guillen@arm.com 14011527Sdavid.guillen@arm.com if (!contains_non_alpha) { 14111527Sdavid.guillen@arm.com Node * n = new Node(); 14211527Sdavid.guillen@arm.com n->op = sVariable; 14311527Sdavid.guillen@arm.com n->variable = expr; 14411527Sdavid.guillen@arm.com return n; 14511527Sdavid.guillen@arm.com } 14611527Sdavid.guillen@arm.com } 14711527Sdavid.guillen@arm.com 14811527Sdavid.guillen@arm.com return NULL; 14911527Sdavid.guillen@arm.com} 15011527Sdavid.guillen@arm.com 15111527Sdavid.guillen@arm.comdouble 15211527Sdavid.guillen@arm.comMathExpr::eval(const Node *n, EvalCallback fn) const { 15311527Sdavid.guillen@arm.com if (!n) 15411527Sdavid.guillen@arm.com return 0; 15511527Sdavid.guillen@arm.com else if (n->op == sValue) 15611527Sdavid.guillen@arm.com return n->value; 15711527Sdavid.guillen@arm.com else if (n->op == sVariable) 15811527Sdavid.guillen@arm.com return fn(n->variable); 15911527Sdavid.guillen@arm.com 16011527Sdavid.guillen@arm.com for (auto & opt : ops) 16111527Sdavid.guillen@arm.com if (opt.op == n->op) 16211527Sdavid.guillen@arm.com return opt.fn( eval(n->l, fn), eval(n->r, fn) ); 16311527Sdavid.guillen@arm.com 16411527Sdavid.guillen@arm.com panic("Invalid node!\n"); 16511527Sdavid.guillen@arm.com return 0; 16611527Sdavid.guillen@arm.com} 16711527Sdavid.guillen@arm.com 16811527Sdavid.guillen@arm.comstd::string 16911527Sdavid.guillen@arm.comMathExpr::toStr(Node *n, std::string prefix) const { 17011527Sdavid.guillen@arm.com std::string ret; 17111527Sdavid.guillen@arm.com ret += prefix + "|-- " + n->toStr() + "\n"; 17211527Sdavid.guillen@arm.com if (n->r) 17311527Sdavid.guillen@arm.com ret += toStr(n->r, prefix + "| "); 17411527Sdavid.guillen@arm.com if (n->l) 17511527Sdavid.guillen@arm.com ret += toStr(n->l, prefix + "| "); 17611527Sdavid.guillen@arm.com return ret; 17711527Sdavid.guillen@arm.com} 17811527Sdavid.guillen@arm.com 179