c_src/hyper_carray.c

// Copyright (c) 2014 Johannes Huning <mail@johanneshuning.com>
// Copyright (c) 2015 Christian Lundgren, Chris de Vries, and Jon Elverkilde
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use, copy,
// modify, merge, publish, distribute, sublicense, and/or sell copies
// of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
//
// Format this file with
//     indent -kr -i8 -sob c_src/hyper_carray.c
// before committing.

#include <stdint.h>
#include <stdio.h>
#include <string.h>

#include "erl_nif.h"

/*
 * Erlang NIF resource type used to 'tag' hyper_carrays.
 */
static ErlNifResourceType *carray_resource;

/*
 * Single resource produced and consumed by these NIFs.
 * Header placed directly in front of the items it points to.
 */
struct hyper_carray {
	/*
	 * Precision = log_2(size). Handy to have it.
	 */
	unsigned int precision;
	/*
	 * Number of items.
	 */
	unsigned int size;
	/*
	 * Array of items each one byte in size.
	 */
	uint8_t *items;
};

#ifdef _WIN32
typedef struct hyper_carray *carray_ptr;
#else
typedef struct hyper_carray *restrict carray_ptr;
#endif

#define HYPER_CARRAY_SIZE sizeof(struct hyper_carray)

/*
 * Attempts to read a hyper_carray from _term into _varname.
 * Returns badarg on failure to do so.
 */
#define HYPER_CARRAY_OR_BADARG(_term, _varname) \
    void* _varname_res = NULL; \
    if (!enif_get_resource(env, _term, carray_resource, &_varname_res)) \
        return enif_make_badarg(env); \
    _varname = _varname_res;

/*
 * Allocate a new hyper_carray for use as an Erlang NIF resource.
 */
static void carray_alloc(unsigned int precision, carray_ptr * arr)
{
	unsigned int nitems = 0x01 << precision;
	size_t header_size = HYPER_CARRAY_SIZE;
	size_t res_size = header_size + nitems;

	void *res = enif_alloc_resource(carray_resource, res_size);
	*arr = res;

	memset(*arr, 0, header_size);
	(*arr)->precision = precision;
	(*arr)->size = nitems;
	(*arr)->items = (uint8_t *) res + header_size;
}

/*
 * Given an hyper_carray and a valid index, set the value at that index to
 * max(current value, given value).
 */
#ifdef _WIN32
static void carray_merge_item(carray_ptr arr,
				     unsigned int index,
				     unsigned int value)
#else
static inline void carray_merge_item(carray_ptr arr,
				     unsigned int index,
				     unsigned int value)
#endif
{
	uint8_t *item = arr->items + index;
	*item = (value > *item) ? value : *item;
}

/*
 * Create a new hyper_carray resource with all items set to 0.
 */
static ERL_NIF_TERM new_hyper_carray(ErlNifEnv * env, int argc,
				     const ERL_NIF_TERM argv[])
{
	unsigned int precision = 0;
	if (!enif_get_uint(env, argv[0], &precision))
		return enif_make_badarg(env);

	carray_ptr arr = NULL;
	carray_alloc(precision, &arr);
	memset(arr->items, 0, arr->size);

	ERL_NIF_TERM erl_res = enif_make_resource(env, arr);
	enif_release_resource(arr);
	return erl_res;
}

/*
 * NIF variant of carray_merge_item (see above).
 */
static ERL_NIF_TERM set(ErlNifEnv * env, int argc,
			const ERL_NIF_TERM argv[])
{
	carray_ptr arr = NULL;
	HYPER_CARRAY_OR_BADARG(argv[2], arr);

	unsigned int index = 0;
	unsigned int new_value = 0;
	if (!enif_get_uint(env, argv[0], &index)
	    || !enif_get_uint(env, argv[1], &new_value))
		return enif_make_badarg(env);

	// Validate bounds
	if (index > arr->size - 1)
		return enif_make_badarg(env);

	carray_merge_item(arr, index, new_value);

	return argv[2];
}

void dtor(ErlNifEnv * env, void *obj);

/*
 * Given a list of at least 1 hyper_carrays [A,B,...], merge into a single new
 * hyper_carray N. Where the i-ths item N[i] is max(A[i], B[i], ...).
 * A, B, and so on are assumed to be _different_ hyper_carrays.
 */
static ERL_NIF_TERM max_merge(ErlNifEnv * env, int argc,
			      const ERL_NIF_TERM argv[])
{
	unsigned int narrays = 0;
	ERL_NIF_TERM head;
	ERL_NIF_TERM tail;

	if (!enif_get_list_length(env, argv[0], &narrays)
	    || !enif_get_list_cell(env, argv[0], &head, &tail))
		return enif_make_badarg(env);

	if (narrays < 1)
		return enif_make_badarg(env);

	carray_ptr first = NULL;
	HYPER_CARRAY_OR_BADARG(head, first);
	const unsigned int nitems = first->size;

	carray_ptr acc = NULL;
	carray_alloc(first->precision, &acc);
	memcpy(acc->items, first->items, acc->size);

	// Merge arrays
	for (int i = 1; i < narrays; ++i) {
		carray_ptr curr = NULL;

		if (!enif_get_list_cell(env, tail, &head, &tail)
		    || !enif_get_resource(env, head, carray_resource,
					  (void *) &curr))
			goto dealloc_and_badarg;

		// Require uniform precision.
		if (curr->precision != acc->precision)
			goto dealloc_and_badarg;

		for (uint8_t * accitem = acc->items, *item = curr->items,
		     *enditem = curr->items + nitems;
		     item != enditem; ++item, ++accitem) {
			*accitem = (*item > *accitem) ? *item : *accitem;
		}

		continue;

	      dealloc_and_badarg:
		dtor(env, acc);
		return enif_make_badarg(env);
	}

	ERL_NIF_TERM erl_res = enif_make_resource(env, acc);
	enif_release_resource(acc);
	return erl_res;
}

