汇编开发(七)：字符串与数组

作者: _凌浩雨 | 来源:发表于2019-02-23 09:55 被阅读1次

1. 字符串原语指令

String Primitive Instructions.png

使用重复前缀
如果添加重复前缀，则使用ECX作为计数器重复该指令。

Repeat Prefix.png

复制字符串

cld                     ; clear direction flag
mov esi,OFFSET string1  ; ESI points to source
mov edi,OFFSET string2  ; EDI points to target
mov ecx,10              ; set counter to 10
rep movsb               ; move 10 bytes

方向标志
字符串基元指令根据Direction标志的状态递增或递减ESI和EDI。

CLD ; clear Direction flag (forward direction)
STD ; set Direction flag (reverse direction)

Direction Flag Usage in String Primitive Instructions.png

1). MOVSB, MOVSW 和 MOVSD

MOVSB,MOVSW和MOVSD将数据从ESI指向的内存位置复制到EDI指向的内存位置。

MOVSB, MOVSW, and MOVSD.png

示例：复制DWORD数组

.data
    source DWORD 20 DUP(0FFFFFFFFh)
    target DWORD 20 DUP(?)
.code
    cld                         ; direction = forward
    mov ecx,LENGTHOF source     ; set REP counter
    mov esi,OFFSET source       ; ESI points to source
    mov edi,OFFSET target       ; EDI points to target
    rep movsd                   ; copy doublewords

2). CMPSB, CMPSW 和 CMPSD

CMPSB, CMPSW 和 CMPSD指将ESI指向的每个内存操作数都与EDI指向的内存操作数进行比较。

CMPSB, CMPSW, and CMPSD.png

示例：比较DWORD

.data
    source DWORD 1234h
    target DWORD 5678h
.code
    mov esi,OFFSET source
    mov edi,OFFSET target
    cld                         ; direction = forward
    mov ecx,LENGTHOF source     ; repetition counter
    repe cmpsd                  ; repeat while equal

3). SCASB, SCASW 和 SCASD

SCASB, SCASW和SCASD将AL / AX / EAX中的值分别与EDI寻址的字节，字或双字进行比较。这个指令可用在在字符串或者数组中查找单个字符。

示例：扫描匹配字符

.data
    alpha BYTE "ABCDEFGH",0
.code
    mov edi,OFFSET alpha    ; EDI points to the string
    mov al,'F'              ; search for the letter F
    mov ecx,LENGTHOF alpha  ; set the search count
    cld                     ; direction = forward
    repne scasb             ; repeat while not equal
    jnz quit                ; quit if letter not found
    dec edi                 ; found: back up EDI

4). STOSB, STOSW 和 STOSD

STOSB, STOSW 和 STOSD指令将AL / AX / EAX的内容分别存储在EDI指向的偏移量的内存中。

.data
    Count = 100
    string1 BYTE Count DUP(?)
.code
    mov al,0FFh             ; value to be stored
    mov edi,OFFSET string1  ; EDI points to target
    mov ecx,Count           ; character count
    cld                     ; direction = forward
    rep stosb               ; fill with contents of AL

5). LODSB, LODSW 和 LODSD

LODSB, LODSW 和 LODSD指令将ESI中的内存中的字节或字分别加载到AL / AX / EAX中。

示例：数组元素乘法

; 数组元素乘法

INCLUDE Irvine32.inc

.data
    array DWORD 1, 2, 3, 4, 5, 6, 7, 8, 9, 10   ; 测试数据
    multiplier DWORD 10

.code
main PROC
    cld                     ; direction = forward
    mov esi, OFFSET array   ; 数组首地址
    mov edi, esi            ; 目标序号
    mov ecx, LENGTHOF array ; 循环计数

L1:
    lodsd                   ; 加载[ESI]到EAX
    mul multiplier          ; 乘每个数据
    stosd                   ; 保存EAX到[EDI]
    LOOP L1             
    
    call Crlf
    call WaitMsg
    exit
main ENDP
END

2. 字符串处理程序

; Copy a source string to a target string.
Str_copy PROTO,
    source:PTR BYTE,
    target:PTR BYTE

; Return the length of a string (excluding the null byte) in EAX.
Str_length PROTO,
    pString:PTR BYTE

; Compare string1 to string2. Set the Zero and
; Carry flags in the same way as the CMP instruction.
Str_compare PROTO,
    string1:PTR BYTE,
    string2:PTR BYTE

; Trim a given trailing character from a string.
; The second argument is the character to trim.
Str_trim PROTO,
    pString:PTR BYTE,
    char:BYTE

