net.mograsim.logic.core/src/net/mograsim/logic/core/types/BitVector.java

   1 package net.mograsim.logic.core.types;
   2
   3 import static java.lang.String.format;
   4
   5 import java.math.BigInteger;
   6 import java.util.Arrays;
   7 import java.util.Iterator;
   8 import java.util.NoSuchElementException;
   9 import java.util.Objects;
  10 import java.util.RandomAccess;
  11 import java.util.function.BinaryOperator;
  12 import java.util.function.UnaryOperator;
  13
  14 /**
  15  * Immutable class representing a {@link Bit}Vector
  16  *
  17  * @author Christian Femers
  18  *
  19  */
  20 public final class BitVector implements StrictLogicType<BitVector>, Iterable<Bit>, RandomAccess
  21 {
  22         public static final BitVector SINGLE_U = new BitVector(Bit.U);
  23         public static final BitVector SINGLE_X = new BitVector(Bit.X);
  24         public static final BitVector SINGLE_0 = new BitVector(Bit.ZERO);
  25         public static final BitVector SINGLE_1 = new BitVector(Bit.ONE);
  26         public static final BitVector SINGLE_Z = new BitVector(Bit.Z);
  27
  28         private static final BitVector[] SINGLE_BIT_MAPPING = { SINGLE_U, SINGLE_X, SINGLE_0, SINGLE_1, SINGLE_Z };
  29
  30         private final Bit[] bits;
  31
  32         private BitVector(Bit single)
  33         {
  34                 Objects.requireNonNull(single);
  35                 bits = new Bit[] { single };
  36         }
  37
  38         private BitVector(Bit[] bits)
  39         {
  40                 this.bits = Objects.requireNonNull(bits); // do this first to "catch" bits==null before the foreach loop
  41                 for (Bit bit : bits)
  42                         if (bit == null)
  43                                 throw new NullPointerException();
  44         }
  45
  46         public static BitVector of(Bit... bits)
  47         {
  48                 if (bits.length == 1)
  49                         return SINGLE_BIT_MAPPING[bits[0].ordinal()];
  50                 return new BitVector(bits.clone());
  51         }
  52
  53         public static BitVector of(Bit bit, int length)
  54         {
  55                 if (length == 1)
  56                         return SINGLE_BIT_MAPPING[bit.ordinal()];
  57                 return new BitVector(bit.makeArray(length));
  58         }
  59
  60         public BigInteger getUnsignedValue()
  61         {
  62                 if (!isBinary())
  63                         throw new NumberFormatException("BitVector is non binary: " + toString());
  64                 byte[] bytes = new byte[(bits.length / 8) + 1];
  65                 for (int i = 0; i < bits.length; i++)
  66                 {
  67                         if (Bit.ONE == bits[i])
  68                         {
  69                                 bytes[i / 8] |= 1 << (i % 8);
  70                         }
  71                 }
  72                 return new BigInteger(bytes);
  73         }
  74
  75         public static BitVector from(BigInteger b, int length)
  76         {
  77                 int bitLength = b.bitLength();
  78                 int actualLength = Integer.min(bitLength, length);
  79                 Bit[] bits = new Bit[length];
  80                 for (int i = 0; i < actualLength; i++)
  81                         bits[i] = b.testBit(i) ? Bit.ONE : Bit.ZERO;
  82                 if (b.signum() < 0)
  83                         for (int i = actualLength; i < length; i++)
  84                                 bits[i] = Bit.ONE;
  85                 else
  86                         for (int i = actualLength; i < length; i++)
  87                                 bits[i] = Bit.ZERO;
  88                 return BitVector.of(bits);
  89         }
  90
  91         public static BitVector of(long value, int bits)
  92         {
  93                 return of(BigInteger.valueOf(value), bits);
  94         }
  95
  96         public static BitVector of(BigInteger value, int bits)
  97         {
  98                 Bit[] values = new Bit[bits];
  99                 for (int i = 0; i < bits; i++)
 100                 {
 101                         values[bits - i - 1] = Bit.of(value.testBit(i));
 102                 }
 103                 return new BitVector(values);
 104         }
 105
 106         public BitVectorMutator mutator()
 107         {
 108                 return BitVectorMutator.of(this);
 109         }
 110
 111         /**
 112          * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
 113          */
 114         public Bit getMSBit(int bitIndex)
 115         {
 116                 return bits[bitIndex];
 117         }
 118
 119         /**
 120          * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
 121          */
 122         public Bit getLSBit(int bitIndex)
 123         {
 124                 return bits[bits.length - bitIndex - 1];
 125         }
 126
 127         public Bit[] getBits()
 128         {
 129                 return bits.clone();
 130         }
 131
 132         public boolean isBinary()
 133         {
 134                 for (int i = 0; i < bits.length; i++)
 135                 {
 136                         if (!bits[i].isBinary())
 137                                 return false;
 138                 }
 139                 return true;
 140         }
 141
 142         @Override
 143         public BitVector join(BitVector t)
 144         {
 145                 checkCompatibility(t);
 146                 if (bits.length == 1)
 147                         return SINGLE_BIT_MAPPING[bits[0].join(t.bits[0]).ordinal()];
 148                 return new BitVector(binOp(bits.clone(), t.bits, Bit::join));
 149         }
 150
 151         @Override
 152         public BitVector and(BitVector t)
 153         {
 154                 checkCompatibility(t);
 155                 if (bits.length == 1)
 156                         return SINGLE_BIT_MAPPING[bits[0].and(t.bits[0]).ordinal()];
 157                 return new BitVector(binOp(bits.clone(), t.bits, Bit::and));
 158         }
 159
 160         @Override
 161         public BitVector or(BitVector t)
 162         {
 163                 checkCompatibility(t);
 164                 if (bits.length == 1)
 165                         return SINGLE_BIT_MAPPING[bits[0].or(t.bits[0]).ordinal()];
 166                 return new BitVector(binOp(bits.clone(), t.bits, Bit::or));
 167         }
 168
 169         @Override
 170         public BitVector xor(BitVector t)
 171         {
 172                 checkCompatibility(t);
 173                 if (bits.length == 1)
 174                         return SINGLE_BIT_MAPPING[bits[0].xor(t.bits[0]).ordinal()];
 175                 return new BitVector(binOp(bits.clone(), t.bits, Bit::xor));
 176         }
 177
 178         @Override
 179         public BitVector not()
 180         {
 181                 if (bits.length == 1)
 182                         return SINGLE_BIT_MAPPING[bits[0].not().ordinal()];
 183                 return new BitVector(unOp(bits.clone(), Bit::not));
 184         }
 185
 186         public int length()
 187         {
 188                 return bits.length;
 189         }
 190
 191         public BitVector concat(BitVector other)
 192         {
 193                 Bit[] newBits = Arrays.copyOf(bits, length() + other.length());
 194                 System.arraycopy(other.bits, 0, newBits, length(), other.length());
 195                 return new BitVector(newBits);
 196         }
 197
 198         public BitVector subVector(int start)
 199         {
 200                 return new BitVector(Arrays.copyOfRange(bits, start, length()));
 201         }
 202
 203         public BitVector subVector(int start, int end)
 204         {
 205                 return new BitVector(Arrays.copyOfRange(bits, start, end));
 206         }
 207
 208         private void checkCompatibility(BitVector bv)
 209         {
 210                 if (length() != bv.length())
 211                         throw new IllegalArgumentException(format("BitVector length does not match: %d and %d", length(), bv.length()));
 212         }
 213
 214         static Bit[] binOp(Bit[] dest, Bit[] second, BinaryOperator<Bit> op)
 215         {
 216                 if (dest == null)
 217                         return second.clone();
 218                 for (int i = 0; i < dest.length; i++)
 219                 {
 220                         dest[i] = op.apply(dest[i], second[i]);
 221                 }
 222                 return dest;
 223         }
 224
 225         static Bit[] unOp(Bit[] dest, UnaryOperator<Bit> op)
 226         {
 227                 if (dest == null)
 228                         return null;
 229                 for (int i = 0; i < dest.length; i++)
 230                 {
 231                         dest[i] = op.apply(dest[i]);
 232                 }
 233                 return dest;
 234         }
 235
 236         /**
 237          * Class for comfortable and efficient manipulation of {@link BitVector}s, similar to {@link StringBuilder}
 238          *
 239          * @author Christian Femers
 240          */
 241         public static final class BitVectorMutator implements LogicType<BitVectorMutator, BitVector>
 242         {
 243                 private Bit[] bits;
 244
 245                 private BitVectorMutator(Bit[] bits)
 246                 {
 247                         this.bits = bits;
 248                 }
 249
 250                 static BitVectorMutator of(BitVector bv)
 251                 {
 252                         return new BitVectorMutator(bv.getBits());
 253                 }
 254
 255                 /**
 256                  * Returns a new mutator of the specified length, <b>with all bits set to <code>null</code></b>. Use with care!
 257                  */
 258                 public static BitVectorMutator ofLength(int length)
 259                 {
 260                         return new BitVectorMutator(new Bit[length]);
 261                 }
 262
 263                 /**
 264                  * Returns an empty mutator which has no bits set and will simply copy the values from the first binary operation performed.
 265                  * <p>
 266                  * An empty BitVectorMutator <b>must not</b> be converted to BitVector or used to manipulate single bits until at least one two
 267                  * operand logic operation is performed.
 268                  */
 269                 public static BitVectorMutator empty()
 270                 {
 271                         return new BitVectorMutator(null);
 272                 }
 273
 274                 /**
 275                  * @see #empty()
 276                  */
 277                 public boolean isEmpty()
 278                 {
 279                         return bits == null;
 280                 }
 281
 282                 /**
 283                  * Produces the resulting, immutable {@link BitVector}<br>
 284                  *
 285                  * @throws IllegalStateException if the mutator is (still) empty
 286                  */
 287                 public BitVector toBitVector()
 288                 {
 289                         if (bits == null)
 290                                 throw new IllegalStateException("cannot create a BitVector from an empty mutator");
 291                         return new BitVector(bits);
 292                 }
 293
 294                 @Override
 295                 public BitVectorMutator join(BitVector t)
 296                 {
 297                         checkCompatibility(t);
 298                         bits = binOp(bits, t.bits, Bit::join);
 299                         return this;
 300                 }
 301
 302                 @Override
 303                 public BitVectorMutator and(BitVector t)
 304                 {
 305                         checkCompatibility(t);
 306                         bits = binOp(bits, t.bits, Bit::and);
 307                         return this;
 308                 }
 309
 310                 @Override
 311                 public BitVectorMutator or(BitVector t)
 312                 {
 313                         checkCompatibility(t);
 314                         bits = binOp(bits, t.bits, Bit::or);
 315                         return this;
 316                 }
 317
 318                 @Override
 319                 public BitVectorMutator xor(BitVector t)
 320                 {
 321                         checkCompatibility(t);
 322                         bits = binOp(bits, t.bits, Bit::xor);
 323                         return this;
 324                 }
 325
 326                 @Override
 327                 public BitVectorMutator not()
 328                 {
 329                         unOp(bits, Bit::not);
 330                         return this;
 331                 }
 332
 333                 /**
 334                  * Set the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
 335                  */
 336                 public void setMSBit(int bitIndex, Bit bit)
 337                 {
 338                         if (bits == null)
 339                                 throw new IllegalStateException("cannot set a bit of an empty mutator");
 340                         bits[bitIndex] = bit;
 341                 }
 342
 343                 /**
 344                  * Set the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
 345                  */
 346                 public void setLSBit(int bitIndex, Bit bit)
 347                 {
 348                         if (bits == null)
 349                                 throw new IllegalStateException("cannot set a bit of an empty mutator");
 350                         bits[bits.length - bitIndex - 1] = bit;
 351                 }
 352
 353                 /**
 354                  * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
 355                  */
 356                 public Bit getMSBit(int bitIndex)
 357                 {
 358                         if (bits == null)
 359                                 throw new IllegalStateException("cannot get a bit of an empty mutator");
 360                         return bits[bitIndex];
 361                 }
 362
 363                 /**
 364                  * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
 365                  */
 366                 public Bit getLSBit(int bitIndex)
 367                 {
 368                         if (bits == null)
 369                                 throw new IllegalStateException("cannot get a bit of an empty mutator");
 370                         return bits[bits.length - bitIndex - 1];
 371                 }
 372
 373                 public int length()
 374                 {
 375                         if (bits == null)
 376                                 throw new IllegalStateException("cannot obtain a length of an empty mutator");
 377                         return bits.length;
 378                 }
 379
 380                 private void checkCompatibility(BitVector bv)
 381                 {
 382                         if (bits != null && bits.length != bv.length())
 383                                 throw new IllegalArgumentException(format("BitVector length does not match: %d and %d", bits.length, bv.length()));
 384                 }
 385         }
 386
 387         /**
 388          * @see Arrays#hashCode(Object[])
 389          */
 390         @Override
 391         public int hashCode()
 392         {
 393                 return Arrays.hashCode(bits);
 394         }
 395
 396         /**
 397          * Does test for equality of values/content
 398          *
 399          * @see Object#equals(Object)
 400          */
 401         @Override
 402         public boolean equals(Object obj)
 403         {
 404                 if (this == obj)
 405                         return true;
 406                 if (!(obj instanceof BitVector))
 407                         return false;
 408                 BitVector other = (BitVector) obj;
 409                 return Arrays.equals(bits, other.bits);
 410         }
 411
 412         /**
 413          * Does test for equality of values/content, shifting the other BitVector by <code>offset</code> to the right.<br>
 414          * Therefore <code>offset + other.length() <= this.length()</code> needs to be true.
 415          *
 416          * @throws ArrayIndexOutOfBoundsException if <code>offset + other.length() > this.length()</code>
 417          *
 418          * @see Object#equals(Object)
 419          */
 420         public boolean equalsWithOffset(BitVector other, int offset)
 421         {
 422                 if (other == null)
 423                         return false;
 424                 return Arrays.equals(bits, offset, offset + other.length(), other.bits, 0, other.length());
 425         }
 426
 427         /**
 428          * All {@link Bit}s symbols concatenated together (MSB first)
 429          *
 430          * @see #parse(String)
 431          */
 432         @Override
 433         public String toString()
 434         {
 435                 StringBuilder sb = new StringBuilder(bits.length);
 436                 for (Bit bit : bits)
 437                         sb.append(bit);
 438                 return sb.toString();
 439         }
 440
 441         /**
 442          * Returns the value of the BitVector as BigInteger either unsigned or as two-complement.
 443          *
 444          * @param signed if true and the BitVector represents a negative two-complement integer, an equivalent BigInteger is returned
 445          * @return the value of this BitVector as BigInteger
 446          *
 447          */
 448         public BigInteger toBigInteger(boolean signed)
 449         {
 450                 if (!isBinary())
 451                         throw new NumberFormatException(this + " is not binary");
 452                 BigInteger val = new BigInteger(toString(), 2);
 453                 if (signed && bits[0] == Bit.ONE)
 454                         val = val.not().setBit(val.bitLength()).add(BigInteger.ONE);
 455                 return val;
 456         }
 457
 458         /**
 459          * Parses a String containing solely {@link Bit} symbols (MSB first)
 460          *
 461          * @see #toString()
 462          */
 463         public static BitVector parse(String s)
 464         {
 465                 Bit[] values = new Bit[s.length()];
 466                 for (int i = 0; i < s.length(); i++)
 467                 {
 468                         values[i] = Bit.parse(s, i);
 469                 }
 470                 return new BitVector(values);
 471         }
 472
 473         /**
 474          * Iterate over the {@link Bit}s of the BitVector <b>from MSB to LSB</b> (left to right).
 475          */
 476         @Override
 477         public Iterator<Bit> iterator()
 478         {
 479                 return new Iterator<>()
 480                 {
 481                         private int pos = 0;
 482
 483                         @Override
 484                         public Bit next()
 485                         {
 486                                 if (!hasNext())
 487                                         throw new NoSuchElementException();
 488                                 return getMSBit(pos++);
 489                         }
 490
 491                         @Override
 492                         public boolean hasNext()
 493                         {
 494                                 return pos != length();
 495                         }
 496                 };
 497         }
 498 }