汇编冒泡排序

PS：由于Redefine主题和Butterfly主题目前都不支持汇编代码高亮，所以如果想要看到更好看的代码可以联系我拿博文的PDF版本

原题

问题2

请理解给定的do_swap汇编函数功能，写出等价的 C 语言函数代码；提示需注意数据类型，如长度、有无符号等（unsigned char ？无符号 1 Byte 长的变量？）

问题3

请用汇编语言实现冒泡排序函数（需要有详尽的代码注释）；提示会调用到已给定的do_swap汇编函数

（提示会自动对所实现的冒泡排序函数进行重复测试，无需自行输入字符串）

初始代码

.arch i386
.intel_syntax noprefix

.data
.globl	_char_list
.globl	_char_list_len
.globl	_check_flag
.globl	_test_no

.data
_char_list_len:
	.byte	10
	.bss
	.align 4
_char_list:
	.space 11

.data
_check_flag:
	.byte	1
_test_no:
	.byte	1
	.section .rdata,"dr"
	.align 4

.data
hint_test_no:
	.ascii "\12-----------------------------test-%d\12\0"
hint_given_array:
	.ascii "The given array:  %s\12\0"
hint_sorted_array:
	.ascii "The sorted array: %s\12\0"

hint_test_error_bar:
	.ascii "\12--!--!--!--!--!--!--!--!--!--test-%d\12\12\0"
hint_test_error:
	.ascii "Sorry but try it again!\12\0"
	.align 4
hint_test_success_bar:
	.ascii "\12--*--*--*--*--*--*--*--*--*--passed!\12\12\0"
hint_test_success:
	.ascii "Well done!\12\0"

.text
.extern _printf
.extern _puts
.extern _time    # C标准库函数：获取系统时间；可以用于设定随机数种子
.extern _srand   # C标准库函数：用于设定随机数种子
.extern _rand    # C标准库函数：生成随机数

.globl	gen_random_list
.globl	do_swap
.globl	do_bubble_sort
.globl	check_sort
.globl	_main

#Function-1# 根据时间种子，随机生成由大小写英文字母构成的字符数组
gen_random_list:
	push	ebp
	mov	ebp, esp
	sub	esp, 12

	mov	BYTE PTR [ebp-1], 0
in_gen_random_list_loop:
	movzx	eax, BYTE PTR _char_list_len
	cmp	BYTE PTR [ebp-1], al
	jnb	end_gen_random_list

	mov	DWORD PTR [esp], 0
	call	_time
	mov	edx, eax
	movzx	eax, BYTE PTR [ebp-1]
	add	edx, eax
	movzx	eax, BYTE PTR _test_no
	movzx	eax, al
	add	eax, edx
	mov	DWORD PTR [esp], eax
	call	_srand

	call	_rand
	and	eax, 1
	test	eax, eax
	setne	al
	test	al, al
	je	in_gen_lower_letter

	call	_rand
	mov	ecx, eax
	mov	edx, 0x4EC4EC4F
	mov	eax, ecx
	imul	edx
	sar	edx, 3
	mov	eax, ecx
	sar	eax, 31  # 算数右移指令；其中，与逻辑右移shr 补 0 不同，sar 补位时，最高位保持不变
	sub	edx, eax
	mov	eax, edx
	imul	eax, eax, 26  # 有符号乘法指令，eax * 26 --所得乘积放入--> eax
	sub	ecx, eax
	mov	eax, ecx
	mov	edx, eax
	movzx	eax, BYTE PTR [ebp-1]
	add	edx, 65
	mov	BYTE PTR _char_list[eax], dl

	jmp	in_gen_upper_letter

in_gen_lower_letter:
	call	_rand
	mov	ecx, eax
	mov	edx, 0x4EC4EC4F
	mov	eax, ecx
	imul	edx
	sar	edx, 3   # 算数右移指令；其中，与逻辑右移shr 补 0 不同，sar 补位时，最高位保持不变
	mov	eax, ecx
	sar	eax, 31
	sub	edx, eax
	mov	eax, edx
	imul	eax, eax, 26
	sub	ecx, eax
	mov	eax, ecx
	mov	edx, eax
	movzx	eax, BYTE PTR [ebp-1]
	add	edx, 97
	mov	BYTE PTR _char_list[eax], dl

in_gen_upper_letter:
	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	mov	BYTE PTR [ebp-1], al
	jmp	in_gen_random_list_loop

end_gen_random_list:
	movzx	eax, BYTE PTR _char_list_len
	movzx	eax, al
	mov	BYTE PTR _char_list[eax], 0  # 字符数组末尾置零，方便按字符串进行一次性整体打印

	movzx	eax, BYTE PTR _test_no
	movzx	eax, al

	mov	DWORD PTR [esp+4], eax
	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_no
	call	_printf

	mov	DWORD PTR [esp+4], OFFSET FLAT:_char_list
	mov	DWORD PTR [esp], OFFSET FLAT:hint_given_array
	call	_printf

	leave
	ret

