4 * (c) 2010 Martin Mares <mj@ucw.cz>
8 * Things that are not implemented:
11 * - exact behavior of accumulator/R1/R2 (the manual lacks details)
12 * - exact behavior of negative zero
13 * - I/O instructions for devices that are not emulated (paper tape
14 * reader and puncher, card reader and puncher, magnetic tape unit)
18 #define UNUSED __attribute__((unused))
19 #define NORETURN __attribute__((noreturn))
21 #undef ENABLE_DAEMON_MODE
33 static int cpu_quota = -1;
34 static int print_quota = -1;
35 static void (*error_hook)(char *msg);
37 // Minsk-2 has 37-bit words in sign-magnitude representation (bit 36 = sign)
38 typedef unsigned long long int word;
41 #define WORD_MASK 01777777777777ULL
42 #define SIGN_MASK 01000000000000ULL
43 #define VAL_MASK 00777777777777ULL
45 static int wsign(word w)
47 return (w & SIGN_MASK) ? -1 : 1;
50 static word wabs(word w)
55 #define WF(w) (wsign(w) < 0 ? '-' : '+'), wabs(w)
57 static long long wtoll(word w)
65 static word wfromll(long long x)
67 word w = ((x < 0) ? -x : x) & VAL_MASK;
73 static double wtofrac(word w)
75 return (double)wtoll(w) / (double)(1ULL << 36);
78 static word wfromfrac(double d)
80 return wfromll((long long)(d * (double)(1ULL << 36)));
83 static int int_in_range(long long x)
85 return (x >= -(long long)VAL_MASK && x <= (long long)VAL_MASK);
88 static int frac_in_range(double d)
90 return (d > -1. && d < 1.);
93 static int wexp(word w)
96 return (w & 0100 ? -exp : exp);
99 static word wputexp(word w, int exp)
101 return ((w & ~(word)0177) | ((exp < 0) ? 0100 | (-exp) : exp));
104 static int wmanti(word w)
106 return ((w >> 8) & ((1 << 28) - 1));
109 static double wtofloat(word w)
111 double x = wmanti(w);
112 return ldexp(x, wexp(w) - 28);
115 static int float_in_range(double x)
118 return (x <= ldexp((1 << 28) - 1, 63 - 28));
121 static word wfromfloat(double x, int normalized)
130 double m = frexp(x, &exp);
131 word mm = (word) ldexp(m, 28);
136 if (normalized || exp < -91)
154 static word mem[4096];
156 static word rd(int addr)
158 word val = addr ? mem[addr] : 0;
160 printf("\tRD %04o = %c%012llo\n", addr, WF(val));
164 static void wr(int addr, word val)
166 assert(!(val & ~(WORD_MASK)));
168 printf("\tWR %04o = %c%012llo\n", addr, WF(val));
174 NORETURN static void parse_error(char *msg)
177 error_hook("Parse error");
178 printf("Ошибка входа (стр. %d): %s\n", lino, msg);
182 static void parse_in(void)
187 while (fgets(line, sizeof(line), stdin))
190 char *eol = strchr(line, '\n');
192 parse_error("Строка слишком долгая");
194 if (eol > line && eol[-1] == '\r')
198 if (!c[0] || c[0] == ';')
208 for (int i=0; i<4; i++)
212 if (*c >= '0' && *c <= '7')
213 addr = 8*addr + *c++ - '0';
215 parse_error("Плохая цифра");
220 parse_error("Адрес слишком долгий");
228 parse_error("Плохой знак");
230 for (int i=0; i<12; i++)
234 if (*c >= '0' && *c <= '7')
235 w = 8*w + *c++ - '0';
237 parse_error("Плохая цифра");
242 parse_error("Номер слишком долгий");
249 static word r1, r2, current_ins;
250 static int ip = 00050; // Standard program start location
253 NORETURN static void stop(char *reason, char *notice)
257 printf("Машина остановлена -- %s\n", reason);
258 printf("СчАК:%04o См:%c%012llo Р1:%c%012llo Р2:%c%012llo\n", prev_ip, WF(acc), WF(r1), WF(r2));
262 NORETURN static void over(void)
264 stop("Аварийный останов", "Overflow");
267 NORETURN static void notimp(void)
270 stop("Устройство разбитое", "Not implemented");
273 NORETURN static void noins(void)
276 stop("Эту команду не знаю", "Illegal instruction");
279 static uint16_t linebuf[128];
281 static uint16_t russian_chars[64] = {
282 '0', '1', '2', '3', '4', '5', '6', '7', // 0x
283 '8', '9', '+', '-', '/', ',', '.', ' ', // 1x
284 0x2169, '^', '(', ')', 0x00d7, '=', ';', '[', // 2x
285 ']', '*', '`', '\'', 0x2260, '<', '>', ':', // 3x
286 0x410, 0x411, 0x412, 0x413, 0x414, 0x415, 0x416, 0x417, // 4x
287 0x418, 0x419, 0x41a, 0x41b, 0x41c, 0x41d, 0x41e, 0x41f, // 5x
288 0x420, 0x421, 0x422, 0x423, 0x424, 0x425, 0x426, 0x427, // 6x
289 0x428, 0x429, 0x42b, 0x42c, 0x42d, 0x42e, 0x42f, 0x2013 // 7x
292 static uint16_t latin_chars[64] = {
293 '0', '1', '2', '3', '4', '5', '6', '7', // 0x
294 '8', '9', '+', '-', '/', ',', '.', ' ', // 1x
295 0x2169, '^', '(', ')', 0x00d7, '=', ';', '[', // 2x
296 ']', '*', '`', '\'', 0x2260, '<', '>', ':', // 3x
297 'A', 'B', 'W', 'G', 'D', 'E', 'V', 'Z', // 4x
298 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', // 5x
299 'R', 'S', 'T', 'U', 'F', 'H', 'C', ' ', // 6x
300 ' ', ' ', 'Y', 'X', ' ', ' ', 'Q', 0x2013 // 7x
303 static void print_line(int r)
306 * Meaning of bits of r:
307 * 0 = perform line feed
313 if (print_quota > 0 && !--print_quota)
314 stop("Бумага дошла - нужно ехать в Сибирь про новую", "Out of paper");
315 for (int i=0; i<128; i++)
324 putchar(0xc0 | (ch >> 6));
325 putchar(0x80 | (ch & 0x3f));
329 putchar(0xe0 | (ch >> 12));
330 putchar(0x80 | ((ch >> 6) & 0x3f));
331 putchar(0x80 | (ch & 0x3f));
336 memset(linebuf, 0, sizeof(linebuf));
344 static void print_ins(int x, int y)
348 int r = (x >> 9) & 7;
361 case 0: // Decimal float
362 fmt = "+dddddddx+xbd";
364 case 1: // Octal number
365 fmt = "+oooooooooooo";
367 case 2: // Decimal fixed
370 case 3: // Decimal unsigned
374 case 4: // One Russian symbol
377 case 5: // Russian text
380 case 6: // One Latin symbol
383 default: // Latin text
400 ch = (yy & (1ULL << bit)) ? '-' : '+';
404 ch = '0' + ((yy >> bit) & 1);
408 ch = '0' + ((yy >> bit) & 7);
412 ch = '0' + ((yy >> bit) & 15);
418 ch = russian_chars[(yy >> bit) & 077];
422 ch = latin_chars[(yy >> bit) & 077];
430 if (ch == '0' || ch == ' ')
436 pos = (pos+1) & 0177;
441 static void run(void)
450 int op = (w >> 30) & 0177; // Operation code
451 int ax = (w >> 28) & 3; // Address extensions not supported
452 int ix = (w >> 24) & 15; // Indexing
453 int x = (w >> 12) & 07777; // Operands (original form)
455 int xi=x, yi=y; // (indexed form)
457 printf("@%04o %c%02o %02o %04o %04o\n",
459 (w & SIGN_MASK) ? '-' : '+',
460 (int)((w >> 30) & 077),
461 (int)((w >> 24) & 077),
469 xi = (xi + (int)((i >> 12) & 07777)) & 07777;
470 yi = (yi + (int)(i & 07777)) & 07777;
472 printf("\tIndexing -> %04o %04o\n", xi, yi);
477 if (cpu_quota > 0 && !--cpu_quota)
478 stop("Тайм-аут", "CPU quota exceeded");
480 /* Arithmetic operations */
483 long long aa, bb, cc;
487 auto void afetch(void);
497 auto void astore(word result);
498 void astore(word result)
505 auto void astore_int(long long x);
506 void astore_int(long long x)
508 if (!int_in_range(x))
513 auto void astore_frac(double f);
514 void astore_frac(double f)
516 if (!frac_in_range(f))
518 astore(wfromfrac(f));
521 auto void astore_float(double f);
522 void astore_float(double f)
524 if (!float_in_range(f))
526 astore(wfromfloat(f, 0));
535 case 004 ... 007: // XOR
539 case 010 ... 013: // FIX addition
541 astore_int(wtoll(a) + wtoll(b));
543 case 014 ... 017: // FP addition
545 astore_float(wtofloat(a) + wtofloat(b));
547 case 020 ... 023: // FIX subtraction
549 astore_int(wtoll(a) - wtoll(b));
551 case 024 ... 027: // FP subtraction
553 astore_float(wtofloat(a) - wtofloat(b));
555 case 030 ... 033: // FIX multiplication
557 astore_frac(wtofrac(a) * wtofrac(b));
559 case 034 ... 037: // FP multiplication
561 astore_float(wtofloat(a) * wtofloat(b));
563 case 040 ... 043: // FIX division
569 astore_frac(ad / bd);
571 case 044 ... 047: // FP division
575 if (!bd || wexp(b) < -63)
577 astore_float(ad / bd);
579 case 050 ... 053: // FIX subtraction of abs values
581 astore_int(wabs(a) - wabs(b));
583 case 054 ... 057: // FP subtraction of abs values
585 astore_float(fabs(wtofloat(a)) - fabs(wtofloat(b)));
587 case 060 ... 063: // Shift logical
590 if (i <= -37 || i >= 37)
593 astore((a << i) & WORD_MASK);
597 case 064 ... 067: // Shift arithmetical
601 if (i <= -36 || i >= 36)
604 cc = (aa << i) & VAL_MASK;
607 astore((a & SIGN_MASK) | wfromll(cc));
609 case 070 ... 073: // And
613 case 074 ... 077: // Or
621 stop("Останов машины", "Halted");
622 case 0103: // I/O magtape
624 case 0104: // Disable rounding
626 case 0105: // Enable rounding
628 case 0106: // Interrupt control
630 case 0107: // Reverse tape
633 wr(yi, r1 = acc = rd(xi));
635 case 0111: // Move negative
636 wr(yi, acc = (r1 = rd(xi)) ^ SIGN_MASK);
638 case 0112: // Move absolute value
639 wr(yi, acc = (r1 = rd(xi)) & VAL_MASK);
641 case 0113: // Read from keyboard
643 case 0114: // Copy sign
644 wr(yi, acc = rd(yi) ^ ((r1 = rd(xi)) & SIGN_MASK));
646 case 0115: // Read code from R1 (obscure)
648 case 0116: // Copy exponent
649 wr(yi, acc = wputexp(rd(yi), wexp(r1 = rd(xi))));
651 case 0117: // I/O teletype
657 aa = (a >> 24) & 017777;
660 b = rd(y); // (a mountain range near Prague)
661 acc = ((aa-1) << 24) |
662 (((((a >> 12) & 07777) + (b >> 12) & 07777) & 07777) << 12) |
663 (((a & 07777) + (b & 07777)) & 07777);
671 case 0131: // Jump to subroutine
672 wr(y, acc = ((030ULL << 30) | ((ip & 07777ULL) << 12)));
675 case 0132: // Jump if positive
681 case 0133: // Jump if overflow
682 // Since we always trap on overflow, this instruction always jumps to the 1st address
685 case 0134: // Jump if zero
691 case 0135: // Jump if key pressed
692 // No keys are ever pressed, so always jump to 2nd
695 case 0136: // Interrupt masking
697 case 0137: // Used only when reading from tape
699 case 0140 ... 0147: // I/O
701 case 0150 ... 0154: // I/O
703 case 0160 ... 0161: // I/O
705 case 0162: // Printing
710 case 0170: // FIX multiplication, bottom part
712 if (wtofrac(a) * wtofrac(b) >= .1/(1ULL << 32))
714 acc = wfromll(((unsigned long long)wabs(a) * (unsigned long long)wabs(b)) & VAL_MASK);
715 // XXX: What should be the sign? The book does not define that.
728 case 0172: // Add exponents
731 i = wexp(a) + wexp(b);
732 if (i < -63 || i > 63)
737 case 0173: // Sub exponents
740 i = wexp(b) - wexp(a);
741 if (i < -63 || i > 63)
746 case 0174: // Addition in one's complement
753 // XXX: The effect on the accumulator is undocumented, but likely to be as follows:
756 case 0175: // Normalization
761 wr((yi+1) & 07777, 0);
769 while (!(a & (SIGN_MASK >> 1)))
776 wr((yi+1) & 07777, i);
779 case 0176: // Population count
782 for (int i=0; i<36; i++)
785 // XXX: Guessing that acc gets a copy of the result
794 printf("\tACC:%c%012llo R1:%c%012llo R2:%c%012llo\n", WF(acc), WF(r1), WF(r2));
798 NORETURN static void die(char *msg)
800 fprintf(stderr, "minsk: %s\n", msg);
804 /*** Daemon interface ***/
806 #ifdef ENABLE_DAEMON_MODE
809 * The daemon mode was a quick hack for the Po drate contest.
810 * Most parameters are hard-wired.
817 #include <sys/signal.h>
818 #include <sys/wait.h>
819 #include <sys/poll.h>
820 #include <sys/socket.h>
821 #include <netinet/in.h>
822 #include <arpa/inet.h>
825 #define DTRACE(msg, args...) fprintf(stderr, msg "\n", ##args)
826 #define DLOG(msg, args...) fprintf(stderr, msg "\n", ##args)
828 #define DTRACE(msg, args...) do { } while(0)
829 #define DLOG(msg, args...) syslog(LOG_INFO, msg, ##args)
832 #define MAX_CONNECTIONS 50 // Per daemon
833 #define MAX_CONNS_PER_IP 1 // Per IP
834 #define MAX_TRACKERS 200 // IP address trackers
835 #define TBF_MAX 5 // Max number of tokens in the bucket
836 #define TBF_REFILL_PER_SEC 0.2 // Bucket refill rate (buckets/sec)
838 #define PID_FILE "/var/run/pd-minsk.pid"
842 static char **spt_argv;
843 static char *spt_start, *spt_end;
845 static void setproctitle_init(int argc, char **argv)
848 char **env, **oldenv, *t;
852 /* Create a backup copy of environment */
855 for (i=0; oldenv[i]; i++)
856 len += strlen(oldenv[i]) + 1;
857 __environ = env = malloc(sizeof(char *)*(i+1));
859 if (!__environ || !t)
860 die("malloc failed");
861 for (i=0; oldenv[i]; i++)
864 len = strlen(oldenv[i]) + 1;
865 memcpy(t, oldenv[i], len);
870 /* Scan for consecutive free space */
871 spt_start = spt_end = argv[0];
872 for (i=0; i<argc; i++)
873 if (!i || spt_end+1 == argv[i])
874 spt_end = argv[i] + strlen(argv[i]);
875 for (i=0; oldenv[i]; i++)
876 if (spt_end+1 == oldenv[i])
877 spt_end = oldenv[i] + strlen(oldenv[i]);
881 setproctitle(const char *msg, ...)
888 if (spt_end > spt_start)
890 n = vsnprintf(buf, sizeof(buf), msg, args);
891 if (n >= (int) sizeof(buf) || n < 0)
892 sprintf(buf, "<too-long>");
893 n = spt_end - spt_start;
894 strncpy(spt_start, buf, n);
896 spt_argv[0] = spt_start;
902 static void sigchld_handler(int sig UNUSED)
906 static void sigalrm_handler(int sig UNUSED)
908 const char err[] = "--- Timed out. Time machine disconnected. ---\n";
909 write(1, err, sizeof(err));
910 DLOG("Connection timed out");
914 static void child_error_hook(char *err)
916 DLOG("Stopped: %s", err);
919 static void child(int sk2)
925 struct sigaction sact = {
926 .sa_handler = sigalrm_handler,
928 if (sigaction(SIGALRM, &sact, NULL) < 0)
929 die("sigaction: %m");
936 const char welcome[] = "+++ Welcome to our computer museum. +++\n+++ Our time machine will connect you to one of our exhibits. +++\n\n";
937 write(1, welcome, sizeof(welcome));
939 error_hook = child_error_hook;
949 struct tracker *tracker;
952 static struct conn connections[MAX_CONNECTIONS];
954 static struct conn *get_conn(struct in_addr *a)
956 for (int i=0; i<MAX_CONNECTIONS; i++)
958 struct conn *c = &connections[i];
961 memcpy(&c->addr, a, sizeof(struct in_addr));
968 static struct conn *pid_to_conn(pid_t pid)
970 for (int i=0; i<MAX_CONNECTIONS; i++)
972 struct conn *c = &connections[i];
979 static void put_conn(struct conn *c)
992 static struct tracker trackers[MAX_TRACKERS];
994 static int get_tracker(struct conn *c)
997 time_t now = time(NULL);
1000 for (i=0; i<MAX_TRACKERS; i++)
1003 if (!memcmp(&t->addr, &c->addr, sizeof(struct in_addr)))
1006 if (i < MAX_TRACKERS)
1008 if (now > t->last_access)
1010 t->tokens += (now - t->last_access) * (double) TBF_REFILL_PER_SEC;
1011 t->last_access = now;
1012 if (t->tokens > TBF_MAX)
1013 t->tokens = TBF_MAX;
1015 DTRACE("TBF: Using tracker %d (%.3f tokens)", i, t->tokens);
1020 for (int i=0; i<MAX_TRACKERS; i++)
1023 if (!t->active_conns && (min_i < 0 || t->last_access < trackers[min_i].last_access))
1028 DLOG("TBF: Out of trackers!");
1031 t = &trackers[min_i];
1033 DTRACE("TBF: Recycling tracker %d", min_i);
1035 DTRACE("TBF: Creating tracker %d", min_i);
1036 memset(t, 0, sizeof(*t));
1038 t->last_access = now;
1039 t->tokens = TBF_MAX;
1042 if (t->active_conns >= MAX_CONNS_PER_IP)
1044 DTRACE("TBF: Too many conns per IP");
1048 if (t->tokens >= 0.999)
1053 DTRACE("TBF: Passed (%d conns)", t->active_conns);
1058 DTRACE("TBF: Failed");
1064 static void put_tracker(struct conn *c)
1066 struct tracker *t = c->tracker;
1069 DLOG("put_tracker: no tracker?");
1073 if (t->active_conns <= 0)
1075 DLOG("put_tracker: no counter?");
1080 DTRACE("TBF: Put tracker (%d conns remain)", t->active_conns);
1083 static void run_as_daemon(int do_fork)
1085 int sk = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP);
1090 if (setsockopt(sk, SOL_SOCKET, SO_REUSEADDR, &one, sizeof(one)) < 0)
1091 die("setsockopt: %m");
1093 struct sockaddr_in sa = {
1094 .sin_family = AF_INET,
1095 .sin_port = ntohs(1969),
1096 .sin_addr.s_addr = INADDR_ANY,
1098 if (bind(sk, (struct sockaddr *) &sa, sizeof(sa)) < 0)
1100 if (listen(sk, 128) < 0)
1102 // if (fcntl(sk, F_SETFL, O_NONBLOCK) < 0)
1103 // die("fcntl: %m");
1112 FILE *f = fopen(PID_FILE, "w");
1115 fprintf(f, "%d\n", pid);
1122 setresgid(GID, GID, GID);
1123 setresuid(UID, UID, UID);
1127 struct sigaction sact = {
1128 .sa_handler = sigchld_handler,
1129 .sa_flags = SA_RESTART,
1131 if (sigaction(SIGCHLD, &sact, NULL) < 0)
1132 die("sigaction: %m");
1134 DLOG("Daemon ready");
1135 setproctitle("minsk: Listening");
1136 openlog("minsk", LOG_PID, LOG_LOCAL7);
1140 struct pollfd pfd[1] = {
1141 { .fd = sk, .events = POLLIN },
1144 int nfds = poll(pfd, 1, 60000);
1145 if (nfds < 0 && errno != EINTR)
1154 while ((pid = waitpid(-1, &status, WNOHANG)) > 0)
1156 if (!WIFEXITED(status) || WEXITSTATUS(status))
1157 DLOG("Process %d exited with strange status %x", pid, status);
1159 struct conn *conn = pid_to_conn(pid);
1162 DTRACE("Connection with PID %d exited", pid);
1167 DTRACE("PID %d exited, matching no connection", pid);
1170 if (!(pfd[0].revents & POLLIN))
1173 socklen_t salen = sizeof(sa);
1174 int sk2 = accept(sk, (struct sockaddr *) &sa, &salen);
1184 DTRACE("Got connection: fd=%d", sk2);
1186 struct conn *conn = get_conn(&sa.sin_addr);
1187 const char *reason = NULL;
1190 if (!get_tracker(conn))
1192 DLOG("Connection from %s dropped: Throttling", inet_ntoa(sa.sin_addr));
1195 reason = "--- Sorry, but you are sending too many requests. Please slow down. ---\n";
1200 DLOG("Connection from %s dropped: Too many connections", inet_ntoa(sa.sin_addr));
1201 reason = "--- Sorry, maximum number of connections exceeded. Please come later. ---\n";
1207 DLOG("fork failed: %m");
1216 DLOG("Accepted connection from %s", inet_ntoa(sa.sin_addr));
1217 setproctitle("minsk: %s", inet_ntoa(sa.sin_addr));
1222 DLOG("Sending error message to %s", inet_ntoa(sa.sin_addr));
1223 setproctitle("minsk: %s ERR", inet_ntoa(sa.sin_addr));
1224 write(sk2, reason, strlen(reason));
1229 DTRACE("Created process %d", pid);
1238 static void run_as_daemon(int do_fork UNUSED)
1240 die("Daemon mode not supported in this version, need to recompile.");
1243 static void setproctitle_init(int argc UNUSED, char **argv UNUSED)
1249 static void init_memory(int set_password)
1253 // For the contest, we fill the whole memory with -00 00 0000 0000 (HALT),
1254 // not +00 00 0000 0000 (NOP). Otherwise, an empty program would reveal
1255 // the location of the password :)
1256 for (int i=0; i<MEM_SIZE; i++)
1257 mem[i] = 01000000000000ULL;
1259 // Store the password
1261 mem[pos++] = 0574060565373;
1262 mem[pos++] = 0371741405340;
1263 mem[pos++] = 0534051524017;
1266 for (int i=0; i<MEM_SIZE; i++)
1267 mem[i] = 00000000000000ULL;
1270 static const struct option longopts[] = {
1271 { "cpu-quota", required_argument, NULL, 'q' },
1272 { "daemon", no_argument, NULL, 'd' },
1273 { "nofork", no_argument, NULL, 'n' },
1274 { "set-password", no_argument, NULL, 's' },
1275 { "print-quota", required_argument, NULL, 'p' },
1276 { "trace", required_argument, NULL, 't' },
1277 { NULL, 0, NULL, 0 },
1280 static void usage(void)
1282 fprintf(stderr, "Options:\n\n");
1283 #ifdef ENABLE_DAEMON_MODE
1285 --daemon Run as daemon and listen for network connections\n\
1286 --nofork When run with --daemon, avoid forking\n\
1290 --set-password Put hidden password in memory\n\
1291 --trace=<level> Enable tracing of program execution\n\
1292 --cpu-quota=<n> Set CPU quota to <n> instructions\n\
1293 --print-quota=<n> Set printer quota to <n> lines\n\
1298 int main(int argc, char **argv)
1301 int daemon_mode = 0;
1303 int set_password = 0;
1305 while ((opt = getopt_long(argc, argv, "", longopts, NULL)) >= 0)
1318 print_quota = atoi(optarg);
1321 cpu_quota = atoi(optarg);
1324 trace = atoi(optarg);
1332 setproctitle_init(argc, argv);
1333 init_memory(set_password);
1336 run_as_daemon(do_fork);