Tables .
Introduction
Tables are flows of organized Data. For example, you may have a String (which is a Table of Bytes), a Table of Strings, a Table of Pointers to Code, and so on.
Tables may have any number of Dimensions [1 to n], for example, a Table of a visual object might have as well five dimensions (X / Y / depth / time / Color).
Tables may be organized, internally, in as many manners and tricks and tips as the human brain is able build (Simple linear Flow, Look-up, OOP Objects, Linked Lists, XOR Linked List...)
Structures are usual Tables, but this naming is reserved for flows of Data organized in named Members flows. These are particularly used in OS Data organizations.
I write this chapter (I didn't at first think it could be useful), because experience shows that beginners undergo a lot of pain with the choices for how to declare, organize and use Tables. For older programmers, this may seem perfectly evident, but the Messages, at the various Asm Boards, show that this is not evident for beginners at all.
Declaring Tables
We have 3 ways for declaring Tables:
Static Initialized Data
[MyTable: D$ 1 2 3 4 5]
This way is by far the simplest one. We choose it when Data Values may be defined at write time, and when the overall size of the Table is not dramatically large.
Static Un-Initialized Data
[MyTable: D$ ? #5]
This way is also very simple. At launch time the value will be zeroed by the OS when uploading the PE into Memory. The Application takes care of filling these Data when wanted. It is, of course, better to only use these Unnitialized Data, when the overall size of the Table remains under (say, ...) 1000 Octets, or so. Note that Uninitialized Data do not appear at all, in the dead PE File. They only eat as much Memory as Initialized Data, but no Disk space at all. Note also, that the upper given limit (of 1000 Octets, or so...), does not make any sense if the Table is really to be used all along the Application's life. In such (rare) cases, it is as simpler to make use of Static Data, whatever size they could be, as, using Dynamic Memory, in such cases, would make no difference.
Dynamically Allocated Data
These are the Memory areas allocated at run time, by the OS, under the Application's requirements. This way is to be chosen for big Chunks of Memory, particularly in cases when the need of it is temporary (VirtualFree, when no longer used).
[MyTablePointer: ?]
call 'KERNEL32.VirtualAlloc' &NULL 50000,
&MEM_RESERVE__&MEM_COMMIT,
&PAGE_READWRITE
mov D$MyTablePointer eax
As you may guess, this way will introduce one added difficulty: When accessing this Memory (future Table, when filled in with something, just like with Static-Un-Initialized Data), we will no longer say something like:
mov eax D$MyTable + (3*4)
That would only return a wrong value pointing elsewhere into you Data Section. We will then have to add a one Pointer abstraction level:
mov esi D$MyTable | mov eax D$esi + (3*4)
because our static Pointer (MyTable) now holds a Dynamic Pointer to the effective Memory attributed by the OS.
Beginners seem to have some difficulties in making this 'abstraction' jump, from Data physically visible in their Sources, to this more 'virtual' form of Tables. This is an absolute necessity to learn how to implement and use this form of Dynamic Tables in memory.
We regularly see Posts at the Assembly Boards of users wanting always more and more powerful features in order to be able to declare repetitive chunks of Data (Structures usually), without having to type them in, with so many added Sources Lines. They would prefer doing it with any complicated and weird Macros Declarations, than having to assume this intellectual effort. Nevertheless, this is the only reasonable way, and in any case, we have to work with Dynamic memories, particularly in cases of huge and temporary storages. So...
Accessing Tables
Accessing by Labels
Accessing Static Tables and Structures is quite simple:
[Point: @X: 24 @Y: 155]
mov eax D$point@X | mov ebx D$Point@Y
Accessing by Equates
Accessing Tables by Equates is a much more interesting method, really flexible and powerful when having to work with Dynamically declared Tables, or even with Static Uninitialized-Tables:
[MyTable: ? #800]
[Member1 0 Member2 4 Member3 8 Record 12]
mov eax D$MyTable+(Record*5)+Member3
The set of Equates for 'Members' and 'Record' are simple Offsets, given in Bytes, relative to the zero origin. As all of these symbols (including 'MyTable', that the Assembler replaces by a physical Address at compile time) are resolved into a simple number. If 'MyTable', in the PE Data Memory is to be at 0403010, the upper targeted address will simply, at run time be equal to:
0403010+(12*5)+8 ; = 0403054
As the compiler has no limitations when adding / subtracting an immediate, you can guess that there is no limitation at accessing any Member in any dimension of any Table, as long as you previously can tell how long each component of the Table will be.
With a Dynamically declared Table, the only difference would be, as shown previously:
mov esi D$MyTable
mov eax D$esi+(Record*5)+Member3
Multi-Dimensional Arrays
We ask a 1000 people, 1) how old they are, 2) how tall they are, 3) What weight they are, 4) How happy they are.
You could think of this Table, as an Array with 4 Dimensions, and so forth, imagine the physical Table, as composed of 4 different Sub-Tables, where to store the collected information. This is not this, at all: Whatever number of Dimensions a Array may have, we always have to think of it, as an Array of Records. Each person, just like in any Data Base File, will be one Record, that is, in our example, a set of 4 dWords (could be Bytes, here...) holding the relative information.
So, our Table will be like this (Equates access form, Dynamic Allocation):
[HappyPeopleTablePointer: ?] ; Data (Memory Pointer).
; Displacements Equates.
[AGE 0 HEIGHT 4 WEIGHT 8 HAPPY 12 RECORD 16]
call 'KERNEL32.VirtualAlloc' &NULL, (10000*4*4)
&MEM_RESERVE__&MEM_COMMIT,
&PAGE_READWRITE
mov D$HappyPeopleTablePointer eax
Writing, for example, the Weight of the 32nd person, will be:
mov edi D$HappyPeopleTablePointer
add edi ((Record*31) + WEIGHT)
mov D$edi 76
Or simpler:
lea edi D$HappyPeopleTablePointer + ((RECORD*31) + WEIGHT)
mov D$edi 76
Of course, in a real Application, we do not access directly a Record's Member by use of immediates as stated above, to make it simple. We have to access Records and Members through Registers, usually:
; Supposing that the Person Number is in ebx, and that the Member Displacement is in eax:
shl ebx 4
mov D$HappyPeopleTablePointer+eax+ebx 76
Linked Lists
Often times, we may have to work with Tables made of Records with different sizes. In such cases, parsing the whole Table, when searching for one particular Record may be a painful task. A clever way with those cases, is to start each Record by a dWord holding a Pointer to the next record. Example, with a simple Table of Strings (each Record could, of course, contain absolutely anything):
[TableOfString:
String1: D$ String2, B$ 'First string', 0
String2: D$ String3, B$ 'Second String, 0
String3: D$ String4, B$ 'Third String', 0
String4: D$ 0, B$ 'Last String', 0]
Pointers Tables
Instead of having the Records' pointers inside the same Table, a simpler way is to organize them in another independent Pointers Table:
[TableOfString:
String1: B$ 'First string', 0
String2: B$ 'Second String, 0
String3: B$ 'Third String', 0
String4: B$ 'Last String', 0]
[PointersToTableOfString: D$ String1, String2, String3, String4, String4, 0]
This way may be a bit simpler and, in more complicated cases, more flexible and more powerful.
Xor Linked Lists
Xor Linked Lists works the same as Linked Lists, but can be accessed and read in TWO ways: Down-Top and Top-Down. They are not really used, because there are other better and simpler organization methods, but they are a well known 'curiosity' in the programming world. Let us take the same upper example, and make it readable both ways:
[TableOfString:
String1: D$ String2, B$ 'First string', 0
String2: D$ 0, B$ 'Second String, 0
String3: D$ 0, B$ 'Third String', 0
String4: D$ String3, B$ 'Last String', 0]
mov eax String1 | xor eax String3 | mov D$String2 eax
mov eax String2 | xor eax String4 | mov D$String3 eax
Now let us walk the backward through the list: We start at String4, we store the first value, say in ebx. ebx now points to String3. We then xor the ebx value with the one stored at String3: It will point to String2, store the new Position (Label of String3) in ebx again, xor it with the value stored at String2; It will point to String1. It would have worked the same the other way round, with exactly the same Routine starting at Top.
The only real advantage of this technique is to allow saving half of the search operations, in the cases when you can guess that one given Record is more likely among the top half of the List or more likely among the lower half of the List. Though, another real advantage is to show other programmers how great your knowledge is, when you have no more interesting things to show (I mean, for example, like if you have a small penis).
Rotary Tables
Rotary Tables are useful for providing no end Tables, without any care of upper and lower limits (bounds). This technique is based on the fact that, for a Byte, 0FF+1 = 0 (same for a Word: 0FFFF+1 = 0). Also, of course, 0-1 = 0FF, for a Byte (0FFFF for a Word). I have used this, for example, in the RosAsm Source Editor Undo feature, with a Table of 010000 Bytes and for the Right-Clicks moves back and forth, with a Table of 0100 Bytes.
Accessing those Tables through Pointers is quite simple: You just increase / decrease the Pointer by only touching the Byte or the Word of the Pointer, instead of touching the whole dWord Size Pointer. The Table may therefore be considered as a ring. One of the Records must be zeroed and maintained zeroed in order to keep track of the 'Last/First' Record, so that the Application, when walking over the First or Last record, instead of looping no end across the Table, erases the next Record when writing, which is then simply and silently lost, or, when reading, stops running backward at the Record after the zeroed one. Note that the zeroed Record's Position moves along the ring when the Application stores more Records than the Table can hold.
Rotary Tables must be aligned on their size boundary. A simple and ensured way to achieve this alignment is by calling VirtualAlloc (which always aligns the Block of Memory on 010000 for reservations -or on 01000, for Commitments).
LookUp Tables
A LookUp Tables purpose is to provide a quick Value replacement from a given one. There are many well known usages of this technique:
Complete replacements of Strings Characters, given in one ASCII set, by another ASCII set. You just have to declare the new ASCII Table, load the Source Byte, for example, in al and mov al B$MyTable+al will perform the replacement in one single Instruction instead of no end Cases selections.
Various numeric/text translations. Example:
; Reads a Byte, returns the Hexa in ax, with a short Table:
[HexaTable: '0123456789ABCDEF']
OpToHexa:
movzx eax B$esi | inc esi
mov ebx eax | shr ebx 4
and eax 0F | and ebx 0F
mov al B$HexaTable+eax, bl B$HexaTable+ebx
shl eax 8 | or eax ebx
ret
; Could even be much faster with a 256 Word Table giving the 2 Characters in one single Instruction .
Check Tables
A Check Tables purpose is, first, as it says, to provide an easy way for marking an events serial into a Table. Under certain circumstances, it may be also a very precious time saver when you have to store Pointers or Values on the fly, with a sort requirement, at the end of the process. As you may know, sorting Data may contribute to a massively delaying slow down in an Application.
Talking of Pointers, for example, you may prefer to simply set to 1 (&TRUE) the corresponding Bytes in a Check Table instead of storing the real Value of the Pointers into an unsorted Table. When the Checking computations are done; all you have to do is to read the Check Table Values 1, subtract from the reading Pointer Value the Check Table Origin, add to it the Real Pointers Origin,... and save the results back into a fresh new Table, that will then be sorted without any effective sort.
Just a very simple example. In RosAsm Disassembler I am in need, first, to know what is Code and what is Data. This is not always easy to decipher, because in most PEs Code and Data may be living together mixed inside the same section...
So, the Disassembler starts, first a 'Try&See' Disassemblage, from the PE Entry Point. Each time it points out valid Code, and/or valid CALLs and JMPs to another area of the PE, it _Flags_ it in a so called 'Check Table'. That is simply, a VirtualAlloc Table the same size as the Disassembled PE. When it finds some Code, it writes the Value 1 in the corresponding Byte, in the Check Table. Each time it finds out some ensured Data Evocation, it flags the corresponding Bytes, in the Check Table with the Value 2, and so on.
So, at the end of the Analyses, we have a Table, that is nothing but an 'image' of the disassembled PE, and that tells what is what.
There are many other kinds of Check Tables, but I suppose that this example can show you the overall story. It does not create any list of Code and Data Chunks, does not sort anything. Just Flagging, and that's all.
You can imagine any number of similar problems. Let's say, that you want to know where the vowels are, inside a String. You could create a table for storing all encountered vowels, with one record per vowel, pointing to each vowel.
Simpler, you can also create an zeored String, the same length as the original string, and parse the String. Then each time you encounter a vowel, in the original String, you write 1 at the same Displacement in the 'image buffer', and it's done.
So, to summarize, a Check Table is a Memory Chunk that is used to map references to other data structures in order to represent specific elements of that other data.
1. The programmer defines a mapping criteria.
2. The programmer determines the specific elements of the data structure that the check table maps to.
Once a check table is created, if info on the specific elements is needed, the programmer only has to refer to the check table instead of the other data structure. Several Check Tables may provide various informations and references to the same Data, so that, when scanning the Data, it is quite easy read in parallel as many Check Tables contents by a simple TablePointer(s) switch(es).
CheckSums Tables
Often times called Hash Tables, the CheckSums Tables are used to store and to retrieve Data on the base of Named Variables.
The CheckSum
Considered alone, the CheckSum (or the Hash), is nothing but the result of a Computation, that, from a given flow of Bytes, achieves into a Binary Number, that will be used to point directly into the Storage Table.
For building this Number (or a derivated indice) from a Name, many Algorithims have been developed. For this Computation only, two points are to be considered: The Speed of the Computation and the quality of the results. The quality of a CheckSum Algo is to be evaluated in terms of randomness, this is to say that, the better the Algo is, the more the Repartition of the Records, in the Table, will be similar to a random repartition.
The Algo used by RosAsm is an original one, that I created for the implementation of the Assembler Management of the computed Source Symbols:
CheckSum64:
; esi -> Name
mov eax 0, ebx 0, ecx 0
While B$esi > ' ' ;LowSigns
rol eax 1 | lodsb | mul eax
xor ebx edx | inc ecx
End_While
add ebx ecx
If eax = 0
On ebx = 0, mov eax 1
End_If
; ebx:eax = CheckSum64
ret
Many other Algos are several pages long, but not significantly faster and do not give better Repartitions, for the very best of them.
Then, once this Algo is chosen, comes the considerations about the design of the Storage Table.
The Storage Table
Here also, there are as many Methods as you could imagine, but, basically, the generic principle is really quite simple:
We define whatever form of Records we mean to store into the Table.
As long as no CheckSum can be guaranteed to be unique, we define the mechanism that will be used to assume the cases of conflicts (two different Names achieving into the same CheckSum64 and/or CheckSum16, or whatever size of the derived Indice...).
We define the size and structure of the Table.
For RosAsm Assembler, the Symbols Table is a huge Table, that is, in fact, a Double-Table:
[CheckSumsRecords: ? ? ? ? #010000
CheckSumsLinkedRecords: ? ? ? ? #010000]
Where each Record ('... / ?, ?, ?, ? /...') is in the form of CheckSum64 / Pointer / Link, and where the CheckSum64 Member represents the ebx:eax, as returned by CheckSum64, where Pointer is a Pointer to the internal Data, as used by the Assembler, and where Link points to the next same CheckSum Record, in cases of conflicts (same CheckSum, different Symbol). When a Link Member is found, it points somewhere into the second Table, to the next matching Record.
So, as long as a Record is found empty, in the first Table, the Data are stored there, on the random-like basis of the CheckSum16 Indice, and when a Record is found occupied, the Link Member, is taken and the Data are stored into the second half Table, top-down, and linked.
Given the requirements of such a Tables System, as used by the Assembler, - that is not that simple -, let us take another example, that will be simpler to understand. This same Method is also used by RosAsm, on Start-Up for computing the Win32 Equates List, so that the Assembler could retrieve the value of, say '&TRUE', in almost no time.
This particular usage is simpler, because the CheckSum64 of all the Win32 Equates are verified and known to be unique, before the releases of the 'Equates.equ' file. In fact there are extremely few chances for any CheckSum64 to ever conflict with another one. So, here, the Records are in the form of: CheckSum64 / Value / Link. This is to say that the Values of the Win32 Equates are directly stored into the same Record Value member.
Let us see, first, how the Win32 Equates are stored into the CheckSums Tables. First, we are reading the 'Equates.equ' File, that is in the form of:
0_REG 010
A1_REG 011
......
AAL5_MODE_STREAMING 02
......
AA_CLOSE 08
......
and so on...
We have esi pointing to an Equate Name:
call CheckSum64 | call CheckSum16
Now, we have the CheckSum64 Values of the Equate Name in ebx:eax. From this 64 Bit Value, we created one other 16 Bit Value, in ecx, that will be used, as an Indice, to point into the first Table. In between we also call for a small Routine for converting the Value, as found in the File, from its Ascii form, to a Binary from, in ecx.
So, we can now point into the first table. If it is found free, we write directly there:
.If D$CheckSumsRecords+ecx = 0
On D$CheckSumsRecords+ecx+4 <> 0, jmp L1>
mov D$CheckSumsRecords+ecx eax
mov D$CheckSumsRecords+ecx+4 ebx
move D$CheckSumsRecords+ecx+8 edx
.Else
If found occupied, we take the Link Record, and search until a free Record is found, in the second Table:
.Else
L1: If D$CheckSumsRecords+ecx+12 = 0
move D$CheckSumsRecords+ecx+12 D$PointerToCheckSumsLinkedRecords
Else
mov edi D$CheckSumsRecords+ecx+12
While D$edi+12 <> 0
mov edi D$edi+12
End_While
move D$edi+12 D$PointerToCheckSumsLinkedRecords
End_If
At this point, we do the same as for a prime time recording, plus, we fill in the Link Record, of the previously found occupied Record, in order to build a kind of logical tree, having its first root in the first Table, and its linked branches, in the second Table:
mov edi D$PointerToCheckSumsLinkedRecords
mov D$edi eax
mov D$edi+4 ebx
move D$edi+8 edx
add D$PointerToCheckSumsLinkedRecords 16
.End_If
Writing and reading
Whatever particular implementation writing into such a Table is just a matter of pointing out an empty slot, and reading a Value matching with some given Name, is, simply:
Rebuilding the CheckSum 64 and the CheckSum16
Pointing to the displacement, into the Table, at the Indice given byte the Indice CheckSum
Reading the stored CheckSum64
Comparing or not (depends on the implementation) the searched Name to the stored Name.
All of this is extremely fast. For example, when RosAsm encounters, say, some '&TRUE', in your Source, it simply does:
ReadWin32Equate:
call CheckSum64 | call CheckSum16
mov esi D$NewWinEquatesMem | add esi ecx
L0: .If D$esi = eax
If D$esi+4 = ebx
mov eax D$esi+8, B$EquateFound &TRUE | ret
End_If
.End_If
mov esi D$esi+12 | cmp esi 0 | jne L0<
mov B$EquateFound &FALSE
ret
which takes almost no time, even in the cases when two different Win32 Equates could have the same CheckSum16, as the whole thing is resolved by simply switching the Pointer to the Linked one, and looping for two comparisons, until a matching Record could be found, parsing, at once, 65,536 Records, at each loop.
For the RosAsm Symbols Tables Management, one String comparison is done, when storing, in case when a matching Slot is found, in order to control the duplications of Symbols Declarations, and one String comparison is done, when reading, to make sure that we are not facing a case of CheckSum64 conflict (requiring, also, a Linked Record).
These methods are one of the reasons why RosAsm is the fastest of the actual Assemblers, and many variant implementations can be invented from this basis:
Compute a CheckSum64.
Compute a smaller CheckSum from the CheckSum64.
Declare a Double-Table, with a size, - depending on the smaller CheckSum and on the definition of a Record -, where, it could be used as an Indice.
Defining Records that include a dWord, for the possible Linked Records.
Accessing the Records of the Double-Table, either directly for the empty Slots, in the first Half Table, or by Link Pointers for the occupied Slots, the Links always pointing to the Second Half Table.
~~~~~~~