31 May 2004 A precode macro I've been thinking about how Karig's keyboard handler should work. Each key, when pressed, generates its own key code, which Karig should use to look up the name of the routine to be run for that key. Note I said "name," not "address." If the routine is compiled on demand, not stored as ready-to-run code, then the routine's address will change, so Karig would have to identify the routine by its name. The routine name would actually be a 32-bit number, or cell. This cell would be generated from the text form of the name — up to seven ASCII characters. In other words, the routine name would be stored as what Chuck Moore would call a "pre-parsed word," or what I would call precode. So if I want to store precode into the tables that my keyboard handler would use, I have to figure out how to include precode cells in my source code. Chuck Moore generated his ColorForth wordlists by entering a complicated calculated value for each word, such as (in MASM syntax): dd (((4 shl 7+140o)shl 4+7)shl 4+2)shl 13 ; edit This sequence takes four compressed-character codes — for the letters 'e', 'd', 'i', and 't' — and combines them into a single 32-bit number, stored by the DD directive. I don't want to come up with a DD statement like that for each pre-parsed word. I'd rather have a macro do it for me, so that I could enter, say, macro_name "screen" into my source code and have the calculated value for "screen" generated for me. I'd never written a NASM macro to handle a job as complex as this before, and I didn't really know more than a fourth of all the NASM directives, so I studied the NASM Manual — especially Chapters Three and Four. I found that the directives existed to allow me to write the macro I wanted:
The macro "DP" The source-code file contains both the macro definition and some lines that use the macro to generate precode. (The file contains no real assembly language, so you cannot assemble and run the file. To test the file, examine the file with a hex-dump utility from within Windows, or Linux, or whatever OS you're using.) What it does A DP statement looks like this: dp "boot", "warm", "pause", "macro" For each of the four strings in the above statement, DP generates the equivalent precode value. The words and their precode equivalents in hex are: "boot" = 0xC6664000 "warm" = 0xBA8C4000 "pause" = 0xC4B9A080 "macro" = 0x8AC84C00 So DP would cause NASM to generate the same code that would be produced by something like this — dd 0xC6664000, 0xBA8C4000, 0xC4B9A080, 0x8AC84C00 — or (horrors) this: dd ((((((143q<<4)+3)<<4)+3)<<4)+2)<<13 ;boot dd ((((((27q<<4)+5)<<4)+1)<<5)+21q)<<14 ;warm dd ((((((((142q<<4)+5)<<7)+146q)<<5)+20q)<<4)+4)<<5 ;pause dd ((((((((21q<<4)+5)<<5)+22q)<<4)+1)<<4)+3)<<10 ;macro How it works The definition begins with the %imacro directive, which allows the user to invoke DP with any combination of uppercase and lowercase — dp, DP, Dp, or dP. The 1-* part means that DP can take any number of parameters from one up. %imacro dp 1-* The macro body consists of an inner loop inside an outer loop. The %rep %0 marks the beginning of the outer loop. The %0 returns the number of parameters passed to DP, so %rep %0 means "execute the following macro code once for each parameter (i.e., each string) passed." %rep %0 The first thing the outer loop does is initialize variables:
%assign _cell 0 %assign _wlen 0 %assign _index 1 Here starts the beginning of the inner loop, which is executed once for each of up to the first seven characters in the current string parameter. (I limit this to the first seven characters because the smallest a compressed character can be is four bits, and the precode cell reserves only 28 bits for compressed characters, so no more than seven compressed characters can be stored in a precode cell.) %rep 7 ; Do no more than first seven characters This extracts the next ("_indexth") character from the current string parameter (%1) and stores the character in the variable _char. %substr _char %1 _index Now the macro determines what the character is — which determines _code (the series of bits representing the character) and _clen ("code length" — the number of bits in the _code series). Note that this part of the routine follows the character standard documented on the ColorForth site. %if _char = 'r' || _char = 'R' %assign _code 001q %assign _clen 4 %elif _char = 't' || _char = 'T' %assign _code 002q %assign _clen 4 %elif _char = 'o' || _char = 'O' %assign _code 003q %assign _clen 4 %elif _char = 'e' || _char = 'E' %assign _code 004q %assign _clen 4 %elif _char = 'a' || _char = 'A' %assign _code 005q %assign _clen 4 %elif _char = 'n' || _char = 'N' %assign _code 006q %assign _clen 4 %elif _char = 'i' || _char = 'I' %assign _code 007q %assign _clen 4 %elif _char = 's' || _char = 'S' %assign _code 020q %assign _clen 5 %elif _char = 'm' || _char = 'M' %assign _code 021q %assign _clen 5 %elif _char = 'c' || _char = 'C' %assign _code 022q %assign _clen 5 %elif _char = 'y' || _char = 'Y' %assign _code 023q %assign _clen 5 %elif _char = 'l' || _char = 'L' %assign _code 024q %assign _clen 5 %elif _char = 'g' || _char = 'G' %assign _code 025q %assign _clen 5 %elif _char = 'f' || _char = 'F' %assign _code 026q %assign _clen 5 %elif _char = 'w' || _char = 'W' %assign _code 027q %assign _clen 5 %elif _char = 'd' || _char = 'D' %assign _code 140q %assign _clen 7 %elif _char = 'v' || _char = 'V' %assign _code 141q %assign _clen 7 %elif _char = 'p' || _char = 'P' %assign _code 142q %assign _clen 7 %elif _char = 'b' || _char = 'B' %assign _code 143q %assign _clen 7 %elif _char = 'h' || _char = 'H' %assign _code 144q %assign _clen 7 %elif _char = 'x' || _char = 'X' %assign _code 145q %assign _clen 7 %elif _char = 'u' || _char = 'U' %assign _code 146q %assign _clen 7 %elif _char = 'q' || _char = 'Q' %assign _code 147q %assign _clen 7 %elif _char = 'k' || _char = 'K' %assign _code 150q %assign _clen 7 %elif _char = 'z' || _char = 'Z' %assign _code 151q %assign _clen 7 %elif _char = 'j' || _char = 'J' %assign _code 152q %assign _clen 7 %elif _char = '3' %assign _code 153q %assign _clen 7 %elif _char = '4' %assign _code 154q %assign _clen 7 %elif _char = '5' %assign _code 155q %assign _clen 7 %elif _char = '6' %assign _code 156q %assign _clen 7 %elif _char = '7' %assign _code 157q %assign _clen 7 %elif _char = '8' %assign _code 160q %assign _clen 7 %elif _char = '9' %assign _code 161q %assign _clen 7 %elif _char = '1' %assign _code 162q %assign _clen 7 %elif _char = '-' %assign _code 163q %assign _clen 7 %elif _char = '0' %assign _code 164q %assign _clen 7 %elif _char = '.' %assign _code 165q %assign _clen 7 %elif _char = '2' %assign _code 166q %assign _clen 7 %elif _char = '/' %assign _code 167q %assign _clen 7 %elif _char = ';' %assign _code 170q %assign _clen 7 %elif _char = ':' %assign _code 171q %assign _clen 7 %elif _char = '!' %assign _code 172q %assign _clen 7 %elif _char = '+' %assign _code 173q %assign _clen 7 %elif _char = '@' %assign _code 174q %assign _clen 7 %elif _char = '*' %assign _code 175q %assign _clen 7 %elif _char = ',' %assign _code 176q %assign _clen 7 %elif _char = '?' %assign _code 177q %assign _clen 7 If the current character is not one of those listed above, then it is not one of the forty-eight defined in ColorForth's character set, so the value and length of its _code is zero. %else ; (Character is not one of the 48 defined ; in ColorForth's character set.) %assign _code 000q %assign _clen 0 %endif So now we know the character code (_code), and we know the length of that code in bits (_clen). We add the code length (_clen) to the total word length (_wlen), as long as the result is 28 or less (because we're only allowed to use 28 bits for storing compressed characters). If there is room to add the compressed character code to the cell, we slide the characters already in the cell up to make room and then add the new character. %assign _wlen _wlen+_clen %if _wlen > 28 %assign _wlen _wlen-_clen %else %assign _cell (_cell << _clen)+_code %endif We increment _index in order to retrieve the next character from the current string parameter. This is the end of the inner loop. %assign _index _index+1 %endrep The inner loop exits when we have squeezed into the cell as many compressed characters as will fit. Now we have to slide all the characters up, so that the first bit of the first character is stored in the high bit (bit 31) of the precode cell. %assign _cell _cell<<(32-_wlen) Once this is done, we can finally generate the correct DD directive. dd _cell The last thing the outer loop does is to rotate the parameters, so that what was the second parameter becomes the first. If there is another string to convert to a precode cell, the loop starts over. Otherwise, this is the end of the macro. %rotate 1 %endrep %endmacro Testing the macro The testing part of the source-code file generates precode. I translate the following fifty-nine words into pseudocode (these are all taken from the FORTH wordlist in ColorForth):
I generate precode words in groups of four — first with my DP macro, then with the equivalent DD statement (as taken from a NASM-compatible version of Chuck Moore's original code). The idea is to verify that the precode is being generated correctly by examining the file with a hex-dump utility, such as Robert Bachmann's DumpHex, which displays sixteen byte values in each row. Four precode words take up sixteen bytes. If I generate four precode words using one method and then generate the same four precode words using another method, then when you dump the file to the screen, you should see pairs of rows, with each row containing the same sequence of bytes, like this: 00 40 66 C6 00 40 8C BA 80 A0 B9 C4 00 4C C8 8A 00 40 66 C6 00 40 8C BA 80 A0 B9 C4 00 4C C8 8A If a byte value in the upper row differs from the byte value right below it, then the two methods generate different precode. That doesn't necessarily mean that my macro has a bug, as I explain below. The encoding The character-encoding scheme I followed in my macro is documented on Chuck Moore's site:
The eight most common compressed characters are each four bits long, and the leftmost bit is always zero. The next eight most common are each five bits long, and the leftmost two bits are always "10". The remaining are each seven bits long; the two leftmost bits are always "11". The cell consists of two fields — the character field and the color field. The character field contains the top 28 bits (bits 31 through 4); the color field contains the bottom four bits (bits 3 through 0). (I infer this from Mr. Moore's page on the layout of a pre-parsed word.) The compressed characters packed into the character field, with the first bit of the first character stored in bit 31, and each character stored immediately after the character before. If a character is too wide to fit within the space remaining in the character field (e.g., if the character is five bits wide and there are only four bits of space left), then the character is not added to the field. If all characters fit within the field and there are bits of space left over, these extra bits are set to zero. Here is an example: The word "forth" translates into five compressed characters:
Here is the layout for the bits in a precode cell generated from the name "forth":
Results The macro runs slowly, but it works. The two methods for generating precode usually produce the same result, but there are some instances where they produce different results. I've supplied the hex dump of the assembled file below, with the differences in bold. 00000000h: 00 40 66 C6 00 40 8C BA 80 A0 B9 C4 00 4C C8 8A .@f¦.@î¦Çá¦-.L+è 00000010h: 00 40 66 C6 00 40 8C BA 80 A0 B9 C4 00 4C C8 8A .@f¦.@î¦Çá¦-.L+è 00000020h: 00 64 89 B1 00 00 00 90 00 20 1E 81 00 00 5C 14 .dë¦...É. .ü..\. 00000030h: 00 64 89 B1 00 00 00 90 00 20 1E 81 00 00 5C 14 .dë¦...É. .ü..\. 00000040h: 00 20 B9 B8 00 00 00 69 C0 2A C6 91 00 80 26 82 . ¦+...i+*¦æ.Ç&é 00000050h: 00 20 B9 B8 00 00 00 69 C0 2A C6 91 00 40 27 82 . ¦+...i+*¦æ.@'é 00000060h: 00 13 5C 14 00 00 10 59 00 B8 43 86 00 00 AE A1 ..\....Y.+Cå..«í 00000070h: 00 13 5C 14 00 00 10 59 00 B8 43 86 00 00 AE A1 ..\....Y.+Cå..«í 00000080h: 00 80 82 C8 00 20 47 FF 00 00 F8 D7 00 00 F8 ED .Çé+. G ..°+..°f 00000090h: 00 80 82 C8 00 20 47 FF 00 00 F8 D7 00 00 F8 D5 .Çé+. G ..°+..°+ 000000A0h: 00 00 F8 E5 00 00 00 FC 00 00 42 A2 80 38 9A D5 ..°s...n..BóÇ8Ü+ 000000B0h: 00 00 F8 D3 00 00 00 FC 00 00 42 A2 80 38 9A E5 ..°+...n..BóÇ8Üs 000000C0h: 00 31 49 59 00 00 B8 C4 00 20 58 41 00 98 E2 91 .1IY..+-. XA.ÿGæ 000000D0h: 10 31 49 59 00 00 B8 C4 00 20 58 41 00 98 E2 91 .1IY..+-. XA.ÿGæ 000000E0h: 00 80 8E 8A 00 20 E2 48 00 00 B9 48 00 72 F5 C0 .ÇÄè. GH..¦H.r)+ 000000F0h: 00 40 8F 8A 00 20 E2 48 00 00 B9 48 00 72 F5 C0 .@Åè. GH..¦H.r)+ 00000100h: 00 72 91 EC 00 00 00 EA 00 00 D4 C9 00 80 D5 C9 .ræ8...O..++.Ç++ 00000110h: 00 72 91 D4 00 00 00 EA 00 00 D4 C9 00 80 D5 C9 .ræ+...O..++.Ç++ 00000120h: 00 00 80 90 00 92 25 86 00 60 77 C0 00 40 0E 4C ..ÇÉ.Æ%å.`w+.@.L 00000130h: 00 00 80 90 00 92 25 86 00 60 77 C0 00 40 0E 4C ..ÇÉ.Æ%å.`w+.@.L 00000140h: 00 00 00 40 00 00 40 A4 00 00 80 18 80 2C AE A8 ...@..@ñ..Ç.Ç,«¿ 00000150h: 00 00 00 40 00 00 40 A4 00 00 80 18 80 2C AE A8 ...@..@ñ..Ç.Ç,«¿ 00000160h: 00 40 CA 24 60 C6 93 D0 00 F3 98 C0 00 00 00 52 .@-$`¦ô-.=ÿ+...R 00000170h: 00 40 CA 24 60 C6 93 E8 00 F3 98 C0 00 00 00 52 .@-$`¦ôF.=ÿ+...R 00000180h: 00 00 A4 F6 00 00 30 CB 00 00 E1 B1 00 C0 D8 B3 ..ñ÷..0-..ߦ.++¦ 00000190h: 00 00 A4 F6 00 00 30 CB 00 00 E1 B1 00 C0 D8 B3 ..ñ÷..0-..ߦ.++¦ 000001A0h: 00 40 79 C6 00 00 B2 A3 00 C4 D0 91 00 B1 12 39 .@y¦..¦ú.--æ.¦.9 000001B0h: 00 40 79 C6 00 00 B2 A3 00 C4 D0 91 00 B1 12 39 .@y¦..¦ú.--æ.¦.9 000001C0h: 00 00 20 86 00 80 C0 A2 40 96 D8 CC 00 00 00 00 .. å.Ç+ó@û+¦.... 000001D0h: 00 00 20 86 00 80 C0 A2 40 96 D8 CC 00 00 00 00 .. å.Ç+ó@û+¦.... Differences My DP macro and Chuck Moore's code translate each of fifty-one words into the same precode value. The other eight are:
I examined the data above and concluded that the character encoding that Chuck Moore published does not match the character encoding that he used in his source code to produce his lists of pre-parsed words. The four- and five-bit characters seem to have the same encoding, but seven-bit characters are different, notably 'j', 'k', 'z', '0', '1', and '2'. In addition, while my macro observes a strict rule that characters have to fit entirely within the 28-bit character field, Mr. Moore's encoding of the word "accept" breaks this rule. My macro fits the letters "accep" into 25 bits; Mr. Moore adds the 't', thus filling 29 bits. Perhaps Mr. Moore uses another rule that says that if adding a compressed character into a full cell will write one or more bits into the color field, but those bits will all be zeroes, then it's OK to add that last character. But all this is fine. I am happy with my macro for now, and I will use it as is to generate precode for future projects. Summary I've decided that my macro works, even though it produces precode different from that evident in Chuck Moore's code, because my macro conforms to the standard that Moore published. It is possible that Moore has altered his encoding scheme since publishing his standard on the Web, but then it is also possible, based on conversation preserved in the ColorForth Mail-List Archive, that Moore may decide to alter his scheme yet again in future. He seems to want a single text-encoding scheme for ColorForth, and already I am considering two text-encoding schemes at the minimum for Karig — the compressed-character scheme for precode, and normal ASCII for human-readable text. So Moore's published standard is good enough for what I want to do. Check the index for other entries. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
