1
//! ```
2
//!                                Sacred Geometry
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
//! ## Memory Layout
31
//!
32
//! | index  | value             |
33
//! | ------ | ----------------- |
34
//! | 0x0000 | op_halt_dest      |
35
//! | 0x0020 | op_add_dest       |
36
//! | 0x0040 | op_sub_dest       |
37
//! | 0x0060 | op_mul_dest       |
38
//! | 0x0080 | op_div_dest       |
39
//! | 0x00a0 | op_swap1_dest     |
40
//! | 0x00c0 | op_swap2_dest     |
41
//! | 0x00e0 | op_swap3_dest     |
42
//! | 0x0100 | op_swap4_dest     |
43
//! | 0x0120 | op_swap5_dest     |
44
//! | 0x0140 | op_swap6_dest     |
45
//! | 0x0160 | op_swap7_dest     |
46
//! | 0x0180 | program_counter   |
47
//! | 0x01a0 | executable        |
48
//! | 0x01c0 | virtual_stack_ptr |
49
//!
50
//! ## Instruction Set
51
//!
52
//! | opcode | byte |
53
//! | ------ | ---- |
54
//! | HALT   | 0x00 |
55
//! | ADD    | 0x01 |
56
//! | SUB    | 0x02 |
57
//! | MUL    | 0x03 |
58
//! | DIV    | 0x04 |
59
//! | SWAP1  | 0x05 |
60
//! | SWAP2  | 0x06 |
61
//! | SWAP3  | 0x07 |
62
//! | SWAP4  | 0x08 |
63
//! | SWAP5  | 0x09 |
64
//! | SWAP6  | 0x0a |
65
//! | SWAP7  | 0x0b |
66

67
// --- Application Binary Interface ---
68

69
#define function name() pure returns (string)
70
#define function generate(address) pure returns (uint256)
71
#define function verify(uint256,uint256) pure returns (bool)
72

73
// --- Constants ---
74

75
#define constant NAME_STR = 0x0f5361637265642047656f6d65747279
76
#define constant MAX_VALUE = 0x06
77
#define constant VIRTUAL_STACK_PTR = 0x07
78
#define constant OPCODE_MOD = 0x0c
79

80
#define constant PC_PTR = 0x0180
81
#define constant EXECUTABLE_PTR = 0x01a0
82
#define constant VIRTUAL_STACK_PTR_PTR = 0x01c0
83

84
#define constant ARG0_CD_PTR = 0x04
85
#define constant ARG1_CD_PTR = 0x24
86

87
#define constant PRIME_0 = 0x0d
88
#define constant PRIME_1 = 0x11
89
#define constant PRIME_2 = 0x13
90

91
#define constant INPUT_0 = 0x1f
92
#define constant INPUT_1 = 0x1e
93
#define constant INPUT_2 = 0x1d
94
#define constant INPUT_3 = 0x1c
95
#define constant INPUT_4 = 0x1b
96
#define constant INPUT_5 = 0x1a
97
#define constant INPUT_6 = 0x19
98
#define constant INPUT_7 = 0x18
99

100
// --- Macros ---
101

102
/// ## Entry Point
103
///
104
/// ### Directives
105
///
106
/// 1. Dispatch function by selector.
107
/// 2. Revert if selector is not matched.
108
///
109
/// ### Panics
110
///
111
/// - When selector is not matched.
112
/// - When `VERIFY` panics.
113
#define macro MAIN() = takes (0) returns (0) {
114
    0x00 calldataload 0xe0 shr
115
    dup1 __FUNC_SIG(name) eq is_name jumpi
116
    dup1 __FUNC_SIG(generate) eq is_generate jumpi
117
    dup1 __FUNC_SIG(verify) eq is_verify jumpi
118
    0x00 0x00 revert
119

120
    is_name:
121
        NAME()
122
    is_generate:
123
        GENERATE()
124
    is_verify:
125
        VERIFY()
126
}
127

128
/// ## Return Name
129
///
130
/// ### Directives
131
///
132
/// 1. Store name in memory.
133
/// 2. Return from memory.
134
#define macro NAME() = takes (0) returns (0) {
135
    0x20                        // [ptr]
136
    0x00                        // [mem_ptr, ptr]
137
    mstore                      // []
138
    [NAME_STR]                  // [name]
139
    0x2f                        // [mem_ptr, name]
140
    mstore                      // []
141
    0x60                        // [mem_len]
142
    0x00                        // [mem_ptr, mem_len]
143
    return                      // []
144
}
145

146
/// ## Generate Random Number
147
///
148
/// ### Directives
149
///
150
/// 1. Load seed from calldata.
151
/// 2. Generate 8 bytes with `GEN_BYTE`.
152
/// 3. Return the bytes, left padded in a single uint256.
153
#define macro GENERATE() = takes (0) returns (0) {
154
    0x04                        // [seed_cd_ptr]
