Сборка MIPS для двумерного массива и зубчатого массива

Я видел несколько простых преобразований из кода 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-код просто на бумаге. Буду признателен за любую помощь.

Структурированный массив Numpy
Структурированный массив Numpy
Однако в реальных проектах я чаще всего имею дело со списками, состоящими из нескольких типов данных. Как мы можем использовать массивы numpy, чтобы...
T - 1Bits: Генерация последовательного массива
T - 1Bits: Генерация последовательного массива
По мере того, как мы пишем все больше кода, мы привыкаем к определенным способам действий. То тут, то там мы находим код, который заставляет нас...
Что такое деструктуризация массива в JavaScript?
Что такое деструктуризация массива в JavaScript?
Деструктуризация позволяет распаковывать значения из массивов и добавлять их в отдельные переменные.
0
0
27
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Это не код 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.

Ваше объяснение действительно полезно. Спасибо.

Aylin Naebzadeh 05.04.2022 17:15

Во второй части разве не должно быть A[r, c] вместо A[r][c]? Что нам делать, если это было в C#? Я думаю, что в С# у нас нет указателей или поиск адреса памяти будет таким же, и это просто зависит от типа структуры данных?

Aylin Naebzadeh 05.04.2022 17:24

В C нет. В C нет конструкции [r,c], поэтому мы просто применяем [] дважды. Если объявление было для прямоугольного массива, эта нотация является чистым вычислением, а если объявление было для зубчатого массива, первый [] является разыменованием, а второй - чистым вычислением. Возможно, это не так ясно, как подход C# [r,c] по сравнению с подходом C# [r][c], но компилятор C и система типов могут сохранить это прямо — он знает, когда добавить, а когда уважать.

Erik Eidt 05.04.2022 17:26

Оказывается, в C# механизм [r,c] необходим для объявления прямоугольных многомерных массивов, т. к. механизм [] [] автоматически подразумевает массив массива (т.е. зубчатый), потому что все — даже массив 1d — объект (на который ссылаются) в C#. В отличие от C, массив вовсе не ссылка, а прямое хранилище, поэтому [][] также является прямым хранилищем в C.

Erik Eidt 05.04.2022 17:35

Итак, массивы C# больше похожи на C++ std::vector? По-видимому, их размер нельзя изменить во время выполнения (Array.Resize заменяет ссылку копией другого размера), но да, это структура данных, которая содержит свой собственный размер, в отличие от простых массивов C/C++ или std::array.

Peter Cordes 06.04.2022 05:38

Другие вопросы по теме