File Coverage

blib/lib/Crypt/IDA.pm

Criterion	Covered	Total	%
statement	398	546	72.8
branch	152	258	58.9
condition	109	237	45.9
subroutine	29	30	96.6
pod	3	16	18.7
total	691	1087	63.5

package Crypt::IDA;

use 5.008008;
use strict;
use warnings;

use Carp;
use Fcntl qw(:DEFAULT :seek);
use Math::FastGF2 qw(:ops);
use Math::FastGF2::Matrix;

use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS $VERSION);

require Exporter;

our @export_default = qw(fill_from_string fill_from_fh
			 fill_from_file empty_to_string
			 empty_to_fh empty_to_file
			 ida_split ida_combine);
our @export_extras  = qw(ida_rng_init ida_fisher_yates_shuffle
			 ida_generate_key ida_check_key
			 ida_key_to_matrix ida_check_transform_opts
			 ida_check_list);

our @ISA = qw(Exporter);
our %EXPORT_TAGS = ( 'default' => [ @export_default ],
		     'extras'  => [ @export_extras  ],
		     'all'     => [ @export_extras, @export_default  ] );
our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );
our @EXPORT = qw( );

our $VERSION = '0.01';

# hard-coding module names is supposedly not good style, but at least
# I'm up-front about breaking that "rule":
our $classname="Crypt::IDA";

sub fill_from_string {
  # Allow calling as a regular sub call or as a method. This might not
  # be a good style to use, but it allows callers to use either the
  # exported name, as in $f=fill_from_string(...) or to avoid
  # exporting any method names and use the fully-qualified call
  # $f=Crypt::IDA::fill_from_string(...) without needing to worry
  # about the extra class name parameter.  Of course, this means that
  # if the user wants to use the class name as the first input
  # parameter, they'll have to specify it twice. A similar pattern is
  # used in other routines in this module.
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    # we won't actually use the $self->method() style of calling, but
    # with this pattern we could if we wanted to.
    $self=$classname;
    $class=$classname;
  }
  my $s     = shift;
  my $align = shift || 1;

  # There's a one-line (non-looping) way of doing the following, but
  # writing it as a loop is simpler to understand and hence less prone
  # to errors
  while ((length $s) % $align) { $s.="\0" }
  return {
	  SUB => sub {
	    my $bytes=shift;
	    # substr returns an empty string if input is empty
	    return substr $s, 0, $bytes, "";
	  }
	 };
}

sub empty_to_string {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my $strref=shift;

  return {
	  SUB => sub {
	    my $str=shift;
	    $$strref.=$str;
	    return length $str;
	  }
	 };
}

sub fill_from_fh {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my $fh=shift;
  my $align=shift || 0;
  my $offset=shift || 0;
  my $eof=0;
  my $bytes_read=0;

  if ($offset) { sysseek $fh, $offset, SEEK_SET; }

  return {
	  SUB => sub {
	    my $bytes = shift;
	    my $buf = "";
	    if ($bytes < 0) {
	      carp "Asked to read $bytes bytes\n";
	    }
	    my $rc = sysread $fh, $buf, $bytes;

	    if ($rc == 0) {
	      if ($align) {
		while ($bytes_read % $align and
		       length($buf) < $bytes) {
		  $buf.="\0";
		  ++$bytes_read;
		}
	      }
	    } elsif ($rc < 0) {
	      return undef;
	    } else {
	      $bytes_read+=$rc;
	    }
	    return $buf;
	  }
	 };
}

sub fill_from_file {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my $filename = shift;
  my $align    = shift || 0;
  my $offset   = shift || 0;
  my $fh;

  return undef  unless (sysopen $fh, $filename, O_RDONLY);
  return fill_from_fh($fh,$align,$offset);
}

sub empty_to_fh {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my $fh     = shift;
  my $offset = shift || 0;

  #warn "got fh=$fh; offset=$offset\n";
  sysseek $fh, $offset, SEEK_SET if $offset;
  return {
	  SUB => sub {
	    my $str=shift;
	    return syswrite $fh, $str;
	  }
	 };
}

sub empty_to_file {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my $filename = shift;
  my $perm     = shift || 0644;
  my $offset   = shift || 0;
  my $fh;

  return undef unless
    sysopen $fh, $filename, O_CREAT | O_WRONLY, $perm;
  return $self->empty_to_fh($fh, $offset);
}

