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