Contando bits…

Por que diabos estou escrevendo sobre ponto flutuante, de novo, ultimamente? É que topei com um projetinho legal em que o sujeito recria o próprio esquema de ponto flutuante ao invés de usar os tipos float e double. No esquema do sujeito, a mantissa é inteira (como é nos tipos float e double), mas sem o bit ‘1’, implícito e o expoente é de base 10, não 2. Relembrando, um número em ponto flutuante, binário, tem o formato:

885px-Float_example.svg

A parte da fração é um valor inteiro com um ‘1’ na frente (que não é mostrado no esquema acima). No exemplo, seria 0b101000000000000000000000. Um valor de 24 bits que, multiplicado por 2^{e-127}=2^{-3} e por (-1)^s=1, nos dá o valor fracionário em decimal.

O que o sujeito fez foi criar uma pequena estrutura do tipo:

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

O que dá uma estrutura diferente: O valor inteiro pode ter até 25 bits, variando de -16777216 até 16777215 (-2^{24} até 2^{24}-1 e o expoente pode variar de -64 até 63. O valor 0 é perfeitamente codificado com todos os bits zerados (0\cdot10^0) e valores negativos dependem do sinal de value. Assim as rotinas de conversão de double para fp10_s e vice-versa ficam assim:

struct fp10_s dtofp(double x)
{
  struct fp10_s fp;
  int signal = (x < 0);
  int e = 0;

  if (signal)
    x = -x;
  
  while (x > 0xffffff)
  {
    x /= 10.0;
    if (++e > 63)
    {
      fp.value = 0xffffff;
      if (signal)
        fp.value = -fp.value;
      fp.expoent = 63;
      return fp;
    }
  }

  while (x < 1)
  {
    x *= 10.0;
    if (--e < -64)
    {
      fp.value = fp.expoent = 0;
      return fp;
    }
  }

  fp.value = lrint(x);
  if (signal)
    fp.value = -fp.value;
  fp.expoent = e;
  return fp;
}

double fptod(struct fp10_s x)
{
  double power10 = 1.0;

  while (x.expoent > 0)
  {
    power10 *= 10.0;
    x.expoent--;
  }

  while (x.expoent < 0)
  {
    power10 /= 10.0;
    x.expoent++;
  }

  return x.value * power10;
}

Essa estrutura apresenta alguns problemas, mas para as finalidades do sujeito (que só estava interessado em armazenar valores entre 0.00001 e 1677721500000, ela funciona muito bem.

O que “contagem de bits” tem haver com isso? Bem… estou tentando encontrar um esquema diferente que me possibilite escrever rotinas mais rápidas e garantir a precisão desejada… Lidar com double não é uma opção, já que ele ocupa o dobro de espaço da estrutura acima… A estrutura fp10_s ocupa, exatamente, 4 bytes ou o mesmo tamanho de um int. Então, estou estudando rotinas de conversão de ponto-flutuante para “ascii”. Usar sprintf() não é uma opção (muito lerda!) e usar rotinas aceleradas para conversão de double para ascii também não é. Não por causa do tamanho do double, mas porque elas também são bem lentas em comparação com a rotina original feita pelo sujeito! Se você está curioso, algumas dessas rotinas podem ser encontradas aqui.

De qualquer modo, estive procurando em minhas anotações as rotinas rápidas para contagem de bits setados ou zerados de um lado ou outro de um valor inteiro. O que quero é contar quantos bits zerados existem do lado esquerdo para poder achar o ‘1’ implícito o mais rápido possível. Um bom material sobre o assunto pode ser lido aqui… Mas existe um jeito mais rápido desde a criação dos processadores 386!

A instrução BSR (Bit Scan Reverse) faz exatamente isso! Ela conta quantos bits zerados existem à esquerda do valor inteiro até que um bit ‘1’ seja encontrado. Se encontrar o bit ‘1’, retorna a posição do bit, senão flag ZF estará setado. A rotina fica assim:

int hzbitcnt(unsigned int x)
{
  int found=0, bit;

  __asm__ __volatile__ (
    "  bsrl %2,%0\n"
    "  setnz %%dl"
    : "=a" (bit), "+d" (found)
    : "r" (x)
  );

  // Retorna quantos bits temos que deslocar para
  // a esquerda para eliminarmos o '1' implícito.
  if (found)
    return 32 - bit;

  return 0;
}

A rotina final, gerada pelo compilador para x86_64, fica assim:

hzbitcnt:
  xor   edx,edx
  bsr   edi,eax
  setnz dl
  xor   ecx,ecx
  test  edx,edx
  jz    .L2
  mov   cl,32
  sub   ecx,eax
.L2:
  mov   eax,ecx
  ret   

Podemos melhorá-la colocando todos os testes dentro do bloco __asm__, mas está muito boa, no geral… O compilador poderia aproveitar o ZF vindo da instrução BSR, por exemplo… Felizmente temos uma função built in do GCC chamada __builtin_clz() de “Count Leading Zeroes” que simplifica muito as coisas:

shift = 32 - __builtin_clz(x);

Mas o código gerado é estranho:

  bsr  edi,edi  ; EDI é 'x'
  mov  eax,32   ; EAX é 'shift'.
  xor  edi,31
  sub  eax,edi

Note que ela desconsidera totalmente o flag ZF e o manual de desenvolvimento da Intel diz, claramente que se ZF=1, o valor destino da instrução BSR é indefinido! É mais seguro, então fazer algo assim:

shift = x ? 32 - __builtin_clz(x) : 0;

E o código resultante:

  xor  eax,eax
  test edi,edi
  jz   .L2
  bsr  edi,edi
  mov  al,32
  xor  edi,31
  sub  eax,edi
.L2:

Melhor que o meu codigo original, não é? Anyway… se você precisar contar os bits zerados à direita do valor, use BSF (Bit Scan Forward). Ambas as instruções, como falei, são padrão desde o 386. Existe uma instrução parecida com BSF que retorna a contagem de bits zerados do lado esquerdo: LZCNT (Leading Zeroes Count), mas ela não está presente em todos os processadores… Assim como existe uma que conta quantos bits setados existem no valor POPCNT.. Essa é uma instrução bem diferente do que queremos: Se o valor for 5, por exemplo, POPCNT retornará 2 (5 = 0b101).

Anúncios