#include <stdlib.h>
#include <stdio.h>
#include <string.h>


static size_t gcd(size_t a, size_t b)
{
    while (b)
    {
        size_t c = a%b;
        a = b;
        b = c;
    }
    return a;
}

void memmove_wrap(char *dst, const char *src, size_t n, const char *start, const char *end)
{
    const char *srcend = src+n;
    if (srcend >= end) srcend -= end-start;

    if ((dst < src && (src < srcend || srcend <= dst)) ||
        (src+n <= dst))
    {
        /* dst isn't in [src; src+n[
         *       src     srcend
         *  start|       |  end
         *  v    v       v  v
         * |-----ssssssss---|
         * |---dddddddd-----|
         *     ^
         *     dst
         * or
         * |ss-----sssssssss|
         * |d-----dddddddddd|
         * or
         * |--ssssssssss----|
         * |ddddddd------ddd| */
 #if 0
        while (n--)
        {
            *dst++ = *src++;
            if (dst == end)
                dst = (char *)start;
            if (src == end)
                src = start;
        }
#else
        if (dst+n > end && src+n > end)
        {
            size_t dchunk = end-dst;
            size_t schunk = end-src;
            if (dchunk < schunk)
            {
                memmove(dst, src, dchunk);
                memmove(start, src+dchunk, schunk-dchunk);
                memmove(start+schunk-dchunk, start, n-schunk);
            }
            else
            {
                memmove(dst, src, schunk);
                memmove(dst+schunk, start, dchunk-schunk);
                memmove(start, start+dchunk-schunk, n-dchunk);
            }
        }
        else if (dst+n > end)
        {
            size_t chunk = end-dst;
            memmove(dst, src, chunk);
            memmove(start, src+chunk, n-chunk);
        }
        else if (src+n > end)
        {
            size_t chunk = end-src;
            memmove(dst, src, chunk);
            memmove(dst+chunk, start, n-chunk);
        }
        else
        {
            memmove(dst, src, n);
        }
#endif
    }
    else if (src != dst)
    {
        /* dst is in [src; src+n[
         * |-----ssssssss---|
         * |------dddddddd--|
         * or
         * |ss-----sssssssss|
         * |-ddddddddddd----|
         * or
         * |ss-----sssssssss|
         * |dddd-----ddddddd| */
        /* copy non overlapping data first */
        if (2*n <= end-start)
        {
            ssize_t offset = srcend-dst;
            if (offset < 0) offset += end-start;
            char *dstoffset = dst+offset;
            if (dstoffset >= end) dstoffset -= end-start;
            const char *srcoffset = src+offset;
            if (srcoffset >= end) srcoffset -= end-start;
            memmove_wrap(dstoffset, srcoffset, n-offset, start, end);
            memmove_wrap(dst, src, offset, start, end);
        }
        else
        {
            ssize_t step = src-dst;
            if (step < 0)
                step += end-start;
            size_t g = gcd(end-start, step);
            size_t i;
            for (i = 0; i < g; i++)
            {
                const char *s = src+i;
                if (s >= end)
                    s -= end-start;
                char *d = dst+i;
                if (d >= end)
                    d -= end-start;
                char *dorig = d;
                char old = *d;
                do
                {
                    *d = *s;
                    d += step;
                    if (d >= end)
                        d -= end-start;
                    s += step;
                    if (s >= end)
                        s -= end-start;
                } while (s != dorig);
                *d = old;
            }
        }
    }
}

int main(void)
{
/* Undefine COUNT_ERRORS to get extra information about the first error */
#define COUNT_ERRORS
#define SIZE 8
#define FMT "%.1d"
    char buffer[SIZE];

#ifdef COUNT_ERRORS
    int fail = 0;
    int count = 0;
#endif
    int len;
    for (len = 1; len < SIZE; len++)
    {
        int src;
        for (src = 0; src < SIZE; src++)
        {
            int dst;
            for (dst = 0; dst < SIZE; dst++)
            {
                if (dst == src)
                    continue;
                printf("Testing len %d: src "FMT" -> dst "FMT
#ifndef COUNT_ERRORS
                "\n"
#endif
                , len, src, dst);
                memset(buffer, 0, SIZE);
                int i;
                for (i = 0; i < len; i++)
                    buffer[(src+i)%SIZE] = i+1;
                memmove_wrap(buffer+dst, buffer+src, len, buffer, buffer+SIZE);
                int err = 0;
                for (i = 0; i < len; i++)
                    if (buffer[(dst+i)%SIZE] != i+1)
                    {
                        err = 1;
                        break;
                    }

#ifdef COUNT_ERRORS
                if (err)
                    printf(" ERROR");
                printf("\n");
#endif
                if (err)
                {
#ifndef COUNT_ERRORS
                    printf("ERROR!\n");
                    printf("Position: ");
                    for (i = 0; i < SIZE; i++)
                        printf(FMT" ", i);
                    printf("\n");
                    printf("Had     : ");
                    for (i = 0; i < SIZE; i++)
                    {
                        int j = (src+i+1)%SIZE;
                        if (j > 0 && j <= len )
                            printf(FMT" ", j);
                        else
                            printf(FMT" ", 0);
                    }
                    printf("\n");
                    printf("Expected: ");
                    for (i = 0; i < SIZE; i++)
                    {
                        int j = (SIZE-dst+i+1)%SIZE;
                        if (j > 0 && j <= len )
                            printf(FMT" ", j);
                        else
                        {
                            j = (SIZE-src+i+1)%SIZE;
                            if (j > 0 && j <= len )
                                printf(FMT" ", j);
                            else
                                printf(FMT" ", 0);
                        }
                    }
                    printf("\n");
                    printf("Got     : ");
                    for (i = 0; i < SIZE; i++)
                        printf(FMT" ", buffer[i]);
                    printf("\n");
                    return -1;
#else
                    fail ++;
#endif
                }
#ifdef COUNT_ERRORS
                count ++;
#endif
            }
        }
    }
#ifdef COUNT_ERRORS
    printf("fail: %d/%d\n", fail, count);
    if (fail == 0)
        printf("Oh yeah!\n");
#endif
    return 0;
}