#Function-2# 实现交换两个指针各自指向的数据内容
do_swap:                          #*# 问题-2：请理解已给定的do_swap汇编函数功能，写出等价的 C 语言函数代码
                                  #          提示需注意数据类型，如长度、有无符号等
	push	ebp
	mov	ebp, esp
	sub	esp, 4

	mov	eax, DWORD PTR [ebp+8]
	movzx	eax, BYTE PTR [eax]
	mov	BYTE PTR [ebp-1], al

	mov	eax, DWORD PTR [ebp+12]
	movzx	edx, BYTE PTR [eax]
	mov	eax, DWORD PTR [ebp+8]
	mov	BYTE PTR [eax], dl

	mov	eax, DWORD PTR [ebp+12]
	movzx	edx, BYTE PTR [ebp-1]
	mov	BYTE PTR [eax], dl

	leave
	ret

#Function-3# 对排序结果得正确性进行检查
check_sort:
	push	ebp
	mov	ebp, esp
	sub	esp, 12

	mov	DWORD PTR [esp+4], OFFSET FLAT:_char_list
	mov	DWORD PTR [esp], OFFSET FLAT:hint_sorted_array
	call	_printf

	mov	BYTE PTR [ebp-1], 0

in_check_loop:
	movzx	eax, BYTE PTR [ebp-1]
	movzx	edx, BYTE PTR _char_list_len
	movzx	edx, dl
	sub	edx, 1
	cmp	eax, edx
	jge	end_check_sort

	movzx	eax, BYTE PTR [ebp-1]
	movzx	edx, BYTE PTR _char_list[eax]
	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	dl, al
	jbe	in_error_check

	movzx	eax, BYTE PTR [ebp-1]
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	al, 96
	jbe	in_error_marked

	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	al, 90
	jbe	continue_in_check_loop

in_error_marked:
	mov	BYTE PTR _check_flag, 0
	jmp	end_check_sort

in_error_check:
	movzx	eax, BYTE PTR [ebp-1]
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	al, 90
	ja	continue_in_check_loop

	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	al, 96
	jbe	continue_in_check_loop

	mov	BYTE PTR _check_flag, 0
	jmp	end_check_sort

continue_in_check_loop:
	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	mov	BYTE PTR [ebp-1], al
	jmp	in_check_loop

end_check_sort:
	leave
	ret

#Function-4# 冒泡排序函数
do_bubble_sort:                          #*# 问题-3：请用汇编语言实现冒泡排序函数；
                                         #          提示会调用到已给定的do_swap汇编函数
	push	ebp
	mov	ebp, esp
	sub	esp, 16

### ------------------------------------冒泡排序正文----------------------------------------开始
    nop     # 为 No Operation 缩写，表示不进行任何有效操作的汇编指令
    nop
    nop
### ------------------------------------冒泡排序正文----------------------------------------结束

end_bubble_sort:
	leave
	ret

#Function-5# 主函数 main
_main:
	push	ebp
	mov	ebp, esp
	sub	esp, 8

test_loop:
	movzx	eax, BYTE PTR _test_no
	cmp	al, 100       # 对排序函数进行测试的总次数；提示：调试时可以将这里改小一点，如改为 2
	ja end_test_loop  # 通过判断两个无符号数之间的大小关系，如果 CF & ZF = 0，说明大于，则转移

	call	gen_random_list
	call	do_bubble_sort
	call	check_sort

	movzx	eax, BYTE PTR _check_flag                                 
	test	al, al
	jne	continue_test

	movzx	eax, BYTE PTR _test_no
	movzx	eax, al
	mov	DWORD PTR [esp+4], eax
	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_error_bar
	call	_printf
	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_error
	call	_puts
	jmp	end_test_loop

continue_test:
	movzx	eax, BYTE PTR _test_no
	add	eax, 1
	mov	BYTE PTR _test_no, al
	jmp	test_loop

end_test_loop:
	movzx	eax, BYTE PTR _check_flag
	test	al, al
	je	_end_main

	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_success_bar
	call	_printf

	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_success
	call	_puts

_end_main:                                     
	mov	eax, 0

	leave
	ret

问题分析

问题2

原题重现

请理解给定的do_swap汇编函数功能，写出等价的 C 语言函数代码；提示需注意数据类型，如长度、有无符号等（unsigned char ？无符号 1 Byte 长的变量？）

#Function-2# 实现交换两个指针各自指向的数据内容
do_swap:                          
	push	ebp
	mov	ebp, esp
	sub	esp, 4

	mov	eax, DWORD PTR [ebp+8]
	movzx	eax, BYTE PTR [eax]
	mov	BYTE PTR [ebp-1], al

	mov	eax, DWORD PTR [ebp+12]
	movzx	edx, BYTE PTR [eax]
	mov	eax, DWORD PTR [ebp+8]
	mov	BYTE PTR [eax], dl

	mov	eax, DWORD PTR [ebp+12]
	movzx	edx, BYTE PTR [ebp-1]
	mov	BYTE PTR [eax], dl

	leave
	ret

