Практика. Распараллеливание перевода строки в верхний регистр

Использование сопроцессора NEON позволяет ускорить выполнение различных задач. Посмотрим на примере. Пусть, нам надо перевести символы в верхний регистр. По сути перевод в верхний регистр отдельного символа - это операция, которая никак не затрагивает другие символы. Соответственно мы можем распараллелить данную задачу.

Итак, определим файл toupper.s, который будет содержать функцию для перевода строки в верхний регистр:

// X0 - адрес входной строки
// X1 - адрес выходной строки
// X2 - для загрузки данных
// Q0 - символы для обработки
// V1 - содержит символы "a" для проверки символов на регистр
// V2 - результат сравнения с символом "a"
// Q3 - содержит числа 25 для сравнения результата
// Q8 - пробелы для операции bic
.global toupper
    .EQU N, 4           // изменяем 4 группы из 16 символов
toupper:
    LDR X2, =aaa
    LDR Q1, [X2]        // загружаем в Q1 строку с "a"
    LDR X2, =endch
    LDR Q3, [X2]        // загружаем в Q3 все числа 25
    LDR X2, =spaces
    LDR Q8, [X2]        // загружаем в Q8 пробелы
    MOV W3, #N
// проходим по каждому символу в цикле, пока не встретим нулевой байт
loop: 
    LDR Q0, [X0], #16               // загружаем 16 символов и увеличиваем адрес на 16 байт
    SUB V2.16B, V0.16B, V1.16B      // Вычитаем из загруженных символов символы "a"
    CMHI V2.16B, V2.16B, V3.16B     // сравниваем результат вычитания с 25
    NOT V2.16B, V2.16B              // инвертируем все биты чисел
    AND V2.16B, V2.16B, V8.16B      // результат умножаем поразрядно на 0x20 - дорожки, где нет строчных букв алфавита, будут равны 0.
    BIC V0.16B, V0.16B, V2.16B      // удаляем старщий бит 0x20
    STR Q0, [X1], #16               // сохраняем полученные 16 символов в выходную строку
    SUBS W3, W3, #1                 // уменьшаем счетчик цикла на 1
    B.NE loop                       // если еще есть символы
    MOV X0, #(N*16)                 // получаем длину строки
    RET
.data
    aaa: .fill 16, 1, 'a'      // 16 символов a для проверки на регистр символа
    endch: .fill 16, 1, 25      // после вычитания должно быть в дапазоне 0-25
    spaces: .fill 16, 1, 0x20   // для инструкции BIC

Рассмотрим выполнение этой функции. Прежде всего определяем константу, которая определяет, сколько символов мы будем обрабатывать. В данном случае мы упростим задачу и будем обрабатывать 64 символа. Одномоментно в регистры NEON мы будем загружать 16 символов. И для теста сделаем это 4 раза. Для это определяем константу-счетчик N:

.EQU N, 4

Сначала загружаем начальные данные. В регистр Q1/V1 загружаем адрес 16 символов "a":

LDR X2, =aaa
LDR Q1, [X2]

Числовой код "a" позволит выявить, является ли символ в нижнем регистре. Если мы отнимем от кода текущего символа строки числовой код символа "a", то мы получим расстояние между этими двумя символами. Если текущий символ строки представляет символ латинского алфавита в нижнем регистре, то разность будет в диапазоне от 0 до 25. Разность меньше нуля означает, что текущий символ строки уже в верхнем регистре, либо представляет число, либо другой символ ASCII, который идет до символа "a". Однако если мы будем рассматривать разность как число без знака (которое не может быть отрицательным), то отрицательные значения в данном случае мы можем отбросить. И будет достаточно сравнивать, больше ли разность, чем число 25. И для сравнения результата вычитания в регистр Q3/V3 загружаем 16 чисел 25:

LDR X2, =endch
LDR Q3, [X2]

