LSL Assembly... Sort of

For almost two years I've been thinking about writing an LSL Assembler & Disassembler for the LSO. Having found my self with a bit of time and the motivation I have taken a first crack at. Two years ago I started collecting research on LSL and the LSO (not to mention other data types). With in a few months I had complete the research but found my self otherwise preoccupied...

The language is partially based on XML; it uses XML to provide structure (as LSL has too much structure IMHO for pure assembly, but then I don't know assembly all that well).
It will have extensive support for Macro's.
It will handle dependancies so that unused functions will be excluded.
Assuming LSO allows it, I will be supporting Stack addressed Locals; these are values that are pushed onto the stack but are not popped off until return or the user pops them off. Basically a local variable that is never declared; but it still has a name. This has the advantage of saving on bytecode.
I'm still experimenting with the format and trying things out. Any and all input would be appreciated.
To upload these scripts once compiled you would use LibSL.
I'm trying to decide if it will be written in C# or IronPython.

With the exception of LSL function calls, there aren't any macro's used in this sample

Here is a sample:

<function name="Float2Hex" params="float a" return="string">
	<lsltext literaly="no">
		<![CDATA[
		string Float2Hex(float a)
		{// Copyright Strife Onizuka, 2006, LGPL, http://www.gnu.org/copyleft/lesser.html
			if((integer)a != a)//LL screwed up hex integers support in rotation & vector string typecasting
			{//this also keeps zero from hanging the zero stripper.
				float b = llFabs(a);//logs don't work on negatives.
				integer c = llFloor(llLog(b) / 0.69314718055994530941723212145818);//floor(log2(b))
				if(c > 127) c = 127;//catch fatal rounding error in exponent.
				integer d = (integer)((b / (float)("0x1p"+(string)c)) * 0x1000000);//shift up into integer range
				while(!(d & 0x1))
				{//strip extra zeros off before converting or they break "p"
					d = d >> 1;
					c = -~c;//++c;
				}
				string e = "p" + (string)(c - 24);
				do
					e = llGetSubString(hexc,15&d,15&d) + e;
				while(d = d >> 4);
				if(a < 0)
					return "-0x" + e;
				return "0x" + e;
			}//integers pack well so anything that qualifies as an integer we dump as such, supports netative zero
			return llDeleteSubString((string)a,-7,-1);//trim off the float portion, return an integer
		}
		]]>
	</lsltext><asm>
	#ifndef GlobalVar(hexc)
		GlobalString hexc "0123456789ABCDEF"
	#endif
	ReadLocalDword a;
	ReadLocalDword a;
	Convert(float ~ integer);
	Equals(integer, float);
	JumpTrue(integer) end;
	{
		fake b = llFabs{
			ReadLocalDword a;
		};
		fake c = llFloor{
			ValueDword float(0.69314718055994530941723212145818);
			llLog{b}
			Divide(float, float)
		}
		ValueDword 127;
		ReadLocalDword c;
		GreaterThan(integer, integer);
		JumpFalse(integer) skip;
		{
			ValueDword 127;
			MoveToLocalDword c;
		}@skip;
		fake d;
		ReadLocalDword c;
		Convert(int ~ string);
		ValueString("0x1p");
		Add(string + string);
		Convert(string ~ float);
		ReadLocalDword b;
		Divide(float / float);
		ValueDword 0x1000000;
		Multiply(float * integer);
		Convert(float ~ integer);
		{
			@loop;
			ValueDword 1;
			ReadLocalDword d;
			BitwiseAND
			JumpTrue(integer) done;
			{
				ValueDword 1;
				ReadLocalDword d;
				RightShift
				MoveToLocalDword d;
				ReadLocalDword c;
				BitwiseNOT
				Negitive
				MoveToLocalDword c;
				Jump loop;
			}@done;
		}
		ValueDword 24;
		ReadLocalDword c;
		Minus(integer - integer)
		Convert(integer ~ string);
		ValueString("p")
		Add(string + string)
		{@do_while;
			llGetSubString{
				ReadGlobalString hexc,
				fake e = 
					ReadLocalDword d;
					ValueDword 0xf;
					BitwiseAnd,
				e
			}
			Add(string + string)
			ValueDword 4;
			ReadLocalDword d;
			RightShift
			CopyToLocalDword d;
		JumpTrue(integer) do_while;}
		ValueString("0x")
		ReserveInt
		ReadLocalDword a;
		LessThan(float, float)
		JumpFalse(integer) Jump monkeys;
			ValueString("-")
			Add(string + string)
		@monkeys;
		Add(string + string)
		MoveToLocalDword return;
		Pop d;//The assembler does keep track of our fakes but it forces us to release them
		Pop c;//this is done so it doesn't have to figure out how to clean up your mess.
		Pop b;//The assembler will take care of any locals though.
		Return;
	}
	@end;
	llDeleteSubString{
		ReadLocalDword a;
		Convert(float ~ string);
		ValueDword(-7);
		ValueDword(-1);
	};
	MoveToLocalDword return;
	Return;
</asm></function>

And here are some of the notes in the config file for the compiler/decompiler

Besides the function table at the bottom there isn't much that should ever be changed in here.
Command names can be changed and new alt texts can be added for them.
function_setup is a simple macro setup to simplify the use of functions (which are otherwise a *****)
Of course you don't have to use the function_setup macros.

Limitations:
The decompiler's handling of jumps is very limited. It cannot cope with jumps to mid command offsets.
So that means:
No jumping into string constants.
No jumping out of the scripts memory.
No jumping to the middle of a command.

The ValidateJumps makes sure jumps only occure with-in a function or events scope and not between code blocks.
By turning this off you are effectively disabling SniffoutStackLeaks.

Just because you can write really bad code now, doesn't mean you should.
Just so you aren't stupid, i've enabled the crash flag on typecasts between the same type.

Both the compiler and decompiler will walk the stack to seek out leaks.

Amazing! Will you give a high level overview of what this could be useful for?

Writing efficient optimized code.

Pure LSL isn't far removed from the LSO specification. You can actually write a decompiler for code generated with the LSL compiler that will generate code almost identical to what you gave it (At this time I am not writing an LSO -> LSL decompiler).

The problem is the LSL compiler has some annoying limitations and does some things in a really stupid way.

Evil things you can do in the Assembly language:
Jump between functions & states.
Have multiple states use the same event handlers.
Have multiple events use the same event handler.

For example:
In this we show a moderate improvement in speed by not having a local variable and just keeping the value on the stack.

//Convert an integer into a hex string, more or less.
string hexc = "0123456789ABCDEF";

string Int2Hex(integer a)
{
	string b = llGetSubString(hexc, a&15, a&15);
	if((a = (0x0FFFFFFF & (a >> 4))))
		do
			b = llGetSubString(hexc, a&15, a&15) + b;
		while(a = a >> 4);
	return b;
}
//When the LSL compiler compilers, it turns the above function into...
<function name="Int2Hex" params="integer a" return="string" locals="string b">
{
	llGetSubString{
		ReadGlobalString hexc,
		ReadLocalDword a;
			ValueDword 0xf;
			BitwiseAnd,
		ReadLocalDword a;
			ValueDword 0xf;
			BitwiseAnd
	}
	MoveToLocalString b;
	
	ValueDword 4;
	ReadLocalDword a;
	RightShift
	ValueDword 0x0FFFFFFF;
	BitwiseAnd;
	CopyToLocalDword a;
	JumpFalse(integer) over;
	{
		@loop;
		ReadLocalString b;
		llGetSubString{
			ReadGlobalString hexc,
			ReadLocalDword a;
				ValueDword 0xf;
				BitwiseAnd,
			ReadLocalDword a;
				ValueDword 0xf;
				BitwiseAnd
		}
		Add(string + string)
		CopyToLocalString b;
		PopString;
		
		ValueDword 4;
		ReadLocalDword a;
		RightShift;
		CopyToLocalDword a;
		JumpTrue(integer) loop;
	}
	@over;
	ReadLocalString b;
	CopyToLocalString return;
	PopString;
	PopString;
	PopInteger;
	ReturnNow;
}
</function>

//How I would write it
<function name="Int2Hex" params="integer a" return="string">
{
	fake b = 
	llGetSubString{
		ReadGlobalString hexc,
		fake c =
		ReadLocalDword a;
			ValueDword 0xf;
			BitwiseAnd,
		ReadLocalDword c
	}
	
	ValueDword 4;
	ReadLocalDword a;
	RightShift
	ValueDword 0x0FFFFFFF;
	BitwiseAnd;
	CopyToLocalDword a;
	JumpFalse(integer) over;
	{
		@loop;
		ReadLocalString b;
		llGetSubString{
			ReadGlobalString hexc,
			fake c = ReadLocalDword a;
				ValueDword 0xf;
				BitwiseAnd,
			ReadLocalDword c
		}
		Add(string + string)
		
		ValueDword 4;
		ReadLocalDword a;
		RightShift;
		CopyToLocalDword a;
		JumpTrue(integer) loop;
	}
	@over;
	MoveToLocalString return;
	PopString;
	PopInteger;
	ReturnNow;
}
</function>

Is there a website I can download your tools at to give them a try? This sounds really interesting.

I considered using a hex editor to fiddle with the LSO directly after seeing http://www.libsecondlife.org/wiki/LSO , but I have no idea how to upload the file. Even just providing a tool to do that would be very helpful.

I've been updating the LibSL LSO notes (as they were somewhat incomplete).
I haven't formalized any tools yet, I'm still working out how the language will be designed.

I am considering writing an extended LSL language, with a low-level interface much like embedding assembly in C.

The decompiler is coming along; I haven't gotten into writing the parsing for the code chunks yet.

<Moved to Off the Wall>

Thanks for the work on our LSO notes, I know that page hasn't gotten any love in a long time.

http://www.libsecondlife.org/wiki/LSO if anyone else is interested or has more info to add.

Because more reverse-engineering still needs to be done, it would be nice to be able to have direct access to the different blocks (be able to specify some parts in raw hex) if the user wants.

If that is too difficult to add because of how your code is currently structured, could you at least include a command for the code sections like .db or .dw in most assembly languages that let you specify raw bytes/words to insert into the code? That shouldn't be too hard and could have many useful debugging and reverse engineering uses.

That LSO page is awesome! Reading through the sequence of LL calls at the end is like a history lesson. You get a sense of lsl capabilities developing over time as features were added.

However, Mono is not far away! Is this stuff really useful in a mono context? I have no idea about answering that question but maybe you have some info from LL? Then again, eddy might get his new client working before mono comes along!

Are we doing this to make a better LSL compiler? I hope so. Otherwise I do not see much sense in decompiling code for which we already have the original scripts complete with comments. I just hope that mono does not make these efforts wasted.

Often I need a particular event always handled by the same code, regardless of what state I'm in. Now that can be done directly. Also, just knowing how everything works can allow one to write more efficient code (look at all the strange suggestions at lslwiki for when dealing with lists, now we can understand WHY those work and do these things directly instead of frustratingly guessing to get stuff to work with less memory).

How much will this help the average LSL programmer? Probably none. But for those curious or willing, I'm sure it will be grandly useful.


Strife Onizuka,
It looks like you have really stirred up interest. Someone just posted an assembler on the wiki! http://www.libsecondlife.org/wiki/LSO_Assembler

It has the low level abilities I was hoping for, and maybe the macro abilities can allow for easier function calling as well (best of both worlds!). I'll have to fiddle with it.

Can you please release your LSO uploader so we can all try out this assembler? It looks like others are even willing to pay for such a service ( http://www.libsecondlife.org/wiki/Bounties ), so you'd be making a lot of people happy.

EDIT: I can't seem to figure out how to get floating point numbers to work with that assembler. Can someone help?
EDIT(2): Hmmm... the new page says it needs to be done by hand. Oh well.

Status:
After giving it a lot of thought, I've desided not write a pure assembler. Instead, it will be an extended version of LSL. Think i'll be calling it CLSL (The C because the syntax will be very similar to C; many evil things that C supports will be supported in CLSL). The compiler will do some optimizations. Not many. Most are stack end optimizations, local address recycling and dead code removal.

Features:
Inline assembly
Inline conditionals
stack based locals (space is not reserved for them).
events will be able to be called like functions
multiple events can point to a single event handler or global function.
uninitialized local variables (not depicted but to indicate one you must put the token "ignore" in the declare).
The compiler will give type based feedback and complain when it thinks you are doing something stupid.

Here is some sample code.

string Float2Hex(float b)
{//Dump FUI float-integer to a hex-float string
	if((integer)b != b)//LL screwed up hex integers support in rotation & vector string typecasting
	{//this also keeps zero from hanging the zero stripper.
		b = <float to integer>b;//trick the compiler, b is now treated as an integer, doesn't actually result in any bytecode.

		fake integer e = (0xff & (b >> 23));
		fake integer f = (b & 0x7fffff) | (0x800000 << !e);
		fake integer d = asm{PUSHE};
		//d is last on the stack. don't need the push,or load opcodes
		while !(0xf & (f >> d))//not loop, uses other conditional opcode.
			d = 4 + d;//d is taken off the stack by the addition operater
					//the result is already in d's place.
		
		fake string c = "p"+(string)(e - 150 + (!e | d));
		//same stack treatment for c, since it is now last.
		//in truth, the store opcode is never used with c
		do
			c = llGetSubString(hexc, 0xf & (f >> d), asm{DUP_T}) + c;
		while(24 ^ (d = 4 + d));
		
		return (b&0x80000000)?"-0x":"0x" + c;
	}//integers pack well so anything that qualifies as an integer we dump as such, supports negative zero
	return llDeleteSubString((string)b,-7,-1);//trim off the float portion, return an integer
}