Legendes II

Listen to the Legendes musical theme

IMPORTANT NOTE: Legendes is now definitely dead and will not be continued. This page is only kept for its historical interest.

Table of contents

Introduction and FAQ

What is Legendes?

Several things.

First of all, with an acute accent on the first ``e'', that is, ``légendes'', it is a french word that means (would you have guessed it) ``legends''.

Second, Legendes is a game which my friends Philippe Clavel, Laurent Pénet and I wrote in Turbo-Pascal, and which runs under MS-DOS. If confusion is likely, I will refer to this game as ``Legendes I''.

Finally, and most importantly for this document, Legendes is a game which Philippe Clavel and I are currently writing.

One thing Legendes is not, however, is a spelling mistake.

How do I pronounce it?

That's an unresolved question. You can pronounce it just as the english word ``legends'', but that's not chic. You can also pronounce it as the french word ``légendes'', but that's rather hard if you don't know French (the ``l'' is made with the tip of the tongue, which is different from the english ``l''; the ``é'' is very closed, somewhat like the ``ay'' sound in ``day''; the ``g'' is pronounced like the ``z'' in ``azure''; the ``en'' is a nasalized ``a'', just pronounce ``ah'' and let the air flow through your nose at the same time; the ``d'' is pronounced somewhat like in English; and the ``es'' at the end is not pronounced at all). I tend to think that since its a hybrid french-english word, the ``le'' should be pronounced as in English (since there is no accent on the ``e''), and the rest like in French. But since I have not had much the occasion to speak of Legendes in english, I really don't know.

Or perhaps it should be a word like ``netscape'' (which, remember, is spelled n-e-t-s-c-a-p-e, but pronounced ``mozilla''), and we should pronounce it something completely different. One possibility is ``sedneggel'' (where the ``gg'' is as in ``nuggets''), the almost-backwards spelling of Legendes, that we used in Legendes I as the name of the world.

Anyway, this is free software, you may pronounce it as you want ;-)

What kind of game is Legendes II?

Legendes II is (or rather, will be) an adventure game in the spirit of Ultima VI/VII. (Ultima is a registered trademark of Richard Garriott and Origin Systems, inc.)

There are two features, however, which we want Legendes to have, and that Ultima VI/VII did not have. First, easily modifiable data files by means of a scenery editor or some such thing. In other words, the same executable can be used for creating many different games by creating different sets of data files (one such data file is the map of the world). For this reason, we say that Legendes is a meta-game. Second, Legendes is to be multi-player and have the possibility of working over a network.

What are the conditions for copying Legendes?

Legendes is free software. It is distributed under the terms of the GNU General Public License (either version 2 of the license, or, at your option, any later version) as published by the Free Software Foundation.

As indicated by the GNU General Public License, Legendes comes with absolutely no warranty, not even the implied warranty of merchantability or fitness for a particular purpose.

What are the target architectures for Legendes?

The main target for Legendes is an Intel box running Linux. Simply because that is what I happen to have.

That being said, we use the GNU autoconf and automake utilities, so we hope to achieve a reasonable degree of portability. Any Linux platform will certainy work, and in fact probably any decent flavour of Unix (the authors, of course, reserve the right to define ``decent'' in any manner they want :-) with a POSIX threads library and X11R6.

Moreover, at the insistance of one of the authors (who is not the one writing this document), Legendes will be ported to some version of Microsoft Windows.

Where can I get Legendes I?

The game Legendes I is no longer maintained. Most of its version history has, in fact, been lost in the Great Bit Bucket. The two last versions, however, have survived. Version 21 is playable (at least, if you speak French and are patient enough), and version 22 is extremely incomplete, but also closer to what we hope to achieve for Legendes II.

