4.41 Dynamic Arrays in Assembly Language

One problem with arrays as this chapter describes them is that their size is static. That is, the number of elements in all of the examples was chosen when writing the program; it was not selected while the program runs (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 runtime.

Allocating storage for a single dimension array, and accessing elements of that array, is a nearly trivial task at runtime. 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 straightforward. 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 array.^[34] 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 because 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;

^[34]Technically, you don't need the value of the leftmost 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 runtime as well.