问题分析

其实在做这个作业的过程中读了很多很多汇编代码了，过了一开始的入门阶段之后再来读这段汇编代码其实不太难的

我往代码里加点注释，就能把这段代码读懂了

#Function-2# 实现交换两个指针各自指向的数据内容
do_swap:                          
	push	ebp
	mov	ebp, esp
	sub	esp, 4

    mov	eax, DWORD PTR [ebp+8]    ; 将第一个指针地址从函数参数中加载到EAX寄存器
    movzx	eax, BYTE PTR [eax]    ; 将指针所指的地址中的字节数据加载到EAX寄存器
    mov	BYTE PTR [ebp-1], al    ; 将EAX寄存器的低字节内容保存到新分配的栈空间中

    mov	eax, DWORD PTR [ebp+12]    ; 将第二个指针地址从函数参数中加载到EAX寄存器
    movzx	edx, BYTE PTR [eax]    ; 将指针所指的地址中的字节数据加载到EDX寄存器
    mov	eax, DWORD PTR [ebp+8]    ; 将第一个指针地址从函数参数中重新加载到EAX寄存器
    mov	BYTE PTR [eax], dl    ; 将EDX寄存器的低字节内容保存到EAX所指向的地址中

    mov	eax, DWORD PTR [ebp+12]    ; 将第二个指针地址从函数参数中重新加载到EAX寄存器
    movzx	edx, BYTE PTR [ebp-1]    ; 将新分配的栈空间中的低字节内容加载到EDX寄存器
    mov	BYTE PTR [eax], dl    ; 将EDX寄存器的低字节内容保存到EAX所指向的地址中

    leave    ; 恢复堆栈
    ret    ; 函数返回

其中要注意的就是这里的数据类型，转换为C语言代码之后是unsigned char，在汇编代码中是不带符号的数据传递，因此这边是一个无符号数据

其实反过来想，题目是一个字符串排序，ASCII码不可能是负值，因此使用无符号数就够了

等价的C语言代码如下

void do_swap(unsigned char *a, unsigned char *b) {
    unsigned char c = *a;  
    *a = *b;  
    *b = c;  
}

问题3

原题重现

请用汇编语言实现冒泡排序函数（需要有详尽的代码注释）；提示会调用到已给定的do_swap汇编函数

问题分析

这个题目真的写了好久好久，下面是一些笨人作为小白的一些简单分析

首先我们应该先知道普通的冒泡排序的原理以及用C语言如何实现：

冒泡排序原理

从第一个元素开始往后冒泡，遇到比自己小的就向前交换，直到最后

每次一个元素冒泡到最大处冒泡的长度就可以-1，冒剩余的N-1个泡即可

C语言代码

参考自上学期的数据结构笔记的代码（其实是懒得再写一遍了…）

void Bubble_Sort(ElementType A[], int N) {
    for (P = N - 1; P >= 0; P--) {
        flag = 0; //标志位，用来记录是否发生了交换
        for (i = 0; i < P; i++) { /* 一趟冒泡 */
            if (A[i] > A[i + 1]) {
                Swap(A[i], A[i + 1]);//调用交换子函数
                flag = 1; /* 标识发生了交换 */
            }
        }
        if (flag == 0) break; /* 全程无交换 */
    }
}

汇编代码编写分析

从C语言的代码就可以看到了，冒泡排序需要两个循环，一个外层循环和一个内层循环，然后传进来的参数有两个，一个是待排序的数组，另一个就是数组长度。在本题当中数组和数组长度作为全局变量在汇编代码最开始的时候就定义了，因此它们两个的地址还是很好找的，直接拿下来用就行（老师在这里还是很善良的，不然就要去读前面Function 1里面的代码去找生成的数组放在哪了）。

因此，在编写汇编代码的时候也是这样，写一个内层循环和一个外层循环分别实现两个循环的功能就行，在把 C语言的循环转换成汇编语言的时候，有几个注意点：1.计数器 2.循环跳转 3.参数传递

首先是对于循环体本身，我们需要用一个局部变量来存储计数器，内层循环和外层循环都是这样，这里将计数器存在局部变量区，需要操作的时候再调入寄存器，这样可以防止因为寄存器使用冲突（比如放入了eax寄存器，子函数也使用了eax寄存器）导致计数器丢失，同时这样也释放了寄存器，有了更多的寄存器可以使用。虽然本题寄存器够用，将计数器放入局部变量区反倒需要调用内存使得程序的局部性变差，同时调用内存也不如寄存器速度快，但是在其它题目就不一定了，如果出现寄存器不够用就必须得存入局部变量区了。（而且局部变量区有16字节，不用白不用嘛~）

