/[dynamips]/trunk/insn_lookup.c
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Annotation of /trunk/insn_lookup.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 7 - (hide annotations)
Sat Oct 6 16:23:47 2007 UTC (16 years, 5 months ago) by dpavlin
Original Path: upstream/dynamips-0.2.7-RC1/insn_lookup.c
File MIME type: text/plain
File size: 7871 byte(s)
dynamips-0.2.7-RC1

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    
21     /* Hash function for a CBM */
22     static inline u_int cbm_hash_f(void *ccbm)
23     {
24     cbm_array_t *cbm = (cbm_array_t *)ccbm;
25     char *p,*s = (char *)(cbm->tab);
26     u_int h,g,i;
27    
28     for(h=0,i=0,p=s;i<(cbm->nr_entries*sizeof(int));p+=1,i++)
29     {
30     h = (h << 4) + *p;
31     if ((g = h & 0xf0000000)) {
32     h = h ^ (g >> 24);
33     h = h ^ g;
34     }
35     }
36    
37     return(h);
38     }
39    
40     /* Comparison function for 2 CBM */
41     static inline int cbm_cmp_f(void *b1,void *b2)
42     {
43     cbm_array_t *cbm1 = (cbm_array_t *)b1;
44     cbm_array_t *cbm2 = (cbm_array_t *)b2;
45     int i;
46    
47     for(i=0;i<cbm1->nr_entries;i++)
48     if (cbm1->tab[i] != cbm2->tab[i])
49     return(FALSE);
50    
51     return(TRUE);
52     }
53    
54     /* Set bit corresponding to a rule number in a CBM */
55     static inline void cbm_set_rule(cbm_array_t *cbm,int rule_id)
56     {
57     CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) |= 1 << (rule_id & (CBM_SIZE-1));
58     }
59    
60     /* Clear bit corresponding to a rule number in a CBM */
61     static inline void cbm_unset_rule(cbm_array_t *cbm,int rule_id)
62     {
63     CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) &= ~(1 << (rule_id & (CBM_SIZE-1)));
64     }
65    
66     /* Returns TRUE if bit corresponding to a rule number in a CBM is set */
67     static inline int cbm_check_rule(cbm_array_t *cbm,int rule_id)
68     {
69     return(CBM_ARRAY(cbm,(rule_id >> CBM_SHIFT)) &
70     (1 << (rule_id & (CBM_SIZE-1))));
71     }
72    
73     /* Compute bitwise ANDing of two CBM */
74     static inline void
75     cbm_bitwise_and(cbm_array_t *result,cbm_array_t *a1,cbm_array_t *a2)
76     {
77     int i;
78    
79     /* Compute bitwise ANDing */
80     for(i=0;i<a1->nr_entries;i++)
81     CBM_ARRAY(result,i) = CBM_ARRAY(a1,i) & CBM_ARRAY(a2,i);
82     }
83    
84     /* Get first matching rule number */
85     static inline int cbm_first_match(insn_lookup_t *ilt,cbm_array_t *cbm)
86     {
87     int i;
88    
89     for(i=0;i<ilt->nr_insn;i++)
90     if (cbm_check_rule(cbm,i))
91     return(i);
92    
93     return(-1);
94     }
95    
96     /* Create a class bitmap (CBM) */
97     static cbm_array_t *cbm_create(insn_lookup_t *ilt)
98     {
99     cbm_array_t *array;
100     int size;
101    
102     size = CBM_CSIZE(ilt->cbm_size);
103    
104     /* CBM are simply bit arrays */
105     array = malloc(size);
106     assert(array);
107    
108     memset(array,0,size);
109     array->nr_entries = ilt->cbm_size;
110     return array;
111     }
112    
113     /* Duplicate a class bitmap */
114     static cbm_array_t *cbm_duplicate(cbm_array_t *cbm)
115     {
116     int size = CBM_CSIZE(cbm->nr_entries);
117     cbm_array_t *array;
118    
119     array = malloc(size);
120     assert(array);
121     memcpy(array,cbm,size);
122     return array;
123     }
124    
125     /*
126     * Get equivalent class corresponding to a class bitmap. Create eqclass
127     * structure if needed (CBM not previously seen).
128     */
129     static rfc_eqclass_t *cbm_get_eqclass(rfc_array_t *rfct,cbm_array_t *cbm)
130     {
131     rfc_eqclass_t *eqcl;
132     cbm_array_t *bmp;
133    
134     /* Lookup for CBM into hash table */
135     if ((eqcl = hash_table_lookup(rfct->cbm_hash,cbm)) == NULL)
136     {
137     /* Duplicate CBM */
138     bmp = cbm_duplicate(cbm);
139     assert(bmp);
140    
141     /* CBM is not already known */
142     eqcl = malloc(sizeof(rfc_eqclass_t));
143     assert(eqcl);
144    
145     assert(rfct->nr_eqid < rfct->nr_elements);
146    
147     /* Get a new equivalent ID */
148     eqcl->eqID = rfct->nr_eqid++;
149     eqcl->cbm = bmp;
150     rfct->id2cbm[eqcl->eqID] = bmp;
151    
152     /* Insert it in hash table */
153     if (hash_table_insert(rfct->cbm_hash,bmp,eqcl) == -1)
154     return NULL;
155     }
156    
157     return eqcl;
158     }
159    
160     /* Allocate an array for Recursive Flow Classification */
161     static rfc_array_t *rfc_alloc_array(int nr_elements)
162     {
163     rfc_array_t *array;
164     int total_size;
165    
166     /* Compute size of memory chunk needed to store the array */
167     total_size = (nr_elements * sizeof(int)) + sizeof(rfc_array_t);
168     array = malloc(total_size);
169     assert(array);
170     memset(array,0,total_size);
171     array->nr_elements = nr_elements;
172    
173     /* Initialize hash table for Class Bitmaps */
174     array->cbm_hash = hash_table_create(cbm_hash_f,cbm_cmp_f,CBM_HASH_SIZE);
175     assert(array->cbm_hash);
176    
177     /* Initialize table for converting ID to CBM */
178     array->id2cbm = calloc(nr_elements,sizeof(cbm_array_t *));
179     assert(array->id2cbm);
180    
181     return(array);
182     }
183    
184     /* Check an instruction with specified parameter */
185     static void rfc_check_insn(insn_lookup_t *ilt,cbm_array_t *cbm,
186     ilt_check_cbk_t pcheck,int value)
187     {
188     void *p;
189     int i;
190    
191     for(i=0;i<ilt->nr_insn;i++) {
192     p = ilt->get_insn(i);
193    
194     if (pcheck(p,value))
195     cbm_set_rule(cbm,i);
196     else
197     cbm_unset_rule(cbm,i);
198     }
199     }
200    
201     /* RFC Chunk preprocessing: phase 0 */
202     static rfc_array_t *rfc_phase_0(insn_lookup_t *ilt,ilt_check_cbk_t pcheck)
203     {
204     rfc_eqclass_t *eqcl;
205     rfc_array_t *rfct;
206     cbm_array_t *bmp;
207     int i;
208    
209     /* allocate a temporary class bitmap */
210     bmp = cbm_create(ilt);
211     assert(bmp);
212    
213     /* Allocate a new RFC array of 16-bits entries */
214     rfct = rfc_alloc_array(RFC_ARRAY_MAXSIZE);
215     assert(rfct);
216    
217     for(i=0;i<RFC_ARRAY_MAXSIZE;i++)
218     {
219     /* determine all instructions that match this value */
220     rfc_check_insn(ilt,bmp,pcheck,i);
221    
222     /* get equivalent class for this bitmap */
223     eqcl = cbm_get_eqclass(rfct,bmp);
224     assert(eqcl);
225    
226     /* fill the RFC table */
227     rfct->eqID[i] = eqcl->eqID;
228     }
229    
230     free(bmp);
231     return rfct;
232     }
233    
234     /* RFC Chunk preprocessing: phase j (j > 0) */
235     static rfc_array_t *rfc_phase_j(insn_lookup_t *ilt,rfc_array_t *p0,
236     rfc_array_t *p1)
237     {
238     rfc_eqclass_t *eqcl;
239     rfc_array_t *rfct;
240     cbm_array_t *bmp;
241     int nr_elements;
242     int index = 0;
243     int i,j;
244    
245     /* allocate a temporary class bitmap */
246     bmp = cbm_create(ilt);
247     assert(bmp);
248    
249     /* compute number of elements */
250     nr_elements = p0->nr_eqid * p1->nr_eqid;
251    
252     /* allocate a new RFC array */
253     rfct = rfc_alloc_array(nr_elements);
254     assert(rfct);
255     rfct->parent0 = p0;
256     rfct->parent1 = p1;
257    
258     /* make a cross product between p0 and p1 */
259     for(i=0;i<p0->nr_eqid;i++)
260     for(j=0;j<p1->nr_eqid;j++)
261     {
262     /* compute bitwise AND */
263     cbm_bitwise_and(bmp,p0->id2cbm[i],p1->id2cbm[j]);
264    
265     /* get equivalent class for this bitmap */
266     eqcl = cbm_get_eqclass(rfct,bmp);
267     assert(eqcl);
268    
269     /* fill RFC table */
270     rfct->eqID[index++] = eqcl->eqID;
271     }
272    
273     free(bmp);
274     return rfct;
275     }
276    
277     /* Compute RFC phase 0 */
278     static void ilt_phase_0(insn_lookup_t *ilt,int idx,ilt_check_cbk_t pcheck)
279     {
280     rfc_array_t *rfct;
281    
282     rfct = rfc_phase_0(ilt,pcheck);
283     assert(rfct);
284     ilt->rfct[idx] = rfct;
285     }
286    
287     /* Compute RFC phase j */
288     static void ilt_phase_j(insn_lookup_t *ilt,int p0,int p1,int res)
289     {
290     rfc_array_t *rfct;
291    
292     rfct = rfc_phase_j(ilt,ilt->rfct[p0],ilt->rfct[p1]);
293     assert(rfct);
294     ilt->rfct[res] = rfct;
295     }
296    
297     /* Postprocessing */
298     static void ilt_postprocessing(insn_lookup_t *ilt)
299     {
300     rfc_array_t *rfct = ilt->rfct[2];
301     int i;
302    
303     for(i=0;i<rfct->nr_elements;i++)
304     rfct->eqID[i] = cbm_first_match(ilt,rfct->id2cbm[rfct->eqID[i]]);
305     }
306    
307     /* Instruction lookup table compilation */
308     static void ilt_compile(insn_lookup_t *ilt)
309     {
310     ilt_phase_0(ilt,0,ilt->chk_hi);
311     ilt_phase_0(ilt,1,ilt->chk_lo);
312     ilt_phase_j(ilt,0,1,2);
313     ilt_postprocessing(ilt);
314     }
315    
316     /* Create an instruction lookup table */
317     insn_lookup_t *ilt_create(int nr_insn,ilt_get_insn_cbk_t get_insn,
318     ilt_check_cbk_t chk_lo,ilt_check_cbk_t chk_hi)
319     {
320     insn_lookup_t *ilt;
321    
322     ilt = malloc(sizeof(*ilt));
323     assert(ilt);
324     memset(ilt,0,sizeof(*ilt));
325    
326     ilt->cbm_size = normalize_size(nr_insn,CBM_SIZE,CBM_SHIFT);
327     ilt->nr_insn = nr_insn;
328     ilt->get_insn = get_insn;
329     ilt->chk_lo = chk_lo;
330     ilt->chk_hi = chk_hi;
331    
332     ilt_compile(ilt);
333     return(ilt);
334     }

  ViewVC Help
Powered by ViewVC 1.1.26