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 width)
56 return SINGLE_BIT_MAPPING[bit.ordinal()];
57 return new BitVector(bit.makeArray(width));
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++)
70 values[bits - i - 1] = Bit.of(value.testBit(i));
72 return new BitVector(values);
75 public BitVectorMutator mutator()
77 return BitVectorMutator.of(this);
81 * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
83 public Bit getMSBit(int bitIndex)
85 return bits[bitIndex];
89 * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
91 public Bit getLSBit(int bitIndex)
93 return bits[bits.length - bitIndex - 1];
96 public Bit[] getBits()
102 * Checks if all bits are {@link Bit#isBinary() binary}.
104 * @see Bit#isBinary()
106 public boolean isBinary()
108 for (int i = 0; i < bits.length; i++)
110 if (!bits[i].isBinary())
117 public BitVector join(BitVector t)
119 checkCompatibility(t);
120 if (bits.length == 1)
121 return SINGLE_BIT_MAPPING[bits[0].join(t.bits[0]).ordinal()];
122 return new BitVector(binOp(bits.clone(), t.bits, Bit::join));
126 public BitVector and(BitVector t)
128 checkCompatibility(t);
129 if (bits.length == 1)
130 return SINGLE_BIT_MAPPING[bits[0].and(t.bits[0]).ordinal()];
131 return new BitVector(binOp(bits.clone(), t.bits, Bit::and));
135 public BitVector or(BitVector t)
137 checkCompatibility(t);
138 if (bits.length == 1)
139 return SINGLE_BIT_MAPPING[bits[0].or(t.bits[0]).ordinal()];
140 return new BitVector(binOp(bits.clone(), t.bits, Bit::or));
144 public BitVector xor(BitVector t)
146 checkCompatibility(t);
147 if (bits.length == 1)
148 return SINGLE_BIT_MAPPING[bits[0].xor(t.bits[0]).ordinal()];
149 return new BitVector(binOp(bits.clone(), t.bits, Bit::xor));
153 public BitVector not()
155 if (bits.length == 1)
156 return SINGLE_BIT_MAPPING[bits[0].not().ordinal()];
157 return new BitVector(unOp(bits.clone(), Bit::not));
165 public BitVector concat(BitVector other)
167 Bit[] newBits = Arrays.copyOf(bits, width() + other.width());
168 System.arraycopy(other.bits, 0, newBits, width(), other.width());
169 return new BitVector(newBits);
172 public BitVector subVector(int start)
174 return new BitVector(Arrays.copyOfRange(bits, start, width()));
177 public BitVector subVector(int start, int end)
179 return new BitVector(Arrays.copyOfRange(bits, start, end));
182 private void checkCompatibility(BitVector bv)
184 if (width() != bv.width())
185 throw new IllegalArgumentException(format("BitVector width does not match: %d and %d", width(), bv.width()));
188 static Bit[] binOp(Bit[] dest, Bit[] second, BinaryOperator<Bit> op)
191 return second.clone();
192 for (int i = 0; i < dest.length; i++)
194 dest[i] = op.apply(dest[i], second[i]);
199 static Bit[] unOp(Bit[] dest, UnaryOperator<Bit> op)
203 for (int i = 0; i < dest.length; i++)
205 dest[i] = op.apply(dest[i]);
211 * Class for comfortable and efficient manipulation of {@link BitVector}s, similar to {@link StringBuilder}
213 * @author Christian Femers
215 public static final class BitVectorMutator implements LogicType<BitVectorMutator, BitVector>
219 private BitVectorMutator(Bit[] bits)
224 static BitVectorMutator of(BitVector bv)
226 return new BitVectorMutator(bv.getBits());
230 * Returns a new mutator of the specified width, <b>with all bits set to <code>null</code></b>. Use with care!
232 public static BitVectorMutator ofWidth(int width)
234 return new BitVectorMutator(new Bit[width]);
238 * Returns an empty mutator which has no bits set and will simply copy the values from the first binary operation performed.
240 * An empty BitVectorMutator <b>must not</b> be converted to BitVector or used to manipulate single bits until at least one two
241 * operand logic operation is performed.
243 public static BitVectorMutator empty()
245 return new BitVectorMutator(null);
251 public boolean isEmpty()
257 * Produces the resulting, immutable {@link BitVector}<br>
259 * @throws IllegalStateException if the mutator is (still) empty
261 public BitVector toBitVector()
264 throw new IllegalStateException("cannot create a BitVector from an empty mutator");
265 return new BitVector(bits);
269 public BitVectorMutator join(BitVector t)
271 checkCompatibility(t);
272 bits = binOp(bits, t.bits, Bit::join);
277 public BitVectorMutator and(BitVector t)
279 checkCompatibility(t);
280 bits = binOp(bits, t.bits, Bit::and);
285 public BitVectorMutator or(BitVector t)
287 checkCompatibility(t);
288 bits = binOp(bits, t.bits, Bit::or);
293 public BitVectorMutator xor(BitVector t)
295 checkCompatibility(t);
296 bits = binOp(bits, t.bits, Bit::xor);
301 public BitVectorMutator not()
303 unOp(bits, Bit::not);
308 * Set the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
310 public void setMSBit(int bitIndex, Bit bit)
313 throw new IllegalStateException("cannot set a bit of an empty mutator");
314 bits[bitIndex] = bit;
318 * Set the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
320 public void setLSBit(int bitIndex, Bit bit)
323 throw new IllegalStateException("cannot set a bit of an empty mutator");
324 bits[bits.length - bitIndex - 1] = bit;
328 * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
330 public Bit getMSBit(int bitIndex)
333 throw new IllegalStateException("cannot get a bit of an empty mutator");
334 return bits[bitIndex];
338 * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
340 public Bit getLSBit(int bitIndex)
343 throw new IllegalStateException("cannot get a bit of an empty mutator");
344 return bits[bits.length - bitIndex - 1];
350 throw new IllegalStateException("cannot obtain a width of an empty mutator");
354 private void checkCompatibility(BitVector bv)
356 if (bits != null && bits.length != bv.width())
357 throw new IllegalArgumentException(format("BitVector width does not match: %d and %d", bits.length, bv.width()));
362 * @see Arrays#hashCode(Object[])
365 public int hashCode()
367 return Arrays.hashCode(bits);
371 * Does test for equality of values/content
373 * @see Object#equals(Object)
376 public boolean equals(Object obj)
380 if (!(obj instanceof BitVector))
382 BitVector other = (BitVector) obj;
383 return Arrays.equals(bits, other.bits);
387 * Does test for equality of values/content, shifting the other BitVector by <code>offset</code> to the right.<br>
388 * Therefore <code>offset + other.width() <= this.wdith()</code> needs to be true.
390 * @throws ArrayIndexOutOfBoundsException if <code>offset + other.width() > this.width()</code>
392 * @see Object#equals(Object)
394 public boolean equalsWithOffset(BitVector other, int offset)
398 return Arrays.equals(bits, offset, offset + other.width(), other.bits, 0, other.width());
402 * All {@link Bit}s symbols concatenated together (MSB first)
404 * @see #parse(String)
407 public String toString()
409 StringBuilder sb = new StringBuilder(bits.length);
412 return sb.toString();
416 * Returns the value of the BitVector as BigInteger.
418 * @throws NumberFormatException if the BitVector is not {@link #isBinary() binary}.
420 public BigInteger getUnsignedValue()
423 throw new NumberFormatException(this + " is not binary");
424 byte[] bytes = new byte[(bits.length / 8) + 1];
425 for (int i = 0; i < bits.length; i++)
427 if (Bit.ONE == bits[i])
429 bytes[i / 8] |= 1 << (i % 8);
432 return new BigInteger(bytes);
436 * Parses a String containing solely {@link Bit} symbols (MSB first)
440 public static BitVector parse(String s)
442 Bit[] values = new Bit[s.length()];
443 for (int i = 0; i < s.length(); i++)
445 values[i] = Bit.parse(s, i);
447 return new BitVector(values);
451 * Iterate over the {@link Bit}s of the BitVector <b>from MSB to LSB</b> (left to right).
454 public Iterator<Bit> iterator()
456 return new Iterator<>()
464 throw new NoSuchElementException();
465 return getMSBit(pos++);
469 public boolean hasNext()
471 return pos != width();