2016-05-07 - In IL: Volume of a Cylinder (Operations)

So far we've looked at variables, stacks, and instructions. It's time to see how these things work together. For this we are going to use a C# program that calculates the volume of a cylinder.

Once you compile this program and disassemble the IL you get something like this. (Note: I compiled in release mode so optimizations are enabled)

So let's go through this program line by line and see if we can understand what it's doing.

.entrypoint

This is a directive that specifies that this is the function that should be called when the program is launched

.maxstack  4

This directive indicates that maximum number of items on the stack and therefore it's required size. In this case we have 4 items so our stack would look like this

Evaluation Stack
Type	Value

And right now our stack is empty.

.locals init

This directive we've already seen, it specifies the local variables of the function. The init keyword indicates that variables are initialized to zero. So combining our stack and variables we have.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
		0	int32	0
		1	int32	0
		2	float64	0

ldc.i4.3

This instruction loads the value 3 as an int32 onto the stack.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
int32	3	0	int32	0
		1	int32	0
		2	float64	0

stloc.0

This instruction pops the value from the top of the stack and stores it in variable 0 which is cylinderRadius. This corresponds to "int cylinderRadius = 3" in the original program

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
		0	int32	3
		1	int32	0
		2	float64	0

ldc.i4.s   15

stloc.1

These instructions load 15 using the immediate load short form instruction and then stores it in variable 1. This corresponds to "int cylinderHeight = 15".

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
		0	int32	3
		1	int32	15
		2	float64	0

ldc.r8     3.1415926540000001

This instruction loads 3.141592654 as a float64 onto the stack.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
float64	3.141592654	0	int32	3
		1	int32	15
		2	float64	0

ldloc.0

This instruction loads variable 0 onto the stack.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
float64	3.141592654	0	int32	3
int32	3	1	int32	15
		2	float64	0

conv.r8

This instruction converts the value on top of the stack into a float64. Because of the way floating point values work the value won't be exactly the same as the original value but we're going to ignore that for the sake of simplicity.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
float64	3.141592654	0	int32	3
float64	~3.0	1	int32	15
		2	float64	0

mul

This instruction pops the top two values from the stack multiplies them together and then pushes the result onto the stack

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
float64	~9.424777962	0	int32	3
		1	int32	15
		2	float64	0

ldloc.0

conv.r8

mul

These instructions load variable 0 onto the stack again, convert it to float64 and multiplies it with the existing value on the stack.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
float64	~28.274333886	0	int32	3
		1	int32	15
		2	float64	0

ldloc.1

conv.r8

mul

These instructions load variable 1 onto the stack, converts it to float64 and multiplies it with the existing value on the stack.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
float64	~424.11500829	0	int32	3
		1	int32	15
		2	float64	0

stloc.2

This instruction pops the value from the top of the stack and stores it in variable 2 which is the cylinderVolume. The previous loads, converts, and multiplies correspond to the calculations to determine the value of cylinderVolume in the original program.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
		0	int32	3
		1	int32	15
		2	float64	~424.11500829

ldstr      "A Cylinder with radius {0} m and height {1} m has a volume of {2} m^3"

This instruction loads a reference to the constant string onto the stack. Up until now we have been dealing only with value types which are stored entirely on the stack. Reference types are stored elsewhere and only a reference to them is stored on the stack. To indicate this I'm going to use square brackets [].

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
string	["A Cylinder..."]	0	int32	3
		1	int32	15
		2	float64	~424.11500829

ldloc.0

This instruction loads variable 0 onto the stack.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
string	["A Cylinder..."]	0	int32	3
int32	3	1	int32	15
		2	float64	~424.11500829

box        [mscorlib]System.Int32

This instruction converts the value onto of the stack into a reference type. This involves creating a copy of its content and storing it elsewhere. A reference to the copy location is then stored on the stack. Note that this converts the value from the built-in int32 type to System.Int32 type defined in the standard library.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
string	["A Cylinder..."]	0	int32	3
System.Int32	[3]	1	int32	15
		2	float64	~424.11500829

ldloc.1

box        [mscorlib]System.Int32

ldloc.2

box        [mscorlib]System.Double

These instructions load variables 1 and 2 onto the stack and them boxes them as reference types.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
string	["A Cylinder..."]	0	int32	3
System.Int32	[3]	1	int32	15
System.Int32	[15]	2	float64	~424.11500829
System.Double	[~424.11500829]

