/
MIPS.sol
918 lines (825 loc) · 33.9 KB
/
MIPS.sol
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
// SPDX-License-Identifier: MIT
pragma solidity 0.7.6;
import { IPreimageOracle } from "./interfaces/IPreimageOracle.sol";
/// @title MIPS
/// @notice The MIPS contract emulates a single MIPS instruction.
/// Note that delay slots are isolated instructions:
/// the nextPC in the state pre-schedules where the VM jumps next.
/// The Step input is a packed VM state, with binary-merkle-tree
/// witness data for memory reads/writes.
/// The Step outputs a keccak256 hash of the packed VM State,
/// and logs the resulting state for offchain usage.
/// @dev https://inst.eecs.berkeley.edu/~cs61c/resources/MIPS_Green_Sheet.pdf
/// @dev https://www.cs.cmu.edu/afs/cs/academic/class/15740-f97/public/doc/mips-isa.pdf
/// (page A-177)
/// @dev https://uweb.engr.arizona.edu/~ece369/Resources/spim/MIPSReference.pdf
/// @dev https://en.wikibooks.org/wiki/MIPS_Assembly/Instruction_Formats
/// @dev https://github.com/golang/go/blob/master/src/syscall/zerrors_linux_mips.go
/// MIPS linux kernel errors used by Go runtime
contract MIPS {
/// @notice Stores the VM state.
/// Total state size: 32 + 32 + 6 * 4 + 1 + 1 + 8 + 32 * 4 = 226 bytes
/// If nextPC != pc + 4, then the VM is executing a branch/jump delay slot.
struct State {
bytes32 memRoot;
bytes32 preimageKey;
uint32 preimageOffset;
uint32 pc;
uint32 nextPC;
uint32 lo;
uint32 hi;
uint32 heap;
uint8 exitCode;
bool exited;
uint64 step;
uint32[32] registers;
}
/// @notice Start of the data segment.
uint32 constant public BRK_START = 0x40000000;
uint32 constant FD_STDIN = 0;
uint32 constant FD_STDOUT = 1;
uint32 constant FD_STDERR = 2;
uint32 constant FD_HINT_READ = 3;
uint32 constant FD_HINT_WRITE = 4;
uint32 constant FD_PREIMAGE_READ = 5;
uint32 constant FD_PREIMAGE_WRITE = 6;
uint32 constant EBADF = 0x9;
uint32 constant EINVAL = 0x16;
/// @notice The pre-image oracle.
IPreimageOracle public oracle;
/// @notice Extends the value leftwards with its most significant bit (sign extension).
function SE(uint32 _dat, uint32 _idx) internal pure returns (uint32) {
bool isSigned = (_dat >> (_idx - 1)) != 0;
uint256 signed = ((1 << (32 - _idx)) - 1) << _idx;
uint256 mask = (1 << _idx) - 1;
return uint32(_dat & mask | (isSigned ? signed : 0));
}
/// @notice Computes the hash of the MIPS state.
/// @return out_ The hash of the MIPS state.
function outputState() internal returns (bytes32 out_) {
assembly {
// copies 'size' bytes, right-aligned in word at 'from', to 'to', incl. trailing data
function copyMem(from, to, size) -> fromOut, toOut {
mstore(to, mload(add(from, sub(32, size))))
fromOut := add(from, 32)
toOut := add(to, size)
}
// From points to the MIPS State
let from := 0x80
// Copy to the free memory pointer
let start := mload(0x40)
let to := start
// Copy state to free memory
from, to := copyMem(from, to, 32) // memRoot
from, to := copyMem(from, to, 32) // preimageKey
from, to := copyMem(from, to, 4) // preimageOffset
from, to := copyMem(from, to, 4) // pc
from, to := copyMem(from, to, 4) // nextPC
from, to := copyMem(from, to, 4) // lo
from, to := copyMem(from, to, 4) // hi
from, to := copyMem(from, to, 4) // heap
from, to := copyMem(from, to, 1) // exitCode
from, to := copyMem(from, to, 1) // exited
from, to := copyMem(from, to, 8) // step
from := add(from, 32) // offset to registers
// Copy registers
for { let i := 0 } lt(i, 32) { i := add(i, 1) } {
from, to := copyMem(from, to, 4)
}
// Clean up end of memory
mstore(to, 0)
// Log the resulting MIPS state, for debugging
log0(start, sub(to, start))
// Compute the hash of the resulting MIPS state
out_ := keccak256(start, sub(to, start))
}
return out_;
}
/// @notice Handles a syscall.
function handleSyscall() internal returns (bytes32 out_) {
// Load state from memory
State memory state;
assembly {
state := 0x80
}
// Load the syscall number from the registers
uint32 syscall_no = state.registers[2];
uint32 v0 = 0;
uint32 v1 = 0;
// Load the syscall arguments from the registers
uint32 a0 = state.registers[4];
uint32 a1 = state.registers[5];
uint32 a2 = state.registers[6];
// mmap: Allocates a page from the heap.
if (syscall_no == 4090) {
uint32 sz = a1;
if (sz&4095 != 0) { // adjust size to align with page size
sz += 4096 - (sz&4095);
}
if (a0 == 0) {
v0 = state.heap;
state.heap += sz;
} else {
v0 = a0;
}
}
// brk: Returns a fixed address for the program break at 0x40000000
else if (syscall_no == 4045) {
v0 = BRK_START;
}
// clone (not supported) returns 1
else if (syscall_no == 4120) {
v0 = 1;
}
// exit group: Sets the Exited and ExitCode states to true and argument 0.
else if (syscall_no == 4246) {
state.exited = true;
state.exitCode = uint8(a0);
return outputState();
}
// read: Like Linux read syscall. Splits unaligned reads into aligned reads.
else if (syscall_no == 4003) {
// args: a0 = fd, a1 = addr, a2 = count
// returns: v0 = read, v1 = err code
if (a0 == FD_STDIN) {
// Leave v0 and v1 zero: read nothing, no error
}
// pre-image oracle read
else if (a0 == FD_PREIMAGE_READ) {
// verify proof 1 is correct, and get the existing memory.
uint32 mem = readMem(a1 & 0xFFffFFfc, 1); // mask the addr to align it to 4 bytes
(bytes32 dat, uint256 datLen) = oracle.readPreimage(state.preimageKey, state.preimageOffset);
// Transform data for writing to memory
// We use assembly for more precise ops, and no var count limit
assembly {
let alignment := and(a1, 3) // the read might not start at an aligned address
let space := sub(4, alignment) // remaining space in memory word
if lt(space, datLen) { datLen := space } // if less space than data, shorten data
if lt(a2, datLen) { datLen := a2 } // if requested to read less, read less
dat := shr(sub(256, mul(datLen, 8)), dat) // right-align data
dat := shl(mul(sub(sub(4, datLen), alignment), 8), dat) // position data to insert into memory word
let mask := sub(shl(mul(sub(4, alignment), 8), 1), 1) // mask all bytes after start
let suffixMask := sub(shl(mul(sub(sub(4, alignment), datLen), 8), 1), 1) // mask of all bytes starting from end, maybe none
mask := and(mask, not(suffixMask)) // reduce mask to just cover the data we insert
mem := or(and(mem, not(mask)), dat) // clear masked part of original memory, and insert data
}
// Write memory back
writeMem(a1 & 0xFFffFFfc, 1, mem);
state.preimageOffset += uint32(datLen);
v0 = uint32(datLen);
}
// hint response
else if (a0 == FD_HINT_READ) {
// Don't read into memory, just say we read it all
// The result is ignored anyway
v0 = a2;
}
else {
v0 = 0xFFffFFff;
v1 = EBADF;
}
}
// write: like Linux write syscall. Splits unaligned writes into aligned writes.
else if (syscall_no == 4004) {
// args: a0 = fd, a1 = addr, a2 = count
// returns: v0 = written, v1 = err code
if (a0 == FD_STDOUT || a0 == FD_STDERR || a0 == FD_HINT_WRITE) {
v0 = a2; // tell program we have written everything
}
// pre-image oracle
else if (a0 == FD_PREIMAGE_WRITE) {
uint32 mem = readMem(a1 & 0xFFffFFfc, 1); // mask the addr to align it to 4 bytes
bytes32 key = state.preimageKey;
// Construct pre-image key from memory
// We use assembly for more precise ops, and no var count limit
assembly {
let alignment := and(a1, 3) // the read might not start at an aligned address
let space := sub(4, alignment) // remaining space in memory word
if lt(space, a2) { a2 := space } // if less space than data, shorten data
key := shl(mul(a2, 8), key) // shift key, make space for new info
let mask := sub(shl(mul(a2, 8), 1), 1) // mask for extracting value from memory
mem := and(shr(mul(sub(space, a2), 8), mem), mask) // align value to right, mask it
key := or(key, mem) // insert into key
}
// Write pre-image key to oracle
state.preimageKey = key;
state.preimageOffset = 0; // reset offset, to read new pre-image data from the start
v0 = a2;
}
else {
v0 = 0xFFffFFff;
v1 = EBADF;
}
}
// fcntl: Like linux fcntl syscall, but only supports minimal file-descriptor control commands,
// to retrieve the file-descriptor R/W flags.
else if (syscall_no == 4055) { // fcntl
// args: a0 = fd, a1 = cmd
if (a1 == 3) { // F_GETFL: get file descriptor flags
if (a0 == FD_STDIN || a0 == FD_PREIMAGE_READ || a0 == FD_HINT_READ) {
v0 = 0; // O_RDONLY
} else if (a0 == FD_STDOUT || a0 == FD_STDERR || a0 == FD_PREIMAGE_WRITE || a0 == FD_HINT_WRITE) {
v0 = 1; // O_WRONLY
} else {
v0 = 0xFFffFFff;
v1 = EBADF;
}
} else {
v0 = 0xFFffFFff;
v1 = EINVAL; // cmd not recognized by this kernel
}
}
// Write the results back to the state registers
state.registers[2] = v0;
state.registers[7] = v1;
// Update the PC and nextPC
state.pc = state.nextPC;
state.nextPC = state.nextPC + 4;
out_ = outputState();
}
/// @notice Handles a branch instruction, updating the MIPS state PC where needed.
/// @param _opcode The opcode of the branch instruction.
/// @param _insn The instruction to be executed.
/// @param _rtReg The register to be used for the branch.
/// @param _rs The register to be compared with the branch register.
/// @return out_ The hashed MIPS state.
function handleBranch(uint32 _opcode, uint32 _insn, uint32 _rtReg, uint32 _rs) internal returns (bytes32 out_) {
// Load state from memory
State memory state;
assembly {
state := 0x80
}
bool shouldBranch = false;
// beq/bne: Branch on equal / not equal
if (_opcode == 4 || _opcode == 5) {
uint32 rt = state.registers[_rtReg];
shouldBranch = (_rs == rt && _opcode == 4) || (_rs != rt && _opcode == 5);
}
// blez: Branches if instruction is less than or equal to zero
else if (_opcode == 6) {
shouldBranch = int32(_rs) <= 0;
}
// bgtz: Branches if instruction is greater than zero
else if (_opcode == 7) {
shouldBranch = int32(_rs) > 0;
}
// bltz/bgez: Branch on less than zero / greater than or equal to zero
else if (_opcode == 1) {
// regimm
uint32 rtv = ((_insn >> 16) & 0x1F);
if (rtv == 0) {
shouldBranch = int32(_rs) < 0;
}
if (rtv == 1) {
shouldBranch = int32(_rs) >= 0;
}
}
// Update the state's previous PC
uint32 prevPC = state.pc;
// Execute the delay slot first
state.pc = state.nextPC;
// If we should branch, update the PC to the branch target
// Otherwise, proceed to the next instruction
if (shouldBranch) {
state.nextPC = prevPC + 4 + (SE(_insn & 0xFFFF, 16) << 2);
} else {
state.nextPC = state.nextPC + 4;
}
// Return the hash of the resulting state
out_ = outputState();
}
/// @notice Handles HI and LO register instructions.
/// @param _func The function code of the instruction.
/// @param _rs The value of the RS register.
/// @param _rt The value of the RT register.
/// @param _storeReg The register to store the result in.
/// @return out_ The hash of the resulting MIPS state.
function handleHiLo(uint32 _func, uint32 _rs, uint32 _rt, uint32 _storeReg) internal returns (bytes32 out_) {
// Load state from memory
State memory state;
assembly {
state := 0x80
}
uint32 val;
// mfhi: Move the contents of the HI register into the destination
if (_func == 0x10) {
val = state.hi;
}
// mthi: Move the contents of the source into the HI register
else if (_func == 0x11) {
state.hi = _rs;
}
// mflo: Move the contents of the LO register into the destination
else if (_func == 0x12) {
val = state.lo;
}
// mtlo: Move the contents of the source into the LO register
else if (_func == 0x13) {
state.lo = _rs;
}
// mult: Multiplies `rs` by `rt` and stores the result in HI and LO registers
else if (_func == 0x18) {
uint64 acc = uint64(int64(int32(_rs)) * int64(int32(_rt)));
state.hi = uint32(acc >> 32);
state.lo = uint32(acc);
}
// multu: Unsigned multiplies `rs` by `rt` and stores the result in HI and LO registers
else if (_func == 0x19) {
uint64 acc = uint64(uint64(_rs) * uint64(_rt));
state.hi = uint32(acc >> 32);
state.lo = uint32(acc);
}
// div: Divides `rs` by `rt`.
// Stores the quotient in LO
// And the remainder in HI
else if (_func == 0x1a) {
state.hi = uint32(int32(_rs) % int32(_rt));
state.lo = uint32(int32(_rs) / int32(_rt));
}
// divu: Unsigned divides `rs` by `rt`.
// Stores the quotient in LO
// And the remainder in HI
else if (_func == 0x1b) {
state.hi = _rs % _rt;
state.lo = _rs / _rt;
}
// Store the result in the destination register, if applicable
if (_storeReg != 0) {
state.registers[_storeReg] = val;
}
// Update the PC
state.pc = state.nextPC;
state.nextPC = state.nextPC + 4;
// Return the hash of the resulting state
out_ = outputState();
}
/// @notice Handles a jump instruction, updating the MIPS state PC where needed.
/// @param _linkReg The register to store the link to the instruction after the delay slot instruction.
/// @param _dest The destination to jump to.
/// @return out_ The hashed MIPS state.
function handleJump(uint32 _linkReg, uint32 _dest) internal returns (bytes32 out_) {
// Load state from memory.
State memory state;
assembly {
state := 0x80
}
// Update the next PC to the jump destination.
uint32 prevPC = state.pc;
state.pc = state.nextPC;
state.nextPC = _dest;
// Update the link-register to the instruction after the delay slot instruction.
if (_linkReg != 0) {
state.registers[_linkReg] = prevPC + 8;
}
// Return the hash of the resulting state.
out_ = outputState();
}
/// @notice Handles a storing a value into a register.
/// @param _storeReg The register to store the value into.
/// @param _val The value to store.
/// @param _conditional Whether or not the store is conditional.
/// @return out_ The hashed MIPS state.
function handleRd(uint32 _storeReg, uint32 _val, bool _conditional) internal returns (bytes32 out_) {
// Load state from memory.
State memory state;
assembly {
state := 0x80
}
// The destination register must be valid.
require(_storeReg < 32, "valid register");
// Never write to reg 0, and it can be conditional (movz, movn).
if (_storeReg != 0 && _conditional) {
state.registers[_storeReg] = _val;
}
// Update the PC.
state.pc = state.nextPC;
state.nextPC = state.nextPC + 4;
// Return the hash of the resulting state.
out_ = outputState();
}
/// @notice Computes the offset of the proof in the calldata.
/// @param _proofIndex The index of the proof in the calldata.
/// @return offset_ The offset of the proof in the calldata.
function proofOffset(uint8 _proofIndex) internal pure returns (uint256 offset_) {
// A proof of 32 bit memory, with 32-byte leaf values, is (32-5)=27 bytes32 entries.
// And the leaf value itself needs to be encoded as well. And proof.offset == 358
offset_ = 358 + (uint256(_proofIndex) * (28 * 32));
uint256 s = 0;
assembly { s := calldatasize() }
require(s >= (offset_ + 28 * 32), "check that there is enough calldata");
return offset_;
}
/// @notice Reads a 32-bit value from memory.
/// @param _addr The address to read from.
/// @param _proofIndex The index of the proof in the calldata.
/// @return out_ The hashed MIPS state.
function readMem(uint32 _addr, uint8 _proofIndex) internal pure returns (uint32 out_) {
// Compute the offset of the proof in the calldata.
uint256 offset = proofOffset(_proofIndex);
assembly {
// Validate the address alignement.
if and(_addr, 3) {
revert(0, 0)
}
// Load the leaf value.
let leaf := calldataload(offset)
offset := add(offset, 32)
// Convenience function to hash two nodes together in scratch space.
function hashPair(a, b) -> h {
mstore(0, a)
mstore(32, b)
h := keccak256(0, 64)
}
// Start with the leaf node.
// Work back up by combining with siblings, to reconstruct the root.
let path := shr(5, _addr)
let node := leaf
for { let i := 0 } lt(i, 27) { i := add(i, 1) } {
let sibling := calldataload(offset)
offset := add(offset, 32)
switch and(shr(i, path), 1)
case 0 {
node := hashPair(node, sibling)
} case 1 {
node := hashPair(sibling, node)
}
}
// Load the memory root from the first field of state.
let memRoot := mload(0x80)
// Verify the root matches.
if iszero(eq(node, memRoot)) {
mstore(0, 0x0badf00d)
revert(0, 32)
}
// Bits to shift = (32 - 4 - (addr % 32)) * 8
let shamt := shl(3, sub(sub(32, 4), and(_addr, 31)))
out_ := and(shr(shamt, leaf), 0xFFffFFff)
}
}
/// @notice Writes a 32-bit value to memory.
/// This function first overwrites the part of the leaf.
/// Then it recomputes the memory merkle root.
/// @param _addr The address to write to.
/// @param _proofIndex The index of the proof in the calldata.
/// @param _val The value to write.
function writeMem(uint32 _addr, uint8 _proofIndex, uint32 _val) internal pure {
// Compute the offset of the proof in the calldata.
uint256 offset = proofOffset(_proofIndex);
assembly {
// Validate the address alignement.
if and(_addr, 3) {
revert(0, 0)
}
// Load the leaf value.
let leaf := calldataload(offset)
let shamt := shl(3, sub(sub(32, 4), and(_addr, 31)))
// Mask out 4 bytes, and OR in the value
leaf := or(and(leaf, not(shl(shamt, 0xFFffFFff))), shl(shamt, _val))
offset := add(offset, 32)
// Convenience function to hash two nodes together in scratch space.
function hashPair(a, b) -> h {
mstore(0, a)
mstore(32, b)
h := keccak256(0, 64)
}
// Start with the leaf node.
// Work back up by combining with siblings, to reconstruct the root.
let path := shr(5, _addr)
let node := leaf
for { let i := 0 } lt(i, 27) { i := add(i, 1) } {
let sibling := calldataload(offset)
offset := add(offset, 32)
switch and(shr(i, path), 1)
case 0 {
node := hashPair(node, sibling)
} case 1 {
node := hashPair(sibling, node)
}
}
// Store the new memory root in the first field of state.
mstore(0x80, node)
}
}
/// @notice Executes a single step of the vm.
/// Will revert if any required input state is missing.
function step(bytes calldata stateData, bytes calldata proof) public returns (bytes32) {
State memory state;
// Packed calldata is ~6 times smaller than state size
assembly {
if iszero(eq(state, 0x80)) { // expected state mem offset check
revert(0,0)
}
if iszero(eq(mload(0x40), mul(32, 48))) { // expected memory check
revert(0,0)
}
if iszero(eq(stateData.offset, 100)) { // 32*3+4=100 expected state data offset
revert(0,0)
}
if iszero(eq(proof.offset, 358)) { // 100+32+226=358 expected proof offset
revert(0,0)
}
function putField(callOffset, memOffset, size) -> callOffsetOut, memOffsetOut {
// calldata is packed, thus starting left-aligned, shift-right to pad and right-align
let w := shr(shl(3, sub(32, size)), calldataload(callOffset))
mstore(memOffset, w)
callOffsetOut := add(callOffset, size)
memOffsetOut := add(memOffset, 32)
}
// Unpack state from calldata into memory
let c := stateData.offset // calldata offset
let m := 0x80 // mem offset
c, m := putField(c, m, 32) // memRoot
c, m := putField(c, m, 32) // preimageKey
c, m := putField(c, m, 4) // preimageOffset
c, m := putField(c, m, 4) // pc
c, m := putField(c, m, 4) // nextPC
c, m := putField(c, m, 4) // lo
c, m := putField(c, m, 4) // hi
c, m := putField(c, m, 4) // heap
c, m := putField(c, m, 1) // exitCode
c, m := putField(c, m, 1) // exited
c, m := putField(c, m, 8) // step
// Unpack register calldata into memory
mstore(m, add(m, 32)) // offset to registers
m := add(m, 32)
for { let i := 0 } lt(i, 32) { i := add(i, 1) } {
c, m := putField(c, m, 4)
}
}
// Don't change state once exited
if (state.exited) {
return outputState();
}
state.step += 1;
// instruction fetch
uint32 insn = readMem(state.pc, 0);
uint32 opcode = insn >> 26; // 6-bits
// j-type j/jal
if (opcode == 2 || opcode == 3) {
// TODO(CLI-4136): likely bug in original code: MIPS spec says this should be in the "current" region;
// a 256 MB aligned region (i.e. use top 4 bits of branch delay slot (pc+4))
return handleJump(opcode == 2 ? 0 : 31, SE(insn & 0x03FFFFFF, 26) << 2);
}
// register fetch
uint32 rs; // source register 1 value
uint32 rt; // source register 2 / temp value
uint32 rtReg = (insn >> 16) & 0x1F;
// R-type or I-type (stores rt)
rs = state.registers[(insn >> 21) & 0x1F];
uint32 rdReg = rtReg;
if (opcode == 0 || opcode == 0x1c) {
// R-type (stores rd)
rt = state.registers[rtReg];
rdReg = (insn >> 11) & 0x1F;
} else if (opcode < 0x20) {
// rt is SignExtImm
// don't sign extend for andi, ori, xori
if (opcode == 0xC || opcode == 0xD || opcode == 0xe) {
// ZeroExtImm
rt = insn & 0xFFFF;
} else {
// SignExtImm
rt = SE(insn & 0xFFFF, 16);
}
} else if (opcode >= 0x28 || opcode == 0x22 || opcode == 0x26) {
// store rt value with store
rt = state.registers[rtReg];
// store actual rt with lwl and lwr
rdReg = rtReg;
}
if ((opcode >= 4 && opcode < 8) || opcode == 1) {
return handleBranch(opcode, insn, rtReg, rs);
}
uint32 storeAddr = 0xFF_FF_FF_FF;
// memory fetch (all I-type)
// we do the load for stores also
uint32 mem;
if (opcode >= 0x20) {
// M[R[rs]+SignExtImm]
rs += SE(insn&0xFFFF, 16);
uint32 addr = rs & 0xFFFFFFFC;
mem = readMem(addr, 1);
if (opcode >= 0x28 && opcode != 0x30) {
// store
storeAddr = addr;
// store opcodes don't write back to a register
rdReg = 0;
}
}
// ALU
uint32 val = execute(insn, rs, rt, mem) & 0xffFFffFF; // swr outputs more than 4 bytes without the mask
uint32 func = insn & 0x3f; // 6-bits
if (opcode == 0 && func >= 8 && func < 0x1c) {
if (func == 8 || func == 9) { // jr/jalr
return handleJump(func == 8 ? 0 : rdReg, rs);
}
if (func == 0xa) { // movz
return handleRd(rdReg, rs, rt == 0);
}
if (func == 0xb) { // movn
return handleRd(rdReg, rs, rt != 0);
}
// syscall (can read and write)
if (func == 0xC) {
return handleSyscall();
}
// lo and hi registers
// can write back
if (func >= 0x10 && func < 0x1c) {
return handleHiLo(func, rs, rt, rdReg);
}
}
// stupid sc, write a 1 to rt
if (opcode == 0x38 && rtReg != 0) {
state.registers[rtReg] = 1;
}
// write memory
if (storeAddr != 0xFF_FF_FF_FF) {
writeMem(storeAddr, 1, val);
}
// write back the value to destination register
return handleRd(rdReg, val, true);
}
/// @notice Execute an instruction.
function execute(uint32 insn, uint32 rs, uint32 rt, uint32 mem) internal pure returns (uint32) {
uint32 opcode = insn >> 26; // 6-bits
uint32 func = insn & 0x3f; // 6-bits
// TODO(CLI-4136): deref the immed into a register
if (opcode < 0x20) {
// transform ArithLogI
// TODO(CLI-4136): replace with table
if (opcode >= 8 && opcode < 0xF) {
if (opcode == 8) { func = 0x20; } // addi
else if (opcode == 9) { func = 0x21; } // addiu
else if (opcode == 0xa) { func = 0x2a; } // slti
else if (opcode == 0xb) { func = 0x2B; } // sltiu
else if (opcode == 0xc) { func = 0x24; } // andi
else if (opcode == 0xd) { func = 0x25; } // ori
else if (opcode == 0xe) { func = 0x26; } // xori
opcode = 0;
}
// 0 is opcode SPECIAL
if (opcode == 0) {
uint32 shamt = (insn >> 6) & 0x1f;
if (func < 0x20) {
// jr/jalr/div + others
if (func >= 0x08) {
return rs;
}
// sll: Logical Shift Left
else if (func == 0x00) {
return rt << shamt;
}
// srl: Logical Shift Right
else if (func == 0x02) {
return rt >> shamt;
}
// sra: Arithmetic Shift Right
else if (func == 0x03) {
return SE(rt >> shamt, 32 - shamt);
}
// sllv: Variable Logical Shift Left
else if (func == 0x04) {
return rt << (rs & 0x1F);
}
// srlv: Variable Logical Shift Right
else if (func == 0x06) {
return rt >> (rs & 0x1F);
}
// srav: Variable Arithmetic Shift Right
else if (func == 0x07) {
return SE(rt >> rs, 32 - rs);
}
}
// R-type (ArithLog)
// 0x10-0x13 = mfhi, mthi, mflo, mtlo
// add or addu
if (func == 0x20 || func == 0x21) {
return rs + rt;
}
// sub or subu
else if (func == 0x22 || func == 0x23) {
return rs - rt;
}
// and
else if (func == 0x24) {
return rs & rt;
}
// or
else if (func == 0x25) {
return (rs | rt);
}
// xor
else if (func == 0x26) {
return (rs ^ rt);
}
// nor
else if (func == 0x27) {
return ~(rs | rt);
}
// slt: Set to 1 if less than
else if (func == 0x2a) {
return int32(rs) < int32(rt) ? 1 : 0;
}
// sltu: Set to 1 if less than unsigned
else if (func == 0x2B) {
return rs<rt ? 1 : 0;
}
}
// lui: Load Upper Immediate
else if (opcode == 0xf) {
return rt << 16;
}
// SPECIAL2
else if (opcode == 0x1c) {
// mul
if (func == 2) {
return uint32(int32(rs) * int32(rt));
}
// clo
if (func == 0x20 || func == 0x21) {
if (func == 0x20) {
rs = ~rs;
}
uint32 i = 0;
while (rs&0x80000000 != 0) {
i++;
rs <<= 1;
}
return i;
}
}
}
else if (opcode < 0x28) {
// lb
if (opcode == 0x20) {
return SE((mem >> (24 - (rs & 3) * 8)) & 0xFF, 8);
}
// lh
else if (opcode == 0x21) {
return SE((mem >> (16 - (rs & 2) * 8)) & 0xFFFF, 16);
}
// lwl
else if (opcode == 0x22) {
uint32 val = mem << ((rs & 3) * 8);
uint32 mask = uint32(0xFFFFFFFF) << ((rs & 3) * 8);
return (rt & ~mask) | val;
}
// lw
else if (opcode == 0x23) {
return mem;
}
// lbu
else if (opcode == 0x24) {
return (mem >> (24 - (rs & 3) * 8)) & 0xFF;
}
// lhu
else if (opcode == 0x25) {
return (mem >> (16 - (rs & 2) * 8)) & 0xFFFF;
}
// lwr
else if (opcode == 0x26) {
uint32 val = mem >> (24 - (rs & 3) * 8);
uint32 mask = uint32(0xFFFFFFFF) >> (24 - (rs & 3) * 8);
return (rt & ~mask) | val;
}
}
// sb
else if (opcode == 0x28) {
uint32 val = (rt & 0xFF) << (24 - (rs & 3) * 8);
uint32 mask = 0xFFFFFFFF ^ uint32(0xFF << (24 - (rs & 3) * 8));
return (mem & mask) | val;
}
// sh
else if (opcode == 0x29) {
uint32 val = (rt & 0xFFFF) << (16 - (rs & 2) * 8);
uint32 mask = 0xFFFFFFFF ^ uint32(0xFFFF << (16 - (rs & 2) * 8));
return (mem & mask) | val;
}
// swl
else if (opcode == 0x2a) {
uint32 val = rt >> ((rs & 3) * 8);
uint32 mask = uint32(0xFFFFFFFF) >> ((rs & 3) * 8);
return (mem & ~mask) | val;
}
// sw
else if (opcode == 0x2b) {
return rt;
}
// swr
else if (opcode == 0x2e) {
uint32 val = rt << (24 - (rs & 3) * 8);
uint32 mask = uint32(0xFFFFFFFF) << (24 - (rs & 3) * 8);
return (mem & ~mask) | val;
}
// ll
else if (opcode == 0x30) {
return mem;
}
// sc
else if (opcode == 0x38) {
return rt;
}
revert("invalid instruction");
}
}