Created
March 20, 2015 14:30
-
-
Save anonymous/f7e4a5086a2b0acc83aa to your computer and use it in GitHub Desktop.
Revisions
-
Anonymous created this gist
Mar 20, 2015 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,215 @@ /* http://redd.it/2zna5q * Fibonacci example: * (1) (2) + * 0:0 * 1:1 * 20 */ #define _BSD_SOURCE // MAP_ANONYMOUS #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <unistd.h> struct asmbuf { size_t nconstants; double constants[32]; size_t size, fill; uint8_t code[]; }; #ifdef __WIN32__ #include <windows.h> struct asmbuf * asmbuf_create(void) { SYSTEM_INFO system_info; GetSystemInfo(&system_info); long page_size = system_info.dwPageSize; struct asmbuf *buf = VirtualAlloc(NULL, page_size, MEM_COMMIT, PAGE_READWRITE); buf->size = page_size; return buf; } void asmbuf_free(struct asmbuf *buf) { VirtualFree(buf, buf->size, MEM_RELEASE); } void asmbuf_finalize(struct asmbuf *buf) { DWORD old_protect; VirtualProtect(buf, buf->size, PAGE_EXECUTE_READ, &old_protect); } #else /* POSIX */ #include <sys/mman.h> struct asmbuf * asmbuf_create(void) { long page_size = sysconf(_SC_PAGESIZE); int prot = PROT_READ | PROT_WRITE; int flags = MAP_ANONYMOUS | MAP_PRIVATE; struct asmbuf *buf = mmap(NULL, page_size, prot, flags, -1, 0); buf->size = page_size; return buf; } void asmbuf_free(struct asmbuf *buf) { munmap(buf, buf->size); } void asmbuf_finalize(struct asmbuf *buf) { mprotect(buf, buf->size, PROT_READ | PROT_EXEC); } #endif void asmbuf_ins(struct asmbuf *buf, int size, uint64_t ins) { for (int i = size - 1; i >= 0; i--) buf->code[buf->fill++] = (ins >> (i * 8)) & 0xff; } void asmbuf_immediate(struct asmbuf *buf, int size, const void *value) { memcpy(buf->code + buf->fill, value, size); buf->fill += size; } static void operator2(struct asmbuf *buf, int size, uint64_t op) { asmbuf_ins(buf, 6, 0x660f1244cff0); // movlpd -16(%rdi, %rcx, 8), %xmm0 asmbuf_ins(buf, 6, 0x660f124ccff8); // movlpd -8(%rdi, %rcx, 8), %xmm1 asmbuf_ins(buf, size, op); asmbuf_ins(buf, 3, 0x48ffc9); // dec %rcx asmbuf_ins(buf, 6, 0x660f1344cff8); // movlpd %xmm0, -8(%rdi, %rcx, 8) } int main(void) { /* %rdi : pointer to the base of the stack * %rsi : index of the top of the stack when called * %rcx : index of the current top of the stack * %xmm* : intermediate results */ struct asmbuf *buf = asmbuf_create(); long max_backreference = 0; long max_stack = 0; long current_stack = 0; asmbuf_ins(buf, 3, 0x4889f1); // mov %rsi, %rcx int c; while ((c = fgetc(stdin)) != '\n' && c != EOF) { if (c == ' ') continue; switch (c) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': { ungetc(c, stdin); double *data = &buf->constants[buf->nconstants++]; scanf("%lf", data); asmbuf_ins(buf, 2, 0x48a1); // mov (data), %rax asmbuf_immediate(buf, 8, &data); asmbuf_ins(buf, 4, 0x488904cf); // mov %rax, (%rdi, %rcx, 8) asmbuf_ins(buf, 3, 0x48ffc1); // inc %rcx if (++current_stack > max_stack) max_stack = current_stack; } break; case '(': { int n; scanf("%d)", &n); if (n > max_backreference) max_backreference = n; int8_t offset = -8 * n; asmbuf_ins(buf, 4, 0x488b44f7); // mov -offset(%rdi,%rsi,8),%rax asmbuf_immediate(buf, 1, &offset); asmbuf_ins(buf, 4, 0x488904cf); // mov %rax, (%rdi, %rcx, 8) asmbuf_ins(buf, 3, 0x48ffc1); // inc %rcx if (++current_stack > max_stack) max_stack = current_stack; } break; case '+': operator2(buf, 4, 0xf20f58c1); // addsd %xmm1,%xmm0 current_stack--; break; case '-': operator2(buf, 4, 0xf20f5cc1); // subsd %xmm1,%xmm0 current_stack--; break; case '*': operator2(buf, 4, 0xf20f59c1); // mulsd %xmm1,%xmm0 current_stack--; break; case '/': operator2(buf, 4, 0xf20f5ec1); // divsd %xmm1,%xmm0 current_stack--; break; case 'Q': asmbuf_ins(buf, 6, 0x660f124ccff8); // movlpd -8(%rdi,%rcx,8),%xmm1 asmbuf_ins(buf, 4, 0xf20f51c9); // sqrtsd %xmm1,%xmm1 asmbuf_ins(buf, 6, 0x660f134ccff8); // movlpd %xmm1,-8(%rdi,%rcx,8) break; case '@': asmbuf_ins(buf, 6, 0x660f124ccff8); // movlpd -8(%rdi,%rcx,8),%xmm1 asmbuf_ins(buf, 6, 0x660f134ccff8); // movlpd %xmm1,-8(%rdi,%rcx,8) if (++current_stack > max_stack) max_stack = current_stack; break; } } asmbuf_ins(buf, 3, 0x4889c8); // mov %rcx, %rax asmbuf_ins(buf, 1, 0xc3); // retq asmbuf_finalize(buf); __attribute__ ((sysv_abi)) long (*recurrence)(double *, long) = (void *)buf->code; double stack[max_backreference + max_stack]; /* Accept up to `max_backreference` initial values. */ long nterms; for (;;) { char line[256]; fgets(line, sizeof(line), stdin); long n; double value; if (sscanf(line, "%ld:%lf", &n, &value) != 2) { nterms = strtol(line, NULL, 10); break; } else { stack[n] = value; } } /* Compute terms. */ for (long n = 0; n < max_backreference; n++) printf("%ld: %.15f\n", n, stack[n]); for (long n = max_backreference; n <= nterms;) { long nelements = recurrence(stack, max_backreference); long nvalues = nelements - max_backreference; for (long i = 0; i < nvalues; i++) printf("%ld: %.15f\n", n + i, stack[max_backreference + i]); memmove(stack, stack + nvalues, max_backreference * sizeof(stack[0])); n += nvalues; } return 0; }