Page 1 of 1

## Lists, Vectors, Queues and Stacks In MASM x64 Assembly

### #1 Martyn.Rae

• The programming dinosaur

Reputation: 556
• Posts: 1,436
• Joined: 22-August 09

Posted 10 November 2018 - 11:16 PM

My apologies, the title should read Lists, Vectors, Queues And Stacks In MASM X64 Assembly

Lists, Vectors, Queues and Stacks

What we are going to look at in this tutorial is lists, vectors, queues and stacks. More specifically, why the industry has ended up with them in the standard templates library. Is there a difference between these types or not? Let's take a look at them individually so we are sure we are reading from the same page!

Lists

Google defines a list as a number of connected items or names written or printed consecutively, typically one below the other. In computer terms it is probably more appropriate to say a list is a number of connected items held as a collection. For example, we could have a list of strings or a list of objects held in a collection.

Seen from an implementation perspective, lists are generally held as a set of chained objects where the chain is either a single forward pointer to the next object in the chain or two pointers used to reference the next and previous objects in the chain.

Lists are used when the objects that are contained within the container are relatively static. Inserting an object into the chain anywhere except the head or the tail of the list requires that entries are examined one by one down the chain until the insertion point is located. For very large lists this can be somewhat time consuming.

Vectors

A vector is a collection of objects where a specific object can be located via an index (anybody have a better description?). For example, a machine code instruction number is a vector into the microcode used to implement that instruction.

Vectors are extremely fast in terms of accessing a specific object but are somewhat slow in terms of insertion and/or deletion. Objects from the insertion point to the end of the vector table have to be moved either down in order to obtain a 'hole' in the vector table to be used for the inserted object. Objects from the deletion point to the end of the table have to be moved up to remove the 'hole' where the deleted object was. Without taking these actions, the integrity of the vector table would be compromised.

Vectors like lists tend to be used in situations where the overall collection remains static.

Queues

A queue is a collection of transient objects that are added and removed from either the head or tail of the collection normally implemented on a first in/first out principle.

Queues are really a specialised form of a list were one can push onto the tail of the queue and pop from the head of the queue.

Stacks

Stacks like queues are really a specialised form of a list were one can push onto the tail of the queue and pop from the tail of the queue or push onto the head of the queue and pop from the head of the queue (depending on whether the stack grows downwards or upwards).

Implementation of Lists, Vectors, Queues and Stacks Using A Common Approach

What we are going to do is to implement the list, queue and stack as a vector.

We loose no functionality in doing this as we can transverse a list using an index pointer. So the next object in the list would be the index of the current object + 1 and the previous object in the list would be the index of the current object - 1. We can insert objects into and delete objects from the vector collection at the expense of adding and removing holes in the vector table itself.

The API

The API (which just happens to be called List) consists of 6 functions:-

• CreateList
• InsertItem
• DeleteItem
• GetItem
• GetNumberItems

The implementation would be in a dynamic link library.

Here is the code:-

