NASAM: Not Another Strange Acronym Mixer

The various abbreviations became more and more unpronouncable. I give you "NASAM".

This is a new mixer that has been tested quite thoroughly. Since I don't have more than 2 machines at my disposal (a Ryzen 7 1700 and an i7-5820), testing takes quite some time. I will complete this posting with data on sparse gammas and other interesting things I may think of.

This is the fastest permutation function I am aware of that passes RRC-64-42-TF2-0.94. Tommy Ettinger's function Pelican also passes RRC-64-42-TF2-0.94 and has similar speed.

NASAM mixer in C.

uint64_t nasam(uint64_t x) {   // ror64(a, r) is a 64-bit rotation of a by r bits.   x ^= ror64(x, 25) ^ ror64(x, 47);   x *= 0x9E6C63D0676A9A99UL;   x ^= x >> 23 ^ x >> 51;   x *= 0x9E6D62D06F6A9A9BUL;   x ^= x >> 23 ^ x >> 51;   return x; }

Pelican has one advantage over NASAM; Pelican has no fixed point at 0. There are at least three obvious ways of fixing this defect, should it be deemed necessary for a particular use-case:

1. Adding a constant after the first multiplication ("rrma2xsm2xs" in this post).
2. Xoring a constant prior to rotating/xoring ("xNASAM" in this post).
3. Xoring a constant prior to rotating/xoring and after the last xor-shift ("xNASAMx" in this post).

Assuming the statistical quality of 1--3 above is at least as good as NASAM, the most interesting thing to analyze is of course speed. xNASAMx also has another property that might be of interest in some use cases.

For speed measurements, I've used Chris Wellon's shootout-program, described here.

Speed in MB/s, compiled with -Ofast -march=native. The highest speed for each mixer is marked in green, the lowest in red. The % column gives the speed relative to SplitMix64.

	i7-5820			Ryzen 7 1700
Mixer	gcc 9.2.1	clang 8.0.1	%	gcc 9.2.1	clang 8.0.1	%
baseline	10165	10213	-	8639	8681	-
splitmix64	6276	7334	100.00%	6471	6971	100.00%
rrmxmx	6091	6064	83.04%	5949	6361	91.24%
NASAM	4412	4489	61.20%	4385	4816	69.08%
Pelican	4320	4382	59.74%	4256	4638	66.53%
xNASAM	4156	4313	58.81%	3959	4632	66.45%
rrma2xsm2xs	4278	4214	58.33%	4083	4475	64.20%
xNASAMx	3921	4067	55.46%	3762	3806	54.60%

rrma2xsm2xs

The preliminary name of NASAM was rrm2xsm2xs for "2 rotations, multiply, 2 term xor-shift, multiply, 2 term xor-shift". The "rrma..." is simply an addition after the first multiply:

rrma2xsm2xs mixer in C.

uint64_t rrma2xsm2xs(uint64_t x) {   // ror64(a, r) is a 64-bit rotation of a by r bits.   x ^= ror64(x, 25) ^ ror64(x, 47);   x = x * 0x9E6C63D0676A9A99UL + C; // Avoids trivial fixpoint at 0.   x ^= x >> 23 ^ x >> 51;   x *= 0x9E6D62D06F6A9A9BUL;   x ^= x >> 23 ^ x >> 51;   return x; }

Special care would have to be taken for the constant C above to be used for anything interesting but avoiding the fix point at 0. In particular, it must not be used for "independent streams"; AFAICT, they will be strongly correlated due to the fact that C will come into play quite late in the mixing.

It is worth noting that the speed penalty compared to NASAM is small (4%--7%).

xNASAM

The same as NASAM with xor of a constant before the mixing steps. Adding instead of xoring would be equivalent to a linear offset in the sequence.

This is much more promising as a construction where the constant could be used for something resembling independent streams. Some care will have to be taken; I think there's a good way of segmenting a 64-bit stream index into an increment part and an xor-part for a total of $2^{64}$ distinct streams, each with period $2^{64}$.

xNASAM mixer in C.

uint64_t xnasam(uint64_t x, uint64_t c) {   x ^= c;   // ror64(a, r) is a 64-bit rotation of a by r bits.   x ^= ror64(x, 25) ^ ror64(x, 47);   x *= 0x9E6C63D0676A9A99UL;   x ^= x >> 23 ^ x >> 51;   x *= 0x9E6D62D06F6A9A9BUL;   x ^= x >> 23 ^ x >> 51;   return x; }

xNASAMx

The same as NASAM with xor of a constant before and after the mixing steps.

This has the interesting property that it to a small extent masks the counter and the increment used. The idea is similar to the XEX encryption mode, using NASAM as an unkeyed block cipher. This has zero cryptographic security, of course. Still it may be useful if you have a use case where a minor inconvience with regards to deducing the counter and/or increment is appropriate. The last xorstep makes the function harder to invert, without knowing the constant used.

This version is also the slowest of the mixers published here at 54%--56% of the speed of SplitMix and 80%--90% of the speed of NASAM. I somehow doubt that it behaves any better than xNASAM when considering using the constant to generate distinct streams.

xNASAMx mixer in C.

uint64_t xnasamx(uint64_t x, uint64_t c) {   x ^= c;   // ror64(a, r) is a 64-bit rotation of a by r bits.   x ^= ror64(x, 25) ^ ror64(x, 47);   x *= 0x9E6C63D0676A9A99UL;   x ^= x >> 23 ^ x >> 51;   x *= 0x9E6D62D06F6A9A9BUL;   x ^= x >> 23 ^ x >> 51;   x ^= c;   return x; }

Below, 256 subtests of 4 TB each (1 PB total) didn't show any anomalies. This of course doesn't mean that there aren't any; just that RRC-64-42-TF2-0.94 is a too weak test to detect them.

(Lack of) NASAM failures, $2^{42}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42		42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42
16	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42		42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42
32	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42		42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42
48	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42		42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42		42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42
16	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42		42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42
32	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42		42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42
48	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42		42	42	42	42	42	42	42	42	42	42	42	42	42	42	42	42