TOC PREV NEXT INDEX

Webster Home Page

4.9 Large Arrays and MASM

There is a defect in later versions of MASM v6.x that create some problems when you declare large static arrays in your programs. Now you may be wondering what this has to do with you since we're using HLA, but don't forget that HLA v1.x compiles to MASM assembly code and then runs MASM to assemble this output. Therefore, any defect in MASM is going to be a problem for HLA users.

The problem occurs when the total number of array elements you declare in a static section (STATIC, READONLY, or STORAGE) starts to get large. Large in this case is CPU dependent, but it falls somewhere between 128,000 and one million elements for most systems. MASM, for whatever reason, uses a very slow algorithm to emit array code to the object file; by the time you declare 64K array elements, MASM starts to produce a noticeable delay while compiling your code. After that point, the delay grows linearly with the number of array elements (i.e., as you double the number of array elements you double the assembly time) until the data saturates MASM's internal buffers and the cache. Then there is a big jump in execution time. For example, on a 300 MHz Pentium II processor, compiling a program with an array with 256,000 elements takes about 30 seconds, compiling a program with an array having 512,000 element takes several minutes. Compiling a program with a one-megabyte array seems to take forever.

There are a couple of ways to solve this problem. First, of course, you can limit the size of your arrays in your program. Unfortunately, this isn't always an option available to you. The second possibility is to use MASM v6.11; the defect was introduced in MASM after this version. The problem with MASM v6.11 is that it doesn't support the MMX instruction set, so if you're going to compile MMX instructions (or other instructions that MASM v6.11 doesn't support) with HLA you will not be able to use this option. A third option is to put your arrays in a VAR section rather than a static declaration section; HLA processes arrays you declare in the VAR section so MASM never sees them. Hence, arrays you declare in the VAR section don't suffer from this problem.

4.10 Dynamic Arrays in Assembly Language

One problem with arrays up to this point is that their size is static. That is, the number of elements in all of the examples is chosen when writing the program, it is not set while the program is running (i.e., dynamically). Alas, sometimes you simply don't know how big an array needs to be when you're writing the program; you can only determine the size of the array while the program is running. This section describes how to allocate storage for arrays dynamically so you can set their size at run time.

Allocating storage for a single dimension array, and accessing elements of that array, is a nearly trivial task at run time. All you need to do is call the HLA Standard Library malloc routine specifying the size of the array, in bytes. Malloc will return a pointer to the base address of the new array in the EAX register. Typically, you would save this address in a pointer variable and use that value as the base address of the array in all future array accesses.

To access an element of a single dimensional dynamic array, you would generally load the base address into a register and compute the index in a second register. Then you could use the based indexed addressing mode to access elements of that array. This is not a whole lot more work than accessing elements of a statically allocated array. The following code fragment demonstrates how to allocate and access elements of a single dimension dynamic array: 

