1 /************************************************************************
2 ************************************************************************
3 FAUST compiler
4 Copyright (C) 2003-2018 GRAME, Centre National de Creation Musicale
5 ---------------------------------------------------------------------
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 ************************************************************************
20 ************************************************************************/
21
22 #include "aterm.hh"
23 #include "ppsig.hh"
24 #include "sigtype.hh"
25
26 // static void collectMulTerms (Tree& coef, map<Tree,int>& M, Tree t, bool invflag=false);
27
28 #undef TRACE
29
30 using namespace std;
31
32 typedef map<Tree, mterm> SM;
33
aterm()34 aterm::aterm()
35 {
36 }
37
38 /**
39 * create a aterm from a tree expression
40 */
aterm(Tree t)41 aterm::aterm(Tree t)
42 {
43 #ifdef TRACE
44 cerr << "aterm::aterm (" << ppsig(t) << ")" << endl;
45 #endif
46 *this += t;
47 #ifdef TRACE
48 cerr << "aterm::aterm (" << ppsig(t) << ") : -> " << *this << endl;
49 #endif
50 }
51
52 /**
53 * Add two terms trying to simplify the result
54 */
simplifyingAdd(Tree t1,Tree t2)55 static Tree simplifyingAdd(Tree t1, Tree t2)
56 {
57 faustassert(t1 != 0);
58 faustassert(t2 != 0);
59
60 if (isNum(t1) && isNum(t2)) {
61 return addNums(t1, t2);
62
63 } else if (isZero(t1)) {
64 return t2;
65
66 } else if (isZero(t2)) {
67 return t1;
68
69 } else if (t1->serial() <= t2->serial()) {
70 return sigAdd(t1, t2);
71
72 } else {
73 return sigAdd(t2, t1);
74 }
75 }
76
77 /**
78 * return the corresponding normalized expression tree
79 */
80
81 /*====================================================
82
83 addTermsWithSign:
84
85 (s1 v1 s2 v2) -> (s3 v3)
86
87 (s1 0 s2 v2) -> (s2 v2)
88 (s1 v1 s2 0) -> (s1 v1)
89 (+ v1 + v2) -> (+ (v1+v2))
90 (+ v1 - v2) -> (+ (v1-v2))
91 (- v1 + v2) -> (+ (v2-v1))
92 (- v1 - v2) -> (- (v1+v2))
93
94 */
95
addTermsWithSign(bool p1,Tree v1,bool p2,Tree v2,bool & p3,Tree & v3)96 static void addTermsWithSign(bool p1, Tree v1, bool p2, Tree v2, bool& p3, Tree& v3)
97 {
98 if (isZero(v1)) {
99 p3 = p2;
100 v3 = v2;
101 return;
102 }
103 if (isZero(v2)) {
104 p3 = p1;
105 v3 = v1;
106 return;
107 }
108 if (p1 && p2) {
109 p3 = true;
110 v3 = sigAdd(v1, v2);
111 return;
112 }
113 if (p1) {
114 p3 = true;
115 v3 = sigSub(v1, v2);
116 return;
117 }
118 if (p2) {
119 p3 = true;
120 v3 = sigSub(v2, v1);
121 return;
122 } else {
123 p3 = false;
124 v3 = sigAdd(v1, v2);
125 return;
126 }
127 }
128
normalizedTree() const129 Tree aterm::normalizedTree() const
130 {
131 // store positive and negative tems by order and sign
132 // positive terms are stored in P[]
133 // negative terms are inverted (made positive) and stored in N[]
134 Tree P[4], N[4];
135 bool hasPositiveTerm = false;
136 bool hasNegativeTerm = false;
137
138 // prepare
139 for (int order = 0; order < 4; order++) P[order] = N[order] = tree(0);
140
141 // sum by order and sign
142 for (SM::const_iterator p = fSig2MTerms.begin(); p != fSig2MTerms.end(); p++) {
143 const mterm& m = p->second;
144 if (m.isNegative()) {
145 Tree t = m.normalizedTree(false, true);
146 int order = getSigOrder(t);
147 N[order] = simplifyingAdd(N[order], t);
148 hasNegativeTerm = true;
149 } else {
150 Tree t = m.normalizedTree();
151 int order = getSigOrder(t);
152 P[order] = simplifyingAdd(P[order], t);
153 hasPositiveTerm = true;
154 }
155 }
156
157 Tree SUM = subNums(P[0], N[0]);
158 bool signe = true;
159 Tree R;
160 bool s;
161
162 for (int order = 3; order > 0; order--) {
163 addTermsWithSign(false, N[order], signe, SUM, s, R);
164 signe = s;
165 SUM = R;
166
167 addTermsWithSign(true, P[order], signe, SUM, s, R);
168 signe = s;
169 SUM = R;
170 }
171
172 if (!signe) {
173 AudioType* ty = (AudioType*)SUM->getType();
174 Tree zero = (ty && ty->nature() == kReal) ? sigReal(0.0) : sigInt(0);
175
176 SUM = sigSub(zero, SUM);
177 }
178 #ifdef TRACE
179 cerr << __LINE__ << ":" << __FUNCTION__ << "(" << *this << ") ---> " << ppsig(SUM) << endl;
180 #endif
181 return SUM;
182 }
183
184 /**
185 * Print an aterm in a human readable format
186 */
print(ostream & dst) const187 ostream& aterm::print(ostream& dst) const
188 {
189 if (fSig2MTerms.empty()) {
190 dst << "AZERO";
191 } else {
192 const char* sep = "";
193 for (SM::const_iterator p = fSig2MTerms.begin(); p != fSig2MTerms.end(); p++) {
194 dst << sep << p->second;
195 sep = " + ";
196 }
197 }
198
199 return dst;
200 }
201
202 /**
203 * Add in place an additive expression tree. Go down recursively looking
204 * for additions and substractions
205 */
operator +=(Tree t)206 const aterm& aterm::operator+=(Tree t)
207 {
208 int op;
209 Tree x, y;
210
211 faustassert(t != 0);
212
213 if (isSigBinOp(t, &op, x, y) && (op == kAdd)) {
214 *this += x;
215 *this += y;
216
217 } else if (isSigBinOp(t, &op, x, y) && (op == kSub)) {
218 *this += x;
219 *this -= y;
220
221 } else {
222 mterm m(t);
223 *this += m;
224 }
225 return *this;
226 }
227
228 /**
229 * Substract in place an additive expression tree. Go down to recursively looking
230 * for additions and substractions
231 */
operator -=(Tree t)232 const aterm& aterm::operator-=(Tree t)
233 {
234 int op;
235 Tree x, y;
236
237 faustassert(t != 0);
238
239 if (isSigBinOp(t, &op, x, y) && (op == kAdd)) {
240 *this -= x;
241 *this -= y;
242
243 } else if (isSigBinOp(t, &op, x, y) && (op == kSub)) {
244 *this -= x;
245 *this += y;
246
247 } else {
248 mterm m(t);
249 *this -= m;
250 }
251 return *this;
252 }
253
254 /**
255 * Add in place an mterm
256 */
operator +=(const mterm & m)257 const aterm& aterm::operator+=(const mterm& m)
258 {
259 #ifdef TRACE
260 cerr << *this << " aterm::+= " << m << endl;
261 #endif
262 Tree signature = m.signatureTree();
263 #ifdef TRACE
264 cerr << "signature " << *signature << endl;
265 #endif
266 SM::const_iterator p = fSig2MTerms.find(signature);
267 if (p == fSig2MTerms.end()) {
268 // its a new mterm
269 fSig2MTerms.insert(make_pair(signature, m));
270 } else {
271 // we already have a mterm of same signature, we add them together
272 fSig2MTerms[signature] += m;
273 }
274 return *this;
275 }
276
277 /**
278 * Substract in place an mterm
279 */
operator -=(const mterm & m)280 const aterm& aterm::operator-=(const mterm& m)
281 {
282 // cerr << *this << " aterm::-= " << m << endl;
283 Tree sig = m.signatureTree();
284 // cerr << "signature " << *sig << endl;
285 SM::const_iterator p = fSig2MTerms.find(sig);
286 if (p == fSig2MTerms.end()) {
287 // its a new mterm
288 fSig2MTerms.insert(make_pair(sig, m * mterm(-1)));
289 } else {
290 fSig2MTerms[sig] -= m;
291 }
292 return *this;
293 }
294
greatestDivisor() const295 mterm aterm::greatestDivisor() const
296 {
297 int maxComplexity = 0;
298 mterm maxGCD(1);
299 // cerr << "greatestDivisor of " << *this << endl;
300
301 for (SM::const_iterator p1 = fSig2MTerms.begin(); p1 != fSig2MTerms.end(); p1++) {
302 for (SM::const_iterator p2 = p1; p2 != fSig2MTerms.end(); p2++) {
303 if (p2 != p1) {
304 mterm g = gcd(p1->second, p2->second);
305 // cerr << "TRYING " << g << " of complexity " << g.complexity() << " (max complexity so far " <<
306 // maxComplexity << ")" << endl;
307 if (g.complexity() > maxComplexity) {
308 maxComplexity = g.complexity();
309 maxGCD = g;
310 }
311 }
312 }
313 }
314 // cerr << "greatestDivisor of " << *this << " --> " << maxGCD << endl;
315 return maxGCD;
316 }
317
318 /**
319 * Reorganize the aterm by factorizing d
320 */
factorize(const mterm & d)321 aterm aterm::factorize(const mterm& d)
322 {
323 // cerr << "factorize : " << *this << " with " << d << endl;
324 aterm A;
325 aterm Q;
326
327 // separate the multiple of m from the others
328 for (SM::const_iterator p1 = fSig2MTerms.begin(); p1 != fSig2MTerms.end(); p1++) {
329 mterm t = p1->second;
330 if (t.hasDivisor(d)) {
331 mterm q = t / d;
332 // cerr << "q = " << q << endl;
333 Q += q;
334 // cerr << "step Q = " << Q << endl;
335 } else {
336 A += t;
337 // cerr << "step A = " << A << endl;
338 }
339 }
340
341 // combines the two parts
342 // cerr << "d.normalizedTree() " << ppsig(d.normalizedTree()) << endl;
343 // cerr << "Q.normalizedTree() " << ppsig(Q.normalizedTree()) << endl;
344 // Tree tt = sigMul(d.normalizedTree(), Q.normalizedTree());
345 // cerr << "tt " << *tt << endl;
346
347 // Tree ttt = sigAdd(
348 A += sigMul(d.normalizedTree(), Q.normalizedTree());
349 // cerr << "Final A = " << A << endl;
350 // cerr << "Final Tree " << *(A.normalizedTree()) << endl;
351 return A;
352 }
353