!note https://old.reddit.com/r/C_Programming/comments/1kf7l7w/_/mqpavfa/
!profile openai
!:model gpt-4.1
!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
Let's clarify what the function does, show the relevant equations, and see if we can find states that collide (map to the same next state), or that collapse (map to the all-zero state, instant cycle).
Given:
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;
}Let's write it as:
Let ((s_0, s_1)) be the input state.
-
(m = s_0 + s_1)
-
(s_0' = m + \text{rol}(s_0, 26))
-
(s_1' = m \oplus \text{rol}(s_1, 35))
Where (\text{rol}(x, n)) is the rotation left by (n) bits.
Your question is:
- Are there nonzero inputs that map to the zero state?
- Or, more generally, do two different states map to the same next state?
We want to find ((s_0, s_1)\neq(0,0)) such that: [ \begin{align*} s_0' & = 0 \ s_1' & = 0 \end{align*} ]
Write the update equations: [ \begin{align*} s_0' &= m + \text{rol}(s_0, 26) = 0\ s_1' &= m \oplus \text{rol}(s_1, 35) = 0\ \end{align*} \Rightarrow \begin{align*} m &= -\text{rol}(s_0, 26) \ m &= \text{rol}(s_1, 35) \end{align*} ] So, substituting: [ -\text{rol}(s_0, 26) = \text{rol}(s_1, 35) ] [ m = s_0 + s_1 = \text{rol}(s_1,35) ] But also, (m = -\text{rol}(s_0,26)).
So: [ s_0 + s_1 = \text{rol}(s_1, 35) \ s_0 + s_1 = -\text{rol}(s_0, 26) ]
So, given one value, can we solve for the other?
Let’s pick (s_1 = x,\ s_0 = y):
[ y + x = \text{rol}(x, 35) ] [ y + x = -\text{rol}(y, 26) ]
Subtract: [ \text{rol}(x,35) + \text{rol}(y,26) = 0 \to \text{rol}(x,35) = -\text{rol}(y,26) ]
So, let's try a simple guess:
- Let (x = a,\ y = -a). Let's try if that's possible.
So, [ y + x = 0 = \text{rol}(x,35) ] So unless (x = 0), this is only true if (\text{rol}(x,35) = 0\ \implies x = 0).
So (x = y = 0): trivial solution.
Try another approach.
Suppose (x \neq 0):
Let's assign (x = t,\ y = -\text{rol}(t, 35) - t). Let's test if such a (y) works. Plugging into the other equation:
[ y + x = \text{rol}(x,35) \implies y = \text{rol}(x,35) - x ]
But above, we also have (y = -\text{rol}(y,26) - x).
Let's equate:
[ \text{rol}(x,35) - x = -\text{rol}(\text{rol}(x,35) - x, 26) - x\ \implies \text{rol}(x,35) = -\text{rol}(\text{rol}(x,35) - x, 26) ]
This becomes very messy, but let's try a simple guess: what if (x) is an order-2 element under rotation? That is, (\text{rol}(x, n) = -x)?
Set (x =) any value such that (\text{rol}(x,35) = -x).
Pick the 2-cycle values for 64-bit rotations:
For an order-2 element under 64-bit rotate-left by 35, (x \oplus \text{rol}(x,35) = 0)?
But there are only special values (possibly all ones, all zeros).
Let’s just check if we can find a pair. Let's try some quick values:
Suppose (x = 1):
[ \text{rol}(1,35) = 1 << 35 = 0x800000000 ] But since (64-35=29), so that's binary: 1<<35 = 0x800000000, not a negative of 1.
Try (x = 0xFFFFFFFFFFFFFFFF):
[ \text{rol}(x,35) = x ] So, differences above don't yield -x.
Suppose, instead, try to find a collision, i.e., two distinct ((s_0, s_1)) and ((s_0', s_1')) that map to the same next state.
Suppose ((a,b)) and ((c,d)) map to the same next state:
Let (m_1 = a + b,\ m_2 = c + d).
Then: [ \begin{align*} m_1 + \text{rol}(a,26) &= m_2 + \text{rol}(c,26) \ m_1 \oplus \text{rol}(b,35) &= m_2 \oplus \text{rol}(d,35) \end{align*} ] Let’s define (A = a - c,\ B = b - d).
Let’s try to find a nontrivial solution with (A \neq 0) or (B \neq 0).
Let’s set (b = d,\ a \neq c):
Then (m_1 = a + b,\ m_2 = c + b), so (m_1 - m_2 = a - c = A):
- First equation:
[ m_1 + \text{rol}(a,26) = m_2 + \text{rol}(c,26) \ \implies m_1 - m_2 = \text{rol}(c,26) - \text{rol}(a,26) \ \implies A = \text{rol}(c,26) - \text{rol}(a,26) ]
But (A = a - c), so:
( a - c = \text{rol}(c,26) - \text{rol}(a,26)\ \implies a + \text{rol}(a,26) = c + \text{rol}(c,26) )
So unless (a = c), this can't generally hold, unless there’s a special value where (a + \text{rol}(a,26) = c + \text{rol}(c,26)) and (a \neq c).
Is this possible?
- The function (f(x) = x + \text{rol}(x, 26)) is (almost) injective over 64 bits (if (\text{rol}) is a permutation, which it is, and addition is group operation).
- Let's suppose (a = x,\ c = x \oplus M), for some difference (M \neq 0).
- Substitute in, see if we can find (x), (M) such that:
[ x + \text{rol}(x,26) = (x \oplus M) + \text{rol}(x\oplus M, 26) ]
But unless (M = 0), these usually differ. Unless for a very specific (M).
Try putting numbers. Most likely, no solution except (M=0).
So, let's instead try both variables.
Let’s set things up as a system mod (2^{64}):
Let’s define (s = (s_0, s_1)).
Let’s seek two states with same (next) state:
Let’s set:
(m = s_0 + s_1) ( \text{next}_0 = m + \text{rol}(s_0,26)\ \text{next}_1 = m \oplus \text{rol}(s_1,35) )
Suppose two input states ((s_0, s_1)), ((t_0, t_1)) map to the same next state.
So as above:
[ (s_0 + s_1) + \text{rol}(s_0,26) = (t_0 + t_1) + \text{rol}(t_0,26)\ (s_0 + s_1) \oplus \text{rol}(s_1,35) = (t_0 + t_1) \oplus \text{rol}(t_1,35) ]
If we subtract,
Let’s suppose (s_1 = t_1), differing only in the first word, so:
[ (s_0 + s_1) + \text{rol}(s_0,26) = (t_0 + s_1) + \text{rol}(t_0,26)\ (s_0 + s_1) \oplus \text{rol}(s_1,35) = (t_0 + s_1) \oplus \text{rol}(s_1,35) ]
Second eq simplifies:
( (s_0 + s_1) \oplus \text{rol}(s_1,35) = (t_0 + s_1) \oplus \text{rol}(s_1,35) \ \implies s_0 + s_1 = t_0 + s_1 \implies s_0 = t_0 )
Thus, for equal (s_1), both equations only hold if (s_0 = t_0).
Similarly, for equal (s_0), equations only hold if (s_1 = t_1).
Thus, unless both entries differ, you can’t have a collision just by flipping one variable.
Suppose both (s_0 \neq t_0, s_1 \neq t_1).
Set:
( a = s_0,\quad b = s_1\ c = t_0,\quad d = t_1\ X = (a,b),\ Y = (c,d) )
Try for pairs where (a + b = c + d).
Set (m = a + b = c + d).
Then:
( m + \text{rol}(a,26) = m + \text{rol}(c,26)\ \implies \text{rol}(a,26) = \text{rol}(c,26) \implies a = c )
But that would mean that (b = d), so (X=Y).
Therefore, under the update, unless you have equal sums and rotations match, only possible if the states are the same.
Now, what if (a + b \neq c + d)?
Let’s generalize: suppose a degenerate state with special structure.
Suppose (a = 0, b = x), and try to land on the zero state.
Recall from above:
We need:
( m + \text{rol}(a,26) = 0\ m \oplus \text{rol}(b,35) = 0\ )
Given (a = 0):
( m = b\ m + \text{rol}(0,26) = b + 0 = b\ \implies b = 0\ )
So both zero.
Try (a = x, b = 0):
(m = x), so
[ x + \text{rol}(x,26) = 0\ x \oplus \text{rol}(0,35) = x \oplus 0 = x = 0\ ] So only (x = 0).
Therefore, the only zero-collapsing input is all zeros.
No nontrivial (nonzero) state will collapse immediately to the zero state.
No two different states seem to map to the same next state.
The mapping seems injective (at least, up to the strength of the nonlinear mixing and rotations; it's extremely resistant to collisions under analysis). The only exception is the trivial all-zeros initial state, which always maps to itself (simple 1-cycle).
- The pair ((s_0, s_1)\mapsto (next_0, next_1)) is almost always invertible because each component depends nonlinearly on the previous ones and on different rotations.
- The only potential for collapse is with all-zero input.
- Yes, (m = s_0 + s_1) compresses two words into one (irreversible).
- However, each output branch also uses a rotation of one of the starting values to effectively separate the information.
You are correct that (m=s_0 + s_1) is not invertible. But the final state values after the update cannot both simultaneously be zero unless both (s_0) and (s_1) are zero.
No nonzero state can collapse to (0,0), and no two different states seem to produce the same updated state.
If you want a mathematical proof, you'd need to check whether, more systematically, the pair of equations has any solution with input states different from output states, but in practice with 64-bit and these rotated additions/XORs, the mapping is for all intents and purposes injective, except for the trivial zero input.
You can check empirically with:
#include <stdint.h>
#include <stdio.h>
void dualmix128(uint64_t s[2]) {
uint64_t m = s[0] + s[1];
uint64_t x = m + ((s[0]<<26)|(s[0]>>(64-26)));
uint64_t y = m ^ ((s[1]<<35)|(s[1]>>(64-35)));
s[0] = x;
s[1] = y;
}
int main() {
uint64_t s[2], t[2];
for(uint64_t a=0; a<256; ++a) for(uint64_t b=0; b<256; ++b)
for(uint64_t c=0; c<256; ++c) for(uint64_t d=0; d<256; ++d)
{
s[0] = a; s[1] = b;
t[0] = c; t[1] = d;
dualmix128(s); dualmix128(t);
if(s[0] == t[0] && s[1] == t[1] && (a!=c || b!=d)) {
printf("Collision: (%llu, %llu) -> (%llu, %llu)\n", a,b,s[0],s[1]);
}
if(s[0]==0 && s[1]==0 && (a!=0 || b!=0)) {
printf("Zero collapse: (%llu, %llu)\n", a,b);
}
}
}No nontrivial collisions or collapses will appear in this small range.
- There are no nonzero states that collapse to zero.
- No two different states collide.
- The function is "accidentally" nearly a permutation on the (2^{128}) state space, except that (0,0) is a fixed point (degenerate 1-cycle).
If you had used only m to update both state variables, then the mapping would be highly compressive and likely to produce many collisions and cycles. But the use of the original state values (rotated) protects you.
If you want rigorous mathematical proof, the equations above show that searching for collapses/collisions very quickly reduces to trivial cases only.
If you want further technical insight or a more formal proof, let me know!