Musings on the MoPaQ Format

So, Q survived finals and term papers, though not unscathed. Now for something completely different, and pseudo-random.

A couple weeks ago, BahamutZero and I were talking about the MPQ file format. I can't remember exactly what we were talking about, but he mentioned that it didn't seem all that good. It occurred to me that while I'm probably the most knowledgeable person on the format outside Blizzard (excluding, of course, the author of the format, who no longer works for Blizzard), I'd never really formed an opinion on how good or bad it was in general. That gave me the idea to write a critique of the format - at least, of the more interesting things in the format - on my blog.

Hashing

One of the more distinctive features of MPQs is the way in which files are located within the archives. The standard method of finding files in databases and file systems is the B-tree or B+-tree. For databases, there is one tree for each index in each table; for file systems, each directory has its own tree. This allows for efficient searching (O(log N) disk accesses per lookup) and the ability to keep only part of the index in memory at any time. However, archive files are generally concerned more about optimizing size than speed (ACE being the extreme example), they may use something simpler, such as a sorted or unsorted array of filenames (and if unsorted, then it is possible to just store the filenames along with the file data, itself).

The MPQ format, however, opted for something more industrial-strength: hashing. Each MPQ archive has a single large hash table (an O(1) structure), containing entries for all (readable) files in the archive. Files are identified by two 32-bit hashes of the filename, a language code, and a platform code (what exactly this is remains to be seen, as it's still unused); the index is derived from a third hash of the filename. Note that nowhere is the filename itself.

You really can't do any better than this for the original purpose MPQs were designed for: to store read-only game data in a compact form that is both fast to access and fast to load. The use of fixed-size hashes (rather than the actual filenames) makes the size of archive data in memory optimal, and the hash table structure makes file lookups optimal. The format of the hash table (specifically, how unused entries are encoded) means that the size on disc could be further reduced by compressing the hash table (it isn't compressed on disc); presumably this was not done to make opening archives faster. Apart from that, the hash table has no real weaknesses for the originally intended purpose.

However, the hash table proves to be a pain for modders because of the lack of absolute filenames in the archives. This apparently became a pain for Blizzard as well, indicated by the fact that in Starcraft: Brood War (the third game/expansion to use MPQs), Blizzard added a separate mechanism not integrated with the hash table for storing the names of files in the archive.

