Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Можно ли достоверно предсказать будущее хоть на немного вперед? Иногда - вполне, надо только много везения... или немного знаний.
Сегодня пронаблюдаем сеанс черной магии с последующим разоблачением, или «Я угадаю твой рандом с 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
Что же там "под капотом"?
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()в текущем сеансе будут повторяться.
Собственно, мы только что убедились, что если "случайности не случайны", то для криптографии тут места точно нет. Но что это за "простой линейный алгоритм"?
Идем на официальное 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, отбросить ненужные старшие биты и поделить, и - результат вы уже видели в самом начале статьи.
