What Is It Good For?

So, a couple people have been asking what the advantage of atomic structures is over simple traditional structures (like STL) and a mutex. Speed is the primary reason. Atomic structures are slightly slower than their traditional counterparts when only a single thread is using them (the best case scenario), but quickly make up for this in multithreaded programs.

Mutexes, by definition, are mutually exclusive. Only a single thread may hold one, and any additional threads trying to get it have to get in line and wait their turn. Now, doing something with a data structure inside a mutex doesn't take that many cycles (I'd estimate about 500, if a memory allocation is required), but that's still completely dead time.

The real killer, however, is the possibility of going into wait. Suppose A holds a mutex and B wants that mutex. If B is lucky, it's running on a different CPU, and spinning a bit (up to 500 cycles) will succeed in waiting A out. But if there's only a single processor, spinning is out of the question. Worse yet, A could have its time slice expire inside the mutex, and now B will have to wait tens or hundreds of thousands of cycles (which is way beyond any reasonable spin limit), prompting it having to wait on the mutex.

Once B has to wait on the mutex, any hope of a speedy trial is over. Once you give up the CPU, Gord knows when you'll get it back (even in the best case it will likely take more than 10,000 cycles). Even worse, if A gets preempted in the mutex, that causes two wait equivalents: one for A to get the CPU again, and one for B to get the CPU after A leaves the mutex. These problems only get worse if there's a thread C or D also waiting for the mutex.

So, what can lock-free structures do? Lock-free means, by definition, that at any given time, one of the threads attempting to perform an operation will succeed in a constant number of cycles that make up 1 iteration (atomic structures are implemented in AtomicCompareExchange loops). For the atomic stack, the simplest of the structures (because only a single iteration failure point exists), each thread that didn't get it on the first try will have to spin, in the worst case, x iterations, where x is the number of threads that have some CPU attempting an operation on the same structure at the same time. If my logic is correct, this can be solved to yield the formula that the total amount of dead time (dead iterations between all threads), in the worst case, is O(x^3), where x is the number of CPUs in the system. In the average case, only 1 or 2 CPUs will be attempting operations at the same time, which means 0 and 1 dead iterations, respectively. The other atomic structures are more complicated, and I'm not certain how to calculate the complexity of them in the worst case (math never was my strong suit).

In addition to being a dramatic improvement in dead time, there are some cases where threads absolutely cannot wait. These are mainly hardware-linked real-time threads. For example, one day BZ asked me for help with a problem he was having, where he needed to dequeue something from a shared structure in a hardware feeder thread (the thread fetches data for the hardware, and so has a very limited amount of time it can take to get that data). In this case, going into wait means death. That leaves only the possibility of lock-free (or, even better, wait-free) structures.

There is a stronger version of lock-free algorithms called wait-free algorithms. Wait-free algorithms provide an additional guarantee: that threads attempting an operation will complete that operation in the same order they started the operation (unlike lock-free algorithms, which only guarantee an upper limit on the number of failed attempts for a thread). However, wait-free structures are far more difficult to design than lock-free structures, which are already far more difficult to design than thread-unsafe structures. I only have an algorithm for a wait-free implementation of load/store with reserve.

Status Report

Atomic stack and atomic queue are complete, and working by my tests (although I've only tested it with a single thread, so some errors may not show up). Now I just need Merlin to proof-read them, then help me optimize them and figure out where to put memory barriers. In the mean time I'll get to work on: atomic set, atomic hash table, read/write with reserve variable template, atomic linked list, and atomic deque, possibly in that order.

Happy, happy nights ahead!

Perfect Nerd Evolution

So, Merlin finally got around to sending me a few articles I was looking for (actually about a week ago). A whole bunch of sweet stuff in there. Algorithms for atomic, lock-free (thread-safe without the need for a mutex/read-write lock) stacks, queues, linked lists, deques (double-ended queues), sets, hash tables, even a memory allocator. As well as algorithms for load/store with reserve (you read a variable, make some change to it, then write it back only if it hasn't been modified since you read it; if it's been modified, you start from the beginning again) on arbitrary variables (even structures larger than one processor word). Naturally I'm planning to add all/most of this to LibQ (we'll see if that ever happens).

So yeah, it's awesome. And to think I thought it was kinda pathetic when Merlin was going nuts when he found this stuff a year or two ago. I guess you can get more nerdy over time.

Incidentally, the title is a reference to The Wallflower (AKA Perfect Girl Evolution). A candidate title was Plato Lives (that's an inside joke; hopefully at least one person gets it).

Why the AVI?

So, I've had a couple people question (well, okay, it wasn't really 'questioning'...) my choice of video file formats. For those too lazy to look, the format I ultimately decided on was Microsoft MPEG-4 v2 video and MPEG Layer-3 audio in an AVI package. This was actually the product of quite a bit of research.

