Можно ли достоверно предсказать будущее хоть на немного вперед? Иногда - вполне, надо только много везения... или немного знаний.

Сегодня пронаблюдаем сеанс черной магии с последующим разоблачением, или «Я угадаю твой рандом с 3 строк!»:

Немного магии

tst=# SELECT r random, magic(r) random_next FROM random() r;
       random       |    random_next
--------------------+--------------------
 0.3921143477755571 | 0.6377947747296489

tst=# SELECT r random, magic(r) random_next FROM random() r;
       random       |    random_next
--------------------+--------------------
 0.6377947747296489 | 0.5727554063674667

tst=# SELECT r random, magic(r) random_next FROM random() r;
       random       |    random_next
--------------------+--------------------
 0.5727554063674667 | 0.4979625995285346
Ты угадал следующий random оба раза?..
Ты угадал следующий random оба раза?..

Что же там "под капотом"?

CREATE OR REPLACE FUNCTION magic(r double precision) RETURNS double precision AS $$
  SELECT
    (
      (
        (r & x'FFFFFFFFFFFF'::bigint) * (mul & x'000000000FFF'::bigint)
      + (r & x'000FFFFFFFFF'::bigint) * (mul & x'000000FFF000'::bigint)
      + (r & x'000000FFFFFF'::bigint) * (mul & x'000FFF000000'::bigint)
      + (r & x'000000000FFF'::bigint) * (mul & x'FFF000000000'::bigint)
      + add
      ) & x'FFFFFFFFFFFF'::bigint
    )::double precision / x'1000000000000'::bigint
  FROM
    (VALUES(
      (r * x'1000000000000'::bigint)::bigint
    , x'0005deece66d'::bigint
    , x'000b'::bigint
    )) T(r, mul, add)
$$ LANGUAGE sql;

Но как и почему это работает? Обратимся к документации:

Функция random() использует простой линейный конгруэнтный алгоритм. Она работает быстро, но не подходит для криптографических приложений; более безопасная альтернатива имеется в модуле pgcrypto. Если воспользоваться функцией setseed() и вызывать её с одним и тем же аргументом, результаты последующих вызовов random() в текущем сеансе будут повторяться.

Собственно, мы только что убедились, что если "случайности не случайны", то для крипт��графии тут места точно нет. Но что это за "простой линейный алгоритм"?

We Need To Go Deeper
We Need To Go Deeper

Идем на официальное github-зеркало PostgreSQL и находим определение setseed в float.c:

/*
 *		setseed		- set seed for the random number generator
 */
Datum
setseed(PG_FUNCTION_ARGS)
{
	float8		seed = PG_GETARG_FLOAT8(0);
	uint64		iseed;

  // ...
  
	/* Use sign bit + 47 fractional bits to fill drandom_seed[] */
	iseed = (int64) (seed * (float8) UINT64CONST(0x7FFFFFFFFFFF));
	drandom_seed[0] = (unsigned short) iseed;
	drandom_seed[1] = (unsigned short) (iseed >> 16);
	drandom_seed[2] = (unsigned short) (iseed >> 32);
	drandom_seed_set = true;

	PG_RETURN_VOID();
}

Уже интересно - оказывается из float8-аргумента используется всего 48 бит.

А теперь поднимемся чуть выше:

/*
 *		drandom		- returns a random number
 */
Datum
drandom(PG_FUNCTION_ARGS)
{
	float8		result;

	/* Initialize random seed, if not done yet in this process */
	if (unlikely(!drandom_seed_set))
	{
		/*
		 * If possible, initialize the seed using high-quality random bits.
		 * Should that fail for some reason, we fall back on a lower-quality
		 * seed based on current time and PID.
		 */
		if (!pg_strong_random(drandom_seed, sizeof(drandom_seed)))
		{
			TimestampTz now = GetCurrentTimestamp();
			uint64		iseed;

			/* Mix the PID with the most predictable bits of the timestamp */
			iseed = (uint64) now ^ ((uint64) MyProcPid << 32);
			drandom_seed[0] = (unsigned short) iseed;
			drandom_seed[1] = (unsigned short) (iseed >> 16);
			drandom_seed[2] = (unsigned short) (iseed >> 32);
		}
		drandom_seed_set = true;
	}
  
	/* pg_erand48 produces desired result range [0.0 - 1.0) */
	result = pg_erand48(drandom_seed);

	PG_RETURN_FLOAT8(result);
}

Название функции pg_erand48 подсказывает нам, что мы на верном пути - найдем ее в erand48.c:

/*
 * Generate a random floating-point value using caller-supplied state.
 * Values are uniformly distributed over the interval [0.0, 1.0).
 */