155
    calldataload                // [seed]
156
    GEN_BYTE(INPUT_0)           // [seed]
157
    GEN_BYTE(INPUT_1)           // [seed]
158
    GEN_BYTE(INPUT_2)           // [seed]
159
    GEN_BYTE(INPUT_3)           // [seed]
160
    GEN_BYTE(INPUT_4)           // [seed]
161
    GEN_BYTE(INPUT_5)           // [seed]
162
    GEN_BYTE(INPUT_6)           // [seed]
163
    GEN_BYTE(INPUT_7)           // [seed]
164
    0x20                        // [mem_len, seed]
165
    0x00                        // [mem_ptr, mem_len, seed]
166
    return                      // []
167
}  
168
  
169
/// ## Verify Solution
170
///  
171
/// ### Directives
172
///
173
/// 1. Initialize the VM with `INITIALIZE_VM`.
174
/// 2. Start execution loop.
175
/// 3. Get current opcode with `GET_OPCODE`.
176
/// 4. Increment program counter with `INCREMENT_PC`.
177
/// 5. Dispatch opcode with `DISPATCH_OPCODE`.
178
/// 6. Based on opcode, perform operation.
179
/// 7. If the opcode is not HALT, jump to exec_start, continue at step 3.
180
/// 8. If the opcode is HALT, check the output with `CHECK_OUTPUT`.
181
/// 9. If the output is correct, return true, else return false.
182
///
183
/// ### Panics
184
///
185
/// - When the stack underflows.
186
#define macro VERIFY() = takes (0) returns (0) {
187
    INITIALIZE_VM()             // [input_0, input_1, input_2, input_3, input_4, input_5, input_6, input_7]
188

189
    exec_start:                 // [..inputs]
190
        GET_OPCODE()            // [opcode, ..inputs]
191
        INCREMENT_PC()          // [opcode, ..inputs]
192
        DISPATCH_OPCODE()       // []
193

194
    op_add:                     // [a, b, ..inputs]
195
        DEC_VIRTUAL_STACK_PTR() // [a, b, ..inputs]
196
        add                     // [sum, ..inputs]
197
        exec_start jump         // [sum, ..inputs]
198

199
    op_sub:                     // [a, b, ..inputs]
200
        DEC_VIRTUAL_STACK_PTR() // [a, b, ..inputs]
201
        sub                     // [difference, ..inputs]
202
        exec_start jump         // [difference, ..inputs]
203

204
    op_mul:                     // [a, b, ..inputs]
205
        DEC_VIRTUAL_STACK_PTR() // [a, b, ..inputs]
206
        mul                     // [prod, ..inputs]
207
        exec_start jump         // [prod, ..inputs]
208

209
    op_div:                     // [a, b, ..inputs]
210
        DEC_VIRTUAL_STACK_PTR() // [a, b, ..inputs]
211
        div                     // [quotient, ..inputs]
212
        exec_start jump         // [quotient, ..inputs]
213

214
    op_swap1:                   // [a, b, ..inputs]
215
        swap1                   // [b, a, ..inputs]
216
        exec_start jump         // [b, a, ..inputs]
217

218
    op_swap2:                   // [a, _, b, ..inputs]
219
        swap2                   // [b, _, a, ..inputs]
220
        exec_start jump         // [b, _, a, ..inputs]
221

222
    op_swap3:                   // [a, _, _, b, ..inputs]
223
        swap3                   // [b, _, _, a, ..inputs]
224
        exec_start jump         // [b, _, _, a, ..inputs]
225

226
    op_swap4:                   // [a, _, _, _, b, ..inputs]
227
        swap4                   // [b, _, _, _, a, ..inputs]
228
        exec_start jump         // [b, _, _, _, a, ..inputs]
229

230
    op_swap5:                   // [a, _, _, _, _, b, ..inputs]
231
        swap5                   // [b, _, _, _, _, a, ..inputs]
232
        exec_start jump         // [b, _, _, _, _, a, ..inputs]
233

234
    op_swap6:                   // [a, _, _, _, _, _, b, ..inputs]
235
        swap6                   // [b, _, _, _, _, _, a, ..inputs]
236
        exec_start jump         // [b, _, _, _, _, _, a, ..inputs]
237

238
    op_swap7:                   // [a, _, _, _, _, _, _, b]
239
        swap7                   // [b, _, _, _, _, _, _, a]
240
        exec_start jump         // [b, _, _, _, _, _, _, a]
241

242
    op_halt:                    // [result]
243
        CHECK_OUTPUT()          // [is_valid_prime]
244
        0x00                    // [mem_ptr, is_valid_prime]
245
        mstore                  // []
