网站LOGO
博客 | 棋の小站
页面加载中
2月21日
网站LOGO 博客 | 棋の小站
记录学习,心得,状态,生活。
菜单
  • 热评
    用户的头像
    首次访问
    上次留言
    累计留言
    我的等级
    我的角色
    打赏二维码
    打赏博主
    计组课设,使用四个寄存器、13个汇编指令实现一个排序器
    点击复制本页信息
    微信扫一扫
    文章二维码
    文章图片 文章标题
    创建时间
  • 一 言
    确认删除此评论么? 确认
  • 本弹窗介绍内容来自,本网站不对其中内容负责。
    按住ctrl可打开默认菜单

    计组课设,使用四个寄存器、13个汇编指令实现一个排序器

    · 原创 ·
    做做项目 · 汇编
    共 7012 字 · 约 9 分钟 · 332

    文章
    摘要

    这段文本描述了一个计算机组成原理课程设计,实现了输入任意个数并进行冒泡排序的功能。使用了汇编语言进行编程,涉及到寄存器的使用和内存操作。作者还讨论了汇编指令的具体实现,包括MOV、ADD、SUB等指令的用法。在排序算法方面,由于汇编指令的限制,对原有的排序算法进行了调整。最后,作者提供了汇编代码,并解释了如何将其转换为机器码并成功运行。
    本文仅为记录。

    计组课设做完了。

    实现的功能是使用输入单元输入任意个数,输入0结束输入,对这些数进行冒泡排序,然后输出。本机器提供4个寄存器R0、R1、R2、R3,其中R2被用作偏移地址寄存器,其他三个寄存器暂存其他变量。将这些数放在以A1为起始地址的连续内存单元中,9DH存储数组长度,9EH存储j的值,9FH存储i的值。这些功能要用可编程芯片8255、8259和机器码实现,伪代码使用汇编语言实现。

    本实验中提供的指令如下。

    本实验提供的指令本实验提供的指令
    • MOV指令用于将RS寄存器的值传到RD中;
    • ADD指令用于将RS和RD寄存器的值做相加运算,结果赋值给RD;
    • SUB指令用于将RS和RD寄存器的值做相减运算,结果赋值给RD;
    • AND指令用于将RS和RD寄存器的值做按位与运算,结果赋值给RD;
    • OR指令用于将RS和RD寄存器的值做按位或运算,结果赋值给RD;
    • RR指令为右环移指令,这里用不到;
    • INC指令为将RD的值加一后赋值给RD,即自增1;
    • LAD指令用于从内存中读取一个值,将值赋给RD;
    • STA指令用于将寄存器RS的值写入到内存中;
    • JMP指令为无条件跳转;
    • BZC指令为有条件跳转,当上一步运算结果为0或有进位或有借位而让FZ或FC等于1时跳转;
    • IN指令是输入指令;
    • OUT指令是输出指令;
    • LDI指令是将一个具体的值赋值给一个寄存器,这是唯一一个给寄存器赋立即数的指令;
    • HALT指令为停机指令。

    这里需要注意,MOV等指令只能在两个寄存器之间运算,这与我们熟知的汇编指令是不一致的。此外,这些指令有些是单字节的,有些是双字节的,翻译成机器码时要注意。

    然后我们来看一下冒泡排序。

    js 代码:
    function bubblesort(arr){
        var length = arr.length;
        for (var i = 0; i < length - 1; i++){
            for (var j = 0; j != length - i + 1; j++){
                if (arr[j] > arr[j+1]){
                    swap(arr[j], arr[j+1]);
                }
            }
        }
    }

    这里的排序不适合使用指令比较,因为这里没有CMP指令,只有减运算和跳转,因此我们需要将代码改一下。

    js 代码:
    function bubblesort(arr){
        var length = arr.length;
        for (var i = 1; i != length; i++){
            for (var j = 1; j != length - i + 1; j++){
                //a[1]是第一个数组元素
                if (arr[j] > arr[j+1]){
                    swap(arr[j], arr[j+1]);
                }
            }
        }
    }

    这里假设arr[1]是第一个元素。为什么要这样做呢?以外循环为例,在当时我们考虑如下:原算法中外循环条件为i<len-1,且i从0开始。假设数组长度为3,那么外循环应执行2次,执行顺序如下:

    1. 初始化i=0,执行判断:i<len-1。i的值为0,len的值为3,则表达式为0<2,符合条件;
    2. i++,再执行判断,这时表达式为1<2;符合条件;
    3. i++,再执行判断,这时表达式为2<2;不符合条件,循环结束,总共循环两次。

    然而这里的指令没有比较小于的功能,只有SUB(减)和BZC(跳转)结合使用才能实现判断的效果。打个比方,原算法的表达式有两种情况:

    1. 1<2。在指令中,假设R1的值为2,R2的值为1(大减小以排除减出负数影响FZ进而影响BZC的结果),结果为1,无借位,结果也不为0,那么FC和FZ都为0,BZC就不会跳转,这时这下面只需要继续执行内循环判断即可。
    2. 2<2。在指令中,假设R2的值为2,R2的值为2,那么结果显然是为0,BZC会执行,即外循环判断的结果是不符合条件。

    也就是说,如果i==len - 1,循环就会结束。这时i是从0开始的。我们做一个简单的移项,让i+1与len比较。此时i还是从0开始的,即i+1是以1开始的。那我们不妨将i+1的起始值设为1,并将i+1改为i。所以上方改进的代码中循环条件是i!=len。这里需要注意,由于i还作为内循环的判断条件,所以要考虑到它对于内循环执行次数的影响。我们先验证一下i的起始值改为1、循环结束条件改为i==len后执行次数是否正确,这里还是假设数组长度为3。第一次i的值为1,len为3,两者不相等,执行第一次,i++。然后i的值为2,仍然不相等,再执行第二次,i++。最后i的值为3,相等,循环结束,跳转至输出。

    在精简了外循环后,我们还需要判断内循环判断条件是否相等。原算法中外循环的判断是:j<len-i+1,其中j的起始值为0。假设数组是以从大到小的顺序排列的,那么第一轮排序应该执行两次交换,第二轮排序应该执行一次交换,我们先验证一下第一轮排序。在改了的算法中,j的起始值为0,i的值为1,len的值为3,结束条件为j==len+i-1,期望的交换次数为2。这里i的值为1,表达式中还有一个加一,这两个抵消了,那么第一轮排序的结束判断就是j==len。

    1. j的值为0,len的值为3,判断表达式为0==3,不成立,执行第一次交换。
    2. j的值为1,判断表达式为1==3,不成立,执行第二次交换。
    3. j的值为2,2==3不成立,执行第三次交换。

    出问题了。多一次交换。解决方法很简单,让j的起始值也为1。所以这就是为什么i的起始值和j的起始值都为1的原因。

    在搞懂了这部分之后,就是如何处理数组的地址,因为交换时需要用到j的值。第一个元素存于A1H中,而j的起始值为1,那如果让起始值为A0H的话,这两者相加,就可以取到第一个元素了。

    在解决这些问题之后,就可以将其转换成汇编代码了。由于汇编一次只能计算一个值,不像其他编程语言一样可以一次计算复合表达式,所以对于复合表达式,要按照运算符优先级逐个计算,还需要注意汇编指令会将计算结果赋值给RD中,应尽量不让计算影响第二次计算的值,即对寄存器的值做了篡改后不能再次计算。

    首先将其转换为输入。输入的格式为IN RD, P,其中P为端口号,这里使用00H以从IN单元读入数据。

    assembly 代码:
    LDI R2, A1H            ;设置存入内存的初始地址
    input:                ;输入数据开始
        IN R1, 00H        ;输入一个数据
        LDI R3, 00H        ;判断输入的数是否为0第一步
        OR R1, R3        ;判断输入的数是否为0第二步
        BZC initiandlen        ;若结果为0则跳转至排序
        STA [R2], R1        ;将数据存入R2所指的地址中
        INC R2            ;R2+1,以便于下次存储
        JMP input        ;重新输入数据
                    ;输入数据结束

    这里设置存入内存的初始地址为A1H,这样存入数据后对R2自增一后就可以存入下一段内存单元了。然后从IN单元读入一个数据并赋值给R1。下步就是判断输入的数是否为0,首先给R3一个立即数00H,然后让R1和00H做按位或运算,因为任何数与0做或运算都是原数,因此若结果为00H则代表输入的数为0。若输入的数为0则跳转至初始化i和len(init i and len),不再执行输入,否则将数存入内存中,再执行下一步输入。

    接着就是执行排序。这里需要先弄清楚排序的顺序,排序内涉及到的计算有:

    • var i = 1;
    • var j = 1;
    • 外循环判断;
    • 内循环判断;
    • 是否交换判断;
    • 交换;
    • i++;
    • j++。

    它们之间的执行顺序如下:

    1. 初始化数组长度,i,以便执行第一次循环;
    2. 外循环判断,若符合执行条件则继续,否则跳转至输出,代表排序结束;
    3. 内循环判断,若符合执行条件则继续,否则跳转至5;
    4. 交换条件判断,若前一个数大于后一个数则交换这两个数,否则跳转至6;
    5. i++,执行后跳转至2;
    6. j++,执行后跳转至3。

    弄懂了循环的执行顺序,也弄懂了i、j、len的关系以及如何计算比较,就可以写出如下的汇编代码。从初始化数组长度和i开始。

    assembly 代码:
    initiandlen:
                    ;数组长度保存,初始化i的值开始
        MOV R3, R2        ;暂存输入时R2的值,便于下面计算数组长度
        LDI R1, A1H        ;R2的值减去偏移地址初始值就是数组长度
        SUB R3, R1        ;相减得到数组长度
        LDI R2, 9DH        ;9DH存储数组长度
        STA [R2], R3        ;将数组长度写入内存
        LDI R2, 9FH        ;9FH存储i的值,i为外层循环变量
        LDI R3, 01H        ;i的初始值为1
        STA [R2], R3        ;将i的值写入内存
                    ;保存数组长度,初始化i结束

    这里因为初始化数组长度和i只有一次,因此写在这里。

    首先让R3寄存器保存输入时R2保留的最后值,然后减去初始地址就是数组长度的值。然后就是将数组长度和i的值写入内存。

    接下来就是外循环判断。

    assembly 代码:
                    ;外层循环判断开始
    outerjudgement:
        LDI R2, 9FH        ;9FH存储i的值
        LAD R0, [R2]        ;此时R0的值为i
        LDI R2, 9DH        ;9DH存储数组长度
        LAD R1, [R2]        ;此时R1的值为数组长度
        SUB R1, R0        ;判断,这里是大减小,防止借位影响标志位
        BZC output        ;外循环结束,开始输出
        JMP initj        ;否则跳转至初始化j,代表下一步内循环开始
                    ;外循环判断结束

    首先从对应内存中读入i、len的值,然后进行相减,若相减为0代表跳出循环,否则执行内循环。由于内循环第一步是初始化j,所以要跳转到那里。

    接下来是内循环初始化,这一部分很简单,将j的初始值1写入内存9EH即可。

    assembly 代码:
    initj:
        LDI R2, 9EH            ;9EH存储j的值
        LDI R3, 01H            ;j的初始值为1
        STA [R2], R3        ;写入内存    
                            ;初始化j结束

    然后是内循环判断,这里要计算的表达式是len+1-j-i==0。

    assembly 代码:
                            ;内循环判断开始
    innerjudgement:
        LDI R2, 9F            ;9FH存储i的值
        LAD R0, [R2]        ;R0的值就是i
        LDI R2, 9E            ;9EH存储j的值
        LAD R1, [R2]        ;R1的值就是j
        LDI R2, 9DH            ;9DH存储数组长度
        LAD R3, [R2]        ;R3的值就是数组长度
        INC R3                ;计算len+1
        SUB R3, R1            ;计算(len+1)-i
        SUB R3, R0            ;计算(len+1-j)-i
        BZC iplusplus        ;若结果为0代表内循环结束,跳转至i++
        JMP swapjudgement    ;跳转至是否交换判断
                            ;内循环判断结束

    首先先从内存中加载变量,i存在R0中,j存在R1中,len存在R3中,再作想减运算即可。

    然后是交换判断和交换。交换判断和之前一样,这里不再赘述。交换的操作不需要中间变量,使用两个寄存器存a[j]和a[j+1]的值,然后分别存入对方的地址即可。

    assembly 代码:
                            ;判断是否交换开始,条件是两个数大小
    swapjudgement:
    ;因为第一个数存于A1H,且j的初始值为1,因此初始地址是A0H
        LDI R3, A0H            ;R3是常数
        LDI R2, 9EH            ;9EH存j
        LAD R2, [R2]        ;R2=j
        ADD R2, R3            ;获取a[j]的地址,运算后R2直接就是地址
        LAD R0, [R2]        ;R0的值为a[j]
        INC R2                ;R2此时存储的为a[j+1]
        LAD R1, [R2]        ;R1的值为a[j+1]
    ;下一步计算a[j]-a[j+1],若前面等于后面结果为0,会跳转
    ;若前面小于后面,由于计算结果为负数,会借位,也会跳转
    ;跳转代表不执行交换程序
        SUB R0, R1            
        BZC jplusplus        ;跳转至j++,不执行交换
                            ;判断是否交换结束
    
    swap:
        LDI R3, A0H
        LDI R2, 9EH
        LAD R2, [R2]        ;R2的值为j
        ADD R2, R3            ;运算后R2的值为a[j]的地址
        LAD R0, [R2]        ;R0的值为a[j]
        MOV R3, R2            ;R3暂存a[j]的地址
        INC R2                ;R2此时为a[j+1]的地址
        LAD R1, [R2]        ;R1的值为a[j+1]
    ;下一步,R0的值是a[j],R2的值是a[j+1]的地址,所以可以写入
        STA [R2], R0
        MOV R2, R3            ;取回a[j]的地址
        STA [R2], R1        ;R1的值是a[j+1],R2为a[j]的地址
        JMP jplusplus        ;交换完成,跳转至j++
                            ;交换结束

    这里需要用R3暂存一下a[j]的地址。R0存a[j]的值,R1存a[j+1]的值,R2先存a[j+1]的地址,然后将R0的值存入,再将R3的值赋值给R2,最后将R1的值存入。这里没有初始化R2的地址或从某处读入是因为在交换判断中以及计算完了a[j]的地址。

    接着就是i++和j++,它们只需要先从对应内存中读入,然后再自增,最后再写入即可。

    最后的部分就是输出了,这里使用A1H为初始化地址,然后每次读入一个数,并判断这个数是否为0,若为0则结束输出。由于刚启动机器时内存的值是随机的,因此向机器装入指令时要将A1H为开头的内存单元全部赋值为0。

    assembly 代码:
    output:
        LDI R2, A1H            ;初始地址
        LDI R3, 00H            ;判断是否为0,用或运算
    
                            ;循环输出开始
    outputloop:
        LAD R1, [R2]        ;获取a[j]的值
        OR R1, R3            ;判断是否为0
        BZC end
        OUT R1, 40H            ;输出
        INC R2                ;地址+1,变成下一个元素的地址
        JMP outputloop        ;跳转至下一步输出
                            ;输出循环结束
    end:HALT

    编写完汇编代码后就是转换成机器码,机器码的各个位置在上方图片中已经给出。这里的指令分为两种:单字节指令和双字节指令。

    如MOV,它的语法是MOV RD, RS,翻译成机器码时,前四位为操作码,即0100,即4。后面两位是RS,最后两位为RD。其中R0到R3,分别用00、01、10、11表示。如MOV R3, R2,R2是RS,为10;R3是RD,为11,再加上操作码,二进制数为01001011,即4BH。

    双字节指令则需要将两个字节分别写在两个内存中。需要注意,在向内存中写入数字时,需要避免覆盖掉指令,所以这里将数据存在A1H开头。

    最后程序也是成功运行了,这里有一个视频和三个图片,这三张图分别是刚开始、第一次排序前、完整排序后9DH和AAH的内存数,这里输入的三个数依次是0F、07、03。

    内存数情况内存数情况

    完整运行视频:

    声明:本文由 (博主)原创,依据 CC-BY-NC-SA 4.0 许可协议 授权,转载请注明出处。

    还没有人喜爱这篇文章呢

    现在已有

    6

    条评论
    发一条!
    1. 头像
      云晓晨CatchYun
      • 等级:Lv.5
      • 角色:首页 · 好友
      • 在线:本月

      汇编,真的好难

      · · · 山东-济南
      1. 头像

        没事,只在学校学,以后碰都不碰。

        · · · 河北-秦皇岛
    2. 头像
      网安冷墨寒
      • 等级:Lv.3
      • 角色:技术 · 好友
      • 在线:三月内

      汇编这玩意太底层了太抽象烧脑了 学过一次汇编 这辈子都不想接触汇编开发

      · · · 海外
      1. 头像

        计算机要学这玩意 😅 我想学后端啊可学校压根不教

        · · · 河北-石家庄
    3. 头像
      obaby
      • 等级:Lv.4
      • 角色:综合 · 好友
      • 在线:本月

      现在还学汇编呐?

      · · · 山东-青岛
      1. 头像
        obaby

        是的,这学期学的。

        · · · 河北-秦皇岛
    博客logo 博客 | 棋の小站 记录学习,心得,状态,生活。
    ICP 冀ICP备2023007665号

    🕛

    本站已运行 299 天 11 小时 1 分

    🌳

    建站:Typecho 主题:MyLife

    👁️

    今日访问量:1592 昨日访问量:1607
    棋の小站 © 2024.
    网站logo

    博客 | 棋の小站 记录学习,心得,状态,生活。
     
     
     
     
    壁纸