#使用局部变量区存储计数器，可以避免在调用do_swap的过程中计数器的值被子函数修改
    mov     BYTE PTR [ebp-8], 0  #外层循环计数器,将其存在局部变量区
    movzx   ebx, BYTE PTR _char_list_len #数组长度存入ebx寄存器

在定位数组元素的时候使用相对寻址，写法是这样的：BYTE PTR _char_list[edi]

本题有一个细节：从示例我们可以看到是要将小写字母放在大写字母前面的，而小写字母的ASCII码是大于大写字母的，所以我们需要判断大小写，并将小写字母的数值变得比大写字母小。调试的时候注意看寄存器，字符存进去时存放的都是ASCII码，也就是说底层字符就是用ASCII码表示的，因此可以直接修改ASCII码，使得小写字母在比较大小的时候比大写字母小，这样就可以解决大小写判断问题。

汇编语言的if-else语句是使用跳转函数实现的，所以在这题里面就有一个很反人类的点了，连续两个字符都需要进行大小写判断，所以这个地方的跳转必须是一个一个按顺序写，我暂时不知道有没有更优的写法，反正我写的是很不优雅…

如果有更好的写法dd我：

#进行大小写检查，由于大写字母ASCII码从65开始，因此可以在比较的时候将小写字母-58将其接到大写字母前面使得其一定比大写字母小
    cmp     eax, 97 #小写字母ASCII起始值为97
    jae     transfer_a #如果是小写字母就让它-58
    cmp     edx, 97 #接着检查下一个字符是否为小写字符
    jae     transfer_b
    jmp     compare  

transfer_a: #要按顺序跳转才行
    sub     eax, 58
    cmp     edx, 97 #检查下一个字符是否为小写字符
    jae     transfer_b
    jmp     compare
    
transfer_b:
    sub     edx, 58 #如果是小写字母就让它-58

循环也是一样的，循环结束使用的是跳转指令进行的，因为这个题目中间因为比较有几次跳转，因此我们需要为循环跳转再写两个函数：内层循环：not_swap，外层循环：end_inner_loop

not_swap: 
    dec     BYTE PTR [ebp-4] #内层循环计数器-1
    jmp     inner_loop #回到内层循环，进行下一轮的比较

end_inner_loop:
    cmp     BYTE PTR [ebp-9], 1 #测试标志位，检查是否发生了交换
    jne     end_bubble_sort #如果发生了交换就跳入外层循环，否则说明数组已经有序，直接结束排序
    inc     BYTE PTR [ebp-8] #外层循环计数器+1，表示已经进行完一轮冒泡
    jmp     outer_loop #进行下一轮冒泡

接下来就是最重要的参数传递部分，首先先看看我的第四版代码：

mov     eax, DWORD PTR [ebp-12] #将左指针存入eax，即将前面的字符存入eax
  movzx   eax, BYTE PTR [eax]
  mov     edx, DWORD PTR [ebp-16] #将右指针存入edx，即将后面的字符存入edx
  movzx   edx, BYTE PTR [edx] 

  cmp     eax, edx #比较前后两个元素的值
  jbe     not_swap #如果前面的元素小于后面的元素值则不交换

  mov     eax, DWORD PTR [ebp-12] #把要交换的两个元素放入do_swap程序栈中准备供do_swap调用，传参操作
  mov     edx, DWORD PTR [ebp-16]
  mov     DWORD PTR [esp+8], edx
  mov     DWORD PTR [esp+4], eax 
  #mov     DWORD PTR [esp], OFFSET FLAT:do_swap #将do_swap函数地址移动到栈顶，准备调用
  call    do_swap #调用do_swap，交换前后两个元素
  mov     BYTE PTR [ebp-9], 1 #标志位设置为1，记录内层发生了交换

这个是ChatGPT写的，相当丑陋的代码，而且这个代码根本无法实现参数传递，但是我们注意看这段代码参数传递的方式，这段代码的参数传递使用MOV指令，通过ESP寄存器的偏移来传参的，这就需要查看_do_swap函数函数使用的参数在哪，同时我们也需要知道函数栈的结构：

函数栈结构图：

do_swap:                         
	push	ebp
	mov	ebp, esp
	sub	esp, 4

	mov	eax, DWORD PTR [ebp+8] #第一个参数
	movzx	eax, BYTE PTR [eax]
	mov	BYTE PTR [ebp-1], al

	mov	eax, DWORD PTR [ebp+12] #第二个参数
	movzx	edx, BYTE PTR [eax]
	mov	eax, DWORD PTR [ebp+8]
	mov	BYTE PTR [eax], dl

	mov	eax, DWORD PTR [ebp+12]
	movzx	edx, BYTE PTR [ebp-1]
	mov	BYTE PTR [eax], dl

	leave
	ret