; Convert a string to upper case.
Str_ucase PROTO,
    pString:PTR BYTE

1). Str_compare 程序

格式

INVOKE Str_compare, ADDR string1, ADDR string2

这个函数从第一个字节开始有序的比较，它比较是敏感的，因为大小写ASCII码是不同的。函数不返回值，但是他的CF和ZF会被更改。

Flags Affected by the Str_compare Procedure.png

程序源码

;-----------------------------------------------------------
Str_compare PROC USES eax edx esi edi,
    string1:PTR BYTE,
    string2:PTR BYTE
;
; Compares two strings.
; Returns nothing, but the Zero and Carry flags are affected
; exactly as they would be by the CMP instruction.
;-----------------------------------------------------------
    mov esi,string1
    mov edi,string2
    L1: mov al,[esi]
    mov dl,[edi]
    cmp al,0        ; end of string1?
    jne L2          ; no
    cmp dl,0        ; yes: end of string2?
    jne L2          ; no
    jmp L3          ; yes, exit with ZF = 1
    L2: inc esi     ; point to next
    inc edi
    cmp al,dl       ; characters equal?
    je L1           ; yes: continue loop
                    ; no: exit with flags set
    L3: ret
Str_compare ENDP

2). Str_length 程序

Str_length 程序将字符串的长度存储在EAX寄存器中返回，调用它的时候通过字符串的首地址。

INVOKE Str_length, ADDR myString

程序源码

Str_length PROC USES edi,
    pString:PTR BYTE        ; pointer to string
    mov edi,pString
    mov eax,0 ; character count
L1: 
    cmp BYTE PTR[edi],0     ; end of string?
    je L2                   ; yes: quit
    inc edi                 ; no: point to next
    inc eax                 ; add 1 to count
    jmp L1
L2: 
    ret
Str_length ENDP

3). Str_copy 程序

Str_copy 程序从源字符串复制一个以空值终止的字符串到目标字符串。当调用这个程序的时候，你必须给目标字符串一个足够大的字节数为复制字符串。

INVOKE Str_copy, ADDR source, ADDR target

程序源码

;--------------------------------------------------------
Str_copy PROC USES eax ecx esi edi,
    source:PTR BYTE, ; source string
    target:PTR BYTE ; target string
;
; Copies a string from source to target.
; Requires: the target string must contain enough
; space to hold a copy of the source string.
;--------------------------------------------------------
    INVOKE Str_length,source    ; EAX = length source
    mov ecx,eax                 ; REP count
    inc ecx                     ; add 1 for null byte
    mov esi,source
    mov edi,target
    cld                         ; direction = forward
    rep movsb                   ; copy the string
    ret
Str_copy ENDP

4). Str_trim程序

Str_trim 程序从一个以空值终止的字符串中移除所有出现的选定尾随字符。

INVOKE Str_trim, ADDR string, char_to_trim

源代码

;------------------------------------------------------------
; Str_trim
; Remove all occurrences of a given delimiter
; character from the end of a string.
; Returns: nothing
;------------------------------------------------------------
Str_trim PROC USES eax ecx edi,
    pString:PTR BYTE,       ; points to string
    char: BYTE              ; character to remove

    mov edi,pString         ; prepare to call Str_length
    INVOKE Str_length,edi   ; returns the length in EAX
    cmp eax,0               ; is the length equal to zero?
    je L3                   ; yes: exit now
    mov ecx,eax             ; no: ECX = string length
    dec eax
    add edi,eax             ; point to last character
L1: 
    mov al,[edi]            ; get a character
    cmp al,char             ; is it the delimiter?
    jne L2                  ; no: insert null byte
    dec edi                 ; yes: keep backing up
    loop L1                 ; until beginning reached
L2: 
    mov BYTE PTR [edi+1],0  ; insert a null byte
L3: 
    ret
Stmr_trim ENDP

Testing the Str_trim Procedure with a # Delimiter Character.png

5). Str_ucase 程序

Str_ucase 程序转换字符串全部为大写字符。无返回值。当调用它的时候，需要传递字符串的地址。

INVOKE Str_ucase, ADDR myString

源码

;-------------------------------------------------------
; Str_ucase
; Converts a null-terminated string to uppercase.
; Returns: nothing
;-------------------------------------------------------
Str_ucase PROC USES eax esi,
    pString:PTR BYTE
    mov esi,pString
