Como implementar função de número randômico não vicioso sem usar libs gcc

Oi pessoal, estou precisando de uma implementação não viciosa de uma função que gera um número randômico em C e que não utilize nenhum recurso do gcc, ou seja, NÃO utilize bibliotecas <stdio.h> e <stdlib.h>. (Obs: estou usando apenas para testar e imprimir em tela, depois irei remover )

Eu consegui fazer a partir desta referência, sendo que ela é viciosa, ou seja toda vez que eu inicializo ele me dá sempre os mesmos resultados.

Fiz a implementação abaixo:

[code]#include <stdio.h>
#include <stdlib.h>

static int randseed = 1;

void srandom(int seed) {
randseed = seed;
}
/#if sparc && !__SUNPRO_C8/
#ifdef notdef
#ifdef svr4
#define RANDOM “random”
#define RANDSEED “randseed”
#else
#define RANDOM “_random”
#define RANDSEED “_randseed”
#endif
asm("
.global " RANDOM " ;\

" RANDOM ":                             ;\
    sethi   %hi(16807), %o1                 ;\
    wr      %o1, %lo(16807), %y             ;\
    sethi  %hi(" RANDSEED "), %g1          ;\
    ld     [%g1 + %lo(" RANDSEED ")], %o0  ;\
    andcc  %g0, 0, %o2                     ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %o0, %o2                   ;\
    mulscc  %o2, %g0, %o2                   ;\
    rd      %y, %o3                         ;\
    srl     %o2, 16, %o1                    ;\
    set     0xffff, %o4                     ;\
    and     %o4, %o2, %o0                   ;\
    sll     %o0, 15, %o0                    ;\
    srl     %o3, 17, %o3                    ;\
    or      %o3, %o0, %o0                   ;\
    addcc   %o0, %o1, %o0                   ;\
    bneg    1f                              ;\
    sethi  %hi(0x7fffffff), %o1            ;\
    retl                                    ;\
    st     %o0, [%g1 + %lo(" RANDSEED ")]  ;\
1:                                              ;\
    or      %o1, %lo(0x7fffffff), %o1       ;\
    add     %o0, 1, %o0                     ;\
    and     %o1, %o0, %o0                   ;\
    retl                                    ;\
    st     %o0, [%g1 + %lo(" RANDSEED ")] ");

#else
int random() {
register int x = randseed;
register int hi, lo, t;

hi = x / 127773;
lo = x % 127773;
t = 16807 * lo - 2836 * hi;
if (t <= 0)
t += 0x7fffffff;
randseed = t;
return (t);

}
#endif

int main() {
printf("\n%d", random() % 100);
printf("\n%d", random() % 100);
printf("\n%d", random() % 100);
printf("\n%d", random() % 100);
printf("\n%d", random() % 100);
printf("\n");
system(“PAUSE”);
}[/code]
quando eu rodo da 1ª vez ele me traz o resultado:

[quote]7
49
73
58
30
e por aí vai[/quote]
quando eu rodo pela 2ª vez, o resultado é o mesmo, sendo que preciso que me traga a valores diferentes.
se vocês pegarem o código acima do jeito que está ele compila e roda.

alguém conhece alguma referência ou já se envolveu com problema parecido ?

editado: adição da palavra NÃO em negrito acima

Cara, pra esses casos costuma-se usar como seed o tempo (em minutos, segundos, mili segundos, etc) pra garantir que sempre seja diferente.
Experimente ^^

Abraços.

é verdade, no caso como eu poderia implementar usando o seed?

uma coisa que não mencionei é que irei usar este código em um microcontrolador, em específico 8051, por isso justifico aqui que não posso usar nenhuma lib do compilador gcc.

estive conversando com um colega de trabalho e ele me orientou a mesma coisa, concluímos que eu teria que correr para esta teoria, ou seja, utilizar um timer(contabilizar o tempo) ou pulso de clock.

sendo que o microcontrolador, família 8051, não tem um timer, ou seja, eu teria que implementar a mais um timer para depois tentar sincronizar com o computador de alguma forma, deixando ele sempre ligado na bateria para garantir a continuidade deste timer ser progressivo e o algoritmo consequentemente não vicioso e repetivivo.

Puxa vida, eu fiz isso diversas vezes, mas nao consegui lhe apresentar um exemplo…tente procura algo com a funcao abaixa (vem da <stdlib.h>)

void srand(unsigned int seed);

Pelo que me lembro passava o tempo corrente para ela…

Abracos

<><

é verdade conforme função acima eu modifiquei a chamada da função conforme exemplo que citei acima entre as linhas 78 e 82 para:

neste caso estou usando uma semente, em que este número poderia ser o seed, timer ou pulso de clock do meu microcontrolador.

meu próximo problema agora é como implementar o timer ou pulso de clock para passar sempre uma semente diferente que irá passar este valor para função random ( x ).

estou pesquisando a partir deste tutorial como posso fazê-lo. sei que foge do escopo deste tópico, mas ainda continuo insistindo a fim de obter sempre um número randômico.

estarei pensquisando a partir do timer ou pulso de cloclk do microcontrolador. se alguém puder ajudar sobre como posso fazê-lo sobre o assunto agradeço.

Cara, boa sorte na sua busca!
Garanto que o aprendizado será muito bom, sempre é assim =P

Infelizmente não sei te ajudar nesse caso, nunca programei pra microcontroladores, dispositivos embarcados, etc e tal, mas provavelmente haverá muito material disponível na rede.
Espero tê-lo ajudado de alguma forma, nem que seja pra excluir uma alternativa inviável (otimismo sempre hehe).

Abraços!

valeu pessoal, só para constar os problemas que estou precisando resolver, pelo menos por enquanto: :smiley:

[quote]1. o valor da semente que eu passaria, seria por exemplo 200811251317XX(o segundo é desprezível) + YYYYYY, em que na verdade está dizendo 2008-11-25 às 13:17:XX + YYYYYY(número de série do equipamento). O problema é, tenho que arranjar uma forma que possa representar este número com a menor quantidade de caracteres possíveis (estou pensando em usar o resto da divisão por 100, algo assim). Ainda estou pesquisando qual valor exato vou aplicar ao seed/semente. :x

  1. efetuar a contagem de clock de forma assíncrona para contar o time/tempo do equipamento fabricado(referências boas que ainda estou estudando TMOD SFR e TMOD [Timer Mode]). Tipicamente como a hora do computador, existe uma bateria interna que o mantém funcionando.[/quote]
    agradeço ajuda e quem já teve experiência ou têm com o assunto, pode ficar a vontade para comentar.

Vc pode olhar o capitulo 7 do numerical recipes (versão C) e traduzir algum algoritmo para Java.

http://www.fizyka.umk.pl/nrbook/bookcpdf.html

Ia sugerir utilizar o Mersenne Twister mas pelo que vi está trabalhando em plataforma 16-bits.

Boa sorte.

Teu problema não é um algorítmo de número pseudo-aleatórios, mas sim a seed inicial.

Existem duas formas convencionais de se resolver isso e ambas dependem das características
de entropia que você precisa.

Se você não precisa que a entropia seja alta no inicio, a solução mais simples é coletar bits a esmo a partir das interrupções de hardware e ir fazendo hashing deles em pool de entropia.

Se você precisa de entropia boa logo no início, precisa verificar quais características do teu hardware são incertas e produzem valores dispares suficientes durante a inicialização como, por exemplo, ler registradores de um dispositvo antes de inicalizá-lo. Normalmente ler alguns kilobits de memória não inicializa costumam ser suficiente se o teu microcontrolador não zerar tudo na inicialização.

[quote=peczenyj]Vc pode olhar o capitulo 7 do numerical recipes (versão C) e traduzir algum algoritmo para Java.

http://www.fizyka.umk.pl/nrbook/bookcpdf.html[/quote]
muito bom o material peczenyj, esta você tirou da cartola ? gostei bastante. estou estudando qual algoritmo ou característica comportamental ele teria, pois como o louds mencionou, inclusive um colega de trabalho eu deveria saber qual nível de entropia eu me envolveria, ou seja, a partir de quantas combinações próximas ele seria provavel uma próxima repetição.

gostei bastante a partir dos capítulos 7.4. estive justamente analisando o algoritmo irbit1, no qual descreve característica

ele possui duas formas de implementação conforme modelo abaixo:

inicialmente eu poderia utilizá-lo, pois ele têm uma característica um pouco mais eficaz, acredito, por conta do uso do desvio de bits sem necessitar muitas operações, e isto é importante, visto que esse código irá rodar dentro do microcontrolador em que o processamento da CPU dele já está em 22% de pico, ainda com a falta de algumas lógicas a fazer.

o outro capítulo que achei bacana que poderia ter um maior índice de entropia seria o 7.5 utilizando implementação cypher via DES, visto que seria mais interessante AES, pois AES também pode ser implementado em hardware e ambos são assimétricos. mas o que me desmotivou mesmo neste capítulo, foi logo o primeiro parágrafo:

se eu estivesse utilizando outro microcontrolador com maior capacidade poderia até encarar, acho que o bichinho não aguentaria no trampo, e olhe que ainda falta umas coisas básicas que irei controlar que estou somando mais 20% da CPU deste hardware.

um outro fator associado, mas não tenho certeza se existe tanta incisão nisto é que mais recurso de hardware requer mais energia, e aí consequentemente maior consumo da bateria.

estou com muito medo dos overflows, mas como disse ainda estou analisando e muito obrigado pela referência, essa já guardei nos meus bookmarks.

nunca tinha ouvido falar em Mersenne twister, mas me pareceu bastante complexo, não sei se isso é um bom sinal, mas como citei acima, acho que para o meu caso não rola que ele estaria trabalhando em cima de uma matriz de aproximadamente 623 elementos, conforme pseudo-codigo caracterizava.

acho que o bichinho também não aguentaria o trampo, mas valeu pela referência e ele me pareceu ser bastante aceitável por ter sido implementado em várias linguagens, mas sua implementação é complexa de entender.

é verdade, antes estava perdido e não sabia por onde começar, e depois que fui entendendo os conceitos já evoluí bastante.

estava pensando sobre isto, e achei mais interessante a implementação do capítulo sugerido por peczenyj, do capítulo 7.4 que se beneficia de desvios de bits a partir de poucas iterações. mas como mencionei ainda estou estudando sobre este caso.

para isto percebi que o microcontrolador que estou utilizando, o at89s8252 da atmel da família 8051, possui 2 timers de clock e estou pensando em utilizar um destes para me basear em fazer a contagem a partir de interrupção por exemplo. bem isto para mim não tenho idéia ainda de como fazer! :shock:

desculpa, mas não entendi esta parte, poderia me explicar melhor?

valeu pela força pessoal! :wink:

Se você tiver alguma RAM cujo conteúdo, antes do reset, é aleatório, então você pode usá-la como semente. O problema é que normalmente rotinas de reset costumam deixar tudo limpinho, até para evitar certos problemas.

Alguns microcontroladores, mais orientados para criptografia, contém seus próprios geradores de números aleatórios. Acho que seu microcontrolador não tem esse recurso.