Blog. Just Blog

Генератор xoshiro128 на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail 05.07.2021 | Категория: Образ мышления: Assembler | Автор: ManHunter
Семейство xoshiro (xoroshiro) - это высокоскоростные и очень эффективные алгоритмы генерации псевдослучайных чисел общего назначения с хорошим распределением. Свое название генераторы получили от используемых в них операций XOR/Shift/Rotate. Разные варианты генераторов используют для рабочего буфера разные объемы памяти, а также реализованы как в 64-битной, так и в 32-битной версии. У меня тут будет 32-битный вариант xoshiro128 с периодом 2128.

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

Переходим к программированию. Как можно догадаться из суффикса названия, для работы генератора потребуется 128 бит, то есть 4 DWORD'а.
Code (Assembler) : Убрать нумерацию
  1. ;---------------------------------------------
  2. ; Данные для генератора случайных чисел
  3.  
  4. s  rd 4
Дальше выполняется инициализация. В оригинальном алгоритме есть два варианта инициализации - "короткая" и "длинная". Они отличаются только количеством холостых прокруток генератора, соответственно, 264 и 296 раз. Я решил использовать второй вариант.
Code (Assembler) : Убрать нумерацию
  1. ;---------------------------------------------
  2. ; Инициализация генератора случайных чисел
  3. ; stdcall long_jump,seed
  4. ;---------------------------------------------
  5. proc long_jump seed:DWORD
  6.         locals
  7.              s0 dd ?
  8.              s1 dd ?
  9.              s2 dd ?
  10.              s3 dd ?
  11.         endl
  12.  
  13.         pusha
  14.  
  15.         ; Начальное "засеивание" генератора
  16.         mov     edi,s
  17.         mov     eax,[seed]
  18.         rol     eax,1
  19.         xor     eax,0x1C580662
  20.         stosd
  21.         rol     eax,3
  22.         add     eax,0x0B6F099F
  23.         stosd
  24.         rol     eax,5
  25.         xor     eax,0xB523952E
  26.         stosd
  27.         rol     eax,7
  28.         sub     eax,0xCCF5A0EF
  29.         stosd
  30.  
  31.         ; Холостая прокрутка генератора для инициализации
  32.         lea     edi,[s0]
  33.         push    edi
  34.         xor     eax,eax
  35.         stosd
  36.         stosd
  37.         stosd
  38.         stosd
  39.  
  40.         xor     ebx,ebx
  41. .loc_for_1:
  42.         xor     ecx,ecx
  43. .loc_for_2:
  44.         mov     eax,[.lj+ebx*4]
  45.         and     eax,1
  46.         shl     eax,cl
  47.         jz      @f
  48.  
  49.         mov     esi,s
  50.         lodsd
  51.         xor     [s0],eax
  52.         lodsd
  53.         xor     [s1],eax
  54.         lodsd
  55.         xor     [s2],eax
  56.         lodsd
  57.         xor     [s3],eax
  58. @@:
  59.         stdcall next
  60.  
  61.         inc     ecx
  62.         cmp     ecx,32
  63.         jb      .loc_for_2
  64.  
  65.         inc     ebx
  66.         cmp     ebx,4
  67.         jb      .loc_for_1
  68.  
  69.         pop     esi
  70.         mov     edi,s
  71.         movsd
  72.         movsd
  73.         movsd
  74.         movsd
  75.  
  76.         popa
  77.         ret
  78.  
  79. .lj:    dd 0xB523952E
  80.         dd 0x0B6F099F
  81.         dd 0xCCF5A0EF
  82.         dd 0x1C580662
  83. endp
Также стоит упомянуть начальное "засеивание" рабочего буфера генератора. В комментариях к оригинальному коду просто сказано, что буфер не должен быть полностью нулевым, а все действия по его заполнению отдаются целиком на откуп программиста. Я добавил свой вариант заполнения, который показался мне рабочим, вы можете заменить его на любой другой. В принципе, достаточно инициализировать ненулевым значением любой из четырех DWORD'ов буфера.

