Fixed a performance issue in CoreWire introduced when fixing Fusions
[Mograsim.git] / net.mograsim.logic.core / src / net / mograsim / logic / core / wires / CoreWire.java
1 package net.mograsim.logic.core.wires;
2
3 import static net.mograsim.logic.core.types.Bit.U;
4 import static net.mograsim.logic.core.types.Bit.Z;
5
6 import java.util.ArrayList;
7 import java.util.Arrays;
8 import java.util.HashSet;
9 import java.util.List;
10 import java.util.Set;
11
12 import net.mograsim.logic.core.LogicObservable;
13 import net.mograsim.logic.core.LogicObserver;
14 import net.mograsim.logic.core.timeline.Timeline;
15 import net.mograsim.logic.core.types.Bit;
16 import net.mograsim.logic.core.types.BitVector;
17 import net.mograsim.logic.core.types.BitVector.BitVectorMutator;
18
19 /**
20  * Represents an array of wires that can store n bits of information.
21  * 
22  * @author Fabian Stemmler
23  *
24  */
25 public class CoreWire
26 {
27         public final String name;
28         private BitVector cachedValues;
29         public final int travelTime;
30         private List<ReadEnd> attached = new ArrayList<>();
31         public final int width;
32         List<ReadWriteEnd> inputs = new ArrayList<>();
33         Timeline timeline;
34         private Bit[] bitsWithoutFusions;
35         FusedBit[] fusedBits;
36
37         public CoreWire(Timeline timeline, int width, int travelTime)
38         {
39                 this(timeline, width, travelTime, null);
40         }
41
42         public CoreWire(Timeline timeline, int width, int travelTime, String name)
43         {
44                 if (width < 1)
45                         throw new IllegalArgumentException(
46                                         String.format("Tried to create an array of wires with width %d, but a width of less than 1 makes no sense.", width));
47                 this.name = name;
48                 this.timeline = timeline;
49                 this.width = width;
50                 this.travelTime = travelTime;
51                 initValues();
52         }
53
54         private void initValues()
55         {
56                 cachedValues = U.toVector(width);
57                 bitsWithoutFusions = cachedValues.getBits();
58         }
59
60         private void setNewValues(BitVector newValues)
61         {
62                 cachedValues = newValues;
63                 notifyObservers();
64         }
65
66         private void invalidateCachedValuesForAllFusedWires()
67         {
68                 invalidateCachedValues();
69                 if (fusedBits != null)
70                         for (FusedBit fusion : fusedBits)
71                                 if (fusion != null)
72                                         fusion.invalidateCachedValuesForAllParticipatingWires();
73         }
74
75         private void invalidateCachedValues()
76         {
77                 cachedValues = null;
78                 notifyObservers();
79         }
80
81         void recalculateValuesWithoutFusions()
82         {
83                 Bit[] bits = new Bit[width];
84                 if (inputs.isEmpty())
85                         Arrays.fill(bits, U);
86                 else
87                 {
88                         System.arraycopy(inputs.get(0).getInputValues().getBits(), 0, bits, 0, width);
89                         for (int i = 1; i < inputs.size(); i++)
90                                 Bit.join(bits, inputs.get(i).getInputValues().getBits());
91                 }
92                 bitsWithoutFusions = bits;
93                 if (fusedBits == null)
94                         setNewValues(BitVector.of(bits));
95                 else
96                         invalidateCachedValuesForAllFusedWires();
97         }
98
99         private void recalculatedCachedValues()
100         {
101                 Bit[] bits;
102                 if (fusedBits == null)
103                         bits = bitsWithoutFusions;
104                 else
105                 {
106                         bits = new Bit[width];
107                         for (int i = 0; i < width; i++)
108                         {
109                                 FusedBit fusion = fusedBits[i];
110                                 if (fusion == null)
111                                         bits[i] = bitsWithoutFusions[i];
112                                 else
113                                         bits[i] = fusion.getValue();
114                         }
115                 }
116                 cachedValues = BitVector.of(bits);
117         }
118
119         /**
120          * Forces a Wire to take on specific values. If the new values differ from the old ones, the observers of the Wire will be notified.
121          * WARNING! Use this with care! The preferred way of writing the values is ReadWriteEnd.feedSignals(BitVector)
122          * 
123          * @param values The values the <code>Wire</code> will have immediately after this method is called
124          */
125         public void forceValues(BitVector values)
126         {
127                 setNewValues(values);
128         }
129
130         /**
131          * The {@link CoreWire} is interpreted as an unsigned integer with n bits.
132          * 
133          * @return <code>true</code> if all bits are either <code>Bit.ONE</code> or <code>Bit.ZERO</code> (they do not all have to have the same
134          *         value), not <code>Bit.U</code>, <code>Bit.X</code> or <code>Bit.Z</code>. <code>false</code> is returned otherwise.
135          * 
136          * @author Fabian Stemmler
137          */
138         public boolean hasNumericValue()
139         {
140                 return getValues().isBinary();
141         }
142
143         /**
144          * The {@link CoreWire} is interpreted as an unsigned integer with n bits.
145          * 
146          * @return The unsigned value of the {@link CoreWire}'s bits, where value 0 corresponds with 2^0, value 1 is 2^1 and so on.
147          * 
148          * @author Fabian Stemmler
149          */
150         public long getUnsignedValue()
151         {
152                 long val = 0;
153                 long mask = 1;
154                 for (Bit bit : getValues())
155                 {
156                         switch (bit)
157                         {
158                         default:
159                         case Z:
160                         case X:
161                                 return 0; // TODO: Proper handling for getUnsignedValue(), if not all bits are 1 or 0;
162                         case ONE:
163                                 val |= mask;
164                                 break;
165                         case ZERO:
166                         }
167                         mask = mask << 1;
168                 }
169                 return val;
170         }
171
172         /**
173          * The {@link CoreWire} is interpreted as a signed integer with n bits.
174          * 
175          * @return The signed value of the {@link CoreWire}'s bits, where value 0 corresponds with 2^0, value 1 is 2^1 and so on.
176          * 
177          * @author Fabian Stemmler
178          */
179         public long getSignedValue()
180         {
181                 long val = getUnsignedValue();
182                 long mask = 1 << (width - 1);
183                 if ((mask & val) != 0)
184                 {
185                         int shifts = 64 - width;
186                         return (val << shifts) >> shifts;
187                 }
188                 return val;
189         }
190
191         /**
192          * Returns the least significant bit (LSB)
193          */
194         public Bit getValue()
195         {
196                 return getValue(0);
197         }
198
199         /**
200          * Returns the least significant bit (LSB) of the given index
201          */
202         public Bit getValue(int index)
203         {
204                 return getValues().getLSBit(index);
205         }
206
207         public BitVector getValues(int start, int end)
208         {
209                 return getValues().subVector(start, end);
210         }
211
212         public BitVector getValues()
213         {
214                 if (cachedValues == null)
215                         recalculatedCachedValues();
216                 return cachedValues;
217         }
218
219         /**
220          * Adds an {@link LogicObserver}, who will be notified when the value of the {@link CoreWire} is updated.
221          * 
222          * @param ob The {@link LogicObserver} to be notified of changes.
223          * @return true if the given {@link LogicObserver} was not already registered, false otherwise
224          * 
225          * @author Fabian Stemmler
226          */
227         boolean attachEnd(ReadEnd end)
228         {
229                 return attached.add(end);
230         }
231
232         void detachEnd(ReadEnd end)
233         {
234                 attached.remove(end);
235         }
236
237         private void notifyObservers()
238         {
239                 attached.forEach(ReadEnd::update);
240         }
241
242         /**
243          * Create and register a {@link ReadWriteEnd} object, which is tied to this {@link CoreWire}. This {@link ReadWriteEnd} can be written
244          * to.
245          */
246         public ReadWriteEnd createReadWriteEnd()
247         {
248                 return new ReadWriteEnd();
249         }
250
251         /**
252          * Create a {@link ReadEnd} object, which is tied to this {@link CoreWire}. This {@link ReadEnd} cannot be written to.
253          */
254         public ReadEnd createReadOnlyEnd()
255         {
256                 return new ReadEnd();
257         }
258
259         void registerInput(ReadWriteEnd toRegister)
260         {
261                 inputs.add(toRegister);
262                 recalculateValuesWithoutFusions();
263         }
264
265         /**
266          * A {@link ReadEnd} feeds a constant signal into the {@link CoreWire} it is tied to. The combination of all inputs determines the
267          * {@link CoreWire}s final value. X dominates all other inputs Z does not affect the final value, unless there are no other inputs than
268          * Z 0 and 1 turn into X when they are mixed
269          * 
270          * @author Fabian Stemmler
271          */
272         public class ReadEnd implements LogicObservable
273         {
274                 private List<LogicObserver> observers = new ArrayList<>();
275
276                 ReadEnd()
277                 {
278                         super();
279                         CoreWire.this.attachEnd(this);
280                 }
281
282                 public void update()
283                 {
284                         notifyObservers();
285                 }
286
287                 /**
288                  * Included for convenient use on {@link CoreWire}s of width 1.
289                  * 
290                  * @return The value of bit 0.
291                  * 
292                  * @author Fabian Stemmler
293                  */
294                 public Bit getValue()
295                 {
296                         return CoreWire.this.getValue();
297                 }
298
299                 /**
300                  * @param index Index of the requested bit.
301                  * @return The value of the indexed bit.
302                  * 
303                  * @author Fabian Stemmler
304                  */
305                 public Bit getValue(int index)
306                 {
307                         return CoreWire.this.getValue(index);
308                 }
309
310                 public BitVector getValues()
311                 {
312                         return CoreWire.this.getValues();
313                 }
314
315                 /**
316                  * @param start Start of the wanted segment. (inclusive)
317                  * @param end   End of the wanted segment. (exclusive)
318                  * @return The values of the segment of {@link Bit}s indexed.
319                  * 
320                  * @author Fabian Stemmler
321                  */
322                 public BitVector getValues(int start, int end)
323                 {
324                         return CoreWire.this.getValues(start, end);
325                 }
326
327                 /**
328                  * The {@link CoreWire} is interpreted as an unsigned integer with n bits.
329                  * 
330                  * @return <code>true</code> if all bits are either <code>Bit.ONE</code> or <code>Bit.ZERO</code> (they do not all have to have the
331                  *         same value), not <code>Bit.X</code> or <code>Bit.Z</code>. <code>false</code> is returned otherwise.
332                  * 
333                  * @author Fabian Stemmler
334                  */
335                 public boolean hasNumericValue()
336                 {
337                         return CoreWire.this.hasNumericValue();
338                 }
339
340                 /**
341                  * The {@link CoreWire} is interpreted as an unsigned integer with n bits.
342                  * 
343                  * @return The unsigned value of the {@link CoreWire}'s bits, where value 0 corresponds with 2^0, value 1 is 2^1 and so on.
344                  * 
345                  * @author Fabian Stemmler
346                  */
347                 public long getUnsignedValue()
348                 {
349                         return CoreWire.this.getUnsignedValue();
350                 }
351
352                 /**
353                  * The {@link CoreWire} is interpreted as a signed integer with n bits.
354                  * 
355                  * @return The signed value of the {@link CoreWire}'s bits, where value 0 corresponds with 2^0, value 1 is 2^1 and so on.
356                  * 
357                  * @author Fabian Stemmler
358                  */
359                 public long getSignedValue()
360                 {
361                         return CoreWire.this.getSignedValue();
362                 }
363
364                 @Override
365                 public String toString()
366                 {
367                         return CoreWire.this.toString();
368                 }
369
370                 public void close()
371                 {
372                         inputs.remove(this);
373                         detachEnd(this);
374                         recalculateValuesWithoutFusions();
375                 }
376
377                 public int width()
378                 {
379                         return width;
380                 }
381
382                 public CoreWire getWire()
383                 {
384                         return CoreWire.this;
385                 }
386
387                 @Override
388                 public void registerObserver(LogicObserver ob)
389                 {
390                         observers.add(ob);
391                 }
392
393                 @Override
394                 public void deregisterObserver(LogicObserver ob)
395                 {
396                         observers.remove(ob);
397                 }
398
399 //              void registerCloseObserver(LogicObserver ob)
400 //              {
401 //                      closeObserver.add(ob);
402 //              }
403 //              
404 //              void deregisterCloseObserver(LogicObserver ob)
405 //              {
406 //                      closeObserver.remove(ob);
407 //              }
408
409                 @Override
410                 public void notifyObservers()
411                 {
412                         observers.forEach(ob -> ob.update(this));
413                 }
414         }
415
416         public class ReadWriteEnd extends ReadEnd
417         {
418                 private boolean open;
419                 private boolean isWriting;
420                 private BitVector inputValues;
421
422                 ReadWriteEnd()
423                 {
424                         super();
425                         open = true;
426                         isWriting = true;
427                         initValues();
428                         registerInput(this);
429                 }
430
431                 private void initValues()
432                 {
433                         inputValues = U.toVector(width);
434                 }
435
436                 /**
437                  * Sets the wires values. This takes up time, as specified by the {@link CoreWire}s travel time.
438                  * 
439                  * @param newValues The new values the wires should take on.
440                  * 
441                  * @author Fabian Stemmler
442                  */
443                 public void feedSignals(Bit... newValues)
444                 {
445                         feedSignals(BitVector.of(newValues));
446                 }
447
448                 public void feedSignals(BitVector newValues)
449                 {
450                         if (newValues.length() != width)
451                                 throw new IllegalArgumentException(
452                                                 String.format("Attempted to input %d bits instead of %d bits.", newValues.length(), width));
453                         if (!open)
454                                 throw new IllegalStateException("Attempted to write to closed WireArrayEnd.");
455                         timeline.addEvent(e -> setValues(newValues), travelTime);
456                 }
457
458                 /**
459                  * Sets values of a subarray of wires. This takes up time, as specified by the {@link CoreWire}s travel time.
460                  * 
461                  * @param bitVector   The new values the wires should take on.
462                  * @param startingBit The first index of the subarray of wires.
463                  * 
464                  * @author Fabian Stemmler
465                  */
466                 public void feedSignals(int startingBit, BitVector bitVector)
467                 {
468                         if (!open)
469                                 throw new IllegalStateException("Attempted to write to closed WireArrayEnd.");
470                         timeline.addEvent(e -> setValues(startingBit, bitVector), travelTime);
471                 }
472
473                 /**
474                  * Sets the values that are being fed into the {@link CoreWire}. The preferred way of setting {@link ReadWriteEnd} values is via
475                  * feedValues(...) with a delay.
476                  */
477                 void setValues(int startingBit, BitVector newValues)
478                 {
479                         // index check covered in equals
480                         if (!inputValues.equalsWithOffset(newValues, startingBit))
481                         {
482                                 Bit[] vals = inputValues.getBits();
483                                 System.arraycopy(newValues.getBits(), 0, vals, startingBit, newValues.length());
484                                 inputValues = BitVector.of(vals);
485                                 CoreWire.this.recalculateValuesWithoutFusions();
486                         }
487                 }
488
489                 /**
490                  * Sets the values that are being fed into the {@link CoreWire}. The preferred way of setting {@link ReadWriteEnd} values is via
491                  * feedValues(...) with a delay.
492                  */
493                 void setValues(BitVector newValues)
494                 {
495                         if (inputValues.equals(newValues))
496                                 return;
497                         inputValues = newValues;
498                         CoreWire.this.recalculateValuesWithoutFusions();
499                 }
500
501                 /**
502                  * @return The value (of bit 0) the {@link ReadEnd} is currently feeding into the associated {@link CoreWire}.Returns the least
503                  *         significant bit (LSB)
504                  */
505                 public Bit getInputValue()
506                 {
507                         return getInputValue(0);
508                 }
509
510                 /**
511                  * @return The value which the {@link ReadEnd} is currently feeding into the associated {@link CoreWire} at the indexed {@link Bit}.
512                  *         Returns the least significant bit (LSB)
513                  * 
514                  */
515                 public Bit getInputValue(int index)
516                 {
517                         return inputValues.getLSBit(index);
518                 }
519
520                 /**
521                  * @return A copy (safe to modify) of the values the {@link ReadEnd} is currently feeding into the associated {@link CoreWire}.
522                  */
523                 public BitVector getInputValues()
524                 {
525                         return inputValues;
526                 }
527
528                 public BitVector getInputValues(int start, int end)
529                 {
530                         return inputValues.subVector(start, end);
531                 }
532
533                 /**
534                  * {@link ReadEnd} now feeds Z into the associated {@link CoreWire}.
535                  */
536                 public void clearSignals()
537                 {
538                         feedSignals(Z.toVector(width));
539                 }
540
541                 public BitVector wireValuesExcludingMe()
542                 {
543                         BitVectorMutator mutator = BitVectorMutator.empty();
544                         boolean modified = false;
545                         for (ReadWriteEnd wireEnd : inputs)
546                         {
547                                 if (wireEnd == this)
548                                         continue;
549                                 modified = true;
550                                 mutator.join(wireEnd.inputValues);
551                         }
552                         if (!modified)
553                                 mutator.join(BitVector.of(Bit.Z, width));
554                         return mutator.toBitVector();
555                 }
556
557                 @Override
558                 public String toString()
559                 {
560                         return inputValues.toString();
561                 }
562
563                 @Override
564                 public void close()
565                 {
566                         super.close();
567                         open = false;
568                 }
569
570                 void setWriting(boolean isWriting)
571                 {
572                         if (this.isWriting != isWriting)
573                         {
574                                 this.isWriting = isWriting;
575                                 if (isWriting)
576                                         inputs.add(this);
577                                 else
578                                         inputs.remove(this);
579                                 CoreWire.this.recalculateValuesWithoutFusions();
580                         }
581                 }
582
583                 boolean isWriting()
584                 {
585                         return isWriting;
586                 }
587         }
588
589         @Override
590         public String toString()
591         {
592                 String name = this.name == null ? String.format("0x%08x", hashCode()) : this.name;
593                 return String.format("wire %s value: %s inputs: %s", name, getValues(), inputs);
594         }
595
596         public static ReadEnd[] extractEnds(CoreWire[] w)
597         {
598                 ReadEnd[] inputs = new ReadEnd[w.length];
599                 for (int i = 0; i < w.length; i++)
600                         inputs[i] = w[i].createReadWriteEnd();
601                 return inputs;
602         }
603
604         /**
605          * 
606          * Fuses two wires together. If the bits change in one Wire, the other is changed accordingly immediately. Warning: The bits are
607          * permanently fused together.
608          * 
609          * @param a The {@link CoreWire} to be fused with b
610          * @param b The {@link CoreWire} to be fused with a
611          */
612         public static void fuse(CoreWire a, CoreWire b)
613         {
614                 fuse(a, b, 0, 0, a.width);
615         }
616
617         /**
618          * Fuses the selected bits of two wires together. If the bits change in one Wire, the other is changed accordingly immediately. Warning:
619          * The bits are permanently fused together.
620          * 
621          * @param a     The {@link CoreWire} to be (partially) fused with b
622          * @param b     The {@link CoreWire} to be (partially) fused with a
623          * @param fromA The first bit of {@link CoreWire} a to be fused
624          * @param fromB The first bit of {@link CoreWire} b to be fused
625          * @param width The amount of bits to fuse
626          */
627         public static void fuse(CoreWire a, CoreWire b, int fromA, int fromB, int width)
628         {
629                 // iterate in this direction to be fail-fast (rely on the checks in fuse(Wire, Wire, int, int)
630                 for (int i = width - 1; i >= 0; i--)
631                         fuse(a, b, fromA + i, fromB + i);
632         }
633
634         /**
635          * Fuses one bit of two wires together. If this bit changes in one Wire, the other is changed accordingly immediately. Warning: The bits
636          * are permanently fused together.
637          * 
638          * @param a    The {@link CoreWire} to be (partially) fused with b
639          * @param b    The {@link CoreWire} to be (partially) fused with a
640          * @param bitA The bit of {@link CoreWire} a to be fused
641          * @param bitB The bit of {@link CoreWire} b to be fused
642          */
643         public static void fuse(CoreWire a, CoreWire b, int bitA, int bitB)
644         {
645                 if (bitA >= a.width)
646                         throw new IllegalArgumentException("No bit " + bitA + " in " + a + " (width " + a.width + ")");
647                 if (bitB >= b.width)
648                         throw new IllegalArgumentException("No bit " + bitB + " in " + b + " (width " + b.width + ")");
649                 if (a.fusedBits == null)
650                         a.fusedBits = new FusedBit[a.width];
651                 if (b.fusedBits == null)
652                         b.fusedBits = new FusedBit[b.width];
653                 FusedBit oldFusionA = a.fusedBits[bitA];
654                 FusedBit oldFusionB = b.fusedBits[bitB];
655                 if (oldFusionA == null)
656                         if (oldFusionB == null)
657                         {
658                                 FusedBit fusion = new FusedBit();
659                                 fusion.addParticipatingWireBit(a, bitA);
660                                 fusion.addParticipatingWireBit(b, bitB);
661                         } else
662                                 oldFusionB.addParticipatingWireBit(a, bitA);
663                 else if (oldFusionB == null)
664                         oldFusionA.addParticipatingWireBit(b, bitB);
665                 else
666                         oldFusionA.mergeOtherIntoThis(oldFusionB);
667         }
668
669         private static class FusedBit
670         {
671                 private final Set<WireBit> participatingWireBits;
672
673                 public FusedBit()
674                 {
675                         this.participatingWireBits = new HashSet<>();
676                 }
677
678                 public void addParticipatingWireBit(CoreWire w, int bit)
679                 {
680                         addParticipatingWireBit(new WireBit(w, bit));
681                 }
682
683                 private void addParticipatingWireBit(WireBit wb)
684                 {
685                         wb.wire.fusedBits[wb.bit] = this;
686                         participatingWireBits.add(wb);
687                         wb.wire.invalidateCachedValuesForAllFusedWires();
688                 }
689
690                 public void mergeOtherIntoThis(FusedBit other)
691                 {
692                         for (WireBit wb : other.participatingWireBits)
693                                 addParticipatingWireBit(wb);
694                 }
695
696                 public void invalidateCachedValuesForAllParticipatingWires()
697                 {
698                         for (WireBit wb : participatingWireBits)
699                                 wb.wire.invalidateCachedValues();
700                 }
701
702                 public Bit getValue()
703                 {
704                         Bit result = null;
705                         for (WireBit wb : participatingWireBits)
706                                 if (!wb.wire.inputs.isEmpty())
707                                 {
708                                         Bit bit = wb.wire.bitsWithoutFusions[wb.bit];
709                                         result = result == null ? bit : result.join(bit);
710                                 }
711                         return result == null ? U : result;
712                 }
713         }
714
715         private static class WireBit
716         {
717                 public final CoreWire wire;
718                 public final int bit;
719
720                 public WireBit(CoreWire wire, int bit)
721                 {
722                         this.wire = wire;
723                         this.bit = bit;
724                 }
725
726                 @Override
727                 public int hashCode()
728                 {
729                         final int prime = 31;
730                         int result = 1;
731                         result = prime * result + bit;
732                         result = prime * result + ((wire == null) ? 0 : wire.hashCode());
733                         return result;
734                 }
735
736                 @Override
737                 public boolean equals(Object obj)
738                 {
739                         if (this == obj)
740                                 return true;
741                         if (obj == null)
742                                 return false;
743                         if (getClass() != obj.getClass())
744                                 return false;
745                         WireBit other = (WireBit) obj;
746                         if (bit != other.bit)
747                                 return false;
748                         if (wire == null)
749                         {
750                                 if (other.wire != null)
751                                         return false;
752                         } else if (!wire.equals(other.wire))
753                                 return false;
754                         return true;
755                 }
756         }
757 }