dynamips/trunk/insn_lookup.c

/*
 * Cisco router simulation platform.
 * Copyright (c) 2006 Christophe Fillot (cf@utc.fr)
 *
 * Instruction Lookup Tables.
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <assert.h>

#include "utils.h"
#include "hash.h"
#include "insn_lookup.h"
#include "dynamips.h"

/* Hash function for a CBM */
static inline u_int cbm_hash_f(void *ccbm)
{
   cbm_array_t *cbm = (cbm_array_t *)ccbm;
   char *p,*s = (char *)(cbm->tab);
   u_int h,g,i;

   for(h=0,i=0,p=s;i<(cbm->nr_entries*sizeof(int));p+=1,i++)
   {
      h = (h << 4) + *p;
      if ((g = h & 0xf0000000)) {
         h = h ^ (g >> 24);
         h = h ^ g;
      }
   }

   return(h);
}

/* Comparison function for 2 CBM */
static inline int cbm_cmp_f(void *b1,void *b2)
{
   cbm_array_t *cbm1 = (cbm_array_t *)b1;
   cbm_array_t *cbm2 = (cbm_array_t *)b2;
   int i;
   
   for(i=0;i<cbm1->nr_entries;i++)
      if (cbm1->tab[i] != cbm2->tab[i])
         return(FALSE);
   
   return(TRUE);
}

/* Set bit corresponding to a rule number in a CBM */
static inline void cbm_set_rule(cbm_array_t *cbm,int rule_id)
{
   CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) |= 1 << (rule_id & (CBM_SIZE-1));
}

/* Clear bit corresponding to a rule number in a CBM */
static inline void cbm_unset_rule(cbm_array_t *cbm,int rule_id)
{
   CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) &= ~(1 << (rule_id & (CBM_SIZE-1)));
}

/* Returns TRUE if  bit corresponding to a rule number in a CBM is set */
static inline int cbm_check_rule(cbm_array_t *cbm,int rule_id)
{
   return(CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) & 
          (1 << (rule_id & (CBM_SIZE-1))));
}

/* Compute bitwise ANDing of two CBM */
static inline void 
cbm_bitwise_and(cbm_array_t *result,cbm_array_t *a1,cbm_array_t *a2)
{
   int i;

   /* Compute bitwise ANDing */
   for(i=0;i<a1->nr_entries;i++)
      CBM_ARRAY(result,i) = CBM_ARRAY(a1,i) & CBM_ARRAY(a2,i);
}

/* Get first matching rule number */
static inline int cbm_first_match(insn_lookup_t *ilt,cbm_array_t *cbm)
{
   int i;

   for(i=0;i<ilt->nr_insn;i++)
      if (cbm_check_rule(cbm,i)) 
         return(i);
   
   return(-1);
}

/* Create a class bitmap (CBM) */
static cbm_array_t *cbm_create(insn_lookup_t *ilt)
{
   cbm_array_t *array;
   int size;

   size = CBM_CSIZE(ilt->cbm_size);

   /* CBM are simply bit arrays */
   array = malloc(size);
   assert(array);

   memset(array,0,size);
   array->nr_entries = ilt->cbm_size;
   return array;
}

/* Duplicate a class bitmap */
static cbm_array_t *cbm_duplicate(cbm_array_t *cbm)
{
   int size = CBM_CSIZE(cbm->nr_entries);
   cbm_array_t *array;

   array = malloc(size);
   assert(array);
   memcpy(array,cbm,size);
   return array;
}

/* 
 * Get equivalent class corresponding to a class bitmap. Create eqclass 
 * structure if needed (CBM not previously seen).
 */