Функции генерации также представлены в трех вариантах - xoshiro128+, xoshiro128++ и xoshiro128**. Версии с "+" самые скоростные, но при этом имеют незначительную статистическую уязвимость, связанную со слабыми младшими битами. Поэтому рекомендуется использовать только старшие биты ее результата или же использовать "плюсовой" xoshiro128 для генерации вещественных чисел. Впрочем, это относится исключительно к каким-нибудь чувствительным решениям, где даже минимальные просчеты недопустимы. Для подавляющего большинства прикладных задач это никакого значения не имеет.

Самая первая версия алгоритма - xoshiro128+, количеством "плюсов" обозначено количество операций сложения, используемых при генерации.
Code (Assembler) : Убрать нумерацию
  1. ;---------------------------------------------
  2. ; Получить случайное число xoshiro128+
  3. ; stdcall next
  4. ; на выходе EAX - случайное число
  5. ;---------------------------------------------
  6. proc next
  7.         pusha
  8.  
  9.         mov     ecx,[s+3*4]
  10.         add     ecx,[s+0*4]
  11.         mov     ebx,[s+1*4]
  12.         shl     ebx,9
  13.  
  14.         mov     eax,[s+0*4]
  15.         xor     [s+2*4],eax
  16.         mov     eax,[s+1*4]
  17.         xor     [s+3*4],eax
  18.         mov     eax,[s+2*4]
  19.         xor     [s+1*4],eax
  20.         mov     eax,[s+3*4]
  21.         xor     [s+0*4],eax
  22.  
  23.         xor     [s+2*4],ebx
  24.  
  25.         mov     eax,[s+3*4]
  26.         mov     ebx,eax
  27.         shl     eax,11
  28.         shr     ebx,(32-11)
  29.         or      eax,ebx
  30.         mov     [s+3*4],eax
  31.  
  32.         mov     [esp+28],ecx
  33.  
  34.         popa
  35.         ret
  36. endp
Чуть посложнее версия xoshiro128++. Как вы догадались из названия, тут используется уже две операции сложения.
Code (Assembler) : Убрать нумерацию
  1. ;---------------------------------------------
  2. ; Получить случайное число xoshiro128++
  3. ; stdcall next
  4. ; на выходе EAX - случайное число
  5. ;---------------------------------------------
  6. proc next
  7.         pusha
  8.  
  9.         mov     eax,[s+3*4]
  10.         add     eax,[s+0*4]
  11.         mov     ebx,eax
  12.         shl     eax,7
  13.         shr     ebx,(32-7)
  14.         or      eax,ebx
  15.         add     eax,[s+0*4]
  16.         mov     ecx,eax
  17.  
  18.         mov     ebx,[s+1*4]
  19.         shl     ebx,9
  20.  
  21.         mov     eax,[s+0*4]
  22.         xor     [s+2*4],eax
  23.         mov     eax,[s+1*4]
  24.         xor     [s+3*4],eax
  25.         mov     eax,[s+2*4]
  26.         xor     [s+1*4],eax
  27.         mov     eax,[s+3*4]
  28.         xor     [s+0*4],eax
  29.  
  30.         xor     [s+2*4],ebx
  31.  
  32.         mov     eax,[s+3*4]
  33.         mov     ebx,eax
  34.         shl     eax,11
  35.         shr     ebx,(32-11)
  36.         or      eax,ebx
  37.         mov     [s+3*4],eax
  38.  
  39.         mov     [esp+28],ecx
  40.  
  41.         popa
  42.         ret
  43. endp
Версия xoshiro128** предотвращает появление линейных артефактов в младших битах, так что именно этот алгоритм рекомендуется к использованию, хотя он и имеет более низкую скорость работы. Все три функции отличаются друг от друга очень незначительно, а инициализация так и вовсе одинаковая.
Code (Assembler) : Убрать нумерацию
  1. ;---------------------------------------------
  2. ; Получить случайное число xoshiro128**
  3. ; stdcall next
  4. ; на выходе EAX - случайное число
  5. ;---------------------------------------------
  6. proc next
  7.         pusha
  8.  
  9.         xor     edx,edx
  10.         mov     eax,[s+1*4]
  11.         mov     ecx,5
  12.         mul     ecx
  13.         mov     ebx,eax
  14.         shl     eax,7
  15.         shr     ebx,(32-7)
  16.         or      eax,ebx
  17.         xor     edx,edx
  18.         mov     ecx,9
  19.         mul     ecx
  20.         mov     ecx,eax
  21.  
  22.         mov     ebx,[s+1*4]
  23.         shl     ebx,9
  24.  
  25.         mov     eax,[s+0*4]
  26.         xor     [s+2*4],eax
  27.         mov     eax,[s+1*4]
  28.         xor     [s+3*4],eax
  29.         mov     eax,[s+2*4]
  30.         xor     [s+1*4],eax
  31.         mov     eax,[s+3*4]
  32.         xor     [s+0*4],eax
  33.  
  34.         xor     [s+2*4],ebx
  35.  
  36.         mov     eax,[s+3*4]
  37.         mov     ebx,eax
  38.         shl     eax,11
  39.         shr     ebx,(32-11)
  40.         or      eax,ebx
  41.         mov     [s+3*4],eax
  42.  
  43.         mov     [esp+28],ecx
  44.  
  45.         popa
  46.         ret
  47. endp