L1:
    mov al,[esi]    ; get char
    cmp al,0        ; end of string?
    je L3           ; yes: quit
    cmp al,'a'      ; below "a"?
    jb L2
    cmp al,'z'      ; above "z"?
    ja L2
    and BYTE PTR [esi],11011111b ; convert the char
L2: 
    inc esi         ; next char
    jmp L1
L3: 
    ret
Str_ucase ENDP

6). 字符串示例

; 字符串示例

INCLUDE Irvine32.inc

.data
    string_1 BYTE "abcde////",0
    string_2 BYTE "ABCDE",0
    msg0 BYTE "string_1 in upper case: ",0
    msg1 BYTE "string_1 and string_2 are equal",0
    msg2 BYTE "string_1 is less than string_2",0
    msg3 BYTE "string_2 is less than string_1",0
    msg4 BYTE "Length of string_2 is ",0
    msg5 BYTE "string_1 after trimming: ",0

.code
main PROC
    
    call trim_string
    call upper_case
    call compare_strings
    call print_length
    
    call Crlf
    call WaitMsg
    exit
main ENDP

trim_string PROC
    ; 从string_1移除选定的尾随字符
    INVOKE Str_trim, ADDR string_1, '/'
    mov edx, OFFSET msg5
    call WriteString
    mov edx, OFFSET string_1
    call WriteString
    call Crlf
    RET
trim_string ENDP

upper_case PROC
    ; 将string_1转换为大写
    mov edx, OFFSET msg0
    call WriteString
    INVOKE str_ucase, ADDR string_1
    mov edx, OFFSET string_1
    call WriteString
    call Crlf
    RET
upper_case ENDP

compare_strings PROC
    ; 比较string_1 和 string_2
    INVOKE Str_compare, ADDR string_1, ADDR string_2
    .IF ZERO?
        mov edx, OFFSET msg1
    .ELSEIF CARRY?
        mov edx, OFFSET msg2        ; string 1 is less than ...
    .ELSEIF 
        mov edx, OFFSET msg3        ; string 2 is less than ...
    .ENDIF
    call WriteString
    call Crlf
    RET
compare_strings ENDP

print_length PROC
    ; 显示string_2的长度
    mov edx, OFFSET msg4
    call WriteString
    INVOKE Str_length, ADDR string_2
    call WriteDec
    call Crlf
    RET
print_length ENDP
END

String Library Demo.png

7). Irvine64库中字符串程序

String Procedures in the Irvine64 Library.png

Str_compare

; -------------------------------------------------
; Str_compare
; Compares two strings
; Receives: RSI points to the source string
; RDI points to the target string
; Returns: Sets ZF if the strings are equal
; Sets CF if source < target
; -------------------------------------------------
Str_compare PROC USES rax rdx rsi rdi
L1: 
    mov al,[rsi]
    mov dl,[rdi]
    cmp al,0        ; end of string1?
    jne L2          ; no
    cmp dl,0        ; yes: end of string2?
    jne L2          ; no
    jmp L3          ; yes, exit with ZF = 1
L2: 
    inc rsi         ; point to next
    inc rdi
    cmp al,dl       ; chars equal?
    je L1           ; yes: continue loop
    ; no: exit with flags set
L3: 
    ret
Str_compare ENDP

Str_copy

;------------------------------------------------------
; Str_copy
; Copies a string
; Receives: RSI points to the source string
; RDI points to the target string
; Returns: nothing
;------------------------------------------------------
Str_copy PROC USES rax rcx rsi rdi
    mov rcx,rsi     ; get length of source string
    call Str_length ; returns length in RAX
    mov rcx,rax     ; loop counter
    inc rcx         ; add 1 for null byte
    cld             ; direction = up
    rep movsb       ; copy the string
    ret
Str_copy ENDP

Str_length

;-------------------------------------------------------
; Str_length
; Gets the length of a string
; Receives: RCX points to the string
; Returns: length of string in RAX
;-------------------------------------------------------
Str_length PROC USES rdi
    mov rdi,rcx             ; get pointer
    mov eax,0               ; character count
L1:
    cmp BYTE PTR [rdi],0    ; end of string?
    je L2                   ; yes: quit
    inc rdi                 ; no: point to next
    inc rax                 ; add 1 to count
    jmp L1
L2: 
    ret                     ; return count in RAX
Str_length ENDP

测试程序

; 测试Irvine64库字符串程序

Str_compare PROTO
Str_length PROTO
Str_copy PROTO
ExitProcess PROTO

.data
    source BYTE "AABCDEFGAABCDEFG", 0
    target BYTE 20 DUP(0)

