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


--- Comment #0 from timon.gehr@gmx.ch 2013-06-08 16:28:49 PDT ---
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: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10310



--- Comment #1 from timon.gehr@gmx.ch 2013-06-08 16:41:16 PDT ---
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: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10310


Walter Bright <bugzilla@digitalmars.com> changed:

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


--- Comment #2 from Walter Bright <bugzilla@digitalmars.com> 2013-06-08 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: -------

http://d.puremagic.com/issues/show_bug.cgi?id=10310



--- Comment #3 from timon.gehr@gmx.ch 2013-06-09 03:54:00 PDT ---
(In reply to comment #2)
> 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: -------