Kawa/gnu/math/BitOps.java

// Copyright (c) 1997  Per M.A. Bothner.
// This is free software;  for terms and warranty disclaimer see ./COPYING.

package gnu.math;

/** Implements logical (bit-wise) operations on infinite-precision integers.
 * There are no BitOps object - all the functions here are static.
 * The semantics used are the same as for Common Lisp.
 * @author Per Bothner
 */

public class BitOps
{
  private BitOps () { }

  /** Return the value of a specified bit in an IntNum. */
  public static boolean bitValue (IntNum x, int bitno)
  {
    int i = x.ival;
    if (x.words == null)
      {
	return bitno >= 32 ? i < 0 : ((i >> bitno) & 1) != 0;
      }
    else
      {
	int wordno = bitno >> 5;
	return wordno >= i ? x.words[i-1] < 0
	  : ((x.words[wordno] >> bitno) & 1) != 0;
      }
  }
 
  /** Make a fresh buffer conatining the value of x.
   * Make sure bitno ius within the buffer.
   */
  static int [] dataBufferFor (IntNum x, int bitno)
  {
    int i = x.ival;
    int[] data;
    int nwords = (bitno+1) >> 5;
    if (x.words == null)
      {
        if (nwords == 0)
          nwords = 1;
        data = new int[nwords];
        data[0] = i;
        if (i < 0) // Sign-extend if needed.
          {
            for (int j = 1; j < nwords;  j++)
              data[j] = -1;
          }
      }
    else
      {
        nwords = (bitno+1) >> 5;
        data = new int[nwords > i ? nwords : i];
        for (int j = i;  --j >= 0; )
          data[j] = x.words[j];
        if (data[i-1] < 0) // Sign-extend if needed.
          {
            for (int j = i; j < nwords;  j++)
              data[j] = -1;
          }
      }
    return data;
  }

  /** Set the value of a specified bit in an IntNum. */
  public static IntNum setBitValue (IntNum x, int bitno, int newValue)
  {
    newValue &= 1;
    int i = x.ival;
    int[] data;
    int nwords;
    if (x.words == null)
      {
        int oldValue = (i >> (bitno < 31 ? bitno : 31)) & 1;
        if (oldValue == newValue)
            return x;
        if (bitno < 63)
          return IntNum.make((long) i ^ (long) (1 << bitno));
      }
    else
      {
	int wordno = bitno >> 5;
        int oldValue;
        if (wordno >= i)
          oldValue = x.words[i-1] < 0 ? 1  : 0;
        else
          oldValue = (x.words[wordno] >> bitno) & 1;
        if (oldValue == newValue)
          return x;
      }
    data = dataBufferFor(x, bitno);
    data[bitno >> 5] ^= 1 << (bitno & 31);
    return IntNum.make(data, data.length);
  }
 
  /** Return true iff an IntNum and an int have any true bits in common. */
  public static boolean test (IntNum x, int y)
  {
    if (x.words == null)
      return (x.ival & y) != 0;
    return (y < 0) || (x.words[0] & y) != 0;
  }

  /** Return true iff two IntNums have any true bits in common. */
  public static boolean test (IntNum x, IntNum y)
  {
    if (y.words == null)
      return test (x, y.ival);
    else if (x.words == null)
      return test (y, x.ival);
    if (x.ival < y.ival)
      {
        IntNum temp = x;  x = y;  y = temp;
      }
    for (int i = 0;  i < y.ival;  i++)
      {
	if ((x.words[i] & y.words[i]) != 0)
	  return true;
      }
    return y.isNegative ();
  }

  /** Return the logical (bit-wise) "and" of an IntNum and an int. */
  public static IntNum and (IntNum x, int y)
  {
    if (x.words == null)
      return IntNum.make (x.ival & y);
    if (y >= 0)
      return IntNum.make (x.words[0] & y);
    int len = x.ival;
    int[] words = new int[len];
    words[0] = x.words[0] & y;
    while (--len > 0)
      words[len] = x.words[len];
    return IntNum.make (words, x.ival);
  }

