source: proto/s2k/trunk/framework/input/test/s2k/proto/grep/grep_flow.s2k @ 4009

Last change on this file since 4009 was 4009, checked in by ksherdy, 5 years ago

Added description. Initial binding strategy.

File size: 5.3 KB
Line 
1/*
2 * grep exact-string search C++ in \s2k{}.
3 *
4 * Description:
5 *
6 * The \s2k{} grep exact-string search demo is organized into the following
7 * pipeline stages.
8 * 
9 * Stage 1 - Read`
10 * Stage 2 - Transpose~
11 * Stage 3 - ClassifyBytes~
12 * Stage 4 - Match~
13 * Stage 5 - MatchLines~
14 * Stage 6 - Write`
15 *
16 * Trailing tildes characters `~' indicate pipeline stages written in \s2k{}.
17 * Trailing back ticks `'', indicate stages defined within the
18 * \s2k{} C++ templates file, 'grep.template'.
19 *
20 * The \s2k{} program defines the following program elements.
21 *
22 * 1. Stream structures Lex and Output.
23 *
24 * 2. Stream functions ClassifyBytes, Match, and MatchLines.
25 * ClassifyBytes defines \s2k{} equations for each of the character
26 * classes encountered in the fixed string `apple' and line feeds.
27 * In this example, the generation of character class bit stream
28 * equations is automated using the character class compiler tool.
29 * Match defines \s2k{} equations to match the fixed string `apple'
30 * and line feeds.
31 *
32 * 3. Stream `graph' of stream filters.
33 *
34 *
35 * The Pablo compiler translates Pablo code to C++ code as follows.
36 *
37 * 1. \s2k{} stream structures to C/C++ structures, i.e., simple data containers.
38 *
39 * 2. \s2k{} stream functions to C/C++ structures, i.e., objects with methods.
40 *    C/C++ structures are generated with `do_block', `do_final_blocks', `clear'
41 *    member functions, as well as member variables to capture
42 *    the propagation of state information across segment and register
43 *    boundaries for block-by-block stream computations.
44 *
45 * 3. \s2k{} `graph' method to sequence of stream function `do_block',
46 *    `do_final_block', and `clear' function calls.
47 */
48
49/*
50struct Basis_bits{
51    stream bit_0;
52    stream bit_1;
53    stream bit_2;
54    stream bit_3;
55    stream bit_4;
56    stream bit_5;
57    stream bit_6;
58    stream bit_7;
59};
60*/
61
62struct Lex{
63    stream a;
64    stream p;
65    stream l;
66    stream e;
67    stream LF;
68};
69
70struct Output{
71    stream match_follows;
72    stream lines;
73    stream line_starts;
74    stream line_ends;
75};
76
77filter ClassifyBytes(struct Basis_bits basis_bits, struct Lex lex) {
78    stream temp1 = (basis_bits.bit_1 & (~ basis_bits.bit_0));
79    stream temp2 = (basis_bits.bit_2 & (~ basis_bits.bit_3));
80    stream temp3 = (temp1 & temp2);
81    stream temp4 = (basis_bits.bit_4 | basis_bits.bit_5);
82    stream temp5 = (basis_bits.bit_7 & (~ basis_bits.bit_6));
83    stream temp6 = (temp5 & (~ temp4));
84    lex.a = (temp3 & temp6);
85    stream temp7 = (basis_bits.bit_2 & basis_bits.bit_3);
86    stream temp8 = (temp1 & temp7);
87    stream temp9 = (basis_bits.bit_6 | basis_bits.bit_7);
88    stream temp10 = (temp4 | temp9);
89    lex.p = (temp8 & (~ temp10));
90    stream temp11 = (basis_bits.bit_4 & basis_bits.bit_5);
91    stream temp12 = (temp11 & (~ temp9));
92    lex.l = (temp3 & temp12);
93    stream temp13 = (basis_bits.bit_5 & (~ basis_bits.bit_4));
94    stream temp14 = (temp13 & temp5);
95    lex.e = (temp3 & temp14);
96    stream temp15 = (basis_bits.bit_0 | basis_bits.bit_1);
97    stream temp16 = (basis_bits.bit_2 | basis_bits.bit_3);
98    stream temp17 = (temp15 | temp16);
99    stream temp18 = (basis_bits.bit_4 & (~ basis_bits.bit_5));
100    stream temp19 = (basis_bits.bit_6 & (~ basis_bits.bit_7));
101    stream temp20 = (temp18 & temp19);
102    lex.LF = (temp20 & (~ temp17));
103}
104
105filter Match(struct Lex lex, struct Output output) {
106    stream cursor = flow.Advance(lex.a);
107    cursor = flow.Advance((cursor & lex.p));
108    cursor = flow.Advance((cursor & lex.p));
109    cursor = flow.Advance((cursor & lex.l));
110    cursor = flow.Advance((cursor & lex.e));
111    output.match_follows = cursor;
112}
113
114filter MatchLines(struct Lex lex, struct Output output) {
115    stream all_line_starts = (flow.ScanToFirst((~ lex.LF)) | (flow.Advance(lex.LF) & (~ lex.LF)));
116    stream all_line_ends = lex.LF;
117    stream last_line_start = flow.ScanToFirst(all_line_starts);
118    stream cursor = last_line_start;
119    while (flow.inFile(cursor)) {
120        if ((cursor & all_line_starts)) {
121            last_line_start = cursor;
122        }
123        if ((cursor & output.match_follows)) {
124            cursor = flow.ScanTo(cursor, lex.LF);
125            output.lines |= flow.InclusiveSpan(last_line_start, cursor);
126        }
127        cursor = flow.AdvanceThenScanTo(cursor, (all_line_starts | output.match_follows));
128    }
129    output.line_starts = (output.lines & all_line_starts);
130    output.line_ends = flow.ScanTo(output.line_starts, (output.lines & all_line_ends));
131}
132
133// pgather
134/*
135filter Write(struct Output output) {
136  stream<8> lines = pgather<8>(output.lines);
137  write<8>(oaddr, lines);
138}
139*/
140
141// post-processing
142/*
143filter Write(struct Output output) {
144  write<1>(oaddr, output.line_starts);
145  write<1>(oaddr, output.line_ends);
146  write<1>(oaddr, output.match_follows);
147}
148*/
149
150graph Main() {
151
152    // char * byte_data;
153    struct Basis_bits basis_bits;
154    struct Lex lex;
155    struct Output output;
156   
157//  filter Read src;
158    filter Transpose transpose;
159    filter ClassifyBytes classifyBytes;
160    filter Match match;
161    filter MatchLines matchLines;
162//  filter Write snk; // bind<1>(output.line_starts, line_starts); bind<1>(output.line_ends, line_ends); bind<1>(output.match_follows, match_follows);
163
164//  read();
165    transpose(byte_data, basis_bits);
166    classifyBytes(basis_bits, lex);
167    match(lex, output);
168    matchLines(lex, output);
169//  write(output);
170   
171}
172
Note: See TracBrowser for help on using the repository browser.