Integer Math Instructions ..
Add
Adds Source to Destination:
mov eax 100
add eax eax ; eax = 200
(Flags set on if overflow)
Sub
Subtracts Source from Destination:
mov eax 100
sub eax 10 ; eax = 90
(Flags set on if overflow)
Inc
mov eax 12
inc eax ; eax = 13
Dec
mov eax 12
dec eax ; eax = 11
Mul
Multiplies eax by the given 32 Bits operand and stores the result in edx:eax
(Multiplies ax by the given 16 Bits operand and stores the result in dx:ax)
(Multiplies al by the given 8 Bits operand and stores the result in ax)
mov eax 24
mov ecx 10
mul ecx ; edx = 0 / eax = 240
iMul
This instruction has 3 forms. The first one is just like upper mul:
Multiplies eax by the given 32 Bits operand and stores the result in edx:eax
(Multiplies ax by the given 16 Bits operand and stores the result in dx:ax)
(Multiplies al by the given 8 Bits operand and stores the result in ax)
mov eax 24
mov ecx 0-10
imul ecx ; edx = 0 / eax = -240
Form 2 is, for example:
mov eax 24
mov ecx 0-10
imul ecx eax ; ecx = -240
imul ecx 2 ; ecx = -480
Form 3 is, for example:
mov eax 24
mov ecx 0-10
imul edx ecx eax ; edx = -240
imul edi edx 2 ; edi = -480
Div
Divides a number in edx:eax by the given 32 bits argument. Result in eax
(Divides a number in dx:ax by the given 16 bits argument. Result in ax)
(Divides a number in ax by the given 32 bits argument. Result in al)
mov edx 0 ; zeroed edx (high dWord of 64 Bits)
mov eax 101 ; Value to be divided
mov ecx 10 ; Divisor
div ecx ; eax = 10 / edx = 1
Quotient in eax (/ ax / al); Remainder in edx (/ dx / ah).
Lets write a real life Macro example to adapt a size to user screen size (our development computer screen size is 800/600 and we want the user to see about the same things as we do):
[AdjustSizeToUserScreen | mov edx 0
mov eax #1 | mul D§UserScreenDim.X
mov ecx 800 | div ecx | mov #1 eax | #+1]
; ...
; ...
AdjustToScreenSize D§MyBoxWidth D§MyBoxHight
iDiv
Divides a number in eax by the given 32 bits argument. Result in eax
(Divides a number in ax by the given 16 bits argument. Result in ax)
(Divides a number in al by the given 8 bits argument. Result in al)
Quotient in eax (/ ax / al); Remainder in edx (/ dx / ah).
mov eax 0-26
cdq ; see next paragraph (edx holds the sign)
mov ecx 10
idiv ecx ; eax = 2 / edx = 6
cdq / cwd / cbw
For iDiv instruction, we need to extend the declared sign of our value to edx / dx, because the division applies on these Registers pairs. cdq / cwd (Convert dWord to qWord / Convert Word to dWord) perform this required operation. cbw (Convert Byte to Word) does the same for ah Register for 8 bits divisions.
~~~~~~~
Shifting and Rolling ..
Shifting and Rolling are the acts of moving all the Bits of a Byte / Word / dWord to the right or to the left. Rolling recovers the 'pushed out' bits and reintroduces them at the opposite side.
Sal / Shl (Shift Arithmetic Left / Shift Logical Left)
7 < 6 < 5 < 4 < 3 < 2 < 1< 0
__| __| __| __| __| __| __| __| <<< 0
|
>>> CY (Lost)
(CY means that the Carry Flag is set on, if the kick-out Bit was set on (1).
mov al 00_1111_1111
shl al 3 ; al = 00_1111_1000
shl is often used to perform fast ^2 multiplication. In the upper example, al is multiplied by 8 (Think of 3 as: 2 / 4 / 8 instead of 1 / 2 / 3).
Sar (Shift Arithmetic Right)
7 > 6 > 5 > 4 > 3 > 2 > 1> 0
__| __| __| __| __| __| __| __| >>> CY (Lost)
|
<<< Hb
(Hb means that the first high Bit (the first left 'x') is reintroduced (instead of a zero. This particular Shifting operation is for signed numbers (very few used...).
(CY means that the Carry Flag is set on if the kick-out Bit was set on.)
mov al 00_0011_0001
sar al 1 ; al = 00_0001_1000 / CF = 1
sar al 1 ; al = 00_0000_1100 / CF = 0
mov al 00_1011_0001
sar al 1 ; al = 00_1001_1000 / CF = 1
sar al 1 ; al = 00_1100_1100 / CF = 0
mov al 00_1000_0000
sar al, 3 ; al = 1111_0000
Note that while shl and sal are the *same* instruction, shr and sar differ in that shr fills the ''vacated'' bits with zero, sar fills the ''vacated'' bit with the ''sign bit'' (the leftmost, most significant bit) of the original value - thus useful for signed numbers.
Shr (Shift Logical Right)
7 > 6 > 5 > 4 > 3 > 2 > 1> 0
__| __| __| __| __| __| __| __| >>> CY (Lost)
|
<<< 0
mov al 00_1011_0001
shr al 1 ; al = 00_0101_1000 / CF = 1
shr al 1 ; al = 00_0010_1100 / CF = 0
Rcl (Rotate with Carry Left)
7 < 6 < 5 < 4 < 3 < 2 < 1< 0
__| __| __| __| __| __| __| __| <<< (CY)
|
>>> (CY)
Rcr (Rotate with Carry Right)
7 > 6 > 5 > 4 > 3 > 2 > 1> 0
__| __| __| __| __| __| __| __| >>> (CY)
|
<<< (CY)
Rol
7 < 6 < 5 < 4 < 3 < 2 < 1< 0
__| __| __| __| __| __| __| __| <<< Lb
|
>>> (Lb+CY)
(Lb means Low Bit (the first(s) right 'x')
The Carry Flag is set too, according with the last rotated bit; The difference between rol and rcr is that rcr uses the Carry flag as a ninth Bit, whereas rol does not.
mov al 00_1011_0001
rol al 1 ; al = 00_0110_0011 ( CF = 1)
rol al 1 ; al = 00_1100_0110 (CF = 0)
Ror
7 > 6 > 5 > 4 > 3 > 2 > 1> 0
__| __| __| __| __| __| __| __| >>> (Hb+CY)
|
<<< Hb
mov al 00_1011_0001
ror al 1 ; al = 00_1101_1000 ( CF = 1)
ror al 1 ; al = 00_0110_1100 (CF = 0)
~~~~~~~
Logical Instructions ..
The simpler way to understand the Logical Instructions is to think of them in Binary format. and, or, xor, not, test, as they only apply on Bits.
And
0 and 0 > 0
0 and 1 > 0
1 and 0 > 0
1 and 1 > 1
The result is 1 only when both bits are 1
Example, we have a Char in AL. This Char is known to be in the range of 'A-z'. Hexa ASCII code for 'A' is 041. Hexa ASCII code for 'a' is 061. The difference between 'A' and 'a' is 020 (decimal 32, Binary 0010_0000. So, we can consider that, for insuring that a Character will be Upper Case, we just have to ensure that this bit is zeroed:
mov al 'd'
and al 00_1101_1111 ; al = 'D'
Or
0 or 0 > 0
0 or 1 > 1
1 or 0 > 1
1 or 1 > 1
As you can see if either of the compared bits is 1 the result is 1.
Example: Ensure that a number is odd:
mov al 10
or al 1 ; al = 11
Xor
0 xor 0 > 0
0 xor 1 > 1
1 xor 0 > 1
1 xor 1 > 0
If the source Bit is set to 1, the destination Bit is inverted.
Example, the user of our application can set a feature On/Off with a Check Button. We retrieve this given information in a Value that can be either TRUE or FALSE to enable disable the feature:
If B§UserClickOnConfig1CheckBox = &TRUE
xor B§FlagForFeature1 &TRUE
End_If
Or even more concise:
mov al B§UserClickOnConfig1CheckBox
xor B§FlagForFeature1 al
Not
Not reverses all the target bits:
mov eax 0FF
not eax ; eax = 0_FFFF_FF00
You can consider this operation as a reversing sign one (for signed numbers), but:
mov eax 12
not eax ; eax = -13
...because of the Data Representation of signed Numbers. neg is the instruction of choice for this:
mov eax 12
neg eax ; eax = -12
Test
Test is just like some and operation that would not modify the target. The flags are set, depending on the result of this and operation. Example; checking if a signed Byte value is negative or positive:
test al 080 | jz Positive
; if here sign bit was on.
Positive:
(080 = 00_1000_0000 = high bit for a signed Octet, used as a '-' marker)
~~~~~~~
Moving_Flags ..
See the Flags Register in Flags_and_Jcc. See how Conditional Jumps are affected by the Flags in Jumping.
The main Flags management is done by the processor itself when running Instructions. You can't modify the Flags Register directly. For this you have to use two instructions: Pushf / Popf
pushf
pop eax
or eax, 1 ; set ZF on
push eax
popf ; Done.
Two other instructions are available for Flags management: Lahf / Sahf. Do not use them. They will no longer be available under 64 bits processors.
Another regular way for modifying the Flags states is to use these instructions:
stc - sets carry flag
clc - clears carry flag
cmc - complements (reverses) carry flag
std - sets direction flag (to ''down'')
cld - clears direction flag - direction flag should *always* be returned to it's
''up'' (cleared) condition if you've set it ''down''!!!
sti - sets interrupt flag
cli - clears interrupt flag
The more common way for working with the Flags is to use the Conditional Jumps instructions. See Jumping.
~~~~~~~
Moving_Data ..
Mov
Move_to Destination, Source:
mov ebx 1 ; ebx = 1
mov eax ebx ; eax = 1
[Data: 24]
mov esi Data ; esi = Whatever Memory Address where ''Data'' is stored
mov eax D$esi ; eax = 24
[BytesData: B$ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
mov al B$BytesData+4 ; al = 4
[dWordsData: D$ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
mov eax 5 | mov al B$dWordsData+eax*4 ; al = 4
Movzx / Movsx
Move_to Destination (Reg32) , Source (Reg/Mem 8/16), Zero or Sign extended:
movzx ebx B$edi ; Byte at ebx = 1 >>> ebx = 1
movsx eax W$esi ; Word at esi = -03A >>> eax = -03A
LEA (Load Effective Address)
LEA loads in the destination register, the Address of a given Data (noted as Value):
[MyTable: 25 #32]
lea esi D$MyTable ; esi = MyTable Address
This is to say that upper statement does exactly the same as:
mov esi MyTable
LEA is often used as is in a wrong syntax assembler (like MASM) to retrieve the Address of a symbol previously declared with a Data typing.
Hopefully, the real interest of LEA, compared to MOV resides in its extended forms. These extended forms are nothing but the ones of Effective_Address notation:
[MyTable: 111 222 333 444 555]
mov D$WhatIndex 3 ;DD
; ....
; ....
mov ebx D$WhatIndex
lea eax D$MyTable+ebx*4
mov ecx D$eax ; ecx = 444
You can consider that upper LEA does the same as a mov instruction (which does *NOT* exist in the x86 instruction set), like:
mov eax MyTable+ebx*4
The multiplication (*4) can only be *2 / *4 / *8. The maximum syntax for LEA is, for example (you can add only one constant):
lea eax D$Table + ebx*4 + edx + 12
... what does, in one single instruction, the same as:
mov eax ebx | shl eax 2 | add eax MyTable | add eax edx | add eax 12
Besides use for retrieving an indexed pointer to a table, LEA can be deturned from its original target to perform fast integer multiplication with possible move and immediate addition in one instruction:
lea eax D$ebx*2-1 ; eax = (ebx*2)-1
lea eax D$ebx*2+ebx ; eax = ebx*3
lea eax D$ecx*4+24 ; eax = (ecx*4)+24
lea eax D$ebx*4+ebx ; eax = ebx*5
lea eax D$eax*8-02000 ; eax = (eax*8)-02000
lea eax D$eax*8+eax ; eax = eax*9
Xchg (Exchange)
mov eax 1 | mov ebx 2
xchg eax ebx ; eax = 2 / ebx = 1
Like as with the MOV instruction, one member can as well be a Memory Location :
xchg edi D$PreviousPointer
Push / Pop
Push and Pop, Store/Restore to/from the Stack the given member. So, you can use them, for example, to move some value from memory to memory (Note there is no particular instruction for this with x86 CPUs):
push D$Value1 | pop D$Value2 ; D$Value2 = D$Value1
Instead of:
mov eax D$Value1 | mov D$Value2 eax
I often use a Macro for exchanging the Values in two dWords Memories:
[Exchange | push #1 | push #2 | pop #1 | pop #2]
[Value1: 1 Value2: 2]
Exchange D$Value1 D$Value2 ; D$Value1 = 2, D$Value2 = 1
~~~~~~~
String_Instructions ..
String instructions do not exclusively apply only to string Data types, but are called so, because they often do.
Strings REPetition instructions are known for being slow under Intel Processors. Usually programmers tend to optimize their Coding by replacing them by other, not so slow, Instructions, doing 'by hand' what these Strings Instructions are supposed to do. Do not be afraid of slowing down your Applications with these. This is not our job, as programmers, to take care of Intel Processors speed. AMD Strings Instructions are perfectly effective and fast. So, if your Applications slow down, because of Intel, this is not your problem. This is Intel's problem. RosAsm itself is at least 4 times slower under Intel equivalent Processors, and I don't feel, in any manner, concerned with this.
Lodsb / Lodsw / Lodsd (LODSB)
Read a Byte / Word / Dword at the address pointed by ESI register, store the content encoded value in AL / AX / EAX and increment ESI, according with the chosen Data size.
[StringData: 'abcd', 0]
mov esi StringData | lodsb ; al = 'a'
lodsb ; al = 'b'
lodsb ; al = 'c'
Lodsb does the same as:
mov al B$esi | inc esi
lodsd does the same as:
mov eax D$esi | add esi 4
Std / Cld (STD CLD)
The default behavior of the String Instructions is to work forward, but you can have them working backward with STD instruction (Set Direction Flag on).
[String: B$ 'abcdefg' EndOfString: 0]
mov esi EndOfString
std
lodsb ; al = 0
lodsb ; al = 'g'
lodsb ; al = 'f'
lodsb ; al = 'e'
cld
CLD (Clear Direction Flag) resets the flag to zero. You have to consider this flag state (Off) as the default one, and to indent STD / CLD nested instructions (consider unpairing a disastrous fault with these instructions of the same gravity you would consider as with PUSH / POP unpairing...).
Stosb / Stosw / Stosd (STOSB)
Just do the reverse of Lodsb, ... operations. They store Bytes, Words, Dwords given in AL / AX / EAX at the location pointed by EDI and increase / decrease EDI according with the Data size and Direction Flag.
[PointsString: '..............']
mov edi PointsString
mov al 'a' | stosb
mov al 'b' | stosb
mov al 'c' | stosb
; Now, the Memory at PointsString is: 'abc.......'
Rep (REP)
The REPetition Instruction(s) gives all the desirable power to String Instructions. It can be extended with condition markers: REPE (repeat while Equal), REPNE (Repeat while Not Equal), and so on.
REP repeats attached instruction ECX times.
[Table: B$ ? #100]
mov edi Table | mov ecx 90 | mov al 'x' | rep stosb
; 'Table' Memory is 'xxxxxxxxxxx............' (90 'x')
; Searching for the end of Table String:
mov edi Table | mov al 0 | mov ecx 100 | repne scasb
; (edi now point to the second first zero in Table).
Movsb / Movsw / Movsd (MOVSB)
Movsb reads a byte at ESI and writes this byte at EDI. Then, it increases ESI and EDI. Movsb does the same as a paired Lodsb / Stosb, but AL / AX / EAX registers are not modified.
[String1: 'abcde' String1Length: Len]
[String2: B$ 0 #100]
mov esi String1 | mov edi String2 | mov ecx D$String1Lenght | rep movsb
; Now, The Memory at String2 is: 'abcde', 0 0 0 0 ...
Cmpsb / Cmpsw / Cmpsd (CMPSB)
... Compare(s) the byte(s) at EDI with the byte(s) at ESI and increments ESI and EDI. The Flags' status are set according with the result of the comparison, (to be tested with Conditional JMPs):.
[String1: 'abcde' 0]
[String2: 'abcde' 0]
mov esi String1 | mov edi String2 | mov ecx 5
repe cmpsb | je Same
; If here, the strings were different
Same: ; If here, the strings were same.
Scasb / Scasw / Scasd (SCASB)
Is (are) used to search at EDI for a given value previously stored in AL (AX, EAX). Let us end this Chapter with a real life example. Screen Savers are run by Zindoz with a Command Line that can have several forms. This Command Line could be, for examples:
''C:\Windows\System\MyScreenSaver.scr/P 1176''
or: ''C:\Windows\System\MyScreenSaver.scr/S''
'S' and 'P' are to define in what mode the Saver is expected to run (S > Saver mode / P > Preview mode, ...). When the line is ended by a decimal ASCII number, this number is the Handle of the caller (The Screen Savers installer main window Handle). We are going to retrieve these parameters :
call 'KERNEL32.GetModuleHandleA' 0 | mov D$hInstance eax
call 'KERNEL32.GetCommandLineA' | mov D$CommandLine eax
; Go to the end of Command Line:
mov edi eax, al 0, ecx 0FF | repne scasb | sub edi 2 | mov esi edi
; After ''repne scasb'', EDI points to the character following the ending zero.
; We get back 2 characters so that:
; EDI now points to either '6' or 'S' in each upper Command Lines examples.
mov eax 0, ecx 0
L0: On B$esi-1 < '0', jmp L1> ; Search for the start of
On B$esi-1 > '9', jmp L1> ; possible Decimal number Handle.
dec esi
jmp L0<
L1: push esi ; esi > either '1' or 'P' in upper example.
L2: lodsb
On al > '9', jmp L9> ; Compute possible Handle
On al < '0', jmp L9>
sub al '0' ; convert Decimal to binary:
lea ecx D$ecx+ecx*4 ; ecx = ecx * 5
lea ecx D$eax+ecx*2 ; ecx = eax + old ecx * 10
jmp L2<
L9: pop esi
; If the Command Line was our first example, ecx = 1176 and al = 'P'.
; If the Command Line was our second example, ecx = 0 and al = 'S'.
~~~~~~~
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.
~~~~~~~
Aligning Data ...
When an Instruction accesses a Memory location, for reading or for writing, if the targeted data is not aligned, in Memory, on its own Boundary, the Processor performs two Memory accesses instead of one. To prevent this penalty, you have to take care of always aligning your data on their own Boundary.
Aligning a Byte Data on its own boundary: Nothing to do.
Aligning a Word Data on its own boundary: The binary form of the Address must be 00_xxxx...xx00
Aligning a dWord Data on its own boundary: The binary form of the Address must be 00_xxxx...0000
Aligning a qWord Data on its own boundary: The binary form of the Address must be 00_xxxx...0000_0000
You may use an Align_On Macro, for doing this:
[Align_on | add #2 #1-1 | and #2 0-#1]
> Align_On 8, edi ; 8 or any Power of 2.
When declaring Data with RosAsm, each time you open a new Square Bracket, RosAsm does the alignment for you, by default. (You may get rid of it, as explained in the RosAsm Manual). RosAsm's default Alignment is on four Byte Boundaries. See how to force this alignment to another boundary in the RosAsm Manual in Data_Management.
There is not only a real speed consideration with this: In the new Windows versions, the Api Functions are more and more sensitive to the Alignment of Data, particularly for Structures. Some Functions would simply fail, if the provided Structures are not aligned on four Byte boundaries.
~~~~~~~
Unions .
The Union concept is nothing but providing several Names (Data Addresses Symbolics) for the same Address. Programmers with some previous HLL experience are often times a bit lost with not having a concept like HLLs Unions in Assembly. In fact, we do have it, for free:
[DwordData:
WordData1:
ByteData1: B$ ?
ByteData2: B$ ?
WordData2:
ByteData3: B$ ?
ByteData4: B$ ?]
The upper Declaration is a Union for a Data area that can be accessed either as one single dWord, or two different Words, or four different Bytes.
~~~~~~~
Strings in Assembly ..
Under modern OSes, Strings come in two flavors : Bytes Flows and Words Flows. I will describe only the Bytes Strings form here. The same rules apply, of course to the Words Strings form. The Bytes Strings are known as ASCII Strings and the Words Strings as Unicode Strings. Many Api Functions have two forms, ending by ''A'' and by ''W'' that reflects the Character sizes of the Strings concerned by the called Functions.
Unicode Strings are for oriental Languages (requiring many more Characters than the alphabetic system).
So, ASCII Strings are nothing but Flows of Bytes, each Byte representing one Character. Example: the Space Character is represented by the ASCII Value 020 (32d).
A bit of History
The complete Table of ASCII Characters is, - as you may guess when talking of Byte Values - , 256 Characters long. Several aspects of this Table cannot be understood without first considering its historical evolution.
In the earlier days of Personal Computers, that worked in Text Mode, the position of the Caret, on the screen was controlled by the ASCII Characters themselves, in the Printing Interruptions. So, the lower Bytes from 0 to 31 were reserved as control characters. For example, I remember that, at that time, I wrote a Prompt (Command Line Invitation) doing a lot of things at once. It was showing the Path and the Prompt, printing the Time in the upper Right corner, and other things like this, in various colors. The Prompt Command was managing the Caret movements by these Control Characters. Needless to say, these things are obsolete in PC's for a long time, but, the ASCII Codes, for moving the Caret on the screen, for example, still have their place inside the ASCII Table, which was developed with the advent of Teletype machines to send telegrams and telexes worldwide over wires long before any type of computers ever existed on this earth. In fact the the early mainframe computers used Teletypes to allow humans to talk with the CPU.
Linux users should be aware they have TTY devices in their systems. These control characters have their names such as <carriage return> and <line feed> copied from those ancient things called typewriters. Which had carriages, which held the sheet of paper between its platen and rollers, typing on one line at a time. The carriage was then returned to position it to the start of the left column and the platen rolled up to go to the next line, in effect the paper feed. Our keyboards are laid out in the same way as those old typewriters ....in some ways things change and yet remain the same.
There are still in use, even today, mainframes with Teletype interfaces......
You may wonder, for example, why, for going to next Line, we have usually to provide *two* Control Chars: CR/LF (13, 10). Historically, this is because the original meaning, in PC's of CR -Carriage Return- simply was ''Put the Caret in the first Row'', whereas the original meaning of LF -Line Feed- was ''Push the Caret one Line down''.
In the DOS time, the ASCII Table had a version in Memory (Graphics Table), which the upper half of it, was available for Pseudo-Graphical outputs. Usually, this upper part was for drawing Boxes, for example, with double or single lines. Many older Programmers were used to Poking them for building Sprites by Characters. The Good old days... ;)
Organization of the Alphabet inside the ASCII Table
You may view the ASCII Table, from RosAsm, by running [Tools][ASCII Table]. The very first Character to memorize is the Space (020 / 32). Then, two other important positions to consider are the ones of 'A' and 'a' Characters. As you may see, RosAsm's ASCII Table is organized by Row of 32 Characters, that helps viewing the parallelism between the Upper and lower Cases Characters.
For having any upper case Character made lower case, or reverse, all you have to do is add or subtract 32 from its ASCII Value. In fact, we never do this that way. To insure that a Character is Low or Upper Case, we do, for example:
> or B$MyString 020 ; >>> Lower case.
> and cl (not 020) ; >>> Upper case.
Viewing this in Binary (020 = 00_0100000):
7 6 5 4 3 2 1 0
_0| _1| _0| _0| _0| _1| _1| _0| = ''F''
7 6 5 4 3 2 1 0
_0| _1| _1| _0| _0| _1| _1| _0| = ''f''
Another interesting part of the Table is the part with the Numeric Characters. As you see, for translating a Value smaller than 10 into the its corresponding ASCII Character, all you have to do is:
> add al 030 ; If al was 3, it now is ''3''.
... or, same but neater:
> add al '0'
A stupid difficulty comes from this organization: As the 'A' Character does not come right after the '9' Character, (there are seven ASCII Characters between these two), for Printing HexaDecimal forms of a number, we have to add (sub) 7 to (from) the upper values (0A to 0F) because of this 'hole' between '9' and 'A', during the translations between Binary and Hexdecimal.... Too bad... ;)
Strings in Memory
Declaring a String:
> [MyFirstAsciiString: B$ 'Hi! you!', 0]
Most often, Strings are zero ended. For example most of the Api's expect Zero ended Strings: The operations stop when encountering the zero. Even if you are using ASCII Strings, and not Unicode Strings, you may be in need of some Unicode Strings for some Functions (For example, in Resources Templates, the Strings are always Unicode). In these cases, the Declaration is:
> [MyFirstUnicodeString: U$ 'Hi! you!', 0]
Which is identical to:
> [MyFirstHandMadeUnicodeString: B$ 'H', 0, 'i', 0, '!', 0, ' ', 0, 'y', 0, 'o', 0, 'u', 0, '!', 0, ', 0, 0]
Strings in Registers
Any Register may contain ASCII Chars, in the same way they may contain any other Value, with the usual respect of Sizes:
> mov al 'a'
> mov eax 'abcd'
Some older Assemblers, when encoding such a Statement as mov eax 'abcd', perform the Bytes reversing as they do for Values. That is, in Memory, 'abcd', once reversed, is stored as:
064, 063, 062, 061 .... That is: 'd', 'c', 'b', 'a'.
Of course RosAsm does what you expect to have, instead, without reversing these Strings Bytes.
~~~~~~~