246
        0x20                    // [mem_len]
247
        0x00                    // [mem_ptr, mem_len]
248
        return                  // []
249
}
250

251
// --- Virtual Machine Operations ---
252

253
/// ## Initialize VM
254
///
255
/// > Note: The program counter (`memory[0x0180]`) is implicitly initialized to 0.
256
///
257
/// ### Directives
258
///
259
/// 1. Store the opcode jumptable in memory.
260
/// 2. Write the executable to memory.
261
/// 3. Write the virtual stack depth to memory.
262
/// 4. Read the program input from calldata.
263
/// 5. Get and push each random number to the stack with `PUSH_NUMBER`.
264
#define macro INITIALIZE_VM() = takes (0) returns (1) {
265
    __tablesize(OPCODE_TABLE)   // [opcode_table_len]
266
    __tablestart(OPCODE_TABLE)  // [opcode_table_ptr, opcode_table_len]
267
    0x00                        // [mem_ptr, opcode_table_ptr, opcode_table_len]
268
    codecopy                    // []
269

270
    [ARG1_CD_PTR]               // [executable_cd_ptr]
271
    calldataload                // [executable]
272
    [EXECUTABLE_PTR]            // [mem_ptr, executable]
273
    mstore                      // []
274

275
    [VIRTUAL_STACK_PTR]         // [virtual_stack_depth]
276
    [VIRTUAL_STACK_PTR_PTR]     // [virtual_stack_ptr_ptr, virtual_stack_depth]
277
    mstore                      // []
278

279
    [ARG0_CD_PTR]               // [program_input_cd_ptr]
280
    calldataload                // [program_input]
281
    PUSH_NUMBER(INPUT_7)        // [program_input, input_7]
282
    PUSH_NUMBER(INPUT_6)        // [program_input, input_6, input_7]
283
    PUSH_NUMBER(INPUT_5)        // [program_input, input_5, input_6, input_7]
284
    PUSH_NUMBER(INPUT_4)        // [program_input, input_4, input_5, input_6, input_7]
285
    PUSH_NUMBER(INPUT_3)        // [program_input, input_3, input_4, input_5, input_6, input_7]
286
    PUSH_NUMBER(INPUT_2)        // [program_input, input_2, input_3, input_4, input_5, input_6, input_7]
287
    PUSH_NUMBER(INPUT_1)        // [program_input, input_1, input_2, input_3, input_4, input_5, input_6, input_7]
288
    PUSH_NUMBER(INPUT_0)        // [program_input, input_0, input_1, input_2, input_3, input_4, input_5, input_6, input_7]
289
    pop                         // [input_0, input_1, input_2, input_3, input_4, input_5, input_6, input_7]
290
}
291

292
/// ## Get Opcode
293
///
294
/// ### Directives
295
///
296
/// 1. Read the program counter from memory.
297
/// 2. Add the executable offer to the program counter.
298
/// 3. Read the opcode from memory.
299
/// 4. Shift the opcode to the right by 248 bits.
300
/// 5. Mask the opcode with seven.
301
#define macro GET_OPCODE() = takes (0) returns (1) {
302
    [PC_PTR]                    // [program_counter_ptr]
303
    mload                       // [program_counter]
304
    [EXECUTABLE_PTR]            // [executable_start, program_counter]
305
    add                         // [opcode_ptr]
306
    mload                       // [opcode_word]
307
    0xf8                        // [shift, opcode_word]
308
    shr                         // [opcode]
309
    [OPCODE_MOD]                // [opcode_mod, opcode]
310
    swap1                       // [opcode, opcode_mod]
311
    mod                         // [valid_opcode]
312
}
313

314
/// ## Increment Program Counter
315
///
316
/// ### Directives
317
///
318
/// 1. Read the program counter from memory.
319
/// 2. Add one to the program counter.
320
/// 3. Write the new program counter to memory.
321
#define macro INCREMENT_PC() = takes (0) returns (0) {
322
    [PC_PTR]                    // [program_counter_ptr, opcode]
323
    dup1                        // [program_counter_ptr, program_counter_ptr, opcode]
324
    mload                       // [program_counter, program_counter_ptr, opcode]
325
    0x01                        // [one, program_counter, program_counter_ptr, opcode]
326
    add                         // [new_program_counter, program_counter_ptr, opcode]
327
    swap1                       // [program_counter_ptr, new_program_counter, opcode]
328
    mstore                      // [opcode]
329
}
330

331
/// ## Dispatch Opcode
332
///
333
/// ### Directives
334
///
335
/// 1. Shift the opcode to the left by five bits.
336
/// 2. Read the opcode from the jumptable in memory.
337
#define macro DISPATCH_OPCODE() = takes (1) returns (0) {
338
    0x05                        // [shift, opcode]
