chapter3.htm

嵌入式软件开发.rar

it is probably best if an alternate search method be used to find the table index rather than 
the straight linear search seen above.  What are our choices?  One choice stands out as 
good.  This choice is the binary search.
<p>	All searches require compares.  The important question  that should be addressed 
is the average number of compares needed to determine the needed index into the table.  
The linear search will require,on average, a number of compares that is equal to one-half 
the length of the table if the input data are distributed uniformly over the input range.  A 
binary search is a search that determines the location of the index by successively reducing 
the search space in half after each comparison.  This approach leads to a number of 
searches that is proportional to the  logarithm, based 2, of the length of the table.  If the 
table has only 4 entries, the linear search will require an average of 2 comparisons and the 
binary search will also require a maximum of 2 comaprisons.  On the other hand, at 8 
entries, the linear search requires an average of 4 comparisons, and the binary search 
needs a maximum of only 3 comparisons.  Above 8, the advantage of the binary search 
becomes much greater.
<p>	A binary seach is implemented as follows:  The input data are assumed to be an 
array with its contents in order.  The array is divided in half, and the data value is 
compared with the contents of the center of the  array.  If the data value is greater than the 
value found in the center, the lower half of the array is discarded, and the search is 
restarted with the newly shortened array.  Similarly, the larger half of the array is 
discarded if the data value happens to be less than the value of the center entry in the 
array.  This routine is repeated until one of two things happen.  First, the comparison test 
is to determine if the value is either greater or less than the center entry in the array.  If it 
is neither, the value must equal the center value, and the search is completed with this 
value being returned to the calling program.  Secondly, the search will continue until the 
value lies between two entries in the array.  In this case, the lower index value is returned 
to the calling  program.  The implementation of this algorithm is shown  below. 
<pre><code>
	int table_search(Look_up *this,BYTE value)
	{
	    int top, bottom, middle;

	    top=this-&gtlength - 1;
	    bottom=0;
	    while((top-bottom)&gt1)
	    {
	        middle=(top+bottom)/2;
	        if(value&gtthis-&gttable[middle].x)
	            bottom=middle;
	        else if(value&ltthis-&gttable[middle].x)
	            top=middle;
	        else
	            return middle;
	    }
	    return  bottom;
	}
</pre></code><p>
	The three variables used in this function are top, bottom and middle.  The top of 
the array being tested is at top, the bottom is at bottom, and middle is the center between 
top and bottom.  The value of top is started at one less than the length of the array and 
bottom is at zero.  The while loop in which all of the calculation is completed is exercised 
as long as top and bottom are separated by more than one.  When top is one greater than 
bottom, value has been bracketed by the adjacent table entries corresponding to top and 
bottom.  At this time, bottom is returned to the calling program.  Otherwise, value is 
compared with the central entry in the array.  If it is larger than the center value, bottom is 
changed to the value of middle and the procedure is continued.  Whenever value is less 
than the central array entry, top is given the value of middle.  In the  event that value is 
neither larger nor smaller than the value found at middle, it must equal the value at middle, 
and this index value is returned. 
<p>	There is a subtle difference between this binary search and the one you usually see 
in textbooks. In those cases, the mid point is excluded when the new values of top or  
bottom are calculated.  The following lines of code show this difference. 
<pre><code>
        if(value&gtthis-&gttable[middle].x)
            bottom=middle+1;
        else if(value&ltthis-&gttable[middle].x)
            top=middle-1;
