## Problem converting small random Z80 code to AVR

42 posts / 0 new
Author
Message

I found a relative small random number generator written in Z80 ASM, and I have tried to convert it to AVR but it don't work , if it's the code or my translation that fail I don't know so:

Are there anyone that can check if the Z80 code actually work?

and/or what I have done wrong? (I haven't done Z80 for a long time so perhaps something with the carry is not what I expect or something like that)

it's all here (I know that it can be optimized a lot but first I want it to work)

```;
; AssemblerApplication4.asm
;
; Created: 09-02-2017 23:45:45
;
//Z80 code
//ld  de,(RandSeed)
//ld  a,d
//ld  h,e
//ld  l,\$FD
//or  a
//sbc hl,de
//sbc hl,de
//ld  d,0
//sbc a,d
//ld  e,a
//sbc hl,de
//jr nc,Rand
//inc hl
//Rand ld (RandSeed),hl

//r23 a
//r25:r24 de
//r27:r26 hl
//r17:r16 RandSeed

//Z counter
ldi r30,0
ldi r31,0
//seed=1
ldi r16,1
ldi r17,0

start:

movw r24,r16 //ld seed

mov r23,r25 //a=d
mov r27,r24 //h=e
ldi r26,0xfd//l=fd
clc  //or a
sbc r26,r24
sbc r27,r25 //hl-=de
sbc r26,r24
sbc r27,r25 //hl-=de
ldi r25,0   //d=0
sbc r23,r25 //a-=d

mov r24,r23 //e=a

sbc r26,r24
sbc r27,r25 //hl-=de

brcc L0
L0:
movw r16,r26//store seed

or r17 ,r17
brne start
nop
rjmp start
```

My way of checking is to have a breakpoint at "nop" and then see different numbers in r16 that only repeat after 256 times, (Z show the number of loops)

This topic has a solution.
Last Edited: Wed. Feb 15, 2017 - 08:55 AM

I have never written much Z80.   I was happy with 6502, 68000, 8051, ...

I cannot believe that any ASM programmer would write left-flush code.  (with one notable exception)

I suspect that if you formatted the code,   it would become instantly readable.

David.

? there are one label so what is the difference?

But if you think it make a difference here is it better formatted: (only Z80 and the equivalent AVR code are formattet )

```;
; AssemblerApplication4.asm
;
; Created: 09-02-2017 23:45:45
;
//Z80 code
//	ld		de,(RandSeed)
//	ld		a,d
//	ld		h,e
//	ld		l,\$FD
//	or		a
//	sbc		hl,de
//	sbc		hl,de
//	ld		d,0
//	sbc		a,d
//	ld		e,a
//	sbc		hl,de
//	jr		nc,Rand
//	inc		hl
//Rand  ld	       (RandSeed),hl

//	r23 a
//	r25:r24 de
//	r27:r26 hl
//	r17:r16 RandSeed

//Z counter
ldi r30,0
ldi r31,0
//seed=1
ldi r16,1
ldi r17,0

//Z80 code start

start:
movw	        r24,r16		//ld seed

mov		r23,r25		//a=d
mov		r27,r24		//h=e
ldi		r26,0xfd	//l=fd
clc				//or a
sbc		r26,r24
sbc		r27,r25		//hl-=de
sbc		r26,r24
sbc		r27,r25		//hl-=de
ldi		r25,0		//d=0
sbc		r23,r25		//a-=d

mov		r24,r23		//e=a

sbc		r26,r24
sbc		r27,r25		//hl-=de

brcc	        L0
L0:
movw	        r16,r26		//store seed

//Z80 code end

or r17 ,r17
brne start
nop
rjmp start
```

edit some formatting went wrong in the forum

Last Edited: Sat. Feb 11, 2017 - 05:24 PM

Maybe convert it to C first? It might be easier to debug. Sure, simulating the carry flag will take some work.

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.

Last Edited: Sun. Feb 12, 2017 - 08:02 AM

'Pnuemonic' - did he have trouble breathing? Or was he posessed by air?

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);
}```

#5 If you convert to C I gladly write the AVR ASM :)

#6 They are all at least 32 bit.

This code "if it works" use only simple 16 arithmetic for a 16 bit number.

Rand:  is this your code or are you calling the libraries rand() function that implements the prime polynomial?

Rand that is the label for the Z80 code

`jr		nc,Rand`

That is the good thing with this , there is no poly. and no loops, just 14 Z80 instructions, (and about the same in optimized AVR ASM so if it works it will be about 14 clk)

So aren't there any that can check is the Z80 code actually works, or point to a simple Z80 assembler and simulator?

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

Is it important that you use the same Z80 algo for the PRN?  If not, I'd go for a LFSR.  There are plenty of maximal length LFSR polynomials which require XOR on only the top 8 bits.  This is true for just about any length LFSR.  For instance, the following 32-bit polynomials are maximal length:

0xA3000000
0xAF000000
0xF5000000

Running the LFSR one step then becomes:

```        lsr
ror
ror
ror
eor
```

There are 2,100 other polynomials for maximal length 32-bit LFSR which require XOR on only 2 bytes, and over a quarter of a million polynomials which require XOR on only 3 bytes.  The remainder of the maximal length 32-bit polynomials (over 67 million of them) require XOR on all 4 bytes.

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

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...

Kartman wrote:
'Pnuemonic' - did he have trouble breathing? Or was he posessed by air?

Auto spill check.  Mnemonic

I now work with pneumatic pipe organs.  Some pipes which are white noise random generators.

joeymorin wrote:

Is it important that you use the same Z80 algo for the PRN?  If not, I'd go for a LFSR.  There are plenty of maximal length LFSR polynomials which require XOR on only the top 8 bits.  This is true for just about any length LFSR.  For instance, the following 32-bit polynomials are maximal length:

0xA3000000
0xAF000000
0xF5000000

Running the LFSR one step then becomes:

```        lsr
ror
ror
ror
eor
```

There are 2,100 other polynomials for maximal length 32-bit LFSR which require XOR on only 2 bytes, and over a quarter of a million polynomials which require XOR on only 3 bytes.  The remainder of the maximal length 32-bit polynomials (over 67 million of them) require XOR on all 4 bytes.

I was just looking for that page this morning, thanks, Joey!

Four legs good, two legs bad, three legs stable.

But then there are some thing we don't get because the special thing with this code is that it should go thru all 2^16 combinations, and not the normal 2^16-1 .

I just found this code that do 2^16 as well :

```lda seed
beq lowZero ; \$0000 and \$8000 are special values to test for

