Семинары по курсу «Архитектура ЭВМ и язык ассемблера» учебно-методическое пособие. Часть 2. - Е.А. Кузьменкова_ В.А. Падарян_ М.А. Соловьев, страница 3

Используем регистры ESI и EDIдля хранения переменных цикла, регистр ECX – для вычисления смещения от начала массива в двойных словах.Вариант «А»section .bssA resd M*NB resd N*Msection .textmovesi, 0 ; индекс i.l1:movedi, 0 ; индекс j.l2:imuladdmovimuladdmovecx, esi, Necx, edieax, dword [A + 4*ecx]ecx, edi, Mecx, esidword [B + 4*ecx], eax; Начинается тело внешнего цикла;;;;;Начинается тело внутреннего циклаСмещаемся на esi строк по N элементов каждая… и еще на edi элементов (массив A)Считываем элемент по вычисленному смещениюАналогично считаем смещение в массиве B; и записываем значение элементаinccmpjlediedi, N.l2; Проверка счетчика внутреннего циклаinccmpjlesiesi, M.l1; Проверка счетчика внешнего циклаКак можно заметить, обращение к элементам массива A приводит к последовательному считыванию содержимого памяти, что позволяет избавиться от одногоумножения во вложенном цикле. Идея заключается в том, что смещение для массива A хранится в дополнительно выделенном регистре EDX, на каждой итерациивнутреннего цикла EDX будет увеличиваться на единицу.

Новые команды в варианте «Б» показаны серым цветом. Замена двойного цикла на одинарный не представляется целесообразной, т. к. преобразование линейного смещения в индексыматрицы B дополнительно потребует вычисления частного и остатка, что являетсядостаточно дорогой операцией.14Вариант «Б»section .bssA resd M*NB resd N*Msection .textmovmovesi, 0 ; индекс iedx, 0.l1:movedi, 0 ; индекс j.l2:movimuladdmoveax, dword [A + 4*edx]ecx, edi, Mecx, esidword [B + 4*ecx], eaxincinccmpjledxediedi, N.l2inccmpjlesiesi, M.l1Пример 1-5 Восстановление размеров массиваВ следующем фрагменте Си-программы используются константы R и S.int A[R][S];int extract(int i, int j, int *dest) {*dest = A[i][j];return sizeof(A);}Для тела данной функции был получен следующий ассемблерный код. Формальные параметры функции расположены в памяти по следующим адресам: i – EBP+8,j – EBP+12, dest – EBP+16.imul eax, dword [ebp + 8], 90add eax, dword [ebp + 12]mov edx, dword [A + eax * 4]mov eax, dword [ebp + 16]mov dword [eax], edxmov eax, 3960;;;;;;(1)(2)(3)(4)(5)(6)Определите значения констант R и S.15Решениеimul eax, dword [ebp + 8], 90 ;;add eax, dword [ebp + 12];;mov edx, dword [A + eax * 4] ;;;mov eax, dword [ebp + 16];;mov dword [eax], edx;;mov eax, 3960;(1) В регистр eax помещается значениевыражения i * 90(2) Добавляем j.

итого, в eax находитсязначение выражения i * 90 + j(3) В регистр помещается 32-разрядноезначение из памяти по адресуa + 4 * (i * 90 + j)(4) Теперь в eax помещается значениепараметра dest, являющегося указателем(5) По этому адресу (*dest) кладетсясодержимое edx(6) Возвращаемое значение – 3960Для произвольного типа T размер двумерного массива T arrary[N1][N2] определятсяпо формуле sizeof(T)*N1*N2. Размер всего массива можно определить из инструкции №6, в регистр EAX помещается константа, являющаяся значением sizeof(A).

Таким образом,sizeof(A) = 3960  sizeof(int)*R*S = 3960  R*S = 990Ключевым моментом является определение порядка вычисления адреса памяти,используемого в инструкции №3. В адресе A+4*(i*90+j) реализовано обращение кэлементу массива A[i][j]. Первый индекс означает, что необходимо i раз переместится на расстояние из S элементов. Таким образом, константа S = 90.

Из приведенного выше уравнения можно определить, что R = 11.Массив указателейМассивы указателей позволяют применять два индексных выражения, как и в случае с матрицей. Но массив указателей имеет два существенных отличия. Вопервых, при объявлении такой переменной элементом одномерного массива является указатель, всегда требующий для своего размещения 4 байта. Во-вторых,элемент скалярного типа получается уже после вычисления первого индекса, послечего необходимо обратиться в память и извлечь оттуда элемент-адрес. Далее кэтому извлеченному адресу прибавляется смещение, полученное при вычислениивторого индексного выражения.

Таким образом, для объявления T* pA[N] вычислениеадресаэлементаp[i][j]будетсоответствоватьформуле, где– начальный (базовый) адрес переменнойpA , а M[A] – содержимое памяти по адресу A.Пример 1-6 Массив указателей vs. Двумерный массивДан массив некоторой ненулевой длины, содержащий ненулевые указатели на ограниченные нулем строки символов. Строки преобразуются с помощью массиваподстановок. Переведите Си-код на язык ассемблера.16static char *strings[N];static char tr[8][256];for (int i = 0; i < N; i++) {for int (j = 0; '\0' != strings[i][j]; j++) {strings[i][j] = tr[i % 8][(unsigned char)strings[i][j]];}}РешениеНа языке Си код, обращающийся к массиву указателей, ничем не отличается от обращения к двумерному массиву: дважды используется операция индексирования.Но типы данных массивов требуют реализовывать эти обращения различнымиспособами.

Вычисление strings[i][j] потребует сначала извлечь из памяти указатель strings[i], а затем использовать его в качестве адреса при обращении к очередному символу в преобразуемой строке. Обращение к двумерному массиву trтребует вычислить смещение в непрерывном блоке памяти, выделенном для егоразмещения. Помимо того, различие между переменными strings и tr проявляетсяв выделении памяти: для первой был выделен одномерный массив из N двойныхслов (хранятся указатели), для второй – 8*256 байтов, в которых последовательноразмещены строки двумерного массива.section .bss; выделяем память под переменныеstrings resd Ntrredb 8*256section .textmovecx, 0;;.l1:;movebx, dword [strings + 4*ecx] ;;cmpbyte [ebx], 0;jz.l2e;.l2:;movzx edx, byte [ebx];moveax, ecx;andeax, 7;saleax, 8;movdl, byte [tr + eax + edx];movbyte [ebx], dl;incebx;cmpbyte [ebx], 0jnz.l2;.l2e:inccmpjlecxecx, N.l1В ecx размещаем i.

Т.к. массив строкне пустой – предварительно проверятьi не требуетсяПомещаем в ebx strings[i] – адресначала в памяти очередной строкиПеред первым выполнением тела forпроверяем условие выхода из цикла,поскольку строка может быть пустойБеззнаковое расширение charВычисляем смещение для массива trеах – смещение на (i%8) строк,умноженное на 256edx – смещение внутри строкиСохраняем новое значениеПереходим на адрес очередного символаПродолжаем, если strings[i][j] != 0; Продолжаем внешний цикл, пока i < N17Следует отметить, что условие указывает на то, что в массиве strings находятся ненулевые указатели. В противном случае потребуется дополнительная проверка, икорректный Си-код будет выглядеть следующим образом.static char *strings[N];static char tr[8][256];for (int i = 0; i < N; i++) {if (NULL != strings[i]) {for int (j = 0; '\0' != strings[i][j]; j++) {strings[i][j] = tr[i % 8][(unsigned char)strings[i][j]];}}}ЗадачиЗадачи, название которых подчеркнуто, снабжены ответом, приведенным в концепособия.Задача 1-1Заданы два массива целых чисел: массив short A[100] и массив int B[100].

Требуется выполнить копирование всех элементов массива A в массив B со знаковым расширением.Задача 1-2В переменной A хранится указатель на область памяти, содержащую слова, количество которых указано в переменной N. Требуется расширить каждое из этих слов додвойного слова «на месте», то есть после работы программы A указывает на массивиз N двойных слов, значения которых получены знаковым расширением исходныхзначений. Считать, что выделенной памяти достаточно для хранения N двойныхслов.Замечание: следует расширять элементы «справа налево», так как иначе произойдёт перезапись части оригинального массива.Задача 1-3Напишите ассемблерную программу, проверяющую симметричность статическогомассива (N элементов типа int, N – константа, 2 <= N < 220): одинаковые значенияимеют первый и последний, второй и предпоследний, и т.