call       string [mscorlib]System.String::Format(string, object, object, object)

This instruction calls the String.Format method. It pops the values on the stack as its arguments and pushes the result onto the stack. Note that the argument types to this function are objects. The variables had to be boxed so that they could be passed as objects to this function. The string on the stack is now the formatted string with the variables inserted into it.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
string	["A Cylinder..."]	0	int32	3
		1	int32	15
		2	float64	~424.11500829

call       void [mscorlib]System.Console::WriteLine(string)

This instruction calls the Console.WriteLine method which prints it's arguments to the console. This method returns void so there's nothing pushed onto the stack. Notice that there's a step missing here. In the original program we stored the output of String.Format in a variable and then printed the variable. The compiler decided it didn't need that variable and removed it.

Evaluation Stack		Local Variables
Type	Value	Index	Type	Value
		0	int32	3
		1	int32	15
		2	float64	~424.11500829

ret

This instruction ends execution of the method. The stack is empty after calling Console.WriteLine which is a requirement for the return instruction. The local variables will also go out of scope at this point and eventually be cleaned up.

Next time we will look at branching instructions.

2016-04-09 - Why Comment

Commenting code is one of those things that seems simple at first but turns out to be rather complicated. Write too few comments and it's hard for people to understand the code. Write too many comments and it's equally hard because it's difficult to see the code through the comments.

I think the answer is in determining what information isn't already being provided by the code. Variable names tell you what information is being worked with. Operations and function names tell you how those variables are going to change. Because the code is meant to tell the computer what to do it's also good at telling the reader what it's doing. The only thing missing is why. Why are you calling this function with these arguments? Why did you implement that algorithm a certain way? Why aren't you using this feature of the language? As much as possible you want your code to tell the reader everything they need to know but comments can be added to fill in gaps. They help to explain to future people reading the code why you did certain things a certain way if it's not obvious.

The same goes for documenting your own classes and functions. The class name, methods, and fields should tell you a lot about what the class if for. Similarly a function name, parameters, and return type can tell you what it will do. Again the only thing missing is why. Why would I want to use this class instead of another? Why would I want to call this function? That information can be put in comments on the class or function. Then people thinking about using that class or function can understand the scenario it's meant for and decide if it meets their needs or not.

2016-03-29 - In IL: Instructions and the Stack

So now that we’ve learned where local variables are stored it’s time to learn what we can do with them. In most high level languages you write a series of symbols which indicate what you want to happen with each symbol implying the action they represent. In IL you have a series of instruction and their arguments with the name of each instruction implying the action it will perform. Before we get to instructions though we need to understand stacks.

A Stack is a data structure that can be imagined as a pile of things. You can “push” things onto the top of the pile or “pop” things off of the top of the pile. Depending on the implementation you may also be able to look at things on the top of the pile without removing them. In IL every method has an Evaluation Stack. Most instructions pop things from this stack, push things onto this stack, or both. The stack is used to store temporary values similar to how registers work in some computer processors.

There are a bunch of instructions in IL so I will start by summarizing some of the common ones.

nop (No OPeration)

Used to fill up space for various uses. Such as allowing instructions to be patched in later.

Instruction	Description	Binary Format
nop	Does nothing	0x00

ldc (LoaD Constant)

Pushes a value, determined by the instruction or its argument, onto the stack.

Instruction	Description	Binary Format
ldc.i4.m1	Loads –1 onto the stack as a 4-byte integer	0x15
ldc.i4.X	Loads X onto the stack as a 4-byte integer where X is 0-8	0x16 - 0x1E
ldc.i4.s <num>	Loads “short” 1-byte integer <num> onto the stack as a 4-byte integer	0x1F <int8>
ldc.i4 <num>	Loads 4-byte integer <num> onto the stack	0x20 <int32>
ldc.i8 <num>	Loads 8-byte integer <num> onto the stack	0x21 <int64>
ldc.r4 <num>	Loads 4-byte floating-point value <num> onto the stack	0x22 <float32>
ldc.r8 <num>	Loads 8-byte floating-point value <num> onto the stack	0x23 <float64>

ldstr (LoaD STRing)

Pushes a reference to a string onto the stack

Instruction	Description	Binary Format
ldstr <string>	Loads a reference to <string> onto the stack	0x72 <T>

<T> represents a metadata token. These are 4-byte values that indicate a location where the actual data is stored in the file containing the code.

