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

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

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

Редактирование: Microsoft имеет платформу для этого типа вещи, на которую можно посмотреть. Названный Обходы

Вот пример вложенных функций:

#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, указатель функции является просто указателем.

Существует также смысл LISP 'батута', как описано на Википедию:

Используемый в некоторых реализациях LISP, батут является циклом, который многократно вызывает возвращающие преобразователя функции. Единственный батут достаточен для выражения всех передач управления программы; программа, так выраженная, является trampolined или в "trampolined стиль"; преобразование программы к стилю trampolined является trampolining. Функции Trampolined могут использоваться для реализации вызовов рекурсивной функции хвоста на языках со стековой организацией

Давайте скажем, что мы используем JavaScript и хотим записать наивную функцию Fibonacci в передающем стиле продолжения. Причина мы сделали бы это, не относится - к схеме порта к 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), что trampolining решает. Вместо того, чтобы выполнить (рекурсивный) вызов к функции, позвольте нам return инструкция (преобразователь), чтобы вызвать ту функцию, быть интерпретированным в цикле.

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]});
}

Для 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");

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

Теперь, когда C# имеет Локальные Функции , , Подающий шары Игровой kata кодирования может быть изящно решен с батутом:

using System.Collections.Generic;
using System.Linq;

class Game
{
    internal static int RollMany(params int[] rs) 
    {
        return Trampoline(1, 0, rs.ToList());

        int Trampoline(int frame, int rsf, IEnumerable<int> rs) =>
              frame == 11             ? rsf
            : rs.Count() == 0         ? rsf
            : rs.First() == 10        ? Trampoline(frame + 1, rsf + rs.Take(3).Sum(), rs.Skip(1))
            : rs.Take(2).Sum() == 10  ? Trampoline(frame + 1, rsf + rs.Take(3).Sum(), rs.Skip(2))
            :                           Trampoline(frame + 1, rsf + rs.Take(2).Sum(), rs.Skip(2));
    }
}

метод Game.RollMany называют со многими списками: обычно 20 списков, при отсутствии запчастей или забастовок.

первая строка сразу вызывает функцию батута: return Trampoline(1, 0, rs.ToList());. Эта локальная функция рекурсивно пересекает массив списков. Локальная функция (батут) позволяет обходу запускаться с двух дополнительных значений: запустите с frame 1 и rsf (результат до сих пор) 0.

В локальной функции существует тернарный оператор, который обрабатывает пять случаев:

• Игра заканчивается в кадре 11: возвратите результат до сих пор
• Игровые концы, если больше нет списков: возвратите результат до сих пор
• Забастовка: вычислите кадр выигрывают и продолжают обход
• Запчасть: вычислите кадр выигрывают и продолжают обход
• Нормальный счет: вычислите кадр выигрывают и продолжают обход

, Продолжение обхода сделано путем вызова батута снова, но теперь с обновленными значениями.

Для получения дополнительной информации, ищите: " аккумулятор хвостовой рекурсии ". Следует иметь в виду, что компилятор не оптимизирует хвостовую рекурсию. Таким образом, столь изящный, как это решение может быть, это, вероятно, не будет постившийся.

В настоящее время я экспериментирую со способами реализации оптимизации хвостового вызова для интерпретатора схемы, и поэтому в настоящий момент я пытаюсь выяснить, подойдет ли мне батут.

Поскольку Я понимаю, что в основном это просто серия вызовов функций, выполняемых функцией трамплина. Каждая функция называется преобразователем и возвращает следующий шаг в вычислении, пока программа не завершится (пустое продолжение).

Вот первый фрагмент кода, который я написал для улучшения моего понимания батута:

#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 !