CODE

// 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());

}

}