Being the compatability nut that I am, I first and foremost wanted a single format that both Windows and OS X could play out of the box. I looked at the list for Windows XP, the Windows Media Codecs Download Package 8.0, QuickTime, and this page. A few different possibilities showed up. Of the possibilities, MP3 was the obvious choice for audio.

For video, the choices are much more limited. QuickTime supports a fair variety of formats, but not that many than Windows XP also supports. By far the best option of the video codecs was ISO MPEG-4, supposedly supported by both. However, trying this out produced a rather ugly bug in the Windows ISO MPEG-4 codec - the codec only works when running as an administrator. I don't know the exact reason for this, but I suspect it has something to do with accessing restricted registry keys. In any case, ISO MPEG-4 was out. Failing that, I tried Microsoft Video 1; this proved far too poor quality to consider using. It was about this point when I realized that I wasn't going to find a single perfect format that works on both out of the box.

So, I applied a bit of market logic to the problem. Windows has something like 90% market share, OS X less than 5%, and Linux less than 5% as well. That made the decision pretty easy: whatever format I used had to work in Windows out of the box. I did some asking around, and found out about Windows Media Components for QuickTime. This seemed like the best available solution to the problem - run on 90% of computers out of the box, make the other 5% download a plug-in to work with the format.

Once this was decided, MS MPEG-4 became the obvious choice for the video codec. I would have used version 3, but the encoder I'm using - mencoder (with the libavcodec library) - doesn't support this.

The choice of container was semi-arbitrary. My first choice was the MP4 container, but Windows can't play that out of the box. So, I went with the old, reliable AVI.

So, that's the story; not a whole lot to it.

Forgot to Mention

Here's a little physics quiz for you: when is more energy less energy? I actually have a topic to write about involving the answer to this question; we'll see if it gets added to the list of things I plan to write about and never do :P

& More Trophies

Oh yeah. This time I've got the good stuff. Well, some of it (mostly the stuff I didn't do) more than others. Let's go through these from worst and/or least interesting to best.

First up, a demonstration of a basic step sparring combination - StepSparring.avi

Next, me breaking four boards with a jump side kick - Break2.avi; I actually was expecting to have to do five boards with a step-behind side kick, but this is what they wanted, instead. When I was getting this off the video camera, I was pretty depressed about my obvious grace (or lack thereof), until I saw that neither of the two instructors did it that much more elegantly than I did :P

Me breaking three boards with a turning kick - Break3.avi

Me breaking three boards with a punch - Break1.avi. Looking at the video, I don't use my waist as much as I should, so there's some extra power to be gained, there.

My instructor breaking four brickish things with a side kick - 4BrickBreak.avi. This would technically be considered a speed break (which is harder than other types of breaks for the same number of boards/hard objects), as neither end of the bricks is really secured. This requires dramatically greater speed to do than normal breaks, because the thing you're attacking is free to move away from you, distributing the impact over time; the only thing holding it in place for you to break is inertia. This instructor is a fourth degree black belt; he was planning on testing for fifth degree this test, but his wife wasn't ready to test for fifth degree, and asked him to wait for her.

The aforementioned master instructor (or is seventh degree considered low grand master? I'm not sure) breaking seven boards with a back kick - 7BoardBreak.avi. It wasn't caught on camera, but if you'd been at the test, you would have seen me rapidly back away from the breaking area when he got up and started walking in that direction :P

& Trophies

And I'm back from the black belt test. Not exactly the portrait of the ideal martial artist, but I passed, which is what's important for the moment. Got some nice trophies; at least, they should be nice. My dad video-taped part of it, and took still pictures for other parts. Unfortunately, the digital camera he was using for the still shots doesn't really take pictures at a precise time (you can't expect it to take a picture within like 1/10 of a second after you press the button), so he wasn't able to get too many good still pictures; the slow shutter speed of the camera made for some sweet motion blur shots, though. I'm posting the four best still pics right now; none of them are of me doing anything (although you can see me holding boards in a couple of them):


Awesome motion blur (the best of the 42 pics, in this regard). This is a four-corner break, where you do four separate attacks in quick, fluid succession, and usually with less boards than you'd do with each attack individually; this is a front snap kick with one board. I'm the one holding the board she's kicking.


Another person's four-corner break; side kick with one board. Again, I'm the one holding the board.


And another. Apparently this shot is the leg returning to the floor after breaking two boards with a side kick. By this point I was taking a break from holding, between the twice I got kicked in the fingers by one woman, and the fact that I'd just done my four-corner break and power breaks (several individual attacks with lots of boards).