339
    shl                         // [op_dispatch_ptr]
340
    mload                       // [op_dispatch_dest]
341
    jump                        // []
342
}
343

344
/// ## Decrement Virtual Stack Pointer
345
///
346
/// ### Directives
347
///
348
/// 1. Read the virtual stack pointer from memory.
349
/// 2. Subtract one from the virtual stack pointer.
350
/// 3. Write the new virtual stack pointer to memory.
351
#define macro DEC_VIRTUAL_STACK_PTR() = takes (0) returns (0) {
352
    [VIRTUAL_STACK_PTR_PTR]     // [virtual_stack_ptr_ptr]
353
    0x01                        // [one, virtual_stack_ptr_ptr]
354
    dup2                        // [virtual_stack_ptr_ptr, one, virtual_stack_ptr_ptr]
355
    mload                       // [virtual_stack_ptr, one, virtual_stack_ptr_ptr]
356
    sub                         // [new_virtual_stack_ptr, virtual_stack_ptr_ptr]
357
    swap1                       // [virtual_stack_ptr_ptr, new_virtual_stack_ptr]
358
    mstore                      // []
359
}
360

361
/// ## Check the Program Output
362
///
363
/// ### Directives
364
///
365
/// 1. Checks if the result is equal to prime 0.
366
/// 2. Checks if the result is equal to prime 1.
367
/// 3. Checks if the result is equal to prime 2.
368
/// 4. Accumulates the result of the three checks.
369
/// 5. Checks if the stack is empty.
370
/// 6. Accumulates the result of the two checks.
371
#define macro CHECK_OUTPUT() = takes (1) returns (1) {
372
    // takes:                   // [result]
373
    dup1 dup1                   // [result, result, result]
374
    [PRIME_0]                   // [prime_0, result, result, result]
375
    eq                          // [is_prime_0, result, result]
376

377
    swap1                       // [result, is_prime_0, result]
378
    [PRIME_1]                   // [prime_1, result, is_prime_0, result]
379
    eq                          // [is_prime_1, is_prime_0, result]
380

381
    swap2                       // [result, is_prime_1, is_prime_0]
382
    [PRIME_2]                   // [prime_2, result, is_prime_1, is_prime_0]
383
    eq                          // [is_prime_2, is_prime_1, is_prime_0]
384

385
    or or                       // [is_valid_prime]
386

387
    [VIRTUAL_STACK_PTR_PTR]     // [virtual_stack_ptr_ptr, is_valid_prime]
388
    mload                       // [virtual_stack_ptr, is_valid_prime]
389
    iszero                      // [is_stack_empty, is_valid_prime]
390
    and                         // [is_valid_output]
391
}
392

393
// --- Utilities ---
394

395
/// ## Generate Byte of Pseudorandom Number
396
///
397
/// ### Directives
398
///
399
/// 1. Extract a byte from the `seed` index `idx`.
400
/// 2. Modulo the byte by the `MAX_VALUE`.
401
/// 3. Add one to the result.
402
/// 4. Store the result in memory.
403
#define macro GEN_BYTE(idx) = takes (1) returns (1) {
404
    // takes:                   // [seed]
405
    [MAX_VALUE]                 // [mod, seed]
406
    dup2                        // [seed, mod, seed]
407
    <idx>                       // [idx, seed, mod, seed]
408
    byte                        // [byte, mod, seed]
409
    mod                         // [rand, seed]
410
    0x01                        // [one, rand, seed]
411
    add                         // [rand, seed]
412
    <idx>                       // [idx, rand, seed]
413
    mstore8                     // [seed]
414
}
415

416
/// ## Push Pseudorandom Number to Stack
417
///
418
/// ### Directives
419
///
420
/// 1. Extract a byte from the `program_input` index `idx`.
421
#define macro PUSH_NUMBER(idx) = takes (1) returns (2) {
422
    // takes:                   // [program_input]
423
    dup1                        // [program_input, program_input]
424
    <idx>                       // [idx, program_input, program_input]
425
    byte                        // [byte, program_input]
426
    swap1                       // [program_input, byte]
427
}
428

429
// --- Jumptable ---
430

431
/// ## Opcode Jumptable
432
///
433
/// Maps opcodes to jumptable indices in memory.
434
#define jumptable OPCODE_TABLE {
435
    op_halt                     // 0x0000
436
    op_add                      // 0x0020
437
    op_sub                      // 0x0040
438
    op_mul                      // 0x0060
439
    op_div                      // 0x0080
440
    op_swap1                    // 0x00a0
441
    op_swap2                    // 0x00c0
442
    op_swap3                    // 0x00e0
443
    op_swap4                    // 0x0100
444
    op_swap5                    // 0x0120
445
    op_swap6                    // 0x0140
446
    op_swap7                    // 0x0160
447
}