# ida_process_streams is the heart of the module. It's called from
# both ida_split and ida_combine, so it's capable of operating with
# just one or several fillers/emptiers. Its main purpose is to manage
# the input/output buffers, and it calls the external matrix multiply
# code to actually transform blocks of data in large chunks. For
# efficiency, it has some requirements on the organisation of
# input/output buffer matrices. It also delegates the task of
# reading/writing data to relatively simple user-supplied callbacks.
# This module isn't intended to be called by users directly, though,
# so it's not even documented in the POD section. Even though
# technically this could be useful if the user wanted to specify their
# own input/output matrices, there's so little error-checking of
# parameters here that it's probably best not to mention its
# existence/availability.
sub ida_process_streams {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my ($xform, $in, $fillers, $out, $emptiers, $bytes_to_read,
     $inorder, $outorder)=@_;

  # default values are no byte-swapping, read bytes until eof
  $inorder=0         unless defined($inorder);
  $outorder=0        unless defined($outorder);
  $bytes_to_read = 0 unless defined($bytes_to_read);

  my $bytes_read=0;
  my ($IR, $OW);		# input read, output write pointers
  my ($ILEN, $OLEN);
  my ($IFmin, $OFmax);		# input and output buffer fill levels
  my ($want_in_size, $want_out_size);

  my ($eof, $rc, $str, $max_fill, $max_empty);
  my $width=$in->WIDTH;
  my $bits=$width << 3;
  my $rows=$in->ROWS;

  my $nfillers  = scalar(@$fillers);
  my $nemptiers = scalar(@$emptiers);
  my ($idown,$odown);
  my ($iright,$oright);
  my ($rr,$cc);
  my ($i, $k);
  my ($start_in_col,$start_out_col);

  #warn "-------------------------------------\n";
  #warn "Asked to process $bytes_to_read bytes\n";
  #warn "Input cols is " .$in->COLS. ", Output cols is " . $out->COLS . "\n";
  #warn "Inorder is $inorder, Outorder is $outorder\n";
  #warn "There are $nfillers fillers, $nemptiers emptiers\n";

  if ($bytes_to_read % ($width * $xform->COLS)) {
    carp "process_streams: bytes to read not a multiple of COLS * WIDTH";
    return undef;
  }
  unless ($nfillers == 1 or $nfillers==$in->ROWS) {
    carp "Fillers must be 1 or number of input rows";
    return undef;
  }
  unless ($nemptiers == 1 or $nemptiers == $out->ROWS) {
    carp "Emptiers must be 1 or number of output rows";
    return undef;
  }


  ($IFmin, $OFmax, $IR, $OW) = (0,0,0,0);
  if ($nfillers == 1) {
    if ($in->ORG ne "colwise" and $in->ROWS != 1) {
      carp "Need a 'colwise' input matrix with a single filler";
      return undef;
    }
    $ILEN=$rows * $in->COLS * $width;
    $idown=$width;
    $iright=$in->ROWS * $width;
    $want_in_size = $width * $rows;
  } else {
    if ($in->ORG ne "rowwise" and $in->ROWS != 1) {
      carp "Need a 'rowwise' input matrix with multiple fillers";
      return undef;
    }
    $ILEN=$in->COLS * $width;
    $idown=$ILEN;
    $iright=$width;
    $want_in_size = $width;
  }
  for my $i (0 .. $nfillers - 1) {
    $fillers->[$i]->{"IW" }  = $i * $idown;
    $fillers->[$i]->{"END"}  = $i * $idown + $ILEN - 1;
    $fillers->[$i]->{"BF"}   = 0;
    $fillers->[$i]->{"PART"} = ""; # partial word
  }
  if ($nemptiers == 1) {
    if ($out->ORG ne "colwise" and $out->ROWS != 1) {
      carp "Need a 'colwise' output matrix with a single emptier";
      return undef;
    }
    $OLEN=$out->ROWS * $out->COLS * $width;
    $odown=$width;
    $oright=$out->ROWS * $width;
    $want_out_size = $width * $out->ROWS;
  } else {
    if ($out->ORG ne "rowwise" and $out->ROWS != 1) {
      carp "Need a 'rowwise' output matrix with multiple emptiers";
      return undef;
    }
    $OLEN   = $out->COLS * $width;
    $odown  = $OLEN;
    $oright = $width;
    $want_out_size = $width;
  }
  for my $i (0 .. $nemptiers - 1) {
    $emptiers->[$i]->{"OR"}   = $i * $odown;
    $emptiers->[$i]->{"END"}  = $i * $odown + $OLEN - 1;
    $emptiers->[$i]->{"BF"}   = 0;
    $emptiers->[$i]->{"SKIP"} = 0;
  }

  do {
    # fill some of the input matrix
    #warn "Checking whether we need input (IFmin=$IFmin)\n";
    while (!$eof and ($IFmin < $want_in_size)) {
      #warn "Seems like we need input\n";
      for ($i = 0, $IFmin=$ILEN; $i < $nfillers ; ++$i) {
	#warn "IR is $IR, filler ${i}'s IW is " . $fillers->[$i]->{"IW"}. "\n";
	$max_fill = $ILEN - $fillers->[$i]->{"BF"};
	if ($fillers->[$i]->{"IW"} >= $IR + $i * $idown) {
	  if ($fillers->[$i]->{"IW"} + $max_fill >
	      $fillers->[$i]->{"END"}) {
	    $max_fill = $fillers->[$i]->{"END"} -
	      $fillers->[$i]->{"IW"} + 1;
	  }
	} else {
	  if ($fillers->[$i]->{"IW"} + $max_fill >=
	      $IR + $i * $idown) {
	    $max_fill = $IR  + $i * $idown - $fillers->[$i]->{"IW"};
	  }
	}

	#warn "Before adjusting maxfill: $max_fill (bytes read $bytes_read)\n";
	#warn "BF on filler $i is ". $fillers->[$i]->{"BF"} . "\n";
	if ($bytes_to_read and
	    ($bytes_read  + $max_fill > $bytes_to_read)) {
	  $max_fill = $bytes_to_read - $bytes_read;
	}

	#next unless $max_fill;

	#warn "Calling fill handler, maxfill $max_fill\n";

	# Subtract the length of any bytes from partial word read in
	# the last time around.
	$max_fill-=length $fillers->[$i]->{"PART"};
	die "max fill: $max_fill < 0\n" unless $max_fill >= 0;

	$str=$fillers->[$i]->{"SUB"}->($max_fill);

	#warn "Got input '$str' on row $i, length ". length($str). "\n";

	if (!defined($str)) {
	  carp "Read error on input stream $!";
	  return undef;
	} elsif ($str eq "") {
	  ++$eof;
	} else {
	  # setvals must be passed a string that's aligned to width
	  # (mainly so that it can do byte-order manipulation). As a
	  # result, we need to keep track of any bytes left over from
	  # the last call to the fill handler and prepend them to the
	  # string to be sent to setvals. We also need to chop off any
	  # extra bytes at the end of the string and save them until
	  # the next time around.

	  #warn "Got string '$str' from filler $i\n";
	  #warn "length of str is " . (length($str)) . "\n";

	  my $aligned=$fillers->[$i]->{"PART"} . $str;
	  $fillers->[$i]->{"PART"}=
	    substr $aligned,
	      (length($aligned) - (length($aligned) % $width)),
		(length($aligned) % $width),
		  "";
	  die "Alignment problem with filler $i\n"
	    if length($aligned) % $width;
	  die "Alignment problem with fill pointer $i\n"
	    if $fillers->[$i]->{"IW"} % $width;

	  #next unless length $aligned;

	  #warn "Adding string '$aligned' to input buffer\n";

	  $in->
	    setvals($in->
		    offset_to_rowcol($fillers->[$i]->{"IW"}),
		    $aligned,
		    $inorder);

	  # For the purpose of updating IW and BF variables, we
	  # pretend we didn't see any bytes from partial words
	  my $saw_bytes=(length $aligned) - (length($aligned) % $width) ;
	  $bytes_read += $saw_bytes;
	  $fillers->[$i]->{"BF"}  += $saw_bytes;
	  $fillers->[$i]->{"IW"}  += $saw_bytes;
	  if ($fillers->[$i]->{"IW"} > $fillers->[$i]->{"END"}) {
	    $fillers->[$i]->{"IW"}  -= $ILEN;
	  }
	}
	if ($fillers->[$i]->{"BF"} < $IFmin) {
	  $IFmin = $fillers->[$i]->{"BF"};
	}
      }
      if ($eof) {
	print "EOF detected in $eof stream(s)\n";
	if ($eof % $nfillers) {
	  carp "Not all input streams of same length";
	  return undef;
	}
      }
    }

    # flush some of the output matrix and do some processing
    do {

      #warn "Checking for output space; OFmax is $OFmax\n";

      # flush output buffer if we need some space
      while (($eof && $OFmax) || ($OFmax + $want_out_size > $OLEN)) {

        #warn "Seems like we needed to flush\n";

	for ($i=0, $OFmax=0; $i < $nemptiers; ++$i) {

	  $max_empty = $emptiers->[$i]->{"BF"};
	  if ($emptiers->[$i]->{"OR"} >= $OW + $i * $odown)  {
	    if ($emptiers->[$i]->{"BF"} + $want_out_size > $OLEN) {
	      $max_empty = $emptiers->[$i]->{"END"} -
		$emptiers->[$i]->{"OR"} + 1;
	      #warn "Stopping overflow, max_empty is now $max_empty\n";
	    }
	  } else {
	    if ($emptiers->[$i]->{"OR"} + $want_out_size >
		$OW + $i * $odown) {
	      #warn "Stopping tail overwrite, max_empty is now $max_empty\n";
	      $max_empty =
		$OW + $i * $odown - $emptiers->[$i]->{"OR"};
		# printf ("Stopping tail overwrite, max_empty is now %Ld\n",
		#   (long long) max_fill_or_empty);  */
	    }
	  }

	  die "invalid max empty $max_empty\n"
	    if $max_empty>0 and $max_empty<$width;
	  #next unless $max_empty;

	  # call handler to empty some data
	  #warn "Emptying row $i, col ".
	  #  ($emptiers->[$i]->{"OR"} % ( $out->COLS * $width)) .
	  #    " with $max_empty bytes\n";

	  die "Alignment problem with OR emptier $i" if
	    $emptiers->[$i]->{"OR"} % $width;
	  ($rr,$cc)=$out->
	    offset_to_rowcol($emptiers->[$i]->{"OR"});

	  #warn "got (row,col) ($rr,$cc) from OR#$i offset ".
	  #  $emptiers->[$i]->{"OR"}. "\n";

	  # When emptying, we have to check whether the emptier
	  # emptied full words. If it emptied part of a word, we have
	  # to prevent those bytes that were sent from being sent
	  # again. To do this, we keep track of a SKIP variable for
	  # each output buffer, which is the number of bytes to skip
	  # at the start of the output string.

	  $str=$out->
	    getvals($rr,$cc,
		    $max_empty / $width,
		    $outorder);
	  #substr $str, 0, $emptiers->[$i]->{"SKIP"}, "";
	  $rc=$emptiers->[$i]->{"SUB"}->($str);

	  unless (defined($rc)) {
	    carp "ERROR: write error $!\n";
	    return undef;
	  }
	  #$emptiers->[$i]->{"SKIP"} = $rc % $width;
	  #$rc -= $rc % $width;
	  $emptiers->[$i]->{"BF"}   -= $rc;
	  $emptiers->[$i]->{"OR"}   += $rc;
	  if ($emptiers->[$i]->{"OR"} > $emptiers->[$i]->{"END"}) {
	    $emptiers->[$i]->{"OR"} -= $OLEN;
	  }
	  if ($emptiers->[$i]->{"BF"} > $OFmax) {
	    $OFmax = $emptiers->[$i]->{"BF"};
	  }
	}
      }

      # do some processing
      #warn "Processing: IR=$IR, OW=$OW, IFmin=$IFmin, OFmax=$OFmax\n";
      ($rr,$cc)=$in->offset_to_rowcol($IR);
      $start_in_col = $cc;
      ($rr,$cc)=$out->offset_to_rowcol($OW);
      $start_out_col = $cc;
      $k=int ($IFmin  / $want_in_size);
      #warn "k=$k, start_in_col=$start_in_col, start_out_col=$start_out_col\n";
      if ($k + $start_in_col > $in->COLS) {
	$k = $in->COLS - $start_in_col;
      }
      if ($k + $start_out_col > $out->COLS) {
	$k = $out->COLS - $start_out_col;
      }
      #warn "k is now $k\n";
      Math::FastGF2::Matrix::multiply_submatrix_c
	  ($xform, $in, $out,
	   0, 0, $xform->ROWS,
	   $start_in_col, $start_out_col, $k);
      $IFmin -= $want_in_size * $k;
      $OFmax += $want_out_size * $k;
      $IR+=$iright * $k;
      if ($IR > $fillers->[0]->{"END"}) {
	$IR=0;
      }
      $OW+=$oright * $k;
      if ($OW > $emptiers->[0]->{"END"}) {
	$OW=0;
      }
      # printf ("Moving to next column: IFmin, OFmax are (%lld, %lld)\n",
      #	  (long long) IFmin, (long long) OFmax); */

      #warn "Finished processing chunk of $k columns\n";

      # we've been updating IFmin and OFmax, but not the real BF
      # variables in the gf2_streambuf_control structures. We do that
      # after the processing loop is finished.

      if ($k) {
	for ($i=0;  $i < $nfillers; ++$i) {
	  $fillers->[$i]->{"BF"}  -= $k * $want_in_size;
	}
	for ($i=0; $i < $nemptiers; ++$i) {
	  $emptiers->[$i]->{"BF"} += $k * $want_out_size;
	}
      }

    } while ($eof && $OFmax);
  } while (!$eof);

  return $bytes_read;
}

