/**
 *  BitVector - Effecient bit vector class extension for Ruby
 *  Copyright (c) 2000 Robert Feldt, feldt@ce.chalmers.se
 *
 *  Robert Feldt
 *  Brolyckan 1
 *  SE-433 68 Savedalen
 *  SWEDEN
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Library General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Library General Public License for more details.
 *
 *  You should have received a copy of the GNU Library General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
#include "ruby.h"
#include "steffen_beyers_bit_vector/ToolBox.h"
#include "steffen_beyers_bit_vector/BitVector.h"

/* Wrap in struct so that GC works */
struct RBitVector {
  wordptr llbv;
};

/* BitVector class */
static VALUE cBitVector;

/* Constants that we pre-calc at module load time to get better
   performance at run-time. */
static VALUE mMarshal;
static VALUE mKernel;
static VALUE mMath;
static VALUE idNew;
static VALUE idSize;
static VALUE idAref;
static VALUE idDump;
static VALUE idLoad;
static VALUE idAdd;
static VALUE idMinus;
static VALUE idMult;
static VALUE idRand;
static VALUE idBetween;
static VALUE idCvarCarry;
static VALUE idLog10;
static VALUE maxunsignedint; 
static VALUE fixnum1;
static VALUE fixnum2;
static VALUE fixnum0;
static VALUE fixnum31;
static VALUE fixnum32;
static VALUE fixnum2_28;
static VALUE fixnumneg1;
static VALUE log10_2;
static VALUE fix2_to29;
VALUE num2_toX[31]; /* Fixnum 2**X where X in [0..30] */

/* prototype declarations */
static int	valid_bitref(VALUE ref, wordptr llbv);
static void	bv_error(char* method, char* errmsg, VALUE error);
static VALUE	make_ruby_bitvector(wordptr llbv);
static wordptr	get_lowlevel_bitvector(VALUE rbbv);
static void	get_lowlevel_bitvector_and_struct(VALUE rbbv, wordptr *llbv, struct RBitVector **sbv);
static VALUE	bv_version(VALUE klass);
static VALUE	bv_s_new(int argc, VALUE* argv, VALUE class);
static VALUE	bv_s_from_bin(VALUE class, VALUE bits, VALUE str);
static VALUE	bv_s_from_dec(VALUE class, VALUE bits, VALUE str);
static VALUE	bv_s_from_hex(VALUE class, VALUE bits, VALUE str);
static VALUE	bv_s_from_enum(VALUE class, VALUE bits, VALUE str);
static VALUE	bv_s_from_int(int argc, VALUE *argv, VALUE class);
static VALUE	bv_set_bit(VALUE self, VALUE bit, VALUE newval);
static VALUE	bv_concat(VALUE self, VALUE other);
static VALUE	bv_clone(VALUE self);
static VALUE	bv_init_from_bignum(VALUE self, VALUE bits, VALUE bignum);
static VALUE	bv_init_from_fixnum(VALUE self, VALUE bits, VALUE fixnum);
static VALUE	bv_initialize(int argc, VALUE *argv, VALUE self);
static VALUE	bv_aset(int argc, VALUE *argv, VALUE self);
static VALUE	bv_aset(int argc, VALUE *argv, VALUE self);
static VALUE	bv_length(VALUE self);
static void	randomize_bits(wordptr bitvector, N_int start, N_int end, double probability);
static VALUE	bv_randomize(int argc, VALUE *argv, VALUE self);
static VALUE	bv_fill(int argc, VALUE *argv, VALUE self);
static VALUE	bv_empty(int argc, VALUE *argv, VALUE self);
static VALUE	bv_flip(int argc, VALUE *argv, VALUE self);
static VALUE	bv_reverse(int argc, VALUE *argv, VALUE self);
static VALUE	bv_primes(VALUE self);
static VALUE	bv_is_empty(VALUE self);
static VALUE	bv_is_full(VALUE self);
static VALUE	bv_is_equal(VALUE self, VALUE other);
static VALUE	bv_lexicompare(VALUE self, VALUE other);
static VALUE	bv_compare(VALUE self, VALUE other);
static VALUE	bv_to_binstr(VALUE self);
static VALUE	bv_to_hexstr(VALUE self);
static VALUE	bv_to_decstr(VALUE self);
static VALUE	bv_to_enumstr(VALUE self);
static VALUE	bv_off(VALUE self, VALUE bit);
static VALUE	bv_on(VALUE self, VALUE bit);
static VALUE	bv_flipbit(VALUE self, VALUE bit);
static VALUE	bv_bitref(VALUE self, VALUE bit);
static VALUE	bv_aref(int argc, VALUE *argv, VALUE self);
static VALUE	bv_test(VALUE self, VALUE bit);
static VALUE	bv_set_norm(VALUE self);
static VALUE	bv_set_union(VALUE self, VALUE other);
static VALUE	bv_set_intersection(VALUE self, VALUE other);
static VALUE	bv_set_difference(VALUE self, VALUE other);
static VALUE	bv_set_exor(VALUE self, VALUE other);
static VALUE	bv_set_complement(VALUE self);
static VALUE	bv_set_is_subset(VALUE self, VALUE other);
static VALUE	bv_set_is_superset(VALUE self, VALUE other);
static VALUE	bv_set_min(VALUE self);
static VALUE	bv_set_max(VALUE self);
static VALUE	bv_get_lsb(VALUE self);
static VALUE	bv_set_lsb(VALUE self, VALUE newVal);
static VALUE	bv_get_msb(VALUE self);
static VALUE	bv_set_msb(VALUE self, VALUE newVal);
static VALUE	bv_rotate_left(VALUE self);
static VALUE	bv_rotate_right(VALUE self);
static VALUE	bv_shift_left(VALUE self, VALUE carryIn);
static VALUE	bv_shift_right(VALUE self, VALUE carryIn);
static VALUE	bv_move_left(VALUE self, VALUE steps);
static VALUE	bv_move_right(VALUE self, VALUE steps);
static VALUE	bv_increment(VALUE self);
static VALUE	bv_decrement(VALUE self);
static VALUE	bv_substitute(VALUE self, VALUE other, VALUE off1, VALUE len1, VALUE off2, VALUE len2);
static VALUE	bv_dump(VALUE self, VALUE limit);
static VALUE	bv_load(VALUE class, VALUE aString);
static VALUE	bv_to_uint(VALUE self);
static VALUE	bv_to_int(VALUE self);
static VALUE	bv_ones(VALUE self);
static VALUE	bv_zeroes(VALUE self);
static VALUE	bv_resize(VALUE self, VALUE newSize);
static VALUE	bv_set_carry(VALUE self, VALUE newVal);
static VALUE	bv_get_carry(VALUE self);
static VALUE	bv_add(VALUE self, VALUE other);
static VALUE	bv_sub(VALUE self, VALUE other);
static VALUE	bv_negate(VALUE self);
static VALUE	bv_abs(VALUE self);
static VALUE	bv_sign(VALUE self);
static VALUE	bv_multiply(VALUE self, VALUE other);
static VALUE	bv_divide(VALUE self, VALUE other);
static void	bv_free(struct RBitVector *rbv);
void		Init_bitvector(void);

/* Defines */
#define ZERO_OR_FALSE(v) ((fixnum0 == (v)) || (Qfalse == (v)))
#define ONE_OR_TRUE(v) ((fixnum1 == (v)) || (Qtrue == (v)))
#define KINDOF_INT(v) (Qtrue==rb_obj_is_kind_of(v, rb_cInteger))
#define KINDOF_BV(v) (Qtrue==rb_obj_is_kind_of(v, cBitVector))
#define BV_OBJ(v) (Qtrue==rb_obj_is_instance_of(v, cBitVector))
#define ISFLOAT(v) (T_FLOAT==TYPE(v))
#define KINDOF_RANGE(v) (Qtrue==rb_obj_is_kind_of(v, rb_cRange))
#define INSPECT(v) (RSTRING(rb_funcall(v,idInspect,0))->ptr)

