本帖最后由 niuniu 于 2015-6-9 03:26 编辑
前言
首先，本人非常承认用汇编语言实现二叉堆是很白痴的做法，也是非常吃力不讨好的做法。不过貌似俺自己觉得接近了发烧友的程度了，所以有时发烧，这次写了几个汇编程序，包括二叉堆、快速排序、计数排序。然后就告一段落了，因为实在有多余觉得，不过有兴趣的同学可以来讨论一下呢，我是非常欢迎的。
目录 第一章 什么是二叉堆4 1.1 二叉堆的结构和存储4 1.2 二叉堆的操作4 第二章 关键汇编指令5 2.1 数据传送5 2.1.1 MOV5 2.1.2 LDR5 2.1.3 STR5 2.2 算数和逻辑运算6 2.2.1 ADD6 2.2.2 LSL6 2.3 跳转6 2.3.1 B6 2.3.2 BL7 第三章 汇编与C语言相互调用7 3.1 C语言调用汇编7 3.1.1 汇编子程序的返回7 3.1.2 汇编子程序的参数8 3.2 汇编调用C语言8 第四章 汇编实现二叉堆9 4.1、二叉堆最大化 - ASM_BiHeap_Maxify9 4.1.1 二叉堆最大化的作用9 4.1.2 二叉堆最大化的伪代码9 4.1.3 二叉堆最大化C语言原形和解释10 4.1.4 二叉堆最大化汇编语言描述10 4.2、二叉堆建立 - ASM_BiHeap_Build12 4.2.1 二叉堆建立的作用12 4.2.2 二叉堆建立的伪代码12 4.2.3 二叉堆建立的C语言原形和解释12 4.2.4 二叉堆建立的汇编语言描述13 4.3、二叉堆排序 - ASM_BiHeap_Sort13 4.3.1 二叉堆排序的作用13 4.3.2 二叉堆排序的伪代码13 4.3.3 二叉堆最大化的C语言原形和解释14 4.3.4 二叉堆最大化的汇编语言描述14 4.4、二叉堆键值增加 - ASM_BiHeap_KeyInc15 4.4.1 二叉堆键值增加的作用15 4.4.2 二叉堆键值增加的伪代码15 4.4.3 二叉堆键值增加的C语言原形和解释16 4.4.4 二叉堆键值增加的汇编语言描述16 4.5、二叉堆元素插入 - ASM_BiHeap_Insert17 4.5.1 二叉堆元素插入的作用17 4.5.2 二叉堆元素插入的伪代码17 4.5.3 二叉堆元素插入的C语言原形和解释17 4.5.4 二叉堆元素插入的汇编语言描述18 4.6、二叉堆最大元素 - ASM_BiHeap_Maximum18 4.6.1 二叉堆最大元素的作用18 4.6.2 二叉堆最大元素的伪代码18 4.6.3 二叉堆最大元素的C语言原形和解释19 4.6.4 二叉堆最大元素的汇编语言描述19 4.7、二叉堆出队最大元素 - ASM_BiHeap_ExtraMax19 4.7.1 二叉堆出队最大元素的作用19 4.7.2 二叉堆出队最大元素的伪代码19 4.7.3 二叉堆出队最大元素的C语言原形和解释20 4.7.4 二叉堆出队最大元素的汇编语言描述20 第五章 测试21 5.1 汇编文件的包装21 5.2 C语言头文件22 5.3 测试23 5.4 测试结果24 附录24 参考文献24
第一章 什么是二叉堆 数据结构方面的知识，可以参考有关数据结构的书，我这里参考的是《算法导论》第二版，大家有兴趣的话也可以参考一下。这一章介绍的是二叉堆。 1.1 二叉堆的结构和存储 有很多数据结构，从链表到树到图，二叉堆算是树的一种吧，这里我们讨论的是最大堆，需要借用《算法导论》的原文来说明什么是二叉堆。先看图： 
左图 二叉堆的结构 右图 二叉堆的存储。 我们先看看结构，是层次型的。处在上层的节点的值大于下面节点的值，比如1（16）大于2（14）和3（10），这样的堆我们称为最大堆。 存储的话，编号为1点节点存储在第1个位置，编号为2的节点存储在第2个位置，以此类推。属于顺序存储。 我们存储在计算机上的二叉堆是类似于C语言的数组，并且本人编程实现时（C语言和汇编语言）是将第0号位置用于存储二叉堆的大小，即存储的是二叉堆有多少个元素。比如上面的第0号位置存储的是10，因为有10个元素。 了解了二叉堆的结构和存储，我们来看一下二叉堆支持什么操作。 1.2 二叉堆的操作二叉堆这种数据结构需要支持的操作分别有： 1、二叉堆最大化 - ASM_BiHeap_Maxify 2、二叉堆建立 - ASM_BiHeap_Build 3、二叉堆排序 - ASM_BiHeap_Sort 4、二叉堆键值增加 - ASM_BiHeap_KeyInc 5、二叉堆元素插入 - ASM_BiHeap_Insert 6、二叉堆最大元素 - ASM_BiHeap_Maximum 7、二叉堆出队最大元素 - ASM_BiHeap_ExtraMax 对应的这些操作在具体实现的时候会具体说明，当然，我们使用的是Cortex-M3汇编语言实现的。 需要注意的是，我们是用C语言调用这些操作的。也就是说源代码用汇编写，但是留出C语言接口，让C语言调用这些函数，这里我们初步了解一下，具体实现下面再做介绍。 接下来因为是使用汇编语言，所以也大概介绍一下关键的汇编指令。
第二章 关键汇编指令 汇编语言可能大家不是很熟悉，不过本人的话，从大二第二学期到大四第一学期，上课的话，每个学期都有涉及汇编指令，汇编程序。具体是从微机原理 -> 单片机原理 -> DSP原理 -> 嵌入式系统，呵呵，接触了两年多的会汇编，也该有点感觉了吧。这章介绍一点汇编指令，具体是参考《Cortex M3权威指南》。有一点要注意的是，对于汇编语言来说，在分号（;）后面是注释，类似于C语言的行注释（//）。 2.1 数据传送 这里的数据传送包括寄存器与寄存器之间的数据传送和寄存器与存储器之间的数据传送，介绍三个指令MOV，LDR，STR。 2.1.1 MOV 可以说最经典的汇编指令就是MOV了，因为貌似连助记符都没有变过，在众多的微处理器中都是采用助记符MOV。下面举个例子： MOV R0, R1 ;将R1寄存器的值复制到R0 相当简单的汇编指令，看注释就知道是什么意思了（分号后面的内容是注释）。 2.1.2 LDR 这个算数据加载吧，跟存储器相关的数据传送。本人理解为LoaD Register，大写字母组成缩写LDR，就是将存储器ROM或者RAM的数据传送到寄存器，举个例子： LDR R0, [R1] ;相当于C语言的R0 = *(unsigned int *)R1; 就是把R1当成地址，将R1指向的那个地址对应的数据传送到R0。需要引起注意的是，这个指令一般是操作RAM或者ROM数据。 2.1.3 STR 这个算数据存储吧，也是跟存储器相关的数据传送，只不过方向跟LDR相反。本人理解为STore Register，大写字母组成缩写STR，就是将寄存器的数据存储到RAM或者ROM里面（现在的ROM很多都支持在线编程，比如Flash）。举个例子： STR R0, [R1] ;相当于C语言的*(unsigned int *)R1 = R0; 就是把R1当成地址，将R0的内容存储到R1所指向的那个地址的存储器上。同样需要引起注意的是，这个指令一般也是操作RAM或者ROM数据。
2.2 算数和逻辑运算 算数包括基本的加减乘除，逻辑运算是与或非位移等，这里介绍两个最简单的ADD和LSL。其他指令类似。 2.2.1 ADD 加法指令，实现两个数据相加，结果存储到寄存器中。对应的还有减法指令SUB，乘法指令MUL，除法指令DIV。例子： ADD R0, R1 ;相当于C语言的R0 = R0 + R1或者R0 += R1 实现将R0 + R1两个值相加，结果放在R0。
2.2.2 LSL 逻辑左移指令，实现数据的逻辑左移。本人的理解为Logic Shift Left，大写字母对应的缩写为LSL。对应的有逻辑右移LSR，算数右移ASR等，这里只介绍LSL，例子： LSL R0, #2 ;相当于C语言的R0 = R0 << 2 或者R0 <<= 2; 实现将R0左移两位，结果存放在R0，当然一般情况下会与LDR配合使用，可能稍微有一点点复杂了，例子： LDR R0, [R1, R2, LSL #2] ;相当于C语言R0 = *(unsigned int *)(R1 + ( R2 << 2 ) ); 将R1与R2左移两位的值相加，作为地址，取该地址的数据传送到R0。 2.3 跳转 跳转实现与PC相关的操作，改变程序的流程，这里介绍到是B，BL。 2.3.1 B 这个指令的助记符就一个字母B，Branch，分支的意思，就是程序有两个方向可以执行，选择其中一个分支。例子： B ASM_Loop ;跳转到ASM_Loop那里，ASM_Loop是一个标号 也就是程序的跳转，并且是无条件跳转，对应的有条件跳转，再举个条件跳转到例子，对应的指令是BEQ，本人理解Branch EQual，大写字母对应的缩写为BEQ。 BEQ ASM_Loop ;在执行该指令前，一般执行CMP比较两个数据 如果上一次比较两个数据相等，就跳转到ASM_Loop那里，如果不相等，不跳转，也就是这条指令执行完后，程序流程没有改变，依然是顺序执行。跳转与不跳转对应的是两个分支，也就应验了Branch是分支的意思了。 2.3.2 BL 这个是Branch and Link，其中的Branch与上个指令的Branch是一样的，分支，但是多了一个Link。意思是跳转前，保存了PC+4到LR寄存器。LR是Link Register，其中LR的L与BL的L是同个意思，Link。 多了这一步保存PC+4到LR的作用是可以实现程序返回，相当于C语言的子程序返回，比如我们有个C语言函数func，那么函数调用func()操作，在func函数执行完后可以返回调用该函数的程序那里继续执行，这就是BL发挥了作用。例子： BL ASM_My_Func ;相当于C语言的ASM_My_Func()，函数调用，调用完会返回。 其中ASM_My_Func是一个汇编标号，或者是C语言函数，根本上来说就是一个地址。
介绍了这些基本的指令，当然是远远不够的，还是要看看《Cortex M3权威指南》才能有更深入的了解。有兴趣的同学可以阅读这个资料。接下来介绍汇编语言与C语言的混合编程。
第三章 汇编与C语言相互调用 一般情况下我们都是用C语言编程的，但是也有不得不用到汇编的时候，就出现了C语言程序调用汇编子程序的问题。然而我们这里也会再介绍一下，相反的过程，就是汇编程序调用C语言子程序。 3.1 C语言调用汇编 模仿C语言的函数，将汇编程序写成类似于C语言的函数，也就是需要返回，继续执行前面的程序。并且有时候还需要带有参数，带有返回值，与C语言交互。下面一一介绍。 3.1.1 汇编子程序的返回 指令B和BL都能实现跳转，其中BL保存了下一条指令地址（PC+4）到LR，所以我们根据LR可以返回，返回操作指令具体是BX LR。指令将LR值赋给PC，实现程序的返回，看下面的例子： ASM_Func MOV R0, R1 BX LR ASM_Func_End 这就是一个汇编子程序了，只有两条指令。第一条指令将R1复制到R0，第二条指令就是实现子程序的返回了。想要在C语言中调用这个汇编子程序，还需要做一些工作。 1、将标号ASM_Func声明为外部的 2、C语言的头文件声明ASM_Func函数 3、C语言的源文件调用ASM_Func函数 具体怎么做分别如下： 1、在汇编文件中添加 EXPORT ASM_Func 2、C语言头文件添加 void ASM_Func(void); 3、C语言源文件添加 ASM_Func(); （实现程序调用） 这样做就可以了，当然还有其他一些小工作，比如汇编文件末尾要有END，要声明汇编文件的段啊什么的，具体后面介绍。上面的程序是没有参数的，也就是C语言没有传递参数给汇编子程序，汇编子程序也没有返回参数给函数调用者。下面看看C语言怎么传递参数给汇编子程序，也就是准备函数间的通信啦。 3.1.2 汇编子程序的参数 这一小节需要参考的是ATPCS，是ARM官方资料，讲的是汇编与C语言之间参数的传递，我这里只是简单介绍。 首先传进汇编子程序的参数，按照C语言函数调用是参数从左到右分别放在R0，R1，R2，R3，再到栈，如果有这么多参数的话，当然如果没有这么多参数，比如只有两个参数，就分别放在R0，R1了，以此类推。 然后是返回给C语言的返回值，有返回值的话放在R0，没有的话就不管R0是什么值了，因为C语言并不会用到。下面举个简单的例子： ASM_Add ADD R0, R1 BX LR ASM_Add_End 这个函数实现两个数相加，返回相加的结果，类似于C语言的函数： Int ASM_Add(int a, int b) { Return a + b; } 也就是汇编函数和C语言函数实现的是同样的功能，只不过用不同编程语言实现而已。跟上面介绍的没有参数的函数一样，也是要做一些工作C语言才能顺利调用这个函数的，老样子列出来： 1、将标号ASM_Add声明为外部的 2、C语言的头文件声明ASM_Add函数 3、C语言的源文件调用ASM_Add函数 具体怎么做分别如下： 1、在汇编文件中添加 EXPORT ASM_Add 2、C语言头文件添加 void ASM_Add(int a, int b); 3、C语言源文件添加 ASM_Func(3, 2); 这样的话我们就可以实现在C语言中灵活的调用汇编子程序了，接下来是相反的过程，汇编程序调用C语言子程序。 3.2 汇编调用C语言 如果我们用汇编实现类似于C语言的malloc函数，那真的是更加的吃力不讨好了，所以有时候我们也可以在汇编中调用已有的C语言函数，方便我们的程序开发。下面也通过一个例子介绍： 汇编语言调用一个C语言函数func()，比如func()函数是这样子的 Int func(int a, int b) { Return a + b; } 那么汇编语言调用时的参数从R0，R1，R2，R3到栈传递，返回值也是在R0取。调用实例如下： MOV R1, #2 MOV R2, #3 BL Func ;调用C语言函数 ... ;这时候R0已经是5了 当然，为了让汇编程序能知道Func标号，需要在文件前面添加IMPORT Func才能成功编译链接。
可以看到汇编语言和C语言编程也是比较方便等，有了上面这些基础知识，下面我们开始介绍具体怎么用汇编语言实现二叉堆了，测试程序的话用C语言编写，因为我们重点是实现汇编子程序而不是整个工程。 第四章 汇编实现二叉堆 我们实现的几个接口函数在第一章讲过，函数原形也是在第一章就给出了，这一章是具体实现了。这里分别给出操作的作用，然后给出伪代码，再给出C语言的函数原形和解释，最后给出Cortex-M3的汇编语言描述。再次说明，本人参考的是《算法导论》第二版，所以伪代码是来自算法导论的。 4.1、二叉堆最大化 - ASM_BiHeap_Maxify4.1.1 二叉堆最大化的作用 二叉堆最大化是一个子程序，被其他二叉堆操作调用。其作用是保持二叉堆的性质，即父节点的值大于子节点的值，然后递归下去。 4.1.2 二叉堆最大化的伪代码 需要注意的是这个函数是递归的，也就是第10行调用的函数就是本函数，具体看截图： 
4.1.3 二叉堆最大化C语言原形和解释 C语言原形：void ASM_BiHeap_Maxify( uint32_t *BiHeap, uint32_t i ); 其中BiHeap是指向二叉堆的指针，也就是二叉堆的首地址，我们这里是一个数组的首地址，i是二叉堆元素的位置，该操作实现将二叉堆中以i为根的二叉堆保持二叉堆的性质（父节点的值大于子节点的值）。 再次说明，二叉堆的大小（二叉堆元素的个数）是存储在BiHeap数组的第0个位置，也就是heap-size[BiHeap]相当于C语言的BiHeap[0]。 伪代码的意思是： 1、找到第i个节点的值，比较其与左右子节点的值的大小 2、获取最大值的位置存放在largest 3、比较largest与i 不同：交换largest与i对应位置的元素值，递归调用本函数最大化largest 相同：不需要操作，退出 这样就实现而二叉堆的最大化，还不明白的同学请网上找资料，我们这里的重点是用汇编语言实现上面的伪代码。 4.1.4 二叉堆最大化汇编语言描述 汇编语言也是根据伪代码编写出来的，所以先理解伪代码才对，具体代码如下： ;***************************** ******************************* ; 函数名 : ASM_BiHeap_Maxify ; 描述 : 二叉堆最大化 ; 输入 : R0 --- 二叉堆首地址 ; R1 --- 二叉堆父节点偏移 ; 输出 : 无 ; 寄存器 : 使用R1 ~ R8 ; 调用 : 内部调用 ;***************************** ******************************* ASM_BiHeap_Maxify PUSH {LR}
MOV R2, R1 ;R1为父节点偏移 ADD R2, R2 ;R2为左孩子偏移 ADD R3, R2, #1 ;R3为右孩子偏移 MOV R4, R1 ;R4为最大节偏移 LDR R5, [R0, R1, LSL #2] ;R5为最大节点值 LDR R6, [R0] ;R6为二叉堆大小
CMP R2, R6 ;判断是否有左孩子 BGT AMS_BiHeap_Maxify_Exit ;没有左孩子, 退出
LDR R7, [R0, R2, LSL #2] ;R7为左孩子节点 CMP R7, R5 ;比较节点大小 ITT GT ;如果违反最大堆规则 MOVGT R4, R2 ;左孩子值大于父节点值, 更新R4 MOVGT R5, R7 ;更新最大值R5
CMP R3, R6 ;判断是否有右孩子 BGT ASM_BiHeap_Maxify_Judge ;没有右孩子, 退出
LDR R7, [R0, R3, LSL #2] ;R7为右孩子节点 CMP R7, R5 ;比较节点大小 IT GT ;如果违反最大堆规则 MOVGT R4, R3 ;右孩子值大于父节点值, 更新R4 MOVGT R5, R7 ;更新最大值R5
ASM_BiHeap_Maxify_Judge CMP R1, R4 ;如果父节是, 不违反二叉堆规则 BEQ AMS_BiHeap_Maxify_Exit ;退出
ASM_BiHeap_Maxify_Exchange LDR R7, [R0, R1, LSL #2] ;取父节点值 STR R5, [R0, R1, LSL #2] ;交换 STR R7, [R0, R4, LSL #2] ;交换
MOV R1, R4 ;R1作为父节点, 递归二叉堆最大化 BL ASM_BiHeap_Maxify ;递归
AMS_BiHeap_Maxify_Exit POP {PC} ;退出 ASM_BiHeap_Maxify_End
本人非常承认伪代码确实也有点长，比起C语言编写的函数，实在是吃力不讨好，连本人自己看着注释都有点觉得难懂，不过如果想看懂汇编语言的话先要非常清楚的知道几个寄存器存放的是什么，再次罗列出来： ;R1为父节点偏移 ;R2为左孩子偏移 ;R3为右孩子偏移 ;R4为最大节偏移 ;R5为最大节点值 ;R6为二叉堆大小 只要清楚的认识这几个寄存器的作用就好多了，不会很晕。参考伪代码和寄存器作用的注释，就比较容易看懂这个汇编了。在这里先告诉大家一个好消息是，这个函数是最复杂的，下面的几个操作调用这个函数的话，就显得很简洁易懂了。 4.2、二叉堆建立 - ASM_BiHeap_Build4.2.1 二叉堆建立的作用 我们把一个普通的数组构建成一个二叉堆，调用的就是二叉堆建立函数，可见，二叉堆的建立不改变数据的存储，仍然是一个数组，但是改变了数据的结构，变成层次型了。 4.2.2 二叉堆建立的伪代码 可以看到非常简洁的伪代码，验证了刚才说的，调用二叉堆最大化子程序，可以把二叉堆其他操作的实现变得很简洁。 
4.2.3 二叉堆建立的C语言原形和解释 C语言原形：void ASM_BiHeap_Build( uint32_t *BiHeap ); 老样子，BiHeap是二叉堆首地址，调用该函数实现二叉堆的建立，把一个普通的数组建立成一个二叉堆，之后我们就可以对二叉堆实现二叉堆特有的各种操作了。 伪代码解释： 1、获取二叉堆的大小，保存在heap-size[A]中 2、把数组平均划分成两个部分，前半部分和后半部分 3、对前半部分，从Length[A]/2到1，循环调用MAX_Heapify，也就是我们上节实现的二叉堆最大化。 这样就实现了二叉堆的建立。通俗一点，举个例子是数组有10个元素，我们从5（一半）到1，循环调用二叉堆最大化，至于为什么这么做能实现二叉堆最大化，大家如果不明白的话网上找资料吧。 4.2.4 二叉堆建立的汇编语言描述;***************************** ******************************* ; 函数名 : ASM_BiHeap_Build ; 描述 : 二叉堆构建 ; 输入 : R0 --- 二叉堆首地址 ; 输出 : 无 ; 寄存器 : 无 ; 调用 : 外部调用 ;***************************** ******************************* ASM_BiHeap_Build PUSH {R1, LR}
LDR R1, [R0] ;R1为二叉堆大小 LSR R1, #1 ;二叉堆需要最大化个数
ASM_BiHeap_Build_Loop PUSH {R1-R8} ;入栈 BL ASM_BiHeap_Maxify ;二叉堆最大化 POP {R1-R8} ;出栈
SUB R1, #1 ;递减二叉堆最大化个数 CMP R1, #0 ;判断是否为零 BNE ASM_BiHeap_Build_Loop ;不为零, 继续循环
POP {R1, PC} ;返回 ASM_BiHeap_Build_End
老样子先看懂伪代码，再顺着代码，看注释是比较容易理解的，接下来继续其他操作。 4.3、二叉堆排序 - ASM_BiHeap_Sort4.3.1 二叉堆排序的作用 二叉堆的排序算是二叉堆的一个附加操作了，因为排序后二叉堆就已经不是二叉堆的结构了，而是一个按值的大小排序的数组了。 4.3.2 二叉堆排序的伪代码 伪代码依然是这么的简洁，同样也调用了二叉堆最大化子程序。 
4.3.3 二叉堆最大化的C语言原形和解释 C语言原形：void ASM_BiHeap_Sort( uint32_t *BiHeap ); 伪代码解释： 1、建立二叉堆 2、循环执行Length[A]-1次，每次的操作包含以下： 3、改变循环变量i，从Length[A]到2 4、交换第一个元素（最大值）与第i个元素的值（交换后最后一个元素是最大值） 5、二叉堆元素个数减一 6、最大化二叉堆，保持二叉堆性质（因为交换了第一个元素和第i个元素值，父节点可能不是最大值） 4.3.4 二叉堆最大化的汇编语言描述;***************************** ******************************* ; 函数名 : ASM_BiHeap_Sort ; 描述 : 二叉堆排序 ; 输入 : R0 --- 二叉堆首地址 ; 输出 : 无 ; 寄存器 : 无 ; 调用 : 外部调用 ;***************************** ******************************* ASM_BiHeap_Sort PUSH {R1-R4, LR}
BL ASM_BiHeap_Build ;建立二叉堆
LDR R1, [R0] ;R1存放二叉堆大小 PUSH {R1}
ASM_BiHeap_Sort_Loop LDR R3, [R0, #4] ;R2为二叉堆首元素 LDR R4, [R0, R1, LSL #2] ;R3为二叉堆最后一个元素
STR R3, [R0, R1, LSL #2] ;最大元素放在二叉堆末尾 STR R4, [R0, #4] ;二叉堆末尾元素放在二叉堆首
SUB R1, #1 ;二叉堆元素个数减一 STR R1, [R0] ;保存二叉堆元素个数
PUSH {R1-R8} ;入栈 MOV R1, #1 ;R1为待最大化二叉堆元素 BL ASM_BiHeap_Maxify ;二叉堆最大化 POP {R1-R8} ;出栈
CMP R1, #0 ;比较二叉堆元素是否为零 BNE ASM_BiHeap_Sort_Loop ;不为零, 继续排序
POP {R1} ;出栈二叉堆大小 STR R1, [R0] ;重新赋值二叉堆大小
POP {R1-R4, PC} ;返回 ASM_BiHeap_Sort_End
也是从伪代码到汇编代码和注释这样看。进入下一个操作。 4.4、二叉堆键值增加 - ASM_BiHeap_KeyInc4.4.1 二叉堆键值增加的作用 二叉堆键值增加实现二叉堆元素值增加，可以实现优先级队列，算是优先级队列的一个操作吧，增加对应的优先级。 4.4.2 二叉堆键值增加的伪代码 也是很简洁，但是这次没有调用二叉堆最大化子程序。 
4.4.3 二叉堆键值增加的C语言原形和解释 C语言原形： void ASM_BiHeap_KeyInc( uint32_t *BiHeap, uint32_t Pos, uint32_t NewKey ); 伪代码解释： 1、如果键值小于原来的键值 2、退出 3、赋值新的键值（有可能破坏二叉堆结构，新键值可能大于父节点值） 4、循环保持二叉堆性质 5、循环条件为i大于根节点位置，并且父节点值小于子节点值 6、交换父节点值与子节点值 7、修改i的位置为父节点位置（继续循环，回到4，因为有可能二叉堆性质被破坏）, 4.4.4 二叉堆键值增加的汇编语言描述;***************************** ******************************* ; 函数名 : ASM_BiHeap_KeyInc ; 描述 : 二叉堆指定元素键值更新 ; 输入 : R0 --- 二叉堆首地址 ; R1 --- 指定元素偏移 ; R2 --- 新键值 ; 输出 : 无 ; 寄存器 : 无 ; 调用 : 外部调用 ;***************************** ******************************* ASM_BiHeap_KeyInc PUSH {R3-R4, LR}
LDR R3, [R0, R1, LSL #2] ;R3为指定元素值 CMP R3, R2 ;比较指定元素与新元素大小 BGT ASM_BiHeap_KeyInc_Exit ;指定元素更大, 退出
STR R2, [R0, R1, LSL #2] ;保存新元素到指定元素
MOV R3, R1, LSR #1 ;R3为父节点偏移 CMP R3, #0 ;如果父节点是否大于零 BEQ ASM_BiHeap_KeyInc_Exit ;为零, 退出
ASM_BiHeap_KeyInc_Loop LDR R4, [R0, R3, LSL #2] ;R4为父节点元素 CMP R4, R2 ;比较父节点元素与新元素 BGT ASM_BiHeap_KeyInc_Exit ;父节点大, 满足二叉堆规则, 退出
STR R4, [R0, R1, LSL #2] ;小元素放在子节点 STR R2, [R0, R3, LSL #2] ;大元素放在父节点
MOV R4, R2 ;更新子节点偏移 MOV R1, R3 ; LSR R3, #1 ;更新父节点偏移
CMP R3, #0 ;如果父节点是否大于零 BGT ASM_BiHeap_KeyInc_Loop ;大于零, 继续循环
ASM_BiHeap_KeyInc_Exit POP {R3-R4, PC} ;返回 ASM_BiHeap_KeyInc_End
看懂程序 == 伪代码 + 汇编代码 + 注释，接下来进入下一个操作。 4.5、二叉堆元素插入 - ASM_BiHeap_Insert4.5.1 二叉堆元素插入的作用 插入新元素是一种非常常见的操作，二叉堆当然也支持这种操作，可以理解为添加一个新成员吧。 4.5.2 二叉堆元素插入的伪代码 调用了二叉堆键值增加子程序，代码更加简洁了。 
4.5.3 二叉堆元素插入的C语言原形和解释 C语言原形：void ASM_BiHeap_KeyInsert (uint32_t *BiHeap, uint32_t Key) ; 伪代码解释： 1、二叉堆元素个数加一（因为插入了一个新元素） 2、新元素赋值为负无穷，实际我们用一个很小的数代替 3、调用键值增加子程序实现对应元素的赋值（保持了二叉堆的性质） 4.5.4 二叉堆元素插入的汇编语言描述;***************************** ******************************* ; 函数名 : ASM_BiHeap_KeyInsert ; 描述 : 二叉堆元素插入 ; 输入 : R0 --- 二叉堆首地址 ; R1 --- 新元素键值 ; 输出 : 无 ; 寄存器 : 无 ; 调用 : 外部调用 ;***************************** ******************************* ASM_BiHeap_KeyInsert PUSH {R2-R3, LR}
LDR R2, [R0] ;二叉堆大小 ADD R2, #1 ;二叉堆大小加一 STR R2, [R0] ;更新二叉堆大小
MOV R3, #0 ;R3为0 STR R3, [R0, R2, LSL #2] ;新元素值为0
MOV R3, R2 ;R3为新元素位置 MOV R2, R1 ;R2为新元素值 MOV R1, R3 ;R1为新元素位置 BL ASM_BiHeap_KeyInc ;调用二叉堆指定元素键值更新
POP {R2-R3, PC} ;返回 ASM_BiHeap_KeyInsert_End
看懂程序 == 伪代码 + 汇编代码 + 注释，接下来进入下一个操作。 4.6、二叉堆最大元素 - ASM_BiHeap_Maximum4.6.1 二叉堆最大元素的作用 查询二叉堆中最大的元素使用的操作，比较简单。 4.6.2 二叉堆最大元素的伪代码
4.6.3 二叉堆最大元素的C语言原形和解释 C语言原形：uint32_t ASM_BiHeap_Maximum( uint32_t *BiHeap ); 伪代码解释：直接返回位置为1的元素 4.6.4 二叉堆最大元素的汇编语言描述 可以说这是最简单的操作了，代码： ;***************************** ******************************* ; 函数名 : ASM_BiHeap_Maximum ; 描述 : 二叉堆返回最大元素 ; 输入 : R0 --- 二叉堆首地址 ; 输出 : uint32_t --- 二叉堆最大元素 ; 寄存器 : 无 ; 调用 : 外部调用 ;***************************** ******************************* ASM_BiHeap_Maximum LDR R0, [R0, #4] ;获取二叉堆首元素
BX LR ;返回 ASM_BiHeap_Maximum_End
接下来下一个操作，也是最后一个操作了。 4.7、二叉堆出队最大元素 - ASM_BiHeap_ExtraMax4.7.1 二叉堆出队最大元素的作用 出队实现了返回最大元素的功能，同时将元素从二叉堆移除，也就是出队后二叉堆就没有了这个元素。 4.7.2 二叉堆出队最大元素的伪代码 还是调用了二叉堆最大化子程序，变得很简洁了。 
4.7.3 二叉堆出队最大元素的C语言原形和解释 C语言原形：uint32_t ASM_BiHeap_ExtracMax( uint32_t *Arr ); 伪代码解释： 1、如果二叉堆元素个数小于1，返回错误 2、把第1个元素（最大元素）放在max 3、最后一个元素放在第1个元素位置（覆盖了第一个位置的值） 4、二叉堆元素个数减一（因为出队） 5、调用二叉堆最大化子程序保持二叉堆性质（最后一个元素放在第一个，可能破坏二叉堆性质） 6、返回max（返回最大元素，同时最大元素也已经出队了） 4.7.4 二叉堆出队最大元素的汇编语言描述;***************************** ******************************* ; 函数名 : ASM_BiHeap_ExtracMax ; 描述 : 二叉堆返回最大元素 ; 输入 : R0 --- 二叉堆首地址 ; 输出 : uint32_t --- 二叉堆最大元素 ; 寄存器 : 无 ; 调用 : 外部调用 ;***************************** ******************************* ASM_BiHeap_ExtracMax PUSH {R1-R2, LR}
LDR R1, [R0, #4] ;R1二叉堆最大元素 PUSH {R1} ;入栈保护最大元素
LDR R1, [R0] ;R1为二叉堆大小 LDR R2, [R0, R1, LSL #2] ;R2为二叉堆最后一个元素 STR R2, [R0, #4] ;最后一个元素放在首元素, 破坏二叉堆结构
SUB R1, #1 ;二叉堆元素个数减一 STR R1, [R0] ;保存二叉堆元素个数
PUSH {R2-R8} MOV R1, #1 ;二叉堆待最大化元素 BL ASM_BiHeap_Maxify ;二叉堆最大化 POP {R2-R8}
POP {R0} ;最大元素放在R0 POP {R1-R2, PC} ;返回 ASM_BiHeap_ExtracMax_End
看懂程序 == 伪代码 + 汇编代码 + 注释，最后一个操作也完了。
实现了这些操作之后，我们就开始编写程序测试这些操作是否正确了，测试程序是用C语言编写的，也就是用C语言调用汇编子程序。 第五章 测试5.1 汇编文件的包装 我们在上一章编写的只是子程序，对一个汇编文件来说，跟C语言一样也要包括其他伪指令啊宏定义啊什么的，这一节我们来看看这么做。需要的操作有： 1、代码段声明 2、声明标号为外部的 3、添加END 具体整个文件应该是对应的一下形式： ;***************************** 接口函数声明 ******************************* EXPORT ASM_BiHeap_Build ;二叉堆构建 EXPORT ASM_BiHeap_Sort ;二叉堆排序 EXPORT ASM_BiHeap_Maximum ;二叉堆返回最大元素 EXPORT ASM_BiHeap_ExtracMax ;二叉堆返回最大元素 EXPORT ASM_BiHeap_KeyInc ;二叉堆指定元素键值更新 EXPORT ASM_BiHeap_KeyInsert ;二叉堆元素插入 ;***************************** *******************************
;***************************** 代码段声明 ******************************* AREA |.text|, CODE, READONLY, ALIGN=2 THUMB REQUIRE8 PRESERVE8 ;***************************** *******************************
;***************************** 代码 ******************************* 汇编子程序 ;***************************** *******************************
END ;**************************************文件结束****************************
以上格式就是我们的汇编源文件，分别对应四个部分。 1、标号声明 2、代码段声明 3、代码段 4、END 其中的汇编子程序就是上一章我们所实现的二叉堆的操作了。 5.2 C语言头文件 本人为了让C语言能调用这些汇编函数，对应编写了一个C语言的头文件，声明这些函数，具体实现如下：
#ifndef __BIHEAP_H #define __BIHEAP_H
#include "stm32f10x.h"
void ASM_BiHeap_Maxify(uint32_t *Arr, uint32_t Len); //二叉堆最大化 void ASM_BiHeap_Build(uint32_t *Arr); //二叉堆建立 void ASM_BiHeap_Sort(uint32_t *Arr); //二叉堆排序 void ASM_BiHeap_KeyInc(uint32_t *Arr, uint32_t Pos, uint32_t NewKey); //二叉堆键值增加 void ASM_BiHeap_KeyInsert(uint32_t *Arr, uint32_t Key); //二叉堆元素插入 uint32_t ASM_BiHeap_Maximum(uint32_t *Arr); //二叉堆最大元素 uint32_t ASM_BiHeap_ExtracMax(uint32_t *Arr); //二叉堆出对最大元素
#endif //#ifndef __BIHEAP_H
5.3 测试 对应的C语言测试源文件，这个函数并没有测试所有的汇编子程序，不过本人自己都测试过了，这里只是举个例子：
#include "data_struc.h"
#if BI_HEAP_TEST_EN //如果使能二叉堆测试 static uint32_t Arr[20] = {15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; //二叉堆, 首元素为二叉堆的元素个数 #endif //#if BI_HEAP_TEST_EN
#if BI_HEAP_TEST_EN //如果使能二叉堆测试 FStat BiHeap_Test(void) { ASM_BiHeap_Build( Arr ); //构建二叉堆函数 ASM_BiHeap_KeyInsert( Arr, 10); //添加元素 ASM_BiHeap_KeyInc( Arr, 2, 16 ); //指定元素键值增加 printf("%d\n", ASM_BiHeap_ExtracMax( Arr ) );//打印出对元素
return FuncOK; } #endif //#if BI_HEAP_TEST_EN
5.4 测试结果 测试结果是本人认为是正确的，这里也不贴出来了，毕竟文章也比较长了。如果那里有错误欢迎大家指出来，感谢大家啦。 附录1、C语言的主函数 
参考文献[1] 《算法导论》第二版 机械工业出版社 [2] 《Cortex-M3权威指南》 Joseph Yiu 著 宋岩 译 | 