These two things taken together, however, suggest one way in which the MPQ format could have been improved (besides a minor alteration that would have allowed the hash table to be resized; presumably Blizzard didn't see a need for this ability when creating the MPQ format). Rather than including the hash table in the archive format itself, Blizzard could have made the hash table a global, separate entity. That is, store the filenames in some simple structure in the archives, and have the installer/patcher code create a global hash table (containing files of all archives) which would be used by the archive accessing code; this could even be specialized, such as only indexing files of the correct language. This would reduce the in-memory overhead (although increase the total size on disc) as well as potentially decrease the search time for finding a file in multiple archives. It has the added benefit of removing that complexity from the format itself, and moving it to support code. If memory serves, Neverwinter Nights took this approach.

Language/Platform Codes

Another interesting design decision in MPQs was the choice of including support for different languages/platforms in the archive format itself. As briefly mentioned previously, files in MPQs are identified, rather than by filenames, by three hashes derived from the filename, a language code, and a platform code. When a game runs, it sets the language and platform currently running. The MPQ access code then looks through the archives for a file matching that description. If no such file exists, it performs a second search, using the same hashes, but using default language and platform codes (in practice, files identified by these codes are generally American English files).

While it's nice that Blizzard put some thought into internationalization, I tend to think this was something that could have been better implemented outside the archive format itself. It would have been just as easy to use a prefix or suffix on the filename for this purpose (e.g. "platform\language\filename" or "filename.platform.language"). Both of these could have been implemented completely in code.

Alternatively, had they used a global index, they could have simply included only files of the proper language/platform (or the neutral language/platform, if no specific version exists) in the index when it is built by the installer/patcher, without the need to modify the filenames at all.

Separate Hash and Block Tables

One detail about the hash table that wasn't previously mentioned was the fact that the hash table stores only some information about each file (specifically, only that already mentioned). Additional information, such as the file size and offset, as well as file modes and flags, is stored in the block/file table ('block' is more technically accurate, but 'file' better describes its intended purpose). The hash table then stores an index into the file table for each entry in the hash table.

This is something that is common in file systems - you typically have a file table, containing the basic info about each file's data, and an index (often B/B+-tree) of filenames that index into the file table. The obvious benefit of this is that the file table can be modified less frequently, and doesn't need to be completely rewritten every time there's a change in the directory structure. A second benefit is that it's possible to create hard links - multiple 'files' in multiple directories (or in the same directory with different names) that refer to the same physical file.

File Data Blocking

Another feature of the MPQ format that resembles a file system more than an archive format is the way it structures file data. It's generally beneficial, from a compression ratio perspective, to compress a data set as a whole (though compression libraries typically feature a mechanism to indicate when it's necessary to read more data or write out compressed data, so that you don't have to load the entire file into memory at once). However, file systems that support compression don't do that. As file systems must read and write entire sectors of data, file data is broken into chunks of some number of sectors, compressed as a single block, then written out, padding out to the nearest sector; if at least one sector cannot be saved by the compression, the compressed data is discarded, and the uncompressed data is used, instead (there no point having to decompress something when compression doesn't even reduce the size).

However, the MPQ format also does this, despite the fact that it does not pad out disc sectors. The reason is that there's a second benefit of blocking data in this way. When a block of data is compressed as a stream (a single entity), it can generally only be read likewise - as a stream, from beginning to end. That is, you cannot seek in compressed data. As seeking is an essential function in general file systems (and similarly in game archive formats), this constraint is unacceptable. Blocking is thus used to reduce the size of the blocks that must be accessed atomically. To read from an arbitrary point, you find the block containing the position desired and decompress it.

One last point unique to the MPQ format is that when files are blocked, each block may use a different compression algorithm, indicated by a byte prefix with the compression algorithm.

Single Block Files

Nevertheless, as mentioned previously, it's better from a compression (and possibly performance, as well) standpoint to compress files as a single unit. In most cases this would work for arbitrary data (the type that might appear in an MPQ), as many file types will be read once and then kept in memory. To take advantage of this, the MPQ format has a second mode of file storage (I can't recall off the top of my head when this was added. Possibly in World of Warcraft): single block compression. This is basically exactly what it sounds like: the entire file is treated exactly as a single block of data - compressed in a single go, and prefixed with a byte indicating the compression algorithm, just like each block normally is.

In theory (and at the level of the file format), this isn't any different from normal, non-blocked archive formats. The problem is really with the implementation (the code, to be precise). The implementor wanted an easy way to take advantage of improved compression by not blocking data, when seeking is not necessary, so decided to use exactly the same block decompression code as for blocked files - blocks are loaded into memory whole, decrypted, and decompressed all at once. The problem here is that it requires two buffers, and requires the entire compressed block to be read before anything can be decrypted or uncompressed.

ADPCM Compression

As mentioned, the MPQ format supports multiple compression algorithms. Currently, the PKWare Implode, Zip Deflate, BZip2, and Huffman encoding algorithms are supported. There's also one more that's more unexpected: the ADPCM algorithm. I briefly discussed ADPCM compression on the E Terra blog. It's a lossy format that compresses 16-bit audio samples down to 4 bits, giving 4:1 compression ratio, at a non-negligible loss of quality.

This is used for a compression mode typically referred to as "WAV compression". This mode is used for compressing sound effects and music prior to Warcraft III. The MPQ editor scans the WAV to import, and distinguishes blocks that contain only PCM data from blocks that contain anything else. Blocks containing only PCM data are compressed with ADPCM, the others are compressed with one of the lossless compression algorithms. This way, the game sees only a PCM-encoded WAV, though it had actually been converted transparently to ADPCM and back.

This is a pretty strange feature for an archive file format - at least, as a basic compression type. Especially considering that there are better formats for this that have higher compression ratios and higher quality (MP3 comes readily to mind), without requiring an alteration to the basic archive format.

I suspect the real reason for this design decision was historical. WAV compression first appeared in Starcraft (the same time support for different compression algorithms for each block appeared, by the way). Diablo, the only game to use MPQs before that, used uncompressed WAVs, played through several Storm.dll APIs. I suspect ADPCM was used to allow the existing Storm.dll streaming code to continue to work using the new compression algorithm. Though again, it's not a particularly good solution, I think.

Extended Attributes

The last feature worth noting is a system for adding new metadata attributes to files in MPQ archives that weren't included in the original format, which I've dubbed extended attributes. Extended attributes are stored as a file (conveniently named "(attributes)") in the archive consisting of parallel arrays of the extended attributes, each array containing one entry for each entry in the block table. The extended attributes in use at present (as of World of Warcraft) are CRC32, FILETIME, and MD5; an archive may contain any combination of these. Oddly, when Storm loads these extended attributes, it merges them with the rest of the fields in the block table, creating a single large table in memory.

This design decision has both advantages and disadvantages. Storing these in parallel arrays makes it, in theory, efficient to store, load, and access them when present, and ignore them when absent; however, the implementation peculiarity mentioned previously makes it slower to load them, with the benefit to slightly improve access (as it doesn't have to check whether they're all present each time you access them).

There are a couple disadvantages, however. First, as extended attributes are stored in arrays parallel to the block table, it isn't possible to exclude entries for files where you don't need that attribute, requiring more space if only some files need certain attributes. I suppose this is only an issue for the tables when loaded in memory, as, as the attributes file is compressed in the archive, unused entries can (have have been observed to) be zeroed, allowing them to take almost no disk space after compression.

The other disadvantage is that this system is not readily extensible. Because new attributes must be known by the MPQ library (for size calculations when processing the attributes file), it's cumbersome to add new attributes, as the MPQ library must also be updated to support them. This is even worse with regard to the fact that the block table mixing code and data must be updated correspondingly. It also doesn't allow for custom metadata at all.

Random Fact of the Day

Q is officially starting to panic.

Stuff to do this week (last week of school):
- Finish the class version of E Terra
- Start/finish video of something for school
- Start/finish term paper
- Study for and take 4 finals

Exercise for the Reader

Okay, here's one you can apply to your real, daily lives (well, some of you, anyway). When does throwing a stronger punch/kick (something along those lines) require using less strength/energy than throwing a weaker one?

No, there's no esoteric Zen metaphysics at work, here. Nothing but classical European physics.

Edit: Also, English is a bit ambiguous for the question. I'm asking when is it necessary to punch weaker in order to punch stronger?

Solution

The basic steps used in the link to find the distance between P3 and P are:
1. Calculate the distance between P1 and P
2. Calculate the exact location of P
3. Calculate the distance between P and P3

Now, a little common sense suggests there are two too many steps here. But we can't compute the distance between P and P3 directly, because at this point the location of P is unknown.

Yet there's a very simple solution: we rotate P2 90 degrees around P1 to create P2'. By definition the distance between P1 and P' is the same as the distance between P3 and P. This has exactly the same form as the version in the link, but it is able to find the distance between P1 and P' in the first step, instead of the distance between P1 and P. Thus we've eliminated steps 2 and 3 entirely, and use exactly the same math as before:
u' = ( (x3 - x1)(x2' - x1) + (y3 - y1)(y2' - y1) ) / ( ||p2' - p1||^2 )