/*
 * NOTE: Strange GC bug if I use maxunsignedint instead of recalcing
 * the value.
 *
 * #define VALID_BITNUM(v) ((Qtrue == rb_obj_is_kind_of((v), rb_cInteger)) && (Qtrue == rb_funcall((v),idBetween,2,fixnum0, maxunsignedint)))
 */

#define VALID_BITNUM(v) ((Qtrue == rb_obj_is_kind_of((v), rb_cInteger)) && (Qtrue == rb_funcall((v),idBetween,2,fixnum0, UINT2NUM((N_int)(-1)))))
#define UINTABLE(v) (FIXNUM_P(v) || ((T_BIGNUM==TYPE(v)) && (FIX2INT(rb_funcall(v,idSize,0))<=sizeof(unsigned int))))

static int
valid_bitref(VALUE ref, wordptr llbv)
{
  N_int n;

  if(!KINDOF_INT(ref) || !UINTABLE(ref))
    return false;

  n = NUM2UINT(ref);
  return ((0<=n) && (n<bits_(llbv)));
}
#define VALID_BITREF(v,llbv) valid_bitref(v,llbv)
#define VALID_BITREF2(nint,llbv) ((0<=nint) && (nint<bits_(llbv)))

/** Error handling **/
static void
bv_error(char* method, char* errmsg, VALUE error)
{
  static char buffer[100];
  sprintf(buffer, "%s (%s)", errmsg, method);
  rb_raise(error, buffer);
}

#define BV_ERROR(method, errmsg, error) bv_error(method, errmsg, error)
#define BV_INDEX_ERROR(method) BV_ERROR(method, "invalid bit number", rb_eIndexError)
#define BV_SIZE_ERROR(method) BV_ERROR(method, "invalid size", rb_eArgError)
#define BV_MEMORY_ERROR(method) BV_ERROR(method, "unable to allocate memory", rb_eNoMemError)
#define BV_ERRORCODE(err, method) printf("Error %d in method %s\n", err, method)

/** Converting between Ruby and low-level object **/

/* Free struct */
static void
bv_free(struct RBitVector* rbv)
{
  if(rbv && rbv->llbv) {
    BitVector_Destroy(rbv->llbv);
  }
  if(rbv) {
    xfree(rbv);
  }
}

/* Make Ruby object from low-level object */
static VALUE
make_ruby_bitvector(wordptr llbv)
{
  struct RBitVector *rbv = ALLOC(struct RBitVector);
  rbv->llbv = llbv;
  return Data_Wrap_Struct(cBitVector, 0, bv_free, rbv);
}

/* Get struct from Ruby BitVector */
struct RBitVector *
get_struct_from_rbv(VALUE rbbv)
{
  struct RBitVector *p;
  Data_Get_Struct(rbbv, struct RBitVector, p);
  return p;
}

/* Get low-level object from ruby object */
static wordptr
get_lowlevel_bitvector(VALUE rbbv)
{
  struct RBitVector *p;
  Data_Get_Struct(rbbv, struct RBitVector, p);
  return p->llbv;
}
#define LLBV(rbbv) (get_lowlevel_bitvector(rbbv))

/* Get low-level object and struct from ruby object */
static void
get_lowlevel_bitvector_and_struct(VALUE rbbv, wordptr *llbv,
				  struct RBitVector **sbv)
{
  Data_Get_Struct(rbbv, struct RBitVector, *sbv);
  *llbv = (*sbv)->llbv;
}
#define LLASBV(rbbv,llbv,sbv) get_lowlevel_bitvector_and_struct(rbbv,llbv,sbv)

/** Class method **/
static VALUE
bv_version(VALUE klass)
{
  char buffer[100];
  sprintf(buffer, "BitVector version 0.1.6 using Steffen Beyer's Bit::Vector lib version %s", BitVector_Version());
  return rb_str_new2(buffer);
}

static VALUE
bv_s_new(int argc, VALUE* argv, VALUE class)
{
  VALUE tdata = make_ruby_bitvector(NULL);
  rb_obj_call_init(tdata, argc, argv);
  return tdata;
}

static VALUE
bv_s_from_bin(VALUE class, VALUE bits, VALUE str)
{
  VALUE obj = make_ruby_bitvector(NULL);
  wordptr objll = BitVector_Create(NUM2UINT(bits), false);
  ErrCode err;
  char* strp = RSTRING(str)->ptr;

  err = BitVector_from_Bin(objll, strp);
  if(err)
    rb_raise(rb_eArgError, "not a valid string");

  get_struct_from_rbv(obj)->llbv = objll;
  return obj;
}

static VALUE
bv_s_from_dec(VALUE class, VALUE bits, VALUE str)
{
  VALUE obj = make_ruby_bitvector(NULL);
  wordptr objll = BitVector_Create(NUM2UINT(bits), false);
  ErrCode err;
  char* strp = RSTRING(str)->ptr;

  err = BitVector_from_Dec(objll, strp);
  if(err)
    rb_raise(rb_eArgError, "not a valid string");

  get_struct_from_rbv(obj)->llbv = objll;
  return obj;
}

static VALUE
bv_s_from_hex(VALUE class, VALUE bits, VALUE str)
{
  VALUE obj = make_ruby_bitvector(NULL);
  wordptr objll = BitVector_Create(NUM2UINT(bits), false);
  ErrCode err;
  char* strp = RSTRING(str)->ptr;

  err = BitVector_from_Hex(objll, strp);
  if(err)
    rb_raise(rb_eArgError, "not a valid string");

  get_struct_from_rbv(obj)->llbv = objll;
  return obj;
}

static VALUE
bv_s_from_enum(VALUE class, VALUE bits, VALUE str)
{
  VALUE obj = make_ruby_bitvector(NULL);
  wordptr objll = BitVector_Create(NUM2UINT(bits), false);
  ErrCode err;
  char* strp = RSTRING(str)->ptr;

  err = BitVector_from_Enum(objll, strp);
  if(err)
    rb_raise(rb_eArgError, "not a valid string");

  get_struct_from_rbv(obj)->llbv = objll;
  return obj;
}

static VALUE
bv_s_from_int(int argc, VALUE *argv, VALUE class)
{
  VALUE num_bits;
  VALUE integer = argv[0];
  VALUE obj;
  VALUE temp;
  double t_d;
  int t_i;

  if(!KINDOF_INT(integer))
    rb_raise(rb_eArgError, "invalid type");
  
  if(argc==1) {
    /*
     * Calc minimum bits needed:
     * (Math.log10(integer.abs)/Math.log10(2)).ceil.to_i
     * Add one extra bit for sign bit.
     */
    temp = rb_funcall(integer, rb_intern("abs"), 0);
    temp = rb_funcall(mMath, idLog10, 1, temp);
    t_d = (RFLOAT(temp)->value) / 0.3010299957;
    t_i = (int)t_d;
    t_i += (((t_d-(int)t_d)>0.0)?1:0); /* Add 1 if decimals not zero */
    t_i++; /* Extra bit for sign */
    num_bits = INT2NUM(t_i);
  } else if(KINDOF_INT(argv[1])) {
    num_bits = argv[1];
  }
  
  obj = make_ruby_bitvector(NULL);

  if(FIXNUM_P(integer)) {
    return bv_init_from_fixnum(obj, num_bits, integer);
  } else {
    return bv_init_from_bignum(obj, num_bits, integer);
  }
}