可以看到do_swap函数的参数使用的是[ebp+8]和[ebp+12]的位置，因此我们需要把参数传到这两个位置上去

使用MOV而使用PUSH来传递参数的好处就是不会改变函数栈的栈顶位置（也就是ESP的位置），但是上面这段代码传的相当丑陋，苯小白现在也还没解决这个问题，希望懂的佬看到了dd我😢

所以我最终使用的是PUSH来传参，使用PUSH函数就不用管这个参数在子函数中该是当前的[esp+多少]了，而且这个_do_swap函数本身在一开始就初始化了函数栈，因此我们可以随便push，记得push之后要改一下ESP：

lea     eax, BYTE PTR _char_list[edi]  # 计算左指针地址，存入eax寄存器，准备压入函数栈
   push    eax
   inc     edi #edi+1索引到右指针
   lea     eax, BYTE PTR _char_list[edi]  # 计算右指针地址，存入eax寄存器，准备压入函数栈
   push    eax
   
   call    do_swap #调用do_swap，交换前后两个元素
   add     esp, 8 #往函数栈中压入了两个字符，esp栈寄存器+8，由于每次调用函数都会重新设置栈寄存器，所以在调用do_bubble_sort时会自动将esp还原

传递参数之前要使用LEA指令将需要交换的数组元素的地址放到寄存器当中才可以正确将指针传入！

整体代码实现

#Function-4# 冒泡排序函数
do_bubble_sort:
    push    ebp
    mov     ebp, esp
    sub     esp, 16

    ### ------------------------------冒泡排序正文----------------------------开始
    #选择从后往前冒泡
    #使用局部变量区存储计数器，可以避免在调用do_swap的过程中计数器的值被子函数修改
    mov     BYTE PTR [ebp-8], 0  #外层循环计数器,将其存在局部变量区
    movzx   ebx, BYTE PTR _char_list_len #数组长度存入ebx寄存器
outer_loop:
    mov     BYTE PTR [ebp-9], 0 #标志位，记录是否发生了交换
    mov     cl, BYTE PTR [ebp-8]#将外层循环计数器的值调入寄存器中,准备进行比较
    movzx   ecx, cl
    cmp     ecx, ebx #比较最后一个元素下标和循环计数器的值
    jae     end_bubble_sort #如果循环次数已经和数组下标-1相等（即已经排序到最后一个元素）则排序结束

    mov     BYTE PTR [ebp-4], bl #内层循环计数器
    dec     BYTE PTR [ebp-4] #内层循环计数器，初始值是数组长度-1，表示数组最后一个元素的下标,并且每一轮都-1
    
inner_loop: #内层循环，进行一次的冒泡（交换）
    movzx   esi, BYTE PTR [ebp-4]#将两个计数器装入通用寄存器
    movzx   edi, BYTE PTR [ebp-8]
    cmp     esi, edi #比较循环计数器与最后一个元素的下标值
    jbe     end_inner_loop #如果相等则表示一轮冒泡结束，跳转到退出内层循环
    
    mov     eax, esi #将内层循环计数器的值放入通用寄存器
    mov     edx, eax #将右指针存入edx，即将后面的字符存入edx，此时edx的值是数组的最后一个未排序元素的下标
    dec     eax      #此时eax存的是前一个字符的下标
    mov     edi, eax #edi此时的索引值就是左指针（前一个字符）     

    movzx   eax, BYTE PTR _char_list[edi] #将前一个字符装入eax
    movzx   edx, BYTE PTR _char_list[esi] #将后一个字符装入edx
    
    #一个更优的写法，先将字符存入局部变量区，需要时再移入寄存器，这样可以防止因寄存器被修改导致字符丢失，不过此处由于是连续使用字符所以也无需这样做
    #mov    DWORD PTR [ebp-10], eax #存储左指针地址
    #mov    DWORD PTR [ebp-12], edx #存储右指针地址
    
    #进行大小写检查，由于大写字母ASCII码从65开始，因此可以在比较的时候将小写字母-58将其接到大写字母前面使得其一定比大写字母小
    cmp     eax, 97 #小写字母ASCII起始值为97
    jae     transfer_a #如果是小写字母就让它-58
    cmp     edx, 97 #接着检查下一个字符是否为小写字符
    jae     transfer_b
    jmp     compare  

transfer_a: #要按顺序跳转才行
    sub     eax, 58
    cmp     edx, 97 #检查下一个字符是否为小写字符
    jae     transfer_b
    jmp     compare
    
transfer_b:
    sub     edx, 58 #如果是小写字母就让它-58
    
