Click here to Skip to main content
14,297,293 members

A 2D List Implementation in MASM Assembly

Rate this:
5.00 (7 votes)
Please Sign up or sign in to vote.
5.00 (7 votes)
27 Feb 2016CPOL
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

Image 1

ListR Data Structure:

ListR STRUCT
    p PREAL8 ? ; pointer to beginning address of the list data
    n DWORD ?  ; count of elements
ListR ENDS

Image 2

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

Image 3

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

Image 4

Here is the code.

Code

The 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 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:

  1. Reference http://www.deconflations.com/2011/masm-assembly-in-visual-studio-2010/
  2. Download Visual Studio assembly extension AsmHighlighter.vsix from http://asmhighlighter.codeplex.com/releases
  3. Open AsmHighlighter.vsix archives with 7-Zip or rename it to AsmHighlighter.zip, then open it
  4. Edit extension.vsixmanifest to add or replace <Edition>Pro</Edition> to <Edition>Express_All</Edition> within node <VisualStudio Version="10.0">
  5. 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.
  6. Copy all contents to C:\Program Files\Microsoft Visual Studio 10.0\Common7\IDE\VCExpressExtensions\Platform\
  7. Open VC++ Express 2010.
  8. Create a new Empty Project in General catalog
  9. In Solution Explorer, select "Build Customizations" => check the second "MASM ... " item.
  10. Change Configuration Properties => Linker => System => SubSystem to Console or other types
  11. 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.
  12. 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 2 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

  • Feb 27, 2016: Add 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.
  • Feb 26, 2016 : Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

John Jiyang Hou
Software Developer
Canada Canada
My name is Jiyang Hou (or John Hou). I was born in HeiLongJiang province in north east of China. I got all my educations in China. My university major is Geophysics, but my main professional role is software developer. My biggest accomplishment so far is quit smoking about 5 years ago after almost 20 years smoking history. I am still interested on programming beside making living with it like many other developers. I immigrated to Canada in 2003 and became a permanent resident till now. I live in Calgary, Alberta, Canada. You can reach me by jyhou69@gmail.com regarding to any questions, comments, advice, etc.

Comments and Discussions

 
-- There are no messages in this forum --
Article
Posted 27 Feb 2016

Stats

9.2K views
257 downloads
2 bookmarked