// Note that this may not quite be legal Java code (I didn't run this)! Don't complain if it doesn't execute as is.
// My purpose here was to document and explain an algorithm.
// For working code, refer to the bigger file posted previously.

// The Digital Discrete Analyzer (DDA) is an operator that takes two endpoints, and produces a stream of intermediate values that linearly interpolate the endpoints.
// The DDA is really just an iterator that linearly interpolates a bunch of values at the same time.
// Do not think of the DDA as something specific to the triangle drawing algorithm (although the triangle engine will USE a few DDA blocks to draw shapes).
// One value (in this case "t") is used as the "master" or "guide": the DDA will produce 1 set of interpolated values per step of the master value.
// Any number of "interpolated" or "slave" variables (only 1 in this case, "x0") can be computed by the DDA. For this simplified example, we will only consider 1 such variable.
public class DDA{
	// Start point and end point
	public DDAState start, end;
	
	// Current DDA state
	public DDAState cur;
	
	// Difference (end - start for each variable)
	public int dt,	dx0;
	
	// Sign	(are we going in the positive or the negative direction?)
	public int st,	sx0;
	
	// Error: just like in the Bresenham line engine, error accumulation is central to the algorithm.
	// We accumulate error (increase) of all interpolated when we increase the master variable.
	// When the error gets to be too large, we compensate by adjusting the interpolated variables.
	// We don't need to store the error for the master variable - it is always 0.
	public int 		ex0;
	
	// Constructor
	public DDA(DDAState start, DDAState stop){
		// set the boundary conditions
		this.start	= start;
		this.end	= stop;
		
		// set the starting condition (copy the start state
		this.cur	= new DDAState(this.start);
		
		// Calculate the distances for all variables
		// Cannot make assumptions about the relative ordering of start and end points (they are not sorted).
		// Take the absolute value because distances are always positive!
		dt		= Math.abs(end.t - start.t);
		dx0		= Math.abs(end.x0 - start.x0);
		
		// Compute the sign (direction of change) for all variables
		st		= (start.t < end.t)?	1 : -1;	// sign is 1 if end > start. -1 otherwise
		sx0		= (start.x0 < end.x0)?	1 : -1; // the variable will only change in the direction specified by the sign.
		
		// Initialize the error to 1/2 of the master distance
		// If you want to know why, think about the math behind this algorithm.
		ex0 = dt / 2;
	}
	
	// The DDA is essentially an iterator (will return a sequence of points connecting start to end)
	// Each successive point is produced using this function.
	// This function is heavily annotated, and does not actually compile. Pay attention to the structure, not the sequence!
	public DDAState step(){
		// If we have not yet finished interpolating (have not reached the goal state)
		if(cur.y != end.y){	
			// Adjust all interpolated components per y coordinate. Note: this may take more than 1 cycle!
			while(ex0 < 0){		// While at least 1 interpolated variable is not within its error bound
				// IN PARALLEL: Adjust the interpolated variable(s) that are outside of the error bound, like this:
				cur.x0	= cur.x0 + sx0;	// Increment (or decrement) the SLAVE variable
				ex0		= ex0+dt;		// Reduce error. Note: DT is ADDED, and we want to keep the errror ABOVE zero!			
			}
			
			// Now, each interpolated variable is within an acceptable error bound.
			// Advance the master variable, and accumulate error.
			cur.t		= cur.t + st;	// Increment (or decrement) the MASTER variable
			ex0			= ex0-dx0;		// Accumulate error. Note: DX0 is SUBTRACTED, and we want to keep the errror ABOVE zero!
			
			// Now we are ready to yield the new point.
			// Signal valid, and start working on the next point.
			return cur;
		} else {			
			// We have interpolated from start to end. There are no more points to return!
			// Now we take Valid low on the output, and raise Ready on the inputs.
			return null;
		}
	}
}

/*
A good way to organize the DDA is to treat it as a stream operator:


The DDA will take in 2 Ready-Valid (FIFO-like Ready-Valid-Data interface) streams as input, and produce 1 Ready-Valid stream as output.
For each PAIR of inputs, the DDA will produce 2 or more values interpolating between the inputs.

NOTE : this interface is a SUGGESTION! You may need to add things, or be able to optimize something away.

module DDA(		
		Clock,
		Reset,
		
		InAReady,
		InAValid,
		InA,
		
		InBReady,
		InBValid,
		InB,
		
		OutReady,
		OutValid,
		Out
	);
	
	parameter	DDAWidth = 10;	// Bitwidth of a single variable. We will have quite a few differently sized variables.
	parameter	DDASlaves = 4;	// Number of variables to interpolate against 1 master variable;
	
	localparam	Width = DDAWidth*DDASlaves;
	
	input				Clock;
	input				Reset;
		
	output				InAReady;
	input				InAValid;
	input	[Width-1:0]	InA;
		
	output				InBReady;
	input				InBValid;
	input	[Width-1:0]	InB;
		
	input				OutReady;
	output				OutValid;
	output	[Width-1:0]	Out;
		
	// TODO: Your stuff goes here.
		
endmodule

Plan to get this thing WORKING before you get it OPTIMIZED. Good luck.

*/

// This is just a helper class to organize state.
// If this were C, I would have used a struct here.
public class DDAState{
	// The state
	public int t, x0;  // Interpolate x0 (and x1, x2, ...) against t.
	
	// Constructors:
	//	new DDA constructor
	public DDAState(int t, int x0){
		this.t		= t;
		this.x0		= x0;
	}
	
	//	copy constructor
	public DDAState(DDAState src){
		t	= src.t;
		x0	= src.x0;
	}
}