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

Генератор случайных чисел XorShift128 напоминает уже известное вам семейство генераторов xoshiro128. Из названия понятно, что тут используются только команда XOR и сдвиговые команды SHL/SHR, а период равняется 2¹²⁸-1. В алгоритме отсутствуют операции деления и умножения, поэтому его можно использовать в тех микроконтроллерах, где таких ассемблерных операций нет в принципе. Также генератор XorShift является одними из самых быстрых генераторов случайных чисел.

Читать статью целиком »

Поиск подстроки в строке по алгоритму Карпа-Рабина

Когда речь заходит об алгоритмах точного поиска подстроки в строке, то обычно все так или иначе сводится к последовательному сравнению символов. Но есть группа алгоритмов, которые основаны не на сравнении символов, а на сравнении числовых данных - хешей. Одним из таких алгоритмов является алгоритм Карпа-Рабина. Его принцип достаточно простой: вычисляется хеш от строки поиска, затем вычисляется хеш от фрагмента строки, в которой производится поиск. Длина фрагмента равна длине искомой строки. Если хеши равны, то выполняется дополнительное посимвольное сравнение, если не равны, то продвигаемся по строке дальше. Казалось бы, что выигрыша тут никакого быть не может, ведь вместо сравнения вычислительные ресурсы тратятся на хеширование. Однако, как показывает практика, для поиска совпадения это гораздо эффективнее, чем сравнение отдельных символов строк. Вместо O(n*m) операций можно добиться среднего результата O(n+m), где n - длина исходной строки, а m - длина искомой строки. К тому же алгоритм Карпа-Рабина не требует выделения дополнительной памяти для своей работы.

Читать статью целиком »

Алгоритм быстрой сортировки на Ассемблере

Алгоритм быстрой сортировки появился еще на заре компьютерной эпохи в 1960 году. И до сих пор он остается одним из самых быстрых универсальных алгоритмов сортировки массивов. Несмотря на некоторые недостатки в виде наличия рекурсивных вызовов, алгоритм быстрой сортировки очень прост в реализации, не требует выделения дополнительной памяти и даже может быть распараллелен между несколькими подпроцессами.

Читать статью целиком »

Использование системных функций хеширования

Я уже выкладывал на сайте ассемблерные реализации алгоритмов хеширования MD4, MD5 и SHA1. Но в Windows есть уже готовые функции для подсчета не только этих хешей, но и некоторых других. Конечно, делать все самому гораздо приятнее для души и полезнее для мозгов, но почему бы не переложить часть работы на систему? Как говорил один мой хороший товарищ: "У лошади голова большая, вот пусть она и думает".

Читать статью целиком »

Как узнать сетевое имя компьютера и название домена

Маленький сниппет для получения сетевого имени компьютера и названия домена. Но сперва структура, которая нам понадобится для работы.C помощью функции NetWkstaGetInfo можно получить информацию о рабочей станции. Полнота информации зависит от кода запрошенной структуры и уровня доступа пользователя. Самый низкий уровень - 100-й - доступен для всех. 101-й код требует как минимум авторизованного пользователя, выше уже необходим доступ с правами администратора.Обратите внимание, что саму структуру WKSTA_INFO_100 в приложении хранить не надо, она создается автоматически где-то в системе. Вся работа выполняется через указатель на эту структуру.

Читать статью целиком »