计算机系统作业
3.54
int decode2(int x, int y, int z)
{
int ans = z-y;
ans <<= 15;
ans >>= 15;
ans = ans ^ x;
ans = ans * (z - y);
return ans;
}3.55
4.45
// bubble sort by index
void bubble_sort(int *nums, int size)
{
int *i, *j;
for (i = nums; i < nums + size; ++i) {
for (j = nums; j <nums + (size - i - 1); ++j) {
if (*j > *(j + 1)) {
int tmp = *j;
*j = *(j + 1);
*(j + 1) = tmp;
}
}
}
}
## Y86冒泡排序完整程序（修复寄存器覆盖问题，栈管理循环次数）
# 函数功能：对int数组升序排序
# 函数参数：%edi = 数组首地址（nums），%esi = 数组长度（size）
# 调用约定：遵循Y86 callee-saved寄存器规则（保存%ebx/%edi/%esi）
bubble_sort:
# -------------------------- 1. 函数入口：建立栈帧 + 保存寄存器 --------------------------
pushl %ebp # 保存调用者的%ebp（栈帧基址）
movl %esp, %ebp # 初始化当前函数栈帧基址（%ebp固定）
pushl %ebx # 保存被调用者寄存器（Y86要求：%ebx/%edi/%esi需保护）
pushl %edi
pushl %esi
# -------------------------- 2. 参数加载与初始化 --------------------------
movl 8(%ebp), %edi # 加载第1个参数：nums数组首地址 → %edi
movl 12(%ebp), %esi # 加载第2个参数：数组长度size → %esi
subl $1, %esi # 外层循环总轮次 = size-1（最后1个元素无需比较）
movl %edi, %ebx # 外层指针i初始值 = nums → %ebx（对应C的i = nums）
# 外层循环：控制排序轮次（%esi = 剩余轮次，初始size-1，递减至0）
outer_loop:
cmpl $0, %esi # 检查外层剩余轮次：是否已完成所有轮次？
jle end_sort # 剩余轮次≤0 → 跳至排序结束
# 内层循环初始化：j指针 = nums，计算初始内层次数
movl %edi, %ecx # 内层指针j初始值 = nums → %ecx（对应C的j = nums）
movl %esi, %edx # 初始内层次数 = 当前外层轮次 - 1（每轮少1次比较）
subl $1, %edx
pushl %edx # 【栈操作1】压栈保存初始内层次数（避免被元素值覆盖）
jmp inner_loop_start # 跳至内层循环的“次数检查”步骤（避免重复代码）
# 内层循环：相邻元素比较与交换（%ecx = j指针，栈存储循环次数）
inner_loop:
# 读取当前元素*j和下一个元素*(j+1)（%edx可复用存元素值，次数在栈中）
movl (%ecx), %eax # %eax = *j（当前元素）
movl 4(%ecx), %edx # %edx = *(j+1)（下一个元素，int占4字节，偏移+4）
# 比较*j和*(j+1)，无需交换则跳至更新j指针
cmpl %edx, %eax # 比较：*j > *(j+1)？
jle no_swap # 若*j ≤ *(j+1) → 无需交换，跳至no_swap
# 交换逻辑：用栈暂存元素值（避免寄存器覆盖）
pushl %eax # 暂存*j到栈（栈顶：*j）
pushl %edx # 暂存*(j+1)到栈（栈顶：*(j+1)，下一层：*j）
popl %eax # 取出*(j+1) → %eax
popl %edx # 取出*j → %edx（此时%eax=*(j+1)，%edx=*j）
movl %eax, (%ecx) # 写回：*j = *(j+1)
movl %edx, 4(%ecx) # 写回：*(j+1) = *j
# -------------------------- 3. 内层循环更新：j指针 + 循环次数递减 --------------------------
no_swap:
addl $4, %ecx # j指针后移1个int（j++，偏移+4）
popl %edx # 【栈操作2】从栈取“当前剩余循环次数”（覆盖元素值）
subl $1, %edx # 循环次数递减1（此时%edx是正确次数，非元素值）
pushl %edx # 【栈操作3】将“递减后的次数”压回栈（供下一次循环用）
# -------------------------- 4. 内层循环条件检查：次数是否为0 --------------------------
inner_loop_start:
popl %edx # 【栈操作4】取栈中“当前剩余次数” → %edx（准备检查）
cmpl $0, %edx # 检查：剩余比较次数是否为0？
jle next_outer # 次数≤0 → 退出内层循环，跳至外层迭代
pushl %edx # 【栈操作5】将“未使用的次数”压回栈（供inner_loop复用）
jmp inner_loop # 次数≠0 → 进入下一次元素比较
# -------------------------- 5. 外层循环迭代：更新i指针 + 轮次递减 --------------------------
next_outer:
addl $4, %ebx # i指针后移1个int（i++，偏移+4）
subl $1, %esi # 外层剩余轮次递减1（下一轮比较次数更少）
jmp outer_loop # 进入下一轮外层循环
# -------------------------- 6. 函数结束：恢复寄存器 + 清理栈帧 --------------------------
end_sort:
popl %esi # 恢复被调用者寄存器（与push顺序相反：esi→edi→ebx）
popl %edi
popl %ebx
movl %ebp, %esp # 用%ebp恢复%esp（清理当前函数栈帧：局部变量+保存的寄存器）
popl %ebp # 恢复调用者的%ebp（还原上一层栈帧基址）
ret # 返回调用者（弹出栈中返回地址→程序计数器）
# -------------------------- 测试代码（可选，用于验证功能） --------------------------
# 需在Y86汇编器中与bubble_sort链接，初始化数组后调用排序
main:
pushl %ebp
movl %esp, %ebp
subl $20, %esp # 栈上分配20字节（存储5个int的数组：arr[5] = {5,3,8,2,1}）
# 初始化数组：arr[0]=5, arr[1]=3, arr[2]=8, arr[3]=2, arr[4]=1
movl $5, -20(%ebp)
movl $3, -16(%ebp)
movl $8, -12(%ebp)
movl $2, -8(%ebp)
movl $1, -4(%ebp)
# 调用bubble_sort：参数1=数组地址（-20(%ebp)），参数2=数组长度（5）
pushl $5 # 第二个参数：size=5（压栈顺序与参数声明相反）
leal -20(%ebp), %eax # 第一个参数：数组首地址→%eax
pushl %eax # 压栈第一个参数
call bubble_sort # 调用排序函数
addl $8, %esp # 清理函数调用压栈的2个参数（8字节）
# 此处可添加数组输出逻辑（需Y86 IO指令支持），验证排序结果
movl %ebp, %esp
popl %ebp
ret