/**

kurr solver

See xtea_collider() for an example.
Barely tested. Should work, though.

2010-03-11
cipherdev.org, yarrkov@gmail.com

**/

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

typedef unsigned int uint;

typedef void (*kurr_submitter)(void*);
typedef void (*kurr_mixer)(void*, void*);

typedef struct
{
    kurr_mixer mix;
    uint in_len, out_len, plan_len;
    uint plan[];
} kurr;

#define KURR_RNDS 4096
#define KURR_LIMIT 20
#define UINT_MAX ((uint)(-1))

void kurr_rec(kurr *ctx, kurr_submitter submit,
              uint8_t *in, uint8_t *out, uint pos)
{
    if(pos == ctx->plan_len)
    {
        submit(in);
        return;
    }

    uint bit_pos = ctx->plan[pos*2+1];

    if(ctx->plan[pos*2+0] == 1)
    {
        ctx->mix(in, out);
        if(out[bit_pos/8] & (1<<(bit_pos%8)))
            return;
        kurr_rec(ctx, submit, in, out, pos+1);
    } else
    {
        kurr_rec(ctx, submit, in, out, pos+1);
        in[bit_pos/8] ^= 1<<(bit_pos%8);
        kurr_rec(ctx, submit, in, out, pos+1);
    }
}

void kurr_solve(kurr *ctx, void (*submit)(void*))
{
    uint8_t in[ctx->in_len], out[ctx->out_len];
    kurr_rec(ctx, submit, in, out, 0);
}

kurr *kurr_new(kurr_mixer mix, void (*randomize)(),
               uint in_len, uint out_len)
{
    uint i, j, k;
    uint matrix[in_len*8][out_len*8];
    uint lock[out_len*8], plan_len = 0;
    uint8_t in[in_len], out[2][out_len];
    kurr *res;

    memset(matrix, 0, sizeof(matrix));
    memset(lock, 0, sizeof(lock));

    res = malloc(sizeof(*res) + (in_len+out_len)*8*sizeof(uint)*2);
    res->mix = mix;
    res->in_len = in_len;
    res->out_len = out_len;

    for(i=0; i<KURR_RNDS; i++)
    {
        if(randomize)
            randomize();
        for(j=0; j<in_len; j++)
            in[j] = rand();
        mix(in, out[0]);
        for(j=0; j<in_len*8; j++)
        {
            in[j/8] ^= 1<<(j%8);
            mix(in, out[1]);
            in[j/8] ^= 1<<(j%8);
            for(k=0; k<out_len*8; k++)
                matrix[j][k] += ((out[0][k/8]^out[1][k/8])>>(k%8))&1;
        }
    }

    for(i=0; i<in_len*8; i++)
        for(j=0; j<out_len*8; j++)
            matrix[i][j] = matrix[i][j] < KURR_LIMIT ? 0 : 1;

    while(1)
    {
        uint dep, min_dep = UINT_MAX, min_pos = 0;
        for(i=0; i<out_len*8; i++)
        {
            if(lock[i])
                continue;
            dep = 0;
            for(j=0; j<in_len*8; j++)
                dep += matrix[j][i];
            if(dep < min_dep)
            {
                min_dep = dep;
                min_pos = i;
            }
        }
        if(min_dep == UINT_MAX)
            break;
        if(min_dep == 0)
        {
            res->plan[plan_len*2+0] = 1;
            res->plan[plan_len*2+1] = min_pos;
            lock[min_pos] = 1;
        } else
        {
            for(i=0; !matrix[i][min_pos]; i++);
            res->plan[plan_len*2+0] = 0;
            res->plan[plan_len*2+1] = i;
            for(j=0; j<out_len*8; j++)
                matrix[i][j] = 0;
        }
        plan_len++;
    }

    res->plan_len = plan_len;

    return res;
}

//------------------------------------------------------------------------------

uint32_t rand32()
{
    return rand()^(rand()<<7)^(rand()<<19);
}

void xtea_collider()
{
    #define XF(x) ((((x) << 4) ^ ((x) >> 5)) + (x))

    uint32_t base;
    void randomize()
    {
        base = rand32();
    }
    void xdiff(uint32_t *in, uint32_t *out)
    {
        *out = XF(base) ^ XF(base + *in);
    }

    uint32_t *list = NULL, lcount = 0;

    void submit(uint32_t *delta)
    {
        uint i, score = 0;
        for(i=0; i<lcount; i++)
            if(list[i] == *delta)
                break;
        if(i != lcount)
            return;

        const uint xrnds = 1<<16;

        for(i=0; i<xrnds; i++)
        {
            uint32_t x = rand32();
            if((XF(x) ^ XF(x+*delta)) == 0)
                score++;
        }
        if(score > 50)
        {
            lcount++;
            list = realloc(list, lcount*4);
            list[lcount-1] = *delta;
            printf("0x%08X->0, p=%u/%u\n", *delta, score, xrnds);
        }
    }

    kurr *solver = kurr_new((kurr_mixer)xdiff, randomize, 4, 4);
    while(1)
    {
        randomize();
        kurr_solve(solver, (kurr_submitter)submit);
    }
}

int main()
{
    xtea_collider();
    return 0;
}