7731l1.txt0100664000175300003300000000033110152740121011431 0ustar jillljedit void BF(char *x, int m, char *y, int n) { int i, j; /* Searching */ for (j = 0; j <= n - m; ++j) { for (i = 0; i < m && x[i] == y[i + j]; ++i); if (i >= m) { OUTPUT(j); } } } 7731l2.txt0100664000175300003300000001673510152740121011451 0ustar jillljedit #include /* Prototypes for inlined routines */ void search (int firstpass, uint64_t texta, uint64_t textb, uint64_t textc, uint64_t pattern, int *result); void compare (char a0,char a1,char a2,char a3,char a4,char a5,char a6,char a7, char b0,char b1,char b2,char b3,char b4,char b5,char b6,char b7, int *r); /* The Brute Force text search algorithm for the MAP */ void BF(long long Text[], int m, long long Patterns[], int n, int *found, int mapid) { int i, j; int find; int starting; int vld; uint64_t evalue0,value0,evalue1,value1; uint64_t text; int result0,result1,result2,result3,result4; int result5,result6,result7,result8,result9; uint64_t pattern0,pattern1,pattern2,pattern3,pattern4; uint64_t pattern5,pattern6,pattern7,pattern8,pattern9; OBM_BANK_A (al, long long, MAX_OBM_SIZE) OBM_BANK_B (bl, long long, MAX_OBM_SIZE) find = 0; i = 0; starting = 1; /* * Initiate a transfer from the microprocessor memory * to the MAP. This is a streaming transfer that does not * get buffered into Onboard Memory. Instead it stransfers * through 2 64 bit words in 2 banks giving maximum bandwidth. * A valid bit (vld) is set whenever valid data can be picked up. */ DMA_CPU_STREAM (CM2OBM,al, MAP_OBM_stripe(0,"A,B"), Patterns, 1, m, 0); /* * This loop continues until all of the requested search patterns * have been streamed into the scalars: pattern0 ... pattern9 do { /* * Here is the actual receipt of streaming data */ recv_stream_from_dma_a_and_b (&al[0], &value0, &value1, &vld); if (vld) { if(i == 0) {pattern0 = value0; pattern1 = value1;} if(i == 2) {pattern2 = value0; pattern3 = value1;} if(i == 4) {pattern4 = value0; pattern5 = value1;} if(i == 6) {pattern6 = value0; pattern7 = value1;} if(i == 8) {pattern8 = value0; pattern9 = value1;} } /* * Use an accumulator functional unit to increment the * loop variable "i" thus avoiding a loop carried scalar * dependency and consequent loop slowdown. */ cg_accum_add_32_np (2, vld, 0, starting, &i); starting = 0; } while (i < m/8); j = 0; starting = 1; text = 0; /* * Initiate a streaming stransfer for the 20MB of text to be searched */ DMA_CPU_STREAM (CM2OBM,al, MAP_OBM_stripe(0,"A,B"), Text, 1, n, 1); /* * This is the main loop for processing the text to be searched. * This loop continues until all 20MB of data has streamed through * the search logic. */ do { /* * Text to be searched is presented 2 words at a time. */ recv_stream_from_dma_a_and_b (&al[0], &evalue0, &evalue1, &vld); cg_accum_add_32_np (2, vld, 0, starting, &j); // increment loop index if (vld) { /* * If a DES key is provided, the incomong Text is encrypted. * The des routines are provided as a Verilog macro that is * integrated at compile time. des is pipelined and therefore * has minimal impact on the compute time for the 20MB Text. */ if (key) { des(evalue0,key,1,&value0); des(evalue1,key,1,&value1); } /* * The actual search for any of the 10 patterns is done * here. Note that since there is no data dependency * all of these 10 searches can actually occur in parallel. * This is accomplished by inlining the search routine. * There will be 10 intantiations of the search that can * all proceed in parallel. */ search (starting, text, value0, value1, pattern0, &result0); search (starting, text, value0, value1, pattern1, &result1); search (starting, text, value0, value1, pattern2, &result2); search (starting, text, value0, value1, pattern3, &result3); search (starting, text, value0, value1, pattern4, &result4); search (starting, text, value0, value1, pattern5, &result5); search (starting, text, value0, value1, pattern6, &result6); search (starting, text, value0, value1, pattern7, &result7); search (starting, text, value0, value1, pattern8, &result8); search (starting, text, value0, value1, pattern9, &result9); /* * Here we just accumulate the number of finds that each * search routine has come up with. */ cg_accum_add_32_np (result0+result1+result2+result3+result4+ result5+result6+result7+ result8+result9, 1, 0, starting, &find); text = value1; } starting = 0; } while (j < n/8); *found = find; } /* * The search routine uses a brute force search. This is actually very fast because * the comparisons can all be done in parallel. */ void search (int firstpass, uint64_t texta, uint64_t textb, uint64_t textc, uint64_t pattern, int *result) { char p0, p1, p2, p3, p4, p5, p6, p7; char t0, t1, t2, t3, t4, t5, t6, t7; char t8, t9, ta, tb, tc, td, te, tf; char tg, th, ti, tj, tk, tl, tm, tn; int r0, r1, r2, r3, r4, r5, r6, r7; int r8, r9, ra, rb, rc, rd, re, rf; /* * Split the 64 bit Text and Search Pattern out into bytes * to make the comparisons simple *. split_64to8(pattern,&p7,&p6,&p5,&p4,&p3,&p2,&p1,&p0); split_64to8(texta, &t7,&t6,&t5,&t4,&t3,&t2,&t1,&t0); split_64to8(textb, &tf,&te,&td,&tc,&tb,&ta,&t9,&t8); split_64to8(textc, &tn,&tm,&tl,&tk,&tj,&ti,&th,&tg); /* * Do parallel Search Pattern comparisons in every starting position * across 16 byte positions of the Text. Note that this allows * finding overlapping patterns. Notice that there are no data * dependencies among the compare routines input. Therefore all * of the compares can occur in parallel. The compare routines is * inlined, creating 16 instantiations of the resulting logic. */ if (firstpass == 0) { /* On the 1st time through we only have 2 64 bit wds of text. * After the 1st time, we always have 3 64 bit wds of text * to work on. */ compare(t0,t1,t2,t3,t4,t5,t6,t7,p0,p1,p2,p3,p4,p5,p6,p7,&r0); compare(t1,t2,t3,t4,t5,t6,t7,t8,p0,p1,p2,p3,p4,p5,p6,p7,&r1); compare(t2,t3,t4,t5,t6,t7,t8,t9,p0,p1,p2,p3,p4,p5,p6,p7,&r2); compare(t3,t4,t5,t6,t7,t8,t9,ta,p0,p1,p2,p3,p4,p5,p6,p7,&r3); compare(t4,t5,t6,t7,t8,t9,ta,tb,p0,p1,p2,p3,p4,p5,p6,p7,&r4); compare(t5,t6,t7,t8,t9,ta,tb,tc,p0,p1,p2,p3,p4,p5,p6,p7,&r5); compare(t6,t7,t8,t9,ta,tb,tc,td,p0,p1,p2,p3,p4,p5,p6,p7,&r6); compare(t7,t8,t9,ta,tb,tc,td,te,p0,p1,p2,p3,p4,p5,p6,p7,&r7); } else { r0 = 0; r1 = 0; r2 = 0; r3 = 0; r4 = 0; r5 = 0; r6 = 0; r7 = 0; } compare(t8,t9,ta,tb,tc,td,te,tf,p0,p1,p2,p3,p4,p5,p6,p7,&r8); compare(t9,ta,tb,tc,td,te,tf,tg,p0,p1,p2,p3,p4,p5,p6,p7,&r9); compare(ta,tb,tc,td,te,tf,tg,th,p0,p1,p2,p3,p4,p5,p6,p7,&ra); compare(tb,tc,td,te,tf,tg,th,ti,p0,p1,p2,p3,p4,p5,p6,p7,&rb); compare(tc,td,te,tf,tg,th,ti,tj,p0,p1,p2,p3,p4,p5,p6,p7,&rc); compare(td,te,tf,tg,th,ti,tj,tk,p0,p1,p2,p3,p4,p5,p6,p7,&rd); compare(te,tf,tg,th,ti,tj,tk,tl,p0,p1,p2,p3,p4,p5,p6,p7,&re); compare(tf,tg,th,ti,tj,tk,tl,tm,p0,p1,p2,p3,p4,p5,p6,p7,&rf); *result = r0+r1+r2+r3+r4+r5+r6+r7+r8+r9+ra+rb+rc+rd+re+rf; } /* * The compare routine simply does a byte by byte compare and returns * a zero, non-zero result. */ void compare (char a0,char a1,char a2,char a3,char a4,char a5,char a6,char a7, char b0,char b1,char b2,char b3,char b4,char b5,char b6,char b7, int *r) { /* * Note that al of the "=="'s are done by multiple pipelined functional * units operating in parallel. So the comparison takes 1 clock cycle. */ *r = ((a0==b0)&(a1==b1)&(a2==b2)&(a3==b3)& (a4==b4)&(a5==b5)&(a6==b6)&(a7==b7)); } 7731l3.txt0100664000175300003300000000266710152740121011451 0ustar jillljedit#define ASIZE 50 #define XSIZE 50 int MAX(int i, int j); void OUTPUT(int i); void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; } void suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { OUTPUT(j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); } }