Дополнительная работа №1

Доп задание №1

Условие

Создать программу на языке С, которая считывает из файла целые числа. Необходимо написать ассемблерную вставку, осуществляющую сортировку массива. Метод сортировки определяет разработчик. Вставка должна быть вынесена в отдельную функцию. Использовать глобальные переменные для передачи данных в указанную функию запрещено. Полученный массив записать в файл вывода.

Входные данные

Первая строка входного файла INPUT.TXT содержит одно целое число N (1 ≤ N ≤ 100). В следующих N строках содержатся числа, по модулю не превышающие 10^9.

Содержание отчета по работе

• Условие программы;
• Текст программы.

Link to original

Пояснение % %

Ввиду того, что сборщик интерпретирует два подряд идущих знака процента как начало комментария, он не отображает содержимое, находящееся между парой таких знаков. Поэтому, чтобы избежать этого, вместо использования %% везде применяется % %.

Link to original

Код

void InsertionSort(int *array_ptr, int n) {  
    __asm__(  
		"mov %[array_ptr], % %rdi;"
		"mov $1, % %rcx;"
		"cmp %[N], % %rcx;"
		"jge end;"
		"main_loop:;"
		"mov (% %rdi, % %rcx, 4), % %rax;"
		"mov % %rcx, % %rdx;"
		"dec % %rdx;"
		"sub_loop:;"
		"mov (% %rdi, % %rdx, 4), % %rbx;"
		"cmp % %rbx, % %rax;"
		"jge sub_loop_end;"
		"mov % %rbx, (% %rdi, % %rcx, 4);"
		"mov % %rdx, % %rcx;"
		"dec % %rdx;"
		"cmp $-1, % %rdx;"
		"jge sub_loop;"
		"sub_loop_end:;"
		"lea 1(% %rdx), % %rdx;"
		"mov % %rax, (% %rdi, % %rdx, 4);"
		"inc % %rcx;"
		"cmp %[N], % %rcx;"
		"jl main_loop;"
		"end:;"
		:  
		: [array_ptr] "m"(array_ptr), [N] "r"(n)  
    : "rax", "rbx", "rcx", "rdx", "rdi"  
    );
}

raw

Код сортирует массив целых чисел методом вставки, используя встроенный ассемблер для оптимизации производительности.

Функция InsertionSort

void InsertionSort(int *array_ptr, int n) {

Функция принимает два аргумента:

1. array_ptr — указатель на массив целых чисел, который нужно отсортировать.
2. n — количество элементов в массиве.

Встроенный ассемблер

Введение в Ассемблер

Синтаксис Ассемблера

Значения символов % и % % к контексте ассемблерных вставок

__asm__(
	"mov %[array_ptr], % %rdi;"  
	"mov $1, % %rcx;"
	"cmp %[N], % %rcx;"
	"jge end;"

Инициализация

1. mov %[array_ptr], % %rdi; — загрузка адреса массива в регистр rdi используя mov.
2. mov $1, % %rcx; — инициализация регистра rcx значением 1. Это будет наш индекс текущего элемента, который мы вставляем в отсортированную часть массива.
3. cmp %[N], % %rcx; — сравнение длины массива с текущим индексом используя cmp.
4. jge end; — если текущий индекс не меньше длины массива, то перейти к метке end используя jge.

Основной цикл сортировки

    "main_loop:;"
    "mov (% %rdi, % %rcx, 4), % %rax;"
    "mov % %rcx, % %rdx;"
    "dec % %rdx;"

1. main_loop:; — метка начала цикла.
2. mov (% %rdi, % %rcx, 4), % %rax; — загрузка текущего элемента массива в регистр rax. Здесь используется адресная арифметика для доступа к элементу массива (% %rdi + % %rcx * 4) (% %rdi + % %rcx * 4) (Почему именно 4?).
3. mov % %rcx, % %rdx; — копирование значения индекса в регистр rdx (rcx → rdx).
4. dec % %rdx; — уменьшение значения rdx на 1, чтобы получить индекс предыдущего элемента.

Внутренний цикл (перемещение элементов)

    "sub_loop:;"
    "mov (% %rdi, % %rdx, 4), % %rbx;"
    "cmp % %rbx, % %rax;"
    "jge sub_loop_end;"
    "mov % %rbx, (% %rdi, % %rcx, 4);"
    "mov % %rdx, % %rcx;"
    "dec % %rdx;"
    "cmp $-1, % %rdx;"
    "jge sub_loop;"

1. sub_loop:; — метка начала внутреннего цикла.
2. mov (% %rdi, % %rdx, 4), % %rbx; — загрузка предыдущего элемента массива в регистр rbx.
3. cmp % %rbx, % %rax; — сравнение предыдущего элемента с текущим.
4. jge sub_loop_end; — если предыдущий элемент больше или равен текущему, переход к метке sub_loop_end.
5. mov % %rbx, (% %rdi, % %rcx, 4); — перемещение предыдущего элемента на позицию текущего.
6. mov % %rdx, % %rcx; — обновление текущего индекса (rdx).
7. dec % %rdx; — уменьшение индекса предыдущего элемента (dec).
8. cmp $-1, % %rdx; — проверка, не достигнут ли индекс -1.
9. jge sub_loop; — если индекс не меньше 0, повторить внутренний цикл.

Пропуск и завершение внутреннего цикла

    "sub_loop_end:;"
    "lea 1(% %rdx), % %rdx;"
    "mov % %rax, (% %rdi, % %rdx, 4);"
    "inc % %rcx;"
    "cmp %[N], % %rcx;"
    "jl main_loop;"

1. sub_loop_end:; — метка для пропуска перемещения.

2. lea 1(% %rdx), % %rdx; — увеличение rdx на 1, чтобы получить корректный индекс для вставки (lea).

   Объяснение синтаксиса lea 1(…) …

3. mov % %rax, (% %rdi, % %rdx, 4); — вставка текущего элемента на правильное место.

4. inc % %rcx; — увеличение индекса текущего элемента (inc).

5. cmp %[N], % %rcx; — проверка, не достигнут ли конец массива.

6. jl main_loop; — если конец массива не достигнут, повторить внешний цикл (jl).

Завершение сортировки

    "end:;"
    :
    : [array_ptr] "m"(array_ptr), [N] "r"(n)
    : "rax", "rbx", "rcx", "rdx", "rdi"
);
}

1. end:; — метка завершения сортировки.
2. : — секция для указания выходных операндов (в данном случае отсутствует).
3. : [array_ptr] "m"(array_ptr), [N] "r"(n) — секция для указания входных операндов:
   • [array_ptr] "m"(array_ptr) — адрес массива.
   • [N] "r"(n) — длина массива.
   Спецификаторы операндов
4. : "rax", "rbx", "rcx", "rdx", "rdi" — секция для указания изменяемых регистров (clobbered registers) (rax, rbx, rcx, rdx, rdi).