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())
114 public boolean isHighImpedance()
116 for (int i = 0; i < bits.length; i++)
118 if (!bits[i].equals(Bit.Z))
125 public BitVector join(BitVector t)
127 checkCompatibility(t);
128 if (bits.length == 1)
129 return SINGLE_BIT_MAPPING[bits[0].join(t.bits[0]).ordinal()];
130 return new BitVector(binOp(bits.clone(), t.bits, Bit::join));
134 public BitVector and(BitVector t)
136 checkCompatibility(t);
137 if (bits.length == 1)
138 return SINGLE_BIT_MAPPING[bits[0].and(t.bits[0]).ordinal()];
139 return new BitVector(binOp(bits.clone(), t.bits, Bit::and));
143 public BitVector or(BitVector t)
145 checkCompatibility(t);
146 if (bits.length == 1)
147 return SINGLE_BIT_MAPPING[bits[0].or(t.bits[0]).ordinal()];
148 return new BitVector(binOp(bits.clone(), t.bits, Bit::or));
152 public BitVector xor(BitVector t)
154 checkCompatibility(t);
155 if (bits.length == 1)
156 return SINGLE_BIT_MAPPING[bits[0].xor(t.bits[0]).ordinal()];
157 return new BitVector(binOp(bits.clone(), t.bits, Bit::xor));
161 public BitVector not()
163 if (bits.length == 1)
164 return SINGLE_BIT_MAPPING[bits[0].not().ordinal()];
165 return new BitVector(unOp(bits.clone(), Bit::not));
173 public BitVector concat(BitVector other)
175 Bit[] newBits = Arrays.copyOf(bits, length() + other.length());
176 System.arraycopy(other.bits, 0, newBits, length(), other.length());
177 return new BitVector(newBits);
180 public BitVector subVector(int start)
182 return new BitVector(Arrays.copyOfRange(bits, start, length()));
185 public BitVector subVector(int start, int end)
187 return new BitVector(Arrays.copyOfRange(bits, start, end));
190 private void checkCompatibility(BitVector bv)
192 if (length() != bv.length())
193 throw new IllegalArgumentException(format("BitVector length does not match: %d and %d", length(), bv.length()));
196 static Bit[] binOp(Bit[] dest, Bit[] second, BinaryOperator<Bit> op)
199 return second.clone();
200 for (int i = 0; i < dest.length; i++)
202 dest[i] = op.apply(dest[i], second[i]);
207 static Bit[] unOp(Bit[] dest, UnaryOperator<Bit> op)
211 for (int i = 0; i < dest.length; i++)
213 dest[i] = op.apply(dest[i]);
219 * Class for comfortable and efficient manipulation of {@link BitVector}s, similar to {@link StringBuilder}
221 * @author Christian Femers
223 public static final class BitVectorMutator implements LogicType<BitVectorMutator, BitVector>
227 private BitVectorMutator(Bit[] bits)
232 static BitVectorMutator of(BitVector bv)
234 return new BitVectorMutator(bv.getBits());
238 * Returns a new mutator of the specified length, <b>with all bits set to <code>null</code></b>. Use with care!
240 public static BitVectorMutator ofLength(int length)
242 return new BitVectorMutator(new Bit[length]);
246 * Returns an empty mutator which has no bits set and will simply copy the values from the first binary operation performed.
248 * An empty BitVectorMutator <b>must not</b> be converted to BitVector or used to manipulate single bits until at least one two
249 * operand logic operation is performed.
251 public static BitVectorMutator empty()
253 return new BitVectorMutator(null);
259 public boolean isEmpty()
265 * Produces the resulting, immutable {@link BitVector}<br>
267 * @throws IllegalStateException if the mutator is (still) empty
269 public BitVector toBitVector()
272 throw new IllegalStateException("cannot create a BitVector from an empty mutator");
273 return new BitVector(bits);
277 public BitVectorMutator join(BitVector t)
279 checkCompatibility(t);
280 bits = binOp(bits, t.bits, Bit::join);
285 public BitVectorMutator and(BitVector t)
287 checkCompatibility(t);
288 bits = binOp(bits, t.bits, Bit::and);
293 public BitVectorMutator or(BitVector t)
295 checkCompatibility(t);
296 bits = binOp(bits, t.bits, Bit::or);
301 public BitVectorMutator xor(BitVector t)
303 checkCompatibility(t);
304 bits = binOp(bits, t.bits, Bit::xor);
309 public BitVectorMutator not()
311 unOp(bits, Bit::not);
316 * Set the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
318 public void setMSBit(int bitIndex, Bit bit)
321 throw new IllegalStateException("cannot set a bit of an empty mutator");
322 bits[bitIndex] = bit;
326 * Set the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
328 public void setLSBit(int bitIndex, Bit bit)
331 throw new IllegalStateException("cannot set a bit of an empty mutator");
332 bits[bits.length - bitIndex - 1] = bit;
336 * Returns the most significant bit at <code>bitIndex</code>. (leftmost bit of a binary number at the given index)
338 public Bit getMSBit(int bitIndex)
341 throw new IllegalStateException("cannot get a bit of an empty mutator");
342 return bits[bitIndex];
346 * Returns the least significant bit at <code>bitIndex</code>. (rightmost bit of a binary number at the given index)
348 public Bit getLSBit(int bitIndex)
351 throw new IllegalStateException("cannot get a bit of an empty mutator");
352 return bits[bits.length - bitIndex - 1];
358 throw new IllegalStateException("cannot obtain a length of an empty mutator");
362 private void checkCompatibility(BitVector bv)
364 if (bits != null && bits.length != bv.length())
365 throw new IllegalArgumentException(format("BitVector length does not match: %d and %d", bits.length, bv.length()));
370 * @see Arrays#hashCode(Object[])
373 public int hashCode()
375 return Arrays.hashCode(bits);
379 * Does test for equality of values/content
381 * @see Object#equals(Object)
384 public boolean equals(Object obj)
388 if (!(obj instanceof BitVector))
390 BitVector other = (BitVector) obj;
391 return Arrays.equals(bits, other.bits);
395 * Does test for equality of values/content, shifting the other BitVector by <code>offset</code> to the right.<br>
396 * Therefore <code>offset + other.length() <= this.wdith()</code> needs to be true.
398 * @throws ArrayIndexOutOfBoundsException if <code>offset + other.length() > this.length()</code>
400 * @see Object#equals(Object)
402 public boolean equalsWithOffset(BitVector other, int offset)
406 return Arrays.equals(bits, offset, offset + other.length(), other.bits, 0, other.length());
410 public String toString()
412 return toBitstring();
416 * All {@link Bit}s symbols concatenated together (MSB first)
418 * @see #parseBitstring(String)
420 public String toBitstring()
422 StringBuilder sb = new StringBuilder(bits.length);
425 return sb.toString();
429 * Returns the value of the BitVector as BigInteger.
431 * @throws NumberFormatException if the BitVector is not {@link #isBinary() binary}.
433 public BigInteger getUnsignedValue()
436 throw new NumberFormatException(this + " is not binary");
437 byte[] bytes = new byte[(bits.length / 8 + (bits.length % 8 == 0 ? 0 : 1)) + 1];
438 for (int i = bits.length - 1; i >= 0; i--)
440 if (Bit.ONE == bits[bits.length - i - 1])
444 bytes[bytes.length - (i / 8) - 1] |= 1 << (i % 8);
446 catch (IndexOutOfBoundsException e)
452 return new BigInteger(bytes);
455 public long getUnsignedValueLong()
457 return getUnsignedValue().longValue();
461 * Returns the value of the BitVector as BigInteger interpreted as a two's complement number.
463 * @throws NumberFormatException if the BitVector is not {@link #isBinary() binary}.
465 * @author Daniel Kirschten
467 public BigInteger getSignedValue()
469 BigInteger unsignedValue = getUnsignedValue();
470 if (bits[bits.length - 1] == Bit.ZERO)
471 return unsignedValue;
472 return unsignedValue.subtract(BitVector.of(Bit.ONE, bits.length).getUnsignedValue()).subtract(BigInteger.ONE);// TODO speed this up!
475 public long getSignedValueLong()
477 return getSignedValue().longValue();
481 * Parses a String containing solely {@link Bit} symbols (MSB first)
483 * @see #toBitString()
485 public static BitVector parseBitstring(String s)
487 Bit[] values = new Bit[s.length()];
488 for (int i = 0; i < s.length(); i++)
490 values[i] = Bit.parse(s, i);
492 return new BitVector(values);
496 * Changes a single Bit using the given operation. This can be used to set, clear or flip bits.
498 * @param msbIndex index of the MSB to be changed
499 * @param singleBitOperation the operation to perform on that Bit
500 * @return the resulting, new BitVektor
502 public BitVector withBitChanged(int msbIndex, UnaryOperator<Bit> singleBitOperation)
504 Bit[] newBits = bits.clone();
505 newBits[msbIndex] = singleBitOperation.apply(newBits[msbIndex]);
506 return new BitVector(newBits);
510 * Iterate over the {@link Bit}s of the BitVector <b>from MSB to LSB</b> (left to right).
513 public Iterator<Bit> iterator()
515 return new Iterator<>()
523 throw new NoSuchElementException();
524 return getMSBit(pos++);
528 public boolean hasNext()
530 return pos != length();
535 public BitVector reverse()
537 int length = length();
538 Bit[] other = new Bit[length];
539 for (int i = 0, j = length - 1; i < length; i++, j--)
543 return new BitVector(other);