double
pg_erand48(unsigned short xseed[3])
{
	uint64		x = _dorand48(xseed);

	return ldexp((double) (x & UINT64CONST(0xFFFFFFFFFFFF)), -48);
}

Еще поднимемся на шаг за _dorand48:

/* These values are specified by POSIX */
#define RAND48_MULT		UINT64CONST(0x0005deece66d)
#define RAND48_ADD		UINT64CONST(0x000b)

/* POSIX specifies 0x330e's use in srand48, but the other bits are arbitrary */
#define RAND48_SEED_0	(0x330e)
#define RAND48_SEED_1	(0xabcd)
#define RAND48_SEED_2	(0x1234)

static unsigned short _rand48_seed[3] = {
	RAND48_SEED_0,
	RAND48_SEED_1,
	RAND48_SEED_2
};

/*
 * Advance the 48-bit value stored in xseed[] to the next "random" number.
 *
 * Also returns the value of that number --- without masking it to 48 bits.
 * If caller uses the result, it must mask off the bits it wants.
 */
static uint64
_dorand48(unsigned short xseed[3])
{
	/*
	 * We do the arithmetic in uint64; any type wider than 48 bits would work.
	 */
	uint64		in;
	uint64		out;

	in = (uint64) xseed[2] << 32 | (uint64) xseed[1] << 16 | (uint64) xseed[0];

	out = in * RAND48_MULT + RAND48_ADD;

	xseed[0] = out & 0xFFFF;
	xseed[1] = (out >> 16) & 0xFFFF;
	xseed[2] = (out >> 32) & 0xFFFF;

	return out;
}

А вот и волшебные константы!

Так что такое random()?

Теперь у нас достаточно информации, чтобы понять, как вычисляется значение random().

"Посев"

При первом запросе random() в рамках PostgreSQL-процесса три 16-битных слова (48 бит) инициализируются значениями now-таймстампа "проксоренных" с PID процесса:

			TimestampTz now = GetCurrentTimestamp();
			uint64		iseed;

			/* Mix the PID with the most predictable bits of the timestamp */
			iseed = (uint64) now ^ ((uint64) MyProcPid << 32);
			drandom_seed[0] = (unsigned short) iseed;
			drandom_seed[1] = (unsigned short) (iseed >> 16);
			drandom_seed[2] = (unsigned short) (iseed >> 32);

В последующем именно этот массив можно "засеять" своим значением с помо��ью setseed.

Шаг вычислений

При каждом следующем обращении этот массив рассматриваются как единое 48-битное число, которое умножается на RAND48_MULT (0x0005deece66d) и добавляется RAND48_ADD (0x000b).

Результат сохраняется обратно и возвращается в виде double, состоящего из младших 48 бит.

Эмулируем шаг вычислений на SQL

Фактически, надо просто взять последнее известное значение random(), умножить да сложить, но есть нюансы.

double precision (double) <-> bigint (uint64)

В C-исходниках одни и те же двоичные данные используются то как doublе,то как uint64 - в SQL мы так не можем. Зато можем призвать на помощь знание стандарта хранения чисел с плавающей точкой IEEE754 и математику.

По стандарту, для хранения мантиссы используются младшие 52 бита. То есть наш 48-битный результат double precision прямо там и лежит, причем порядок обнулен - а, значит, достаточно умножить его на 2^48, и мы получим целочисленное bigint-представление:

SELECT (r::double precision * x'1000000000000'::bigint)::bigint;

Аналогично в обратную сторону:

SELECT r::double precision / x'1000000000000'::bigint;

Псевдодлинная арифметика

Теперь достаточно лишь умножить на 0x0005deece66d, и...

ОШИБКА:  bigint вне диапазона

Вполне понятно - взяли 48-битное число, умножили на 35-битное - в 64 бита не влезли.

Но нам же и не нужно даже 64 бита - всего лишь младшие 48! Умножим наши значения "столбиком" как 12-битные слова (поскольку 16-битные все-таки при умножении вылезают в знаковый бит) с ограничением разрядности:

         12 12 12 12
48 bit =  A  B  C  D
        * E  F  G  H
--------------------
        |AH BH CH DH = A B C D * 0 0 0 H
      AG|BG CG DG    = 0 B C D * 0 0 G 0
   AF BF|CF DF       = 0 0 C D * 0 F 0 0
AE BE CE|DE          = 0 0 0 D * E 0 0 0

Осталось только это все сложить, добавить 0x000b, отбросить ненужные старшие биты и поделить, и - результат вы уже видели в самом начале статьи.