static rfc_eqclass_t *cbm_get_eqclass(rfc_array_t *rfct,cbm_array_t *cbm)
{
   rfc_eqclass_t *eqcl;
   cbm_array_t *bmp;

   /* Lookup for CBM into hash table */
   if ((eqcl = hash_table_lookup(rfct->cbm_hash,cbm)) == NULL)
   {
      /* Duplicate CBM */
      bmp = cbm_duplicate(cbm);
      assert(bmp);

      /* CBM is not already known */
      eqcl = malloc(sizeof(rfc_eqclass_t));
      assert(eqcl);

      assert(rfct->nr_eqid < rfct->nr_elements);

      /* Get a new equivalent ID */
      eqcl->eqID = rfct->nr_eqid++;
      eqcl->cbm = bmp;
      rfct->id2cbm[eqcl->eqID] = bmp;

      /* Insert it in hash table */
      if (hash_table_insert(rfct->cbm_hash,bmp,eqcl) == -1)
         return NULL;
   }

   return eqcl;
}

/* Allocate an array for Recursive Flow Classification */
static rfc_array_t *rfc_alloc_array(int nr_elements)
{
   rfc_array_t *array;
   int total_size;

   /* Compute size of memory chunk needed to store the array */
   total_size = (nr_elements * sizeof(int)) + sizeof(rfc_array_t);
   array = malloc(total_size);
   assert(array);
   memset(array,0,total_size);
   array->nr_elements = nr_elements;
   
   /* Initialize hash table for Class Bitmaps */
   array->cbm_hash = hash_table_create(cbm_hash_f,cbm_cmp_f,CBM_HASH_SIZE);
   assert(array->cbm_hash);

   /* Initialize table for converting ID to CBM */
   array->id2cbm = calloc(nr_elements,sizeof(cbm_array_t *));
   assert(array->id2cbm);

   return(array);
}

/* Check an instruction with specified parameter */
static void rfc_check_insn(insn_lookup_t *ilt,cbm_array_t *cbm,
                           ilt_check_cbk_t pcheck,int value)
{
   void *p;
   int i;

   for(i=0;i<ilt->nr_insn;i++) {
      p = ilt->get_insn(i);

      if (pcheck(p,value)) 
         cbm_set_rule(cbm,i);
      else
         cbm_unset_rule(cbm,i);
   }
}

/* RFC Chunk preprocessing: phase 0 */
static rfc_array_t *rfc_phase_0(insn_lookup_t *ilt,ilt_check_cbk_t pcheck)
{
   rfc_eqclass_t *eqcl;
   rfc_array_t *rfct;
   cbm_array_t *bmp;
   int i;

   /* allocate a temporary class bitmap */
   bmp = cbm_create(ilt);
   assert(bmp);

   /* Allocate a new RFC array of 16-bits entries */
   rfct = rfc_alloc_array(RFC_ARRAY_MAXSIZE);
   assert(rfct);

   for(i=0;i<RFC_ARRAY_MAXSIZE;i++)
   {
      /* determine all instructions that match this value */
      rfc_check_insn(ilt,bmp,pcheck,i);

      /* get equivalent class for this bitmap */
      eqcl = cbm_get_eqclass(rfct,bmp);
      assert(eqcl);

      /* fill the RFC table */
      rfct->eqID[i] = eqcl->eqID;
   }

   free(bmp);
   return rfct;
}

/* RFC Chunk preprocessing: phase j (j > 0) */
static rfc_array_t *rfc_phase_j(insn_lookup_t *ilt,rfc_array_t *p0,
                                rfc_array_t *p1)
{
   rfc_eqclass_t *eqcl;
   rfc_array_t *rfct;
   cbm_array_t *bmp;
   int nr_elements;
   int index = 0;
   int i,j;

   /* allocate a temporary class bitmap */
   bmp = cbm_create(ilt);
   assert(bmp);

   /* compute number of elements */
   nr_elements = p0->nr_eqid * p1->nr_eqid;

   /* allocate a new RFC array */
   rfct = rfc_alloc_array(nr_elements);
   assert(rfct);
   rfct->parent0 = p0;
   rfct->parent1 = p1;

   /* make a cross product between p0 and p1 */
   for(i=0;i<p0->nr_eqid;i++)
      for(j=0;j<p1->nr_eqid;j++)
      {
         /* compute bitwise AND */
         cbm_bitwise_and(bmp,p0->id2cbm[i],p1->id2cbm[j]);

         /* get equivalent class for this bitmap */
         eqcl = cbm_get_eqclass(rfct,bmp);
         assert(eqcl);

         /* fill RFC table */
         rfct->eqID[index++] = eqcl->eqID;
      }

   free(bmp);
   return rfct;
}

/* Compute RFC phase 0 */
static void ilt_phase_0(insn_lookup_t *ilt,int idx,ilt_check_cbk_t pcheck)
{
   rfc_array_t *rfct;

   rfct = rfc_phase_0(ilt,pcheck);
   assert(rfct);
   ilt->rfct[idx] = rfct;
}

/* Compute RFC phase j */
static void ilt_phase_j(insn_lookup_t *ilt,int p0,int p1,int res)
{
   rfc_array_t *rfct;

   rfct = rfc_phase_j(ilt,ilt->rfct[p0],ilt->rfct[p1]);
   assert(rfct);
   ilt->rfct[res] = rfct;
}

/* Postprocessing */
static void ilt_postprocessing(insn_lookup_t *ilt)
{
   rfc_array_t *rfct = ilt->rfct[2];
   int i;

   for(i=0;i<rfct->nr_elements;i++)
      rfct->eqID[i] = cbm_first_match(ilt,rfct->id2cbm[rfct->eqID[i]]);
}

/* Instruction lookup table compilation */
static void ilt_compile(insn_lookup_t *ilt)
{  
   ilt_phase_0(ilt,0,ilt->chk_hi);
   ilt_phase_0(ilt,1,ilt->chk_lo);
   ilt_phase_j(ilt,0,1,2);
   ilt_postprocessing(ilt);
}

/* Dump an instruction lookup table */
static void ilt_dump(insn_lookup_t *ilt)
{
   rfc_array_t *rfct;
   int i,j;
   
   printf("ILT %p: nr_insn=%d, cbm_size=%d\n",ilt,ilt->nr_insn,ilt->cbm_size);

   for(i=0;i<RFC_ARRAY_NUMBER;i++) {
      rfct = ilt->rfct[i];
      
      for(j=0;j<rfct->nr_elements;j++)
         printf("  (0x%4.4x,0x%4.4x) = 0x%4.4x\n",i,j,rfct->eqID[j]);
   }
}

/* Write the specified RFC array to disk */
static void ilt_store_rfct(FILE *fd,int id,rfc_array_t *rfct)
{
   /* Store RFC array ID + number of elements */
   fwrite(&id,sizeof(id),1,fd);
   fwrite(&rfct->nr_elements,sizeof(rfct->nr_elements),1,fd);
   fwrite(&rfct->nr_eqid,sizeof(rfct->nr_eqid),1,fd);

   fwrite(rfct->eqID,rfct->nr_elements,sizeof(int),fd);
}

/* Write the full instruction lookup table */
static void ilt_store_table(FILE *fd,insn_lookup_t *ilt)
{
   int i;

   for(i=0;i<RFC_ARRAY_NUMBER;i++)
      if (ilt->rfct[i] != NULL)
         ilt_store_rfct(fd,i,ilt->rfct[i]);
}

/* Load an RFC array from disk */
static int ilt_load_rfct(FILE *fd,insn_lookup_t *ilt)
{
   u_int id,nr_elements,nr_eqid;
   rfc_array_t *rfct;
   size_t len;

   /* Read ID and number of elements */
   if ((fread(&id,sizeof(id),1,fd) != 1) ||
       (fread(&nr_elements,sizeof(nr_elements),1,fd) != 1) ||
       (fread(&nr_eqid,sizeof(nr_eqid),1,fd) != 1))
      return(-1);

   if ((id >= RFC_ARRAY_NUMBER) || (nr_elements > RFC_ARRAY_MAXSIZE))
      return(-1);

   /* Allocate the RFC array with the eqID table */
   len = sizeof(*rfct) + (nr_elements * sizeof(int));

   if (!(rfct = malloc(len)))
      return(-1);

   memset(rfct,0,sizeof(*rfct));
   rfct->nr_elements = nr_elements;
   rfct->nr_eqid = nr_eqid;

   /* Read the equivalent ID array */
   fread(rfct->eqID,rfct->nr_elements,sizeof(int),fd);

   ilt->rfct[id] = rfct;
   return(0);
}

/* Check an instruction table loaded from disk */
static int ilt_check_cached_table(insn_lookup_t *ilt)
{
   int i;

   /* All arrays must have been loaded */
   for(i=0;i<RFC_ARRAY_NUMBER;i++)
      if (!ilt->rfct[i])
         return(-1);

   return(0);
}

/* Load a full instruction table from disk */
static insn_lookup_t *ilt_load_table(FILE *fd)
{
   insn_lookup_t *ilt;

   if (!(ilt = malloc(sizeof(*ilt))))
      return NULL;

   memset(ilt,0,sizeof(*ilt));

   while(!feof(fd)) {
      if (ilt_load_rfct(fd,ilt) == -1)
         break;
   }

   if (ilt_check_cached_table(ilt) == -1)
      return NULL;

   return ilt;
}

/* Build a filename for a cached ILT table on disk */
static char *ilt_build_filename(char *table_name)
{
   return(dyn_sprintf("ilt_%s_%s",sw_version_tag,table_name));
}

/* Try to load a cached ILT table from disk */
static insn_lookup_t *ilt_cache_load(char *table_name)
{
   insn_lookup_t *ilt;
   char *filename;
   FILE *fd;

   if (!(filename = ilt_build_filename(table_name)))
      return NULL;

   if (!(fd = fopen(filename,"r"))) {
      free(filename);
      return NULL;
   }

   ilt = ilt_load_table(fd);
   fclose(fd);
   return ilt;
}

/* Store the specified ILT table on disk for future use (cache) */
static int ilt_cache_store(char *table_name,insn_lookup_t *ilt)
{
   char *filename;
   FILE *fd;

   if (!(filename = ilt_build_filename(table_name)))
      return(-1);

   if (!(fd = fopen(filename,"w"))) {
      free(filename);
      return(-1);
   }

   ilt_store_table(fd,ilt);
   fclose(fd);
   return(0);
}

/* Create an instruction lookup table */
insn_lookup_t *ilt_create(char *table_name,
                          int nr_insn,ilt_get_insn_cbk_t get_insn,
                          ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi)
{
   insn_lookup_t *ilt;
   
   /* Try to load a cached table from disk */
   if ((ilt = ilt_cache_load(table_name))) {
      printf("ILT: loaded table \"%s\" from cache.\n",table_name);
      return ilt;
   }

   /* We have to build the full table... */
   ilt = malloc(sizeof(*ilt));
   assert(ilt);
   memset(ilt,0,sizeof(*ilt));

   ilt->cbm_size = normalize_size(nr_insn,CBM_SIZE,CBM_SHIFT);
   ilt->nr_insn  = nr_insn;
   ilt->get_insn = get_insn;
   ilt->chk_lo   = chk_lo;
   ilt->chk_hi   = chk_hi;

   /* Compile the instruction opcodes */
   ilt_compile(ilt);
   
   /* Store the result on disk for future exec */
   ilt_cache_store(table_name,ilt);
   return(ilt);
}
1	dpavlin	1	/*
2	dpavlin	7	* Cisco router simulation platform.
3	dpavlin	1	* Copyright (c) 2006 Christophe Fillot (cf@utc.fr)
4			*
5			* Instruction Lookup Tables.
6			*/
7
8			#include <stdio.h>
9			#include <stdlib.h>
10			#include <unistd.h>
11			#include <string.h>
12			#include <sys/types.h>
13			#include <sys/stat.h>
14			#include <sys/mman.h>
15			#include <assert.h>
16
17			#include "utils.h"
18			#include "hash.h"
19			#include "insn_lookup.h"
20	dpavlin	8	#include "dynamips.h"
21	dpavlin	1
22			/* Hash function for a CBM */
23			static inline u_int cbm_hash_f(void *ccbm)
24			{
25			cbm_array_t cbm = (cbm_array_t )ccbm;
26			char p,s = (char *)(cbm->tab);
27			u_int h,g,i;
28
29			for(h=0,i=0,p=s;i<(cbm->nr_entries*sizeof(int));p+=1,i++)
30			{
31			h = (h << 4) + *p;
32			if ((g = h & 0xf0000000)) {
33			h = h ^ (g >> 24);
34			h = h ^ g;
35			}
36			}
37
38			return(h);
39			}
40
41			/* Comparison function for 2 CBM */
42			static inline int cbm_cmp_f(void b1,void b2)
43			{
44			cbm_array_t cbm1 = (cbm_array_t )b1;
45			cbm_array_t cbm2 = (cbm_array_t )b2;
46			int i;
47
48			for(i=0;i<cbm1->nr_entries;i++)
49			if (cbm1->tab[i] != cbm2->tab[i])
50			return(FALSE);
51
52			return(TRUE);
53			}
54
55			/* Set bit corresponding to a rule number in a CBM */
56			static inline void cbm_set_rule(cbm_array_t *cbm,int rule_id)
57			{
58			CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) \|= 1 << (rule_id & (CBM_SIZE-1));
59			}
60
61			/* Clear bit corresponding to a rule number in a CBM */
62			static inline void cbm_unset_rule(cbm_array_t *cbm,int rule_id)
63			{
64			CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) &= ~(1 << (rule_id & (CBM_SIZE-1)));
65			}
66
67			/* Returns TRUE if bit corresponding to a rule number in a CBM is set */
68			static inline int cbm_check_rule(cbm_array_t *cbm,int rule_id)
69			{
70			return(CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) &
71			(1 << (rule_id & (CBM_SIZE-1))));
72			}
73
74			/* Compute bitwise ANDing of two CBM */
75			static inline void
76			cbm_bitwise_and(cbm_array_t result,cbm_array_t a1,cbm_array_t *a2)
77			{
78			int i;
79
80			/* Compute bitwise ANDing */
81			for(i=0;i<a1->nr_entries;i++)
82			CBM_ARRAY(result,i) = CBM_ARRAY(a1,i) & CBM_ARRAY(a2,i);
83			}
84
85			/* Get first matching rule number */
86			static inline int cbm_first_match(insn_lookup_t ilt,cbm_array_t cbm)
87			{
88			int i;
89
90			for(i=0;i<ilt->nr_insn;i++)
91			if (cbm_check_rule(cbm,i))
92			return(i);
93
94			return(-1);
95			}
96
97			/* Create a class bitmap (CBM) */
98			static cbm_array_t cbm_create(insn_lookup_t ilt)
99			{
100			cbm_array_t *array;
101			int size;
102
103			size = CBM_CSIZE(ilt->cbm_size);
104
105			/* CBM are simply bit arrays */
106			array = malloc(size);
107			assert(array);
108
109			memset(array,0,size);
110			array->nr_entries = ilt->cbm_size;
111			return array;
112			}
113
114			/* Duplicate a class bitmap */
115			static cbm_array_t cbm_duplicate(cbm_array_t cbm)
116			{
117			int size = CBM_CSIZE(cbm->nr_entries);
118			cbm_array_t *array;
119
120			array = malloc(size);
121			assert(array);
122			memcpy(array,cbm,size);
123			return array;
124			}
125
126			/*
127			* Get equivalent class corresponding to a class bitmap. Create eqclass
128			* structure if needed (CBM not previously seen).
129			*/
130			static rfc_eqclass_t cbm_get_eqclass(rfc_array_t rfct,cbm_array_t *cbm)
131			{
132			rfc_eqclass_t *eqcl;
133			cbm_array_t *bmp;
134
135			/* Lookup for CBM into hash table */
136			if ((eqcl = hash_table_lookup(rfct->cbm_hash,cbm)) == NULL)
137			{
138			/* Duplicate CBM */
139			bmp = cbm_duplicate(cbm);
140			assert(bmp);
141
142			/* CBM is not already known */
143			eqcl = malloc(sizeof(rfc_eqclass_t));
144			assert(eqcl);
145
146			assert(rfct->nr_eqid < rfct->nr_elements);
147
148			/* Get a new equivalent ID */
149			eqcl->eqID = rfct->nr_eqid++;
150			eqcl->cbm = bmp;
151			rfct->id2cbm[eqcl->eqID] = bmp;
152
153			/* Insert it in hash table */
154			if (hash_table_insert(rfct->cbm_hash,bmp,eqcl) == -1)
155			return NULL;
156			}
157
158			return eqcl;
159			}
160
161			/* Allocate an array for Recursive Flow Classification */
162			static rfc_array_t *rfc_alloc_array(int nr_elements)
163			{
164			rfc_array_t *array;
165			int total_size;
166
167			/* Compute size of memory chunk needed to store the array */
168			total_size = (nr_elements * sizeof(int)) + sizeof(rfc_array_t);
169			array = malloc(total_size);
170			assert(array);
171			memset(array,0,total_size);
172			array->nr_elements = nr_elements;
173
174			/* Initialize hash table for Class Bitmaps */
175			array->cbm_hash = hash_table_create(cbm_hash_f,cbm_cmp_f,CBM_HASH_SIZE);
176			assert(array->cbm_hash);
177
178			/* Initialize table for converting ID to CBM */
179			array->id2cbm = calloc(nr_elements,sizeof(cbm_array_t *));
180			assert(array->id2cbm);
181
182			return(array);
183			}
184
185			/* Check an instruction with specified parameter */
186			static void rfc_check_insn(insn_lookup_t ilt,cbm_array_t cbm,
187			ilt_check_cbk_t pcheck,int value)
188			{
189			void *p;
190			int i;
191
192			for(i=0;i<ilt->nr_insn;i++) {
193			p = ilt->get_insn(i);
194
195			if (pcheck(p,value))
196			cbm_set_rule(cbm,i);
197			else
198			cbm_unset_rule(cbm,i);
199			}
200			}
201
202			/* RFC Chunk preprocessing: phase 0 */
203			static rfc_array_t rfc_phase_0(insn_lookup_t ilt,ilt_check_cbk_t pcheck)
204			{
205			rfc_eqclass_t *eqcl;
206			rfc_array_t *rfct;
207			cbm_array_t *bmp;
208			int i;
209
210			/* allocate a temporary class bitmap */
211			bmp = cbm_create(ilt);
212			assert(bmp);
213
214			/* Allocate a new RFC array of 16-bits entries */
215			rfct = rfc_alloc_array(RFC_ARRAY_MAXSIZE);
216			assert(rfct);
217
218			for(i=0;i<RFC_ARRAY_MAXSIZE;i++)
219			{
220			/* determine all instructions that match this value */
221			rfc_check_insn(ilt,bmp,pcheck,i);
222
223			/* get equivalent class for this bitmap */
224			eqcl = cbm_get_eqclass(rfct,bmp);
225			assert(eqcl);
226
227			/* fill the RFC table */
228			rfct->eqID[i] = eqcl->eqID;
229			}
230
231			free(bmp);
232			return rfct;
233			}
234
235			/* RFC Chunk preprocessing: phase j (j > 0) */
236			static rfc_array_t rfc_phase_j(insn_lookup_t ilt,rfc_array_t *p0,
237			rfc_array_t *p1)
238			{
239			rfc_eqclass_t *eqcl;
240			rfc_array_t *rfct;
241			cbm_array_t *bmp;
242			int nr_elements;
243			int index = 0;
244			int i,j;
245
246			/* allocate a temporary class bitmap */
247			bmp = cbm_create(ilt);
248			assert(bmp);
249
250			/* compute number of elements */
251			nr_elements = p0->nr_eqid * p1->nr_eqid;
252
253			/* allocate a new RFC array */
254			rfct = rfc_alloc_array(nr_elements);
255			assert(rfct);
256			rfct->parent0 = p0;
257			rfct->parent1 = p1;
258
259			/* make a cross product between p0 and p1 */
260			for(i=0;i<p0->nr_eqid;i++)
261			for(j=0;j<p1->nr_eqid;j++)
262			{
263			/* compute bitwise AND */
264			cbm_bitwise_and(bmp,p0->id2cbm[i],p1->id2cbm[j]);
265
266			/* get equivalent class for this bitmap */
267			eqcl = cbm_get_eqclass(rfct,bmp);
268			assert(eqcl);
269
270			/* fill RFC table */
271			rfct->eqID[index++] = eqcl->eqID;
272			}
273
274			free(bmp);
275			return rfct;
276			}
277
278			/* Compute RFC phase 0 */
279			static void ilt_phase_0(insn_lookup_t *ilt,int idx,ilt_check_cbk_t pcheck)
280			{
281			rfc_array_t *rfct;
282
283			rfct = rfc_phase_0(ilt,pcheck);
284			assert(rfct);
285			ilt->rfct[idx] = rfct;
286			}
287
288			/* Compute RFC phase j */
289			static void ilt_phase_j(insn_lookup_t *ilt,int p0,int p1,int res)
290			{
291			rfc_array_t *rfct;
292
293			rfct = rfc_phase_j(ilt,ilt->rfct[p0],ilt->rfct[p1]);
294			assert(rfct);
295			ilt->rfct[res] = rfct;
296			}
297
298			/* Postprocessing */
299			static void ilt_postprocessing(insn_lookup_t *ilt)
300			{
301			rfc_array_t *rfct = ilt->rfct[2];
302			int i;
303
304			for(i=0;i<rfct->nr_elements;i++)
305			rfct->eqID[i] = cbm_first_match(ilt,rfct->id2cbm[rfct->eqID[i]]);
306			}
307
308			/* Instruction lookup table compilation */
309			static void ilt_compile(insn_lookup_t *ilt)
310			{
311			ilt_phase_0(ilt,0,ilt->chk_hi);
312			ilt_phase_0(ilt,1,ilt->chk_lo);
313			ilt_phase_j(ilt,0,1,2);
314			ilt_postprocessing(ilt);
315			}
316
317	dpavlin	8	/* Dump an instruction lookup table */
318			static void ilt_dump(insn_lookup_t *ilt)
319			{
320			rfc_array_t *rfct;
321			int i,j;
322
323			printf("ILT %p: nr_insn=%d, cbm_size=%d\n",ilt,ilt->nr_insn,ilt->cbm_size);
324
325			for(i=0;i<RFC_ARRAY_NUMBER;i++) {
326			rfct = ilt->rfct[i];
327
328			for(j=0;j<rfct->nr_elements;j++)
329			printf(" (0x%4.4x,0x%4.4x) = 0x%4.4x\n",i,j,rfct->eqID[j]);
330			}
331			}
332
333			/* Write the specified RFC array to disk */
334			static void ilt_store_rfct(FILE fd,int id,rfc_array_t rfct)
335			{
336			/* Store RFC array ID + number of elements */
337			fwrite(&id,sizeof(id),1,fd);
338			fwrite(&rfct->nr_elements,sizeof(rfct->nr_elements),1,fd);
339			fwrite(&rfct->nr_eqid,sizeof(rfct->nr_eqid),1,fd);
340
341			fwrite(rfct->eqID,rfct->nr_elements,sizeof(int),fd);
342			}
343
344			/* Write the full instruction lookup table */
345			static void ilt_store_table(FILE fd,insn_lookup_t ilt)
346			{
347			int i;
348
349			for(i=0;i<RFC_ARRAY_NUMBER;i++)
350			if (ilt->rfct[i] != NULL)
351			ilt_store_rfct(fd,i,ilt->rfct[i]);
352			}
353
354			/* Load an RFC array from disk */
355			static int ilt_load_rfct(FILE fd,insn_lookup_t ilt)
356			{
357			u_int id,nr_elements,nr_eqid;
358			rfc_array_t *rfct;
359			size_t len;
360
361			/* Read ID and number of elements */
362			if ((fread(&id,sizeof(id),1,fd) != 1) \|\|
363			(fread(&nr_elements,sizeof(nr_elements),1,fd) != 1) \|\|
364			(fread(&nr_eqid,sizeof(nr_eqid),1,fd) != 1))
365			return(-1);
366
367			if ((id >= RFC_ARRAY_NUMBER) \|\| (nr_elements > RFC_ARRAY_MAXSIZE))
368			return(-1);
369
370			/* Allocate the RFC array with the eqID table */
371			len = sizeof(rfct) + (nr_elements sizeof(int));
372
373			if (!(rfct = malloc(len)))
374			return(-1);
375
376			memset(rfct,0,sizeof(*rfct));
377			rfct->nr_elements = nr_elements;
378			rfct->nr_eqid = nr_eqid;
379
380			/* Read the equivalent ID array */
381			fread(rfct->eqID,rfct->nr_elements,sizeof(int),fd);
382
383			ilt->rfct[id] = rfct;
384			return(0);
385			}
386
387			/* Check an instruction table loaded from disk */
388			static int ilt_check_cached_table(insn_lookup_t *ilt)
389			{
390			int i;
391
392			/* All arrays must have been loaded */
393			for(i=0;i<RFC_ARRAY_NUMBER;i++)
394			if (!ilt->rfct[i])
395			return(-1);
396
397			return(0);
398			}
399
400			/* Load a full instruction table from disk */
401			static insn_lookup_t ilt_load_table(FILE fd)
402			{
403			insn_lookup_t *ilt;
404
405			if (!(ilt = malloc(sizeof(*ilt))))
406			return NULL;
407
408			memset(ilt,0,sizeof(*ilt));
409
410			while(!feof(fd)) {
411			if (ilt_load_rfct(fd,ilt) == -1)
412			break;
413			}
414
415			if (ilt_check_cached_table(ilt) == -1)
416			return NULL;
417
418			return ilt;
419			}
420
421			/* Build a filename for a cached ILT table on disk */
422			static char ilt_build_filename(char table_name)
423			{
424			return(dyn_sprintf("ilt_%s_%s",sw_version_tag,table_name));
425			}
426
427			/* Try to load a cached ILT table from disk */
428			static insn_lookup_t ilt_cache_load(char table_name)
429			{
430			insn_lookup_t *ilt;
431			char *filename;
432			FILE *fd;
433
434			if (!(filename = ilt_build_filename(table_name)))
435			return NULL;
436
437			if (!(fd = fopen(filename,"r"))) {
438			free(filename);
439			return NULL;
440			}
441
442			ilt = ilt_load_table(fd);
443			fclose(fd);
444			return ilt;
445			}
446
447			/* Store the specified ILT table on disk for future use (cache) */
448			static int ilt_cache_store(char table_name,insn_lookup_t ilt)
449			{
450			char *filename;
451			FILE *fd;
452
453			if (!(filename = ilt_build_filename(table_name)))
454			return(-1);
455
456			if (!(fd = fopen(filename,"w"))) {
457			free(filename);
458			return(-1);
459			}
460
461			ilt_store_table(fd,ilt);
462			fclose(fd);
463			return(0);
464			}
465
466	dpavlin	1	/* Create an instruction lookup table */
467	dpavlin	8	insn_lookup_t ilt_create(char table_name,
468			int nr_insn,ilt_get_insn_cbk_t get_insn,
469	dpavlin	1	ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi)
470			{
471			insn_lookup_t *ilt;
472
473	dpavlin	8	/* Try to load a cached table from disk */
474			if ((ilt = ilt_cache_load(table_name))) {
475			printf("ILT: loaded table \"%s\" from cache.\n",table_name);
476			return ilt;
477			}
478
479			/* We have to build the full table... */
480	dpavlin	1	ilt = malloc(sizeof(*ilt));
481			assert(ilt);
482			memset(ilt,0,sizeof(*ilt));
483
484			ilt->cbm_size = normalize_size(nr_insn,CBM_SIZE,CBM_SHIFT);
485			ilt->nr_insn = nr_insn;
486			ilt->get_insn = get_insn;
487			ilt->chk_lo = chk_lo;
488			ilt->chk_hi = chk_hi;
489
490	dpavlin	8	/* Compile the instruction opcodes */
491	dpavlin	1	ilt_compile(ilt);
492	dpavlin	8
493			/* Store the result on disk for future exec */
494			ilt_cache_store(table_name,ilt);
495	dpavlin	1	return(ilt);
496			}