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