Что такое функция батута?

Question

Во время недавних обсуждений на работе кто-то ссылался на функцию батута.

Я прочитал описание на Wikipedia. Достаточно дать общее представление о функциональности, но мне хотелось бы что-то более конкретное.

У вас есть простой фрагмент кода, который иллюстрирует батут?

Answer 1

Я приведу вам пример, который я использовал в анти-чит-патче для онлайн-игры.

Мне нужно было проверить все файлы, которые были загружены игрой для модификации. Поэтому самым надежным способом, который я нашел для этого, было использование батута для CreateFileA. Поэтому, когда игра была запущена, я нашел бы адрес для CreateFileA с помощью GetProcAddress, затем я бы изменил первые несколько байтов функции и вставил код сборки, который бы переместился на мою собственную функцию «батут», где я бы сделал некоторые вещи и то я вернусь к следующему месту в CreateFile после моего кода jmp. Чтобы быть в состоянии сделать это надежно, это немного сложнее, но базовая концепция - просто подключить одну функцию, заставить ее перенаправить на другую функцию, а затем вернуться к исходной функции.

Редактировать: Microsoft имеет структуру для такого типа вещей, на которую вы можете смотреть. Вызывается 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 функция может быть использована для реализации хвоста рекурсивной функция вызывает в стеке-ориентированных языках

Допустит, мы используем Javascript и хотим написать наивную функцию Фибоначчей в продолжении обходя стиль. Причина, по которой мы это сделаем, не имеет значения - например, для схемы портов для 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"); 

Edit: Более эзотерические батуты будет неявно, генерируемый компилятором. Одним из таких применений будет таблица перехода. (Хотя есть явно более сложные, тем дальше вы начинаете пытаться генерировать сложный код.)

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

Позвольте мне добавить несколько примеров для функции факториала реализованной с батутами , на разных языках:

Scala:

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(); 
} 
// ...