Page 1 of 1

Lists, Vectors, Queues and Stacks In MASM x64 Assembly

#1 Martyn.Rae   User is offline

  • The programming dinosaur
  • member icon

Reputation: 551
  • View blog
  • Posts: 1,432
  • 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
  • AddItem
  • InsertItem
  • DeleteItem
  • GetItem
  • GetNumberItems


The implementation would be in a dynamic link library.

Here is the code:-

						title			'List'
						public			_DllMainCRTStartup
						public			CreateList
						public			AddItem
						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)
						;	You would use the first method by loading the address into a register
						;	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.
						;

ListHeader				struc
	NumberObjects		dq				? 
	MaximumObjects		dq				?
	FreeSpace			dq				?
ListHeader				ends

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
						add				rdx, SIZE ListHeader
						xor				rcx, rcx
						mov				r8, 1000H
						mov				r9, 4H
						call			qword ptr [__imp_VirtualAlloc]
						mov				rbx, SIZE ListHeader
						add				rbx, rax
						mov				ListHeader.MaximumObjects[rax], r15
						mov				ListHeader.FreeSpace[rax], rbx
						add				rsp, 32
						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.
						;

AddItem:				push			r14
						mov				rax, ListHeader.FreeSpace[rcx]
						mov				r14, SIZE ListItem
						add				r14, rax
						mov				ListHeader.FreeSpace[rcx], r14
						inc				ListHeader.NumberObjects[rcx]
						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.
						;

GetNumberItems:			mov				rax, ListHeader.NumberObjects[rcx]
						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
						cmp				ListHeader.NumberObjects[rcx], rdx
						jb				GetItemReturn
						shl				rdx, 3
						add				rdx, SIZE ListHeader
						add				rdx, rcx
						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
						cmp				ListHeader.NumberObjects[rcx], rdx
						jb				InsertItemReturn
						mov				r14, ListHeader.NumberObjects[rcx]
						mov				r13, r14
						sub				r14, rdx
						inc				r14
						inc				ListHeader.NumberObjects[rcx]
						shl				r13, 3
						add				r13, SIZE ListHeader
						add				r13, rcx
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
						cmp				ListHeader.NumberObjects[rcx], rdx
						jbe				DeleteItemReturn
						mov				r14, ListHeader.NumberObjects[rcx]
						sub				r14, rdx
						inc				r14
						dec				ListHeader.NumberObjects[rcx]
						mov				r13, rdx
						shl				r13, 3
						add				r13, SIZE ListHeader
						add				r13, rcx
DeleteNextEntry:		mov				rax, qword ptr 8[r13]
						mov				qword ptr [r13], rax
						add				r13, 8
						dec				r14
						jne				DeleteNextEntry
DeleteItemReturn:		pop				r14
						pop				r13
						ret
						end



Here is the linker definition (.def) file.

LIBRARY
EXPORTS
CreateList @1
AddItem @2
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