;FindPixel
;* Snake86    97-199 cycles    25 bytes  (d,e) to hl:a  destroyes: b
;* CLEM          131 cycles    28 bytes  (b,c) to hl:a  destroyes: -
;  CLEM          127 cycles    35 bytes  (b,c) to hl:a  destroyes: bc
;* Eble-Yopp...  122 cycles 34-41 bytes  (e,d) to hl:a  destroyes: c
;  ZAPO          105 cycle     40 bytes  (c,b) to hl:a  destroyes: de
;Line
;* ROM call    time: 115/37     0 bytes  (b,c)-(d,e)    destroyes: h
;  Jantzen     time:  51/16   109 bytes  (e,d)-(l,h)    destroyes: abc  fp: (b,c)
;* FastLine    time:  14/4    145 bytes  (d,e)-(h,l)    destroyes: a    fp: (e,d)

;------------------------------------------------------
;  Snake86-FindPixel
;  by David Phillips/Jonah Cohen/Ben Mickle
;
;   97-199 cycles  25 bytes    (d,e) to hl:a  destroyes: b
;  104-206 cycles  27 bytes    (d,e) to hl:a  destroyes: bc(=16)
;------------------------------------------------------

FindPixel:
	ld h,$fc00/1024
	ld a,e
	add a,a
	add a,a
	ld l,a    ;hl=$3f00+4*y
	ld a,d
	rra
	add hl,hl
	rra
	add hl,hl ;hl=$fc00+16*y
	rra       ;a=x/8
	or l
	ld l,a
	ld a,d
	and 7
	inc a
	ld b,a
	ld a,1
PixelLoop:
	rrca
	djnz PixelLoop
;	ld c,16   ;bc=$10
	ret

;------------------------------------------------------
;  CLEM's FIND_PIXEL
;  by Clem
;
;  131 cycles  28 bytes    (b,c) to hl:a  destroyes: none
;------------------------------------------------------

FindPixel:
	ld h,63
	ld a,c
	add a,a
	add a,a
	ld l,a    ;hl=$3f00+4*y
	ld a,b
	rra
	add hl,hl
	rra
	add hl,hl ;hl=$fc00+16*y
	rra       ;a=x/8
	or l
	ld l,a
	ld a,b
	and 7
	cpl
	rlca
	rlca
	rlca
	ld (FP_Bit),a
	xor a
FP_Bit =$+1
	set 0,a
	ret

;------------------------------------------------------
;  CLEM's FINDPIXEL
;  by Clem
;
;  127 cycles  35 bytes    (b,c) to hl:a  destroyes: bc
;------------------------------------------------------

FindPixel:
	ld h,63
	ld a,c
	add a,a
	add a,a
	ld l,a    ;hl=$3f00+4*y
	ld a,b
	rra
	add hl,hl
	rra
	add hl,hl ;hl=$fc00+16*y
	rra       ;a=x/8
	or l
	ld l,a
	ld a,b
	and 7
	ld bc,FP_Bits
	add a,c
	ld c,a
	adc a,b
	sub c
	ld b,a
	ld a,(bc)
	ret
FP_Bits:
	.db $80,$40,$20,$10,$08,$04,$02,$01

;---------------------------------------------------------------------
;  Eble-Yopp-Yopp-Eble-Eble-Eble-Yopp-Eble Faster FindPixel Routine
;
;  122 cycles  34-41 bytes (e,d) to hl:a  destroyes: c
;  118 cycles  33-40 bytes (e,d) to hl:c  destroyes: a
;---------------------------------------------------------------------

FindPixel:
	ld hl,FP_Bits
	ld a,e
	and $07         ;bit offset
	or l            ;add bit offset to HL
	ld l,a
	ld c,(hl)       ;c=bitmask
	ld h,$3F
	ld a,d
	add a,a
	add a,a
	ld l,a          ;l=y*4
	ld a,e
	rra
	add hl,hl
	rra
	add hl,hl       ;hl=$fc00+y*16
	rra             ;a=x/8
	or l            ;add x
	ld l,a          ;video-byte
	ld a,c          ;bitmask (can be removed)
	ret

	.org (($+8) & 0FFF8h)   ; align FP_Bits on the next 8-byte boundary
FP_Bits:
	.db $80,$40,$20,$10,$08,$04,$02,$01

;---------------------------------------------------------------------
;  The ZAPO even faster findpixel
;  by ~Code7~
;
;  105 cycles  40 bytes    (c,b) to hl:a  destroyes: de
;  101 cycles  39 bytes    (c,a) to hl:a  destroyes: de
;---------------------------------------------------------------------

