source: mainline/uspace/lib/bithenge/transform.c@ 1f136a27

/*
 * Copyright (c) 2012 Sean Bartell
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - 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.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
 */

/** @addtogroup bithenge
 * @{
 */
/**
 * @file
 * Transforms.
 */

#include <assert.h>
#include <errno.h>
#include <stdarg.h>
#include <stdlib.h>
#include "blob.h"
#include "os.h"
#include "print.h"
#include "transform.h"



/***************** transform                                 *****************/

/** Initialize a new transform.
 * @param[out] self Transform to initialize.
 * @param[in] ops Operations provided by the transform.
 * @param num_params The number of parameters required. If this is nonzero, the
 * transform will get its own context with parameters, probably provided by a
 * param_wrapper. If this is zero, the existing outer context will be used with
 * whatever parameters it has, so they can be passed to any param_wrappers
 * within.
 * @return EOK or an error code from errno.h. */
int bithenge_init_transform(bithenge_transform_t *self,
    const bithenge_transform_ops_t *ops, int num_params)
{
        assert(ops);
        assert(ops->apply || ops->prefix_apply);
        assert(ops->destroy);
        if (bithenge_should_fail())
                return ENOMEM;
        self->ops = ops;
        self->refs = 1;
        self->num_params = num_params;
        return EOK;
}

static void transform_indestructible(bithenge_transform_t *self)
{
        assert(false);
}

/** Apply a transform. Takes ownership of nothing.
 * @memberof bithenge_transform_t
 * @param self The transform.
 * @param scope The scope.
 * @param in The input tree.
 * @param[out] out Where the output tree will be stored.
 * @return EOK on success or an error code from errno.h. */
int bithenge_transform_apply(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out)
{
        assert(self);
        assert(self->ops);
        if (self->ops->apply)
                return self->ops->apply(self, scope, in, out);

        if (bithenge_node_type(in) != BITHENGE_NODE_BLOB)
                return EINVAL;
        aoff64_t self_size, whole_size;
        int rc = bithenge_transform_prefix_apply(self, scope,
            bithenge_node_as_blob(in), out, &self_size);
        if (rc != EOK)
                return rc;
        rc = bithenge_blob_size(bithenge_node_as_blob(in), &whole_size);
        if (rc == EOK && whole_size != self_size)
                rc = EINVAL;
        if (rc != EOK) {
                bithenge_node_dec_ref(*out);
                return rc;
        }
        return EOK;
}

/** Find the length of the prefix of a blob this transform can use as input. In
 * other words, figure out how many bytes this transform will use up.  This
 * method is optional and can return an error, but it must succeed for struct
 * subtransforms. Takes ownership of nothing.
 * @memberof bithenge_transform_t
 * @param self The transform.
 * @param scope The scope.
 * @param blob The blob.
 * @param[out] out Where the prefix length will be stored.
 * @return EOK on success, ENOTSUP if not supported, or another error code from
 * errno.h. */
int bithenge_transform_prefix_length(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_blob_t *blob, aoff64_t *out)
{
        assert(self);
        assert(self->ops);
        if (self->ops->prefix_length)
                return self->ops->prefix_length(self, scope, blob, out);
        if (!self->ops->prefix_apply)
                return ENOTSUP;

        bithenge_node_t *node;
        int rc = bithenge_transform_prefix_apply(self, scope, blob, &node,
            out);
        if (rc != EOK)
                return rc;
        bithenge_node_dec_ref(node);
        return EOK;
}

/** Apply this transform to a prefix of a blob. In other words, feed as much of
 * the blob into this transform as possible. Takes ownership of nothing.
 * @memberof bithenge_transform_t
 * @param self The transform.
 * @param scope The scope.
 * @param blob The blob.
 * @param[out] out_node Holds the result of applying this transform to the
 * prefix.
 * @param[out] out_size Holds the size of the prefix. Can be null, in which
 * case the size is not determined.
 * @return EOK on success, ENOTSUP if not supported, or another error code from
 * errno.h. */