Three board power break with a middle knife hand strike. Both holders have pretty pathetic looks on their faces :P

I don't yet know how the video turned out; it looks like it's gonna take a fair bit of work to extract video from this thing with it's A/V out and encode it, and I don't really have the time to spend until like next weekend. But if it turned out well, there are three clips I want to post online: me breaking three boards with a punch, the master instructor (the 7th degree I mentioned last post) breaking seven boards with a back kick (awesome), and another instructor (the one who teaches at my school, 4th degree) breaking four bricks with a side kick (pretty cool looking).

& Stress

So yeah, that title pretty much says it all. A short summary of the coming week (and last couple days) for me:
- Turned in a programmingish assignment Tuesday
- Have another programmingish assignment due Thursday (not too bad)
- Have a history report to start and finish by Monday (not too good)
- Have a cumulative biochemistry test on Wednesday (bad)

So, all in all that's not too good. But that list in and of itself isn't sufficient to give me this psychosomatic stomach flu I've got right now. No, that requires the test for third degree black belt I have on Saturday (3 days from now). I only found out I was eligible for it on Monday (2 days ago), and that was around the time this stomach flu started.

This is a pretty big deal, at least for me (given a bit of history). I've been a second degree for 6 years now. Most of this is due to me simply being too lazy to put too much effort into it the last 3 years (most people are eligible to test for third degree after 3 years of being second degree, but this was after I started college, and I didn't really feel like I ought to test).

Last October (black belt tests are every 6 months) was really the first time I actually wanted to test for third (and actually put effort into getting ready for it), but I wasn't allowed to. Basically, the reason for this was that a lot of big names in the school were planning to test in two days from now (the teacher and his wife, as well as two other teachers, were going to test for fifth degree, and another student was going to test for fourth degree), and the teacher wanted me to wait and test with all the others.

The other reason was that I didn't pre-test the test before that. That normally wouldn't have been significant (I had pre-tested way more times than I needed - five - before that). What happened was that the school was sold to a new teacher a bit before that, and he wanted me to pre-test for him before finally testing for third.

So, that was pretty disappointing. Anyway, I'm testing now, and way more freaked out than I should be. The test will consist of six parts: patterns, terminology, sparring, board-breaking, step-sparring, and self-defense.

