#include <stdbool.h>
#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include <immintrin.h>

#define BLCKSZ 8192
#define LOOPS 1000

static inline bool
allzeros_byte_per_byte(const void *ptr, size_t len)
{
	const unsigned char *p = (const unsigned char *) ptr;
	const unsigned char *end = &p[len];

	while (p < end)
	{
		if (*p++ != 0)
			return false;
	}
	return true;
}

static inline bool
allzeros_size_t(const void *ptr, size_t len)
{
    const unsigned char *p = (const unsigned char *) ptr;
    const unsigned char *end = &p[len];
    const unsigned char *aligned_end = (const unsigned char *)
        ((uintptr_t) end & (~(sizeof(size_t) - 1)));

    /* Compare bytes until the pointer "p" is aligned */
    while (((uintptr_t) p & (sizeof(size_t) - 1)) != 0)
    {
        if (p == end)
            return true;

        if (*p++ != 0)
            return false;
    }

    /*
     * Compare remaining size_t-aligned chunks.
     *
     * aligned_end cant' be > end as we ensured to take care of len < 8 (in
     * the len < 64 check below). So, no risk to read beyond the memory area.
     */
    for (; p < aligned_end; p += sizeof(size_t))
    {
        if (*(size_t *) p != 0)
            return false;
    }

    /* Compare remaining bytes until the end */
    while (p < end)
    {
        if (*p++ != 0)
            return false;
    }

    return true;
}

static inline bool
pg_memory_is_all_zeros_v10(const void *ptr, size_t len)
{
    const unsigned char *p = (const unsigned char *) ptr;
    const unsigned char *end = &p[len];
    const unsigned char *aligned_end = (const unsigned char *)
        ((uintptr_t) end & (~(sizeof(size_t) - 1)));

    /* Compare bytes until the pointer "p" is aligned */
    while (((uintptr_t) p & (sizeof(size_t) - 1)) != 0)
    {
        if (p == end)
            return true;

        if (*p++ != 0)
            return false;
    }

    /*
     * Compare 8 * sizeof(size_t) chunks at once.
     *
     * For performance reasons, we manually unroll this loop and purposefully
     * use bitwise-ORs to combine each comparison.  This prevents boolean
     * short-circuiting and lets the compiler know that it's safe to access
     * all 8 elements regardless of the result of the other comparisons.  This
     * seems to be enough to coax a few compilers into using SIMD
     * instructions.
     *
     * There is no risk to read beyond the memory area thanks to the len < 64
     * check done below.
     */
    for (; p < aligned_end - (sizeof(size_t) * 7); p += sizeof(size_t) * 8)
    {
        if ((((size_t *) p)[0] != 0) | (((size_t *) p)[1] != 0) |
            (((size_t *) p)[2] != 0) | (((size_t *) p)[3] != 0) |
            (((size_t *) p)[4] != 0) | (((size_t *) p)[5] != 0) |
            (((size_t *) p)[6] != 0) | (((size_t *) p)[7] != 0))
            return false;
    }

    /*
     * Compare remaining size_t-aligned chunks.
     *
     * aligned_end cant' be > end as we ensured to take care of len < 8 (in
     * the len < 64 check below). So, no risk to read beyond the memory area.
     */
    for (; p < aligned_end; p += sizeof(size_t))
    {
        if (*(size_t *) p != 0)
            return false;
    }

    /* Compare remaining bytes until the end */
    while (p < end)
    {
        if (*p++ != 0)
            return false;
    }

    return true;
}

