欢迎关注个人的微信公众号《Android安全工程》（可点击进行扫码关注）。个人微信公众号主要围绕 Android 应用的安全防护和逆向分析， 分享各种安全攻防手段、Hook 技术、ARM 汇编等 Android 相关的知识。
二叉查找算法示例
C语言实现二叉查找算法的函数例子如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
|
这个函数接收一个数组、要查找的左边界和右边界、以及要查找的目标元素。在函数中，我们首先通过 left 和 right 确定数组的中间元素 mid，并将其与目标元素进行比较。如果相等，则返回中间元素的索引。如果中间元素比目标元素小，则在右侧查找，反之在左侧查找。如果没有找到目标元素，则返回 -1 表示未找到。
转ARM32汇编解析
下面是将 C 代码转换为 ARM32 汇编代码后的函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | binarySearch:
@ r0 = arr, r1 = left, r2 = right, r3 = target
push {r4, lr} @ 保存 r4 和 lr 寄存器
mov r4, r1 @ 将左边界保存到 r4 中
loop:
cmp r1, r2 @ 比较左右边界
bgt end @ 如果左边界大于右边界，则跳转到 end 标签
add r5, r1, r2 @ 计算中间位置
mov r5, r5, asr
ldr r6, [r0, r5] @ 将中间位置的元素加载到 r6 中
cmp r6, r3 @ 比较中间位置的元素和目标元素
beq found @ 如果相等，则跳转到 found 标签
bge right @ 如果中间位置的元素小于目标元素，则跳转到 right 标签
left:
add r1, r5,
b loop @ 跳转到 loop 标签
right:
sub r2, r5,
b loop @ 跳转到 loop 标签
found:
mov r0, r5 @ 将找到的位置保存到 r0 中
pop {r4, pc} @ 恢复 r4 和 pc 寄存器，跳转到函数调用位置
end:
mov r0,
pop {r4, pc} @ 恢复 r4 和 pc 寄存器，跳转到函数调用位置
|
上面汇编代码的注释详细地说明了每行汇编指令地作用。相信有接触过汇编代码的读者，会有这样的疑问：push {r4, lr} 这行汇编具体的作用是什么呢？
push {r4, lr} 的作用是将寄存器 r4 和 lr 的值存入当前的栈帧中。通常在函数调用时使用 push 指令保存当前函数栈现场，以便在调用的子函数返回时恢复现场。
在这个函数中，r4 寄存器被用来存储左边界的值，而 lr 寄存器则是链接寄存器，用于存储返回地址（这里记录的地址是当前跳转函数的下一条指令的地址，即 lr=pc+1）。因此，使用 push {r4, lr} 保存这两个寄存器的值是为了确保在函数执行过程中它们的值不会被覆盖或修改。
在函数执行结束后，我们需要使用 pop 指令恢复现场，将之前保存在栈中的值取出并存储回 r4 和 lr 寄存器中，以便从函数返回到调用者。
阅读到这里，相信有的读者会存在疑问：为什么上述汇编的 r5 和 r6 不用压栈呢？
在这个函数中，r5 和 r6 寄存器是临时寄存器，仅在函数内部用于计算和存储中间位置和中间位置的元素值。它们的值在函数执行过程中可能会被多次修改，但并不需要在函数调用过程中保留它们的值。
因此，在函数的开头，我们使用 push {r4, lr} 指令将 r4 和 lr 寄存器的值压入栈中，这是为了保存调用函数前的现场，并保证函数执行结束后现场可以被恢复。而对于函数中的临时寄存器，我们没有必要将它们的值压入栈中，因为它们的值不需要被保留。
需要注意的是，如果函数中使用了其他的寄存器作为临时寄存器，而这些寄存器的值在函数调用结束后需要被保留，那么在函数开头时需要将这些寄存器的值压入栈中，以便在函数执行结束后恢复现场。
push 指令是将数据写入栈中的操作，这个过程可以简单地理解为将数据从寄存器（或内存）移动到内存中的某个地址。在 ARM32 汇编中，使用栈可以方便地保存现场信息，比如被调用的函数在执行时需要保存当前的寄存器值、返回地址、参数等信息，这些信息可以通过将寄存器的值压入栈中来实现。
在 ARM32 架构中，栈的实现通常是通过将栈顶指针（Stack Pointer，SP）指向栈顶地址，并在需要保存数据时将数据压入栈中，栈顶指针递减，反之在需要弹出数据时，栈顶指针递增，从栈中弹出数据。这样，通过控制栈顶指针的位置，可以实现栈的压入和弹出操作，实现现场的保存和恢复。
具体来说，当执行 push {r4, lr} 指令时，该指令会将寄存器 r4 和 lr 中的值依次压入栈中，栈顶指针 SP 递减 8 个字节（因为 r4 和 lr 都是 4 字节长），指向新的栈顶地址。这样就实现了现场信息的保存，同时也为后续的代码执行做好了准备。
在需要恢复现场时，通常使用 pop 指令将栈中的数据弹出到寄存器中，恢复原来的值。具体来说，执行 pop {r4, lr} 指令时，该指令会将栈顶位置的值弹出到寄存器 lr 和 r4 中，栈顶指针 SP 递增 8 个字节，指向新的栈顶地址。这样就完成了现场信息的恢复，函数可以从保存现场的位置继续执行。
既然是通过汇编 push 指令来保持现场，为什么在该栈里面还可以使用 r4 呢？
在 ARM32 汇编语言中，使用 push 和 pop 指令可以方便地进行现场保存和恢复操作，这是因为这两个指令会自动将栈顶指针（Stack Pointer，SP）递减或递增，并将寄存器中的数据压入或弹出栈中。在调用函数时，通常会使用 push 指令将当前函数的返回地址和寄存器中的值压入栈中，然后使用 pop 指令在返回时将现场信息恢复到原来的状态。
由于 push 指令压栈时只保存了 r4 和 lr 寄存器的值，并没有在栈中分配空间来存储其他寄存器的值，因此在该函数的栈帧中并没有为其他寄存器（比如 r5 和 r6）分配空间。实际上，如果在该函数中需要使用这些寄存器，它们的值是可以直接保存在寄存器中的，不需要使用栈来保存。只有在需要保存到栈中的寄存器值，才需要通过 push 和 pop 指令来进行保存和恢复操作。
总之，通过使用 push 和 pop 指令来进行现场保存和恢复时，需要注意指令所保存的寄存器的数量和顺序，以及栈指针的位置等细节。
除了 push {r4, lr}，在 ARM 汇编语言中还有其他类似的指令可以用于保存现场，以下是一些常见的指令：
stmdb sp!, {r4, lr}: 将寄存器 r4 和 lr 的值存入当前栈帧中，并将栈指针 sp 减去相应的值，以便在函数返回时恢复现场;stmfd sp!, {r4, lr}: 与 stmdb 功能相同，将寄存器 r4 和 lr 的值存入当前栈帧中，但是将栈指针 sp 增加相应的值;sub sp, sp, #size: sp 减去 size 的值，从而开辟 size 大小的栈空间。例如，sub sp, sp, #16 表示在栈上开辟 16 个字节的空间;
补充介绍
在 ARM 汇编语言中，push 指令和 stm 指令都可以用来保存现场。它们的使用方式和效果有以下几点差别：
- 操作数：
push 指令只能将连续的寄存器依次压入栈中，而 stm 指令可以指定需要保存的寄存器。例如，stmdb sp!, {r4, lr} 可以将 r4 和 lr 寄存器的值存入栈中。
- 栈指针变化：
push 指令只需指定要保存的寄存器，它会自动计算栈指针的偏移量，并将值存入栈中。而 stm 指令需要显式指定栈指针的变化量，以便在保存完寄存器的值后，栈指针可以正确地指向下一个栈帧。
- 立即数：
push 指令可以使用立即数来压入常量值，而 stm 指令只能用于保存寄存器的值。
- 灵活性：
stm 指令比 push 指令更加灵活，可以用于保存任意数量和任意顺序的寄存器。而 push 指令只能依次保存连续的寄存器。
需要注意的是，由于 push 指令只能依次保存连续的寄存器，如果要保存的寄存器不是连续的，就需要使用多条 push 指令。而 stm 指令则可以一次性保存多个不连续的寄存器，这可以减少指令的数量，提高代码的效率。
[培训]二进制漏洞攻防（第3期）；满10人开班；模糊测试与工具使用二次开发；网络协议漏洞挖掘；Linux内核漏洞挖掘与利用；AOSP漏洞挖掘与利用；代码审计。
