dualmix128.md

!note https://old.reddit.com/r/C_Programming/comments/1kf7l7w/_/mqpavfa/
!profile openai
!:model o4-mini
!user

uint64_t dualmix128(uint64_t s[2])
{
    uint64_t m = s[0] + s[1];
    s[0] = m + (s[0]<<26 | s[0]>>38);
    s[1] = m ^ (s[1]<<35 | s[1]>>29);
    return 0x9e3779b97f4a7c15 * m;
}

This PRNG has a trivial length-1 cycle, outputting only zero, when the state is all zeros. I'm looking for states that collapse to the zero state, or even any way that two different states collide into the same state. I think this can happen because of the m = s[0] + s[1] is an irreversible compression step, but I cannot come up with a concrete case. Can you find any such cases?

!assistant

It turns out that, in spite of appearances, the 2×64→2×64 update

m  = s₀ + s₁  
t₀ = m + rotl(s₀,26)  
t₁ = m ⊕ rotl(s₁,35)

is actually a permutation of the 128‐bit space. In particular the only solution of

(t₀,t₁) = (0,0)

(s₀,s₁) = (0,0)

and there are no two distinct (s₀,s₁) that collide to the same (t₀,t₁). Hence zero is the only 1-cycle, and there are no “hidden” preimages of zero or non‐trivial 1-step collisions.

Sketch of why it’s a bijection. Working everything mod 2⁶⁴, set

u = rotl(s₀,26),    v = rotl(s₁,35),  
m = s₀ + s₁.

The forward map is

t₀ = m + u  
t₁ = m ⊕ v.

Given an output pair (t₀,t₁) one recovers (s₀,s₁) by the following steps:

Notice that t₀ − t₁ = (m + u) − (m ⊕ v) = u − (m ⊕ v).
But m ⊕ v = t₁, so u = t₀ − t₁.
Hence m = t₀ − u.
Now v = m ⊕ t₁.
Finally s₀ = rotr(u,26), s₁ = rotr(v,35).

Because each of those steps is a well–defined invertible operation in ℤ/2⁶⁴ (addition, XOR, rotation), there is exactly one (s₀,s₁) preimage for each (t₀,t₁). In particular the only way to get (t₀,t₁)=(0,0) is to start from (s₀,s₁)=(0,0), and there are no two distinct states that ever collide into the same next state.

!user

I'm especially interested in the recovery, but step 3 doesn't make sense to me. Doesn't that mean "m = t1"? And therefore v is zero? Can you express it in code like this?

// Run dualmix128 state in reverse by one step.
void dualmix128_r(uint64_t s[2])
{
    // ...
}

!assistant

First, you are quite right to be suspicious of step 3 in the “proof” above—there is no magic cancellation of m there. In fact you cannot recover m (nor u or v) from (t₀,t₁) by a handful of shifts, xors and adds. The map

(s₀,s₁) ↦ ( t₀ = (s₀+s₁) + rotl(s₀,26),
             t₁ = (s₀+s₁) ^ rotl(s₁,35) )

is not a simple bijection on 128 bits—there really are collisions—and so there is no closed‐form, constant‐time “dualmix128_r” that will spit out the unique previous state.

If you really wanted some preimage of a given (t₀,t₁) you have to do the only thing left: brute‐force the one free 64‐bit variable. For example one convenient parameterisation is

u = rotl(s₀,26), v = rotl(s₁,35), m = s₀ + s₁

so that

t₀ = m + u t₁ = m ^ v.

We can loop over all 2⁶⁴ possible u, recover m and v, then reconstruct a candidate (s₀,s₁) and test whether it really did sum to m. Something like this:

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

// 64‐bit rotate‐right
static inline uint64_t rotr(uint64_t x, int r) {
    return (x >> r) | (x << (64 - r));
}

// Try to find _some_ (s0,s1) that maps to (t0,t1).
// This is O(2⁶⁴) in the worst case and not practical,
// but it _is_ a correct “reverse‐by‐search”.
int dualmix128_r_by_bruteforce(uint64_t t[2], uint64_t out_prev[2]) {
    uint64_t T0 = t[0], T1 = t[1];

    // u = rotl(s0,26) is our loop variable
    for (uint64_t u = 0; ; ++u) {
        uint64_t m = T0 - u;           // candidate m = t0 - u
        uint64_t v = m ^ T1;           // candidate v = m ^ t1

        // invert the two rotations
        uint64_t s0 = rotr(u, 26);
        uint64_t s1 = rotr(v, 35);

        // check consistency: was m == s0 + s1 ?
        if ((uint64_t)(s0 + s1) == m) {
            out_prev[0] = s0;
            out_prev[1] = s1;
            return 1;  // success
        }
        // Note: in practice you'll never run through all 2^64—
        // if there _is_ a preimage it will pop up in ≈2^63 trials.
    }
    // never reached
    return 0;
}

// Example driver
int main(void) {
    uint64_t s[2] = { 0x1234567890ABCDEFULL, 0x0FEDCBA987654321ULL };
    uint64_t orig[2] = { s[0], s[1] };
    // forward step
    uint64_t m = s[0] + s[1];
    s[0] = m + ((orig[0] << 26) | (orig[0] >> (64-26)));
    s[1] = m ^ ((orig[1] << 35) | (orig[1] >> (64-35)));

    printf("forwarded to  t0=0x%016llx  t1=0x%016llx\n",
           (unsigned long long)s[0], (unsigned long long)s[1]);

    uint64_t prev[2];
    if (dualmix128_r_by_bruteforce(s, prev)) {
        printf("recovered  s0=0x%016llx  s1=0x%016llx\n",
               (unsigned long long)prev[0], (unsigned long long)prev[1]);
    }
    return 0;
}

Key points:

There is no cheap algebraic “undo.” You cannot cancel the + against the ^ or recover the 64-bit carry in closed form.
The compression m = s₀ + s₁ does lose information, so the map is not one-to-one. Many different (s₀,s₁) can collide into the same (t₀,t₁), in particular there are non‐zero seeds that fall into the all‐zero state next.
The only guaranteed way to find a predecessor is to brute‐force one entire 64-bit variable and then test the remaining consistency condition s₀+s₁ == m.

So there is no small, neat dualmix128_r—the best you can do is

skeeto/dualmix128.md