sub ida_rng_init {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my $bytes  = shift;
  my $source = shift || "/dev/urandom";
  my $fh;

  return undef unless ($bytes == 1 or $bytes == 2 or $bytes == 4);

  if ($source eq "rand") {
    my $max=256 ** $bytes;
    return sub { int rand $max };
  }

  return undef unless sysopen $fh, $source, O_RDONLY;

  # Return an anonymous closure to act as an iterator. Calling the
  # iterator will return an integer in the range 0 .. 2^(8*bytes)-1
  my $format;
  if ($bytes == 1) {
    $format="C";
  } elsif ($bytes == 2) {
    $format="S";
  } else {
    $format="L";
  }
  return sub {
    my $deinit=shift;		# passing any args will close the
    my $buf;			# file, allowing the calling program
    if (defined($deinit)) {	# to deallocate the iterator without
      close $fh;		# (possibly) leaving an open, but
      return undef;		# inaccessible file handle
    }
    if ($bytes != sysread $fh,$buf,$bytes) {
      die "Fatal Error: not enough bytes in random source!\n";
    }
    return unpack $format, $buf;
  };
};

sub ida_fisher_yates_shuffle {	# based on recipe 4.15 from the
				# Perl Cookbook
  my $array=shift;

  # Note that this uses plain old rand rather than our high-quality
  # RNG. If that is a problem, either replace this rand with a better
  # alternative or avoid having this function called by using more
  # than 1 byte-security. Since we're using the random variables to
  # generate a permutation, the actual numbers chosen won't be
  # revealed, so it should be a little more difficult for an attacker
  # to guess the sequence used (and hence make better guesses about
  # the random values for the other shares). I can't say either way
  # whether this will be a problem in practice, but it might be a good
  # idea to shuffle the array a second time if attacking rand is a
  # worry. Since an attacker won't have access to all the shares,
  # this should destroy or limit his ability to determine the order in
  # which the numbers were generated. Shuffling a list of high-quality
  # random numbers (such as from the rng_init function) with a
  # poor-quality rand-based shuffle should not leak any extra
  # information, while using two passes with the rand-based shuffler
  # (effectively one to select elements, the other to shuffle them)
  # seems like it should improve security.

  # Change recipe to allow picking a certain number of elements
  my $picks=shift;
  $picks=scalar(@$array) unless
    defined($picks) and $picks >=0 and $picks

  my $i=scalar(@$array);
  while (--$i > $picks - scalar(@$array)) {
    my $j=int rand ($i + 1);	# random int from [0,$i]
    next if $i==$j;		# don't swap element with itself
    @$array[$i,$j]=@$array[$j,$i]
  }
  # If we want fewer picks than are in the full list, then truncate
  # the list by shifting off some elements from the front. This
  # destruction of the list may not be a good thing in general, but
  # it's fine for our purposes in this program. Note that this tail
  # processing effectively brings the algorithm up to O(n), where n is
  # the list length, but we still save out on the more expensive calls
  # to rand and the element-swapping for elements we'll never
  # select. Using mjd-permute might be a marginally better choice
  # where there are many unused elements, but since we're only
  # interested in using this with arrays of up to 256 elements, this
  # will be fine.
  #
  while (scalar(@$array) > $picks) {
    shift @$array;		# using splice() is quicker!
  }
  # splice @$array, 0, scalar @$array - $picks;
};

