Changeset 2023 for proto/parabix2


Ignore:
Timestamp:
Apr 13, 2012, 6:04:59 AM (7 years ago)
Author:
cameron
Message:

Scan and Span operations

File:
1 edited

Legend:

Unmodified
Added
Removed
  • proto/parabix2/pablo.py

    r1987 r2023  
    9696                strm >>= 1
    9797        return zeroes
    98        
     98#
     99#
     100#  Are there any bits in a stream
     101def any(strm):
     102        return strm != 0
    99103#
    100104#  ScanThru is the core operation for parallel scanning.
     
    118122def AdvancebyPos(stream, pos):
    119123        return stream << pos
     124
     125
     126#
     127# Advance-and-Scan
     128#
     129# These are common and useful operations, with a slight
     130# optimization to avoid a separate Advance.   
     131#
     132# Warning:  they each require a "separation" property
     133# between markers and scanclass streams.   This property
     134# normally seems to hold in our applications, but we should
     135# work out methods for formally establishing it.
     136#
     137# AdvanceThenScanThru(marker, scanclass)
     138# optimizes: ScanThru(Advance(marker), scanclass)
     139# requires: scanclass-marker separation: no occurrence of
     140# a marker immediately after a scanclass run.  That is,
     141# any(Advance(scanclass) & marker) == False
     142# (this is a sufficient precondition, but maybe not weakest.)
     143#
     144def AdvanceThenScanThru(marker, scanclass):     
     145        return ScanThru(marker, marker | scanclass)
     146#
     147# AdvanceThenScanTo(marker, scanclass)
     148# optimizes: ScanTo(Advance(marker), scanclass)
     149# requires: scanclass existence between markers
     150
     151def AdvanceThenScanTo(marker, scanclass):
     152        return ScanTo(marker, scanclass &~ marker)
     153
     154#
     155# Span operations
     156# These operations define spans of positions from
     157# starting to ending positions.
     158# Requirement:  start and end positions are properly
     159# matched: popcount(ends)==popcount(starts) and
     160# nth-one(starts, n) < nth-one(ends, n), if n < popcount(starts)
     161# nth-one(ends, n) < nth-one(starts, n+1) if n < popcount(starts)
     162
     163def SpanUpTo(starts, ends):
     164        return (ends - starts)
     165
     166def InclusiveSpan(starts, ends):
     167        return (ends - starts) | ends
     168
     169def ExclusiveSpan(starts, ends):
     170        return (ends - starts) &~ starts
     171
     172
     173
     174
     175
     176
    120177
    121178
Note: See TracChangeset for help on using the changeset viewer.