Initial implementation.

13 files changed, 665 insertions, 0 deletions

diff --git a/fibers.pro b/fibers.pro
new file mode 100644
index 0000000..65d9262
--- /dev/null
+++ b/fibers.pro
@@ -0,0 +1,2 @@
+TEMPLATE = subdirs
+SUBDIRS = src
diff --git a/src/backend/initializestack_32.cpp b/src/backend/initializestack_32.cpp
new file mode 100644
index 0000000..d387460
--- /dev/null
+++ b/src/backend/initializestack_32.cpp
@@ -0,0 +1,21 @@
+#include <stdlib.h>
+
+void initializeStack(void *data, int size, void (*entry)(), void **stackPointer)
+{
+    void* stackBottom = (char*)data + size;
+    // align to 16 byte
+    stackBottom = (void*)((size_t)stackBottom & ~0xF);
+    
+    void **p = (void**)stackBottom;
+
+    *(--p) = 0; // align
+    *(--p) = (void*)entry; // rip
+    *(--p) = stackBottom; // ebp
+    *(--p) = 0; // ebx
+    *(--p) = 0; // esi
+    *(--p) = 0; // edi
+    *(--p) = (void*)0x00001f80; // SIMD floating point control default
+    *(--p) = (void*)0x0000033f; // floating point control default
+    
+    *stackPointer = p;
+}
diff --git a/src/backend/initializestack_64_linux_mac.cpp b/src/backend/initializestack_64_linux_mac.cpp
new file mode 100644
index 0000000..5465dfb
--- /dev/null
+++ b/src/backend/initializestack_64_linux_mac.cpp
@@ -0,0 +1,22 @@
+#include <stdlib.h>
+
+void initializeStack(void *data, int size, void (*entry)(), void **stackPointer)
+{
+    void* stackBottom = (char*)data + size;
+    // align to 16 byte
+    stackBottom = (void*)((size_t)stackBottom & ~0xF);
+    
+    void **p = (void**)stackBottom;
+
+    *(--p) = 0; // align
+    *(--p) = (void*)entry; // rip
+    *(--p) = stackBottom; // rbp
+    *(--p) = 0; // rbx
+    *(--p) = 0; // r12
+    *(--p) = 0; // r13
+    *(--p) = 0; // r14
+    *(--p) = 0; // r15
+    *(--p) = (void*)0x00001f800000033f; // SIMD and regular floating point control defaults
+    
+    *stackPointer = p;
+}
diff --git a/src/backend/initializestack_64_win.cpp b/src/backend/initializestack_64_win.cpp
new file mode 100644
index 0000000..3b29caf
--- /dev/null
+++ b/src/backend/initializestack_64_win.cpp
@@ -0,0 +1,44 @@
+#include <stdlib.h>
+
+void initializeStack(void *data, int size, void (*entry)(), void **stackPointer)
+{
+    void* stackBottom = (char*)data + size;
+    // align to 16 byte
+    stackBottom = (void*)((size_t)stackBottom & ~0xF);
+    
+    void **p = (void**)stackBottom;
+
+    //*(--p) = 0; // align to 16 bytes
+    *(--p) = (void*)fn; // rip
+    *(--p) = entry; // rbp
+    *(--p) = 0; // rbx
+    *(--p) = 0; // r12
+    *(--p) = 0; // r13
+    *(--p) = 0; // r14
+    *(--p) = 0; // r15
+    *(--p) = 0; // rsi
+    *(--p) = 0; // rdi
+    *(--p) = 0; // xmm6
+    *(--p) = 0; // xmm6
+    *(--p) = 0; // xmm7
+    *(--p) = 0; // xmm7
+    *(--p) = 0; // xmm8
+    *(--p) = 0; // xmm8
+    *(--p) = 0; // xmm9
+    *(--p) = 0; // xmm9
+    *(--p) = 0; // xmm10
+    *(--p) = 0; // xmm10
+    *(--p) = 0; // xmm11
+    *(--p) = 0; // xmm11
+    *(--p) = 0; // xmm12
+    *(--p) = 0; // xmm12
+    *(--p) = 0; // xmm13
+    *(--p) = 0; // xmm13
+    *(--p) = 0; // xmm14
+    *(--p) = 0; // xmm14
+    *(--p) = 0; // xmm15
+    *(--p) = 0; // xmm15
+    *(--p) = (void*)0x00001f800000033f; // SIMD and regular floating point control defaults
+    
+    *stackPointer = p;
+}
diff --git a/src/backend/switchstack_gcc_32_linux_mac.s b/src/backend/switchstack_gcc_32_linux_mac.s
new file mode 100644
index 0000000..e4eac63
--- /dev/null
+++ b/src/backend/switchstack_gcc_32_linux_mac.s
@@ -0,0 +1,41 @@
+.text
+.globl _switchStackInternal
+
+_switchStackInternal:
+    // save callee-saved registers
+    push %ebp
+    movl %esp, %ebp
+    push %ebx
+    push %esi
+    push %edi
+
+    // store SIMD floating point control word
+    sub $4, %esp
+    stmxcsr (%esp)
+
+    // store floating point control bytes
+    sub $4, %esp
+    fstcw (%esp)
+
+    // save the old stack pointer
+    movl 0xc(%ebp), %edx
+    movl %esp, (%edx)
+    // set the new stack pointer
+    movl 0x8(%ebp), %esp
+
+    // restore floating point control bytes
+    fnclex
+    fldcw (%esp)
+    add $4, %esp
+
+    // restore SIMD floating point control word
+    ldmxcsr (%esp)
+    add $4, %esp
+
+    // pop callee-saved registers
+    pop %edi
+    pop %esi
+    pop %ebx
+    pop %ebp
+
+    ret
diff --git a/src/backend/switchstack_gcc_32_win.s b/src/backend/switchstack_gcc_32_win.s
new file mode 100644
index 0000000..2e8c140
--- /dev/null
+++ b/src/backend/switchstack_gcc_32_win.s
@@ -0,0 +1,42 @@
+.global _switchStackInternal 
+.section .text 
+.def _switchStackInternal ; .scl 2 ; .type 32 ; .endef 
+
+_switchStackInternal:
+    // save callee-saved registers
+    push %ebp
+    movl %esp, %ebp
+    push %ebx
+    push %esi
+    push %edi
+
+    // store SIMD floating point control word
+    sub $4, %esp
+    stmxcsr (%esp)
+
+    // store floating point control bytes
+    sub $4, %esp
+    fstcw (%esp)
+
+    // save the old stack pointer
+    movl 0xc(%ebp), %edx
+    movl %esp, (%edx)
+    // set the new stack pointer
+    movl 0x8(%ebp), %esp
+
+    // restore floating point control bytes
+    fnclex
+    fldcw (%esp)
+    add $4, %esp
+
+    // restore SIMD floating point control word
+    ldmxcsr (%esp)
+    add $4, %esp
+
+    // pop callee-saved registers
+    pop %edi
+    pop %esi
+    pop %ebx
+    pop %ebp
+    
+    ret
diff --git a/src/backend/switchstack_gcc_64_linux_mac.s b/src/backend/switchstack_gcc_64_linux_mac.s
new file mode 100644
index 0000000..ced6a5d
--- /dev/null
+++ b/src/backend/switchstack_gcc_64_linux_mac.s
@@ -0,0 +1,44 @@
+.text
+.globl _switchStackInternal
+
+_switchStackInternal:
+    // save callee-saved registers
+    push %rbp
+    movq %rsp, %rbp
+    push %rbx
+    push %r12
+    push %r13
+    push %r14
+    push %r15
+
+    // store SIMD floating point control word
+    sub $4, %rsp
+    stmxcsr (%rsp)
+
+    // store floating point control bytes
+    sub $4, %rsp
+    fstcw (%rsp)
+
+    // save the old stack pointer (second arg in rsi)
+    movq %rsp, (%rsi)
+    // set the new stack pointer (first arg in rdi)
+    movq %rdi, %rsp
+
+    // restore floating point control bytes
+    fnclex
+    fldcw (%rsp)
+    add $4, %rsp
+
+    // restore SIMD floating point control word
+    ldmxcsr (%rsp)
+    add $4, %rsp
+
+    // pop callee-saved registers
+    pop %r15
+    pop %r14
+    pop %r13
+    pop %r12
+    pop %rbx
+    pop %rbp
+
+    retq
diff --git a/src/backend/switchstack_gcc_64_win.s b/src/backend/switchstack_gcc_64_win.s
new file mode 100644
index 0000000..f75c53c
--- /dev/null
+++ b/src/backend/switchstack_gcc_64_win.s
@@ -0,0 +1,93 @@
+.global _switchStackInternal
+.section .text 
+.def _switchStackInternal ; .scl 2 ; .type 32 ; .endef 
+
+_switchStackInternal:
+    // save callee-saved registers
+    push %rbp
+    movq %rsp, %rbp
+    push %rbx
+    push %r12
+    push %r13
+    push %r14
+    push %r15
+
+    push %rsi
+    push %rdi
+
+    sub $0x10, %rsp
+    movupd %xmm6, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm7, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm8, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm9, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm10, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm11, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm12, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm13, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm14, (%rsp)
+    sub $0x10, %rsp
+    movupd %xmm15, (%rsp)
+
+    // store SIMD floating point control word
+    sub $4, %rsp
+    stmxcsr (%rsp)
+
+    // store floating point control bytes
+    sub $4, %rsp
+    fstcw (%rsp)
+
+    // save the old stack pointer (second arg in rsi)
+    movq %rsp, (%rsi)
+    // set the new stack pointer (first arg in rdi)
+    movq %rdi, %rsp
+
+    // restore floating point control bytes
+    fnclex
+    fldcw (%rsp)
+    add $4, %rsp
+
+    // restore SIMD floating point control word
+    ldmxcsr (%rsp)
+    add $4, %rsp
+
+    // pop callee-saved registers
+    movupd (%rsp), %xmm15
+    add $0x10, %rsp
+    movupd (%rsp), %xmm14
+    add $0x10, %rsp
+    movupd (%rsp), %xmm13
+    add $0x10, %rsp
+    movupd (%rsp), %xmm12
+    add $0x10, %rsp
+    movupd (%rsp), %xmm11
+    add $0x10, %rsp
+    movupd (%rsp), %xmm10
+    add $0x10, %rsp
+    movupd (%rsp), %xmm9
+    add $0x10, %rsp
+    movupd (%rsp), %xmm8
+    add $0x10, %rsp
+    movupd (%rsp), %xmm7
+    add $0x10, %rsp
+    movupd (%rsp), %xmm6
+    add $0x10, %rsp
+
+    pop %rdi
+    pop %rsi
+
+    pop %r15
+    pop %r14
+    pop %r13
+    pop %r12
+    pop %rbx
+    pop %rbp
+
+    retq
diff --git a/src/backend/switchstack_msvc_32.cpp b/src/backend/switchstack_msvc_32.cpp
new file mode 100644
index 0000000..eae68ee
--- /dev/null
+++ b/src/backend/switchstack_msvc_32.cpp
@@ -0,0 +1,44 @@
+extern "C" {
+void __declspec(naked) _switchStackInternal(void* to, void** from)
+{
+    __asm {
+    // save callee-saved registers
+    PUSH EBP
+    MOV EBP, ESP
+    PUSH EBX
+    PUSH ESI
+    PUSH EDI
+
+    // store SIMD floating point control word
+    SUB ESP, 4
+    STMXCSR [ESP]
+
+    // store floating point control bytes
+    SUB ESP, 4
+    FSTCW [ESP]
+
+    // save the old stack pointer
+    MOV EDX, dword ptr 12[EBP]
+    MOV [EDX], ESP
+    // set the new stack pointer
+    MOV ESP, dword ptr 8[EBP]
+
+    // restore floating point control bytes
+    FNCLEX
+    FLDCW [ESP]
+    ADD ESP, 4
+
+    // restore SIMD floating point control word
+    LDMXCSR [ESP]
+    ADD ESP, 4
+
+    // pop callee-saved registers
+    POP EDI
+    POP ESI
+    POP EBX
+    POP EBP        
+    
+    RET
+    }
+}
+}
diff --git a/src/backend/switchstack_msvc_64.asm b/src/backend/switchstack_msvc_64.asm
new file mode 100644
index 0000000..3c6f321
--- /dev/null
+++ b/src/backend/switchstack_msvc_64.asm
@@ -0,0 +1,98 @@
+.model flat, c
+.code
+
+_switchStackInternal PROC to:QWORD, from:QWORD
+    ; save callee-saved registers
+    PUSH RBP
+    MOV RBP, RSP
+    PUSH RBX
+    PUSH ESI
+    PUSH EDI
+
+    PUSH R12
+    PUSH R13
+    PUSH R14
+    PUSH R15
+
+    PUSH RSI
+    PUSH RDI
+
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM6
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM7
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM8
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM9
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM10
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM11
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM12
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM13
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM14
+    SUB RSP, 0x10
+    MOVUPD [RSP], XMM15
+
+    ; store SIMD floating point control word
+    SUB RSP, 4
+    STMXCSR [RSP]
+
+    ; store floating point control bytes
+    SUB RSP, 4
+    FSTCW [RSP]
+
+    ; save the old stack pointer
+    MOV [from], RSP
+    ; set the new stack pointer
+    MOV RSP, to
+
+    ; restore floating point control bytes
+    FNCLEX
+    FLDCW [RSP]
+    ADD RSP, 4
+
+    ; restore SIMD floating point control word
+    LDMXCSR [RSP]
+    ADD RSP, 4
+
+    ; pop callee-saved registers
+    MOVUPD XMM15, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM14, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM13, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM12, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM11, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM10, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM9, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM8, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM7, [RSP]
+    ADD RSP, 0x10
+    MOVUPD XMM6, [RSP]
+    ADD RSP, 0x10
+
+    POP RDI
+    POP RSI
+
+    POP R15
+    POP R14
+    POP R13
+    POP R12
+    POP RBX
+    POP RBP
+
+    RET
+_switchStackInternal ENDP
+
+end
diff --git a/src/fiber.cpp b/src/fiber.cpp
new file mode 100644
index 0000000..7208ced
--- /dev/null
+++ b/src/fiber.cpp
@@ -0,0 +1,120 @@
+#include <stdlib.h>
+#include <QtCore/QtGlobal>
+
+#include "fiber.h"
+
+/*!
+  \class Fiber
+  \brief The Fiber class provides cooperatively scheduled stacks of execution.
+
+  Fibers, also known as coroutines, allow managing multiple stacks in the same
+  thread.
+
+  To create a fiber, subclass Fiber and override the run() method. To run it,
+  call cont(). This will execute the code in run() until it calls Fiber::yield().
+  At that point, the call to cont() returns. Subsequent calls to cont() will
+  continue execution of the fiber just after the yield().
+
+  Example:
+  class MyFiber : public Fiber
+  {
+      virtual void run()
+      {
+          qDebug() << "1";
+          Fiber::yield();
+          qDebug() << "2";
+      }
+  }
+
+  MyFiber fib;
+  qDebug() << "0.5";
+  fib.cont(); // prints 1
+  qDebug() << "1.5";
+  fib.cont(); // prints 2
+*/
+
+#ifdef Q_OS_MAC
+extern "C" void switchStackInternal(void* to, void** from);
+void initializeStack(void *data, int size, void (*entry)(), void **stackPointer);
+void switchStack(void* to, void** from) { switchStackInternal(to, from); }
+#else
+extern "C" void _switchStackInternal(void* to, void** from);
+void initializeStack(void *data, int size, void (*entry)(), void **stackPointer);
+void switchStack(void* to, void** from) { _switchStackInternal(to, from); }
+#endif
+
+Fiber *Fiber::_currentFiber = 0;
+
+Fiber::Fiber(int stackSize)
+    : _stackData(0)
+    , _stackPointer(0)
+    , _previousFiber(0)
+    , _status(NotStarted)
+{
+    // establish starting fiber context if necessary
+    currentFiber();
+    
+    _stackData = malloc(stackSize);
+    initializeStack(_stackData, stackSize, &entryPoint, &_stackPointer);
+}
+
+Fiber::Fiber(bool)
+    : _stackData(0)
+    , _stackPointer(0)
+    , _previousFiber(0)
+    , _status(Running)
+{
+}
+
+Fiber::~Fiber()
+{
+    if (_stackData)
+        free(_stackData);
+}
+
+Fiber *Fiber::currentFiber()
+{
+    // establish a context for the starting fiber
+    if (!_currentFiber)
+        _currentFiber = new Fiber(true);
+    
+    return _currentFiber;
+}
+
+void Fiber::entryPoint()
+{
+    _currentFiber->run();
+    yieldHelper(Terminated);
+    Q_ASSERT(0); // unreachable
+}
+
+// returns whether it can be continued again
+bool Fiber::cont()
+{    
+    Q_ASSERT(_status == NotStarted || _status == Stopped);
+    Q_ASSERT(!_previousFiber);
+    
+    _previousFiber = _currentFiber;
+    _currentFiber = this;
+    _status = Running;
+    switchStack(_stackPointer, &_previousFiber->_stackPointer);
+    return _status != Terminated;
+}
+
+void Fiber::yield()
+{
+    yieldHelper(Stopped);
+}
+
+void Fiber::yieldHelper(Status stopStatus)
+{
+    Fiber *stoppingFiber = _currentFiber;
+    Q_ASSERT(stoppingFiber);
+    Q_ASSERT(stoppingFiber->_previousFiber);
+    Q_ASSERT(stoppingFiber->_status == Running);
+
+    _currentFiber = stoppingFiber->_previousFiber;
+    stoppingFiber->_previousFiber = 0;
+    stoppingFiber->_status = stopStatus;
+    switchStack(_currentFiber->_stackPointer, &stoppingFiber->_stackPointer);
+}
diff --git a/src/fiber.h b/src/fiber.h
new file mode 100644
index 0000000..6afc57d
--- /dev/null
+++ b/src/fiber.h
@@ -0,0 +1,48 @@
+#ifndef INCLUDE_FIBER_H
+#define INCLUDE_FIBER_H
+
+class Fiber
+{
+public:
+    enum Status
+    {
+        NotStarted,
+        Running,
+        Stopped,
+        Terminated
+    };
+
+public:
+    explicit Fiber(int stackSize = 32768);
+    virtual ~Fiber();
+    
+    bool cont();
+    static void yield();
+    
+    static Fiber *currentFiber();
+    
+    Status status()
+    { return _status; }
+    
+protected:
+    // could be abstract if subclassing for start fiber
+    virtual void run() {}
+    
+private:
+    // for the original fiber
+    Fiber(bool);
+
+    static void yieldHelper(Status stopStatus);
+    
+    void *_stackData;
+    void *_stackPointer;
+    Fiber *_previousFiber;
+    Status _status;
+    
+    // should be thread local
+    static Fiber *_currentFiber;
+    
+    static void entryPoint();
+};
+
+#endif // INCLUDE_FIBER_H
diff --git a/src/src.pro b/src/src.pro
new file mode 100644
index 0000000..b2b9f6d
--- /dev/null
+++ b/src/src.pro
@@ -0,0 +1,46 @@
+TEMPLATE = lib
+TARGET = fibers
+
+HEADERS += fiber.h
+SOURCES += fiber.cpp
+
+INCLUDEPATH += .
+DEPENDPATH += .
+
+contains(QMAKE_CXX,g++) {
+    win32 {
+        # will fail for 64 bit win!
+        SOURCES += \
+            backend/switchstack_gcc_32_win.cpp \
+            backend/initializestack_32.cpp
+    }
+
+    mac {
+        CONFIG(x86_64) {
+            SOURCES += \
+                backend/switchstack_gcc_64_linux_mac.s \
+                backend/initializestack_64_linux_mac.cpp
+        } else {
+            SOURCES += \
+                backend/switchstack_gcc_32_linux_mac.s \
+                backend/initializestack_32.cpp
+        }
+    }
+    !win32:!mac {
+        contains(QMAKE_CFLAGS,-m64) {
+            SOURCES += \
+                backend/switchstack_gcc_64_linux_mac.s \
+                backend/initializestack_64_linux_mac.cpp
+        } else {
+            SOURCES += \
+                backend/switchstack_gcc_32_linux_mac.s \
+                backend/initializestack_32.cpp
+        }
+    }
+}
+win32:contains(QMAKE_CXX,cl) {
+    # will fail for 64 bit win!
+    SOURCES += \
+        backend/switchstack_msvc_32.cpp \
+        backend/initializestack_32.cpp
+}