程序设计中的分支表(branch table)或跳躍表(jump table)是一種利用表格來轉移程式控制權(分支)的方式,表格中的內容就是對應的分支指令。這屬於多路分支。若使用汇编语言撰寫程式,常會用到分支表,不過也可能是由編譯器產生,特別是實現最佳化的,且其數值很相近的情形。
典型的實現
分支表包括許多的分支指令,而分支到這些分支指令的方式是是用其序列索引乘以分支指令長度當作分支指令的偏移量,此作法的原因是机器语言的分支指令長度是固定的,而且若很容易轉換為序列索引值,此方式特別有效。此方式包括三個步驟:
可能會做輸入資料的数据确认,確認資料是正確可接受的(若輸入資料是位元組,而且已有256個元素的轉換表,直接求得以下的偏移量,此步驟可以和第二步驟合併,不會有額外運算)。若很確定輸入資料都正確,也可以省略此步驟。
將資料轉換為分支表中會用到的偏移量,可能會用到乘法或是位操作(乘以二的次方,速度較快),要乘的數則視分支指令長度而定。若使用靜態的轉換表,也可以在轉換表編譯時就將乘法考慮進去,以避免重複的運算。
用分支表的基底位置加上偏移量,分支到計算出來的位置。這會用在程式計數器加上偏移量的加法(也有可能有些指令集架構下,分支指令會使用特殊的索引暫存器。最後的位置會指向分支表中分支到某程式的指令。
以下的偽代碼說明此概念
... validate x / transform x to 0 (invalid) or 1,2,3, according to value..) /
y = x 4; / multiply by branch instruction length (e.g. 4 ) */
goto next + y; / branch into 'table' of branch instructions /
/ start of branch table /
next: goto codebad; / x= 0 (invalid) /
goto codeone; / x= 1 /
goto codetwo; / x= 2 /
... rest of branch table
codebad: / deal with invalid input /
相關條目
- 分派表,分支表的另一個名稱,用在時。
- 函数指针陣列,也可以用作分支表。
- 間接分支
- 查找表
- ,高階語言中的條件指令,可以產生分支表。
- 虛擬方法表,另一種跳躍表的名稱,動態分派函式指標。
參考資料
外部連結
*[https://web.archive.org/web/20120212110151/http://www.netrino.com/node/137] Examples of, and arguments for, Jump Tables via Function Pointer Arrays in C/C++
*[http://www.eventhelix.com/realtimemantra/Basics/CToAssemblyTranslation3.htm] Example code generated by 'Switch/Case' branch table in C, versus IF/ELSE.
*[http://www.eventhelix.com/realtimemantra/Basics/CToAssemblyTranslation2.htm] Example code generated for array indexing if structure size is divisible by powers of 2 or otherwise.
*[http://www.rmbconsulting.us/Publications/PointerToFunction.pdf] "Arrays of Pointers to Functions" by Nigel Jones
评论 (0)