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