cloud9_root/src/third_party/stp/src/simplifier/simplifier.cpp
//compute the multiplicative inverse of the input
compute the multiplicative inverse of the input
compute the multiplicative inverse of the input
ASTNode
  Simplifier::MultiplicativeInverse(const ASTNode& d)
  {
    ASTNode c = d;
    if (BVCONST != c.GetKind())
      {
        FatalError("Input must be a constant", c);
      }
    if (!BVConstIsOdd(c))
      {
        FatalError("MultiplicativeInverse: Input must be odd: ", c);
      }
    ASTNode inverse;
    if (CheckMultInverseMap(d, inverse))
      {
        return inverse;
      }
    inverse = c;
    unsigned inputwidth = c.GetValueWidth();
    create a '0' which is 1 bit long
    ASTNode onebit_zero = _bm->CreateZeroConst(1);
    zero pad t0, i.e. 0 @ t0
    c = BVConstEvaluator(nf->CreateTerm(BVCONCAT, inputwidth + 1, onebit_zero, c));
    construct 2^(inputwidth), i.e. a bitvector of length
    'inputwidth+1', which is max(inputwidth)+1
    all 1's
    ASTNode max = _bm->CreateMaxConst(inputwidth);
    zero pad max
    max = BVConstEvaluator(nf->CreateTerm(BVCONCAT, inputwidth + 1, onebit_zero, max));
    _bm->Create a '1' which has leading zeros of length 'inputwidth'
    ASTNode inputwidthplusone_one = _bm->CreateOneConst(inputwidth + 1);
    add 1 to max
    max = nf->CreateTerm(BVPLUS, inputwidth + 1, max, inputwidthplusone_one);
    max = BVConstEvaluator(max);
    ASTNode zero = _bm->CreateZeroConst(inputwidth + 1);
    ASTNode max_bvgt_0 = nf->CreateNode(BVGT, max, zero);
    ASTNode quotient, remainder;
    ASTNode x, x1, x2;
    x1 initialized to zero
    x1 = zero;
    x2 initialized to one
    x2 = _bm->CreateOneConst(inputwidth + 1);
    while (ASTTrue == BVConstEvaluator(max_bvgt_0))
      {
        quotient = (c divided by max)
        quotient = BVConstEvaluator(nf->CreateTerm(BVDIV, inputwidth + 1, c, max));
        remainder of (c divided by max)
        remainder = BVConstEvaluator(nf->CreateTerm(BVMOD, inputwidth + 1, c, max));
        x = x2 - q*x1
        x = nf->CreateTerm(BVSUB, inputwidth + 1, x2, nf->CreateTerm(BVMULT, inputwidth + 1, quotient, x1));
        x = BVConstEvaluator(x);
        fix the inputs to the extended euclidian algo
        c = max;
        max = remainder;
        max_bvgt_0 = nf->CreateNode(BVGT, max, zero);
        x2 = x1;
        x1 = x;
      }
    ASTNode hi = _bm->CreateBVConst(32, inputwidth - 1);
    ASTNode low = _bm->CreateZeroConst(32);
    inverse = nf->CreateTerm(BVEXTRACT, inputwidth, x2, hi, low);
    inverse = BVConstEvaluator(inverse);
    UpdateMultInverseMap(d, inverse);
    cerr << "output of multinverse function is: " << inverse << endl;
    return inverse;
  }
ASTNode Simplifier :: MultiplicativeInverse ( const ASTNode & d ) { ASTNode c = d ; if ( BVCONST != c . GetKind ( ) ) { FatalError ( " " , c ) ; } if ( ! BVConstIsOdd ( c ) ) { FatalError ( " " , c ) ; } ASTNode inverse ; if ( CheckMultInverseMap ( d , inverse ) ) { return inverse ; } inverse = c ; unsigned inputwidth = c . GetValueWidth ( ) ; ASTNode onebit_zero = _bm -> CreateZeroConst ( 1 ) ; c = BVConstEvaluator ( nf -> CreateTerm ( BVCONCAT , inputwidth + 1 , onebit_zero , c ) ) ; ASTNode max = _bm -> CreateMaxConst ( inputwidth ) ; max = BVConstEvaluator ( nf -> CreateTerm ( BVCONCAT , inputwidth + 1 , onebit_zero , max ) ) ; ASTNode inputwidthplusone_one = _bm -> CreateOneConst ( inputwidth + 1 ) ; max = nf -> CreateTerm ( BVPLUS , inputwidth + 1 , max , inputwidthplusone_one ) ; max = BVConstEvaluator ( max ) ; ASTNode zero = _bm -> CreateZeroConst ( inputwidth + 1 ) ; ASTNode max_bvgt_0 = nf -> CreateNode ( BVGT , max , zero ) ; ASTNode quotient , remainder ; ASTNode x , x1 , x2 ; x1 = zero ; x2 = _bm -> CreateOneConst ( inputwidth + 1 ) ; while ( ASTTrue == BVConstEvaluator ( max_bvgt_0 ) ) { quotient = BVConstEvaluator ( nf -> CreateTerm ( BVDIV , inputwidth + 1 , c , max ) ) ; remainder = BVConstEvaluator ( nf -> CreateTerm ( BVMOD , inputwidth + 1 , c , max ) ) ; x = nf -> CreateTerm ( BVSUB , inputwidth + 1 , x2 , nf -> CreateTerm ( BVMULT , inputwidth + 1 , quotient , x1 ) ) ; x = BVConstEvaluator ( x ) ; c = max ; max = remainder ; max_bvgt_0 = nf -> CreateNode ( BVGT , max , zero ) ; x2 = x1 ; x1 = x ; } ASTNode hi = _bm -> CreateBVConst ( 32 , inputwidth - 1 ) ; ASTNode low = _bm -> CreateZeroConst ( 32 ) ; inverse = nf -> CreateTerm ( BVEXTRACT , inputwidth , x2 , hi , low ) ; inverse = BVConstEvaluator ( inverse ) ; UpdateMultInverseMap ( d , inverse ) ; return inverse ; }
compute the multiplicative inverse of the input
compute the multiplicative inverse of the input
//cerr << "input to multinverse function is: " << d << endl; //cerr << "found the inverse of: " << d << "and it is: " << //inverse << endl; //Compute the multiplicative inverse of c using the extended //euclidian algorithm // //create a '0' which is 1 bit long //zero pad t0, i.e. 0 @ t0 //construct 2^(inputwidth), i.e. a bitvector of length //'inputwidth+1', which is max(inputwidth)+1 // //all 1's //zero pad max //_bm->Create a '1' which has leading zeros of length 'inputwidth' //add 1 to max //x1 initialized to zero //x2 initialized to one //quotient = (c divided by max) //remainder of (c divided by max) //x = x2 - q*x1 //fix the inputs to the extended euclidian algo //cerr << "output of multinverse function is: " << inverse << endl;