x86 MASM Chapter 9

Chapter 9: Strings and Arrays

9.1 Introduction

• Understanding efficient string and array processing is crucial for code optimization.

• Studies indicate that most programs spend 90% of their execution time in 10% of their code.

• This critical 10% is often marked by loops that handle strings and arrays.

• Techniques for efficient string and array processing will be covered.

• Starting with optimized string primitive instructions for data manipulation (moving, comparing, loading, and storing).

• Introduction to several string-handling procedures in Irvine32 and Irvine64 libraries, similar to the standard C string library.

• The manipulation of two-dimensional arrays will be discussed, including advanced addressing modes: base-index and base-index-displacement.

• Section 9.5 will focus on searching and sorting integer arrays, emphasizing practical algorithms: bubble sort and binary search.

• Encouragement to study these algorithms in Java or C++ as well as assembly language.

9.2 String Primitive Instructions

• The x86 instruction set includes five groups of instructions for processing arrays.

• Although termed string primitives, they apply to more than just character arrays.

• In 32-bit mode, instructions use ESI and EDI registers for addressing memory, while the accumulator uses AL, AX, or EAX based on data size.

• String primitives execute operations efficiently by automatically handling array indexes.

9.2.1 MOVSB, MOVSW, and MOVSD

• MOVSB: Move string bytes from memory at ESI to memory at EDI.

• MOVSW: Move string words.

• MOVSD: Move string doublewords.

• The increment/decrement behavior of ESI and EDI depends on the Direction flag (DF).

• The size of the increment or decrement based on the instruction:

  • MOVSB: 1 byte

  • MOVSW: 2 bytes

  • MOVSD: 4 bytes

• Example for Copying Doubleword Array:

  .data
  source DWORD 20 DUP (FFFFFFFFH)
  target DWORD 20 DUP(?)
  .code
  cld
  mov ecx, LENGTHOF source
  mov esi, OFFSET source
  mov edi, OFFSET target
  rep movsd

9.2.2 CMPSB, CMPSW, and CMPSD

• CMPSB: Compare string bytes.

• CMPSW: Compare string words.

• CMPSD: Compare string doublewords.

• It is possible to use a repeat prefix with these instructions to compare multiple elements efficiently.

9.2.3 SCASB, SCASW, and SCASD

• SCASB: Compare AL to a string byte (memory at EDI).

• SCASW: Compare AX to a string word.

• SCASD: Compare EAX to a string doubleword.

• Used for searching single values in strings or arrays.

9.2.4 STOSB, STOSW, and STOSD

• STOSB: Store contents of AL into the memory location pointed by EDI.

• STOSW: Store AX; STOSD: store EAX.

• When used with the REP prefix, useful for filling a string or array with a single value.

9.2.5 LODSB, LODSW, and LODSD

• LODSB: Load byte from memory at ESI into AL.

• LODSW: Load word into AX; LODSD: load doubleword into EAX.

• Each increment/decrement based on Direction flag.

9.2.6 Section Review

• This section includes questions regarding string primitives and their behavior.

• Register that acts as the accumulator in reference to string primitives is EAX.

9.3 Selected String Procedures

• Demonstrating several procedures from the Irvine32 library for manipulating null-terminated strings similar to standard C library functions.

9.3.1 Str_compare Procedure

• Compares two strings and affects the Zero and Carry flags accordingly.

• Call format: INVOKE Str_compare, ADDR string1, ADDR string2.

9.3.2 Str_length Procedure

• Returns the length of a string (excluding the null byte) in EAX.

• Call format: INVOKE Str_length, ADDR myString.

9.3.3 Str_copy Procedure

• Copies a null-terminated string from one location to another.

• Ensures the target string has enough space.

• Call format: INVOKE Str_copy, ADDR source, ADDR target.

9.3.4 Str_trim Procedure

• Removes trailing occurrences of a specified character from a string.

• Call format: INVOKE Str_trim, ADDR string, char_to_trim.

• Handles multiple cases of string content during trimming.

9.3.5 Str_ucase Procedure

• Converts a string to uppercase. Call format: INVOKE Str_ucase, ADDR myString.

9.3.6 String Library Demo Program

• Example 32-bit program illustrating the use of the above procedures in Irvine32 library.