д. Выполнять ввод значений элементов массива и выравнивать стек не требуется. Если массив симметричный, на выходе из функции CMAIN регистр EAX должен иметь значение 0, в противном случае – 1. Запрещается использовать строковые инструкции и использовать стек. Программа должна содержать не более 16 инструкций. Учитываются всеинструкции, включая ret.18Задача 1-4В заданном массиве shortэлементы.a[50]поменять местами максимальный и минимальныйЗадача 1-5Дан массив из 100 элементов типа int.

Найти сумму элементов массива, превосходящих значение последнего элемента.Задача 1-6Даны два массива из 100 элементов типа short. Проверить массивы на равенство инапечатать 1 в случае положительного ответа и 0 в противном случае.Задача 1-7Дан массив char x[200], содержащий символы некоторого текста. Сформироватьмассив char y[200], в начале которого расположены все цифры из массива x (в порядке их следования в исходном массиве), затем все оставшиеся символы из массива y (в произвольном порядке).Задача 1-8Написать программу, которая вводит число типа unsigned longрядке убывания все десятичные цифры, входящие в это число.longи печатает в по-Задача 1-9Дан текст, состоящий из строчных латинских букв, оканчивающийся точкой (точка втекст не входит). Напечатать:а) в алфавитном порядке все строчные латинские буквы, встречающиеся в тексте ровно 1 раз;б) букву, наиболее часто встречающуюся в тексте.

В случае если таких букв несколько, напечатать первую по алфавиту.Задача 1-10Дана матрицаEDX.int A[N][M].Выписать код, загружающий элементA[i][j]на регистрЗадача 1-11Дана матрица int A[N][N]. Требуется напечатать сумму всех нечетных элементов ееглавной диагонали.Задача 1-12Транспонируйте квадратную матрицу «на месте», не используя дополнительнойпамяти.19Более сложный вариант задачи: Транспонируйте «на месте», не используя дополнительной памяти, матрицу произвольного размера M×N. До и после транспонирования матрица хранится в памяти с разверткой по строкам.Задача 1-13Дана матрица размера N×N (N= 50) из элементов типа int.а) Найти сумму элементов матрицы, лежащих ниже главной диагонали.б) Поменять местами элементы главной и побочной диагоналей матрицы.в) Подсчитать количество строк матрицы, элементы которых упорядочены повозрастанию.г) Напечатать номер строки, содержащей наибольшее количество нулевыхэлементов.Задача 1-14Дан массив из 30 ненулевых указателей на ограниченные нулем строки символов.а) Подсчитать количество строк, начинающихся с ненулевой цифры.б) Напечатать строку максимальной длины.

Если таких строк несколько, напечатать первую из них по порядку следования в массиве.в) Подсчитать количество строк, являющихся палиндромами.Задача 1-15Дана матрица int A[N][M]. Требуется удалить из нее все строки, сумма элементов вкоторых меньше нуля.Задача 1-16Дана матрица, заданная в виде массива указателей int *A[N], где для каждой строки уже выделена и заполнена память под M элементов. Требуется удалить из неевсе столбцы, сумма элементов в которых меньше нуля.Задача 1-17Дана последовательность слов, состоящих из строчных латинских букв. Слова отделены друг от друга одним или несколькими пробелами, после последнего словазаписана точка, не входящая в текст.

Удалите из текста лишние пробелы.а) Текст вводится и выводится посимвольно.б) Текст содержится в массиве char S[] и выводится на печать посимвольно.в) Текст содержится в массиве char S[], а обработанный текст размещается вмассиве char R[].г) Тест содержится в массиве char S[] и обрабатывается «на месте».202.Структуры и объединенияВыравнивание данных в памятиПри размещении в памяти массивов все элементы расположены друг за другом,без промежутков. Структуры объединяют в себе поля произвольных типов, размещаемых в памяти в том же порядке, в каком они были объявлены в исходном Сикоде.