Skip to content

Instantly share code, notes, and snippets.

@iscgar
Created November 9, 2020 19:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save iscgar/9026d13060524f546268d08fb285e45f to your computer and use it in GitHub Desktop.
Save iscgar/9026d13060524f546268d08fb285e45f to your computer and use it in GitHub Desktop.
Hand-rolled FizzBuzz redux (thanks, Itai!)
#include <string.h>
#include <unistd.h>
#define CACHELINE 64
#define ALIGNED_BUF 65536
#define DELIM " "
typedef struct {
unsigned short offset;
char data[CACHELINE - sizeof(unsigned short)];
} counters_t;
__attribute__((always_inline))
static inline unsigned int inc(counters_t *ct, char *f)
{
const char *end = ct->data + ct->offset;
const unsigned int n = sizeof(ct->data) - ct->offset - 1;
char *c = ct->data + sizeof(ct->data) - sizeof(DELIM) - 1;
char carry, v;
memcpy(f, end, n);
for (carry = 1, v = 5; ; --c, v = carry, carry = 0)
{
*c += v;
if (*c > '9')
{
++carry;
*c -= 10;
}
else if (!carry)
{
break;
}
}
if (c - ct->data < ct->offset)
{
ct->offset = c - ct->data;
}
return n;
}
int main(void)
{
__attribute__((aligned(CACHELINE))) static counters_t counters[] = {
{ sizeof(counters[0].data) - (sizeof(DELIM) + 1), "000000000000000000000000000000000000000000000000000000000001" DELIM },
{ sizeof(counters[0].data) - (sizeof(DELIM) + 1), "000000000000000000000000000000000000000000000000000000000002" DELIM },
{ 0, "Fizz" DELIM },
{ sizeof(counters[0].data) - (sizeof(DELIM) + 1), "000000000000000000000000000000000000000000000000000000000004" DELIM },
{ 0, "Buzz" DELIM },
{ 0, "Fizz" DELIM },
{ sizeof(counters[0].data) - (sizeof(DELIM) + 1), "000000000000000000000000000000000000000000000000000000000007" DELIM },
{ sizeof(counters[0].data) - (sizeof(DELIM) + 1), "000000000000000000000000000000000000000000000000000000000008" DELIM },
{ 0, "Fizz" DELIM },
{ 0, "Buzz" DELIM },
{ sizeof(counters[0].data) - (sizeof(DELIM) + 2), "000000000000000000000000000000000000000000000000000000000011" DELIM },
{ 0, "Fizz" DELIM },
{ sizeof(counters[0].data) - (sizeof(DELIM) + 2), "000000000000000000000000000000000000000000000000000000000013" DELIM },
{ sizeof(counters[0].data) - (sizeof(DELIM) + 2), "000000000000000000000000000000000000000000000000000000000014" DELIM },
{ 0, "FizzBuzz" DELIM },
};
__attribute__((aligned(4096))) static char buf[ALIGNED_BUF + (sizeof(counters[0].data) * 15)] = { 0 };
char *off = buf;
for (;;)
{
while (off - buf < ALIGNED_BUF)
{
if (__builtin_expect(counters[0].data[0] != '0', 0))
{
goto end;
}
off += inc(&counters[0], off);
off += inc(&counters[1], off);
for (const char *c = counters[2].data; *c; *off++ = *c++)
;
off += inc(&counters[3], off);
for (const char *c = counters[4].data; *c; *off++ = *c++)
;
for (const char *c = counters[5].data; *c; *off++ = *c++)
;
off += inc(&counters[6], off);
off += inc(&counters[7], off);
for (const char *c = counters[8].data; *c; *off++ = *c++)
;
for (const char *c = counters[9].data; *c; *off++ = *c++)
;
off += inc(&counters[10], off);
for (const char *c = counters[11].data; *c; *off++ = *c++)
;
off += inc(&counters[12], off);
off += inc(&counters[13], off);
for (const char *c = counters[14].data; *c; *off++ = *c++)
;
}
write(1, buf, ALIGNED_BUF);
memcpy(buf, buf + ALIGNED_BUF, (off - buf) % ALIGNED_BUF);
off -= ALIGNED_BUF;
}
end:
*off++ = '\n';
write(1, buf, off - buf);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment