什麼是蹦牀功能？

Question

在最近的工作討論中，有人提到了蹦牀功能。

我已閱讀說明Wikipedia。對功能進行總體概括就足夠了，但我希望更具體一些。

你有簡單的代碼片段可以說明蹦牀嗎？

Answer 1

我給你舉個例子，我在網上游戲的反作弊補丁中使用。

我需要能夠掃描遊戲加載的所有文件以進行修改。因此，我發現要做到這一點的最強有力的方法是爲CreateFileA使用蹦牀。所以當遊戲啓動時，我會使用GetProcAddress找到CreateFileA的地址，然後修改函數的前幾個字節並插入彙編代碼，這些代碼會跳轉到我自己的「蹦牀」函數，我會做一些事情，並且那麼在我的jmp代碼之後，我會跳回到CreateFile中的下一個位置。爲了能夠可靠地做到這一點有點棘手，但基本概念是鉤住一個函數，強制它重定向到另一個函數，然後跳回到原始函數。

編輯：微軟有一個這種類型的東西，你可以看看的框架。所謂的Detours

Answer 2

這裏的嵌套函數的例子：

#include <stdlib.h> 
#include <string.h> 
/* sort an array, starting at address `base`, 
* containing `nmemb` members, separated by `size`, 
* comparing on the first `nbytes` only. */ 
void sort_bytes(void *base, size_t nmemb, size_t size, size_t nbytes) { 
    int compar(const void *a, const void *b) { 
     return memcmp(a, b, nbytes); 
    } 
    qsort(base, nmemb, size, compar); 
} 

compar不能是一個外部函數，因爲它使用nbytes，其中sort_bytes通話過程中才存在。在某些體系結構中，一個小的存根函數 - 蹦牀 - 在運行時生成，並且包含調用sort_bytes的當前的的堆棧位置。當被調用時，它跳轉到compar代碼，傳遞該地址。

像PowerPC這樣的體系結構不需要這樣的混亂，ABI指定函數指針實際上是一個「胖指針」，一個包含指向可執行代碼的指針和另一個指向數據的指針的結構。但是，在x86上，函數指針只是一個指針。

Answer 3

還有如維基百科上描述的「蹦牀」的LISP感：

用在一些LISP實現中， 蹦牀是一個循環，反覆地 所調用咚返回功能。 A 單蹦牀足以讓 表達一個 節目的所有控制轉移;如此表達的節目是 蹦牀或「蹦牀式」; 轉換程序爲trampolined 風格是蹦牀。 Trampolined 功能可以被用來實現 尾 面向堆棧的語言

遞歸函數調用讓我們說，我們使用JavaScript和希望寫在延續傳遞風格天真斐波那契功能。我們這樣做的原因是不相關的 - 例如將Scheme移植到JS上，或者使用我們必須使用的CPS來調用服務器端函數。

所以，第一次嘗試

function fibcps(n, c) { 
    if (n <= 1) { 
     c(n); 
    } else { 
     fibcps(n - 1, function (x) { 
      fibcps(n - 2, function (y) { 
       c(x + y) 
      }) 
     }); 
    } 
} 

但是，隨着n = 25運行這個在Firefox提供了一個錯誤 '太多的遞歸調用！'。現在，這正是問題（缺少Javascript中的尾部調用優化），因此可以解決蹦牀問題。讓我們用return指令（thunk）來調用該函數，而不是對函數進行（遞歸）調用，以循環方式解釋。

function fibt(n, c) { 
    function trampoline(x) { 
     while (x && x.func) { 
      x = x.func.apply(null, x.args); 
     } 
    } 

    function fibtramp(n, c) { 
     if (n <= 1) { 
      return {func: c, args: [n]}; 
     } else { 
      return { 
       func: fibtramp, 
       args: [n - 1, 
        function (x) { 
         return { 
          func: fibtramp, 
          args: [n - 2, function (y) { 
           return {func: c, args: [x + y]} 
          }] 
         } 
        } 
       ] 
      } 
     } 
    } 

    trampoline({func: fibtramp, args: [n, c]}); 
} 

Answer 4

對於C，蹦牀將是一個函數指針：

size_t (*trampoline_example)(const char *, const char *); 
trampoline_example= strcspn; 
size_t result_1= trampoline_example("xyzbxz", "abc"); 

trampoline_example= strspn; 
size_t result_2= trampoline_example("xyzbxz", "abc"); 

編輯：更深奧的蹦牀將被隱式由編譯器生成。其中一種用途就是跳轉表。 （雖然顯然有更復雜的，你開始嘗試生成複雜的代碼。）

Answer 5

我目前正在試驗如何實現方案解釋器的尾部呼叫優化，所以此刻我想圖看看蹦牀對我來說是否可行。

據我所知，它基本上只是一系列由蹦牀功能執行的函數調用。每個函數都稱爲thunk，並返回計算中的下一個步驟，直到程序終止（空繼續）。

下面是第一段代碼，我寫來提高我的蹦牀的理解：

#include <stdio.h> 

typedef void *(*CONTINUATION)(int); 

void trampoline(CONTINUATION cont) 
{ 
    int counter = 0; 
    CONTINUATION currentCont = cont; 
    while (currentCont != NULL) { 
    currentCont = (CONTINUATION) currentCont(counter); 
    counter++; 
    } 
    printf("got off the trampoline - happy happy joy joy !\n"); 
} 

void *thunk3(int param) 
{ 
    printf("*boing* last thunk\n"); 
    return NULL; 
} 

void *thunk2(int param) 
{ 
    printf("*boing* thunk 2\n"); 
    return thunk3; 
} 

void *thunk1(int param) 
{ 
    printf("*boing* thunk 1\n"); 
    return thunk2; 
} 

int main(int argc, char **argv) 
{ 
    trampoline(thunk1); 
} 

結果：

meincompi $ ./trampoline 
*boing* thunk 1 
*boing* thunk 2 
*boing* last thunk 
got off the trampoline - happy happy joy joy ! 

Answer 6

讓我補充幾個例子與蹦牀實現的階乘函數，用不同的語言：

斯卡拉：

sealed trait Bounce[A] 
case class Done[A](result: A) extends Bounce[A] 
case class Call[A](thunk:() => Bounce[A]) extends Bounce[A] 

def trampoline[A](bounce: Bounce[A]): A = bounce match { 
    case Call(thunk) => trampoline(thunk()) 
    case Done(x) => x 
} 

def factorial(n: Int, sum: BigInt): Bounce[BigInt] = { 
    if (n <= 2) Done(sum) 
    else Call(() => factorial(n - 1, n * sum)) 
} 

object Factorial extends Application { 
    println(trampoline(factorial(100000, 1))) 
} 

的Java：

import java.math.BigInteger; 

class Trampoline<T> 
{ 
    public T get() { return null; } 
    public Trampoline<T> run() { return null; } 

    T execute() { 
     Trampoline<T> trampoline = this; 

     while (trampoline.get() == null) { 
      trampoline = trampoline.run(); 
     } 

     return trampoline.get(); 
    } 
} 

public class Factorial 
{ 
    public static Trampoline<BigInteger> factorial(final int n, final BigInteger sum) 
    { 
     if(n <= 1) { 
      return new Trampoline<BigInteger>() { public BigInteger get() { return sum; } }; 
     } 
     else { 
      return new Trampoline<BigInteger>() { 
       public Trampoline<BigInteger> run() { 
        return factorial(n - 1, sum.multiply(BigInteger.valueOf(n))); 
       } 
      }; 
     } 
    } 

    public static void main(String [ ] args) 
    { 
     System.out.println(factorial(100000, BigInteger.ONE).execute()); 
    } 
} 

C（不吉利沒有大的數字實現）：

#include <stdio.h> 

typedef struct _trampoline_data { 
    void(*callback)(struct _trampoline_data*); 
    void* parameters; 
} trampoline_data; 

void trampoline(trampoline_data* data) { 
    while(data->callback != NULL) 
    data->callback(data); 
} 

//----------------------------------------- 

typedef struct _factorialParameters { 
    int n; 
    int sum; 
} factorialParameters; 

void factorial(trampoline_data* data) { 
    factorialParameters* parameters = (factorialParameters*) data->parameters; 

    if (parameters->n <= 1) { 
    data->callback = NULL; 
    } 
    else { 
    parameters->sum *= parameters->n; 
    parameters->n--; 
    } 
} 

int main() { 
    factorialParameters params = {5, 1}; 
    trampoline_data t = {&factorial, &params}; 

    trampoline(&t); 
    printf("\n%d\n", params.sum); 

    return 0; 
} 

Answer 7

typedef void* (*state_type)(void); 
void* state1(); 
void* state2(); 
void* state1() { 
    return state2; 
} 
void* state2() { 
    return state1; 
} 
// ... 
state_type state = state1; 
while (1) { 
    state = state(); 
} 
// ...