/** Instance methods **/

static VALUE
bv_set_bit(VALUE self, VALUE bit, VALUE newval)
{
  wordptr selfll = LLBV(self);

  if(!VALID_BITREF(bit, selfll))
    BV_INDEX_ERROR("set_bit");

  if(ZERO_OR_FALSE(newval))
    BitVector_Bit_Copy(LLBV(self), NUM2UINT(bit), false);
  else
    BitVector_Bit_Copy(LLBV(self), NUM2UINT(bit), true);
  return self;
}

static VALUE
bv_concat(VALUE self, VALUE other)
{
  if(!KINDOF_BV(other))
    rb_raise(rb_eTypeError, "invalid type");
  return make_ruby_bitvector(BitVector_Concat(LLBV(self), LLBV(other)));
}

static VALUE
bv_clone(VALUE self)
{
  return make_ruby_bitvector(BitVector_Clone(LLBV(self)));
}

static VALUE
bv_init_from_bignum(VALUE self, VALUE bits, VALUE bignum)
{
  N_int num_bits = NUM2UINT(bits);
  wordptr selfll = BitVector_Create(num_bits, true);  
  N_int i;

  for(i = 0; i < num_bits; i++) {
    if(fixnum1 == rb_funcall(bignum, idAref, 1, INT2FIX(i)))
      BitVector_Bit_On(selfll, i);
  }

  get_struct_from_rbv(self)->llbv = selfll;  
  return self;
}

static VALUE
bv_init_from_fixnum(VALUE self, VALUE bits, VALUE fixnum)
{
  N_int num_bits = NUM2UINT(bits);
  wordptr selfll = BitVector_Create(num_bits, true);  
  N_int i;
  unsigned int v = FIX2UINT(fixnum);

  for(i = 0; i < num_bits; i++) {
    if(1 == (v & 0x01)) BitVector_Bit_On(selfll, i);
    v >>= 1;
  }
  get_struct_from_rbv(self)->llbv = selfll;  
  return self;
}

/**
 * BitVector.new(anInteger)       => Create bv with anInteger bits
 * BitVector.new(aBitVector)      => Create clone of aBitVector
 * BitVector.new(bs, anInteger)   => Create bv with bs bits, init from int
 * BitVector.new(nil or false, aFixnum)    => Create bv with 31 bits, init from fixnum
 * BitVector.new(true, aFixnum)    => Create bv with 32 bits, init from fixnum
 * BitVector.new(bs, aFixnum)      => Create bv with bs bits, init from fixnum
 * BitVector.new(nil, aBignum)    => Create bv with needed by bignum and init
 */
static VALUE
bv_initialize(int argc, VALUE *argv, VALUE self)
{
  N_int bits;

  if(1==argc) {
    if(VALID_BITNUM(argv[0])) {
      get_struct_from_rbv(self)->llbv = 
	BitVector_Create(NUM2UINT(argv[0]), true);
      /* printf("Creating BV %u\n", get_struct_from_rbv(self)->llbv); */
      return self;
    } else if(BV_OBJ(argv[0])) {
      get_struct_from_rbv(self)->llbv = BitVector_Clone(LLBV(argv[0]));
      return self;
    } else {
      rb_raise(rb_eArgError, "invalid parameter (must be Fixnum or BitVector)");
    }
  } else if(2==argc) {
    if(FIXNUM_P(argv[1])) {
      if(VALID_BITNUM(argv[0]))
	return bv_init_from_fixnum(self, argv[0], argv[1]);
      else if(RTEST(argv[0]))
	return bv_init_from_fixnum(self, fixnum32, argv[1]);
      else
	return bv_init_from_fixnum(self, fixnum31, argv[1]);
    } else if(T_BIGNUM == TYPE(argv[1])) {
      if(VALID_BITNUM(argv[0]))
	return bv_init_from_bignum(self, argv[0], argv[1]);
      else {
	bits = NUM2UINT(rb_funcall(argv[1],idSize,0))*8;
	return bv_init_from_bignum(self, INT2NUM(bits), argv[1]);
      }
    }
  }
  rb_raise(rb_eArgError, "invalid parameters");
}

/**
 * Similar to Array.[]=
 *
 * bv[i] = v            => Set value of bit i to v
 * bv[r] = v            => Set values of bits in range r to v
 * bv[s,l] = v          => Set values of bits in range s...(s+l) to v
 *
 * v can be {0, false} or {1, true} or bit vector of same size as the bits to
 * be assigned.
 */
static VALUE
bv_aset(int argc, VALUE *argv, VALUE self)
{
  N_int beg, len;
  wordptr selfll = LLBV(self);
  VALUE new_val;
  wordptr otherll;

  if (argc == 3) {
    if(!VALID_BITREF(argv[0],selfll))
      BV_INDEX_ERROR("aset");
    if(!KINDOF_INT(argv[1]))
      rb_raise(rb_eArgError, "arg2 has invalid type (should be kind-of Integer)");
    beg = NUM2UINT(argv[0]);
    len = NUM2UINT(argv[1]);
    new_val = argv[2];
    goto assign_bits;
  }
  if (argc != 2) {
    rb_raise(rb_eArgError, "wrong # of arguments(%d for 2 or 3)", argc);
  }
  if (KINDOF_INT(argv[0])) {
    if(!VALID_BITREF(argv[0],selfll))
      BV_INDEX_ERROR("aset");
    beg = NUM2UINT(argv[0]);
    len = 1;
    new_val = argv[1];
    goto assign_bits;
  }
  if (KINDOF_RANGE(argv[0]) &&
      rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, 
		       bits_(selfll), 1)) {
    new_val = argv[1];
    goto assign_bits;
  }

  rb_raise(rb_eArgError, "invalid arguments");    

 assign_bits:
  if(ZERO_OR_FALSE(new_val))
    BitVector_Interval_Empty(selfll, beg, beg+len-1);
  else if(KINDOF_BV(new_val)) {
    otherll = LLBV(new_val);
    if(bits_(otherll) != len)
      rb_raise(rb_eRangeError, "size of bit vectors mismatch");
    BitVector_Interval_Copy(selfll, otherll, beg, 0, len);
  } else
    BitVector_Interval_Fill(selfll, beg, beg+len-1);
  return new_val;
}

/*
static VALUE
bv_aset(int argc, VALUE *argv, VALUE self)
{
  N_int beg, len;
  wordptr selfll = LLBV(self);

  if (argc == 3) {
    if(!VALID_BITREF(argv[0],selfll))
      BV_INDEX_ERROR("aset");
    if(!KINDOF_INT(argv[1]))
      rb_raise(rb_eArgError, "arg2 has invalid type (should be kind-of Integer)");
    beg = NUM2UINT(argv[0]);
    len = NUM2UINT(argv[1]);
    if(ZERO_OR_FALSE(argv[2]))
      BitVector_Interval_Empty(selfll, beg, beg+len-1);
    else
      BitVector_Interval_Fill(selfll, beg, beg+len-1);
    return argv[2];
  }
  if (argc != 2) {
    rb_raise(rb_eArgError, "wrong # of arguments(%d for 2 or 3)", argc);
  }
  if (KINDOF_INT(argv[0])) {
    if(!VALID_BITREF(argv[0],selfll))
      BV_INDEX_ERROR("aset");
    if(ZERO_OR_FALSE(argv[1]))
      BitVector_Bit_Off(selfll, NUM2UINT(argv[0]));
    else
      BitVector_Bit_On(selfll, NUM2UINT(argv[0]));
    return argv[1];
  }
  if (KINDOF_RANGE(argv[0]) &&
      rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, 
		       bits_(selfll), 1)) {
    if(ZERO_OR_FALSE(argv[1]))
      BitVector_Interval_Empty(selfll, beg, beg+len-1);
    else
      BitVector_Interval_Fill(selfll, beg, beg+len-1);
    return argv[1];
  }
  rb_raise(rb_eArgError, "invalid arguments");    
}
 */