sub ida_check_key {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my ($k,$n,$w,$key)=@_;

  # Check that key generated by the algorithm (or supplied by the
  # user) has the properties required for linear independence.
  #
  # The key supplied is a list of distinct numbers in the order
  # x1,...,xn,y1,...,yk

  die "No key elements to check\n" unless defined $key;

  die "Supplied key for generating matrix is of the wrong size"
    unless scalar(@$key) == $k + $n;

  my %values;

  # For integer values xi, yj mod a prime p, the conditons that must
  # be satisfied are...
  # xi + yj != 0        |
  # i != j -> xi != xj  } for all i,j
  # i != j -> yi != yj  |
  #
  # For calculations in GF_2, since each number is its own additive
  # inverse, these conditions can be achieved by stating that all
  # numbers must be distinct.
  foreach my $v (@$key) {
    return 1 if $v >= 256 ** $w;
    return 1 if exists($values{$v}); # failure; duplicate value
    $values{$v}=1;
  }
  return 0;			# success; all values distinct
};

sub ida_generate_key {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }

  my ($k,$n,$w,$rng)=@_;
  my $key=[];

  # Generate an array of $k + $n distinct random values, each in the
  # range [0..256**$w)

  # If the width is 1 byte, then we'll use the Fisher-Yates shuffle to
  # choose distinct numbers in the range [0,255]. This takes only
  # O($k+$n) steps and requires O(256) storage. If the width is 2 or
  # more bytes, the Fisher-Yates shuffle would require too much memory
  # (O(2**16), O(2**24), etc.), so we use a different algorithm which
  # uses the rng to generate the numbers directly, checking for
  # duplicates as it goes, and re-rolling whenever dups are found.
  if ($w == 1) {
    push @$key,(0..255);
    ida_fisher_yates_shuffle($key,$k + $n);
  } else {
    my (%rolled,$r);
    my $count=$k+$n;
    while ($count) {
      $r=$rng->();
      next if exists($rolled{$r});
      $rolled{$r}=1;
      push @$key,$r;
      --$count;
    }
  }

  # do a final shuffle of the elements. This should help guard against
  # exploiting weaknesses in either random generator, but particularly
  # the 1-byte version which uses the system's rand function. The
  # extra security derives from the fact that consecutively-generated
  # numbers will likely end up being distributed to different parties,
  # so it should no longer be possible for an attacker to determine
  # the order in which the rng generated them without actually
  # collecting all the shares (which would avoid the need to attack
  # the rng in the first place).
  ida_fisher_yates_shuffle($key);
  return $key;
};

