определить четность битового представления числа в MIPS - PullRequest
Новая
       10

определить четность битового представления числа в MIPS

1 голос
/ 11 апреля 2010

Есть ли в MIPS какая-то инструкция, которая будет определять четность определенного битового представления? Я знаю, чтобы определить, является ли «число» четным или нечетным, это XOR для отдельных бит двоичного представления вместе, но это кажется вычислительно-интенсивным для набора инструкций MIPS ... как можно быстрее.

Кроме того, число, в котором я работаю, представлено в Сером коде ... просто чтобы добавить это. Так есть ли в MIPS какая-то псевдоинструкция для определения четности «числа» или я должен это делать вручную?

Если инструкции MIPS нет, что кажется маловероятным, какой-нибудь совет, как это сделать вручную?

Спасибо, Христо

продолжение: я нашел оптимизацию, но моя реализация не работает. 

unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;

1 Ответ

3 голосов
/ 11 апреля 2010

Я не знаю ни одного варианта MIPS с инструкцией по четности, но есть хитрый прием для вычисления четности быстрее, чем очевидный метод прохождения каждого из 32 битов по очереди. В С: 

result = in ^ (in >> 16);
result ^= (result >> 8);
result ^= (result >> 4);
result ^= (result >> 2);
result ^= (result >> 1);
result &= 1;

  • После первого шага нижние 16 битов результата содержат четность битов N и N + 16 входных данных - по сути, 16 шагов вычисления четности были выполнены за один раз. Запись result{N} в значении «бит N из result»: 

    result{0}  =  in{0} ^ in{16}
result{1}  =  in{1} ^ in{17}
result{2}  =  in{2} ^ in{18}
...
result{7}  =  in{7} ^ in{23}
result{8}  =  in{8} ^ in{24}
...
result{15} = in{15} ^ in{31}

    (и оставшиеся старшие 16 бит result теперь можно игнорировать; они не служат никакой полезной цели в оставшейся части вычисления).

  • После второго шага нижние 8 битов result содержат четность битов N, N + 8, N + 16, N + 24 исходного ввода: 

    result{0} = result{0} ^ result{8}  =  in{0} ^  in{8} ^ in{16} ^ in{24}
result{1} = result{1} ^ result{9}  =  in{1} ^  in{9} ^ in{17} ^ in{25}
...
result{7} = result{7} ^ result{15} =  in{7} ^ in{15} ^ in{23} ^ in{31}

    (и снова оставшиеся биты можно игнорировать с этого момента).

  • ... и так далее до тех пор, пока четность всех битов исходного входа не окажется в нижнем бите result: 

    result{0} = in{0} ^ in{1} ^ in{2} ^ ... ^ in{30} ^ in{31}

Это легко перевести непосредственно на сборку MIPS; это 11 инструкций: 

# input in $a0, output in $v0, $t0 corrupted
srl $t0, $a0, 16
xor $v0, $a0, $t0
srl $t0, $v0, 8
xor $v0, $v0, $t0
srl $t0, $v0, 4
xor $v0, $v0, $t0
srl $t0, $v0, 2
xor $v0, $v0, $t0
srl $t0, $v0, 1
xor $v0, $v0, $t0
and $v0, $v0, 1

Возможное улучшение может заключаться в использовании справочной таблицы. Например, после первых двух шагов имеем: 

    result{0} =  in{0} ^  in{8} ^ in{16} ^ in{24}
    result{1} =  in{1} ^  in{9} ^ in{17} ^ in{25}
    ...
    result{7} =  in{7} ^ in{15} ^ in{23} ^ in{31}

чтобы мы могли использовать 256-байтовую таблицу поиска на этом этапе. В С: 

result = in ^ (in >> 16);
result ^= (result >> 8);
result = lookup_table[result & 0xff];

, где lookup_table[n] был предварительно рассчитан, например ::

for (i = 0; i < 256; i++) {
    n = i ^ (i >> 4);
    n ^= (n >> 2);
    n ^= (n >> 1);
    lookup_table[i] = n & 1;
}

Это 7 инструкций MIPS, не считая загрузки базового адреса таблицы поиска в регистр: 

# input in $a0, lookup table address in $a1, output in $v0, $t0 corrupted
srl  $t0, $a0, 16
xor  $v0, $a0, $t0
srl  $t0, $v0, 8
xor  $v0, $v0, $t0
andi $v0, $v0, 0xff
addu $t0, $a1, $v0
lbu  $v0, 0($t0)

Однако это 7 инструкций, которые включают в себя доступ к памяти, по сравнению с 11 инструкциями, которые являются чисто операциями регистрации; это может или не может быть быстрее. (Этот вид микрооптимизации всегда должен быть профилирован!)

...