static VALUE
bv_length(VALUE self)
{
  return INT2NUM(bits_(LLBV(self)));
}

static void
randomize_bits(wordptr bitvector, N_int start, N_int end, double probability)
{
  double randfloat;
  N_int i;
  N_long rand_bits;
  N_int current = start;
  N_int bits_left = end-start+1;
  N_int chunk_size;

  if(probability != 0.5) {
    for(i = start; i <= end; i++)
      if(RFLOAT(rb_funcall(mKernel, idRand, 1, fixnum0))->value <= probability)
	BitVector_bit_flip(bitvector, i);
  } else {
    i = bits_left/28;
    for(; i>0; i--) {
      /* Get a random fixnum. We only use 28 bits from it so that we're sure no */
      /* Bignums are involved. */
      rand_bits = FIX2UINT(rb_funcall(mKernel, idRand, 1, fixnum2_28));

      /* Copy them to bitvector */
      BitVector_Chunk_Store(bitvector, 28, current, rand_bits);
      current += 28;
    }

    if(bits_left % 28) {
      rand_bits = FIX2UINT(rb_funcall(mKernel, idRand, 1, fixnum2_28));
      BitVector_Chunk_Store(bitvector, bits_left%28, current, rand_bits);
    }
  }
}

/**
 * bv.randomize(prob=0.5)       => Randomize all bits with probability prob
 * bv.randomize(s, prob=0.5)    => Randomize bit s with probability prob
 * bv.randomize(s, l, prob=0.5) => Randomize bits s...(s+l) with prob
 * bv.randomize(range, prob=0.5) => Randomize bits in range with prob
 */
static VALUE
bv_randomize(int argc, VALUE *argv, VALUE self)
{
  wordptr selfll = LLBV(self);
  double prob = 0.5;
  N_int beg, len;

  if(argc==0) {
    beg = 0;
    len = bits_(selfll);
  } else if(argc==1) {
    if(KINDOF_INT(argv[0])) {
      if(!VALID_BITREF(argv[0],selfll))
	BV_INDEX_ERROR("randomize");
      beg = NUM2UINT(argv[0]);
      len = 1;
    } else if(ISFLOAT(argv[0])) {
      beg = 0;
      len = bits_(selfll);
      prob = RFLOAT(argv[0])->value;
    } else if(KINDOF_RANGE(argv[0])) {
      rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, bits_(selfll), 1);
    } else
      rb_raise(rb_eArgError, "invalid parameters");
  } else if(argc==2) {
    if(VALID_BITNUM(argv[0]) && VALID_BITNUM(argv[1])) {
      beg = NUM2UINT(argv[0]);
      len = NUM2UINT(argv[1]);
    } else if(VALID_BITNUM(argv[0]) && ISFLOAT(argv[1])) {
      beg = NUM2UINT(argv[0]);
      len = 1;
      prob = RFLOAT(argv[1])->value;
    } else if(rb_obj_is_kind_of(argv[0], rb_cRange) &&
	      T_FLOAT == TYPE(argv[1])) {
      rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, bits_(selfll), 1);
      prob = RFLOAT(argv[1])->value;
    } else
      rb_raise(rb_eArgError, "invalid parameters");
  } else if(argc==3) {
    if(VALID_BITNUM(argv[0]) && VALID_BITNUM(argv[1]) &&
       (T_FLOAT == TYPE(argv[2]))) {
      beg = NUM2UINT(argv[0]);
      len = NUM2UINT(argv[1]);
      prob = RFLOAT(argv[2])->value;
    } else {
      rb_raise(rb_eArgError, "invalid parameters");
    }
  } else {
    rb_raise(rb_eArgError, "invalid parameters");
  }

 randomize_now:
  if(!VALID_BITREF2(beg,selfll))
    BV_INDEX_ERROR("randomize");
  randomize_bits(selfll, beg, beg+len-1, prob);
  return self;
}

/**
 * bv.fill         => All bits gets value 1
 * bv.fill(s)      => Bit s gets value 1
 * bv.fill(s,l)    => Bits s...(s+l) gets value 1
 * bv.fill(range)  => Bits in range gets value 1
 */
static VALUE
bv_fill(int argc, VALUE *argv, VALUE self)
{
  wordptr selfll = LLBV(self);
  N_int beg, len;

  if(argc==0)
    BitVector_Fill(selfll);
  else if(argc==2) {
    if(!VALID_BITREF(argv[0],selfll))
      BV_INDEX_ERROR("fill");
    beg = NUM2UINT(argv[0]);
    len = NUM2UINT(argv[1]);
    BitVector_Interval_Fill(selfll, beg, beg+len-1);
  } else if((argc==1) && VALID_BITREF(argv[0],selfll))
    BitVector_Bit_On(selfll, NUM2UINT(argv[0]));
  else if (rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, 
			    bits_(selfll), 1)) {
    if(!VALID_BITREF2(beg,selfll))
      BV_INDEX_ERROR("fill");
    BitVector_Interval_Fill(selfll, beg, beg+len-1);
  } else
    rb_raise(rb_eArgError, "invalid parameters");

  return self;
}

/**
 * bv.empty         => All bits gets value 0
 * bv.empty(s)      => Bits s gets value 0
 * bv.empty(s,l)    => Bits s...(s+l) gets value 0
 * bv.empty(range)  => Bits in range gets value 0
 */
static VALUE
bv_empty(int argc, VALUE *argv, VALUE self)
{
  wordptr selfll = LLBV(self);
  N_int beg, len;

  if(argc==0)
    BitVector_Empty(selfll);
  else if(argc==2) {
    beg = NUM2UINT(argv[0]);
    len = NUM2UINT(argv[1]);
    BitVector_Interval_Empty(selfll, beg, beg+len-1);
  } else if((argc==1) && VALID_BITREF(argv[0],selfll))
    BitVector_Bit_Off(selfll, NUM2UINT(argv[0]));
  else if (rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, bits_(selfll), 1))
    BitVector_Interval_Empty(selfll, beg, beg+len-1);

  return self;
}

/**
 * bv.flip         => All bits are flipped
 * bv.flip(s)      => Bits s is flipped
 * bv.flip(s,l)    => Bits s...(s+l) are flipped
 * bv.flip(range)  => Bits in range are flipped
 */
static VALUE
bv_flip(int argc, VALUE *argv, VALUE self)
{
  wordptr selfll = LLBV(self);
  N_int beg, len;

  if(argc==0)
    BitVector_Flip(selfll);
  else if(argc==2) {
    beg = NUM2UINT(argv[0]);
    len = NUM2UINT(argv[1]);
    BitVector_Interval_Flip(selfll, beg, beg+len-1);
  } else if((argc==1) && VALID_BITREF(argv[0],selfll))
    BitVector_bit_flip(selfll, NUM2UINT(argv[0]));
  else if (rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, bits_(selfll), 1))
    BitVector_Interval_Flip(selfll, beg, beg+len-1);

  return self;
}

