source: proto/s2k/trunk/demo/grep/grep_demo.py @ 4053

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

Consolidated s2k demos.

File size: 5.7 KB
Line 
1#
2# grep - A very simple example to demonstrate 'fixed-string' grep with parallel bit streams.
3#'
4#        This prototypes demonstrates a compilable prototype with
5#        minimal reliance on complementary hand-written template code.
6#        In addition, this examples draws attention to missing features in the Pablo
7#        language which prevent the elimination of hand-written templates.
8#
9
10import sys
11from lib import pablo
12from lib import bitutil
13import optparse
14import grep_demo_config
15
16class Basis(): 
17        bit_0 = 0
18        bit_1 = 0
19        bit_2 = 0
20        bit_3 = 0
21        bit_4 = 0
22        bit_5 = 0
23        bit_6 = 0
24        bit_7 = 0
25
26class Lex():
27        a  = 0
28        p  = 0
29        l  = 0
30        e  = 0
31        LF = 0
32       
33class Output():
34        match_follows   = 0
35        lines                   = 0
36        line_starts             = 0
37        line_ends               = 0
38
39def ClassifyBytes(basis_bits, lex): 
40        temp1 = (basis_bits.bit_1 &~ basis_bits.bit_0)
41        temp2 = (basis_bits.bit_2 &~ basis_bits.bit_3)
42        temp3 = (temp1 & temp2)
43        temp4 = (basis_bits.bit_4 | basis_bits.bit_5)
44        temp5 = (basis_bits.bit_7 &~ basis_bits.bit_6)
45        temp6 = (temp5 &~ temp4)
46        lex.a = (temp3 & temp6)
47        temp7 = (basis_bits.bit_2 & basis_bits.bit_3)
48        temp8 = (temp1 & temp7)
49        temp9 = (basis_bits.bit_6 | basis_bits.bit_7)
50        temp10 = (temp4 | temp9)
51        lex.p = (temp8 &~ temp10)
52        temp11 = (basis_bits.bit_4 & basis_bits.bit_5)
53        temp12 = (temp11 &~ temp9)
54        lex.l = (temp3 & temp12)
55        temp13 = (basis_bits.bit_5 &~ basis_bits.bit_4)
56        temp14 = (temp13 & temp5)
57        lex.e = (temp3 & temp14)
58        temp15 = (basis_bits.bit_0 | basis_bits.bit_1)
59        temp16 = (basis_bits.bit_2 | basis_bits.bit_3)
60        temp17 = (temp15 | temp16)
61        temp18 = (basis_bits.bit_4 &~ basis_bits.bit_5)
62        temp19 = (basis_bits.bit_6 &~ basis_bits.bit_7)
63        temp20 = (temp18 & temp19)
64        lex.LF = (temp20 &~ temp17)
65       
66def Match(lex, output):
67#   Mark '_follows'
68        cursor = pablo.Advance(lex.a)
69        cursor = pablo.Advance(cursor & lex.p)
70        cursor = pablo.Advance(cursor & lex.p)
71        cursor = pablo.Advance(cursor & lex.l)
72        cursor = pablo.Advance(cursor & lex.e)
73        output.match_follows = cursor
74
75#   Mark '_ends'
76#       m0 = lex.a
77#       m1 = pablo.Advance(m0) & lex.p
78#       m2 = pablo.Advance(m1) & lex.p
79#       m3 = pablo.Advance(m2) & lex.l
80#       m4 = pablo.Advance(m3) & lex.e
81#       output.matches = m4
82
83def MatchLines(lex, output):
84       
85        all_line_starts   = pablo.ScanToFirst(~lex.LF) | (pablo.Advance(lex.LF) &~ lex.LF)
86        all_line_ends     = lex.LF
87
88        last_line_start   = pablo.ScanToFirst(all_line_starts) 
89        cursor            = last_line_start
90
91        while(pablo.inFile(cursor)):
92               
93                if(cursor & all_line_starts):
94                        last_line_start = cursor
95                       
96                if(cursor & output.match_follows):
97                        cursor = pablo.ScanTo(cursor, lex.LF)
98                        output.lines |= pablo.InclusiveSpan(last_line_start, cursor) 
99               
100                cursor = pablo.AdvanceThenScanTo(cursor, all_line_starts | output.match_follows)
101
102        output.line_starts = output.lines & all_line_starts
103        output.line_ends   = pablo.ScanTo(output.line_starts, output.lines & all_line_ends)
104
105# Progressively marks line_starts and line_ends.
106def MatchLines2(lex, output):
107
108        all_line_starts   = pablo.ScanToFirst(~lex.LF) | (pablo.Advance(lex.LF) &~ lex.LF)
109        all_line_ends     = lex.LF
110
111        last_line_start   = pablo.ScanToFirst(all_line_starts) 
112        cursor            = last_line_start
113
114        while(pablo.inFile(cursor)):
115               
116                if(cursor & all_line_starts):
117                        last_line_start = cursor
118                       
119                if(cursor & output.match_follows):
120                        output.line_starts |= last_line_start                   
121                        cursor = pablo.ScanTo(cursor, lex.LF)
122                        output.line_ends |= cursor
123                        output.lines |= pablo.InclusiveSpan(last_line_start, cursor) # LF | match
124               
125                cursor = pablo.AdvanceThenScanTo(cursor, all_line_starts | output.match_follows)
126               
127def FilterMatchLines(data, output):
128        output.byte_data = pablo.filter_bytes(data, ~output.lines)
129        # output.byte_data = pablo.filter_bytes(data, ~output.lines)                                                            # LF
130
131def CountLines(lex, output):
132        ### return pablo.PopCount(pablo.MatchStar(output.lines, ~lex.LF) & lex.LF)  # LF
133        return pablo.PopCount(output.lines & lex.LF)                                                                                                                            # LF
134        # return pablo.PopCount(pablo.Advance(output.lines) & lex.LF)                                           # no LF
135
136basis_bits      = Basis()
137lex                 = Lex()
138output          = Output()
139
140if __name__ == "__main__":
141
142        option_parser = grep_demo_config.get_option_parser() 
143        options, args = option_parser.parse_args(sys.argv[1:])
144
145        if len(args) != 1:
146                option_parser.print_usage()
147                sys.exit()
148        else:
149                input_file = args[0]
150
151  # ReadStreamInput(data)
152        global data
153        data = bitutil.readfile(input_file)
154 
155        global lgth
156        lgth = len(data)
157
158  # Transpose(data, basis)
159        pablo.EOF_mask = pablo.transpose_streams(data, basis_bits)
160        ClassifyBytes(basis_bits, lex)
161        Match(lex, output)
162        #MatchLines(lex, output)
163        MatchLines2(lex, output)
164
165  # WriteStreamOutput(Output)
166        if(options.count):
167          print str(CountLines(lex, output))
168
169        elif(options.invertMatch):
170            output.lines = ~output.lines                                                                        # LF
171            # output.lines = (~output.lines) &~ lex.LF          # no LF
172            FilterMatchLines(data, output)
173            print output.byte_data
174        else:
175            FilterMatchLines(data, output)
176            print output.byte_data
177
178        if(options.debug):
179                print ""
180                print "data.replace('LF','$')   " + data.replace("\n","$")
181                print "lex.a                    " + bitutil.bitstream2string(lex.a, lgth)
182                print "lex.p                    " + bitutil.bitstream2string(lex.p, lgth)
183                print "lex.l                    " + bitutil.bitstream2string(lex.l, lgth)
184                print "lex.e                    " + bitutil.bitstream2string(lex.e, lgth)
185                print "lex.LF                   " + bitutil.bitstream2string(lex.LF, lgth)
186                print "output.match_follows     " + bitutil.bitstream2string(output.match_follows, lgth)
187                print "output.line_starts       " + bitutil.bitstream2string(output.line_starts, lgth)
188                print "output.line_ends         " + bitutil.bitstream2string(output.line_ends, lgth)
189                print "output.lines             " + bitutil.bitstream2string(output.lines, lgth)
190                print ""
191
192        #lgth = len(data)
193
194
195               
196       
197
198
Note: See TracBrowser for help on using the repository browser.