  /** Return the logical (bit-wise) "and" of two IntNums. */
  public static IntNum and (IntNum x, IntNum y)
  {
    if (y.words == null)
      return and (x, y.ival);
    else if (x.words == null)
      return and (y, x.ival);
    if (x.ival < y.ival)
      {
        IntNum temp = x;  x = y;  y = temp;
      }
    int i;
    int len = y.isNegative () ? x.ival : y.ival;
    int[] words = new int[len];
    for (i = 0;  i < y.ival;  i++)
      words[i] = x.words[i] & y.words[i];
    for ( ; i < len;  i++)
      words[i] = x.words[i];
    return IntNum.make (words, len);
  }

  /** Return the logical (bit-wise) "(inclusive) or" of two IntNums. */
  public static IntNum ior (IntNum x, IntNum y)
  {
    return bitOp (7, x, y);
  }

  /** Return the logical (bit-wise) "exclusive or" of two IntNums. */
  public static IntNum xor (IntNum x, IntNum y)
  {
    return bitOp (6, x, y);
  }

  /** Return the logical (bit-wise) negation of an IntNum. */
  public static IntNum not (IntNum x)
  {
    return bitOp (12, x, IntNum.zero ());
  }

  /** Return the boolean opcode (for bitOp) for swapped operands.
   * I.e. bitOp (swappedOp(op), x, y) == bitOp (op, y, x).
   */
  public static int swappedOp (int op)
  {
    return
    "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
    .charAt (op);
  }

  /** Do one the the 16 possible bit-wise operations of two IntNums. */
  public static IntNum bitOp (int op, IntNum x, IntNum y)
  {
    switch (op)
      {
        case 0:  return IntNum.zero();
        case 1:  return and (x, y);
        case 3:  return x;
        case 5:  return y;
        case 15: return IntNum.minusOne();
      }
    IntNum result = new IntNum ();
    setBitOp (result, op, x, y);
    return result.canonicalize ();
  }