int bithenge_transform_prefix_apply(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node,
    aoff64_t *out_size)
{
        assert(self);
        assert(self->ops);
        if (self->ops->prefix_apply)
                return self->ops->prefix_apply(self, scope, blob, out_node,
                    out_size);
        if (!self->ops->prefix_length)
                return ENOTSUP;

        aoff64_t size;
        int rc = bithenge_transform_prefix_length(self, scope, blob, &size);
        if (rc != EOK)
                return rc;
        bithenge_node_t *prefix_blob;
        bithenge_blob_inc_ref(blob);
        rc = bithenge_new_subblob(&prefix_blob, blob, 0, size);
        if (rc != EOK)
                return rc;
        rc = bithenge_transform_apply(self, scope, prefix_blob, out_node);
        bithenge_node_dec_ref(prefix_blob);
        if (out_size)
                *out_size = size;
        return rc;
}



/***************** scope                                     *****************/

/** Create a transform scope. It must be dereferenced with @a
 * bithenge_scope_dec_ref after it is used. Takes ownership of nothing.
 * @memberof bithenge_scope_t
 * @param[out] out Holds the new scope.
 * @param outer The outer scope, or NULL.
 * @return EOK on success or an error code from errno.h. */
int bithenge_scope_new(bithenge_scope_t **out, bithenge_scope_t *outer)
{
        bithenge_scope_t *self = malloc(sizeof(*self));
        if (!self)
                return ENOMEM;
        self->refs = 1;
        if (outer)
                bithenge_scope_inc_ref(outer);
        self->outer = outer;
        self->error = NULL;
        self->barrier = false;
        self->num_params = 0;
        self->params = NULL;
        self->current_node = NULL;
        self->in_node = NULL;
        *out = self;
        return EOK;
}

/** Dereference a transform scope.
 * @memberof bithenge_scope_t
 * @param self The scope to dereference, or NULL. */
void bithenge_scope_dec_ref(bithenge_scope_t *self)
{
        if (!self)
                return;
        if (--self->refs)
                return;
        bithenge_node_dec_ref(self->current_node);
        for (int i = 0; i < self->num_params; i++)
                bithenge_node_dec_ref(self->params[i]);
        bithenge_scope_dec_ref(self->outer);
        free(self->params);
        free(self->error);
        free(self);
}

/** Get the outer scope of a scope, which may be NULL.
 * @memberof bithenge_scope_t
 * @param self The scope to examine.
 * @return The outer scope, which may be NULL. */
bithenge_scope_t *bithenge_scope_outer(bithenge_scope_t *self)
{
        return self->outer;
}

/** Get the error message stored in the scope, which may be NULL. The error
 * message only exists as long as the scope does.
 * @memberof bithenge_scope_t
 * @param scope The scope to get the error message from.
 * @return The error message, or NULL. */
const char *bithenge_scope_get_error(bithenge_scope_t *scope)
{
        return scope->error;
}

/** Set the error message for the scope. The error message is stored in the
 * outermost scope, but if any scope already has an error message this error
 * message is ignored.
 * @memberof bithenge_scope_t
 * @param scope The scope.
 * @param format The format string.
 * @return EINVAL normally, or another error code from errno.h. */
int bithenge_scope_error(bithenge_scope_t *scope, const char *format, ...)
{
        if (scope->error)
                return EINVAL;
        while (scope->outer) {
                scope = scope->outer;
                if (scope->error)
                        return EINVAL;
        }
        size_t space_left = 256;
        scope->error = malloc(space_left);
        if (!scope->error)
                return ENOMEM;
        char *out = scope->error;
        va_list ap;
        va_start(ap, format);

        while (*format) {
                if (format[0] == '%' && format[1] == 't') {
                        format += 2;
                        int rc = bithenge_print_node_to_string(&out,
                            &space_left, BITHENGE_PRINT_PYTHON,
                            va_arg(ap, bithenge_node_t *));
                        if (rc != EOK) {
                                va_end(ap);
                                return rc;
                        }
                } else {
                        const char *end = str_chr(format, '%');
                        if (!end)
                                end = format + str_length(format);
                        size_t size = min((size_t)(end - format),
                            space_left - 1);
                        memcpy(out, format, size);
                        format = end;
                        out += size;
                        space_left -= size;
                }
        }
        *out = '\0';

        va_end(ap);
        return EINVAL;
}

/** Get the current node being created, which may be NULL.
 * @memberof bithenge_scope_t
 * @param scope The scope to get the current node from.
 * @return The node being created, or NULL. */
bithenge_node_t *bithenge_scope_get_current_node(bithenge_scope_t *scope)
{
        if (scope->current_node)
                bithenge_node_inc_ref(scope->current_node);
        return scope->current_node;
}

/** Set the current node being created. Takes a reference to @a node.
 * @memberof bithenge_scope_t
 * @param scope The scope to set the current node in.
 * @param node The current node being created, or NULL. */
