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 BigInteger getUnsignedValue()
63 throw new NumberFormatException("BitVector is non binary: " + toString());
64 byte[] bytes = new byte[(bits.length / 8) + 1];
65 for (int i = 0; i < bits.length; i++)
67 if (Bit.ONE == bits[i])
69 bytes[i / 8] |= 1 << (i % 8);
72 return new BigInteger(bytes);
75 public static BitVector from(BigInteger b, int length)
77 int bitLength = b.bitLength();
78 int actualLength = Integer.min(bitLength, length);
79 Bit[] bits = new Bit[length];
80 for (int i = 0; i < actualLength; i++)
81 bits[i] = b.testBit(i) ? Bit.ONE : Bit.ZERO;
83 for (int i = actualLength; i < length; i++)
86 for (int i = actualLength; i < length; i++)
88 return BitVector.of(bits);
91 public static BitVector of(long value, int bits)
93 return of(BigInteger.valueOf(value), bits);
96 public static BitVector of(BigInteger value, int bits)
98 Bit[] values = new Bit[bits];
99 for (int i = 0; i < bits; i++)
101 values[bits - i - 1] = Bit.of(value.testBit(i));
103 return new BitVector(values);
106 public BitVectorMutator mutator()
108 return BitVectorMutator.of(this);
112 * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
114 public Bit getMSBit(int bitIndex)
116 return bits[bitIndex];
120 * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
122 public Bit getLSBit(int bitIndex)
124 return bits[bits.length - bitIndex - 1];
127 public Bit[] getBits()
132 public boolean isBinary()
134 for (int i = 0; i < bits.length; i++)
136 if (!bits[i].isBinary())
143 public BitVector join(BitVector t)
145 checkCompatibility(t);
146 if (bits.length == 1)
147 return SINGLE_BIT_MAPPING[bits[0].join(t.bits[0]).ordinal()];
148 return new BitVector(binOp(bits.clone(), t.bits, Bit::join));
152 public BitVector and(BitVector t)
154 checkCompatibility(t);
155 if (bits.length == 1)
156 return SINGLE_BIT_MAPPING[bits[0].and(t.bits[0]).ordinal()];
157 return new BitVector(binOp(bits.clone(), t.bits, Bit::and));
161 public BitVector or(BitVector t)
163 checkCompatibility(t);
164 if (bits.length == 1)
165 return SINGLE_BIT_MAPPING[bits[0].or(t.bits[0]).ordinal()];
166 return new BitVector(binOp(bits.clone(), t.bits, Bit::or));
170 public BitVector xor(BitVector t)
172 checkCompatibility(t);
173 if (bits.length == 1)
174 return SINGLE_BIT_MAPPING[bits[0].xor(t.bits[0]).ordinal()];
175 return new BitVector(binOp(bits.clone(), t.bits, Bit::xor));
179 public BitVector not()
181 if (bits.length == 1)
182 return SINGLE_BIT_MAPPING[bits[0].not().ordinal()];
183 return new BitVector(unOp(bits.clone(), Bit::not));
191 public BitVector concat(BitVector other)
193 Bit[] newBits = Arrays.copyOf(bits, length() + other.length());
194 System.arraycopy(other.bits, 0, newBits, length(), other.length());
195 return new BitVector(newBits);
198 public BitVector subVector(int start)
200 return new BitVector(Arrays.copyOfRange(bits, start, length()));
203 public BitVector subVector(int start, int end)
205 return new BitVector(Arrays.copyOfRange(bits, start, end));
208 private void checkCompatibility(BitVector bv)
210 if (length() != bv.length())
211 throw new IllegalArgumentException(format("BitVector length does not match: %d and %d", length(), bv.length()));
214 static Bit[] binOp(Bit[] dest, Bit[] second, BinaryOperator<Bit> op)
217 return second.clone();
218 for (int i = 0; i < dest.length; i++)
220 dest[i] = op.apply(dest[i], second[i]);
225 static Bit[] unOp(Bit[] dest, UnaryOperator<Bit> op)
229 for (int i = 0; i < dest.length; i++)
231 dest[i] = op.apply(dest[i]);
237 * Class for comfortable and efficient manipulation of {@link BitVector}s, similar to {@link StringBuilder}
239 * @author Christian Femers
241 public static final class BitVectorMutator implements LogicType<BitVectorMutator, BitVector>
245 private BitVectorMutator(Bit[] bits)
250 static BitVectorMutator of(BitVector bv)
252 return new BitVectorMutator(bv.getBits());
256 * Returns a new mutator of the specified length, <b>with all bits set to <code>null</code></b>. Use with care!
258 public static BitVectorMutator ofLength(int length)
260 return new BitVectorMutator(new Bit[length]);
264 * Returns an empty mutator which has no bits set and will simply copy the values from the first binary operation performed.
266 * An empty BitVectorMutator <b>must not</b> be converted to BitVector or used to manipulate single bits until at least one two
267 * operand logic operation is performed.
269 public static BitVectorMutator empty()
271 return new BitVectorMutator(null);
277 public boolean isEmpty()
283 * Produces the resulting, immutable {@link BitVector}<br>
285 * @throws IllegalStateException if the mutator is (still) empty
287 public BitVector toBitVector()
290 throw new IllegalStateException("cannot create a BitVector from an empty mutator");
291 return new BitVector(bits);
295 public BitVectorMutator join(BitVector t)
297 checkCompatibility(t);
298 bits = binOp(bits, t.bits, Bit::join);
303 public BitVectorMutator and(BitVector t)
305 checkCompatibility(t);
306 bits = binOp(bits, t.bits, Bit::and);
311 public BitVectorMutator or(BitVector t)
313 checkCompatibility(t);
314 bits = binOp(bits, t.bits, Bit::or);
319 public BitVectorMutator xor(BitVector t)
321 checkCompatibility(t);
322 bits = binOp(bits, t.bits, Bit::xor);
327 public BitVectorMutator not()
329 unOp(bits, Bit::not);
334 * Set the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
336 public void setMSBit(int bitIndex, Bit bit)
339 throw new IllegalStateException("cannot set a bit of an empty mutator");
340 bits[bitIndex] = bit;
344 * Set the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
346 public void setLSBit(int bitIndex, Bit bit)
349 throw new IllegalStateException("cannot set a bit of an empty mutator");
350 bits[bits.length - bitIndex - 1] = bit;
354 * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
356 public Bit getMSBit(int bitIndex)
359 throw new IllegalStateException("cannot get a bit of an empty mutator");
360 return bits[bitIndex];
364 * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
366 public Bit getLSBit(int bitIndex)
369 throw new IllegalStateException("cannot get a bit of an empty mutator");
370 return bits[bits.length - bitIndex - 1];
376 throw new IllegalStateException("cannot obtain a length of an empty mutator");
380 private void checkCompatibility(BitVector bv)
382 if (bits != null && bits.length != bv.length())
383 throw new IllegalArgumentException(format("BitVector length does not match: %d and %d", bits.length, bv.length()));
388 * @see Arrays#hashCode(Object[])
391 public int hashCode()
393 return Arrays.hashCode(bits);
397 * Does test for equality of values/content
399 * @see Object#equals(Object)
402 public boolean equals(Object obj)
406 if (!(obj instanceof BitVector))
408 BitVector other = (BitVector) obj;
409 return Arrays.equals(bits, other.bits);
413 * Does test for equality of values/content, shifting the other BitVector by <code>offset</code> to the right.<br>
414 * Therefore <code>offset + other.length() <= this.length()</code> needs to be true.
416 * @throws ArrayIndexOutOfBoundsException if <code>offset + other.length() > this.length()</code>
418 * @see Object#equals(Object)
420 public boolean equalsWithOffset(BitVector other, int offset)
424 return Arrays.equals(bits, offset, offset + other.length(), other.bits, 0, other.length());
428 * All {@link Bit}s symbols concatenated together (MSB first)
430 * @see #parse(String)
433 public String toString()
435 StringBuilder sb = new StringBuilder(bits.length);
438 return sb.toString();
442 * Returns the value of the BitVector as BigInteger either unsigned or as two-complement.
444 * @param signed if true and the BitVector represents a negative two-complement integer, an equivalent BigInteger is returned
445 * @return the value of this BitVector as BigInteger
448 public BigInteger toBigInteger(boolean signed)
451 throw new NumberFormatException(this + " is not binary");
452 BigInteger val = new BigInteger(toString(), 2);
453 if (signed && bits[0] == Bit.ONE)
454 val = val.not().setBit(val.bitLength()).add(BigInteger.ONE);
459 * Parses a String containing solely {@link Bit} symbols (MSB first)
463 public static BitVector parse(String s)
465 Bit[] values = new Bit[s.length()];
466 for (int i = 0; i < s.length(); i++)
468 values[i] = Bit.parse(s, i);
470 return new BitVector(values);
474 * Iterate over the {@link Bit}s of the BitVector <b>from MSB to LSB</b> (left to right).
477 public Iterator<Bit> iterator()
479 return new Iterator<>()
487 throw new NoSuchElementException();
488 return getMSBit(pos++);
492 public boolean hasNext()
494 return pos != length();