@Ozzy: Ich antworte mal hier, vielleicht kann ja sonst noch wer was damit anfangen...
:-k Was meinst du mit "auf verschiedene Pins ausgeben? Sind doch immer die gleichen...
Zunächst mal mein C-File, da ist manches besser nachzuvollziehen, auch für Assembler-Progger, die kein C können :-)
#include <avr/io.h>
#include "parit-15.h"
#define POLY 0xe125 /* 1 + x^2 + x^5 + x^8 + x^13 + x^14 + x^15 */
#define DEGREE 15
#define ROOT 0x2200 /* x^9 + x^13 */
typedef uint16_t poly;
static uint16_t seed;
static poly pprod (poly, poly);
static poly ppow (poly, poly);
#define MASK(b) \
(((poly) 1) << (b))
/**
* Berechnet a*b mod p
*/
poly pprod (poly a, poly b)
{
const poly mask = MASK (DEGREE);
poly c = 0;
while (b)
{
// Ist bit i in b gesetzt?
if (b & 1)
c ^= a; // dann c = c + a * x^i
a <<= 1; // a = a*x
if (a & mask) // a = a mod p
a ^= POLY;
b >>= 1;
}
return c;
}
void __attribute__ ((naked, section (".init3")))
__init_seed()
{
uint16_t s = 0;
uint16_t *p = (uint16_t*) (RAMEND+1);
extern uint16_t __noinit_start;
while (p >= &__noinit_start + 1)
s ^= * (--p);
seed = s;
}
// Liefert eine Pseudo-Zufallszahl x
// mit 1 <= x <= 2^DEGREE-1 = 32767
uint16_t prandom()
{
return (uint16_t) (seed = pprod (seed, ROOT));
}
Hier das, was gcc draus macht. "Out of the Box" wirst du das nicht nutzen können, weil (i) benutzt du wohl kein GNU-Assembler und (ii) hast du bestimmt ne andere ABI (Registerverwendung etc) und wirst es in lesbareren Assembler hinschreiben wollen.
__init_seed
Als erstes wird __init_seed aufgerufen (Vorsicht, muss noch ein RET dazu). Sie berechnet aus dem uninitialisierten RAM-Inhalt eine seed, indem der RAM-Inhalt als 16-Bit-Werte interpretiert wird, die mit XOR "überlagert" werden. Das Ende des RAM war bei 1120 (=96+1024 = 0x60+0x400). Das RAM wird von hinten dach vorne durchpflügt.
Evtl reicht dir schon, ne seed aus den (ebenfalls nicht initialisierten) GPRs zu besorgen: seed = R1:R0 xor R3:R2 xor ... xor R31:R30.
Für die Anfangs-seed muss gelten 1 <= seed <= 32767
prandom
Besorgt eine weitere Zufallszahl x mit 1 <= x <= 32767 und aktualisiert seed. Am klarsten wird das im C-File.
avr-gcc hat sich entschieden, pprod in prandom zu integrieren...aber egal. Magische Zahlen sind:
8704 = ROOT
-7899 = POLY
Der 15-Bit-Rückgabewert wird in R25:R24 zurückgegeben.
Zerstört werden die Inhalte von R18-R23, seed lebt im RAM und wird wie gesagt aktualisiert. __zero_reg__ ist hier R1 (es entält den Wert 0).
pprod
Die eigentliche, für den Pseudozufall verantwortliche Routine. Auf den mathematischen Hintergrund will ich nicht eingehen. (Entweder man raffts am Kommentar, oder versteht's auch mit Erklärung nicht tiefer).
.file "parit-15.c"
.arch atmega8
__SREG__ = 0x3f
__SP_H__ = 0x3e
__SP_L__ = 0x3d
__tmp_reg__ = 0
__zero_reg__ = 1
.global __do_copy_data
.global __do_clear_bss
; GNU C version 3.4.5 (avr)
.section .init3,"ax",@progbits
.global __init_seed
.type __init_seed, @function
__init_seed:
/* prologue: frame size=0 */
/* prologue: naked */
/* prologue end (size=0) */
ldi r18,lo8(0) ; s,
ldi r19,hi8(0) ; s,
ldi r30,lo8(1120) ; p,
ldi r31,hi8(1120) ; p,
.L7:
ldi r24,hi8(__noinit_start+2) ; ,
cpi r30,lo8(__noinit_start+2) ; p,
cpc r31,r24 ; p,
brlo .L6 ; ,
ld r25,-Z ; tmp43,
ld r24,-Z ; tmp43,
eor r18,r24 ; s, tmp43
eor r19,r25 ; s, tmp43
rjmp .L7 ;
.L6:
sts (seed)+1,r19 ; seed, s
sts seed,r18 ; seed, s
/* epilogue: frame size=0 */
/* epilogue: naked */
/* epilogue end (size=0) */
/* function __init_seed size 17 (17) */
.size __init_seed, .-__init_seed
.text
.global prandom
.type prandom, @function
prandom:
/* prologue: frame size=0 */
/* prologue end (size=0) */
lds r18,seed ; a, seed
lds r19,(seed)+1 ; a, seed
ldi r20,lo8(8704) ; b,
ldi r21,hi8(8704) ; b,
ldi r24,lo8(0) ; c,
ldi r25,hi8(0) ; c,
ldi r22,lo8(-7899) ; tmp49,
ldi r23,hi8(-7899) ; tmp49,
.L13:
sbrs r20,0 ; b,
rjmp .L11 ;
eor r24,r18 ; c, a
eor r25,r19 ; c, a
.L11:
lsl r18 ; a
rol r19 ; a
sbrs r19,7 ; a
rjmp .L12 ;
eor r18,r22 ; a, tmp49
eor r19,r23 ; a, tmp49
.L12:
lsr r21 ; b
ror r20 ; b
cp r20,__zero_reg__ ; b
cpc r21,__zero_reg__ ; b
brne .L13 ; ,
sts (seed)+1,r25 ; seed, c
sts seed,r24 ; seed, c
/* epilogue: frame size=0 */
ret
/* epilogue end (size=1) */
/* function prandom size 30 (29) */
.size prandom, .-prandom
.lcomm seed,2
/* File "parit-15.c": code 47 = 0x002f ( 46), prologues 0, epilogues 1 */
Die Periode der Zahlen liegt bei 2^15-1 = 32767. Für gleiche seed wird auch die gleiche Folge erzeugt. Ein Zufallswert ist nur abhängig von der Anfangs-seed und der Anzahl der prandom-Aufrufe.
Wenn du einen 8-Bit Zufallswert willst, dann schiebst du der Wert am besten um 2 Bits (oder so) nach rechts und wirfst den high-Teil weg. Der Wertebereich ist dann 0...255.
Einen 8-Bit-Algorithmus zu implementieren ginge auch. Er wäre merklich knapper und schneller, hätte allerdings nur eine Periode von 127 (mit etwas Hirnschmalz auch 255). Du bräuchtest dann ein irreduzibles Polynom POLY vom Grad 8 über F2 sowie eine primitive Wurzel ROOT von (F2[x] mod r*F2[x])*.