r/dailyprogrammer Challenge #347 : Linear Feedback Shift Register

lfsr.c

 /* https://redd.it/7r17qr */
#define _POSIX_C_SOURCE 200112L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>

typedef unsigned long (*lfsr)(unsigned long);

static lfsr
lfsr_compile(int len, int not, int *taps, int ntaps)
{
    /* Accumulate taps into bitmask */
    unsigned long mask = 0;
    for (int i = 0; i < ntaps; i++)
        mask |= 1UL << taps[i];

    /* Allocate memory for function */
    int fd = open("/dev/zero", O_RDWR);
    void *p = mmap(0, 4096, PROT_WRITE, MAP_PRIVATE, fd, 0);
    close(fd);

    unsigned char *jit = p;
    /* mov  rsi, mask */
    *jit++ = 0x48;
    *jit++ = 0xBE;
    *jit++ = mask >>  0;
    *jit++ = mask >>  8;
    *jit++ = mask >> 16;
    *jit++ = mask >> 24;
    *jit++ = mask >> 32;
    *jit++ = mask >> 40;
    *jit++ = mask >> 48;
    *jit++ = mask >> 56;
    /* and  rsi, rdi  */
    *jit++ = 0x48;
    *jit++ = 0x21;
    *jit++ = 0xfe;
    /* popcnt rax, rsi */
    *jit++ = 0xf3;
    *jit++ = 0x48;
    *jit++ = 0x0f;
    *jit++ = 0xb8;
    *jit++ = 0xc6;
    if (not) {
        /* inc  eax   */
        *jit++ = 0xff;
        *jit++ = 0xc0;
    }
    /* and  eax, 1    */
    *jit++ = 0x83;
    *jit++ = 0xE0;
    *jit++ = 0x01;
    /* shr  rdi, 1    */
    *jit++ = 0x48;
    *jit++ = 0xd1;
    *jit++ = 0xef;
    /* shl  rax, len - 1 */
    *jit++ = 0x48;
    *jit++ = 0xc1;
    *jit++ = 0xe0;
    *jit++ = len - 1;
    /* or   rax, rdi  */
    *jit++ = 0x48;
    *jit++ = 0x09;
    *jit++ = 0xf8;
    /* ret            */
    *jit++ = 0xc3;

    mprotect(p, 4096, PROT_EXEC);
    return p;
}

static void
print(unsigned long long v, int len)
{
    for (int i = len - 1; i >= 0; i--)
        putchar((v >> i) & 1 ? '1' : '0');
    putchar('\n');
}

int
main(void)
{
    char tapstr[129];
    char op[5];
    char seed[65];
    int steps;

    while (scanf(" [%128[^]]] %4s %64s %d", tapstr, op, seed, &steps) == 4) {
        unsigned long long state = 0;
        int ntaps = 0;
        int taps[64];
        int len = strlen(seed);

        /* Parse seed */
        for (int i = 0; i < len; i++)
            if (seed[len - i - 1] == '1')
                state |= 1ULL << i;

        /* Parse taps */
        for (char *v = strtok(tapstr, ","); v; v = strtok(0, ","))
            taps[ntaps++] = len - atoi(v) - 1;

        /* Compile LSFR to a native function */
        lfsr f = lfsr_compile(len, op[1] == 'N', taps, ntaps);

        /* Run LFSR */
        printf("%-2d ", 0);
        print(state, len);
        for (int i = 0; i < steps; i++) {
            state = f(state);
            printf("%-2d ", i + 1);
            print(state, len);
        }
    }
}

Makefile

CFLAGS = -std=c99 -Wall -Wextra -O3 -g3
lfsr: lfsr.c