void bithenge_scope_set_current_node(bithenge_scope_t *scope,
    bithenge_node_t *node)
{
        bithenge_node_dec_ref(scope->current_node);
        scope->current_node = node;
}

/** Get the current input node, which may be NULL.
 * @memberof bithenge_scope_t
 * @param scope The scope to get the current input node from.
 * @return The input node, or NULL. */
bithenge_node_t *bithenge_scope_in_node(bithenge_scope_t *scope)
{
        if (scope->in_node)
                bithenge_node_inc_ref(scope->in_node);
        return scope->in_node;
}

/** Set the current input node. Takes a reference to @a node.
 * @memberof bithenge_scope_t
 * @param scope The scope to set the input node in.
 * @param node The input node, or NULL. */
void bithenge_scope_set_in_node(bithenge_scope_t *scope, bithenge_node_t *node)
{
        bithenge_node_dec_ref(scope->in_node);
        scope->in_node = node;
}

/** Set a scope as a barrier.
 * @memberof bithenge_scope_t
 * @param self The scope to change. */
void bithenge_scope_set_barrier(bithenge_scope_t *self)
{
        self->barrier = true;
}

/** Check whether a scope is a barrier, meaning that variable lookup stops at
 * it.
 * @memberof bithenge_scope_t
 * @param self The scope to check.
 * @return Whether the scope is a barrier. */
bool bithenge_scope_is_barrier(bithenge_scope_t *self)
{
        return self->barrier;
}

/** Allocate parameters. The parameters must then be set with @a
 * bithenge_scope_set_param. This must not be called on a scope that already
 * has parameters.
 * @memberof bithenge_scope_t
 * @param scope The scope in which to allocate parameters.
 * @param num_params The number of parameters to allocate.
 * @return EOK on success or an error code from errno.h. */
int bithenge_scope_alloc_params(bithenge_scope_t *scope, int num_params)
{
        scope->params = malloc(sizeof(*scope->params) * num_params);
        if (!scope->params)
                return ENOMEM;
        scope->num_params = num_params;
        for (int i = 0; i < num_params; i++)
                scope->params[i] = NULL;
        return EOK;
}

/** Set a parameter. Takes a reference to @a node. Note that range checking is
 * not done in release builds.
 * @memberof bithenge_scope_t
 * @param scope The scope in which to allocate parameters.
 * @param i The index of the parameter to set.
 * @param node The value to store in the parameter.
 * @return EOK on success or an error code from errno.h. */
int bithenge_scope_set_param( bithenge_scope_t *scope, int i,
    bithenge_node_t *node)
{
        assert(scope);
        assert(i >= 0 && i < scope->num_params);
        if (bithenge_should_fail()) {
                bithenge_node_dec_ref(node);
                return ENOMEM;
        }
        scope->params[i] = node;
        return EOK;
}

/** Get a parameter. Note that range checking is not done in release builds.
 * @memberof bithenge_scope_t
 * @param scope The scope to get the parameter from.
 * @param i The index of the parameter to set.
 * @param[out] out Stores a new reference to the parameter.
 * @return EOK on success or an error code from errno.h. */
int bithenge_scope_get_param(bithenge_scope_t *scope, int i,
    bithenge_node_t **out)
{
        assert(scope);
        if (scope->num_params) {
                assert(i >= 0 && i < scope->num_params);
                *out = scope->params[i];
                bithenge_node_inc_ref(*out);
                return EOK;
        } else {
                return bithenge_scope_get_param(scope->outer, i, out);
        }
}



/***************** barrier_transform                         *****************/

typedef struct {
        bithenge_transform_t base;
        bithenge_transform_t *transform;
} barrier_transform_t;

static inline barrier_transform_t *transform_as_barrier(
    bithenge_transform_t *base)
{
        return (barrier_transform_t *)base;
}

static inline bithenge_transform_t *barrier_as_transform(
    barrier_transform_t *self)
{
        return &self->base;
}

static int barrier_transform_apply(bithenge_transform_t *base,
    bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out)
{
        barrier_transform_t *self = transform_as_barrier(base);
        bithenge_scope_t *inner_scope;
        int rc = bithenge_scope_new(&inner_scope, scope);
        if (rc != EOK)
                return rc;
        bithenge_scope_set_barrier(inner_scope);
        bithenge_scope_set_in_node(inner_scope, in);
        rc = bithenge_transform_apply(self->transform, inner_scope, in, out);
        bithenge_scope_dec_ref(inner_scope);
        return rc;
}

