Arbitrary Precision BigInt class (In Development)

BigInt.class.nut

// Copyright (c) 2014 Electric Imp
// This file is licensed under the MIT License
// http://opensource.org/licenses/MIT

//==============================================================================

class BigIntLib{
    
    static function hexByteToInt(str, start=0){
        local result = 0;
        local c = str[start];
        if( '0' <= c && c <= '9'){
            result = (c - 0x30) << 4;  
        }else if( 'a' < c && c <= 'f' ){
            result = (c - 0x57) << 4;
        }else if( 'A' < c && c <= 'F' ){
            result = (c - 0x37) << 4;
        }else{
            throw "Invalid Hex Character: "+c;
        }

        local c = str[start+1];
        if( '0' <= c && c <= '9'){
            result = result | (c - 0x30);  
        }else if( 'a' < c && c <= 'f' ){
            result = result | (c - 0x57);
        }else if( 'A' < c && c <= 'F' ){
            result = result | (c - 0x37);
        }else{
            throw "Invalid Hex String: "+c;
        }
        
        return result;
    }

    static function fromHexString(str, isSigned=true){
        //Create an empty BigInt to hold our data        
        local bi = BigInt(null);
        local data = bi._data;
        local sign = bi._sign;
        local valid = bi._valid;
        local hex2int = BigIntHelpers.hex2Int;
        
        //Let's only deal with lower case letters
        str = str.tolower();
        
        //Remove leading "0x" if present
        if( str.len() >= 2 && str.slice(0, 2) == "0x" ){
            str = str.slice(2);
        }
        
        // make sure we have an even number of digits, otherwise return invalid
        if( value.len() % 2 == 1){
            bi._valid = false;
            return bi;
        }
                         
        // start scanning from the right
        data = blob();
        for (local i = value.len() - 2; i >= 0; i -= 2) {
            local hex = value.slice(i, i+2)
            local int = _hex2int(hex);
            _data.writen(int, 'b');
        }
        
    }
    
    static function fromInteger(integer){
        local magnitude = blob(4);
        local sign = (integer >= 0) ? 1:-1;
        
        //Turn the integer into an absolute value (magnitude)
        integer = math.abs(integer);
        
        magnitude[0] = (integer      ) & 0xFF;
        magnitude[1] = (integer >>  8) & 0xFF;
        magnitude[2] = (integer >> 16) & 0xFF;
        magnitude[3] = (integer >> 24) & 0xFF;
        
        return BigInt(magnitude, sign);
    }        

    static function abs(bigint){
        return BigInt(bigint.data, 1);
    }
    
    static function negate(bigint){
        return BigInt(biginit.data, -bigint.sign)
    }
    
}

class BigInt {
    
    magnitude  = null; // Blob with LSByte at index 0
    sign  = null; // 1 = positive, -1 = negative
    valid = null; // Tells if an error condition happened such as unsupported operation

    constructor(_magnitude = null, _sign = 1) {
        if(_magnitude == null){
            valid = false;  //Create an empty object (which is invalid)
            return;
        }
        
        valid = true;
        sign  = (_sign >= 0) ? 1:-1;
        magnitude  = clone _magnitude;
        _trim();
    }

    //--------------------------------------------------------------------------    
    //  Public Methods
    //--------------------------------------------------------------------------    
    function tostring() {
        return _tostring();
    }
    
    //--------------------------------------------------------------------------    
    //  Private (Non-Meta) Methods
    //--------------------------------------------------------------------------    

    // Remove excess 0x00 bytes and make the blob as compact as possible
    function _trim() {
        local m = magnitude; //Local for speed
        local l = m.len();
        local i;
        for(i = l-1; i > 0; i--) {
            if(m[i] != 0x00) {
                break;
            }
        }
        m.resize(i+1);
        
        // Don't allow a value of -0x00
        if(m.len() == 1 && m[0] == 0x00){
            sign = 1;
        }
    }
 
    // If both operands are the same sign we can add the magnitudes and keep the same sign
    // if operands have opposite signs, but we need to do a subtraction then this is equivalent
    // to a sameSignAdd. (Math!)
    static function addMagnitudes(aMag, bMag) {
        local aLen = aMag.len();
        local bLen = bMag.len();
        local maxLen = (aLen > bLen) ? aLen : bLen;
        
        // Grow by 1 byte over longest integer to allow overflow
        maxLen++;
        
        // Create a blob to hold the result
        local newMag = blob(maxLen);
        
        local val;
        local carry = 0;
        for (local i = 0; i < maxLen; i++) {
            val  = carry;
            val += (i < aLen) ? aMag[i] : 0;
            val += (i < bLen) ? bMag[i] : 0;

            carry = (val >> 8);
            newMag[i] = val & 0xFF;
        }
        
        return newMag;
    }

