Search This Blog

Wednesday, March 22, 2006

It's a Wonderful Life

So, I've now had midterms in every one of my classes this semester - biochemistry, biology, biology lab, computer science, and history. It seems this semester I'm having extraordinarily bad luck at getting teachers with both a good sense of logic and a good sense of time.

The first of these tests was in biochemistry. The teacher had very clearly said, about a week before the test, what material would and would not be on the test (that is, none of the stuff in lecture less than a week before the test would be on the test). She even very specifically listed a couple topics in particular that would not be on the test. Guess what was worth 15% of the grade on the test? However, when she saw that I'd written on the test that she said that wouldn't be on the test, she decided to multiple everyone's test scores by 1/0.85.

But that wasn't the only problem. I noticed that at the end of the test, when she told everybody to turn in their tests now, only 3 or 4 people (out of a class of at least 30) had left early. I reasoned that if only 10% of the class had left early, that probably meant that a good 65%+ of the class or more hadn't even finished the test. I sent her an e-mail to that effect, saying that the test was too long. I got back this reply (actual quote taken from the e-mail):

at least 30-40% of the class had finished the test before time was up thus I do not believe that there was any problem with the length of the exam (except that it was probably too short)...

Okay, moving on...

Next up: biology. This test had more or less the same problem, only worse: few, if any, of the students had time to complete the test (indeed, after we handed in the tests I heart just about everybody at my table complaining that they weren't done). On the test was a wide variety of questions, but one, worth about 20% of the test (which means you should be able to answer it in about 20 minutes), was really the deathblow to reason and sanity. It went something like this (recalling from memory):

You are working in a barn, and sit down for a moment. When you sit down, you find that you've sat on a rusty nail, and deeply impaled yourself. An additional concern to you is that you have previously had a skin infection, which might have managed to get in the wound. Explain how the immune system would respond to this, including specific cells, locations of occurrence, chemicals, and chemical receptors.

Okay... macrophages, neutrophils, cytokines, inflammation, complement, lymph system, phagocytosis, antigen presentation, B-cell proliferation/differentiation, memory cells, plasma cells, antibody production, and a few other assorted things. Well that answer covers a good 2/3 of everything we'd learned in class up till the test. A succinct person like myself might be able to squish the answer into 3 full pages (had I had the time); other students had already gone beyond that before running out of time (and still didn't get near all of it covered). Honestly, this is about as much material as I expected to have to recite on the entire test; but then, maybe I'm too sane to be a teacher.

Next up was computer science. Nothing much to see here, other than more of the same: too freakin long. Again only 2 or 3 people out of a class of at least 30 had turned in their tests before being forced to, and again I heard people all over the room saying "I didn't have time to finish!" Somehow (probably due to the fact that 2 out of 2 of the previous tests had been this way) this wasn't so very surprising.

This was the same test that one grammar question was on; the teacher is a pretty cool guy (imagine a slightly nerdy Howie Mandel; he even looks like Howie Mandel), but he really could stand to get a handle on the fourth dimension.

Next was the history test. This was the only one of the tests that I was actually satisfied with my answers (and didn't feel like I could have done better if I'd had more time). Although a bit of that is due to the fact that we knew exactly what was on the test before we took it; the teacher made a study guide (about 3 times as long as the test) which included all of the questions on the test, as well as about twice as many questions that weren't (though we didn't know which was which ahead of time).

Then today came the biology lab test. This test seemed to be the worst of all of them, but that could just be because I've forgotten some of the specifics of other tests (which were 1-2 weeks ago). As this post is already way too long, I'll limit my complaints to only a few of the problems with this test. Let's start with this gem (rough recall of the question from memory: "Explain what the difference between confocal microscopy and fluorescent microscopy is, and the advantages of confocal microscopy." Mu? How does one explain the difference (and the superiority/inferiority) between two things that aren't mutually exclusive?

A second example (the last one, as this post is already hideously long) is one involving a graph of "precipitation" (no units given) vs. "antigen" (mg). The question asks you to calculate how much antibody there is at a given point in the graph, giving the answer in mg/ml. A bit of explanation is in order for this. This is a graph you would make using a spectrophotometer (hence the lack of units for the y axis); you would then use a standard curve to calculate the concentration of the unknown based on its absorption. Usually the x axis is in mg/ml, but this could be calculated if the volume was known (since the weight is known). I go up to the teacher, and the dialog goes something like this:

Me: There isn't enough information to answer this problem
Her: Huh? Never had a problem with it before...
Me: This graph and the data table are in mg. The answer requires the volume to be known, and it isn't given in the question.
Her: *takes a minute or two to look over the question* Oh. Well, I guess just assume that was supposed to be "mg/ml".
Me: Also, this y axis of this graph has no units
Her: So? That's how we always do it.
Me: We always have a standard curve. There is no standard curve here.
Her: *takes a minute or two to look at the question* Oh. I guess that axis would have to be mg/ml, then.
If you're looking to get a space craft to Mars, I can give you the name of somebody not to employ.

Tuesday, March 21, 2006

The Solution

Alright, let's see if I can get through writing this post without my computer blue-screening (again).

The reason this question was so cool is that it's not only hard (1 in 25 isn't very much), but the solution is extremely simple and elegant (at least in concept; when written out in grammar it isn't so pretty): it's a simple deterministic 4-state machine, represented by the following graph:

The machine begins in the even 0s and even 1s state, and changes state each time it reads a bit in the number (the order it does this doesn't matter). If at the end of the string the state is even 0s and odd 1s, then the number is valid. This machine can be directly expressed in grammar, but it can be a bit cumbersome to read; thus why I've only given the graph.

As a bonus, this next graph shows a machine for the same problem, save that it's 0-exclusive: it isn't valid to have zero 0s and odd 1s.

Oh, and on an unrelated note, I just learned that Windows Vista has new API functions for read-write locks and condition variables. Also, NT 3.5+ has undocumented but stable functions for read-write locks. I'll have to see about adding support for those in LibQ at some point (heck, I'll have to see about doing anything with LibQ at some point). For those of you wondering, the complete lack of content lately has been due to me getting back into WoW after a couple month break :P

Friday, March 17, 2006

MSDNAA is Godly

So I just got hooked up with Microsoft Developer Network Academic Alliance through my school. I more or less downloaded everything they had up there, including Windows 2000 Pro, Windows XP Pro, Windows Server 2003 Enterprise (!!), Visio 2003 Pro, Project 2003 Pro, Visual Studio 6.0 Pro, and Visual Studio 2005 Pro (KAITY). Nothing like waking up and finding like 5 grand of software legally at your fingertips for free!

Oh yeah, and I used Visio to make a beautiful diagram of the solution to that grammar problem. I'll post it this weekend, so you better try it before then! :P

Wednesday, March 15, 2006

The Challenge

I just had my first test in High Level Languages, a third-year course about the structures common to most/all high level languages, and how high level languages in general work. I thought one of the questions on the test was absolutely godly (and from what the teacher said, I was the only one in the class who figured out how to do it; however, I don't know if this is because nobody could figure out how to do it, or they made some critical typographical errors in their answers). I suggest you try and solve it, because it's an awesome question. It goes like this:

Create a grammar (BNF, EBNF, syntax diagram, whatever kind of formal metalanguage you want) rule for binary numbers of any length, containing an even number of 0s (0 inclusive) and an odd number of 1s, in any order.
You have fifteen minutes. Go!

Saturday, February 11, 2006

Real Life Adventures - Salva Nos - Part 2

1: Dominus* Deus
2: exaudi nos et miserere
3: exaudi, Dominus*

4: Dona nobis pacem
5: et salva nos a* hostibus
6: Salva nos, Deus

7: Dominus* exaudi nos
8: Dominus* miserere
9: Dona nobis pacem
10: Sanctus, Gloria

11: dona nobis pacem
12: et dona eis requiem
13: inter ovas* locum
14: voca me cum benedictis
15: pie jesu domine, dona eis requiem
16: dominus* deus, Sanctus, Gloria

Looking at the lyrics, there are two distinct themes that seem odd to encounter in the same song. While the entire song is speaking to God, one refers to 'us' - 'hear us', 'have mercy on us', 'save us', 'give us peace'. The second theme (lines 12 and 15) refers to 'them' - 'give them rest'. For this reason, I'd initially thought that there were two sources. Well, it turned out that I was right... sort of.

Lines 12 and 15 sound very much like a Catholic funeral mass, so that's where I started looking. It turns out that this is exactly what it was - a part of the Dies Irae ('Day of Wrath'), a poem incorporated into the funeral mass (for translations, see the Wikipedia article):

Lacrimosa dies illa,
qua resurget ex favilla

judicandus homo reus.
Huic ergo parce, Deus:

pie Jesu Domine,
dona eis requiem. Amen.

Interestingly, a couple different passages also appears in the poem (don't assume these lines are all consecutive):

Rex tremendæ majestatis,
qui salvandos salvas gratis,
salva me, fons pietatis.

Inter oves locum præsta,
et ab hædis me sequestra,
statuens in parte dextra.

Confutatis maledictis,
flammis acribus addictis:
voca me cum benedictis.

So, there are lines 12 through 14. What about the rest? Well, save for three lines, none of the rest of the song is taken whole from any other work (that I've found). Rather, it's a weaving of passages from several other things. First of all, let's look at the first line, part of which is repeated in the last line. As I mentioned before, 'Dominus' is the nominative form, which is incorrect in this context (it should be 'Domine' - the vocative form). Yet surprisingly, it turns out that this line is taken directly from Sanctus, a part of all Catholic mass (not just funeral mass):

Sanctus, Sanctus, Sanctus,
Dominus Deus Sabaoth;
pleni sunt coeli et terra gloria tua.

Hosanna in excelsis.
Benedictus qui venit in nomine Domini.
Hosanna in excelsis

Holy, holy, holy,
Lord God of hosts;
heaven and earth are filled with Your glory.

Hosanna in the highest.
Blessed is he who comes in the name of the Lord.
Hosanna in the highest.

Okay, so. We have the original Latin, and it's still in the nominative form, even though it's speaking to God. Is my assessment wrong? It isn't, actually (not in this case, anyway). It turns out that this Latin is actually a mistranslation of Isaiah 6:3, presumably originally in Hebrew: "And they cried one to another, and said: Holy, holy, holy, the Lord God of hosts, all the earth is full of his glory". The original text was not speaking to God at all, and as such the nominative case would be appropriate. If you look at the rest of the mass program, 'Dominus' is never used again when speaking to God; it's always 'Domine'.

This error was presumably propogated to other instances of 'Dominus' in Salva Nos.

The use of 'exaudi' seems to come from the Introit of the mass service (also a part of the funeral mass):

Requiem aeternam dona eis, Domine,
et lux perpetua luceat eis.
Te decet hymnus Deus, in Sion,
et tibi reddetur votum in Ierusalem.
Exaudi orationem meam;
ad te omnis caro veniet.

So, that's as far as the funeral mass can take us in this study. This leaves us still with three phrases. To my surprise, two of these may be found in Agnus Dei, another passage in the mass. This did not come to my attention when looking at the funeral mass, because the two phrases are missing (actually replaced by other phrases) in the funeral mass version:

Agnus Dei, qui tollis peccata mundi, miserere nobis
Agnus Dei, qui tollis peccata mundi, miserere nobis
Agnus Dei, qui tollis peccata mundi, dona nobis pacem

That just leaves one word - 'hostibus' ('enemies'). This one I'm not so sure of. The exact word does not appear in either the ordinary mass or funeral mass ('hostias' is a different word - 'sacrifices'). And looking for a document that was read by the author of the song when you only know a single word in it is like looking for a needle in a haystack; I think I'm gonna let that one go.

Lastly, I probably prompted a couple questions in my study, such as why the erroneous words (indicated by asterisks) have changed. First of all, 'a' - 'from' - is incorrect. Yes, 'a' does indeed mean 'from'; but from what I've been able to tell, 'a' changes to 'ab' when used before a word that begins with a vowel sound (try searching for "a hostibus" and "ab hostibus").

The big one, of course, is 'salva'. It turns out that 'salvo' is indeed a verb. Given the way it was used in the song (the fact that it was using a different conjugation system, and that it was used as a transitive verb), I was beginning to wonder if this might be the case. It seems to be an uncommon word, as most dictionaries don't have it (I've only been able to find one dictionary online to date that does).

So, I think that's the end of my report. If you haven't noticed by now, I've color-coded the lyrics so that their origins can be easily seen in the passages I've quoted. Thanks to John Briggs and Johannes Patruus for answering my Latin questions.

Friday, February 10, 2006

Real Life Adventures - Salva Nos - Part 1

Recently I've been listening to the music of Noir, an anime I like (although the ending kind of sucked), its music composed by my beloved Yuki Kajiura. I quickly came to like one song in particular, called Salva Nos. Eventually I started to wonder what the lyrics were (noticing a pattern, here?), as the operatic style makes it difficult to distinguish the words by ear. A quick search on Google turned up a listing on Anime Lyrics (I've modified them a bit because I think there were errors in the original transcript, and I've included my rationale for these changes in brackets).

Dominus* Deus
exaudi nos et miserere [singular imperative form of 'misereor' - have pity]
exaudi, Dominus*

Dona nobis pacem
et salva* nos a hostibus
Salva* nos, Deus

Dominus* exaudi nos
Dominus* miserere
Dona nobis pacem
Sanctus, Gloria

dona nobis pacem
et ['and'] dona eis requiem
inter ovas* locum
voca me cum benedictis
pie jesu domine, dona eis requiem
dominus* deus, Sanctus, Gloria

Anyone who has seen such a thing before will immediately recognize this as Latin. It looks like a Christian hymn, based on the subject matter; either a real hymn (as in, written back when Latin was still common in the church) or an imitation made to sound like a real one. At first I suspected it was the latter, until I read the lyrics near the end of the song. Much to my surprise, there was a reference to Jesus by name. This is such a surprise because less than 0.5% of Japanese are Christian, and a good majority doesn't even know who Jesus is; this suggested that perhaps it was a real Christian hymn, after all.

So, how to tell the difference? Well, the first solution that came to mind was to check if it was proper Latin grammar. If the grammar was flawless, it was probably written by someone fluent in Latin, such as a native speaker or a priest of the church. If it was badly bastardized, it was probably written by Kajiura herself (for comparison, take a look at the lyrics to Maze, by the same composer).

Now, checking Latin grammar isn't hard... if you know Latin. Unfortunately, my knowledge of Latin consists of a few dozen words along with my knowledge of Spanish (a Latin derivative, which often resembles Latin). That means it's time to break out my Latin-English dictionary and Quick Study Latin grammar sheet.

Okay, going through this word by word (specifically the ones I marked with asterisks, indicating that I think they're incorrect)...
Dominus: This is the nominative (sentence subject) form of 'lord'. The correct form for direct address would be 'domine'. I don't know whether Deus is kept the same for the direct address form or not.
Salva: This is the Spanish/Portuguese form. 'Salvar' means 'save', and the conjugation is imperative. However, in Latin 'salveo' is more of a passive voice - 'be well' or 'be safe' (it also is an intransitive verb). The correct word in Latin is 'servo', conjugated as 'serva.'
Ovas: A form of 'ovis' - 'sheep' - referring to God's sheep (the church). The correct conjugation would be either 'ovibus' or 'oves' (I don't know whether the accusative or ablative form would be correct, here).

Okay, so, that makes it seem likely that this is not a real hymn; that leaves the question of where the lyrics came from. As mentioned previously, most Japanese don't know who Jesus is, so it would be improbable that this was written by somebody who is Japanese. Well, let's look for other clues...

Tuesday, January 24, 2006

& Science - Maternity

I usually try to keep non-programming stuff (especially non-computer stuff) off my blog, but there are just some news items so interesting that I have to post them. The summary I posted on Star Alliance:
A fascinating article in the January issue of Scientific American summarizes recent evidence in maternity. To summarize some of the specific and general findings:

- Hormones during and following pregnancy cause drastic changes in the structure of female brains, effects which are long-lasting or permanent
- Mother rats are significantly better at processing sensory input, navigating mazes, and hunting prey than nonmaternal rats, indicating increased intelligence
- Mother rats show increased complexity in the hippocampus and proliferation of glial cells, as well as finding previously encountered rewards than nonmaternal rats, indicating improved memory
- Experiments with covered/uncovered ground indicate that mother rats experience less fear and tolerate stress better than nonmaternal rats
- Maternal rats demonstrate significantly slower intellectual decline in old age than nonmaternal rats
- Experiments involving multiple independent tasks or streams of input indicate that maternal rats are significantly better at multitasking than nonmaternal rats
- These benefits seem to increase with the number of children

Note that there has been little research of this kind done on human females to date. Note also that the title [Career Women Smarter than Housewives? Better think twice] was only meant to be provocative; it is not to imply that maternity and a place in the workforce are mutually exclusive (in fact, if these maternal traits also apply to human females, it's likely that they could be applied to the workplace).

Monday, January 23, 2006

Saturday, January 21, 2006

Q's Shiny Thing of the Day

I may yet write a post about my exploits for the last week. But suffice to say, for the purpose of this post, that I need to compare two copies of a LARGE amount of data (files), to ensure they're identical. Fortunately for me, the Windows Platform SDK comes with just such a program (originally I was worrying that I'd have to write one, myself) - WinDiff. If you have need of such a program, it comes in pretty handy.

By the way, I'm having a bit of trouble writing the post about writing multi-user friendly code. The reason is that there are three different but closely related topics I want to talk about, and I'm having trouble discussing all of them without the information becoming either redundant or chaotic.

Wednesday, January 18, 2006

Multi-User Compatibility

One of the things I listed on the recent wish-list of "taxes" features I want to support in LibQ is multi-user compatibility. What exactly is meant by that? Well, literally, it means the ability to share a single computer with multiple people, and not step on the toes of others.

In practice, it comes down to a game of permissions. In a typical multi-user system (unlike DOS, Windows 1.0-3.1, and Windows 9x, which were fundamentally single-user systems), disk resources are divided among the different users of the computer. Typically there will be one or more administrators, which have access to everything, and a number of individual users, who only have access to a portion of the disk.

In a strict multi-user system like Unix, individual users can only write to files and directories in their partition, called their home directory on Unix (while Windows NT doesn't really promote this idea by name, there is in fact a perfect analog to the home directory). Everything outside this home directory is likely to be read-only, and some of it (system directories, other users' home directories, etc.) may not even be readable to the individual users at all. Each user potentially has access to different directories than other users (this is always the case with home directories, but it may apply to things outside the home directories, as well).

To Unix users and programmers, this system is ancient, as Unix was designed (and operated) this way from day one. However, to Windows users, this is a fairly new concept. As mentioned, DOS, 16-bit Windows, and Windows 9x do not really have the concept of user isolation. Contrary to what most Slashdotters will swear, Windows NT was designed from the beginning to support user isolation; however, NT 3.1-4.0 (3.1 was the first version; it was called 3.1 because its interface was based on the Windows 3.1 shell) were primarily used (on home computers) by hardcore nerds, while Windows 2000 won over the casual geeks, and it wasn't until Windows XP (back in 2001) that the technophobic end user installed NT on their home computer. The end result of this is that, even today, programs that do not work on multi-user systems plague the NT platform, and this is the reason so many NT users run as administrator today.

Where I'm going with this topic is this: learn to write multi-user compatible programs; it is not a useless skill. If you plan to write Unix programs, you're going to have to learn; but even if you're just a Windows coder, it would save people like me a considerable amount of pain if you would still learn how to write programs that play nice.

Next time (whenever I write another technical post): how to write multi-user compatible programs on Windows and Unix. And coming soon: multi-user compatibility hall of shame.

Tuesday, January 17, 2006

Don't Buy Acer Laboratory Products

What has Q been doing for the last 5 days? Well, let's take a look at the e-mail he just sent to Acer Laboratories (ALi) customer service, and find out!
I've been having horrible problems with M1535D+ drivers since I started using my IDE drives on the motherboard IDE channels (previously several were on my Promise IDE controller, and my new Windows volume is brand new). I installed Windows XP SP1 fresh onto the new 250 GB drive. After installation, Windows could not use the drives in anything but PIO mode, despite all of them being set to "DMA if available".

I downloaded the beta ALi IDE controller drivers (the version I'm now using) from the Asus site. After that, the ALi IDE utility reported that the drive was running at UDMA100/133, but it was obvious from the slow performance and KERNRATE (from the Windows 2003 Resource Kit) data that it was still using PIO (when reading large amounts from the drive - I used a checksumming program on a 5 gig file to ensure that the drive would be read from, but no other drives would be accessed - more than 90% of the kernel time was spent servicing interrupts, and 83% of the time READ_PORT_BUFFER_USHORT was being used; both of these indicate PIO transfer is being used, and neither being the case when I used the same procedure on a drive connected to my Promise IDE controller).

Also, since installing the beta ALi drivers, my CD-ROM and DVD-ROM on the motherboard channels have not been working properly (reporting bad sectors on the CD/DVD when this can readily be proven false in another computer; both drives worked fine using the Windows XP default motherboard drivers).

Lastly, I am unable to uninstall the beta drivers. The ALI5INST utility that runs when I select the drivers in Add/Remove Programs simply opens a console window and remains there indefinitely (and it appears that this is a 16-bit program, as it runs in NTVDM). Any attempts to uninstall the drivers through device manager have resulted in the need to roll back the system state with system restore.

Oh, and did you know that the drivers page on your ALi site is a broken link?

Friday, January 13, 2006

Light at the End of the Tunnel

Well, after the seemingly bad situation yesterday, there's good news. First, I installed SuSE on VMWare to try it out, some. While there is no formal definition of the encoding of filenames (which are just null-terminated character arrays), common usage dictates that they be interpreted as UTF-8 (the Linux GUIs and some terminals do this). That means it would be moderately safe to translate Unicode filenames (and by that I mean UCS-2) to UTF-8 on Linux (and possibly POSIX at large).

Next, I was mistaken about the behavior of Windows NT on non-Unicode-capable drives. It does indeed appear to use UTF-8 encoding for filenames on such drives. The reason I thought it didn't was that it was appearing as unprintable characters (boxes, to be specific) in Explorer on the computer I tried it on (which was not my computer). Apparently it's been so long since I've used such a thing that I'd forgotten that Windows XP doesn't come with Asian fonts...

Lastly, while I could support (with effort) both the Unicode and ANSI versions of Windows file API functions, it's much easier to just use the Unicode version, and leave Win9x support (which doesn't support the Unicode versions) to the Microsoft Layer for Unicode.

So, in the end it looks like it will work fine to use all Unicode for filenames in LibQ.

On an unrelated note, I went and picked up the Hitachi 250 GB hard drive for $50 at Fry's Electronics. While I was in the checkout aisle, a couple of other things caught my eye, as well: the Quick Study Japanese Grammar and Latin Vocabulary sheets. So, I picked up those, as well.

Wednesday, January 11, 2006

Dilemma - Filenames

Somebody just kill me, now.

So, I've been considering supporting Unicode filenames in LibQ, but that brings up not nice problem. First and foremost, not all operating systems and/or file systems support Unicode filenames. Windows NT supports true Unicode (UCS-2) filenames on NTFS, but converts (and degrades) the filenames to ANSI (similar to ASCII, both not supporting foreign language characters) on file systems like FAT and FAT32 that don't support Unicode file names. I'm told some Linux file systems support Unicode file names, but I've yet to find an interface to manipulate such files.

I could get around this problem by automatically converting Unicode filenames on unsupporting OS or file systems to something like UTF-7 or UTF-8, which will fit in a char array, but this brings up its own problems. First, as previously mentioned, NT automatically converts Unicode filenames to ANSI code page on unsupporting file systems, replacing characters that can't be converted to some default character (and it's not feasible to detect file systems that don't support Unicode, to protect against this). Second, this would create an odd duality for files saved with UTF filenames. You could open them by the Unicode version of their name (as it would automatically convert the name to UTF before calling the OS functions), but the names could appear garbled in directory listings (as there'd be no good way to detect that a filename is UTF, and convert it back to Unicode).

Last but not least, I'm having difficulty figuring out the API to convert Unicode strings to UTF-7/8 on POSIX.

Tuesday, January 10, 2006

Tolkien Was an Anime Watcher?

Just watched The Two Towers with my grandpa (he's a big Lord of the Rings fan). For the first time it occurred to me that Lord of the Rings has a stereotypical anime girl that has a hopeless crush on one of the main characters, tries to win the guy's heart by cooking for him, but she sucks at cooking, and the plan goes terribly wrong. Or maybe that stereotype reaches further than anime, and I'm just too illiterate to know.

Real Life Fun - SBltROP3 Bug

Sometime after I woke up yesterday morning and started doing stuff online, Skywing messaged me. He asked me what ordinal (function number) 0x139 in Storm.dll (the custom run-time library used by Blizzard games) was. Now, the reason for asking me in particular this question was that I wrote a program called StormWatch, which logs all calls to Storm, and has a list of all the functions I've either positively identified (the names to go with their ordinals) or have reason to believe they are a given function. This list might possibly be the most complete list of Storm.dll functions held by anyone lacking access to Blizzard's source code.

The reason he wanted to know what ordinal 0x139 is was that he had installed Warcraft 2: Battle.net Edition on his computer, and it was crashing in ordinal 0x139. I knew this function - it was SBltROP3, a DirectDraw sprite-blitting function (the name is a pun based on the Windows SetROP2 - Set Raster Operation To - function, which sets what raster operation to use when drawing on a display context). I'd looked at this function some when Suicidal Insanity asked me to reverse engineer a variety of things in the graphics and sprite system of Starcraft. If memory serves, it generates dynamic blitting code on the fly for the various raster operations. This coincided with Skywing's observation that the function was generating code, and crashing when it attempted to execute the code. Goody. Debugging assembly generated by assembly code: good times.

Fortunately, the problem became readily apparent when Skywing supplied one more piece of information: his computer supported Data Execution Protection. Yup, that'd do it. Skywing and I have independently observed a number of programming blunders on Blizzard's part, and it was no surprise that they'd try to execute a function without marking it as code (although in their defense this code was written long before NX/DEP was available in hardware; but it was still supported in the Windows API).

To confirm this was the case, Skywing first examined the page that was allocated to store the rendering code. Sure enough, it wasn't marked executable. Next, he tried marking it as executable, and, sure enough, the crash evaporated.

So, now we know what and where the bug is, as well as how to fix it. The next question was how wide the problem had spread. We had positive confirmation that the bug existed in the version of Storm used for Warcraft 2: Battle.net Edition (Storm.dll version 1999.11.18.1), but Skywing doesn't have Diablo, Starcraft, or Diablo II (all of which can use DirectDraw, and thus may be subject to the bug. So, I guess that makes it a job for... me.

Unfortunately, I don't have a DEP-capable CPU to try it on; that leaves reverse-engineering. Proof of bug could be accomplished in a two-step process: first, use StormWatch to verify that they used SBltROP3. Second, verify that the bug exists in their version of Storm.

StormWatch reports (and debugging the games in WinDbg confirms) that Starcraft and Diablo both call SBltROP3; Diablo II does not. That just leaves the question of whether the two games have the bug in their version of Storm.dll.

Looking at the Diablo version of Storm.dll, it is version 1999.11.18.1 - the very same as the WC2:BNE version; FC (file compare) was used to confirm the files were byte-for-byte identical. Starcraft, however, uses a newer version - version 2003.1.1.0; that means that I'll have to get out a dissassembler and debugger to confirm that Starcraft has the same bug.

Stepping through SBltROP3, it's trivial to identify the place where it calls the generated code:
15007cf0 8b7d08 mov edi,[ebp+0x8]
15007cf3 8b750c mov esi,[ebp+0xc]
15007cf6 8b5db0 mov ebx,[ebp-0x50]
15007cf9 8b4d20 mov ecx,[ebp+0x20]
15007cfc 8b5514 mov edx,[ebp+0x14]
15007cff ffe3 jmp ebx {00cd0594}

So, there's the address of the function: 0xCD0594; now I needed to find out what the protection state was. There seems to be a way to make function calls on the command line of WinDbg, but as I'm not very proficient with WinDbg (I usually use the VC++ debugger for my reverse-engineering), I had to manually create a stack frame and set the instruction pointer to VirtualProtect (which will return the previous protection, which is what we're interested in).

Well, after ironing out a couple quirks in WinDbg, I got my result: 0x40. A quick look at winnt.h reveals the identity of this constant: PAGE_EXECUTE_READWRITE. Isn't that interesting? Looks like they fixed the bug in the Storm.dll shipped with the latest Starcraft patch.

Lastly, I performed the same process on Warcraft 2: Battle.net Edition, as a final confirmation. The result? 0x4 - PAGE_READWRITE. Sure enough, there was our bug. And so concludes the official investigation (now I can get back to working on truly evil things...).

& The Room

Remember that room we've been building in the back yard for quite a few months, now, and I haven't said anything about in ages? Well, my grandparents just arrived from Texas, today, and my parents let them use their room, while my parents are sleeping out in the new room. It isn't completely done, but the walls are all up and permanently set in place, the outside is painted, the insulation's in, the door and windows are in, the tool shed (right outside the room) is built, the rain gutters are in place, and some of the electrical works. All that's left is to put in and paint the drywall, put a second coat of paint on the outside, install the electrical outlets, switches, and air conditioner, and lay the floor down (it's still plain concrete, right now). So, making progress.

Monday, January 09, 2006

& Scheming

I'm contemplating doing something extremely evil. No, I won't say what it is, but I'll probably post about it, if I actually do it.

The Destruction Dilemma, Solved

The CThread class has been around (and written, to varying degrees) for quite some time, but I never felt like it was something I wanted to put into actual use, as some things are rather crude. In the spirit of all the other classes in LibQ so far, a CThread represents a thread. The thread is created on construct, and... well, what to do with destruction was the real question (particularly when the thread was still running), and one of the main things that made me hesitant to release CThread into the wild.

Obviously the CThread could not be destructed while the thread was still running, as that would lead to a crash when the thread tries to access its own CThread. At the time, I could think of three ways to handle destruction: kill the thread, wait for the thread to finish, and assert. Killing the thread seemed to be the worst of the options. Killing a running thread is an extremely risky proposition. In addition to the fact that the thread might be needed in the future, the bigger problem is that the thread may be in the middle of using data (possibly inside a mutex, or some other synchronization object), which would likely lead to either the program crashing or deadlocking.

The last two options were about the same, as far as desirability. The problem with both is that, if the thread were to deadlock or hang, the thread that was attempting to destruct the CThread would also hang (probably indefinitely). Ultimately, I decided to have it assert if the destructor should be called while the thread was still running; but I wasn't happy about it.

The problem became intolerable thanks to asynchronous I/O. Recall that one of the methods of asynchronous I/O completion notification was to queue an asynchronous procedure call (APC) to the thread that issued the I/O. In other words, a pointer to the CThread was being hidden away somewhere you couldn't see or get to. Once this occurred, you can pretty much forget about ensuring that the CThread was no longer being used; of course you could track all places you give a pointer to, but that would be uselessly cumbersome, and strongly opposed to the low-maintenance model I have for LibQ.

However, the asynchronous I/O problem hinted at the solution: reference counting - having the object itself track how many references exist to it, and destructing itself when that number reaches zero. Reference counting wasn't a new idea to me, but it's something I avoid as much as possible, as it requires that reference-counted objects be allocated on the heap. Memory allocations are fairly expensive, as they typically take hundreds of cycles. However, between necessity and the fact that creating a thread is expensive (if my memory serves, it takes more than 10,000 cycles on Windows), which makes the added cost of allocation marginal, this is a perfect place to use reference counting.

So, with one major hurdle down, CThread is that much closer to going public. And now that I'm thinking about reference counting, I'm considering making CSyncFile and CAsyncFile reference-counted, as well, for similar reasons (and in the process it will be possible to simplify their code, as well).

Friday, January 06, 2006

More To Do

Reading over Raymond Chen's (see Old New Thing on the list of links) taxes series, I've been thinking. The entire mission of LibQ was to abstract painfully platform-dependant system features in a set of easy to use, fast, and lightweight classes; and there are few features more platform-dependant than some of these. Where I'm going with this should be obvious: I want to support some of this stuff in LibQ. A couple of the features I would like to support (note that this is a wish list; I haven't yet researched most of those to see if they're feasible to do):

- Pathfinding/multi-user interoperability. The ability to locate the appropriate directories for various things, such as machine-wide data, user-specific data (data that will be stored on the server if the user is on a domain), temporary files, shared programs, etc. I call this multi-user interoperability because it will allow (if used properly) programs to run as non-administrator/root (this is something most Unix people should know, but way too many Windows programmers don't), as well as work efficiently on a network.
- Power management. The ability to discern what state the computer and components in it are in, so that inappropriate operations (i.e. doing background stuff on the hard drive when the computer is on battery) can be avoided. I'd also stick Windows hierarchal storage management (the automatic archival of files to tape, and automatic recall on access) in this category, because it also suggests that things should not be touched even though they can be.
- Session information. The ability to tell when the system is shutting down, the application is going to the background, and if the application is running locally (on the computer the user is sitting at) or remotely (on a different computer, where the user's computer is just a terminal, and where bandwidth is often low, and latency high).

So yeah, welcome to the todo list, gang!

Thursday, January 05, 2006

I Have Scary Friends

Oh yeah, and did you know that NX/DEP (the feature that prevents execution of noncode - i.e. buffer overflows tactics - in Windows XP+) doesn't work? Just got this link from Skywing (one of my 'best' friends - that is, the ones I talk to the most), although it's back from October. Notice the names of the authors. After reading this, I submitted the following summary to Slashdot (we'll see if it actually gets accepted):

A pair of hackers (including a personal friend) have identified a flaw in the design of Windows Data Execution Protection (DEP/NX), which ordinarily protects the system against remote code execution and other exploits that involve the execution of data, on capable processors. This flaw, detailed in their article, allows a worm or other malicious program to remotely disable DEP via a buffer overflow procedure that does not inject code of its own (and is thus not prevented by DEP). This possibility is not due to a bug in Windows, but rather due to the design decision to allow programs (for compatibility purposes) to disable their own DEP. As such, it cannot be 'fixed' in the normal sense; however, some clever tricks of Windows coding can be used to thwart this attack.