X-Git-Url: https://scm.cri.ensmp.fr/git/Faustine.git/blobdiff_plain/c7f552fd8888da2f0d8cfb228fe0f28d3df3a12c..b4b6f2ea75b9f0f3ca918f5b84016610bf7a4d4f:/interpretor/preprocessor/faust-0.9.47mr3/compiler/normalize/aterm.cpp diff --git a/interpretor/preprocessor/faust-0.9.47mr3/compiler/normalize/aterm.cpp b/interpretor/preprocessor/faust-0.9.47mr3/compiler/normalize/aterm.cpp new file mode 100644 index 0000000..18f7cb5 --- /dev/null +++ b/interpretor/preprocessor/faust-0.9.47mr3/compiler/normalize/aterm.cpp @@ -0,0 +1,275 @@ +#include "aterm.hh" +#include "ppsig.hh" +//static void collectMulTerms (Tree& coef, map& M, Tree t, bool invflag=false); + +#undef TRACE + +using namespace std; + +typedef map SM; + +aterm::aterm () +{} + + +/** + * create a aterm from a tree expression + */ +aterm::aterm (Tree t) +{ + #ifdef TRACE + cerr << "aterm::aterm (" << ppsig(t)<< ")" << endl; + #endif + *this += t; + #ifdef TRACE + cerr << "aterm::aterm (" << ppsig(t)<< ") : -> " << *this << endl; + #endif +} + + +/** + * Add two terms trying to simplify the result + */ +static Tree simplifyingAdd(Tree t1, Tree t2) +{ + assert(t1!=0); + assert(t2!=0); + + if (isNum(t1) && isNum(t2)) { + return addNums(t1,t2); + + } else if (isZero(t1)) { + return t2; + + } else if (isZero(t2)) { + return t1; + + } else if (t1 <= t2) { + return sigAdd(t1, t2); + + } else { + return sigAdd(t2, t1); + } +} + +/** + * return the corresponding normalized expression tree + */ + +Tree aterm::normalizedTree() const +{ + // store positive and negative tems by order and sign + // positive terms are stored in P[] + // negative terms are inverted (made positive) and stored in N[] + Tree P[4], N[4]; + + // prepare + for (int order = 0; order < 4; order++) P[order] = N[order] = tree(0); + + // sum by order and sign + for (SM::const_iterator p = fSig2MTerms.begin(); p != fSig2MTerms.end(); p++) { + const mterm& m = p->second; + if (m.isNegative()) { + Tree t = m.normalizedTree(false, true); + int order = getSigOrder(t); + N[order] = simplifyingAdd(N[order],t); + } else { + Tree t = m.normalizedTree(); + int order = getSigOrder(t); + P[order] = simplifyingAdd(P[order],t); + } + } + + // combine sums + Tree SUM = tree(0); + for (int order = 0; order < 4; order++) { + if (!isZero(P[order])) { + SUM = simplifyingAdd(SUM,P[order]); + } + if (!isZero(N[order])) { // we have to substract + if (isZero(SUM) && (order < 3)) { + // we postpone substraction + N[order+1] = simplifyingAdd(N[order], N[order+1]); + } else { + SUM = sigSub(SUM, N[order]); + } + } + } + + assert(SUM); + return SUM; +} + + +/** + * print an aterm in a human readable format + */ +ostream& aterm::print(ostream& dst) const +{ + if (fSig2MTerms.empty()) { + dst << "AZERO"; + } else { + const char* sep = ""; + for (SM::const_iterator p = fSig2MTerms.begin(); p != fSig2MTerms.end(); p++) { + dst << sep << p->second; + sep = " + "; + } + } + + return dst; +} + + +/** + * Add in place an additive expression tree Go down t recursively looking + * for additions and substractions + */ +const aterm& aterm::operator += (Tree t) +{ + int op; + Tree x,y; + + assert(t!=0); + + if (isSigBinOp(t, &op, x, y) && (op == kAdd)) { + *this += x; + *this += y; + + } else if (isSigBinOp(t, &op, x, y) && (op == kSub)) { + *this += x; + *this -= y; + + } else { + mterm m(t); + *this += m; + } + return *this; +} + + +/** + * Substract in place an additive expression tree Go down t recursively looking + * for additions and substractions + */ +const aterm& aterm::operator -= (Tree t) +{ + int op; + Tree x,y; + + assert(t!=0); + + if (isSigBinOp(t, &op, x, y) && (op == kAdd)) { + *this -= x; + *this -= y; + + } else if (isSigBinOp(t, &op, x, y) && (op == kSub)) { + *this -= x; + *this += y; + + } else { + mterm m(t); + *this -= m; + } + return *this; +} + + +/** + * Add in place an mterm + */ +const aterm& aterm::operator += (const mterm& m) +{ + #ifdef TRACE + cerr << *this << " aterm::+= " << m << endl; + #endif + Tree sig = m.signatureTree(); + #ifdef TRACE + cerr << "signature " << *sig << endl; + #endif + SM::const_iterator p = fSig2MTerms.find(sig); + if (p == fSig2MTerms.end()) { + // its a new mterm + fSig2MTerms.insert(make_pair(sig,m)); + } else { + fSig2MTerms[sig] += m; + } + return *this; +} + + +/** + * Substract in place an mterm + */ +const aterm& aterm::operator -= (const mterm& m) +{ + //cerr << *this << " aterm::-= " << m << endl; + Tree sig = m.signatureTree(); + //cerr << "signature " << *sig << endl; + SM::const_iterator p = fSig2MTerms.find(sig); + if (p == fSig2MTerms.end()) { + // its a new mterm + fSig2MTerms.insert(make_pair(sig,m*mterm(-1))); + } else { + fSig2MTerms[sig] -= m; + } + return *this; +} + +mterm aterm::greatestDivisor() const +{ + int maxComplexity = 0; + mterm maxGCD(1); + + for (SM::const_iterator p1 = fSig2MTerms.begin(); p1 != fSig2MTerms.end(); p1++) { + for (SM::const_iterator p2 = p1; p2 != fSig2MTerms.end(); p2++) { + if (p2 != p1) { + mterm g = gcd(p1->second,p2->second); + if (g.complexity()>maxComplexity) { + maxComplexity = g.complexity(); + maxGCD = g; + } + } + } + } + //cerr << "greatestDivisor of " << *this << " is " << maxGCD << endl; + return maxGCD; +} + +/** + * reorganize the aterm by factorizing d + */ +aterm aterm::factorize(const mterm& d) +{ + //cerr << "factorize : " << *this << " with " << d << endl; + aterm A; + aterm Q; + + // separate the multiple of m from the others + for (SM::const_iterator p1 = fSig2MTerms.begin(); p1 != fSig2MTerms.end(); p1++) { + mterm t = p1->second; + if (t.hasDivisor(d)) { + mterm q = t/d; + //cerr << "q = " << q << endl; + Q += q; + //cerr << "step Q = " << Q << endl; + } else { + A += t; + //cerr << "step A = " << A << endl; + } + } + + // combines the two parts + //cerr << "d.normalizedTree() " << ppsig(d.normalizedTree()) << endl; + //cerr << "Q.normalizedTree() " << ppsig(Q.normalizedTree()) << endl; + //Tree tt = sigMul(d.normalizedTree(), Q.normalizedTree()); + //cerr << "tt " << *tt << endl; + + //Tree ttt = sigAdd( + A += sigMul(d.normalizedTree(), Q.normalizedTree()); + //cerr << "Final A = " << A << endl; + //cerr << "Final Tree " << *(A.normalizedTree()) << endl; + return A; +} + + +