AVR Freaks

Sometime google is your freind.

https://en.wikipedia.org/wiki/Linear_congruential_generator

and more specifically

https://en.wikipedia.org/wiki/Lehmer_random_number_generator

Both links come with code examples.

While I have not looked in detail at the code above,  Do you know how the system represents floats and how they are passed in.  Or do you have a good understanding of fixed point or BCD numbers and their respective libraries.   I also am not seeing the label Rand:  is this your code or are you calling the libraries rand() function that implements the prime polynomial?

Also most ASM uses ';' for comments.   the C++ slashes '//' make the code hard to read.   I still get a laugh when I remember one of my classmates commenting the ASM code by spelling out each instruction mnemonic.  When documenting ASM code (which is an art) you are explaining to the reader and your self later, what the code does, not what the code is. 

Edit: corrected auto spill check.

Well, i converted the code to C to make it easy to analyze the pseudorandom sequence that is generated. I think it is correct, I didn't test against the Z80 code, but it does seem to generate the same numbers as the AVR code, so my guess is they are indeed all equivalent.

My conclusion is that this is a crappy pseudorandom generator, with no real mathematical basis, just some guy thinking he was clever but did not actually look at the numbers generated. I did. A good 16 bit sequence will contain all, or at least most, 16 bit numbers. This one contains only 306 numbers. I seeded it with one of the numbers in the sequence for illustration purposes. If you seed with a number that is not in the sequence, it will eventually settle in the sequence anyway. Or maybe settle in a different short sequence. Anyway, this is not a good algo.

I recommend the linear feedback shift register method, like I mentioned in a recent thread. The congruence method is fine, but computationally very intensive, I wouldn't use it in a 8 bit MCU.

Code in C, for testing in a PC and view the sequence:

#include <stdio.h>

_Bool carry;
unsigned short RandSeed = 0x221E;

unsigned short sbc16 (unsigned short lval, unsigned short rval) {
	rval += carry;	
	carry = (rval > lval);
	return lval - rval;	
}

unsigned char sbc8 (unsigned char lval, unsigned char rval) {
	rval += carry;	
	carry = (rval > lval);
	return lval - rval;	
}

int main (void) {
	unsigned short de, hl;
	unsigned char a;

	int n;
	for (n = 1; n < 65536; n++) {
		de = RandSeed;
		a = de >> 8;
		hl = (de << 8) + 0xFD;
		carry = 0;

		hl = sbc16(hl, de);
		hl = sbc16(hl, de);

		a = sbc8(a, 0);

		de = a;
		hl = sbc16(hl, de);
		hl += carry;

		RandSeed = hl;

		printf("0x%.4X\n", RandSeed);
		if (RandSeed == 0x221E) break;
	}
	printf("%d", n);
}

Let me see, Z80... maybe a Game Boy or ZX Spectrum emulator could be used.

My conclusion is that this is a crappy pseudorandom generator

It certainly doesn't look like most of the random generators I've seen - no XOR, no shifting...

I always used a 39-bit MLS with 5 registers as there are two taps 8 apart so you can do a byte-wide XOR and get 8 shifts at once.

No, he's right.  If you look at the latest "AVR Instruction Set" document ( http://www.atmel.com/images/atme... from 2016), it says that the 16bit instructions use the R25:24 sytax:

Example:

 

adiw r25:24,1 ; Add 1 to r25:r24
adiw ZH:ZL,63 ; Add 63 to the Z-pointer(r31:r30)

 mov w r17:16,r1:r0 ; Copy r1:r0 to r17:r16

Now, that is the Atmel assembler syntax, and sparrow2 might be using the Gnu assembler, which is slightly different.

Or the assembler could have been updated to accept multiple syntaxes...

this is the output from the studio7 C compiler (the .lss file)

  460:    0a 96           adiw    r24, 0x0a

Sure, but that's clearly gcc...

And I just checked [the Atmel assembler ] actually eat adiw r25:r24,1 (and make the same code as normal adiw r24,1)

Interesting.  I suspect that a lot of this is because the people (HW engineers?) who tried to define the assembly language, didn't actually understand much about writing an assembler.  Or rather, they get oblivious of the two competing STYLES of assembler, that go back at least to the Intel vs Zilog mnemonics for the 8080/z80.

Most machine languages have an "opcode" field and some argument fields.  And most assemblers have an "instruction" field and some "operand" fields.

In the orignal (Intel 8080) (let's call it "old style") assembler, things were very simple.  You defined an "instruction" for each possible opcode, and then parsed operands depending on what that opcode needed.   So 8080 had:

  mov  reg2, reg1      ; move one register to another
  mvi  B, const  ; move immediate val to register
  lxi  B, reg1   ; move immediate val to register pair.
  lda  memaddr   ; move memory from memaddr to acc.

(and more), all of which did some sort of "move value to register."   In the newer (Zilog) (let's call it "polymorphic"), the instructions are more generic, but the operand syntax becomes more complex, and you have to figure out which opcode to produce based on both the instruction AND the argument syntax.  So they had:

   LD  reg1,reg2    ; move one register to another
   LD  reg1, number ; move immmediat value to register
   LD  regpair, number ; move immed16 to register pair
   LD  A, (memaddr)   ; move memory from memaddr to acc

(If I did it right, those should produce the same binary as the first examples.)

(They were all probably ATTEMPTS to duplicate mainframe/minicomputer instruction sets that were much more "regular" in both syntax and execution (but more complex HW.)  Like the PDP11;  All the microcontroller vendors used to claim "PDP11-like instruction set" even when they weren't very close at all.)

(Interestingly, Intel went polymorphic when they designed the 8086 instruction set.  (And strongly typed, too.   This led to some really ugly instructions.)

The AVR "adiw  R25:R24, 1" syntax has both a unique instruction name AND an operand syntax that identifies the instruction as a 16bit add.  An assembler doesn't need both.