sub ida_check_list {

  # Check a given listref to make sure it has no dups and that all
  # values are within range. Returns the list less any deleted
  # elements, as well as doing an in-place delete on the passed
  # listref.

  my ($list,$item,$min,$max)=@_;

  my $new_list=[];	# list without dups, invalid values
  my @saw_val=((0) x $max);
  for my $i (@$list) {
    if ($saw_val[$i]) {
      carp "Duplicate $item number $i in ${item}list; ignoring";
    } elsif ($i < $min or $i > $max) {
      carp "$item number $i out of range in ${item}list; ignoring.";
    } else {
      ++$saw_val[$i];
      push @$new_list, $i;
    }
  }
  $list=$new_list;
}

sub ida_check_transform_opts {

  # Return 0 for success, or 1 otherwise. Fixes sharelist if it had
  # any duplicate or out-of-range vales

  my ($self,$class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self=shift;
    $class=ref($self);
  } else {
    $self=$classname;
  }
  my %o= (
	  "quorum"     => undef,
	  "shares"     => undef,
	  "width"      => undef,
	  "sharelist"  => undef,
	  "key"        => undef,
	  "matrix"     => undef,
	  @_);
  my ($k,$n,$w,$sharelist,$key,$mat) =
    map {
      exists($o{$_}) ? $o{$_} : undef;
    } qw(quorum shares width sharelist key matrix);

  if (defined($key) and defined($mat)) {
    carp "both key and matrix parameters supplied; use one only";
    return 1;
  }
  if (defined($key)) {
    unless (defined ($n) and defined ($sharelist)) {
      carp "If a key is supplied, must specify shares and sharelist";
      return 1;
    }
    unless (ref($key) and scalar(@$key) == $k + $n) {
      carp "key must be a reference to a list of $k + $n elements";
      return 1;
    }
  }
  if (defined($mat)) {
    if ( ref($mat) ne "Math::FastGF2::Matrix") {
      carp "Matrix must be of type Math::FastGF2::Matrix";
      return 1;
    }
    if ($mat->ORG ne "rowwise")  {
      carp "supplied matrix must use 'rowwise' organisation";
      return undef;
    }
    if (($mat->ROWS != $n or $mat->COLS != $k)) {
      carp "supplied matrix must be $n rows x $k cols";
      return 1;
    }
  }
  if (defined($sharelist)) {
    ida_check_list($sharelist,"share",0,$n-1);
    unless (scalar(@$sharelist) > 0) {
      carp "sharelist does not contain any valid share numbers; aborting";
      return 1;
    }
  }

  return 0;
}

