Q & Stuff

R.I.P. Dorkess

2012-01-27T14:30:00.000-08:00

Dorkess (AKA Poguita): March 27, 1992-January 27, 2012

The twins, Poguita and Ping Pong (as well as two others we didn't keep, which seemed to be from different fathers) were born at our house on March 27, 1992. Poguita (yes, that is an English/Spanish pun) was named for the distinctive white stripe on her nose.

As with Slinky, I later started calling her Dorkess based on her distinctive personality. She was always extremely high strung, even for a cat. The slightest sudden noise would cause her to do her characteristic "vertical takeoff and landing" - shooting a couple feet into the air - then flee in terror, either out of the house or into a closet to hide. I used to say she never walks anywhere, she just sprints.

Her dorkiness led to a wide array of memorable incidents. In one case me, my mom, and one of my friends were watching something scary on TV. At one point, my mom screamed, at which point the entire clothes hamper exploded, throwing various pieces of clothing into the air. As it turned out, Dorkess had been sleeping in it, and completely freaked out when my mom screamed.

She was also an extremely finicky cat; nothing was acceptable to her unless you did it exactly how she wanted it. Perhaps she was narcissistic, as she did, after all, love staring at herself in shiny surfaces. Though she lacked the congenital metabolic problems Slinky had - and as a result was not so thin and slinky - she seemed to have some kind of a deformity on her back feet such that she was never able to fully retract her claws, resulting in a distinctive clicking as she walked on hard surfaces.

As she got older, she gained another distinctive attribute. For a variety of reasons, from wanting something to letting people know she was entering the house, as well as some which were just mysterious, she would use just about every muscle in her body to howl at an unbelievable volume, which vaguely resembled a baby crying; as one friend put it the first time he heard it, "What the heck was that?". On a couple occasions she even howled so loudly that she got dogs howling along with her. One particularly interesting feature of this was that, when howling, her meows were neither identical nor random, but followed a well-established pitch contour (e.g. there was always a large drop in pitch during the third meow).

Apart from a couple of serious but temporary cases where she was severely sick (and could conceivably have died), she was in fairly good health until just recently (though she certainly showed her age). She did end up going completely deaf a few years ago, but this was probably for the best, as afterwards she was much calmer and less high strung.

At one point a couple years ago, she began accumulating fluid around her lungs, making it difficult to breath. This probably would have killed her, but with regular medication with Lasix (the drug) the problem essentially went away (though the Lasix did seem to be doing some harm to her kidneys and liver). We never did learn the root cause, and it's possible that's ultimately related to why she died. For one reason or another, she eventually decided that she wanted to die, and simply stopped eating. This, on top of her already weakened state due to old age, resulted in her death a week later. The ultimate reason for this choice remains unknown.

One of Dorkess' common places to sleep

The twins: Dorkess (left) and Slinky (right)

The twins sleeping, Zen-style; best guess is that Slinky is in front, Dorkess is in back

Me and Dorkess, 5-10 years ago

Rest in peace, Dorkess.

Anti-Piracy for Dummies

2011-12-30T16:35:00.000-08:00

Are you a content producer or the holder of copyright you didn't actually create? Are filthy thieving pirates downloading and uploading your content all across the web, driving your gross revenue into the negative? Fear not! Immigration and Customs Enforcement is here to help!

Beginning several years ago, the US Immigration and Customs Enforcement agency, in conjunction with the Department of Justice and the Department of Homeland Security, now handles copyright and other intellectual property enforcement through Operation In Our Sites. Through this program ICE has the authority to forcibly seize web sites that infringe your copyrights et al, providing critical relief for those besieged by piracy such as you. Once seized, these sites prominently display the ICE et al logos and a brief explanation that the site has been seized. As an example, observe the fate that befell torrent-finder.com for the rampant theft of copyrighted works it harbored.

It's a common misconception that you need to have special government connections, secret backroom deals, or incriminating evidence on politicians to request such a seizure. In fact, this is not true. Any copyright, patent, or trademark holder with a Windows computer may request such a seizure for any legitimate reason, and ICE will rapidly respond, taking the offending site offline with all due haste.

To request such a seizure, simply follow these easy steps:

Log onto your Windows computer with an account with administrator privileges (e.g. the Administrator account)
Open the Run dialog, either through the Start menu or by pressing WINKEY+R
Type in notepad "C:\Windows\System32\drivers\etc\hosts". If your Windows directory is not "C:\Windows", you will need to substitute the correct path.
For each pirate site you wish to have seized, add the line "74.81.170.110 [site domain name]" to the bottom of the file. For example, to seize TechDirt, a notorious site dedicated to the promotion of piracy and the suppression of the free speech of congressmen and businesses, you would add "74.81.170.110 www.techdirt.com"
Save the file and close Notepad
Wait for your request to be processed by ICE. This typically varies from a few seconds to a day or so. If the sites are still online after several days, you should probably go back and make sure you did not make any mistakes in performing the above procedure.

That's all! Fast. Easy.

With you and ICE working together, we can all look forward to a piracy-free tomorrow!

This post inspired by tsavory.

Public Service Announcement

2010-10-18T15:47:00.000-07:00

While solar panels are dark blue, almost black, they are also reflective. This means that they will likely appear white or some other bright color, which may be a big shock (and a big aesthetic problem) if you have a dark roof and the panels are clearly visible.

My parents are NOT amused.

Update: Actually this is only the case when the sky is cloudy, which it was the day my parents had the panels installed. When the sky is clear they look like they do without the reflection.

RIP Bigg'ns

2010-09-21T21:34:00.000-07:00

The big, old puppy

June 17, 1997-September 21, 2010

Public Service Announcement

2010-09-08T14:03:00.001-07:00

When you call Discover card customer service, the very first thing you have to do is enter the last 4 digits of your Discover card, last 4 digits of "your social security number", and your ZIP code. It's important to note here that "your social security number" and "your ZIP code" do NOT mean "your social security number" and "your ZIP code"; it means the social security number and ZIP code of the primary cardholder, which may or may not be you.

Discover card apologizes for the inconvenience of refusing to even let you talk to a real person without providing something it specifically did not ask for.

NWScript Stack System

2010-08-04T11:00:00.000-07:00

Note: SW has written a new post, talking about NWScript in general, akin to my post yesterday (though possibly in more detail than mine; I haven't actually read it all yet).

So, now we know where we are (the NWScript system), and where we need to go (LLVM assembly). Now, how do we get there?

Well, a lot of things are simple enough, requiring only trivial use of LLVM and a parser. But after investigating the NWScript system for this purpose, I identified several areas that would be nontrivial and would require some thought and effort, which I'll discuss.

The first challenge - that is, a nontrivial design issue - was the stack machine. Stack machines are easy to interpret, but harder to convert to something like LLVM assembly that uses registers (like real assembly languages) and strongly declared and typed variables (unlike real assembly languages). Stack machines use a huge number of stack locations during execution, the vast majority of them (more than 96% of them, in one sample I looked at) temporary copies that last only until the next math (or other) instruction. From the opposite perspective, it's necessary that all accesses of a single variable be mapped to the same memory location, regardless of where the variable is, relative to the top of the stack. It's even possible that multiple separate locations in the code could create a stack location that represents only a single variable, despite being created in multiple places.

To illustrate these problems, a few examples:

// var1 * 0x1E
CPTOPSP FFFFFFEC, 0004
CONSTI 0000001E
MULII
// + var2
CPTOPSP FFFFFFEC, 0004
ADDII
// var3 =
CPDOWNSP FFFFFFF0, 0004
MOVSP FFFFFFFC

Here, we can see two stack locations are created that do not represent variables at all, but rather temporary parameters to the MUL instruction. A third temporary that also is not a real variable is created as the return value to the MUL instruction, which is then used as a parameter to the ADD instruction along with a fourth temporary copied from a variable. Finally, a fifth temporary is created for the return value from the ADD instruction, which is copied down to a result variable and destroyed. The C code for this would be var3 = (var1 * 0x1E) + var2;

// if (3 == 0)
00000045 CONSTI 00000003
0000004B CONSTI 00000000
00000051 EQUALII
00000053 JZ off_00000065
// true: var = 1
00000059 CONSTI 00000001
0000005F JMP off_0000006B
// false: var = 2
00000065 CONSTI 00000002
0000006B

In this second case, we have an optimized variable initialization where a stack location is created in two separate locations (depending on whether a condition is true), but is in reality only a single variable. This is from a script that has int g_i = (3 == 0 ? 1 : 2);

It may also be possible to use the stack as, well, a stack, building up a variable-length list of things as they're processed in one loop, then popping them in a second loop. I can't think of a practical use for this off the top of my head (something that is both useful and couldn't be accomplished any other way), but it might be possible.

So, the stack system poses challenges related to identifying variables. However, a second, less obvious problem exists, although it's not as specific to stack machines. In this case, the problem relates to functions. In NWScript, a call consists of:

Reserve a temporary slot on the stack for the return value
Push the parameters in reverse order
Call the function
Copy and pop the return value

As implied, the caller allocates space for the return value, and the called function must remove all parameters before return. This causes a problem for us, because we need to keep track of stack positions so that we can locate variables, and alignment of the stack would be impossible as long as we have no idea what a function call will do to the stack.

The solution I came up with to this problem (as well as other problems, which I'll talk about in the future), was a two-pass system that performs analysis and intermediate code generation (intermediate code is an expanded form which deals with variable references rather than the stack, making it much easier to work with; this intermediate code would then be converted to the output code type in a third pass). The two passes could have been done in a single pass, but this would have been quite messy and needlessly memory-hungry, as opposed to the more elegant and efficient two-pass system.

First Pass
The first pass through the script file performs a couple tasks. It identifies functions and code flow blocks: the largest groups of instructions that execute as an atomic unit and have only a single execution path from the first to the last instruction in the block. It also determines the number of parameters and return values for each function (in NWScript, functions only have a single return value, but when the bytecode is generated, structs and other complex types are flattened to primitive types, making it look like there are multiple return values).

This pass is quite simple. It proceeds by scanning through the code, beginning with the main function, parsing each instruction as it goes. The current stack pointer (but not an actual stack) is maintained from instruction to instruction. As well, a code flow graph is created by watching for branch instructions and creating new flow blocks and splitting old ones (if a branch jumps into the middle of an existing flow, that flow must be split, as it's not an atomic unit). Finally, entries for functions are created as they're encountered.

The biggest trick here is dealing with function calls. The effect of other operations on the stack can be trivially calculated by decoding the instruction, but we can't step past a call instruction until we know the stack displacement. The same is true for calls to API functions, but we already know exactly what they do to the stack, as those are a closed set.

What I decided to do was to use a task queue. When a new, previously unencountered function is encountered in a call, a new function entry and task queue entry corresponding to the function are created, and the current analysis task is marked as blocking on that function. Conditional branches are handled more or less the same way: a new task is created for one branch, though not blocking on anything, and analysis continues at the other branch. Whenever the current task blocks (e.g. it calls an unanalyzed function), analysis switches to the first task in the queue that is not blocking on anything, and execution continues from there.

Tasks ultimately complete when a return is encountered. When that occurs, the number of parameters for the function is calculated by the difference in stack pointer from the beginning of the function to the end. The function is marked as analyzed, and any tasks blocking on the function are unblocked and may potentially continue analysis. The number of return values is determined by observing the lowest stack address written to within the function. This requires that all paths through a function be evaluated, but as the return value does not affect overall stack displacement, tasks blocking on the function may resume prior to determining the exact number of return values.

While this can potentially generate a large number of blocked tasks in the queue, so long as the script does not contain a loop that has no exit path or a function that calls itself recursively without a path that returns, this is guaranteed to ultimately locate a function that can return. While functions may have multiple paths from beginning to end, and all must eventually be traversed, we need only a single path to return to know the function's displacement, resulting in unblocking of tasks waiting on that function. This discovery process cascades, and analysis of all routes through the script eventually completes.

Second Pass
After the completion of the first pass, we now know all functions, code flows, and the number of parameters and return values for each function. The second pass performs several functions:

Determine the types and locations of local and global variables and create variable objects for them
Determine the types of function parameters and return values
Generate the intermediate code

The second pass is somewhat simpler in code flow logic, but much more complicated in terms of the amount of work done. It too operates on a task queue system, but has no concept of blocking - the task queue exists merely to queue up alternate paths for processing after the current path completes. It operates locally on a function using the code flow graphs as rails to guide analysis, processing each function completely before moving on to the next.

The code for this pass resembles a mini-interpreter (well, I suppose it is), including a stack filled with references to the variable objects at that location. A new variable object is created each time some manner of instruction pushes a variable on the stack. To make things simpler during processing and final code generation, variables are explicitly created and destroyed with dedicated instructions in the intermediate code, unlike the implicit generation/destruction in the bytecode.

Because the stack is necessary to determine what variables individual instructions reference, functions must, as in the first pass, be executed in control flow order, rather than simply evaluating each flow in the list in random order (as we do with functions). The stack at the end of each flow is saved until analysis of the function completes, so that successor flows evaluated later can pick up the stack where the previous flow left off (and one other reason I'll explain in a second).

Most of the details of the second phase relate not to the topic of this post, but to later ones. One detail worth mentioning, however, is that after all flows for a function have been evaluated, stack merging occurs. Because it's possible that a stack location might be created in two separate locations that together form a single variable (as in the example above), when multiple flows converge in a single successor flow, the stacks from each of the predecessor flows must be merged: for each offset in the stacks, the variables in each corresponding position are merged, eliminating all but one copy. Because the intermediate code representation is flexible, variable merging is trivial, and requires no modification of the intermediate code itself.

However, for this and other reasons, this compiler does not, as of now, support variable use of the stack: when the stack is extended to a variable length by a loop or some such, as mentioned earlier. There is no way to generate such a structure in NWScript (the scripting language), and manually-written bytecode files are anywhere between incredibly rare and non-existent, so we thought that was a reasonable omission.

One really cool thing about this system, however, is that the host program can be a hybrid of interpretation and compilation. E.g. the compilation of all scripts can be offloaded to a worker thread when a module is loaded to compile in the background, and the host program can use the interpreter for a script until compilation of that script finishes. The interpreter could also be used as a fall-back for scripts the compiler is unable to compile for one reason or another, such as those with evil stack usage.

Below is an example of a random block (a flow, to be precise) of bytecode and its corresponding intermediate code. Note that the addresses differ by 0xD because the bytecode block is generated by a disassembler that includes the file header in the address:

00005282 ACTION GetTimeHour(0010), 00
00005287 CPTOPSP FFFFFF34, 0004
0000528F ACTION StringToInt(00E8), 01
00005294 ACTION GetTimeHour(0010), 00
00005299 SUBII
0000529B ADDII
0000529D CPDOWNSP FFFFFF00, 0004
000052A5 MOVSP FFFFFFFC
000052AB CONSTI 00000000
000052B1 CONSTI 00000000
000052B7 CONSTI 00000000
000052BD CPTOPSP FFFFFEF8, 0004
000052C5 ACTION SetTime(000C), 04
000052CA CPTOPSP FFFFFF04, 0004
000052D2 CONSTI 00000000
000052D8 LTII
000052DA JZ off_00005304

00005275: CREATE 01F36000 ( temp SSA int )
00005275: ACTION 0010 (0) 01F36000 ( temp SSA int )
0000527A: CREATE 01F36030 ( temp SSA string )
0000527A: ASSIGN 01F36030 ( temp SSA string ), 02102C10 ( string )
00005282: CREATE 01F36060 ( temp SSA int )
00005282: ACTION 00E8 (1) 01F36060 ( temp SSA int ), 01F36030 ( temp SSA string )
00005282: DELETE 01F36030 ( temp SSA string )
00005287: CREATE 01F36090 ( temp SSA int )
00005287: ACTION 0010 (0) 01F36090 ( temp SSA int )
0000528C: CREATE 01F360C0 ( temp SSA int )
0000528C: SUB    01F360C0 ( temp SSA int ), 01F36060 ( temp SSA int ), 01F36090 ( temp SSA int )
0000528C: DELETE 01F36090 ( temp SSA int )
0000528C: DELETE 01F36060 ( temp SSA int )
0000528E: CREATE 01F360F0 ( temp SSA int )
0000528E: ADD    01F360F0 ( temp SSA int ), 01F36000 ( temp SSA int ), 01F360C0 ( temp SSA int )
0000528E: DELETE 01F360C0 ( temp SSA int )
0000528E: DELETE 01F36000 ( temp SSA int )
00005290: ASSIGN 02102910 ( int ), 01F360F0 ( temp SSA int )
00005298: DELETE 01F360F0 ( temp SSA int )
0000529E: CREATE 01F36150 ( temp SSA int )
0000529E: ASSIGN 01F36150 ( temp SSA int ), 01F36120 ( const int )
000052A4: CREATE 01F361B0 ( temp SSA int )
000052A4: ASSIGN 01F361B0 ( temp SSA int ), 01F36180 ( const int )
000052AA: CREATE 01F36210 ( temp SSA int )
000052AA: ASSIGN 01F36210 ( temp SSA int ), 01F361E0 ( const int )
000052B0: CREATE 01F36240 ( temp SSA int )
000052B0: ASSIGN 01F36240 ( temp SSA int ), 02102910 ( int )
000052B8: ACTION 000C (4) 01F36240 ( temp SSA int ), 01F36210 ( temp SSA int ), 01F361B0 ( temp SSA int ), 01F36150 ( temp SSA int )
000052B8: DELETE 01F36240 ( temp SSA int )
000052B8: DELETE 01F36210 ( temp SSA int )
000052B8: DELETE 01F361B0 ( temp SSA int )
000052B8: DELETE 01F36150 ( temp SSA int )
000052BD: CREATE 01F36270 ( temp SSA int )
000052BD: ASSIGN 01F36270 ( temp SSA int ), 02102910 ( int )
000052C5: CREATE 01F362D0 ( temp SSA int )
000052C5: ASSIGN 01F362D0 ( temp SSA int ), 01F362A0 ( const int )
000052CB: CREATE 01F36300 ( temp SSA int )
000052CB: LT     01F36300 ( temp SSA int ), 01F36270 ( temp SSA int ), 01F362D0 ( temp SSA int )
000052CB: DELETE 01F362D0 ( temp SSA int )
000052CB: DELETE 01F36270 ( temp SSA int )
000052CD: TEST   01F36300 ( temp SSA int )
000052CD: DELETE 01F36300 ( temp SSA int )
000052CD: JZ     000052F7

And lastly, perhaps getting ahead of myself, the same segment after running it through my variable optimization pass:

00005275: CREATE 01F36000 ( temp SSA int )
00005275: ACTION 0010 (0) 01F36000 ( temp SSA int )
00005282: CREATE 01F36060 ( temp SSA int )
00005282: ACTION 00E8 (1) 01F36060 ( temp SSA int ), 02102C10 ( merged string )
00005287: CREATE 01F36090 ( temp SSA int )
00005287: ACTION 0010 (0) 01F36090 ( temp SSA int )
0000528C: CREATE 01F360C0 ( temp SSA int )
0000528C: SUB    01F360C0 ( temp SSA int ), 01F36060 ( temp SSA int ), 01F36090 ( temp SSA int )
0000528C: DELETE 01F36090 ( temp SSA int )
0000528C: DELETE 01F36060 ( temp SSA int )
0000528E: ADD    02102910 ( merged int ), 01F36000 ( temp SSA int ), 01F360C0 ( temp SSA int )
0000528E: DELETE 01F360C0 ( temp SSA int )
0000528E: DELETE 01F36000 ( temp SSA int )
000052B8: ACTION 000C (4) 02102910 ( merged int ), 01F361E0 ( merged const int ), 01F36180 ( merged const int ), 01F36120 ( merged const int )
000052CB: CREATE 01F36300 ( temp SSA int )
000052CB: LT     01F36300 ( temp SSA int ), 02102910 ( merged int ), 01F362A0 ( merged const int )
000052CD: TEST   01F36300 ( temp SSA int )
000052CD: DELETE 01F36300 ( temp SSA int )
000052CD: JZ     000052F7

For those keeping score, that's 17 instructions in the original bytecode, 43 in the raw intermediate code (26 that are create or destroy, 9 that are assigns to temporary variables), and 19 in the optimized intermediate code (10 that are create or destroy; if that still sounds like too many, note that all of those variables will be converted to registers in LLVM).

& NWScript

2010-08-02T12:05:00.000-07:00

The attentive might have wondered why I bothered to spend a moderate amount of timewriting about a topic I'd already moved past, which is kind of uncharacteristic of me. As I said before, I had looked at LLVM for a couple days a couple weeks prior to the corresponding blog post, then moved on (I can't recall if there was anything in between LLVM and cache-oblivious algorithms).

Well, part of the reason I didn't spend too much time on LLVM was because while it's neat, I didn't have an immediate use for it. However, a few days before I wrote said post Skywing randomly came up to me and asked if I wanted to write a native code compiler for NWScript, the scripting language in NeverWinter Nights 1 and 2, for the client and server he's been writing. Suddenly I had an immediate and interesting use for LLVM.

NWScript (for more information see this) is a language based on C, and supports a subset of the features. It supports only a small number of data types: int, float, string, and a number of opaque types that are more or less handles to game structures accessed solely via APIs. It also supports user-defined structures, including the built-in type vector (consisting of 3 floats), though it does not support arrays, pointers, etc. All variables and functions are strongly typed, although some game objects - those referred to with handles, such as the "object" type - may not be fully described by their scripting type. NWScript has a special kind of callback pointer called an action (a term which, confusingly, has at least two additional meanings in NWScript), which is more or less a deferred function call that may be invoked in the future - specifically, by the engine - and consists of a function pointer and the set of arguments to pass to that function (a call to an action takes no parameters from the caller itself).

NWScript is compiled by the level editor into a bytecode that is interpreted by a virtual machine within the games. Like the Java and .NET VMs, the VM for NWScript is a stack system, where a strongly-typed stack is used for opcode and function parameters and return values. Parameters to assembly instructions, as with function calls, are pushed on the top of the stack, and instructions and function calls pop the parameters and, if there is one, push the result/return value onto the top of the stack. Data down the stack is copied to the top of the stack with load operations, and copied from the top of the stack to locations further down by store operations.

Unlike those VMs, however, NWScript uses a pure, integrated stack system, implementing global and local variables through the stack, as well. Global variables are accessed through instructions that load/store values at indices relative to the global variable pointer BP, which is an index into the stack. Normally, global variables are at the very bottom of the stack, pushed in a wrapper function called #globals before the script's main function is called; there are opcodes to alter BP, though this is not known to ever be used. Local variables are accessed by loads and stores relative to the top of the stack, just as with the x86 (ignoring the CPU registers). Unlike the x86, however, return addresses are not kept on the stack, but like Itanium are maintained in a separate, program-inaccessible stack.

Oh, and for those wondering, the Java and .NET VMs have separate mechanisms for global and local variables that do not use the stack. This is actually rather surprising - you would expect them to use the stack at least for local variables, as actual processor architectures do (when they run out of registers to assign).

The following show a couple random pieces of NWScript bytecode with some comments:

; Allocate int and object local variables on the stack
0000007F 02 03                    RSADDI
00000081 02 06                    RSADDO
; Push parameter 0
00000083 04 06 00000000           CONSTO 00000000
; Call game API function
00000089 05 00 0360 01            ACTION GetControlledCharacter(0360), 01
; Copy return value to the object local variable
0000008E 01 01 FFFFFFF8 0004      CPDOWNSP FFFFFFF8, 0004
; Pop the return value
00000096 1B 00 FFFFFFFC           MOVSP FFFFFFFC

; Allocate float on stack
00000015 02 04                    RSADDF
; Incredibly stupid way of setting the float to 3.0f
00000017 04 04 40400000           CONSTF 3.000000
0000001D 01 01 FFFFFFF8 0004      CPDOWNSP FFFFFFF8, 0004
00000025 1B 00 FFFFFFFC           MOVSP FFFFFFFC
; Assign the current stack frame to BP
0000002B 2A 00                    SAVEBP
; Call main()
0000002D 1E 00 00000010           JSR fn_0000003D
; Restore BP to what it was before (not that it was anything)
00000033 2B 00                    RESTOREBP
; Clean up the global variables
00000035 1B 00 FFFFFFFC           MOVSP FFFFFFFC
0000003B 20 00                    RETN

; Push last two parameters to FloatToString
0000043C 04 03 00000009           CONSTI 00000009
00000442 04 03 00000012           CONSTI 00000012
; Divide 5.0f by 2.0f
00000448 04 04 40A00000           CONSTF 5.000000
0000044E 04 04 40000000           CONSTF 2.000000
00000454 17 21                    DIVFF
; Return value of DIVFF is the first parameter to FloatToString
00000456 05 00 0003 03            ACTION FloatToString(0003), 03
; Return value is second parameter to SendMessageToPC. Push first parameter.
0000045B 04 06 00000000           CONSTO 00000000
00000461 05 00 0176 02            ACTION SendMessageToPC(0176), 02

Stack systems - especially this one, where everything is held on the stack - make for VMs that are very simple and easy to implement, and Merlin told me in the past that they're easy to compile to native code, as well. So it's not surprising that the developers used this architecture for NWScript.

You might notice that Skywing has started a series of his own on the project, today. I actually wrote this post several weeks ago, but was waiting until the project was done to post about it. But now that it looks like he's gonna cover it, I need to start posting or I'll end up posting after him despite starting before him.

2010-06-28T11:04:00.000-07:00

Gah, this NWScript compiler is absolutely idiotic.

How to push a constant onto the stack in 4 easy steps:

reserve a spot on the stack for the constant
push the constant on top of the stack
copy the constant to the reserved space
pop the top (pushed in 2) off the stack

& LLVM

2010-06-27T13:20:00.000-07:00

A few weeks ago - before I got into cache-oblivious algorithms - I briefly had a different topic du jour. In particular, I had just learned about Low-Level Virtual Machine, and spent a couple days researching that.

LLVM is a bit hard to explain, because the boundary around what it is is rather fuzzy. To sum it up in a noun phrase, I'd say that LLVM is a modular compilation system and virtual machine. I say "compilation system" because it doesn't really consist of an actual compiler, and there's a lot of it that is outside the definition of a compiler.

The core idea is that you have a program in some programming language which is compiled into a platform and language independent intermediate format. From there, the program is translated into some machine code (whatever type is used on the machine it's being run on) at a later time, either during execution (just-in-time compiling) or prior to execution (e.g. an installer converting the application to native code when the program is installed), and executed. In that sense there's some similarity to the .NET platform and Java platform, though it isn't totally analogous to those.

LLVM is a collection of modules that makes the various parts of the process possible. These components form a redundant superset of a full system, so you can choose which you want for a particular purpose and leave the rest.

Going chronologically through that process, the first module in LLVM is its assembler. LLVM does not directly parse and compile any particular programming language. When creating a working compiler, you must create a language parser that processes a program and performs any language-specific optimizations. LLVM takes as its input a program in LLVM assembly plus various metadata that could be useful later in the process, and assembles them into language and platform independent LLVM intermediate bytecode. A few of the open-source parsers already available for LLVM include C, C++, Objective-C, and many others; there are even parsers under development that take .NET and Java bytecodes as input.

The LLVM assembly language differs substantially from the Java and .NET bytecode languages, and bears some resemblance to RISC assembly languages such as MIPS and PPC. LLVM assembly consists of an infinite set of Single Static Assignment (SSA) registers; each register can be assigned only once, and a new register must be allocated for the result of every computation. However, LLVM also stores a significant amount of metadata, such as call graphs and other things at a higher level than a simple assembly language, in the bytecode (language-dependent metadata provided by the compiler is also stored for later use by language-dependent modules, e.g. if a particular language has a runtime environment that needs more information than just the native code). This combination of the assembly language design and rich metadata allows the optimizer and native code generator to act much more effectively, in a language-independent manner, than if they were working on a bare assembly language. Yet they are compact enough to not be significantly larger than the equivalent native code alone.

The next step in the process is global optimization. LLVM implements a substantial number of language-independent optimization algorithms, and compiler writers can use some or all of them as they like. Because of the metadata stored with the assembly language, LLVM is not limited to dealing simply with assembly, and the effectiveness of it's optimization algorithms resembles that of a standalone compiler (e.g. Visual C++). Even better, because optimization occurs after the entire program has been assembled, LLVM can do whole-program optimizations (known as link-time code generation in VC++ and others) that are outside the ability of simple compilers that only look at a function or a source module at a time.

After optimization comes native code generation (or, alternately, you could interpret the bytecode without producing native code). This step takes the assembly and metadata that has undergone language and platform independent optimization and creates executable machine code, usually after performing platform-specific optimizations, and the code is then executed. Native code generators are language-independent, interchangeable modules invoked by LLVM and, given a program in LLVM bytecode, native code can be generated for any platform that a native code generation module exists for (x86 and PPC are a couple that are already supported with open-source implementations).

Finally, LLVM provides a runtime system that allows for various runtime tasks to be performed. We'll get to the other tasks later, but one to mention here is that this runtime system allows language or platform specific runtime environments to interface with LLVM-generated native code, as well as interfacing with system or dynamic link libraries. Language-dependent metadata provided by the language compiler in the distant past is also available for use here.

So, that's the basic process. However, as I've been describing the logical process and not the details, this description is much more linear than reality. As was mentioned, LLVM provides a number of modules that may be optionally used, and some are redundant. As well, there's also flexibility in how the modules interact.

LLVM especially provides a great deal of flexibility in the timing of optimization and native code generation. While LLVM can be used like a normal compiler, taking in LLVM assembly and generating an executable with native code that can be directly executed on the target platform, it does not need to be. It's equally possible to store the LLVM bytecode in a platform-independent "executable" and optimize it and compile it to native code at a later point, either on execution or prior to execution. LLVM can even compile individual functions to native code the first time they are called, allowing some portions of the program to potentially never be compiled at all.

Finally, LLVM also supports profiling and dynamic recompilation of a program. The LLVM runtime is capable of profiling the native code of the program at runtime, determining where the program spends most of its time, what functions are executed most often, etc. based on actual usage. It can then recompile the program from bytecode, either between executions or during idle time, using this profile data to perform optimizations based on actual usage.

So, that's squishy. But why should you care? Well, a few reasons. Probably the most attractive is that you can make a full, optimizing compiler for a language that will generate native code for many platforms simply by writing a parser and LLVM assembly generator - thousands of lines of code compared to hundreds of thousands or millions (see here for one example of this). Alternately, if you're designing a processor for some reason (work, school, or hobby), you can write a native code generator and instantly support all the languages parsers already exist for. And then there are some less obvious uses, such as using the metadata generated by LLVM to perform complex analysis of source code for the purpose of searching for bugs, security holes, etc.

LLVM is a free open-source project that may be used in free or commercial projects, open-source or proprietary. Its largest benefactor is Apple, who uses it extensively. Other companies such as Adobe also use it in various ways. For more information, see this brief summary of the LLVM system, and the LLVM web page.

& Cache-Oblivious Algorithms (Updated)

2010-06-23T17:00:00.000-07:00

Hey, does anybody remember the days when I actually wrote stuff on this blog? Those were good times.

Well, in case anybody actually remembers that far back, one of the things I'm known for is my topic du jour manner of self-education. I hear about some topic (or it comes up in some thought process), I research it for anywhere from a few days to a few months (however long it holds my interest), then I move on to some other topic. This week's topic du jour is cache-oblivious algorithms.

To explain what cache-oblivious algorithms are and why they're good, let's work through an example.

Suppose we've got a sorted array of 2^24 32-bit values, for a total size of 64 MB, and we need to determine if it contains a given value (if not, to find the nearest values). As we know that the list is sorted, binary search is the obvious choice, as it's known to be O(log N) complexity; note also that a sorted array is effectively an implicit binary search tree with items stored in-order, and the binary search is just a traversal of that tree. This complexity dictates that the search will require approximately log2(2^24) = 24 comparisons, each by definition involving a memory access (obviously, as the array is stored in memory).

Now consider a similar array containing 2^8 32-bit values (total size of 1 KB). According to the big O, a search through this array will take about 8 comparisons - 1/3 as many as the 2^24 array. Now, while these two numbers are accurate, they're highly misleading. By that measure, you'd expect it to take three times as long to perform the 2^24 search as the 2^8. It doesn't. In fact, the difference is well over an order of magnitude.

The reason for this discrepancy is the assumption that all memory accesses are equal. This is invalidated by the existence of processor (and other) caching, where cache hits are significantly faster than cache misses, as well as Non-Uniform Memory Architectures, where different memory banks have different access times for different processors. The 1 KB array can easily be held entirely in the processor's L1 cache, and in theory all accesses will be cache hits. The 64 MB array, on the other hand, can't even be held in L2 or L3 cache, so most memory accesses will be cache misses, and must go all the way to main memory.

Of course, main memory isn't that extreme of an example, as it isn't too much slower than processor cache. The real killer is when you have something (e.g. a database) that can't be held entirely in memory, and must be read from disk as needed (or worse, accessed over the internet at a speed that makes hard disks look fast). Hard drives are about a million times slower than RAM, meaning that each and every disk access is an excruciating performance hit, and the internet can be an order of magnitude worse.

Unsurprisingly, a massive amount of research effort over the last half a century has been in minimizing that amount that must be read from disk, especially in the class of cache-aware algorithms. Cache-aware algorithms are algorithms that are tuned (typically parametrized) for a specific system configuration (e.g. cache size) to achieve performance superior to algorithms that don't take such configuration into consideration.

One of the most common cache-aware algorithms, used in most file systems and database structures, is the B-tree (and family members), an upside-down (non-binary) search tree designed to minimize the number of disk accesses in searching data sets too large to fit entirely into memory. The B-tree is cache-aware because the block size can be adjusted to perform optimally on a given system configuration through either abstract math or actual benchmarks, and the optimal size for one configuration may perform poorly on another configuration.

Surprisingly, only in the last decade have people seriously investigated whether it is possible to create algorithms that make optimal use of a system configuration regardless of what exactly that configuration is, with no parametrization. This type of algorithm is called cache-oblivious algorithms.

Sometimes this is easy. A sequential scan of an array that does something on every element in order is cache-oblivious because it produces the provably minimum number of cache misses regardless of how the cache works. Divide and conquer algorithms that access each item in an array are also generally cache-oblivious and provably optimal because they ultimately divide enough to operate only on what's in a single cache line, regardless of what size the cache line is, before moving on to the next cache line (assuming, of course, that the size of each element is small in relation to the size of a cache line); in other words, they have a more or less linear scanning memory access pattern.

Binary search, however, is not cache-oblivious, as it's not a true divide and conquer algorithm in the sense that matters to us; specifically, it does not access all elements, and therefore does not get to take advantage of the predominant locality in the array. However, we can make a cache-oblivious implicit binary search tree by changing the ordering of items. To maximize performance, we want to lay out the nodes of the binary tree such that child nodes are as close as possible to their parents as often as possible, resulting in a minimal number of cache misses.

The key here is what's called the van Emde Boas layout (VEB) (you can tell I use HTTPS Everywhere because my Wikipedia links are all HTTPS). The basic idea is that the (triangular when drawn on paper) tree is divided recursively into (triangular) subtrees, with all nodes in each subtree being clustered together. This gives it a fractal structure with child and parent nodes being as close as possible to each other, maximizing cache locality during searches without needing to know the details of the cache system. A short tree in this form is shown below; below that is a comparison with trees in in-order, breadth-first (BFS), and depth-first search (DFS):

It's worth noting that cache-oblivious structures may or may not be as fast/faster than the simpler forms when the entire data set is in the same level of cache (whether you're talking about L1, RAM, etc.). One of the papers (the same one the images are from) examined the performance of static (non-changing) binary trees stored in in-order, BFS (an order that gives some cache locality while still being trivial to calculate child positions for), DFS, and VEB order, as well as two cache-aware search tree formats. In this experiment, the tree was stored in memory and cached in the processor cache - cache hits stay in the processor, cache misses go to main memory.

In the case of VEB, the complex fractal structure makes it nontrivial to calculate the position of a node's children in the array. As a result, when the entire data structure is in cache, calculation of child position takes longer than memory accesses, and VEB is about 40% slower than the standard in-order ordering. VEB begins to outperform in-order ordering once about half of the tree does not fit into cache; this calculation complexity problem can be overcome by storing child pointers with each node, but this is rather self-defeating, as this only multiplies the amount of data that has to be fit into the limited cache. In almost all cases, the cache-aware algorithms were superior to the others, but obviously require tuning to the particular cache, which is exactly what we're trying to avoid. BFS also performed admirably, always at least 15% faster than in-order ordering, and superior to VEB when more than ~1.5% of the data was able to fit into cache.

Another article compared a cache-oblivious binary heap based on VEB ordering with a standard binary heap using BFS ordering, in the context of a real-world internet page cache in actual use. Here, the heap is stored on (solid state) disk and cached in memory - cache hits go to memory while cache misses go to the disk. As in the previous benchmark, VEB performed 30% worse than the standard BFS when the entire tree could be stored in cache, but outperformed BFS when more than 0.2% of the tree was not stored in memory (I would guess this threshold is so low due to the many order of magnitude difference between memory and disk performance). At the other end, VEB peaked at 10x the speed of BFS when most of the tree was not cached. I imagine the reason this wasn't much higher was that in this real-world benchmark the priority queue was very small relative to the other data that is being accessed, and as such performance was dominated by other operations.

In the ~10 years researchers have been working on this, an array of cache-oblivious algorithms have been described, such as searching, sorting, linked lists, heaps, matrix multiplication and transposition, and various geometric algorithms such as 3D bounding volumes. The list of stuff I've seen so far (though not necessarily read through completely) is shown below, though I'm certain there are other things out there as well.

Cache-Efficient Layouts of Bounding Volume Hierarchies [and space partitioning]
Cache-Oblivious Algorithms (overview and survey)
Cache-Oblivious Algorithms and Data Structures (overview and survey)
Cache Oblivious Distribution Sweeping (sorting and various geometric algorithms)
Cache-Oblivious Dynamic Search Trees
Cache-Oblivious Priority Queue and Graph Algorithm Applications
Cache Oblivious Search Trees via Binary Trees of Small Height
You're Doing It Wrong (overview and heap algorithm applied to a real-life internet cache program)

When Size Matters

2010-05-25T13:15:00.000-07:00

I and another person, who is an IT professional, spent some time this weekend doing some volunteer work at a charity - more specifically, a homeless shelter and rehabilitation clinic, though any more details information isn't particularly relevant. Our task was to do "computer stuff", including basic maintenance on all their computers (those in the administration offices and those for use by residents), as well as take a look at what they had in storage.

While the computers available to residents weren't bad (about 5 years old or less), the situation in the office was more grim. Almost all of the computers were Pentium 3s and 4s, most with 256 megs of RAM and running Windows 2000 with Internet Explorer 6. That's right, Windows 2000 and IE6, which are both several years past end of life, and thus inherently insecure; oh, and did I mention that all the office staff run with admin privileges?

So, we started off with the easy stuff: chkdsk (full disk surface scan) and defrag on all of them. We intended to run virus scans on all of them, but were repeatedly thwarted by bad CD-ROM drives and stupid video cards that prevented us from using the AV boot disks I'd burned for the occasion (as I didn't trust the computers to not have rootkits), and eventually we had to resort on many computers to just running the AV from inside Windows.

While there were a few more specific problems with the computers, one universal complaint among the office staff was that the computers were anywhere from slow to extremely slow. While defrag no doubt helped a little with that (the computers were between 5 and 40% fragmented), the primary problem appeared to be something else entirely. Most of the computers had 256 megs of RAM, and on boot most of them were using anywhere from 210 to 260 megs of memory; add in 20 megs of memory for IE (I wanted to switch them to Firefox or a newer version of IE, but as both of those used significantly more memory that wasn't really an option), 30-40 megs for an Office app or two, and the observation that Windows starts disk-thrashing when you get to about 85% of physical memory used (about 220 megs), and it was clear that the computers were severely disk-thrashing.

So, memory upgrades were the obvious prescription. But that raises the question: why were the computers using so much memory to begin with? Anyone who remembers back from the day 10 years ago, including both myself and the other guy, can tell you that 256 megs should be plenty for Windows 2000 (and perhaps even XP). Given all the available evidence - that the computers ran Windows 2000 and IE6 in admin mode, our inability to do a proper virus scan on most of them, and the fact that there was a lot of unaccounted for memory (memory that was in use but not accounted for by running processes or kernel allocations) - naturally we assumed that they were severely infested with malware.

As irony would have it, the cause was actually just the opposite. On Sunday I finally got fed up with the situation, and decided to try a drastic experiment inspired with some experience in the past: I uninstalled the AVG Free antivirus that was on most of the computers. This experiment paid off; it turns out that AVG was in fact using a full 130 megs of memory. Without it, Windows was using about 80 megs of memory at boot, which is very much like what we remembered back from the day, when virus scanners took 30-40 megs, which would leave about 110 of the 256 megs available for running applications comfortably.

So... now what? Well, another 256 megs memory would put an end to the problem. But in the mean time, I had a stop-gap measure: get a smaller AV. Out of my previous tests on the best of the free AVs, the best current-generation AV in this regard was Avira AntiVir Personal, weighing in at about 95 megs. So, I switched all of the computers over to that. This reduced the amount of memory in use at boot to about 180 megs, leaving about 40 megs available for comfortably running applications. While that isn't a huge amount, I'm hoping that in a case this severe it will substantially improve performance until more memory can be acquired cheaply.

On that topic, I actually ordered a batch of used and very cheap 256 meg sticks off eBay, and I'm hoping to be able to test them out (which will take a couple days to thoroughly test this quantity of sticks) and get them installed this weekend or next, bringing the computers up to 512 megs; assuming, of course, that these computers (most of them Dells) aren't of the extremely finicky variety that reject all but very closely-matched memory. At 512 megs, it becomes reasonable to start looking at upgrading the computers to XP (pretty sure it wouldn't be a good idea to try Vista on those computers) and Firefox, which would go a long way to improving security (and, of course, at that point it would be worth making them not run as admin).

On one last note, one thing that continues to stump both of us is how on one computer the fonts in IE are enormous. On typical web pages lines of text are often 1-1.5 inches tall, making it extremely difficult to use the web. We both independently looked at both font settings and accessibility features in both IE and Windows, but none of those proved to be the cause. Setting fonts to smallest in IE made text more reasonable, but on some pages the text was actually "smallest", making it impossibly small to read; thus this was not a sufficient solution to the problem.

What the

2010-05-04T12:25:00.001-07:00

This one was a bit too long to post on Twitter. A quote from a link I tweeted:

In addition, the appeals court took aim at several filtering schemes. Blocking all files of a certain type (such as RAR files) was deemed inappropriate, since a file type has no bearing on the legality of an upload. Scanning by IP address was also tossed, because numerous people can use a single IP address. File name filtering tells you nothing about the contents of a file, so that was tossed. Even content scanning was problematic, as the court noted that this would just lead to encrypted files. Besides, even if you could know that a file was copyrighted, it could still be a legal "private backup" not distributed to anyone else.

Courts making rulings based on actual technical knowledge? What's this world coming to? I note that they even listened to me (okay, probably just other people with similar technical knowledge) and realized that content scanning would be ineffective as it would just lead to ubiquitous encryption with no actual reduction in infringement.

& Twitter

2010-05-03T15:40:00.000-07:00

Okay, I replaced the Twitter gadget from Blogger with the official Twitter one. It doesn't really visually match the blog, but all the ones that were available on Blogger had the same problem with links. This one doesn't.

Let me know if somebody knows one that matches visually without this problem.

& Bugs

2010-05-03T15:13:00.000-07:00

Yikes. Somebody just made me aware that if you follow one of the links posted in my tweets on the sidebar, it opens the link in that little tweet frame. That's very buggy. I'll have to see if I can get Blogger (the one that created the Twitter thing) to fix that.

& Domain-Specific Computing

2010-04-30T15:30:00.000-07:00

So, I went to the public lecture at UCI today (the one I posted an event for on my Facebook page). These public lectures are by various guest speakers on a wide range of topics; each one is usually something of an overview of a particular field, often ones which the average computer science student has minimal or no exposure to in their classes. As with last time, there were free brownies and coffee/tea.

Note that this post is all from memory. I didn't take notes or anything, so there are likely to be omissions and vagueness compared to the actual lecture.

The topic this time was domain-specific computing. Essentially this refers to the use of some manner of special-purpose hardware to offload work from a general-purpose CPU, either eliminating the CPU entirely or allowing the use of a smaller, cheaper, and more efficient CPU. The ultimate purpose of this is to reduce overall cost and power consumption while increasing overall performance for a given task.

If this doesn't sound revolutionary, it's because it's not. Modular electronics have been around for as long as electronics in total. If you want a real-world example of something built this way, you can look at just about anything at all. Computers consist of many components (e.g. motherboard, video card), each composed of many further components (GPU, southbridge, northbridge, etc.), usually microchips.

The problem then is that it's hard to manufacture these chips. It's expensive, requires skill in engineering, and is largely done manually. Skilled electrical engineers must manually design a circuit, then a huge fabrication plant uses big and very expensive machines to manufacture the circuit, which is then available for use in various devices. Because of the expense and manufacturing requirements, most companies are not able to produce custom chips in this way.

As a result, very common specialized circuits are produced and sold off-the-shelf in large quantities, while less general circuits instead use code running on a general-purpose CPU. After chip design and fabrication, another electric engineer must then analyze everything a particular device must do, determine where it would be beneficial to use specialized off-the-shelf components (which may either be used directly or require some manner of mapping to make the data fit the exact component), then determine which CPU to use for everything else, and have the programmers write the code for it.

Done correctly, the resulting device is faster, cheaper to manufacture, and more efficient than simply using a fast CPU to do everything. One of the papers he cited examined different algorithms implemented on a general-purpose CPU, a general-purpose GPU, and a custom FPGA (chips that can be programmed without massive fabrication plants, but are less efficient than standard fabricated chips). For one algorithm (seemingly a highly parallel one), the GPU performed 93x as well as the CPU, and the FPGA 11x. While the GPU was 8x as fast as the FPGA in absolute terms (though presumably you could increase the size of the FPGA 8 times, to match the GPU's total performance), when you compare performance:power consumption, the GPU was 60x that of the CPU, and the FPGA was about 220x: about 3.5x the performance of the GPU (and I'd wager the FPGA cost less than either of them). In other algorithms, the difference was tens of thousands of times.

But it's still a whole lot of work. Consequently, this tends to be done for mass-produced electronic devices, while more specialized things are simply executed on a common computer, as it's cheaper to code a program than engineer an electrical device.

This guy (the one who gave the lecture) is working to develop analysis and automation tools to reduce the cost and difficulty of custom hardware development, to significantly increase the range of things that are viable to produce this way. Ideally, you'd be able to write a specification or algorithm (e.g. a C++ program that describes an entire device's function), then automation would analyze the system, performing these steps (essentially the same ones I summarized above):

Break it down into major functional units
Determine which units can use off-the-shelf components and what the optimal component is
Locate algorithms that would substantially benefit from the production of new components and then design those components for manufacturing, either using FPGAs, circuit boards, or as actual fabricated chips
Choose the optimal CPU and algorithm for the tasks remaining (that aren't worth implementing in hardware) and write the code. Remember that different tasks run better or worse on different CPU architectures, so this step must find the best CPU for the given algorithm or rewrite the algorithm in a way that runs better on a more preferable (e.g. cheaper) CPU. For example, CPUs that lack branch prediction are cheaper and more energy-efficient, but perform poorly on algorithms that use a great deal of branching; however, depending on the task to be performed, an alternate algorithm might be able to perform the task with less branching.
Design an optimal bus architecture for all the different electronic to communicate

Of course, it's very likely that this ideal is fundamentally impossible - at least until artificial intelligence is able to perform as well as a skilled electrical engineer. However, he hopes to create tools that drastically reduce the amount of human time and cost needed for this process, and the talk was about recent research toward that goal. A few of the automation problems under research by different groups:

Identification of identical algorithm matches to existing circuits as well as partial matches that can work with some amount of data conversion
Profiling of different matching circuits to determine which performs optimally on a given problem
Determination of which algorithms would perform substantially better if implemented in custom hardware
Conversion of procedures (e.g. C++ programs) to electronic schematics for manufacturing
Profiling of different CPU architectures (e.g. x86 and ARM), models (e.g. i5 and i7), and variants (e.g. cache size, with or without optional subunits, etc.), to determine which is optimal for a given device, based on performance and cost
Profiling of different bus architectures (e.g. mesh and crossbar) and configurations (e.g. number and size of channels) to determine what is optimal for a device
Modularization for energy efficiency, to allow entire circuits to be shut off when they aren't in use (but others are)

I don't remember too much more detail than what I've already said. One last point is that this guy seemed to be a big fan of the multiband radio-frequency interconnect (RF-I) bus for the purpose of inter-component communication. This works essentially the same as the radio or broadcast TV, where bandwidth is split into separate channels, each with a different range of modulation frequencies. As this allows bandwidth to be arbitrarily allocated between many bus channels (and may even be configured in real time), this is very amenable to communication and power optimization.

Actually, it looks like the slides from the lecture are available online for you to look at, beyond what I've already written about it.

& MPQDraft and StarCraft 2

2010-04-16T18:31:00.000-07:00

In the course of randomly wasting time today, I decided to go look at how MPQDraft is doing in terms of popularity, these days. I do that every so often, but it had been a few months since I last looked.

To my surprise, I noted a substantial spike in downloads: 50% more binary downloads and 100% more source downloads, beginning in February. It took me a second to realize the likely cause: SC2 going into beta mid-February. It's not clear to me whether people expect MPQDraft to work with SC2, or whether SC2 has inspired a more general revival in modding.

In any case - MPQDraft does not work with the SC2 beta. There are two reasons for this.

Part of why MPQDraft is so elegant is that it works in a game- and version-independent manner. This is possible because MPQDraft intercepts function calls between the games and the Storm DLL, the latter which contains the functions to access MPQs. This only works if Storm is dynamically linked to the game, in its own DLL. The SC2 beta statically links to Storm; the MPQ functions, as well as others, are incorporated directly into the game executable.

This means the current simple, elegant MPQDraft method will not work, period. The only way to deal with this problem, and to make MPQDraft work when the game statically links to Storm, is to directly locate the function addresses in the game, and include those addresses themselves in the MPQDraft DLL.

The problem with this is that it's game- and version-dependent. Every time a new patch comes out you'll have to wait until I or somebody else updates the function addresses before you can use MPQDraft on the new version. And this obviously requires somebody taking the time to manually locate the functions in every new version, from scratch.

So, that's in the "pain in the ass" class of problems. It also remains to be seen whether Blizzard intends to ship SC2 linked in this way, or if it will dynamically link to Storm in the release version.

The bigger problem is the fact that SC2 is online most of the time, including when you're playing single player (unless you specifically tell it to run in offline mode). Depending on how aggressively Blizzard performs its anti-cheating scans (which they've been doing since SC1), it's plausible that MPQDraft could be detected as a cheat, in which case you'd probably get your account banned.

That's the current state of MPQDraft and SC2.

& Twitter

2010-04-11T15:40:00.000-07:00

On a tangentially-related note, I've also joined Twitter. This one I have a very specific purpose for: link spam (the stuff I formerly sent to friends on IM services and pasted into chat room). A place where I can simply link to interesting, funny, or otherwise linkable stuff I find online, without giving any commentary, and I can post stuff too insignificant or off-topic to clutter this blog with (although I may occasionally post short random thoughts, as well).

Those of you who think this blog has had entirely too little computer/programming stuff on it lately should check out my Twitter feed. While these days most of the stuff I think long and hard about (and blog about) is linguistics, the majority of the stuff I read online remains about computers, video games, and programming. So, expect the majority of my tweets to be on those topics, like this blog was, back before I became interested in linguistics.

There are several ways you can access my tweets. If you're on Twitter, you can simply follow me. If you're not, you can either see the mini-Twitter feed now on the blog sidebar, read the Twitter tab of my FaceBook page, or subscribe to the RSS version of my Twitter feed.

& Facebook

2010-04-11T13:32:00.000-07:00

So, I joined Facebook.

Not much to say about it. It was purely for practical reasons (because an organization I'm with apparently now uses Facebook to communicate with their members with regard to things like meeting dates), so I'm not planning on doing too much with it. I'll take a look at the features and we'll see. If I can find a use for some part of it (that I actually care to use) I might use it for that; if not I'll just use it as a friend hub and one more way to find me on the internet.

& Spring Anime Thoughts

2010-04-03T12:49:00.000-07:00

Sooooo, exactly how much of that last post was real, and how much was April Fools? About half of it. RaptorIIC did indeed talk to me about the idea of making an anime blog, and the idea has come up again (and more seriously) with Random Curiosity closing. It's not true that we've actually (yet) decided to go for it, and the ecchi/hentai theme is definitely not true, either. And, ironically, the day after I wrote that post, RC announced that it might not be closing after all.

So, moving back into the real world, in this post I'll discuss some of the new series I might actually watch, this season. Of course this is all very tentative, as not even one episode of most of these have aired yet. What's more, many of them really fall into a "I'll take a look at it and see how it is" category, which isn't particularly informative. Again, the series summaries and pictures are coming from RC and THAT (although in this post they'll be quoted, so you can differentiate the summary from my own comments).

Kaichou wa Maid-sama! | 会長はメイド様！
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi
After only reading a glimpse of the premise and taking a look at the art style, I was already convinced that “The Student Council President is a Maid!” was my kind of show. Reading a bit of the shoujo manga only reaffirmed that thought, as it has everything I’d want in a romantic comedy. The story focuses on a girl who’s enrolled in an all-boys school that has recently turned co-ed, and worked her ass off to become the student council president so that she can change the bad habits in the still predominantly male school. She develops a tough exterior as a result and doesn’t particularly like men because of how her father walked out on her and her family, but works a part-time job at a maid cafe to make ends meet. The most popular guy in school stumbles onto her secret one day and she thinks she’s set up for a huge embarrassment, but he chooses to keep it a secret because he’s unknowingly infatuated with her.

I'm not so sure about that picture, but the description sounds like it could be entertaining, and slice-of-life comedies (optionally with romance) are my bread and butter in anime, after all. The first episode aired last night (covered by both RC and THAT), and one of the (very) fast but good subbing groups already had it out, so I got a chance to see it. So far it looks pretty good, although you can't always count on the first episode of something being representative of a series, as the first episode usually forms the background of the main story.

The premise of the series is very much like the "so moe I am gonna die" [what it actually got tagged on AniDB at one point] Nogizaka Haruka's Secret. So far this one doesn't seem as horrific as that series; perhaps this is due to this being a girls' series and that one being an ecchi guys' series, though shoujo series can (potentially) be horrific in their own way. This hasn't been the case in the first episode, but the first episode is pre-romance, which is where things could go downhill.

So, I'll definitely watch some more and see how it goes.

Angel Beats! | エンジェルビーツ!
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi
One of the series I’m really looking forward to and can safely recommend to all audiences is Angel Beats. For some, it might be enough if I just say, “Key and P.A. Works.” For everyone else, this means the visual novel company that brought us AIR, CLANNAD, and Kanon, and the studio that produced true tears and CANAAN. Maeda Jun from Key is writing the script and screenplay, depicting an afterworld where one girl forms a war front, the Shinda Sekai Sensen (SSS), in defiance to god for giving her an unreasonable and short life. In this supernatural afterlife setting, we follow male protagonist Otonashi, who has no memories of when he was alive and gets dragged into the SSS’s struggles. Guns and superpowers are involved, but so is a seemingly normal school life at the same time.

Key is a very well known maker of "dating sim" games. As mentioned in the summary, to date three of their games have been adapted into anime, and I've seen them all. The supernatural and fighting aspects are certainly different than any of previous ones, though it sounds as though it still has the school slice-of-life parts they're known for, as well. The three series so far have been at least enjoyable, so I'll probably end up watching this, also. It will be interesting to see how they do something less traditional dating sim.

RC has covered episode 1. It's also been subbed by a group, though I haven't seen it, yet.

Romance of the Three Kingdoms | 最強武将伝・三国演義
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi
And here it is, the fourth series this season with some basis on Romance of the Three Kingdoms, except this one’s meant to be the real deal, or at least Chinese studio Beijing Glorious Animation’s interpretation of it. It’s actually a joint production with Japan’s Takara Tomy and Future Planet (the first of its kind) in regards to both planning and animation production. So if you don’t care for the pretty girls seen in Ikkitousen and Koihime Musou nor Gundams and wanted a faithful version with old men, then here’s the perfect alternative. This 52-episode series was aired in China by CCTV and completed its run back in 2008, meaning this is a rebroadcasting for the Japanese market. It took four years to complete and cost 650 million yen (~7m USD).

Well, that isn't the most informative summary in the world. For more information, see the Wikipedia entry on the original Romance of the Three Kingdoms.

Basically, it's a pretty famous Chinese story (at least in that part of the world). For that reason I might check it out, although I must say that 52 episodes is a really large number for a series that may or may not be any good. One thing that could be interesting is that, as the series was produced by a Chinese company and originally aired in China, the series might be in Chinese, with Japanese subtitles.

WORKING!! | ワーキング!!
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi
If you’re looking for a cute slice-of-life comedy with an all-star cast, then look no further than WORKING. It’s an easy-going series that centers on high school student Takanashi Souta, who gets recruited by his short and absolutely adorable senior, Taneshima Popura, to work at a Hokkaido family restaurant named Wagnaria (hence the official site URL). As a normal and diligent 16 year old, Souta soon learns that all his coworkers are a bit unusual. This includes a manager who doesn’t care to work properly, a floor chief who carries a katana with her, and a server with androphobia. However, as a self-proclaimed lover of all things small and helpless (i.e. “minicon”), Souta sticks with it and there doesn’t ever seem to be a boring day at his job. The first episode of this had a special early broadcast last month, and I found it a perfect fit to fill that quirky yet clean humor slot for the season.

That's about as slice-of-life comedy as you can get. This one actually had an early airing of the first episode a few weeks ago, and it wasn't bad. So, I'm planning on watching it. Oddly, neither RC nor THAT did a summary of the first episode to link you to, despite it being out for a couple weeks.

Arakawa Under the Bridge | 荒川アンダーザブリッジ
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi
This is an adaptation of Nakamura Hikaru’s gag/romantic comedy manga about a young man named Ichinomiya Kou who sits on top of the business world, and whose family motto is to never be in debt to anyone for anything. He has that so ingrained in his mind since birth that the mere thought of having debts gives him an asthmatic panic attack. One day by Arakawa Bridge, he’s saved by a homeless girl named Nino living below, leaving him with the biggest debt ever. He’s completely unable to cope with the thought of that and tries to repay Nino by buying her a house, but she’s a bit odd and asks him to love her instead. Thus begins Kou’s life under the bridge with her, where he meets a bunch of very strange individuals, including the resident Kappa village chief. From the manga, I found the character interactions reminiscent of Bakemonogatari, mainly because Kou doesn’t know how to deal with the calm, composed, and most of all weird Nino.

Another one for the "definitely maybe" pile. On the one hand the art and premise just screams "chick flick" (it is a girls' series, after all), though the premise also seems a bit intriguing. Bakemonogatari was pretty good, so if it's like Bakemonogatari, it could be good; we'll have to see how similar they really are.

RAINBOW Nisha Rokubou no Shichinin | RAINBOW 二舎六房の七人
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi
If you’re looking for a show that’s very different from the usual stuff, then consider this adaptation of Abe George (Jouji) and Kakizaki Masumi’s award-winning manga. Taking place in 1955 after the end of World War II, it depicts the hardships that six juvenile delinquents go through after getting thrown into a corrections facility/prison, often graphically so. From everything to getting sexually abused by the male doctor and having to deal with the tyranny of the wardens, it’s meant to be a realistic view on poverty-stricken Japan following the war. Upon arrival to the prison, the six boys are thrown into Block 2 Cell 6 where they meet “Anchan”, their senior inmate who shows them some tough love on how to survive. The story follows the lives of these seven, both in prison and afterward. Abe George described this as a “story about friendship and courage”, which I could get a sense of from the first few chapters of the manga. Each of the boys was sentenced for acts of assault and theft, but the circumstances they committed their crimes under don’t necessarily make them bad kids, and you can get a feel for that from the bonds they make.

Another maybe series. From that description, it sounds like it could be interesting, if it doesn't turn out to be too depressing. I tend to dislike series that are dark and depressing, so we'll see how it turns out.

K-ON!! | けいおん!!
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi

It was only at the end of last year that K-ON season two was announced, but three months later we already have more of our favorite light music club. Now with one more exclamation mark in the title! The extra DVD/BD live house episode helped tide things over a bit, but it’s not quite the same as a full season where we’re bound to hear a bunch of new songs. For those unfamiliar with this series, it’s Kyoto Animation’s adaptation of a lighthearted 4-koma manga that follows a group of girls who revive their high school’s music club by forming a band called “After School Tea Time”. It’s published in a seinen manga magazine and features quirky humor and a very cute cast of female characters. In short, it’s moe overload. When the original season aired last spring, the cast of seiyuus were all relatively low-profile, but that all changed with this series. The opening and ending theme songs they sang debuted at #4 and #2 on the Oricon music charts respectively, and they’ve all been in numerous series now, especially lead actress Toyosaki Aki. There are 28 broadcast stations lined up to air this highly anticipated sequel, which absolutely dwarfs every other series by a long shot. There’s no doubt in my mind that I’ll be watching this and it’s a safe series to recommend to almost anyone. Go watch the first season now if you haven’t!

...and the infamous moe blob returns. To summarize it in a sentence, it's a slice-of-life school comedy about excessively moe girls doing excessively moe things, especially writing/performing excessively moe songs in their amateur band (the premise of the series). It's "the definition of moe" [what it got tagged on AniDB]: if you love moe, you'll probably love it; if you hate moe, you'll probably hate it.

I watched the first season of this, a couple seasons ago (I mentioned that it had a good ending song). It was fairly enjoyable, although it really had entirely too much moe; though obviously the guy who wrote the summary disagrees with that assessment. In either case, it's decently amusing, even if it can get on your nerves.

Saraiya Goyou | さらい屋五葉
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi
The noitaminA time slot has expanded from half an hour to a full hour this season, and taking the bottom slot is an adaptation of Ristorante Paradiso creator Ono Natsume’s “House of Five Leaves”. It takes place during the Edo period and revolves around a timid rounin named Akitsu Masanosuke. By chance, he runs into a charismatic individual that wants to hire him as his bodyguard but later finds out that he’s the leader of a gang known as the Five Leaves. Realizing what he’s up against, Masanosuke gets wrapped up in the gang and its very unique individuals and learns there’s more to them than it initially seems. Don’t be swayed by the character designs here if they seem a bit odd to you, as this is just Natsume’s unique style. Personally, I find they’re a refreshing change from the more generic ones you often see.

This one's a big question mark. It sounds like it could potentially be interesting, but that's a pretty big maybe. I watched the first couple episodes of Ristorante Paradiso and couldn't stand it, between the art and the writing. So, we'll find out in a week or two how this one is.

Yojou-han Shinwa Taikei | 四畳半神話大系
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi
Taking the top slot in noitaminA’s newly expanded time slot is a novel adaptation about a nameless third-year Kyoto University student (only referred to as “I”) and his life with the “Tennis Circle Cupid” club that he joined in his first year. The story is broken up into four chapters and will be aired as an 11 episode series here. Not having read the novel, I’m not too sure what to expect, but the promo videos already showcase how strangely different everything is. The title on the other hand seems to translate to “Compendium of 4½ Tatami Mythology”.

Another big question mark, and this one is even less clear on what it's going to be like. Though I have to say the art kind of gives me a bad feeling. Either way, we'll again know more in a couple weeks.

Oh, and in case anyone happens to be interested, RC has covered B Gata H Kei 1 (mentioned yesterday).

On a final note, both the Currently Watching section and the Introduction to Anime/List (which includes a list of almost all free-to-watch anime series I've seen) link on the sidebar are still live, and being updated as new series come out.

& New Endeavors

2010-04-01T18:04:00.000-07:00

A ways back, RaptorIIC, one of the modders back from the StarCraft era, came to me with an idea. He was considering starting an anime blogging site with some of his friends, and wondered if I'd be interested. The basic idea is that bloggers write summaries of episodes of certain series (the ones they're watching) each time a new episode comes out; readers then read the summaries and discuss each episode via the posts' comments. In the past I've mentioned two such sites that I follow: Random Curiosity (henceforth known as RC) and T.H.A.T. Anime Blog (although the latter is mainly for a second set of opinions on new season series, in addition to RC).

I gave it some serious consideration, and mentioned it to a number of my friends online, though I don't think I ever mentioned it on this blog. However, nothing ever became of the idea, and for quite a while nobody thought about it again.

However, now that RC is closing its doors, the idea has come up again, and more seriously than before. To make a long story short, we decided to give it a shot, and just applied to AnimeBlogger (the host of RC, and I believe at one time the host of THAT). As is typical for AnimeBlogger (as mentioned in their FAQ), it's taking a few days to get the new blog all set up.

However, despite this being inspired by the closure of RC, our blog is a bit more of a niche market. That is, our blog will specialize in ecchi and hentai series.

Coming up with a name wasn't exactly trivial. We wanted something halfway tasteful, yet still had a halfway appropriate meaning. "Q & H" was immediately rejected for being too cheesy. Ultimately we decided on Zettai Ryouiki [from WWWJDIC: "絶対領域: exposed skin between top of knee-high socks and hemline of skirt (lit: absolute territory)"].

As you might know, this is right in time for the spring anime season, which begins next week. Obviously we won't know exactly what we're going to cover until we can actually see an episode or two of the new series, but here are a couple that look like good candidates for blogging (the information and pictures are ripped from RC's and THAT's season previews from a few weeks ago; note thus that any first-person statements are not mine):

B Gata H Kei | B型H系
http://www.bgata-hkei.com/
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi

Adapted from a 4-koma manga serialized in Weekly Young Jump, B Gata H Kei (B-type H-style) targets an older audience with a story about a beautiful high school girl named Yamada, whose sex-ridden mind wants to sleep with 100 different guys. Despite her beauty, she’s actually a virgin because she’s too worried about being ridiculed by good-looking and experienced sex partners to lose it. One day, she mistakenly believes that a plain and homely guy named Kosuda Takashi intentionally saved her from falling over in a bookstore. Sensing that he’s a good yet sexually-inexperienced man like she’s been looking for, she decides to use him as her first and craziness ensues.

kiss x sis | キスシス
http://www.starchild.co.jp/special/kiss_sis/
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi

Ecchi fans rejoice, as the seinen manga turned OVA is getting its own TV series. Studio Feel is producing this retelling as well, and it will be broadcast on AT-X (and only AT-X). I don’t think I’ll ever quite understand the Japanese fantasy/fetish over incest, but kiss x sis revolves around that idea with stepsiblings unrelated by blood. This is probably the most risqué/borderline hentai series in this season’s lineup, involving a middle school boy named Suminoe Keita, whose high school twin stepsisters, Ako and Riko, are passionately in love with him and will seduce and violate him every chance they get. Keita however doesn’t want any involvement with them in that way and tries to focus on getting into the same high school, even though their parents encourage a potential relationship. The girls completely drive the explicit fan-service here, with Ako being a closet pervert and Riko calm and assertive, but there is some plot involving their childhoods to tie things together in a meaningful way. This still doesn’t change the fact that sexual scenarios are foremost, so unsuspecting viewers beware.

Ikkitousen XTREME XECUTOR | 一騎当千 XTREME XECUTOR
http://www.ikkitousen.com/
Information Links: ANN Encyclopedia, AnimeNfo, AniDB, MyAnimeList, syoboi

I gather Ikkitousen doesn’t need too much introduction, seeing as XTREME XECUTOR marks the fourth season of the series, but the story here is loosely based on the classic Chinese novel Romance of the Three Kingdoms. That’s what they advertise it as anyway, but anyone who’s actually watched the show will probably tell you it’s an overflowing fan-service affair with busty girls from rival schools fighting one another and getting their clothes torn off like there’s no tomorrow.

On the downside, being an anime blogger will require a lot less laziness from me, as I'll have to blog each episode as it comes out (once a week, for however many series). And everybody knows I hate obligations.

I'll let you know when the blog is online.

Oh, and entirely coincidentally, Anime News Network currently has an ad theme that seems very relevant to this announcement. The relevant slice of the theme:

& StarCraft 2

2010-03-28T14:36:00.000-07:00

I really should have posted this weeks ago, but IskatuMesk (user mancatcher, on YouTube) has being doing a series of YouTube posts of SC2 games with commentary. Many of the replays are in 1080 high-definition, although I only watch the 480 resolution versions, as that's all my 1.5 Mbps DSL can support in real-time, and it's okay, clarity-wise. I've been watching just about everything he's posted since he started covering it.

The vast majority of them are of high or mid/high-level players. A lot of them are games (usually free-for-alls) he plays in, himself. He's in the platinum league (currently the highest, with gold, silver, bronze, and copper below), which puts him in the mid/high skill category. Others, however, are commentaries on replays of really famous SC1 pro players, frequently obtained from Team Liquid's forum.

On one or two occasions you see him getting in-game messages from me (some of which make absolutely no sense, like when I was testing out what the mature language filter blocks - e.g. "XonX" and "came" - which he had disabled). One replay, however, is a 2on2 I actually played. Now, I'm in the silver league, so this is not exactly a replay displaying master strategy (and I get my ass handed to me by Mesk's commentary of the match, which is kind of amusing in its own way). It does, however, have an absolutely hilarious ending, as indicated by the stuff people have said about it (e.g. "oh god im dying over here", "Holy shit. I teared up at the end there", "dear god that was amazing", "Most hilarious ending evar"). Amusingly, this replay has proven his most popular, and has almost 3x as many views as almost all of the other replays of the same age; I wonder if it got posted on a forum with a couple thousand users, somewhere.

Part 1
Part 2

Oh, and since the ending is kind of ambiguous: my team won.

Q's Squishy Thing of the Day

2010-03-22T18:09:00.000-07:00

One of the manga series I've been waiting forever for an English translation of (to buy, that is; fan-translated versions have been around online for years) is Elfen Lied, which I mentioned being fond of in the past. Well, there's still not official English translation, but I just learned something very interesting: there's an official Spanish version (also German and Taiwanese Chinese, for speakers of those languages). So I can own the series I've wanted for a long time, while practicing my Spanish.

I mentioned a ways back that I was reading the Spanish version of the Trique grammar book (as there wasn't an equivalent English version), and I was surprised how well I could read the Spanish, without even looking things up. However, a part of the reason this went so smoothly was that most of the unknown words in that were linguistic jargon that I was able to figure out from context very quickly.

Actually, my very first exposure to Trique, prior to that, also involved Spanish. It all began with a Spanish/Trique bilingual Bible I got from my grandpa. I started by comparing the text in Spanish and Trique to attempt to figure out the grammar by example. This was somewhat more difficult than the grammar book. It had a much broader array of words used, so it was significantly harder to figure out unknown words from context. Still, I made a respectable amount of progress, given the method.

If I'm lucky, reading Elfen Lied would be closer to the former, as the illustrations give some context. But even if I infrequently need to look things up it wouldn't be too bad. And it would very likely improve my ability to read/write Spanish in general by a noteworthy amount.

So, I'll probably buy that after money is no longer so tight.

Q's Squishy Thing of the Day

2010-03-21T11:22:00.001-07:00

Just saw this today. Perhaps nobody else will find it interesting, but I do.

Essential WoW terminology in other languages

Q's Squishy Thing of the Day

2010-02-25T12:53:00.000-08:00

Meet ShadyURL. It encodes URLs in things that look like spam, porn, malware, and cults/racism. Some of the things I've linked to various people in the last day:

http://5z8.info/PIN-phisher_a1x6x_nakedgrandmas.jpg
http://5z8.info/double-your-wang_z2f4t_nazi
http://5z8.info/worm.exe_i8k3z_stalin-will-rise-again
http://5z8.info/killallimmigrants_x2l9n_protocols-of-the-elders-of-zion.doc (best URL so far)
http://5z8.info/OPI423098BVMPEMBUDSGND423098889708807909788079_k3j7r_dogporn

And, just for fun, here's the Copyright Alliance blog: http://5z8.info/pirate-anything_w2x9e_racist-raps

And this blog: http://5z8.info/whitepower_o3q2x_inject_worm, which is awesome, because I'm actually 3/4 German

And yes, I have been made aware that I'm late to the party on this one.

& Content Filtering

2010-02-24T16:33:00.000-08:00

Following a brief scuffle with Patrick Ross in the comments of the Copyright Alliance blog, I thought the topic I briefly discussed deserved elaboration: content filtering. That is, the analysis and identification of illicit content packets as they pass through a router, based on hashing (not so effective) or fingerprinting (more effective), usually followed by dropping the packet.

I'll discuss the full range of content filtering, though one thing at a time.

First of all, the specific type I referred to previously: filtering at the internet service provider level. Imagine an ISP that is being legally pressured to do something about file-sharing by copyright industry representatives, a situation hundreds of ISPs around the world find themselves in at this very moment.

Now, Mr. Sales Rep, from another company that makes deep packet inspection hardware, offers to sell a product to Mr. Business Suit from the ISP, that will solve the file-sharing problem, as many sales reps are currently doing. This company's tests show that the product is 95% effective at identifying and blocking traffic containing illicit copyrighted material, and has a low rate of false-positives. Naturally, Mr. Business Suit at the ISP looks at this product, and sees an amazing solution to all of their problems. Mr. Engineer at the same ISP looks at the product and sees a million-dollar paperweight, and tells Mr. Sales Rep to get out of his office. Nevertheless, convinced by Mr. Sales Rep, Mr. Business Suit purchases the product, and has Mr. Engineer install it.

Now the product has been installed, and everybody watches eagerly, as Mr. Engineer turns the new product on. Immediately the product begins logging transfers of copyrighted content by the thousands, and successfully blocks them. Yet Mr. Engineer looks at his network statistics and sees that not only is the product having 0 effect on the amount of internet traffic, there is still just as much illicit content being successfully uploaded by users of the ISP.

What could possibly have gone wrong? And why were the appraisals of the product so drastically different between Mr. Business Suit and Mr. Engineer, to begin with? Is the product defective? Did Mr. Sales Rep lie?

Well, not exactly.

What happened is that the ISP's users adapted effortlessly to the new piece of filtering hardware. While it's certainly viable, if implemented competently, to detect and block things like copyrighted content, this is only possible if you have access to the data being transmitted. The universal Achilles heel of such identification algorithms is encryption.

Modern file-sharing software supports end-to-end encryption - the same kind used to secure credit card transactions online: the uploader encrypts the data, the downloader decrypts it, and nothing in the middle can access the data in between the two, because nothing else has the encryption key. This "nothing" includes that million-dollar product our ISP just bought.

Now, this encryption is not a technology that needs to be developed, nor does it need to be downloaded and installed by the user. It's already there. If a user is able to share files through a P2P application, the encryption code is already in that P2P application; it needs only to be enabled by a user clicking a check box. And, of course, you can be certain that it will be turned on by default in future versions of said software if content filtering by ISPs becomes common.

In other words, each of those "blocked" uploads the product registers is merely the first of two attempts. A blocked upload is merely an upload that will succeed seconds later, after the user clicks the box to enable encryption (though if content filtering is widely deployed, users won't even need to do that). Thus, to make a long story short, while you have successfully prevented file-sharers from uploading unencrypted illicit content, you haven't actually prevented a single copyright infringement.

This is a theoretical problem, not an implementation issue. As such, there is no basis to hope that this is a limitation that will ever be overcome in the future.

But look on the bright side: Mr. Sales Rep got a nice commission off that million bucks the ISP paid his company, and as he technically never lied, the ISP has no legal recourse to argue fraudulent advertising.

However, the fact that ISP-level filtering is a technological dead-end should not be taken to mean that all filtering technology is useless. As stated, filtering technology can be effective, given that it has access to the data. Of course, the hackers of the world will continually work to find new ways to evade such filtering algorithms, but it should still be possible to successfully filter enough to justify the cost of the filtering hardware/software.

One example where this works to a satisfactory degree, both in theory and in practice, is YouTube. Because YouTube actually processes and decodes the content uploaded to it, it's impossible for it to not have access to the data - it couldn't function otherwise. As such, it always has access to the full, unencrypted content uploaded, at which point filtering of that content is possible, and in fact is already being performed.

Dumb file storage sites - sites like RapidShare - which store data without any regard to what type of data it is, fall somewhere in the middle. As they do not require access to the data itself, encryption is entirely possible, and would indeed be capable of evading any filtering of uploaded content done on the part of the site. However, use of this type of encryption would be much more of an inconvenience than is the case with encryption in P2P programs; in this case, encryption must be done manually, by the user, through a completely separate program (almost anything that can make ZIP files can encrypt them, for instance), and the encryption key must be distributed through other channels, such as forums that link to the encrypted file. As such, while filtering at the level of such sites will certainly not prevent such encrypted transmission of content (nor probably even a majority of total transmission), it's possible that filtering systems might reduce sharing of illicit content by some sufficiently valuable fraction by means of sheer annoyance.

Die! smash

2010-02-10T22:53:00.000-08:00

I have squashed the mystery.

I did some chatting with Merlin (never mind who that is, just that he knows some about the electrical engineering of computers, as well as programming). He gave me a couple of theoretical possibilities what the problem could be, some of which could be tested, others were simply components on the motherboard that I had no way to individually test.

One thing was the power supply. According to him, it's possible that when data is being sent from the memory to the controller (in 8 blocks of 64 bits), if the power supply is flaky the voltage could droop over time, which could hypothetically explain why the bit only fails only once in each cache line even if the problem is in one of those 64 data lines. However, this was easily disproved, as I do have other power supplies.

More importantly, while talking to him I thought of my grandma's computer (my computer prior to 2001), which had the same type of memory. While this computer is too old to support 512 meg DIMMs (this was why I couldn't just use it to verify the DIMMs worked and be done with it), it did have some smaller DIMMs in it (256 meg). See where this is going?

Now I had more than two DIMMs, and with them I was able to demonstrate that the same bit failure occurred with any combination of two DIMMs (although the frequency of the error did vary some depending on the pair used). This proved conclusively that the DIMMs themselves were not responsible, and the problem had to reside in the common element - the motherboard or the CPU. This appears to be a problem that only shows up when both DIMM slots were full.

Now, it's still possible that it could be a software (BIOS) problem that could be fixed by updating the BIOS, but I don't care to try that, for the reason I mentioned previously.

...Now What?

2010-02-10T16:32:00.000-08:00

A few weeks ago my parents' desktop died. This was my old Athlon XP computer I had before I bought the one I have now (about a year and a half ago). A bit of trivial diagnostics demonstrated that either the CPU or motherboard had died, and I didn't have the parts necessary to determine which. So, my dad went looking on eBay for a replacement motherboard and CPU to go with the existing memory, as they didn't really have the money to buy a new computer right now (actually, I was the one who did most of the looking at the specs, to make sure it would work).

A few days ago, the motherboard+CPU arrived, and I quickly set to determining whether or not they worked, as the amount of time to return it was limited. As my past experiences have made me a little paranoid in that respect, naturally the first thing I did was run MemTest 86 on it.

While it seemed to work for the most part, about once every pass (took a couple hours) on test #7, an error would show up. After leaving it running overnight, some patterns emerged. The error was always the 0x02000000 bit getting set when it should be cleared, and it usually occurred when the value written to the memory was 0xFDxxxxxx (less commonly, 0xF9xxxxxx). The base address of the error seemed to always be at 0x3C, 0x7C, 0xBC, or 0xFC. The errors also appeared to cluster in the low 512 megs of the memory space.

In short, it appeared to be 1 bit every 64 bytes, where the containing byte changes from 11111x01 to 11111x11.

Separately, neither of the two 512-meg DIMMs shows this problem, regardless of which of the two sockets the DIMM is in (as tested by running MemTest 86 overnight, which would be expected to produce about a dozen errors). However, when put in in one order, this error occurs. Peculiarly, when put in the opposite order, MemTest begins spewing out memory errors before soon crashing (presumably due to memory errors in the locations the program is at).

So, where is the problem? Well, I wish I knew the answer to that.

The fact that both DIMMs worked correctly when alone suggests that the DIMMs are good (these are the same ones that were used in the computer that failed, and to my knowledge there was nothing wrong with them then). The fact that each DIMM works in both sockets suggests that it's not a bad socket. The fact that it's every 64 bytes tells me that it's not one of the data lines on the DIMMs or on the motherboard, as the data width is 64 bits (64 pins). The fact that the error period isn't into the kilobytes indicates that it's not a CPU cache failure, as I saw in the past.

64 bytes is the size of the cache line for the CPU, which seems to hint that it's somewhere after where the 64-bit memory reads are assembled into whole cache lines; unfortunately, I don't know where exactly this occurs, to narrow down the possibilities. Yet the fact that it only seems to occur in the lowest 512 megs of the memory space is very suspicious, and seems to suggest something with one of the DIMMs, sockets, or data paths on the motherboard, which appear to already be ruled out from earlier tests.

So, I'm really at a loss as to what to make of this and what to do next, and I've got three days left to do it. I can't test the memory on another computer, because I don't have another computer to test it on. The BIOS could use updating, which could theoretically fix the problem, but I've been reluctant to do that because it's a trivial way to say "You broke it, I'm not giving you a refund!"

I suppose I need to try mixing and matching the CPUs and motherboards. I need to do that anyway, to find out exactly what broke on the old computer, but it should also tell me whether the problem is in the CPU or motherboard (though nothing more specific than that).

Let's Do Some Math!

2010-02-06T02:10:00.000-08:00

There are a couple common equations of importance for what I'm working on at the moment. Both of them involve the idea of a set of items, where each item has a probability of being chosen (and more than one may be chosen in some cases). It's trivial to go item by item, draw a random number, and see if that item is chosen, but this is obviously inefficient. I wanted equations that would allow me to stick in a single random number and it will tell me the first relative item to be chosen, with a fixed number of operations.

The first equation is based on each item in the set having an equal probability of being chosen (note that more than one may be chosen, or none may be chosen):
probability(item) = perItemProbability

The general form of this decision is (rnd <= perItemProbability), where rnd is between 0 and 1 (as is the case with all instances of rnd in this post). Trivial. The equation we want to derive, however, not quite as much.

While it's tempting to think that the probability of any of n items being chosen is (perItemProbability * n), it's not. This isn't a linear function. Rather, you have to derive it from the probability that NONE of those items will be chosen, which is exponential.

(1 - perItemProbability)^n : probability none of n items will be chosen
1 - (1 - perItemProbability)^n : probability that at least one of n items will be chosen
rnd = 1 - (1 - perItemProbability)^n : switch out probability for a random number
1 - rnd = (1 - perItemProbability)^n : arithmetic rearrangement
log(1 - rnd) = log(1 - perItemProbability) * n : take the log of both sides
log(1 - rnd) / log(1 - perItemProbability) = n : arithmetic rearrangement

This gives us what we want: the index of the first chosen item. Of course you have to watch for values that result in taking log(0). You also have to notice that the range of the result is [0, infinity]; this is correct, but if the value is greater than the upper bound of your set of items, you have to recognize that no item was chosen.

Next up is the case where the probability of each item follows a geometric series:
probability(n + 1) = probability(n) * (1/divisor)
probability(0) = p0
sum of probabilities = 1

With this series there's no misleading simple solution, so we're forced to go straight to a more complex one. We know the sum of all the probabilities is 1, but we don't know what value of p0 to use to produce that sum. We can trivially calculate this using the geometric series equation:
1 = p0 * (1 - (1/divisor)^n) / (1 - (1/divisor)) : geometric series equation
p0 = (1 - (1/divisor)) / (1 - (1/divisor)^n) : arithmetic rearrangement

Okay, that's the easy part. Now the equation itself. Here again we'll solve for n:
rnd = p0 * (1 - (1/divisor)^n) / (1 - (1/divisor)) : substitute rnd for sum of probability
rnd / p0 * (1 - (1/divisor)) = 1 - (1/divisor)^n : arithmetic rearrangement
1 - (rnd / p0) * (1 - (1/divisor)) = (1/divisor)^n : arithmetic rearrangement
log(1 - (rnd / p0) * (1 - (1/divisor))) = log(1/divisor) * n : log of both sides
n = log(1 - (rnd / p0) * (1 - (1/divisor))) / log(1/divisor) : arithmetic rearrangement

And thus the solution: a long, ugly equation to calculate something simple. Again, you have to watch for values that result in errors: divisor must be greater than 1; but that's pretty obvious: a geometric series will only sum to a finite number if (1/divisor) is less than 1. You also have to note that when rnd = 1, n = the number of items in the set, which will be out of bounds.

Isn't math fun?

& Solid State Stuff

2010-02-04T18:10:00.000-08:00

Pretty soon I'm going to be looking to upgrade some things on my computer, starting with the hard drive. In addition to getting a large disk to begin using for archived anime (as opposed to the large stack of DVDs I've burned), I was going to get a solid-state disk to put my Windows 7 that I won in a raffle a couple weeks ago on.

For anyone not familiar with them, SSDs have the benefit that they have 0 seek time (as opposed to about 9 ms for HDs), combined with linear read speeds several times that of HDs. For very large and contiguous files, which involve only linear access, an SSD could be 3 or 4x as fast as an HD. But for accessing large numbers of small, non-contiguous files, which involve many seeks, the difference is much, much larger. Thus SSDs can be anywhere from substantially faster to massively faster than HDs, depending on the type of access.

But what exactly do I do with the SSD when I get it? Prior to Wednesday, the answer was obvious: use it as my boot drive. That is, put Windows and frequently used programs on it, and use a separate HD to put large and infrequently used stuff on.

Today, however, there's another option, thanks to the announcement of this evil little thing: a disk controller which combines an HD and an SSD, using the SSD as a massive cache for the much larger HD. That is, instead of having the SSD serve as a dedicated boot drive, it's used to cache frequently used files from all over the HD (when talking about an 80 gig cache, "frequently" probably amounts to once every week or two).

One obvious advantage is that the superior performance of the SSD is applied not just to system files (e.g. Windows), but also to anything on the disk that gets used frequently. Similarly, you don't need to let part of the SSD go to waste if you don't have enough files to fill it up (I'm told using an SSD as your boot drive takes 30-40 gigs of SSD, while higher end SSDs go up to 256 gigs). Another big benefit is that you don't have to manually split files that are normally on the boot drive (e.g. Program Files and the Users documents folder) between the SSD and HD depending on whether you want them fast or slow; for example, I wouldn't want to put downloaded anime on my (dedicated) SSD, nor would I want my SSD bloated with the various bulky compiler intermediates.

Now, the big question is how exactly this is going to work. According to the manufacturer, it requires a driver for Windows in order to work. This suggests that caching may all be done in software, rather than hardware. This brings up the obvious question: in what cases the cache will be used? If the cache is only used within the current Windows boot (essentially serving as a gigantic system cache), this won't be very useful, at least for me (perhaps for a database server, with multiple terabytes of database, a 100+ gig cache would be substantially beneficial). I already have 8 gigs of RAM, about 4 of which (at a minimum) is available to be used by the system cache, which is a pretty decent cache for one session (and RAM is much faster than an SSD, anyway).

From the write-up, however, it sounds like the cache at least persists between Windows boots, which would mean it wouldn't quite be that bad. However, if the caching is all software-based via a Windows driver, this obviously means that it won't be of any benefit prior to loading that driver - that is, during boot up/shut down and going into/out of hibernate, which are things I was hoping to gain out of getting an SSD.

I guess we'll find out when the thing ships, in 3 weeks or so.

Random Fact of the Day

2010-01-31T16:07:00.001-08:00

You can't install SilverLight on a Pentium 2. It has to be something that supports SSE.

EPIC FAIL

2010-01-23T20:00:00.000-08:00

I got a letter from Wells Fargo bank with a new credit card, today. Nothing out of the ordinary in that respect, but the extent Wells Fargo failed in the process is pretty remarkable.

The first page was all the stuff you'd expect - credit card glued on, as well as account number and other info, and instructions to use it. The second page is shown below (the back is completely blank):

Looks completely innocuous and generic, right? Except for that black block in the lower right that I filled in. There is a bar-code and, in 6 point font, a number of numbers (most that I don't recognize), including the credit card number itself. If you weren't looking for it, you would most certainly never have seen it.

The number of people who have thrown that page away without ever realizing it had their credit card number on it is surely uncountable. Funny how a page about guarding against fraud sets you up perfectly for fraud by printing entirely unnecessary sensitive information on a completely generic page (that would have been cheaper to print without that information). You have to wonder if there's some malicious intent, there.

So, after the facepalm, I go online to activate the new card. After logging in and going to the activation page on Wells Fargo's (secure) web site, I'm met by this page:

Birth date? Work phone number? Really? It's been known for a long time that "security questions" are major security vulnerabilities, but this may just set a new record as to extent.

I can't say I can trust Wells Fargo after that rather brilliant display of insecurity.

What the Goat

2010-01-19T17:45:00.001-08:00

The National Weather Service has issued a tornado warning for the South Los Angeles, Long Beach and Whittier [right about here] areas as a powerful new storm moves ashore.

Tornado Warning Issued for South Los Angeles, Long Beach, and Whittier

A tornado watch. In Los Angeles county. Has that ever happened before?

Random Fact of the Day

2010-01-18T22:57:00.000-08:00

Watching CSI: Miami I learned something new: that receiving a liver transplant* can change your blood type to that of the donor. I'd never heard anything about that before, so I had to do a Google search before believing it. Apparently it's actually happened; once. It seems that stem cells in the liver managed to detach and land in the bone marrow of the recipient, and take over the marrow.

This makes me wonder. If I understand the biology involved correctly, this would only be possible if the blood type changed in a particular direction. In any other direction you'd get the same effect you'd get from getting an incompatible blood transfusion. Thus my question: might this have happened before, but been misclassified as simple organ rejection?

*In theory this is probably possible with most transplants, given that it involves stem cells being transported with the organ.

Computer Book Library

2010-01-12T12:00:00.000-08:00

This post lists some of the computer books I have on my shelf, between text books and books I bought outside of school. This list is meant to provide readers with books they might be interested in reading, and so is limited to the books most likely to be of interest to others. While I list the versions that I have, myself, the links to the books on Amazon are to the most recent edition at the time of writing about them.

This post is likely to be updated from time to time in the future.

3D Game Engine Design, 2nd ed
David Eberly, Morgan Kaufman, 2006
Covers development of a 3D game engine that includes graphics, physics, and a few lesser topics (though the focus on the book is definitely graphics). Covers both the theory behind concepts and actual implementation of a complete working engine; this latter point makes it vastly superior to more typical graphics books, which usually cover the theory but not a complete implementation.

Artificial Intelligence, 5th ed
George Lugar, Pearson Education, 2004
Computer science textbook I used in the senior-level course.

C++ Programming: Program Design Including Data Structures,
D.S. Malik, Couse Technology, 2002
First year (for me) college textbook

Code Complete
Steve McConnell, Microsoft Press, 1993
Handbook of coding best practices for minimizing bugs and improving maintainability.

Developing Windows NT Device Drivers
Edward Dekker and Joseph Newcomer, Addison Wesley, 1999
A rather dated guide to programming Windows NT (4.0) device drivers.

Developing Your Own 32-Bit Operating System
Richard Burgess, SAMS Publishing, 1995
Prior to the Linux phenomenon, this was pretty much the only book that showed you how to create a full, real, working operating system for a modern computer (at the time, anyway). Throughout the book the author codes the example MMURTL (Message-based MUltitasking Real-Time kerneL), a (some redundancy, here) 32-bit message-passing, preemptive-multitasking operating system that runs on x86 computers, in 32-bit assembly + C, and several sample programs (including the command-line interpreter and debugger) in C.

Fundamentals of Computer Graphics, 2nd ed
Peter Shirley et al., A K Peters, 2005
A fourth-year (for me) college textbook. Like most books of its kind, it teaches you the theory behind graphics (and, if you're lucky, gives you pseudocode for some concepts), but leaves you on your own to figure out how to create a working graphics engine (if you have the need to do so).

Fundamentals of Database Systems, 5th ed
Ramez Elmasri and Shamkant Navathe, Pearson Education, 2007
A fourth-year (for me) college text book on databases. Covers from the basics to the advanced, as well as SQL programming, both in theory and practice.

Game Architecture and Design
Andrew Rollings and Dave Morris, Coriolis Group, 1999
A guide to the complete development process for a commercial game. The first section covers developing a game idea and balancing gameplay, the second section covers project and team management, and the third section covers development from architectural design (the thing code is based on) to production and postmortem analysis. The vast majority of the book is at a higher level, summarizing the entire game development process and the lessons learned by the author from his experience in commercial game development, though the author does create a (simple) working game in the process (several other game ideas are discussed in various chapters, but not developed into the full games).

Game Coding Complete, 3rd ed
Mike McShaffry et a., Charles River Media, 2009
A guide to the game development process and development of game systems. While the scope of material in this book is much the same as other game programming books (e.g. Tricks of the Windows Game Programming Gurus), this book distinguishes itself on quality and scalability. All game programming books invariably contain a guide to the various APIs your game will need to use (e.g. DirectX) and a survey of game technology (e.g. 3D graphics, AI, and networking). However, most books teach you from the perspective of a hobbyist getting into game programming, teaching you easy things that work okay for small games, but lack the power and scalability to deal with a large commercial game (and omit things that aren't necessary for small games).

This book dedicates itself to filling in those gaps, addressing frequently-omitted topics such as the build process, memory management and resource caching, event management, scripting support (the engine the author creates throughout the book is actually a data-driven engine based on Lua scripting), debugging, parallel programming, etc. Of course, it also contains the mandatory survey of game-related technologies, but I haven't looked at those parts and don't expect too much, as most of them are best left to their own books (graphics, physics, networks, AI, etc.), given the overwhelming broadness of those fields.

Programming Applications for Windows, 4th ed
Jeffrey Richter, Microsoft Press, 1999
Perhaps better described by its older name, Advanced Windows, this is the gold standard in "advanced" Windows API programming - things such as multithreading, advanced memory management, DLLs (including DLL injection and function hooking), exception-handling, and advanced window messaging.

Programming Windows, 5th ed
Charles Petzold, Microsoft Press, 1998
The first book to read on Windows API programming. Covers a broad range of topics from basic windows and controls to more advanced topics such as (basic) graphics, printing, multithreading, network communication, etc.

Programming Windows with MFC, 2nd ed
Jeff Prosise, Microsoft Press, 1999
The definitive guide to the Microsoft Foundation Class library, a C++ framework that wraps the Windows API. Analogous to Programming Windows, this was the book to read if you needed to learn MFC, though as MFC is easier to program than the Windows API, this book covers topics beyond those in Programming Windows. MFC is essentially obsolete now that .NET has become so common, though I'm told some people still have to deal with it in older software at their jobs.

Tricks of the Windows Game Programming Gurus
André LaMothe, SAMS Publishing, 1999
The Game Programming Gurus has been pretty well respected throughout its life. This was the 2D Windows game incarnation of the series (also see the companion Tricks of the 3D Game Programming Gurus); it covered basic Windows programming, the various DirectX systems, and then a survey of the various fields in game programming (like those mentioned a ways back). As stated above, this (and presumably the 3D version, which I haven't seen) is more of an introduction to game programming than a reference that would be useful at a real game programming job.

Visual C# 2005 How to Program, 2nd ed
Paul Deitel, Pearson Education, 2005
Lower-division college textbook on C# programming (at my school C and C++ were first-year courses, C#/Java/etc. were second-year).

Lastly, a couple books on the list of things to buy:

Game Engine Architecture
Jason Gregory, A K Peters, 2009

Real-Time Rendering, 3rd ed
Tomas Akenine-Moller, Eric Haines, and Naty Hoffman, A K Peters, 2008

Bibliography - Programming

2010-01-10T16:00:00.000-08:00

This post is a partial directory of the various programming and reverse-engineering I've done over the last 12 years, especially those that produced some manner of result (program, specification, or processed data). This list may omit projects that are too old, too obscure, too uninteresting, or that I just don't remember off the top of my head; it also omits most projects that were done as assignments or term projects in school. With a handful of exceptions, all of these are entirely my own work. With the exception of the few most significant projects being moved to the top, the list is in alphabetical order.

This list may undergo updates in the future.

(CHK) Starcraft Map File Format [reverse-engineering]
Reverse-engineering of most of the Starcraft map file format. This was my first modding community project, and it was for this that I was invited to join Campaign Creations in 1998. This consisted of repeated edits of a map in the Starcraft map editor (StarEdit) and then observing the changes in the map file it generates. Perhaps one of the most impressive parts of this accomplishment was that the vast majority of this was done using nothing more than the DOS edit.com utility and Windows calculator; no true hex editor, no disassembler or debugger (at that time I wasn't even familiar with reverse-engineering), etc.

It looks like this spec has become difficult to come by these days. Campaign Creations appears to no longer have it (I'll have to get that fixed) and only a few modified and/or butchered copies of it found on Google, some lacking credits for who wrote it. So, here's the version I still have on my computer.

MoPaQ 2000 [programming]
This (a.k.a. MPQ2K) was the project that really put the name Quantam on the Blizzard game modding map: the first stable, full-featured MPQ editor. Prior to this there was already a full-featured MPQ editor (I think the name was MPQEdit), however the extreme instability and bugginess meant that it was widely considered worse than nothing, and rarely used.

MPQ2K was a command-line user interface for the Lelik MPQ API, a library that hijacked the Starcraft Campaign Editor (StarEdit) and called the MPQ-writing functions it contained (as Starcraft maps are packaged into MPQ archives), without ever knowing the details of the MPQ format, itself (it's worth noting that this is where I learned about breaking and entering into processes and hooking functions). At the same time as the library, Lelik released a sample editor (I believe the name was MPQ Archiver) that the MPQ2K interface design used as a starting point; it was very clumsy and minimalistic, however, and lacked the major features that would make MPQ2K popular, such as scripting. MPQ2K remained the MPQ editor for several years, until cumulative speed improvements finally allowed WinMPQ, a graphical MPQ editor, to seize the title of most popular MPQ editor.

Understanding the significance of a practical MPQ editor requires some knowledge of the context. Prior to the use of MPQs, the only option to modify Starcraft game data, apart from what could be done in the map editor alone, was StarDraft, the predecessor to MPQDraft. StarDraft allowed in-memory patching of most Starcraft data files, allowing much more than was possible with the map editor alone (e.g. modification of sound effects, graphics, gameplay data such as unit statistics, etc.). While this was a hugely important development that essentially founded the Starcraft modding community (apart from custom maps), StarDraft suffered from several severe shortcomings that drastically limited its practicality: it was version-specific (meaning that every time a Starcraft patch was released StarDraft had to be manually updated by the coder before it could work with the new version), it could not replace music and certain other files, and, perhaps most significantly, it tended to actually slow down the game, degrading gameplay noticeably.

Thus, StarDraft was the first revolution in Starcraft modding, and use of MPQ files was the second. The replacement of StarDraft with custom MPQs as the basis for community mods solved many of these problems that plagued StarDraft. Music files could now be patched (although a handful of relatively minor files remained unpatchable until the coming of MPQDraft); as well, as MPQs were used natively by Starcraft and other Blizzard games, rather than requiring hacking into the game via StarDraft, this approach meant no gameplay degradation; it also meant this method could be applied to other Blizzard games that used MPQs, not merely Starcraft. This made StarDraft obsolete overnight.

MoPaQ File Format [reverse-engineering]
The complete reverse-engineering of the MPQ archive format and publishing of what remains the authoritative modder's specification the format. Most of this was performed during development of MoPaQ 2000 2.0. While Lelik reverse-engineered StarEdit sufficiently to allow LMPQAPI to call functions in the Blizzard MPQ API in StarEdit, he never actually looked at the MPQ format itself. Thus the work fell to me to provide functions that didn't exist in StarEdit, by writing code that edited the MPQs directly (code which was then integrated into LMPQAPI 2.0). This was also where I first learned how to reverse-engineer a program via disassembly and debugging. While I gave out a lot of information about the format to a number of people on forums and other media, I didn't actually release a full spec document until some time later (the official version of the spec is here, though as it's a wiki it's been known to be vandalized from time to time).

MPQDraft [reverse-engineering, programming]
The third revolution in Blizzard game modding, MPQDraft perfected the MPQ file technique. Like StarDraft, MPQDraft consisted of a loader that actively invaded the game being patched by a mod; however, MPQDraft suffered from none of the problems of StarDraft: it was version (and game) independent, it finally solved the problem of unpatchable files once and of all, and did not produce any gameplay degradation.

Like StarDraft, MPQDraft allowed the creation of "self-executing MPQs", which allow authors of mods to conveniently distribute large, complex mods in single executable files. However, MPQDraft added support for a plugin system, which allowed developers to add on new functionality to mods, while still making use of the basic functionality of MPQDraft. A couple examples of the most noteworthy plugins developed for MPQDraft are MemGraft (now obsolete), which allowed modification of data stored in the Starcraft executable itself (as opposed to in the Starcraft data files), and ThunderGraft (described below).

MPQDraft is now open-source, on SourceForge. Surprisingly, it still gets more than 600 downloads each month (this is only counting downloads through the SourceForge page; mirrors such as the one on Campaign Creations would not be counted), despite the fact that the most recent game it works on, Warcraft III, is about 8 years old, now.

ThunderGraft [reverse-engineering, programming]
The third of my major modding programs, ThunderGraft adding the ability to play modern audio compression formats (e.g. MP3 and Ogg Vorbis) to older Blizzard games, especially Starcraft. Prior to Warcraft III, Blizzard games used either raw PCM (Diablo) or compressed ADPCM (Starcraft, Diablo II, and Warcraft II) audio formats to store music and sound effects; both formats were undesirable for mods because they were either very bulky (in the case of PCM) or resulted in noticeable loss of audio quality with sub-optimal file sizes (ADPCM). ThunderGraft replaced the entire music streaming system of the games with its own, using the FMod Ex audio library to perform audio decoding of any of the multitude of compression formats the library supports. To my knowledge, it is, six years later, still the only modding tool to attempt such a feat. I finally got around to cleaning up and releasing ThunderGraft as open source a couple months ago on SourceForge, though given that the most recent game it supports, Diablo II, is about 10 years old, and the fact that broadband has made small mod sizes less critical than it was 10 years ago, it sees little use today (only about 30 downloads through SourceForge per month).

Allocation Benchmark [reverse-engineering, programming]
A project to examine the relative performance of several memory allocators - the Windows heap, Windows low-fragmentation heap, Hoard allocator, and the Blizzard Storm allocator (SMem, a custom buddy allocator). Allocation, free, and resize operations were logged from an actual game of Warcraft III via function hooking, then fed in order to each allocator while the duration of each operation is measured, and the results compared. Covered some in various posts.

AUS Decode [reverse-engineering, programming]
This project consisted of reverse-engineering the archive (AIF) and digital audio (AUS) file formats in the Mega Man Anniversary Collection to create a decoder that could extract the music directly from the game. Both AIF and AUS file formats were previously unexamined and undocumented, although the audio compression algorithm turned out to be the documented Sony ADPCM variant VAG. Reverse-engineering of both formats was accomplished with nothing more than a hex editor (no disassembler or debugger). I talked a tiny bit about this, but never said much about the technical side of it or released the code.

(BIN) Diablo II Binary Data Format [reverse-engineering]
Reverse-engineering of a number of major Diablo II binary data formats, e.g. armor.bin, itemtypes.bin monstats.bin, treasureclassex.bin, etc. These files are compiled binary versions of the SLYK spreadsheet files containing game global data. This was originally done with the intent of making a data editor tentatively called HellForge, but I never got around to that. I don't believe I ever released the specs of the BIN files; if I did, it would have been on Phrozen Keep.

DxWnd [reverse-engineering, programming]
DxWnd allows full-screen DirectDraw games that do not support windowed-mode DirectDraw to run in a window. I can't remember whether the initial idea was mine or Skywing's, but I did the initial research and reverse-engineering for the program and came up with the basic method. Skywing then wrote the code and debugged the cases that required modifications to my basic method (e.g. programs that combine Windows GDI and DirectDraw for graphics, such as the Diablo/Starcraft/Warcraft 2 Battle.net interface). I later added code to support window resizing via Direct3D, rather than the standard drawing method using GDI, though I can't remember if that code ever got released.

E Terra [programming]
A real-time strategy game based on ecology and evolution. Because this game focuses on nature and the organic, rather than humanity and society, the gameplay is substantially different than any existing RTS I've heard of, though it's bears some resemblance to Populous. E.g. there are no unit classes - unit "classes" are created by the player through gameplay/evolution; units are not built/trained - they are born automatically; etc. Current status: awaiting the motivation to work on it more.

Engram [design]
The name a Portmanteau contraction of "English program", a programming language based on a subset of natural English. This was something I started working on early in my compilers class, when I heard we were each going to be writing a compiler as a term project. Work on it came to an abrupt end when I learned that we didn't get to choose the language for our compilers. Other than what I communicated to a friend in IRC and IM, I never really wrote down a specification or anything.

LibQ [programming]
A small, minimalistic cross-platform library (designed for at least Windows and POSIX support) of highly platform-dependent features, such as multithreading (more specifically, synchronization, inter-thread/process communication, and atomic operations and structures), endian-conversion, and high-performance file I/O. Talked about extensively on this blog, though that was before I started using tags or anything to make the posts easy to find.

NWNScript Compiler [programming]
A compiler capable of compiling NWScript, the world scripting language used in NeverWinter Nights, NWN2, and Dragon Age, to native machine code for use in Skywing's NWN2 standalone server. This is the first attempt at such a thing that I'm familiar with; both the original games and Skywing's standalone server previously implement interpreters to execute the scripts.

In addition to the analyzer, which parses the NWScript bytecode files and generates intermediate representation code, two backend code generators were created to produce native code by proxy. Skywing's backend generates .NET bytecode, which uses the .NET just-in-time compiler to generate partially optimized native code; my backend generates Low-Level Virtual Machine code, which uses the LLVM optimizer and JIT compiler to produce optimized native code.

Q1 [design, programming]
A fairly simple and elegant RISC processor design and emulator. The Q1 began as an idea for a term project in computer architecture class to create a simple CPU and emulator; like Engram, the Q1 was conceived and work began prior to learning that we couldn't design the instruction set (the whole purpose of the Q1). However, I stuck with this one long enough to finish the basic instruction set architecture and create an emulator and sample programs (though not an assembler, which made it a huge pain to program). A number of the design decisions were discussed on the blog.

Ray Tracer [programming]
As with just about everybody who has ever taken a graphics course, I had to make a simple ray tracer. As this was only one assignment (and not a term project), the emphasis was kind of on the simple (there was no requirement for support of meshes, reflection/refraction, etc. However, I really ended up getting into this one, and added a substantial amount of additional features beyond those required in the assignment. Thanks to all my additions, it easily grabbed the top spot in the class.

While I intended to, I never got around to writing much about the ray tracer and the various features I chose to implement (and why), though the project page on the school wiki summarizes the features and shows them off with various screen shots.

recMPQ [reverse-engineering, programming]
recMPQ was a simple program to test some revere-engineering work on the MPQ format. The World of Warcraft Burning Crusade expansion added several new MPQ format features related to support for large archives (greater than 4 gigabytes). However, at the time no actual archives used these features. Consequently, I was forced to rely on pure disassembly, without being able to look at properly-formed archives or even watch the game load an archive using these features. recMPQ was a program to make a large MPQ archive based on my disassembly findings, which I could then replace a BC archive with to observe whether the game was able to successfully load the archive (indicating I had properly used the new features). This information was ultimately added to my MoPaQ format specification.

TextBreaker [programming]
A system to identify the language of a block of text using artificial neural networks. This was my term project (and accompanying term paper) in artificial intelligence class, which integrated AI, my interest in linguistics, and my interest in biology all into one. Unfortunately, identifying languages isn't as easy as it sounds, and the project ended up being more educational - in the sense of revealing difficulties and what does and doesn't work - than remarkably successful at actually identifying text. Nevertheless, it did manage to impress the (undergraduate) class, the teacher (specializing in AI), and my grandpa (a professional linguist), and my teacher and grandpa both suggested that I continue work on it and submit my results to AI and linguistics journals.

I never got around to cleaning up the source to release it (I did the whole term project in a week and a half, which made for very hackish code), but I did post the accompanying Orthographic Language Identification Using Artificial Neural Networks paper back when I turned it in.

StormDump [reverse-engineering, programming]
A memory tracker and browser used to examine the memory use of Blizzard games. Unlike the benchmarking project mentioned above, which merely logged calls to the allocation functions, this project consisted of reverse-engineering of the memory allocation system itself, and the associated data structures. It logged each memory allocation made, and tracked how many allocations were made of given sizes and types, both at a particular time and in total, and allowed you to dump all memory allocated at a particular time via hotkeys. All of this was done by directly traversing the memory structures for the allocation system. I don't believe I ever gave this or the source out to anyone.

Watcher [programming]
A simple program that logs all calls to API functions in various libraries that you specify using an configuration file. Version 1 of this hooked only functions specified in specified DLLs via INI files; some functions, such as the MPQ APIs, had hard-coded parameter-logging functions. Version 2 was capable of hooking all functions in all libraries and was intended to be scriptable to allow function-specific parameter logging for logged functions, though scriptability was never actually implemented.

ZIC2RAW [reverse-engineering, programming]
A project/program to extract the digital music files from the 3DO version of Mega Race. The format actually ended up being quite trivial to reverse-engineer, though the files turned out to not be entirely self-contained - part of the music data was embedded in the game executable itself, and not stored in the separate music files. Apart from a tool to work with 3DO discs, all of the reverse-engineering for this was done with a hex editor.

Do I Speak WHAT?

2010-01-05T18:44:00.001-08:00

Reference material: HP 15C, z80

Random Fact of the Day

2010-01-03T13:23:00.000-08:00

In .NET, String.GetHashCode computes the hash code every time the function is called. This is slightly surprising given that Strings are immutable, and thus could easily compute the hash code on construct or on the first call to GetHashCode (although both of those options do have associated overhead).

Someone I know believes that Java is the same way.

& Modern Things Part 3

2009-12-28T19:55:00.000-08:00

So yeah, the Xbox 360 is pretty uninteresting, apart from the memory limitation. Fortunately, the third and final thing you can program with XNA is rather interesting: the Zune. The Zune is Microsoft's answer to the iPod: a portable music player. However, the Zune is also capable of running third-party programs through XNA. This makes it rather interesting, as it gives you the best taste of what it was like to program a console in the past (back before console CPUs were in the GHz and memory was in the hundreds of megs), as it has some of the same programming considerations (or at least moreso than the 360 or PC).

There are a few different models of Zune with different capabilities, which can be separated into what I'll call the 'Zune' (the first several models, which are pretty much identical for our purposes), and the recent Zune HD.

The Zune series is shown above. Members of the series vary in exact design, but all have a few common features. All models have a low-power ARM CPU, 64 megs of RAM, and has the ability to do basic bitmap graphics. They contain a 240x320 LCD screen in 3:4 aspect ratio (the screen size varies from 1.8 to 3.2 inches, diagonal), running at 30 FPS (some high-end models also support 60 FPS). For input, each has a circular pad as well as one button to each side of the pad.

These features give the Zune a unique set of programming considerations. Obviously, the CPU is drastically less powerful than on the PC or Xbox 360. Games have a quota of 16 megs of RAM usage, in which both code and data must fit (although as this is only 1/4 of the total RAM of the Zune, garbage collection overhead is much less of a problem, and you should be able to use all 16 megs without seeing too much garbage collection slowdown). Graphics are limited to 2D sprite-based operations, and screen space is very limited (the Zune actually has a quite impressive display resolution for its screen size, but it's still tiny). Of course, the fact that this is a portable system means that battery life is also an issue. But perhaps the most tricky issue is the input system.

The Zune is designed to be used standing up, as shown in the above picture. In this orientation, the screen is taller than it is wide. Control can use both thumbs, with one thumb on one button, and the other thumb shared between the circular pad and the second button. However, as games typically are designed around a screen that is wider than it is tall, this configuration comes off as somewhat unnatural, though some games are more appropriate for this than others (e.g. a top-down shooter would have no problems, here).

Alternately, the Zune may be turned on its side, yielding the standard 4:3 aspect ratio used on everything prior to high-definition televisions and wide-screen monitors. The chief problem with this configuration, then, becomes control. Due to the button configuration of the Zune, this configuration allows only one thumb for input, shared between the circular pad and the two buttons. This has the effect of drastically reducing the potential complexity of gameplay input, as it's far more cumbersome to switch between buttons than to simply have a second thumb take care of one of them.

The Zune HD is shown above. You could really call this the Zune 2 (or, if you're Nintendo, the Super Zune), as it's almost entirely different from the previously mentioned Zune series. It's powered by an nVidia Tegra (2600), a system on a chip which both acts as an (ARM) CPU and a GPU capable of 3D graphics (although thus far XNA does not support 3D on the Zune HD). As far as I know, the amount of memory on the HD has not been published, though it's safe to say it has at least 64 megs RAM. While the screen is only 3.3 inches (about the same as the higher-end Zunes), the screen is now 480x272 (when laid sideways) in the HDTV 16:9 aspect ratio.

Perhaps most significant, however, and the reason the Zune is much more interesting than the PC and Xbox 360, is the change in input system. As can be seen in the image, the Zune HD has no buttons or other controls. Instead, the HD features two new input methods: a multi-touch display and an accelerometer.

For those not familiar with it, multi-touch displays are a type of touch-screen, which take as input a point on the screen and the pressure exerted on the screen at that point. Multi-touch takes this to the next level by allowing multiple points of contact, including tracking of movement of each point. This allows for very flexible and powerful input, permitting such interfaces as "point and click" via pressing the screen at a point, dragging and dropping, and things such as gestures. This even allows interfaces such as the one seen in Minority Report (and other sci-fi-ish depictions), where multiple points of contact with the touch screen can be used to grab and move, rotate, or resize items on screen (this type of interface exists in the Microsoft Surface and other multi-touch devices; also, be sure to check out the Dungeons and Dragons on Surface demonstration).

You might not be able to guess what an accelerometer is, based only on the name: obviously it measures acceleration, but unless you're into physics, you probably wouldn't make the connection with gravity. Technically, holding an object in air (as opposed to letting it free-fall) requires an upward force to be applied to the object, and a force produces acceleration. An accelerometer measures this acceleration against the force of gravity; in other words, an accelerometer measures which direction is up, based on the orientation of the device. Of course, it also detects other types of acceleration, such as movement in space, as well. Between the possibilities, this allows a number of interesting (and impossible, with traditional input methods) input systems, such a basing the in-game camera on position and/or orientation of the Zune, actions triggered by bumping or shaking, etc.

Microsoft makes the multi-touch screen and accelerometer available in XNA through the XNA Zune Extensions addon. Once you've downloaded that, search the help for Zune HD Input Overview for general information about support. After that, zunezune.org has posted a helpful simple "game" that demonstrates multi-touch and accelerometer: the code is available here, and a video of the program in action is below. Finally, Platformer: Adding Touch Support (also in Extensions help) is a tutorial that shows you how to add multi-touch and accelerometer support to the platformer starter kit.

& Modern Things Part 2

2009-12-23T12:23:00.000-08:00

So, after looking a bit at several (very) old game systems, how about we look at a couple of the new ones. Though in reality, the XBox 360 is actually pretty boring; which is to say that it's more or less a modern computer.

The 360's Xenon CPU is a pretty typical incarnation of the PowerPC line used in older Macs, and is related to the Playstation 3's Cell CPU (although the Cell has a very unusual architecture resembling a cluster on a chip, and differs quite a bit from other PowerPC chips - or most CPUs, for that matter). The PowerPC line, the low-end portion of the larger Power line, are RISC processors with simple instructions limited primarily to operations on registers, in contrast to the CISC x86 and the CPUs of the 2600, NES, and SNES, which tend to use many instructions that operate on memory data.

The Xenon is composed of three symmetric 64-bit cores with a shared L2 cache. Each core executes two threads simultaneously, and contains (among the expected things) a SIMD vector unit for significant math performance (although if you're using XNA you won't have access to the vector unit). The only remotely noteworthy part of the CPU is the fact that unlike some other PowerPC varieties (and all Intel CPUs for quite a while, now), execution is in-order, meaning that it must pause execution of a thread when a slow I/O operation is required; the assumption then is that the number of threads executing at a time (2 per core) will reduce the impact of individual stalls.

The Xenos GPU is also fairly uninteresting. It's a custom ATI 3D GPU designed specifically for the XBox 360 and optimized for console games, though a lot of it resembles common PC GPUs of the same vintage. It supports the DirectX 9 Shader Model 3, although it contains some custom extensions that provide some of the features new in DirectX 10 Shader Model 4 (though the details may differ), such as the unified shader architecture. It also has dedicated hardware to provide 4x anti-aliasing for "free" (as opposed to the performance penalty that normally occurs with anti-aliasing) and optimized z-only rendering. Finally, after all the fancy rendering is done, the 360 supports several (television) output resolutions from 640x480 (standard TV) to 1920x1080 (highest HD widescreen).

But the most noteworthy parts are the ones we haven't seen before (at least in this series of posts).

Some versions of the 360 come with a hard drive of varying sizes. In addition to saved games (which can also be stored on memory cards or internal flash memory, on models without the hard drive), this drive is used for game caching (hard drives are faster than DVDs) and optional downloadable content. It's also used to store the XBox compatibility software that allows the 360 to emulate games for the original XBox.

Finally, all XBox 360s come with the ability to connect to the internet (wired ethernet ports are standard, with a wireless addon), especially for the purpose of connecting to the XBox Live service. Live is a social platform that covers a wide range of services (although some require a paid subscription to Live), including friends lists and communication; multiplayer matchmaking and play; game achievements that allow your friends to see your gaming accomplishments; voice and video chat with friends; downloadable bonus game content; the Live Marketplace, where you can purchase and download addons and entire games (including XNA games) and other content (e.g. movies); and several major third-party web services such as Netflix streaming movies and Last.fm steaming music.

So, that's the hardware and the platform. But what's it like to program? Well, thanks to the surreal veil of secrecy surrounding consoles in general, that much isn't really common knowledge, and I'm not entirely sure. Development is in C or C++, probably with the Intel C++ compiler. The 360 uses a custom operating system (so they say) that supports at least some approximation of the Windows API and DirectX; while the OS does not use the same driver system Windows normally uses, the CPU is probably the only piece of hardware in the system programmers are supposed to directly access, with other hardware abstracted through the Windows or DirectX APIs or some such. Given this, if Microsoft is smart, they made it as similar to programming on Windows as possible, so that developers can transition from the PC to the 360 with minimal education. Though one thing that will definitely have to differ is the compiler intrinsics, for things such as vector math (perhaps the same intrinsics that were used on the PowerPC Mac) and multithreading-related things (e.g. memory barriers; remember those?).

The situation is different if you're using XNA. In this case programming the 360 is almost identical to programming the PC via XNA. Programming is done in C#, and run on the .NET compact framework. The runtime libraries consist of a subset of the .NET class library and the additional features supplied by the XNA class library. No hardware is directly accessible; the CPU and memory are hidden behind the .NET framework, and graphics and sound hardware can only be accessed through the XNA class library (as far as I know you can't directly access DirectX through XNA, at least on the 360).

But regardless of how you program it, perhaps the most noteworthy difference between programming a PC and the 360 is the memory limitation. While on PCs it's always been cheapest to just make your users buy more memory, on consoles it's frequently the case that you have to actually spend development manpower shaving off memory usage to make your game fit in the console's memory (at least for large, complex games). The 360 has 512 megs of memory. While this may not sound so bad at first, you have to realize that this is common memory, shared by both the CPU and the graphics system (though at least the OS probably takes up drastically less memory on the 360 than on the PC). Compared to PC games that typically take north of a gig of main memory and 512 megs video memory, 512 megs starts to look pretty small (for the curious, the Playstation 3 is comparable: 256 megs main memory and 256 megs graphics memory).

This is especially true in the case of XNA. As stated previously, thanks to garbage collection, you can only use 30-40% of the total system memory before you start seeing a substantial decrease in available processing power due to garbage collection; on the 360 this comes out to something like 64-128 megs, depending on how much memory is used for graphics. Fortunately, there's a way to deal with this penalty: avoid garbage collection entirely. Garbage collection is triggered when a memory allocation fails due to there not being enough unallocated memory to perform the allocation; the framework then performs garbage collection to look for memory that was allocated but is no longer being used, and can be freed to make room for the new allocation.

In other words, if you can avoid allocating memory during gameplay, you can prevent garbage collection (you could also manually cause the framework to do garbage collection at times which are convenient, such as during loading or pausing); this is optimization 101: the fastest code is the code that isn't executed. Use structs, which are allocated on the stack or within the containing memory structure, rather than classes, which are allocated out of the heap; use allocation-minimizing algorithms and data structures, such as an open-addressing hash table (e.g. Dictionary), where the hash table is an array of entries, rather than an array of linked lists or a binary tree (e.g. SortedDictionary), which must allocate memory for each entry; use reasonable reserve sizes for structures so the structure isn't likely to need to be reallocated during gameplay; use free lists as much as possible; use specific enumerators rather than IEnumerator; etc. - anything that can significantly reduce the need to allocate memory.

& Modern Things Part 1

2009-12-18T19:00:00.000-08:00

One thing that has always kind of mystified me is the degree of inaccessibility maintained about video game console development. For almost every single video game console in history, getting access to the manufacturer's developer documentation and hardware requires that you be licensed (and it sucks to be you if the manufacturer doesn't like you) and have a large sum of money for the development kits; for most systems, the accessibility of the system to lone hobbyists has been 0.

Of course, eventually the system, if there's enough interest, is reverse-engineered, and unofficial documentation is put up on the internet (and perhaps followed by law suits). But such documentation is usually incomplete, inaccurate, or just plain badly written, and there's almost always anti-piracy lockout mechanisms that prevent you from actually running any code you manage to write on the system itself.

This is a strikingly odd decision, and seemingly self-destructive. Many software companies turn a blind eye to piracy among college students because they realize that students pirating their programs in college, when they couldn't afford to buy the programs, anyway, makes them more likely to use them professionally, when they do have money to purchase the programs. Some companies even give away their programs to students for educational purposes, for the very same reason: more student users that get the program for free means more buyers after graduation. Economically, it's a simple business investment, trading theoretical income now, which they couldn't collect anyway, for greater actual income later.

This situation on consoles is no different. If you promote hobbyist development on your game console, that increases the probability that those hobbyists will develop on your console when they go pro. This is especially applicable considering that the modern game console business model is to sell the consoles at a loss, then make up that loss in licensing of games; thus, every additional game developed for your system equals more money for you. Ultimately, I suspect the reason for this odd behavior lies in the lockout mechanism: in order to allow hobbyists to develop for the console, the console cannot have a lockout mechanism, which would make it much easier to pirate games.

Anyway, there are only a couple exceptions to this rule, that I know of. Sony published a mini developer kit for the Playstation, called the Net Yaroze, for about a grand, which included a black development version of the system (lacking the lockout hardware), various documentation (I don't know if this was the same or inferior to the professional documentation), some run-time libraries (probably inferior to the professional kits) and software to get custom code onto the Yaroze. Of course, anything you write could only be run by people with their own Yaroze, due to the lockout system.

Very surprisingly, only in the last couple years has anyone actually targeted non-professionals as serious developers for their system. Of course I'm talking about XNA (official site). XNA is a free game programming framework built on top of the .NET platform. Games are written in C# in Visual C#, and make use of the .NET and XNA class libraries. The .NET libraries (a subset, to be precise) provide general support code such as data structures and multi-threading, and the XNA libraries cover hardware access, such as graphics and sound, and various support routines too game-specific for the .NET libraries, such as quaternions and interpolated curves. Use of the .NET framework also provides things such as garbage collection, that make programming easier and faster; the use of non-native code and APIs also means that, if code is written carefully, a single game can be compiled and run on all three platforms XNA supports: Windows, Xbox 360, and the Zune (the fine print: development on the 360 requires a Creators Club Premium subscription; membership is available to anyone, but costs $100/year).

Unlike the completely unrelated, professional Xbox 360 Software Developer Kit, XNA is targeted specifically at hobbyists and independent developers (e.g. a person who writes a small game and wants to sell it for cheap). Microsoft runs an active community site containing Microsoft-written code samples, tutorials, and starter kits (e.g. a 2D RPG and a 3D racing game), and forums where both hobbyists and XNA developers post. There are also third-party XNA tutorial/code sites, though Ziggyware, the largest and best, imploded a ways back (humorously, according to Google, Ziggyware and a few others had posted the presentation I wrote on kd-trees as part of my graphics term project, prior to the site going under).

Once a game is finished, in addition to distributing the source and/or binaries manually, finished games can be submitted to several places, depending on platform. Free Windows games may be submitted to the XNA community website for download. Finished games can also be submitted to the Xbox Live Marketplace, where they can be downloaded, either for free or for sale (whatever you decide on), by anyone who has an Xbox 360 (a Creators Club subscription is not required to play games published on the Marketplace). To say that again: you can sell your amateur Xbox games for cash through Live Marketplace, right next to professional downloadable games.

Of course, this isn't without its caveats. XNA doesn't allow you to directly access the hardware, or use the same low-level API professional developers use from a natively-executed (after compiling) language like C++. This means that XNA games cannot compete in sheer speed and power with professionally-developed games. It also means that you may not be able to access 100% of the features of the hardware, where XNA only exposes a portion of the feature set; one very notable omission is the ability to use the Xbox 360's vector math unit, a fact that drastically reduces the performance potential for some types of calculations.

Second is the fact that it's a .NET platform. While this choice was good from an ease of programming perspective (garbage collection is easier to program and less prone to various coding errors, especially given that most of the people coding on XNA will be amateurs and thus may not be very good), it's not so good from a performance perspective. Perhaps the most stereotypical problem for garbage-collected systems like Java or the .NET platform is that garbage collection is far from free, both in terms of CPU and memory. If you plot the proportion of time the CPU spends collecting garbage (instead of, you know, actually running the program) against memory usage, you'll find that after a certain threshold cost grows exponentially. One study found that, when memory utilization is at 20%, garbage collection is no more expensive (and maybe even faster) than explicit allocation/deletion, but costs rise quickly from there: garbage collection is 17% slower at 33% memory usage, 70% slower at 50% memory usage, and as you approach 100% memory utilization garbage collection approaches 100% of total CPU time.

A third major point of concern is that the XNA framework on the Xbox 360 does not have the full .NET framework/compiler, but only the Compact Framework. This version is designed for hardware that doesn't have a lot of memory or processing power (especially things like PDAs), and offers reduced memory and CPU overhead at the price of sub-optimal execution speed. Of the various optimizations performed by the full-fledged .NET framework, only a subset are performed by the compact framework; for example, inlining is restricted, virtual function calls are implemented in a more compact but slower manner, and both the framework and garbage collection algorithm are just dumber in general, to name a few issues (see here for a more lengthy list).

However, making decisions is easy when there's only one option, and if you're a hobbyist wanting to code for a modern video game console, that option is XNA. Even if you're not interested in consoles, XNA still provides a convenient and free game development platform, designed specifically with hobbyists in mind. It also opens the possibility of making a bit of money off your amateur games prior to going pro.

& Moral Panics

2009-12-15T14:24:00.000-08:00

One topic that came up rather suddenly in IRC is the topic of the irrationality of humans when a person feels wronged. The particular topic in chat was that, I'm told, you should never, ever touch leaked materials, such as the Windows source or COFEE, because this tends to send companies (especially the one that produced said thing) into moral panics and refuse to ever hire you.

Think about this for a moment; a little bit of rational thought concludes that this is highly irrational behavior, reminiscent of the Pointy-Haired Boss (is there a Dilbert strip on this topic, I wonder?). If you were Microsoft, for instance, and you were looking to hire a programmer for the Windows team (although this could also apply to other parts as well), the #1 most desirable candidate for you is the one who has played extensively with the leaked Windows source, all other things being equal. Not only would categorically refusing to hire such a person result in no benefit, but it would materially harm you as a company, by refusing the candidate most beneficial to you. This is a case where moral outrage contradicts reason, and acting on that outrage results in self-destructive behavior that does more harm than good; or, as the saying goes, cutting off your nose to spite your face.

An alternate form of this is observed extensively in the copyright industries, who have a long history of various licensing and technology blunders with a detrimental effect to their own sales in the name of fighting piracy (and the goal of fighting piracy is, you know, to increase sales). In this case the moral outrage is provoked by a fixation on the amount of piracy; this is a fundamentally flawed measurement. The entire purpose of business is to maximize profit, and that is concerned (usually) solely with sales: reducing piracy (if you can even manage that) is of no benefit if doing so does not produce a net increase in sales at the same time; whatever the exact number of pirated copies may be is entirely irrelevant. And if you haven't managed to boost sales in the process, you're all the worse off because you're already out the money you spent trying to fight piracy.

(for those wondering, yes, the term "moral panics" is from Patry)

& Even Older Things

2009-12-13T16:32:00.000-08:00

On Friday I went to a free, open presentation at University of California Irvine. Normally I wouldn't even mention such a thing on the blog, but it just so happened that a significant part of of presentation was about the hardware of the Atari 2600, a game console launched in 1977, 6 years before the Nintendo (NES). As this fits right in with a series of posts on this blog, I figured I might as well write about it.

Interestingly, the 2600 used almost the same CPU (the 6507) as the NES (6502) and Commodore 64 computer (6510). According to Wikipedia, the 6507 was a smaller version of the NES's 6502, while the 6510 was an expanded version of the 6502 . The 6502 supported 64 KB of address space (16-bit addressing), while the 6507 supported 8 KB (13-bit addressing); the 6502 also supported (external) hardware interrupts (the vertical blank interrupt, in the case of the NES), while the 6507 did not.

In contrast to the NES's 2 KB and SNES's 128 KB, the 2600 had an amazing 128 bytes of RAM (although more could be added on cartridges, for a manufacturing price). Early 2600 games came in 2 KB ROMs, although the system supported up to 32 KB with bank switching (4 KB at a time); in comparison, NES games ranged from (I think) 32 KB to 768 KB (also with bank switching: 32 KB at a time), although in theory it could support more.

But by far the most "interesting" thing about the system was the graphics system. Unlike the NES, SNES, and pretty much all consoles and computers made in the last three decades, the 2600 had no video RAM to speak of. Instead of storing on-screen image data in video memory which is then composed by the graphics chip and output to the display, on the 2600 the video was drawn actively, one line at a time; by "actively" I mean that the game had to compose each line as it was drawn by the television. Each line, 160 pixels wide, was composed of 24 two-color background blocks, 2 eight-bit single-color bitmap sprites, 2 single-color line "missiles" whose colors mirror those of the sprites, and a line "ball" that was much like the missiles, but was the color of the background.

However, while the hardware was very (very) limited, the ability (or necessity, in this case) to change the screen contents while drawing was underway provided some flexibility for the clever programmer (just like with the NES and SNES). Clever use of the missiles and ball, changing each scan line, allowed for more complex graphics than you'd imagine given the hardware capabilities. By changing the sprite configuration you could have more than two sprites, though having more than two sprites on the same scan line required alternating between them each frame, resulting in flicker. Alternating palettes allowed the system to display 4 different colors on each line (out of a total of 128), as well as multicolored sprites and backgrounds. Clever use of the missiles and ball allowed for additional sprites per line, or multi-color and non-block backgrounds. Developers even found that they could expand the background to a full 48 blocks (the background is 48 blocks wide, but the background is only 24 bits, describing the left half of the screen; the right side is formed by repeating or mirroring the left side) by modifying the background registers halfway through the line.

Finally, the 2600 had sound analogous but inferior to the NES's. It had two channels of sound, one generating a square wave of varying pitch, the other white noise. In comparison, the NES had five channels: 2 square wave (used to approximate most melodic instruments in music), one triangle wave (often for bass or low-frequency strings), a noise channel (used for drums and other percussion), and a waveform channel (I'm not familiar with any instances of this being used by games).

Pac Man, showing off more than two sprites and 48-block-wide backgrounds:

Pitfall, showing off multi-colored sprites and backgrounds, as well as (possibly) non-block backgrounds:

Random Fact of the Day

2009-12-04T19:05:00.000-08:00

Exact Audio Copy, like some similar programs (I know older versions of Nero are like this) can be made to work on a Windows limited user account, but it requires a couple of things.

First, you have to make the DAT files in the EAC folder writable by all users (or at least those you want to be able to use it).

Second, you have to enable low-level access to the disk drive for limited users. The easiest and least dangerous (in terms of downloading software from who knows where) method of doing this is to simply use Nero BurnRights (search down on the page), and it will allow you to set this option; note that you don't need to actually have Nero to use this program. Of course you'll have to install it and run it as admin, but once you set the option you'll be able to use EAC (and other similar programs) from any user.

Finally, make sure EAC is set to use the Native Win32 Interface (EAC Options->Interface); this should be the default, but who knows.

& Almost as Old Things

2009-12-03T13:05:00.000-08:00

Recently I've had the whim to play through Final Fantasy 6 (3 in the US) again, and have been doing so on an (SNES) emulator. I'm currently about to start the last level, but that's beside the point of this post. While playing, I thought I'd take a look at the SNES hardware and write a blog post about it, given that I'd already looked at the NES hardware - though not anything half so extensive as what I did with the NES, just a look at the basic hardware. What I found actually surprised me. As it turns out, the SNES really is the Super NES; that is, it has very similar hardware, only better.

First of all, the CPU is a generational upgrade to the NES' CPU, bigger and better. The CPU is now 16-bit (as opposed to the NES' 8-bit CPU), but has essentially the same instruction set (with some augmentations). The CPU is still CISC, sporting the same three general registers (an accumulator and two index registers) and operating on an accumulator register using the contents of memory. However, the CPU now has much greater flexibility in memory access, with a 24-bit pointer register and the ability to access memory relative to the stack pointer*. It also now has multiply and divide instructions, as well as a few other things. But deep down, it's the very same instruction set architecture, and in fact has an 8-bit compatibility mode that lets it directly execute code from the original NES CPU.

*Both of these features were conspicuous absent in the NES, as I believe I noted. As the NES only had 8-bit registers, it had no way to hold pointers (which were 16 bits) in registers; to make use of pointers the NES had an indirect addressing mode where the CPU would write a pointer to memory 8 bits at a time, and then had an instruction to load/store a value through that pointer (think "mov reg, [memory]"). While the NES did have a stack, it had only push and pop instructions, and lacked the ability to access data relative to the stack pointer, preventing use of the stack to pass parameters or store local variables; consequently, parameters and local variables were assigned fixed memory addresses, and the stack was rarely used.

The situation is somewhat similar in the graphics system. While the graphics chip is drastically more powerful than the NES', it's based on the same concept of background layers and sprites, all drawn from a (larger) bank of 8x8 tiles. The SNES supports twice as many sprites as the NES (and a lot more per line) and sprites can be much larger (up to 64x64, compared to 8x16 on the NES), with 16 colors each (compared to 4, including transparent, on the NES); but perhaps the most interesting improvement is that there are now 4 background layers, and they can be combined via various raster operations in many interesting ways.

To illustrate this, take a look at this picture: a typical shot from a battle. The SNES supports 8 different graphics modes. For the most part the difference between the 8 is the number of layers and how many colors each layer supports (presumably this is due to it being too expensive to put enough video memory in to allow full color from all layers at once). In this scene I'm guessing that it's using mode 3 ("3 layers, two using 16-color palettes and one using 4-color palettes"), based on the number of layers I can see plus the number of colors.

To show off the graphic abilities of the SNES, next is a screen shot of the special effects from casting of a spell, which we're going to dissect.

This is layer 1. You can see the bubble from the spell here, sporting transparency that tints other layers. Interestingly, you can see part of a screen (the magic selection screen) that isn't open at all; in the composite, this section is covered up by the bottom part of layer 2. In other words, in the top part of the screen layer 1 is drawn on top of all other layers, while the bottom part is drawn at the bottom of the layers; this goes to illustrate what I said about very complicated and flexible interaction between the layers (it's possible this involves changing the layer parameters in between lines, a technique I mentioned being possible on the NES).

Layer 2 is the background for the whole screen, the top section the battlefield, the bottom section the menu system. Note that a sine wave offset pattern has been applied to the battlefield background; while I haven't investigated it to be certain, I suspect this is accomplished by simply modifying the screen scroll position in between drawing each line.

Layer 3, again serving an array of purposes, is used for special effects and the text on the menus. You can't see it clearly at all from just this layer, but this layer is used to produce those discolored blotches on the spell bubble. This may be another case of transparency for the special effect, but it's hard to tell from screen shots alone.

To illustrate this fact, layers 1 and 3 together:

And finally, the least interesting part: the sprite layer. Although here again we see something rather unexpected: it looks like there's some type of sprite garbage that is normally (again) covered by the menu.

So, that's basically what 7 of the 8 graphics modes are all about. The 8th one, known as Mode 7, however, is a bit different. It has only a single large 256-color background layer, but it has the ability to apply a transformation matrix to the background, allowing scaling and rotation. This is used very commonly in SNES games, especially with the swap-the-registers-between-lines trick, allowing it to do primitive 3D perspective projection. Believe it or not, that minimap is actually a sprite (as is some of the glow in the background).

One particularly interesting (in the sense of peculiar) feature of the SNES design is the sound system. As opposed to most sound systems, the SNES system does not consist of the CPU simply writing channel parameters such as sample #, frequency, etc. to the sound chip which then performs the requested operation. Rather, the SNES has a separate CPU (the SPU) which acts as a sound coprocessor: sound programs are written, assembled, and then executed on this coprocessor; once the program has been uploaded, the sound system can play (e.g. music) without any further involvement of the main CPU at all (I proved this a decade ago by showing that shorting between two pins on the SNES would crash the main CPU while the SPU continued to play the music without missing a beat), though obviously the main CPU must instruct the SPU when it's time to play dynamic sound effects.

We can only guess why the SNES was designed this way. The most obvious possibility is that this frees the main CPU from having to deal with music and sounds effects, leaving it more cycles to spend on something else (especially in the case where one or more channels of the music must be temporarily dropped to allow a sound effect to be played).

An alternate possibility that I haven't been able to confirm is that this is done to increase the resolution of the audio system. In Blaster Master, the game would perform all the calculations for the frame, then spin waiting for the vertical blank interrupt to begin work on the next frame. Thus code executed 60 times a second, apparently including audio code. If this is true in the general case, that limits the resolution of audio operations to 1/60 second as well. In contrast, the SPU runs at 1 MHz independent of the main CPU, allowing it to issue commands to the sound generator at any time, in theory allowing for higher music tempo and more complex audial effects.

The Taxonomy of Linking

2009-09-19T21:50:00.000-07:00

There are generally at least two steps to building a program, regardless of language. Compiling takes a source code file (operating on one file at a time), parses it, and produces machine code (or some manner of other thing such as Java bytecode) in what's called an object file. Here, there's one object file produced from each source file.

Linking then occurs on the set of object files for a project, producing a single binary. 'Linking' refers to connecting the code between object files, so that functions in one file may access functions and data in other object files, which the compiler couldn't do because it works on one file at a time. The linker also adds the operating system-specific wrapper material needed to allow the OS to load and execute the binary.

That's the general idea, anyway. As with most things, reality is more complicated.

What was just described is known as static linking (or build-time linking). Static linking is when called code is included directly in the binary. It's loaded and unloaded with all the other code in that binary, and as such is always available. The code may either come from object files, as above, or from what are called static libraries - essentially archives containing multiple object files combined into one.

However, there are disadvantages to static linking. Because the code is tightly integrated into the binary, it's effectively impossible to update any functions without recompiling the entire binary. Furthermore, because the code is included in each binary, functions used by many binaries must be duplicated, wasting space.

The alternative to static linking is dynamic linking. In dynamic linking, common functions are built into stand-alone binaries called dynamic link libraries (DLLs). Functions in these DLLs, unlike in static libraries, are not integrated into other binaries by the linker, but instead are called directly from the other binaries. This requires the functions be exported - a process in which the linker writes information into the DLL about what functions the DLL contains and where those functions exist in the DLL; this data is then used by the operating system to allow other binaries to locate and call these exported functions (importing). As DLLs exist independently of binaries that call exported functions, only a single copy of exported functions need exist on disk or in memory, and DLLs may be updated independently of other binaries.

Dynamic linking may further be classified as load-time linking or run-time linking. In load-time linking the linker, when creating a binary that calls functions in DLLs, creates an import table, which lists all DLLs and functions therein that the binary requires. The operating system then, when loading the binary, automatically loads all of these DLLs and finds the addresses of all imported functions, writing the addresses to fixed places in the binary; the binary may then trivially call the functions through these pointers that are at known locations. This is entirely automatic; the DLLs are automatically loaded when the calling binary is, and unloaded when the calling binary is unloaded (assuming no other binaries still need them), ensuring they're always available when needed.

To accomplish this, the linker needs what are known as import libraries. These are generated by the linker when it builds the DLL, and contains a list of all functions exported by the DLL. The reason this is necessary is that DLLs themselves contain only a function name (or ordinal number) - only enough information to allow the operating system to locate the desired function; they may not include information such as what parameters a function takes or the calling convention to use to call the function, which are necessary to seamlessly link to the function. A consequence of this is that both the DLL name and all functions needed must be known when the calling binary is linked.

The other type of dynamic linking is run-time linking. Unlike load-time linking, in which the entire importing process is automatic, the run-time linking process is entirely manual. You must manually load the DLL when you need it, call OS functions to get pointers to the desired functions (which you must manually specify by name/ordinal), manually call the functions through the obtained pointers, making sure you use the right parameters and calling convention, and finally manually unloading the DLL when you no longer need it.

As this is much, much less convenient, you generally use load-time linking whenever possible, reserving run-time linking only for those times when you can't use load-time linking for one reason or another. Generally this is because you don't know the name of the DLL (or the function to import) at link-time. There may be multiple DLLs with different versions of a function (e.g. in Diablo II there are DLLs for the graphics system, with separate DLLs for DirectDraw, Direct3D, and Glide); the DLL may be loaded based on user action (e.g. loading plugins); the DLL may not exist until run-time (e.g. the calling binary must download the DLL first); etc.

(for more general information on DLLs, see The Old New Thing)

Sometimes, however, you get in the unenviable position of not being able to use either. This is the situation I found myself in when linking ThunderGraft to the FMOD Ex DLL. Because the DLL will be packed into a Self-Executing MPQ and extract as a temporary file with a random name, I couldn't use load-time linking (which requires a fixed DLL file name). However, the fact that the DLL was exporting full classes meant that I couldn't use run-time linking either, as the names were too complex to manually specify (with such memorable names as "?createSound@System@FMOD@@QAG?AW4FMOD_RESULT @@PBDIPAUFMOD_CREATESOUNDEXINFO@@PAPAVSound@2@@Z" [spaces inserted so the blog formatting doesn't get all screwed up by the huge string]). Static linking was also out, as the authors do not make a static library of FMOD available (which isn't too surprising as static libraries tend to be compiler- and version-specific).

Fortunately, there's one more option: delay-loading. Delay-loading is essentially a neat linker trick. It uses an import library for a DLL, but instead of generating import tables it generates code that loads the DLL and get the imported function addresses through the run-time linking functions; the DLL is loaded and the function addresses obtained when an imported function is first called (or you tell the linker code to do so at a time of your choosing). This allows the convenience of load-time linking with the flexibility of run-time linking, and allows you to get out of sticky situations like this one.

Of course, in this case it was all due to poor design in FMOD to begin with. It's a well-known principle that you should never export full classes; a much better way is to export pure virtual classes. This avoids the problem because functions in virtual classes are not exported individually, but rather accessed through the v-table; no exports to link to, no names to mangle, etc. It's to avoid this very problem that COM chose to use pure virtual classes as the basis of the COM object system, after all, and there really isn't any better alternative.

& Hobbit Birthday Parties

2009-09-15T16:38:00.000-07:00

There probably aren't many that care that wouldn't see my post on Campaign Creations, but here it is just in case:

Well, it's that time of year again, and I've got some presents to give out. First, I released build 2009.09.13 of MPQDraft a couple days ago. While it only fixes bugs, it fixes some major ones - so major I'm amazed nobody told me about them in the last year and I had to find them myself.

The bugs fixed, in approximate order of severity:
-SEMPQs not activating for games specified with relative names
-plugin page not setting the plugin pointer after selecting with Browse, resulting in a crash
-plugin page stops listing plugins after one fails to load
-not saving custom executable names in the SEMPQ wizard
-plugins weren't forced to use proper plugin IDs for their modules, allowing some plugins to get away with bad behavior that didn't work with FireGraft (which forced plugins to use the correct ID)

As with the last year and a half, MPQDraft is open-source on SourceForge. You can get both the binaries and the source from the files page.

Second, ThunderGraft has been resurrected from the dead. For those who haven't heard about ThunderGraft before, it allows the use of MP3s, Ogg Vorbis, and other sound compression formats in Diablo, Diablo II, StarCraft, and WarCraft II: Battle.net Edition, which give higher audio quality and smaller file sizes than the WAV compression used in those games normally; ThunderGraft also integrates with StarEdit to allow maps to use non-WAV sounds in triggers. I'm calling it a beta version as ShadowFlare just yesterday mentioned a crash that only occurred on her computer, and I probably won't have time to investigate it until at least tomorrow.

And finally, as sort of "present #2.5", ThunderGraft has been open-sourced as well, and it's also on SourceForge. The binaries are available on the files page, but I haven't gotten around to putting a ZIP of the source up yet. Specifically, I really, really need to clean up the directory structure of MPQDraft and ThunderGraft to make it much easier for people other than me (without my directory organization) to compile it. You can still view the source through the source browser, or download it with Subversion or CVS, but you probably won't get it compiled without a bit more info from me; I'll get to that when I have time.

As always, there are two flavors: release and debug. I'd advise using debug for mod development, as it generates log files that are very helpful in fixing bugs, should you find any (but would probably annoy people who download your mod).

Enjoy!

& Very Old Things - Part 3

2009-08-31T08:00:00.000-07:00

So. Thus far everything I did involved nothing more than the memory editor and cheat search. In other words, something just about anybody could do. To really say that I reverse-engineered Blaster Master, I needed something a lot bigger, and I knew just what to do: I was gonna find the cause of a 21-year-old bug. There's a well known glitch in Blaster Master that on some bosses, if you or the boss is being hit when you pause the game, you (or the boss) will continue to take damage while the game is paused. This only works on some bosses, however, leaving a big question mark as to whether it's a bug or a feature (it was especially strange that it affected both player and boss); I wanted to find out.

Unsurprisingly, it's quite a bit of work to reverse-engineer something you have absolutely no info on (e.g. in computer programs you at least know OS API calls the program makes, and can use that as a starting point), especially when you're learning both the hardware and the assembly language as you go. Ultimately, it took me an embarrassingly long time to get the job done (certainly more than it was worth), and I ended up disassembling a lot more of the game than was necessary (as is often the case when you don't have any idea what you are looking for). I'll just talk about some of the more important lines of investigation, findings, and complications.

As I didn't know anything about the game, naturally the first thing was to hit "step into" and see where I ended up. I always ended up in the same place: a busy loop that checks a single value. Given the nature of this and some idea about the hardware, I reasoned that this was a loop to wait for the next vertical sync, to start on the next frame; this was confirmed by observing that address being written to from the non-maskable interrupt (vsync) handler.

From there I stepped out of the function and took a look around, writing down the various functions called after vsync. I then went about refining the list and detailing more levels of the call tree, ultimately (after all of my disassembly) resulting in the call tree and other related notes below (note the comments have a focus on things relevant to finding this pause glitch). One thing of particular importance is that there's an object-oriented handler for each object type, and the appropriate handler is called for each non-empty object table entry.

$E936 waits for vertical blank to occur
$C971: for each object calls $C8DF, decreases hit timer if nonzero, calls $C9A4, and calls $C928
-$C8DF copies object data from $400+$56 to $46 ($C925 writes life)
-$C9A4 sets hit timer back to full and decreases life in the object buffer when hit with hit timer at 0 after decrement
--$EA3A
--$EB51 saves the object-specific handler to $7A (LE)
--jumps to the object-specific handler at $C9D3
-$C928 copies object data from $46 to $400+$56
$CA4B->$EA3A->$E61B->$E63C/$EB98 unmaps $8DF6 page [the page the object handlers are], which gets mapped by the NMI handler

$EB7E NMI handler (does not branch)
$EB97 IRQ/BRK handler (stub)
$F7: controller 1 state (bits in reverse order)
$F8: controller 2 state (bits in reverse order)

For a while I did some looking around with breakpoints on the location in the object buffer where the life is stored, looking for things that modify it. Some of the information gathered this way:

Copy of object struct for current object: 46
Buffer used to hold 16-bit pointers [LE] from various tables: 7A

$53 [life of the current object] written to directly by $8DF6 in $C9A4 when damage is taken
$8C6B-8C9F, $8DDF-8DFE (inside $8D76) only executed when hit timer is 0
During pause taking hit, $C1E6->$D7A0 returns A0/N+ to $8DD5 on boss 2, but 7F/N- to boss 5

$D7A0 seems to determine whether you get hit during pause. $7E indicates whether you're being hit or not: high bit for hit, lower bits for damage taken.
$7E is written to by $D71A in ($C141->$D711) when hit by boss, $D7B2 to clear hit per frame. $D71A is not reached when paused with boss 5 because $D6CD does not return
$D6CD returns if the current object is hitting the player, throws an "exception" returning to caller of caller if not hitting (returns from $D710)

Eventually I decided to take a more systematic look at the object handler for the catacombs (overhead view) player object:

$8C38->8D98->$8DBF catacombs player object handler paused
-$C15F
-$C0FF->$EF2B sets $3E and $3F to the X and Y coordinates (in pixels on screen) of the player for $D7A0
-$C1E6->$D7A0 returns A0/N+ to $8DD5 on boss 2, but 7F/N- to boss 5, when paused and being hit. A indicates the damage player should take. highest bit of A and the negative flag indicates whether player is hit or not.
-on N+, $C216 then handles hit (including decrease life)
-$93BD
-$EA3A
-$F029
-$E63C

From this we can see that $C1E6 is the switch we're looking for, determining whether the player takes damage; though a look through the function shows a clear lack of anything resembling hit detection - it simply reads from a struct in memory at $7C, generated who knows where. So, if that isn't determined in the player object handler, maybe it was handled in the objects you can be hit by. For that reason, and to satisfy my curiosity a bit about what makes bosses tick, I decided to take a look at a boss handler function; and as I hate the crab boss so much, naturally I went with that, first.

It was about this time that I discovered that NOPing function calls was a very effective way to quickly get an idea what a function is doing. This method works poorly on computers, because of the greater number of registers and drastically greater stack usage, making such NOPs result in crashes more often than not. On the NES (or at least in Blaster Master), however, the method works very well, with crashes very uncommon.

Crab (level 5) boss unpaused object handler ($A6D0):
-$A07B: (no discernible effect)
-$A6DE: handles movement of crab and state transitioning (but not animation)
-$A7A2: spawns bubbles when necessary
--$C1F5: spawns a bubble
-$C0FF: updates crab screen position based on crab 65 position (NOPout fixes crab position where it shouldn't be, despite crab 65 object movement). affects everything onward.
-$C153->$EB51
-for each body segment (right pincer, left pincer, back):
--$C141->$D711: detection of whether player has been hit. detection of player being hit by green sprite is elsewhere.
---$D6CD: checks for collision
--$C216->$DECC (only if hit)
-$C12C: (no discernible effect)
-$C189: draws (animates?) the green sprite
-$C144->$D697: sets player damage if player hits green sprite. also handles things damaging the boss.
--$D6CD: returns on collision (either player hit by something or boss hit by something). eats the stack frame if no collision (returns to caller of caller)
-$9EB3: animates the background layer

Okay, so $D6CD is another function that looks like a good candidate. So, let's take a look and see if it's what we're looking for or another tangentially related function (don't blame me for the formatting, Blogger doesn't like indentations).

$44 = A
$00 = $3E - ($40 / 2)
$01 = $3F - ($41 / 2)
X = 0xF
do
{
A = $7E[X]
if (A > 0)
{
$45 = A
A = $7C[X] - $00
if (A <= $40)
{
A = $7D[X] - $01
if (A <= $41)
return
}
}
X -= 3
} while (X >= 0)

throw

Now that looks like a collision detection function, more or less. We can see the X coordinate, Y coordinate, width, and height of whatever it is we're comparing against at $3E-$41, respectively (this is a case of a memory region being used like a stack frame). We can also see an array of 5 structs containing the X coordinate, Y coordinate, and a thingy, respectively, starting at $7C. Clearly only the size of the "current" object is considered, and the array of thingies are just points.

Well, let's think about it for a minute. We know that this function is called 4 times for the crab boss, for the 4 different parts of the body (and that one of those is not like the others). What might collide with the boss that would be of interest? Well, the player and the player's projectiles. A bit of playing around proved this to be true: the first entry in the array is the player, the rest are the player's projectiles (limited to 4, as you can see). That third byte in the struct array indicates the amount of damage the projectile does (or 7F for the player).

So, now we have everything we need to figure out how this works. The boss object checks for collisions with the player and the player's projectiles. If it hits the former, it marks the player for damage, which is then applied by the player object handler (presumably next frame, since the player handler always gets executed before enemy handlers); if it's the latter, the boss takes damage, though only if the part hit is the green sprite, which is the hit box.

Now that we know how the collision detection and damage system works, and why bosses that are susceptible to being hit while paused also themselves can hit you while paused (the collision detection for both is one in the same); that just leaves the question of why it only operates on some bosses. Well, it was about here that I discovered that that wasn't actually true. While only some bosses can be hit (and hit you) while paused, this is not the case for projectiles. Specifically, the projectiles fired by boss 3 and boss 8-1 can hit you while paused, even though the boss cannot be hit while paused.

Well, it turns out there are two sets of object-specific handlers, one for when the game is running, one for when it's paused. Now, bullets and other things are generally not prone to the problem of dealing damage while paused, as they disappear as soon as they hit something (e.g. the bubbles spewed by the crab boss). The things that can hit you while paused appear to be exactly those objects that have pause handlers and that don't disappear after hitting you; this is the case with all susceptible bosses, plus the projectiles of bosses 3 and 8-1.

Boss object handlers:
1 (63): base $A58A, paused stub
2 (5F): $9B64
3 (61): $A196, paused stub
4 (5D): $970C
5 (65): $A6CD, paused stub
6 (5F): $9B64
7 (5D): $970C
8-1 (67): $AA34, paused stub
8-2 (69): $AC84, paused stub

While I didn't go searching for every single object handler to compare the paused and non-paused versions, I did compile a list of the ones for the bosses. Note that there is only actually a single table of handlers in memory; the address in the table points to the paused handler, while the unpaused handler is always 3 bytes afterward (3 bytes is the size of a JMP instruction). For the bosses not prone to this glitch, you can see that I've indicated the pause handler is a stub that returns immediately. For the rest, the pause handler jumps midway into the unpaused handler (after things like movement).

To illustrate this, take a look at the handler for boss 2 ($9B67):

-$A07B: (no discernible effect)
-$C01E: handles movement of boss
-if time to spawn next projectile:
--$C1F5->$D851: fork projectile from boss, giving it a new proto-object type
--$C216
-paused handler jumps directly to here
-$C0FF
-$9D77: draw and do hit detection for arms
-$C090->$D770: do hit detection for back (not hit box)
--$D711: hit detection
-$C093: do hit detection for hit box
-$9EB3: moves and animates the background

So, that's how it is. Now we know why it happens and why it only affects some things. That just leaves one more question: is it a bug or a feature? Unfortunately, the evidence is much too ambiguous to answer that clearly. While it's within the bounds of imagination that damaging the boss during pause could have been intentionally put in as a cheat of sorts, it's very hard to imagine that the same thing against the player would be intended.

Yet it's also hard to imagine that it could be a bug; while the player being hit during pause could be eliminated by a single change to the player handler (a single mistake, in other words), doing the same for bosses would require that every boss's handler be changed. Furthermore, there's the fact that only 2 of the 5 unique boss object handlers (2 of them are used for 2 bosses each, bringing the total to 9 bosses) have pause handlers, in contrast to the player and most projectiles, and without pause handlers the bosses don't even get drawn completely (and what point is there in having a pause that lets you see the boss battle if you can't see the boss?). It seems as though a lot of stuff was left out or in arbitrarily; I have to wonder if there is a deadline lurking in here, somewhere.

Various resources used during reverse-engineering:
Nintendo Entertainment System Documentation
6502 Instruction Summary
How NES Graphics Work
Comprehensive NES Mapper Document
For more info, see this big list of documents

& Very Old Things - Part 2

2009-08-29T14:18:00.000-07:00

As for the hacking itself, this started out with simple stuff. Search memory, find special values (life, lives, gun power, boss items, etc.), and overwrite them. This was quite easy with an emulator that has a cheat search feature; you simply have it save the memory contents at the initial state, the repeatedly perform searches based on specified criteria until you've narrowed it down to 1 or a small number of possibilities. For example, finding player health was a trivial matter of searching for something that decreases each time you take damage and stays the same in between damage.

With the exception of the boss items, all of the others in this list were similarly easy to find. Boss items, however, were a bit more complicated. Because you only get the items after beating a boss, naturally this is a situation where there are likely to be a lot of changes all over RAM, as it's a major transition in the gameplay; this means that you can't narrow it down as easily. I had to try several locations, starting with the ones whose values made them the most probable to be correct (specifically ones that had a bit flipped on when the item was picked up).

However, there was one other complication figuring that one out: boss items are represented by two separate bit masks that are partially redundant. I first discovered the mask at 3FC, because that's the one that changes the bullet your tank fires after you get the first boss item; as it was a visual change, it was very easy to see that it was working. Once I found that, I checked to see if it was a bit flag, and confirmed it was, finding the flags for the second and third boss items by experimentation.

That's where things got weird. While this mask contained flags for boss items, the flags for the other boss items didn't seem to actually do anything. As well, while having the hover bit flag set caused hover power to be displayed (it's hidden prior to getting the third boss item), you couldn't actual hover. The bits here also did not make the upgrades show up on the pause screen. So, I went on, with my infinite life and gun power, and killed a few more bosses (somehow I still remember most of the maps of this game).

I found that there was a second bit mask with a completely different set of flags, one for each of the 7 items in the game. For the first 2 items, these flags did nothing more than make the item show up in the pause screen. For the third item (hover) this flag allowed you to hover, but did not show the hover power bar or allow you to accumulate hover power (so you still couldn't actually fly with this flag alone). I still can't imagine why it was done this way, but at least I figured out all the flags.

One thing that I couldn't figure out with cheat searches, however, was boss life. That is, I found it - repeatedly: it was in a different place every time (including even for the same boss). I correctly reasoned that this implied that the boss's life was not a special value, but that bosses were simply common entries in the list of objects in the game. As it turns out, so is the player; you just don't notice that because the player is always at index 0 in the object array and thus always at address 0x400, while the boss was stuck in whatever slot was available at the time. This led directly to the discovery of the object array itself. From there, I started looking at the struct that represented each object, beginning with offset 0xD: life.

As I've already pointed out that you tend to have to get clever when coding on a system with so little RAM, it shouldn't be surprising that maps are stored in a similarly clever way. As far as I can tell, there is only a single map for each area in the game (8 areas), which is 128x256 or less. However, the map is diced up and jam-packed in there such that they need to do some camera tricks when transitioning between areas (teleporting through some doors) to make sure you never see other sections that are contiguous in memory.

While I was working on it, I figured I should try to answer some long-standing questions about Blaster Master. To begin with, why does the power of your gun (what it actually shoots) not always match the gun power that's displayed? For example, if you have full gun (8 bars) and get hit, you take 1 bar of damage, but the effect of your gun falls beneath what 7 bars should give you. Many years ago I hypothesized that there were two variables for gun power; one was the one displayed, and one that was the actual effect: getting hit did a bit more damage to effect than the display.

It turned out to be simpler than that. It's a consequence of the fact that while most hits (I can't think of any counterexamples) do an integral number of bars of damage, life, gun, and hover are stored from 0-FF, in bytes. See where this is going? One bar = 20, but 8 bars = FF, not 100. In other words, the number of bars displayed is (x + 1) / 20. When you get full gun and then take a hit, your gun drops to DF; while this still displays as 7 bars, it doesn't give you the maximum gun effect (which requires E0). It's not clear whether this is a bug or a feature, though I'm kind of leaning toward a bug (specifically, an edge case the coders didn't think of, which could be easily solved).

All numbers are in hex.

Continues: 37E
Lives: DD
Gun: C3
Hover: 92
Bosses killed: 3FB. bit x = boss x+1
Boss items 1: 3FC. same values as 3FB.
Boss items 2: 99. bit 0: hover, 1: dive, 2: wall 1, 3: wall 2, 4: crusher, 5: key, 6: hyper
Homing Missiles: 6F0
Lightning: 6F1
Thunderhead Missiles: 6F2
Pause: 15

Gun Levels:
20: 2 long shots
40: 3 long shots
80: circling shots
C0: white wave shots
E0: full wave shots

Beginning of Object Table: 400. 12 slots. Slot 0 is reserved for the player. Slots 1-4 are reserved for projectiles. Enemies fill slots 5-11 as needed.

Object Struct (14 bytes)
byte @0: Object type. A few of the known object types:
3: Normal
4: Dying
5: On left wall
6: On right wall
7: On ceiling
8: Diving
9: Climbing H->V convex
A: Climbing V->H convex
B: Climbing horizontal->vertical concave
C: Climbing V->H concave
D/E/F 10/11/12: Entering/transitioning/leaving door right/left
1B: Outside tank
1D: Entering tank
84/85/86: Entering/transitioning/leaving door catacombs

byte @1: Orientation. The exact meaning of this seems to vary by object type.
Tank mode: Between 0 for left and F for right (the intermediates indicate that the tank is changing face), with the high bit set if the tank is pointing to the left
Catacombs mode: 0 for up, 1 for right, 2 for down, etc.
uint16 [LE] @2: Horizontal position. The high byte indicates the attribute-size tile, while the bottom byte is the position within that tile. The highest bit indicates that you're currently moving through a teleporting door.
uint16 [LE] @4: Vertical position
byte @6: X velocity
byte @7: Y velocity
byte @8: Attribute-size tile index on screen? This was always observed to be (Y * 0x11) + X where X and Y are relative to the tiles visible on screen.
byte @9: Hit timer: the number of ticks until the object can be hit again. Controls invulnerability, damage flashing, and also decreases gun by 1 for each tick above 1 (this causes gun power to drop smoothly rather than suddenly, though I'm not sure why they did it this way; life does not do this when damage is taken).
byte @A: Current AI state
byte @B: Frames till AI state change
byte @C: ?? (no observed effect)
byte @D: Life. For trivia value, normal tank shot does 4, hyper shot does 6, crusher shot does 8, normal catacomb shot does 1, catacomb shot with wave gun does 2, and grenades do 2.

Note that the AI state bytes in the struct are for simple enemies. Bosses have other state stored elsewhere. For example, in the above crab boss, the AI state and timer control movement but not spraying bubbles, which occurs entirely independently. The density of bubble spray, however, was directly controlled by the life of the boss; e.g. below 0x20 life (it starts with 50) it does the full sawtooth volley with dozens of bubbles.

The Story of ThunderGraft

2009-08-26T15:24:00.000-07:00

For those who aren't familiar with it, ThunderGraft was possibly the coolest of the three modding tools I released (the other two being MoPaQ 2000 and MPQDraft). Diablo, Diablo II, Starcraft, and Warcraft II: BNE all use PCM WAV audio (22khz 16-bit if I recall correctly) for their sound effects and music. Diablo used raw PCM WAV audio, while Starcraft introduced (and the other two used) a special "WAV compression", which compressed the audio in lossy ADPCM form, resulting in a compression ratio between 3:1 and 4:1 (though at the cost of audio quality); WAV compression, however, was implemented transparently in the MPQ API - the games saw what they read and wrote to the MPQs as simply PCM, and that's all the audio streaming API was capable of playing (in other words, the audio streaming functions were identical in all four games).

ThunderGraft was a utility that added the ability for all four of these games to play MP3s and Ogg Vorbis, in addition to standard PCM WAVs; even better, it did this in a version-independent way* (the very same ThunderGraft binary worked for all versions of all of those games). Naturally this was huge, especially in the days of dial-up (which was when the modding community first became big). You could use modern audio compression formats that yielded significantly smaller file sizes and higher audio quality compared to WAV compression. Yet ThunderGraft is all but dead now. Why is that?

MPQDraft and ThunderGraft have a few things in common. They're both very simple, clean, version/program independent, and highly effective. The reason is also the same: they both rely on very clean exploits of design to do their thing, without getting into messy exploits of implementation that depend on the precise binary patched. MPQDraft exploited the priority system in the MPQ API; ThunderGraft exploited the fact that the audio streaming API was encapsulated in functions supplied in Storm.dll.

The fact that the functions were entirely contained in Storm meant that I could cleanly capture calls to them and redirect them. For cleanliness, I opted to simply replace the streaming API in its entirety. Anything less would have been version-dependent, as it would have required all sorts of messy code modifications inside Storm's internal functions.

This meant that I needed my own decoding and streaming code to replace Storm's. At the time I just coincidentally happened to have such a thing handy. Specifically, a friend of mine by the moniker Dark_Brood was writing a game engine called Aegis, and happened to have audio decoding/streaming code handy for me to plug into ThunderGraft. He sent me a static library of the code, and in it went. Easy.

Where things took a turn for the worst was when he wrote the next iteration of his game engine. This involved rewriting a whole bunch of stuff, and integrated the various systems in the engine much more tightly (e.g. added garbage collection and other global things). This meant that it was no longer possible to simply extract the audio portion of the engine.

While in theory I could have just continued to use the old version, there was a big problem: I never had the code for the original version, nor did he save a copy after rewriting the code. This is a big problem because static libraries are compiler- and version-dependent. Now the only way I could even compile ThunderGraft was on the very same version the original was compiled on: Visual C++ 6, which is some 11 years old, now, and I haven't even had it installed for many years.

Thus, the only way to resurrect ThunderGraft would be to replace the decoding and streaming system entirely, and thus far I simply haven't managed to muster the effort. After open-sourcing MPQDraft I wanted to do the same with ThunderGraft, but was unable to readily do so for the same reason.

*There is one thing that's version-dependent in ThunderGraft, as there's simply no theoretical way to do it in a version-independent way: importing of non-WAV audio files into maps with StarEdit (the Starcraft map editor). Special support for this was required for several reasons: 1. StarEdit verifies that things imported are WAVs and refuses anything else, 2. it needed to know how long the audio file was in order for triggers to work right. The audio decoding and streaming in ThunderGraft, in contrast, was truly game- and version-independent.

& Very Old Things - Part 1

2009-08-23T21:44:00.000-07:00

Bring back any painful memories?

So, a couple days I had one of those evil, perverted urges I'm so notorious for. Specifically, I felt like doing a bit of hacking of Blaster Master. For those not familiar with it, it was an NES game published 21 years ago. A good one, in fact. But before I talk a bit about anything I did resembling reverse-engineering, let me explain the NES hardware to the best of my knowledge (which consists of what I saw in my hacking, and a bit of stuff I looked up online).

The main CPU of the NES is a modified 6502, the CPU used in various Commodore and Apple computers (not that I ever used one of those). The 6502 is a primitive CISC CPU, and in fact somewhat resembles the x86 (though more primitive). It has 3 8-bit registers: a numeric accumulator (A) and 2 index registers (X and Y). Operations generally operate on the value of A and a memory location or literal, and write the result back to A.

It has a stack, though from what I saw in Blaster Master it seems to be relatively rarely used, used mainly to save registers (though even that was pretty rare). Specifically, I didn't see much in the way of stack frames holding local variables. Functions that require local variables tended to have (dedicated) memory ranges allocated to them to be used as private buffers. For example, one address I initially thought was the boss life location actually turned out to be in a buffer region used by the function while updating objects in the object list. This kind of surprised me, as the NES has only 2 KB of RAM; I imagine this must be forced by the architecture, e.g. a lack of instructions to access the stack at a specific offset.

As for the graphics system. If you ever messed around with text mode and text graphics in DOS, the NES graphics system is similar. At the lowest level, graphics are stored as blocks called patterns. Each pattern is 8x8 pixels, 2 bits each (total of 4 colors). The NES has enough video memory for 512 patterns at a time, stored in 2 pattern tables. What exactly it does with these patterns depends. The NES has 3 graphics layers: 1 for background and 2 for sprites (1 in front of and 1 behind the background layer).

deconstructulator provides an excellent illustration for most of the things discussed here. It shows the pattern tables (note that the top half is the sprite pattern table and the bottom half is the background pattern table) and sprites along with a playable version of Super Mario Bros.; although it does not show the name/attribute tables. Refer to that from here onward.

The background layer (illustration below) is very much like the screen buffer in DOS text mode; it's a buffer of screens composed of 32x30 patterns each (indices into the pattern table), called name tables (lost in translation, perhaps?); all patterns in the background must come from the same pattern table. The NES supports up to 4 screen buffers in this way, though it only contains enough memory for 2 of them (if the cartridge doesn't supply additional memory, the game can simply set the NES to mirror the 2 screens).

However, so far each pixel only has 2 bits of color (the bits in the pattern table). An additional table, called the attribute table, supplies an additional 2 bits to the name tables, increasing the total to 4 bits, or 16 colors (though each tile on screen still has only 4 colors within it). However, the attribute table does not contain a value for every tile. Rather, it only contains 1 two-bit entry for each block of 2x2 entries in the name table (so 16x16 blocks composed of 4 patterns). This is the reason 16x16 blocks appear everywhere in NES games - that's the smallest block that can be fully independently controlled.

The background position is specified independently of the sprites. A horizontal and vertical scroll position is specified by pixel for the background, which indicates where the graphics chip should start drawing the background on screen. This is how smooth scrolling works, although implementing this can be quite a trick, as you have to essentially use the name tables as a ring buffer (even more tricky if you support scrolling in both dimensions).

A shot of the side-scrolling portion of Blaster Master (top) and the corresponding, merged name/attribute tables (bottom). The white lines indicate where the top left of the screen currently is (where the two lines cross). The visual discontinuities are caused by the way the game streams the background into the name/attribute tables on demand, filling in only what's on screen in the frame; they're stale data. The color glitches result when the current color in the attribute table for an entry does not match some of the stale patterns still in that name table for that entry (e.g. on the far left the second column of patterns is discolored because they are stale and the attribute entry now corresponds to the first column of patterns, which is on screen).

The NES supports 64 sprites, each either 1 or 2 patterns in size (8x8 and 8x16, respectively), depending on whether a global flag is set. Analogous to the attribute table, each sprite contains the 2 high bits of color (though still that allows only 4 colors per sprite). Other info each sprite possesses includes position (obviously), mirroring parameters, and whether the sprite is in the foreground or background. However, even if you can have 64 sprites, the NES only supports 8 sprites per scan line; if there is more than that, only the 8 with the highest priority are drawn (smart games can cycle through their sprites each frame, but that results in flicker).

There are, however, some tricks that can be done to circumvent some of the innate limitations (e.g. 16 colors, 16x16 blocks, 64 sprites, etc.). These often involve clever but perverse tricks related to swapping out the various things such as scroll offset or sprite data while drawing is underway. One common use of this is to draw part of the screen (the gameplay) with scrolling, while a portion of the screen on top or bottom is fixed (the score area). This can also be used to draw more than 64 sprites per frame, though there's still a limitation of only 8 sprites per scan line.

Blaster Master and others frequently use the background as a grotesque way to draw very large sprites. In the above screen shot, the boss crab is actually the background, while the bubbles, player, and energy bars are sprites (the green areas of the boss are actually sprites, as well). The crab has a couple frames of animation; each of these is on a separate screen in the name table, and every frame the scrolling position is modified. This results in the crab moving around the screen and animating, as if it were a huge sprite.

Oh, and in case you were wondering, yes, this boss frequently exceeds the 8 sprites per scan line limit (that would be 4 bubbles), resulting in the game slowing down to draw them all.

& Summer 2009 Anime Music

2009-08-06T14:46:00.000-07:00

As with last season, I was again inspired to post theme songs that I like of current anime series. As with last season, one show's music in particular provided this inspiration - Umineko no Naku Koro ni [When the Seagulls Cry].

Umineko no Naku Koro ni really walked away with the title of best theme music of the season, between the music not being bad, and the lack of any high-caliber competition. The opening especially appeals to me because one of the musical themes I go for is modern compositions/melodies in symphonic/operatic style. The ending I suppose would be classified as fun, in rock opera style with a singer that has the perfect voice to perform the the creepy insane rambling lyrics.

Opening theme: Katayoku no Tori [One-Winged Bird]

Ending theme: La Divina Tragedia

Perhaps given the lack of serious competition I may have lowered the threshold for inclusion in this post, I dunno. Anyway, next up is Kara no Kyoukai [Boundary of Emptiness]: Garden of Sinners: Oblivion Recorder. Kara no Kyoukai is a series of movies that form a single plot line. While some of the themes are shared between all of the movies, some are unique to the movie (in this case the one that just came out a couple weeks ago).

As you can see, the video was replaced with the logo of the movie. Note that I set it to start at 0:42, which is where the theme for this movie starts. The music before 0:42 and after 4:18 is from the main theme of Kara no Kyoukai, which I think it pretty bland.

Ending theme: fairy tale

The rest all fall under the category of fun/cute. Bakemonogatari [translated by some as GhoStory, which preserves the pun] has a pretty fun ending theme with a bit of cuteness. The video of the credits seems to have been replaced with a still of the picture that's in the background during the credits.

Ending theme: Kimi no Shiranai Monogatari [Your Strange Story]

Yoku Wakaru Gendai Mahou [Comprehensible Modern Magic] has a somewhat peculiar ending theme. Like the animation during the credits (which you just know is going to get made into animated GIFs), the music is overly cute, yet strangely catchy (although I can imagine it would make some people want to kill things).

Ending theme: Made in Wonder

Finally, Hayate no Gotoku!! [Like the Wind; this is a pun on the main character's name being Hayate]; first of all, note that the sound on this video is LOUD, so you might want to turn your volume down. This one really crosses the line from cute into obnoxious. While the melody is nice and fun, the "cute" accompaniment makes me want to smash things.

I can only figure that the producer of this series is an absolute copyright Nazi, because despite quite a bit of looking I can't find a single video of this ending theme with the credits animation, which is unfortunate, because that would show you who the infernal peanut gallery is. Instead, I found this video, and I really don't know where it came from. It's called a preview, but as I only saw one copy of it, I'm thinking maybe it's a fan-created anime music video. In either case, it seemed better than the large number of others, which simply played the music to some picture (the album cover, a picture of the character singing, etc.).

Ending theme: Mankai Watashi Iro [something along the lines of My Full Bloom Form]

Introduction to Anime

2009-08-03T18:13:00.000-07:00

As the amount I'm blogging has been decreasing for a while now, I'm noticing that the proportion I talk about anime is increasing significantly. For a while now I've listed the series I'm currently watching on the sidebar, and occasionally written anime-related posts (especially lately). This is all well and good if you're an anime watcher, and know basic things like how to find and download anime, but not so useful for people who don't know anything about anime (which are probably the majority of readers).

So, I thought I should provide a very brief introduction. "Anime" is a nontechnical term for Japanese animation. Usually what we call cartoons are intended primarily for children, while anime has no such limitation; this frees anime up to represent just about anything you can come up with, including the more serious types of things that appear here in (filmed) movies and television. Apart from that, anime is vaguely defined by the Japanese cultural themes present in it, which may give it a different feel than our cartoons, movies, or TV shows. One theme that's conspicuously absent in anime is the strong bias to have fictional stories take place in something resembling the real world, resulting in a lot more variation in setting and less adherence to realism in anime than in our movies/TV.

Okay, that wasn't as brief as I was hoping for. Next topic: where to check out anime, if you haven't seen it before (or if you've only seen cartoony children's anime). Specifically, the rest of this post is a listing of free, legal anime series available for streaming online. Generally the quality of streamed episodes isn't near as good as episodes you download, but it has the advantage of allowing you to watching instantly without having to download hundreds of megs in advance (not to mention that I don't know of any free, fully legal sources of downloadable high).

How this works is that I've essentially gone through all the streaming sites I know and made a list of all the series I've seen (or at least the ones that didn't suck so bad I'm not even willing to admit to watching them) and their genres. I threw in a couple series (marked with a *) that I haven't seen, simply because they're phenomenally popular and no list of anime would be complete without them. As anime dubs are often almost as bad as Japanese actors trying to speak English (occasionally seen in anime), I've only included links to dubbed series (marked with D) when there is no alternate subbed version available.

The genres listed are (supposedly) in order from most to least meaningful, but are all off the top of my head; as I haven't seen some of these series in many years (and some not at all), accuracy is not guaranteed (and of course it's always possible that I might simply have mislabeled something on accident). I've defined "fantasy" pretty broadly, so as to include stuff outside the typical Lord of the Rings type story (e.g. I include supernatural). "Slice of life" refers to series centered around the daily lives and activities of the main characters (most commonly school), where the activities usually resemble the life of the intended watcher to some extent. Here I use "fighting" in contrast with "action", where the former refers to things that are substantially composed of a progressive series of fights between the protagonists and antagonists (usually duels, often with named attacks, etc.), while the latter often has more general battle scenes (such as shoot-outs).

The ones I liked most, and would most recommend:
CODE GEASS Lelouch of the Rebellion. Drama, comedy, mecha, action. Note that while I and a large number of others liked it a lot, it's pretty hit or miss with people, so your mileage may vary.
Death Note. Drama, mystery, supernatural
Durarara!!. Fantasy, drama, action
Full Metal Panic! Comedy, military, action, mecha
Full Metal Panic? Fumoffu [sequel]
Fullmetal Alchemist: Brotherhood. Drama, fantasy, fighting, military
Gunslinger Girl. Action, drama
Gunslinger Girl: Il Teatrino [sequel]. Action, drama
Higurashi - When They Cry. Mystery, horror, comedy, drama, ecchi (D)
Hikaru no Go. Gaming, comedy, drama
Kannagi. Comedy, supernatural, slice of life
Last Exile. Scifi/fantasy, drama, action
The Melancholy of Haruhi Suzumiya. Comedy, parody
Mushi-shi. Supernatural, drama (D)
Noir. Action, drama
School Rumble. Comedy, slice of life, romance (D)
Spice and Wolf (both seasons). Fantasy, medieval, slice of life, comedy

The rest I've seen:
5 Centimeters per Second. Drama
11 Eyes. Fantasy, fighting, drama, ecchi
Air. Romance, fantasy, tragedy
Asura Cryin. Scifi/fantasy, fighting, mecha, drama
Aria the Scarlet Ammo. Action, comedy
Baka and Test - Summon the Beasts. Comedy, fantasy/scifi, fighting, ecchi
Bamboo Blade. Martial arts, slice of life, comedy
Beck: Mongolian Chop Squad. Music, drama
Black Butler. Supernatural, comedy, action
Black Butler II [sequel]
Bleach. Fighting, supernatural, comedy
Book of Bantorra. Fantasy, action
A Bridge to the Starry Sky. Romance, comedy, ecchi
Busou Renkin. Fighting, fantasy, comedy
C. Drama, fighting, fantasy
Canaan. Action, military
Chrome Shelled Regios. Sci-fi/fantasy, military, action
Claymore. Fighting, fantasy
Cross Game. Sports, comedy, slice of life
D.Gray-Man. Fighting, supernatural, comedy
Dance in the Vampire Bund. Fantasy, drama, action, ecchi
Darker than Black. Fighting, fantasy/scifi
Deadman Wonderland. Drama, action
Dragon Crisis. Fantasy, action, comedy
Eden of the East. Drama, romance, scifi
Erin. Fantasy, slice of life, drama
Fortune Arterial. Slice of life, supernatural, romance
Full Metal Panic! The Second Raid [sequel]
Fullmetal Alchemist [alternate]
Fractale. Sci-fi, drama, action
Fruits Basket. Fantasy, slice of life, comedy (D)
Ghost Hunt. Supernatural, horror, drama, mystery
Ghost Hound. Supernatural, mystery, psychological
Golgo 13. Action
Gosick. Mystery
Gundam 00. Scifi, mecha, action, drama*
Gurren Lagann. Mecha, scifi, action, comedy (D)
Hanasaku Iroha. Slice of life, drama, comedy
Hayate no Gotoku! Comedy, parody, fighting
Hayate no Gotoku!! [sequel]
His and Her Circumstances. Slice of life, comedy, romance
Honey and Clover. Drama, slice of life
Hyakko. Comedy, slice of life
InuYasha. Fantasy, drama, comedy, fighting
InuYasha: The Final Act [sequel]
Kanon. Slice of life, romance, comedy
Kaze no Stigma. Fantasy, fighting, comedy
Kimikiss: Pure Rouge #. Slice of life, romance
Kino's Journey #. Fantasy, philosophy
Kore wa Zombie Desu ka. Fantasy, comedy, action, ecchi
Kurokami The Animation. Fighting, martial arts, drama
The Legend of the Legendary Heroes. Fantasy, comedy, action
Lucky Star. Comedy, parody, slice of life
Maria Holic. Comedy
Monster. Drama, horror (D)
Moon Phase. Supernatural, fighting, comedy, romance
My Bride Is a Mermaid. Comedy, fantasy, parody, ecchi
My Ordinary Life. Comedy, slice of life
Myself Yourself. Comedy, slice of life, romance
Naruto. Fighting, martial arts, drama, fantasy, comedy*
Naruto Shippuden [sequel]*
NATSU NO ARASHI! Comedy, supernatural
Negima! Fantasy, comedy, ecchi, fighting,
Nogizaka Haruka no Himitsu. Comedy, romance, ecchi
Occult Academy. Supernatural, scifi, mystery, action, comedy
Okamisan. Comedy, slice of life, parody
One Piece. Comedy, action, fantasy*
Oreimo. Comedy, parody
Otome Yokai Zakuro. Supernatural, comedy, romance
Pandora Hearts. Fantasy, comedy, action
Pani Poni Dash. Comedy, school life, parody
Princess Jellyfish. Comedy
Pumpkin Scissors. Military, drama, comedy, action (D)
Rideback. Mecha, drama, military
R.O.D. The TV. Fantasy/scifi, action
Rumbling Hearts. Drama, comedy, ecchi
Sacred Blacksmith. Fantasy, action, comedy, ecchi
Saki. Gaming, drama, comedy
Samurai X [AKA Rurouni Kenshin]. Martial arts, fighting, comedy, drama (D)
Sasameki Koto. Comedy, slice of life
Seitokai no Ichizon - Student Council's Discretion. Comedy, parody
Shana. Fighting, supernatural, comedy (D)
Shigofumi: Letters from the Departed #. Drama, supernatural, psychological
Shiki. Mystery, horror, fantasy
SHANGRI-LA. Drama, scifi, action
SKET Dance. Comedy, action
Sketchbook. Comedy, slice of life
Skip Beat! Drama, comedy, romance
Slayers. Fantasy, fighting, drama (D)
Slayers NEXT [sequel] (D)
Slayers Revolution [sequel]
Slayers Evolution-R [sequel]
Sora no Woto. Slice of life, military, comedy
Special A #. Comedy, slice of life, romance
Squid Girl. Comedy
STEINS;GATE. Scifi, drama
Strain: Strategic Armored Infantry. Action, scifi, mecha, drama
Tears to Tiara. Fantasy, drama, action
Tegami Bachi: Letter Bee. Fantasy, action
Trigun. Action, comedy, scifi
Vampire Knight. Supernatural, drama
Vandread. Scifi, mecha, comedy, ecchi, action
Welcome to the NHK. Comedy, drama, psychological (D)
White Album. Drama, romance
The World Only God Knows. Supernatural, school life, comedy, romance
xxxHolic ['xxx' seems to refer to the supernatural, here]. Supernatural, drama (D)

Finally, the list of noteworthy free, legal anime sites, listed from largest selection to smallest:
Anime News Network
Crunchyroll
Hulu
Funimation
Joost

& Summer 2009 Thoughts

2009-07-27T20:25:00.000-07:00

So, we're now several episodes into the summer 2009 anime season. I've been meaning to write mini-reviews of new series for a few seasons, now, but never got around to it; we'll see if I actually make it to the end of (writing) this post, this time.

First of all, I always get my first looks at new series from Random Curiosity's season previews. and I'll probably end up quoting some of their descriptions here (and go in the order they're listed in the preview). With the exception of one, all the ones I'm going to list here piqued my interest at least enough to give them a shot (at least the first episode).

Charger Girl Ju-den Chan [that's the official English name on CrunchyRoll; it's listed as Fight Ippatsu! Juuden-chan!! on the preview]

Preview says:

Let me start by saying that I’m not convinced that this series is anything other than a vehicle for fanservice and nudity. Originally by the author of Mahoromatic and KissXsis, Juuden-chan is a story about a clumsy girl whose job it is to inject energy into people who are depressed. If that doesn’t tip you off on what kind of series this’ll be, then maybe a visit to the official site where you can remove some of the main character’s clothing will. And then there’s the promo video (see below) that’s got the main character orgasming during a transformation sequence.

Verdict: who could say no to that? Me, for one.

Umineko no Naku Koro ni [When the Seagulls Cry]
Genre: mystery, drama, psychological
"Sequel" to Higurashi no Naku Koro ni [When the Cicadas Cry], another mystery murder series, about a rich family getting together to hash out the details of their inheritance after the patriarch dies. From there things quickly go downhill, as six people are murdered on the first night.

Higurashi, as I mentioned, was quite a strange series. I didn't particularly like the characters, nor did I like some of the excessively slapstick comedy [OMGWTF @ Higurashi Rei 1], but it had an awesome and intelligent high-level story, and it was told very well. As such, I liked Higurashi as a whole, and I've been waiting for Umineko ever since I heard about it (it was originally a game, like the Higurashi series). So far it seems to be more drama than comedy, although there's also been some of that.

By the way, I hear that the Higurashi games have just been licensed, and will be released in English pretty soon.
Verdict: definitely watching

Taishou Yakyuu Musume [Taishou Baseball Girls]
Genre: slice of life, comedy

High school girls forming a baseball team in the early 1900s. I was/am pretty wary about this one. I've seen entirely too many (which is to say a few) "cute girls do (often boy) things in cute ways" series that rely on girls being cute as the primary attraction (a genre I've named Shoukawa). E.g. while I did watch and enjoy "the definition of moe" K-ON! (girls forming a rock band) last season, it really had entirely too much moe, and I would have liked it more if it had less.

There was, however, a shred of hope with this series. Japan is in some ways even more conservative than the US, so it would be unheard of for there to be a girls' baseball team in that time (e.g. how in the first episode one girl refers to baseball as "that thing boys do"). If they could create a realistic depiction of the cultural and social clash of something like this (as opposed to simply saying "Here's some cute girls doing funny things! Watch!"), that could be interesting enough to justify watching it. So I decided to take a look and see.

Well, thus far only the first episode has been translated by a decent group, so that's all I have to go on. It wasn't bad, to sum up in a couple words. There were indeed signs of exploiting moe, but there were also signs of interesting cultural material - enough to keep my hopes alive, for the moment. I'll know more after a couple more episodes.
Verdict: still watching

Two of the girls (the rest all ran away immediately) on a field trip to watch boys play baseball, after seeing the batter nail the pitcher in the head with the ball.

Bakemonogatari [I'm told this is wordplay on 'bakemo monogatari', which would be something like Supernatural Story]
Genre: supernatural/mythology, comedy, randomness

This one I hadn't really planned to watch, though I decided to take a look after some of the WTF stuff in the first episode summary on Random Curiosity (the girl stapling the guy's cheek comes readily to mind). It's a rather weird story about a guy who encounters a number of supernatural phenomena in his daily life; in the past he himself had been a vampire, and in the time of the series he encounters a number of girls with various supernatural problems. Sounds like a dating sim adaptation to me (which was part of why I didn't initially intend to watch it), though I really hope that's not the case, as the second girl has to be in elementary school.
Verdict: still watching. I don't know if I'd say it's good; but I really hate to drop series after I've watched a few episodes, and it hasn't been bad enough to do that. It really doesn't help that it's by SHAFT, who I rather dislike; they can certainly draw pretty pictures (as you can see in the summary), but they have an incredibly distinctive artistic style that I find quite disorienting and relatively difficult to follow.

Girl #1. She can probably kill you with each of those.

Canaan [main character's name]
Genre: action, drama, fighting

Another series about an inhumanly good gunfighter girl with underworld dealings, lots of action and gunfights, and something about bio-terrorism. It sure sounds (and looks, thus far) like its girls-with-guns predecessors Noir and Madlax, though as far as I can tell it's not by any of the same people. As a matter of fact, it's an adaptation of a video game, so I suppose the fact that it seems pretty decent to even people who haven't played the game is noteworthy.
Verdict: pretty decent

Kanamemo [not too sure about this one; Kana could be the main character's name, but the only thing I could think of for "memo" is some misapplication of the English word to refer to newspapers]
Genre: comedy, slice of life

Story of an orphan girl who gets hired to work and live at a newspaper delivery place, and her daily life. That was enough to make me take a look, as slice of life comedies are one of the things I'm most into. While it's always possible I'm not giving it enough of a chance, the one episode I saw lead me to believe it was merely the sum of it's parts, as listed by AniDB (categories): coming of age, large breasts, lolicon [pedophilic], shoujo ai [lesbian], small breasts.
Verdict: taking my ball and going home. Perhaps if I'm ever desperate for something to watch I might see if the second episode was like the first; but not any time soon.

Sora no Manimani [Following the Sky? This is a really tricky name to crack, for somebody with limited knowledge of Japanese]
Genre: comedy, slice of life, romance

Another slice of life comedy, this time about a small astronomy club at a high school. Of course this one also caught my attention for something to at least check out. Out of the first two episodes it seems pretty average, as far as slice of life comedies go, though it's difficult to come up with something more cliche in anime than the harem [multiple girls that all like the male main character]. This will probably end up in the slot of "something to watch when I'm out of better stuff to watch".
Verdict: better than nothing

Spice and Wolf II
Genre: drama, comedy, romance, medieval slice of life

Based on a series of novels, this series is about a traveling merchant in the middle ages and his (sage wolf god) traveling companion. This is one of those series that features more mature topics than most, such as economics and politics. I liked the first season of it a couple years ago, and I've been looking forward to a second season ever since. If you're looking for something outside the ordinary anime, this is one to consider.
Verdict: good

Wolf and hangover. In case anybody is wondering, these are all pictures I took while watching the series, not ones taken specifically for this post.

Yoku Wakaru Gendai Mahou [something like Modern Day Magic to Be Well Learned]
Genre: comedy, fantasy

In this world, like in Serial Experiments Lain, reality is fundamentally composed of information, and like data in a computer this information can be altered; this is the nature of magic. I thought that creative take on magic was interesting enough to warrant checking out. Unfortunately, the first two episodes lead me to believe that an interesting premise is all this show has going for it, and in general it appears to be a dud; and with an average rating of 6.4 out of 10, it seems like a lot of people concur.
Verdict: on life support. If I'm feeling generous, I might watch the third episode (next week) and see if it manages to improves any.

& That Memory Leak

2009-07-26T14:00:00.000-07:00

I'm pretty sure that a while back I mentioned a particular Firefox plugin called Feed Sidebar. It's a nice little RSS feed plugin that does exactly what I wanted an RSS plugin to do (and all others work differently). As such, I'm rather fond of it, and have been rather tolerant of its faults.

The particular fault I believe I discussed was that it leaked memory. With the ~15 RSS feeds I have on it set to update every 10 minutes, it leaked about 20 megs of memory per hour. While many would probably not find this to be a serious problem (e.g. 8 hours x 20 megs/hour = 160 megs leaked before shutting down for the day), as I tend to leave my computer running for weeks straight, this was a moderate annoyance. Left on its own, Firefox would crash about every three days due to address space exhaustion (32-bit applications have a 2 gig address space, and fragmentation can reduce the amount actually allocatable below that; I was seeing it crash around 1.5 gigs). Much more frequently, I'd start World of Warcraft and my computer would grind to a halt, as Windows really, really doesn't like it when you get > 90% memory usage (up until a month or two ago, when I have 4 gigs of RAM), and I'd have to manually restart Firefox at that point.

On one occasion I e-mailed the author about the problem; he said that he'd been looking for the leak for a while, and was stumped. Unfortunately, as I haven't done anything with Javascript (what Firefox plugins are written in) in over a decade, and I don't know the first thing about the Firefox plugin architecture, I couldn't go looking for the problem myself as I've done so many times in the past (at least 3 or 4 incidents on the blog).

However, a couple weeks ago the problem suddenly become much worse. Immediately after installing Firefox 3.5, I noticed that it was now hemorrhaging about 150 megs/hour, more than seven times as fast as in 3.0 and earlier (in fact, at first I thought it was that 3.5 was just unstable, as it crashed about every day; then I noticed that it was allocating massive amounts of memory). After verifying both that this was consistent/reproducible and that this was indeed due to the particular addon, I e-mailed the author again, with my new data.

Apparently that got a pretty quick response. A couple days later he sent me a test build he wanted me to try. After some looking, he'd come to believe that there was a bug in Firefox that was leaking SQLite resources; resources that should have been freed when an SQLite connection was closed were being leaked (it was not clear from his e-mail whether this was a new bug with 3.5, or just that the quantity of resources leaked was greater in 3.5). This test build included a workaround for it (presumably he saved the connection instead of creating a new connection every time it updates the RSS feeds, but he didn't say).

This seemed to work well. After installing it, I immediately noticed that it was not hemorrhaging memory like it did before (previously it was leaking about 25 megs each time the RSS feeds were updated, which was now gone). Rather, after a couple of days of collecting data, I concluded that it was now only leaking 1-2 megs each update (about 10 megs/hour).

It's not clear yet whether this is true leakage (which would suggest that one leak was plugged but another remains) or that this is a side-effect of the workaround. It's conceivable that Firefox might delay freeing SQLite resources as long as a connection is in use; if he's indeed keeping an SQLite connection open the whole time, we could imagine that this "leak" is not a leak (lack of resource reclamation) so much as a deferral of resource reclamation. If this is the case, this should go away after Firefox fixes the SQLite connection leak and he goes back to creating a new connection on every update.

We'll see.

Incidentally, version 4.1 of Feed Sidebar was released today; this is the version I tried a test build of. After I've had more time to collect data I'll have to see if it's leaking the same amount as the test build, or if there have been further modifications.

Useful Fact of the Day

2009-07-24T12:43:00.000-07:00

As of a few versions, you can no longer get the nice graphical Visual Studio profiler in anything less than the most expensive Team Suite edition of Visual Studio. For most people (namely, those that don't have 6 grand to spend to get a profiler), this isn't really an option.

Fortunately, Microsoft has been kind enough to release a command-line version of the Visual Studio 2008 profiler for free. If you need a profiler, get it. Fortunately for me, I got Visual Studio 2005 and 2008 Team Suites for free through my school via Microsoft Developer Network Academic Alliance; unfortunately, I won't be able to do that with Visual Studio 2010, so hopefully they'll make the 2010 profiler available that way as well.

RIP E Terra Blog

2009-07-23T19:08:00.000-07:00

As you can see, I've removed the link and RSS feed for the E Terra blog from the sidebar. After several years of no real content and over a year since the last post (that's even worse than this blog!), I'm finally putting it out of its misery. If I'd been a prolific writer on the development of E Terra there might have been a purpose to a separate blog, but I sure haven't been, once the class I had to create it for ended. If I have anything to say about E Terra or game programming in the future, I'll just put it here, instead.

By the way, a few semesters ago (after the class I wrote E Terra for) I got a very nice book: 3D Game Engine Design (second edition). It's largely about graphics engines, though it does have occasional other topics (e.g. that's where I learned to write a good collision detection system for E Terra). What's really nice about this book is that it's not limited to theory; while it does explain the theory behind things, it also shows how to bring everything together into a working system. Most (useless) textbooks, in contrast, simply explain the theory and (if you're lucky) give you pseudocode for each separate concept, with no advice on how to integrate everything into a complete system. If you're interested in game programming, this is by far the best book I know of (I originally found it looking through the book shelves of my graphics teacher).

& Detexify

2009-07-15T17:51:00.000-07:00

So, somebody just linked me to Detexify, a very neat little program that reads your "handwriting" and tries to find the TeX special character that you just wrote.

Now, personally I don't have much use for such a thing, as I don't use TeX. However, it happens to be open source, which means that if I can muster the energy I'm going to try it with the set of Chinese characters and see how well it can do identifying those. If it can do that decently I have some much less theoretical uses for it...

& the Genitive

2009-07-15T15:51:00.000-07:00

Last in the series of core cases (the four cases almost universal among languages that use grammatical case) is the genitive (the nominative/absolutive and accusative/ergative are described here, and the dative here).

Genitive Relation
The genitive relation consists of a noun phrase (the minimum noun phrase in most languages being a single noun) that modifies another noun phrase. As described by grammar books, a genitive phrase is a noun phrase that specifies or describes another noun phrase, with the result being that the genitive phrase helps to answer the question "which?" with regard to the modified noun phrase; e.g. "the girl next door's dog" (genitive in italic) answers "which dog?", "music of Starcraft" answers "which music?", etc.

As it essentially contains all manner of modifying phrases, clearly the genitive is an extremely broad relation, and there are quite a few more-specific relations that fall under the umbrella of "genitive". A semi-exhaustive listing of the various types of relations the genitive can express:

Physical possession: "my computer"
Abstract possession: "your happiness"
Relational: "his wife"
Compositional: "bottle of water", "box of nails"
Quantitative: "half of them"
Subjective: "her snoring"
Objective: "its destruction"
Purpose: "sledgehammer of castration"
Location: "citizens of America"
Origin: "Kazuhiro Sasaki of Japan" (for those who don't know, he's a Japanese baseball player that was recruited to play professionally in America)
Affiliation: "Apple's Steve Jobs"
Attributive: "thing of beauty"
Topical: "Of Mice and Men"
Appositional/classifying: "President Obama"

It's likely that all languages can represent all genitive relations, though the methods used in languages differ, and a single language may have multiple mechanisms that may or may not overlap. A genitive case (or multiple cases that each represent more constrained relations) is one option to represent the genitive, but a language need not have an actual case, nor are case(s) and non-case methods mutually exclusive. Japanese, for example, does not have a genitive case, while Latin (and many other Indo-European languages) has both genitive case and a variety of prepositions that allow expression of specific relations.

One very good reason for a language to have more than a single mechanism of representing the genitive is that any single such mechanism would necessarily be ambiguous. Take, for example, the English phrase "betrayal of Illidan"; with this phrase it is unclear whether the genitive is subjective or objective - that is, whether Illidan is the betrayer or the one betrayed. Other such examples can be invented based on other uses of the genitive.

Of course it's not all bad; if there were no ambiguity in language, puns would be impossible. One real-life example of genitive ambiguity comes from IRC. jfroy says 'Snow Leopard meeting' in the sense of 'meeting about [Apple] Snow Leopard', to which I reply, interpreting that as 'meeting with a snow leopard':
<@jfroy> Snow Leopard meeting over. Ow.
<enma_hinobara>Next time don't poke it
<enma_hinobara>It's not Kaity

The Genitive in English
It's arguable whether English still has a genitive case; if it does, it only exists for (some) pronouns, where it indicates a purely possessive relation (which is why it might better be called the possessive case). It does, however, have three different mechanisms for expressing genitive relations in general - the periphrastic genitive, the analytic/agglutinative genitive (both are my own terms, so don't expect to find them in a dictionary), and the possessive.

The periphrastic genitive renders the genitive phrase as a prepositional phrase with the preposition 'of', e.g "fog of war". This is the "true" genitive in English, in that it is the mechanism that can express nearly every possible genitive phrase (although some phrases may sound better using one of the other mechanisms), while the others are much more restricted in use.

The analytic/agglutinative genitive renders the genitive relation purely by shoving two (or more) nouns together, e.g. "milk carton" (compare to "carton of milk"), "wood chips" ("chips of wood"), etc. I call it the analytic genitive because the genitive relation is expressed purely analytically - through word order, rather than word form. I call it the agglutinative genitive because in more synthetic relatives of English, such as German or Old English, the modifying word(s) would be agglutinated with the modified word to form a single large word (this can sometimes produce very long compound words); for example, "girl next door" would be "Nachbarmädchen" in German (literally "neighborgirl"). In English, this type of genitive is restricted to certain types of relations, and is especially used for classification.

Finally, English has a special means of expressing possessive relations, a subset of genitive relations (it's unclear exactly how this form originated; some argue that it's an evolution of the genitive case, while others are more skeptical of that conclusion). Note here that English has a rather broad concept of possession, and as such the possessive can be used with some relations that aren't strictly possessive in nature.

The Genitive in Latin
As a relative of English, the genitive in Latin is much the same, in that genitive relations can be expressed via prepositional phrases (which are substantially similar to their English equivalents) or analytically; however, Latin also has an actual genitive case (a result of which is that it does not need a possessive structure as English does), which is used very commonly. A few examples of the genitive case in Latin:

"agricolae [farmer, genitive] filia [daughter, nominative]": "farmer's daughter"
"horum [these, genitive] omnium [all, genitive]": "of all these/of all of these"
"vir [man, nominative] magnae [great, genitive] virtutis [courage, genitive]": "man of great courage"
"fossa [ditch, nominative] decem [10] pedum [foot, genitive]": "ditch of ten feet/ten-foot ditch"
"Rex [king, nominative] belli [war, genitive] cupidus [desirous, nominative] est [is]": "The king is desirous of war"

The Genitive in Japanese
Finally, As Japanese does not have true case, like English it uses non-case-based structures for constructing the genitive. Japanese has two genitive-marking particles - 'no' and 'na', which differ only in whether the genitive phrase is abstract (e.g. 'baka' - 'stupidity') or concrete (e.g. 'shakunetsu' - 'scorching heat') - used in the periphrastic genitive, as well as the agglutinative/analytic genitive (the genitive may or may not actually be agglutinated). However, Japanese also shows off several uses of the genitive that English and Latin do not.

Consider the rough definition of the genitive - something which specifies or defines a noun phrase; where have we heard this definition before? Well, for one, it's the definition of adjectives. In fact, a language can get by just fine with almost no true adjectives (e.g. the kind we have in English), instead opting to use one or more of the three alternate methods I talked about previously. One of these methods is to use the genitive with descriptive nouns, a method that is used extensively in Japanese and Caia (in fact, it's the primary method in Caia). A couple example from previously used words would be "baka na inu": "stupid dog" (literally "dog of/with stupidity") and"shakunetsu no koi": "scorching love" (literally "love of scorching heat").

The other structure this definition matches is apposition; that is, a restatement of something previously said for the purpose of definition or clarification, such as the italicized part in "Julius, son of Ambrose". In a previous post on the predicative, I explained that in Indo-European languages such phrases are in the same case as the phrase they restate, but that we could imagine other reasonable ways of expressing them. In Japanese such phrases may be expressed either by the analytic genitive (e.g. "kemono [beast] no sousha [player, generally of an instrument] Erin": "Erin the beast player") or the periphrastic genitive (e.g. "Hamelin no violin hiki [player]": "Hamelin the violinist" - literally "violinist of Hamelin").

Finally, some languages, such as Japanese and Caia, allow other relational phrases to be put into the genitive, where the genitive particle indicates the modification of a noun phrase, and the other relational particle specifies the precise relation of the genitive phrase (you might say the genitive particle applies top-down, while the other relational particle applies bottom-up). Some examples of this in Japanese:

"ano [that] group to [with] no kankei [relationship]": "relationship with that group" (literally "relationship of with that group")
"ano kaisha [company] to no keiyaku [contract]": "contract with that company"
"Asia kara [from] no ryuugakusei [exchange student]": "exchange student from Asia" (literally "exchange student of from Asia")
"Hokkaido kara no omiyage [souvenir]": "souvenir from Hokkaido"
"America ye [towards/to] no monkowohiraku [opening the door; this is rendered as a noun in this phrase, not a verb, in this example]": "opening the door to America" (literally "opening the door of to America")
"anata [you] ye no tegami [letter]": "letter to/for you"

& the Real World

2009-06-05T13:19:00.000-07:00

Martial arts in a skirt, eh? I thought that kind of thing only happened in anime.

(found via http://www.darkroastedblend.com/2007/01/anti-us-north-korean-posters.html)

The Dative

2009-05-27T12:53:00.000-07:00

The dative, or indirect object, is one of the four core cases - those cases that are almost universal in languages that have case - along with nominative/absolutive, accusative/ergative, and the genitive.

While the details vary by language, the general concept for the dative is a goal or direction of an action (especially with regard to transfer or movement), or the one perceiving an action. In the study of grammatical role, the dative roughly corresponds to the role of goal (although it may have additional uses in a given language). While English has pretty much lost its case system, the logical dative remains, usually expressed with the prepositions 'to' or 'for'.

Some examples of the various uses in several languages from Wikipedia and other sources (note that I'm mainly covering the most common uses, not ones that are specific to certain languages):

Goal of Transfer:
Latin: "Regina puellae pecuniam dat" ("The queen gives money to the girl")
Japanese: "Kodomo ni yaru" ("Give to the child")

Goal of Movement:
Japanese: "Ano hito wa gakkou ni haitta" ("That man has gone to the school")

Goal of Intent or Benefit
Latin: "Auxilio vocare" ("I call for help")
Latin: "Puellae ornamento est" ("It is for the girl's decoration")
Latin: Graecis agros colere ("To till fields for the Greeks")
Greek: "τῷ βασιλεῖ μάχομαι" ("I fight for the king")
Greek: "πᾶς ἀνὴρ αὑτῷ πονεῖ" ("Every man toils for himself")

Goal of Experience:
Latin: "Vir bonus mihi videtur' 'the man seems good to me"
Latin: "Quid mihi Celsus agit?" ("What is Celsus doing [that I am interested in]?")

One of the more peculiar uses (at least for English speakers, as I don't think English has anything like it), is the dative of possession. This renders phrases of possession as phrases of existence with the possessor in the dative. The logical basis of this usage is that in terms of grammatical role, in phrases of possession the possessor is technically classified as the goal.

Some examples:
Latin: "Angelis alae sunt" (literally "For angels there are wings"; freely "Angels have wings")
Greek: "ἄλλοις μὲν γὰρ χρήματα ἐστι πολλὰ καὶ ἵπποι, ἡμῖν δὲ ξύμμαχοι ἀγαθοί" (literally "For others there is a lot of money and ships and horses, but for us there are good allies")
Japanese: "Watashi ni tsuno ga nai" (literally "For me there aren't horns")
Tsez: "Кидбехъор кIетIу зовси" (literally "For the girl there was a cat")

Random Fact of the Day

2009-05-25T21:08:00.000-07:00

I just learned that some lizards (e.g. Gila Monsters, Komodo Dragons) are venomous.

MRI scans of a preserved skull showed the presence of two poison glands in the lower jaw. They extracted one of these glands from the head of a terminally ill specimen in the Singapore Zoological Gardens, and found that it secreted a venom containing several different toxic proteins. The known functions of these proteins include inhibition of blood clotting, lowering of blood pressure, muscle paralysis, and the induction of hypothermia, leading to shock and loss of consciousness in envenomated prey.

I'd always heard what had been previously believed - that they merely had toxic bacteria in their mouths that was transferred in bites.

Basic Word Order

2009-05-15T12:38:00.000-07:00

Obviously, English typically has has the word order subject-verb[-(direct) object] (or SVO, for short). This can be altered in specific situations due to WH-movement (e.g. OSV in "What would you like?") and other structures, but SVO is the normal word order.

However, this isn't the only possible word order. Basic combination math tells us that there are six possible orders: SVO, SOV (e.g. Japanese, Korean, Latin, and Proto-Indo-European), VSO (e.g. Hebrew, Trique, and Caia), VOS, OSV, OVS; these are, however, not all equally likely.

Two rules have been developed which govern the prominence of different word orders. First, there's a tendency for the subject to precede the (direct) object. This is known as subject salience. There have been various theories on the exact reason for this; the general idea is that it's more natural for the subject to precede the object because they subject is typically the source of an action, and thus precedes the object in both cause and effect and chronological order.

The other is that there is a tendency for the object to sit next to the verb (on either side). Linguistics thus far has developed the notion that the object and the verb logically form a structure called the predicate, which stands apart from the subject (i.e. a clause is typically defined as a subject + a predicate). I haven't investigated the full depth of why this has been decided, so I couldn't really give more detail than that (though it's noteworthy that this idea is consistent with my hypothesis that language began as commands - the command forms the predicate, and the subject was added in later).

Thus, we have four classes of word order: those that meet both conditions, those that meet one or the other, and those that meet neither. In agreement with theory, SVO and SOV are by far the most common among languages, at 42% and 45%, respectively. On the distant second tier is VSO, which places the subject between verb and object, occurring with 9% frequency. On the again distant third tier are VOS, and OVS, each placing the object before the subject; these occur with 3% and 1% frequency, respectively. At the bottom is OSV, which violates both rules, and was not seen in any language in this survey of 402 languages.

Clearly the subject salience rule dominates in significance, as orders where object precedes subject are very rare (3% or less); although it's also true that languages where the object is not next to the verb are uncommon (9% or less).

& Spring 2009 Anime Music

2009-05-06T22:10:00.000-07:00

I've been meaning to write a post about the anime series I'm watching this season (though some I still haven't decided if I'm gonna watch all of yet), but thus far (up to and including now) I've been too lazy to actually do it.

Instead, I'll do something that's substantially less work for me: post some of the theme songs of series I'm watching with (very) brief comments.

The Asura Cryin' ending theme is really the one that made me decide to do this post. Which is to say I'm fond of it.

The music within the series also didn't seem too bad. I haven't heard enough to decide whether I think it's good, it's certainly superior to the typical mediocre anime music.

The opening isn't as good as the ending, but not bad, especially the first 20 seconds or so.

As I watched the Pandora Hearts opening theme, the short violin segment reminded me of Yuki Kajiura, one of my favorite composers, who is known especially for very pretty violin pieces. A quick look on Anime News Network confirmed that the series was indeed done by her. I wouldn't say the opening is her best work, but it's certainly not bad.

So that should mean the music for the series will be pretty good.

The ending isn't as good as the opening, but from a quick glance at the credits I don't think it was done by her (it's fairly common for the openings and/or endings to be done by different composers than the series music - often real bands). It also isn't bad.

K-ON! is a quirky series. It's amusing, but excessively cute. From what I've seen so far, the music is very mediocre, though the opening and ending aren't quite so much, though for different reasons.

About all I have to say about that is that I don't think I'll be listening to that opening apart from showing it to people with hangovers.

The ending is similarly loud, but substantially better; palatable, and even a bit catchy. I do really like the animation that goes along with the ending theme - parts of it are quite artistic, and look very sharp (such as the black and white ensemble).

Empathy Hierarchy and Other Ungodly Things

2009-04-26T10:44:00.000-07:00

A ways back I wrote a post about empathy (also called animacy or agency) hierarchies and how the empathy hierarchy in Spanish and other romance languages worked, explaining a peculiarity of their grammar that had haunted me since high school Spanish. Unfortunately, I was excited at the time I was writing, and didn't explain it near as clearly as I should have.

Anyway, to briefly recap, empathy hierarchy is a system of classifying entities (e.g. nouns) according to the level of empathy the speaker feels towards them. While the number and composition of levels vary by language, the general trends are 1st person >= 2nd person >= 3rd person, animate >= inanimate, definite >= indefinite (e.g. "those people" >= "some people"). In Spanish there were three levels with regard to verb agreement: 1st person ("[yo] juego" - "I play") > 2nd person familiar ("[tú] juegas") > 2nd person formal ("usted juega") + 3rd person ("[él] juega"); this makes logical sense because you would have more empathy towards those you would address with the 2nd person familiar (e.g. your friends and family) than those you would address with the formal 2nd person (e.g. people you meet on the street). One of the most common things governed by empathy hierarchy is verb agreement, which is exactly what is seen in Spanish in the above examples.

One of the languages (actually a family of languages) I'm creating for one of my stories turns the concept of empathy hierarchy completely upside-down. In these languages, verbs agree with the subject, direct object [if any], and indirect object [if any] (this is as complicated as it sounds, though some real "polypersonal" languages actually do have verbs that agree with all three of those). As the subject, direct object, and indirect object are not marked for case and word order is free, verb agreement is really the only way to tell who's doing what in a sentence; for example, you could have something like "Dog bone boy gaveheitit" or "Bone boy dog gaveheitit", which would mean more or less the same thing, as word order isn't important in this respect (word order indicates more subtle things, such as what is emphasized in a sentence).

However, instead of relying on animacy or empathy to create this agreement system (animacy and/or empathy being pretty much universal in natural languages, as far as I know), these languages use rank. Specifically, a seven-tiered hierarchy with levels I label -3 (lowest) to +3 (highest). For humans, rank reflects social status relative to the speaker. Rank 0 is reserved for the first person, ranks below 0 represent those below the social status of the speaker, and ranks above 0 above the speaker, with the degree of difference indicated by the rank (rank x + 1 > rank x); e.g. use of rank 2 by the speaker to refer to someone would mean that that person has a social status substantially higher than that of the speaker. For nonhumans (animals and inanimate objects) rank is based on respect for that thing - positive and/or honorable things would have high rank, negative or dishonorable things would have low rank; in this way rank resembles more arbitrary noun class systems.

Now, depending on how deeply you thought about what I just said, you may or may not already be scared of this idea; so let me illustrate. Suppose you have two coworkers at a job talking to each other (thus they'd be of the same social status). As it's customary to show some respect to those of the same rank as you in East Asian cultures (these languages are loosely based on Japanese, with a bunch of fun stuff thrown in), both would refer to each other ("you" in English) with the +1 level. However, as this system does not distinguish between 2nd and 3rd person, if one of them uses the +1 level for something, it could just as easily refer to some third co-worker who wasn't a part of the conversation (a 3rd person, no pun intended). Or it could simply refer to some inanimate object that just happens to be at the +1 rank.

But that's easy stuff. Now imagine a person writing to a politician. If this was just an average person, they might use rank +2 to refer to the politician ("you", in English), given the significant difference in social status. The politician would then use rank -2 to refer to the person (or -1, if the politician wanted to be polite), which would also be written "you" in English. Now suppose they were talking about the king. The lay person would probably refer to the king with +3 rank; the politician, however, would use a lower rank (+1 or +2), as their own social status is greater. Of course, any of these (-2, -1, +1, +2, +3) could simply be referring to an inanimate object, instead.

Worse yet, the innate rank of an animal or inanimate object could be modified based on the rank of a possessor; that is, if the possessor of an object has a significantly different rank than the speaker, the rank of the thing possessed might be elevated or lowered to reflect the possessor.
Suppose that dog' has an innate rank of +1. In the previous scenario, the person might then use rank +1 to refer to his dog, +2 to refer to the politician's dog, and +2 or +3 to refer to the king's dog. The politician, on the other hand, might refer to his own dog as +1, the person's dog as -1, and the king's dog as +2.

And as one last nail in the coffin of sanity is a concept I call the heterogeneous plural. That is, a plural that comprises members of significantly different rank. In this case, the rank of the group as a whole would be the rank of the highest-ranking member. So if the person writing a politician referred to level +3, he could be referring the the king, the king and the politician together, the king's dog, or something else entirely.

That's me: raping your mind since 1983.

Moving On Up

2009-04-11T22:12:00.000-07:00

I'd heard all of this from him directly, but I just ran across this post on the ZDNet Security blog - Microsoft adds 'Skywing' to Windows defense team.

Incidentally, Miller is the arch-nemesis I mentioned earlier.

Random Late-Night Thought

2009-04-10T11:15:00.000-07:00

For a while I've been aware of a particular piece of linguistic evidence - namely, that cross-linguistically it is common for the imperative (command) form of verbs to be shorter than other forms, seemingly lacking inflectional affixes applied to other conjugations. For example, in Old English, the verb 'creopan' (infinitive form) is 'creope' for first person singular, 'criepth' for third person singular, but 'creop' for imperative singular. This led me to hypothesize that language might have begun as commands, and later evolved to support more general types of expressions by the addition of affixes or extra words.

Think about the significance of this for a moment. One of the most frequent differences between normal sentences and imperative sentences is that the imperative usually does not have a (stated) subject, while, depending on the language, general sentences may require subjects.

Now, one of the big mysteries of linguistics is how we came to have such radically different language systems as accusative, ergative, and topic-comment*. Yet if commands were all that was originally spoken, this provides us with a trivial answer: initially, there was only a direct object and no subject, thus that language would predate the differentiation of the three types.

As the language evolved further, eventually there would be the need to add in a subject; how exactly this was handled would then determine which of the three paths was taken. Accusative languages would place the subject in a separate case (nominative) from the direct object (accusative case). Ergative languages would classify the subject based on whether its role is the agent (ergative case) or patient (absolutive case). Finally, topic-comment languages would place the subject (the topic) completely apart from the rest of the sentence (the comment).

*Since I don't think I've talked too much about topic-comment structure, I'll briefly explain here. In topic-comment languages, a topic is stated for a sentence or set of sentences, then a number of comments are made regarding that topic. Japanese, Korean, and Chinese are like this, among others, although it's also possible to use a periphrastic form in languages like English (e.g. "As for the movie [the topic], we'll meet at 2 [the comment]").

Of particular relevance, one thing the topic can be used for is the subject of the sentence, e.g. "As for him, he'll be coming later" (though true topic-comment languages usually wouldn't duplicate the subject as English does - it would be more like "As for him, will come later"); this is frequently done in Japanese and Korean, for example. Of course, the comment may have a different subject than the topic, so topic-comment languages may also be accusative or ergative (e.g. Japanese is accusative). Here I am hypothesizing that initially the subject was represented exclusively as the topic, then further evolution allowed the subject to be within the comment itself (although whether this is true is relatively unimportant to the theory that languages began as commands).

Curve Ball

2009-04-09T10:31:00.000-07:00

Some surprising last-minute good news from France:

After the parliament voted in favor of the law, no one doubted that it would be approved by the senate and National Assembly as well. As expected the law was indeed ratified by the senate this morning, but to everyone’s surprise it didn’t make it through the National Assembly.
...
Unfortunately the law is not completely off the table. It is likely to be voted on again on April 27 according to members of UMP, one of the supporting parties. However, failing to get it passed through the National Assembly the first time is clearly a huge mistake that is almost amateurish, and public opinion is not likely to change anytime soon.

Which I suppose makes for a (tentative) good-triumphs-over-evil-in-the-end Hollywood ending, after what the proponents of the law pulled in parliament.

Name That Movie

2009-04-03T13:54:00.000-07:00

See if you can recognize this one.

A bill written by big business interests is proposed in French parliament. Hugely controversial, the bill is opposed by most apart from the business interests that wrote it, and it is difficult to see how it could pass (although you can never underestimate the corruption of government officials). As the deadline for the vote draws near, an intense debate lasting 42 hours straight breaks out among parliament members.

Eventually, late Thursday evening, it is decided that the debate should cease and parliament members should go home for the night, and the bill would be voted on the next week. So, parliament members do exactly that. After about 98% of parliament members have left the building, the vote is called early, at nearly 11 PM on Thursday night. With 16 members remaining, the bill passes, 12 to 4.

Can you name that movie?

Actually you can't, because it actually happened - yesterday. This is the French Three-Strikes law, which promises to disconnect people from the internet on allegation of copyright infringement, without ever having to present evidence in court or even tell the accused what copyright they are thought to have infringed. It will also require running spyware on all computers that constantly talks to government systems and monitors activity and the state of your network.

Welcome to French democracy, proving that America really isn't that bad afterall.

& Patents... or Lack Thereof

2009-04-01T14:50:00.000-07:00

A ways back (might have even been a couple years), I came up with an idea for something called Anonymous Private Mail, or a-p mail, a system of e-mail which provides for much greater privacy. Rather than using an e-mail address, a-p mail identifies individuals by their public/private key pair used to encrypt the e-mails (the private part). What made the a-p mail system so novel was that it was able to route a message from sender to receiver without ever knowing the keys of the sender or recipient (the anonymous part). Because of this, the e-mail server (or anyone monitoring it) could not even tell if two e-mails were sent by the same person or received by the same person (in contrast to normal e-mail systems, where the server always knows at least the e-mail address of the receiver).

I was initially concerned about disclosing how it works, especially with regard to patenting it. This system originated in one of my stories (the universe of Starfall and Eve of Tomorrow, which I briefly mentioned previously) as a method allowing criminals (especially terrorists) to communicate. I was concerned that if I patented it, it would be used in the same was it was used in the story. For this reason I posted the basic description (essentially what I wrote above) on this blog and some forums, asking for comments about whether I should patent it or keep it secret forever.

Eventually, a consensus opinion was reached that if I'd managed to come up with this idea, others would also be able to, so the only thing that keeping it secret would do is prevent me from potentially receiving licensing fees for the patent on it. So, after a great deal of procrastination (me being me), I finally wrote up the patent application and submitted it to the US Patent and Trademark Office last Thursday.

While not entirely unforeseeable, I was still very surprised to find two men in suits at my front door on Friday. To make a long discussion short, they explained that they were from the US Department of Homeland Security; they had seen my patent application, and, apparently, I wasn't the only one concerned about the possible application of the method to criminal organizations (particularly terrorism). They informed me that they'd deleted my patent application, and presented me with a federal gag order barring me from disclosing the details of the method to anyone else (including making further attempts to patent it).

So, I guess I won't be patenting it afterall. Funny how all decisions become easy when you're reduced to only a single option... At least this won't impact my stories - as they weren't targeted specifically at people with great knowledge of computers, most people wouldn't have understood the thing even if I had explained how it worked in the stories.

So Much for That

2009-03-27T17:44:00.000-07:00

A couple weeks ago I happened to be at a certain computer store. I happened to notice that they had a sale on a GeForce 9400 GT 512 meg video card for $40 (normally $70). While I already have a sufficiently powerful video card, I'd been thinking for a while about picking up a cheap GeForce, in case I ever felt inclined to play with CUDA (my video card is an ATI). So, I grabbed one.

After a sufficient amount of procrastination (specifically, two weeks, bringing it to the last day to return it), I figured I should see about opening it and installing it, to make sure it works. But first I decided to do a bit of research: namely, whether you can have both an ATI and nVidia card in the computer at a time. Obviously this should work, but with the ATI and nVidia war, driver idiocy, etc., you never know.

Well, it turns out that you can't - at least, not in Vista (I'm using 2008, which is based on Vista). Specifically, Vista only allows one WDDM display driver to be loaded at a time; this means that if you have multiple video cards, they all need to use the same video driver. While Vista still supports older XP XPDM display drivers (and allows multiple XPDM drivers to be loaded at once), it'll cost you - WDDM drivers are required for things such as Aero and DirectX 10; worse, you can't have one driver that's XPDM and one that's WDDM. Windows 7 is rumored to support multiple WDDM display drivers at once.

And that's why I tried it while it was still returnable, and didn't open it before doing some basic research.

Die, .NET. Thanks.

2009-03-26T16:16:00.000-07:00

So, just encountered an (extremely) evil quirk of the .NET platform in a bug.

Everyone who programs .NET knows that one key difference between the two is that structs are (without ref specified) always passed by value, while classes are passed by reference. Apparently that rule is not limited to actual passing of structs, themselves; passing a "pointer" to a callback function for an instance of a struct causes a copy of the entire struct to be passed, and the callback is then called on that copy, not your original instance.

Example:
system.FindCollisions(collisionSet.OnPossibleCollision, workingSet);

In this line, FindCollisions receives a local copy of collisionSet. When it then calls that callback function, that callback operates on the local copy, not on collisionSet itself.

I'm not sure whether this is by design or whether it's a bug. While it's consistent with the policy of always passing structs by value, the fact that it's so counter-intuitive makes me wonder if it might not be a bug.

& More Piracy

2009-03-25T13:26:00.000-07:00

I haven't written about it as much on this blog as other places (instant messages, IRC, various forums, etc.), but I'm a huge opponent of both Digital Rights Management (also known as Content Restriction, Annulment and Protection) and draconian anti-piracy efforts like the RIAA's law suit campaign. This was based on the belief that regardless of the raw numbers (e.g. total P2P downloads of something vs. actual sales), the total number of lost sales due to piracy was low enough that it was better to just eat the losses as part of the cost of doing business than to expend the effort, cost, and public good will to try and fight piracy (which wouldn't work anyway). Specifically, I was guessing that the actual losses were in the 5-15% range - that is, if there were 0 piracy, producers could sell 5-15% more of whatever they make.

However, just now I came across some rather shocking statistics, complements of the makers of World of Goo (a game that shipped without DRM). According to their data collection, 82% of copies of the game played were pirated. That's higher than I expected, but that wasn't the shocking part: that the ratio of pirated copies to lost sales is about 1000:1. Crunching the numbers and rounding up a bit to err on the side of caution, this means that the actual losses of piracy are less than 0.6% of the revenue they make from legitimate sales. This is between 8 and 25 times lower than I thought it would be.

These numbers absolutely demolish the claims that

Internet piracy seriously hurts publishers (the actual damage is negligibly small)
That DRM does more help than harm by reducing piracy (with levels of losses that low, there isn't any room for DRM to help, yet it's clear that it does a substantial amount of harm)

Random Linguistic Fact of the Day

2009-03-19T13:25:00.000-07:00

Technically English (and I think all Germanic languages) doesn't have a future tense. The future is rendered as a mood in English, using a modal (mood auxiliary) verb, in the same class as (and mutually exclusive with) "can", "may", "must", "would", etc. The past and present tenses, on the other hand, are true tenses, and both in the indicative mood (no modal verb or the "do" dummy modal verb).

The logical basis for this distinction has to do with the concept of realis. Essentially that means what it looks like: realis moods have to do with 'real' things - things which are considered certain to have already happened; while irrealis moods are not certain for one reason or another. There's a general tendency in language to regard the future as inherantly uncertain, and thus place it in an irrealis mood.

Whether this is a peculiarity of Germanic languages or is universal among Indo-European languages is unclear. In Latin there is a future tense for the imperative mood (commands - an irealis mood) as well as indicative (events that are certain - a realis mood), but not for subjunctive or supine, two other irealis moods.

For trivia value: Caia does not have tense; aspect and mood are used to imply tense, and if tense must be made absolutely certain, it can be indicated with adverbs. It has three basic moods (more complex moods are specified with helper verbs or particles): indicative, potential, and hypothetical. As in English, the indicative is used for events considered certain, and is used primarily for past and present tense. Potential mood indicates that an event is possible, but not certain; it is used for the future, among other things (although the preferred method of referring to the future is to reduce it to a certain, indicative present expression such as "I intend to go" or "I want to go", which is more precise). The hypothetical refers to events that are known to be false (hence talking about a hypothetical, counter-factual "what if" situation).

Random Linguistic Fact of the Day

2009-03-08T16:17:00.000-07:00

Ever wonder why it's fairly common to create compound nouns from phrases (e.g. bird-watching, card-carrying), but in all these cases the object comes before the verb participle? Based on English word order it should be watching-bird, etc., yet it never is.

This is probably due to the fact that word order in Proto-Indo-European was very different than the word order used in English and most other Indo-European languages today. In particular, instead of the subject-verb-object order typically used today, PIE (along with more recent ones, like Latin) preferred the subject-object-verb word order. So you might say things like "Avem [bird] spectabam [I watched]" in Latin, which is exactly the order seen in the compounds.

Here We Go Again!

2009-01-10T20:24:00.000-08:00

It's that time again: the beginning of the next anime season; the winter 2009 season, in this case, and things look pretty bleak. THAT Anime Blog put their preview up quite a while ago. I'd been waiting to post until Random Curiosity posted theirs, although then I was too lazy to actually post when they did, a week ago or so :P

So, what's Q looking forward to? Well, not much. I'll probably watch Slayers EVOLUTION-R because I have a couple of friends that absolutely love that franchise. I downloaded the first episode of White Album (though I haven't watched it) mainly because of the pretty pictures on Random Curiosity's first episode review; we'll see how that turns out. Other than that, there are three series that, while I can't say they sound great, I'm at least willing to try watching a couple episodes and see - Chrome Shelled Regios, Black God (listed as "Kurokami the Animation" on Random Curiosity), Kemono no Souja Erin [The Beast Player Erin] (in no particular order).

Really, the closest thing to something I'm "looking forward to" on that list is Minami-ke Okaeri [Minami family, welcome home]. While I wouldn't name it among my favorites, the Minami-ke franchise was sufficiently amusing to make me watch more of it (although it has a bit more cross-dressing than I'd care for).

I'd say the best stuff ("best" is a relative measure, here) is the two+-season series that are continuing into this season. Toradora!, Clannad After Story, Skip-Beat!, Toaru Majutsu no Index [A Certain Magical Index], and Tales of the Abyss, listed vaguely in the order I like them.

However, I do have good news. I recently saw a mini-review on the sidebar of Anime News Network for a series by the name of Higurashi no Naku Koro ni ["when the cicadas cry", though the official translation is "Higurashi - When They Cry"] that kind of intrigued me; a quick look on AniDB revealed that it was fairly well-rated (although the art style is hideous). So, I grabbed it. While the first roughly 2/3 of the series were sufficiently amusing to hold my interest, the last third of the season really elevated my opinion of it, and made me recommend it to all my friends. However, this series is not for the faint of heart, faint of stomach, or those who don't like brutal, tragic stories that don't have happy endings.

It's a big of a peculiar series. It's structured into a number of arcs (six in the first season), falling into the categories of question arcs and answer arcs. Question arcs are kind of horror/thriller type, where a lot of weird stuff happens, but a lot of it is left unexplained, as to why it happened to begin with. Answer arcs explain parts of the series - why things happened the way they did, and what is behind some of the strange occurrances in question arcs. Oddly, while some of the arcs are compatible, others appear to take place in different universes, as they're mutually exclusive subject matter occurring at the same time, to the same characters. The last arc of the first season, however, suggests that there are actually parallel worlds that aren't entirely separate, and there's some crossover between them; the details are left, presumably, to the second season (Higurashi no Naku Koro ni Kai) or the OVA, which I haven't seen yet.

In any case, I've quickly become attached to it (I watched all 26 episodes in 2 days, which is more than I usually watch of anime), and I'm a bit depressed by running out of the first season to watch.

You can get it from a variety of places, at least one of which is downloadable online (*cough* Boxtorrents *cough*); note that the first season has 26 episodes, while they second has 24. I'd definitely recommend watching it. If you want to start with the best part, I'd say watch episodes 5-8 and 16-21 (both contain the same story, but from different perspectives; the latter explains what was going on in the background of the former, and shows why things turned out the way they did). Though even if you don't skip ahead, I'd recommend watching those two arcs back-to-back at some point, as they're part of the same story.

Q & Stuff

R.I.P. Dorkess

Anti-Piracy for Dummies

Public Service Announcement

RIP Bigg'ns

Public Service Announcement

NWScript Stack System

& NWScript

& LLVM

& Cache-Oblivious Algorithms (Updated)

When Size Matters

What the

& Twitter

& Bugs

& Domain-Specific Computing

& MPQDraft and StarCraft 2

& Twitter

& Facebook

& Spring Anime Thoughts

& New Endeavors

& StarCraft 2

Q's Squishy Thing of the Day

Q's Squishy Thing of the Day

Q's Squishy Thing of the Day

& Content Filtering

Die! *smash*

...Now What?

Let's Do Some Math!

& Solid State Stuff

Random Fact of the Day

EPIC FAIL

What the Goat

Random Fact of the Day

Computer Book Library

Bibliography - Programming

Do I Speak WHAT?

Random Fact of the Day

& Modern Things Part 3

& Modern Things Part 2

& Modern Things Part 1

& Moral Panics

& Even Older Things

Random Fact of the Day

& Almost as Old Things

The Taxonomy of Linking

& Hobbit Birthday Parties

& Very Old Things - Part 3

& Very Old Things - Part 2

The Story of ThunderGraft

& Very Old Things - Part 1

& Summer 2009 Anime Music

Introduction to Anime

& Summer 2009 Thoughts

& That Memory Leak

Useful Fact of the Day

RIP E Terra Blog

& Detexify

& the Genitive

& the Real World

The Dative

Random Fact of the Day

Basic Word Order

& Spring 2009 Anime Music

Empathy Hierarchy and Other Ungodly Things

Moving On Up

Random Late-Night Thought

Curve Ball

Name That Movie

& Patents... or Lack Thereof

So Much for That

Die, .NET. Thanks.

& More Piracy

Random Linguistic Fact of the Day

Random Linguistic Fact of the Day

Here We Go Again!

Die! smash