Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Bop is a very fast Boyer-Moore parser/matcher for String or Buffer patterns.
JavaScript Shell
Branch: opt
Pull request Compare This branch is 6 commits ahead, 54 commits behind master.

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
bench
lib
test
.gitignore
.npmignore
.travis.yml
Readme.md
index.js
package.json

Readme.md

BoyerParser

build status

  • Bop is a very fast Boyer-Moore parser for string or buffer patterns.
  • It is optimized for using with pattern strings/buffers <= 255 chars/bytes.
  • It is ideal for parsing multipart/form-data streams, that have a pattern / boundary length < ~70 bytes.

Main features

Given a m-length pattern and n-length data:

  • it performs the comparisons from right to left.
  • preprocessing phase in O(m+σ) time and space complexity.
  • searching phase in O(m*n) time complexity.
  • 3*n text character comparisons in the worst case when searching for a non periodic pattern.
  • O(n/m) best performance.

See Lecroq for reference.

Install

$ npm install bop [-g]

Run Tests

$cd bop/
$npm test

Signatures

Create an instance with a Buffer or String pattern.

Bop( String pattern )
Bop( Buffer pattern )

List all pattern occurrences into a String or Buffer data. It returns a new array of indexes, or populates an array passed as the last argument to parse method.

// slower with String
Bop.parse( String data, [ Number startFromIndex ], [ Number limitResultsTo ], [ Array array ] ) : []
// faster with Buffer
Bop.parse( Buffer data, [ Number startFromIndex ], [ Number limitResultsTo ], [ Array array ] ) : []

Change the pattern with a Buffer or String

Bop.setPattern( String anotherPattern )
Bop.setPattern( Buffer anotherPattern )

Usage Example

var assert = require( 'assert' ),
    BoyerParser = require( './bop' ).BoyerParser, // or Bop
    pattern = 'hellofolks\r\n\r\n',
    text = 'hehe' + pattern +'loremipsumhellofolks\r\n' + pattern;

// create a Bop instance that parses the pattern
var bop = BoyerParser( pattern ),
    // parse data from beginning
    results = bop.parse( text );

// change pattern with a buffer
bop.setPattern( new Buffer( pattern ) );

// re-parse data passing a Buffer instance instead of a String
var bresults = bop.parse( new Buffer( text ) );

// results are the same
assert.deepEqual( results, bresults );

// parser results ( starting indexes ) [ 4, 40 ]
console.log( results, bresults );

Benchmark for small patterns

  $ node bench/small-pattern-data-rate

for default :

  • uses a pattern string of 57 bytes/chars
  • builds a data buffer of 700 MB in memory
  • uses a redundancy factor for pattern strings. The bigger the value, the lesser are occurrences of pattern string into the text buffer. ( range: [1,5] )

Custom Usage:

  // with [NumberOfMegaBytes] [GapFactor] [patternString]
  $ node bench/small-pattern-data-rate.js 700 4 "that'sallfolks"

Benchmark for big patterns

  $ node bench/big-pattern-data-rate
  • it uses a pattern size of 20MB
  • builds a data buffer of 300MB copying pattern 12 times
Something went wrong with that request. Please try again.