sub ida_key_to_matrix {
  my ($self,$class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self=shift;
    $class=ref($self);
  } else {
    $self=$classname;
  }
  my %o= (
	  "quorum"      => undef,
	  "shares"      => undef,
	  "width"       => undef,
	  "sharelist"   => undef,
	  "key"         => undef,
	  "invert?"     => 0,	# want us to invert the matrix?
	  "skipchecks?" => 0,	# skip long checks on options?
	  @_,
	 );
  my ($k,$n,$w,$sharelist,$key,$invert,$skipchecks) =
    map {
      exists($o{$_}) ? $o{$_} : undef;
    } qw(quorum shares width sharelist key invert? skipchecks?);

  # skip error checking if the caller tells us it's OK
  unless (defined($skipchecks) and $skipchecks) {
    if (ida_check_transform_opts(%o)) {
      carp "Can't create matrix due to options problem";
      return undef;
    }
  }

  my $mat=Math::FastGF2::Matrix ->
    new(rows => scalar(@$sharelist),
	cols => $k,
	width => $w,
	org => "rowwise");
  unless (defined($mat)) {
    carp "Failed to create transform matrix";
    return undef;
  }
  my $dest_row=0;
  for my $row (@$sharelist) {
    for my $col (0 .. $k-1) {
      my $x   = $key->[$row];
      my $y   = $key->[$n+$col];
      my $sum = $x ^ $y;
      $mat->setval($dest_row, $col, gf2_inv($w << 3,$sum));
    }
    ++$dest_row;
  }
  if (defined($invert) and $invert) {
    return $mat->invert;
  } else {
    return $mat;
  }
}