A visual proof:


While understanding the way the distance is calculated using the dot product requires knowledge of calculus/linear algebra, deriving this improved equation from the original in the link is just trivial high school geometry. That's why it's neat.

Sucky Test Teacher Strikes Again

So, just got back the graded midterms in networking class (theoretical stuff), taught by the same teacher. Not surprisingly, it was disappointing. As before, this guy could teach a class on how not to write (and grade) tests. Among smaller gripes were two main things:

1. One question (in particular) was taken straight out of the book, and was fairly simple. What could go wrong? Well, giving the same answer to the problem as in the book got you a wrong answer on the test (and no, it wasn't an essay question where theoretically he could expect more detail).

2. Throughout the semester (there's one week left), whenever math was used, it was exclusively high-school-level math (basic algebra and such; there was one area under the curve problem, but as the "curve" was a line, it could be calculated with basic algebra). Neither the book, the lectures, nor any homework has gone beyond that. So, what does he do? He puts a calculus question on the test, and makes it worth 25% of the test (note that calculus is not a prerequisite for this class; I wonder if he could get in trouble with the dean for this).

Ultimately, Q got (like always, although it's always hard to believe in classes with this teacher) an A on the test. I don't know what the exact ranges for grades are, but I talked to one person who got an A- for 58%, and rumor has it that one person got a C for 18%.

Which brings me back to what I said in the previous post about this guy: CURVING THE SCORE DOES NOT MAKE UP FOR A HORRIBLE TEST.

Exercise for the Reader

Oh no, not another one of Q's easy but slightly tricky quiz questions. Today it's regarding finding the shortest distance between a point and a line. This explains the theory behind it, and how to calculate it.

But if you are only interested in the distance between P and P3 itself, and you don't care what P is, this math is moderately wasteful, as you have to first find P, then calculate the distance between P and P3. Surely there must be a way to calculate the distance without ever calculating P. And in fact, there is.

Find it, without cheating (looking up the answer online of through friends. It's actually pretty easy and simple. I just thought it was kind of neat.

& Insanity

*evil, maniacal laughter*

No, that's not me starting to panic about E Terra and deadlines (although I am starting to panic about E Terra and deadlines, as indicated by my physical stress symptoms that are starting to appear). Let's just say that I'm very pleased with my class schedule and related things, and gloating without being able to say exactly why.

Happy, happy months ahead (and at least one very stressful month)!

World Without Windows

Okay, so that title is a bit misleading. Anyway, this post hopes to provide some meaningful answers to the question: what would the world be like if the overwhelmingly dominant operating system was secure in ways that Windows is not. For the purposes of this discussion, I'm defining "secure" by several criteria:
1. All users run as limited users - they can't do administrative tasks or screw with the OS without explicitly logging on as admin or running a program as administrator (e.g. Windows run as or Unix sudo)
2. The system is fully isolating with respect to users - one user may not access another user's data without explicit permission
3. There are no privilege escalation exploits in the OS - tricks that limited users could use to gain administrator privilege without having to enter the administrator password
4. There are no remote exploits in the OS itself - in the kernel, standard drivers, basic services, etc.

So, we have this idealized, nonexistent operating system; let's call it Qunix. How exactly, then, would the world look if Qunix had 95% market share? Would this be, as the average Slashdotter seems to believe, a secure and malware-free utopia, where nobody knows what viruses, worms, spyware, or security breaches are, because they don't exist?

The answer, actually, is somewhat depressing: the world would look pretty similar to how it looks right now. Malware and security breaches would still be prominent, the security industry (anti-malware products) would still be big business, and the black hat industry would have similar job security. Granted, the nature of malware would be different, but that would not make it any less prolific or dangerous.

Ultimately, those four criteria I specified have one intended goal: to put everything the user does in a sandbox, where it can't harm the OS or other users (this was how Windows NT was originally envisioned, but time has proved that hope misplaced). Let's assume, for the moment, that these measures achieve that goal (we'll come back to why they don't, later). With this assumption, it becomes impossible for a piece of malware (or a hacker exploiting a buffer overflow, or some such) to invade the kernel, either to destroy the system or to merely hide its existence from the user and malware scanners (a rootkit, in other words).

Unfortunately, while there's no denying that this would make the lives of evil-doers harder, this is anything but the doom of malware/security breaches. Even without the ability to harm the OS itself, a piece of malware could still damage that user's data, and data is often more valuable than the computer it resides on.

Furthermore, the ability to invade the kernel is no requirement for a virile piece of malware. While hiding is more difficult, creating a virus/worm/etc. that runs entirely in user mode is completely viable. Macro viruses, worms that spread through chat programs, and old-fashioned viruses that spread from a disk/e-mail to the computer and back would still be viable and common (although, amusingly, Windows is more resistant to this last type of virus than Linux). There would still inevitably be security holes in third party applications allowing an attacker to get a foothold in the computer and execute code under the user's privileges, and the user could still get (their data) owned, without the attacker ever invading the kernel.

Thus, the necessity of anti-malware products would remain. Now, it would be reasonable to assume that anti-malware products would run with administrative privileges. However, this advantage of privilege would only make life more difficult for malware authors. While it would make it impossible to completely hide from a scanner running at higher privilege, there are many ways of obfuscating, evolving, and encrypting a piece of malware such that it is not readily recognizable by a malware scanner.

Clearly this could be overcome by the malware scanner being updated to respond to a new threat... but that's exactly how the world works right now: anti-malware programs must be kept up to date, or they will not be able to protect against everything that has been analyzed (not to mention the time between when a piece of malware is released into the wild and protection is added to anti-malware products). Consequently, malware analysis labs would still be working frantically, and companies would still have support contracts with anti-malware companies to keep their computers perpetually updated with the latest malware protection.

Now, let's make one final invalid assumption, for the sake of argument: through a combination of various methods, such as security cookies, data execution prevention, and other manner of code hardening, that it's impossible for an attacker to penetrate an application running on the computer (e.g. code injection into a web server, an office application executing code in a document, etc.). That leaves one final mode of attack, one which has been used for decades with incredible success, and one which all of the aforementioned measures combined can't stop: PEBKAC; that is, user naivety.

Even if you could stop all remote and automated methods of invading a system, it will always be trivial to trick the user into running something that is actually malware. This fact nullifies every one of the defense measures proposed previously. Even if a user cannot be attacked other ways, an executed program could wipe all their data. Even if a user only runs as an administrator to install new programs/drivers and perform administrative tasks, an executed "installer" could wipe the data of all other users, and an installed "driver" could install a rootkit for future or immediate use. Similarly, even an air-gapped computer (one which has no network connection at all) still remains susceptible to infection (remember, viruses were rampant on air-gapped computers long before networks or the internet entered the average home/business).

To give you an idea how easily malware can spread relying only on tricking users into manually running it, you only need to take a brief look at the Storm worm. While this worm has been revised and updated extensively over its life, it began as a humble executable that was e-mailed to people; when run, it infected the computer. This worm is now considered to compose the largest botnet in history.

It's That Time Again

Time to register for spring classes.

So, what's on the plate this semester? After talking to the adviser, it looks like I have exactly 8 classes (3 units each) needed to graduate (I've already finished my biology major, including GE courses, so all 8 are in computer science - third year and fourth year courses). Some of these courses are mandatory, either because they're directly required by the major, or they're required as prerequisites for courses I absolutely want to take. The ones I need specifically, along with their description from the school catalog:

Programming Languages and Translation
Introduce both basic concepts of programming languages and principles of translation. The topics include the history of programming languages and various programming paradigms, language design issues and criteria, developing practical translator for modern programming languages.

Software Engineering
Basic concepts, principles, methods, techniques and practices of software engineering. All aspects of software engineering fields will be covered briefly. Software engineering tools are recommended to use.

Artificial Intelligence
Use of computers to simulate human intelligence. Topics include production systems, pattern recognition, problem solving, searching game trees, knowledge representation, and logical reasoning. Programming in AI environments.

Principles of Computer Graphics
Examination and analysis of computer graphics; software structures, display processor organization, graphical input/output devices, display files. Algorithmic techniques for clipping, windowing, character generation and viewpoint transformation.

Advanced Game Programming
Intermediate and advanced game programming techniques including 3D game development, realtime rendering, physic simulation, etc.

Game Development Project [thesisish thingy]
Individual or team develops realistic games based on the theories and techniques, present and demonstrate their work regularly.

I definitely need to take advanced game programming and computer graphics this semester. The other two slots are open. I'm thinking of taking AI, since that would be useful for E Terra. Unfortunately, that and compilers are at the same time (so are mutually exclusive), and they would both be used for E Terra AI :P I'm hoping to be able to use E Terra for the game project, but I won't be able to take that until the fall.

Besides those, I have a couple decisions to make. I have to take one other programming language than C++ - either Visual Basic, Java, or C#. VB is definitely out of the running, but I'm not sure whether Java or C# would be better. I'm learning some C# this semester because we use it in the game programming class (with XNA), but other than that I'm not sure which is better.

Finally, if my petition to drop one class (not mentioned), which the teacher says is unnecessary, is accepted, I'll need one more upper-division class for the units. Not too sure about which to take for that one. Here are the most appealing prospects, although none of them are something I'd be inclined to take if I didn't have to:

UNIX and Open Source Systems
Introduces the UNIX operating systems, various open source applications and systems, open source programming languages, and open source software development techniques.

Data Security and Encryption Techniques
System security and encryption. Current issues in security, encryption and privacy of computer based systems.

Advanced Operating Systems
The course covers internal structures of a modern operating system. The specific topics include processing, process communication, file systems, networking, and the I/O system. There are several programming assignments which include system calls, and other low level interfaces.

Web Programming and Data Management
Various techniques for developing Web-based database applications using software engineering methodology. Introduce concept and architecture of Web servers, Web database design techniques, client/server side programming, and Web application tools and techniques.

Or, I suppose there's always...
Independent Study
Special topic in Computer Science selected in consultation with and completed under the supervision of instructor.

Internship in Computer Science
Practical experience and service learning relevant to computer science in industry or organizations. Written and oral reports are required.

Hmmmm. Are you thinking what I'm thinking, Pinky?

Annoyance

How dost thou suck, Thursday? Let me count the ways. Well, my Visual C# Express just stopped working due to me not registering it; more specifically, due to a bug in Visual C# that makes it not accept any registration numbers, regardless of whether they are valid. Did I mention that MS offers NO technical support for the express editions (and XNA only works with Visual C# Express)? So no working on E Terra (or anything else related to video game development class, for that matter), for the time being.

On a related note, I still have no programmers who have volunteered to work with me on it. Although arguably that's my fault for waiting so long to get started. As well, the forum of the video game design club is broken and not accepting registrations, so I can't post help wanted ads on their site. In either case, doing all the coding for an unsimple RTS myself will be... interesting.

Finally, Live Spaces is broken today and not allowing any new blog posts, so I can't even blog about E Terra (I'd already written up a new entry to post).

E Terra

Okay, my new blog E Terra is now online. No, I'm not giving up on Q & Stuff (which is still my main blog); the first post explains everything.

& Homework Solution

This problem is actually very straightforward, and does not require much cunning to solve. By definition, raising a number to a power is the same as multiplying the number by itself repeatedly (e.g. a^3 = a*a*a). However, polynomial expansion, a 7th grade math principle, yields a trick that can be used to compute the partial result of each multiplication (az % x) without ever computing the entire result of the exponent (a^b). A rudimentary proof of the trick:

az % x

Decompose a and z into portions which are multiples of x and portions which aren't: a = xm + n, z = xo + p
= (xm + n)(xo + p) % x

Polynomial expansion
= (x^2*mo + xmp + xno + np) % x

(y + z) % x = y % x + z % x. We have to add another % x at the end because it's possible that the sum of the remainders exceeds x.
= ((x^2*mo + xmp + xno) % x + np % x) % x

Extract common multiple
= (x(xmo + mp + no) % x + np % x) % x

xy % x = 0 by definition
= (np % x) % x

Two modulus in series are redundant
= np % x

As the result of each multiplication/modulus will always be less than x (which must fit in a word), there is no need for big numbers or for many multiplications for each step (for comparison, the most straightforward method of multiplying big numbers requires n^2 primitive multiplications, where n is the number of digits in the big numbers). Thus this algorithm is O(power) in the worst case.

This process can be further optimized by noting that a^b % x = (a^(b/c) % x)^c when b is a multiple of c. Thus divide and conquer can be used with recursion to eliminate duplicate work in the case where the exponent is a multiple of c. With this optimization, the algorithm becomes OMEGA(log power) in the best case; the example I gave in the original post was a best case scenario where the exponent was a power of two, and required only 62 multiplications and 62 divisions to solve.

Another problem in the same homework is proving much more difficult, however: write an algorithm using divide and conquer to, given an unsorted array of values, determine whether there is a single value that appears more than half as many times as the number of elements in the array; the algorithm must be generalizable such that you can only compare elements for equality - you can't tell if one element is greater or less than another (which rules out sorting and creating any kind of data structure to count them). Those multiple constraints, taken together, are really brutal for resisting solutions. I've figured out a fact of the problem that I think will be important in solving this (a condition that, if false, guarantees that such a value doesn't exist; however, if the condition is true, it's still possible a majority value doesn't exist), but I haven't quite figured out how to solve it, yet.

& Homework Fun

Got this question on a homework assignment in algorithms class, and thought it was pretty cool (or rather, the solution is pretty cool): develop an algorithm to calculate x^pow % mod, which does not use big numbers (numbers that take more than one processor word to store, and more than one processor math operation for each calculation).

Random fact: 1928374655647382910^9223372036854775808 % 4123456789 = 3021338089

In other news, posts about generally cool things will now be tagged 'squishy', rather than the previously used 'shiny'.

Logitech: At It Again

So I just spent an enjoyable period attempting to contact Logitech customer support through their Email Us link in their support site. Shortly after sending the first one, I felt inclined to send this one:

I take it you people don't like getting support requests, and do as much as you can to discourage them. There's a rather gaping bug with your support site, where it will say invalid e-mail address/password on attempt to login, tell you that the e-mail address is not in the database when you attempt to get your password sent to you, then tell you that the e-mail address is already in the database when you try to create a new account using that e-mail address. This occurred with both my primary address and backup address. I wasn't able to manage to register until I tried this one, which isn't even mine.

As you can see, this has nothing to do with the mouse I entered (that was a different support request from a few minutes ago). I just thought you might want to know that your web site makes people want to hurt you physically, and I needed to enter product info to contact you at all.

I thought I wrote about Logitech's technical incompetence a year or so back, as well, but I guess not. Maybe that was on my todo list...

Public Service Announcement

Microsoft Office 2007 Ultimate for $60 through MS special to students in eligible countries (US, CA, UK, FR, IT, SP). That's 91% off retail (not that anyone would pay that).

Buy here
Verify offer is legit here

We now return you to your regularly scheduled doldrums.

I Like It! I'll Take It!

So, I've been reading my new book, Introduction to Typology: The Unity and Diversity of Language. I've just encountered something I like a lot, and plan to use it in Caia. Let me attempt to give a very brief amount of background and explanation.

Not all languages have tense. And some languages on both sides have something called aspect. Aspect indicates some facet of time about a verb in ways that are more complicated than tense. For example, some languages conjugate the same verb (without a helper verb, which English uses) differently depending on whether the subject is starting to do something (e.g. "began to eat"), finishing something (e.g. "finished eating"), etc.

One very common class of aspect (although usually this aspect in intrinsic to the verb, and does not have multiple conjugations for the same verb) is the distinction between state, achievement, activity, and accomplishment. The state aspect indicates that the subject is maintaining some preexisting state. The achievement aspect indicates a change in state. The activity aspect indicates some act that is self-contained and does not include a change in state. Finally, the accomplishment aspect indicates that the subject has caused an action with regard to some other object.

Some examples in English, using the verb 'break' (note that English cannot perfectly distinguish these four aspects for individual verbs, so try not to get confused by the ambiguity). The state aspect: "the window is broken" (this is a little ambiguous; specifically what that says is that the window was broken before the present time, and continues to be broken). The achievement aspect: "the window broke" (also "the window was broken", but that could also indicate the state aspect). The activity aspect: "I ran to the window". The accomplishment aspect: "the ball broke the window".

As this very elegantly accounts for the active and passive voices, as well as both transitive and intransitive verbs, I'm gonna definitely use those as some of the mandatory aspects of Caia (some aspects - the most useful and common ones - and possibly tense are included in the basic conjugation of the verb, while other aspects are formed, as in English, either through phrases or extra words such as adverbs). Though I may combine the achievement and activity aspects, as I'm hard-pressed to find a verb for which activity and achievement are not mutually exclusive (note how 'break', by its very definition, could not display the activity aspect, so I had to use a different verb). And for anyone who's curious: the jury is still out on whether Caia will use tense.

Sprachbund - UPDATED

So, I'm attempting to evade work (again), and was struck by another random thought. I mentioned previously that Japanese and Korean adjectives are really intransitive verbs, which use relative clause structure to act as adjectives. I also mentioned that this seemed to be an integral part of Korean (e.g. the suffixes for adjectives and verbs are the same), while there's some evidence to the contrary in Japanese - adjectives have different suffixes, all but one of which have the form -k_, leaving the possibility that Japanese adjectives were true uninflected adjectives at one point, and had some suffix beginning in k affixed to them.

Well, there's a linguistic principle known as sprachbund. That's German for "binding of languages" ('sprach' is the Old English word for 'speak', and is still used in German). This is the principle that, when you have two or more languages in contact for a large period of time (and, especially, when there is a high degree of multilingualism in the population), the syntax (word order) of unrelated languages will come into sync. Other things also happen, such as word borrowing and language mutation, but those are beside the point.

What if, at some point in the past, Japanese and Korean (for the purpose of this hypothesis, we'll assume the languages are unrelated; the relation of the two - or lack thereof - is still in dispute, so this is not a radical assumption) populations mixed extensively. It's possible that Japanese acquired the Korean syntax of adjectives, transforming Japanese adjectives into intransitive verbs.

If this were the case, it's possible Japanese acquired other aspects of Korean, as well. For example, I saw in one book from the early 1900s that you could use the '[subject] [verb]' form in Japanese as well as the modern forms '[topic] wa [verb]' and '[subject] ga [verb]' ('wa' and 'ga' mark the topic and subject, respectively; at least in these forms, they do) at one point in the past, whereas in current books you only see the 'wa'/'ga' forms. It's interesting to wonder if Japanese might have picked up the topic and/or subject particles from Korean; especially so considering that 'ga' originally meant something completely different, and has been crudely repurposed into the subject particle, in a downright bizarre manner. Though you should take that idea with a grain of salt, as I haven't researched that possibility at all, and don't even have the original book I read about that in anymore (returned it to the library).

In other news, I just lost contact with my computer at work (more than a thousand miles away, on a holiday weekend). I guess that means work's done for this weekend.

UPDATE: Okay, got a reply from a Japanese-speaking classmate (naturally, as I do most of my blogging on a whim, I didn't wait for a reply to the e-mail I sent before posting :P ). He says that the "[subject] [verb]" form is still used in informal speech. So that probably rules out my second item of speculation. I'm still interested in whether there is any truth to my Korean adjectives hypothesis, though.

Writing Systems and...

As with most of my posts, this post is written on a whim. Specifically, I just happened to be talking with someone on an IM about this topic earlier today, and I had the whim to write a post about it.

There are four major types of writing systems: alphabets, abjads, syllabaries, and ideographic/logographic systems (those two are not the same thing, but for our purposes they're in the same category). You should be very familiar with alphabets. Alphabets are writing systems in which, more or less, each character corresponds to a single spoken sound, though the nature of language change makes it impossible for there to be a 1:1 relationship between sounds and letters indefinitely (some alphabets originally did have a 1:1 relationship). Some common examples are the Roman and Greek alphabets, Roman being perhaps the most widely used writing system in the world.

Next are the abjads. I believe I mentioned these a few posts ago. These are incomplete alphabets - that is, only some sounds (typically consonants) are written, and the rest are omitted. Sometimes additional characters may be represented by diacritic marks. Arabic, Hebrew, and Tengwar are examples of this. Arabic may, depending on the writer and the application, either omit short vowels (long vowels have characters just like consonants), or represent short vowels with diacritic marks (these marks are what give Arabic its distinctive glittery appearance, in cases where short vowels are written). Some writing systems may have an implied vowel after each consonant, and diacritics are only written when the vowel differs from the implied vowel; some may even have characters for all sounds, but omit some at the discretion of the writer.

Syllabaries, also mentioned previously, consist of one character for each syllable possible in the language (though they are also subject to loss of 1:1 correspondence due to language change). The syllabaries most familiar to me are the Japanese hiragana and katakana, although there are others.

Finally, we have a class that I don't know of a single name for, and include systems of ideographs and logographs. Logographs are when a single character represents an entire word - that is, there is a (near) 1:1 relationship between words and characters; the most well known logographic system, and the other contender for most used writing system in the world, is the Chinese writing system. Ideographs are similar, but in this case each character represents some idea or abstract concept. Contrary to common misconception, Chinese is not an ideographic system; however, the Japanese use of Chinese characters bears some resemblance to an ideographic system, where words frequently use multiple kanji (which is part of what makes the Japanese writing system harder than the Chinese system, as I mentioned in the distant past). For example, the Japanese word for goat (山羊) is written mountain (山) + sheep (羊).

Finally, there are complications/impurities in all of these. For example, some writing systems, such as Devanagari (an abjad with implied vowels), has one character for each consonant/syllable, but also has some characters which represent combinations of consonants/syllables; in other words, some characters may be combined to form entirely new compound characters in nontrivial ways.

Next post, resolve willing, I'll get to where I'm going with this (and why I've written this post so briefly and hastily - it's only background for the main topic).

Thanks (not)

Got my monthly notice that my monthly tuition payment was due, a couple days ago.

Statement Date [this is the date printed on it, not the date it was actually received]: 08/17/07
Payment Due Date: 08/14/07

Talk about helpful. Makes you wonder why they bothered to send it at all; could have saved some on postage.

Awesome!

Blizzard negotiating with researchers for virtual epidemic study

Around this time last year, a strange phenomenon struck the virtual inhabitants of World of Warcraft. A disease designed to be limited to areas accessed by high-level characters managed to make it back to the cities of that virtual world, where it devastated their populations. At the time, Ars' Jeremy Reimer noted, "it would be even more interesting if epidemiologists in the real world found that this event was worthy of studying as a kind of controlled experiment in disease propagation." The epidemiologists have noticed, and there may be more of these events on the way for WoW players
...
On balance, the analysis in Epidemiology felt that virtual worlds might provide a useful supplement to traditional models of disease spread, and suggested working with game programmers to test a variety of disease conditions. "Multiplayer online role-playing games may even be useful as a testing ground for hypotheses about infectious disease dissemination," the author said, "Game programmers could allow characters to be inflicted by various infectious diseases, some of which may not be visible to the player, and track the dissemination patterns of the disease in specific subpopulations." It looks like something of the sort is in the works. A report from the Agence France-Presse indicates that Nina Fefferman, a researcher from Tufts University, is currently negotiating with Blizzard about running epidemiological tests in WoW.

Maybe I should go apply at Blizzard, now :P