/**
 * bv.reverse         => All bits are reversed
 * bv.reverse(s)      => Bits s reversed (ie. nothing happens!)
 * bv.reverse(s,l)    => Bits s...(s+l) are reversed
 * bv.reverse(range)  => Bits in range are reversed
 */
static VALUE
bv_reverse(int argc, VALUE *argv, VALUE self)
{
  wordptr selfll = LLBV(self);
  wordptr newll;
  N_int beg, len;

  if(argc==0) {
    newll = BitVector_Create(bits_(selfll), false);
    BitVector_Reverse(newll, selfll);
    BitVector_Destroy(selfll);
    get_struct_from_rbv(self)->llbv = newll;
  } else if(argc==2) {
    beg = NUM2UINT(argv[0]);
    len = NUM2UINT(argv[1]);
    BitVector_Interval_Reverse(selfll, beg, beg+len-1);
  } else if (rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, bits_(selfll), 1))
    BitVector_Interval_Reverse(selfll, beg, beg+len-1);

  return self;
}

static VALUE
bv_primes(VALUE self)
{
  BitVector_Primes(LLBV(self));
  return self;
}

static VALUE
bv_is_empty(VALUE self)
{
  if(BitVector_is_empty(LLBV(self)))
    return Qtrue;
  else
    return Qfalse;
}

static VALUE
bv_is_full(VALUE self)
{
  if(BitVector_is_full(LLBV(self)))
    return Qtrue;
  else
    return Qfalse;
}

static VALUE
bv_is_equal(VALUE self, VALUE other)
{
  if(KINDOF_BV(other) && BitVector_equal(LLBV(self), LLBV(other)))
    return Qtrue;
  else
    return Qfalse;
}

static VALUE
bv_lexicompare(VALUE self, VALUE other)
{
  if(!KINDOF_BV(other))
    rb_raise(rb_eTypeError, "invalid type (lexicompare)");
  return INT2FIX(BitVector_Lexicompare(LLBV(self), LLBV(other)));
}

static VALUE
bv_compare(VALUE self, VALUE other)
{
  if(!KINDOF_BV(other))
    rb_raise(rb_eTypeError, "invalid type (<=> or compare)");
  return INT2FIX(BitVector_Compare(LLBV(self), LLBV(other)));
}

static VALUE
bv_to_binstr(VALUE self)
{
  charptr p = BitVector_to_Bin(LLBV(self));
  VALUE str = rb_str_new2(p);
  BitVector_Dispose(p);
  return str;
}

static VALUE
bv_to_hexstr(VALUE self)
{
  charptr p = BitVector_to_Hex(LLBV(self));
  VALUE str = rb_str_new2(p);
  BitVector_Dispose(p);
  return str;
}

static VALUE
bv_to_decstr(VALUE self)
{
  charptr p = BitVector_to_Dec(LLBV(self));
  VALUE str = rb_str_new2(p);
  BitVector_Dispose(p);
  return str;
}

static VALUE
bv_to_enumstr(VALUE self)
{
  charptr p = BitVector_to_Enum(LLBV(self));
  VALUE str = rb_str_new2(p);
  BitVector_Dispose(p);
  return str;
}

static VALUE
bv_off(VALUE self, VALUE bit)
{
  BitVector_Bit_Off(LLBV(self), NUM2UINT(bit));
  return self;
}

static VALUE
bv_on(VALUE self, VALUE bit)
{
  BitVector_Bit_On(LLBV(self), NUM2UINT(bit));
  return self;
}

static VALUE
bv_flipbit(VALUE self, VALUE bit)
{
  if(BitVector_bit_flip(LLBV(self), NUM2UINT(bit)))
    return fixnum1;
  else
    return fixnum0;
}

static VALUE
bv_bitref(VALUE self, VALUE bit)
{
  if(BitVector_bit_test(LLBV(self), NUM2UINT(bit)))
    return fixnum1;
  else
    return fixnum0;
}

static VALUE
bv_aref(int argc, VALUE *argv, VALUE self)
{
  N_int beg, len, i, cnt;
  wordptr selfll = LLBV(self);
  wordptr newll;

  /* bv[anInteger] */
  if (argc == 1 && KINDOF_INT(argv[0])) {
    if(!VALID_BITREF(argv[0], selfll))
      BV_INDEX_ERROR("aref");
    beg = NUM2UINT(argv[0]);
    len = 1;
    goto get_aref_bits;
  }
  
  /* bv[anInteger, anInteger] */
  if (argc == 2 && KINDOF_INT(argv[0]) && KINDOF_INT(argv[1])) {
    if(!VALID_BITREF(argv[0], selfll))
      BV_INDEX_ERROR("aref");
    beg = NUM2UINT(argv[0]);
    len = NUM2UINT(argv[1]);
    goto get_aref_bits;
  }

  /* bv[aRange] */
  if (argc==1 && KINDOF_RANGE(argv[0])) {
    rb_range_beg_len(argv[0], (long*)&beg, (long*)&len, bits_(selfll), 1);
    if(!VALID_BITREF2(beg, selfll))
      BV_INDEX_ERROR("aref");
    goto get_aref_bits;
  }

  rb_raise(rb_eArgError, "invalid arguments");    

 get_aref_bits:
  if(len==1) {
    if(BitVector_bit_test(selfll, beg))
      return fixnum1;
    else
      return fixnum0;
  } else if(len==0) {
    return Qnil;
  } else {
    newll = BitVector_Create(len, true);
    BitVector_Interval_Copy(newll, selfll, 0, beg, len); /* Does not work!! */
    return make_ruby_bitvector(newll);
  }
}

static VALUE
bv_test(VALUE self, VALUE bit)
{
  if(BitVector_bit_test(LLBV(self), NUM2UINT(bit)))
    return Qtrue;
  else
    return Qfalse;
}

static VALUE
bv_set_norm(VALUE self)
{
  return INT2NUM(Set_Norm(LLBV(self)));
}

static VALUE
bv_set_union(VALUE self, VALUE other)
{
  wordptr selfll = LLBV(self);
  wordptr otherll;
  wordptr newll;
  int bits = bits_(selfll);
  int bits_other;

  if(!KINDOF_BV(other))
    rb_raise(rb_eTypeError, "invalid type (union)");
  otherll = LLBV(other);
  bits_other = bits_(otherll);

  if(bits != bits_other)
    rb_raise(rb_eArgError, "vectors differ in length");

  newll = BitVector_Create(bits, false); /* No need to clear */
  Set_Union(newll, selfll, otherll);

  return make_ruby_bitvector(newll);
}

static VALUE
bv_set_intersection(VALUE self, VALUE other)
{
  wordptr selfll = LLBV(self);
  wordptr otherll;
  wordptr newll;
  int bits = bits_(selfll);
  int bits_other;

  if(!KINDOF_BV(other))
    rb_raise(rb_eTypeError, "invalid type (union)");
  otherll = LLBV(other);
  bits_other = bits_(otherll);

  if(bits != bits_other)
    rb_raise(rb_eArgError, "vectors differ in length");

  newll = BitVector_Create(bits, false); /* No need to clear */
  Set_Intersection(newll, selfll, otherll);

  return make_ruby_bitvector(newll);
}

static VALUE
bv_set_difference(VALUE self, VALUE other)
{
  wordptr selfll = LLBV(self);
  wordptr otherll;
  wordptr newll;
  int bits = bits_(selfll);
  int bits_other;

  if(!KINDOF_BV(other))
    rb_raise(rb_eTypeError, "invalid type (union)");
  otherll = LLBV(other);
  bits_other = bits_(otherll);

  if(bits != bits_other)
    rb_raise(rb_eArgError, "vectors differ in length");

  newll = BitVector_Create(bits, false); /* No need to clear */
  Set_Difference(newll, selfll, otherll);

  return make_ruby_bitvector(newll);
}

