Binary Math

// LSL Binary Arithmetic
// (Anti-)Proof of concept
//
// The largest numbers LSL supports are 32-bit signed 
// integers, which limits llModPow to 16-bit exponents, 
// therefore limiting key length in RSA encryption and 
// Diffie-Hellman exchanges to 16-bit keys. To get 
// around this limitation I started writing a binary 
// arithmetic library which would allow arbitrary size 
// numbers in ModPow functions, bringing LSL up to 
// par with the strength of PHP libraries like bcmath and 
// gmp. Unfortunately, the speed of LSL makes this a 
// laughable experience. Multiplying the two 32-bit 
// test numbers takes over 30 seconds in my tests. I 
// guess 64-bit exponents are out of the question...
//     (What was I thinking?)
// Anyways instead of throwing the code away I'm 
// archiving it here in case anyone else gets the wild 
// idea to try something similar. Addition and subtraction 
// can be done very quickly if someone has a use for those, 
// and this could probably be optimized by using strings 
// instead of lists. Only addition and multiplication are 
// implemented in this version, but from my testing they 
// are both very robust. Unless you start passing non-
// binary data in of course. 

// Some random test values, 3816682369 and 2305728161

list number_one = [1,1,1,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,1,0,0,0,0,0,0,1];
list number_two = [1,0,0,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,1,1,1,1,0,1,0,1,0,0,0,0,1];

print_binary(list number)
{
    integer i;
    string output;
    
    for (i = 0; i < llGetListLength(number); i++) {
        output += llList2String(number, i);
    }
    
    llSay(0, output);
}

list reverse(list number)
{
    list new;
    integer i;
    
    for (i = llGetListLength(number) - 1; i >= 0; i--) {
        new += llList2List(number, i, i);
    }
    
    return new;
}

list add(list first, list second)
{
    list answer = [];
    list temp = [];
    integer i;
    integer f;
    integer s;
    integer carry = FALSE;
    integer diff = llGetListLength(first) - llGetListLength(second);

    // Pad the one of the numbers with leading zeroes if necessary   
    if (diff < 0) {
        for (i = 0; i < llAbs(diff); i++) {
            temp += [0];
        }
        
        first = temp + first;
    } else if (diff > 0) {
        for (i = 0; i < diff; i++) {
            temp += [0];
        }
        
        second = temp + second;
    }
    
    // Addition loop
    for (i = llGetListLength(first) - 1; i >= 0; i--) {
        f = llList2Integer(first, i);
        s = llList2Integer(second, i);

        if (f && s && carry) {
            carry = TRUE;
            answer += [1];
        } else if (f && s || ((f || s) && carry)) {
            carry = TRUE;
            answer += [0];
        } else {
            if (f || s || carry) {
                answer += [1];
            } else {
                answer += [0];
            }
            
            carry = FALSE;
        }
    }
    
    if (carry) {
        answer += [1];
    }
    
    return reverse(answer);
}

list multiply(list multiplicand, list multiplier)
{
    integer i;
    integer j;
    list partial_sum = [0];
    list product;
    integer length = llGetListLength(multiplier);
    
    for (i = length - 1; i >= 0; i--) {
        product = [];
        
        if (llList2Integer(multiplier, i)) {
            // Build the right-side zero padding for the product
            for (j = 0; j < (length - i) - 1; j++) {
                product += [0];
            }
            
            product = multiplicand + product;
            partial_sum = add(partial_sum, product);
        }
    }
    
    return partial_sum;
}


default
{
    state_entry()
    {
    }

    touch_start(integer total_number)
    {
        list answer;
        
        llSay(0, "Free memory: " + (string)llGetFreeMemory());
        
        llSay(0, "Binary addition test");
        print_binary(number_one);
        print_binary(number_two);
        llSay(0, "--------------------------------");
        answer = add(number_one, number_two);
        print_binary(answer);
        
        llSay(0, "Binary multiplication test");
        print_binary(number_one);
        print_binary(number_two);
        llSay(0, "--------------------------------");
        answer = multiply(number_one, number_two);
        print_binary(answer);
        
        llSay(0, "Free memory: " + (string)llGetFreeMemory());
    }
}