1 package net.mograsim.logic.core.types;
3 import static java.lang.String.format;
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;
15 * Immutable class representing a {@link Bit}Vector
17 * @author Christian Femers
20 public final class BitVector implements StrictLogicType<BitVector>, Iterable<Bit>, RandomAccess
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);
28 private static final BitVector[] SINGLE_BIT_MAPPING = { SINGLE_U, SINGLE_X, SINGLE_0, SINGLE_1, SINGLE_Z };
30 private final Bit[] bits;
32 private BitVector(Bit single)
34 Objects.requireNonNull(single);
35 bits = new Bit[] { single };
38 private BitVector(Bit[] bits)
40 this.bits = Objects.requireNonNull(bits); // do this first to "catch" bits==null before the foreach loop
43 throw new NullPointerException();
46 public static BitVector of(Bit... bits)
49 return SINGLE_BIT_MAPPING[bits[0].ordinal()];
50 return new BitVector(bits.clone());
53 public static BitVector of(Bit bit, int length)
56 return SINGLE_BIT_MAPPING[bit.ordinal()];
57 return new BitVector(bit.makeArray(length));
60 public static BitVector from(long value, int bits)
62 return from(BigInteger.valueOf(value), bits);
65 public static BitVector from(BigInteger value, int bits)
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);
73 public BitVectorMutator mutator()
75 return BitVectorMutator.of(this);
79 * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
81 public Bit getMSBit(int bitIndex)
83 return bits[bitIndex];
87 * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
89 public Bit getLSBit(int bitIndex)
91 return bits[bits.length - bitIndex - 1];
94 public Bit[] getBits()
100 * Checks if all bits are {@link Bit#isBinary() binary}.
102 * @see Bit#isBinary()
104 public boolean isBinary()
106 for (int i = 0; i < bits.length; i++)
108 if (!bits[i].isBinary())
115 public BitVector join(BitVector t)
117 checkCompatibility(t);
118 if (bits.length == 1)
119 return SINGLE_BIT_MAPPING[bits[0].join(t.bits[0]).ordinal()];
120 return new BitVector(binOp(bits.clone(), t.bits, Bit::join));
124 public BitVector and(BitVector t)
126 checkCompatibility(t);
127 if (bits.length == 1)
128 return SINGLE_BIT_MAPPING[bits[0].and(t.bits[0]).ordinal()];
129 return new BitVector(binOp(bits.clone(), t.bits, Bit::and));
133 public BitVector or(BitVector t)
135 checkCompatibility(t);
136 if (bits.length == 1)
137 return SINGLE_BIT_MAPPING[bits[0].or(t.bits[0]).ordinal()];
138 return new BitVector(binOp(bits.clone(), t.bits, Bit::or));
142 public BitVector xor(BitVector t)
144 checkCompatibility(t);
145 if (bits.length == 1)
146 return SINGLE_BIT_MAPPING[bits[0].xor(t.bits[0]).ordinal()];
147 return new BitVector(binOp(bits.clone(), t.bits, Bit::xor));
151 public BitVector not()
153 if (bits.length == 1)
154 return SINGLE_BIT_MAPPING[bits[0].not().ordinal()];
155 return new BitVector(unOp(bits.clone(), Bit::not));
163 public BitVector concat(BitVector other)
165 Bit[] newBits = Arrays.copyOf(bits, length() + other.length());
166 System.arraycopy(other.bits, 0, newBits, length(), other.length());
167 return new BitVector(newBits);
170 public BitVector subVector(int start)
172 return new BitVector(Arrays.copyOfRange(bits, start, length()));
175 public BitVector subVector(int start, int end)
177 return new BitVector(Arrays.copyOfRange(bits, start, end));
180 private void checkCompatibility(BitVector bv)
182 if (length() != bv.length())
183 throw new IllegalArgumentException(format("BitVector length does not match: %d and %d", length(), bv.length()));
186 static Bit[] binOp(Bit[] dest, Bit[] second, BinaryOperator<Bit> op)
189 return second.clone();
190 for (int i = 0; i < dest.length; i++)
192 dest[i] = op.apply(dest[i], second[i]);
197 static Bit[] unOp(Bit[] dest, UnaryOperator<Bit> op)
201 for (int i = 0; i < dest.length; i++)
203 dest[i] = op.apply(dest[i]);
209 * Class for comfortable and efficient manipulation of {@link BitVector}s, similar to {@link StringBuilder}
211 * @author Christian Femers
213 public static final class BitVectorMutator implements LogicType<BitVectorMutator, BitVector>
217 private BitVectorMutator(Bit[] bits)
222 static BitVectorMutator of(BitVector bv)
224 return new BitVectorMutator(bv.getBits());
228 * Returns a new mutator of the specified length, <b>with all bits set to <code>null</code></b>. Use with care!
230 public static BitVectorMutator ofLength(int length)
232 return new BitVectorMutator(new Bit[length]);
236 * Returns an empty mutator which has no bits set and will simply copy the values from the first binary operation performed.
238 * An empty BitVectorMutator <b>must not</b> be converted to BitVector or used to manipulate single bits until at least one two
239 * operand logic operation is performed.
241 public static BitVectorMutator empty()
243 return new BitVectorMutator(null);
249 public boolean isEmpty()
255 * Produces the resulting, immutable {@link BitVector}<br>
257 * @throws IllegalStateException if the mutator is (still) empty
259 public BitVector toBitVector()
262 throw new IllegalStateException("cannot create a BitVector from an empty mutator");
263 return new BitVector(bits);
267 public BitVectorMutator join(BitVector t)
269 checkCompatibility(t);
270 bits = binOp(bits, t.bits, Bit::join);
275 public BitVectorMutator and(BitVector t)
277 checkCompatibility(t);
278 bits = binOp(bits, t.bits, Bit::and);
283 public BitVectorMutator or(BitVector t)
285 checkCompatibility(t);
286 bits = binOp(bits, t.bits, Bit::or);
291 public BitVectorMutator xor(BitVector t)
293 checkCompatibility(t);
294 bits = binOp(bits, t.bits, Bit::xor);
299 public BitVectorMutator not()
301 unOp(bits, Bit::not);
306 * Set the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
308 public void setMSBit(int bitIndex, Bit bit)
311 throw new IllegalStateException("cannot set a bit of an empty mutator");
312 bits[bitIndex] = bit;
316 * Set the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
318 public void setLSBit(int bitIndex, Bit bit)
321 throw new IllegalStateException("cannot set a bit of an empty mutator");
322 bits[bits.length - bitIndex - 1] = bit;
326 * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
328 public Bit getMSBit(int bitIndex)
331 throw new IllegalStateException("cannot get a bit of an empty mutator");
332 return bits[bitIndex];
336 * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
338 public Bit getLSBit(int bitIndex)
341 throw new IllegalStateException("cannot get a bit of an empty mutator");
342 return bits[bits.length - bitIndex - 1];
348 throw new IllegalStateException("cannot obtain a length of an empty mutator");
352 private void checkCompatibility(BitVector bv)
354 if (bits != null && bits.length != bv.length())
355 throw new IllegalArgumentException(format("BitVector length does not match: %d and %d", bits.length, bv.length()));
360 * @see Arrays#hashCode(Object[])
363 public int hashCode()
365 return Arrays.hashCode(bits);
369 * Does test for equality of values/content
371 * @see Object#equals(Object)
374 public boolean equals(Object obj)
378 if (!(obj instanceof BitVector))
380 BitVector other = (BitVector) obj;
381 return Arrays.equals(bits, other.bits);
385 * Does test for equality of values/content, shifting the other BitVector by <code>offset</code> to the right.<br>
386 * Therefore <code>offset + other.length() <= this.wdith()</code> needs to be true.
388 * @throws ArrayIndexOutOfBoundsException if <code>offset + other.length() > this.length()</code>
390 * @see Object#equals(Object)
392 public boolean equalsWithOffset(BitVector other, int offset)
396 return Arrays.equals(bits, offset, offset + other.length(), other.bits, 0, other.length());
400 * All {@link Bit}s symbols concatenated together (MSB first)
402 * @see #parse(String)
405 public String toString()
407 StringBuilder sb = new StringBuilder(bits.length);
410 return sb.toString();
414 * Returns the value of the BitVector as BigInteger.
416 * @throws NumberFormatException if the BitVector is not {@link #isBinary() binary}.
418 public BigInteger getUnsignedValue()
421 throw new NumberFormatException(this + " is not binary");
422 byte[] bytes = new byte[(bits.length / 8 + (bits.length % 8 == 0 ? 0 : 1)) + 1];
423 for (int i = bits.length - 1; i >= 0; i--)
425 if (Bit.ONE == bits[bits.length - i - 1])
429 bytes[bytes.length - (i / 8) - 1] |= 1 << (i % 8);
431 catch (IndexOutOfBoundsException e)
437 return new BigInteger(bytes);
441 * Parses a String containing solely {@link Bit} symbols (MSB first)
445 public static BitVector parse(String s)
447 Bit[] values = new Bit[s.length()];
448 for (int i = 0; i < s.length(); i++)
450 values[i] = Bit.parse(s, i);
452 return new BitVector(values);
456 * Changes a single Bit using the given operation. This can be used to set, clear or flip bits.
458 * @param msbIndex index of the MSB to be changed
459 * @param singleBitOperation the operation to perform on that Bit
460 * @return the resulting, new BitVektor
462 public BitVector withBitChanged(int msbIndex, UnaryOperator<Bit> singleBitOperation)
464 Bit[] newBits = bits.clone();
465 newBits[msbIndex] = singleBitOperation.apply(newBits[msbIndex]);
466 return new BitVector(newBits);
470 * Iterate over the {@link Bit}s of the BitVector <b>from MSB to LSB</b> (left to right).
473 public Iterator<Bit> iterator()
475 return new Iterator<>()
483 throw new NoSuchElementException();
484 return getMSBit(pos++);
488 public boolean hasNext()
490 return pos != length();