static inline bool
pg_memory_is_all_zeros_v11(const void *ptr, size_t len)
{
    const unsigned char *p = (const unsigned char *) ptr;
    const unsigned char *end = &p[len];
    const unsigned char *aligned_end = (const unsigned char *)
        ((uintptr_t) end & (~(sizeof(size_t) - 1)));

    /*
     * For len < 64, compare byte per byte to ensure we'll not read beyond the
     * memory area.
     */
    if (len < sizeof(size_t) * 8)
    {
        while (p < end)
        {
            if (*p++ != 0)
                return false;
        }
        return true;
    }

    /* Compare bytes until the pointer "p" is aligned */
    while (((uintptr_t) p & (sizeof(size_t) - 1)) != 0)
    {
        if (p == end)
            return true;

        if (*p++ != 0)
            return false;
    }

    /*
     * Compare 8 * sizeof(size_t) chunks at once.
     *
     * For performance reasons, we manually unroll this loop and purposefully
     * use bitwise-ORs to combine each comparison.  This prevents boolean
     * short-circuiting and lets the compiler know that it's safe to access
     * all 8 elements regardless of the result of the other comparisons.  This
     * seems to be enough to coax a few compilers into using SIMD
     * instructions.
     *
     * There is no risk to read beyond the memory area thanks to the len < 64
     * check done below.
     */
    for (; p < aligned_end - (sizeof(size_t) * 7); p += sizeof(size_t) * 8)
    {
        if ((((size_t *) p)[0] != 0) | (((size_t *) p)[1] != 0) |
            (((size_t *) p)[2] != 0) | (((size_t *) p)[3] != 0) |
            (((size_t *) p)[4] != 0) | (((size_t *) p)[5] != 0) |
            (((size_t *) p)[6] != 0) | (((size_t *) p)[7] != 0))
            return false;
    }

    /*
     * Compare remaining size_t-aligned chunks.
     *
     * aligned_end cant' be > end as we ensured to take care of len < 8 (in
     * the len < 64 check below). So, no risk to read beyond the memory area.
     */
    for (; p < aligned_end; p += sizeof(size_t))
    {
        if (*(size_t *) p != 0)
            return false;
    }

    /* Compare remaining bytes until the end */
    while (p < end)
    {
        if (*p++ != 0)
            return false;
    }

    return true;
}

static inline bool
pg_memory_is_all_zeros_v12(const void *ptr, size_t len)
{
    const unsigned char *p = (const unsigned char *) ptr;
    const unsigned char *end = &p[len];
    const unsigned char *aligned_end = (const unsigned char *)
        ((uintptr_t) end & (~(sizeof(size_t) - 1)));

    if (len < sizeof(size_t))  // < 8 bytes
    {
        while (p < end)
        {
            if (*p++ != 0)
                return false;
        }
        return true;
    }
    else if (len < sizeof(size_t) * 8)  // 8-63 bytes
    {
        while (((uintptr_t) p & (sizeof(size_t) - 1)) != 0)
        {
            if (p == end)
                return true;
            if (*p++ != 0)
                return false;
        }

        for (; p < aligned_end; p += sizeof(size_t))
        {
            if (*(size_t *) p != 0)
                return false;
        }

        while (p < end)
        {
            if (*p++ != 0)
                return false;
        }
        return true;
    }

    /* Compare bytes until the pointer "p" is aligned */
    while (((uintptr_t) p & (sizeof(size_t) - 1)) != 0)
    {
        if (p == end)
            return true;

        if (*p++ != 0)
            return false;
    }

    /*
     * Compare 8 * sizeof(size_t) chunks at once.
     *
     * For performance reasons, we manually unroll this loop and purposefully
     * use bitwise-ORs to combine each comparison.  This prevents boolean
     * short-circuiting and lets the compiler know that it's safe to access
     * all 8 elements regardless of the result of the other comparisons.  This
     * seems to be enough to coax a few compilers into using SIMD
     * instructions.
     *
     * There is no risk to read beyond the memory area thanks to the len < 64
     * check done below.
     */
    for (; p < aligned_end - (sizeof(size_t) * 7); p += sizeof(size_t) * 8)
    {
        if ((((size_t *) p)[0] != 0) | (((size_t *) p)[1] != 0) |
            (((size_t *) p)[2] != 0) | (((size_t *) p)[3] != 0) |
            (((size_t *) p)[4] != 0) | (((size_t *) p)[5] != 0) |
            (((size_t *) p)[6] != 0) | (((size_t *) p)[7] != 0))
            return false;
    }

    /*
     * Compare remaining size_t-aligned chunks.
     *
     * aligned_end cant' be > end as we ensured to take care of len < 8 (in
     * the len < 64 check below). So, no risk to read beyond the memory area.
     */
    for (; p < aligned_end; p += sizeof(size_t))
    {
        if (*(size_t *) p != 0)
            return false;
    }

    /* Compare remaining bytes until the end */
    while (p < end)
    {
        if (*p++ != 0)
            return false;
    }

    return true;
}

static inline bool
all_zeros_simd(const size_t *p, const size_t * end)
{
    printf("p01=(%p)\n", p);
    printf("end=(%p)\n", end);
    for (; p < (end - sizeof(size_t) * 7); p += sizeof(size_t) * 8)
    {
        if ((((size_t *) p)[0] != 0) | (((size_t *) p)[1] != 0) |
            (((size_t *) p)[2] != 0) | (((size_t *) p)[3] != 0) |
            (((size_t *) p)[4] != 0) | (((size_t *) p)[5] != 0) |
            (((size_t *) p)[6] != 0) | (((size_t *) p)[7] != 0))
            return false;
    }
    for (; p < end; p += sizeof(size_t))
    {
        if (*(size_t *) p != 0)
            return false;
    }
    printf("p02=(%p)\n", p);

    return true;
}

