Как стать автором
Обновить
411.57
Тензор
Разработчик системы СБИС

Случайности не случайны

Время на прочтение 5 мин
Количество просмотров 7.3K

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

Сегодня пронаблюдаем сеанс черной магии с последующим разоблачением, или «Я угадаю твой рандом с 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, отбросить ненужные старшие биты и поделить, и - результат вы уже видели в самом начале статьи.

Теги:
Хабы:
+19
Комментарии 1
Комментарии Комментарии 1

Публикации

Информация

Сайт
sbis.ru
Дата регистрации
Дата основания
Численность
1 001–5 000 человек
Местоположение
Россия