Код сборки MIPS - пытаясь выяснить, о чем этот код - PullRequest
Новая
       28

Код сборки MIPS - пытаясь выяснить, о чем этот код

1 голос
/ 08 июля 2019

Я изучаю ассемблерный код, и, учитывая этот код, мне нужно выяснить, о чем этот код. Однако я пытаюсь отладить с помощью qtspim. Я знаю, каково значение внутри каждого регистра, но я все еще не понимаю, о чем этот код.

Если вы найдете шаблон и о чем этот код, вы можете сказать мне, как вы можете это сделать и в какой строке вы знаете шаблон? спасибо! 

.text
.globl main


.text
main:
li $s0, 0x00BEEF00 ##given $s0= 0x00BEEF00

Init:
li $t0, 0x55555555
li $t1,0x33333333
li $t2,0x0f0f0f0f
li $t3,0x00ff00ff
li $t4,0x0000ffff
Step1: and $s1, $s0, $t0

srl $s0,$s0,1
and $s2,$s0,$t0
add $s0,$s1,$s2

Step2: and $s1,$s0,$t1

srl $s0,$s0,2
and $s2,$s0,$t1
add $s0,$s1,$s2


Step3: and $s1,$s0,$t2
srl $s0,$s0,4
and $s2,$s0,$t2
add $s0,$s1,$s2

Step4: and $s1,$s0,$t3
srl $s0,$s0,8
and $s2,$s0,$t3
add $s0,$s1,$s2

Step5: 
and $s1,$s0,$t4
srl $s0,$s0,16
and $s2,$s0,$t4
add $s0,$s1,$s2

End:
andi $s0,$s0,0x003f

введите описание изображения здесь

введите описание изображения здесь

Мипс объяснить

1 Ответ

1 голос
/ 08 июля 2019

Это подсчет населения, он же popcount, он же вес Хэмминга . Окончательный результат в $s0 - это число 1 битов на входе. Это оптимизированная реализация, которая дает тот же результат, что и сдвиг каждого бита отдельно в конец регистра и добавление его к итоговому значению. Смотри https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Эта реализация работает путем наращивания от 2-разрядных аккумуляторов до 4-разрядных, 8-разрядных и 16-разрядных с использованием SWAR для выполнения нескольких узких добавлений, которые не несите друг друга с одной инструкцией add.

Обратите внимание, как он маскирует каждый второй бит, затем каждую пару битов, затем каждую группу из 4 битов. И использует сдвиг, чтобы привести другую пару в очередь за add. Как C
(x & mask) + ((x>>1) & mask)

Повторение этого с большим сдвигом и другой маской в ​​конечном итоге дает вам сумму всех битов (рассматривая их все как имеющие значение-место 1), то есть количество установленных битов на входе.

Таким образом, GNU C представляет это __builtin_popcnt(x).

(За исключением того, что компиляторы на самом деле будут использовать более эффективный popcnt: либо таблицу поиска байтов для каждого байта отдельно, либо битовый взлом, который начинается таким образом, но использует умножение на число, подобное 0x01010101, до горизонтальной суммы 4 байтов в старший байт результата. Потому что умножение - это инструкция сдвига и сложения. Как посчитать количество установленных бит в 32-разрядном целом числе? )

Но это не работает: нужно использовать addu, чтобы избежать ошибок ; если вы попытаетесь сделать popcnt 0x80000000, первый add будет иметь оба входа = 0x40000000, что приведет к переполнению со знаком и отказу.

IDK, почему кто-либо использует инструкцию add для MIPS. Обычная инструкция двоичного сложения называется addu.

Команда add-with-trapping-on-Sign-overflow - add, что редко требуется, даже если ваши номера подписаны. Вы можете просто забыть о его существовании и использовать addu / addui

...