</pre></code>
Here, bottom is given a value middle + 1 and top is given a value middle - 1 then the 
appropriate conditions are met.  This approach assumes that the array data itself is the 
desired result, not an interpolated value between two points in the array.  When the above 
code is used with the table look-up, the range nearest the center point, middle, is excluded 
from the next test, and the program misses the correct result most of the time.  
<p>	We can now see one of the big advantages of object oriented programming.  The 
above modifications to the program will be included in the header file and the 
implementation file for the look-up table objects.  The header file needs to have a function 
prototype for the routine table_search().  The new header file is
	<pre><code>
		#ifndef LUTOBJ_H
		#define LUTOBJ_H

		#include "defines.h"

		/* table used below is a pointer  to an array of the type Entry.
		   The number of entries in the array must be equal to x_length.
		   Of course, each entry contains two values which are of the 
		   type BYTE   */

		#ifndef ENTRYF
		#define ENTRYF
		    typedef struct
		    {
		        BYTE x,y;
		    }Entry;
		#endif

		#define LOOK_UP_CLASS \
				int length; \
				Entry *table; \

		typedef struct LU
		{
			LOOK_UP_CLASS
		} Look_up;

		Look_up *look_up_(int x_length, Entry *table);
		void look_up__(Look_up * this);
		BYTE get_value(struct LU *this, BYTE value);
		BYTE interpolate(BYTE value,BYTE x0,BYTE y0,BYTE x1,BYTE y1);
		int table_search(Look_up *,BYTE);
		#endif 
</pre></code>
The next to last line in the  above code is added for this part of the program.  In the 
implementation file, the routine get_value() is modified so that the table_search()  function 
is called rather than to execute the linear search above.  Also, the code for the 
table_search() function is added to the implementation file. This function is made static so 
that there is no visibility to the routine outside of the implementation file. 
<pre><code>
	#include "lutobjnu.h"
	#include &ltstdlib.h&gt

	BYTE get_value(Look_up *this, BYTE value)
	{
	    int i;

	    i=table_search( this,value);
	    if(value==this-&gttable[i].x)
	        return this-&gttable[i].y;
	    else
	        return interpolate(value,
	                           this-&gttable[i].x,
	                           this-&gttable[i].y,
	                           this-&gttable[i+1].x,
	                           this-&gttable[i+1].y);
	}

	/* the constructor's name ends with a single underscore _ */

	Look_up *look_up_(int length, Entry *table)
	{
	    Look_up *this;

	    if(!(this=(Look_up*)malloc(sizeof(Look_up))))
	        error_handler();
	    this-&gtlength=length;
	    this-&gttable=table;
	    return this;
	}

	/* the destructor's name ends with a double underscore __ */

	void look_up__(Look_up *this)
	{
	    free(this);
	}

	/* interpolate() function can be used by other look-up tables, 
	   such as the a three dimensional look-up.  This function works only
	   for unsigned numbers, both inputs and outputs. It is assumed that
	   x progresses monotonically, but y need not. */

	BYTE interpolate(BYTE value,BYTE x0,BYTE y0,BYTE x1,BYTE y1)
	{
	    WORD v=(WORD)value,xx0=(WORD)x0,yy0=(WORD)y0,xx1=(WORD)x1,
	          yy1=(WORD)y1;

	    if(yy1 &gt yy0)
	        return yy0+(v-xx0)*(yy1-yy0)/(xx1-xx0);
	    else
	        return yy0-(v-xx0)*(yy0-yy1)/(xx1-xx0);
	 
	}

	static int table_search(Look_up *this,BYTE value)
	{
	    int top, bottom, middle;

	    top=this-&gtlength - 1;
	    bottom=0;
		    while((top-bottom)&gt1)
	    {
	        middle=(top+bottom)/2;
	        if(value&gtthis-&gttable[middle].x)
	            bottom=middle;
	        else if(value&ltthis-&gttable[middle].x)
	            top=middle;
	        else
	            return middle;
	    }
	    return  bottom;
	}
 </pre></code>
	The names of these files were changed from lutobj2d.x to lutobjnu.x to keep them 
separate from earlier files.  The test program used above can be used to test this version of 
the table look-up object.  The only change in the test program is to change the lutobj2d.h 
to lutobjnu.h.  Otherwise the program is identical.  We have made significant changes in 
the class code, but it is unnecessary to alter the program code at all to be able to realize 
these changes.    

