在 ARM 汇编中实现简单的排序算法

我在 ARM Assembly 中完成了我的简单排序算法的第一个粗略版本（请参阅我的更新的第 1 部分和第 2 部分）。到目前为止（在进行一些清理和优化之前）：


 /*
R0 address of string used with printf ti output %d
R4 address of numbers to sort
R5 current number to be compared
R6 offset index for outer loop through numbers
R7 offset index for inner loop
R8 current smallest identified value
R9 current offset index of next uncompared value
*/
.global main
main:
  push {ip, lr}
  MOV R6, #0 @outerloop offset to numbers to be sorted
  MOV R7, #0 @innerloop offers to number to be sorted
  MOV R9, #0 @init value for index to next uncompared value
outerLoop:
  MOV R8, #99 @reset large default for next loop comparison
  MOV R7,R6 @copy outerloop offset to next starting offset for the innerloop
innerLoop:
  LDR R0, =output @load addr of output string
  LDR R4, =nums @load addr of nums to compare to R4
  LDR R5,[R4,R7] @load current num to R5 from R4 with offset R7
  MOV R1,R5 @move num for output
  BL printf
  CMP R5,R8 @is current < smallest so far
  BLT swapSmallest @if true, swap smallest to current first position then continue
continue:
  CMP R7,#16 @ 0 plus 4*4bytes for 5 entries in array
  ADD R7, R7,#4 @inc offset by 4 bytes
  BLT innerLoop
continueOuterLoop:
  CMP R6, #16 @check if we've looped through all values
  ADD R6, R6, #4
BLT outerLoop @if not, branch back to start of outer loop
_exit:
  POP {ip, lr}
resetLoopOffsets:
  MOV R7, #0 @reset loop counter
writeFinalSoredList: @TODO: this is a near copy of the innner loop - refactor this to function
  LDR R0, =writeSorted @load addr of output string
  LDR R4, =nums @load addr of nums
  LDR R5,[R4,R7] @load current num to R5 from R4 with offset R7
  MOV R1,R5 @move num for output
  BL printf
  CMP R7,#16 @ 0 plus 4*4bytes for 5 entries in array
  ADD R7, R7,#4 @inc offset by 4 bytes
  BLT writeFinalSoredList
doExit:
  MOV R1, #0
  MOV R7, #1
  SWI 0
swapSmallest:
  MOV R8,R5 @keep copy of smallest in the current loop
  LDR R10, [R4,R6] @tmp copy first position to R10
  LDR R11, [R4,R7] @tmp copy value in position currently being compared
  STR R10, [R4, +R7] @swap first position value to current position being compared
  STR R11, [R4, +R6] @swap the current smallest value into the current first position
  BX lr @return
.data
nums:
.word 5,2,7,1,8
output:
.asciz "%d\n"
writeSorted:
.asciz "%d\n"

如果您想获取副本，请在此处的 github 中获取完整的源代码。

为了做到这一点，我学习了很多关于 ARM 架构的知识——随着时间的推移，它已经发展并且有许多不同的版本，并且不同的基于 ARM 的 CPU 实现了不同的架构版本。更复杂的是，命名方案有点混乱。

Raspberry Pi 中的 ARM CPU 是 Broadcom BCM2835 片上系统 (SoC)，其中包括一个 ARM1176JZF-S （此处为 ARM 参考手册）。这是一个 ARM11 内核，基于 ARMv6架构。

ARMv6 指令的兴趣点（不是一个全面的总结，只是一些粗略的笔记，以备日后参考）：

大多数指令都是结构化的“指令目标，源”，但由于某种原因，STR（存储）被颠倒了，所以它是“指令源，目标”
LDR（加载寄存器），可以将源作为常量的标签，或者以'='为前缀，它获取常量所在的内存中的地址。
LDR 可以移动另一个寄存器中地址指向的值，使用 [Rn]，也可以与偏移量耦合作为第二个参数，[Rn, Rm]

我可能会花一些时间看看我是否可以进一步清理代码，但到目前为止我对此很满意。

在 ARM 汇编中实现简单的排序算法

相关文章