Устройство Даффа

Традиционный способ последовательного копирования (до открытия Даффа) выглядел так:

do { /* Предполагается count > 0 */
    *to = *from++;            /* Здесь указатель to не увеличивается */
} while (--count > 0);

В этом примере to не увеличивается потому, что Дафф копировал в единственный регистр ввода-вывода, отображаемый в память. В современном языке Си определение переменной to должно быть подкреплено с помощью ключевого слова volatile.

Во время оптимизации этого кода Дафф осознал, что «раскрученный» вариант цикла может быть реализован при помощи наложения конструкций switch и do/while.

strcpy(to, from, count)
register char *to, *from;
register count;
{
    register n = (count + 7) / 8;
    if (!count) return;
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n > 0);
    }
}

Сам алгоритм был широко известен и раньше: программисты, разрабатывающие программы на ассемблере, применяли его для уменьшения количества сравнений и ветвлений при копировании.

В свою очередь, реализация метода Даффа на языке Си на первый взгляд выглядит необычно. Однако, этот код написан в соответствии с описанием и стандартом языка Си; спецификация конструкции switch вполне допускает такое использование:

1. На момент изобретения увидело свет лишь первое издание книги «Язык программирования Си», в которой требовалось лишь, чтобы частью конструкции switch была синтаксически правильная инструкция, в том числе блок (составная инструкция), в котором все метки case должны предшествовать какой-либо инструкции внутри блока.
2. Вторая особенность синтаксиса Си состоит в том, что при отсутствии break, управление внутри блока передаётся «вниз и насквозь» от инструкции, стоящей под одной меткой case, к инструкции, стоящей под следующей меткой case.

Сочетание этих двух фактов приводит к тому, что вышеприведённый код выполнит копирование из последовательно расположенных адресов (*from) в отображаемый порт вывода (*to) заданное число раз (count[3]).

Первоначальный вариант метода Даффа предназначался для копирования в регистр ввода-вывода. Чтобы просто скопировать фрагмент памяти из одного места в другое, нужно добавить автоматическую инкрементацию к каждому упоминанию to:

  *to++ = *from++;

Метод Даффа в таком виде приводится в качестве упражнения в книге Бьёрна Страуструпа «Язык программирования C++»[4]. По-видимому, изменение связано с тем, что автор не ожидает от начинающего программиста знакомства с регистрами ввода-вывода. Практического применения такой вариант не имеет, так как в стандартной библиотеке языка Си уже есть функция копирования участка памяти (memcpy).

Прямое использование конечных автоматов программистами часто затруднено тем, что выбранный язык программирования не позволяет ясно и просто представить состояния и переходы автомата в коде (см. примеры в статье «Автоматное программирование»).

Один из удачных вариантов предложен[5] Саймоном Тэтхемом и представляет собой способ реализации неявного конечного автомата при помощи метода Даффа. В свою очередь, конечные автоматы были использованы Тэтхемом для реализации сопрограмм, что позволило ему реализовать задачу производителя-потребителя без использования многопоточности и сопутствующих проблем.

Тот же подход, в числе прочих, был использован и Адамом Данкелсом (англ. Adam Dunkels) в его библиотеке «protothreads»[6], посвящённой различным способам реализации псевдо-многопоточности при помощи неявных конечных автоматов.

Предложенный подход состоит в конструировании конечного автомата по частям, с использованием нескольких макросов языка Си. В упрощённом виде макросы выглядят так:

#define DECLARE() int state

#define INIT() state = 0

#define BEGIN switch (state) { \
                      case 0:

#define YIELD(val) do { \
                        state = __LINE__;   \
                        return val;         \
                      case __LINE__:        \
                        ;                   \
                      } while (0)

#define END }

Пример использования (на C++):

#include <iostream>
using namespace std;

class machine {
    DECLARE();
public:
    machine()
    {
        INIT();
    }

    const char* next()
    {
        BEGIN;
            YIELD("мама");
            YIELD("мыла");
            YIELD("раму");
        END;
        return NULL;
    }
};

int main()
{
    machine m;
    while (const char* val = m.next()) {
        cout << val << ' ';
    }
    return 0;
}

Эта программа выведет «мама мыла раму», причём каждое слово будет сгенерировано отдельным шагом конечного автомата.