; Do a normal shift
asl seed
lda seed+1
rol
bcc noEor

doEor:
; high byte is in .A
eor #>magic
sta seed+1
lda seed
eor #<magic
sta seed
rts

lowZero:
lda seed+1
beq doEor ; High byte is also zero, so apply the EOR
; For speed, you could store 'magic' into 'seed' directly
; instead of running the EORs

; wasn't zero, check for \$8000
asl
beq noEor ; if \$00 is left after the shift, then it was \$80
bcs doEor ; else, do the EOR based on the carry bit as usual

noEor:
sta seed+1
rts```

and I just made a quick AVR version and that (I'm good at 6502 ASM), at that worked fine and 2^16 rounds between the same numbers, so I guess that I clean it up and post it here.

Right, but if you use a 24-bit LFSR, it will go through 2^24-1.  If you take only 16 of those bits, then the probability distribution will be nearly flat, with all values equally weighted at (2^16)/(2^24-1), except for 0x0000 which will have a slightly lower weight of (2^16-1)/(2^24-1).  Going from 16-bit to 24-bit costs you 1 cycle, provided you use an appropriate polynomial.  There are 5 24-bit maximal length polynomials requiring only one XOR:

0x8D0000
0xAF0000
0xD80000
0xDB0000
0xE10000

EDIT:  There are no polynomials for a maximal length 16-bit LFSR which require only one XOR operation.

EDIT2: typo (one XOR)

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Sun. Feb 12, 2017 - 07:11 PM

EDIT:  There are no polynomials for a maximal length 16-bit LFSR which require only XOR operation.

I know , and the 6502 make a special case so 0 can be used.

But I guess that I should look into 24 bit LFSR aswell .

So you mean, force the zero into the sequence. I would insert it after '1', then, after zero the sequence would continue like the normal sequence after one.

```        lsr
ror
ror
ror
brne normal_seq     ;normal sequence if not zero or one
rjmp no_mask        ;if one, next in sequence is zero
normal_seq:
eor

edit: oops, of course the code won't work like that. But I get the idea, I think.

Last Edited: Sun. Feb 12, 2017 - 10:10 PM

I think I misread this :

EDIT:  There are no polynomials for a maximal length 16-bit LFSR which require only one XOR operation.

all full length LFSR can't use 0.

But you say that there are no 16-bit LFSR with only one XOR, but the link I gave show 6 polynomials that only do one XOR! (where one byte is 0)

How can that be? (perhaps because he shift the other way ? but it's still a LFSR! or what am I missing?)

Last Edited: Mon. Feb 13, 2017 - 09:26 AM

Yeah, it seems there are 6:

9C00

B400

BD00

CA00

EB00

FC00

Correct.  I shouldn't post when I'm hungry :)

Those 6 are even there in my own library!

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Mon. Feb 13, 2017 - 03:58 PM
This reply has been marked as the solution.

ok if any interest here is the small ASM program. It go through all 2^16 combinations so no seed are needed.

r3:r2 is the random number.

```;0x0000 and 0x8000 are special cases, where you tread carry different
movw	        r24,r2
or		r24,r25   ;check for zero after shift
brne	        L1        ;if not zero a normal case
brcc	        L2        ;it was zero
rjmp	        L0        ;it was 0x8000
L1:	brcc	        L0        ;only eor if MSB was 1
L2:	ldi		r24,0xbd
eor		r2,r24
L0:                               ;done
```

edit funny tab size

I have marked this as the solution but it's not the code in #1 I never got that to work, but this go through all 2^16 combinations as well (so no init needed for simple things)

It's the 6502 code in #16 converted to AVR

