ref: e2c6d0295c58c9f1c9ce6570e993530b6bc94b68
dir: /tests/checkasm/checkasm.c/
/*
* Copyright © 2018, VideoLAN and dav1d authors
* Copyright © 2018, Two Orioles, LLC
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "tests/checkasm/checkasm.h"
#include <math.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include "src/cpu.h"
#ifdef _WIN32
#include <windows.h>
#define COLOR_RED FOREGROUND_RED
#define COLOR_GREEN FOREGROUND_GREEN
#define COLOR_YELLOW (FOREGROUND_RED|FOREGROUND_GREEN)
static unsigned get_seed(void) {
return GetTickCount();
}
#else
#include <unistd.h>
#include <sys/time.h>
#define COLOR_RED 1
#define COLOR_GREEN 2
#define COLOR_YELLOW 3
static unsigned get_seed(void) {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_usec + tv.tv_sec * 1000000;
}
#endif
/* List of tests to invoke */
static const struct {
const char *name;
void (*func)(void);
} tests[] = {
#if CONFIG_8BPC
{ "cdef_8bpc", checkasm_check_cdef_8bpc },
{ "ipred_8bpc", checkasm_check_ipred_8bpc },
{ "itx_8bpc", checkasm_check_itx_8bpc },
{ "loopfilter_8bpc", checkasm_check_loopfilter_8bpc },
{ "looprestoration_8bpc", checkasm_check_looprestoration_8bpc },
{ "mc_8bpc", checkasm_check_mc_8bpc },
#endif
#if CONFIG_10BPC
{ "cdef_10bpc", checkasm_check_cdef_10bpc },
{ "ipred_10bpc", checkasm_check_ipred_10bpc },
{ "itx_10bpc", checkasm_check_itx_10bpc },
{ "loopfilter_10bpc", checkasm_check_loopfilter_10bpc },
{ "looprestoration_10bpc", checkasm_check_looprestoration_10bpc },
{ "mc_10bpc", checkasm_check_mc_10bpc },
#endif
{ 0 }
};
/* List of cpu flags to check */
static const struct {
const char *name;
const char *suffix;
unsigned flag;
} cpus[] = {
#if ARCH_X86
{ "SSE", "sse", DAV1D_X86_CPU_FLAG_SSE },
{ "SSE2", "sse2", DAV1D_X86_CPU_FLAG_SSE2 },
{ "SSE3", "sse3", DAV1D_X86_CPU_FLAG_SSE3 },
{ "SSSE3", "ssse3", DAV1D_X86_CPU_FLAG_SSSE3 },
{ "SSE4.1", "sse4", DAV1D_X86_CPU_FLAG_SSE41 },
{ "SSE4.2", "sse42", DAV1D_X86_CPU_FLAG_SSE42 },
{ "AVX", "avx", DAV1D_X86_CPU_FLAG_AVX },
{ "AVX2", "avx2", DAV1D_X86_CPU_FLAG_AVX2 },
{ "AVX-512", "avx512", DAV1D_X86_CPU_FLAG_AVX512 },
#elif ARCH_AARCH64 || ARCH_ARM
{ "NEON", "neon", DAV1D_ARM_CPU_FLAG_NEON },
#endif
{ 0 }
};
typedef struct CheckasmFuncVersion {
struct CheckasmFuncVersion *next;
void *func;
int ok;
unsigned cpu;
int iterations;
uint64_t cycles;
} CheckasmFuncVersion;
/* Binary search tree node */
typedef struct CheckasmFunc {
struct CheckasmFunc *child[2];
CheckasmFuncVersion versions;
uint8_t color; /* 0 = red, 1 = black */
char name[1];
} CheckasmFunc;
/* Internal state */
static struct {
CheckasmFunc *funcs;
CheckasmFunc *current_func;
CheckasmFuncVersion *current_func_ver;
const char *current_test_name;
const char *bench_pattern;
int bench_pattern_len;
int num_checked;
int num_failed;
int nop_time;
unsigned cpu_flag;
const char *cpu_flag_name;
const char *test_name;
} state;
/* float compare support code */
typedef union {
float f;
uint32_t i;
} intfloat;
static int is_negative(const intfloat u) {
return u.i >> 31;
}
int float_near_ulp(const float a, const float b, const unsigned max_ulp) {
intfloat x, y;
x.f = a;
y.f = b;
if (is_negative(x) != is_negative(y)) {
// handle -0.0 == +0.0
return a == b;
}
if (llabs((int64_t)x.i - y.i) <= max_ulp)
return 1;
return 0;
}
int float_near_ulp_array(const float *const a, const float *const b,
const unsigned max_ulp, const int len)
{
for (int i = 0; i < len; i++)
if (!float_near_ulp(a[i], b[i], max_ulp))
return 0;
return 1;
}
int float_near_abs_eps(const float a, const float b, const float eps) {
return fabsf(a - b) < eps;
}
int float_near_abs_eps_array(const float *const a, const float *const b,
const float eps, const int len)
{
for (int i = 0; i < len; i++)
if (!float_near_abs_eps(a[i], b[i], eps))
return 0;
return 1;
}
int float_near_abs_eps_ulp(const float a, const float b, const float eps,
const unsigned max_ulp)
{
return float_near_ulp(a, b, max_ulp) || float_near_abs_eps(a, b, eps);
}
int float_near_abs_eps_array_ulp(const float *const a, const float *const b,
const float eps, const unsigned max_ulp,
const int len)
{
for (int i = 0; i < len; i++)
if (!float_near_abs_eps_ulp(a[i], b[i], eps, max_ulp))
return 0;
return 1;
}
/* Print colored text to stderr if the terminal supports it */
static void color_printf(const int color, const char *const fmt, ...) {
static int8_t use_color = -1;
va_list arg;
#ifdef _WIN32
static HANDLE con;
static WORD org_attributes;
if (use_color < 0) {
CONSOLE_SCREEN_BUFFER_INFO con_info;
con = GetStdHandle(STD_ERROR_HANDLE);
if (con && con != INVALID_HANDLE_VALUE &&
GetConsoleScreenBufferInfo(con, &con_info))
{
org_attributes = con_info.wAttributes;
use_color = 1;
} else
use_color = 0;
}
if (use_color)
SetConsoleTextAttribute(con, (org_attributes & 0xfff0) |
(color & 0x0f));
#else
if (use_color < 0) {
const char *const term = getenv("TERM");
use_color = term && strcmp(term, "dumb") && isatty(2);
}
if (use_color)
fprintf(stderr, "\x1b[%d;3%dm", (color & 0x08) >> 3, color & 0x07);
#endif
va_start(arg, fmt);
vfprintf(stderr, fmt, arg);
va_end(arg);
if (use_color) {
#ifdef _WIN32
SetConsoleTextAttribute(con, org_attributes);
#else
fprintf(stderr, "\x1b[0m");
#endif
}
}
/* Deallocate a tree */
static void destroy_func_tree(CheckasmFunc *const f) {
if (f) {
CheckasmFuncVersion *v = f->versions.next;
while (v) {
CheckasmFuncVersion *next = v->next;
free(v);
v = next;
}
destroy_func_tree(f->child[0]);
destroy_func_tree(f->child[1]);
free(f);
}
}
/* Allocate a zero-initialized block, clean up and exit on failure */
static void *checkasm_malloc(const size_t size) {
void *const ptr = calloc(1, size);
if (!ptr) {
fprintf(stderr, "checkasm: malloc failed\n");
destroy_func_tree(state.funcs);
exit(1);
}
return ptr;
}
/* Get the suffix of the specified cpu flag */
static const char *cpu_suffix(const unsigned cpu) {
for (int i = (int)(sizeof(cpus) / sizeof(*cpus)) - 2; i >= 0; i--)
if (cpu & cpus[i].flag)
return cpus[i].suffix;
return "c";
}
#ifdef readtime
static int cmp_nop(const void *a, const void *b) {
return *(const uint16_t*)a - *(const uint16_t*)b;
}
/* Measure the overhead of the timing code (in decicycles) */
static int measure_nop_time(void) {
uint16_t nops[10000];
int i, nop_sum = 0;
for (i = 0; i < 10000; i++) {
uint64_t t = readtime();
nops[i] = readtime() - t;
}
qsort(nops, 10000, sizeof(uint16_t), cmp_nop);
for (i = 2500; i < 7500; i++)
nop_sum += nops[i];
return nop_sum / 500;
}
/* Print benchmark results */
static void print_benchs(const CheckasmFunc *const f) {
if (f) {
print_benchs(f->child[0]);
/* Only print functions with at least one assembly version */
if (f->versions.cpu || f->versions.next) {
const CheckasmFuncVersion *v = &f->versions;
do {
if (v->iterations) {
int decicycles = (10*v->cycles/v->iterations -
state.nop_time) / 4;
printf("%s_%s: %d.%d\n", f->name, cpu_suffix(v->cpu),
decicycles/10, decicycles%10);
}
} while ((v = v->next));
}
print_benchs(f->child[1]);
}
}
#endif
#define is_digit(x) ((x) >= '0' && (x) <= '9')
/* ASCIIbetical sort except preserving natural order for numbers */
static int cmp_func_names(const char *a, const char *b) {
const char *const start = a;
int ascii_diff, digit_diff;
for (; !(ascii_diff = *(const unsigned char*)a -
*(const unsigned char*)b) && *a; a++, b++);
for (; is_digit(*a) && is_digit(*b); a++, b++);
if (a > start && is_digit(a[-1]) &&
(digit_diff = is_digit(*a) - is_digit(*b)))
{
return digit_diff;
}
return ascii_diff;
}
/* Perform a tree rotation in the specified direction and return the new root */
static CheckasmFunc *rotate_tree(CheckasmFunc *const f, const int dir) {
CheckasmFunc *const r = f->child[dir^1];
f->child[dir^1] = r->child[dir];
r->child[dir] = f;
r->color = f->color;
f->color = 0;
return r;
}
#define is_red(f) ((f) && !(f)->color)
/* Balance a left-leaning red-black tree at the specified node */
static void balance_tree(CheckasmFunc **root) {
CheckasmFunc *const f = *root;
if (is_red(f->child[0]) && is_red(f->child[1])) {
f->color ^= 1;
f->child[0]->color = f->child[1]->color = 1;
}
else if (!is_red(f->child[0]) && is_red(f->child[1]))
*root = rotate_tree(f, 0); /* Rotate left */
else if (is_red(f->child[0]) && is_red(f->child[0]->child[0]))
*root = rotate_tree(f, 1); /* Rotate right */
}
/* Get a node with the specified name, creating it if it doesn't exist */
static CheckasmFunc *get_func(CheckasmFunc **root, const char *const name) {
CheckasmFunc *f = *root;
if (f) {
/* Search the tree for a matching node */
int cmp = cmp_func_names(name, f->name);
if (cmp) {
f = get_func(&f->child[cmp > 0], name);
/* Rebalance the tree on the way up if a new node was inserted */
if (!f->versions.func)
balance_tree(root);
}
} else {
/* Allocate and insert a new node into the tree */
const int name_length = strlen(name);
f = *root = checkasm_malloc(sizeof(CheckasmFunc) + name_length);
memcpy(f->name, name, name_length + 1);
}
return f;
}
/* Perform tests and benchmarks for the specified
* cpu flag if supported by the host */
static void check_cpu_flag(const char *const name, unsigned flag) {
const unsigned old_cpu_flag = state.cpu_flag;
flag |= old_cpu_flag;
dav1d_set_cpu_flags_mask(flag);
state.cpu_flag = dav1d_get_cpu_flags();
if (!flag || state.cpu_flag != old_cpu_flag) {
state.cpu_flag_name = name;
for (int i = 0; tests[i].func; i++) {
if (state.test_name && strcmp(tests[i].name, state.test_name))
continue;
state.current_test_name = tests[i].name;
tests[i].func();
}
}
}
/* Print the name of the current CPU flag, but only do it once */
static void print_cpu_name(void) {
if (state.cpu_flag_name) {
color_printf(COLOR_YELLOW, "%s:\n", state.cpu_flag_name);
state.cpu_flag_name = NULL;
}
}
int main(int argc, char *argv[]) {
(void)func_new, (void)func_ref;
unsigned int seed = get_seed();
int ret = 0;
while (argc > 1) {
if (!strncmp(argv[1], "--bench", 7)) {
#ifndef readtime
fprintf(stderr,
"checkasm: --bench is not supported on your system\n");
return 1;
#endif
if (argv[1][7] == '=') {
state.bench_pattern = argv[1] + 8;
state.bench_pattern_len = strlen(state.bench_pattern);
} else
state.bench_pattern = "";
} else if (!strncmp(argv[1], "--test=", 7)) {
state.test_name = argv[1] + 7;
} else {
seed = strtoul(argv[1], NULL, 10);
}
argc--;
argv++;
}
fprintf(stderr, "checkasm: using random seed %u\n", seed);
srand(seed);
check_cpu_flag(NULL, 0);
for (int i = 0; cpus[i].flag; i++)
check_cpu_flag(cpus[i].name, cpus[i].flag);
if (!state.num_checked) {
fprintf(stderr, "checkasm: no tests to perform\n");
} else if (state.num_failed) {
fprintf(stderr, "checkasm: %d of %d tests have failed\n",
state.num_failed, state.num_checked);
ret = 1;
} else {
fprintf(stderr, "checkasm: all %d tests passed\n", state.num_checked);
#ifdef readtime
if (state.bench_pattern) {
state.nop_time = measure_nop_time();
printf("nop: %d.%d\n", state.nop_time/10, state.nop_time%10);
print_benchs(state.funcs);
}
#endif
}
destroy_func_tree(state.funcs);
return ret;
}
/* Decide whether or not the specified function needs to be tested and
* allocate/initialize data structures if needed. Returns a pointer to a
* reference function if the function should be tested, otherwise NULL */
void *checkasm_check_func(void *const func, const char *const name, ...) {
char name_buf[256];
va_list arg;
va_start(arg, name);
const int name_length = vsnprintf(name_buf, sizeof(name_buf), name, arg);
va_end(arg);
if (!func || name_length <= 0 || (size_t)name_length >= sizeof(name_buf))
return NULL;
state.current_func = get_func(&state.funcs, name_buf);
state.funcs->color = 1;
CheckasmFuncVersion *v = &state.current_func->versions;
void *ref = func;
if (v->func) {
CheckasmFuncVersion *prev;
do {
/* Only test functions that haven't already been tested */
if (v->func == func)
return NULL;
if (v->ok)
ref = v->func;
prev = v;
} while ((v = v->next));
v = prev->next = checkasm_malloc(sizeof(CheckasmFuncVersion));
}
v->func = func;
v->ok = 1;
v->cpu = state.cpu_flag;
state.current_func_ver = v;
if (state.cpu_flag)
state.num_checked++;
return ref;
}
/* Decide whether or not the current function needs to be benchmarked */
int checkasm_bench_func(void) {
return !state.num_failed && state.bench_pattern &&
!strncmp(state.current_func->name, state.bench_pattern,
state.bench_pattern_len);
}
/* Indicate that the current test has failed */
void checkasm_fail_func(const char *const msg, ...) {
if (state.current_func_ver->cpu && state.current_func_ver->ok) {
va_list arg;
print_cpu_name();
fprintf(stderr, " %s_%s (", state.current_func->name,
cpu_suffix(state.current_func_ver->cpu));
va_start(arg, msg);
vfprintf(stderr, msg, arg);
va_end(arg);
fprintf(stderr, ")\n");
state.current_func_ver->ok = 0;
state.num_failed++;
}
}
/* Update benchmark results of the current function */
void checkasm_update_bench(const int iterations, const uint64_t cycles) {
state.current_func_ver->iterations += iterations;
state.current_func_ver->cycles += cycles;
}
/* Print the outcome of all tests performed since
* the last time this function was called */
void checkasm_report(const char *const name, ...) {
static int prev_checked, prev_failed, max_length;
if (state.num_checked > prev_checked) {
int pad_length = max_length + 4;
va_list arg;
print_cpu_name();
pad_length -= fprintf(stderr, " - %s.", state.current_test_name);
va_start(arg, name);
pad_length -= vfprintf(stderr, name, arg);
va_end(arg);
fprintf(stderr, "%*c", imax(pad_length, 0) + 2, '[');
if (state.num_failed == prev_failed)
color_printf(COLOR_GREEN, "OK");
else
color_printf(COLOR_RED, "FAILED");
fprintf(stderr, "]\n");
prev_checked = state.num_checked;
prev_failed = state.num_failed;
} else if (!state.cpu_flag) {
/* Calculate the amount of padding required
* to make the output vertically aligned */
int length = strlen(state.current_test_name);
va_list arg;
va_start(arg, name);
length += vsnprintf(NULL, 0, name, arg);
va_end(arg);
if (length > max_length)
max_length = length;
}
}