static int barrier_transform_prefix_length(bithenge_transform_t *base,
    bithenge_scope_t *scope, bithenge_blob_t *in, aoff64_t *out)
{
        barrier_transform_t *self = transform_as_barrier(base);
        bithenge_scope_t *inner_scope;
        int rc = bithenge_scope_new(&inner_scope, scope);
        if (rc != EOK)
                return rc;
        bithenge_scope_set_barrier(inner_scope);
        bithenge_scope_set_in_node(inner_scope, bithenge_blob_as_node(in));
        rc = bithenge_transform_prefix_length(self->transform, inner_scope, in,
            out);
        bithenge_scope_dec_ref(inner_scope);
        return rc;
}

static int barrier_transform_prefix_apply(bithenge_transform_t *base,
    bithenge_scope_t *scope, bithenge_blob_t *in, bithenge_node_t **out_node,
    aoff64_t *out_length)
{
        barrier_transform_t *self = transform_as_barrier(base);
        bithenge_scope_t *inner_scope;
        int rc = bithenge_scope_new(&inner_scope, scope);
        if (rc != EOK)
                return rc;
        bithenge_scope_set_barrier(inner_scope);
        bithenge_scope_set_in_node(inner_scope, bithenge_blob_as_node(in));
        rc = bithenge_transform_prefix_apply(self->transform, inner_scope, in,
            out_node, out_length);
        bithenge_scope_dec_ref(inner_scope);
        return rc;
}

static void barrier_transform_destroy(bithenge_transform_t *base)
{
        barrier_transform_t *self = transform_as_barrier(base);
        bithenge_transform_dec_ref(self->transform);
        free(self);
}

static const bithenge_transform_ops_t barrier_transform_ops = {
        .apply = barrier_transform_apply,
        .prefix_length = barrier_transform_prefix_length,
        .prefix_apply = barrier_transform_prefix_apply,
        .destroy = barrier_transform_destroy,
};

/** Set the subtransform of a barrier transform. This must be done before the
 * barrier transform is used. Takes a reference to @a transform.
 * @param base The barrier transform.
 * @param transform The subtransform to use for all operations.
 * @return EOK on success or an error code from errno.h. */
int bithenge_barrier_transform_set_subtransform(bithenge_transform_t *base,
    bithenge_transform_t *transform)
{
        assert(transform);
        assert(bithenge_transform_num_params(transform) == 0);

        if (bithenge_should_fail()) {
                bithenge_transform_dec_ref(transform);
                return ENOMEM;
        }

        barrier_transform_t *self = transform_as_barrier(base);
        assert(!self->transform);
        self->transform = transform;
        return EOK;
}

/** Create a wrapper transform that creates a new scope. This ensures nothing
 * from the outer scope is passed in, other than parameters. The wrapper may
 * have a different value for num_params. The subtransform must be set with @a
 * bithenge_barrier_transform_set_subtransform before the result is used.
 * @param[out] out Holds the created transform.
 * @param num_params The number of parameters to require, which may be 0.
 * @return EOK on success or an error code from errno.h. */
int bithenge_new_barrier_transform(bithenge_transform_t **out, int num_params)
{
        int rc;
        barrier_transform_t *self = malloc(sizeof(*self));
        if (!self) {
                rc = ENOMEM;
                goto error;
        }
        rc = bithenge_init_transform(barrier_as_transform(self),
            &barrier_transform_ops, num_params);
        if (rc != EOK)
                goto error;
        self->transform = NULL;
        *out = barrier_as_transform(self);
        return EOK;
error:
        free(self);
        return rc;
}



/***************** ascii                                     *****************/

static int ascii_apply(bithenge_transform_t *self, bithenge_scope_t *scope,
    bithenge_node_t *in, bithenge_node_t **out)
{
        int rc;
        if (bithenge_node_type(in) != BITHENGE_NODE_BLOB)
                return EINVAL;
        bithenge_blob_t *blob = bithenge_node_as_blob(in);
        aoff64_t size;
        rc = bithenge_blob_size(blob, &size);
        if (rc != EOK)
                return rc;

        char *buffer = malloc(size + 1);
        if (!buffer)
                return ENOMEM;
        aoff64_t size_read = size;
        rc = bithenge_blob_read(blob, 0, buffer, &size_read);
        if (rc != EOK) {
                free(buffer);
                return rc;
        }
        if (size_read != size) {
                free(buffer);
                return EINVAL;
        }
        buffer[size] = '\0';

        /* TODO: what if the OS encoding is incompatible with ASCII? */
        return bithenge_new_string_node(out, buffer, true);
}

static const bithenge_transform_ops_t ascii_ops = {
        .apply = ascii_apply,
        .destroy = transform_indestructible,
};

/** The ASCII text transform. */
bithenge_transform_t bithenge_ascii_transform = {
        &ascii_ops, 1, 0
};



/***************** bit                                       *****************/

static int bit_prefix_apply(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node,
    aoff64_t *out_size)
{
        char buffer;
        aoff64_t size = 1;
        int rc = bithenge_blob_read_bits(blob, 0, &buffer, &size, true);
        if (rc != EOK)
                return rc;
        if (size != 1)
                return EINVAL;
        if (out_size)
                *out_size = size;
        return bithenge_new_boolean_node(out_node, (buffer & 1) != 0);
}

static const bithenge_transform_ops_t bit_ops = {
        .prefix_apply = bit_prefix_apply,
        .destroy = transform_indestructible,
};

/** A transform that decodes a bit as a boolean. */
bithenge_transform_t bithenge_bit_transform = {
        &bit_ops, 1, 0
};



/***************** bits_be, bits_le                          *****************/

typedef struct {
        bithenge_blob_t base;
        bithenge_blob_t *bytes;
        bool little_endian;
} bits_xe_blob_t;

static bits_xe_blob_t *blob_as_bits_xe(bithenge_blob_t *base)
{
        return (bits_xe_blob_t *)base;
}

static bithenge_blob_t *bits_xe_as_blob(bits_xe_blob_t *self)
{
        return &self->base;
}

static int bits_xe_size(bithenge_blob_t *base, aoff64_t *out)
{
        bits_xe_blob_t *self = blob_as_bits_xe(base);
        int rc = bithenge_blob_size(self->bytes, out);
        *out *= 8;
        return rc;
}

static uint8_t reverse_byte(uint8_t val)
{
        val = ((val & 0x0f) << 4) ^ ((val & 0xf0) >> 4);
        val = ((val & 0x33) << 2) ^ ((val & 0xcc) >> 2);
        val = ((val & 0x55) << 1) ^ ((val & 0xaa) >> 1);
        return val;
}

static int bits_xe_read_bits(bithenge_blob_t *base, aoff64_t offset,
    char *buffer, aoff64_t *size, bool little_endian)
{
        bits_xe_blob_t *self = blob_as_bits_xe(base);
        aoff64_t bytes_offset = offset / 8;
        aoff64_t bit_offset = offset % 8;
        aoff64_t output_num_bytes = (*size + 7) / 8;
        aoff64_t bytes_size = (*size + bit_offset + 7) / 8;
        bool separate_buffer = bit_offset != 0;
        uint8_t *bytes_buffer;
        if (separate_buffer) {
                /* Allocate an extra byte, to make sure byte1 can be read. */
                bytes_buffer = malloc(bytes_size + 1);
                if (!bytes_buffer)
                        return ENOMEM;
        } else
                bytes_buffer = (uint8_t *)buffer;

        int rc = bithenge_blob_read(self->bytes, bytes_offset,
            (char *)bytes_buffer, &bytes_size);
        if (rc != EOK)
                goto end;
        *size = min(*size, bytes_size * 8 - bit_offset);

        if (little_endian != self->little_endian)
                for (aoff64_t i = 0; i < bytes_size; i++)
                        bytes_buffer[i] = reverse_byte(bytes_buffer[i]);

        if (bit_offset || separate_buffer) {
                for (aoff64_t i = 0; i < output_num_bytes; i++) {
                        uint8_t byte0 = bytes_buffer[i];
                        uint8_t byte1 = bytes_buffer[i + 1];
                        buffer[i] = little_endian ?
                            (byte0 >> bit_offset) ^ (byte1 << (8 - bit_offset)) :
                            (byte0 << bit_offset) ^ (byte1 >> (8 - bit_offset));
                }
        }

end:
        if (separate_buffer)
                free(bytes_buffer);
        return rc;
}

static void bits_xe_destroy(bithenge_blob_t *base)
{
        bits_xe_blob_t *self = blob_as_bits_xe(base);
        bithenge_blob_dec_ref(self->bytes);
        free(self);
}

static const bithenge_random_access_blob_ops_t bits_xe_blob_ops = {
        .size = bits_xe_size,
        .read_bits = bits_xe_read_bits,
        .destroy = bits_xe_destroy,
};

static int bits_xe_apply(bithenge_transform_t *self, bithenge_scope_t *scope,
    bithenge_node_t *in, bithenge_node_t **out)
{
        if (bithenge_node_type(in) != BITHENGE_NODE_BLOB)
                return EINVAL;
        bits_xe_blob_t *blob = malloc(sizeof(*blob));
        if (!blob)
                return ENOMEM;
        int rc = bithenge_init_random_access_blob(bits_xe_as_blob(blob),
            &bits_xe_blob_ops);
        if (rc != EOK) {
                free(blob);
                return rc;
        }
        bithenge_node_inc_ref(in);
        blob->bytes = bithenge_node_as_blob(in);
        blob->little_endian = (self == &bithenge_bits_le_transform);
        *out = bithenge_blob_as_node(bits_xe_as_blob(blob));
        return EOK;
}

static const bithenge_transform_ops_t bits_xe_ops = {
        .apply = bits_xe_apply,
        .destroy = transform_indestructible,
};

/** A transform that converts a byte blob to a bit blob, most-significant bit
 * first. */
bithenge_transform_t bithenge_bits_be_transform = {
        &bits_xe_ops, 1, 0
};

/** A transform that converts a byte blob to a bit blob, least-significant bit
 * first. */
bithenge_transform_t bithenge_bits_le_transform = {
        &bits_xe_ops, 1, 0
};



/***************** invalid                                   *****************/

static int invalid_apply(bithenge_transform_t *self, bithenge_scope_t *scope,
    bithenge_node_t *in, bithenge_node_t **out)
{
        return EINVAL;
}

static const bithenge_transform_ops_t invalid_ops = {
        .apply = invalid_apply,
        .destroy = transform_indestructible,
};

/** A transform that always raises an error. */
bithenge_transform_t bithenge_invalid_transform = {
        &invalid_ops, 1, 0
};



/***************** known_length                              *****************/

static int known_length_apply(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out)
{
        bithenge_node_t *length_node;
        int rc = bithenge_scope_get_param(scope, 0, &length_node);
        if (rc != EOK)
                return rc;
        if (bithenge_node_type(length_node) != BITHENGE_NODE_INTEGER) {
                bithenge_node_dec_ref(length_node);
                return EINVAL;
        }
        bithenge_int_t length = bithenge_integer_node_value(length_node);
        bithenge_node_dec_ref(length_node);

        if (bithenge_node_type(in) != BITHENGE_NODE_BLOB)
                return EINVAL;
        aoff64_t size;
        rc = bithenge_blob_size(bithenge_node_as_blob(in), &size);
        if (rc != EOK)
                return rc;
        if (length != (bithenge_int_t)size)
                return EINVAL;

        bithenge_node_inc_ref(in);
        *out = in;
        return EOK;
}

static int known_length_prefix_length(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_blob_t *in, aoff64_t *out)
{
        bithenge_node_t *length_node;
        int rc = bithenge_scope_get_param(scope, 0, &length_node);
        if (rc != EOK)
                return rc;
        if (bithenge_node_type(length_node) != BITHENGE_NODE_INTEGER) {
                bithenge_node_dec_ref(length_node);
                return EINVAL;
        }
        bithenge_int_t length = bithenge_integer_node_value(length_node);
        bithenge_node_dec_ref(length_node);

        *out = (aoff64_t)length;
        return EOK;
}

static const bithenge_transform_ops_t known_length_ops = {
        .apply = known_length_apply,
        .prefix_length = known_length_prefix_length,
        .destroy = transform_indestructible,
};

/** Pass through a blob, but require its length to equal the first argument. */
bithenge_transform_t bithenge_known_length_transform = {
        &known_length_ops, 1, 1
};

static int nonzero_boolean_apply(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out)
{
        if (bithenge_node_type(in) != BITHENGE_NODE_INTEGER)
                return EINVAL;
        bool value = bithenge_integer_node_value(in) != 0;
        return bithenge_new_boolean_node(out, value);
}

static const bithenge_transform_ops_t nonzero_boolean_ops = {
        .apply = nonzero_boolean_apply,
        .destroy = transform_indestructible,
};

/** A transform that converts integers to booleans, true if nonzero. */
bithenge_transform_t bithenge_nonzero_boolean_transform = {
        &nonzero_boolean_ops, 1, 0
};

