Determine a paridade de uma representação de um número em MIPs

Question

Existe algumas instruções no MIPS que determinarão a paridade de uma certa representação de bits? Sei que determinar se um "número" tem uma paridade uniforme ou uma paridade estranha é xorar os bits individuais da representação binária juntos, mas isso parece computacionalmente intensivo para um conjunto de instruções do MIPS ... e eu preciso fazer isso O mais rápido possível.

Além disso, o número em que estou trabalhando é representado no código cinza ... apenas para jogá -lo lá. Então, existe alguma pseudo-instrução no MIPS para determinar a paridade de um "número" ou eu tenho que fazer isso manualmente?

Se não há instrução MIPS, que parece muito improvável, algum conselho sobre como fazê -lo manualmente?

Obrigado, Hristo

Acompanhamento: encontrei uma otimização, mas minha implementação não está funcionando.

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

Answer 1

Não estou ciente de nenhuma variante MIPS com uma instrução de paridade, mas há um truque de lança para calcular a paridade mais rapidamente do que o método óbvio de percorrer cada um dos 32 bits por sua vez. Em C:

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

• Após a primeira etapa, os 16 bits inferiores do resultado contêm a paridade de bits n e n+16 da entrada - essencialmente, 16 etapas do cálculo da paridade foram realizadas de uma só vez. Escrita result{N} para significar "bit n de 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}
  

  (e os 16 melhores bits restantes de result agora pode ser ignorado; Eles não servem a não ser útil no restante do cálculo).

• Após a segunda etapa, os 8 bits inferiores de result Contém a paridade de bits n, n+8, n+16, n+24 da entrada original:

  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}
  

  (E novamente, os bits restantes podem ser ignorados daqui em diante).

• ... e assim por diante, até a paridade de todos os pedaços da entrada original acabar na parte inferior de result:

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

Isso é fácil de traduzir diretamente para a montagem MIPS; São 11 instruções:

# 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

---

Uma possível melhoria pode ser usar uma tabela de pesquisa. Por exemplo, após as duas primeiras etapas, temos:

    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}

Para que pudéssemos usar uma tabela de pesquisa de 256 bytes neste momento. Em C:

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

Onde lookup_table[n] foi pré -calculado, por exemplo:

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

São 7 instruções do MIPS, sem contar o carregamento do endereço base da tabela de pesquisa em um registro:

# 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)

No entanto, são 7 instruções que incluem acesso à memória, contra 11 instruções que são operações puramente de registro; Pode ou não ser mais rápido. (Esse tipo de micro-otimização sempre precisa ser perfilada!)