.code
main PROC
    mov rcx, offset source
    call Str_length             ; 在EAX中返回字符串长度

    mov rsi, offset source
    mov rdi, offset target
    call Str_copy               ; 复制字符串
    call Str_compare            ; ZF = 1， 字符串相等

    ; 改变目标字符串中第一个字符，并再一次比较
    mov target, 'B'
    call str_compare            ; CF = 1， source < target
    mov ecx, 0
    call ExitProcess
main ENDP
END

3. 二维数组

1). 行和列的排序

在汇编语言中，二维数组是一维数组的高级抽象。高级语言在内存中整理选择行和列两个方法中的一个：行为主轴排序，列为主轴排序。当行为主轴排列的时候，第一行出现在内存块的开头，第一行的最后一个元素跟随者第二行第一个元素。当列为主轴排列的时候，第一列出现在内存卡的开头，第一列的最后一个元素跟随者第二列的第一个元素。x86指令集包括两个操作数类型，base-index和base-index-displacement，两者都适用于数组应用程序。

Row-major and column-major ordering.png

2). Base-Index 操作数

Base-Index操作数将两个寄存器的值相加。方括号是必须要写的，

[base + index]

示例：

.data
    array WORD 1000h,2000h,3000h
.code
    mov ebx,OFFSET array
    mov esi,2
    mov ax,[ebx+esi] ; AX = 2000h
    mov edi,OFFSET array
    mov ecx,4
    mov ax,[edi+ecx] ; AX = 3000h
    mov ebp,OFFSET array
    mov esi,0
    mov ax,[ebp+esi] ; AX = 1000h

二维数组
当以行主要顺序访问二维数组时，行偏移保存在基址寄存器中，列偏移量在索引寄存器中。

; 三行无列的数组

tableB BYTE 10h, 20h, 30h, 40h, 50h
Rowsize = ($ - tableB)
    BYTE 60h, 70h, 80h, 90h, 0A0h
    BYTE 0B0h, 0C0h, 0D0h, 0E0h, 0F0h
; 获取数据方式
row_index = 1
column_index = 2
mov ebx,OFFSET tableB ; table offset
add ebx,RowSize * row_index ; row offset
mov esi,column_index
mov al,[ebx + esi] ; AL = 80h

Addressing an array with a base-index operand.png

计算列的和

;-----------------------------------------------------------
; calc_row_sum
; Calculates the sum of a row in a byte matrix.
; Receives: EBX = table offset, EAX = row index,
; ECX = row size, in bytes.
; Returns: EAX holds the sum.
;-----------------------------------------------------------
calc_row_sum PROC USES ebx ecx edx esi
    mul ecx                         ; row index * row size
    add ebx,eax                     ; row offset
    mov eax,0                       ; accumulator
    mov esi,0                       ; column index
L1: 
    movzx edx,BYTE PTR[ebx + esi]   ; get a byte
    add eax,edx                     ; add to accumulator
    inc esi                          ; next byte in row
    loop L1
    ret
calc_row_sum ENDP

缩放因子

; 其中TYPE tableW的值为2，即缩放因子。
.data
    tableW WORD 10h, 20h, 30h, 40h, 50h
    RowsizeW = ($ - tableW)
         WORD 60h, 70h, 80h, 90h, 0A0h
         WORD 0B0h, 0C0h, 0D0h, 0E0h, 0F0h
.code
    row_index = 1
    column_index = 2
    mov ebx,OFFSET tableW           ; table offset
    add ebx,RowSizeW * row_index    ; row offset
    mov esi,column_index
    mov ax,[ebx + esi*TYPE tableW]  ; AX = 0080h

3). Base-Index-Displacement 操作数

Base-Index-Displacement 操作数联合移位，基寄存器，索引寄存器和一个可选的缩放因子产生一个有效的地址。

[base + index + displacement]
displacement[base + index]

示例：

.data
    tableD DWORD 10h, 20h, 30h, 40h, 50h
    Rowsize = ($ - tableD)
     DWORD 60h, 70h, 80h, 90h, 0A0h
     DWORD 0B0h, 0C0h, 0D0h, 0E0h, 0F0h
.code 
    mov ebx,Rowsize         ; row index
    mov esi,2               ; column index
    mov eax,tableD[ebx + esi*TYPE tableD]

Base-index-displacement example.png

4). 64位中的Base-Index操作数

; 64位下的二维数组

Crlf PROTO
WriteInt64 PROTO
ExitProcess PROTO