compare:
    cmp     edx, eax #比较前后两个元素的值（ASCII码）
    jae     not_swap #如果前面的元素小于后面的元素值则不交换
    
    lea     eax, BYTE PTR _char_list[edi]  # 计算左指针地址，存入eax寄存器，准备压入函数栈
    push    eax
    inc     edi #edi+1索引到右指针
    lea     eax, BYTE PTR _char_list[edi]  # 计算右指针地址，存入eax寄存器，准备压入函数栈
    push    eax
    
    call    do_swap #调用do_swap，交换前后两个元素
    add     esp, 8 #往函数栈中压入了两个字符，esp栈寄存器+8，由于每次调用函数都会重新设置栈寄存器，所以在调用do_bubble_sort时会自动将esp还原
    mov     BYTE PTR [ebp-9], 1 #标志位设置为1，记录内层发生了交换

not_swap:
    dec     BYTE PTR [ebp-4] #内层循环计数器-1
    jmp     inner_loop #回到内层循环，进行下一轮的比较

end_inner_loop:
    cmp     BYTE PTR [ebp-9], 1 #测试标志位，检查是否发生了交换
    jne     end_bubble_sort #如果发生了交换就跳入外层循环，否则说明数组已经有序，直接结束排序
    inc     BYTE PTR [ebp-8] #外层循环计数器+1，表示已经进行完一轮冒泡
    jmp     outer_loop #进行下一轮冒泡

    ### ------------------------------冒泡排序正文----------------------------结束

end_bubble_sort:
    leave
    ret

一些小声bb

大学以来第一次真正破防就是写这个汇编作业，真的写到了作业截止日期的最后一天才写完，中间整整写了六版，而且都是很不一样的，最后还是参考了别人代码的一些些内容（感谢Windy，他！是！我！的！神！）。不过在写这个作业的过程中真的学到了很多，读汇编代码顺了很多，而且也搞懂了函数栈和函数调用。难的作业，学到的也多，而且老师真的超级超级用心，超级超级体谅我们，是我上大学见过的最好的老师了！

完成代码

.arch i386
.intel_syntax noprefix

.data
.globl	_char_list
.globl	_char_list_len
.globl	_check_flag
.globl	_test_no

.data
_char_list_len:
	.byte	10
	.bss
	.align 4
_char_list:
	.space 11

.data
_check_flag:
	.byte	1
_test_no:
	.byte	1
	.section .rdata,"dr"
	.align 4

.data
hint_test_no:
	.ascii "\12-----------------------------test-%d\12\0"
hint_given_array:
	.ascii "The given array:  %s\12\0"
hint_sorted_array:
	.ascii "The sorted array: %s\12\0"

hint_test_error_bar:
	.ascii "\12--!--!--!--!--!--!--!--!--!--test-%d\12\12\0"
hint_test_error:
	.ascii "Sorry but try it again!\12\0"
	.align 4
hint_test_success_bar:
	.ascii "\12--*--*--*--*--*--*--*--*--*--passed!\12\12\0"
hint_test_success:
	.ascii "Well done!\12\0"

.text
.extern _printf
.extern _puts
.extern _time    # C标准库函数：获取系统时间；可以用于设定随机数种子
.extern _srand   # C标准库函数：用于设定随机数种子
.extern _rand    # C标准库函数：生成随机数

.globl	gen_random_list
.globl	do_swap
.globl	do_bubble_sort
.globl	check_sort
.globl	_main

#Function-1# 根据时间种子，随机生成由大小写英文字母构成的字符数组
gen_random_list:
	push	ebp
	mov	ebp, esp
	sub	esp, 12

	mov	BYTE PTR [ebp-1], 0
in_gen_random_list_loop:
	movzx	eax, BYTE PTR _char_list_len
	cmp	BYTE PTR [ebp-1], al
	jnb	end_gen_random_list

	mov	DWORD PTR [esp], 0
	call	_time
	mov	edx, eax
	movzx	eax, BYTE PTR [ebp-1]
	add	edx, eax
	movzx	eax, BYTE PTR _test_no
	movzx	eax, al
	add	eax, edx
	mov	DWORD PTR [esp], eax
	call	_srand

	call	_rand
	and	eax, 1
	test	eax, eax
	setne	al
	test	al, al
	je	in_gen_lower_letter

	call	_rand
	mov	ecx, eax
	mov	edx, 0x4EC4EC4F
	mov	eax, ecx
	imul	edx
	sar	edx, 3
	mov	eax, ecx
	sar	eax, 31  # 算数右移指令；其中，与逻辑右移shr 补 0 不同，sar 补位时，最高位保持不变
	sub	edx, eax
	mov	eax, edx
	imul	eax, eax, 26  # 有符号乘法指令，eax * 26 --所得乘积放入--> eax
	sub	ecx, eax
	mov	eax, ecx
	mov	edx, eax
	movzx	eax, BYTE PTR [ebp-1]
	add	edx, 65
	mov	BYTE PTR _char_list[eax], dl

	jmp	in_gen_upper_letter