static VALUE
bv_set_exor(VALUE self, VALUE other)
{
  wordptr selfll = LLBV(self);
  wordptr otherll;
  wordptr newll;
  int bits = bits_(selfll);
  int bits_other;

  if(!KINDOF_BV(other))
    rb_raise(rb_eTypeError, "invalid type (union)");
  otherll = LLBV(other);
  bits_other = bits_(otherll);

  if(bits != bits_other)
    rb_raise(rb_eArgError, "vectors differ in length");

  newll = BitVector_Create(bits, false); /* No need to clear */
  Set_ExclusiveOr(newll, selfll, otherll);

  return make_ruby_bitvector(newll);
}


static VALUE
bv_set_complement(VALUE self)
{
  wordptr selfll = LLBV(self);
  wordptr newll;

  newll = BitVector_Create(bits_(selfll), false); /* No need to clear */
  Set_Complement(newll, selfll);

  return make_ruby_bitvector(newll);
}

static VALUE
bv_set_is_subset(VALUE self, VALUE other)
{
  if(KINDOF_BV(other) && Set_subset(LLBV(self), LLBV(other)))
    return Qtrue;
  else
    return Qfalse;
}

static VALUE
bv_set_is_superset(VALUE self, VALUE other)
{
  if(KINDOF_BV(other) && Set_subset(LLBV(other), LLBV(self)))
    return Qtrue;
  else
    return Qfalse;
}

static VALUE
bv_set_min(VALUE self)
{
  return INT2NUM(Set_Min(LLBV(self)));
}

static VALUE
bv_set_max(VALUE self)
{
  return INT2NUM(Set_Max(LLBV(self)));
}

static VALUE
bv_get_lsb(VALUE self)
{
  if(BitVector_lsb_(LLBV(self)))
    return fixnum1;
  else
    return fixnum0;
}

static VALUE
bv_set_lsb(VALUE self, VALUE newVal)
{
  if(ZERO_OR_FALSE(newVal))
    BitVector_LSB(LLBV(self), false);
  else
    BitVector_LSB(LLBV(self), true);
  return self;
}

static VALUE
bv_get_msb(VALUE self)
{
  if(BitVector_msb_(LLBV(self)))
    return fixnum1;
  else
    return fixnum0;
}

static VALUE
bv_set_msb(VALUE self, VALUE newVal)
{
  if(ZERO_OR_FALSE(newVal))
    BitVector_MSB(LLBV(self), false);
  else
    BitVector_MSB(LLBV(self), true);
  return self;
}

static VALUE
bv_rotate_left(VALUE self)
{
  if(BitVector_rotate_left(LLBV(self)))
    return fixnum1;
  else
    return fixnum0;
}

static VALUE
bv_rotate_right(VALUE self)
{
  if(BitVector_rotate_right(LLBV(self)))
    return fixnum1;
  else
    return fixnum0;
}

static VALUE
bv_shift_left(VALUE self, VALUE carryIn)
{
  if(BitVector_shift_left(LLBV(self), !ZERO_OR_FALSE(carryIn)))
    return fixnum1;
  else
    return fixnum0;
}

static VALUE
bv_shift_right(VALUE self, VALUE carryIn)
{
  if(BitVector_shift_right(LLBV(self), !ZERO_OR_FALSE(carryIn)))
    return fixnum1;
  else
    return fixnum0;
}

static VALUE
bv_move_left(VALUE self, VALUE steps)
{
  if(!KINDOF_INT(steps))
    rb_raise(rb_eTypeError, "invalid type");
  BitVector_Move_Left(LLBV(self), NUM2UINT(steps));
  return self;
}

static VALUE
bv_move_right(VALUE self, VALUE steps)
{
  if(!KINDOF_INT(steps))
    rb_raise(rb_eTypeError, "invalid type");
  BitVector_Move_Right(LLBV(self), NUM2UINT(steps));
  return self;
}

static VALUE
bv_increment(VALUE self)
{
  BitVector_increment(LLBV(self));
  return self;
}

static VALUE
bv_decrement(VALUE self)
{
  BitVector_decrement(LLBV(self));
  return self;
}

static VALUE
bv_substitute(VALUE self, VALUE other, 
	      VALUE off1, VALUE len1, VALUE off2, VALUE len2)
{
  wordptr selfll = LLBV(self);
  wordptr otherll = LLBV(other);
  N_int self_bits = bits_(selfll);
  N_int other_bits = bits_(otherll);
  N_int offset1;
  N_int offset2;

  if(!(KINDOF_INT(off1) && KINDOF_INT(off2) && 
       KINDOF_INT(len1) && KINDOF_INT(len2)))
    rb_raise(rb_eArgError, "invalid arg types");

  offset1 = NUM2UINT(off1);
  offset2 = NUM2UINT(off2);

  if(!(offset1 >= 0 && offset1<(self_bits+1) &&
       offset2 >= 0 && offset2<(other_bits+1)))
    BV_INDEX_ERROR("substitute");

  BitVector_Interval_Substitute(selfll, otherll,
				offset1, NUM2UINT(len1),
				offset2, NUM2UINT(len2));
  return self;
}

static VALUE
bv_dump(VALUE self, VALUE limit)
{
  N_int num_chars;
  wordptr selfll = LLBV(self);
  charptr str = BitVector_Block_Read(selfll, &num_chars);
  VALUE dumped_str = rb_str_new2(str);
  VALUE ary = rb_ary_new();

  BitVector_Dispose(str);
  rb_ary_push(ary, INT2NUM(bits_(selfll)));
  rb_ary_push(ary, dumped_str);
  return rb_funcall(mMarshal, idDump, 1, ary);
}

static VALUE
bv_load(VALUE class, VALUE aString)
{
  VALUE ary = rb_funcall(mMarshal, idLoad, 1, aString);
  VALUE argv[1];
  VALUE obj;
  VALUE temp;

  argv[0] = rb_ary_entry(ary, 0);
  obj = bv_s_new(1, argv, class);
  temp = rb_ary_entry(ary,1);
  BitVector_Block_Store(LLBV(obj), RSTRING(temp)->ptr, RSTRING(temp)->len);
  return obj;
}

static VALUE
bv_to_uint(VALUE self)
{
  wordptr selfll = LLBV(self);
  N_int num_bits = bits_(selfll);
  VALUE acc = fixnum0;
  VALUE temp;
  N_int i, bits_left, current = num_bits;
  N_long l;

  if(num_bits < 30) {
    l = BitVector_Chunk_Read(selfll, num_bits, 0);
    return UINT2NUM((unsigned int)l);
  } else {
    i = num_bits/29;
    for(i = 0; i < (num_bits/29); i++) {
      current -= 29;
      acc = rb_funcall(acc, idMult, 1, fix2_to29); /* acc *= (2**29) */
      l = BitVector_Chunk_Read(selfll, 29, current);
      temp = INT2FIX((unsigned int)l);
      acc = rb_funcall(acc, idAdd, 1, temp); /* acc += temp */
    }
    bits_left = num_bits%29;
    if(bits_left) {
      /* acc *= (2**bits_left) */
      acc = rb_funcall(acc, idMult, 1, num2_toX[bits_left]); 
      l = BitVector_Chunk_Read(selfll, bits_left, 0);
      temp = UINT2NUM((unsigned int)l);
      acc = rb_funcall(acc, idAdd, 1, temp); /* acc += temp */
    }
    return acc;
  }
}

