Программная реализация операций над большими числами в языке ЛЯПАС-T | ПДМ. Приложение. 2014. № 7.

Программная реализация операций над большими числами в языке ЛЯПАС-T

Представлена информация о программной реализации в виде функций на языке Ассемблер операций языка ЛЯПАС-T над большими числами. Эти функции вставляются компилятором в загружаемый модуль (файл с компилируемой программой). Реализованы два способа встраивания - через вызов подпрограммы и в виде макроса.

Software implementation of operations over large numbers in LYaPAS-T.pdf В настоящее время в программировании большое внимание уделяется быстродействию программ, особенно в области задач компьютерной криптографии. Все в этой области стремятся к сокращению времени работы программ, ищут для этого альтернативные методы программирования, рассматривают возможности реализации программ на разных языках. Но, несмотря на все усовершенствования высокоуровневых языков, более быстрыми являются программы на языках, которые «ближе» к машинному языку, т. е. являются низкоуровневыми. Среди всех языков программирования язык Ассемблера является самым низкоуровневым, поэтому программы, написанные на нём должным образом, работают быстрее программ, представляющих те же алгоритмы на других языках. В данной работе описываются функции на языке Ассемблер, реализующие арифметические операции языка программирования ЛЯПАС-Т [1] над большими числами, и способы встраивания их в загружаемый модуль. П р е д с т а в л е н и е д а н н ы х В языке ЛЯПАС-Т все операции с длинными операндами выполняются с использованием в качестве одного из операндов собственной переменной т. В предлагаемой здесь программной реализации операций ЛЯПАСа-Т над большими числами последние и переменная т представляются логическими комплексами, как описано в [1], с той только разницей, что собственная переменная представляется фиксированным комплексом, называемым собственным. В программе этот комплекс хранится в стеке. Доступ к данным, хранящимся в стеке, осуществляется через смещение от корня стека (регистр ebp). Младший элемент комплекса т расположен по адресу ebp - 64; i-й элемент находится по адресу ebp - 64 - 4i. Мощность Q комплекса т хранится по адресу ebp + 112. Когда цепочка операций начинается с некоторого комплекса Li, его значение копируется в комплекс т. Для любой последующей операции в цепочке комплекс т является первым операндом и результатом операции. 7 Далее опишем арифметические операции, интерпретирующие т как число длины 32Q бит. Все они выполняются по модулю 232Q. Пусть о g { -, +, *,/,; }. Тогда соответствующие операции могут быть выполнены следующим образом. О п е р а ц и я о Пример выполнения: L1oL2^L3. Операция выполнения действия о над числами L1 и L2 и занесения результата в L3. Выполняется записанная на языке ЛЯПАС-Т строка следующим образом: 1) L1 копируется в т; 2) над т и L2 выполняется операция о. При этом результат находится в т, а комплекс L2 не изменяется; 3) значение т копируется в комплекс L3. Таким образом, после выполнения результат операции о над числами L1 и L2 находится в L3 и в т. Следующая операция отличается от предыдущих тем, что в результате её выполнения один из параметров изменяется. Деление (операция «:») Пример выполнения: L1:L2^L3. Операция деления числа L1 на число L2 и занесения результата в L3. Выполняется записанная на языке ЛЯПАС-Т строка следующим образом: 1) L1 копируется в т; 2) т делится на L2. При этом результат (частное) находится в т, а в комплекс L2 записывается остаток от деления. Таким образом, L2 в результате выполнения операции «:» изменяется; 3) значение т копируется в комплекс L3. Таким образом, после выполнения этой операции результат деления числа L1 на число L2 (частное) находится в L3 и в т, а в L2 - остаток от деления. Все представленные операции используют функции, написанные на языке Ассемблер. Эти функции реализуют алгоритмы работы с длинными числами, описанные в книге Дональда Кнута [2], с минимальными изменениями. Генерация ассемблерного кода, реализующего функции над большими операндами языка ЛЯПАС-Т, может выполняться двумя способами. В первом случае функция оформляется как подпрограмма на языке Ассемблера с соблюдением всех соглашений о правилах определения подпрограмм в Ассемблере. Компилятором генерируются команды занесения входных аргументов операции в стек, затем команда вызова подпрограммы call и команды последующего анализа результатов работы подпрограммы. Во втором случае в компиляторе определяются функции на языке C++, которые формируют строку из команд языка Ассемблера, реализующих действия над длинными операндами. Эта строка встраивается компилятором в общую строку, представляющую результат генерации целевой программы на Ассемблере. Сравнивая эти подходы, можно сделать следующий вывод. В первом случае сокращается длина выходного кода, но увеличивается время его работы, так как вызов подпрограммы и возврат из неё занимают дополнительное время. Во втором случае имеем экономию времени работы за счёт отсутствия указанных действий, но увеличение длины кода, так как при появлении данных операций повторно соответствующий код встраивается заново. В дальнейшем экспериментально будет проведён сравнительный анализ изложенных способов генерации. Результатом работы является «состыковка» компилятора языка ЛЯПАС-Т, написанного на языке С++, с функциями работы с длинной арифметикой, написанными на языке Ассемблер. Таким образом, стала возможной работа с длинной арифметикой стандартными средствами языка ЛЯПАС-Т.

Ключевые слова

ЛЯПАС-T, длинная арифметика, LYaPAS-T, long arithmetic

Авторы

ФИООрганизацияДополнительноE-mail
Грибанов Андрей СергеевичТомский государственный университетстудент кафедры защиты информации и криптографииandreigribanovtsu@gmail.com
Сибирякова Валентина АлександровнаТомский государственный университетстарший преподавательval349@mail.ru
Всего: 2

Ссылки

Агибалов Г. П., Липский В. Б., Панкратова И. А. О криптографическом расширении и его реализации для Русского языка программирования // Прикладная дискретная математика. 2013. №3(21). С. 93-104.
Кнут Д. Искусство программирования. М.: Вильямс, 2001.
 Программная реализация операций над большими числами в языке ЛЯПАС-T | ПДМ. Приложение. 2014. № 7.

Программная реализация операций над большими числами в языке ЛЯПАС-T | ПДМ. Приложение. 2014. № 7.