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