www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 10310] New: VRP for bitwise &|^ does not always produce the tightest bound.

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10310

           Summary: VRP for bitwise &|^ does not always produce the
                    tightest bound.
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: timon.gehr gmx.ch



In DMD, VRP for bitwise &|^ does not always produce the tightest bounds.
For my own D frontend implementation, I have devised simple greedy algorithms
that do (disclaimer: proof of tightness for XOR case not carried out yet). This
is the relevant part of the source:


// (C) 2012 Timon Gehr. Feel free to redistribute (derivative works) under
artistic/gpl dual licencing. (The same as DMD.)

// T - unsigned integral type of 8*T.sizeof bytes.
// R - Pair T min, max: Range of Ts [min..max] (min and max inclusive).
// ~R - VRP for bitwise not.
// R&R - Make new R from (minAnd(.,.),maxAnd(.,.))


T maxOr(R lhs, R rhs){
    T x=0;
    auto xor=lhs.max^rhs.max;
    auto and=lhs.max&rhs.max;
     for(T d=1LU<<(8*T.sizeof-1);d;d>>=1){
        if(xor & d){
            x |= d;
            if(lhs.max&d){if(~lhs.min&d) lhs.min=0;}
            else{if(~rhs.min&d) rhs.min=0;}
        }else if(lhs.min&rhs.min&d){
            x |= d;
        }else if(and & d){
            x |= (d<<1)-1;
            break;
        }
    }
    return x;
}

T minOr(R lhs, R rhs){return ~maxAnd(~lhs,~rhs);}

T maxAnd(R lhs, R rhs){
    T x=0;
    for(T d=1LU<<(8*T.sizeof-1);d;d>>=1){
        if(lhs.max&rhs.max&d){
            x |= d;
            if(~lhs.min&d) lhs.min=0;
            if(~rhs.min&d) rhs.min=0;
        }else if(~lhs.min & d && lhs.max & d){
            lhs.max |= d-1;
        }else if(~rhs.min & d && rhs.max & d){
            rhs.max |= d-1;
        }
    }
    return x;
}

T minAnd(R lhs, R rhs){return ~maxOr(~lhs,~rhs);}

T maxXor(R lhs, R rhs){return maxOr(lhs&~rhs,~lhs&rhs);}
T minXor(R lhs, R rhs){return minOr(lhs&~rhs,~lhs&rhs);}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 08 2013
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10310




Example test case that fails now and will work after the changes have been
implemented:

void main(){
    uint y;
    ubyte x = ((y&252)^2)+1;
}

The computed range for the right-hand-side expression is 1..255 (inclusive).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 08 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10310


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugzilla digitalmars.com



18:15:36 PDT ---
I cannot merge code copyrighted by others into DMD that has a license more
restrictive than Boost. This impairs licensing and copyright assignment.
Furthermore, having bits and pieces of the source code with random different
copyrights is simply unworkable.

Code to be merged needs to conform to the original copyright for the file. I
will be happy to give you authorship credit if you desire.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 08 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10310






 I cannot merge code copyrighted by others into DMD that has a license more
 restrictive than Boost. This impairs licensing and copyright assignment.
 Furthermore, having bits and pieces of the source code with random different
 copyrights is simply unworkable.
 
 Code to be merged needs to conform to the original copyright for the file. I
 will be happy to give you authorship credit if you desire.


I don't care that much (or know that much) about copyright, but code that is
posted in bugzilla is placed into the public domain by default. You can use the
code under the boost licence.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 09 2013