chapter3.htm

嵌入式软件开发.rar

allows complete flexibility because, the size of the table is in no way limited by the class 
construction.  It is also important because the table can be placed in ROM or some type of 
programmable ROM where it will usually be found in an embedded application.  To 
simplify the association of the two BYTE entry idea, a new type named Entry is created.  
This type contains two BYTEs, an x and a y value.  ( Recall, the name BYTE is defined in 
the header file defines as a type unsigned char.)   The look up class definition statement  
needs only two entries, the number of entries in the table and a pointer to the first two 
BYTE pair in the table.  The new type Look_up is defined by the next struct statement.  
<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.
	   Each entry contains two values which are of the type BYTE   */

	typedef struct
	{
	    BYTE x,y;
	}Entry;

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

	typedef struct LUT
	{
		LOOK_UP_CLASS
	} Look_up;

	Look_up *look_up_(int x_length, Entry *table);
	void look_up__(Look_up * this);
	BYTE get_value(struct LUT *this, BYTE value);
	BYTE interpolate(BYTE value,BYTE x0,BYTE y0,BYTE x1,BYTE y1);

	#endif
</pre></code><p>	

	There are three method prototypes associated with this class.  The constructor and 
destructor are the usual form.  The method get_value() is the only method that will be 
needed for  the class.  Interpolate is an internal function that does not necessarily need to 
be defined to the outside world.  If, however, there are more than one type of look-up 
tables to be employed, for example, a three dimensional rather than a two dimensional 
table like we are developing here, the interpolation routine could be used elsewhere.  
Therefore, the interpolate() routine is not hidden from the remainder of the program.  The 
routine interpolate has five parameters.  The parameter value above is the input value for 
which the output is to be calculated.  The remainder of the parameters are two adjacent 
points in the look-up table.  The parameter value must lie between x0 and x1.  The 
interpolation routine does not test for this input range.  The interpolation routine returns a 
type BYTE to the calling program.  
<p>	The method get_value() receives a pointer to the look-up table object along with 
the input value to be transformed.  It returns the interpolated value from  the table.  
<pre><code>
	#include "lutobj.h"
	#include &ltstdlib.h&gt

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

	    while(this-&gttable[i].x&lt=value)
	        i++; 
	    --i;                  /* the search has gone too far */
	    if(this-&gttable[i].x==value)
	        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 x_length, Entry *table)
	{
	    Look_up *this;

	    if(!(this=(Look_up*)malloc(sizeof(Look_up))))
	        error_handler();
	    this-&gtx_length=x_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);
	 
	}
</pre></code><p>
	The code for interpolate() bears some discussion.  All of the data passed into the 
the routine is of the type BYTE.  For this discussion, we will assume that characters are 
eight bits and words are sixteen bits.  Everybody knows that the product of two unsigned 
char numbers is an unsigned word result.  However, with C it does not quite work that 
way.  The result of the product of two chars, either signed or unsigned, is a char.  In fact, 
it is the  least significant eight bits of the product.  Of course, that answer is wrong.  This 
problem is avoided easily.  All input data are cast onto the type  WORD, unsigned int, 
prior to its use in any arithmetic operations.  The product of two WORD types is also a 
WORD, and  it is also, the least significant bits of the larger product.  However, because 
the WORD values  contain data only in their least significant eight bits, the product of two 
such words will have significance only  in the  least significant sixteen bits.  Therefore, the 
product of two such WORD types divided by a WORD type with only eight  significant 
bits results in an eight bit result that  can  be safely added to the eight bit word derived 
from value.  The result should be a WORD type with bits in its least significant eight bits 
only and it will cast onto a type BYTE when returned to the calling program with no 
error.
<p>	The test program which follows sets up three look-up tables and exercises the 
object methods in two manners.  The first is to calculate the table look-up value for a 
range of inputs that covers the complete dynamic range of inputs in steps of ten.  The 
second covers the range of inputs that surround a break point in the data to show how the 
interpolation function handles the data near the breaks.  The tables themselves are quite 
arbitrary.  In the first table y is monotonically increasing in x, and it saturates at a fixed 
value before the end of the table is reached.  In the second table, y is quite flat in x, but 
still monotonic. The third table contains a y range that increases and then decreases as x 
values increase.  
<pre><code>
	#include "lutobj2d.h"  
	#include &ltstdio.h&gt

	const Entry taba[]={
	        0,0,
	        96,40,
	        144,68,
	        166,128,
	        221,160,
	        255,160 };

	const Entry tabb[]={
	        0,0,
	        96,128,
	        144,139,
	        166,158,
	        221,178,
	        238,184,
	        255,255 };

	const Entry tabc[]={
	        0,0,
	        96,162,
	        144,117,
	        166,196,
	        221,255,
	        238,184,
	        255,178 };


	void main(void)
	{
	    int i;
	    Look_up *a=look_up_(6,taba), /* create three look-up tables */
	            *b=look_up_(7,tabb), /* named a, b, and c */
	            *c=look_up_(7,tabc);

	    for(i=0;i&lt255;i+=10) 
	        printf(" %d\t%d\t%d\t%d\n", i,get_value(a,i), 
	                get_value(b,i),get_value(c,i));
	    getch();
	    printf("\n");
	    for(i=210;i&lt230;i++)
	        printf(" %d\t%d\t%d\t%d\n", i,get_value(a,i), 
	                get_value(b,i),get_value(c,i));
	    look_up__(a);  /* destroy all objects when no longer needed*/
	    look_up__(b);
	    look_up__(c);
	} 