Last Edited: Wed. Feb 15, 2017 - 09:08 AM

What's in r25?

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

r3

Ah, didn't catch that it was movw... ;-)

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

I know ;)

and here is the normal, 2^16-1 (where 0 isn't a part):

```	add		r2,r2
brcc	        L0
ldi		r24,0xbd
eor		r2,r24
L0:
```

and here is the normal, 2^16-1 (where 0 isn't a part):

Except you shift left instead of right.

So the polynomial needs to be bit-reversed w.r.t. @koopman's polynomials.

Curiously, you've stumbled upon the one maximal-length 16-bit polynomial for which that doesn't matter, because BD in binary is palindromic.

In your code above, you're XORing with 0xBD, so the left-shift polynomial is 0x00BD, or 0b0000000010111101.  This makes the right-shift polynomial 0b1011110100000000, or 0xBD00, equivalent to the left-shift polynomial.

Had you chosen any of the other single-XOR maximal-length polynomials:

• 009C = 0b0000000010011100 -> 0b0011100100000000 = 0x3900
• 00B4 = 0b0000000010110100 -> 0b0010110100000000 = 0x2D00
• 00CA = 0b0000000011001010 -> 0b0101001100000000 = 0xA600
• 00EB = 0b0000000011101011 -> 0b1101011100000000 = 0xD700
• 00FC = 0b0000000011111100 -> 0b0011111100000000 = 0x3F00

... and used it without modification (i.e. without reversing the bits) then you would not have had a maximal-length LFSR.

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

I just made a copy of one of the numbers in the link in #16, where high byte was zero.

I just made a copy of one of the numbers in the link in #16, where high byte was zero.

Then you got lucky ;-).

Quoting from the koopman document:

In the above data files, the feedback term is the hexadecimal number that represents the feedback polynomial for a right-shifted LFSR per the following C code LFSR inner loop implementation:

```  if (i & 1)  { i = (i >> 1) ^ feed; }
else        { i = (i >> 1);       }```

So they are for a right-shifting algorithm, whereas you've implemented a left-shifting algorithm.  Both are correct, but a given polynomial for one is the mirror image of the equivalent polynomial for the other.

So quite the unintended prescience you showed by choosing the only palindromic polynomial out of the bunch!

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

Last Edited: Tue. Feb 14, 2017 - 11:37 PM

But the link in #16 are also shifting left and that is the code I implemented ! (and poly I used)

The hole thread was that I wanted to implement a simple 2^16 random generator so no seed was needed, and I found the one in #1 but never got it to work.

The code in #16 I got to work without any problems (first with a kind of 1 to 1 translation from 6502) I made an optimized version that is the one in #23.

Sorry, when you referenced #16 I assumed you meant the koopman link I'd posted in #11.  My mistake, I didn't scroll back and check that this was so.  Time for some food, I guess ;-)

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

I notice that these three instructions are not syntactically right and the assembler should have thrown them out:

```adiw r26,1 //inc hl                     should be inc r26
L0:
movw r16,r26//store seed                should be mov  r16,r26

adiw r30,1 //just loop counter          should be inc r30```

ADIW and MOVW are operations on 16-bit words composed of two registers:

Syntax:                                 Operands:
ADIW Rd+1:Rd,K            d ∈ {24,26,28,30}, 0 ≤ K ≤ 63

MOVW Rd+1:Rd,Rr+1:   Rr,Rd ∈ {0,2,...,30}, r ∈ {0,2,...,30}

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.

???

I think that you have to learn AVR ASM!

an AVR can't do 16 bit inc (as the Z80 code do with inc hl), but adiw r26,1 do the same add 1 to the register pair r27:r26

same with movw r16,r26 this is a 16 bit move of seed (that is 16 bit), you suggest a 8 bit move (if your AVR don't have movw you had to use mov r16,r26 and mov r17,r27 that do the same job).

same with inc Z (adiw r30,1) that is a 16 bit inc

I think you look in some 15+ year old documentation

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
```
``` 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...

No I use the Atmel assembler

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

the instruction manual I have the examples show :

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

460:    0a 96           adiw    r24, 0x0a    ; 10

And I guess that we all know how bad atmel is about documents.

So it's only the school kid that make the manuals that must have made cut and paste from the absolute first atmel compiler.

Or Atmel simply provided an inadequate change document to the technical writers.

I've beaten up on the technical writers before, but really there's no justification to conclude it's their fault and target them specifically.  The enterprise shoulders the blame.

 "Experience is what enables you to recognise a mistake the second time you make it." "Good judgement comes from experience.  Experience comes from bad judgement." "Wisdom is always wont to arrive late, and to be a little approximate on first possession." "When you hear hoofbeats, think horses, not unicorns." "Fast.  Cheap.  Good.  Pick two." "We see a lot of arses on handlebars around here." - [J Ekdahl]

At least there should be someone that proofread what comes out!

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.

(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

(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.

My guess is that for the assembler : is a normal letter (not used for anything I know of).

so R25:R24 is one word that means the same as R24

Ups to fast it's the label "marker"

Last Edited: Sat. Feb 18, 2017 - 10:42 PM