Obtendo valores aleatórios sem usar a biblioteca padrão

Provavelmente você já usou uma das funções de bibliotecas padrão para obter valores “aleatórios”. Funções como rand()random() retornam um valor inteiro baseados num algoritmo chamado de “Gerador linear congruente” ou “Gerador de congruência linear” (Linar congruenrial generator, ou LCG para os íntimos). Esse gerador nada mais é que uma equação linear como a mostrada abaixo:

X_{n+1} = (a \cdot X_n + c)\ mod\ m

Ou seja, o novo valor depende do valor anterior e de alguns parâmetros (que estão definidos no interior da biblioteca)… Este tipo de gerador é rápido e tem algumas características interessantes, sob o ponto de vista dos pseudo random number generators. Mas, o que você provavelmente não sabia é que seu processador tem um gerador de números aleatórios próprio!

Processadores como o i5 e o i7 possuem a instrução RDRAND. Essa instrução tem apenas um operando: o destino onde será colocado o valor. A instrução também afeta o flag de carry, indicando sucesso ou falha. Se o carry for 1, o valor obtido é válido… se for zero, então o valor obtido “provavelmente” é também zero e inválido. Essa instrução tem outra vantagem prática: Como o processador toma conta do gerador (que é mais complicado que um LCG), não há necessidade de fornecer uma “semente”, um valor inicial. Embora exista uma instrução RDSEED, ela não é implementada em todos os processadores.

Para determinar se seu processador possui a instrução RDRAND, basta executar CPUID com EAX=1 e verificar o bit 30 do ECX. Eis um exemplo que compilará apenas com processadores i5 ou i7:

// Compilar com:
//   gcc -O2 -march=native -o test test.c
#include <stdio.h>
#include <cpuid.h>

int IsRdRndPresent(void)
{
  unsigned int a, b, c, d;

  __get_cpuid(1, &a, &b, &c, &d);

  // 0x40000000 é a constante bit_RDRND existe em cpuid.h.
  return (c & 0x40000000);

  // Obs: Verifique o bit 18 de b se quiser usar RDSEED.
}

int main(int argc, char *argv)
{
  unsigned int rand;
  _Bool ok;

  if (!IsRdRndPresent())
  {
    fprintf(stderr, "RDRND não está presente!\n");
    return 1;
  }

  __asm__ volatile (
    "rdrand %0; setc %1"
    : "=r" (rand), "=r" (ok) );

  if (!ok)
    fprintf(stderr, "RDRAND retornou um valor provavelmente invalido.\n");
  else
    printf("Rand = %lX\n", rand);

  return 0;
}

 

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s