// NOTE 
// ---- 
// All funcitons beginning with the 'u_' prefix assume their arguments are 
// non-negative integers in the range [0, 2^31-1].  Passing values outside 
// this range results in unspecified behavior. 
// 
// All results from these functions will either also be in this range or 
// will overflow into two integer words.  In the latter case, the least 
// significant integer word will be in the above range (the sign bit will be 
// zero).  This means that if 'msw' is the most significant integer word and 
// 'lsw' is the least significant word, the full number is actually: 
//     msw * 2^31 + lsw 
// (notice 2^31, NOT 2^32). 

integer SIGN_BIT_MASK = 0x80000000; 

// Returns the full product of two unsigned integers.  The first (index 0) 
// integer is the most significant integer of the product.  The second 
// (index 1) integer is the least significant integer of the product. 
list u_intProd(integer i1, integer i2) 
{ 
    integer i1Low = i1 & 0xFFFF; 
    integer i1High = i1 >> 16; 
    integer i2Low = i2 & 0xFFFF; 
    integer i2High = i2 >> 16; 
     
    //llOwnerSay("DEBUG - intProd: i1Low = "+(string)i1Low); 
    //llOwnerSay("DEBUG - intProd: i1High = "+(string)i1High); 
    //llOwnerSay("DEBUG - intProd: i2Low = "+(string)i2Low); 
    //llOwnerSay("DEBUG - intProd: i2High = "+(string)i2High); 
     
    integer lowLow = i1Low*i2Low; 
    integer lowHigh = i1Low*i2High; 
    integer highLow = i1High*i2Low; 
    integer highHigh = i1High*i2High; 
     
    integer lowLowMSW = (lowLow >> 31) & 0x1; 
    integer lowLowLSW = lowLow & ~SIGN_BIT_MASK; 
    integer lowHighMSW = (lowHigh >> 15) & 0xFFFF; 
    integer lowHighLSW = (lowHigh << 16) & ~SIGN_BIT_MASK; 
    integer highLowMSW = (highLow >> 15) & 0xFFFF; 
    integer highLowLSW = (highLow << 16) & ~SIGN_BIT_MASK; 
     
    //llOwnerSay("DEBUG - intProd: lowLowMSW = "+(string)lowLowMSW); 
    //llOwnerSay("DEBUG - intProd: lowLowLSW = "+(string)lowLowLSW); 
    //llOwnerSay("DEBUG - intProd: lowHighMSW = "+(string)lowHighMSW); 
    //llOwnerSay("DEBUG - intProd: lowHighLSW = "+(string)lowHighLSW); 
    //llOwnerSay("DEBUG - intProd: highLowMSW = "+(string)highLowMSW); 
    //llOwnerSay("DEBUG - intProd: highLowLSW = "+(string)highLowLSW); 
     
    integer msw = lowLowMSW+(highHigh<<1)+lowHighMSW+highLowMSW; 
     
    integer accum0 = lowLowLSW+lowHighLSW; 
    if (accum0 & SIGN_BIT_MASK) 
    { 
        accum0 = accum0 & ~SIGN_BIT_MASK; 
        ++msw; 
    } 
     
    integer lsw = accum0+highLowLSW; 
    if (lsw & SIGN_BIT_MASK) 
    { 
        lsw = lsw & ~SIGN_BIT_MASK; 
        ++msw; 
    } 
     
    //llOwnerSay("DEBUG - i1 = "+(string)i1); 
    //llOwnerSay("DEBUG - i2 = "+(string)i2); 
    //llOwnerSay("DEBUG - msw = "+(string)msw); 
    //llOwnerSay("DEBUG - lsw = "+(string)lsw); 
     
    return [ msw, lsw ]; 
} 

// Returns the sum of a big number (product of integers) and a little number 
// (integer).  The first (index 0) integer is the most significant integer 
// of the sum, and the second (index 1) integer is the least significant 
// integer of the sum. 
list u_bigSum(integer msw1, integer lsw1, integer i2) 
{ 
    integer msw = msw1; 
    integer lsw = lsw1+i2; 
     
    if (lsw & SIGN_BIT_MASK) 
    { 
        lsw = lsw & ~SIGN_BIT_MASK; 
        ++msw; 
    } 
     
    return [ msw, lsw ]; 
} 