```						title			'List'
public			_DllMainCRTStartup
public			CreateList
public			DeleteItem
public			GetItem
public			GetNumberItems
public			InsertItem

;
;	There are two ways that you can refer to external functions in MASM
;	Firstly, one could say
;
;	extern		__imp_VirtualAlloc: qword
;
;	The alternative is using externdef as I have used below
;
;	The difference between the two methods is that the first reference
;	is to a qword pointer (which of course an external pointer)
;	and the calling the external function with a call statement as follows
;
;	mov			rax, __imp_VirtualAlloc
;	call		qword ptr [rax]
;
;	The second method is perhaps more appropriate mechanism and permits
;	you to simply say
;
;	call		qword ptr __imp_VirtualAlloc
;

externdef		__imp_VirtualAlloc: proc

;
;	The structure definitions used by the dynamic link library are below.
;

NumberObjects		dq				?
MaximumObjects		dq				?
FreeSpace			dq				?

ListItem				struc
Object				dq				?
ListItem				ends

.code

;
;	You need to specify a function called _DllMainCRTStartup (in 'C' is
;	DllMain - called by the C runtime system). For this DLL, we are not
;	interested if its a process attach, detach, or thread attach, detach
;	We simply return a 1, which fundamentally says continue with the task
;

_DllMainCRTStartup:		mov				rax, 1
ret

;
;	This is the entry point for the creation of the list. The function
;	simply expects the maximum number of entries that the list can
;	contain. The function allocates space of the objects in the list, sets
;	up the list header and returns the start of the allocation block to
;	the caller.
;

CreateList:				push			rbx
push			r15
sub				rsp, 32
mov				r15, rdx
mov				rax, SIZE ListItem
imul			rcx
mov				rdx, rax
xor				rcx, rcx
mov				r8, 1000H
mov				r9, 4H
call			qword ptr [__imp_VirtualAlloc]
pop				r15
pop				rbx
ret

;
;	This is the entry point for the addition of an item into the list. It
;	is the address of the item that goes into the list, not the object
;	itself. The address is always added to the end of the list.
;
;	The caller supplies the pointer to the list (returned from the call to
;	CreateList) and the address of the object to be added to the list.
;

mov				r14, SIZE ListItem
mov				ListItem.Object[rax], rdx
pop				r14
ret

;
;	Return the number of items active in the list. The caller supplies the
;	pointer to the list (returned from the call to CreateList), and the
;	number of items is returned.
;

ret

;
;	Get the address of an item in the list. The caller supplies the pointer
;	to the list (returned from the call to CreateList), and the item index
;	of the item to retrieve. The funtion returns the address of the object
;	located at the requested position in the list. If the item index is
;	outside the bounds of the list, NULL is returned.
;

GetItem:				xor				rax, rax
jb				GetItemReturn
shl				rdx, 3
mov				rax, qword ptr [rdx]
GetItemReturn:			ret

;
;	Insert an item in the list. The caller supplies the pointer to the list
;	(returned from the call to CreateList), and the item index of the item
;	before which the new item will be inserted. There is no return value.
;
;	The routine has to move all the items from the supplied index to the last
;	item in the list (i.e. index to index + 1, index + 2 to index + 2 etc).
;	The moving of items is performed backwards.
;

InsertItem:				push			r13
push			r14
xor				rax, rax
jb				InsertItemReturn
mov				r13, r14
sub				r14, rdx
inc				r14
shl				r13, 3
InsertNextEntry:		mov				rax, qword ptr [r13]
mov				qword ptr 8[r13], rax
sub				r13, 8
dec				r14
jne				InsertNextEntry
mov				qword ptr 8[r13], r8
InsertItemReturn:		pop				r14
pop				r13
ret
;
;	Delete an item in the list. The caller supplies the pointer to the list
;	(returned from the call to CreateList), and the item index of the item
;	being deleted. There is no return value.
;
;	The routine has to move all the items from the supplied index to the last
;	item in the list (i.e. index + 1 to index, index + 2 to index + 1 etc).
;	The moving of items is performed forwards.
;

DeleteItem:				push			r13
push			r14
xor				rax, rax
jbe				DeleteItemReturn
sub				r14, rdx
inc				r14
mov				r13, rdx
shl				r13, 3
DeleteNextEntry:		mov				rax, qword ptr 8[r13]
mov				qword ptr [r13], rax
dec				r14
jne				DeleteNextEntry
DeleteItemReturn:		pop				r14
pop				r13
ret
end

```

Here is the linker definition (.def) file.

```LIBRARY
EXPORTS
CreateList @1
GetNumberItems @3
GetItem @4
InsertItem @5
DeleteItem @6

```

Here are the 'C' prototypes should you wish to compile and test the routines.

```extern "C" void * __stdcall CreateList(unsigned long long count);
extern "C" void __stdcall AddItem(void * list, void * item);
extern "C" unsigned long __stdcall GetNumberItems(void * list);
extern "C" void * __stdcall GetItem(void * list, unsigned long item);
extern "C" void __stdcall InsertItem(void * list, unsigned long item, void * object);
extern "C" void __stdcall DeleteItem(void * list, unsigned long item);

```

This post has been edited by Martyn.Rae: 22 November 2018 - 10:01 AM

Is This A Good Question/Topic? 1

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }