Mercurial > hg > Game > Cerium

annotate example/regex_mas/ppe/Exec.cc @ 1662:d865530672fa draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix regex_mas
author Masa <e085726@ie.u-ryukyu.ac.jp>
date Tue, 16 Jul 2013 16:42:31 +0900
parents 8b50b1ee068e
children 99f8130793b4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1598
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdio.h>
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 #include <string.h>
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 #include "Exec.h"
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 #include "Func.h"
1638
aa967337bda2 fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1634
diff changeset
5 #include "SchedTask.h"
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
6 #define max(a,b)((a)>(b)?a:b)
1630
d2581892b8ad fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1623
diff changeset
7
1598
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 /* これは必須 */
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 SchedDefineTask(Exec);
1630
d2581892b8ad fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1623
diff changeset
10
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
11 //ボイヤームーア法による文字列検索アルゴリズム
1655
963d2fc5f685 push (but can't run regex_mas)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1652
diff changeset
12 int BM_method(unsigned char *text,int *offset,int *text_length,
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
13 unsigned char *pattern,unsigned long long *match_string)
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
14 {
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
15 int skip[256];
1655
963d2fc5f685 push (but can't run regex_mas)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1652
diff changeset
16 int text_len = (long int)text_length;
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
17 int pattern_len = strlen((char *)pattern);
1623
f82467ce38f3 fix regex_mas/ppe/Exec.cc . Convert char to unsigned char.
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1621
diff changeset
18 int i = 0;
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
19 int match_counter = 0;
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
20
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
21 for (i = 0; i < 256; ++i){
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
22 skip[i] = pattern_len;
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
23 }
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
24
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
25 for (i = 0; i < pattern_len-1 ; ++i){
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
26 skip[(int)pattern[i]] = pattern_len - i - 1;
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
27 }
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
28
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
29 i = pattern_len - 1;
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
30
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
31 while ( i < text_len){
1623
f82467ce38f3 fix regex_mas/ppe/Exec.cc . Convert char to unsigned char.
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1621
diff changeset
32 int j = pattern_len - 1;
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
33 while (text[i] == pattern[j]){
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
34 if (j == 0){
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
35 match_counter++;
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
36 }
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
37 --i;
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
38 --j;
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
39 }
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
40 i = i + max((int)skip[(int)text[i]],pattern_len - j);
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
41 }
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
42 return match_counter;
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
43 }
1598
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 static int
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 run(SchedTask *s, void *rbuf, void *wbuf)
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 {
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
48 unsigned char *i_data = (unsigned char *)rbuf;
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
49 unsigned long long *o_data = (unsigned long long*)wbuf;
1655
963d2fc5f685 push (but can't run regex_mas)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1652
diff changeset
50 int *length = (int*)s->get_param(0);
1651
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1650
diff changeset
51 int *offset = (int*)s->get_param(1);
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
52 unsigned char search_word[] = "aba";
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
53
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
54 o_data[0] = BM_method(i_data,offset,length,search_word,o_data);
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
55
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
56 s->printf("%d\n",o_data[0]);
1645
4698c92bf2ca Regex_mas implement time measurement.
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1644
diff changeset
57 //s->printf("in Exec.cc\n");
1621
f907bbac14f2 Implement Boyer-Moore String Search Algorithm.(But incomplete divided file point)
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1620
diff changeset
58
1662
d865530672fa fix regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents: 1660
diff changeset
59
1598
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 return 0;
0f94d9d580f9 add regex_mas
Masa <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 }