WikiTI - User contributions [en]

Z80 Routines:Math:Random

2019-08-02T12:10:22Z

John metcalf: Added 16-bit Xorshift

[[Category:Z80 Routines:Math|Random]]
[[Category:Z80 Routines|Random]]

==Ion Random==
This is based off the tried and true [http://en.wikipedia.org/wiki/PRNG pseudorandom number generator] featured in Ion by Joe Wingbermuehle

<nowiki>;-----> Generate a random number
; output a=answer 0<=a<=255
; all registers are preserved except: af
random:
push hl
push de
ld hl,(randData)
ld a,r
ld d,a
ld e,(hl)
add hl,de
add a,l
xor h
ld (randData),hl
pop de
pop hl
ret</nowiki>

randData here must be a 2 byte seed located in ram. While this is a fast generator, it's generally not considered very good in terms of randomness.

==Linear Feedback Shift Register==
This particular prng is based on [http://en.wikipedia.org/wiki/LFSR Linear feedback shift register]. It uses a 64bit seed and generates 8 new bits at every call. LFSRSeed must be an 8 byte seed located in ram.

<nowiki>;------LFSR------
;James Montelongo
;optimized by Spencer Putt
;out:
; a = 8 bit random number
RandLFSR:
ld hl,LFSRSeed+4
ld e,(hl)
inc hl
ld d,(hl)
inc hl
ld c,(hl)
inc hl
ld a,(hl)
ld b,a
rl e \ rl d
rl c \ rla
rl e \ rl d
rl c \ rla
rl e \ rl d
rl c \ rla
ld h,a
rl e \ rl d
rl c \ rla
xor b
rl e \ rl d
xor h
xor c
xor d
ld hl,LFSRSeed+6
ld de,LFSRSeed+7
ld bc,7
lddr
ld (de),a
ret</nowiki>

While this may produces better numbers, it is slower, larger and requires a bigger seed than ionrandom. Assuming theres is a good seed to start, it should generate ~2^56 bytes before repeating. However if there is not a good seed(0 for example), then the numbers created will not be adequate. Unlike Ionrandom and its use of the r register, starting with the same seed the same numbers will be generated. With Ionrandom the code running may have an impact on the number generated. This means this method requires more initialization.

You can initialize with TI-OS's seeds, stored at seed1 and seed2, both are ti-floats but will serve the purpose.

==Combined LFSR/LCG, 16-bit seeds==
This is a very fast, quality pseudo-random number generator. It combines a 16-bit Linear Feedback Shift Register and a 16-bit LCG.
<nowiki>
prng16:
;Inputs:
; (seed1) contains a 16-bit seed value
; (seed2) contains a NON-ZERO 16-bit seed value
;Outputs:
; HL is the result
; BC is the result of the LCG, so not that great of quality
; DE is preserved
;Destroys:
; AF
;cycle: 4,294,901,760 (almost 4.3 billion)
;160cc
;26 bytes
ld hl,(seed1)
ld b,h
ld c,l
add hl,hl
add hl,hl
inc l
add hl,bc
ld (seed1),hl
ld hl,(seed2)
add hl,hl
sbc a,a
and %00101101
xor l
ld l,a
ld (seed2),hl
add hl,bc
ret
</nowiki>
On their own, LCGs and LFSRs don't produce great results and are generally very cyclical, but they are very fast to compute. The 16-bit LCG in the above example will bounce around and reach each number from 0 to 65535, but the lower bits are far more predictable than the upper bits. The LFSR mixes up the predictability of a given bit's state, but it hits every number except 0, meaning there is a slightly higher chance of any given bit in the result being a 1 instead of a 0. It turns out that by adding together the outputs of these two generators, we can lose the predictability of a bit's state, while ensuring it has a 50% chance of being 0 or 1. As well, since the periods, 65536 and 65535 are coprime, then the overall period of the generator is 65535*65536, which is over 4 billion.

==Combined LFSR/LCG, 32-bit seeds==
This is similar to the one above, except that it uses 32-bit seeds (and still returns a 16-bit result). An advantage here is that they've been tested and passed randomness tests (all of thee ones offered by CAcert labs). As well, it is still very fast.
<nowiki>
rand32:
;Inputs:
; (seed1_0) holds the lower 16 bits of the first seed
; (seed1_1) holds the upper 16 bits of the first seed
; (seed2_0) holds the lower 16 bits of the second seed
; (seed2_1) holds the upper 16 bits of the second seed
; **NOTE: seed2 must be non-zero
;Outputs:
; HL is the result
; BC,DE can be used as lower quality values, but are not independent of HL.
;Destroys:
; AF
;Tested and passes all CAcert tests
;Uses a very simple 32-bit LCG and 32-bit LFSR
;it has a period of 18,446,744,069,414,584,320
;roughly 18.4 quintillion.
;LFSR taps: 0,2,6,7 = 11000101
;291cc
seed1_0=$+1
ld hl,12345
seed1_1=$+1
ld de,6789
ld b,h
ld c,l
add hl,hl \ rl e \ rl d
add hl,hl \ rl e \ rl d
inc l
add hl,bc
ld (seed1_0),hl
ld hl,(seed1_1)
adc hl,de
ld (seed1_1),hl
ex de,hl
seed2_0=$+1
ld hl,9876
seed2_1=$+1
ld bc,54321
add hl,hl \ rl c \ rl b
ld (seed2_1),bc
sbc a,a
and %11000101
xor l
ld l,a
ld (seed2_0),hl
ex de,hl
add hl,bc
ret
</nowiki>

==Xorshift==

Xorshift is a class of pseudorandom number generators discover by George Marsaglia and detailed in his 2003 paper, ''Xorshift RNGs''.

<nowiki>
; 16-bit xorshift pseudorandom number generator by John Metcalf
; 20 bytes, 86 cycles (excluding ret)

; returns hl = pseudorandom number
; corrupts a

; generates 16-bit pseudorandom numbers with a period of 65535
; using the xorshift method:

; hl ^= hl << 7
; hl ^= hl >> 9
; hl ^= hl << 8

; some alternative shift triplets which also perform well are:
; 6, 7, 13; 7, 9, 13; 9, 7, 13.

org 32768

xrnd:
ld hl,1 ; seed must not be 0

ld a,h
rra
ld a,l
rra
xor h
ld h,a
ld a,l
rra
ld a,h
rra
xor l
ld l,a
xor h
ld h,a

ld (xrnd+1),hl

ret
</nowiki>

Z80 Routines:Math:Multiplication

2019-08-02T11:41:44Z

John metcalf: /* Signed versions */

[[Category:Z80 Routines:Math|Multiplication]]
[[Category:Z80 Routines|Multiplication]]

== Introduction ==

All these routines use the restoring multiplication algorithm, adapted to the z80 architecture to maximize speed.
They can easily be unrolled to gain some speed.

== Unsigned versions ==

=== 8*8 multiplication ===

The following routine multiplies h by e and places the result in hl

<nowiki>
mult_h_e
ld l, 0
ld d, l

sla h ; optimised 1st iteration
jr nc, $+3
ld l, e

ld b, 7
_loop:
add hl, hl
jr nc, $+3
add hl, de

djnz _loop

ret
</nowiki>

=== 16*8 multiplication ===

The following routine multiplies de by a and places the result in ahl (which means a is the most significant byte of the product, l the least significant and h the intermediate one...)

<nowiki>
mult_a_de
ld c, 0
ld h, c
ld l, h

add a, a ; optimised 1st iteration
jr nc, $+4
ld h,d
ld l,e

ld b, 7
_loop:
add hl, hl
rla
jr nc, $+4
add hl, de
adc a, c ; yes this is actually adc a, 0 but since c is free we set it to zero and so we can save 1 byte and up to 3 T-states per iteration

djnz _loop

ret
</nowiki>

=== 16*16 multiplication ===

The following routine multiplies bc by de and places the result in dehl.

<nowiki>
mult_de_bc
ld hl, 0

sla e ; optimised 1st iteration
rl d
jr nc, $+4
ld h, b
ld l, c

ld a, 15
_loop:
add hl, hl
rl e
rl d
jr nc, $+6
add hl, bc
jr nc, $+3
inc de

dec a
jr nz, _loop

ret
</nowiki>

== Signed versions ==



=== 8*8 multiplication ===

=== 16*8 multiplication ===

=== 16*16 multiplication ===

The following routine multiplies bc by de and places the signed result in dehl.

<nowiki>; 16 bit signed multiply by John Metcalf
; 32 bytes, average approx ~1090 cycles

; call with bc, de = 16 bit signed numbers to multiply
; returns de:hl = 32 bit signed product
; corrupts a

; de:hl = bc*de

multiply:
xor a
ld h,a
ld l,a
bit 7,d
jr z,muldpos
sbc hl,bc
muldpos:
ld a,b
sra a
and 0C0h
add a,d
ld d,a

ld a,16
mulloop:
add hl,hl
rl e
rl d
jr nc,mul0bit
add hl,bc
jr nc,mul0bit
inc de
mul0bit:
dec a
jr nz,mulloop
</nowiki>

Z80 Routines:Math:Square root

2019-08-02T11:31:03Z

John metcalf: Add code for square root in max 379 t-states

[[Category:Z80 Routines:Math|Square root]]
[[Category:Z80 Routines|Square root]]

==Size Optimization==
This version is size optimized, it compares every perfect square against HL until a square that is larger is found. Obviously slower, but does get the job done in only 12 bytes.
<nowiki>;-------------------------------
;Square Root
;Inputs:
;HL = number to be square rooted
;Outputs:
;A = square root

sqrt:
ld a,$ff
ld de,1
sqrtloop:
inc a
dec e
dec de
add hl,de
jr c,sqrtloop
ret </nowiki>

==Speed Optimization==
This version is an unrolled version of a square root algorithm taking at most 555 t-states. The downside is that it takes 111 bytes, but if speed is a priority, this is probably the best option. Most of the unrolled iterations are specially optimised for their location in the algorithm.
<nowiki>;-------------------------------
;Square Root
;Inputs:
;HL = number to be square rooted
;Outputs:
;A = square root
;111 bytes
;555 t-states worst case
SqrtHL:
;zero some registers
xor a
ld c,a
ld d,a

;move the LSB of the input into E for later use, then shift the LSB into L and load H with 0.
;H will be a carry register, where the bits in L are rotated in
ld e,l
ld l,h
ld h,c

;Iteration 1 is optimised
; C is treated as the accumulator
add hl,hl
add hl,hl
sub h
jr nc,$+5
inc c
cpl
ld h,a

;Iteration 2
; rotate in 2 more bits from the MSB of the input into H
add hl,hl
add hl,hl
; shift the accumulator
rl c
ld a,c
rla
; A is now double the shifted accumulator
sub h
; doubles as a comparison of the carry register (H) to double the accumulator
jr nc,$+5
; If the carry is > 2*accumulator, the bit in the accumulator needs to be 1:
inc c
; We need to perform H-(2C+1), but A=2C-H.
; We could do NEG to get A=H-2C, then DEC A, but NEG = CPL \ INC A
; NEG \ DEC A = CPL \ INC A \ DEC A
; So just use CPL, saving 8 t-states, 1 byte
cpl
ld h,a

;Iteration 3
add hl,hl
add hl,hl
rl c
ld a,c
rla
sub h
jr nc,$+5
inc c
cpl
ld h,a

;Iteration 4
add hl,hl
add hl,hl
rl c
ld a,c
rla
sub h
jr nc,$+5
inc c
cpl
ld h,a

;L is 0, H is the current carry
;E is the lower 8 bits
; Load the next set of bits (LSB of input) into L so that they can be rotated into H
ld l,e

;Iteration 5
add hl,hl
add hl,hl
rl c
ld a,c
rla
sub h
jr nc,$+5
inc c
cpl
ld h,a

;Iteration 6
add hl,hl
add hl,hl
rl c
ld a,c
rla
sub h
jr nc,$+5
inc c
cpl
ld h,a

;Iteration 7
; Now we need to start worrying about 8 bit overflow.
; In particular, the carry register, H should be ideally 9 bits for this iteration, 10 for the last.
; The accumulator, C, is 8 bits, but we need to compare H to 2*C, and 2*C is up to 9 bits on the last iteration.
;l has 4 more bits to rotate into h

sla c \ ld a,c \ add a,a
add hl,hl
add hl,hl
jr nc,$+6
sub h \ jp $+6
sub h
jr nc,$+5
inc c
cpl
ld h,a

;Iteration 8
; A lot of fancy stuff here
; D is 0, from way back at the beginning
; now I put H->E so that DE can hold the potentially 10-bit number
; Now C->A, L->H
; H thus has the last two bits of the input that need to be rotated into DE
; L has the value of the accumualtor which needs to be multiplied by 4 for a comparison to DE
; So 2 shifts of HL into DE results in DE holding the carry, HL holding 4*accumulated result!
ld e,h
ld h,l
ld l,c
ld a,l
add hl,hl \ rl e \ rl d
add hl,hl \ rl e \ rl d
sbc hl,de
;the c flag now has the state of the last bit of the result, HL does not need to be restored.
rla
ret
</nowiki>

==Speed Optimization 2==
This 92 byte version is an optimized unrolled loop taking at most 379 t-states. Each iteration is optimized for its location in the algorithm.

<nowiki>
; fast 16 bit isqrt by John Metcalf
; 92 bytes, 344-379 cycles (average 362)
; v2 - saved 3 cycles with a tweak suggested by Russ McNulty

; call with hl = number to square root
; returns a = square root
; corrupts hl, de

; ----------

ld a,h ; 4
ld de,0B0C0h ; 10
add a,e ; 4
jr c,sq7 ; 12 / 7
ld a,h ; 4
ld d,0F0h ; 7
sq7:

; ----------

add a,d ; 4
jr nc,sq6 ; 12 / 7
res 5,d ; 8
db 254 ; 7
sq6:
sub d ; 4
sra d ; 8

; ----------

set 2,d ; 8
add a,d ; 4
jr nc,sq5 ; 12 / 7
res 3,d ; 8
db 254 ; 7
sq5:
sub d ; 4
sra d ; 8

; ----------

inc d ; 4
add a,d ; 4
jr nc,sq4 ; 12 / 7
res 1,d ; 8
db 254 ; 7
sq4:
sub d ; 4
sra d ; 8
ld h,a ; 4

; ----------

add hl,de ; 11
jr nc,sq3 ; 12 / 7
ld e,040h ; 7
db 210 ; 10
sq3:
sbc hl,de ; 15
sra d ; 8
ld a,e ; 4
rra ; 4

; ----------

or 010h ; 7
ld e,a ; 4
add hl,de ; 11
jr nc,sq2 ; 12 / 7
and 0DFh ; 7
db 218 ; 10
sq2:
sbc hl,de ; 15
sra d ; 8
rra ; 4

; ----------

or 04h ; 7
ld e,a ; 4
add hl,de ; 11
jr nc,sq1 ; 12 / 7
and 0F7h ; 7
db 218 ; 10
sq1:
sbc hl,de ; 15
sra d ; 8
rra ; 4

; ----------

inc a ; 4
ld e,a ; 4
add hl,de ; 11
jr nc,sq0 ; 12 / 7
and 0FDh ; 7
sq0:
sra d ; 8
rra ; 4
cpl ; 4
</nowiki>

==Balanced Optimization==
This version is a balance between speed and size. It also uses the high school method and runs under 1200 tstates. It only costs 41 bytes.
<nowiki>;-------------------------------
;Square Root
;Inputs:
;DE = number to be square rooted
;Outputs:
;A = square root

Sqrt:
ld hl,0
ld c,l
ld b,h
ld a,8
Sqrtloop:
sla e
rl d
adc hl,hl
sla e
rl d
adc hl,hl
scf ;Can be optimised
rl c ;with SL1 instruction
rl b
sbc hl,bc
jr nc,Sqrtaddbit
add hl,bc
dec c
Sqrtaddbit:
inc c
res 0,c
dec a
jr nz,Sqrtloop
ld a,c
rr b
rra
ret</nowiki>

== Presumably the best ==

This code was found on z80 bits and has the advantage of being both faster than all three versions above and smaller than the last two (it runs in under 720 T-states (under 640 if fully unrolled) and takes a mere 29 bytes). On the other hand it takes a somewhat unconventionnal input... It computes the square root of the 16bit number formed by la and places the result in d.
<nowiki>
sqrt_la:
ld de, 0040h ; 40h appends "01" to D
ld h, d

ld b, 7

; need to clear the carry beforehand
or a

_loop:
sbc hl, de
jr nc, $+3
add hl, de
ccf
rl d
rla
adc hl, hl
rla
adc hl, hl

djnz _loop

sbc hl, de ; optimised last iteration
ccf
rl d

ret
</nowiki>

==Other Options==
A binary search of a square table would yield much better best case scenarios and the worst case scenarios would be similar to the high school method. However this would also require 512 byte table making it significantly larger than the other routines. Of course the table could also serve as a rapid squaring method.

== Credits and Contributions ==
* '''James Montelongo'''
* '''Milos "baze" Bazelides''' (or possibly one of the contributor of [http://baze.au.com/misc/z80bits.html z80bits])
* '''John Metcalf''' (Speed Optimization 2 from [https://github.com/impomatic/z80snippets/blob/master/fastisqr.asm z80snippets])