<h4><a name="a_different_interpolate">A different  interpolate()</a></h4>

<p>	Every time  that interpolate() is called, the code must execute a multiply, a divide, 
and four adds.  It is possible to eliminate the divide operation and several of the adds in 
the interpolation.  This form of interpolate() will be somewhat faster than the earlier 
version.  Its use will, however, force a reevaluation of the whole approach to the look-up 
table.  We will examine this approach here.  
<p>The function interpolate() from the above class definition is shown here.  In both 

<pre><code>
	BYTE interpolate(BYTE value,BYTE x0,BYTE y0,BYTE x1,BYTE y1)
	{
	    WORD v=(WORD)value,xx0=(WORD)x0,yy0=(WORD)y0,
			 xx1=(WORD)x1,yy1=(WORD)y1;

	    if(yy1 &gt yy0)
	        return yy0+(v-xx0)*(yy1-yy0)/(xx1-xx0);
	    else
	        return yy0-(v-xx0)*(yy0-yy1)/(xx1-xx0);
	 
	}
</pre></code>
calculations, you will  notice that the  portion of the expression
<pre><code>
	(yy1-yy0)/(xx1-xx0)
</pre></code>
or
<pre><code>
	(yy0-yy1)/(xx1-xx0)
</pre></code>
are values that depend on the table values at the break points only and remain unchanged 
between the breakpoints.  Therefore, this calculation could be completed and included in 
the table data.  These values are the slope of the  line that join two adjacent points in the 
table.  Another advantage to the use of the slopes is that we can use negative values for 
slopes and avoid the dual calculation above to account for either a poistive or a negative 
slope with unsigned values.  It is proposed that  the value of slope is calculated and 
included  in the look-up table.  Then the  interpolation will require the multiplication  of 
the partial distance between the points by the slope and then add the result to the y value 
at the point in the table.  
<p>	We now have a problem.  It is necessary to have some kind of fractional 
representation for slopes.  It is impossible to consider rounding all slopes  less than unity 
to zero because this range of slopes is too significant to discard.  A means must be found 
to include fractional data in our table.  We will create for this particular program a fixed 
point fractional arithmetic system that will resolve all of our  problems here. A new class 
of data along with all of the methods needed to execute complete arithmetic on these data 
types could be created.  In this case, though, we need only create some slopes and then 
accurately multiply these values by an unsigned char value.  This set of operations can be 
executed easily without resorting to the implementation of a full class and the appropriate 
objects.  A fixed point arithmetic scheme will be used.  The basic numeric system in this 
case is a sixteen bit number that from a programming  standpoint is merely an int--if an int 
is a sixteen bit number on your machine.  A binary point will be placed between the  two 
eight bit portions of this number.  The most significant byte of the number will be a 
standard integer type number that has a range of -128 to +127.  The least significant byte 
will be the fractional part of the number.  If we start at the left, the first bit is the number 
of halfs in the fraction, the second bit is the number of quarters in the fraction, and so forth 
until we reach the eighth bit which is the number of 256ths in the fractional portion of the 
number.  This fractional portion of the number can represent any fractional value from 
zero to 0.99609375 in steps of  0.00390625.  This range of fractional values will be 
satisfactory for calculation of the  slopes between points in the table.  These numbers are 
generated by merely multiplying the numerator by 256--0x100--prior to execution of a 
divide and then dividing the result of a product by the same value.
<p>	The look-up table will now require three entries per point  rather than two as was 
used  earlier.  Each table entry will need an x value, a y value and a slope value.  This 
change in the program is significant enough that the test program must be altered to 
provide  the  new look-up tables.  Also, the interpolation routine will require different 
arguments and a new routine in the class files forcing  modification of both the  class 
header file along with the class implementation file.  
<p>	Prior to looking at these modifications, we should look at a little program that will 
receive the point values in the  look-up table and calculate the slopes for each point.  This 
seemingly simple program has a couple of pitfalls that will fool the bes