Генератор случайных чисел на ассемблере

Задач, в которых возникает необходимость генерировать случайные числа в заданном диапазоне значений, существует великое множество: это и игры, где создание разнообразных игровых полей, движение объектов да и довольно большое количество логики может быть подчинено так называемой случайности, это и более серьезные направления, такие как шифрование (криптография) и некоторые другие области. Иными словами, любой уважающий себя разработчик всегда должен иметь под рукой генератор случайных чисел. Тем не менее термин генератор случайных чисел не совсем корректен, поскольку считается, что источники истинных случайных чисел найти довольно сложно. Поэтому, применительно к компьютерным системам архитектуры x86 используется несколько иное название - генератор псевдослучайных чисел (сокращенно ГПСЧ).

Практически у всех реализаций ГПСЧ имеется некая внутренняя переменная (или несколько переменных), которая называется инициализатором (стартовым значением) ГПСЧ. При первом выполнении функции ГПСЧ значение этой переменной присваивается из псевдослучайного источника, определяемого той или иной архитектурой (например на x86 можно задействовать для этой цели инструкцию rdtsc). В процессе дальнейшего выполнения функции ГПСЧ, та же переменная становится уже "текущим" значением ГПСЧ и содержит очередное псевдослучайное число. То есть, каждый раз при вызове функции ГПСЧ со значением этой переменной производятся некоторые операции (могут быть любыми, зависит от конкретной реализации алгоритма), целью которых является получение значения, (в идеале) максимально независимого от предыдущего.

При программировании на языках высокого уровня все достаточно прозаично, там имеется целый арсенал штатных решений, однако в ходе разработки кода на низкоуровневом языке Ассемблера зачастую приходится реализовывать процедуру создания случайного числа самостоятельно, изобретая велосипед от руля и до последней спицы или заимствуя и дорабатывая чужой код. Одним словом, возникает не просто огромное, а я бы даже сказал колоссальное поле для творчества.

16-битный код

Для начала, как всегда, приведу код для реального режима, а вдруг кому-то да потребуется :) При прямом неограниченном доступе кода к оборудованию все достаточно просто, поскольку архитектура x86 обеспечивает сразу несколько источников псевдослучайных чисел: это инструкция rdtsc (счетчик тиков), функция 0 прерывания 1Ah (счетчик тиков), порты 70-71h (системное время), порт 40h (таймер) и некоторые другие. Самый компактный генератор выглядит следующим образом:

Да, действительно подобное решение можно применять в случае, когда очень критична длина кода и требуется получить единственное случайное значение. Тем не менее описанная реализация имеет один существенный недостаток: когда вы применяете подобный генератор в потоковом режиме (требуется создать N-ое количество значений), вы сразу же обнаруживаете его линейность.
Более продвинутый собрат, который обеспечивает очень хороший разброс значений, следующий:

Функция принимает на входе в регистре si минимальное число, а в регистре di максимальное число диапазона, в котором генерируется случайное число (общий диапазон генерируемых значений: 0..65535). На выходе в регистре AX получаем псевдослучайное число. Генератор использует сразу две внутренние переменные, поэтому не забудьте их описать:

32-битный код

С кодом под Windows все немного сложнее. В процессе изучения материала, найденного в Сети, выяснилось что уже достаточно давно существует так называемый линейный конгруэнтный метод, как один из методов генерации псевдослучайных чисел, суть которого сводится к вычислению последовательности случайных чисел на основе начального значения с использованием достаточно простого алгоритма. Существует несколько вариаций метода, в том числе и смешанный конгруэнтный метод, самой известной реализацией которого является так называемый минимальный стандартный генератор случайных чисел, предложенный Стивеном Парком (Stephen Park) и Кейтом Миллером (Keith Miller) в 1988 году, так же называемый минимальным генератором Парка-Миллера. В общем то, не составило большого труда собрать воедино разрозненную информацию для написания "собственного" генератора случайных чисел на FASM.
Код я реализовал в виде процедуры, что бы удобнее было использовать её в своих проектах, вот и сам исходник:

Я попытался сделать процедуру GetRandomNumber наиболее универсальной в использовании, поэтому она принимает на входе два параметра: minValue и maxValue, задающие (соответственно) начальное и конечное числа диапазона, в котором сформируется псевдослучайное число. Код процедуры начинается (строка 3) с помещения в регистр eax стартового(инициализатора)/предыдущего числа последовательности (переменная seed). Если обратить внимание на описание линейного конгруэнтного метода, то можно заметить, что значение переменной используется в качестве начального/предыдущего при генерировании текущего члена последовательности. В строке 4 мы проверяем не является ли стартовое/предыдущее число нулевым, и если оно таковым является (что для алгоритма недопустимо) - то уходим на генерирование стартового числа при помощи системной функции GetTickCount (строка 7), возвращающей количество миллисекунд, прошедших с момента запуска системы, а затем инициализируем переменную seed полученным значением. Таким образом, функция GetTickCount используется у нас для создания стартового члена последовательности (инициализатора), а так же в случае, если какой-либо член последовательности на любом шаге оказался вдруг нулевым.

В строках 11-27 реализован непосредственно сам алгоритм генерирования случайного числа. Давайте попробуем рассмотреть его подробнее. В строках 11-13 происходит деление предыдущего числа последовательности на константу 127773 (которая является одной из констант линейного конгруэнтного метода). Затем частное от деления сохраняем (в стек), и умножаем получившийся остаток на вторую константу 16807. Далее восстанавливаем сохраненное частное от первого деления (из стека), а затем сохраняем (в стек) уже частное от второго деления, далее перемножаем частное от первого деления с третьей константой 2836. Восстанавливаем (из стека) частное от второго деления, вычитаем из неё значение результата перемножения и получившееся значение сохраняем в переменную seed для использования при вычислении следующего числа последовательности (при последующих вызовах процедуры).
Но это еще не все, теперь перед нами стоит локальная задача обеспечить вхождение полученного числа в заданный (входными параметрами функции) диапазон, собственно код, размещенный в строках 25-31 для этого и предназначается.

Отдельно бы хотелось поговорить о внутренней переменной seed. Поскольку переменная фигурирует в коде нашего генератора случайных чисел, она должна иметь разрядность двойного слова и размещаться в секции данных:

Инициализировать переменную seed необходимо непременно значением 0, потому как при внимательном изучении алгоритма процедуры можно заметить, что стартовое число генерируется только в том случае, если переменная равна 0, а все очередные значения последовательности вырабатываются вычислениями относительно предыдущего значения.
Вызов процедуры генерации случайного числа в коде приложения производится командой:

,где входные параметры A и B представляют из себя числа (0..4294967295), определяющие соответственно начальное и конечное значения диапазона, в котором должно быть сгенерировано случайное число. Выходным параметром является регистр eax, в котором и возвращается случайное число.