static VALUE
bv_to_int(VALUE self)
{
  wordptr selfll = LLBV(self);
  VALUE uint = bv_to_uint(self);
  VALUE temp;

  if(-1 == BitVector_Sign(selfll)) {
    temp = rb_big_pow(fixnum2, UINT2NUM(bits_(selfll)));
    return rb_funcall(uint, idMinus, 1, temp);
  } else {
    return uint;
  }
}

static VALUE
bv_ones(VALUE self)
{
  VALUE ary = rb_ary_new();
  wordptr selfll = LLBV(self);
  N_int i = 0;

  for(i = 0; i < bits_(selfll); i++) {
    if(BitVector_bit_test(selfll, i))
      rb_ary_push(ary, INT2FIX(i));
  }

  return ary;
}

static VALUE
bv_zeroes(VALUE self)
{
  VALUE ary = rb_ary_new();
  wordptr selfll = LLBV(self);
  N_int i = 0;

  for(i = 0; i < bits_(selfll); i++) {
    if(!BitVector_bit_test(selfll, i))
      rb_ary_push(ary, INT2FIX(i));
  }

  return ary;
}

static VALUE
bv_resize(VALUE self, VALUE newSize)
{
  wordptr llbv;
  struct RBitVector *sbv;
  N_int new_bits;

  LLASBV(self, &llbv, &sbv);
  if(!VALID_BITNUM(newSize))
    BV_SIZE_ERROR("resize");

  sbv->llbv = BitVector_Resize(llbv, NUM2UINT(newSize));
  if(NULL == sbv->llbv)
    BV_MEMORY_ERROR("resize");

  return self;
}

static VALUE
bv_set_carry(VALUE self, VALUE newVal)
{
#ifdef HAVE_RB_CVAR_DECLARE
  rb_cvar_set(cBitVector, idCvarCarry, newVal);
#else
  rb_cvar_set(cBitVector, idCvarCarry, newVal, Qfalse);
#endif
}

static VALUE
bv_get_carry(VALUE self)
{
  return rb_cvar_get(cBitVector, idCvarCarry);
}

static VALUE
bv_add(VALUE self, VALUE other)
{
  wordptr selfll = LLBV(self);
  N_int num_bits = bits_(selfll);
  wordptr otherll;
  wordptr newll;
  boolean carry = 0;
  VALUE argv[2];

  if(KINDOF_BV(other)) {
    otherll = LLBV(other);
  } else if(KINDOF_INT(other)) {
    argv[0] = other;
    argv[1] = UINT2NUM(num_bits);
    otherll = LLBV(bv_s_from_int(2, argv, cBitVector));
  } else {
    rb_raise(rb_eTypeError, "invalid type");
  }

  if(bits_(otherll) != num_bits)
    BV_SIZE_ERROR("add");

  newll = BitVector_Create(num_bits, false);
  BitVector_compute(newll, selfll, otherll, false, &carry);

  bv_set_carry(self, (carry ? fixnum1 : fixnum0));

  return make_ruby_bitvector(newll);
}

static VALUE
bv_sub(VALUE self, VALUE other)
{
  wordptr selfll = LLBV(self);
  N_int num_bits = bits_(selfll);
  wordptr otherll;
  wordptr newll;
  boolean carry = 0;
  VALUE argv[2];

  if(KINDOF_BV(other)) {
    otherll = LLBV(other);
  } else if(KINDOF_INT(other)) {
    argv[0] = other;
    argv[1] = UINT2NUM(num_bits);
    otherll = LLBV(bv_s_from_int(2, argv, cBitVector));
  } else {
    rb_raise(rb_eTypeError, "invalid type");
  }

  if(bits_(otherll) != num_bits)
    BV_SIZE_ERROR("sub");

  newll = BitVector_Create(num_bits, false);
  BitVector_compute(newll, selfll, otherll, true, &carry);

  bv_set_carry(self, (carry ? fixnum1 : fixnum0));

  return make_ruby_bitvector(newll);
}

static VALUE
bv_negate(VALUE self)
{
  wordptr selfll = LLBV(self);
  N_int num_bits = bits_(selfll);
  wordptr newll;

  newll = BitVector_Create(num_bits, false);
  BitVector_Negate(newll, selfll);
  return make_ruby_bitvector(newll);
}

static VALUE
bv_abs(VALUE self)
{
  wordptr selfll = LLBV(self);
  N_int num_bits = bits_(selfll);
  wordptr newll;

  newll = BitVector_Create(num_bits, false);
  BitVector_Absolute(newll, selfll);
  return make_ruby_bitvector(newll);
}

static VALUE
bv_sign(VALUE self)
{
  Z_int sign = BitVector_Sign(LLBV(self));
  switch(sign) {
  case -1:
    return fixnumneg1;
  case 1:
    return fixnum1;
  case 0:
    return fixnum0;
  }
}

static VALUE
bv_multiply(VALUE self, VALUE other)
{
  wordptr selfll = LLBV(self);
  N_int num_bits = bits_(selfll);
  wordptr otherll;
  wordptr newll;
  VALUE argv[2];
  ErrCode err;

  if(KINDOF_BV(other)) {
    otherll = LLBV(other);
  } else if(KINDOF_INT(other)) {
    argv[0] = other;
    argv[1] = UINT2NUM(num_bits);
    otherll = LLBV(bv_s_from_int(2, argv, cBitVector));
  } else {
    rb_raise(rb_eTypeError, "invalid type");
  }

  if(bits_(otherll) != num_bits)
    BV_SIZE_ERROR("add");

  newll = BitVector_Create(2*num_bits, false); /* Expand since multiply... */
  
  if(err = BitVector_Multiply(newll, selfll, otherll))    
    BV_ERRORCODE(err, "multiply");

  return make_ruby_bitvector(newll);
}

static VALUE
bv_divide(VALUE self, VALUE other)
{
  wordptr selfll = LLBV(self);
  N_int num_bits = bits_(selfll);
  wordptr otherll;
  wordptr qll;
  wordptr rll;
  VALUE argv[2];

  if(KINDOF_BV(other)) {
    otherll = LLBV(other);
  } else if(KINDOF_INT(other)) {
    argv[0] = other;
    argv[1] = UINT2NUM(num_bits);
    otherll = LLBV(bv_s_from_int(2, argv, cBitVector));
  } else {
    rb_raise(rb_eTypeError, "invalid type");
  }

  if(bits_(otherll) != num_bits)
    BV_SIZE_ERROR("add");

  qll = BitVector_Create(num_bits, false);
  rll = BitVector_Create(num_bits, false);
  BitVector_Divide(qll, selfll, otherll, rll);
  BitVector_Destroy(rll); /* TODO: Make use of Remainder */

  return make_ruby_bitvector(qll);
}