В приложении примеры программ с исходными текстами, которые используют алгоритмы xoshiro128+, xoshiro128++ и xoshiro128** для генерации псевдослучайных чисел.

Примеры программ с исходными текстами (FASM)Примеры программ с исходными текстами (FASM)

xoshiro128.Demo.zip (9,522 bytes)


Поделиться ссылкой ВКонтакте
Просмотров: 1216 | Комментариев: 3

Внимание! Статья опубликована больше года назад, информация могла устареть!

Комментарии

Отзывы посетителей сайта о статье
ManHunter (06.07.2021 в 10:51):
Добавил алгоритм xoshiro128+, архив обновлен.
ManHunter (05.07.2021 в 14:22):
Конечно бит. Поправил, спасибо!
XopHeT (05.07.2021 в 14:20):
128 байт замените на 128 бит.
Сорри,  на телефоне не нажать ctrl+enter

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал
Я в Telegram
Ограничение по возрасту 16+ Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Метки статей
.NET (32), AJAX (5), Assembler (378), COM (44), CSS (44), Exif (15), FASM (8), Firefox (7), HDD (17), Hello Teddy (9), HTML (53), iconBIT (4), JavaScript (78), MySQL (13), Nikon (19), PDF (10), PHP (125), Samsung (6), SEO (12), Sublime Text (9), Telegram (5), TintonLife (4), UGREEN (4), Windows 7 (67), аккумуляторы (23), аксессуары (12), анализаторы файлов (8), архиваторы (6), аттракционы (7), безопасность (55), браузеры (16), бытовая техника (21), варенье (19), ВВЦ (9), ВДНХ (14), видео (20), Воробьевы горы (9), вторые блюда (129), выпечка (31), выставки (120), генератор ПСЧ (10), графика (122), десерты (31), Египет (9), заготовки на зиму (47), закуска (23), закуска к пиву (26), зарядные устройства (24), защита (15), зоопарки (10), игры (36), иконки (22), интерфейс (26), исследование защиты (325), каша (4), клавиатура (7), Коломенское (37), консоль (7), концерты (52), Кузьминки (4), куклы (27), ледяные скульптуры (6), мои программы (70), мониторы (6), музеи (78), мультимедиа (83), мясо (63), напитки (14), ноутбуки (8), обфускация (7), окна (71), оформление сайта (51), парки Москвы (7), песчаные скульптуры (13), плееры (10), подводная съемка (4), поздравления (135), полезные функции (47), прохождения (4), процессы (25), птица (23), путешествия (26), распаковка (22), реверсинг (53), регулярные выражения (5), рыба (35), салаты (19), сброс триала (4), сеть (37), система (179), Сокольники (8), соусы (16), супы (14), телефоны (10), Тунис (6), умный дом (15), файлы справки (7), фаст-фуд (19), фестиваль цветов (5), флешки (6), фото (23), хеши (18), числа (8), юмор (12), яйца (19), Яндекс (11)
Вам помог этот сайт?
Сказать спасибо! Поблагодарили 36,245 раз
<< 2025 - МАРТ >>
Пн Вт Ср Чт Пт Сб Вс
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
Всемирный день социальной работы
День воссоединения Крыма с Россией
День Парижской коммуны
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Enter
Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Яндекс тИЦ: {YANDEX_TIC} Яндекс ИКС: 360
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2025
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.07 сек. / MySQL: 2 (0.005 сек.) / Память: 4.5 Mb
Наверх