Arbitrary Precision BigNum class (In Development)

BigNum.class.nut

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

class BigNum{
    data = null;
    sign = null; //0 = positive, 1 = negative
    
    constructor(arr, _sign){
        sign = _sign;
        
        local l = arr.len();
        
        data = array(l);
        
        for(local i = 0; i < l; i++){
            data[i] = arr[i] & 0xFF; //Store LSB at 0
        }

//        server.log("Constructed: "+this.tostring());
        _trim();
        server.log("Trimmed To: "+this.tostring());
    }
    
    static function cast(op){
        if(typeof op == "BigNum"){
            return op;
        }else{
            return BigNum(op);
        }
    }
    
    function _typeof(){
        return "BigNum";
    }
    
    function _cmp(op){
        if(typeof op != "BigNum"){
            throw "Can't compare BigNum to "+typeof op;
        }

        local myd = data;
        local opd = op.data;

        if(sign != op.sign){
            return (sign)? -1:1; //If I am negative then I am smaller
        }
        
        //If lengths are different then the values must be different
        // Short positive numbers are smaller than long positive numbers
        // Long negative numbers are smaller than short negative numbers
        if(myd.len() < opd.len()){
            return (sign) ?  1:-1;
        }else if( myd.len() > opd.len() ){
            return (sign) ? -1: 1;
        }
        
        for(local i = myd.len()-1; i >= 0; i--){
            local c = (myd[i] <=> opd[i]); //-1 if I am |smaller|, 1 if I am |bigger|
            if(c){
                return sign ? (0-c) : c;
            }
        }
        
        return 0;
    }
    
    function _trim(){
        local l = data.len();
        local i;
        for(i = l-1; i > 0; i--){
            if(data[i] != 0x00){
                break;
            }
        }
        
        data.resize(i+1);
    }
    
    static function _sameSignAdd(a, b){
        local ad = a.data;
        local bd = b.data;
        local aLen = ad.len();
        local bLen = bd.len();
        local maxLen = (aLen > bLen) ? aLen:bLen;

        local result = array(maxLen+1); //Grow by 1 byte over longest integer to allow overflow
        
        for(local i = 0; i < maxLen + 1; i++){
            result[i]  = (i < aLen) ? ad[i]:0;
            result[i] += (i < bLen) ? bd[i]:0;
            result[i] += (i > 0) ? (result[i-1] >> 8):0; //No carry for first value
            server.log(format("%d: %04X", i, result[i]));
        }

        return BigNum(result, a.sign);
    }
    
    static function _orderedSub(a, b){
        //assert: |a| > |b|
        local ad = a.data;
        local bd = b.data;
        local aLen = ad.len();
        local bLen = bd.len();
        
        local result = array(aLen); //Result will be no larger than larger number
        
        
        for(local i = 0; i < aLen; i++){
            if(i >= bl){
                result[i] = ad[i];
            }else if(ad[i] >= bd[i]){
                result[i] = ad[i] - bd[i];
            }else{
                ad[i+1]--; //i+1 is guranteed to exist by design
                result[i] = (ad[i] + 0x100) - bd[i];
            }
            server.log(format("%d: %04X", i, result[i]));
        }

        return BigNum(result, a.sign);
    }
    
    function _add(op){
        if(this.sign == op.sign){
            return BigNum.sameSignAdd(this, op);
        }else{
            server.log("Mismatch Sub Not implemented");
        }
        
    }
    
    
    function tostring(){
        local s = "0x";
        for(local i = data.len()-1; i >= 0; i--){
            s += format("%02X", data[i]);
        }
        return s;
    }

}

x <- BigNum([0xFF, 0xFF, 0xFF], 0);
y <- BigNum([0xFF, 0xFF, 0xFF], 0);

z <- x + y;