// Ranlux24 PRNG. (1.02)
// Chaotic with long period but slow due to discard.

#include <stdlib.h>
#include <limits.h>
#include <assert.h>
#include <stdio.h>
#include <time.h>

// Utility.

#define BITS(x) \
    (sizeof(x) * CHAR_BIT)

#define UNLIKELY(cond) \
    __builtin_expect(!!(cond), 0)

#define NEW_T(T, n) \
    ((T *) allocate(n * sizeof(T)))

void *allocate(size_t n)
{
    void *r = malloc(n);
    assert(r != 0 || n == 0);
    return r;
}

// Engine Base.

typedef struct EngineBase {
    int  (*next)    (struct EngineBase*);
    void (*discard) (struct EngineBase*, int);
    void (*delete)  (struct EngineBase*);
} EngineBase;

int EngineBase_next(EngineBase *self)
{
    return self->next(self);
}

void EngineBase_discard(EngineBase *self, int n)
{
    return self->discard(self, n);
}

void EngineBase_delete(EngineBase *self)
{
    return self->delete(self);
}

// Subtract With Carry.

typedef struct {
    EngineBase base;
    int *x, c, i, m, r, s;
} SubtractWithCarryEngine;

static inline int next_(int *x, int mask, int i_s, int i_r, int *carry)
{
    int y = x[i_s] - x[i_r] - *carry;
    *carry = -(y >> (BITS(int) - 1));
    return y & mask;
}

int SubtractWithCarryEngine_next(EngineBase *base)
{
    SubtractWithCarryEngine *self = (SubtractWithCarryEngine *) base;

    self->i += 1;
    int *x = self->x, i = self->i, r = self->r;

    if (UNLIKELY(i >= r))
    {
        int *c = &self->c, m = self->m, s = self->s, t = r - s;

        for (int i = 0; i < s; i++)
            x[i] = next_(x, m, i + t, i, c);
        for (int i = s; i < r; i++)
            x[i] = next_(x, m, i - s, i, c);
        self->i = i = 0;
    }
    return x[i];
}

void SubtractWithCarryEngine_discard(EngineBase *base, int n)
{
    for (int i = 0; i < n; i++)
        SubtractWithCarryEngine_next(base);
}

void SubtractWithCarryEngine_delete(EngineBase *base)
{
    SubtractWithCarryEngine *self = (SubtractWithCarryEngine *) base;

    if (self != 0)
    {
        free(self->x);
        free(self);
    }
}

EngineBase *SubtractWithCarryEngine_new(int w, int s, int r)
{
    assert(0 < w && w < BITS(int));
    assert(0 < s && s < r);

    SubtractWithCarryEngine *self = NEW_T(SubtractWithCarryEngine, 1);

    self->base.next = SubtractWithCarryEngine_next;
    self->base.discard = SubtractWithCarryEngine_discard;
    self->base.delete = SubtractWithCarryEngine_delete;
    self->x = NEW_T(int, r);
    self->c = 0;
    self->i = r-1;
    self->m = -1U >> (BITS(int) - w);
    self->r = r;
    self->s = s;

    for (int i = 0; i < r; i++)
        self->x[i] = rand() & self->m;
    return (EngineBase *) self;
}

// Discard Block.

typedef struct {
    EngineBase base, *owned;
    int p, r, i;
} DiscardBlockEngine;

int DiscardBlockEngine_next(EngineBase *base)
{
    DiscardBlockEngine *self = (DiscardBlockEngine *) base;

    if (self->i == 0)
    {
        EngineBase_discard(self->owned, self->p - self->r);
        self->i = self->r;
    }
    self->i -= 1;
    return EngineBase_next(self->owned);
}

void DiscardBlockEngine_discard(EngineBase *base, int n)
{
    for (int i = 0; i < n; i++)
        DiscardBlockEngine_next(base);
}

void DiscardBlockEngine_delete(EngineBase *base)
{
    DiscardBlockEngine *self = (DiscardBlockEngine *) base;

    if (self != 0)
    {
        EngineBase_delete(self->owned);
        free(self);
    }
}

EngineBase *DiscardBlockEngine_new(EngineBase **unique, int p, int r)
{
    assert(0 < r <= p);

    DiscardBlockEngine *self = NEW_T(DiscardBlockEngine, 1);

    self->base.next = DiscardBlockEngine_next;
    self->base.discard = DiscardBlockEngine_discard;
    self->base.delete = DiscardBlockEngine_delete;
    self->owned = *unique; *unique = 0; // Transfer ownership.
    self->p = p;
    self->r = r;
    self->i = r;
    return (EngineBase *) self;
}

// Ranlux24.

EngineBase *Ranlux24_new(void)
{
    EngineBase *ranlux24_base = SubtractWithCarryEngine_new(24, 10, 24);
    return DiscardBlockEngine_new(&ranlux24_base, 223, 23);
}

// Main.

double clock_now(void)
{
    struct timespec now;
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &now);
    return now.tv_sec + now.tv_nsec / 1.0E+09;
}

int main(void)
{
    srand(time(0));
    EngineBase *ranlux24 = Ranlux24_new();

    for (int i = 0; i < 24; i++)
    {
        int r = EngineBase_next(ranlux24);
        printf("%d\n", r);
    }

    int n = 10000000;
    double t = clock_now();
    EngineBase_discard(ranlux24, n);
    printf("Elapsed: %.9fs\n", clock_now() - t);

    EngineBase_delete(ranlux24);
    return 0;
}