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