use strict;
use warnings;
use Math::GMPz qw(:mpz);
use Time::HiRes;

use Inline C => Config =>
  USING => 'ParseRegExp',
  BUILD_NOISY => 1,
  INC =>  '-IC:/MinGW/msys/1.0/local/include',
  LIBS => '-LC:/MinGW/msys/1.0/local/lib -lgmp',
  TYPEMAPS => './typemap', # ships with Math::GMPz
  ;

use Inline C => <<'EOC';

#include <gmp.h>

int start(mpz_t * haystack, int haystack_size,
          mpz_t * needle, int needle_size) {

  int h_bit, n_bit, nless1 = needle_size -1;

  for(h_bit = nless1; h_bit < haystack_size; h_bit++) {
    for(n_bit = 0; n_bit < needle_size; n_bit++) {
      if(mpz_tstbit(*haystack, h_bit - needle_size + n_bit) !=
         mpz_tstbit(needle, n_bit)) break;
      if(n_bit == nless1) return h_bit;
    }
  }
  return 0;

}

EOC

my ($t1, $t2, $match);
my ($haystack_size, $needle_size) = (250e6, 1e6);

# generate the haystack - takes a while
my $h_string = rstring($haystack_size);

# generate a needle that's guaranteed to match , starting
# at 19 bits from the lh end - ie at bit 249999981
my $n_string = substr($h_string, 19, $needle_size);

# create the haystack gmp vector. (We need an additional
# leading "1" bit to ensure that leading zero bits aren't ignored.)
my $haystack = Math::GMPz->new( "1" . $h_string , 2);

# create the needle gmp vector. (We need an additional
# leading "1" bit to ensure that leading zero bits aren't ignored.)
my $needle = Math::GMPz->new("1" . $n_string, 2);

# Check that we've got the right number of bits. 
print Rmpz_sizeinbase($haystack, 2), " ",
        Rmpz_sizeinbase($needle, 2), "\n";

$t1 = Time::HiRes::time();
$match = start($haystack, $haystack_size, $needle, $needle_size);
$t2 = Time::HiRes::time();
print $match, " ", $t2 - $t1, "\n";

sub rstring {
  die "haystack size must be a multiple of 10"
    if $_[0] % 10;
  my $ret;
  my $its = $_[0] / 10;
  $ret .= sprintf("%010b",int rand 1024) for 1 .. $its;
  if(length($ret) != $_[0] || $ret =~ /[^01]/) {
    die "Error in sub rstring";
  }
  return $ret;
}

# Outputs:
# 250000001 1000001
# 249999981 3.16680598258972