9.3.7 String Procedures in the Irvine64 Library

• Discusses translation of string-handling procedures to 64-bit mode.

• Changes include stack parameters and register adjustments (32-bit -> 64-bit).

9.4 Two-Dimensional Arrays

9.4.1 Ordering of Rows and Columns

• Two-dimensional arrays can be stored in row-major order or column-major order.

• Row-major order places data of the first row consecutively in memory.

9.4.2 Base-Index Operands

• Combines a base register and an index register to produce an address.

• Example usage provided for clarity regarding accessing array elements.

9.4.3 Base-Index-Displacement Operands

• Combines an additional displacement with the previous operands to effectively address two-dimensional arrays.

9.4.4 Base-Index Operands in 64-Bit Mode

• Register usage changes from 32-bit to 64-bit mode must be carefully managed in assembly.

9.5 Searching and Sorting Integer Arrays

9.5.1 Bubble Sort

• Simple sorting algorithm that compares adjacent elements.

• Describes the operation through pseudocode transitioning to assembly.

9.5.2 Binary Search

• Efficient search algorithm for sorted arrays leveraging divide-and-conquer.

• Described with both C++ and assembly language implementations.

9.6 Java Bytecodes: String Processing (Optional Topic)

• Illustrates how Java handles strings through bytecode analysis.

9.7 Chapter Summary

• Recap of string primitive instructions and their optimizations.

• Summary of string and array manipulations and the performance benefits from assembly language.

9.8 Key Terms and Instructions

• base-index operands

• base-index-displacement operands

• CMPSB, CMPSW, CMPSD

• column-major order

• Direction flag

• LODSB, LODSW, LODSD

• MOVSB, MOVSW, MOVSD

• REP, REPE, REPNE, REPNZ, REPZ

9.1 Introduction

• Importance of Optimization: Studies indicate that most programs spend $90\%$ of their execution time in $10\%$ of their code. This critical section often involves loops processing large datasets, strings, and arrays.

• Efficiency: Assembly language is preferred for these tasks because string primitive instructions are optimized at the hardware level, executing faster than manual loops in high-level languages.

• Key Areas of Focus:

  • String primitive instructions for data movement, comparison, loading, and storing.

  • Irvine32 and Irvine64 library procedures for higher-level string manipulation.

  • Multi-dimensional array addressing via advanced modes: base-index and base-index-displacement.

  • Algorithmic efficiency through implementations of Bubble Sort and Binary Search.

9.2 String Primitive Instructions

• General Mechanism: String primitives use specific registers to facilitate automatic iteration. In 32-bit mode:

  • $ESI$ (Source Index): Points to the source memory location.

  • $EDI$ (Destination Index): Points to the destination memory location.

  • $EAX$ ($AL, AX, EAX$): Acts as the accumulator for loading or comparing data.

  • $ECX$: Acts as a counter for repeat prefixes.

• Direction Flag ($DF$): Determines the direction of processing.

  • CLD (Clear Direction Flag): Sets $DF = 0$, causing indices to increment (forward processing).

  • STD (Set Direction Flag): Sets $DF = 1$, causing indices to decrement (backward processing).

9.2.1 MOVSB, MOVSW, and MOVSD

• Function: Copies data from the memory location pointed to by $ESI$ to the location pointed to by $EDI$.

• Sizes:

  • MOVSB: Copies 1 byte ($ESI$ and $EDI$ increment/decrement by 1).

  • MOVSW: Copies 2 bytes (increment/decrement by 2).

  • MOVSD: Copies 4 bytes (increment/decrement by 4).

• Repeat Prefix (REP): When prepended, the instruction repeats $ECX$ times, decrementing $ECX$ after each operation until it reaches 0.

9.2.2 CMPSB, CMPSW, and CMPSD

• Function: Compares the value at [ESI] with the value at [EDI] by performing an implicit subtraction. It updates the status flags (Zero, Sign, Overflow, etc.) but does not change the operands.

• Repeat Prefixes:

  • REPE/REPZ: Repeat while the elements are equal ($ZF = 1$) and $ECX > 0$.

  • REPNE/REPNZ: Repeat while the elements are not equal ($ZF = 0$) and $ECX > 0$.

9.2.3 SCASB, SCASW, and SCASD

