Я видел несколько простых преобразований из кода C в код сборки MIPS и работал с некоторыми основными инструкциями. Но как нам преобразовать следующий код C, в котором есть jagged array
и two-dimensional array
, в ассемблер?
int[][] A;
int[,] B;
A[B[0, 1]][A[1][2]] + B[B[j, 1], i]
Я искал в Интернете, но, к сожалению, я не смог найти хороший источник или учебник. Я знаю, как мы должны работать с one-dimensional array
и находить базу адресов памяти по базовому адресу и использовать смещение. Но я не знаю, как решить этот вопрос и написать свой MIPS-код просто на бумаге. Буду признателен за любую помощь.
Это не код C, это похоже на C#.
int[][] A; // C# declaration for jagged multidimensional array
int[,] B; // C# declaration for rectangular multidimensional array
Во-первых, давайте рассмотрим более простой и правильный прямоугольный массив.
Код C для прямоугольного многомерного массива будет таким:
int B[5][10]; // C declaration for rectangular array
Этот фрагмент запрашивает в общей сложности 50 целочисленных элементов, структурированных как 5 строк, где размер строки равен 10 элементам.
Поскольку логическая структура данных двумерна, а физическая память только одномерна, мы должны преобразовать двумерную структуру в одномерную. Есть два способа сделать это, один из них — основной ряд и другой основной столбец. Если мы считаем, что индекс, имеющий 5, является строкой, а 10 — столбцом, то мы можем сказать, что язык C использует упорядочение по строкам.
(То, что есть два варианта сопоставления массива, похоже на идею о том, что существует два разумных порядка для отдельных байтов в многобайтовых (то есть словах) элементах: прямой порядок байтов и прямой порядок байтов.)
В каком-то смысле массив является непосредственным: в этой структуре не хранятся указатели или ссылки, только 50 целочисленных элементов.
Доступ к элементу осуществляется путем вычисления адреса:
В B[r][c]
мы вычисляем addr = B + (r * 10 + c) * 4
, где 10 представляет размер строки, а 4 — размер одного целочисленного элемента. Умножения - это то, что называется масштабированием. Поскольку каждая строка относится к 10 элементам, строка 1 начинается на 10 позиций ниже, чем строка 0. Поскольку каждый элемент занимает 4 байта, а каждый из 4 байтов занимает адрес памяти, столбец 1 начинается на 4 байта ниже, чем столбец 0. Таким образом, элемент 0,0
находится в B + (0*10+0)*4
, что является тем же значением адреса, что и B
, а элемент 1,2
находится в B + (1*10+2)*4
, то есть B + 48
— 3-й элемент (+8) 2-й строки (+10*4).
Этот addr
можно разыменовать, чтобы загрузить элемент r,c
из массива или сохранить обновленное значение в r,c
.
(Если бы мы выбрали порядок столбцов, то формула была бы addr = B + (c * 5 + r) * 4
. Основной порядок строк лучше, если индекс столбца меняется быстрее, т. индексировать быстрее — индекс для внутреннего цикла меняется быстрее, чем индекс для внешнего цикла. Разница между ними связана с использованием кеша (без кеша это не имело бы большого значения).
Зубчатые массивы — это массивы массивов. Каждый задействованный массив является одномерным, поэтому, хотя каждый отдельный массив все еще имеет прямоугольную форму, прямоугольная форма не применяется к двумерной структуре всего «двухмерного» массива.
В C зубчатый массив объявляется как массив указателей, где сами указатели являются ссылками на отдельные массивы из нуля или более целочисленных элементов (или равны нулю).
int *A[10];
Это объявляет массив ([] имеет приоритет над *, поэтому это воспринимается как for ( r = .. ) for ( c = .. ) { }
, тип каждого элемента массива — указатель на int.
Общий размер хранилища этого массива составляет 40 байт, 10 * размер указателя, 4, в 32-разрядной системе MIPS. Каждый элемент массива является типом указателя. В этом объявлении массива не зарезервированы целые числа! Есть позиции для 10 указателей на целое число (массивы), и каждая из 10 для каждой позиции должна быть дополнительно указана с помощью инициализатора или путем выделения. Поскольку элементы этого массива являются указателями на целые числа, каждый такой указатель может быть нулевым или ссылаться на хранилище различного количества целых чисел. Если вы хотите знать, сколько целых чисел было/имеет каждая (строка), вам придется хранить эту информацию отдельно, потому что нет встроенного механизма для ее хранения с помощью этого объявления.
Таким образом, зубчатые массивы в C имеют следующие проблемы:
int *(A[10])
, но при использовании calloc
или в качестве объявления локальной переменной эти указатели будут неинициализированы (т.е. мусор).Доступ к элементу зубчатого массива означает получение элемента-указателя из первого массива и использование его для вычисления адреса целочисленного элемента. Обе эти операции включают одномерные массивы, поэтому, по крайней мере, в этом смысле они концептуально проще: нет проблемы основного порядка строк и столбцов.
Адрес элемента malloc
вычисляется следующим образом:
addr = (*(A + r * sizeof(pointer))) + c * sizeof(int)
где первый * — это косвенное обращение, которое извлекает указатель по индексу A[r][c]
. Этот r
можно использовать так же, как в описании после addr
для прямоугольного массива выше.
Тогда реализация MIPS любого из них довольно проста. Для глобального хранилища зарезервируйте соответствующий объем. В коде вычислите адреса элементов и используйте addr
или lw
, как только вы вычислили sw
.
Во второй части разве не должно быть A[r, c]
вместо A[r][c]
? Что нам делать, если это было в C#? Я думаю, что в С# у нас нет указателей или поиск адреса памяти будет таким же, и это просто зависит от типа структуры данных?
В C нет. В C нет конструкции [r,c], поэтому мы просто применяем [] дважды. Если объявление было для прямоугольного массива, эта нотация является чистым вычислением, а если объявление было для зубчатого массива, первый [] является разыменованием, а второй - чистым вычислением. Возможно, это не так ясно, как подход C# [r,c]
по сравнению с подходом C# [r][c]
, но компилятор C и система типов могут сохранить это прямо — он знает, когда добавить, а когда уважать.
Оказывается, в C# механизм [r,c]
необходим для объявления прямоугольных многомерных массивов, т. к. механизм [] [] автоматически подразумевает массив массива (т.е. зубчатый), потому что все — даже массив 1d — объект (на который ссылаются) в C#. В отличие от C, массив вовсе не ссылка, а прямое хранилище, поэтому [][] также является прямым хранилищем в C.
Итак, массивы C# больше похожи на C++ std::vector
? По-видимому, их размер нельзя изменить во время выполнения (Array.Resize заменяет ссылку копией другого размера), но да, это структура данных, которая содержит свой собственный размер, в отличие от простых массивов C/C++ или std::array
.
Ваше объяснение действительно полезно. Спасибо.