static inline bool
pg_memory_is_all_zeros_v14(const void *ptr, size_t len)
{
    const unsigned char *p = (const unsigned char *) ptr;
    const unsigned char *end = &p[len];
    const unsigned char *aligned_end = (const unsigned char *)
        ((uintptr_t) end & (~(sizeof(size_t) - 1)));

    if ((len >= sizeof(size_t) * 8) && (((uintptr_t) p & (sizeof(size_t) - 1)) == 0))
    {
        return all_zeros_simd(ptr, ptr + len);
    }

    if (len < sizeof(size_t))
    {
        while (p < end)
        {
            if (*p++ != 0)
                return false;
        }
        return true;
    }
    else if (len < sizeof(size_t) * 8)
    {
        while (((uintptr_t) p & (sizeof(size_t) - 1)) != 0)
        {
            if (p == end)
                return true;
            if (*p++ != 0)
                return false;
        }

        for (; p < aligned_end; p += sizeof(size_t))
        {
            if (*(size_t *) p != 0)
                return false;
        }

        while (p < end)
        {
            if (*p++ != 0)
                return false;
        }
        return true;
    }

    /* Compare bytes until the pointer "p" is aligned */
    while (((uintptr_t) p & (sizeof(size_t) - 1)) != 0)
    {
        if (p == end)
            return true;

        if (*p++ != 0)
            return false;
    }

    /*
     * Compare 8 * sizeof(size_t) chunks at once.
     *

     * For performance reasons, we manually unroll this loop and purposefully

     * use bitwise-ORs to combine each comparison.  This prevents boolean
     * short-circuiting and lets the compiler know that it's safe to access

     * all 8 elements regardless of the result of the other comparisons.  This

     * seems to be enough to coax a few compilers into using SIMD
     * instructions.
     *

     * There is no risk to read beyond the memory area thanks to the len < 64
     * check done below.
     */
    for (; p < aligned_end - (sizeof(size_t) * 7); p += sizeof(size_t) * 8)
    {
        if ((((size_t *) p)[0] != 0) | (((size_t *) p)[1] != 0) |
            (((size_t *) p)[2] != 0) | (((size_t *) p)[3] != 0) |
            (((size_t *) p)[4] != 0) | (((size_t *) p)[5] != 0) |
            (((size_t *) p)[6] != 0) | (((size_t *) p)[7] != 0))
            return false;
    }

    /*
     * Compare remaining size_t-aligned chunks.
     *
     * aligned_end cant' be > end as we ensured to take care of len < 8 (in
     * the len < 64 check below). So, no risk to read beyond the memory area.
     */
    for (; p < aligned_end; p += sizeof(size_t))
    {
        if (*(size_t *) p != 0)
            return false;
    }

    /* Compare remaining bytes until the end */
    while (p < end)
    {
        if (*p++ != 0)
            return false;
    }

    return true;
}

#define NANOSEC_PER_SEC 1000000000

// Returns difference in nanoseconds
int64_t
get_clock_diff(struct timespec *t1, struct timespec *t2)
{
	int64_t nanosec = (t1->tv_sec - t2->tv_sec) * NANOSEC_PER_SEC;
	nanosec += (t1->tv_nsec - t2->tv_nsec);

	return nanosec;
}

int main()
{
	//size_t pagebytes[BLCKSZ] = {0};
	char pagebytes[BLCKSZ] = {0};
	volatile bool result;

        printf("sizeof(pagebytes)=%ld\n", sizeof(pagebytes));

        result = allzeros_byte_per_byte(pagebytes, BLCKSZ);
        printf("byte per byte: %s\n", (result?"is_allzeros":"not is allzeros"));

        result = allzeros_size_t(pagebytes, BLCKSZ);
        printf("size_t: %s\n", (result?"is_allzeros":"not is allzeros"));

        result = pg_memory_is_all_zeros_v10(pagebytes, BLCKSZ);
        printf("SIMD v10: %s\n", (result?"is_allzeros":"not is allzeros"));

        result = pg_memory_is_all_zeros_v11(pagebytes, BLCKSZ);
        printf("SIMD v11: %s\n", (result?"is_allzeros":"not is allzeros"));

	result = pg_memory_is_all_zeros_v12(pagebytes, BLCKSZ);
        printf("SIMD v12: %s\n", (result?"is_allzeros":"not is allzeros"));

	result = pg_memory_is_all_zeros_v14(pagebytes, BLCKSZ);
        printf("SIMD v14: %s\n", (result?"is_allzeros":"not is allzeros"));

	return 0;
}