static int prefix_length_1(bithenge_transform_t *self, bithenge_scope_t *scope,
    bithenge_blob_t *blob, aoff64_t *out)
{
        *out = 1;
        return EOK;
}

static int prefix_length_2(bithenge_transform_t *self, bithenge_scope_t *scope,
    bithenge_blob_t *blob, aoff64_t *out)
{
        *out = 2;
        return EOK;
}

static int prefix_length_4(bithenge_transform_t *self, bithenge_scope_t *scope,
    bithenge_blob_t *blob, aoff64_t *out)
{
        *out = 4;
        return EOK;
}

static int prefix_length_8(bithenge_transform_t *self, bithenge_scope_t *scope,
    bithenge_blob_t *blob, aoff64_t *out)
{
        *out = 8;
        return EOK;
}

/** @cond internal */
#define MAKE_UINT_TRANSFORM(NAME, TYPE, ENDIAN, PREFIX_LENGTH_FUNC)            \
        static int NAME##_apply(bithenge_transform_t *self,                    \
            bithenge_scope_t *scope, bithenge_node_t *in,                      \
            bithenge_node_t **out)                                             \
        {                                                                      \
                int rc;                                                        \
                if (bithenge_node_type(in) != BITHENGE_NODE_BLOB)              \
                        return EINVAL;                                         \
                bithenge_blob_t *blob = bithenge_node_as_blob(in);             \
                                                                               \
                /* Read too many bytes; success means the blob is too long. */ \
                TYPE val[2];                                                   \
                aoff64_t size = sizeof(val[0]) + 1;                            \
                rc = bithenge_blob_read(blob, 0, (char *)val, &size);          \
                if (rc != EOK)                                                 \
                        return rc;                                             \
                if (size != sizeof(val[0]))                                    \
                        return EINVAL;                                         \
                                                                               \
                return bithenge_new_integer_node(out, ENDIAN(val[0]));         \
        }                                                                      \
                                                                               \
        static const bithenge_transform_ops_t NAME##_ops = {                   \
                .apply = NAME##_apply,                                         \
                .prefix_length = PREFIX_LENGTH_FUNC,                           \
                .destroy = transform_indestructible,                           \
        };                                                                     \
                                                                               \
        bithenge_transform_t bithenge_##NAME##_transform = {                   \
                &NAME##_ops, 1, 0                                              \
        }

MAKE_UINT_TRANSFORM(uint8   , uint8_t ,                 , prefix_length_1);
MAKE_UINT_TRANSFORM(uint16le, uint16_t, uint16_t_le2host, prefix_length_2);
MAKE_UINT_TRANSFORM(uint16be, uint16_t, uint16_t_be2host, prefix_length_2);
MAKE_UINT_TRANSFORM(uint32le, uint32_t, uint32_t_le2host, prefix_length_4);
MAKE_UINT_TRANSFORM(uint32be, uint32_t, uint32_t_be2host, prefix_length_4);
MAKE_UINT_TRANSFORM(uint64le, uint64_t, uint64_t_le2host, prefix_length_8);
MAKE_UINT_TRANSFORM(uint64be, uint64_t, uint64_t_be2host, prefix_length_8);
/** @endcond */



/***************** uint_be, uint_le                          *****************/

static int uint_xe_prefix_apply(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_blob_t *blob, bithenge_node_t **out_node,
    aoff64_t *out_size)
{
        bool little_endian = (self == &bithenge_uint_le_transform);
        bithenge_node_t *num_bits_node;
        int rc = bithenge_scope_get_param(scope, 0, &num_bits_node);
        if (rc != EOK)
                return rc;
        if (bithenge_node_type(num_bits_node) != BITHENGE_NODE_INTEGER) {
                bithenge_node_dec_ref(num_bits_node);
                return EINVAL;
        }
        bithenge_int_t num_bits = bithenge_integer_node_value(num_bits_node);
        bithenge_node_dec_ref(num_bits_node);
        if (num_bits < 0)
                return EINVAL;
        if ((size_t)num_bits > sizeof(bithenge_int_t) * 8 - 1)
                return EINVAL;

        aoff64_t size = num_bits;
        uint8_t buffer[sizeof(bithenge_int_t)];
        rc = bithenge_blob_read_bits(blob, 0, (char *)buffer, &size,
            little_endian);
        if (rc != EOK)
                return rc;
        if (size != (aoff64_t)num_bits)
                return EINVAL;
        if (out_size)
                *out_size = size;

        bithenge_int_t result = 0;
        bithenge_int_t num_easy_bytes = num_bits / 8;
        if (little_endian) {
                for (bithenge_int_t i = 0; i < num_easy_bytes; i++)
                        result += buffer[i] << 8 * i;
                if (num_bits % 8)
                        result += (buffer[num_easy_bytes] &
                            ((1 << num_bits % 8) - 1)) << 8 * num_easy_bytes;
        } else {
                for (bithenge_int_t i = 0; i < num_easy_bytes; i++)
                        result += buffer[i] << (num_bits - 8 * (i + 1));
                if (num_bits % 8)
                        result += buffer[num_easy_bytes] >> (8 - num_bits % 8);
        }

        return bithenge_new_integer_node(out_node, result);
}