// Returns the modulo of a large dividend (product of two integers) and a 
// small divisor (integer). 
integer u_bigMod(integer dividendMSW, integer dividendLSW, integer divisor) 
{ 
    integer msw = dividendMSW%divisor; 
    integer lsw = dividendLSW%divisor; 
     
    //llOwnerSay("DEBUG - bigMod: dividendMSW = "+(string)dividendMSW); 
    //llOwnerSay("DEBUG - bigMod: dividendLSW = "+(string)dividendLSW); 
    //llOwnerSay("DEBUG - bigMod: divisor = "+(string)divisor); 
     
    // This might be slow, but it WILL finish.  Proof (assume msw > 0): 
    //     x = msw * 2^31 + lsw 
    //     x % y = (msw * 2^31) % y + lsw % y 
    //         = (msw % y) * (2^31 % y) + lsw % y 
    //     msw % y <= msw 
    //     lsw % y <= lsw 
    //     y <= 2^31 - 1 
    //     2^31 % y < 2^31 - 1 
    // thus: 
    //     (msw % y) * (2^31 % y) + lsw % y < msw * 2^31 + lsw 
    while (msw != 0) 
    { 
        //llOwnerSay("DEBUG - msw = "+(string)msw); 
         
        integer wsmod = (0x7FFFFFFF%divisor)+1; 
         
        list prod = u_intProd(wsmod, msw); 
        integer prodMSW = llList2Integer(prod, 0); 
        integer prodLSW = llList2Integer(prod, 1); 
         
        list sum = u_bigSum(prodMSW, prodLSW, lsw); 
        msw = llList2Integer(sum, 0)%divisor; 
        lsw = llList2Integer(sum, 1)%divisor; 
         
        //llOwnerSay("DEBUG - bigMod: msw = "+(string)msw); 
        //llOwnerSay("DEBUG - bigMod: lsw = "+(string)lsw); 
    } 
     
    return lsw; 
} 

// Returns (a*b)%c. 
integer u_modProd(integer a, integer b, integer c) 
{ 
    list prod = u_intProd(a, b); 
    integer prodMSW = llList2Integer(prod, 0); 
    integer prodLSW = llList2Integer(prod, 1); 
     
    integer result =  u_bigMod(prodMSW, prodLSW, c); 
     
    //llOwnerSay("DEBUG modProd - a = "+(string)a); 
    //llOwnerSay("DEBUG modProd - b = "+(string)b); 
    //llOwnerSay("DEBUG modProd - c = "+(string)c); 
    //llOwnerSay("DEBUG modProd - prodMSW = "+(string)prodMSW); 
    //llOwnerSay("DEBUG modProd - prodLSW = "+(string)prodLSW); 
    //llOwnerSay("DEBUG modProd - result = "+(string)result); 
     
    return result; 
} 

// Returns (a^b)%c. 
integer u_modPow(integer a, integer b, integer c) 
{ 
    integer result = 1; 
    integer currentPow = a; 
    integer exp = b; 
     
    while (exp != 0) 
    { 
        //llOwnerSay("DEBUG - modPow: exp = "+(string)exp); 
         
        if (exp & 0x1) 
        { 
            result = u_modProd(result, currentPow, c); 
        } 
         
        //llOwnerSay("DEBUG - modPow: currentPow = "+(string)currentPow); 
        //llOwnerSay("DEBUG - modPow: result = "+(string)result); 
         
        currentPow = u_modProd(currentPow, currentPow, c); 
        exp = exp >> 1; 
    } 
     
    return result; 
} 

default 
{ 
    touch_start(integer total_number) 
    { 
        integer N_TESTS = 10; 
         
        float startTime = llGetTime(); 
         
        integer i; 
        for (i = 0; i < N_TESTS; ++i) 
        { 
            integer a = (integer)llFloor(llFrand(0x7FFFFFFF)); 
            integer b = (integer)llFloor(llFrand(0x7FFFFFFF)); 
            integer c = (integer)llFloor(llFrand(0x7FFFFFFF)); 
             
            llOwnerSay("a = "+(string)a); 
            llOwnerSay("b = "+(string)b); 
            llOwnerSay("c = "+(string)c); 
             
            integer result = u_modPow(a, b, c); 
             
            llOwnerSay("(a^b)%c = "+(string)result); 
        } 
         
        float endTime = llGetTime(); 
         
        float timeDiff = endTime - startTime; 
        float avgTime = timeDiff / N_TESTS; 
         
        llOwnerSay("Average execution time: "+(string)avgTime+" s"); 
    } 
}