  /** Do one the the 16 possible bit-wise operations of two IntNums. */
  public static void setBitOp (IntNum result, int op, IntNum x, IntNum y)
  {
    if (y.words == null) ;
    else if (x.words == null || x.ival < y.ival)
      {
	IntNum temp = x;  x = y;  y = temp;
	op = swappedOp (op);
      }
    int xi;
    int yi;
    int xlen, ylen;
    if (y.words == null)
      {
	yi = y.ival;
	ylen = 1;
      }
    else
      {
	yi = y.words[0];
	ylen = y.ival;
      }
    if (x.words == null)
      {
	xi = x.ival;
	xlen = 1;
      }
    else
      {
	xi = x.words[0];
	xlen = x.ival;
      }
    if (xlen > 1)
      result.realloc (xlen);
    int[] w = result.words;
    int i = 0;
    // Code for how to handle the remainder of x.
    // 0:  Truncate to length of y.
    // 1:  Copy rest of x.
    // 2:  Invert rest of x.
    int finish = 0;
    int ni;
    switch (op)
      {
      case 0:  // clr
	ni = 0;
	break;
      case 1: // and
	for (;;)
	  {
	    ni = xi & yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 1;
	break;
      case 2: // andc2
	for (;;)
	  {
	    ni = xi & ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 1;
	break;
      case 3:  // copy x
	ni = xi;
	finish = 1;  // Copy rest
	break;
      case 4: // andc1
	for (;;)
	  {
	    ni = ~xi & yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 2;
	break;
      case 5: // copy y
	for (;;)
	  {
	    ni = yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	break;
      case 6:  // xor
	for (;;)
	  {
	    ni = xi ^ yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	finish = yi < 0 ? 2 : 1;
	break;
      case 7:  // ior
	for (;;)
	  {
	    ni = xi | yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 1;
	break;
      case 8:  // nor
	for (;;)
	  {
	    ni = ~(xi | yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0)  finish = 2;
	break;
      case 9:  // eqv [exclusive nor]
	for (;;)
	  {
	    ni = ~(xi ^ yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	finish = yi >= 0 ? 2 : 1;
	break;
      case 10:  // c2
	for (;;)
	  {
	    ni = ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	break;
      case 11:  // orc2
	for (;;)
	  {
	    ni = xi | ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0)  finish = 1;
	break;
      case 12:  // c1
	ni = ~xi;
	finish = 2;
	break;
      case 13:  // orc1
	for (;;)
	  {
	    ni = ~xi | yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 2;
	break;
      case 14:  // nand
	for (;;)
	  {
	    ni = ~(xi & yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 2;
	break;
      default:
      case 15:  // set
	ni = -1;
	break;
      }
    // Here i==ylen-1; w[0]..w[i-1] have the correct result;
    // and ni contains the correct result for w[i+1].
    if (i+1 == xlen)
      finish = 0;
    switch (finish)
      {
      case 0:
	if (i == 0 && w == null)
	  {
	    result.ival = ni;
	    return;
	  }
	w[i++] = ni;
	break;
      case 1:  w[i] = ni;  while (++i < xlen)  w[i] = x.words[i];  break;
      case 2:  w[i] = ni;  while (++i < xlen)  w[i] = ~x.words[i];  break;
      }
    result.ival = i;
  }

    /** Create a mask with bits true form bits form startBit to endBit. */
    public static IntNum makeMask(int startBit, int endBit) {
        int width = endBit-startBit;
        if (width <= 0)
            return IntNum.zero();
        if (endBit < 64)
            return IntNum.make(~(-1L << width) << startBit);
        int len = (endBit >> 5) + 1;
        int[] buf = new int[len];
        int startWord = startBit >> 5;
        int i = width >> 5;
        buf[i] = ~(-1 << (width & 31));
        while (--i >= 0)
            buf[i] = -1;
        // Now buf contains '1' in the width low-order bits.
        MPN.lshift(buf, startWord, buf, len-startWord, startBit&31);
        for (i = startWord; --i >= 0; )
            buf[i] = 0;
        return IntNum.make(buf, len);
    }

  /** Extract a bit-field as an unsigned integer. */
  public static IntNum extract (IntNum x, int startBit, int endBit)
  {
    //System.err.print("extract([");  if (x.words!=null) MPN.dprint(x.words);
    //System.err.println (","+x.ival+"], start:"+startBit+", end:"+endBit);
    if (endBit < 32)
      {
	int word0 = x.words == null ? x.ival : x.words[0];
	return IntNum.make ((word0 & ~((-1) << endBit)) >> startBit);
      }
    int x_len;
    if (x.words == null)
      {
	if (x.ival >= 0)
	  return IntNum.make (startBit >= 31 ? 0 : (x.ival >> startBit));
	x_len = 1;
      }
    else
      x_len = x.ival;
    boolean neg = x.isNegative ();
    if (endBit > 32 * x_len)
      {
	endBit = 32 * x_len;
	if (!neg && startBit == 0)
	  return x;
      }
    else
      x_len = (endBit + 31) >> 5;
    int length = endBit - startBit;
    if (length < 64)
      {
	long l;
	if (x.words == null)
	  l = x.ival >> (startBit >= 32 ? 31 : startBit);
	else
	  l = MPN.rshift_long (x.words, x_len, startBit);
	return IntNum.make (l & ~((-1L) << length));
      }
    int startWord = startBit >> 5;
    // Allocate a work buffer, which has to be large enough for the result
    // AND large enough for all words we use from x (including possible
    // partial words at both ends).
    int buf_len = (endBit >> 5) + 1 - startWord;
    int[] buf = new int[buf_len];
    if (x.words == null)  // x < 0.
      buf[0] = startBit >= 32 ? -1 : (x.ival >> startBit);
    else
      {
	x_len -= startWord;
	startBit &= 31;
	MPN.rshift0 (buf, x.words, startWord, x_len, startBit);
      }
    x_len = length >> 5;
    buf[x_len] &= ~((-1) << length);
    return IntNum.make (buf, x_len + 1);
  }

  public static int lowestBitSet (int i)
  {
    if (i == 0)
      return -1;
    int index = 0;
    while ((i & 0xFF) == 0)
      {
        i >>>= 8;
        index += 8;
      }
    while ((i & 3) == 0)
      {
        i >>>= 2;
        index += 2;
      }
   if ((i & 1) == 0)
     index++;
   return index;
  }

  public static int lowestBitSet (IntNum x)
  {
    int[] x_words = x.words;
    if (x_words == null)
      {
	return lowestBitSet(x.ival);
      }
    else
      {
	int x_len = x.ival;
        for (int i = 0; i < x_len; )
          {
            int b = lowestBitSet(x_words[i]);
            if (b >= 0)
              return 32 * i + b;
          }
        return -1;
      }
 }

  // bit4count[I] is number of '1' bits in I.
  static final byte[] bit4_count = { 0, 1, 1, 2,  1, 2, 2, 3,
				     1, 2, 2, 3,  2, 3, 3, 4};

  public static int bitCount (int i)
  {
    int count = 0;
    while (i != 0)
      {
	count += bit4_count[i & 15];
	i >>>= 4;
      }
    return count;
  }

  public static int bitCount (int[] x, int len)
  {
    int count = 0;
    while (--len >= 0)
      count += bitCount (x[len]);
    return count;
  }

  /** Count one bits in an IntNum.
   * If argument is negative, count zero bits instead. */
  public static int bitCount (IntNum x)
  {
    int i, x_len;
    int[] x_words = x.words;
    if (x_words == null)
      {
	x_len = 1;
	i = bitCount (x.ival);
      }
    else
      {
	x_len = x.ival;
	i = bitCount (x_words, x_len);
      }
    return x.isNegative () ? x_len * 32 - i : i;
  }

  public static IntNum reverseBits (IntNum x, int start, int end)
  {
    int ival = x.ival;
    int[] xwords = x.words;
    if (xwords == null)
      {
        if (end < 63)
          {
            long w = ival;
            int i = start;
            int j = end - 1;
            while (i < j)
              {
                long biti = (w >> i) & 1;
                long bitj = (w >> j) & 1;
                w &= ~((1L << i) | (1L << j));
                w = w | (biti << j) | (bitj << i);
                i++;
                j--;
              }
            return IntNum.make(w);
          }
      }
    int[] data = dataBufferFor(x, end-1);
    int i = start;
    int j = end - 1;
    while (i < j)
      {
        int ii = i >> 5;
        int jj = j >> 5;
        int wi = data[ii];
        int biti = (wi >> i) & 1;
        if (ii == jj)
          {
            int bitj = (wi >> j) & 1;
            wi &= ~((1L << i) | (1L << j));
            wi = wi | (biti << j) | (bitj << i);
          }
        else
          {
            int wj = data[jj];
            int bitj = (wj >> (j & 31)) & 1;
            wi &= ~(1 << (i & 31));
            wj &= ~(1 << (j & 31));
            wi |= bitj << (i & 31);
            wj |= biti << (j & 31);
            data[jj] = wj;
          }
        data[ii] = wi;
        i++;
        j--;
      }
    return IntNum.make(data, data.length);
  }

    public static int shift(int x, int count) {
        if (count >= 32)
            return 0;
        if (count >= 0)
            return x << count;
        count = -count;
        if (count >= 32)
            return x < 0 ? -1 : 0;
        return x >> count;
    }

    public static int shiftUnsigned(int x, int count) {
        if (count >= 32)
            return 0;
        if (count >= 0)
            return x << count;
        count = -count;
        return count >= 32 ? 0 : x >>> count;
    }

    public static long shift(long x, int count) {
        if (count >= 64)
            return 0;
        if (count >= 0)
            return x << count;
        count = -count;
        if (count >= 64)
            return x < 0 ? -1 : 0;
        return x >> count;
    }

    public static long shiftUnsigned(long x, int count) {
        if (count >= 64)
            return 0;
        if (count >= 0)
            return x << count;
        count = -count;
        return count >= 64 ? 0 : x >>> count;
    }
}