in_gen_lower_letter:
	call	_rand
	mov	ecx, eax
	mov	edx, 0x4EC4EC4F
	mov	eax, ecx
	imul	edx
	sar	edx, 3   # 算数右移指令；其中，与逻辑右移shr 补 0 不同，sar 补位时，最高位保持不变
	mov	eax, ecx
	sar	eax, 31
	sub	edx, eax
	mov	eax, edx
	imul	eax, eax, 26
	sub	ecx, eax
	mov	eax, ecx
	mov	edx, eax
	movzx	eax, BYTE PTR [ebp-1]
	add	edx, 97
	mov	BYTE PTR _char_list[eax], dl

in_gen_upper_letter:
	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	mov	BYTE PTR [ebp-1], al
	jmp	in_gen_random_list_loop

end_gen_random_list:
	movzx	eax, BYTE PTR _char_list_len
	movzx	eax, al
	mov	BYTE PTR _char_list[eax], 0  # 字符数组末尾置零，方便按字符串进行一次性整体打印

	movzx	eax, BYTE PTR _test_no
	movzx	eax, al

	mov	DWORD PTR [esp+4], eax
	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_no
	call	_printf

	mov	DWORD PTR [esp+4], OFFSET FLAT:_char_list
	mov	DWORD PTR [esp], OFFSET FLAT:hint_given_array
	call	_printf

	leave
	ret

#Function-2# 实现交换两个指针各自指向的数据内容
do_swap:                          #*# 问题-2：请理解已给定的do_swap汇编函数功能，写出等价的 C 语言函数代码
                                  #          提示需注意数据类型，如长度、有无符号等
	push	ebp
	mov	ebp, esp
	sub	esp, 4

	mov	eax, DWORD PTR [ebp+8] 
	movzx	eax, BYTE PTR [eax]
	mov	BYTE PTR [ebp-1], al

	mov	eax, DWORD PTR [ebp+12]
	movzx	edx, BYTE PTR [eax]
	mov	eax, DWORD PTR [ebp+8]
	mov	BYTE PTR [eax], dl

	mov	eax, DWORD PTR [ebp+12]
	movzx	edx, BYTE PTR [ebp-1]
	mov	BYTE PTR [eax], dl

	leave
	ret

#Function-3# 对排序结果得正确性进行检查
check_sort:
	push	ebp
	mov	ebp, esp
	sub	esp, 12

	mov	DWORD PTR [esp+4], OFFSET FLAT:_char_list
	mov	DWORD PTR [esp], OFFSET FLAT:hint_sorted_array
	call	_printf

	mov	BYTE PTR [ebp-1], 0

in_check_loop:
	movzx	eax, BYTE PTR [ebp-1]
	movzx	edx, BYTE PTR _char_list_len
	movzx	edx, dl
	sub	edx, 1
	cmp	eax, edx
	jge	end_check_sort

	movzx	eax, BYTE PTR [ebp-1]
	movzx	edx, BYTE PTR _char_list[eax]
	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	dl, al
	jbe	in_error_check

	movzx	eax, BYTE PTR [ebp-1]
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	al, 96
	jbe	in_error_marked

	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	al, 90
	jbe	continue_in_check_loop

in_error_marked:
	mov	BYTE PTR _check_flag, 0
	jmp	end_check_sort

in_error_check:
	movzx	eax, BYTE PTR [ebp-1]
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	al, 90
	ja	continue_in_check_loop

	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	movzx	eax, BYTE PTR _char_list[eax]
	cmp	al, 96
	jbe	continue_in_check_loop

	mov	BYTE PTR _check_flag, 0
	jmp	end_check_sort

continue_in_check_loop:
	movzx	eax, BYTE PTR [ebp-1]
	add	eax, 1
	mov	BYTE PTR [ebp-1], al
	jmp	in_check_loop

end_check_sort:
	leave
	ret

#Function-4# 冒泡排序函数
do_bubble_sort:
    push    ebp
    mov     ebp, esp
    sub     esp, 16

    ### ------------------------------冒泡排序正文----------------------------开始
    #选择从后往前冒泡
    #使用局部变量区存储计数器，可以避免在调用do_swap的过程中计数器的值被子函数修改
    mov     BYTE PTR [ebp-8], 0  #外层循环计数器,将其存在局部变量区
    movzx   ebx, BYTE PTR _char_list_len #数组长度存入ebx寄存器
outer_loop:
    mov     BYTE PTR [ebp-9], 0 #标志位，记录是否发生了交换
    mov     cl, BYTE PTR [ebp-8]#将外层循环计数器的值调入寄存器中,准备进行比较
    movzx   ecx, cl
    cmp     ecx, ebx #比较最后一个元素下标和循环计数器的值
    jae     end_bubble_sort #如果循环次数已经和数组下标-1相等（即已经排序到最后一个元素）则排序结束

    mov     BYTE PTR [ebp-4], bl #内层循环计数器
    dec     BYTE PTR [ebp-4] #内层循环计数器，初始值是数组长度-1，表示数组最后一个元素的下标,并且每一轮都-1
    
