O truque dos campos bit-mapeados

No artigo passado mostrei como um valor double pode ser recodificado para caber em 32 bits usando campos bit-mapeados em uma estrutura:

struct fp_s {
  int value:25;
  int expoent:7;
} __attribute__((packed));

O que não é muito intuitivo é o fato de que o compilador consegue lidar com o membro value como se ele fosse um int, mas que tenha apenas 25 bits de tamanho! Ou seja, se colocarmos -1 nele, o valor armazenado será 0x1ffffff e valores menores que -16777216 sofrerão underflow, como acontece com qualquer valor inteiro! Mas, como é que o compilador faz essa mágica?

Para facilitar a compreensão lidaremos com duas estruturas menores, de apenas 1 byte de tamanho cada, e uma função de leitura e outra de escrita para o membro a dessas estruturas:

struct S1 {
  char a:5;
  char b:3;
} __attribute__((packed));

struct S2 {
  unsigned char a:5;
  unsigned char b:3;
} __attribute__((packed));

char S1read(struct S1 s)
{ return s.a; }

struct S1 S1write(char c)
{ struct S1 s = { c }; return s; }

char S2read(struct S2 s)
{ return s.a; }

struct S2 S2write(char c)
{ struct S2 s = { c }; return s; }

Eis o código equivalente de cada uma das funções:

S1read:
  lea eax,[rdi*8]
  sar al,3
  ret

S1write:
  mov eax,edi
  and eax,0x1f
  ret

S2read:
  mov eax,edi
  and eax,0x1f
  ret

S2write:
  mov eax,edi
  and eax,0x1f
  ret

Deu pra perceber que apenas a função S1read() é diferente? As outras três simplesmente zeram os bits acima dos 5 primeiros (que é o que mandamos fazer!)… A primeira rotina, S1read é diferente porque ela tem que levar em conta o sinal do membro a do argumento s. Ao fazer LEA EAX,[RDI*8] o compilador está deslocando RDI 3 posições para a esquerda, ou seja, colocando o bit 5 de EDI no bit 7:

EDI original : 0b000snnnn
Depois de LEA: 0bsnnnn000
Depois de SAR: 0bssssnnnn

Onde s é o bit de sinal e n são os bits restantes do valor de 5 bits.

Depois do LEA, qualquer operação pode ser feita como se a tivesse, de fato, 8 bits de tamanho (o tamanho de um char), desde que, no fim das contas, desloquemos o valor obtido de volta em 3 bits para a direita… É exatamente isso que o compilador faz, mas usando a instrução SAR (Shift Arithmetic Right). A diferença entre as instruções SHR e SAR é que a primeira colocará zeros no bit mais a esquerda, depois do shift, enquanto a segunda copiará o bit de mais alta ordem. Isso garante que o sinal do valor seja mantido, enquanto nos livramos dos 3 bits inferiores.

Na escrita, via função S1write() não precisamos nos preocupar com isso. O compilador simplesmente colocará zero nos bits superiores porque mandamos zerar b. Se tivéssemos feito:

struct S1 S1write(char a, char b)
{ struct S1 s = { a, b }; return s; }

O compilador criaria algo assim:

S1write:
  mov eax, edi
  sal esi, 5
  and eax, 31
  or  eax, esi
  ret

No modo x86_64 os registradores RDI e RSI são usados como primeiro e segundo argumentos da função, de acordo com a convenção de chamada POSIX. O compilador isolará b, deslocando-o 5 bits para a esquerda e zerará os 3 bits superiores de a. Logo depois ele faz um OR para misturar os dois. A mesma coisa aconteceria se mudássemos S2write do mesmo jeito… E aqui o uso a instrução SAL não é diferente de usarmos SHL. Ambas colocarão zeros à direita (aliás, elas têm o mesmo μop).

Isso tudo para te dizer que o verdadeiro problema está apenas na transformação da menor quantidade de bits para a maior e quando os tipos forem sinalizados. Mas a solução deslocamento-para-esquerda, operações e deslocamento-para-direita, resolve o problema facilmente… Em tipos sem sinal basta isolar os bits…

Outro ponto que pode causar estranheza é por que o compilador escolheu LEA ao invés de um simples SAL ou SHL? A resposta não é intuitiva: Dois deslocamentos consecutivos não podem ser executados em paralelo na mesma unidade de execução. O compilador escolheu uma operação aritmética, fazendo o cálculo de um endereço efetivo, seguido de um deslocamento porque essas instruções podem ser emparelhadas! Não que isso tenha alguma diferença aqui, já que ambas lidam com RAX como registrador destino.

Anúncios