Далее в регистр Q8/V8 загружаем 16 чисел символов, которые представляют пробел или символ 0x20:

LDR X2, =spaces
LDR Q8, [X2] 

Зачем нам нужны проблелы? Дело в том, что символы в верхнем регистре отличаются от символов в нижнем регистре на 0x20. Например, возьмем бинарный код символа "A" - 01000001 и сравним его с бинарным кодом символа "a" (нижний регистр) - 01100001. Мы видим, что они отличаются на 00100000₂ или на 0x20₁₆. То же самое касается и остальных символов. То есть сбросив третий разряд в 0, мы переведем символ из нижнего регистра в верхний.

Далее начинаем цикл для перевода всех символов в верхний регистр. Здесь мы полагаем, что через регистр X0 в функцию будет передаваться адрес строки для перевода. И первые 16 символов этой строки загружаем в регистр Q0/V0:

LDR Q0, [X0], #16 

Далее вычитаем из загруженных символов числовой код символа "a":

SUB V2.16B, V0.16B, V1.16B

Результат помещаем в регистр V2. Если символы строки в нижнем регистре, то дорожки регистра V2 будут хранить число из диапазона 0-25. Далее применяется инструкция CMHI, которая сравнивает значения регистров NEON.

CMHI V2.16B, V2.16B, V3.16B

Эта инструкция сравнивает сразу все 16 дорожек одновременно и помещает в результирующую дорожку 1, если сравнение истинно и 0, если сравнение не верно. То есть в данном случае сравниваем значение из регистра V2 (разность символов) и регистра V3 (число 25). Если в дорожке в V2 число больше, то в эту дорожку V2 помещаем число 1. Если в дорожку поместить 1, то в итоге это образует значение 0xFF

Далее выполняем поразрядную инверсию:

NOT V2.16B, V2.16B

То есть теперь в дорожках, где строчные буквы, будут числа 1, а в других - число 0.

Затем поразрядно умножаем результат в V2 на число 0x20

AND V2.16B, V2.16B, V8.16B

После этой инструкции в V2 в дорожках, где строчные буквы, будут числа 0x20, а в остальных дорожках - число 0.

В конце с помощью инструкции BIC для тех дорожек, где в V2 числа 0x20, сбрасываем третий разряд в 0, тем самым преобразуя символ из нижнего регистра в верхний:

BIC V0.16B, V0.16B, V2.16B

Затем сохраняем преобразованные символы в память по адресу из регистра X1 (через который, как предполагается, будет передаваться адрес выходной строки). И далее переходим к новой группе символов. В качестве результата функции в регистр X0 помещаем количество обработанных символов.

Общий процесс можно схематически представить следующим образом (на примере строки "Hello Metanit.com" и первых 4 дорожек регистров:

Подключим эту функцию в главном файле программы:

.include "toupper.s"    // вставляем в это место содержимое файла toupper.s
.global _start
_start:
    LDR X0, =input 
    LDR X1, =output
    BL toupper		// вызываем функцию toupper
    // вывод значения
    MOV X2, X0              // код возврата - длина строкиs
    MOV X0, #1              // 1 = StdOut
    LDR X1, =output         // строка для печати
    MOV X8, #64
    SVC 0 
    // выход из программы
    MOV X0, #0 
    MOV X8, #93
    SVC 0
.data
    input: .asciz "Hello Metanit.com\n"
    .align 4
    output: .fill 255, 1, 0

Здесь в качестве входной строки выступает текст "Hello Metanit.com\n", а в качестве выходной - строка output из 255 байтов. Чтобы функция toupper заработала, между двумя строками надо добавить директиву .align 4. Так как мы можем загружать или сохранять данные NEON из или в ячейки памяти с выравниванием по словам. Если мы не cделаем этого, то можем столкнуться с ошибкой "Bus Error" при запуске программы.

В результате программа должна вывести на консоль строку в верхнем регистре:

HELLO METANIT.COM