FindPixel:
	ld a,b
FindPixelShort:
	ld h,$3f
	add a,a
	add a,a
	ld l,a     ;hl=$3f00+4*y
	ld a,c
	rra
	add hl,hl
	rra
	add hl,hl  ;hl=$fc00+16*y
	rra        ;8*x
	add a,l
	ld l,a
	ld d,$87
	ld a,c
	and d      ;=7
	ld e,a
	ld a,(de)
	ret

;  the offset table program must be placed at $8700
;  51 cycles  11 bytes    destroyes: bcdehl

InitializeFP:
	ld de,$8700
	ld hl,Offset
	ld bc,8
	ldir
Offset:
	.db $80,$40,$20,$10,$8,$4,$2,$1

;---------------------------------------------------------------------
;  _DARKLINE (ROM-call $4e4d)
;  by Texas Instruments
;
;  time: 11.5 \ 3.7  0 bytes (b,c)-(d,e)  destroyes: h
;---------------------------------------------------------------------

;call _DARKLINE

;---------------------------------------------------------------------
;  Optimized Implementation of Bresenham's line algorithm (31.I.96)
;  by Stephane Jantzen (Stephane.Jantzen@scinfo.u-nancy.fr)
;
;  time: 5.1 \ 1.6  109 bytes (e,d)-(l,h)  destroyes: abc
;  uses (b,c) findpixel ; weird lines with x>64
;---------------------------------------------------------------------

Line:
	push de
	push hl

	ld  a,d
	sub h
	jr  nc,DXPositive    ;delta_x > 0
DXNegative:
	neg
DXPositive:
	ld  b,a              ;B <- |delta_x|
	ld  a,e
	sub l
	jr  nc,DYPositive    ;delta_y > 0
DYNegative:
	neg
DYPositive:                
	sub b               ;|delta_y|
	push af
	jr  c,DeltaX        ;|delta_x| > |delta_y|
DeltaY:
	ld  a,h             ;if |delta_x| < |delta_y| then
	ld  h,l             ;then values x and y are swapped
	ld  l,a             ;so the loop will always be performed on the
	ld  a,d             ;x value. A flag must be set to 
	ld  d,e             ;remind that data must be drawn (y,x) 
	ld  e,a             ;instead of (x,y)

DeltaX:
	ld  a,d
	sub h
	jr  nc,TestDY        ;x1 < x2 
TestDX:
	ex  de,hl
TestDY:
	ld  a,e
	sub l
	ld  a,$01
	jr  nc,StoreA
	neg                     ;y1 > y2 : in case2 the 'y' variable
StoreA:
	ld  (Way),a
InitLine:       
	ld  b,h
	ld  c,l
	ld  a,e
	sub l
	jr  nc,EndInit
	ld  a,l
	ld  l,e
	ld  e,a
EndInit:
	ld  a,e      
	sub l
	rla
	ld  l,a             ;value to add in case1 (d < 0)
	add a,h
	sub d
	ld  e,a             ;'d' variable is initialised
	add a,h
	sub d
	ld  h,a             ;value to add in case2 (d >= 0)
Loop:
	ld  a,b
	sub d
	jr  nc,EndLine       ;the line is completely drawn.
	pop af
	bit 7,a
	push af
	push af
	push bc
	jr  z,DrawPoint
	ld  a,b
	ld  b,c
	ld  c,a
DrawPoint:     
	push de
	push hl
	call FindPixel
	or  (hl)
	ld  (hl),a
	pop hl
	pop de
	pop bc
	pop af
TestD:
	bit 7,e
	jr  nz,Case1
Case2:                          ;d >= 0 
	ld  a,e
	add a,h
	ld  e,a
	ld  a,0
Way =$-1
	add a,c
	ld  c,a
	jr  EndLoop
Case1:                          ;d < 0
	ld  a,e
	add a,l
	ld  e,a
EndLoop:
	inc b
	jr  Loop
EndLine:
	pop af
	pop hl
	pop de
	ret

