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