sub ida_split {
  my ($self, $class);
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my %o=
    (
     quorum => undef,
     shares => undef,
     width => undef,
     # supply either a list of key parameters or a matrix
     key => undef,
     matrix => undef,
     sharelist => undef,
     # source, sinks
     filler => undef,
     emptiers => undef,
     # misc options
     rand => "/dev/urandom",
     bufsize => 4096,
     bytes => 0,
     # byte order flags
     inorder => 0,
     outorder => 0,
     @_,
    );

  # move all options into local variables
  my ($k,$n,$w,$key,$mat,$sharelist,$filler,$emptiers,$rng,
      $bufsize,$inorder,$outorder,$bytes_to_read) =
	map {
	  exists($o{$_}) ? $o{$_} : undef;
	} qw(quorum shares width key matrix sharelist filler
	     emptiers rand bufsize inorder outorder bytes);

  # validity checks
  unless ($w == 1 or $w == 2 or $w == 4) {
    carp "Width must be one of 1, 2, 4";
    return undef;
  }
  unless ($k > 0 and $k < 256 ** $w) {
    carp "Quorum value out of range";
    return undef;
  }
  unless ($n > 0 and $k + $n < 256 ** $w) {
    carp "Number of shares out of range";
    return undef;
  }
  unless (defined ($filler)) {
    carp "Need a filler to provide data";
    return undef;
  }
  unless (ref($emptiers) and scalar(@$emptiers) == $n) {
    carp "emptiers must be a list of $n items (one for each share)";
    return undef;
  }
  unless (defined($bufsize) and $bufsize > 0) {
    carp "Bad bufsize ($bufsize)";
    return undef;
  }
  unless (defined($inorder) and $inorder >= 0 and $inorder <= 2) {
    carp "inorder != 0 (native), 1 (little-endian) or 2 (big-endian)";
    return undef;
  }
  unless (defined($outorder) and $outorder >= 0 and $outorder <= 2) {
    carp "outorder != 0 (native), 1 (little-endian) or 2 (big-endian)";
    return undef;
  }
  # Move some checks to ida_check_transform_opts
  if (ida_check_transform_opts(%o)) {
    carp "Can't proceed due to problem with transform options";
    return undef;
  }

  if (defined($bytes_to_read) and $bytes_to_read < 0) {
    carp "bytes parameter must be 0 (read until eof) or greater";
    return undef;
  }

  if (defined($sharelist)) {

    # moved some checks to ida_check_transform_opts

    if (defined($mat)) {
      # copy only the listed rows into a new matrix
      my $m2=Math::FastGF2::Matrix->new(rows => scalar(@$sharelist),
					cols => $k,
					width => $w,
					org => "rowwise");
      unless (defined($m2)) {
	carp "Problem creating submatrix with rows from sharelist";
	return undef;
      }
      my $dest_row=0;
      for my $row (@$sharelist) {
	for my $col (0 .. $k-1) {
	  $m2->setval($dest_row,$col, $mat->getval($row,$col));
	}
	++$dest_row;
      }
      $mat=$m2;			# replace matrix with reduced one
    }
  } else {
    $sharelist=[0..$n-1];
  }

  unless (defined($mat)) {
    if (defined ($key)) {
      if (ida_check_key($k,$n,$w,$key)) {
	carp "Problem with supplied key";
	return undef;
      }
    } else {
      # no key and no matrix, so generate random key
      $rng=ida_rng_init($w,$rng);
      unless (defined($rng)) {
	carp "Failed to initialise random number generator";
	return undef;
      }
      $key=ida_generate_key($k,$n,$w,$rng);
    }

    # now generate matrix from key
    $mat=ida_key_to_matrix( "quorum"      => $k,
			    "shares"      => $n,
			    "width"       => $w,
			    "sharelist"   => $sharelist,
			    "key"         => $key,
			    "skipchecks?" => 0);
  }

  # create the buffer matrices and start the transform
  my $in = Math::FastGF2::Matrix->new(rows=>$k,
				      cols=>$bufsize,
				      width=>$w,
				      org => "colwise");
  my $out= Math::FastGF2::Matrix->new(rows=>scalar(@$sharelist),
				      cols=>$bufsize,
				      width=>$w,
				      org => "rowwise");
  unless (defined($in) and defined($out)) {
    carp "failed to allocate input/output buffer matrices";
    return undef;
  }
  my $rc=ida_process_streams($mat,
			     $in, [$filler],
			     $out, $emptiers,
			     $bytes_to_read,
			     $inorder, $outorder);
  if (defined ($rc)) {
    return ($key,$mat,$rc);
  } else {
    return undef;
  }
}

