#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

char buf[64000000] __attribute__ ((aligned (16)));
int size;

static int count_naive() {
  int count = 0, i = 0;
  for (int i = 0; i < size; ++i) {
    count += buf[i] == '\n';
  }
  return count;
}

static int count_memchr() {
  int count = 0, i = 0;
  const char *p = buf;
  while (p) {
    p = memchr(p + 1, '\n', buf + size - p);
    count++;
  }
  return count;
}

static inline int maybe_contain_zero_byte(uint64_t x) {
  // See https://github.com/lattera/glibc/blob/master/string/memchr.c
  const uint64_t MAGIC_BITS = 0x7efefefefefefeff;
  return ((((x + MAGIC_BITS) ^ ~x) & ~MAGIC_BITS) != 0);
}

static int count_u64() {
  uint64_t *p = (uint64_t *)&buf;
  uint64_t x = '\n' + ('\n' << 8);
  int count = 0;
  x |= x << 16;
  x |= x << 32;
  for (int i = 0; i < size / 8; ++i, ++p) {
    uint64_t v = *p ^ x;
    if (maybe_contain_zero_byte(v)) {
      const char *c = (const char *) p;
      for (int j = 0; j < 8; ++j) {
        count += (((v >> (8 * j)) & 0xff) == 0);
      }
    }
  }
  return count;
}

int main(int argc, char const *argv[]) {
  int fd = open(argv[1], O_RDONLY);
  size = (int) read(fd, buf, sizeof buf);
  if (argv[2] && argv[2][0] == 'n') {
    printf("naive:  %d\n", count_naive());
  } else if (argv[2] && argv[2][0] == 'm') {
    printf("memchr: %d\n", count_memchr());
  } else {
    printf("u64:    %d\n", count_u64());
  }
  return 0;
}

/*
# gcc 7.3.0
gcc -O2 a.c -o ao2
gcc -O3 -mavx2 a.c -o ao3

# best of 50 runs, wall time
# test case: random data
# head -c 64000000 /dev/urandom > /tmp/r 
./ao2 naive  0.069
./ao2 u64    0.043
./ao2 memchr 0.039
./ao3 naive  0.038  # best
./ao3 u64    0.043
./ao3 memchr 0.039

# test case: real code
# v=read('/home/quark/hg-committed/mercurial/commands.py')
# write('/tmp/c', v * (64000000/len(v)))
./ao2 naive  0.069
./ao2 u64    0.059
./ao2 memchr 0.055
./ao3 naive  0.038  # best
./ao3 u64    0.055
./ao3 memchr 0.055  # slower

# ruby script to run the tests
path = ARGV[0]
%w[./ao2 ./ao3].product(%w[naive u64 memchr]).each do |exe, name|
  time = 50.times.map do
    t1 = Time.now
    system exe, path, name, 1=>'/dev/null'
    Time.now - t1
  end.min
  puts "#{exe} #{name.ljust(6)} #{time.round(3)}"
end
*/