;---------------------------------------------------------------------
;  FastLine 1.0 (Bresenham's line algorithm)
;  by Jimmy MÕrdell <yarin@acc.umu.se>
;
;  time: 1.4 \ 0.4  145 bytes (d,e)-(h,l)  destroyes: a
;  uses (e,d) findpixel
;---------------------------------------------------------------------

FLine:
 push bc		;1
 push de		;2
 push hl		;3
 ld a,h
 cp d
 jr nc,DXpos
 ex de,hl
DXpos:
 ld b,d
 ld c,e
 push hl		;4
 call eyopFindPixel
 ex (sp),hl		;4
 ld e,c
 ld c,a
 ld a,h
 sub b
 ld b,a
 ld a,l
 sub e
 ld de,16
 jr nc,DYpos
 neg
 ld de,-16
DYpos:
 push af		;5
 sub b
 jr nc,DY_Greater
 add a,a
 neg
 ld (x_ai+1),a
 pop af			;4
 add a,a
 ld (XDNeg+1),a
 sub b
 pop hl			;3
 push af		;4
 ld a,c
 or (hl)
 ld (hl),a
 pop af			;3
 bit 7,a
 jr nz,XDNeg
XNewRow:
 add hl,de
x_ai:
 sub 0
 push af		;4
 rrc c
 jr nc,XNoWrap1
 inc hl
XNoWrap1:
 ld a,c
 or (hl)
 ld (hl),a
 pop af			;3
 dec b
 jr z,LineDone
 jr nc,XNewRow
XDNeg:
 add a,0
 push af		;4
 rrc c
 jr nc,XNoWrap2
 inc hl
XNoWrap2:
 ld a,c
 or (hl)
 ld (hl),a
 pop af 		;3
 dec b
 jr z,LineDone
 jr c,XNewRow
 jr XDNeg

DY_Greater:		;5
 neg
 add a,a
 ld (YNoWrap+1),a
 ld a,b
 add a,a
 ld (YDNeg+1),a
 pop hl			;4
 sub h
 ld b,h
 pop hl			;3
 push af		;4
 ld a,c
 or (hl)
 ld (hl),a
 pop af			;3
YRepeat:
 bit 7,a
 jr nz,YDNeg
 rrc c
 jr nc,YNoWrap
 inc hl
YNoWrap:
 add a,0
 jr YPlot
YDNeg:
 add a,0
YPlot:
 add hl,de
 push af		;4
 ld a,c
 or (hl)
 ld (hl),a
 pop af			;3
 djnz YRepeat
LineDone:
 pop hl			;2
 pop de			;1
 pop bc			;0k
 ret

;---------------------------------------------------------------------
;  Peaworm line
;  by Matthew Shepcar
;
;  time: ? \ ?  118 bytes (d,e)-(h,l)  destroyes: abc
;  uses (?,?) findpixel
;---------------------------------------------------------------------

Line: ;draw line from de to hl (d<h)
  push hl
  push de
  ld a,d
;  cp h
;  jr c,lineOrdered
;  ex de,hl
lineOrdered:  
  ld  b,d
  ld  c,e
  push hl
  push bc
  call FindPixel
  pop bc
  pop de
connectedLine:
  push hl
  ld  h,c
  ld  c,a
  ld  a,d
  sub b
  ld  b,a
  ld  a,e
  jr  nz,LineNotPoint
  cp  h
  jr  nz,LineNotPoint
  pop hl
  jr  DoneLine
LineNotPoint:
  sub h
  ld  de,16
  jr  nc,LinePositiveY
  neg
  ld  de,-16
LinePositiveY:  
  cp  b
  jr  nc,SteepLine
  add a,a
  ld  (line2sm+1),a
  ld  h,a
  xor a
  sub b
  add a,a
  ld  (line1sm+1),a
  ld  a,h
  sub b
  pop hl
LineLoopGentle: 
  push af
  ld  a,(hl)
  or  c
  ld  (hl),a
  rrc c
  jr  nc,$+3
  inc hl
  pop af       
  jp  m,line2sm
line1sm:
  add a,0
  add hl,de
line2sm:
  add a,0
  djnz LineLoopGentle
DoneLine:
  ld  a,(hl)
  or  c
  ld  (hl),a
  pop de
  pop hl
  ret
SteepLine:
  ld  h,a
  neg
  add a,a
  ld  (line3sm+1),a
  ld  a,b
  add a,a
  ld  (line4sm+1),a
  sub h
  ld  b,h
  pop hl
LineLoopSteep: 
  push af
  ld  a,(hl)
  or  c
  ld  (hl),a
  add hl,de
  pop af
  jp  m,line4sm
line3sm:
  add a,0
  rrc c
  jr  nc,$+3
  inc hl
line4sm:
  add a,0
  djnz LineLoopSteep
  jr  DoneLine