注意事項：實操本文前需要部署相關環境，若未部署，請參閱上一篇博客快速部署環境。
《【ChCore Lab 00】ChCore Lab 環境簡單搭建》

1. 前言

在實驗中提供了一個二進制炸彈程序 bomb 以及它的部分源碼 bomb.c。在 bomb.c 中，你可以看到一共有 6 個 phase。對每個 phase，bomb 程序將從標準中輸入中讀取一行用戶輸入作為這一階段的拆彈密碼。若這一密碼錯誤，炸彈程序將異常退出。你的任務是通過 GDB 以及閱讀匯編代碼，判斷怎樣的輸入可以使得炸彈程序正常通過每個 phase。

如果沒有匯編基礎的同學可以通過以下鏈接熟悉 ARM ISA，如果之前只學過 X86 指令的話，看起來會更快一點。
英文原版：https://azeria-labs.com/writing-arm-assembly-part-1/
中文翻譯版：https://zhuanlan.zhihu.com/p/109543670

2. 實驗代碼版本問題

為了避免各位同學與筆者這里所使用的代碼版本不一致可以通過如下鏈接下載筆者同款實驗代碼：

• Github: OS-Course-Lab20250411.tar.gz
• CSDN 資源: OS-Course-Lab20250411.tar.gz
• 上海交大 IPADS 實驗室發布代碼：https://github.com/SJTU-IPADS/OS-Course-Lab

下載好的代碼目錄長這樣子：

im01@Ubuntu:OS-Course-Lab$ ls
Assets     CHANGELOG.md  Lab1  Lab3  Lab5  LICENSE  README.md  Scripts  Thirdparty
book.toml  Lab0          Lab2  Lab4  Lab6  Pages    RELEASE    Slides

進入 Lab0 目錄。

im01@Ubuntu:Lab0$ ls
ans.txt  bomb  bomb.c  bomb.S  Makefile  scores.json  scripts  student-number.txt  warehouse

Makefile 使用講解：

• make bomb: 使用 student-number.txt 提供的學號，生成炸彈，如果您不是上海交通大學的學生可以自行隨意填寫。
• make qemu: 使用 qemu-aarch64 二進制模擬運行炸彈
• make qemu-gdb: 使用 qemu-aarch64 提供的 gdb server 進行調試
• make gdb: 使用 gdb 連接到 qemu-aarch64 的 gdb-server 進行調試

3. 關于使用問題

有關 gdb 使用命令可以自行搜索學習一下，應該會很快了解，本文也只使用到幾個簡單的調試命令不會很復雜，這里筆者不多贅述，這里主要展示一下筆者在分析當前代碼時候所使用的窗口布局，個人認為使用挺方便，各位同學也可以參考借鑒，所使用的終端叫 terminator。

4. 宏觀分析

首先來查看 bomb.c，也就是本文需要分析的代碼。

$ cat bomb.c
#include <stdio.h>
#include "phases.h"
#include "utils.h"int main() {char* input;printf("Type in your defuse password!\n");input = read_line();phase_0(input);phase_defused();input = read_line();phase_1(input);phase_defused();input = read_line();phase_2(input);phase_defused();input = read_line();phase_3(input);phase_defused();input = read_line();phase_4(input);phase_defused();input = read_line();phase_5(input);phase_defused();printf("Congrats! You have defused all phases!\n");return 0;
}

所謂拆彈實驗就是對這個文件所編譯出來的二進制程序解析，可以看到代碼中調用了很多 phase 函數，而這些函數的實現不在該文件里，因此我們是不清楚函數調用具體發生了什么，而函數的執行需要手動傳入正確的參數才能執行下去，這就需要我們通過反匯編來逆向解析獲取程序要求輸入的參數是什么，這就是拆彈實驗，其目的在于通過實驗讓我們對匯編指令以及逆向流程更加熟悉，這對于往后編寫操作系統代碼以及調試很有幫助。

而當我們輸入錯誤的值，將會導致炸彈爆炸：

從 C 代碼中可以看到每一個 phase 前都會調用一個 read_line 函數，從函數名也才得到這個函數是從標準輸入中讀取我們的輸入字符串。

執行 make 命令生成可執行文件 bomb。

$ make bomb

查看 bomb 文件屬性。

$ file bomb
bomb: ELF 64-bit LSB executable, ARM aarch64, version 1 (GNU/Linux), statically linked, BuildID[sha1]=cfb1392f48ecf11232f5c117aeaf081f899f6cbc, for GNU/Linux 3.7.0, with debug_info, not stripped

可以看到該文件是一個 ARM aarch64 架構的 64 位的 ELF 可執行文件。

使用 objdump 生成匯編代碼，并打開。

$ aarch64-linux-gnu-objdump -dS bomb > bomb.s

找到 main 函數所在位置，與 C 語言代碼對比，基本是一一對應的。

5. read_line 函數介紹

由于每個 phase 前都使用到了 read_line 函數，這里并不用對 read_line 函數的匯編進行分析，我們從函數名以及其數據流就能夠清楚該函數的作用就是將標準輸入的字符串原模原樣保存進 input 變量里。然后每個 phase 再對字符串中的內容解讀并判斷是否符合要求。

也正是由于每個 phase 之前都調用了 read_line 函數，因此在使用 GDB 調試時候就將斷點設置到 read_line 函數即可，正好就在我們正要輸入時候停下。

6. phase_0 函數

查看匯編代碼，通過 main 函數我們看到程序首先使用參數執行的是 phase_0，直接看 phase_0 的匯編代碼。

前兩行是函數棧幀的保存操作，把調用者的棧幀指針 x29 和返回地址 x30 保存到當前函數的棧中，將當前 sp（棧指針）賦值給 x29（幀指針），設置當前函數的棧幀基址。用于當前函數返回后恢復調用函數棧幀。

緊接這調用一個 read_int 函數，這個不是標準庫的函數而是代碼中定義的函數，我們跳入進去查看實現。

6.1. read_int 函數

OK，同樣前兩行是函數棧幀的保存操作，暫時就不過多分析這兩行。
接下來將 sp + 0x1c 這個值保存進 x2 寄存器，接下來的兩行 adrp 和 add 指令組合可以簡單的理解為在讀取一個全局變量的一個操作，或者是讀取一個函數地址的操作，有關該指令的具體作用筆者在下方給出了詳細的說明。

ADR 指令作用：小范圍的地址讀取指令。ADR 指令將基于 PC 相對偏移的地址值讀取到寄存器中。
原理：將有符號的 21 位的偏移，加上 PC, 結果寫入到通用寄存器，可用來計算 +/-1MB 范圍的任意字節的有效地址。

ADRP 作用：以頁為單位的大范圍的地址讀取指令，這里的 P 就是 page 的意思。
原理：符號擴展一個 21 位的 offset（immhi+immlo）, 向左移動 12 位，PC 的值的低 12 位清零，然后把這兩者相加，結果寫入到 Xd 寄存器，用來得到一塊含有 lable 的 4KB 對齊內存區域的 base 地址（也就是說 lable 所在的地址，一定落在這個 4KB 的內存區域里，指令助記符里 Page 也就是這個意思）， 可用來尋址 +/- 4GB 的范圍（2^33次冪）。
通俗來講，ADRP 指令就是先進行 PC+imm（偏移值）然后找到 lable 所在的一個4KB 的頁，然后取得 label 的基址，再進行偏移去尋址。

上面簡單描述了 adrp 指令的作用，以及與其相關的一個 adr 指令的作用，如果不太好理解可以不需要完全搞清楚，這里只需要簡單的明白 652 和 653 行的這兩行指令一起用起來就是去訪問內存中的變量，而這里的作用就是將 0x464000 + 0x870 賦值給 x1 寄存器。

接下來去調用 sscanf 函數，這個函數是一個標準庫函數，其函數聲明如下：

int sscanf(const char *str, const char * format, ...);

可以看到，該函數至少接受三個參數，將 str 字符串格式化輸入到另外一個或多個地址中。在匯編代碼中我們看到調用 sscanf 函數是使用的寄存器傳參，也就是上面用 x1、x2 保存的地址，而另外一個參數根據 aarch64 默認參數寄存器應該是 x0。

這里可能會有疑惑，在 read_int 函數中至今為見過對 x0 寄存器進行任何操作，那么 x0 保存的到底是什么值呢？

在此之前我們可以看到在調用 phase_0 的時候有傳入一個參數 input，這里使用的默認寄存器傳參，也就正是 x0 寄存器，而在 phase_0 調用 read_int 函數之前均未對 x0 寄存器做任何操作，那么此時到 read_int 函數中的 x0 寄存器依然是保存的 input 的信息。

這里我們不妨做一個小實驗來驗證我們的解讀是否正確。

由于 sscanf 第二個參數類型是 char * 類型，因此我們已經知道了 x1 的類型，也就可以通過 dgb 打印它到底是什么了。在執行 gdb 后并在 read_int 函數處設置斷點：

設置斷點后輸入 c (continue) 指令繼續執行 bomb 代碼到 read_int 函數處，這時我們輸入一段特殊字符串 Imagine Miracle 用來驗證：

這時代碼已經進入 phase_0 停在 phase_0 函數中調用 read_int 處，此時我們來查看 x0 寄存器的值到底是什么，有兩種方式可以查看 x0 寄存器保存的地址：

這里 x0 保存的是地址，根據我們的分析，該地址存儲的是我們輸入的字符串，那么到底是不是打印出來看看：

看來是沒錯，的確是輸入的字符串成功證實了剛才的分析。

在調用 sscanf 函數時的三個參數分別為 x0、x1、x2，將 x0 字符串以 x1 的格式輸出到 x2 所指向的棧空間中。接下來就看 x1 是什么樣的格式，上文已經分析得到此時 x1 寄存器保存的地址為 0x464000 + 0x780，接下來我們打印出來這里保存的字符串是什么：

OK，這里看到該字符串是 “%d”，那么該函數的作用就是將 x0 字符串以 x1 描述的格式 "%d" 輸入到 x2 中，也就是說，將 x0 字符串以整型格式賦值給 x2。而這里并未找到對 x0 賦值的指令，那么就應該是使用的原來的值，那么原來的值是什么，我們就需要往前追了。

現在回到 sscanf 函數，在將 x0 的字符串格式化輸入到 x2 保存的地址之后，最后又將 x2 地址的值解引用賦值給 w0 后就直接返回了。
[注]：x2 保存的地址是 sp + 0x1c，0x1c 用十進制表示就是 28。ldr 指令的作用是從內存中取數據到寄存器。

這里筆者根據匯編代碼復現出 read_int 函數功能，這里并不是原始代碼，僅僅是與匯編一一對應的 c 語言代碼，便于大家理解，僅供參考。

6.2. 回到 phase_0 函數繼續分析

現在回到 phase_0 中繼續分析后面的指令，又看到了 adrp 指令與下一條指令的組合同樣是從內存中獲取變量，這里是從 0x4a0000 + 84 地址獲取值賦值給 w1，接下來就通過 cmp 比較 w1 和 w0 的值，如果不匹配就跳轉進入 explode 函數，即表示炸彈爆炸。既然要拆炸彈就要避免炸彈發生爆炸，也就是要是的 cmp 匹配成功，即讓我們輸入的字符串表示的整數等于 w1 保存的整數值，這里就可以通過 gdb 打印 w1 保存的整數值。

那么可以看到 w1 保存的整數值是 2022，因此我們在執行后第一個輸入應該輸入 2022，就可以解除第一個爆炸函數了。

6.3. 驗證結果

可以嘗試輸入任何其它數字，都會導致炸彈爆炸。

7. phase_1 函數

這里直接可以看到為 x1 讀取內存 0x4a0000 + 88 的值，之后就調用 strcmp 標準庫函數，該函數的聲明如下。

int strcmp(const char *str1, const char *str2)

該函數接收兩個參數，對比兩個字符串是否相同，若一直則返回 0，反之則不相同。我們無需關心該函數的匯編代碼，只需要了解其功能即可，而這里 strcmp 接收的兩個參數同樣是由寄存器 x0、x1 保存，x0 我們已經知道了是通過 read_line 函數輸入得到，x1 在上面已經看到了，現在我們還知道了 x1 的類型是字符指針（即 char *），就可以通過 dgb 打印出來。
[注]：由于在 phase_0 已經較為詳細的解釋過類似指令，在之后相同的指令筆者就不再贅述或者簡單描述，著重看關鍵指令。

這里可能有同學不太明白上面的 *(char **) 為什么這樣取值，筆者在下面用圖示的方式將這里的邏輯關系描述出來，簡單來說就是 x1 寄存器保存的事實上是我們真正想要的字符串首地址，而又因為 x1 作為 strcmp 的參數又是 char * 類型，相當于對指針再一次指針化一次，故這里我們需要取值，就需要二級指針才能拿到真正的字符串首地址，然后在對拿到的字符串二級指針解引用，即可拿到想要的字符串地址。

7.2. 驗證結果

現在已經分析到程序想要的輸入了，現在嘗試輸入看是否正確。

ok，很好到此 phase_1 也成功解除成功。

8. phase_2 函數

根據之前我們分析的兩個 phase，這里我們可以直接確定， phase_2 接收的參數即我們給的輸入依然是由 x0 寄存器保存。
[注]：該 phase 比起之前的有一點點難度，需要稍微認真分析。

同樣還是首先來看看 phase_2 的反匯編代碼，同樣開始先保存之前的函數棧幀，此時 sp 將會同時指向棧頂元素（sp 始終指向當前棧頂元素）。注意 ARM 的棧空間是向下生長的。

第二行設置當前幀指針 sp 保存到 x29 寄存器中，第三行將 x19、x20 寄存器的值保存到 sp+16 的位置（sp 依然指向棧頂元素，即剛剛存儲 x29 和 x30 的位置，具體來說 sp 是指向 x29）。

接下來將 sp + 0x20 賦值給 x1，即 sp + 32 的位置，也就是申請 32 字節的棧空間，然后就跳轉進入 read_8_numbers 函數執行，從函數名大概可以猜到該函數應該是想讀取 8 個數。

8.1. read_8_numbers 函數

具體來看看 read_8_numbers 函數的代碼。開始同樣是保存調用者棧幀，接著將 x1 的值保存進 x2（x1 保存的是 phase_2 中棧的 ps + 32）。

ok，為了方便理解，我們可以從第 640 行也就是從 0x400bb8 地址的指令開始倒著分析，這一行可以看到是調用標準庫函數 sscanf，而往上看就是對 x2~x7 賦值，很容易明白這就是 sscanf 的參數，目光投向 638 和 639 行，遇到了熟悉的指令組合，我們知道這是從內存中取值的操作，作為寄存器傳參的 x1，也就是 sscanf 的第二個參數（格式化的類型字符串），其類型是 char *，那么就可以使用 gdb 打印出來瞧瞧。

int sscanf(const char *str, const char * format, ...);

從這里可以看出來 sscanf 是希望將 x0 保存的字符串中用空格相間隔的 8 個數字輸入到 8 個整數變量中取。這就與該函數名 read_8_numbers 對應起來了，但是仔細想想，將一個字符串，按照格式化類型字符串的格式，輸入到 8 個整形變量中去，sscanf 函數的參數個數就需要 1 + 1 + 8 = 10 個參數才行，而這里的 x0~x7 只有 8 個寄存器，那還差兩個在哪，事實上在 aarch64 中默認傳參的寄存器只有 x0~x7，而 sscanf 后面的參數是 ... 可變參數，即在函數參數個數超出 8 個后，編譯器會默認使用棧來傳遞參數（且壓棧順序嚴格按照從后往前壓棧）。

從 637 到 633 行是由 x2 依次遞增 4 字節，將該地址賦值到對應寄存器，很容易想到，x2 保存的就是一個 int 整型數組的首地址，且數組長度為 8，而在 read_8_numbers 函數的棧頂位置保存的 x2 + 0x18 就是數組的第 7 個元素地址（&array[6]），在 sp + 8 保存的就是數組的第 8 個元素地址（&array[7]），回溯到 phase_2 函數就是 x1 保存的就是數組首地址。根據這樣的分析，就可以梳理出從 phase_2 到 read_8_numbers 函數整體的棧空間布局。

為了能夠更好的理解整個函數棧空間的布局以及 sscanf 的調用，這里筆者根據匯編代碼實現了 read_8_numbers 函數（這不是原始代碼）。可以清楚的是，整型數組每個元素占用 4B，而使用棧傳參，在棧中要保存的數組元素地址則是 32b 的值，因此棧中每個元素地址需要占用 4B。

ok，分析到這里我們已經非常清楚的知道了 read_8_numbers 函數的作用，就是將通過 read_line 讀到的字符串，按照以空格相間的整型寫入 phase_2 傳入的整型數組中。接下來需要分析的就是，需要我們輸入的字符串到底是什么，也就是以空格相間的 8 個數到底是什么值。

8.2. 回到 phase_2 函數繼續分析

現在繼續分析 phase_2 剩余的代碼，下圖中筆者將 phase_2 的函數棧布局單列出來幫助大家理解，首先來看 359 ~ 365 行代碼，開始先將 sp + 32 位置內存的值保存到 w0，再判斷 w0 是否等于 1，如果不等于將跳轉到 0x4007b4 地址的轉入 explode 爆炸函數，也就是說，判斷數組的第一個數是否為 1，如若不是則爆炸。再接下來將 sp + 36 位置內存的值保存到 w0 并判斷是否為 1，若是則繼續將會調轉執行 explode 爆炸函數，即如若數組的第二個數也不是 1 將會爆炸。由此看來，數組的前兩個數必須是 1。

現在，我們把目光聚焦在下面的代碼，366 行將 x19 指向 sp + 0x20(即 sp + 32)，也就是數組的第一個元素的地址 &array[0]，將 x20 指向 sp + 0x38(即 sp + 56)，也就是數組的第七個元素的地址 &array[6]。接著就跳轉入 0x4007d0 地址執行。

從 0x4007d0 地址執行，將內存中 x19 寄存器保存的地址中取值，保存到 w0 中，即將數組的第一個元素保存到 w0（w0 = array[0]），接著將內存中 x19 + 4 寄存器保存的地址中取值，保存到 w1 中，即將數組中第二個元素保存到 w1（w1 = array[1]）。從上文我們已經分析到數組的前兩個元素值是 1，那么后面的計算就需要用到確切的值。

接下來 add w0, w0, w1，即將 w0 + w1 賦值給 w0，此時 w0 = 1 + 1 = 2，再將 w0 自加 4，w0 += 4，即 w0 此時為 6，再取出 x19 + 8 的值保存到 w1，即去數組的第三個元素到 w1，判斷 w1 與 w0 是否相等，如果相等則跳轉到 0x4007c4 執行循環操作，若不相等則執行 explode 爆炸函數。為了使得炸彈解除，那么第三個元素就必須等于 6，現在我們已經分析得到了第三個數字，接著就往復循環，直到取到的地址 x19 保存的是數組第 7 個元素地址為止。下面筆者將上述第一次循環以圖示和根據匯編實現的 c 語言程序來幫助大家理解這段代碼（c 代碼僅為參考，并非原始代碼）。

8.3. 驗證結果

那么接下來的數字就非常有規律了前三個是 1、1、6，第四個就是 1 + 6 + 4 = 11，以此類推，完整的八個數應該為 1、1、6、11、21、36、61、101，運行程序輸入并驗證我們的推理是否正確。

看來是沒有問題的，現在我們成功已經將 phase_0 ~ 2 解除。
看到這里想必各位已經有點疲憊了，筆者建議在這里自行休息 5~10 分鐘后再繼續回來，接下來的內容會更加精彩。（筆者也寫累了🤣）

9. phase_3 函數

開頭指令為同樣是保存調用者棧幀環境，并建立當前棧幀的操作，接下來的 x3、x2 分別指向棧中變量，目前猜測這兩個變量應該是 int 型，因為 sp+0x18 - (sp+0x1c) = 0x04，占用 4 個字節的變量應該就是 int 型變量，繼續往后看來驗證我們的猜測。

接下來看到我們熟悉的 adrp 指令，我們知道這是從內存中獲取值的操作并用 x1 保存，而下面就看到調用了標準庫函數 sscanf，其函數聲明如下：

int sscanf(const char *str, const char * format, ...);

這又是我們熟悉的操作，這里很顯然就是用寄存器傳參，x0 為 read_line 讀取我們輸入的字符串，x1 作為格式化字符串，x2、x3 作為輸入目標變量傳參給 sscanf 函數，函數調用看起來就像是這樣：

sscanf(x0, x1, x2, x3);

再往下看 cmp w0, #0x2，比較返回值是否為 2，否則將跳轉到 40084c 處執行，也就是執行 explode 爆炸函數，由此更加確信上面所確定的調用方式，那么這里就一定是將兩個值格式化輸入到 x2、x3 所指向的棧空間里。

這樣我們就清楚了 x1 的類型是 char *，因此就可以使用 gdb 打印出來。

看來我們猜測的沒有錯，x2、x3 保存的變量就是整型變量，接下來就需要我們分析出來，程序要求我們輸入的兩個數字到底是什么了。為了幫助大家理解這里筆者先畫出 phase_3 的函數棧布局如下。

當程序調用完 sscanf 返回之后，phase_3 中的兩個整型變量已經被賦值，緊接著就看下面這段指令。

[注]：cmp w0, #0x2，這段指令是判斷 sscanf 是否執行成功，即是否寫入兩個變量，這里無需關心。

紅框部分開始首先取出棧中 sp + 28 位置的數據保存到 w0 寄存器中，即取出 num1，緊接著就是三個條件判斷：

若，num1(*(int *)(sp + 28)) == 3，則跳轉入 0x400854 地址執行；
若，num1(*(int *)(sp + 28)) == 4，則跳轉入 0x4008a0 地址執行；
若，num1(*(int *)(sp + 28)) == 2，則跳轉入 0x400884 地址執行；
若，num1(*(int *)(sp + 28)) 不是 3、4、2 中任何一個數，則執行 explode 爆炸函數。

根據這里的分析，我們確認了第一個數必須是 3、4、2，其中之一，那現在按照條件執行逐一分析。

9.1. 分支 1（num1 == 3）

程序跳轉入 400854 處執行，首先：

• ldr w2, [sp, #24]
  該行指令將棧中 sp+24 處取值 32b 加載入 w2 寄存器中，也就是 x0 寄存器的低 32 位部分；
  下一行指令不必多說，執行結束后 w0 中保存立即數為 0x6667；

• movk w0, #0x6666, lsl #16
  該行指令的作用是首先將立即數 0x6666 左移 16 位，再移入 w0 對應位置，而其它位上的值不變，簡單來說就是替換對應位置上的值。

  那么就是將 0x6666 左移 16 位保存進 w0 中，原來值不變那么 w0 此時保存的值將變為 0x6666_6667；
  [注]：該指令的詳細解釋見附錄。

• smull x0, w2, w0
  該指令會將兩個 32 位寄存器值相乘，并將結果寫入 64 位目標寄存器。這里就是將 w2 也就是輸入的第二個數與 0x6666_6667 相乘的結果保存進 x0 寄存器；

• asr x0, x0, #34
  這條指令就是將 x0 寄存器的值右移 34 位，并保存進 x0 寄存器；

• sub w0, w0, w2, asr #31
  該條指令用 w0 減去 w2 算術右移 31 位后的值作為結果存入 w0 寄存器中；

好了，梳理到這里可能已經有點凌亂了，讓我們來整理一下，筆者將上述步驟用流程圖簡要表述出來如下圖所示：

上面的 6 段匯編代碼實際上執行的操作就如下面表達式所表達的計算過程：

指令本身沒有難度，但為什么要這么做的，為什么要對我們輸入的數做這樣的計算過程。筆者這里也不賣關子直接說明上面這樣一個表達式的作用就相當于對 num2 除以 10 并保留其結果的整數位。

那么為什么這樣就等價于 ?num2 / 10? 呢？這是一個乘法除法取整優化的過程，旨在用乘法、移位等操作代替除法運算，因為計算機的除法電路效率通常較低，而使用乘法、移位等其它電路代替除法將會極大的提高程序的運行效率。

此處的 (num2 * 0x66666667) >> 34 對于無符號整數來說這一步的效果已經達到了 num2 / 10 向下取整的效果，但由于該計算方法在計算負值時會有誤差（誤差為 1），因此這里需要再加上一個偏移修正才是最終的近似整數除法的結果。

在此之前有必要再重新強調一下算術移位和邏輯移位的區別，如果有忘記的同學請先移步到附錄查看再回過來繼續閱讀。
[注]：為了不打斷文章邏輯，筆者將所有補充的小知識都歸納在文末的附錄里。

由于有符號負值的最高位是 1，而 32 位的負值右移 31 的結果將會是 0xFFFF_FFFF 即表示十進制的 -1，這里再減去 -1，也就是相當于加上 1 來彌補負值的誤差。有關乘法除法取整優化的詳細過程筆者將會在文末的附錄中展示，有興趣的同學可以閱讀該內容，這里只需要明白這里的操作就是 ?num2 / 10? ，即對 num2 除 10 并向下取整，最終的結果保存進 x0 寄存器。

ok，繼續接著往下看后面幾條指令，就比較簡單了。

• add w1, w0, w0, lsl #2
w0 邏輯左移 2 位，加上 w0 的值的結果保存進 w1 寄存器中，也就是相當于 w1 = w0 * 5，根據上文，也就是 w1 = ?num2 / 10? * 5；

• sub w1, w2, w1, lsl #1
w2 減去 w1 邏輯左移 1 后的結果保存到 w1 寄存器中，也就相當于 w1 = w2 - w1 * 2 = num2 - ?num2 / 10? * 10 = num2 % 10；

• add w0, w1, w0
w0 = w1 + w0 = num2 % 10 + ?num2 / 10?

接下來的兩行將會比較 w0 若等于 3 將會跳轉入 400844 處執行，也就是程序的出口位置。很好到這里這一個分支也就分析結束了。該條分支的流程圖如下所示。

9.2. 驗證分支1（num1 == 3）

當輸入的第一個數為 3 時，第二個數必須滿足 3 = num2 % 10 + ?num2 / 10?，那么滿足這個計算方法的值有 3、12、21、30，這里筆者只展示一種輸入結果，其余結果可有同學們自己驗證。

9.3. 分支2（num1 == 2）

此時跳轉入地址 0x400884 執行，該處指令首先取出棧中 sp + 24 位置的數據保存到 w0 中，即將 num2 保存到 w0 中。接著執行 eor w0, w0, w0, asr #3 指令，eor 是異或指令，asr 是算術右移指令，該條指令的邏輯表達式如下：

接下來對 w0 進行 and 運算即 w0 = w0 & 0x07，然后取出 sp + 28 的數據賦值給 w1，即取出 num1，比較 w0、w1 是否相等，若相等轉入 0x400844 執行，即正常退出，否則將執行 explode 爆炸函數，下圖將該情況下的流程畫了出來。

這里可以看到轉入 0x400844 執行即使得函數成功返回，也就是說當輸入的第一個數字 num1 的值為 2 時，第二個數只要滿足上述運算過程即可成功解除 phase_3。現在思路就很簡單，已知 num1 = 2，而且上一步是 w0 = w0 & 0x7，即截取其低 3 位，只要 w0 ⊕ (w0 >>> 3) 結果的低三位是 010b 即可，也就是要求第 1bit 和 4bit 位不同，其余對應位相同，0-3、2-5 位相同。

9.4. 驗證分支2（num1 == 2）

滿足這樣運算的數字有很多，這里筆者舉例幾個，如：2、11、25、52 等等。可以用 dgb 單步執行驗證筆者給出的結果是否正確，同樣這里筆者僅驗證一組值作為展示。

其實只要想找這樣值有非常多，這里列出由小到大順序的前 50 個結果。

[2, 11, 16, 25, 38, 47, 52, 61, 66, 75,80, 89, 102, 111, 116, 125, 130, 139, 144, 153,166, 175, 180, 189, 194, 203, 208, 217, 230, 239,244, 253, 258, 267, 272, 281, 294, 303, 308, 317,322, 331, 336, 345, 358, 367, 372, 381, 386, 395]

9.5. 分支3（num1 == 4）

此時跳轉入 0x4008a0 地址執行，這段代碼就非常簡單了，分別取出 num1、num2 保存到 w1、w0 寄存器中，再對 num2 & 0x7 賦值給 w2（即取其低 3 位），然后比較 w2、w1 是否相等，若相等則成功返回，若不相等則執行 ubfx x0, x0, #3, #3 指令。

這里簡單解釋一下 ubfx 指令，該指令是一條無符號位域提取指令，而這里的 ubfx x0, x0, #3, #3 表示，從 x0 的第 3 位開始（最低位是第 0 位），由低向高提取 3 位然后保存到 x0 寄存器中，然后剩余高位補 0，其邏輯運算等價于 x0 = (x0 >> 3) & 0x7。然后再比較 w1、w0 是否相同，若相同則成功返回，否則執行 explode 爆炸函數。

[注]：再舉一個例子，如 ubfx x0, x0, #4, #6，就表示從 x0 的第 4 位開始，由低向高提取 6 位保存到 x0 中，剩余高位補 0。

9.6. 驗證分支3（num1 == 4）

那么經過上面的分析，num1 只能取 2，num2 需要滿足運算規則，而滿足這樣的運算規則的 num2 同樣有很多，首先若要滿足 w2 == w1，num2 可以取像 4、12、20 等等（只要滿足 2~0b == 100b 即可），若要滿足后面的判斷條件 w1 == w0，num2 可以取 32、96等很多（只要滿足 5~3b == 100b 而 2~0b != 100b 即可），下面我們就驗證一下分析是否正確。

可以看到驗證都是通過的，那么 phase_3 到現在也是成功解除。

9.7. phase_3 函數總體計算框圖

phase_3 再經過 sscanf 之后的所有分支流程筆者將其畫了出來如下圖。

10. phase_4 函數

好了，接下來進入第 4 階段，階段預告，這段相比上一階段略有一點點難度，但還行需要各位讀者仔細分析。

10.1. 函數開始部分代碼分析

函數開始仍然是先保存函數調用時的舊的棧幀指針和返回地址，建立棧幀，然后保存當前寄存器狀態。接著將 x0 的值保存到 x19 中，這里 x0 正是我們所輸入的字符串。接著跳轉入 0x400300 地址執行。

這里看到 0x400300 地址的指令是一段我們非常熟悉的 adrp 指令，配合下面的 ldr 將內存中的值取出保存到 x17 寄存器，接著 x16 自加 0x30，也就是 X16 = X16 + 48，此時 X16 和 X17 中保存的值相同，隨即使用 br 跳轉入 x17 寄存器中保存的地址執行，這里我們用 gdb 打印出 x17 保存的地址是多少。

通過 gdb 打印的值可以看到地址是 4344256 （十進制數），通過進制轉換為十六進制就是 0x4249c0，我們轉到該地址查看一下是什么。

0x4249c0 地址可以看到是標準庫函數 strlen，該函數的聲明如下：

size_t strlen(const char *str)

該函數只有一個參數，那也就是使用的寄存器 x0 傳參，也就是獲取我們輸入的字符串長度，然后返回，從 strlen 函數末尾可以看出來最后對 x0 進行賦值操作，那么也就是說將計算出的字符串長度保存到 x0 然后返回到 phase_4 繼續執行。

回到 phase_4 后便將 x0 保存到 x20，然后比較 w0 與 0xa，若大于 10 則執行 0x400a3c 處的 explode 爆炸函數，由此可以推測，當輸入的字符串長度大于 10，將會導致炸彈爆炸，分析到這里，我們得到了第一個關鍵信息輸入的字符串長度一定是小于等于 10 位的。

接下來就將 w20 拷貝到 w1，再將 x19 拷貝到 x0，也就是用 x1 的低 32 位保存輸入字符串的長度，用 x0 保存我們所輸入的字符串。（在 phase_4 開始的時候將輸入的字符串首地址保存進了 x19），這兩步操作顯然就是為函數調用的傳參過程（使用寄存器傳參），果不其然接下來就是調用 encrypt_method1 函數，通過函數名我們大概知道這是一個加密函數，下面就來看看 encrypt_method1 函數的實現。

10.2. 1號加密函數（encrypt_method1）

同樣首先展示源代碼：

代碼開始同樣是保存之前的函數棧幀，并將 sp 保存到 x29 中，為當前函數建立棧幀。

x2 指向 sp + 0x10 的位置，這里是在當前函數棧中建立緩沖區。

接著執行 strb wzr, [x2, w1, sxtw] 指令，這段指令首先將 w1 符號擴展為 64b，然后將 wzr 的一個字節數據寫入 [x2 + (int64)w1] （此處的 (int64)w1 是經由 w1 符號擴展后的值）。

w1 是我們傳入的參數，其中保存的是我們輸入字符串的長度，因此該值一定是正數，經過符號擴展后，其高 32 位全部補 0，x2 保存的是棧中 sp + 0x10 位置的地址，加上輸入字符串長度后，并在該地址寫入一個字節的 0（\0 的 ASCII 碼正好是 0），因此很容易想到這步操作就是為 x2 表示的字符串變量或者字符數組設置結束標志 \0，這個步驟在棧中的變化如下圖。

一些指令的解釋：

• strb：將源寄存器中的字節數據寫入存儲器中；
• wzr：長度為 word 字的零寄存器 zero register，顧名思義，該寄存器中保存的全是 0；
• sxtw：符號擴展指令，即帶符號擴展指令，將 32b 帶符號擴展為 64b。

[注]：由于該指令較為簡單，介紹內容就插入文中了，應該不會影響閱讀。

接下來將 w1 邏輯右移 31b，再與 w1 相加賦值給 w3，w3 再算數右移 1b。

首先我們清楚 w1 保存的是我們輸入字符串的長度（其有限制：小于等于 10），這里筆者將用 len 表示我們輸入的字符串長度，也就是這里的 w1 == len，便于各位讀者理解。

這里兩行的作用等價于，w3 = (w1 + sign(w1)) >> 1 = (w1 + sign(w1)) / 2，由于我們輸入的字符串長度不存在負值，那么這里也就等價于 w3 = ?len / 2?，取字符串的中間位置。
[注]：這里的 sign() 表示當傳入的值為正數則返回 0，負數則返回 1，其用于對負數修正向下取整的除法結果。

然后比較 w1 與 0x01，若小于等會則跳轉入 0x40095c 處執行，此時的 w1 仍然是字符串長度。當字符串長度小于等與 0x1 時直接跳轉入 40095c 處執行，這將會導致加密函數不做實際操作將字符串原模原樣的返回，邏輯很簡單這里筆者就不仔細帶大家分析了，各位讀者這里可以自己看一下，繼續往下看吧。

• mov x4, x2
x2 保存的是已經設置好結束標志的緩沖區首地址，現在 x4 也保存了該緩沖區的首地址。接著將 x2 賦值為 0；

接下來筆者將會用 buf 表示在當前函數中創建的緩沖區。

• lsl x5, x2, #1
  這里就等價于 x5 = x2 * 2；
  [注]：已經看到這里的同學應該不需要筆者再重復這類簡單指令的詳細過程了。

• ldrb w5, [x0, x5]
  取出輸入字符串中某個位置的單個字符，w5 = input[x0 + x5]；

這里筆者用 input 表示該階段我們所手動輸入的字符串。

• strb w5, [x4], #1
  將 w5 保存進 x4 所指向的位置，然后 x4 自加 1，等價于 *(x4++) = w5；
  [注]：第一次執行到這里就等價于 buf[0] = w5。

接下來兩行對 x2 寄存器自加 1，并與 w3 比較，此時 w3 = ?len / 2?，當 w3 > w2 時就回到 4008f0處執行。為了便于讀者理解，筆者寫了一段偽代碼，這幾行指令的效果等價于下面這段 C 代碼。

for (int i = 0; i < len / 2; i++) {char c1 = input[i * 2];buf[i] = c1;
}

通過代碼我們清楚了這段指令的作用其實就是將輸入字符串中偶數位置字符提取出來保存到 buf 中，這里 0 號位置也被算作是偶數位置。

這里簡單解釋一下 csinc 指令（ Conditional Select Increment），指令格式如下：

CSINC <Rd>, <Rn>, <Rm>, <cond>

• 如果條件 cond 為真，則：Rd = Rn
• 如果條件 cond 為假，則：Rd = Rm + 1

在這里就是根據上一條的 cmp w3， #0x0 的結果來判斷條件是否成立，當 w3 > 0x0 時，w5 = w3，否則 w5 = wzr + 1 = 0 + 1 = 1。

然后再當 w1 <= w5 時將跳轉入 40094c 處執行，這樣將會直接直接執行 strcpy，將 buf 內容拷貝給輸入的字符串 input，即用 buf 替換我們輸入的字符串 input，然后就直接退出 encrypt_method1 函數。

因此這里的作用就是為了處理輸入的字符串長度小于 3 的情況，不過不用在意，通過后面的分析你就會發現我們所輸入的字符串長度絕對不會小于 3，因此這里僅僅作為異常處理而存在的條件代碼。繼續往下看。

• sub w4, w1, w5
  w4 保存 w1 - w5 的值，也就是 w4 = len - ?len / 2?，記錄剩余要處理的字符數量；

• sub w2, w5, w3
  經過上文分析只要我們輸入字符串的長度大于 2，那么 w5 一定是等于 w3，都等于 ?len / 2?，因此這里常規情況 w2 == 0；

• add x2, x0, w2, sxtw #1
  x2 = x0 + (int64)w2 >> 1 == x0 + (int64)w2 * 2，定位到字符串起始位置；

• add x2, x2, #0x1
  x2 自加 1，定位到奇數起始位置。

首先執行 x1 = 0；x3 = sp + 0x10，即 x3 保存緩沖區 buf 起始地址；

• add x5, x3, w5, sxtw
  x5 = x3 + (int64)w5，此時 x5 將指向 buf 的空余起始位置；

• lsl x3, x1, #1
  x3 = x1 * 2；

• ldrb w3, [x2, x3]
  w3 = *(x2 + x3)，取出奇數位置上的值；

• strb w3, [x5, x1]
  *(x5 + x1) = w3，將輸入字符串奇數位置的值賦值到 buf 的空余位置里；

接下來 x1 自增 1，只要 x1 不等于 x4，也就是只要 x1 不等于剩下未處理的字符個數就繼續執行上述過程，直到將所有奇數位置字符全部提取拷貝結束為止。

• add x1, sp, #0x10
  x1 重新指向 buf 的起始地址；此時 x0 依然保存 input 首地址。

接下來調用 strcpy 函數，其函數聲明如下：

char *strcpy(char *dest, const char *src);

該函數的作用是將 src 字符串逐個拷貝給 dest 字符串里，這里的作用就是將 x1 所指向的字符串 buf 拷貝到 x0 所指向的 input 字符串，接下來 encrypt_method1 函數執行正常退出。

筆者將用一段 C 語言偽代碼描述上述過程：

int x4 = len - len / 2;
char *x2 = input;
x2 += 1;
int x1 = 0;
int *x5 = buf + len / 2;
int x3 = 0;for (; x1 != x4;) {x3 = x1 * 2;char w3 = *(x2 + x3);*(x5 + x1) = w3;x1++;
}strcpy(x0, x1);return ;

那么到這里 encrypt_method1 函數的邏輯也就非常清晰了，就是將我們輸入的字符串更變為偶數位置字符在前，奇數位置字符在后的順序，如：

input = "acbdef",	len = 6;encrypt_method1(input, len);input == "abecdf"

此時再回到 phase_4 函數。

經過 encrypt_method1 函數的處理此時 input 字符串順序已經改變。再重新將 input 字符串首地址保存到 x0，同時將 len 保存進 w1，準備調用函數 encrypt_method2。

10.3. 2號加密函數（encrypt_method2）

首先貼出 encrypt_method2 完整代碼。

開局首先做字符串長度檢查，當字符串長度 <= 0 為時直接不做任何操作返回。想必這當然不是我們所希望的結果。

這幾段內容同樣是保存舊棧指針，并保存寄存器狀態，為函數返回后的環境恢復做準備。

將輸入字符串 input 首地址保存到 x19 寄存器；

x21 = x0 + (int64)w1，計算字符串的結束位置。

這里又是我們熟悉的獲取全局變量的操作，這里的執行結束 x22 = 0x4a0000 + 0x58 = 0x4a0058，接下來直接跳轉入 4009b0 地址處執行。

開始時候就將 input 字符串首地址保存進了 x19，這里又將其值保存進 x20 寄存器；

• ldrb w0, [x19]
  接著 w0 = [x19]，取出 x19 地址處的值，保存進 w0 中；

• sub w0, w0, #0x61
  w0 = w0 - 0x61，指令很簡單，但這個 0x61 是不是很熟悉，沒錯它就是 a 的 ASCII 碼值；

• and w0, w0, #0xff
  截取 w0 的低 8 位；

• cmp w0, #0x19
  比較 w0 與 0x19 結果，也就是比較與 25 的結果，因為字母一共有 26 個；

• b.ls 400990
  當 w0 < 25 時跳轉入 400990 處執行，否則將會執行下面調用爆炸函數。

很好！不枉筆者一路的提示，沒錯這段代碼就是校驗當前值是否是小寫英文字母，如果不是將會執行爆炸函數。接下來看看跳轉到 400990 處做什么操作了。

• ldrb w1, [x20]
  取出 x20 處的值保存進 w1，若是第一次執行到這里，那么就是取出 input 字符串第一個字符；

• ldr x0, [x22, #8]
  取出 x22 + 8 處指向的值，保存進 x0。首先在之前的分析中我們已經知道了 x22 保存的值是 0x4a0058，那么來看看 0x4a0058 + 8 到底是個什么東西吧；

可以看到這里筆者先是猜測這里 0x4a0058 + 8 是不是保存的一個字符串，也就是 (char *) 格式，發現啥也不是；

那么是不是一個字符呢？ *(char *) ，發現同樣啥也不是；

這時候筆者發現后面又對 x0 做了一次取值操作，那么這里一定保存的是一個地址，而非常規字符或者是普通值；

此時筆者猜測會是一個指向字符串首地址的指針嗎？(char **)，欸！沒錯，的確是的，我們打印出解引用的值這的確是一個字符串；

很好，那么這里的確保存的是一個指向字符串首地址指針的值，這里我們打印出來這個地址，*(int *) 格式，發現這個指針值是 4605936（十進制），不錯，那么此時 x0 中保存的值就是 4605936。

• add x0, x0, x1
  x0 = x0 + x1，x1 此時保存的是 [x20] 也就是取出來的 input 字符串其中的一個字符，這里也就是 x0 加上這個字符的 ASCII 碼值，保存進 x0；

• ldurb w0, [x0, #-97]
  這里就是取出 x0 - 97 指向的值保存進 w0，等等，97 == 0x61，沒錯又是 a 的 ASCII 值。你想到了嗎？哦！我明白了，上一步給 x0 加上了我原本輸入字符串字符的 ASCII 碼值，現在又減去 a 的 ASCII 值，那不就是相當于加上了原本字符與 a 的位置差，即 x0 + 'c' - 97，例如 x0 + 'c' - 'a' = x0 + 2，那么來看一下假設取出來的字符是 c，看看 w0 = [x0 + 'c' - 97] = [x0 + 2] 是個什么值。

• strb w0, [x20]
  緊接著用剛剛取出來 w0 寫入 x20 指向的位置，看來是用這段字符串對應位置上的字符去替換按照小寫字母排序的字符；

• add x19, x19, #0x1
  x19 寄存器自加 1，x19 開始是指向 input 字符串的首地址，看來是準備遍歷整個 input 字符串了；

• cmp x19, x21
  x19 是指向 input 某個字符的指針，而 x21 則是保存的 input 最后一個字符地址，用他倆做對比；

• b.eq 4009d0
  若上面比值相等，則跳入這個地址執行，也就是到了函數尾部退出位置，那么看來的確是在遍歷整個 input 字符串了；

在接下來的這段指令上文已經分析過了，就是校驗當前字符是否是小寫英文字母，若不是則執行爆炸函數。

漂亮，到這里 encrypt_method2 加密函數也被我們分析結束，而它的作用就是將傳入的字符串按照 "qwertyuiopasdfghjklzxcvbnm" 這段字符串對應位置上的字符去替換按照小寫字母排序的字符；

舉例說明：

input = "abcd";encrypt_method2(input, len);
// 執行結束后 input 將變為下面結果
input == "qwer"

10.4. 函數后半段代碼分析

好了讓我們回到 phase_4 函數繼續分析。

執行完 encrypt_method2 函數后，又見到了熟悉的兩段指令，adrp 從全局變量中取值保存進 x1，接下來將 x19 的值保存進 x0，也就是將 input 字符串首地址保存進 x0。

接下來便是調用 strcmp 函數，該函數聲明如下：

int strcmp(const char *str1, const char *str2)

那么這里就是比較 x0 和 x1 所指向的兩個字符串是否一致，當函數返回值為 0 時表示兩個字符串相同，函數正常返回，若不相同則跳轉去執行爆炸函數。

我們的目的明確了，就是最終需要這兩個字符串相同，那么先來看看 x1 中保存的到底是什么字符串：

ok，因為我們需要的字符串 isggstsvke，此時就只需要反過來推導每個加密函數處理之前是什么字符串最終即可得到所需要輸入的字符串內容。

首先在 encrypt_method2 函數中提供的加密字符串中查找對應位置的字符，得到 hloolelwrc，筆者已經將推導過程以及加密字符串所一一對應的常規序列小寫英文字母對比圖也在下方，各位應該會很容易看出來。

再接下來就將 hloolelwrc 字符串從中間切分，一個偶數部分，一個奇數部分字符排序，將最終得到 helloworlc，也就是我們最終需要輸入的字符串內容。

10.5. 驗證結果

ok，接下來我們來驗證一下我們的推測結果：

很棒，這的確是函數所要求輸入的字符串，到此 phase_4 函數也分析結束。

11. phase_5 函數

和往常一樣先貼出 phase_5 所有代碼：

11.1. read_int 函數

可以看到函數最開始調用了一個 read_int 函數，從函數名來猜測函數作用就是讀取一個整數，跳轉到該函數位置來看看是不是這樣。

這里看到函數內部僅調用了一次 sscanf 函數，該函數聲明如下：

int sscanf(const char *str, const char *format, ...)

傳入的第二個參數也就是其上方對 x1 的賦值，這里看一下 x1 保存了什么樣的格式字符串。

看來這里的確僅僅是從標準輸入中讀取一個整數，并輸出給 x2 所指向的當前函數棧。

最后再通過 ldr w0, [sp, #28] 將棧中數據保存進 w0 然后函數返回。然后折返回 phase_5 函數繼續查看接下來的內容。

可以看到這里有是熟悉的準備從內存中讀取值的操作，經過三次的對 x1 寄存器賦值，此時 x1 = 0x4a0000 + 0x58 + 0x18 = 0x4a0070，同時此時 x0 保存的是經過格式轉換后的我們輸入的一個整數值，向 func_5 傳入參數并調用該函數。

11.2. func_5 函數

• cbz x1, 400ab8
  func_5 函數第一行就是判斷當 x1 為 0 時直接跳轉入 400ab8 地址處執行。而同時也看到 400ab8 處也是平平無奇的僅將 w0 寄存器賦值為 0 后就直接退出函數，請記住這個平平無奇的地方，這是我們找到的第一個函數出口，在當前函數會有大作用。

接下來的幾行是按慣例保存舊的函數棧幀，并建立當前函數棧幀，這里筆者就不再過多贅述，往下繼續看。

這里就是將 w0 的值保存進 w20，也就是將我們所輸入的整數值保存進 w20，接著將所傳入的 x1 所保存的地址保存進 x19，再接著讀取 x1 地址所指向的數值并保存進 w0；

這里看到當 w0 == w20 時將會跳轉入 400a98 處執行調用爆炸函數，因此我們絕不能讓 w0 和 w20 值相同；然后讀取 x19 指向的值保存進 w0，再比較 w0 與 w20 的關系，根據上文在 w0 是內存中的值，而 w20 表示我們所輸入的數字（在未被函數修改之前）。

接下來的代碼段有這幾處需要我們關注，筆者先用橫線劃出來，這些涉及函數遞歸、以及函數出口的位置。

• cmp w0, w20
  b.le 400aa0 <func_5+0x54>
  這里的 w0 保存的是從 x1 讀出來的值，下一行當 w0 <= w20 時，將會跳轉入 400aa0 處執行代碼。這里我們先繼續看假如不發生跳轉會發生什么；

• ldr x1, [x19, #8]
  mov w0, w20
  bl 400a4c <func_5>
  這里讀取 x19 + 8 處的值保存進 x1，再將 w20 保存進 w0 然后遞歸調用 func_5 函數；

當這一層遞歸退出之后這里將 w0 << 1 也就等價于 w0 = w0 * 2，然后恢復函數棧并退出。到這里第二個函數出口被我們找到了。

接下來再看在 b.le 400aa0 <func_5+0x54> 發生跳轉后會發生什么？

• ldr x1, [x19, #16]
  mov w0, w20
  bl 400a4c <func_5>
  這里讀取 x19 + 16 處的值保存進 x1，再將 w20 保存進 w0 然后遞歸調用 func_5 函數；當這層遞歸調用退出后將會繼續往下執行；

• lsl w0, w0, #1
  add w0, w0, #0x1
  b 400a8c <func_5+0x40>
  這里將 w0 = w0 * 2，在將 w0 自加 1，然后跳轉入 400a8c 處執行。而 400a8c 處是恢復函數棧幀，并返回。那么第三個函數出口被我們找到了。

好了，這樣一來 func_5 函數就被我們分析完了，通過這里的分析其實也找到了 func_5 函數第二個參數也就是傳入的 x1 其實就是一個二叉樹節點的地址，但是目前這個二叉樹本身的結構我們還不得而知。func_5 函數總的處理流程如下圖。

okok，我知道你會說“這就完了？都完全沒搞清楚在干嘛！”，我會回你“沒錯，不過先不要著急，等會就明白了，暫時我們沒法做更多的分析。”

先回到 phase_5 函數中看看后續內容。

這里看到在退出 func_5 函數后，phase_5 函數比較 w0 是否等于 3，如若不是將會調用 explode 爆炸函數，如果是則正確返回，那么我們清楚了，我們需要 func_5 函數最終將 w0 的值修改為 3 才可以，依據此就可以繼續進入 func_5 中反推出需要輸入的值。

• 分析思路：
  • (1) 找到 func_5 中所有可能修改 w0 的地方；
  • (2) 分析如何修改才可以讓 w0 在最終返回的時候值為 3；
  • (3) 根據以上兩點推導需要輸入的整數值。

關于第一點分析思路：
首先我們在 func_5 中找到了 3 處對 w0 表示輸入值的時候修改內容，并且恰好都位于函數的各個函數出口位置。

• 在函數第一出口位置的修改操作是將 w0 賦值為 0；
• 在函數第二出口位置的修改操作是將 w0 原本的值翻倍即 * 2；
• 在函數第三出口位置的修改操作是將 w0 原本的值翻倍即 * 2，然后再為其加 1。

關于第二點分析思路：

如何讓 w0 的最終值是 3，關于這一點筆者的思路是：

• (1) 首先讓 w0 經過第一出口位置的修改處理變為 w0 = 0；
• (2) 接在再經過第兩次第三出口位置的修改處理，將會分別變為：
  • 第一次 w0 = w0 * 2 = 0，w0 += 1，這時 w0 == 1；
  • 第二次 w0 = w0 * 2 = 2，w0 += 1，此時 w0 == 3。
• (3) 此時正好完全退出 func_5 函數。

再經過這樣的修改處理后 w0 順利的變為 3，不知道還有沒有其它方式讓 w0 變為 3 的，目前筆者沒有想到，似乎這是唯一一種情況？筆者選擇的路線遞歸調用修改 w0 的效果應該像下圖一樣。

關于第三點分析思路：

根據上面所計劃的處理流程，要按照上面計劃的執行順序完成的關鍵在于要在進入 func_5 函數后讓這里 w0 <= w20 先后兩次成立是關鍵，然后才能轉入我們所希望的這條分支。

那么，w20 我們知道是輸入的數字，w0 呢？是什么？不錯，正是 x1 所指向的內存單元的數值，我們先來看看第一次傳入的數值是多少：

ok，第一次我們設計讓輸入的數字要大于等于 49，然后接著再取 x19 + 16 地址保存的值作為參數也就是 func_5(int input, int* num_p) 中的 num_p。

可以看到，按照計劃第一次遞歸調用傳入的 x1 = num_p = 4849824。進入遞歸之后，看看這時候的 w0 <= w20 階段的 w0 是什么值：

此時希望繼續進入能讓 w0 加 1 的分支遞歸，那么繼續讓我們輸入的數字比 88 大即可，現在來到第二次遞歸調用，繼續看看這次遞歸進去的 x1 是什么。

好的，這次遞歸進去的 x1 值是 4849920，再次來到命運的分岔口判斷 w0 <= w20，由于我們現在已經遞歸調用了兩次 w0 自加 1 這里退出的函數，那么這次就不能再調用這里，否則得到 w0 結果就太大了，因此這里我們選擇讓該條件失效，也就是 w20 要小于等于 w0，先看看這里的 w0 是多少吧。

那看來我們的數字就是要求 88 < input <= 91，別忘記了，在此之前還有一個判斷相等的條件，還記得嗎， func_5 函數要求這兩個值不能相等，因此我們所輸入的值只能是 88 < input < 91。

也就是當 w0 <= w20 不成立，就會繼續往下執行。

• ldr x1, [x19, #8]
  mov w0, w20
  bl 400a4c <func_5>
  這里加載 x19 + 8 所指向內存地址的值給 x1，然后再次遞歸調用 func_5，查看這里傳入進去的 x1 是什么。

哦！是 0，終于來到了轉折點，還記得 func_5 第一行就是判斷當 x1 等于 0 時，將 w0 置 0 然后返回。

這一層遞歸退出，返回上一層繼續執行:

返回后，繼續執行 w0 = w0 * 2，結果 w0 == 0，然后返回。退出當前遞歸，繼續返回上一層執行：

終于來到我們想要的地方，此時 w0 = w0 * 2 + 1，即此時 w0 == 1，退出當前遞歸函數，返回上一層繼續執行：

終于來到我們想要的地方，此時 w0 = w0 * 2 + 1，即此時 w0 == 3，函數正常退出，func_5 執行結束。我們得到了想要的 3。

其實通過查找所有的二叉樹數據你將會得到這樣一顆二叉樹：

我們所設計的 func_5 遞歸調用流程圖如下，與筆者開始猜測的流程圖有所不同，這才是真正的工作過程。

11.3. 驗證結果

好的，分析到這里那就已經清楚了 phase_5 所要輸入的值是 88 < input < 91，即 89、90 這兩個數字滿足，下面驗證一下結果。

沒有問題，成功解除 phase_5。

12. 總結

這次拆炸彈實驗一共有 6 個 phase，分別考查了我們的匯編指令閱讀、分析能力，以及 GDB 調試工具使用能力，在邏輯上考查了基本匹配、簡單邏輯計算、分支跳轉、字符串處理、遞歸分析，考查范圍算是覆蓋了計算機語言的基礎內容，總體來說難度適中，適合作為學習 Chcore 前的準備預熱。

#附——本文涉及到的相關知識點詳解

#01. MOVK 指令

MOVK 指令（move with keep）

這里的 K 是 keep 的意思，它將一個16 位的立即數寫入目標寄存器的指定位置（通過左移 LSL 指定），但不影響寄存器中其他位。

32 位模式：(sf == 0 && hw == 0x)

MOVK <Wd>, #<imm>{, LSL #<shift>}

64 位模式：(sf == 1)

MOVK <Xd>, #<imm>{, LSL #<shift>}

• Wd：是通用目標寄存器的 32 位名稱，在 “Rd” 字段中編碼；
• <imm>：是 “imm16” 字段中編碼的 16 位無符號立即數，范圍為 0 到 65535；
• <shift>：對于 “32 位”模式：是向左移動直接位數，0（默認值）或 16，在 “hw” 字段中編碼為 <shift>/16 。對于“64 位”變體：是向左移動的量，為 0（默認值）、16、32 或 48，在“hw”字段中編碼為 <shift>/16；
• <Xd>：是通用目標寄存器的 64 位名稱，在“Rd”字段中編碼。

#01.1. MOVK 示例：

這里假設 x0 寄存器的初始值如下：

X0 = 0xFFFF00000000FFFF

執行如下指令

MOVK X0, #0x1234, LSL #16

這里會把 X0 中位于 bit 16 到 bit 31 之間的 16 位替換為 0x1234，X0 的其他位（0–15 和 32–63）保持不變。

那么指令執行結束后 x0 寄存器的值將變為如下：

X0 = 0xFFFF00001234FFFF

#02. 算術移位 & 邏輯移位

ASR：Arithmetic Shift Right（算術右移）
保持符號位，用于有符號數。 將數值向右移動 N 位，左邊補原符號位（符號擴展）

R0 = -8     = 0b11111111_11111111_11111111_11111000
ASR R0, R0, #2
=> R0 = -2  = 0b11111111_11111111_11111111_11111110

符號位 1 被復制到左邊，結果還是負數。

LSR：Logical Shift Right（邏輯右移）
不管符號位，左邊補 0，用于無符號數。將數值向右移動 N 位，左邊補 0。

R0 = -8     = 0b11111111_11111111_11111111_11111000
LSR R0, R0, #2
=> R0 = 0x3FFFFFFE = 正數（高位補 0）

結果變成一個巨大的正數，因為你破壞了原符號 。

常見誤區

誤區	正確做法
對有符號數用 LSR	? 結果會完全錯
用 ASR 操作無符號整數	? 可能導致錯誤擴展
忘記區別左補 0 還是左補符號位	? 記住：ASR 補符號，LSR 補 0
Verilog 中的符號易混淆	邏輯右移 >>， 算術右移 >>>，左移同理

#03. 乘法除法取證優化

匯編和編譯器優化中經常使用到該方法，尤其是為了避免使用除法指令（因為硬件除法慢）。整數除法（尤其是帶符號的除法）在處理器中相對較慢。現代編譯器（如 GCC、Clang）會將：

int q = n / d;

優化為：

int q = ((int64_t)n * magic) >> shift;

其中 magic 和 shift 是為特定除數 d 計算出的常量，使結果與原本的除法 在整數范圍內是等價的。該方法是來自于經典書籍《Hacker's Delight》中第 10 章給出的算法理論以及《Division by Invariant Integers using Multiplication》這篇論文中的論述理論。

這兩篇文章中詳細的介紹了如何根據除數 d 來確定特定的 Magic 數，以及要移動的位數 Shift。筆者就不在這里解讀文章了有興趣的同學可以查閱這兩篇文章細細閱讀一番，必定會收獲不少。

從 《Hacker's Delight》 這本書中第 10 章，能夠找到為整除 5 構建的 Magic number = (2³³ + 3) = 0x66666667，偏移數 Shift = 33，當被除數是負值時則需要 +1 修正結果（這一步可以通過移位指令和加法指令的配合完成，正如書中代碼這樣）。

那么通過文獻我們知道了整除 5 的 magic number 是 0x6666_6667，shift 是 33，那么整除 10 也就簡單了，不就是整除 5 之后再除 2 嘛，那就讓計算結果再右移 1bit 不就好了，這也就是之前代碼中右移 34bit 的原因。

這里是筆者寫的一個簡單的 C 語言版本驗證該算法的代碼：

#include <stdio.h>
#include <stdint.h>int main() {// 任意一個測試值// int32_t n = -123456789;int32_t n = -76;int32_t M = 0x66666667;  // 魔數 for d = 10// 完整 64 位乘法int64_t full = (int64_t)n * M;// 從完整乘積中提取高/低 32 位int32_t high = (int32_t)(full >> 32);        // 模擬 mulhs(n, M)int32_t low  = (int32_t)(full & 0xFFFFFFFF); // 低 32 位// 方法 A：經典 Hacker’s Delight 算法int32_t q1 = (int64_t)(full >> 34); // 全64位乘法右移34q1 -= high >> 31; // 處理負數的誤差// 方法 B：只取高32位再右移2位（等價做法）int32_t q2 = high >> 2;q2 -= high >> 31; // 處理負數的誤差printf("n = %d\n", n);printf("M = 0x%X\n", M);printf("64-bit full product = 0x%llX\n", (unsigned long long)full);printf("\n");printf("Method A (64-bit >> 33)          : %d\n", q1);printf("Method B (high >> 2)              : %d\n", q2);// 驗證正確性printf("\nActual division n / 10            : %d\n", n / 10);return 0;
}

該函數的執行結果如下：

.\'test.exe'
n = 76
M = 0x66666667
64-bit full product = 0x1E66666694Method A (64-bit >> 33)          : 7
Method B (high >> 2)              : 7Actual division n / 10            : 7

#04. 常見跳轉條件碼詳解

條件碼	描述	滿足條件	通常用于
cmp	比較，實際上等價于 subs x, y —— 它會執行 x - y，之后的條件跳轉指令（如 b.eq, b.lt 等）根據這些標志位來決定是否跳轉。	不會改變兩個寄存器的值即兩個寄存器不會變化，但是其結果會影響 cpsr 狀態寄存器的標記值（n，z，c，v）
b.le	小于等于（less than or equal to），執行標號，否則不跳轉	Z == 1 || N != V	x ≤ y（帶符號）
b.ge	大于等于（great than or equal to），執行標號，否則不跳轉	N == V	x ≥ y（帶符號）
b.ne	not equal（不等）	Z == 0	不相等時跳轉
b.gt	大于（greater than），執行標號，否則不跳轉	Z == 0 && N == V	x > y（帶符號）
b.lt	小于（less than），執行標號，否則不跳轉	N != V	x < y（帶符號）
b.eq	等于（equal to），執行標號，否則不跳轉	Z == 1（Zero標志位）	相等時跳轉
b.hi	無符號大于，執行標號，否則不跳轉	C == 1 && Z == 0	x > y（無符號）
b.hs	higher or same（≥，無符號）	C == 1	x ≥ y（無符號）
b.lo	lower（小于，無符號）	C == 0	x < y（無符號）
b.ls	lower or same（≤，無符號）	C == 0 || Z == 1	x ≤ y（無符號）

[注]：aarch64 的一些條件跳轉指令。

#完