ldloc (LoaD LOCal variable)

Push the value of a local variable onto the stack.

Instruction	Description	Binary Format
ldcloc.X	Loads the value of local variable X onto the stack where X is 0-3	0x06 - 0x09
ldcloc.s <index>	Loads the value of local variable with “short” index <index> onto the stack	0x11 <uint8>
ldcloc <index>	Loads the value of local variable with index <index> onto the stack	0xFE 0x0C <uint16>

conv (CONVersion)

Pops a value off of the stack, converts it to the type based on the specific instruction used and pushes the result onto the stack.

Instruction	Description	Binary Format
conv.i1	Converts the value on the stack to a 1-byte integer	0x67
conv.i2	Converts the value on the stack to a 2-byte integer	0x68
conv.i4	Converts the value on the stack to a 4-byte integer	0x69
conv.i8	Converts the value on the stack to a 8-byte integer	0x6A
conv.r4	Converts the value on the stack to a 4-byte floating-point value	0x6B
conv.r8	Converts the value on the stack to a 8-byte floating-point value	0x6C
conv.u4	Converts the value on the stack to a 4-byte unsigned integer	0x6D
conv.u8	Converts the value on the stack to a 8-byte unsigned integer	0x6E
conv.u2	Converts the value on the stack to a 2-byte unsigned integer	0xD1
conv.u1	Converts the value on the stack to a 1-byte unsigned integer	0xD2

box

Pops a value-type value off of the stack, boxes it as the specified reference type and pushes the result onto the stack.

Instruction	Description	Binary Format
box <type>	Boxes the value on the stack as the specified <type>	0x8C <T>

stloc (SeT LOCal variable)

Pops a value off of the stack and sets it as the value of a local variable.

Instruction	Description	Binary Format
stloc.X	Sets the value of local variable X with a value from the stack where X is 0-3	0x0A - 0x0D
stloc.s <index>	Sets the value of local variable with “short” index <index> with a value from the stack	0x13 <uint8>
stloc <index>	Sets the value of local variable with index <index> with a value from the stack	0xFE 0x0E <uint16>

add (ADDition), sub (SUBtraction), mul (MULtiplication), div (DIVision)

Pops two values off of the stack and pushes the result of the specified action onto the stack. How the action is performed and the type returned depends on the types of the values.

Instruction	Description	Binary Format
add	Adds the first value popped off of the stack to the second value popped off of the stack and pushes the result onto the stack	0x58
sub	Subtracts the first value popped off of the stack from the second value popped off of the stack and pushes the result onto the stack	0x59
mul	Multiplies the second value popped off of the stack by the first value popped off of the stack and pushes the result onto the stack	0x5A
div	Divides the second value popped off of the stack by the first value popped off of the stack and pushes the result onto the stack	0x5B

call

Used to call a method based on the argument to the instruction. The method pops its parameters off of the stack, if any, and pushes its return value onto the stack, if it has one.

Instruction	Description	Binary Format
call <method>	Calls the <method> method	0x28 <T>

ret (RETurn)

Returns from a method. Uses the value on the stack as the return value. The stack should be empty except for this value. If the method doesn't return a value then the stack should be completely empty.

Instruction	Description	Binary Format
ret	Returns from a method	0x2A

Next time we will see some of these instructions in action.

2016-03-05 - Wire Entropy

One of the most annoying things about dealing with computers is all the wires. They seem to just wrap themselves around each other until you end up with a tangled mess. Well that phenomenon can be explained by entropy. Entropy is a complicated thermodynamic quantity but it can be generalized as a measure of how chaotic a system is.

When you first arrange wires they are very neat and tidy. This is a low entropy or ordered arrangement because the specific arrangement of the parts is very important to the overall state. There are a limited number of arrangements that can be considered “neat” and “tidy”. Wires being tangled up is a high entropy or chaotic arrangement because the arrangement of the parts isn’t very important to the overall state. There are a large number of arrangements that can be considered “tangled”.

The Second Law of Thermodynamics states that the entropy of a system can never decrease without work being done to it. This means that wires won’t straighten themselves out unless someone or something forces them to. The problem is there’s no law saying entropy can’t increase. As you bump your desk, as you pull on the wires, as the world turns they are being jostled about. These small forces tend to be rather random so they can’t really be thought of as directed work. So according to the laws of physics these small forces can’t straighten out the wires and can only tangle them.

And that’s the universe for you.