trie.cpp revision 12855:588919e0e4aa 
1#include <stdio.h>
2#include "systemc.h"
3
4SC_MODULE(lc)
5{
6	sc_out<bool> DIN_rdy;
7	sc_in<bool>  DIN_vld;
8#define LOAD_ADDR   0
9#define LOAD_DATA   1
10#define LOOKUP 2 // really op(1) == 1 and op(0) - don't care
11	sc_in<sc_uint<2> >  DIN_op;
12	sc_in<sc_uint<32> > DIN_data_in;
13	sc_in<bool>  DOUT_rdy;
14	sc_out<bool> DOUT_vld;
15	sc_out<sc_uint<32> > DOUT_hop;
16	sc_in<bool> RSTN;
17	sc_in_clk CLK;
18
19	void thread();
20	sc_uint<20> extract(sc_uint<32>, sc_uint<7>, sc_uint<5>);
21	sc_uint<10> lookup(sc_uint<32>);
22
23	sc_uint<32> M[1024];
24	sc_uint<32>  addr;	// latched addr for loading memory
25
26	SC_CTOR(lc){
27		SC_CTHREAD(thread, CLK.pos());
28		reset_signal_is(RSTN,false);
29	}
30};
31
32//
33// this implements the level-compressed trie
34// ip routing algorithm that is proposed in:
35//
36// "Fast Address Lookup for Internet Routers"
37// Stefan Nilsson and Gunnar Karlsson
38// Proc IFIP 4th International Conference on BroadBand Communication
39// pp. 11-22, 1998
40//
41//
42void
43lc::thread()
44{
45	if( !RSTN){
46		DIN_rdy = 1;
47		DOUT_vld = 0;
48		wait(1);
49	}
50
51	for(;;){
52		bool tmp_vld;
53		bool tmp_rdy;
54		sc_uint<2> op;
55		sc_uint<32> data_in;
56		sc_uint<32> hop;
57
58                {
59                do {
60                	tmp_vld = DIN_vld.read();
61                        op = DIN_op.read();
62                        data_in = DIN_data_in.read();
63                        wait(1);
64                } while( !tmp_vld);
65                }
66
67		if( op == 0){
68			// latch address
69			addr = data_in;
70			wait(1);
71		} else if(op == 1){
72			// load memory
73			M[addr] = data_in;
74			wait(1);
75		} else if( op[1] == 1){
76			// do the ip lookup to next hop
77			hop = lookup(data_in);
78			{
79				DIN_rdy = 0;
80				do {
81					tmp_rdy = DOUT_rdy.read();
82					wait(1);
83				} while( !tmp_rdy);
84				DOUT_vld = 1;
85				DOUT_hop.write(hop);
86				DIN_rdy = 1;
87				wait(1);
88				DOUT_vld = 0;
89			}
90		}
91	}
92
93}
94
95sc_uint<20>
96lc::extract(sc_uint<32> x, sc_uint<7> p, sc_uint<5> w)
97{
98	return( (x>>(p-w+1)) & ~(~0<<w) );
99}
100
101#define BRANCH(T)	T.range(31,27)
102#define SKIP(T)		T.range(26,20)
103#define ADDR(T)		T.range(19,0)
104#define LEN(T)		T.range(31,25)
105#define NEXT_HOP(T)	T.range(24,15)
106#define NEXT_PREFIX(T)	T.range(14,0)
107
108sc_uint<10>
109lc::lookup(sc_uint<32> ip)
110{
111	sc_uint<7> pos;
112	sc_uint<5> branch;
113	sc_uint<20> addr;
114	sc_uint<32> t;
115	sc_uint<32> ip_prefix;
116	sc_uint<10> next_hop;
117	sc_uint<32> mask;
118
119	t = M[0];
120	pos = SKIP(t);
121	branch = BRANCH(t);
122	addr = ADDR(t);
123	while(branch != 0){
124		addr = addr + extract(ip, pos, branch);
125		t = M[addr];
126		pos = pos -  (branch + SKIP(t));
127		branch = BRANCH(t);
128		addr = ADDR(t);
129	}
130
131
132	next_hop = 0;
133	for(;;) {
134		addr <<= 1;
135
136		ip_prefix = M[addr];
137		t = M[addr|1];
138		mask = ~0 << (32-LEN(t));
139		if( (ip_prefix&mask) == (ip&mask)){
140			next_hop = NEXT_HOP(t);
141			break;
142		}
143		addr = NEXT_PREFIX(t);
144		if( addr == 0)
145			break;
146	}
147
148	return(next_hop);
149}
150
151
152/*
153 * hop	prefix(bits 31 .. 0)
154 *  1   0000*
155 *  2   0001*
156 *  3   00101*
157 *  4   010*
158 *  5   0110*
159 *  6   0111*
160 *  7   100*
161 *  8   101000*
162 *  9   101001*
163 * 10   10101*
164 * 11   10110*
165 * 12   10111*
166 * 13   110*
167 * 14   11101000*
168 * 15   11101001*
169 *
170 * "not in table" produces a hop of 0
171 */
172
173#define TRIE(LN, SK, AD) \
174  ((((LN)&0x1f)<<27) | (((SK)&0x7f)<<20) | ((AD)&0xfffff))
175#define E(LN, NHP, NPX) \
176  ((((LN)&0x7f)<<25) | (((NHP)&0x3ff)<<15) | ((((NPX))&0x7fff)))
177
178
179#define M_SIZE 52
180sc_uint<32> M[M_SIZE] = {
181/* TRIE */
182/* 00 */ TRIE(3, 31, 1),
183/* 01 */ TRIE(1, 0, 9),
184/* 02 */ TRIE(0, 2, 2+11),
185/* 03 */ TRIE(0, 0, 3+11),
186/* 04 */ TRIE(1, 0, 11),
187/* 05 */ TRIE(0, 0, 6+11),
188/* 06 */ TRIE(2, 0, 13),
189/* 07 */ TRIE(0, 0, 12+11),
190/* 08 */ TRIE(1, 4, 17),
191/* 09 */ TRIE(0, 0, 0+11),
192/* 10 */ TRIE(0, 0, 1+11),
193/* 11 */ TRIE(0, 0, 4+11),
194/* 12 */ TRIE(0, 0, 5+11),
195/* 13 */ TRIE(1, 0, 19),
196/* 14 */ TRIE(0, 0, 9+11),
197/* 15 */ TRIE(0, 0, 10+11),
198/* 16 */ TRIE(0, 0, 11+11),
199/* 17 */ TRIE(0, 0, 13+11),
200/* 18 */ TRIE(0, 0, 14+11),
201/* 19 */ TRIE(0, 0, 7+11),
202/* 20 */ TRIE(0, 0, 8+11),
203/* 21 */ 0, 			/* pad */
204/* BASE + PREFIX */
205/* 22 */ 0x00000000, E(4, 1, 0),
206/* 24 */ 0x10000000, E(4, 2, 0),
207/* 26 */ 0x28000000, E(5, 3, 0),
208/* 28 */ 0x40000000, E(3, 4, 0),
209/* 31 */ 0x60000000, E(4, 5, 0),
210/* 32 */ 0x70000000, E(4, 6, 0),
211/* 34 */ 0x80000000, E(3, 7, 0),
212/* 36 */ 0xa0000000, E(6, 8, 0),
213/* 38 */ 0xa4000000, E(6, 9, 0),
214/* 40 */ 0xa8000000, E(5, 10, 0),
215/* 42 */ 0xb0000000, E(5, 11, 0),
216/* 44 */ 0xb8000000, E(5, 12, 0),
217/* 46 */ 0xc0000000, E(3, 13, 0),
218/* 48 */ 0xe8000000, E(8, 14, 0),
219/* 50 */ 0xe9000000, E(8, 15, 0)
220};
221
222
223struct stimuli {
224	unsigned int ip;
225	int hop;
226} S[] = {
227	{ 0xf0000000, 0 },
228	{ 0x10000000, 2 },
229	{ 0x7c000000, 6 },
230	{ 0x7c001000, 6 },
231	{ 0x7c000070, 6 },
232};
233
234int
235sc_main(int argc, char *argv[])
236{
237	sc_clock clk;
238	sc_signal<bool> reset;
239 	sc_signal<bool> in_rdy;
240        sc_signal<bool> in_vld;
241        sc_signal<bool> out_vld;
242        sc_signal<bool> out_rdy;
243        sc_signal<sc_uint<2> > op;
244        sc_signal<sc_uint<32> > data;
245        sc_signal<sc_uint<32> > hop;
246	int i;
247	int m_addr;
248	lc *lcp;
249
250	lcp = new lc("lc0");
251	(*lcp)(in_rdy, in_vld,
252	      op, data,
253	      out_rdy, out_vld,
254	      hop,
255	      reset, clk);
256
257	reset = 0;
258	sc_start(2, SC_NS);
259	reset = 1;
260	sc_start(2, SC_NS);
261	out_rdy = 1;
262
263	/*
264	 * download the RAM containing
265	 * the routing data
266	 */
267	for(i = 0, m_addr = 0; i < M_SIZE; i++, m_addr++){
268		while(!in_rdy) sc_start(1, SC_NS);
269		in_vld = 1;
270		op.write(LOAD_ADDR);
271		data.write(m_addr);
272		do { sc_start(1, SC_NS); in_vld = 0; } while(!in_rdy);
273		sc_start(1, SC_NS);
274		in_vld = 1;
275		op.write(LOAD_DATA);
276		data.write(M[m_addr]);
277		do { sc_start(1, SC_NS); in_vld = 0; } while(!in_rdy);
278		sc_start(1, SC_NS);
279	}
280
281	/*
282	 * apply some ip's and see what
283 	 * comes back as next-hops
284	 */
285	for(i = 0; i < sizeof S/sizeof(struct stimuli); i++){
286		while(!in_rdy) sc_start(1, SC_NS);
287		in_vld = 1;
288		op.write(LOOKUP);
289		data.write(S[i].ip);
290		do { sc_start(1, SC_NS); in_vld = 0; } while(!out_vld);
291		unsigned int h = hop.read();
292		if( h != S[i].hop){
293			cout << S[i].ip << " should be hop " << S[i].hop
294                             << " got hop " << h << endl;
295		}
296	}
297	cout << "program complete" << endl;
298        return 0;
299
300}
301
302
303
304
305
306
307
308
309