Merge pull request #3 from johannesh/hyper_carray
hyper_carray, a hyper_register implemented by a C-array
diff --git a/.gitignore b/.gitignore
index 6d8c311..be93a07 100644
--- a/.gitignore
+++ b/.gitignore
@@ -4,4 +4,6 @@
*~
hyper.png
estimates.csv
-erl_crash.dump
\ No newline at end of file
+erl_crash.dump
+*.so
+*.o
diff --git a/c_src/hyper_carray.c b/c_src/hyper_carray.c
new file mode 100644
index 0000000..554badd
--- /dev/null
+++ b/c_src/hyper_carray.c
@@ -0,0 +1,334 @@
+// Copyright (c) 2014 Johannes Huning <mail@johanneshuning.com>
+//
+// This program is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Lesser General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program. If not, see <http://www.gnu.org/licenses/>.
+
+#include <stdio.h>
+#include <string.h>
+#include <tgmath.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.
+ */
+ char *items;
+};
+
+#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,
+ struct hyper_carray *restrict * arr)
+{
+ unsigned int nitems = pow(2, 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 = res + header_size;
+}
+
+/*
+ * Given an hyper_carray and a valid index, set the value at that index to
+ * max(current value, given value).
+ */
+static inline void carray_merge_item(struct hyper_carray *restrict arr,
+ unsigned int index,
+ unsigned int value)
+{
+ char *item = arr->items + index;
+ if (value > *item)
+ *item = value;
+}
+
+/*
+ * 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);
+
+ struct hyper_carray *restrict 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[])
+{
+ struct hyper_carray *restrict 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 enif_make_resource(env, arr);
+}
+
+void dtor(ErlNifEnv * env, void *obj);
+
+/*
+ * Given a list of at least 2 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 < 2)
+ return enif_make_badarg(env);
+
+ void *tmp = NULL;
+ struct hyper_carray *restrict first = NULL;
+ struct hyper_carray *restrict acc = NULL;
+ struct hyper_carray *restrict curr = NULL;
+
+ HYPER_CARRAY_OR_BADARG(head, first);
+
+ carray_alloc(first->precision, &acc);
+ memcpy(acc->items, first->items, acc->size);
+
+ unsigned int nitems = 0;
+ for (int i = 1; i < narrays; ++i) {
+ if (!enif_get_list_cell(env, tail, &head, &tail)
+ || !enif_get_resource(env, head, carray_resource,
+ &tmp))
+ goto dealloc_and_badarg;
+ curr = tmp;
+
+ // Require uniform precision.
+ if (curr->precision != acc->precision)
+ goto dealloc_and_badarg;
+
+ nitems = curr->size;
+ for (int j = 0; j < nitems; ++j)
+ carray_merge_item(acc, j, curr->items[j]);
+
+ continue;
+
+ dealloc_and_badarg:
+ dtor(env, acc);
+ return enif_make_badarg(env);
+ }
+
+ return enif_make_resource(env, acc);
+}
+
+/*
+ * 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[])
+{
+ struct hyper_carray *restrict 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[])
+{
+ struct hyper_carray *restrict 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 += pow(2, -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[])
+{
+ struct hyper_carray *restrict 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[])
+{
+ struct hyper_carray *restrict arr = NULL;
+ HYPER_CARRAY_OR_BADARG(argv[0], arr);
+
+ size_t nbytes = HYPER_CARRAY_SIZE + arr->size;
+
+ ERL_NIF_TERM bin;
+ unsigned char *buf = enif_make_new_binary(env, nbytes, &bin);
+ memcpy(buf, arr, 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);
+
+ struct hyper_carray *restrict arr = NULL;
+ carray_alloc(precision, &arr);
+ memcpy(arr, bin.data, HYPER_CARRAY_SIZE + 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);
diff --git a/priv/.keep b/priv/.keep
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/priv/.keep
diff --git a/rebar.config b/rebar.config
index 47ba7fe..20a0778 100644
--- a/rebar.config
+++ b/rebar.config
@@ -3,3 +3,13 @@
{bisect, "",
{git, "https://github.com/knutin/bisect.git", {branch, "master"}}}
]}.
+
+
+{port_specs, [
+ {"priv/hyper_carray.so", ["c_src/hyper_carray.c"]}
+ ]}.
+
+{port_env, [
+ {"CC", "c99"},
+ {"CFLAGS", "$CFLAGS -Wall -Werror -O3"}
+ ]}.
diff --git a/src/hyper_carray.erl b/src/hyper_carray.erl
new file mode 100644
index 0000000..524a041
--- /dev/null
+++ b/src/hyper_carray.erl
@@ -0,0 +1,90 @@
+%% @doc
+%% Dummy module for the NIF implementation in {@link /c_src/hyper_carray.c}.
+-module (hyper_carray).
+
+-on_load(load_shared_obj/0).
+
+-behaviour(hyper_register).
+-export([new/1,
+ set/3,
+ max_merge/1,
+ max_merge/2,
+ bytes/1,
+ register_sum/1,
+ zero_count/1,
+ encode_registers/1,
+ decode_registers/2,
+ compact/1]).
+
+
+% Pull in the NIF.
+load_shared_obj() ->
+ EbinDir = filename:dirname(code:which(?MODULE)),
+ AppPath = filename:dirname(EbinDir),
+ Path = filename:join([AppPath, "priv", "hyper_carray"]),
+ ok = erlang:load_nif(Path, 0).
+
+
+% Nothing to do.
+compact(Handle) ->
+ Handle.
+
+
+% Delegate to generalization.
+max_merge(HandleA, HandleB) ->
+ max_merge([HandleA, HandleB]).
+
+
+% Returns badarg on:
+% - Precision is not a positive integer
+new(_Precision) ->
+ erlang:nif_error(nif_not_loaded).
+
+% Returns badarg on:
+% - Index is not a positive integer
+% - Value not a positive integer
+% - Handle is not a hyper_carray
+% Value is assumed to fit into one byte, that is within [0, 255]
+set(_Index, _Value, _Handle) ->
+ erlang:nif_error(nif_not_loaded).
+
+
+% Returns badarg on:
+% - Argument is not a list
+% - Argument is a list of less than 2 elements
+% - An element is not a hyper_carray
+% - The elements lack uniform precision
+% - Failure to obtain a list element (enif_get_list_cell)
+max_merge(_Handles) ->
+ erlang:nif_error(nif_not_loaded).
+
+
+% Returns badarg on:
+% - Handle is not a hyper_carray
+register_sum(_Handle) ->
+ erlang:nif_error(nif_not_loaded).
+
+
+% Returns badarg on:
+% - Handle is not a hyper_carray
+zero_count(_Handle) ->
+ erlang:nif_error(nif_not_loaded).
+
+
+% Returns badarg on:
+% - Handle is not a hyper_carray
+encode_registers(_Handle) ->
+ erlang:nif_error(nif_not_loaded).
+
+
+% Returns badarg on:
+% - First argument is not a binary
+% - Precision is not a positive integer
+decode_registers(_Binary, _Precision) ->
+ erlang:nif_error(nif_not_loaded).
+
+
+% Returns badarg on:
+% - Handle is not a hyper_carray
+bytes(_Handle) ->
+ erlang:nif_error(nif_not_loaded).