static
 
	ArySize:				uns32;
 
	BaseAdrs:				pointer to uns32;
 
		.
 
		.
 
		.
 
	stdout.put( "How many elements do you want in your array? " );
 
	stdin.getu32();
 
	mov( eax, ArySize;							// Save away the upper bounds on this array.
 
	shl( 2, eax );							// Multiply eax by four to compute the number of bytes.
 
	malloc( eax );							// Allocate storage for the array.
 
	mov( eax, BaseAdrs );							// Save away the base address of the new array.
 
		.
 
		.
 
		.
 

 
	// Zero out each element of the array:
 

 
	mov( BaseAdrs, ebx );
 
	mov( 0, eax );
 
	for( mov(0, esi); esi < ArySize; inc( esi )) do
 

 
		mov( eax, [ebx + esi*4 ]);
 

 
	endfor;

Dynamically allocating storage for a multidimensional array is fairly straight-forward. The number of elements in a multidimensional array is the product of all the dimension values; e.g., a 4x5 array has 20 elements. So if you get the bounds for each dimension from the user, all you need do is compute the product of all of these bound values and multiply the final result by the size of a single element. This computes the total number of bytes in the array, the value that malloc expects.

Accessing elements of multidimensional arrays is a little more problematic. The problem is that you need to keep the dimension information (that is, the bounds on each dimension) around because these values are needed when computing the row major (or column major) index into the array1. The conventional solution is to store these bounds into a static array (generally you know the arity, or number of dimensions, at compile-time, so it is possible to statically allocate storage for this array of dimension bounds). This array of dynamic array bounds is known as a dope vector. The following code fragment shows how to allocate storage for a two-dimensional dynamic array using a simple dope vector. 

var
 
    ArrayPtr:   pointer to uns32;
 
    ArrayDims:  uns32[2];
 
		.
 
		.
 
		.
 
    // Get the array bounds from the user:
 
    
 
    stdout.put( "Enter the bounds for dimension #1: " );
 
    stdin.get( ArrayDims[0] );
 
    
 
    stdout.put( "Enter the bounds for dimension #2: " );
 
    stdin.get( ArrayDims[1*4] );
 
    
 
    // Allocate storage for the array:
 
    
 
    mov( ArrayDims[0], eax );
 
    intmul( ArrayDims[1*4], eax );
 
    shl( 2, eax );          // Multiply by four since each element is 4 bytes.
 
    malloc( eax );          // Allocate storage for the array and
 
    mov( eax, ArrayPtr );   //  save away the pointer to the array.
 
    
 
    
 
    // Initialize the array:
 
    
 
    mov( 0, edx );
 
    mov( ArrayPtr, edi );
 
    for( mov( 0, ebx ); ebx < ArrayDims[0]; inc( ebx )) do
 
    
 
        for( mov( 0, ecx ); ecx < ArrayDims[1*4]; inc( ecx )) do
 
        
 
            // Compute the index into the array
 
            // as esi := ( ebx * ArrayDims[1*4] + ecx ) * 4
 
            // (Note that the final multiplication by four is
 
            //  handled by the scaled indexed addressing mode below.)
 
            
 
            mov( ebx, esi );
 
            intmul( ArrayDims[1*4], esi );
 
            add( ecx, esi );
 
            
 
            // Initialize the current array element with edx.
 
            
 
            mov( edx, [edi+esi*4] );
 
            inc( edx );
 
            
 
        endfor;
 
        
 
    endfor;

4.11 HLA Standard Library Array Support

The HLA Standard Library provides an array module that helps reduce the effort needed to support static and dynamic arrays in your program. The "arrays.hhf" library module provides code to declare and allocate dynamic arrays, compute the index into an array, copy arrays, perform row reductions, transpose arrays, and more. This section will explore some of the more useful features the arrays module provides.

One of the more interesting features of the HLA Standard Library arrays module is that most of the array manipulation procedures support both statically allocated and dynamically allocated arrays. In fact, the HLA array procedures can automatically figure out if an array is static or dynamic and generate the appropriate code for that array. There is one catch, however. In order for HLA to be able to differentiate statically and dynamically allocated arrays, you must use the dynamic array declarations found in the arrays package. This won't be a problem because HLA's dynamic array facilities are powerful and very easy to use.

To declare a dynamic array with the HLA arrays package, you use a variable declaration like the following: 

variableName: array.dArray( elementType, Arity );

The elementType parameter is a regular HLA data type identifier (e.g., int32 or some type identifier you've defined in the TYPE section). The Arity parameter is a constant that specifies the number of dimensions for the array (arity is the formal name for "number of dimensions"). Note that you do not specify the bounds of each dimension in this declaration. Storage allocation occurs later, at run time. The following is an example of a declaration for a dynamically allocated two-dimensional matrix: 

ScreenBuffer: array.dArray( char, 2 );

The array.dArray data type is actually an HLA macro2 that expands the above to the following: 

	ScreenBuffer: record
 
						dataPtr:				dword;
 
						dopeVector:				uns32[ 2 ];
 
						elementType:				char;
 
					endrecord;

The dataPtr field will hold the base address of the array once the program allocates storage for it. The dopeVector array has one element for each array dimension (the macro uses the second parameter of the array.dArray type as the number of dimensions for the dopeVector array). The elementType field is a single object that has the same type as an element of the dynamic array. HLA provides a couple of built-in functions that you can use on these fields to extract important information. The @Elements function returns the number of elements in an array. Therefore, "@Elements( ScreenBuffer.dopeVector )" will return the number of elements (two) in the ScreenBuffer.dopeVector array. Since this array contains one element for each dimension in the dynamic array, you can use the @Elements function with the dopeVector field to determine the arity of the array. You can use the HLA @Size function on the ScreenBuffer.elementType field to determine the size of an array element in the dynamic array. Most of the time you will know the arity and type of your dynamic arrays (after all, you declared them), so you probably won't use these functions often until you start writing macros that process dynamic arrays.

After you declare a dynamic array, you must initialize the dynamic array object before attempting to use the array. The HLA Standard Library array.daAlloc routine handles this task for you. This routine uses the following syntax: 

array.daAlloc( arrayName, comma_separated_list_of_array_bounds );

To allocate storage for the ScreenBuffer variable in the previous example you could use a call like the following: 

array.daAlloc( ScreenBuffer, 20, 40 );

This call will allocate storage for a 20x40 array of characters. It will store the base address of the array into the ScreenBuffer.dataPtr field. It will also initialize ScreenBuffer.dopeVector[0] with 20 and ScreenBuffer.dopeVector[1*4] with 40. To access elements of the ScreenBuffer array you can use the techniques of the previous section, or you could use the array.index function.

The array.index function automatically computes the address of an array element for you. This function uses the following call syntax: 

array.index( reg32, arrayName, comma_separated_list_of_index_values );

The first parameter must be a 32-bit register. The array.index function will store the address of the specified array element in this register. The second array.index parameter must be the name of an array; this can be either a statically allocated array or an array you've declared with array.dArray and allocated dynamically with array.daAlloc. Following the array name parameter is a list of one or more array indices. The number of array indices must match the arity of the array. These array indices can be constants, dword memory variables, or registers (however, you must not specify the same register that appears in the first parameter as one of the array indices). Upon return from this function, you may access the specified array element using the register indirect addressing mode and the register appearing as the first parameter.

One last routine you'll want to know about when manipulating HLA dynamic arrays is the array.daFree routine. This procedure expects a single parameter that is the name of an HLA dynamic array. Calling array.daFree will free the storage associated with the dynamic array. The following code fragment is a rewrite of the example from the previous section that uses HLA dynamic arrays: 

var
 
    da:     array.dArray( uns32, 2 );
 
    Bnd1:   uns32;
 
    Bnd2:   uns32;
 
		.
 
		.
 
		.
 
    // Get the array bounds from the user:
 
    
 
    stdout.put( "Enter the bounds for dimension #1: " );
 
    stdin.get( Bnd1 );
 
    
 
    stdout.put( "Enter the bounds for dimension #2: " );
 
    stdin.get( Bnd2 );
 
    
 
    // Allocate storage for the array:
 
    
 
    array.daAlloc( da, Bnd1, Bnd2 );
 
    
 
    
 
    // Initialize the array:
 
    
 
    mov( 0, edx );
 
    for( mov( 0, ebx ); ebx < Bnd1; inc( ebx )) do
 
    
 
        for( mov( 0, ecx ); ecx < Bnd2; inc( ecx )) do
 
        
 
            // Initialize the current array element with edx.
 
            // Use array.index to compute the address of the array element.
 
            
 
            array.index( edi, da, ebx, ecx );
 
            mov( edx, [edi] );
 
            inc( edx );
 
            
 
        endfor;
 
        
 
    endfor;

Another extremely useful library module is the array.cpy routine. This procedure will copy the data from one array to another. The calling syntax is: 

array.cpy( sourceArrayName, destArrayName );

The source and destination arrays can be static or dynamic arrays. The array.cpy automatically adjusts and emits the proper code for each combination of parameters. With most of the array manipulation procedures in the HLA Standard Library, you pay a small performance penalty for the convenience of these library modules. Not so with array.cpy. This procedure is very, very fast; much faster than writing a loop to copy the data element by element.

4.12 Putting It All Together

Accessing elements of an array is a very common operation in assembly language programs. This chapter provides the basic information you need to efficiently access array elements. After mastering the material in this chapter you should know how to declare arrays in HLA and access elements of those arrays in your programs.

1Technically, you don't need the value of the left-most dimension bound to compute an index into the array, however, if you want to check the index bounds using the BOUND instruction (or some other technique), you will need this value around at run-time as well.

2See the chapter on Macros and the HLA Compile-Time Language for details on macros.

Web Site Hits Since
Jan 1, 2000

TOC PREV NEXT INDEX