inner_loop: #内层循环，进行一次的冒泡（交换）
    movzx   esi, BYTE PTR [ebp-4]#将两个计数器装入通用寄存器
    movzx   edi, BYTE PTR [ebp-8]
    cmp     esi, edi #比较循环计数器与最后一个元素的下标值
    jbe     end_inner_loop #如果相等则表示一轮冒泡结束，跳转到退出内层循环
    
    mov     eax, esi #将内层循环计数器的值放入通用寄存器
    mov     edx, eax #将右指针存入edx，即将后面的字符存入edx，此时edx的值是数组的最后一个未排序元素的下标
    dec     eax      #此时eax存的是前一个字符的下标
    mov     edi, eax #edi此时的索引值就是左指针（前一个字符）     

    movzx   eax, BYTE PTR _char_list[edi] #将前一个字符装入eax
    movzx   edx, BYTE PTR _char_list[esi] #将后一个字符装入edx
    
    #一个更优的写法，先将字符存入局部变量区，需要时再移入寄存器，这样可以防止因寄存器被修改导致字符丢失，不过此处由于是连续使用字符所以也无需这样做
    #mov    DWORD PTR [ebp-10], eax #存储左指针地址
    #mov    DWORD PTR [ebp-12], edx #存储右指针地址
    
    #进行大小写检查，由于大写字母ASCII码从65开始，因此可以在比较的时候将小写字母-58将其接到大写字母前面使得其一定比大写字母小
    cmp     eax, 97 #小写字母ASCII起始值为97
    jae     transfer_a #如果是小写字母就让它-58
    cmp     edx, 97 #接着检查下一个字符是否为小写字符
    jae     transfer_b
    jmp     compare  

transfer_a: #要按顺序跳转才行
    sub     eax, 58
    cmp     edx, 97 #检查下一个字符是否为小写字符
    jae     transfer_b
    jmp     compare
    
transfer_b:
    sub     edx, 58 #如果是小写字母就让它-58
    
compare:
    cmp     edx, eax #比较前后两个元素的值（ASCII码）
    jae     not_swap #如果前面的元素小于后面的元素值则不交换
    
    lea     eax, BYTE PTR _char_list[edi]  # 计算左指针地址，存入eax寄存器，准备压入函数栈
    push    eax
    inc     edi #edi+1索引到右指针
    lea     eax, BYTE PTR _char_list[edi]  # 计算右指针地址，存入eax寄存器，准备压入函数栈
    push    eax
    
    call    do_swap #调用do_swap，交换前后两个元素
    add     esp, 8 #往函数栈中压入了两个字符，esp栈寄存器+8，由于每次调用函数都会重新设置栈寄存器，所以在调用do_bubble_sort时会自动将esp还原
    mov     BYTE PTR [ebp-9], 1 #标志位设置为1，记录内层发生了交换

not_swap:
    dec     BYTE PTR [ebp-4] #内层循环计数器-1
    jmp     inner_loop #回到内层循环，进行下一轮的比较

end_inner_loop:
    cmp     BYTE PTR [ebp-9], 1 #测试标志位，检查是否发生了交换
    jne     end_bubble_sort #如果发生了交换就跳入外层循环，否则说明数组已经有序，直接结束排序
    inc     BYTE PTR [ebp-8] #外层循环计数器+1，表示已经进行完一轮冒泡
    jmp     outer_loop #进行下一轮冒泡

    ### ------------------------------冒泡排序正文----------------------------结束

end_bubble_sort:
    leave
    ret


#Function-5# 主函数 main
_main:
    mov %ebp, %esp #for correct debugging
	push	ebp
	mov	ebp, esp
	sub	esp, 8

test_loop:
	movzx	eax, BYTE PTR _test_no
	cmp	al, 100       # 对排序函数进行测试的总次数；提示：调试时可以将这里改小一点，如改为 2
	ja end_test_loop  # 通过判断两个无符号数之间的大小关系，如果 CF & ZF = 0，说明大于，则转移

	call	gen_random_list
	call	do_bubble_sort
	call	check_sort

	movzx	eax, BYTE PTR _check_flag                                 
	test	al, al
	jne	continue_test

	movzx	eax, BYTE PTR _test_no
	movzx	eax, al
	mov	DWORD PTR [esp+4], eax
	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_error_bar
	call	_printf
	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_error
	call	_puts
	jmp	end_test_loop

continue_test:
	movzx	eax, BYTE PTR _test_no
	add	eax, 1
	mov	BYTE PTR _test_no, al
	jmp	test_loop

end_test_loop:
	movzx	eax, BYTE PTR _check_flag
	test	al, al
	je	_end_main

	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_success_bar
	call	_printf

	mov	DWORD PTR [esp], OFFSET FLAT:hint_test_success
	call	_puts

_end_main:                                    
	mov	eax, 0

	leave
	ret