#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#define CLOCKS_PER_MSEC (CLOCKS_PER_SEC/1000)
#define TRUE (0 == 0)
#define FALSE (!TRUE)
// 8 bit integers
int are_non_negatives_naive_i8(int8_t *a, size_t n)
{
size_t i;
for (i = 0; i < n; ++i)
if (a[i] < 0)
return FALSE;
return TRUE;
}
int are_non_negatives_unrolled_i8(int8_t *a, size_t n)
{
size_t M = (n + 7) / 8;
size_t i = 0;
switch (n % 8) {
case 0: do { if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
} while (--M > 0);
}
}
int are_non_negatives_unrolled_masked_i8(int8_t *a, size_t n)
{
int8_t _i8[8] = { INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN };
uint64_t mask = *(uint64_t *)_i8;
uint64_t *it = (uint64_t *)a;
size_t i = 0;
switch (n % 8) {
case 0: if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
}
size_t N = n / 8;
// for (i = 0; i < N; ++i)
// if (it[i] & mask)
// return FALSE;
size_t M = (N + 7) / 8;
switch (N % 8) {
case 0: do { if (it[i++] & mask) return FALSE;
case 7: if (it[i++] & mask) return FALSE;
case 6: if (it[i++] & mask) return FALSE;
case 5: if (it[i++] & mask) return FALSE;
case 4: if (it[i++] & mask) return FALSE;
case 3: if (it[i++] & mask) return FALSE;
case 2: if (it[i++] & mask) return FALSE;
case 1: if (it[i++] & mask) return FALSE;
} while (--M > 0);
}
return TRUE;
}
int are_non_negatives_chunks_i8(const int8_t *start, int n) {
int8_t combined;
for (; n >= 8; n -= 8, start += 8) {
combined = (start[0] | start[1] | start[2] | start[3] |
start[4] | start[5] | start[6] | start[7]);
if (combined < 0)
return 0;
}
combined = 0;
while (n --> 0) {
combined |= *start++;
}
return combined >= 0;
}
//----------------------------------------------------------------
// 16 bit integers
int are_non_negatives_naive_i16(int16_t *a, size_t n)
{
size_t i;
for (i = 0; i < n; ++i)
if (a[i] < 0)
return FALSE;
return TRUE;
}
int are_non_negatives_unrolled_i16(int16_t *a, size_t n)
{
size_t M = (n + 7) / 8;
size_t i = 0;
switch (n % 8) {
case 0: do { if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
} while (--M > 0);
}
}
int are_non_negatives_unrolled_masked_i16(int16_t *a, size_t n)
{
int16_t _i16[4] = { INT16_MIN, INT16_MIN, INT16_MIN, INT16_MIN };
uint64_t mask = *(uint64_t *)_i16;
uint64_t *it = (uint64_t *)a;
size_t i = 0;
switch (n % 8) {
case 0: if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
}
size_t N = n / 4;
// for (i = 0; i < N; ++i)
// if (it[i] & mask)
// return FALSE;
size_t M = (N + 7) / 8;
switch (N % 8) {
case 0: do { if (it[i++] & mask) return FALSE;
case 7: if (it[i++] & mask) return FALSE;
case 6: if (it[i++] & mask) return FALSE;
case 5: if (it[i++] & mask) return FALSE;
case 4: if (it[i++] & mask) return FALSE;
case 3: if (it[i++] & mask) return FALSE;
case 2: if (it[i++] & mask) return FALSE;
case 1: if (it[i++] & mask) return FALSE;
} while (--M > 0);
}
return TRUE;
}
int are_non_negatives_chunks_i16(const int16_t *start, int n) {
int16_t combined;
for (; n >= 8; n -= 8, start += 8) {
combined = (start[0] | start[1] | start[2] | start[3] |
start[4] | start[5] | start[6] | start[7]);
if (combined < 0)
return 0;
}
combined = 0;
while (n --> 0) {
combined |= *start++;
}
return combined >= 0;
}
//----------------------------------------------------------------
// 32 bit integers
int are_non_negatives_naive_i32(int32_t *a, size_t n)
{
size_t i;
for (i = 0; i < n; ++i)
if (a[i] < 0)
return FALSE;
return TRUE;
}
int are_non_negatives_unrolled_i32(int32_t *a, size_t n)
{
size_t M = (n + 7) / 8;
size_t i = 0;
switch (n % 8) {
case 0: do { if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
} while (--M > 0);
}
}
int are_non_negatives_unrolled_masked_i32(int32_t *a, size_t n)
{
int32_t _i32[2] = { INT32_MIN, INT32_MIN };
uint64_t mask = *(uint64_t *)_i32;
uint64_t *it = (uint64_t *)a;
size_t i = 0;
switch (n % 8) {
case 0: if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
}
size_t N = n / 2;
// for (i = 0; i < N; ++i)
// if (it[i] & mask)
// return FALSE;
size_t M = (N + 7) / 8;
switch (N % 8) {
case 0: do { if (it[i++] & mask) return FALSE;
case 7: if (it[i++] & mask) return FALSE;
case 6: if (it[i++] & mask) return FALSE;
case 5: if (it[i++] & mask) return FALSE;
case 4: if (it[i++] & mask) return FALSE;
case 3: if (it[i++] & mask) return FALSE;
case 2: if (it[i++] & mask) return FALSE;
case 1: if (it[i++] & mask) return FALSE;
} while (--M > 0);
}
return TRUE;
}
int are_non_negatives_chunks_i32(const int32_t *start, int n) {
int32_t combined;
for (; n >= 8; n -= 8, start += 8) {
combined = (start[0] | start[1] | start[2] | start[3] |
start[4] | start[5] | start[6] | start[7]);
if (combined < 0)
return 0;
}
combined = 0;
while (n --> 0) {
combined |= *start++;
}
return combined >= 0;
}
//----------------------------------------------------------------
void fill_array(void *array, size_t type, size_t n, int contains_negatives)
{
size_t i;
switch (type) {
case 1: {
int8_t *a = array;
for (i = 0; i < n; ++i)
a[i] = rand() % INT8_MAX;
break;
}
case 2: {
int16_t *a = array;
for (i = 0; i < n; ++i)
a[i] = rand() % INT16_MAX;
break;
}
case 4: {
int32_t *a = array;
for (i = 0; i < n; ++i)
a[i] = rand() % INT32_MAX;
break;
}
case 8: {
int64_t *a = array;
for (i = 0; i < n; ++i)
a[i] = rand();
break;
}
}
if (contains_negatives) {
int how_many = rand() % n;
for (int i; i < how_many; ++i) {
int j = rand() % n;
switch (type) {
case 1: {
int8_t *a = array;
a[j] *= -1;
break;
}
case 2: {
int16_t *a = array;
a[j] *= -1;
break;
}
case 4: {
int32_t *a = array;
a[j] *= -1;
break;
}
case 8: {
int64_t *a = array;
a[j] *= -1;
break;
}
}
}
}
}
int main()
{
time_t t;
clock_t clock_start;
clock_t clock_end;
clock_t clock_naive = 0;
clock_t clock_unrolled = 0;
clock_t clock_unrolled_masked = 0;
clock_t clock_chunks = 0;
/* Intializes random number generator */
srand((unsigned long) time(&t));
printf("8 bit integers\n");
printf("----------------------------------------------------------------\n");
int8_t *array_i8;
for (int i = 3; i < 7; ++i) {
size_t size = pow(10, i);
array_i8 = malloc(size * sizeof(int8_t));
printf("------------------------------------------------\n");
printf("%lu elements\n", size);
for (int has_neg = 0; has_neg < 2; ++has_neg) {
printf("--------------------------------\n");
printf("Has negatives: %s\n", has_neg ? "yes": "no");
fill_array(array_i8, sizeof(int8_t), size, has_neg);
int neg_naive;
int neg_unrolled;
int neg_unrolled_masked;
int neg_chunks;
clock_start = clock();
neg_naive = are_non_negatives_naive_i8(array_i8, size);
clock_end = clock();
clock_naive = clock_end - clock_start;
clock_start = clock();
neg_unrolled = are_non_negatives_unrolled_i8(array_i8, size);
clock_end = clock();
clock_unrolled = clock_end - clock_start;
clock_start = clock();
neg_unrolled_masked = are_non_negatives_unrolled_masked_i8(array_i8, size);
clock_end = clock();
clock_unrolled_masked = clock_end - clock_start;
clock_start = clock();
neg_chunks = are_non_negatives_chunks_i8(array_i8, size);
clock_end = clock();
clock_chunks = clock_end - clock_start;
if (!has_neg) {
if (!neg_naive)
printf("Error: neg_naive\n");
if (!neg_unrolled)
printf("Error: neg_unrolled\n");
if (!neg_unrolled_masked)
printf("Error: neg_unrolled_masked\n");
if (!neg_chunks)
printf("Error: neg_unrolled_masked\n");
}
printf(" clock_naive: %lu\n", clock_naive);
printf(" clock_unrolled: %lu\n", clock_unrolled);
printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
printf(" clock_chunks: %lu\n", clock_chunks);
printf("--------------------------------\n");
}
printf("------------------------------------------------\n");
free (array_i8);
array_i8 = NULL;
}
printf("----------------------------------------------------------------\n");
printf("16 bit integers\n");
printf("----------------------------------------------------------------\n");
int16_t *array_i16;
for (int i = 3; i < 7; ++i) {
size_t size = pow(10, i);
array_i16 = malloc(size * sizeof(int16_t));
printf("------------------------------------------------\n");
printf("%lu elements\n", size);
for (int has_neg = 0; has_neg < 2; ++has_neg) {
printf("--------------------------------\n");
printf("Has negatives: %s\n", has_neg ? "yes": "no");
fill_array(array_i16, sizeof(int16_t), size, has_neg);
int neg_naive;
int neg_unrolled;
int neg_unrolled_masked;
int neg_chunks;
clock_start = clock();
neg_naive = are_non_negatives_naive_i16(array_i16, size);
clock_end = clock();
clock_naive = clock_end - clock_start;
clock_start = clock();
neg_unrolled = are_non_negatives_unrolled_i16(array_i16, size);
clock_end = clock();
clock_unrolled = clock_end - clock_start;
clock_start = clock();
neg_unrolled_masked = are_non_negatives_unrolled_masked_i16(array_i16, size);
clock_end = clock();
clock_unrolled_masked = clock_end - clock_start;
clock_start = clock();
neg_chunks = are_non_negatives_chunks_i16(array_i16, size);
clock_end = clock();
clock_chunks = clock_end - clock_start;
if (!has_neg) {
if (!neg_naive)
printf("Error: neg_naive\n");
if (!neg_unrolled)
printf("Error: neg_unrolled\n");
if (!neg_unrolled_masked)
printf("Error: neg_unrolled_masked\n");
if (!neg_chunks)
printf("Error: neg_unrolled_masked\n");
}
printf(" clock_naive: %lu\n", clock_naive);
printf(" clock_unrolled: %lu\n", clock_unrolled);
printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
printf(" clock_chunks: %lu\n", clock_chunks);
printf("--------------------------------\n");
}
printf("------------------------------------------------\n");
free (array_i16);
array_i16 = NULL;
}
printf("----------------------------------------------------------------\n");
printf("32 bit integers\n");
printf("----------------------------------------------------------------\n");
int32_t *array_i32;
for (int i = 3; i < 7; ++i) {
size_t size = pow(10, i);
array_i32 = malloc(size * sizeof(int32_t));
printf("------------------------------------------------\n");
printf("%lu elements\n", size);
for (int has_neg = 0; has_neg < 2; ++has_neg) {
printf("--------------------------------\n");
printf("Has negatives: %s\n", has_neg ? "yes": "no");
fill_array(array_i32, sizeof(int32_t), size, has_neg);
int neg_naive;
int neg_unrolled;
int neg_unrolled_masked;
int neg_chunks;
clock_start = clock();
neg_naive = are_non_negatives_naive_i32(array_i32, size);
clock_end = clock();
clock_naive = clock_end - clock_start;
clock_start = clock();
neg_unrolled = are_non_negatives_unrolled_i32(array_i32, size);
clock_end = clock();
clock_unrolled = clock_end - clock_start;
clock_start = clock();
neg_unrolled_masked = are_non_negatives_unrolled_masked_i32(array_i32, size);
clock_end = clock();
clock_unrolled_masked = clock_end - clock_start;
clock_start = clock();
neg_chunks = are_non_negatives_chunks_i32(array_i32, size);
clock_end = clock();
clock_chunks = clock_end - clock_start;
if (!has_neg) {
if (!neg_naive)
printf("Error: neg_naive\n");
if (!neg_unrolled)
printf("Error: neg_unrolled\n");
if (!neg_unrolled_masked)
printf("Error: neg_unrolled_masked\n");
if (!neg_chunks)
printf("Error: neg_unrolled_masked\n");
}
printf(" clock_naive: %lu\n", clock_naive);
printf(" clock_unrolled: %lu\n", clock_unrolled);
printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
printf(" clock_chunks: %lu\n", clock_chunks);
printf("--------------------------------\n");
}
printf("------------------------------------------------\n");
free (array_i32);
array_i32 = NULL;
}
printf("----------------------------------------------------------------\n");
}
