A 2D List Implementation in MASM Assembly
5.00/5 (7 votes)
A List data structure implementation in MASM Assembly with C function realloc
Introduction
In this article, you will see a 2D List data structure implementation in MASM Assembly with C function realloc.
Background
The Assembly has no built-in List data structure, for MASM, its dup syntax has limited ability to create a pre-defined size array. Usually, this array has to be defined bigger than the actual size required, in some situations, the max size is hard to evaluate prior to defining the array.
In this article, a new List data structure is introduced to implement basic List operations, i.e., add new element, get element at index. A two dimension List structure is also introduced. The new List structure supports DWORD or REAL8 data types to store element data.
Data Structure
Here are the data structures for List and 2D List. In these data structures, there are a few new types defined:
PDWORD TYPEDEF PTR DWORD
PREAL8 TYPEDEF PTR REAL8
PLISTI TYPEDEF PTR ListI
PLISTR TYPEDEF PTR ListR
ListI Data Structure:
ListI STRUCT
p PDWORD ? ; pointer to beginning address of the list data
n DWORD ? ; number of elements
ListI ENDS
ListR Data Structure:
ListR STRUCT
p PREAL8 ? ; pointer to beginning address of the list data
n DWORD ? ; count of elements
ListR ENDS
List2DI Data Structure:
List2DI STRUCT
dp PDWORD ? ; pointer to beginning address of row data
np PDWORD ? ; pointer to beginning address of number of elements in row, or of number of columns in row
n DWORD ? ; number of rows
List2DI ENDS
List2DR Data Structure:
List2DR STRUCT
dp PREAL8 ? ; pointer to beginning address of row data
np PDWORD ? ; pointer to beginning address of number of elements in row, or of number of columns in row
n DWORD ? ; number of rows
List2DR ENDS
Here is the code.
Code
All functions for List implementations are in two ASM files, List.asm and List.inc.
The ListUtility.asm is a convenient functions collection based on List library.
Most of the functions in these files are self-evident with the comments.
Here is List.inc:
.686p
.model flat, c ; c calling convention
PDWORD TYPEDEF PTR DWORD
PREAL8 TYPEDEF PTR REAL8
PLISTI TYPEDEF PTR ListI
PLISTR TYPEDEF PTR ListR
;------------------------------
; public function prototypes
;------------------------------
; C function prototypes from C Runtime Library
" C:\Program Files\Microsoft Visual Studio 10.0\VC\lib\msvcrt.lib"
; From MSDN defination
printf PROTO,
formatString: PTR BYTE,
printList: VARARG
ListI STRUCT
p PDWORD ? ; pointer to beginning address of the list
n DWORD 0 ; count of elements, initialize with default 0
ListI ENDS
ListR STRUCT
p PREAL8 ? ; pointer to beginning address of the list
n DWORD 0 ; count of elements, initialize with default 0
ListR ENDS
List2DI STRUCT
dp PDWORD ? ; pointer to beginning address of row data
np PDWORD ? ; pointer to beginning address of number of elements in row
n DWORD 0 ; number of rows
List2DI ENDS
List2DR STRUCT
dp PREAL8 ? ; pointer to beginning address of row data
np PDWORD ? ; pointer to beginning address of number of elements in row
n DWORD 0 ; number of rows
List2DR ENDS
PushI PROTO,
list : PTR ListI, ; pointer of 1D ListI
element : DWORD ; new element
PushR PROTO,
list : PTR ListR, ; pointer of 1D ListR
element : REAL8 ; new element
Push2DI PROTO,
list2d: PTR List2DI, ; pointer of 2D List2DI
element1d : PTR ListI ; the new 1D ListI element
GetListIElement PROTO,
list2d: PTR List2DI, ; pointer of 2D list
rowIndex : DWORD,
element : PTR ListI
Push2DR PROTO,
list2d: PTR List2DR, ; pointer of 2D List2DI
element1d : PTR ListR ; the new 1D ListI element
GetListRElement PROTO,
list2d: PTR List2DR, ; pointer of 2D list
rowIndex : DWORD,
element : PTR ListR
CopyListI PROTO,
srclist : PTR ListI,
destList : PTR ListI
CopyListR PROTO,
srcList : PTR ListR,
destList : PTR ListR
BubbleSortListI PROTO,
list : PTR ListI
CompareListI PROTO,
list1 : PTR ListI,
list2 : PTR ListI
ContainsListI PROTO,
list2d : PTR List2DI,
list : PTR ListI
BubbleSortListR PROTO,
list : PTR ListR
CompareListR PROTO,
list1 : PTR ListR,
list2 : PTR ListR
ContainsListR PROTO,
list2d : PTR List2DR,
list : PTR ListR
;------------------------
; Macro
;------------------------
; return number of rows in eax
GetSizeList2DI MACRO list2d:REQ, retv:REQ
push ebx
push esi
mov esi, list2d
mov ebx, (List2DI PTR [esi]).n
mov retv, ebx
pop esi
pop ebx
endm
; return number of rows in eax
GetSizeList2DR MACRO list2d:REQ, retv:REQ
push ebx
push esi
mov esi, list2d
mov ebx, (List2DR PTR [esi]).n
mov retv, ebx
pop esi
pop ebx
endm
; listiObj : ListI, idx : DWORD, retv : DWORD
; uses esi, ebx
GetListIVal MACRO listiObj:REQ, idx:REQ, retv:REQ
push ebx
push esi
mov esi, offset listiObj
mov esi, (ListI PTR [esi]).p
mov ebx, idx
imul ebx, TYPE DWORD
add esi, ebx
mov ebx, (DWORD PTR[esi])
mov retv, ebx
pop esi
pop ebx
endm
; listrObj : ListR, idx : DWORD, retv : REAL8
; uses esi, ebx
GetListRVal MACRO listrObj:REQ, idx:REQ, retv:REQ
push ebx
push esi
mov esi, offset listrObj
mov esi, (ListR PTR [esi]).p
mov ebx, idx
imul ebx, TYPE REAL8
add esi, ebx
fld (REAL8 PTR[esi])
fstp retv
pop esi
pop ebx
endm
Here is List.asm:
include List.inc
;------------------------------
; private function prototpyes
;------------------------------
; C function prototypes from C Runtime Library
; "C:\Program Files\Microsoft Visual Studio 10.0\VC\lib\msvcrt.lib"
; From MSDN defination
calloc PROTO, ; return allocated memory pointer address in eax
num: DWORD,
elementSize: DWORD
realloc PROTO, ; return reallocated memory pointer address in eax
memBlock : PTR,
newSize : DWORD
memmove PROTO,
dest : PTR,
src : PTR,
count : DWORD
free PROTO,
ptrBlock : PTR
; local functions
SizeOfDPI PROTO,
list2d: PTR List2DI ; pointer of 2D list
CopyFirstI PROTO,
list2d: PTR List2DI, ; pointer of 2D list
elAddr : DWORD,
elBytes : DWORD,
elNumber : DWORD
CopyNPI PROTO,
list2d: PTR List2DI, ; pointer of 2D list
elNumber : DWORD
CopyDPI PROTO,
list2d: PTR List2DI, ; pointer of 2D list
elAddr : DWORD,
elBytes : DWORD
SizeOfDPR PROTO,
list2d: PTR List2DR ; pointer of 2D list
CopyFirstR PROTO,
list2d: PTR List2DR, ; pointer of 2D list
elAddr : DWORD,
elBytes : DWORD,
elNumber : DWORD
CopyNPR PROTO,
list2d: PTR List2DR, ; pointer of 2D list
elNumber : DWORD
CopyDPR PROTO,
list2d: PTR List2DR, ; pointer of 2D list
elAddr : DWORD,
elBytes : DWORD
.code
; push an integer into a list,
; return ListI member p new memory address in eax, list value (address) is unchanged
PushI proc uses ebx esi ecx,
list : PTR ListI, ; check the value in this address to locate the address of ListI struct object list
element : DWORD
local endPos : DWORD
local count : DWORD
; set esi to list
; [esi] is the value in esi address, which is the beginning address of ListI object list,
; it is also the address of the ListI object first member p
; (ListI PTR [esi]) is the reference to the struct object list
; (ListI PTR [esi]).p is the pointer to beginning address of list.p
; (ListI PTR [esi]).n is the value of list.n
mov esi, list
; check if list.p is null via esi
cmp (ListI PTR [esi]).p, 0
JNE NOT_NULL ; skip list.p initialization if list.p is not null
; initialize list.p and list.n if list.p is null
invoke calloc, 0, TYPE DWORD ; return allocated memory pointer in eax
mov (ListI PTR [esi]).p, eax ; initialize list.p
mov (ListI PTR [esi]).n, 0 ; initialize list.n
NOT_NULL:
; get new size in bytes
mov esi, list ; address value of the ListI object
mov ebx, (ListI PTR [esi]).n ;
mov count, ebx ; original count of elements
imul ebx, TYPE DWORD ; convert to bytes count
mov endPos, ebx ; save original last element position
add ebx, TYPE DWORD ; get new bytes length for realloc
; realloc to new bytes size for ListI member p, its new pointer address is in eax
invoke realloc, (ListI PTR [esi]).p, ebx
; set to new memory location
mov (ListI PTR [esi]).p, eax
; append new element
mov esi, eax ; set ListI member p new pointer offset in esi
add esi, endPos ; move esi to the original list last element position
mov ebx, element ; set new element in ebx
mov [esi], ebx ; append the new element to the original list last element position
; set new count
mov esi, list ; get original list address from its pointer
mov ebx, count ; original count of elements
inc ebx ; get new count of elements
mov (ListI PTR [esi]).n, ebx ; set new count of list to ListI member n
ret
PushI endp
; push a real8 into a list, return ListR member p new memory address in eax, list value (address) is unchanged
PushR proc uses ebx esi ecx,
list : PTR ListR, ; check the value in this address to locate the address of ListR struct object list
element : REAL8
local endPos : DWORD
local count : DWORD
; set esi to list
; [esi] is the value in esi address, which is the beginning address of ListR object list,
; it is also the address of the ListR object first member p
; (ListR PTR [esi]) is the reference to the struct object list
; (ListR PTR [esi]).p is the pointer to beginning address of list.p
; (ListR PTR [esi]).n is the value of list.n
mov esi, list
; check if list.p is null via esi
cmp (ListR PTR [esi]).p, 0
JNE NOT_NULL ; skip list.p initialization if list.p is not null
; initialize list.p and list.n if list.p is null
invoke calloc, 0, TYPE REAL8 ; return allocated memory pointer in eax
mov (ListR PTR [esi]).p, eax ; initialize list.p
mov (ListR PTR [esi]).n, 0 ; initialize list.n
NOT_NULL:
; get new size in bytes
mov esi, list ; address value of the ListR object
mov ebx, (ListR PTR [esi]).n ; [esi] is the value in esi address, which is the beginning address of ListR member p
mov count, ebx ; original count of elements
imul ebx, TYPE REAL8 ; convert to bytes count
mov endPos, ebx ; save original last element position
add ebx, TYPE REAL8 ; get new bytes length for realloc
; realloc to new bytes size for ListR member p, its new pointer address is in eax
invoke realloc, (ListR PTR [esi]).p, ebx
; set to new memory location
mov (ListR PTR [esi]).p, eax
; append new element
mov esi, eax ; set ListD member p new pointer offset in esi
add esi, endPos ; move esi to the original list last element position
fld element ; save new element at ST(0)
fstp REAL8 PTR[esi] ; append the new element to the original list last element position
; set new count
mov esi, list ; get original list address from its pointer
mov ebx, count ; original count of elements
inc ebx ; get new count of elements
mov (ListR PTR [esi]).n, ebx ; set new count of list to ListR member n
ret
PushR endp
; push a 1D list to a 2D list
Push2di proc uses ebx esi ecx,
list2d: PTR List2DI, ; pointer of 2D list
element : PTR ListI ; the new 1D list element
local list2dNumber : DWORD
local elNumber, elBytes, elAddr, elEndAddr : DWORD
local dpBytes, dpAddr, dpEndAddr : DWORD
local npBytes, npAddr, npEndAddr : DWORD
; get new element info
; get elBytes
mov esi, element
mov ebx, (ListI PTR [esi]).n
mov elNumber, ebx
imul ebx, TYPE DWORD
mov elBytes, ebx
; get elAddr
mov ebx, [esi]
mov elAddr, ebx
; get elEndAddr
mov ebx, elAddr
add ebx, elBytes
mov elEndAddr, ebx
; check if list2d.p is null
mov esi, list2d
cmp (List2DI PTR [esi]).dp, 0
JNE NOT_NULL ; skip list2d.p initialization if list2d.p is not null
invoke CopyFirstI, list2d, elAddr, elBytes, elNumber
JMP BLANK
NOT_NULL:
invoke CopyDPI,list2d, elAddr, elBytes
invoke CopyNPI, list2d, elNumber
; set list2d.n
mov esi, list2d
inc (List2DI PTR [esi]).n
BLANK:
ret
Push2di endp
CopyFirstI proc uses eax ebx esi,
list2d: PTR List2DI, ; pointer of 2D list
elAddr : DWORD,
elBytes : DWORD,
elNumber : DWORD
; initialize list2d.dp
invoke calloc, elNumber, TYPE DWORD ; return allocated memory pointer in eax
mov esi, list2d
mov (List2DI PTR [esi]).dp, eax ; initialize list2d.p
; initialize list2.np
invoke calloc, 1, TYPE DWORD ; return allocated memory pointer in eax
mov esi, list2d
mov (List2DI PTR [esi]).np, eax ; initialize list2d.p
; initialize list2d.n
mov esi, list2d
mov (List2DI PTR [esi]).n, 1 ; initialize list2d.n
; set list2d.np
mov esi, list2d
mov esi, (List2DI PTR [esi]).np ; get np address
mov ebx, elNumber
mov [esi], ebx
; copy element to list2d.dp
mov esi, list2d
mov esi, (List2DI PTR [esi]).dp ; get dp address
invoke memmove, esi, elAddr, elBytes
ret
CopyFirstI endp
CopyDPI proc uses eax ebx esi,
list2d: PTR List2DI, ; pointer of 2D list
elAddr : DWORD,
elBytes : DWORD
local dpBytes, dpAddr, dpEndAddr, newLen : DWORD
; get dpBytes
invoke SizeOfDPI, list2d
mov dpBytes, eax
; get dpAddr to realloc
mov esi, list2d
mov esi, (List2DI PTR [esi]).dp ; get np address
mov dpAddr, esi
; extend dp with more elBytes bytes
mov ebx, dpBytes
add ebx, elBytes
mov newLen, ebx
invoke realloc, dpAddr, newLen
; get new dp address which could be different with original npAddr
mov esi, list2d
mov (List2DI PTR [esi]).dp, eax
mov dpAddr, eax
; get new dp end address
mov ebx, dpAddr
add ebx, dpBytes
mov dpEndAddr, ebx
; copy element to list2d.dp
invoke memmove, dpEndAddr, elAddr, elBytes
ret
CopyDPI endp
CopyNPI proc uses eax ebx esi,
list2d: PTR List2DI, ; pointer of 2D list
elNumber : DWORD
local list2dNumber, npBytes, npAddr, npEndAddr, newLen : DWORD
; get list2dNumber
mov esi, list2d
mov ebx, (List2DI PTR [esi]).n
mov list2dNumber, ebx
; get npBytes
mov ebx, list2dNumber
imul ebx, TYPE DWORD
mov npBytes, ebx
; get npAddr to realloc
mov esi, list2d
mov esi, (List2DI PTR [esi]).np ; get np address
mov npAddr, esi
; extend np with one new DWORD item
mov ebx, npBytes
add ebx, TYPE DWORD
mov newLen, ebx
invoke realloc, npAddr, newLen
; get new np address which could be different with original npAddr
mov esi, list2d
mov (List2DI PTR [esi]).np, eax
mov npAddr, eax
; get new np end address
mov ebx, npAddr
add ebx, npBytes
mov npEndAddr, ebx
; set list2d.np
mov esi, list2d
mov esi, npEndAddr
mov ebx, elNumber
mov [esi], ebx
ret
CopyNPI endp
; get sum of list2d.dp in eax
SizeOfDPI proc uses esi ecx ebx,
list2d: PTR List2DI ; pointer of 2D list
local dpBytes : DWORD
mov dpBytes, 0 ; initial countBytes
mov esi, list2d
mov ecx, (List2DI PTR [esi]).n ; loop count : rows in list2d
JCXZ BLANK ; if ecx == 0 then skip
mov esi, list2d
mov esi, (List2DI PTR [esi]).np ; get np address
L1:
mov ebx, [esi] ; get current DWORD elements number in this row
imul ebx, TYPE DWORD ; convert to bytes
add dpBytes, ebx ; save total bytes
add esi, TYPE DWORD ; move to next row
LOOP L1
BLANK:
mov eax, dpBytes
ret
SizeOfDPI endp
; get element at row index
GetListIElement proc uses esi ecx ebx,
list2d: PTR List2DI, ; pointer of 2D list
rowIndex : DWORD,
element : PTR ListI
local dpBytes, count, lastdpBytes : DWORD
mov dpBytes, 0
mov count, 0
mov esi, element
; check if element.p is null via esi
cmp (ListI PTR [esi]).p, 0
JNE NOT_NULL ; skip list.p initialization if list.p is not null
; initialize list.p and list.n if list.p is null
invoke calloc, 0, TYPE DWORD ; return allocated memory pointer in eax
mov (ListI PTR [esi]).p, eax ; initialize list.p
mov (ListI PTR [esi]).n, 0 ; initialize list.n
NOT_NULL:
mov esi, list2d
mov ebx, (List2DI PTR [esi]).n ; loop count : rows in list2d
cmp ebx, rowIndex
JLE INDEX_EXCEED
mov ecx, rowIndex ;rowIndex start from 0, this ensure loop count is 1 if rowIndex == 0
inc ecx
mov esi, list2d
mov esi, (List2DI PTR [esi]).np ; get np address
L1:
mov ebx, [esi] ; get current DWORD elements number in this row
mov count, ebx
imul ebx, TYPE DWORD ; convert to bytes
mov lastdpBytes, ebx
add dpBytes, ebx ; save total bytes
add esi, TYPE DWORD ; move to next row
LOOP L1
FIRST_ITEM:
; get dp address for rowIndex
mov esi, list2d
mov ebx, (List2DI PTR [esi]).dp ; get np address
add ebx, dpBytes
sub ebx, lastdpBytes
; return element.p
mov esi, element
mov (ListI PTR [esi]).p, ebx
; return element.n
mov ebx, count
mov (ListI PTR [esi]).n, ebx
INDEX_EXCEED:
ret
GetListIElement endp
; push a 1D list to a 2D list
Push2dR proc uses ebx esi ecx,
list2d: PTR List2DR, ; pointer of 2D list
element : PTR ListR ; the new 1D list element
local list2dNumber : DWORD
local elNumber, elBytes, elAddr, elEndAddr : DWORD
local dpBytes, dpAddr, dpEndAddr : DWORD
local npBytes, npAddr, npEndAddr : DWORD
; get new element info
; get elBytes
mov esi, element
mov ebx, (ListR PTR [esi]).n
mov elNumber, ebx
imul ebx, TYPE REAL8
mov elBytes, ebx
; get elAddr
mov ebx, [esi]
mov elAddr, ebx
; get elEndAddr
mov ebx, elAddr
add ebx, elBytes
mov elEndAddr, ebx
; check if list2d.dp is null
mov esi, list2d
cmp (List2DR PTR [esi]).dp, 0
JNE NOT_NULL ; skip list2d.p initialization if list2d.p is not null
invoke CopyFirstR, list2d, elAddr, elBytes, elNumber
JMP BLANK
NOT_NULL:
invoke CopyDPR,list2d, elAddr, elBytes
invoke CopyNPR, list2d, elNumber
; set list2d.n
mov esi, list2d
inc (List2DR PTR [esi]).n
BLANK:
ret
Push2dR endp
CopyFirstR proc uses eax ebx esi,
list2d: PTR List2DR, ; pointer of 2D list
elAddr : DWORD,
elBytes : DWORD,
elNumber : DWORD
; initialize list2d.dp
invoke calloc, elNumber, TYPE REAL8 ; return allocated memory pointer in eax
mov esi, list2d
mov (List2DR PTR [esi]).dp, eax ; initialize list2d.p
; initialize list2.np
invoke calloc, 1, TYPE DWORD ; return allocated memory pointer in eax
mov esi, list2d
mov (List2DR PTR [esi]).np, eax ; initialize list2d.p
; initialize list2d.n
mov esi, list2d
mov (List2DR PTR [esi]).n, 1 ; initialize list2d.n
; set list2d.np
mov esi, list2d
mov esi, (List2DR PTR [esi]).np ; get np address
mov ebx, elNumber
mov [esi], ebx
; copy element to list2d.dp
mov esi, list2d
mov esi, (List2DR PTR [esi]).dp ; get dp address
invoke memmove, esi, elAddr, elBytes
ret
CopyFirstR endp
CopyDPR proc uses eax ebx esi,
list2d: PTR List2DR, ; pointer of 2D list
elAddr : DWORD,
elBytes : DWORD
local dpBytes, dpAddr, dpEndAddr, newLen : DWORD
; get dpBytes
invoke SizeOfDPR, list2d
mov dpBytes, eax
; get dpAddr to realloc
mov esi, list2d
mov esi, (List2DR PTR [esi]).dp ; get np address
mov dpAddr, esi
; extend dp with more elBytes bytes
mov ebx, dpBytes
add ebx, elBytes
mov newLen, ebx
invoke realloc, dpAddr, newLen
; get new dp address which could be different with original npAddr
mov esi, list2d
mov (List2DR PTR [esi]).dp, eax
mov dpAddr, eax
; get new dp end address
mov ebx, dpAddr
add ebx, dpBytes
mov dpEndAddr, ebx
; copy element to list2d.dp
invoke memmove, dpEndAddr, elAddr, elBytes
ret
CopyDPR endp
CopyNPR proc uses eax ebx esi,
list2d: PTR List2DR, ; pointer of 2D list
elNumber : DWORD
local list2dNumber, npBytes, npAddr, npEndAddr, newLen : DWORD
; get list2dNumber
mov esi, list2d
mov ebx, (List2DR PTR [esi]).n
mov list2dNumber, ebx
; get npBytes
mov ebx, list2dNumber
imul ebx, TYPE DWORD
mov npBytes, ebx
; get npAddr to realloc
mov esi, list2d
mov esi, (List2DR PTR [esi]).np ; get np address
mov npAddr, esi
; extend np with one new DWORD item
mov ebx, npBytes
add ebx, TYPE DWORD
mov newLen, ebx
invoke realloc, npAddr, newLen
; get new np address which could be different with original npAddr
mov esi, list2d
mov (List2DR PTR [esi]).np, eax
mov npAddr, eax
; get new np end address
mov ebx, npAddr
add ebx, npBytes
mov npEndAddr, ebx
; set list2d.np
mov esi, list2d
mov esi, npEndAddr
mov ebx, elNumber
mov [esi], ebx
ret
CopyNPR endp
; get sum of list2d.dp in eax
SizeOfDPR proc uses esi ecx ebx,
list2d: PTR List2DR ; pointer of 2D list
local dpBytes : DWORD
mov dpBytes, 0 ; initial countBytes
mov esi, list2d
mov ecx, (List2DI PTR [esi]).n ; loop count : rows in list2d
JCXZ BLANK ; if ecx == 0 then skip
mov esi, list2d
mov esi, (List2DR PTR [esi]).np ; get np address
L1:
mov ebx, [esi] ; get current DWORD elements number in this row
imul ebx, TYPE REAL8 ; convert to bytes offset in dp
add dpBytes, ebx ; save total bytes
add esi, TYPE DWORD ; move to next row
LOOP L1
BLANK:
mov eax, dpBytes
ret
SizeOfDPR endp
; get element at row index
GetListRElement proc uses esi ecx ebx,
list2d: PTR List2DR, ; pointer of 2D list
rowIndex : DWORD,
element : PTR ListR
local dpBytes, count, lastdpBytes : DWORD
mov dpBytes, 0
mov count, 0
mov esi, element
; check if element.p is null via esi
cmp (ListR PTR [esi]).p, 0
JNE NOT_NULL ; skip list.p initialization if list.p is not null
; initialize list.p and list.n if list.p is null
invoke calloc, 0, TYPE REAL8 ; return allocated memory pointer in eax
mov (ListR PTR [esi]).p, eax ; initialize list.p
mov (ListR PTR [esi]).n, 0 ; initialize list.n
NOT_NULL:
mov esi, list2d
mov ebx, (List2DR PTR [esi]).n ; loop count : rows in list2d
cmp ebx, rowIndex
JLE INDEX_EXCEED
mov ecx, rowIndex ;rowIndex start from 0, this ensure loop count is 1 if rowIndex == 0
inc ecx
mov esi, list2d
mov esi, (List2DR PTR [esi]).np ; get np address
L1:
mov ebx, [esi] ; get current DWORD elements number in this row
mov count, ebx
imul ebx, TYPE REAL8 ; convert to bytes offset in dp
mov lastdpBytes, ebx
add dpBytes, ebx ; save total bytes
add esi, TYPE DWORD ; move to next row
LOOP L1
FIRST_ITEM:
; get dp address for rowIndex
mov esi, list2d
mov ebx, (List2DR PTR [esi]).dp ; get np address
add ebx, dpBytes
sub ebx, lastdpBytes
; return element.p
mov esi, element
mov (ListR PTR [esi]).p, ebx
; return element.n
mov ebx, count
mov (ListR PTR [esi]).n, ebx
INDEX_EXCEED:
ret
GetListRElement endp
; copy list to newList
CopyListI proc uses esi eax ebx,
list : PTR ListI,
newList : PTR ListI ; newList need to initialize with default n value, i.e. declare as global varaible "newList ListI <?>"
local count, srcAddr, oriAddr, oriCount, copyBytes : DWORD
; get copy source address
mov esi, list
mov ebx, (ListI PTR [esi]).n
mov count, ebx
mov ebx, (ListI PTR [esi]).p
mov srcAddr, ebx
; get free original address
mov esi, newList
mov ebx, (ListI PTR [esi]).p
mov oriAddr, ebx
; this n value could be a wild value if newList is declared a local variable or
; or declared a global variable as "newList ListI <>" rather than "newList ListI <?>"
; declare newList as a global with "newList ListI <?>" is correct way,
; which always uses n default value 0 in ListI struct defination to initialize ListI.n
; while "newList ListI <>" declaration does not
mov ebx, (ListI PTR [esi]).n
mov oriCount, ebx
; initialize or reset list.p and list.n
invoke calloc, count, TYPE DWORD ; return allocated memory pointer in eax
mov esi, newList
mov (ListI PTR [esi]).p, eax ; initialize list.p
mov ebx, count
mov (ListI PTR [esi]).n, ebx ; initialize list.n
; free original newList.p here to avoid memory leak
mov ebx, oriCount
cmp ebx, 0
JE SKIP_FREE ; if oriCount == 0
invoke free, oriAddr ; if oriCount != 0, free could fail if the oriCount is a wild n value above
SKIP_FREE:
; get bytes count to copy
mov ebx, count
imul ebx, TYPE DWORD
mov copyBytes, ebx
; copy
mov esi, newList
invoke memmove, (ListI PTR [esi]).p, srcAddr, copyBytes
ret
CopyListI endp
; clone array
CopyListR proc,
srcList : PTR ListR,
destList : PTR ListR
local i, count, srcAddr, destAddr, oriAddr, oriCount, newAddr : DWORD
local tempR : REAL8
pushad ; save all registers
mov esi, srcList
mov ebx, (ListR PTR[esi]).n
mov count, ebx
mov ebx, (ListR PTR[esi]).p
mov srcAddr, ebx
; initialize or reset destList.p and destList.n
invoke calloc, count, TYPE REAL8 ; return allocated memory pointer in eax
cmp eax, 0
; calloc return null, calloc fails.
; this is usually not caused by running out of continous heap memory block
; this is usually caused by a bug somewhere in the functions calling chains
; trace back the functions to see if somewhere having a unexpected global variable overwritting
JE CALLOC_ERROR_ZERO
mov destAddr, eax
; get original address to be freed
mov esi, destList
mov ebx, (ListR PTR [esi]).n
mov oriCount, ebx
mov ebx, (ListR PTR [esi]).p
mov oriAddr, ebx ; this oriAddr maybe 0 if destList is first time referenced after its declaration
mov esi, destList
mov ebx, destAddr
mov (ListR PTR [esi]).p, ebx ; initialize list.p with new allocated memory address
mov ebx, count
mov (ListR PTR [esi]).n, ebx ; initialize list.n same as srcList
; free original destList.p here to avoid memory leak
mov ebx, oriCount
cmp ebx, 0
; if oriCount == 0 then skip free.
; this is usually when destList is first time referenced and its p member is still blank without memory allocated
; in this situation, oriAddr == 0x00000000, which cause free crash
JE SKIP_FREE
; free invokation may crash if oriAddr is 0 (null) or an in-use address, i.e. stack memory address
invoke free, oriAddr ; if oriCount != 0
SKIP_FREE:
mov esi, destList
mov esi, (ListR PTR[esi]).p
mov ebx, esi ; save destination array offset address in ebx
mov i, 0
mov ecx, count
L1:
mov edi, i ; edi as index
; copy
mov esi, srcAddr
fld REAL8 PTR[esi + edi * 8]
mov esi, destAddr
fstp REAL8 PTR[esi + edi * 8]
inc i ; i++
LOOP L1
popad ; restore all registers
JMP DONE
CALLOC_ERROR_ZERO:
; if return eax == -2, then calloc fails
mov eax, -2
DONE:
ret
CopyListR endp
end
Here is ListUtility.asm:
include List.inc
TRUE EQU 1
FALSE EQU 0
.data
tempListI ListI <?>
listCopyI ListI <?>
tempListR ListR <?>
listCopyR ListR <?>
MinRealCompareError REAL8 1.0E-12
.code
BubbleSortListI proc uses eax ecx esi ebx,
list : PTR ListI
local pData : DWORD ; offset address of 1d pDataay
local count : DWORD ; number of elements
mov esi, list
mov ebx, (ListI PTR [esi]).p
mov pData, ebx
mov ebx, (ListI PTR [esi]).n
mov count, ebx
; the following code in this procedure is from
; the book "assembly language for x86 processors" by Kip Irvine
mov ecx,count
dec ecx
L1:
push ecx
mov esi,pData
L2:
mov eax,[esi]
cmp [esi+4],eax
jg L3
xchg eax,[esi+4]
mov [esi],eax
L3:
add esi,4
loop L2
pop ecx
loop L1
L4:
ret
BubbleSortListI endp
CompareListI proc uses ecx ebx esi,
list1 : PTR ListI,
list2 : PTR ListI
local array1 : DWORD ; offset array1
local array2 : DWORD ; offset array2
local array1Len : DWORD ; length of array
local array2Len : DWORD ; length of array
local i : DWORD
local retEqual : DWORD
mov esi, list1
mov ebx, (ListI PTR [esi]).p
mov array1, ebx
mov ebx, (ListI PTR [esi]).n
mov array1Len, ebx
mov esi, list2
mov ebx, (ListI PTR [esi]).p
mov array2, ebx
mov ebx, (ListI PTR [esi]).n
mov array2Len, ebx
cmp ebx, array1Len
JNE DONE_NOT_EQUAL ; if 2 array length is different
; set initial return value TRUE
mov retEqual, TRUE
mov i, 0
mov ecx, array1Len
L1:
mov esi, array1
mov ebx, [esi]
mov esi, array2
cmp [esi], ebx
JNE DONE_NOT_EQUAL
add array1, 4
add array2, 4
LOOP L1
JMP DONE_EQUAL
DONE_NOT_EQUAL:
mov retEqual, FALSE
DONE_EQUAL:
; return retEqual
mov eax, retEqual
ret
CompareListI endp
; check if list2d contains list with ignoring list elements order
ContainsListI proc uses ebx esi,
list2d : PTR List2DI,
list : PTR ListI
local isContains, rows, i : DWORD
; initialize return value
mov isContains, FALSE
; copy list to avoid modify original list with sorting
invoke CopyListI, list, ADDR listCopyI
; sort list
invoke BubbleSortListI, ADDR listCopyI
; get rows
mov esi, list2d
mov ebx, (List2DI PTR [esi]).n
mov rows, ebx
mov i, 0
mov ecx,rows
L1:
invoke GetListIElement, list2d, i, ADDR tempListI
invoke BubbleSortListI, ADDR tempListI
invoke CompareListI, ADDR tempListI, ADDR listCopyI
cmp eax, TRUE
JE DONE_TRUE
inc i
loop L1
JMP DONE_FALSE
DONE_TRUE:
mov isContains, TRUE
DONE_FALSE:
; return value in eax
mov eax, isContains
ret
ContainsListI endp
; check if a 2d real array contains a 1d real array
ContainsListR proc,
list2d : PTR List2DR,
list : PTR ListR
local isContains, rows, i : DWORD
; initialize return value
mov isContains, FALSE
; copy list to avoid modify original list with sorting
invoke CopyListR, list, ADDR listCopyR
; sort list
invoke BubbleSortListR, ADDR listCopyR
; get rows
mov esi, list2d
mov ebx, (List2DR PTR [esi]).n
mov rows, ebx
mov i, 0
mov ecx,rows
L1:
invoke GetListRElement, list2d, i, ADDR tempListR
invoke BubbleSortListR, ADDR tempListR
invoke CompareListR, ADDR tempListR, ADDR listCopyR
cmp eax, TRUE
JE DONE_TRUE
inc i
loop L1
JMP DONE_FALSE
DONE_TRUE:
mov isContains, TRUE
DONE_FALSE:
; return value in eax
mov eax, isContains
ret
ContainsListR endp
; check if two 1d array equal
; return true or false in eax
CompareListR proc,
list1 : PTR ListR,
list2 : PTR ListR
local array1 : DWORD ; offset array1
local array2 : DWORD ; offset array2
local array1Len : DWORD ; length of array
local array2Len : DWORD ; length of array
local dummy1, dummy2 : REAL8
local i : DWORD
local retEqual : DWORD
; set initial return value TRUE
mov retEqual, TRUE
mov esi, list1
mov ebx, (ListR PTR [esi]).p
mov array1, ebx
mov ebx, (ListR PTR [esi]).n
mov array1Len, ebx
mov esi, list2
mov ebx, (ListR PTR [esi]).p
mov array2, ebx
mov ebx, (ListR PTR [esi]).n
mov array2Len, ebx
cmp ebx, array1Len
JNE DONE_NOT_EQUAL ; if 2 array length is different
mov i, 0
mov ecx, array1Len
L1:
; push minimum error at ST(1)
fld MinRealCompareError
; push array1[i] at ST(0)
mov esi, array1
fld REAL8 PTR[esi]
; operate array1[i] - array2[i] at ST(0)
mov esi, array2
fsub REAL8 PTR[esi]
; operate fabs(array1[i] - array2[i]) at ST(0)
fabs
; compare
fcomi ST(0), ST(1)
; return false if difference abs value is above error
JA DONE_NOT_EQUAL
; continue if difference abs value is not above error, the 2 value are equal
fstp dummy2
fstp dummy1
add array1, 8
add array2, 8
LOOP L1
JMP DONE_EQUAL
DONE_NOT_EQUAL:
mov retEqual, FALSE
DONE_EQUAL:
; return retEqual
mov eax, retEqual
ret
CompareListR endp
; Bubble Sort 1d REAL8 array
; for(i = 0; i< count ; i++)
; for (j= i + 1; j< count , j++)
; if(array[i] > array[j])
; {
; temp = array[j];
; array[j] = array[i];
; array[i] = temp;
; }
BubbleSortListR proc,
list : PTR ListR
local i, j : DWORD ; number of elements
local dummy1, dummy2 : REAL8
pushad ; save all general registers
; initialize esi with arr array address
mov esi, list
mov edx, (ListR PTR[esi]).n
mov esi, (ListR PTR[esi]).p
mov i, 0 ; i = 0
L1:
cmp i, edx
JAE DONE ; i < count
; j = i + 1
mov ebx, i
add ebx, 1
mov j, ebx ; j = i + 1
L2:
cmp j, edx
JAE CONT_L1 ; j < count
; push array[i] at ST(1)
mov edi, i
fld REAL8 PTR[esi + edi*8] ; get current real8 value, st(1)
; push array[j] at ST(0)
mov edi, j
fld REAL8 PTR[esi + edi* 8] ; get next real8 value, st(0)
fcomi ST(0),ST(1) ; compare array[j] with array[i]
; if array[i] <= array[j] then continue
JNB CONT_POP_L2
; if array[i] > array[j] then swap array[i] and array[j]
; pop ST(0) to array[i]
mov edi, i
fstp REAL8 PTR[esi + edi * 8]
; pop ST(1) to array[j]
mov edi, j
fstp REAL8 PTR[esi + edi * 8]
JMP CONT_L2 ; continue without 2 fstp pop
CONT_POP_L2: ; continue with 2 fstp pop for cleaning the 2 pushed array[j] and array[i]
fstp dummy2
fstp dummy1
CONT_L2:
inc j ; j++
JMP L2
CONT_L1:
inc i ; i++
JMP L1
DONE:
popad ; restore all general registers
ret
BubbleSortListR endp
end
Test
Here is a test program for main functions in the List library and ListUtility. A complete test program is in the attached package.
Here is how to add a 32 bits DWORD to a ListI:
tempI DWORD 7
tempListI ListI <?>
invoke pushi, ADDR tempListI , tempI
To get the number of elements n in tempListI:
mov esi, offset tempListI
mov ebx, (ListI PTR [esi]).n
mov n, ebx
To get the element at index idx in tempListI, use this macro:
GetListIVal tempListI, idx, tempI
Here is how to add a 64 bits REAL8 to a ListR:
tempR REAL8 7.7
tempListR ListR <?>
invoke pushr, ADDR tempListR , tempR
To get the number of elements n in tempListR:
mov esi, offset tempListR
mov ebx, (ListR PTR [esi]).n
mov n, ebx
To get the element at index idx in tempListI, use this macro GetListRVal:
GetListRVal tempListR, idx, tempR
Here is how to add a ListI to a List2DI:
tempListI ListI <?>
tempList2DI List2DI <?>
invoke push2di, ADDR tempList2DI , ADDR tempListI
To get the number of rows n in tempList2DI, use macro GetSizeList2DI:
local tempAddr : DWORD
mov tempAddr , offset tempList2DI
GetSizeList2DI tempAddr , n
To get the element at index idx in tempList2DI:
invoke GetListIElement, ADDR tempList2DI , idx, ADDR tempListI
Here is how to add a ListI to a List2DR:
tempListR ListR <?>
tempList2DR List2DR <?>
invoke push2dr, ADDR tempList2DR , ADDR tempListR
To get the number of rows n in tempList2DI, use macro GetSizeList2DI:
local tempAddr : DWORD
mov tempAddr , offset tempList2DR
GetSizeList2DR tempAddr , n
To get the element at index idx in tempList2DI:
invoke GetListRElement, ADDR tempList2DR , idx, ADDR tempListR
Here are convenient functions for ListI and List2DI structs:
; sort ListI object
invoke BubbleSortListI, ADDR tempListI
; compare 2 ListI objects
invoke CompareListI, ADDR tempListI1, ADDR tempListI2
; copy a ListI object to another
invoke CopyListI, ADDR srcListI, ADDR destListI
; check if a List2DI object contains a ListI object with ignoring ListI inner element order
invoke ContainsListI, ADDR tempList2DI, ADDR tempListI
Here are convenient functions for ListI and List2DR structs:
; sort ListR object
invoke BubbleSortListR, ADDR tempListR
; compare 2 ListR objects
invoke CompareListR, ADDR tempListR1, ADDR tempListR2
; copy a ListR object to another
invoke CopyListR, ADDR srcListR, ADDR destListR
; check if a List2DR object contains a ListR object with ignoring ListR inner element order
invoke ContainsListR, ADDR tempList2DR, ADDR tempListR
Visual Studio ASM Setup
There is a way to develop MASM program in Visual Studio, which makes ASM debug much easier.
The complete description for how to install and set up AsmHighlighter.vsix is in the attached zip package.
Here are the steps to set up Assembly programming in Visual Studio VC++ Express 2010:
- Reference http://www.deconflations.com/2011/masm-assembly-in-visual-studio-2010/
- Download Visual Studio assembly extension AsmHighlighter.vsix from http://asmhighlighter.codeplex.com/releases
- Open AsmHighlighter.vsix archives with 7-Zip or rename it to AsmHighlighter.zip, then open it
- Edit extension.vsixmanifest to add or replace
<Edition>Pro</Edition>to<Edition>Express_All</Edition>within node<VisualStudio Version="10.0"> - To find out where the extension should be installed, search "
extension" keyword in VC 2010 folder C:\Program Files\Microsoft Visual Studio 10.0\. The keyword "Express_All" for VC2010 Express is also figured out through existing extension.vsixmanifest in the folders found in the above search. - Copy all contents to C:\Program Files\Microsoft Visual Studio 10.0\Common7\IDE\VCExpressExtensions\Platform\
- Open VC++ Express 2010.
- Create a new Empty Project in General catalog
- In Solution Explorer, select "Build Customizations" => check the second "MASM ... " item.
- Change Configuration Properties => Linker => System => SubSystem to Console or other types
- Add an existing .asm file. The step order matters, be sure to add .asm files after step 9 (Build Customizations) is done, if you add an existing .asm file before step 9, you have to exclude them, then re-add them again after step 9 is done.
- Right click project in Solution Explorer => Property, if a new item "Microsoft Macro Assembly" appears, then it means the extension is installed successfully and MASM development in VS is ready.
Compile
There are two version compiles, one is compile in Visual Studio C++, another one is compile through command line.
The compile command line in ASMList project:
cls
echo off
rem compile library
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
/c .\src\List.asm /Fo List.obj
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
/c .\src\ListUtility.asm /Fo ListUtility.obj
rem build library
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\lib.exe" /subsystem:console ^
List.obj ListUtility.obj /out:.\lib\List.lib
rem compile test
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\ml.exe" /I .\include ^
/c .\ListTest.asm /Fo ListTest.obj
rem build test
"C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\link.exe" ^
/libpath:.\lib List.lib ^
/libpath:"C:\Program Files\Microsoft Visual Studio 10.0\VC\lib" msvcrt.lib ^
ListTest.obj /out:TestList.exe
del *.obj
Here is a minimum command line compile environment set up:
echo off
rem run only once this batch before compiling MASM or C program
set path=C:\Program Files\Microsoft Visual Studio 10.0\Common7\IDE;%path%
set include=C:\Program Files\Microsoft Visual Studio 10.0\VC\INCLUDE;
C:\Program Files\Microsoft SDKs\Windows\v7.0A\include;%include%
set lib=C:\Program Files\Microsoft Visual Studio 10.0\VC\LIB;
C:\Program Files\Microsoft SDKs\Windows\v7.0A\lib;
set libpath=C:\Program Files\Microsoft Visual Studio 10.0\VC\LIB;%libpath%
A complete VC++ development environment command line setup is:
C:\Program Files\Microsoft Visual Studio 10.0\VC\bin\vcvars32.bat
To Do
Check all heap memory manipulations to fix memory leaking with freeing unused pointers.
Exception handling in memory manipulation failures.
History
- 27th February, 2016
- Added ListUtility.asm to include convenient functions to utilize List library
- Fixed a bug to avoid memory leak with freeing original heap memory after realloc. There might be other places need to do the same fixes which maybe in next change.
- 26th February, 2016
- Initial post