Patterns (called 'katas' in another martial art - I think karate) are sort of dances of sequences of martial arts moves (I'm being really vague here because lots of different martial arts have them). Besides being neat-looking, these are used to practice the moves in them. To do a pattern well requires that you have both strength and good (elegant) form in all the moves. Some various other things are attached, as well. Each pattern has some historical meaning, and may have some metaphorical parts to it (for example, one common metaphor is to end a pattern with a left-handed attack to symbolize the unfortunate death of the person the pattern is about). For a full test you're supposed to know all patterns up through your belt level (a total of 15, in my case)

Terminology is basic memorize and recite. You need to know the meanings of all the patterns for your belt level (and the meanings for all the lower ones, if your instructor feels like asking you them). In addition, you also have to know a bunch of Korean (in this particular instance) words, such as all the names of the moves and objects and events in the school, counting to 50 (in Korean), etc.

Sparring and board-breaking are pretty obvious, not to mention enjoyable (sarcasm). I'll probably have to break five boards with a side kick, three boards with a punch, three or four (at least I hope not five...) with a back kick, and two boards with a reverse hooking kick. Or, if I'm really lucky, it won't be boards at all; the teacher has been playing around with bricks and ceramic roof tiles (these tiles are curved, making them much stronger than they would be if they were flat, and several times stronger than boards) the last couple weeks...

I should mention that these are stock boards (10" x 12" x 1/2" slices) taken from the nearest Home Depot (or comparable store). They may be picked over so as to not use pieces with knots (unless you're unlucky...), but they're not treated in any way to make them brittle. I had the unpleasant experience once of being one of the holders for the highest ranking student (not grand master) in our school (was sixth degree at the time, now seventh) - 7 boards with his specialty - a jump back kick. Seven boards is a fair bit more than you can get your fingers around, which was actually a good thing, considering basically my entire palms got bruised from that :P (for those wondering what that looked like, there were two of us that actually held the boards, and four people who held our wrists, for reinforcement)

Step-sparring and self-defense are more or less canned counterattack combinations for common scenarios. These are responses either to attacks (step-sparring, where usually the attack is a punch) or someone grabbing/restraining/choking you (self-defense). Unlike much of the stuff in martial arts (at least in modern, sporty martial arts), these are intended to seriously injure or incapacitate somebody, using such things as strikes to the neck, attacks to the groin, or breaking of joints. You don't practice these at full strength :P

So, that's the basic rundown. And now I'd better be getting to bed; I have a lot to do this next week :P

Kids (and Computers) Say the Darndest Things

The last day or two I've been working on the successor to Trans-Roman Alpha (I should blog about this, sometime...): Trans-Roman Beta. Well, so far all I've done is play around with algorithms some; one algorithm in particular reads in an amount of text in some actual language, learns the rules of how that language constructs words to the best of its ability, and then generates random gibberish that imitates the language it was fed.

In addition to the practical value of this algorithm, it's also good for laughs. Initially I fed it the English translation of War and Peace, but it often ended up in infinite loops, using that as its data set. So I decided to feed it an English dictionary, instead. That allowed it to generate a wide variety of gibberish, sometimes actual English words, sometimes humorous words, and sometimes neither of those. Below is a list of some of the ones I found amusing, from a total of 50,000 characters it generated (keep in mind that this is random with regard to each character generated):

goatempts curvaccidatodgy zeppasmo almly zookelpful quinedibly votrepinabitized czarskiing qweryphs zuccon xercococcur forkplay fruckage beepfat qualmly wussyfoo gluejew qwerbage weenie feelworldvic vyingfishpad squettled jarfed clatchfin owlywed xylorying frazziest pornumb bromsdam sunkyard fryingpie menhand xersnigget twirlifted gyroite yowlywed zomboide gagiosex knivie runtnest fobbyhoe dogey glasmanly ptoriery

I've also noticed that this thing suffers from occasional dictionary poisoning. That is, it'll see some odd word once ('qwerty' comes readily to mind) and it'll start using structures from that word all over the place, even if no other word in the dictionary uses said structures (for example, it became quite fond of starting words with 'qwer', despite the fact that 'qwerty' is the ONLY word in the dictionary that has this). So, I guess in a way this is like having a little kid :P

Incidentally, 'xersnigget' might be my all-time favorite "word".

My Program Is Mocking Me...

FusionReactorII says:
Ah crap
FusionReactorII says:
That won't work
FusionReactorII says:
Well, it works for generating random text. But it won't work for Trans-Roman Beta, because it needs to be reversible
Josh says:
heh
FusionReactorII says:
I wonder what would happen if...
FusionReactorII says:
LOFL
FusionReactorII says:
That totally broke it
FusionReactorII says:
You've got to come see what it generated (because it broke)! That's absolutely hysterical!
Josh says:
sec

Windows Internals Curriculum Resource Kit

I've just found something godly: the Windows Operating System Internals Curriculum Resource Kit by Microsoft. It's basically a university course on Windows internals, complete with lectures, labs, quizzes, homework, etc. The material seems to be derived from a number of wildly popular Windows system and internals books, and adapted into a university course by a pair of professors; Microsoft then licensed the material and is distributing it free.

There's even a lecture comparing and contrasting the Windows and Linux kernels.

Now go! Fetch!

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.

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

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

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!

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.

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...

& 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).

Mwahahahaha

Mega Man X Collection acquired. Happy, happy nights ahead!

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.

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.

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?

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.

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.

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.

& 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).

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!

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.

What a Pain

One of the things I got for Christmas was the Memoirs of a Geisha soundtrack. As with all my other CDs, I immediately wanted to rip it for my MP3/Ogg collection. This sounded simple, but ended up being rather unpleasant.

The first sign of trouble came when AudioCatalyst couldn't calculate checksums for the tracks. Looking at the manual, the reason this would occur is that there wasn't at least one frame of silence at the beginning and end of each track. One thing this may mean (which is what I initially suspected) is that the tracks are not discrete, but transition directly from the end of one track to the beginning of another, with no inter-track delay (the Gladiator soundtrack did this, just to name one prominent example). This is troublesome because it's difficult to perfectly mimic this in lossy audio formats, as well as that it sounds bad when you play the tracks on shuffle (like I do).

Well, the real reason turned out to be even more annoying. A quick look at the tracks revealed that there was noise at the beginning and end of each track; but even just looking at the waveform, it was oddly shaped noise. The frequency graph confirmed what I'd suspected from looking at the waveform: there was a prominent spike at an upper frequency, embedded in otherwise brown noise; further investigation revealed that this spike was centered at 15,733 hz. At the beginning and end of tracks (it fades out in towards the center), this peak stood about 50 db above that of the surrounding noise.

While this spike was only present at the beginning and end of the tracks, I soon found that a different spike was present throughout most of the track. Some careful isolation revealed that this spike was centered at 15,700 hz. The intensity of this spike varied anywhere from 14 to 27 db, and may be different intensity on the two channels.

The 15,700 hz spike I managed to dispose of, by means of manually performing notch filters on each track. The 15,733 hz spike, however, I left, as it would be a pain to deal with, only at the beginning and end, and it's not present during most of the tracks.

So, now that we know what these spikes (hums) are, why are they there? Unfortunately, I don't know the answer, though I can think of a number of possibilities. It could be the hum of some piece of equipment in the studio, during the recording of the music (though I've never encountered this kind of thing before); I'm told that power supplies could produce hums in this frequency range. It could also be some sort of resonance with a stray instrument or item in the studio, causing it to vibrate and amplify those particular frequencies. Finally, it could be some kind of watermark or rip-protection system; if it was the latter, I could test for it by recording the music directly from my stereo (a significant amount of work, considering that the stereo's in a different room than my computer), but I don't really have any way to test the first.

So, there's Q's unsolved mystery of the week.

Q's Do-It-Yourself Anime Christmas

Yeah, so that title kind of sucks. What it's supposed to mean is: what anime/manga (note the glossary at the end of the post) Q recommends you get yourself for Christmas (and would consider them all worth the money).

Ai Yori Aoshi (manga & anime). A "guys'" love story about two rich (before the guy ran away from his home, that is) kids betrothed to be married, and trying to get along living together (and, of course, plenty more female characters that love the guy as well). Lots of humor, an amusing story, and typical Japanese ecchi* (though not hentai). I originally started watching this series because it sounded similar to one of the stories I wrote; this similarity ended up being pretty shallow, but I still liked the series a lot.
Azumanga Daioh (manga). Awesome comedy series about the daily life of a group of... unique Japanese high school girls, and their equally unique teachers. There's also an anime version, but I don't consider it near as good, as the conversion from the comic strip format of Azumanga Daioh to anime is quite poor.
Elfen Lied (anime). An extremely vicious diclonius (a two-horned human subspecies, with a number of invisible arms - vectors) escapes from a research facility that has been experimenting on her (and other diclonius) for years. A second, infantile personality develops, allowing her to live peacefully with a boy and his cousin, until the research facility attempts to reclaim her, and her original personality reappears. Primarily drama and action (with very graphic violence), but also a good amount of comedy, and ecchi. There's also a manga, which covers almost twice as much material as the anime, but it has yet to be released in English (and fan translator groups have only gotten about 1/4 through translating).
Full Metal Panic (manga and anime). An elite mercenary (raised in war zones worldwide) has difficulty adjusting, when he is sent to live the life of a Japanese high school student while protecting a female student from a terrorist organization. Best for it's comedy, but also a moderate amount of drama. Can occasionally be ecchi.
Great Teacher Onizuka (manga and anime). None-too-bright biker gang leader turned teacher takes on the school's most delinquent class, and proves that he can do a better job teaching with his brawn and heart than the other teachers can do with their ivy-league diplomas. Comedy and drama, with a bit of ecchi. The manga is almost twice as long as the anime.
Love Hina (manga). The lord of ecchi (more than my taste, actually, but it has more than enough good stuff to make up for it). The story of a boy (attempting to enter Tokyo University, the most prestigious college in Japan) who inherits an inn turned girls' dormitory from his grandmother. In this process he develops various relationships (of various natures, and only one of them ending up being romantic) with the girls in the dorm. Hilarious comedy, as well as drama, and a bit (okay, maybe more than a bit) too much ecchi. There's also an anime, which contains some material not in the manga (although the reverse is true, as well), but I don't like it as much as the manga (although I do prefer the ecchi-light of the anime, which is the one I saw first).
Noir (anime). A pair of assassins make their services available for hire under the name of 'Noir', but soon discover that the name was already used by an ancient secret society. An interesting and amusing series (primarily drama), though things sort of start to suck near the end.
Rurouni Kenshin (manga and anime). Fictional story set in historical Japan (around the 1860s) and anchored around real events and people. Kenshin, a legendary assassin/warrior from the Meiji Revolution (a fictional character, although inspired by the real Hitokiri Gensai from that time) vowed that after the revolution he would no longer kill, but find another way to continue to help the people of the world. So, he wanders from place to place, doing what he can, using his legendary swordsmanship and sakabato (a reverse-bladed katana, where the normal cutting blade is merely a blunted edge, and thus cannot be used to kill). Primarily drama, with a good dose of comedy. I'd consider the manga better than the anime, although both contain material not in the other.
School Rumble (manga and anime). Kenji (male) enters high school with a proud reputation as a delinquent, and has his eyes set firmly on Tenma (female). Tenma, however, is too thoroughly smitten by Oji (male) to notice; Oji also seems to be pretty clueless in general, let alone about her interest in him. Primarily comedy, some drama.
Stars (Seikai) Trilogy (Crest of the Stars, Banner of the Stars, Banner of the Stars II; manga and anime). A sci-fi series about a noble human boy entering the Abh (you just know the original design concept was 'blue-haired elves in space') military, where he becomes a friend of an Abh princess also in training, who commands her own small ship. Ultimately, a war breaks out between human and Abh, which they must participate in. War, culture clash, growing up, falling in love, etc.; primarily drama, but some comedy (and it's rare for the Japanese to not throw in at least a tiny bit of ecchi for good measure).
Yotsuba &! (manga). Another hilarious comedy series by the author of Azumanga Daioh, about an exuberant (and rather psycho) little girl, enjoying life to the fullest.

Glossary:
Anime: Japanese "cartoons". Unlike American cartoons, anime may be for any age group, and may, in the extreme case, be pornographic.
Ecchi: Kind of like 'risque' or 'lewd'. Anything from panty shots to actual nudity (in Japan this is acceptable material for network television).
Hentai: Animated pornography (note that nudity alone is not sufficient to call something hentai).
Manga: Japanese "comics". Again, may be made for any age group, and may even be pornographic.

& Debates - Fidelity

This one (registration required) is actually not one of my debates, although it's a timely topic that was brought up in another thread (and thus I'd been thinking about it, as well):

