This is the second version of the task. The original task had a defect that the given range of integers was too small. This was pointed out by @harold that other methods couldn't defeat the way of hard-coding all the possible prime divisors. Now you have a larger range of integers to test from 0 to 2000000. Also, the result of your program must be sane for all possible input.
Multiplication now stores the overflowed bits in the r0 register. You can name labels with minimum restriction, and the added dbg instruction dumps the value of all registers.
Write a program in assembly that will find out whether the input is a prime number. The program will run through mjvm which has a simple set of instructions and a determined number of clock cycles for each instruction. The input will be from 0 to 2000000 inclusive, and the objective is to write the most optimized program spending the least number of clock cycles to determine the primality of all inputs.
This is an example program doing a primality test in mjvm assembly.
. ind r1 . ; r1 = input ; originally meant input as decimal
. lti r1 2 ; r0 = r1 < 2 ; test less than immediate
. cjmp false . ; if (r0) goto false
. eqi r1 2 ; r0 = r1 == 2
. cjmp true . ; if (r0) goto true
. mv r2 r1 ; r2 = r1
. andi r2 1 ; r2 &= 1
. eqi r2 0 ; r0 = r2 == 0
. cjmp false . ; if (r0) goto false
. mvi r3 3 ; r3 = 3
loop mv r2 r3 ; r2 = r3
. mul r2 r2 ; r2 *= r2
. gt r2 r1 ; r0 = r2 > r1
. cjmp true . ; if (r0) goto true
. mv r2 r1 ; r2 = r1
. div r2 r3 ; r2 /= r3, r0 = r2 % r3
. lnot r0 . ; r0 = !r0 ; logical not
. cjmp false . ; if (r0) goto false
. addi r3 2 ; r3 += 2
. jmp loop . ; goto loop
true mvi r1 0xffffffff ; r1 = -1
. outd r1 . ; print r1 as decimal
. end . . ; end program
false mvi r1 0
. outd r1 .
. end . .
For input from 0 to 2000000, this program consumes total 4043390047 cycles. While some obvious optimizations have been done, there is still a lot of room for improvement.
Now if you're interested, this is the whole list of instructions. Each instruction takes a fixed number of arguments, which can either be a register, an immediate (constant), or a label (address). The type of the argument is also fixed; r means register, i means immediate, and L means label. An instruction with an i suffix takes an immediate as the third argument while the same instruction without an i takes a register as the third argument. Also, I'll explain later, but r0 is a special register.
end - end program
dbg - dumps the value of all registers and pause the program
ind r - read the input in decimal digits and store the value in `r`
outd r - output the value in `r` as decimal digits
not r - bitwise not; set `r` to `~r` (all bits reversed)
lnot r - logical not; if `r` is 0, set `r` to ~0 (all bits on); otherwise, set `r` to 0
jmp L - jump to `L`
cjmp L - if `r0` is non-zero, jump to L
mv(i) r1 r2(i) - copy `r2(i)` to `r1`
cmv(i) r1 r2(i) - if `r0` is non-zero, copy `r2(i)` to `r1`
eq(i) r1 r2(i) - if `r1` equals `r2(i)`, set `r0` to ~0; otherwise set `r0` to 0
neq(i), lt(i), le(i), gt(i), ge(i) - analogus to eq(i)
and(i) r1 r2(i) - set `r1` to `r1 & r2(i)`; bitwise `and`
or(i), xor(i) - analogus to and(i)
shl(i), shr(i) - shift left and shift right; analogus to and(i);
add(i), sub(i) - analogus to and(i)
mul(i) r1 r2(i) - from the result of `r1 * r2(i)`, the high bits are stored in `r0`
and the low bits are stored in `r1`;
if the first argument is `r0`, the low bits are stored in `r0`;
the high bits are 0 when there is no overflow
div(i) r1 r2(i) - set `r0` to `r1 % r2(i)` and set `r1` to `r1 / r2(i)`;
if the first argument is `r0`, `r0` is `r1 / r2(i)`
As you can see, the result of comparison instructions and the remainder part of division is stored in r0. The value is also used to perform a conditional jump or move.
These instructions consume 2 clock cycles.
cjmp, cmv(i), mul(i)
These instructions consume 32 clock cycles.
div(i)
These instructions consume 10 clock cycles.
ind, outd
dbg does not consume any clock cycle.
All other instructions, including end consume 1 clock cycle.
When the program starts, a cycle is consumed per each instruction of the whole program. That means, for example, if your program has 15 instructions in total, initially 15 cycles will be counted.
There are 16 registers from r0 to rf each holding a 32-bit unsigned integer. The number after r is hexadecimal. The initial value of all registers is 0. There is no memory other than the registers.
The result of an operation after an overflow is guaranteed to be result % pow(2, 32). This also applies to an immediate value outside the range of unsigned 32-bits. Division by zero is undefined, but most likely you'll get a hardware interrupt.
Labels can be any sequence of characters except whitespaces and .. The maximum length of each label is 15 characters, and there can be total 256 labels in a single program.
An immediate operand can be hexadecimal starting with 0x or 0X, or octal starting with 0.
You start the program by reading an input with ind. The input will be automatically given by the VM. You end the program by a sequence of outd and end. The VM will determine whether your final output is correct.
If the input is not prime, the output shall be 0. If the input is prime, the output shall be ~0. 0 and 1 are not prime numbers. All the comparison instructions result as ~0 for a true value, and you can often use this for efficient bitwise logic.
In the assembly code file, each line should start with 4 instructions divided by one or more whitespaces, and . is used as a placeholder. Everything else in the line is ignored and thus can be used as comments.
The current implementation of the VM may have bugs, you can report any faulty code in the comments. An alternative implementation is also welcomed. I will post here if there is any.
This is the code of the VM to measure your program's correctness and efficiency. You can compile with any C compiler, and the program will interpret your assembly file given as the first argument.
#include <stdint.h>
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
static uint32_t prime(uint32_t n) {
if (n < 2) return 0;
if (n == 2) return -1;
if (!(n % 2)) return 0;
for (int d = 3; d * d <= n; d += 2) {
if (!(n % d)) return 0;
}
return -1;
}
enum {
NOP, DBG, END,
IND, OUTD,
NOT, LNOT,
JMP, CJMP,
MV, CMV,
EQ, NEQ, LT, LE, GT, GE,
AND, OR, XOR, SHL, SHR,
ADD, SUB, MUL, DIV,
MVI, CMVI,
EQI, NEQI, LTI, LEI, GTI, GEI,
ANDI, ORI, XORI, SHLI, SHRI,
ADDI, SUBI, MULI, DIVI,
};
_Noreturn static void verr_(const char *m, va_list a) {
vprintf(m, a);
putchar('\n');
exit(1);
}
_Noreturn static void err(const char *m, ...) {
va_list a;
va_start(a, m);
verr_(m, a);
}
static void chk(int ok, const char *m, ...) {
if (!ok) {
va_list a;
va_start(a, m);
verr_(m, a);
}
}
#define LBL_DIC_CAP 0x100
typedef struct {
struct {
char id[0x10];
int i;
} _[LBL_DIC_CAP];
int n;
} lblDic_t;
static void lblDic_init(lblDic_t *_) {
_->n = 0;
}
static void lblDic_add(lblDic_t *_, const char *id, int i) {
chk(_->n < LBL_DIC_CAP, "too many labels");
strcpy(_->_[_->n].id, id);
_->_[_->n++].i = i;
}
static int cmp_(const void *a, const void *b) {
return strcmp(a, b);
}
static void lblDic_sort(lblDic_t *_) {
qsort(_, _->n, sizeof(*_->_), cmp_);
}
static int lblDic_search(lblDic_t *_, const char *id) {
int o = &_->_->i - (int *)_;
int *p = bsearch(id, _, _->n, sizeof(*_->_), cmp_);
if (!p) return -1;
return p[o];
}
static int ins(const char *s) {
if (!strcmp(s, "dbg")) return DBG;
if (!strcmp(s, "end")) return END;
if (!strcmp(s, "ind")) return IND;
if (!strcmp(s, "outd")) return OUTD;
if (!strcmp(s, "not")) return NOT;
if (!strcmp(s, "lnot")) return LNOT;
if (!strcmp(s, "jmp")) return JMP;
if (!strcmp(s, "cjmp")) return CJMP;
if (!strcmp(s, "mv")) return MV;
if (!strcmp(s, "cmv")) return CMV;
if (!strcmp(s, "eq")) return EQ;
if (!strcmp(s, "neq")) return NEQ;
if (!strcmp(s, "lt")) return LT;
if (!strcmp(s, "le")) return LE;
if (!strcmp(s, "gt")) return GT;
if (!strcmp(s, "ge")) return GE;
if (!strcmp(s, "and")) return AND;
if (!strcmp(s, "or")) return OR;
if (!strcmp(s, "xor")) return XOR;
if (!strcmp(s, "shl")) return SHL;
if (!strcmp(s, "shr")) return SHR;
if (!strcmp(s, "add")) return ADD;
if (!strcmp(s, "sub")) return SUB;
if (!strcmp(s, "mul")) return MUL;
if (!strcmp(s, "div")) return DIV;
if (!strcmp(s, "mvi")) return MVI;
if (!strcmp(s, "cmvi")) return CMVI;
if (!strcmp(s, "eqi")) return EQI;
if (!strcmp(s, "neqi")) return NEQI;
if (!strcmp(s, "lti")) return LTI;
if (!strcmp(s, "lei")) return LEI;
if (!strcmp(s, "gti")) return GTI;
if (!strcmp(s, "gei")) return GEI;
if (!strcmp(s, "andi")) return ANDI;
if (!strcmp(s, "ori")) return ORI;
if (!strcmp(s, "xori")) return XORI;
if (!strcmp(s, "shli")) return SHLI;
if (!strcmp(s, "shri")) return SHRI;
if (!strcmp(s, "addi")) return ADDI;
if (!strcmp(s, "subi")) return SUBI;
if (!strcmp(s, "muli")) return MULI;
if (!strcmp(s, "divi")) return DIVI;
err("invalid instruction: %s", s);
}
static int reg(const char *s) {
chk(*s == 'r', "invalid register: %s", s);
if ('0' <= s[1] && s[1] <= '9') return s[1] - '0';
if ('a' <= s[1] && s[1] <= 'f') return s[1] - 'a' + 10;
err("invalid register: %s", s);
}
int main(int argc, char **argv) {
chk(argc == 2, "must have 1 argument");
int sz;
uint32_t p[0x10000][3];
uint32_t r[0x10];
lblDic_t l;
lblDic_init(&l);
FILE *f = fopen(argv[1], "r");
chk((int)f, "failed to open file: %s", argv[1]);
for (int i = 0;; ++i) {
char s[0x100];
int m = fscanf(f, "%s", s);
if (m < 0) break;
chk(strlen(s) < 0x10, "%s is too long", s);
if (*s != '.') {
if (lblDic_search(&l, s) < 0) {
lblDic_add(&l, s, i);
lblDic_sort(&l);
}
}
int c;
while ((c = getc(f)) != '\n' && m > 0);
}
rewind(f);
char s[4][0x10];
for (int i = 0;; ++i) {
int m = fscanf(f, "%s %s %s %s", *s, s[1], s[2], s[3]);
if (m < 0) {
sz = i;
break;
}
chk(m == 4, "parse error at line %d", i + 1);
*p[i] = ins(s[1]);
if (*p[i] <= END) {
p[i][1] = NOP;
} else if (*p[i] == JMP || *p[i] == CJMP) {
p[i][1] = lblDic_search(&l, s[2]);
chk(p[i][1] != -1u, "unknown label: %s", s[2]);
} else {
p[i][1] = reg(s[2]);
}
if (*p[i] <= CJMP) {
p[i][2] = NOP;
} else if (*p[i] >= MVI) {
p[i][2] = strtoul(s[3], NULL, 0);
} else {
p[i][2] = reg(s[3]);
}
while ((m = getc(f)) != '\n' && m > 0);
}
chk(!fclose(f), "sth's very twisted with your system");
for (int i = 0; i < l.n; ++i) {
printf("%16s%6d\n", l._[i].id, l._[i].i);
}
for (int i = 0; i < sz; ++i) {
printf("%6d%4u%4u %u\n", i, *p[i], p[i][1], p[i][2]);
}
long long c = 0;
for (int n = 0; n <= 2000000; ++n) {
memset(r, 0, sizeof(r));
uint32_t o = 1;
c += sz;
for (uint32_t *i = *p; i < p[sz]; i += 3) {
start:
switch(*i) {
case DBG: {
for (int i = 0; i < 010; ++i) {
printf("r%x%11u r%x%11u\n", i, r[i], i + 010, r[i + 010]);
}
fputs("press ENTER to continue", stdout);
getchar();
break;
}
case END: ++c; goto end;
case IND: c += 10; r[i[1]] = n; break;
case OUTD: c += 10; o = r[i[1]]; break;
case NOT: ++c; r[i[1]] = ~r[i[1]]; break;
case LNOT: ++c; r[i[1]] = r[i[1]] ? 0 : -1; break;
case JMP: ++c; i = p[i[1]]; goto start;
case CJMP: c += 2; if (*r) {i = p[i[1]]; goto start;} break;
case MV: ++c; r[i[1]] = r[i[2]]; break;
case CMV: c += 2; if (*r) r[i[1]] = r[i[2]]; break;
case EQ: ++c; *r = r[i[1]] == r[i[2]] ? -1 : 0; break;
case NEQ: ++c; *r = r[i[1]] != r[i[2]] ? -1 : 0; break;
case LT: ++c; *r = r[i[1]] < r[i[2]] ? -1 : 0; break;
case LE: ++c; *r = r[i[1]] <= r[i[2]] ? -1 : 0; break;
case GT: ++c; *r = r[i[1]] > r[i[2]] ? -1 : 0; break;
case GE: ++c; *r = r[i[1]] >= r[i[2]] ? -1 : 0; break;
case AND: ++c; r[i[1]] &= r[i[2]]; break;
case OR: ++c; r[i[1]] |= r[i[2]]; break;
case XOR: ++c; r[i[1]] ^= r[i[2]]; break;
case SHL: ++c; r[i[1]] <<= r[i[2]]; break;
case SHR: ++c; r[i[1]] >>= r[i[2]]; break;
case ADD: ++c; r[i[1]] += r[i[2]]; break;
case SUB: ++c; r[i[1]] -= r[i[2]]; break;
case MUL: {
c += 2;
uint64_t p = (uint64_t)r[i[1]] * r[i[2]];
*r = p >> 0x20;
r[i[1]] = p;
break;
}
case DIV: {
c += 32;
uint32_t rm = r[i[1]] % r[i[2]];
uint32_t q = r[i[1]] / r[i[2]];
*r = rm;
r[i[1]] = q;
break;
}
case MVI: ++c; r[i[1]] = i[2]; break;
case CMVI: c += 2; if (*r) r[i[1]] = i[2]; break;
case EQI: ++c; *r = r[i[1]] == i[2] ? -1 : 0; break;
case NEQI: ++c; *r = r[i[1]] != i[2] ? -1 : 0; break;
case LTI: ++c; *r = r[i[1]] < i[2] ? -1 : 0; break;
case LEI: ++c; *r = r[i[1]] <= i[2] ? -1 : 0; break;
case GTI: ++c; *r = r[i[1]] > i[2] ? -1 : 0; break;
case GEI: ++c; *r = r[i[1]] >= i[2] ? -1 : 0; break;
case ANDI: ++c; r[i[1]] &= i[2]; break;
case ORI: ++c; r[i[1]] |= i[2]; break;
case XORI: ++c; r[i[1]] ^= i[2]; break;
case SHLI: ++c; r[i[1]] <<= i[2]; break;
case SHRI: ++c; r[i[1]] >>= i[2]; break;
case ADDI: ++c; r[i[1]] += i[2]; break;
case SUBI: ++c; r[i[1]] -= i[2]; break;
case MULI: {
c += 2;
uint64_t p = (uint64_t)r[i[1]] * i[2];
*r = p >> 0x20;
r[i[1]] = p;
break;
}
case DIVI: {
c += 32;
uint32_t rm = r[i[1]] % i[2];
uint32_t q = r[i[1]] / i[2];
*r = rm;
r[i[1]] = q;
break;
}
}
}
end:
chk(o == prime(n), "wrong result for %d", n);
}
printf("total cycles: %lld\n", c);
return 0;
}
negwill make some useful optimizations available? \$\endgroup\$2and10000, and return the wrong answer for anything else? \$\endgroup\$