.data
    table QWORD 1, 2, 3, 4, 5
    RowSize = ($ - table)
        QWORD 6, 7, 8, 9, 10
        QWORD 11, 12, 13, 14, 15
.code
main PROC
    ; base-index-displacement 操作数
    mov rax, 1              ; 行索引
    mov rsi, 4              ; 列索引
    call get_tableVal       ; 返回值给RAX
    call WriteInt64         ; 显示
    call Crlf


    mov ecx, 0              ; 结束程序
    call ExitProcess
main ENDP

;---------------------------------------------------
; get_tableVal
; Returns the array value at a given row and column
; in a two-dimensional array of quadwords.
; Receives: RAX = row number, RSI = column number
; Returns: value in RAX
;---------------------------------------------------
get_tableVal PROC USES rbx
    mov rbx, RowSize
    mul rbx                 ; 结果存放在RAX中
    mov rax, table[rax + rsi * TYPE table]
    RET
get_tableVal ENDP

END

4. 搜索和排序整型数组

1). 冒泡排序

冒泡排序比较数组中的数值，开始位置为0和1，如果比较是逆序的，则将他们交换。一次循环之后，这个数组仍然是无序的，但是最大的值在索引最大的位置，通过外层循环n-1次之后，这个数组变成有序的。

First pass through an array (bubble sort).png

冒泡排序的平均运行时间如下图

Average running time.png

代码

;-------------------------------------------------------
; BubbleSort
; Sort an array of 32-bit signed integers in ascending
; order, using the bubble sort algorithm.
; Receives: pointer to array, array size
; Returns: nothing
;-------------------------------------------------------
BubbleSort PROC USES eax ecx esi,
    pArray:PTR DWORD,   ; pointer to array
    Count:DWORD         ; array size
    mov ecx,Count
    dec ecx             ; decrement count by 1
L1: 
    push ecx            ; save outer loop count
    mov esi,pArray      ; point to first value
L2: 
    mov eax,[esi]       ; get array value
    cmp [esi+4],eax     ; compare a pair of values
    jg L3               ; if [ESI] <= [ESI+4], no exchange
    xchg eax,[esi+4]    ; exchange the pair
    mov [esi],eax
L3: 
    add esi,4           ; move both pointers forward
    loop L2             ; inner loop
    pop ecx             ; retrieve outer loop count
    loop L1             ; else repeat outer loop
L4: 
    ret
BubbleSort ENDP

2). 二叉树搜索

在搜索大型数组中的单个项目时，二叉树搜索算法特别有效。它有一个重要的前提条件：数组元素必须按升序或降序排列。

Maximum Comparisons for Sequential and Binary Search.png

;--------------------------------------------------------------
; BinarySearch
; Searches an array of signed integers for a single value.
; Receives: Pointer to array, array size, search value.
; Returns: If a match is found, EAX = the array position of the
; matching element; otherwise, EAX = -1.
;--------------------------------------------------------------
BinarySearch PROC USES ebx edx esi edi,
    pArray:PTR DWORD, ; pointer to array
    Count:DWORD, ; array size
    searchVal:DWORD ; search value

    LOCAL first:DWORD, ; first position
        last:DWORD, ; last position
        mid:DWORD ; midpoint
    mov first,0 ; first = 0
    mov eax,Count ; last = (count - 1)
    dec eax
    mov last,eax
    mov edi,searchVal ; EDI = searchVal
    mov ebx,pArray ; EBX points to the array
L1:
    ; while first <= last
    mov eax,first
    cmp eax,last
    jg L5 ; exit search
    ; mid = (last + first) / 2
    mov eax,last
    add eax,first
    shr eax,1
    mov mid,eax
    ; EDX = values[mid]
    mov esi,mid
    shl esi,2 ; scale mid value by 4
    mov edx,[ebx+esi] ; EDX = values[mid]
    ; if ( EDX < searchval(EDI) )
    cmp edx,edi
    jge L2
    ; first = mid + 1
    mov eax,mid
    inc eax
    mov first,eax
    jmp L4
    ; else if( EDX > searchVal(EDI) )
L2: 
    cmp edx,edi ; optional
    jle L3
    ; last = mid - 1
    mov eax,mid
    dec eax
    mov last,eax
    jmp L4
    ; else return mid
L3: 
    mov eax,mid ; value found
    jmp L9 ; return (mid)
L4: 
    jmp L1 ; continue the loop
L5: 
    mov eax,-1 ; search failed
L9: 
    ret
BinarySearch ENDP