So this is the place to discuss serious matters. I love it.

Anyway, I also have something that I'd like us to talk about. Throughout the generations, we're taught that once one reaches a certain age, one marries, has children and continues to live on, without thinking much about it anymore.

At the center of all of this lies fidelity. When you're in love, you can't imagine ever wanting someone or something else. But I've been thinking about this for most of my adolescent life, and even though I am romantic and I really want to believe in eternal love and faithfulness, I think fidelity is against human nature. And that love and desire sometimes go hand in hand, but that they're not one and the same.

Please do not think that I'm pleading for adultery here, I just want to know what you think.

Q1 Register Set

As mentioned previously, the Q1 has 32 32-bit general purpose registers, as well as the instruction pointer, instruction register, and various flags. I've adopted the MIPS register naming convention (registers 0-31 being $0 to $31), because it elegantly allows the use of register nicknames: aliases for certain registers, based on the designated function of the register (we'll come back to this in a couple paragraphs).

Of these 32, 31 are truly general purpose - the software can do anything it wants with them, and the CPU doesn't care. Register 0, however, has a very special purpose: it is the zero register (a concept I read about in the MIPS architecture, and found particularly useful). The zero register always contains the value 0, regardless of what is written to it; this allows the value 0 to always be available to the program, as well as allowing unneeded values (such as the result of subtraction, when all you really care about is the value of the flags - for a conditional branch) to be discarded without overwriting another register.

$31 is nicknamed $ra - the return address. This register is supposed to hold the return address for the current function (at least when the function returns). If the function calls other functions, it must be sure to save and restore its own $ra. As with all the registers that follow, this is not a hardware restriction (as it was in the case of $ra on MIPS), but a software convention that should be followed so that all code remains compatible.

$30 is $sp: the stack pointer. As previously described, the stack is a software structure on Q1; however, as it's integral to the operation of functions, it must be standardized. As with MIPS, $sp always points to the NEXT available stack location (rather than the first occupied stack location, as with x86).

$29 is $gp: the global pointer. This is more of a reserve for function use. Well-behaved Q1 programs should not hard-code the addresses of their global variables. Rather, they are expected to, should they need to access global variables, construct a pointer to their global variables by adding a (negative) offset to the instruction pointer (which can be obtained with the LRA - load relative address - instruction). The global variables can then be accessed through $gp + offset. This variable is nonvolatile; if a function uses it, it must save and restore the previous value, so that it does not overwrite the previous function's $gp.

$2-$5 are $p0-$p3: the first four 32-bit (or smaller) parameters passed to a called function. On return, $2 is $rv: the return value (if the function has a return value of or less than 32 bits).

$2-$15 are also $v0-$v14: the volatile registers. Functions may use these registers however they like, without regard to saving previous values. Thus, if a function needs a value preserved while calling another function, it must either use a different register, or save the value on the stack. These registers allow for functions to do short-term calculations (where the intermediate values are inconsequential, and may be overwritten, and only the end result is important) without the need to save registers on the stack.

$16-$25 are $n0-$n9: the nonvolatile registers. Functions may use these functions however they like, but must save and restore the previous values of any registers they use. These registers are thus saved across function calls, and may be used to store values needed after the call, without the need to save the registers to the stack.

Having both volatile and nonvolatile registers allows for best-of-both-worlds optimization. Intermediate values that will not be needed more than a few instructions later (and not across a function call) can be placed in the volatile registers, and no prolog or epilog code is needed to clean them up. On the other hand, important values can be placed in nonvolatile registers, where cleanup overhead is only needed if the called function actually uses the registers (a probability that is decreased by the fact that the volatile registers are available for quick computations).