static const bithenge_transform_ops_t uint_xe_ops = {
        .prefix_apply = uint_xe_prefix_apply,
        .destroy = transform_indestructible,
};

/** A transform that reads an unsigned integer from an arbitrary number of
 * bits, most-significant bit first. */
bithenge_transform_t bithenge_uint_be_transform = {
        &uint_xe_ops, 1, 1
};

/** A transform that reads an unsigned integer from an arbitrary number of
 * bits, least-significant bit first. */
bithenge_transform_t bithenge_uint_le_transform = {
        &uint_xe_ops, 1, 1
};



/***************** zero_terminated                           *****************/

static int zero_terminated_apply(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_node_t *in, bithenge_node_t **out)
{
        int rc;
        if (bithenge_node_type(in) != BITHENGE_NODE_BLOB)
                return EINVAL;
        bithenge_blob_t *blob = bithenge_node_as_blob(in);
        aoff64_t size;
        rc = bithenge_blob_size(blob, &size);
        if (rc != EOK)
                return rc;
        if (size < 1)
                return EINVAL;
        char ch;
        aoff64_t size_read = 1;
        rc = bithenge_blob_read(blob, size - 1, &ch, &size_read);
        if (rc != EOK)
                return rc;
        if (size_read != 1 || ch != '\0')
                return EINVAL;
        bithenge_blob_inc_ref(blob);
        return bithenge_new_subblob(out, blob, 0, size - 1);
}

static int zero_terminated_prefix_length(bithenge_transform_t *self,
    bithenge_scope_t *scope, bithenge_blob_t *blob, aoff64_t *out)
{
        int rc;
        char buffer[4096];
        aoff64_t offset = 0, size_read = sizeof(buffer);
        do {
                rc = bithenge_blob_read(blob, offset, buffer, &size_read);
                if (rc != EOK)
                        return rc;
                char *found = memchr(buffer, '\0', size_read);
                if (found) {
                        *out = found - buffer + offset + 1;
                        return EOK;
                }
                offset += size_read;
        } while (size_read == sizeof(buffer));
        return EINVAL;
}

static const bithenge_transform_ops_t zero_terminated_ops = {
        .apply = zero_terminated_apply,
        .prefix_length = zero_terminated_prefix_length,
        .destroy = transform_indestructible,
};

/** The zero-terminated data transform. */
bithenge_transform_t bithenge_zero_terminated_transform = {
        &zero_terminated_ops, 1, 0
};

static bithenge_named_transform_t primitive_transforms[] = {
        {"ascii", &bithenge_ascii_transform},
        {"bit", &bithenge_bit_transform},
        {"bits_be", &bithenge_bits_be_transform},
        {"bits_le", &bithenge_bits_le_transform},
        {"known_length", &bithenge_known_length_transform},
        {"nonzero_boolean", &bithenge_nonzero_boolean_transform},
        {"uint8", &bithenge_uint8_transform},
        {"uint16be", &bithenge_uint16be_transform},
        {"uint16le", &bithenge_uint16le_transform},
        {"uint32be", &bithenge_uint32be_transform},
        {"uint32le", &bithenge_uint32le_transform},
        {"uint64be", &bithenge_uint64be_transform},
        {"uint64le", &bithenge_uint64le_transform},
        {"uint_be", &bithenge_uint_be_transform},
        {"uint_le", &bithenge_uint_le_transform},
        {"zero_terminated", &bithenge_zero_terminated_transform},
        {NULL, NULL}
};

/** An array of named built-in transforms. */
bithenge_named_transform_t *bithenge_primitive_transforms = primitive_transforms;

/** @}
 */