The following two links are .tgz (that is, .tar.gz) archives of those two versions of Legendes I (actually, special editions from which have been removed those parts which could pose copyright problems). They contain the complete source code written in Turbo-Pascal, as well as a compiled binary (so you don't need Turbo-Pascal to run the game).

I am told that some self-proclaimed operating systems do not have the necessary tools for loading .tar.gz archives, or that such tools do not work correctly. Please provide me with more information about this. I may on demand make .zip versions available (even though I dislike .zip archives for various reasons).

Legendes II will contain nothing but fresh new code, so downloading the above files is not necessary if you want to contribute (nor is knowing French, by the way).

What is the current version of Legendes II?

As of writing (1998/08/20), version 0.0.2 is available, and we are working (sort of) on version 0.0.3. As you might guess from the version number, this is still pre-pre-alpha (right now, Legendes can be used as a labyrinth game, and that's about all). We plan to make development snapshots available frequently, also.

Where can I get Legendes II?

Consult this directory. The files with names such as l980814.tgz are snapshots of the entire build tree at the specified date. Such snapshots contain all that happened to be in the Legendes working directory at the time (not even a make clean was performed), including object files, compiled binaries, emacs backup files, configure status, and all that kind of junk. (Thus, if you want to compile, you will probably want to start by removing the .deps directory, the config.cache file, and the object files.) Files with names such a legendes-0.0.1.tar.gz are distribution releases, performed with a make dist. Thus, they contain only what is strictly necessary to run the game. There may also be an untared copy of the last snapshot and/or version, and a .zip archive of it, for your convenience. Finally, the sleg2126.tgz and sleg2245.tgz files are not part of Legendes II; rather, they are versions of a former game, Legendes I (see above).

How can I help?

We're looking for developers. If you can program in C and you are interested, then read the present document and/or examine the latest snapshot, and/or contact us, we'd be glad to have your help.

We're also going to need a lot of help with the graphics. If you've done tiles previously in your life (or in some former life), I want you for the Legendes project.

More generally, any kind of help is welcome. If you have any comments, suggestions, criticism, ideas, insults, or anything else, please contact us.

How can I contact the authors?

Here is the complete Legendes team, in alphabetical order, with e-mail:

In addition, I (David Madore) have a Web site, on which the present document can be found.

Is there music?

There is! By courtesy of Antoine Allain, we have a few MIDI files to accompany the Legendes project. Here are the major themes:

Can you show me what it looks like?

[Legendes screen snapshot]

This is a screen snapshot (scaled 0.6, and stored in jpeg with quality 90%) of version 0.0.2 of Legendes. Remember, however, that it doesn't represent much, because the whole point of Legendes is that it should be very versatile and configurable. By changing the X resources and the icon files, it is possible to make it look like pretty much anything. Heck, you may even (with enough patience) make it look almost decent!

About this web page

This document is the main Legendes web page. Its URL is


The above URL always contains the latest version. A copy of this document is also included in every version or snapshot of Legendes.

This document is the unique source of information on Legendes for the moment (barring the C source files, of course). There are no man pages, no texinfo files, nothing else than this. It is destined to receive any kind of information concerning Legendes: FAQs, links and pointers, coding styles and reference documents, documentation, user and programmer guidelines, etc.

This web page is supposed to be viewable with any browser. I have had it checked with weblint, and I have examined it with both netscape and lynx. Please contact me if your browser does not show it satisfactorily.

The logo at the top of this page was produced by the Gimp, using Adobe's utopia font, size 100. It does not come in GIF format, as the Free Software Foundation recommends against using GIF files because of Patent problems.

The History of Legendes

Once upon a time, there was an 8088 at 4.77MHz...

I used to program a lot in Turbo-Pascal. One day Philippe and I were getting bored and he had the bright idea of writing an adventure game. So we started, and when we got as far as 100 lines or so we, were totally bored and we stopped there. The program sat on the hard disk for some time; but then I bought a new computer, gave the old one (the 8088 at 4.77MHz in question) to Laurent, and also taught him a bit of Turbo-Pascal. He found the Legendes game and insisted that we should continue it. So we did. Version 1 of Legendes only had the "create character" part, and version 2 had that plus some fighting of random monsters. That was all: one would create a character and then endlessly fight monsters (and win money) until one died. There were no graphics or anything, just a horrible text display of the stats during the fights. This was still terribly boring, so I just forgot about the whole thing, but then one day when I came back from holidays, Laurent told me that he had modified Legendes somewhat. And indeed, from something like 300 lines it had gone up to nearly 1000. He had added some kind of story, and the possibility of buying potions and weapons between the fightings. That was version 3, but it was still very rudimentary. Still, at that point, I was seduced, and I agreed to work on it seriously.

First, I had to rewrite all that Laurent had written. Not that it was full of bugs (it wasn't, and that is the incredible part), but he had the most extraordinary way of writing Pascal: he would just go to the new line when the line was full. There were no indentations, no nothing. And the variables and procedures had unbelievable names. I was rather ashamed of that, as it is I who had taught him Pascal. Anyway, I rewrote most of it and added some more features of my own, and that was version 4. Then Philippe learned about it and thought, hey, that's great, let's go on. Together, we added some more features, but the whole thing started becoming really interesting only when in version 5 or so we (or was it I alone?) added the map. Then it really started looking like a game. There was a map (in text mode) on which one would move around, seek treasures and avoid (or attack) monsters, and so on. At that point, the world was a 150*150 square made up of little squares of four different possible kinds (water, earth, forest or mountain), and there were 9 zones in it, one consisting of just water, one of earth and water randomly mixed, one of earth and forest, etc.

The versions went on, and the game made much progress. A real quest was added (finding 7 orbs in the world and bringing them to the Demiurge, i.e. creator god, to save Him from Evil), a reasonable kind of world was created, villages were created in which one could enter and visit various shops, a primitive graphics interface was designed (Philippe drew most of the tiles), some music was added (that is, a sound driver was; the actual music was soon copied from Ultima VI, to which the game was conspicuously close in all its good sides), various kinds of monsters, people to which one can talk, many kinds of objects and items, and so on. This way we reached version 21, of which we still have a copy since it is the last playable version of the game.

At this point, the game was really beginning to look good (I mean, for a bunch of low-rank amateurs like us with little time to spend on it, primitive computers like a 8088 at 4.77MHz and so on). The code went as far as 12000 lines which is not so enormous but it is the longest that I had ever written. But one thing was extraordinarily worthless, and that was the fighting. The fighting still occured in text mode (with the stats of one and the other fighter just scrolling across the screen), and that had virtually not changed since version 2. Philippe bugged me more and more about writing a decent fighting interface. However, by thinking back upon what we had written and how it was written, I realized that this could not be done without re-writing most of the game. So we set out to do that (it must have been about the end of the year 1993). Legendes version 22 started very much from scratch. Another friend of ours, Antoine Allain, composed some music for it, I drew some temporary tiles which Philippe was later on supposed to redo (he redid some of them but not all). The world had used to be a single 150x150 array, and upon entering a village, it would itself expand to a 50x50 array or so (randomly generated from the position of the village in the world); now we moved to a fixed world, 4096x4096, with everything done by hand. The whole system was strongly inspired by Ultima VI (and Ultima VII), whose data files I had completely and entirely decoded so that we could imitate the same format. Only by september 1994 I moved from Orsay to Paris where I did not have a computer at hand (and I also had a lot more work to do), so the project was never completed. Legendes version 22 now exists in a very partial way: the program compiles and the world can be visited, but there is very little to do in it (only half a dozen or so living creatures for example).

Still, in a way, it (version 22) is much more interesting than the ``playable'' version 21, since it incoporates some of the essential ideas which will be used in Legendes II. In fact, this version could probably be used as a starting point for a relatively decent game (which version 21 could not). That is, version 21 was abandoned because it could not be improved on any more, whereas version 22 was abandoned simply because MS-DOS was abandoned.

At the end of '96 and the beginning of '97, I completely stopped using MS-DOS and moved over to Linux (for ideological and practical reasons). In the same way, I abandonned Turbo-Pascal in favor of C, and more precisely gcc. So I thought it might be a good idea to save what was worth saving in Legendes and write the successor game. Only at that time Philippe did not have any time for computers (he was busily preparing for his final exams). Then until summer '98, it was again I who had no time for writing code. Now finally things can really start.

Legendes coding standard

standards, n.:
        The principles we use to reject other people's code.

(Taken from ``fortune'')

The files in the game

Every C file (whether .c or .h) must start with exactly these lines:

/* This file is part of Legendes II */
/* Copyright (c) 1998 by
 *   Philippe Clavel (philippe.clavel@supelec.fr)
 *   David Madore (david.madore@ens.fr) */

 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version
 * 2 of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty
 * the GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

If new developpers join the Legendes team, their name will be inserted alphabetically in the list of copyright holders of every file. If the list gets too long (ha, ha, ha, what a joke), the copyright notice will be formulated as follows:

/* Copyright (c) 1998 by the Legendes team. */

After that comes a description of what the file does, like this:

/* File foobar.c */
/* This file contains the functions to frobnicate the baz and qux
 * data structures. */

Finally, there comes a ^L character alone on a line. The real code starts after that.

The ChangeLog file

Any modification made to the source files should be summarized in the ChangeLog file. The ChangeLog is kept exactly in the way emacs does it. This is important, because the need may arise to process this file computerifically.

Formating C source

The end of line character is ^J (ASCII 0x0a), the so-called ``line feed'' character. It is not preceded (nor followed) by a ^M (ASCII 0x0d, ``carriage return'') character.

An important subdivision in a file may be indicated by putting a ^L (ASCII 0x0c, ``form feed'') character alone on a line. This is mandatory after the initial comments in the file.

One level of indentation is two characters wide. Eight spaces (four levels of indentation) can be replaced by a tabulation.

No line should ever exceed 79 characters (not counting the final newline; and a tabulation counts for eight, naturally).

Comments are formatted the way emacs does it: the first line starts with slash-asterisk-space, and subsequent lines have an asterisk and a space in the same column as those of the line above. If a comment spans more than one line, there should be nothing else than the comment on the lines in question.

A function definition looks like this:

void *
foobar(int baz,void *qux)
  void *p;
  if (p==toe(p))
    return p;
    return NULL;
The important thing to note is that the name of the function starts on column zero.

Naming things

Except when tradition very strongly dictates the contrary (such as for an Xt Widget), C identifier names should be all in lower case. Preprocessor defined symbols, on the other hand, should be all in upper case (except, naturally, when they are deliberately written to shadow a C identifier).

When the identifier is made up of several words, an underscore should be used to keep them apart. Do not use capitalization for this! Thus, write read_foo_from_bar() rather than ReadFooFromBar(). Do not use definite articles in such names: write kill_hero() and not kill_the_hero(). Put the object after the predicate rather than before: write kill_hero() rather than hero_kill().

There are cases where the underscore may be dispensed with. A necessary condition for this is that there be no identifier starting or ending the same way (the identifier must be isolated: if killhero() is alone, this is tolerable; but there must not be killhero() and killenemy(): use kill_hero() and kill_enemy() instead).

When several functions or variables are parallel (such as when they have similar prototypes and a similar function), they should also have parallel names. For example, all the functions of the Legendes portable library have names starting with lgd_.

Names of typedefs should end in _t. A purist would tell me that this is bad because such identifiers are reserved for the C language and library, but no matter. A structure name should end in _s and a union name in _u. Here is an example:

typedef struct answer_s {
  int foo,bar,baz,qux;
} answer_t;

static answer_t answer;

Local variables can have short and obscure names, it does not matter. It also is not important if i has type int in one function and long int in another. Global variables and functions, on the other hand, should have sufficiently explicit names. Just calling a function init() is OK provided there is absolutely no doubt as to what it initializes (a condition rarely met).

How data files are coded

First, a few general principles. Number one, our data files are stored in binary. It is more and more the tendency nowadays to store data files in text form (because text is easier read by humans, and also it is more portable). I subscribe to this idea, but I believe that in this particular case it would be very much inconvenient to store the data files in text, so we have chosen binary instead. We have tried to make things as easy as possible, however. This means that we have chosen to store as much as possible everything on 32-bit quantities, with a predefined byte order, that happens to be little-endian (because we work on little-endian machines). Functions from the Legendes portable library will read such quantities in a portable fashion.

The map and chunks

The elementary unit for subdivising the world is called an (elementary) square. We expect the world to be about 4096 squares across, but some worlds (remember that Legendes is a meta-game) may prefer to have more like 8192. Now a square 8192 acoss has 64M elementary squares in it; and if the contents of each is to be stored on a 32-bit quantity, that makes 256Mb for storing the world (or even, each level of the world), which is slightly excessive as most would agree.

So we adopt a sort of ad hoc compression method. The map is divided into squares of side 16 elementary squares, called ``chunks''. The map file, rather than specifying what elementary square is found at every position, specifies what chunk is to be found there. Thus, we gain a factor 256 on the map size, reducing it to 1Mb (or less) per level. We need, however, another file, the chunk file, that specifies the contents of each chunk; its size is 1kb per chunk. If we needed a new and different chunk content for every chunk in the world, we would not have gained anything. However, that is presumably not the case: some chunks are repeated a very great number of times throughout the world. Thus, we have in effect a compression algorithm for the map. However, it is up to the Designer of the Cosmos to worry about chunks and their contents (that is, it is a ``manual'' compression algorithm).

The organization of the chunk file is simple: it is just a succession of chunks, each one being a 16*16 array of words (where ``word'' means, here and elsewhere, a little-endian 32-bit word; the chunk is read from left to right, and, within each column, from top to bottom: the x coordinate comes first in the array). The word gives the type of ground found at that particular place; however, its meaning is not entirely defined yet. Most probably, the lower 16 bits will give the actual ground type, and the top 16 bits will be reserved for future use.

As for the map, for reasons of convenience (because of the way we cache it into memory, and also because of the way objects will be organized), we divide it into yet larger regions, squares of side 16 chunks, that is 256 elementary squares. Such regions are called zones. A zone on disk is stored as a 16*16 array of words, each word giving the number of the chunk found there (at least the lower 16 bits, the higher 16 bits are reserved for now; the chunks are simply numbered in their natural order in the chunk file). The map is a succession of zones. Exactly which zone goes where is not fully determined yet: we are planning to have yet another file, the zone index file, which would specify this in some way. But for the time being, we stick with a one-level map, and the map is actually a 16*16 array of zones, stored from left to right and top to bottom.

Object descriptors

How objects are going to be stored is still under discussion. For the time being, I refer to the way things were started to be done in version 22 of Legendes I. An object descriptor should be padded to an integer multiple of 32-bits so we can read and write them using the portable library calls.

Icon files

A Legendes icon is always 16*16 pixels. Larger tiles will be split in several icons. The icon file, which is called icon, just contains the icons one after the other. Each icon is a 16*16 array of 32-bit little-endian words (column first, row second - as always in Legendes). Each such 32-bit quantity describes the amount of red in the lower 8 bits, the amount of green in the next 8 bits, the amount of blue in the next 8 bits, and the transparency in the last 8 bits.

The program pnm2lgi, which comes with Legendes, will read a PPM/PGM/PBM file (of size 16*16), and store it into the Legendes icon file. It is also capable of reading two PPM files, the second one giving the transparency (black=opaque, white=transparent). The program lgi2pnm will to the converse: it will read a Legendes icon and write a PPM file containing its colors, and optionally also a PGM file containing its transparency. Both these programs take the icon file as first parameter, the icon number as second parameter, the color PPM file as third parameter, and, if desired, the transparency PGM file as fourth parameter.

Legasm files

The Legasm Virtual Machine isn't being used for the moment, and considering some recent exchanges between the programmers, it isn't obvious that it will ever be. Rather, we will use GUILE in its place - partly because it is more pleasant to program in a high-level language like scheme than directly to code in RISC assembler 8-| You may therefore wish to skip this section entirely.

Legasm is a small portable Legendes-dedicated assembler, not unlike the native assembler of some RISC processors in some ways. It exists in source form and in byte-compiled form. It is the latter which is interpreted by the Legasm Virtual Machine. The former must be compiled (assembled) before use.

The Legasm virtual machine handles exclusively 32-bit words. It has 256 registers, numbered R00 through Rff. Register R00 always contains 0, register R01 always 1, register R02 always 0x80000000 and register R03 always -1; registers R04 through R07 are reserved for future use. Register Rff is the program counter (instruction pointer), register Rfe the stack pointer and register Rfd the flag register; registers Rf0 through Rfc are reserved for future use. All other registers are general-purpose. The instruction set is completely orthogonal (that is, any instruction can take input from any register and put the output on any other register) even as far as the ``special'' registers are concerned (but trying to write to R00-R03 will be a no-op). The R8x registers, in particular R80 and R81, are used for all kinds of communication operations; for example, a typical legasm routine will take its input from R80 (typically, an instruction) and R81 (typically, some data) and write the result to R80 and R81. This is of course by no means necessary, it is just a useful convention. However, all service calls will read the function number from register R80.

The Legasm virtual machine uses a flat memory addressing scheme; in other words, all memory is viewed as a flat array, with addresses ranging from 0x00000000 to 0xffffffff, each address containing one machine word (32 bits). The lower part of the memory, starting with 0x00000000, contains the program, read from the disk file, and which is read-only as far as the Legasm virtual machine goes. The actual RAM starts at 0x80000000 and in the present version goes up to 0x80000fff (that makes 4 kilowords, or 16kb of memory). Plus, there is a grow-down stack which occupies the top of memory: the stack pointer (register Rfe) points to the most recently pushed word and decreases before a new word is pushed on the stack. The size of the stack is dynamically ajusted by the legasm interpreter, though the actual mechanisms are left unspecified: we only specify that a program that uses push to put things on the stack will not run out of stack space (provided, of course, it doesn't try to push more than a million or so words). In the present implementation, it is the push and pop operations which are magic and change the size of the stack, though that may change sometime. Anything outside the aforementioned addressing areas contains read-only zeroes, though we must leave that unspecified because we may want to add more addressing areas in the future. But reading anywhere in the address space is always valid (there is no kind of protection mechanism in the Legasm virtual machine). The executable area is not limited to where the program resides: it is perfectly legal for a legasm program to write some code to RAM and then execute it (or even execute things on the stack, but that is not advised).

Every instruction of the Legasm virtual machine sits on one machine word. There are no exceptions. Typically, the first hex digit (4 bits) gives the instruction type, the second hex digit (4 bits) the subtype, the next two and two hex digits give the two input registers, and the last two hex digits give the output register. For example, the instruction 0x24212210 means cmpae r21,r22,r10 (compare registers R21 and R22, and put 1 in R10 if R21 unsigned is above or equal R22 unsigned, 0 otherwise) and is decoded as follow:

   compare^^^^   |       |       |       |
above or equal^^^^       |       |       |
      register r21^^^^^^^^       |       |
         with register r22^^^^^^^^       |
             and put result in r10^^^^^^^^

Now to get on to the acual opcodes.

Opcode 0x0... is an arithmetic or logic operation. It is coded as follows:

where [op] has the following values:
00000x0 addadd
00010x1 adcadd with carry
00100x2 subsubract
00110x3 sbbsubract with borrow
01000x4 andlogical and
01010x5 orlogical or
01100x6 nxorlogical inclusive and
01110x7 xorlogical exclusive or
The carry bit is the bit zero of the flag register (register 0xfd). It is set to one when the result of a sum exceeds 0x100000000 or when the result of a difference is negative. The adc operation means ``add the two operands together with the carry bit'' and is used to add numbers that are more than 32-bit wide. Similarily for the sbb operation.

Note that an instruction that starts in

means add r00,source,destin. In other words, it adds zero to ``source'' and puts it in ``destin'', which means moving ``source'' to ``destin''. So that instruction is how we get a mov operation on the Legasm virtual machine.

A sub-particular case is the instruction

(i.e. 0) which adds zero to zero and puts the result in zero. That is the nop instruction.

Opcode 0x1... is a memory operation. It looks like this:

          0001siml[ data ][ base ][index ]
    load/store^| |
direct/indirect^ |
  index multiply^^
Bit 27 is 1 if the operation is store in memory (st mnemonic) and 0 if the operation is load from memory (ld mnemonic). Bit 26 is 0 if the addressing mode is direct (the base and index registers are added to provide the actual address) or indirect (the index register is added to the contents of the memory located pointed by the base register to provide the actual address). Bits 24 and 25 specify by how many bits the index register should be shifted to the left to provide the actual index; use is deprecated (and may be removed some time in the future).

Opcode 0x2... is a comparison. This is its structure:

where [cp] has the following values:
00000x0 cmpeqtest if equal
00010x1 cmpneqtest if not equal
00100x2 cmpintest if all bits of input1 are in input2
00110x3 cmpouttest if no bits of input1 are in input2
01000x4 cmpaetest if above or equal (unsigned)
01010x5 cmpacompare if above (unsigned)
01100x6 cmpgecompare if greater or equal (signed)
01110x7 cmpgcompare if greater (signed)

Opcode 0x3... is a jump or branch. It is coded thus:

          0011rnRc[ cond ][ destination  ]
Bit 27 is 1 if the destination is a register whose number is specified in bits 0 to 7 (in which case bits 8 to 15 are reserved), 0 if the destination is an immediate 16-bit quantity (signed where relevant) contained in bits 0 to 15 of the instruction. Bit 26 is 0 if the jump condition is Rcond==0 (written bnz), 1 if the jump condition is Rcond!=0 (written bz). Bit 25 is 0 if the jump is absolute (destination replaces pc; if destination is immediate, then it only replaces the low-order bits of pc, that is, destination is in the same 64kword page as origin), 1 if the jump is relative (destination is added to pc; if destination is immediate, then it is considered as signed for this purpose). Note that the pc in question (register Rff) is the pointer to the instruction FOLLOWING the jump instruction (so that to produce an endless loop, the appropriate instruction is 0x3200ffff, whereas 0x32000000 is a no-op as well as 0x380000ff). Finally, bit 24 specifies that the previous pc should be pushed on the stack before performing the jump; in other words, that the instruction is a call (cz and cnz mnemonics).

There are no unconditional jumps; rather, use the R00 register to that effect. That is set bit 26 to 0 and ``cond'' to zero also. The appropriate mnemonics are then jmp and call.

Opcode 0x4... is a bit shift/rotate operation. It works like this:

          0100r[t][source][count ][destin]
Bit 27 is 1 if count is a register (actually, only bits 0-4 of that register), 0 if count is immediate (bits 8-12; and bits 13-15 are then reserved). The meaning of the [t] field is as follows:
0000x0/0x8 shrshift right, unsigned
0010x1/0x9 shlshift left
0100x2/0xa sarshift right, signed
1000x4/0xc rorrotate right
1010x5/0xd rolrotate left
This is self-explanatory, except perhaps for the difference between shr and sar: the point is that the former shifts the bits right by adding zeros on the left (in other words divides the unsigned quantity by a power of two) whereas the latter shifts the bits right by duplicating the most significant bit (in other words divides the signed quantity by a power of two).

Opcode 0x5... is an immediate load. In binary, it is coded as

          0101[md][ reg  ][  immediate   ]
where [op] has the following values:
00000x0 lilload low-order bits
00010x1 lihload high-order bits
00100x2 lilzload low-order bits and clear high-order
00110x3 lihzload high-order bits and clear low-order
01100x6 lilsload low-order bits sign-extend
10000x8 ailadd immediate
10010x9 aihadd immediate to high-order bits
11000xc ailsadd immediate, sign-extended
The lil and lih instructions are used to position the low (resp. high) order bits without modifying the other half. They are most frequently used consecutively to load one entire 32-bit immediate quantity in a register. For example, the two instructions 0x50105678 0x51101234 (in any order) will load the 32-bit quantity 0x12345678 in the register R10. The lilz and lilh instructions are used to load the low (resp. high) order bits while clearing the other half, in other words to load in one single instruction a small quantity (resp. a multiple of 0x00010000) in the register. The lils instruction is the same as lilz but it will use sign-extension to the high-order bits rather than zero-extension. The ail instruction adds the given, unsigned, quantity to the register (so 0x58100001 performs the same as 0x00011010). The ails instruction does the same but with a signed immediate quantity. Lastly, the aih instruction is used to add a multiple of 0x00010000.

Opcode 0x6... is push. It is this:

          011000000000000000000000[ reg  ]
and it pushes the specified register on the stack. Note that in case the sp register (Rfe) itself is pushed, it is the value before the push that is used, not after.

Opcode 0x7... is pop. It is this:

          011100000000000000000000[ reg  ]
and it pops the specified register from the stack.

Opcode 0xf... is a svc. It is this:

          11110000[ registration number  ]
This is a service call. Registration number 0 means stop the program. Registration number 1 means print the contents of register R81. Other registrations numbers are yet undefined.

Here is an example of a legasm program with both binary and mnemonic versions:
0x00000181mov 1, r81
0x00018181mainloop:add 1, r81, r81
0x00000182mov 1, r82
0x00018282tryloop:add 1, r82
0x24828110cmpae r82, r81, r10
0x3610000dbnz r10, +0x000d (print)
0x00008121mov r81, r21
0x00008222mov r82, r22
0x02212221gcdloop:sub r21, r22, r21
0x24212210cmpae r21, r22, r10
0x36100003bnz r10, +0x0003 (orderok)
0x00002130mov r21, r30
0x00002221mov r22, r21
0x00003022mov r30, r22
0x21002210orderok:cmpneq 0, r22, r10
0x3610fff8bnz r10, -0x0008 (gcdloop)
0x20012110cmpeq 1, r21, r10
0x3610fff1bnz r10, -0x000f (tryloop)
0x3200ffeejmp -0x0012 (mainloop)
0xf0000001print:svc 1
0x3200ffecjmp -0x0014 (mainloop)
What this does is obvious, isn't it? It calculates prime numbers...

How things are organized

``Low-level'' files and headers

The header file lgd0.h should be included in every Legendes source file. It just contains the program name and version number, and it is a symbolic way of saying ``this file belongeth to Legendes, so hands off''. Do not ever modify lgd0.h! Rather, if you need to, modify lgd0.h.in, which is the real source file: lgd0.h is automatically generated from lgd0.h.in by configure.

The same applies to config.h, which is generated from config.h.in. It contains a list of preprocessor #defines that specify the configuration.

The legasm.c file contains a library of portable functions and useful routines. These functions have a die_on_failure parameter: when the function is called with this parameter set to 1, the function may not fail (if it does, the program aborts with an error message). This avoids a lot of tedious error checking. Also useful are the lgd_read_littleendian_int32() and lgd_write_littleendian_int32() functions which permit reading files of 32-bit little-endian words in a portable fashion.

The legasm.h header file, of course, contains the public declarations and prototypes for use with the Legendes portable library.

The client/server organization

Legendes is a multithread program. In other words, execution occurs at several places simultaneously (or at any rate seems to). These threads are of two kinds: server threads, all identical (but for the moment there is only one of these), and client threads. The server threads are the actual guardians of the game: they know about the Rules, the Map, and all the Higher Lore; on the other hand, they are not concerned with such things as the user interface. The client threads, on the other hand, are in charge of finding out the wants and questions of the various actors of the game (the player, the possible network connections, the monsters, etc.) and translating them into requests submitted to the server threads.

Communication between the client and server threads takes place through a channel known as the ``control fifo''. The control fifo is a chained list of request descriptors (struct msg_fifo_s). The client threads append requests at the end of the control fifo, and the server threads remove them at its head. To avoid the race condition where a client and server threads access the fifo at the same time, the fifo is protected with a mutex. It also comes with a condition variable, on which the server thread sleeps, and which is used to wake it up when a new request arrives. All the relevant declarations and code are in the files fifo.h and fifo.c.

The primitive functions for appending a request to the control fifo (what the clients do) and removing the first request from the control fifo (what the servers do) are respectively append_control_msg() and wait_control_msg(), and they are contained in fifo.c. The request structure may be (at the client's choice) allocated on the heap or in static storage. In the first case, the in_heap field should be set, indicating that the server thread should free() the memory once the request is treated. In the second case, the client should make sure it will not modify or release (from the stack, e.g.) the request structure while the server is treating it; the fact that the server has treated the request is indicated by the treated field being set or by the response being available (it is part of the server thread's specifications that when the reponse is ready, the request structure is no longer needed).

If the client thread requires a response from the server thread, it will put in the response field a pointer to a msg_response_s structure where the answer should go. If it does not want a response, it will put NULL instead. All requests may return a response (if nothing else, an error code indicating whether the request was successfully performed), and all may proceed without response (though in some cases this is fantastically useless). The response structure contains a state variable (ready_stat, indicating whether the response is ready), a condition (ready_cond, signaled when the server has filled the response), and a mutex (ready_mutex, protecting the previous two variables); in this way, the client is able to sleep until the answer has arrived.

To simplify the clients' life, we provide two sets of functions that will fill the appropriate fields of the request structure, and submit the request (see requests.h and requests.c). The req_ functions are asynchronous: they submit the request, but they do not wait for the server's response. The reqq_ functions, on the other hand, are synchronous: they submit a request and then wait for the answer, and return the result (the actual return code of these functions is always the error code given by the server).

What the various threads do

The code of the server thread is in server.c. It makes use of routines that read and write the world map, which are contained in mapchunks.c (with declarations in mapchunks.h).

On the cliend side, things are slightly more complicated: there are (so far) two clients. They are called the input and output threads respectively, but these terms are a misnomer. The input thread takes care of the communication with the X server: it managed the widgets of the game window, and processes the events. When the user demands an action, it is the input thread that will send the corresponding request to the server thread, so in this respect it is indeed an input thread. However, when the X server demands that the window be redrawn (through an Expose event), it is also the ``input'' thread that will handle this circumstance, so its name is not quite adequate. However, in the latter case, the input thread does this simply by copying the contents of a pixmap, the so-called display pixmap, that is part of the resources of the ViewArea widget.

It is this pixmap that is drawn, handled and modified by the output thread: the output thread spends most of its time sleeping on a condition, the redisplay condition (disp_redisplay_cond). When the redisplay condition is signaled (by the server thread, whenever something, such as the movement of the hero, may have affected what is to be viewed on the screen), the output thread wakes up, sends a bunch of requests to the server thread asking it what the world contains at various places and fills the display table with the appropriate entries (see below for details). After that, it sends a synthetic Expose event to the ViewArea widget and goes back to sleep. In other words, the output thread asks the input thread to redraw the window using the (new) display pixmap, and it does this through the X server. The reason for the latter complication is that most of what the input thread actually does is done via the X toolkit's XtAppMainLoop() function, which (presumably...) performs a select() call on the X socket, waiting for the X server to send data. It would be complicated for the input thread to wait for two things at once: a condition signaled by the output thread, and a socket with data sent to it by the X server. Rather, we prefer for everything to be sent by the X server. (All right, this is a rather poor reason. If you see a Better Way (tm), just tell me.)

The Input Thread, and GUILE

The input thread is the thread that handles all events from the X server. Ordinarily it sits in XtAppMainLoop(), and it gets awoken when an event occurs. The event generally concerns the ViewArea widget (the one which shows the view of the world), and if it is an input event (KeyPress, KeyRelease, ButtonPress or ButtonRelease), it is mapped to the notify() action by the translation table for this widget.

Now the new feature in legendes-0.0.1 (of course, I choose to call this a feature - some may use another, less flattering, word) is that the input thread uses (and includes) a scheme interpreter, as provided by the GUILE (Gnu Ubiquitous Intelligent Language for Extensions) library. (Incidentally, yes, that means that to compile Legendes you need GUILE.) Thus, what actually happens when a key is pressed (for example) is that the ViewArea callback will in turn call a scheme function (whose name is given by the argument to the notify() action in the translation table), and it is that scheme function which performs the action. In order to do so, it has access to certain C functions which are declared in input.c (with names starting with cmd_), and also registered as scheme functions when the input thread is initialized.

The point of all this? The scheme programming language gives us a very great versatility of user interfaces, and the possibility of binding extremely complex actions to keys without dirty C hardcoding (the current map editor, for example, is entirely contained in legendesrc.scm, which essentially defines the user interface).

The Output Thread, Icons, Pixmaps, And All That

As mentioned earlier, the output thread's job is to fill a pixmap, the display pixmap (disp_pm), which the input thread will then write on the screen when it receives an Expose event. Now how does the output thread perform its job?

Basically, the idea is this: the large (512*512) display pixmap is drawn by copying 1024 small (16*16) pixmaps onto it; it is essentially viewed as a 32*32 array of small pixmaps. Each of these small pixmaps is made by superimposing several icons. Icons are also 16*16 pixels, but they (can) have transparency, so that an icon can let something appear of the icon below it. The list of icons that constitute a small pixmap is called the description of that pixmap. Internally, it is represented as a null-terminated sequence of icon numbers. The act of taking a pixmap description and producing the actual pixmap (held in the X server's memory) is called compiling an icon.

In the first step, the output thread calculates the descriptions of the various (small) pixmaps that will constitute the (large) display pixmap, and stores them in disp_desc_tab. In order to do that, it sends many requests to the server thread, asking it what is to be found in the various map locations surrounding the hero. It enumerates these map locations from left to right, and from top to bottom. What is found in one map location can have effect on more than the corresponding pixmap description: a wall tile, for example, consists of four icons (one where the wall is on the map, one one square up, one one square left, and one one square up and one square left), so that when the server thread reports a wall, the output thread will add an icon to four different pixmap descriptions. This icon will be ``on the top'' of the pixmap, so that it is essential (considering the way the perspective is drawn) to go through the array from left to right and top to bottom.

Once the descriptions are calculated, the output thread goes through its second step, namely compiling the small pixmaps and then copying them to the display pixmap. The pixmap compilation is done in the function get_pixmap() whose body is found in pixmaps.c. A cache of (1024) compiled pixmaps is kept, stored in lexicographical order of description. When a compilation is demanded, the function first checks (dichotomically) whether this description is already found in the cache. If it is, it returns the already-compiled pixmap. If it is not, it calls fill_pixmap(), which does the actual compiling. Every new compiled pixmap receives a serial number. This is for optimization purposes: the output thread maintains a table (disp_tab) of the serial numbers of the pixmaps being displayed. A small pixmap will be copied to the display pixmap only if its serial number does not match the one which is already found there. When the hero moves, the output thread considers, as a first approximation, that the display will move by an equal and opposite amount, so it displaces the display pixmap and the table of serial numbers in this manner.

Coding Advice

This section still has to be written. It will be in function of what errors the programmers (ahem) tend to make.

David Madore