00001 #include <stdio.h>
00002 #include <assert.h>
00003 #include "tlib.hh"
00004 #include "signals.hh"
00005 #include "sigprint.hh"
00006 #include "simplify.hh"
00007 #include "normalize.hh"
00008 #include "sigorderrules.hh"
00009 #include <map>
00010 #include <list>
00011
00012 static void countAddTerm (map<Tree,Tree>& M, Tree t, bool invflag);
00013 static void incTermCount (map<Tree,int>& M, Tree t, bool invflag);
00014 static Tree buildPowTerm (Tree f, int q);
00015 static Tree simplifyingAdd (Tree t1, Tree t2);
00016 static Tree simplifyingMul (Tree t1, Tree t2);
00017 static Tree simplifyingReorganizingMul(Tree t1, Tree t2);
00018 static Tree reorganizingMul(Tree k, Tree t);
00019 static void factorizeAddTerm(map<Tree,Tree>& M);
00020
00021 #undef TRACE
00022
00028 Tree normalizeAddTerm(Tree t)
00029 {
00030 #ifdef TRACE
00031 fprintf(stderr, "START ADD Normalize of : "); printSignal(t, stderr); fputs("\n", stderr);
00032 #endif
00033 assert(t!=0);
00034 map<Tree,Tree> M;
00035 Tree coef = tree(0);
00036 collectAddTerms(coef, M, t, false);
00037 factorizeAddTerm(M);
00038 Tree result = buildAddTerm(coef, M);
00039 #ifdef TRACE
00040 fprintf(stderr, "END ADD Normalize -> "); printSignal(result, stderr); fputs("\n", stderr);
00041 #endif
00042 return result;
00043 }
00044
00045
00051 Tree normalizeMulTerm(Tree t)
00052 {
00053 assert(t!=0);
00054 #ifdef TRACE
00055 fprintf(stderr, "START MUL Normalize of : "); printSignal(t, stderr); fputs("\n", stderr);
00056 #endif
00057
00058 map<Tree,int> M;
00059 Tree coef = tree(1);
00060 collectMulTerms(coef, M, t, false);
00061 Tree result = buildMulTerm(coef, M);
00062 #ifdef TRACE
00063 fprintf(stderr, "END MUL Normalize -> "); printSignal(result, stderr); fputs("\n", stderr);
00064 #endif
00065 return result;
00066 }
00067
00068
00073 void collectAddTerms (Tree& coef, map<Tree,Tree>& M, Tree t, bool invflag)
00074 {
00075 int op;
00076 Tree x,y;
00077
00078 assert(t!=0);
00079 if (isSigBinOp(t, &op, x, y) && (op == kAdd)) {
00080 collectAddTerms(coef, M, x, invflag);
00081 collectAddTerms(coef, M, y, invflag);
00082 } else if (isSigBinOp(t, &op, x, y) && (op == kSub)) {
00083 collectAddTerms(coef, M, x, invflag);
00084 collectAddTerms(coef, M, y, !invflag);
00085 } else if (isNum(t)) {
00086 coef = (invflag) ? subNums(coef,t) : addNums(coef,t);
00087 } else {
00088 countAddTerm(M, normalizeMulTerm(t), invflag);
00089 }
00090 }
00091
00092
00096 void collectMulTerms (Tree& coef, map<Tree,int>& M, Tree t, bool invflag)
00097 {
00098 int op;
00099 Tree x,y;
00100
00101 assert(t!=0);
00102
00103 if (isSigBinOp(t, &op, x, y) && (op == kMul)) {
00104 collectMulTerms(coef, M, x, invflag);
00105 collectMulTerms(coef, M, y, invflag);
00106
00107 } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) {
00108 collectMulTerms(coef, M, x, invflag);
00109 collectMulTerms(coef, M, y, !invflag);
00110
00111
00112 } else if (isSigBinOp(t, &op, x, y) && (op == kSub) && isZero(x)) {
00113
00114 coef = minusNum(coef);
00115 collectMulTerms(coef, M, y, invflag);
00116
00117 } else if (isNum(t)) {
00118 coef = (invflag) ? divExtendedNums(coef,t) : mulNums(coef,t);
00119
00120 } else {
00121 #if 0
00122
00123 int op;
00124 Tree x,y;
00125 if (isSigBinOp(t, &op, x, y) && ((op == kAdd) || (op == kSub))) {
00126 t = normalizeAddTerm(t);
00127 }
00128 #endif
00129 incTermCount(M,t,invflag);
00130 }
00131 }
00132
00136 static void flatListTerms(int op, vector<Tree>& v, Tree t)
00137 {
00138 Tree x, y;
00139 int opcode;
00140
00141
00142 assert(t);
00143
00144 if (isSigBinOp(t, &opcode, x, y) && opcode==op) {
00145 flatListTerms(op,v,x); flatListTerms(op,v,y);
00146 } else {
00147 v.push_back(t);
00148 }
00149 }
00150
00151
00156 static Tree buildMidBalancedTerm(int op, vector<Tree>& v, int lo, int hi)
00157 {
00158 int q = hi-lo;
00159 assert(q>0);
00160 if (q == 1) {
00161 assert(lo < int(v.size()));
00162 return v[lo];
00163 } else {
00164 int mi = (hi+lo)/2;
00165 return sigBinOp( op, buildMidBalancedTerm(op,v,lo,mi), buildMidBalancedTerm(op,v,mi,hi) );
00166 }
00167 }
00168
00173 static Tree buildRightBalancedTerm(int op, vector<Tree>& v, int lo, int hi)
00174 {
00175 int q = hi-lo;
00176 assert(q>0);
00177 if (q == 1) {
00178 assert(lo < int(v.size()));
00179 return v[lo];
00180 } else {
00181 return sigBinOp( op, v[lo], buildRightBalancedTerm(op,v,lo+1,hi));
00182 }
00183 }
00184
00189 static Tree buildLeftBalancedTerm(int op, vector<Tree>& v, int lo, int hi)
00190 {
00191 int q = hi-lo;
00192 assert(q>0);
00193 if (q == 1) {
00194 assert(lo < int(v.size()));
00195 return v[lo];
00196 } else {
00197 return sigBinOp( op, buildLeftBalancedTerm(op,v,lo,hi-1), v[hi-1]);
00198 }
00199 }
00200
00201
00205 extern int gBalancedSwitch;
00206
00207 static Tree balanceTerm(int op, Tree t)
00208 {
00209
00210 vector<Tree> v;
00211
00212 flatListTerms(op, v, t);
00213 if (v.size() == 0) {
00214 return t;
00215 } else {
00216 switch (gBalancedSwitch) {
00217 case 0 : return buildLeftBalancedTerm(op, v, 0, v.size());
00218 case 1 : return buildMidBalancedTerm(op, v, 0, v.size());
00219 case 2 : return buildRightBalancedTerm(op, v, 0, v.size());
00220
00221 default: return buildLeftBalancedTerm(op, v, 0, v.size());
00222 }
00223 }
00224 }
00225
00230 Tree buildAddTerm(Tree k, map<Tree,Tree>& M)
00231 {
00232 Tree pt, nt;
00233
00234 assert(k!=0);
00235
00236 if (isGEZero(k)) {
00237 pt = k; nt = tree(0);
00238 } else {
00239 pt = tree(0); nt = minusNum(k);
00240 }
00241
00242 for (int order = 0; order < 4; order++) {
00243
00244 for (map<Tree,Tree>::iterator F = M.begin(); F != M.end(); F++) {
00245 Tree f = F->first;
00246 Tree q = F->second;
00247
00248 if (getSigOrder(f)==order) {
00249 if (isGEZero(q)) {
00250 pt = simplifyingAdd(pt, simplifyingReorganizingMul(q,f));
00251 } else {
00252 nt = simplifyingAdd(nt, simplifyingReorganizingMul(minusNum(q),f));
00253 }
00254 }
00255 }
00256 }
00257
00258 if (isZero(nt)) {
00259 return balanceTerm(kAdd, pt);
00260 } else {
00261 return sigSub(balanceTerm(kAdd, pt),balanceTerm(kAdd, nt));
00262 }
00263 }
00264
00265
00270 Tree buildMulTerm(Tree k, map<Tree,int>& M)
00271 {
00272 assert(k!=0);
00273 Tree t = tree(1.0f);
00274
00275 for (int order = 0; order < 4; order++) {
00276
00277 for (map<Tree,int>::iterator F = M.begin(); F != M.end(); F++) {
00278 Tree f = F->first;
00279 int q = F->second;
00280
00281 if (getSigOrder(f)==order) {
00282
00283 if (q > 0) {
00284 t = simplifyingMul(t, buildPowTerm(f,q));
00285 } else if (q < 0) {
00286 t = sigDiv(t, buildPowTerm(f,-q));
00287 } else {
00288
00289 }
00290 }
00291 }
00292 }
00293
00294
00295 return simplifyingMul(k, balanceTerm(kMul,t));
00296 }
00297
00298
00302 static void countAddTerm(map<Tree,Tree>& M, Tree t, bool invflag)
00303 {
00304 assert(t!=0);
00305 Tree k, F;
00306 if (isSigMul(t, k, F) && isNum(k)) {
00307
00308 } else {
00309 k = tree(1);
00310 F = t;
00311 }
00312 if (invflag) { k = minusNum(k); }
00313 if (M.find(F) == M.end()) {
00314 M[F] = k;
00315 } else {
00316 M[F] = addNums(M[F],k);
00317 }
00318 #ifdef TRACE
00319 fprintf(stderr, "countAddTerm of ");
00320 printSignal(F, stderr);
00321 fprintf(stderr, " is ");
00322 printSignal(M[F], stderr);
00323 fprintf(stderr, "\n");
00324 #endif
00325 }
00326
00327
00331 static void incTermCount(map<Tree,int>& M, Tree t, bool invflag)
00332 {
00333 assert(t!=0);
00334 int c = (invflag) ? -1 : 1;
00335 if (M.find(t) == M.end()) {
00336 M[t] = c;
00337 } else {
00338 M[t] += c;
00339 }
00340 #ifdef TRACE
00341 fprintf(stderr, "mult term coef of ");
00342 printSignal(t, stderr);
00343 fprintf(stderr, " is *(%d) \n", M[t]);
00344 #endif
00345
00346 }
00347
00348
00349 static Tree buildPowTerm(Tree f, int q)
00350 {
00351 assert(f!=0);
00352 assert(q>0);
00353 Tree r = f;
00354 for (int c=2; c<=q; c++) { r = sigMul(r,f); }
00355 return r;
00356 }
00357
00358
00359 static Tree simplifyingAdd(Tree t1, Tree t2)
00360 {
00361 assert(t1!=0);
00362 assert(t2!=0);
00363
00364 if (isNum(t1) && isNum(t2)) {
00365 return addNums(t1,t2);
00366
00367 } else if (isZero(t1)) {
00368 return t2;
00369
00370 } else if (isZero(t2)) {
00371 return t1;
00372
00373 } else if (t1 <= t2) {
00374 return sigAdd(t1, t2);
00375
00376 } else {
00377 return sigAdd(t2, t1);
00378 }
00379 }
00380
00381 static Tree reorganizingMul(Tree k, Tree t)
00382 {
00383 Tree x,y;
00384
00385 if (isNum(k) && isNum(t)) {
00386 #ifdef TRACE
00387 cerr << *k << " [[0]] " << *t << endl;
00388 #endif
00389 return mulNums(k,t);
00390
00391 } else if (isSigMul(t,x,y)) {
00392 #ifdef TRACE
00393 cerr << " [[1]] " << endl;
00394 #endif
00395 return sigMul(reorganizingMul(k,x),y);
00396 } else if (isSigDiv(t,x,y)) {
00397 #ifdef TRACE
00398 cerr << *k << " [[2]] " << *t << endl;
00399 #endif
00400 return sigDiv(reorganizingMul(k,x),y);
00401 } else {
00402 #ifdef TRACE
00403 cerr << " [[end]] " << endl;
00404 #endif
00405 return sigMul(k,t);
00406 }
00407 }
00408
00409 static Tree simplifyingReorganizingMul(Tree t1, Tree t2)
00410 {
00411 assert(t1!=0);
00412 assert(t2!=0);
00413 #ifdef TRACE
00414 fprintf(stderr, "simplifying reorganizing Mul of ");
00415 printSignal(t1, stderr);
00416 fprintf(stderr, " and ");
00417 printSignal(t2, stderr);
00418 fprintf(stderr, " -> ");
00419 #endif
00420
00421 Tree result,x,y;
00422
00423 if (isNum(t1) && isNum(t2)) {
00424 #ifdef TRACE
00425 fprintf(stderr, " [1] ");
00426 #endif
00427 result = mulNums(t1,t2);
00428
00429 } else {
00430
00431 if (isNum(t2)) {
00432 Tree tmp = t1; t1 = t2; t2 = tmp;
00433 }
00434
00435 if (isNum(t1)) {
00436 if (isZero(t1)) {
00437 #ifdef TRACE
00438 fprintf(stderr, " [2] ");
00439 #endif
00440 result = t1;
00441
00442 } else if (isOne(t1)) {
00443 #ifdef TRACE
00444 fprintf(stderr, " [3] ");
00445 #endif
00446 result = t2;
00447
00448 } else if (isSigDiv(t2,x,y) && isNum(x)){
00449 #ifdef TRACE
00450 fprintf(stderr, " [4a] ");
00451 #endif
00452 result = sigDiv(simplifyingReorganizingMul(t1,x),y);
00453
00454 } else {
00455 #ifdef TRACE
00456 fprintf(stderr, " [4b] ");
00457 #endif
00458 result = reorganizingMul(t1,t2);
00459 }
00460
00461 } else {
00462 #ifdef TRACE
00463 fprintf(stderr, " [5] ");
00464 #endif
00465 result = sigMul(t1, t2);
00466 }
00467 }
00468 #ifdef TRACE
00469 printSignal(result, stderr);
00470 fprintf(stderr, " \n ");
00471 #endif
00472 return result;
00473 }
00474
00475
00476
00477 static Tree simplifyingMul(Tree t1, Tree t2)
00478 {
00479 assert(t1!=0);
00480 assert(t2!=0);
00481 #ifdef TRACE
00482 fprintf(stderr, "simplifying mult of ");
00483 printSignal(t1, stderr);
00484 fprintf(stderr, " and ");
00485 printSignal(t2, stderr);
00486 fprintf(stderr, " -> ");
00487 #endif
00488
00489 Tree result;
00490
00491 if (isNum(t1) && isNum(t2)) {
00492
00493 result = mulNums(t1,t2);
00494
00495 } else if (isZero(t1) || isZero(t2)) {
00496
00497 result = tree(0);
00498
00499 } else if (isOne(t1)) {
00500
00501 result = t2;
00502
00503 } else if (isOne(t2)) {
00504
00505 result = t1;
00506
00507 } else {
00508
00509 result = sigMul(t1, t2);
00510 }
00511
00512
00513 return result;
00514 }
00515
00516 typedef map<Tree,int> MT;
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00578 static void factorizeAddTerm(map<Tree,Tree>& MAT)
00579 {
00580 map<Tree,Tree> INV;
00581 bool run;
00582 int factorCount = 0;
00583
00584 do {
00585 run = false;
00586
00587
00588 INV.clear();
00589 for (map<Tree,Tree>::iterator i = MAT.begin(); i != MAT.end(); i++)
00590 {
00591 Tree f = i->first;
00592 Tree q = i->second;
00593
00594 if (INV.find(q) == INV.end()) {
00595 INV[q] = f;
00596 } else {
00597 INV[q] = simplifyingAdd(INV[q], f);
00598 #ifdef TRACE
00599 fprintf(stderr, "factor of : ");
00600 printSignal(q, stderr);
00601 fprintf(stderr, " is now : ");
00602 printSignal(INV[q], stderr);
00603 fputs("\n", stderr);
00604 #endif
00605 factorCount++;
00606 }
00607 }
00608
00609
00610 MAT.clear();
00611
00612 for (map<Tree,Tree>::iterator i = INV.begin(); i != INV.end(); i++)
00613 {
00614 Tree f = i->first;
00615 Tree q = i->second;
00616
00617 if (MAT.find(q) == MAT.end()) {
00618 MAT[q] = f;
00619 } else {
00620 MAT[q] = simplifyingAdd(MAT[q], f);
00621 factorCount++;
00622 run = true;
00623 }
00624 }
00625
00626 } while (run);
00627
00628
00629
00630
00631 }
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659
00660
00661
00662
00663
00664
00665
00666
00667
00668
00669
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
00698
00699
00700
00701
00702
00703
00704
00705
00706
00707
00717 Tree normalizeDelay1Term(Tree s)
00718 {
00719 return normalizeFixedDelayTerm(s, tree(1));
00720 }
00721
00722 Tree XXXnormalizeDelay1Term(Tree s)
00723 {
00724 Tree x, y;
00725
00726 if (isZero(s)) {
00727
00728 return s;
00729
00730 } else if (isSigMul(s, x, y)) {
00731
00732 if (getSigOrder(x) < 2) {
00733 return simplify(sigMul(x,normalizeDelay1Term(y)));
00734 } else if (getSigOrder(y) < 2) {
00735 return simplify(sigMul(y,normalizeDelay1Term(x)));
00736 } else {
00737 return sigDelay1(s);
00738 }
00739
00740 } else if (isSigDiv(s, x, y)) {
00741
00742 if (getSigOrder(y) < 2) {
00743 return simplify(sigDiv(normalizeDelay1Term(x),y));
00744 } else {
00745 return sigDelay1(s);
00746 }
00747
00748 } else {
00749
00750 return sigDelay1(s);
00751 }
00752 }
00753
00770 Tree normalizeFixedDelayTerm(Tree s, Tree d)
00771 {
00772 Tree x, y, r;
00773 int i;
00774
00775 if (isZero(d) && ! isProj(s, &i, r)) {
00776
00777 return s;
00778
00779 } else if (isZero(s)) {
00780
00781 return s;
00782
00783 } else if (isSigMul(s, x, y)) {
00784
00785 if (getSigOrder(x) < 2) {
00786 return simplify(sigMul(x,normalizeFixedDelayTerm(y,d)));
00787 } else if (getSigOrder(y) < 2) {
00788 return simplify(sigMul(y,normalizeFixedDelayTerm(x,d)));
00789 } else {
00790 return sigFixDelay(s,d);
00791 }
00792
00793 } else if (isSigDiv(s, x, y)) {
00794
00795 if (getSigOrder(y) < 2) {
00796 return simplify(sigDiv(normalizeFixedDelayTerm(x,d),y));
00797 } else {
00798 return sigFixDelay(s,d);
00799 }
00800
00801 } else if (isSigFixDelay(s, x, y)) {
00802
00803
00804 return normalizeFixedDelayTerm(x,simplify(sigAdd(d,y)));
00805
00806 } else {
00807
00808 return sigFixDelay(s,d);
00809 }
00810 }
00811