Dragoon
offline
Опыт:
544Активность: |
Поразрядные логические операции в JASS
В JASS отстутствуют как таковые логические операции над переменными. Возможно только применение AND/OR/NOT (хотя с помощью их комбинаций можно получить любую операцию) , да и то только к типу Boolean. Однако может возникуть необходимость выполнить, например, конъюнкцию двух переменных типа integer. Вот как раз для этого случая может пригодиться то, что я напишу далее.
Но давайте для начала вспомним, как выполняется перевод чисел из одной системы исчисления в другую. Возьмем для примера 14 и переведем в двоичную СИ. Для этого будем делать 14 на 2, пока полученное число не будет меньше 2. Получившуюся в процессе деления комбинацию остатков реверсируем и получим представление 14 в двоичной СИ. Но перейдем к примеру. DEAD URL Как видно на рисунке, получившаяся в результате последовательность цифр составляет строку "0111". Но как я уже говорил, получившуюся строку нужно еще переверунть. Значит результатом преобразование 14 из десятичной СИ в двоичную будет строка "1110". Теперь об обратных преобразованиях. Возьмем получившуюся строку "1110". Запишем под каждым символом строки его номер в этой строке, причем писать будем справа налево и первый символ будет обозначаться цифрой 0. Получится так 1110 3210 Так вот, для того, чтобы получить исходное число 14 нам всего лишь необходимо выполнить пару простых действий - буедм возводить 2 (основание СИ, в котором 14 представлено как "1110") в степень, равную цифре под символом и умножать полученное число на цифру. Лучше на примере... 1110 = 2^0 * 0 + 2^1 * 1 + 2^2 * 1+ 2^3 * 1 = 0 + 2 + 4 + 8 = 14 Вот так просто. Теперь у нас есть два алгоритма, необходимые для перевода любого числа из десятичной СИ в любую другую и обратно. Реализуем их на JASS. Так как к моменту написания данной статьи я знаю JASS на средне-базовом уровне, все алгоритмы я воплощал сначала на Delphi, а потом просто переводил их на JASS'овый синтаксис. Думаю многим Delphi роднее и ближе, поэтому буду выкладывать листинги на обоих языках. Delphi Код:
JASS Код:
Однако, как выяснилось, рекурсивные алгоритмы не оправдывают себя в JASS'е. Вследствие этого привожу альтернативный алгоритм, предложенный NETRAT'ом. Его я и использую в карте-примере. JASS Код:
Теперь вторая пара функций. Delphi Код:
JASS Код:
Вот у нас и готовы к употреблению две самых главных функции. Теперь осталось написать собственно сами логические преобразования. Результатом первой функции является строка, представляющая собой последовательность бит. Значит у нас есть возможность с каждым бито выполнить любую операцию. Перед этим снова немного теории... Присутствуют три главных логических функции - AND, OR и NOT. Все остальные являются лишь комбинациями этих функций. AND - конъюнкция, логическое умножение, возвращает истину, когда ОБА логических операнда истинны OR - дизъюнкция, логическое сложение, возвращает истину, когда хотя бы один из логических операндов истинен NOT - логическое отрицание, возвращает истину, когда логический операнд ложен, соотвественно и наоборот Так же существует еще очень интересная и важная функция - XOR. XOR - исключающее OR, возвращает истину, когда два представленных логических операнда различны. Т.е. например XOR(1,1) = 0 , так как оба операнда равны 1, а вот например XOR(1,0) = 1. Особенность этой функции в том, что дважды применив операцию XOR с одним и тем же ключом к какому-либо числу мы получим исходное. Пример : Код:
Данное свойство можно использовать например для шифрофания данных в карте и т.п. Если по совету NETRAT'а использовать в качестве ключа угол поворота какого-либо юнита на карте, и зашифровать все исходные строки XOR'ом данным ключом, то взломщик, открыв war3map.j файл, даже не сможет понять где и что располагается. Ну все, довольно теории, приступим к реализации побитовых операций. Вообще изначально думал для каждой операции писать отдельно функцию, но затем заметил, что получившиеся коды крайне похожи, ну и соответственно решил запихнуть все операции в одну функции и выбирать серией IF'ов, какую надо применить в данный момент времени. Вот что получилось JASS Код:
Серия некрасивых elseif на Delphi преобразуется в один CASE... Как видно, функция получает три параметра - s1,s2 и operation s1 - первая строка s2 - вторая строка operation - код операции, которую необходимо выполнить с битами Код:
Особый случай с операцией NOT, так как отрицание выполняется лишь с одним операндом, то s2 просто игнорируется. Однако достаточно неудобно пользоваться именно этой функцией, так как придется постоянно выполнять переводы из/в двоичную СИ. Вот для этой рутины я и написал 'оболочные' функции для каждой логической операции. JASS Код:
Вот и все. У нас теперь есть возможность работать как с отдельными битами в числах, так и с комбинациями чисел. Самое явное применение - защита загрузочных кодов. При совмещении подсчета контрольной суммы и шифровании данных получается достаточно нудно ломаемый код. Для того, чтобы использовать битовые функции в карте, вам лишь необходимо скопировать участки с фукнциям I2B, B2I, BitwiseOpertaion и Bitwise* в Custom Code участок карты. Доступ к нем можно получить через редактор триггеров, нажав на самую верхнюю строку (там название карты.w3*). В карте-примере показывается, как можно вызывать эти функции на примере двойного применения XOR. Отредактировано Dragoon, 02.05.2006 в 19:44. |
30.04.2006, 09:52 | #1
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
FellGuard
Losyash
offline
Опыт:
39,547Активность: |
Афтору респект и памятник у Кремля. Пиши ищо!! |
30.04.2006, 13:50 | #2
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
:-) |
30.04.2006, 14:02 | #3
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Резонный вопрос - ЗАЧЕМ? Это медленно и неудобно. Лучше уж тогда шифровка по словарю, но в самом деле нет необходимости применять такие методы защиты данных - это только движок и себя нагружать |
30.04.2006, 16:01 | #4
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
remal
нечто
offline
Опыт:
2,087Активность: |
1)NETRAT прав.
2) Код:
3)сам по себе рекурсивный вызов тут не нужен. обычный цикл куда лучше для производительности и восприятия 4)modulointeger выполняется медленно. используй переполнение и последующее деление. ----- а так... ничего сверхестественного... |
30.04.2006, 16:42 | #5
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
NETRAT, зачем то же разработчики языков вводят поразрядные логические операции, значит кому то это может пригодиться. Статья именно для них. Я лишь предложил самое банальное использование алгебры логики - шифрование XOR'ом.
:-)) Это банальное возведение 2 в степень. Присмотрись повнимательнее, а потом уже пиши. Экспоненциальной формулой воспользоваться не получается, поэтому обыный FOR.
|
30.04.2006, 17:04 | #6
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Dragoon это все таки разные вещи - в Асме к примеру без ЛО не обойтись - флаги вычислять, в регистры данные перекидывать. В С - это как вариант хранения сжатых данных и, безусловно, работа с флагами, в Жассе этого нет(ну не нужно это)...
Этот XOR пример показательный, но работать будет в разы(мб десятки раз) медленнее чем более эффективное кодирование по словарю 2) я думаю что ремал имел ввиду то что цикл вообще не нужен - достаточно одного прохода по символам начиная СПРАВА строки с умножением на 2 некоторого коэффициента. То есть степень двойки можно встроить внутрь цикла сложения. Боже упаси использовать для этого экспоненту от логарифма =) 3) точно не в жассе. Вообще говоря не думаю что рекурсия быстрее обычного цикла. Просто не всегда можно представить рекурсию в виде цикла 4) a mod b = a - a/b (ахтунг! - все операнды integer) Статья разве что для общего развития - показать что такое битовые операции |
30.04.2006, 17:32 | #7
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
По четвертому пункту .
Код:
Как видно, функция ModuloInteger это и делает. И кстати, a mod b = a - a/b Возьмем a = 30, b = 4 30 mod 4 = 30 - 30/4 = 30-7= 23 а вот если a mod b = a - Trunc(a/b) * b То 30 mod 4 = 30 - Trunc(30/4) * 4 = 30 - 28 = 2 Dragoon добавил: Правда, насчет цикла я чего то прогнал :) Код:
Отредактировано Dragoon, 30.04.2006 в 18:09. |
30.04.2006, 17:57 | #8
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
4) да не в этом дело, а в том что ты два раза это деление используешь, и вообще, глянь вот такую интерпретацию:
Код:
Она требует всего log(2,I)+1 делений против твоих 2 * (log(2,I)+1) делений и log(2,I)+1 умножений |
30.04.2006, 20:39 | #9
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
NETRAT, пасиб за алгоритм. Моя получается в 2-2,5 раза медленнее :( Прогнал на дельфях тесты. Времени на подобные переводы затрачивается настолько мало, что разница становися заметна только при 64 и более битах... И то это пара десятков тиков. |
30.04.2006, 20:48 | #10
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Dragoon в жассе скорость будет намного меньше. При этом это всего-лишь бинарные операции - то есть фактически простейшие - именно эти функции являются базисом и работают с триггерами(я имею ввиду триггеры, которые стоят внутри процессора), поэтому если строить специальную алгебру на базе твоего функционала, она может достаточно сильно лагать
|
01.05.2006, 18:33 | #11
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
В общем предлагаю скачать пример карты. Это тестовый образец, показывающий скорость выполнения функций. В карте я использовал те алгоритмы, которые предлагал в статье, так как они более понятны с точки зрения базовой информатики, т.е. представляют из себя автоматизированные действия человека при переводе чисел. |
01.05.2006, 20:51 | #12
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
remal
нечто
offline
Опыт:
2,087Активность: |
про рекурсию:
не представляю как рекурсия может быть быстрее в ДАННОМ случае. если ты мне покажешь наглядный пример, то не вопрос. тут у нас и не пахнет обходом в ширину/глубину и тп. про переполнение: да. я имел ввиду сдвиг. сдигаешь влево так, чтобы осталось то, что надо, а потом делаешь сдвиг вправо. ну а сдвиг - это умножение/деление на степень 2. |
02.05.2006, 00:49 | #13
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
про рекурсию :
не знаю, как устроен интерпретатор JASS'a , но в обычных языках и в асме рекурсия( при большом количестве итераций ) быстрее из-за того, что активно используется стек и регистры, а память почти не задевается. А ведь это значит, что и обычный часто выполняемый цикл можно ускорить рекурсией про переполнение:
а в JASS есть возможность быстро оформить сдвиги ? и это будет быстрее , чем использование рекурсивной функции ? И, если сможешь, приведи плиз пример есои есть эта возможность А насчет скорости - попробуй скачать карту и запустить у себя. У меня показывается, что на выполнение 1 функции BitwiseXOR(999999,999999) тратится всего 0,005 сек. А ведь в ней несколько раз конвертируются типы данных из строки в инт и наоборот, используется 8-10 вызовов функций и несколько условий. А так как числа достаточно большие,то выходные строки равны 11110100001000111111. Просто сейчас уже процессоры достаточно быстрые, чтобы оптимизация становилась уж очень необходимой. |
02.05.2006, 07:48 | #14
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Dragoon не думаю, обычный цикл в рекурсию вписывать - не даст увеличения скорости. Ибо регистры все равно быстрее чем стек, в рекурсии стек забивается очень быстро, а в обычном цикле мы используем только регистры.
Ну и, разумеется, АСМ нельзя сравнивать с жассом =) если даже целочисленная переменная в жассе занимает не менее 40 байт памяти(против 4х), дальше различия более значительные По поводу рекурсий - мя курсовая в прошлом году называлась "Реализация рекурсивных алгоритмов", так вот реально они используются только тогда, когда процесс нельзя привести к обычному циклу или когда это значительно увеличит затраты памяти/цп. Всем известно что рекурсии - самый неэффективный вариант использования памяти, но нередко алгоритмы не могут быть приведены к обычным циклам... Быстро в жассе разобрался? |
02.05.2006, 18:05 | #15
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
:((( Млин, и правда насчет рекурсии, написал мини тестик. Там 500 раз прибавляется по 1 к переменной-накопителю двумя способами. Первый - самый логичный в этом случае - это цикл. Второй способ рекурсивный. Разница в скорости выполнения аж 2-3 секунды. :( Где ж близзы в интерпретаторе так накосячить умудрились, что рекурсия не просто медленная, а супер медленная. :( Просто люблю рекурсию,и до сего момента был твердо уверен, что решения с использованием рекурсии будут быстрее своих цикловых собратьев. Ан нет, оказывается не везде
Ну вот получается прошло 4-5 дней где-то с того момента, как я сел за редактирование варика. Дня три уделил JASS'у. В принципе достаточно простой и логичный язык (в пику всяким там JBForth[эт скриптовый язык эмуляторов сервера Lineage II]), поэтому особых сложностей не возникло (пока...). Dragoon добавил: Офигеть, добавил нововведения в функции битовые. Скорость возросла просто в разы. И тут же появился вопрос : Код:
Вот это работает, а вот это - уже нет Код:
Да и еще из той же категории, если вырезать из первого примера вызов TriggerSleepAction(0.00), то и он перестает работать. Перестает работать - значит доходит до j=67 и... все . Текст процедурок можно посмотреть в статье, вроде я ничего необычного не использую, что могло бы вызвать такой эффект... Отредактировано Dragoon, 02.05.2006 в 20:16. |
02.05.2006, 19:48 | #16
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
NETRAT
offline
Опыт:
83,712Активность: |
Dragoon столкнулся с той же лажей что и я, когда начинал... Дело в том что для каждой функции у вара существует лимит выполнения по действиям и по времени. Оценить этот лимит сложно, но обнаружить достаточно просто - вставить вывод контрольных сообщений. Суть в том что когда функция превышает либо лимит операций либо лимит времени, она экстренно завершается эта штука в некоторых источниках называется Watchdog Timer. Что она при этом возвращает - хез(может Null)
В данном примере ты наблюдаешь превышение такого лимита(скорее всего по количеству действий), теперь ты понимаешь почему я говорил что подобного рода преобразования ввиду своей сложности не могут быть применены как какой-то более менее эффективный инструмент - они просто будут рубить выполнения функций. Как эта проблема разрешается? Вроде бы есть три способа: 1. Уменьшить количество действий в функции или в ее вложенных функциях 2. Использовать метод ExecuteFunc, который дает широкие возможности при работе с функциями, но не позволяет нормально передавать параметры. На самом деле я не уверен что он помогает - то есть как я ни пытался, мне он не помог. 3. Разделение функций по времени. Использование таймеров. Смысл в том чтобы разбить функцию на кусочки, промежуток времени между которыми составляет 0.00, то есть фактически функции будут выполняться по отдельности и уж точно не по порядку, но выполняться будут. В данном методе часто не обойтись без кеша и РБ-функционала. В твоем случае этот метод реализуется вызовом таймера, который будет вызывать внутри себя функцию call BitwiseXOR( 999999, 999999 ). Второй(при условии что он работает) и третий методы чреваты лагами, поэтому таймер можно ставить подольше (0.01) |
02.05.2006, 21:08 | #17
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
Ну в общем я решил эту проблему для своего случая и думаю мой способ пригодится еще кому-либо....
1) Создаем глобальную переменную булевого типа. 2) Создаем функцию-оболочку, в которой присутствует лишь вызов нужной вам функции и установление флага. Пример : Код:
3) Динамически создаем триггер и добавляем ему действие - только что созданную функцию-оболочку Код:
4) Вместо вызова функции, которая занимает значительное время, сбрасываем флаг, вызываем триггер (он запускает в новом потоке) и ждем, пока функция-оболочка установит флаг , это значит, что наша функция отработала. Вот в принципе и все. Если вам понадобится передавать параметры функции динамически, это легко решается с помощью дополнительных переменных или кэша+РБ. Лучше всего посмотреть пример, все-таки в целостном состоянии все нагляднее Dragoon добавил: И кстати, в таком состоянии битовые операции уже вполне удобоваримы по скорости ;) У меня затрачивается 0,001 с. на 9 XOR (999999,999999). Процессор - Athlon 64 3000+. |
02.05.2006, 22:01 | #18
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
FellGuard
Losyash
offline
Опыт:
39,547Активность: |
Цитата:
FellGuard добавил: Например func my_func1 takes integer i returns nothing ... call my_func2 (i) endfunc func my_func2 takes integer i returns nothing |
|
03.05.2006, 08:31 | #19
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|
Dragoon
offline
Опыт:
544Активность: |
Оба этих метода получаются достаточно неудобны и в некоторых случаях неприменимы. К примеру у тебя есть какая-либо функция, выполняющая 100000 раз в цикле определенные действия. Как тут выполнить разбиение на кусочки ? ... Потому я изначально и не стал идти этим путем |
03.05.2006, 10:47 | #20
+0/−0
Профиль |
Приват |
Поиск |
IP: Записан
|