/[dynamips]/upstream/dynamips-0.2.5/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

Contents of /upstream/dynamips-0.2.5/insn_lookup.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (show annotations)
Sat Oct 6 16:01:44 2007 UTC (16 years, 5 months ago) by dpavlin
File MIME type: text/plain
File size: 7880 byte(s)
import 0.2.5 from upstream

1 /*
2 * Cisco 7200 (Predator) simulation platform.
3 * 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