The remaining 4 registers are reserved, at this time. The register set isn't 100% final, and I may yet find a use for them.

Asynchronous I/O - Emulation Plan

One of the really cool things I have planned for LibQ is an emulated asynchronous I/O server. This server emulates asynchronous I/O either on systems that don't support it natively (like Windows 9x) or on data sources that operate synchronously. This latter item, in particular, is useful, because it allows you to add on asynchronous I/O support on almost anything (for archive file libraries, for one example).

The basic design of CAsyncServer (a singleton) is pretty straightforward. It maintains two thread pools (and separate request lists), which function almost identically: dequeue a request from the request list, perform the operation synchronously, perform the completion notification, then grab another request, sleeping if none are available. It's very straightforward.

The first thread pool is exactly what you'd expect: a pool for issuing calls for file system files (things you access directly through the operating system). As all of these are exclusively I/O (save for the bit of processing overhead required for each call), the size of this pool is capped only at a large number of threads (something to prevent the system from getting swamped by huge numbers of threads), and all of them execute in parallel. If the list of outstanding requests becomes too long, the dispatcher will spawn another worker thread for the pool.

The reason that there are two pools is due to the fact that CAsyncServer is intended to also work as a server for things other than file system files. One thing I plan on using it for is QuarkLib, the library for Quark, my archive file format. In this case, most operations will require a moderate amount of CPU, as most data will be compressed. If you tried issuing a bunch of operations like this on the first thread pool, with a sky-high limit on the number of concurrent threads, the entire system would grind to a halt. The second thread pool, then, is limited to a small number of threads (around the number of CPUs in the system, give or take). While there may be some waste due to file system access, this will ensure that asynchronous I/O server won't strangle the entire system.

& More Infatuation

Just finished watching Elfen Lied, again, and I still like it a lot. Grabbed a beautiful new desktop from it, too. Again, if you can get your hands on it (and can stomach the gore), go watch Elfen Lied.

& Debates - Truth and Fiction

The latest installment (registration required) in Q's never-ending supply of debating material, and this one's a whopper:

So, I've got this thing called a-p mail that I invented for one of the stories I'm writing. That's anonymous private mail: an e-mail system that allows a piece of encrypted mail to be routed on a public network from a sender to the intended recipient (which the sender must know) without the mail server ever knowing the identity of either. This is not to be confused with something like an Onion network, which can act as an anonymous, untraceable proxy server; this is a method of getting an e-mail to the intended receiver without so much as an e-mail address to identify the receiver.

This is something I invented from scratch; while I don’t know that no one else has thought of it before, I can say that I have no knowledge of anyone else ever implementing or considering this method. This brings up the question of whether I should look into patenting it.

However, if nobody has considered this method previously, a question of ethics arises. This method was invented as a means of secure and anonymous communication between terrorists and other underworld persons, and could, if introduced to the real world, be used just the same. Assuming nobody else has publicly described the method, would it be ethical to bring it into the real world?

Not Quite Idle

Well, since the last few posts, I haven't been completely idle. I've been (from time to time) researching possible solutions to the distortions in a lot of the Mega Man 6 music. This has been complicated by the fact that I'm not that good at math (at least not anything at or above calculus). Right now I have some ideas that sound promising, but I'll have to try them before I post about them.

& Debates - Propaganda?

My latest debate topic (registration required):

As part of an information offensive in Iraq, the U.S. military is secretly paying Iraqi newspapers to publish stories written by American troops in an effort to burnish the image of the U.S. mission in Iraq.

The articles, written by U.S. military "information operations" troops, are translated into Arabic and placed in Baghdad newspapers with the help of a defense contractor, according to U.S. military officials and documents obtained by the Los Angeles Times.

Many of the articles are presented in the Iraqi press as unbiased news accounts written and reported by independent journalists. The stories trumpet the work of U.S. and Iraqi troops, denounce insurgents and tout U.S.-led efforts to rebuild the country.

Though the articles are basically factual, they present only one side of events and omit information that might reflect poorly on the U.S. or Iraqi governments, officials said. Records and interviews indicate that the U.S. has paid Iraqi newspapers to run dozens of such articles, with headlines such as "Iraqis Insist on Living Despite Terrorism," since the effort began this year.