</pre></code><p>
	The tables are constructed as simple linear arrays of the type Entry.  In the main 
program, a variable i is created.  Three look-up tables are created by execution of the 
look_up_() constructor function, and pointers to these tables are assigned to the variables 
a, b and c.  There are two simple print out loops.  The first gives i a value range of zero to 
250 and prints the values of i and get_value(table, i) for each of the tables.  When this 
routine is completed, it prints out the same values for a range of i between 210 and 230 in 
steps of 1 to show the operation as the input passes through a break point in the table.  
The result of this calculation is listed below.  The first value shown is i, the second is table 
a, etc.  The blank line is inserted between the two different calculations.  

<table>

<th>Input<th> Table 1<th>Table 2 <th>Table 3<tr>
<td>0 <td>0 <td>0 <td>0<tr>
<td>0 <td>0 <td>0 <td>0<tr>
<td> 10		  <td>4		 <td>13		 <td>16<tr>
<td> 20		  <td>8		 <td>26		 <td>33<tr>
<td> 30		 <td>12		 <td>40		<td>50<tr>
<td> 40		 <td>16		 <td>53 <td>67<tr>
<td> 50		 <td>20		<td> 66		 <td>84<tr>
<td> 60		 <td>25		 <td>80		<td>101<tr>
<td> 70		 <td>29		 <td>93		<td>118<tr>
<td>  80		 <td>33		<td>106		<td>135<tr>
<td>  90		 <td>37		<td>120		<td>151<tr>
<td> 100		 <td>42		<td>128		<td>159<tr>
<td> 110		 <td>48		<td>131		<td>149<tr>    
<td> 120		 <td>54		<td>133		<td>140<tr>
<td> 130		 <td>59		<td>135		<td>131<tr>
<td> 140		<td> 65		<td>138		<td>121<tr>
<td> 150		 <td>84		<td>144		<td>138<tr>
<td> 160		<td>111		<td>152		<td>174<tr>
<td> 170		<td>130		<td>159		<td>200<tr>
<td> 180	   <td>	136		<td>163		<td>211<tr>
<td> 190		<td>141		<td>166		<td>221<tr>
<td> 200		<td>147		<td>170		<td>232<tr>
<td> 210		<td>153		<td>174		<td>243<tr>
<td> 220		<td>159		<td>177		<td>253<tr>
<td> 230		<td>160	   <td>	181		<td>218<tr>
<td> 240		<td>160		<td>192		<td>184<tr>
<td> 250		<td>160		<td>234		<td>180<tr>
</table>
<p><table>
<th>Input  <th>Table 1 <th>Table2 <th> table3 <tr>
<td> 210		<td>153		<td>174		<td>243<tr>
<td>211		<td>154		<td>174		<td>244	<tr>
 <td>212		<td>154		<td>174		<td>245	<tr>
 <td>213		<td>155		<td>175		<td>246	<tr>
 <td>214		<td>155		<td>175		<td>247	<tr>
<td> 215	   <td>	156		<td>175		<td>248	<tr>
 <td>216		<td>157		<td>176		<td>249	<tr>
 <td>217		<td>157		<td>176		<td>250	<tr>
 <td>218		<td>158		<td>176		<td>251	<tr>
<td> 219		<td>158		<td>177		<td>252	<tr>
 <td>220		<td>159		<td>177		<td>253	<tr>
 <td>221		<td>160		<td>178		<td>255	<tr>
 <td>222		<td>160		<td>178		<td>251	<tr>
 <td>223		<td>160		<td>178		<td>247	<tr>
 <td>224		<td>160		<td>179		<td>243<tr>
 <td>225		<td>160		<td>179		<td>239	<tr>
 <td>226		<td>160		<td>179		<td>235	<tr>
 <td>227		<td>160		<td>180		<td>230	<tr>
 <td>228		<td>160		<td>180		<td>226	<tr>
 </table>

<p>	You must compare the table values with the outputs in each case above.  You will 
note that the output ranges are smooth and appear to be nearly correct in the first table.  
There is no good way of knowing without calculating the correct values by hand.  If you 
should do these calculations, you will find that the computed values are accurate when you 
recognize that integer arithmetic rounds all fractional results down, toward zero.  
Calculation of the data through a break point is shown in the second output.  Note that 
there is a break at 221 in the input data. In each case the calculated value gives the 
specified table value at the break point, and the data to the left and right of the break point 
changes correctly.  Table a satruates at an input of 221, which is demonstrated in the 
output data.  The data in table b is quite flat above the break point and less flat below the 
break point.  This performance is seen in the tabluar data.  Finally, the output from table c 
peaks at the input value of 221 and falls on either side of the break as is shown in the data 
above.


<h4><a name="a_faster_table_search">A faster table search</a></h4>

<p>	In the above code, a simple linear table search to find the index into the table from 
which to start the interpolation was used.  For short tables, this approach is probably the 
best choice.  But, what if there are a large number of entries into the table?  In such a case,