• Function: Scans a string or array by comparing the value in the accumulator ($AL, AX, EAX$) to the value in memory pointed to by $EDI$.

• Usage: Highly effective for finding a specific character or value within an array when combined with REPE or REPNE.

9.2.4 STOSB, STOSW, and STOSD

• Function: Copies the value in the accumulator to the memory pointed to by $EDI$.

• Application: Frequently used to initialize an entire array or string with a specific constant value (e.g., zeroing out a buffer).

9.2.5 LODSB, LODSW, and LODSD

• Function: Loads a value from memory at $ESI$ into the accumulator.

• Note: This instruction is rarely used with the REP prefix because it would overwrite the accumulator on every iteration, leaving only the last value. It is typically used inside a manual loop where further processing is needed on each element.

9.3 Selected String Procedures

• Str_compare: Performs a lexicographical comparison of two null-terminated strings. It sets the Zero flag if the strings are identical.

• Str_length: Scans a string until the null terminator ($00h$) is found and returns the count in $EAX$.

• Str_copy: Copies source to target; the programmer must ensure the target buffer size is at least Str_length(source) + 1 to prevent buffer overflows.

• Str_trim: Removes a trailing character by searching from the end of the string backwards and inserting a null terminator at the first non-matching character position.

• 64-bit Adjustments: In 64-bit mode, pointers must be 64 bits ($RSI, RDI, RDX, RCX$), and parameters are passed via registers ($RCX, RDX, R8, R9$) instead of the stack.

9.4 Two-Dimensional Arrays

9.4.1 Ordering and Addressing

• Row-Major Order: Consecutive rows are stored in memory. The address of an element at $row\, i, column\, j$ is calculated as:

  • $Base + (i \times row_size) + (j \times element_size)$.

• Base-Index Operands: Uses two registers, such as [ebx + esi], where one register usually holds the row offset and the other holds the column index.

• Base-Index-Displacement: Formatted as [base + index + displacement]. This is ideal for arrays of structures, where 'displacement' is the offset of a specific field within the structure.

9.5 Searching and Sorting Integer Arrays

9.5.1 Bubble Sort

• Logic: Iterates through an array, comparing adjacent elements and swapping them if they are in the wrong order. This process is repeated until no swaps occur.

• Complexity: $O(n^2)$, making it inefficient for large datasets but simple for small assembly tasks.

9.5.2 Binary Search

• Pre-requisite: The array must be sorted beforehand.

• Logic: Compares the target value to the middle element. If not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half.

• Performance: $O(\log n)$, significantly faster than linear search for large arrays.

9.7 Chapter Summary

• String primitives ($MOVS, CMPS, SCAS, STOS, LODS$) provide hardware-accelerated array processing.

• Repeat prefixes ($REP, REPE, REPNE$) control the execution of primitives based on $ECX$ and the Zero flag.

• Two-dimensional arrays are managed using complex addressing modes that combine base registers, index registers, and constant displacements.

9.1 Introduction

• The 90/10 Rule of Optimization: Optimization efforts are most effective when directed at the critical $10\%$ of code where programs spend $90\%$ of their execution time. These bottlenecks are typically loops that traverse large strings or arrays.

• Hardware-Level Efficiency: x86 string primitives are highly optimized at the microcode level. Unlike manual loops that fetch, decode, and execute multiple instructions per iteration (e.g., MOV, INC, LOOP), string primitives perform the operation and the pointer adjustment in a single, highly pipelined execution cycle.

• Scope of Primitives: Despite the name "string," these instructions are versatile and process any contiguous data blocks, including integer arrays, floating-point buffers, or custom structures.

9.2 String Primitive Instructions

• Register Roles in 32-bit Mode:

  • $ESI$ (Source Index): Holds the memory address of the input data. By convention, it points to the source.

  • $EDI$ (Destination Index): Holds the memory address of the output or target data.

  • $ECX$: Serves as the loop counter when used with repeat prefixes ($REP$, $REPE$, etc.).

  • Accumulator ($AL, AX, EAX$): Stores the operand for instructions like $STOS$, $SCAS$, and $LODS$.

• The Direction Flag ($DF$):

  • If $DF = 0$ (via CLD), the addresses in $ESI$ and $EDI$ are incremented after each operation (Forward processing).

  • If $DF = 1$ (via STD), the addresses are decremented (Backward processing).

  • Safety Note: It is vital to clear the direction flag after completing backward operations to prevent unexpected behavior in subsequent code.