    // This is an ordered a minus b operation. a must be larger than b otherwise
    // the result will be invalid.
    static function subMagnitudes(aMag, bMag){
        local aLen  = aMag.len();
        local bLen  = bMag.len();
        
        // Result will be no longer than aMag
        local newMag = blob(aLen);
        
        local minuend, subtrahend;
        local borrow = 0;
        for (local i = 0; i < aLen; i++) {
            minuend    = aMag[i];
            subtrahend = borrow  + ((i < bLen) ? bMag[i]:0);
            
            if(minuend >= subtrahend){
                newMag[i] = minuend - subtrahend;
                borrow = 0;
            }else{
                newMag[i] = 0x100 + minuend - subtrahend;
                borrow = 1;
            }
        }

        return newMag;
    }
    
    static function cmpMagnitudes(aMag, bMag){
        // If lengths are different then the values must be different
        local lc = aMag.len() <=> bMag.len();
        if(lc != 0){
            return lc;
        }
        
        // server.log(format("cmp %s <=> %s", this.tostring(), op.tostring()))
        for (local i = aMag.len()-1; i >= 0; i--) {
            local c = (aMag[i] <=> bMag[i]); 
            // server.log(format("cmp[%d] %d <=> %d = %d", i, myd[i], opd[i], c))
            if (c != 0) return c;
        }
        
        return 0;
    }
    
    //--------------------------------------------------------------------------
    //  Meta-Methods
    //--------------------------------------------------------------------------
    
    function _typeof() {
        return "BigInt";
    }
    
    function _add(op){

        local newMag, newSign;
        
        if( sign == op.sign ){
            //  3 +  2 =  5, if both positive then add magnitudes and sign is positive
            // -3 + -2 = -5, if both negative then add magnitudes and sign is negative
            // Simplifies to |this| + |op|, sign
            // 3 + 2 = 5  and -3 + -2 = -5
            newMag  = BigInt.addMagnitudes(magnitude, op.magnitude);
            newSign = sign;
        } else{
            //  3 + -3 =  0, if opposite signs and same magnitude then 0
            //  3 + -2 =  1, if opposite signs and |this| > |op| then |this| - |op| and this.sign
            // -3 +  2 = -1, same as above
            //  2 + -3 = -1, if opposite signs and |this| > |op| then |op| - |this| and -this.sign
            // -2 +  3 =  1, same as above
            local cmp = BigInt.cmpMagnitudes(magnitude, op.magnitude);
            
            if (cmp == 0) {
                // -3 + 3 = 0
                newMag  = blob(1);
                newSign = 1;
            }else if(cmp == 1){
                // 3 + -2 = 1 or -5 + 3 = -2
                newMag  = BigInt.subMagnitudes(magnitude, op.magnitude);
                newSign = sign;
            }else{
                // 2 + -3 = -1 or -3 + 5 = 2
                newMag  = BigInt.subMagnitudes(op.magnitude, magnitude);
                newSign = -sign;
            }
        }

        return BigInt(newMag, newSign);
    }        

    // Invert the sign of the second operand and make it into addition
    function _sub(op) {
        return this + BigInt(op.magnitude, -op.sign);
    }

    function _cmp(op) {
        // If signs mismatch then return sign (1 if I am positive, -1 if I am negative)
        if( sign != op.sign) return sign; 

        // If the signs are the same, then check the magnitudes
        //  3 <=>  3 them cmp =  0, return  0
        // -3 <=> -3 them cmp =  0, return  0
        //  5 <=>  3 then cmp =  1, return  1
        // -5 <=> -3 then cmp =  1, return -1
        //  3 <=>  5 then cmp = -1, return -1
        // -3 <=> -5 then cmp = -1, return  1
        // Simplifies to sign * cmp
        
        local cmp = BigInt.cmpMagnitudes(this.magnitude, op.magnitude);
        return sign * cmp;
        
    }
    
    function _tostring() {
        local s = (sign == -1) ? "-0x" : "0x";
        for (local i = magnitude.len()-1; i >= 0; i--) {
            s += format("%02X", magnitude[i]);
        }
        return s;
    }
}

function checkMath(a, b){
    local bigA = BigIntLib.fromInteger(a);
    local bigB = BigIntLib.fromInteger(b);
    
    local sum      = bigA + bigB;
    local sumCheck = BigIntLib.fromInteger(a+b);
    
    if(sum <=> sumCheck){
        server.error(""+bigA+" + "+bigB+" = "+sum+" != "+sumCheck);
    }else{
        //server.log(""+bigA+" + "+bigB+" = "+sum+" ?= "+check);
    }
    
    local diff      = bigA - bigB;
    local diffCheck = BigIntLib.fromInteger(a-b);
    
    if(diff <=> diffCheck){
        server.error(""+bigA+" - "+bigB+" = "+diff+" != "+diffCheck);
    }else{
        //server.log(""+bigA+" - "+bigB+" = "+diff+" == "+diffCheck);
    }

}

local offset = (RAND_MAX >> 1);
local loops = 0;
function loop(){
    
    local r1 = math.rand() - (RAND_MAX >> 1);;
    local r2 = math.rand() - (RAND_MAX >> 1);;

    checkMath(r1, r2);

    if((++loops % 1000) == 0){
        server.log(""+loops+" test complete...")
    }
    
    imp.wakeup(0, loop);
}
loop();