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