sub ida_combine {
  my $self;
  my $class;
  if ($_[0] eq $classname or ref($_[0]) eq $classname) {
    $self  = shift;
    $class = ref($self) || $self;
  } else {
    $self=$classname;
    $class=$classname;
  }
  my %o=
    (
     quorum => undef,
     shares => undef,   # only needed if key supplied
     width => undef,
     # supply either a list of key parameters and a list of keys or a
     # pre-inverted matrix generated from those key details
     key => undef,
     matrix => undef,
     sharelist => undef,
     # source, sinks
     fillers => undef,
     emptier => undef,
     # misc options
     bufsize => 4096,
     bytes => 0,
     # byte order flags
     inorder => 0,
     outorder => 0,
     @_,
    );

  # copy all options into local variables
  my ($k,$n,$w,$key,$mat,$sharelist,$fillers,$emptier,
      $bufsize,$inorder,$outorder,$bytes_to_read) =
	map {
	  exists($o{$_}) ? $o{$_} : undef;
	} qw(quorum shares width key matrix sharelist fillers
	     emptier  bufsize inorder outorder bytes);

  # validity checks
  unless ($w == 1 or $w == 2 or $w == 4) {
    carp "Width must be one of 1, 2, 4";
    return undef;
  }
  unless ($k > 0 and $k < 256 ** $w) {
    carp "Quorum value out of range";
    return undef;
  }
  unless (ref($fillers) and scalar(@$fillers) == $k) {
    carp "fillers must be a list of $k items (one for each share)";
    return undef;
  }
  unless (defined($emptier)) {
    carp "need an emptier to write data to";
    return undef;
  }
  unless (defined($bufsize) and $bufsize > 0) {
    carp "Bad bufsize";
    return undef;
  }
  unless (defined($inorder) and $inorder >= 0 and $inorder <= 2) {
    carp "inorder ($inorder) != 0 (native), ".
      "1 (little-endian) or 2 (big-endian)";
    return undef;
  }
  unless (defined($outorder) and $outorder >= 0 and $outorder <= 2) {
    carp "outorder ($outorder) != 0 (native), ".
      "1 (little-endian) or 2 (big-endian)";
    return undef;
  }
  if (defined($key)) {
    if (ida_check_key($k,$n,$w,$key)) {
      carp "Invalid key supplied";
      return undef;
    }
  } else {
    $o{"shares"}=$k;		# needed for ida_check_transform_opts
    $n=$k;
  }
  if (ida_check_transform_opts(%o)) {
    carp "Can't continue due to problem with transform opts";
    return undef;
  }
  if (defined($bytes_to_read) and $bytes_to_read < 0) {
    carp "bytes parameter must be 0 (read until eof) or greater";
    return undef;
  }

  if (defined($key)) {
    ida_check_list($sharelist,"share",0,$k-1);
    unless (scalar(@$sharelist) == $k) {
      carp "sharelist does not have k=$k elements";
      return undef;
    }
    #warn "Creating and inverting matrix from key\n";
    $mat=ida_key_to_matrix(%o, "skipchecks?" => 0, "invert?" => 1);
    unless (defined($mat)) {
      carp "Failed to invert transform matrix (this shouldn't happen)";
      return undef;
    }
  }

  # create the buffer matrices and start the transform
  my $in = Math::FastGF2::Matrix->new(rows=>$k,
				      cols=>$bufsize,
				      width=>$w,
				      org => "rowwise");
  my $out= Math::FastGF2::Matrix->new(rows=>$k,
				      cols=>$bufsize,
				      width=>$w,
				      org => "colwise");
  unless (defined($in) and defined($out)) {
    carp "failed to allocate input/output buffer matrices";
    return undef;
  }
  my @vals=$mat->getvals(0,0,$k * $n);
  #warn "matrix is [" . (join ", ", map
  #			{sprintf("%02x",$_) } @vals) . "] (" .
  #		  scalar(@vals) . " values)\n";

  return ida_process_streams($mat,
			     $in, $fillers,
			     $out, [$emptier],
			     $bytes_to_read,
			     $inorder, $outorder);

}


1;
__END__