I'm curently working on an AY-3-8912 audio player, and for the case of convenience I'm adding things like software envelopes and frequency sweeps.
Initially I thought about using something like remainding difference/remainding time to calculate a new value for each time iteration, but then I quickly figured integer math doesn't round very well in such a situation. After some investigation, I decided it was best to make a variation of the Bresenham algorithm.
The integer implementation of the Bresenham algorithm's weak point is that it cannot compute lines ouside one octant of a coordinate system. My use of it needed only to compute a new value of y per x++, so there was some simplifications that got me around this problem.
Since x is always increasing, I didn't need to care about the 4 octants on the -x side, or the function going in the -x direction. dy, on the other hand, can be negative. This was solved by biasing the accepted error around -1/2 < D < 1/2 instead of just D < 0. To include the remaining two octants, I added an integer factor to be added every iteration. This works since I'm only interested in the max value per value of x (ie; I'm not actually drawing a line on a display).
I'm sharing this code because it's very convenient in any case you need a linear function plot on a Z80. I'm sure this can be optimized a lot, but it's at least working properly now!
Here is the code to initiate the datastructure:
Code:
Here is the point iteration code:
Code:
Initially I thought about using something like remainding difference/remainding time to calculate a new value for each time iteration, but then I quickly figured integer math doesn't round very well in such a situation. After some investigation, I decided it was best to make a variation of the Bresenham algorithm.
The integer implementation of the Bresenham algorithm's weak point is that it cannot compute lines ouside one octant of a coordinate system. My use of it needed only to compute a new value of y per x++, so there was some simplifications that got me around this problem.
Since x is always increasing, I didn't need to care about the 4 octants on the -x side, or the function going in the -x direction. dy, on the other hand, can be negative. This was solved by biasing the accepted error around -1/2 < D < 1/2 instead of just D < 0. To include the remaining two octants, I added an integer factor to be added every iteration. This works since I'm only interested in the max value per value of x (ie; I'm not actually drawing a line on a display).
I'm sharing this code because it's very convenient in any case you need a linear function plot on a Z80. I'm sure this can be optimized a lot, but it's at least working properly now!
Here is the code to initiate the datastructure:
Code:
;
; Sets up a datastructure in preparation for the slope algorithm.
;
; HL points to the datastructure
; A contains unsigned x length
; DE contains signed y destination
;
; HL is saved
;
preparegradient:
push hl
ld c,(hl)
inc hl
ld b,(hl) ; get y in bc
inc hl ; point to x
ld (hl),a ; x = x
inc hl ; point to dy
push hl ; save pointer to dy
inc hl
inc hl ; point to dx
ld (hl),a ; dx = x
inc hl
ld (hl),$00 ; Store dx
inc hl ; point to D
ld (hl),$00 ; D = 0
inc hl
ld (hl),$00
ex de,hl ; hl = y dest
or a
sbc hl,bc ; dy = y dest - y current
call div ; hl = dy/dx, a=dy%dx
ex de,hl ; de = dy/dx
inc hl ; point to d
ld (hl),e ; d = dy/dx
inc hl
ld (hl),d ; Store d
pop hl ; restore pointer to dy
ld (hl),a ; dy = dy%dx
inc hl
ld (hl),$00 ; Store dy
bit 7,a
jr z,preppos
ld (hl),$FF ; Store dy
preppos:
pop hl
ret
;
; Divide HL by A
;
; output:
; HL = HL/A
; A = HL%A
;
; call div : HL signed
; call usdiv : unsigned division
;
div:
bit 7,h
jr nz,HLneg
usdiv:
push bc ; HL is positive
ld c,a
xor a
ld b,$11
divnext:
dec b
jr z,divdone
divloop:
add hl,hl
rla
cp c
jr c,divnext
sub c
inc l
djnz divloop
divdone:
pop bc
ret
HLneg:
call flipsignHL ; HL is negative
call usdiv
neg
jp flipsignHL
;
; HL = -HL
;
flipsignHL:
push de
ex de,hl
ld hl,$0000
or a
sbc hl,de
pop de
ret
Here is the point iteration code:
Code:
;
; Calculate points of a linear function, maintaining an even gradient.
;
; HL must be pointing to a datastructure:
;
; hl+0 = y - (Word) Current value of function
; hl+2 = x - (Byte) Current remaining points of the function
; hl+3 = dy - (Word) y ratio of gradient
; hl+5 = dx - (Word) x ratio of gradient
; hl+7 = D - (Word) Current Delta Error
; hl+9 = a - (Word) Whole-number part of gradient
;
; The gradient of the function is defined by a + dy/dx, where dy < dx
;
; To initiate a function, set the appropriate values for x, y, a, dx, dy,
; and then set D = 0. x is decremented by 1 for every point calculated,
; and no more points will be calculated after x reaches zero. If more
; points are needed, just put a new value into x.
;
; a should have the same sign as dy!
;
; The algorithm used is a variation of the Bresenham Line algorithm:
;
; Expected initial conditions:
; dx = x1 - x0 (= x)
; dy = y1 - y0
; a = dy / dx (integer-division)
; dy = dy % dx
; D = 0
;
;
; Algorithm for next point:
;
; y = y + a
; D = D + dy*2
; if D >= dx
; y = y+1
; D = D - dx*2
; else if D <= -dx
; y = y-1
; D = D + dx*2
;
; This algorithm adds no offset of the point-center, and thus assumes atomic-
; sized points. Using this to draw a line of pixels might therefore result
; in a slight offset in case the coordinate of a pixel can be judged from its
; corner. To fix this, the initial value of D must be calculated from the
; centre of the first pixel.
;
; Registers are saved.
;
advancegradient:
push bc
push de
push hl
push af
ld e,(hl)
inc hl
ld d,(hl) ; get y in de
inc hl ; point to x
ld a,(hl) ; get x in a
or a
jp z,grnochange ; Skip if x is 0
dec (hl) ; else continue by counting down x
inc hl ; point to dy
push de ; save original y for reference
push hl ; save pointer to dy
ld bc,$0007
add hl,bc ; point to upper a
ld b,(hl)
dec hl
ld c,(hl) ; get a in bc
ex de,hl ; hl = y
add hl,bc ; y = y + a
ex de,hl ; de = y
dec hl ; point to D
ld b,(hl)
dec hl
ld c,(hl) ; get D in bc
pop hl ; restore pointer to dy
push de ; save y
ld e,(hl)
inc hl
ld d,(hl) ; get dy in de
or a
rl e
rl d ; dy = dy*2
inc hl ; point to dx
push hl ; save pointer to dx
ld h,b
ld l,c ; hl = D
add hl,de ; D = D + dy
ld de,$8000
add hl,de ; adjust D for signed comparison
ex de,hl ; de = D (adj)
pop hl ; restore pointer to dx
ld c,(hl)
inc hl
ld b,(hl) ; get dx in bc
inc hl ; point to D
push hl ; save pointer to D
push bc ; save dx
push de ; save D (adj)
ld h,b
ld l,c ; hl = dx
ld bc,$8000
add hl,bc ; adjust dx for signed comparison
ex de,hl ; hl = D (adj), de = dx (adj)
or a
sbc hl,de ; if D >= dx
pop de ; restore D (adj)
pop bc ; restore dx
jr nc,gradd ; then go add one to y
ld hl,$0000
or a
sbc hl,bc ; hl = -dx
push hl ; save -dx
ld bc,$8000
add hl,bc ; adjust -dx for signed comparison
or a
sbc hl,de ; if D <= -dx
pop bc ; restore -dx
jr nc,grsub ; then go subtract one from y
ex de,hl
ld de,$8000
or a
sbc hl,de
ex de,hl ; undo D signed comparison ajustement
pop hl ; restore pointer to D
pop bc ; restore y
grdone:
ld (hl),e ; Store D
inc hl
ld (hl),d
pop hl ; get original y
or a
sbc hl,bc ; Any changes?
jp z,grnochange ; dont update y then
pop af
pop hl
ld (hl),c ; Store y
inc hl
ld (hl),b
dec hl
pop de
pop bc
or a
ret
grnochange:
pop af
pop hl
pop de
pop bc
or a
ccf
ret
gradd: ; Add one to y:
or a
sbc hl,bc
ex de,hl ; D = D - 2*dx
pop hl ; restore pointer to D
pop bc ; restore y
inc bc ; y = y+1
jp grdone
grsub: ; Subtract one from y:
add hl,bc ; hl = -dx - D +(-dx)
call flipsignHL ; hl = -(-2*dx - D)
ex de,hl ; D = D + 2*dx
pop hl ; restore pointer to D
pop bc ; restore y
dec bc ; y = y-1
jp grdone