9.2.1-9.2.5 Detailed Primitive Breakdown

1. $MOVSB, MOVSW, MOVSD$:

   • Moves data from [ESI] to [EDI].

   • Often used with the REP prefix. REP continues as long as $ECX > 0$. Each iteration decrements $ECX$ and updates $ESI/EDI$.

2. $CMPSB, CMPSW, CMPSD$:

   • Logic: [ESI] - [EDI].

   • Updates the flags ($ZF, CF, SF, OF$) based on the result.

   • Used with REPE (Repeat while Equal) for checking if two strings are identical, or REPNE (Repeat while Not Equal) to find the first differing element.

3. $SCASB, SCASW, SCASD$:

   • Logic: accumulator - [EDI].

   • Scans memory for a match to the value in the accumulator.

   • REPNE SCASB is the standard assembly idiom for strchr (finding a character) or calculating string length (searching for a null terminator).

4. $STOSB, STOSW, STOSD$:

   • Logic: [EDI] = accumulator.

   • Combined with REP, this is the most efficient way to implement memset() (e.g., clearing a buffer to zero).

5. $LODSB, LODSW, LODSD$:

   • Logic: accumulator = [ESI].

   • Unlike others, it is rarely paired with REP because each iteration would simply overwrite the previous value in the accumulator. It is usually used inside a loop to fetch a value for custom processing.

9.3 Selected String Procedures

• $Str_compare$ Implementation: It compares strings lexicographically. If String 1 < String 2, the Carry flag is set. If String 1 = String 2, the Zero flag is set. It handles the null terminator internally.

• $Str_length$ Mechanics: It often uses SCASB with a target value of $00h$ in $AL$. It finds the offset of the null terminator and subtracts the starting address to find the count.

• $Str_trim$ Strategy:

  1. Calculate string length.

  2. Point to the end of the string (just before the null terminator).

  3. Move backwards as long as the current character matches the "chartotrim".

  4. Place a new null terminator ($00h$) at the first non-matching position found.

• 64-bit Procedure Variations:

  • Addresses are 64-bit ($RSI, RDI, RAX$).

  • The calling convention changes: instead of pushing arguments to the stack, the first four arguments are passed in $RCX, RDX, R8, R9$.

9.4 Two-Dimensional Arrays

• Row-Major Storage: Standard in most languages (C, C++, Java). The row is the primary index. For an array with $N$ columns, the offset of element $(row, col)$ is:

  • $Offset = (row \times N + col) \times element_size$

• Column-Major Storage: Used in languages like Fortran. The column is the primary index. The offset is calculated as:

  • $Offset = (col \times M + row) \times element_size$ (where $M$ is the number of rows).

• Addressing Modes:

  • Base-Index: [EBX + ESI]. EBX might hold the base address of a specific row, and ESI the offset of the column within that row.

  • Base-Index-Displacement: [EBX + ESI + displacement]. Often used for an array of structures, where the displacement targets a specific field within the struct.

9.5 Searching and Sorting

• Bubble Sort Process:

  • Uses nested loops. The outer loop runs $n-1$ times. The inner loop compares adjacent elements $A[i]$ and $A[i+1]$.

  • If $A[i] > A[i+1]$, they are swapped.

  • After the first pass, the largest element is "bubbled" to the last position. The effective size of the array for the next pass then decreases by 1.

• Binary Search Algorithm:

  • Requires a sorted array.

  • Variables: Low, High, Mid.

  • While Low <= High:

  1. $Mid = (Low + High) / 2$

  2. If Target == Array[Mid], return index.

  3. If Target < Array[Mid], set High = Mid - 1.

  4. If Target > Array[Mid], set Low = Mid + 1.

  • This logarithmic approach ($O(\log n)$) is vastly superior to linear search ($O(n)$) for large datasets.

9.7 Performance Summary

• Using REP with string primitives eliminates the overhead of the instruction fetch cycle for the loop body during repetition.

• Assembly allows for precise control over the Direction Flag and the specific increment size ($1, 2, 4$ bytes), allowing for fine-tuned data alignment which is crucial for maximizing cache performance.