/*
 * Return the total number of bytes allocated for the given hyper_carray.
 * Includes the header's size.
 */
static ERL_NIF_TERM bytes(ErlNifEnv * env, int argc,
			  const ERL_NIF_TERM argv[])
{
	carray_ptr arr = NULL;
	HYPER_CARRAY_OR_BADARG(argv[0], arr);
	return enif_make_int(env, HYPER_CARRAY_SIZE + arr->size);
}

/*
 * Sum over 2^-X where X is the value of each item in the given hyper_carray.
 */
static ERL_NIF_TERM register_sum(ErlNifEnv * env, int argc,
				 const ERL_NIF_TERM argv[])
{
	carray_ptr arr = NULL;
	HYPER_CARRAY_OR_BADARG(argv[0], arr);

	int currval = 0;
	double sum = 0.0;
	unsigned int size = arr->size;

	for (int i = 0; i < size; ++i) {
		currval = arr->items[i];
		sum += 1.0 / (double) (0x01 << currval);
	}

	return enif_make_double(env, sum);
}

/*
 * Number of items with a 0 as value;
 */
static ERL_NIF_TERM zero_count(ErlNifEnv * env, int argc,
			       const ERL_NIF_TERM argv[])
{
	carray_ptr arr = NULL;
	HYPER_CARRAY_OR_BADARG(argv[0], arr);

	unsigned int nzeros = 0;
	unsigned int size = arr->size;

	for (int i = 0; i < size; ++i) {
		if (arr->items[i] == 0)
			++nzeros;
	}

	return enif_make_int(env, nzeros);
}

/*
 * Encode the given hyper_carray as an Erlang binary.
 */
static ERL_NIF_TERM encode_registers(ErlNifEnv * env, int argc,
				     const ERL_NIF_TERM argv[])
{
	carray_ptr arr = NULL;
	HYPER_CARRAY_OR_BADARG(argv[0], arr);

	size_t nbytes = arr->size;

	ERL_NIF_TERM bin;
	unsigned char *buf = enif_make_new_binary(env, nbytes, &bin);
	memcpy(buf, arr->items, nbytes);

	return bin;
}

/*
 * Decode the given serialized hyper_carray into a new resource.
 */
static ERL_NIF_TERM decode_registers(ErlNifEnv * env, int argc,
				     const ERL_NIF_TERM argv[])
{
	unsigned int precision = 0;
	ErlNifBinary bin;

	if (!enif_get_uint(env, argv[1], &precision)
	    || !enif_inspect_binary(env, argv[0], &bin))
		return enif_make_badarg(env);

	carray_ptr arr = NULL;
	carray_alloc(precision, &arr);
	memcpy(arr->items, bin.data, arr->size);

	ERL_NIF_TERM erl_res = enif_make_resource(env, arr);
	enif_release_resource(arr);

	return erl_res;
}

/*
 * Map of funs to NIFs.
 */
static ErlNifFunc niftable[] = {
	{"new", 1, new_hyper_carray},
	{"set", 3, set},
	{"max_merge", 1, max_merge},
	{"bytes", 1, bytes},
	{"register_sum", 1, register_sum},
	{"zero_count", 1, zero_count},
	{"encode_registers", 1, encode_registers},
	{"decode_registers", 2, decode_registers}
};

/*
 * Destructor for hyper_carray resources.
 */
void dtor(ErlNifEnv * env, void *obj)
{
	enif_release_resource(obj);
}

/*
 * Creates or opens the hyper_carray resource _type_.
 * Registers dtor to be called on garbage collection of hyper_carrays.
 * Please see http://www.erlang.org/doc/man/erl_nif.html.
 */
static int load(ErlNifEnv * env, void **priv_data, ERL_NIF_TERM load_info)
{
	carray_resource =
	    enif_open_resource_type(env, NULL, "hyper_carray", &dtor,
				    ERL_NIF_RT_CREATE |
				    ERL_NIF_RT_TAKEOVER, 0);
	return 0;
}

/*
 * Called when the NIF library is loaded and there is old code of this module
 * with a loaded NIF library.
 */
static int upgrade(ErlNifEnv * env, void **priv, void **old_priv,
		   ERL_NIF_TERM load_info)
{
	*priv = *old_priv;
	return 0;
}

/*
 * Initialize the NIF library.
 */
ERL_NIF_INIT(hyper_carray, niftable, &load, NULL, &upgrade, NULL);