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