Los Angeles Times (found via Mac's blog)

So, couple questions for debate. First, is this propaganda, when it's factual? And in either case, is this acceptable practice (not poor ethics)? If yes, how do you handle the fact that the stories lie about their authors? If no, what do you have to say about the fact that the citizens would be less likely to trust (factual, in this case) news from the US-promoted government?

AMD Opteron Architecture

Dark_Brood found me an amazingly detailed site with more than you ever wanted to know about the Opteron architecture.

Spoils - UPDATED

Just a couple of the tracks I've extracted (and had time to edit and encode):

http://www.campaigncreations.org/starcraft/mpq2k/Misc/data4.aif_0083_E4C2E552.ogg
http://www.campaigncreations.org/starcraft/mpq2k/Misc/data4.aif_0084_3FD54DC5.ogg
http://www.campaigncreations.org/starcraft/mpq2k/Misc/data4.aif_0089_85EE44B9.ogg

UPDATE: Reuploaded the new files, after recompressing them in standard quality mode, so they should be significantly better quality.

Vorbis Bad!

Well, this isn't a happy discovery. While editing the music from Mega Man 5 (to archive it in my library of game music), I discovered that Vorbis was destroying the upper frequencies of the tracks at 70 kbps (I set it to encode at 80 kbps, as they're all mono, but for some reason on MM5 it decided to use 70). Take a look at the results:

The original track, after ADPCM decompression:


The same track, after Vorbis compression at 70 kbps:


The track at 80 kbps (forced by reducing the range of allowable bitrates):


The track again, at 96 kbps:


UPDATE: Hmm. Looks like this is actually only a problem when not using standard quality mode (was using average bit rate mode before). In other news, lots of Mega Man 6 music is recorded at high volume, and noticeably distorted. Maybe I should send an e-mail to Capcom...

Little Change to Asynchronous I/O

I've decided to make a slight change to how LibQ handles one of the three methods of completion notification. Instead of using a CEvent to notify the application of I/O completion, the new method internalizes the waiting process. Practically, instead of waiting on a CEvent you specify when the you begin the I/O, you'll now wait on the CAsyncStatus for the I/O, itself (this requires that the operation be marked as waitable, when initiated).

There are a couple reasons for this. First, it should be a little faster on POSIX systems, due to more direct OS support. Second, it will allow timed waits on I/O completion (remember that timed waits could not be implemented with the CEvent on POSIX, due to technical difficulties).

A third benefit, although I don't know if I'm going to even do this, yet, would be that it allows the possibility of waiting for multiple waitable I/O operations at once, returning when one of them completes (or the timeout expires). However, due to incomplete OS support, this might be slower than desired.

& Debates - Pornography

My lastest attempt (registration required) to incite flame wars for my own amusement:

From Social Psychology, eighth edition (my social psychology text book), by David G. Myers, pages 399-400:

Evidence also suggests that pornography contributes to men's actual aggression toward women. Correlational studies raise that possibility. John Court (1986) noted that across the world, as pornography became more widely available during the 1960s and 1970s, the rate of reported rapes sharply increased - except in countries and areas where pornography was controlled. (The examples that counter this trend, such as Japan, where violent pornography is available but the rape rate is low, remind us that other factors are also important.) In Hawaii, the number of reported rapes rose ninefold between 1960 and 1974, dropped when restraints on pornography were temporarily imposed, and rose again when the restraints were lifted.

In another correlational study, Larry Baron and Murray Straus (1984) discovered that the sale of sexually explicit magazines (such as Hustler and Playboy) in the 50 states correlated with the state rape rates, even when controlling for other factors, such as the percentage of young males in each state. Alaska ranked first in sex magazine sales and first in rape. Nevada was second on both measures.

When interviewed, Canadian and American sexual offenders commonly acknowledged pornography use. For example, William Marshall (1989) reported that Ontario rapists and child molesters used pornography much more than men who were not sexual offenders. An FBI study also reported considerable exposure to pornography among serial kills, as did the Los Angeles Police Department among most child sex abusers (Bennett, 1991; Ressler & others, 1988).

Although limited to the sorts of short-term behaviors that can be studied in the laboratory, controlled experiments reveal what correlational studies cannot - cause and effect. A consensus statement by 21 leading social scientists summed up the results: "Exposure to violent pornography increases punitive behavior toward women" (Koop, 1987). One of these social scientists, Edward Donnerstein (1980), had shown 120 University of Wisconson men a neutral, an erotic, or an aggressive erotic (rape) film. Then, the men, supposedly as part of another experiment, "taught" a male or female confederate some nonsense syllables by choosing how much shock to administer for incorrect answers. The men who had watched the rape film administered markedly stronger shocks, especially when angered with a female victim.

In a sidebar on page 400:

Repeated exposure to erotic films featuring quick, uncommitted sex also tends to

• decrease attraction for one's partner,
  
• increase acceptance of extramarital sex and of women's sexual submission to men, and
  
• increase men's perceiving women in sexual terms.
  

(Source: See Myers, 200)