// Virtually all of these were taken from: https://www.shadertoy.com/view/ttc3zr

uint4 murmurHash42(uint2 src)
{
    const uint M = 0x5bd1e995u;
    uint4 h = uint4(1190494759u, 2147483647u, 3559788179u, 179424673u);
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src.x;
    h *= M;
    h ^= src.y;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

uint murmurHash11(uint src)
{
    const uint M = 0x5bd1e995u;
    uint h = 1190494759u;
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

uint murmurHash12(uint2 src)
{
    const uint M = 0x5bd1e995u;
    uint h = 1190494759u;
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src.x;
    h *= M;
    h ^= src.y;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

uint murmurHash13(uint3 src)
{
    const uint M = 0x5bd1e995u;
    uint h = 1190494759u;
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src.x;
    h *= M;
    h ^= src.y;
    h *= M;
    h ^= src.z;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

uint2 murmurHash22(uint2 src)
{
    const uint M = 0x5bd1e995u;
    uint2 h = uint2(1190494759u, 2147483647u);
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src.x;
    h *= M;
    h ^= src.y;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

uint2 murmurHash21(uint src)
{
    const uint M = 0x5bd1e995u;
    uint2 h = uint2(1190494759u, 2147483647u);
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

uint2 murmurHash23(uint3 src)
{
    const uint M = 0x5bd1e995u;
    uint2 h = uint2(1190494759u, 2147483647u);
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src.x;
    h *= M;
    h ^= src.y;
    h *= M;
    h ^= src.z;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

uint3 murmurHash31(uint src)
{
    const uint M = 0x5bd1e995u;
    uint3 h = uint3(1190494759u, 2147483647u, 3559788179u);
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

uint3 murmurHash33(uint3 src)
{
    const uint M = 0x5bd1e995u;
    uint3 h = uint3(1190494759u, 2147483647u, 3559788179u);
    src *= M;
    src ^= src >> 24u;
    src *= M;
    h *= M;
    h ^= src.x;
    h *= M;
    h ^= src.y;
    h *= M;
    h ^= src.z;
    h ^= h >> 13u;
    h *= M;
    h ^= h >> 15u;
    return h;
}

// 3 outputs, 3 inputs
float3 hash33(float3 src)
{
    uint3 h = murmurHash33(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}

// 1 output, 1 input
float hash11(float src)
{
    uint h = murmurHash11(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}

// 1 output, 2 inputs
float hash12(float2 src)
{
    uint h = murmurHash12(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}


// 1 output, 3 inputs
float hash13(float3 src)
{
    uint h = murmurHash13(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}

// 2 outputs, 1 input
float2 hash21(float src)
{
    uint2 h = murmurHash21(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}

// 3 outputs, 1 input
float3 hash31(float src)
{
    uint3 h = murmurHash31(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}

// 2 outputs, 2 inputs
float2 hash22(float2 src)
{
    uint2 h = murmurHash22(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}

// 4 outputs, 2 inputs
float4 hash42(float2 src)
{
    uint4 h = murmurHash42(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}

void hash42_float(float2 src, out float4 result)
{
    result = hash42(src);
}

// 2 outputs, 3 inputs
float2 hash23(float3 src)
{
    uint2 h = murmurHash23(asuint(src));
    return asfloat(h & 0x007fffffu | 0x3f800000u) - 1.0;
}

float noise11_float(float p)
{
    float i = floor(p);
    float f = frac(p);
    float u = smoothstep(0.0, 1.0, f);

    float val = lerp(hash11(i + 0.0),
                   hash11(i + 1.0), u);
    return val * 2.0 - 1.0;
}

float noise12(float2 p)
{
    float2 i = floor(p);
    float2 f = frac(p);
    float2 u = smoothstep(float2(0.0, 0.0), float2(1.0, 1.0), f);

    float val = lerp(lerp(hash12(i + float2(0.0, 0.0)),
                        hash12(i + float2(1.0, 0.0)), u.x),
                   lerp(hash12(i + float2(0.0, 1.0)),
                        hash12(i + float2(1.0, 1.0)), u.x), u.y);
    return val * 2.0 - 1.0;
}


void noise12_float(float2 p, out float Out)
{
    Out = noise12(p);
}


float noise13_float(float3 x)
{
    float3 i = floor(x);
    float3 f = frac(x);
    f = f * f * (3.0 - 2.0 * f);

    return lerp(lerp(lerp(hash13(i + float3(0.0, 0.0, 0.0)),
                          hash13(i + float3(1.0, 0.0, 0.0)), f.x),
                     lerp(hash13(i + float3(0.0, 1.0, 0.0)),
                          hash13(i + float3(1.0, 1.0, 0.0)), f.x), f.y),
                lerp(lerp(hash13(i + float3(0.0, 0.0, 1.0)),
                          hash13(i + float3(1.0, 0.0, 1.0)), f.x),
                     lerp(hash13(i + float3(0.0, 1.0, 1.0)),
                          hash13(i + float3(1.0, 1.0, 1.0)), f.x), f.y), f.z);
}

float2 noise23_float(float3 x)
{
    float3 i = floor(x);
    float3 f = frac(x);
    f = f * f * (3.0 - 2.0 * f);

    return lerp(lerp(lerp(hash23(i + float3(0.0, 0.0, 0.0)),
                          hash23(i + float3(1.0, 0.0, 0.0)), f.x),
                     lerp(hash23(i + float3(0.0, 1.0, 0.0)),
                          hash23(i + float3(1.0, 1.0, 0.0)), f.x), f.y),
                lerp(lerp(hash23(i + float3(0.0, 0.0, 1.0)),
                          hash23(i + float3(1.0, 0.0, 1.0)), f.x),
                     lerp(hash23(i + float3(0.0, 1.0, 1.0)),
                          hash23(i + float3(1.0, 1.0, 1.0)), f.x), f.y), f.z);
}

float2 noise22(float2 p)
{
    float2 i = floor(p);
    float2 f = frac(p);
    float2 u = smoothstep(float2(0.0, 0.0), float2(1.0, 1.0), f);

    float2 val = lerp(lerp(hash22(i + float2(0.0, 0.0)),
                          hash22(i + float2(1.0, 0.0)), u.x),
                     lerp(hash22(i + float2(0.0, 1.0)),
                          hash22(i + float2(1.0, 1.0)), u.x), u.y);
    return val * 2.0 - 1.0;
}

// The MIT License
// Copyright © 2017 Inigo Quilez
float4 noised_1_3(float3 x)
{
    float3 i = floor(x);
    float3 f = frac(x);
    
    // quintic interpolant
    float3 u = f * f * f * (f * (f * 6.0 - 15.0) + 10.0);
    float3 du = 30.0 * f * f * (f * (f - 2.0) + 1.0);
    
    // gradients
    float3 ga = hash33(i + float3(0.0, 0.0, 0.0)) * 2.0 - 1.0;
    float3 gb = hash33(i + float3(1.0, 0.0, 0.0)) * 2.0 - 1.0;
    float3 gc = hash33(i + float3(0.0, 1.0, 0.0)) * 2.0 - 1.0;
    float3 gd = hash33(i + float3(1.0, 1.0, 0.0)) * 2.0 - 1.0;
    float3 ge = hash33(i + float3(0.0, 0.0, 1.0)) * 2.0 - 1.0;
    float3 gf = hash33(i + float3(1.0, 0.0, 1.0)) * 2.0 - 1.0;
    float3 gg = hash33(i + float3(0.0, 1.0, 1.0)) * 2.0 - 1.0;
    float3 gh = hash33(i + float3(1.0, 1.0, 1.0)) * 2.0 - 1.0;
    
    // projections
    float va = dot(ga, f - float3(0.0, 0.0, 0.0));
    float vb = dot(gb, f - float3(1.0, 0.0, 0.0));
    float vc = dot(gc, f - float3(0.0, 1.0, 0.0));
    float vd = dot(gd, f - float3(1.0, 1.0, 0.0));
    float ve = dot(ge, f - float3(0.0, 0.0, 1.0));
    float vf = dot(gf, f - float3(1.0, 0.0, 1.0));
    float vg = dot(gg, f - float3(0.0, 1.0, 1.0));
    float vh = dot(gh, f - float3(1.0, 1.0, 1.0));
    
    // interpolations
    return float4(
        va + u.x * (vb - va) + u.y * (vc - va) + u.z * (ve - va) +
        u.x * u.y * (va - vb - vc + vd) + u.y * u.z * (va - vc - ve + vg) +
        u.z * u.x * (va - vb - ve + vf) + (-va + vb + vc - vd + ve - vf - vg + vh) * u.x * u.y * u.z,
        
        ga + u.x * (gb - ga) + u.y * (gc - ga) + u.z * (ge - ga) +
        u.x * u.y * (ga - gb - gc + gd) + u.y * u.z * (ga - gc - ge + gg) +
        u.z * u.x * (ga - gb - ge + gf) + (-ga + gb + gc - gd + ge - gf - gg + gh) * u.x * u.y * u.z +
        
        du * (float3(vb, vc, ve) - va +
        u.yzx * float3(va - vb - vc + vd, va - vc - ve + vg, va - vb - ve + vf) +
        u.zxy * float3(va - vb - ve + vf, va - vb - vc + vd, va - vc - ve + vg) +
        u.yzx * u.zxy * (-va + vb + vc - vd + ve - vf - vg + vh))
    );
}

float FBM_1_2(float2 p, int octaves, float persistence, float lacunarity)
{
    float amplitude = 1.0;
    float frequency = 1.0;
    float total = 0.0;
    float normalization = 0.0;

    for (int i = 0; i < octaves; ++i)
    {
        float noiseValue = noise12(p * frequency);
        total += noiseValue * amplitude;
        normalization += amplitude;
        amplitude *= persistence;
        frequency *= lacunarity;
    }

    total /= normalization;
    total = total * 0.5 + 0.5;

    return total;
}

float FBM_1_3(float3 p, int octaves, float persistence, float lacunarity)
{
    float amplitude = 1.0;
    float frequency = 1.0;
    float total = 0.0;
    float normalization = 0.0;

    for (int i = 0; i < octaves; ++i)
    {
        float noiseValue = noise13_float(p * frequency);
        total += noiseValue * amplitude;
        normalization += amplitude;
        amplitude *= persistence;
        frequency *= lacunarity;
    }

    total /= normalization;
    total = total * 0.5 + 0.5;

    return total;
}

static const float3x3 m3 =
{
    0.00, 0.80, 0.60,
    -0.80, 0.36, -0.48,
    -0.60, -0.48, 0.64
};

static const float3x3 m3i =
{
    0.00, -0.80, -0.60,
    0.80, 0.36, -0.48,
    0.60, -0.48, 0.64
};

float4 FBM_D_1_4(float3 x, int octaves)
{
    float f = 1.98; // could be 2.0
    float s = 0.49; // could be 0.5
    float a = 0.0;
    float b = 0.5;
    float3 d = float3(0.0, 0.0, 0.0);
    float3x3 m = float3x3(
        1.0, 0.0, 0.0,
        0.0, 1.0, 0.0,
        0.0, 0.0, 1.0);
    
    for (int i = 0; i < octaves; i++)
    {
        float4 n = noised_1_3(x);
        a += b * n.x; // accumulate values
        d += b * mul(m, n.yzw); // accumulate derivatives
        b *= s;
        x = f * mul(m3, x);
        m = f * mul(m3i, m);
    }
    return float4(a, d);
}