c - 无需预洗牌即可生成(非常)大的非重复整数序列

Question

背景

我有一个我编写的简单媒体客户端/服务器，我想生成一个非显而易见的时间值，我随每个命令从客户端发送到服务器。时间戳将包含相当多的数据(纳秒分辨率，即使由于现代操作系统中定时器采样的限制，它并不真正准确)等。

我正在尝试做的(在 Linux 上，在 C 中)是生成一对一的 n 位值序列(假设数据现在存储在 128 位整数数组元素中)没有重叠/冲突的值。然后，我会将一个伪随机 128 位值/数字作为“盐”，将其应用于时间戳，然后开始向服务器发送命令，增加预加盐/预散列值。

时间戳大小之所以如此之大，是因为时间戳可能必须容纳非常长的持续时间。

---

问题

如何使用初始盐值完成这样的序列(非冲突)？ The best approach that sounds along the lines of my goal is from this post, which notes :

If option 1 isn't "random" enough for you, use the CRC-32 hash of said global (32-bit) counter. There is a 1-to-1 mapping (bijection) between N-bit integers and their CRC-N so uniqueness will still be guaranteed.

但是，我不知道:

• 如果可以(有效地)扩展到 128 位数据。
• 如果对盐值进行某种加法/乘法以为序列提供初始种子会破坏它或引入冲突。

---

跟进

我意识到我可以使用来自 libssl 或类似东西的 128 位随机散列，但我希望使用相同盐值的远程服务器能够将散列时间戳转换回它们的时间戳真正的值(value)观。

谢谢。

Answer 1

您可以使用线性同余生成器。使用正确的参数，可以保证生成具有完整周期(即无冲突)的非重复序列 [唯一] 序列。

这是 random(3) 在 TYPE_0 模式下使用的。我将其调整为完整的 unsigned int 范围，种子可以是任何 unsigned int(请参阅下面的示例代码)。

我相信它可以扩展到 64 或 128 位。我会看看:https://en.wikipedia.org/wiki/Linear_congruential_generator查看有关参数的约束以防止碰撞和良好的随机性。

按照 wiki 页面指南，您可以生成一个可以将 任何 128 位值作为种子的种子，并且在生成所有可能的 128 位数字之前不会重复。

您可能需要编写一个程序来生成合适的参数对，然后测试它们的“最佳”随机性。这将是一次性操作。

获得它们后，只需将这些参数代入实际应用中的方程式即可。

---

这是我在寻找类似东西时一直在玩的一些代码:

// _prngstd -- get random number
static inline u32
_prngstd(prng_p prng)
{
    long rhs;
    u32 lhs;

    // NOTE: random is faster and has a _long_ period, but it _only_ produces
    // positive integers but jrand48 produces positive _and_ negative
#if 0
    rhs = jrand48(btc->btc_seed);
    lhs = rhs;
#endif

    // this has collisions
#if 0
    rhs = rand();
    PRNG_FLIP;
#endif

    // this has collisions because it defaults to TYPE_3
#if 0
    rhs = random();
    PRNG_FLIP;
#endif

    // this is random in TYPE_0 (linear congruential) mode
#if 0
    prng->prng_state = ((prng->prng_state * 1103515245) + 12345) & 0x7fffffff;
    rhs = prng->prng_state;
    PRNG_FLIP;
#endif

    // this is random in TYPE_0 (linear congruential) mode with the mask
    // removed to get full range numbers
    // this does _not_ produce overlaps
#if 1
    prng->prng_state = ((prng->prng_state * 1103515245) + 12345);
    rhs = prng->prng_state;
    lhs = rhs;
#endif

    return lhs;
}