/** Init code **/
void Init_bitvector()
{
  int i;
  char buffer[20];

  BitVector_Boot();
  
  mMarshal = rb_eval_string("Marshal");
  mKernel = rb_eval_string("Kernel");
  mMath = rb_eval_string("Math");
  idNew = rb_intern("new");
  idSize = rb_intern("size");
  idAref = rb_intern("[]");
  idDump = rb_intern("dump");
  idLoad = rb_intern("load");
  idAdd = rb_intern("+");
  idMinus = rb_intern("-");
  idMult = rb_intern("*");
  idRand = rb_intern("rand");
  idBetween = rb_intern("between?");
  idCvarCarry = rb_intern("@@carry");
  idLog10 = rb_intern("log10");
  fixnum1 = INT2FIX(1);
  fixnum2 = INT2FIX(2);
  fixnum0 = INT2FIX(0);
  fixnumneg1 = INT2FIX(-1);
  fixnum31 = INT2FIX(31);
  fixnum32 = INT2FIX(32);
  fixnum2_28 = UINT2NUM(1<<28);
  fix2_to29 = INT2FIX(1<<29);
  for(i=0; i<31; i++)
    num2_toX[i] = UINT2NUM(1<<i);
  log10_2 = rb_eval_string("Math.log10(2.0)");

  /*
   * Max size of bit vectors is the max value that can be held in an
   * N_int since Steffen Beyer's Bit::Vector uses N_int to specify
   * size when creating a bit vector.
   */

  maxunsignedint = UINT2NUM((N_int)(-1));

  /*
  rb_funcall(rb_funcall(fixnum2, rb_intern("**"), 1, INT2FIX(sizeof(N_int)*8)), 
		       rb_intern("-"), 1, fixnum1);
  */

  cBitVector = rb_define_class("BitVector", rb_cObject);

  rb_define_singleton_method(cBitVector, "version", bv_version, 0);

  rb_define_singleton_method(cBitVector, "new", bv_s_new, -1);
  rb_define_singleton_method(cBitVector, "from_bin", bv_s_from_bin, 2);
  rb_define_singleton_method(cBitVector, "from_dec", bv_s_from_dec, 2);
  rb_define_singleton_method(cBitVector, "from_hex", bv_s_from_hex, 2);
  rb_define_singleton_method(cBitVector, "from_enum", bv_s_from_enum, 2);
  rb_define_singleton_method(cBitVector, "from_int", bv_s_from_int, -1);

  rb_define_method(cBitVector, "initialize", bv_initialize, -1);
  rb_define_method(cBitVector, "length", bv_length, 0);

  rb_define_method(cBitVector, "clone", bv_clone, 0);

  rb_define_method(cBitVector, "concat", bv_concat, 1);

  rb_define_method(cBitVector, "fill", bv_fill, -1);
  rb_define_method(cBitVector, "empty", bv_empty, -1);
  rb_define_method(cBitVector, "flip", bv_flip, -1);
  rb_define_method(cBitVector, "reverse", bv_reverse, -1);

  rb_define_method(cBitVector, "primes", bv_primes, 0);

  rb_define_method(cBitVector, "empty?", bv_is_empty, 0);
  rb_define_method(cBitVector, "full?", bv_is_full, 0);
  rb_define_method(cBitVector, "equal?", bv_is_equal, 1);
  rb_define_method(cBitVector, "==", bv_is_equal, 1);
  rb_define_method(cBitVector, "lexicompare", bv_lexicompare, 1);
  rb_define_method(cBitVector, "compare", bv_compare, 1);
  rb_define_method(cBitVector, "<=>", bv_compare, 1);

  rb_define_method(cBitVector, "to_bin_str", bv_to_binstr, 0);
  rb_define_method(cBitVector, "inspect", bv_to_binstr, 0);
  rb_define_method(cBitVector, "to_hex_str", bv_to_hexstr, 0);
  rb_define_method(cBitVector, "to_dec_str", bv_to_decstr, 0);
  rb_define_method(cBitVector, "to_enum_str", bv_to_enumstr, 0);

  rb_define_method(cBitVector, "on", bv_on, 1);
  rb_define_method(cBitVector, "bit_on", bv_on, 1);
  rb_define_method(cBitVector, "off", bv_off, 1);
  rb_define_method(cBitVector, "bit_off", bv_off, 1);
  rb_define_method(cBitVector, "flip_bit", bv_flipbit, 1);
  rb_define_method(cBitVector, "bit_flip", bv_flipbit, 1);

  rb_define_method(cBitVector, "bit", bv_bitref, 1);
  rb_define_method(cBitVector, "test?", bv_test, 1);
  rb_define_method(cBitVector, "[]", bv_aref, -1);

  rb_define_method(cBitVector, "set", bv_set_bit, 2);
  rb_define_method(cBitVector, "[]=", bv_aset, -1);
 
  rb_define_method(cBitVector, "union", bv_set_union, 1);
  rb_define_method(cBitVector, "|", bv_set_union, 1);
  rb_define_method(cBitVector, "intersection", bv_set_intersection, 1);
  rb_define_method(cBitVector, "&", bv_set_intersection, 1);
  rb_define_method(cBitVector, "difference", bv_set_difference, 1);
  rb_define_method(cBitVector, "-", bv_set_difference, 1);
  rb_define_method(cBitVector, "exclusive_or", bv_set_exor, 1);
  rb_define_method(cBitVector, "^", bv_set_exor, 1);
  rb_define_method(cBitVector, "complement", bv_set_complement, 0);
  rb_define_method(cBitVector, "~", bv_set_complement, 0);
  rb_define_method(cBitVector, "subset?", bv_set_is_subset, 1);
  rb_define_method(cBitVector, "superset?", bv_set_is_superset, 1);
  rb_define_method(cBitVector, "norm", bv_set_norm, 0);
  rb_define_method(cBitVector, "min", bv_set_min, 0);
  rb_define_method(cBitVector, "min", bv_set_min, 0);
  rb_define_method(cBitVector, "max", bv_set_max, 0);
  rb_define_method(cBitVector, "max", bv_set_max, 0);

  rb_define_method(cBitVector, "msb=", bv_set_msb, 1);
  rb_define_method(cBitVector, "msb", bv_get_msb, 0);
  rb_define_method(cBitVector, "lsb=", bv_set_lsb, 1);
  rb_define_method(cBitVector, "lsb", bv_get_lsb, 0);
  rb_define_method(cBitVector, "rotate_left", bv_rotate_left, 0);
  rb_define_method(cBitVector, "rotate_right", bv_rotate_right, 0);
  rb_define_method(cBitVector, "shift_left", bv_shift_left, 1);
  rb_define_method(cBitVector, "shift_right", bv_shift_right, 1);
  rb_define_method(cBitVector, "<<", bv_move_left, 1);
  rb_define_method(cBitVector, ">>", bv_move_right, 1);

  rb_define_method(cBitVector, "succ", bv_increment, 0);
  rb_define_method(cBitVector, "pred", bv_decrement, 0);

  rb_define_method(cBitVector, "_dump", bv_dump, 1);
  rb_define_singleton_method(cBitVector, "_load", bv_load, 1);

  rb_define_method(cBitVector, "substitute", bv_substitute, 5);

  rb_define_method(cBitVector, "to_i", bv_to_int, 0);
  rb_define_method(cBitVector, "to_uint", bv_to_uint, 0);

  rb_define_method(cBitVector, "ones", bv_ones, 0);
  rb_define_method(cBitVector, "zeroes", bv_zeroes, 0);

  rb_define_method(cBitVector, "randomize", bv_randomize, -1);

  rb_define_method(cBitVector, "resize", bv_resize, 1);

#ifdef HAVE_RB_CVAR_DECLARE
  rb_cvar_declare(cBitVector, idCvarCarry, fixnum0);
#else
  rb_cvar_set(cBitVector, idCvarCarry, fixnum0, Qtrue);
#endif

  rb_define_singleton_method(cBitVector, "carry", bv_get_carry, 0);
  rb_define_method(cBitVector, "+", bv_add, 1);
  rb_define_method(cBitVector, "-", bv_sub, 1);
  rb_define_method(cBitVector, "-@", bv_negate, 0);
  rb_define_method(cBitVector, "abs", bv_abs, 0);
  rb_define_method(cBitVector, "sign", bv_sign, 0);
  rb_define_method(cBitVector, "*", bv_multiply, 1);
  rb_define_method(cBitVector, "/", bv_divide, 1);
}