/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 
 *
 *    Copyright 2014-2017 (c) Fraunhofer IOSB (Author: Julius Pfrommer)
 *    Copyright 2014, 2016-2017 (c) Florian Palm
 *    Copyright 2014-2016 (c) Sten Grüner
 *    Copyright 2014 (c) Leon Urbas
 *    Copyright 2015 (c) Chris Iatrou
 *    Copyright 2015 (c) Markus Graube
 *    Copyright 2015 (c) Reza Ebrahimi
 *    Copyright 2015-2016 (c) Oleksiy Vasylyev
 *    Copyright 2017 (c) Stefan Profanter, fortiss GmbH
 *    Copyright 2016 (c) Lorenz Haas
 */

#include <open62541/types.h>
#include <open62541/types_generated.h>
#include <open62541/types_generated_handling.h>

#include "ua_util_internal.h"

#include "libc_time.h"
#include "pcg_basic.h"

/* Datatype Handling
 * -----------------
 * This file contains handling functions for the builtin types and functions
 * handling of structured types and arrays. These need type descriptions in a
 * UA_DataType structure. The UA_DataType structures as well as all non-builtin
 * datatypes are autogenerated. */

/* Global definition of NULL type instances. These are always zeroed out, as
 * mandated by the C/C++ standard for global values with no initializer. */
const UA_String UA_STRING_NULL = {0, NULL};
const UA_ByteString UA_BYTESTRING_NULL = {0, NULL};
const UA_Guid UA_GUID_NULL = {0, 0, 0, {0,0,0,0,0,0,0,0}};
const UA_NodeId UA_NODEID_NULL = {0, UA_NODEIDTYPE_NUMERIC, {0}};
const UA_ExpandedNodeId UA_EXPANDEDNODEID_NULL = {{0, UA_NODEIDTYPE_NUMERIC, {0}}, {0, NULL}, 0};

typedef UA_StatusCode (*UA_copySignature)(const void *src, void *dst,
                                          const UA_DataType *type);
typedef void (*UA_clearSignature)(void *p, const UA_DataType *type);

extern const UA_copySignature copyJumpTable[UA_DATATYPEKINDS];
extern const UA_clearSignature clearJumpTable[UA_DATATYPEKINDS];

/* TODO: The standard-defined types are ordered. See if binary search is
 * more efficient. */
const UA_DataType *
UA_findDataType(const UA_NodeId *typeId) {
    if(typeId->identifierType != UA_NODEIDTYPE_NUMERIC)
        return NULL;

    /* Always look in built-in types first
     * (may contain data types from all namespaces) */
    for(size_t i = 0; i < UA_TYPES_COUNT; ++i) {
        if(UA_TYPES[i].typeId.identifier.numeric == typeId->identifier.numeric
           && UA_TYPES[i].typeId.namespaceIndex == typeId->namespaceIndex)
            return &UA_TYPES[i];
    }

    /* TODO When other namespace look in custom types, too, requires access to custom types array here! */
    /*if(typeId->namespaceIndex != 0) {
        size_t customTypesArraySize;
        const UA_DataType *customTypesArray;
        UA_getCustomTypes(&customTypesArraySize, &customTypesArray);
        for(size_t i = 0; i < customTypesArraySize; ++i) {
            if(customTypesArray[i].typeId.identifier.numeric == typeId->identifier.numeric
               && customTypesArray[i].typeId.namespaceIndex == typeId->namespaceIndex)
                return &customTypesArray[i];
        }
    }*/

    return NULL;
}

/***************************/
/* Random Number Generator */
/***************************/

//TODO is this safe for multithreading?
static pcg32_random_t UA_rng = PCG32_INITIALIZER;

void
UA_random_seed(u64 seed) {
    pcg32_srandom_r(&UA_rng, seed, (u64)UA_DateTime_now());
}

u32
UA_UInt32_random(void) {
    return (u32)pcg32_random_r(&UA_rng);
}

/*****************/
/* Builtin Types */
/*****************/

UA_String
UA_String_fromChars(const char *src) {
    UA_String s; s.length = 0; s.data = NULL;
    if(!src)
        return s;
    s.length = strlen(src);
    if(s.length > 0) {
        s.data = (u8*)UA_malloc(s.length);
        if(!s.data) {
            s.length = 0;
            return s;
        }
        memcpy(s.data, src, s.length);
    } else {
        s.data = (u8*)UA_EMPTY_ARRAY_SENTINEL;
    }
    return s;
}

UA_Boolean
UA_String_equal(const UA_String *s1, const UA_String *s2) {
    if(s1->length != s2->length)
        return false;
    if(s1->length == 0)
        return true;
    i32 is = memcmp((char const*)s1->data,
                    (char const*)s2->data, s1->length);
    return (is == 0) ? true : false;
}

static UA_StatusCode
String_copy(UA_String const *src, UA_String *dst, const UA_DataType *_) {
    UA_StatusCode retval = UA_Array_copy(src->data, src->length, (void**)&dst->data,
                                         &UA_TYPES[UA_TYPES_BYTE]);
    if(retval == UA_STATUSCODE_GOOD)
        dst->length = src->length;
    return retval;
}

static void
String_clear(UA_String *s, const UA_DataType *_) {
    UA_Array_delete(s->data, s->length, &UA_TYPES[UA_TYPES_BYTE]);
}

/* QualifiedName */
static UA_StatusCode
QualifiedName_copy(const UA_QualifiedName *src, UA_QualifiedName *dst, const UA_DataType *_) {
    dst->namespaceIndex = src->namespaceIndex;
    return String_copy(&src->name, &dst->name, NULL);
}

static void
QualifiedName_clear(UA_QualifiedName *p, const UA_DataType *_) {
    String_clear(&p->name, NULL);
}

UA_Boolean
UA_QualifiedName_equal(const UA_QualifiedName *qn1,
                       const UA_QualifiedName *qn2) {
    if(qn1 == NULL || qn2 == NULL)
        return false;
    if(qn1->namespaceIndex != qn2->namespaceIndex)
        return false;
    if(qn1->name.length != qn2->name.length)
        return false;
    return (memcmp((char const*)qn1->name.data,
                   (char const*)qn2->name.data, qn1->name.length) == 0);
}

/* DateTime */
UA_DateTimeStruct
UA_DateTime_toStruct(UA_DateTime t) {
    /* Calculating the the milli-, micro- and nanoseconds */
    UA_DateTimeStruct dateTimeStruct;
    if(t >= 0) {
        dateTimeStruct.nanoSec  = (u16)((t % 10) * 100);
        dateTimeStruct.microSec = (u16)((t % 10000) / 10);
        dateTimeStruct.milliSec = (u16)((t % 10000000) / 10000);
    } else {
        dateTimeStruct.nanoSec  = (u16)(((t % 10 + t) % 10) * 100);
        dateTimeStruct.microSec = (u16)(((t % 10000 + t) % 10000) / 10);
        dateTimeStruct.milliSec = (u16)(((t % 10000000 + t) % 10000000) / 10000);
    }

    /* Calculating the unix time with #include <time.h> */
    long long secSinceUnixEpoch = (long long)(t / UA_DATETIME_SEC)
        - (long long)(UA_DATETIME_UNIX_EPOCH / UA_DATETIME_SEC);
    struct mytm ts;
    memset(&ts, 0, sizeof(struct mytm));
    __secs_to_tm(secSinceUnixEpoch, &ts);
    dateTimeStruct.sec    = (u16)ts.tm_sec;
    dateTimeStruct.min    = (u16)ts.tm_min;
    dateTimeStruct.hour   = (u16)ts.tm_hour;
    dateTimeStruct.day    = (u16)ts.tm_mday;
    dateTimeStruct.month  = (u16)(ts.tm_mon + 1);
    dateTimeStruct.year   = (u16)(ts.tm_year + 1900);
    return dateTimeStruct;
}

UA_DateTime
UA_DateTime_fromStruct(UA_DateTimeStruct ts) {
    /* Seconds since the Unix epoch */
    struct mytm tm;
    memset(&tm, 0, sizeof(struct mytm));
    tm.tm_year = ts.year - 1900;
    tm.tm_mon = ts.month - 1;
    tm.tm_mday = ts.day;
    tm.tm_hour = ts.hour;
    tm.tm_min = ts.min;
    tm.tm_sec = ts.sec;
    long long sec_epoch = __tm_to_secs(&tm);

    UA_DateTime t = UA_DATETIME_UNIX_EPOCH;
    t += sec_epoch * UA_DATETIME_SEC;
    t += ts.milliSec * UA_DATETIME_MSEC;
    t += ts.microSec * UA_DATETIME_USEC;
    t += ts.nanoSec / 100;
    return t;
}

/* Guid */
UA_Boolean
UA_Guid_equal(const UA_Guid *g1, const UA_Guid *g2) {
    if(memcmp(g1, g2, sizeof(UA_Guid)) == 0)
        return true;
    return false;
}

UA_Guid
UA_Guid_random(void) {
    UA_Guid result;
    result.data1 = (u32)pcg32_random_r(&UA_rng);
    u32 r = (u32)pcg32_random_r(&UA_rng);
    result.data2 = (u16) r;
    result.data3 = (u16) (r >> 16);
    r = (u32)pcg32_random_r(&UA_rng);
    result.data4[0] = (u8)r;
    result.data4[1] = (u8)(r >> 4);
    result.data4[2] = (u8)(r >> 8);
    result.data4[3] = (u8)(r >> 12);
    r = (u32)pcg32_random_r(&UA_rng);
    result.data4[4] = (u8)r;
    result.data4[5] = (u8)(r >> 4);
    result.data4[6] = (u8)(r >> 8);
    result.data4[7] = (u8)(r >> 12);
    return result;
}

/* ByteString */
UA_StatusCode
UA_ByteString_allocBuffer(UA_ByteString *bs, size_t length) {
    UA_ByteString_init(bs);
    if(length == 0)
        return UA_STATUSCODE_GOOD;
    bs->data = (u8*)UA_malloc(length);
    if(!bs->data)
        return UA_STATUSCODE_BADOUTOFMEMORY;
    bs->length = length;
    return UA_STATUSCODE_GOOD;
}

/* NodeId */
static void
NodeId_clear(UA_NodeId *p, const UA_DataType *_) {
    switch(p->identifierType) {
    case UA_NODEIDTYPE_STRING:
    case UA_NODEIDTYPE_BYTESTRING:
        String_clear(&p->identifier.string, NULL);
        break;
    default: break;
    }
}

static UA_StatusCode
NodeId_copy(UA_NodeId const *src, UA_NodeId *dst, const UA_DataType *_) {
    UA_StatusCode retval = UA_STATUSCODE_GOOD;
    switch(src->identifierType) {
    case UA_NODEIDTYPE_NUMERIC:
        *dst = *src;
        return UA_STATUSCODE_GOOD;
    case UA_NODEIDTYPE_STRING:
        retval |= UA_String_copy(&src->identifier.string,
                                 &dst->identifier.string);
        break;
    case UA_NODEIDTYPE_GUID:
        retval |= UA_Guid_copy(&src->identifier.guid, &dst->identifier.guid);
        break;
    case UA_NODEIDTYPE_BYTESTRING:
        retval |= UA_ByteString_copy(&src->identifier.byteString,
                                     &dst->identifier.byteString);
        break;
    default:
        return UA_STATUSCODE_BADINTERNALERROR;
    }
    dst->namespaceIndex = src->namespaceIndex;
    dst->identifierType = src->identifierType;
    return retval;
}

UA_Boolean
UA_NodeId_isNull(const UA_NodeId *p) {
    if(p->namespaceIndex != 0)
        return false;
    switch (p->identifierType) {
    case UA_NODEIDTYPE_NUMERIC:
        return (p->identifier.numeric == 0);
    case UA_NODEIDTYPE_STRING:
        return UA_String_equal(&p->identifier.string, &UA_STRING_NULL);
    case UA_NODEIDTYPE_GUID:
        return UA_Guid_equal(&p->identifier.guid, &UA_GUID_NULL);
    case UA_NODEIDTYPE_BYTESTRING:
        return UA_ByteString_equal(&p->identifier.byteString, &UA_BYTESTRING_NULL);
    }
    return false;
}

/* Absolute ordering for NodeIds */
UA_Order
UA_NodeId_order(const UA_NodeId *n1, const UA_NodeId *n2) {
    /* Compare namespaceIndex */
    if(n1->namespaceIndex < n2->namespaceIndex)
        return UA_ORDER_LESS;
    if(n1->namespaceIndex > n2->namespaceIndex)
        return UA_ORDER_MORE;

    /* Compare identifierType */
    if(n1->identifierType < n2->identifierType)
        return UA_ORDER_LESS;
    if(n1->identifierType > n2->identifierType)
        return UA_ORDER_MORE;

    /* Compare the identifier */
    switch(n1->identifierType) {
    case UA_NODEIDTYPE_NUMERIC:
        if(n1->identifier.numeric < n2->identifier.numeric)
            return UA_ORDER_LESS;
        if(n1->identifier.numeric > n2->identifier.numeric)
            return UA_ORDER_MORE;
        break;
    case UA_NODEIDTYPE_GUID:
        if(n1->identifier.guid.data1 < n2->identifier.guid.data1) {
            return UA_ORDER_LESS;
        } else if(n1->identifier.guid.data1 > n2->identifier.guid.data1) {
            return UA_ORDER_MORE;
        } else if(n1->identifier.guid.data2 < n2->identifier.guid.data2) {
            return UA_ORDER_LESS;
        } else if(n1->identifier.guid.data2 > n2->identifier.guid.data2) {
            return UA_ORDER_MORE;
        } else if(n1->identifier.guid.data3 < n2->identifier.guid.data3) {
            return UA_ORDER_LESS;
        } else if(n1->identifier.guid.data3 > n2->identifier.guid.data3) {
            return UA_ORDER_MORE;
        } else {
            int cmp = memcmp(n1->identifier.guid.data4, n2->identifier.guid.data4, 8);

            if(cmp < 0) return UA_ORDER_LESS;
            if(cmp > 0) return UA_ORDER_MORE;

        }

        break;
    case UA_NODEIDTYPE_STRING:
    case UA_NODEIDTYPE_BYTESTRING: {
        size_t minLength = UA_MIN(n1->identifier.string.length, n2->identifier.string.length);
        int cmp = strncmp((const char*)n1->identifier.string.data,
                          (const char*)n2->identifier.string.data,
                          minLength);
        if(cmp < 0)
            return UA_ORDER_LESS;
        if(cmp > 0)
            return UA_ORDER_MORE;

        if(n1->identifier.string.length < n2->identifier.string.length)
            return UA_ORDER_LESS;
        if(n1->identifier.string.length > n2->identifier.string.length)
            return UA_ORDER_MORE;
        break;
    }
    default:
        break;
    }

    return UA_ORDER_EQ;
}

/* FNV non-cryptographic hash function. See
 * https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function */
#define FNV_PRIME_32 16777619
static u32
fnv32(u32 fnv, const u8 *buf, size_t size) {
    for(size_t i = 0; i < size; ++i) {
        fnv = fnv ^ (buf[i]);
        fnv = fnv * FNV_PRIME_32;
    }
    return fnv;
}

u32
UA_NodeId_hash(const UA_NodeId *n) {
    switch(n->identifierType) {
    case UA_NODEIDTYPE_NUMERIC:
    default:
        // shift knuth multiplication to use highest 32 bits and after addition make sure we don't have an integer overflow
        return (u32)((n->namespaceIndex + ((n->identifier.numeric * (u64)2654435761) >> (32))) & UINT32_C(4294967295)); /*  Knuth's multiplicative hashing */
    case UA_NODEIDTYPE_STRING:
    case UA_NODEIDTYPE_BYTESTRING:
        return fnv32(n->namespaceIndex, n->identifier.string.data, n->identifier.string.length);
    case UA_NODEIDTYPE_GUID:
        return fnv32(n->namespaceIndex, (const u8*)&n->identifier.guid, sizeof(UA_Guid));
    }
}

/* ExpandedNodeId */
static void
ExpandedNodeId_clear(UA_ExpandedNodeId *p, const UA_DataType *_) {
    NodeId_clear(&p->nodeId, _);
    String_clear(&p->namespaceUri, NULL);
}

static UA_StatusCode
ExpandedNodeId_copy(UA_ExpandedNodeId const *src, UA_ExpandedNodeId *dst,
                    const UA_DataType *_) {
    UA_StatusCode retval = NodeId_copy(&src->nodeId, &dst->nodeId, NULL);
    retval |= UA_String_copy(&src->namespaceUri, &dst->namespaceUri);
    dst->serverIndex = src->serverIndex;
    return retval;
}

UA_Order
UA_ExpandedNodeId_order(const UA_ExpandedNodeId *n1,
                        const UA_ExpandedNodeId *n2) {
    if(n1->serverIndex > n2->serverIndex)
        return UA_ORDER_MORE;
    if(n1->serverIndex < n2->serverIndex)
        return UA_ORDER_LESS;
    if(n1->namespaceUri.length > 0) {
        if(n1->namespaceUri.length > n2->namespaceUri.length)
            return UA_ORDER_MORE;
        if(n1->namespaceUri.length < n2->namespaceUri.length)
            return UA_ORDER_LESS;
        int cmp = strncmp((const char*)n1->namespaceUri.data,
                          (const char*)n2->namespaceUri.data,
                          n1->namespaceUri.length);
        if(cmp < 0)
            return UA_ORDER_LESS;
        if(cmp > 0)
            return UA_ORDER_MORE;
    }
    return UA_NodeId_order(&n1->nodeId, &n2->nodeId);
}

u32
UA_ExpandedNodeId_hash(const UA_ExpandedNodeId *n) {
    u32 h = UA_NodeId_hash(&n->nodeId);
    h = fnv32(h, (const UA_Byte*)&n->serverIndex, 4);
    return fnv32(h, n->namespaceUri.data, n->namespaceUri.length);
}

/* ExtensionObject */
static void
ExtensionObject_clear(UA_ExtensionObject *p, const UA_DataType *_) {
    switch(p->encoding) {
    case UA_EXTENSIONOBJECT_ENCODED_NOBODY:
    case UA_EXTENSIONOBJECT_ENCODED_BYTESTRING:
    case UA_EXTENSIONOBJECT_ENCODED_XML:
        NodeId_clear(&p->content.encoded.typeId, NULL);
        String_clear(&p->content.encoded.body, NULL);
        break;
    case UA_EXTENSIONOBJECT_DECODED:
        if(p->content.decoded.data)
            UA_delete(p->content.decoded.data, p->content.decoded.type);
        break;
    default:
        break;
    }
}

static UA_StatusCode
ExtensionObject_copy(UA_ExtensionObject const *src, UA_ExtensionObject *dst,
                     const UA_DataType *_) {
    UA_StatusCode retval = UA_STATUSCODE_GOOD;
    switch(src->encoding) {
    case UA_EXTENSIONOBJECT_ENCODED_NOBODY:
    case UA_EXTENSIONOBJECT_ENCODED_BYTESTRING:
    case UA_EXTENSIONOBJECT_ENCODED_XML:
        dst->encoding = src->encoding;
        retval = NodeId_copy(&src->content.encoded.typeId,
                             &dst->content.encoded.typeId, NULL);
        retval |= UA_ByteString_copy(&src->content.encoded.body,
                                     &dst->content.encoded.body);
        break;
    case UA_EXTENSIONOBJECT_DECODED:
    case UA_EXTENSIONOBJECT_DECODED_NODELETE:
        if(!src->content.decoded.type || !src->content.decoded.data)
            return UA_STATUSCODE_BADINTERNALERROR;
        dst->encoding = UA_EXTENSIONOBJECT_DECODED;
        dst->content.decoded.type = src->content.decoded.type;
        retval = UA_Array_copy(src->content.decoded.data, 1,
            &dst->content.decoded.data, src->content.decoded.type);
        break;
    default:
        break;
    }
    return retval;
}

/* Variant */
static void
Variant_clear(UA_Variant *p, const UA_DataType *_) {
    if(p->storageType != UA_VARIANT_DATA)
        return;
    if(p->type && p->data > UA_EMPTY_ARRAY_SENTINEL) {
        if(p->arrayLength == 0)
            p->arrayLength = 1;
        UA_Array_delete(p->data, p->arrayLength, p->type);
        p->data = NULL;
    }
    if((void*)p->arrayDimensions > UA_EMPTY_ARRAY_SENTINEL)
        UA_free(p->arrayDimensions);
}

static UA_StatusCode
Variant_copy(UA_Variant const *src, UA_Variant *dst, const UA_DataType *_) {
    size_t length = src->arrayLength;
    if(UA_Variant_isScalar(src))
        length = 1;
    UA_StatusCode retval = UA_Array_copy(src->data, length,
                                         &dst->data, src->type);
    if(retval != UA_STATUSCODE_GOOD)
        return retval;
    dst->arrayLength = src->arrayLength;
    dst->type = src->type;
    if(src->arrayDimensions) {
        retval = UA_Array_copy(src->arrayDimensions, src->arrayDimensionsSize,
            (void**)&dst->arrayDimensions, &UA_TYPES[UA_TYPES_INT32]);
        if(retval != UA_STATUSCODE_GOOD)
            return retval;
        dst->arrayDimensionsSize = src->arrayDimensionsSize;
    }
    return UA_STATUSCODE_GOOD;
}

void
UA_Variant_setScalar(UA_Variant *v, void * UA_RESTRICT p,
                     const UA_DataType *type) {
    UA_Variant_init(v);
    v->type = type;
    v->arrayLength = 0;
    v->data = p;
}

UA_StatusCode
UA_Variant_setScalarCopy(UA_Variant *v, const void *p,
                         const UA_DataType *type) {
    void *n = UA_malloc(type->memSize);
    if(!n)
        return UA_STATUSCODE_BADOUTOFMEMORY;
    UA_StatusCode retval = UA_copy(p, n, type);
    if(retval != UA_STATUSCODE_GOOD) {
        UA_free(n);
        //cppcheck-suppress memleak
        return retval;
    }
    UA_Variant_setScalar(v, n, type);
    //cppcheck-suppress memleak
    return UA_STATUSCODE_GOOD;
}

void UA_Variant_setArray(UA_Variant *v, void * UA_RESTRICT array,
                         size_t arraySize, const UA_DataType *type) {
    UA_Variant_init(v);
    v->data = array;
    v->arrayLength = arraySize;
    v->type = type;
}

UA_StatusCode
UA_Variant_setArrayCopy(UA_Variant *v, const void *array,
                        size_t arraySize, const UA_DataType *type) {
    UA_Variant_init(v);
    UA_StatusCode retval = UA_Array_copy(array, arraySize, &v->data, type);
    if(retval != UA_STATUSCODE_GOOD)
        return retval;
    v->arrayLength = arraySize;
    v->type = type;
    return UA_STATUSCODE_GOOD;
}

/* Test if a range is compatible with a variant. If yes, the following values
 * are set:
 * - total: how many elements are in the range
 * - block: how big is each contiguous block of elements in the variant that
 *   maps into the range
 * - stride: how many elements are between the blocks (beginning to beginning)
 * - first: where does the first block begin */
static UA_StatusCode
computeStrides(const UA_Variant *v, const UA_NumericRange range,
               size_t *total, size_t *block, size_t *stride, size_t *first) {
    /* Test for max array size (64bit only) */
#if (SIZE_MAX > 0xffffffff)
    if(v->arrayLength > UA_UINT32_MAX)
        return UA_STATUSCODE_BADINTERNALERROR;
#endif

    /* Test the integrity of the source variant dimensions, make dimensions
     * vector of one dimension if none defined */
    u32 arrayLength = (u32)v->arrayLength;
    const u32 *dims = &arrayLength;
    size_t dims_count = 1;
    if(v->arrayDimensionsSize > 0) {
        size_t elements = 1;
        dims_count = v->arrayDimensionsSize;
        dims = (u32*)v->arrayDimensions;
        for(size_t i = 0; i < dims_count; ++i)
            elements *= dims[i];
        if(elements != v->arrayLength)
            return UA_STATUSCODE_BADINTERNALERROR;
    }
    UA_assert(dims_count > 0);

    /* Test the integrity of the range and compute the max index used for every
     * dimension. The standard says in Part 4, Section 7.22:
     *
     * When reading a value, the indexes may not specify a range that is within
     * the bounds of the array. The Server shall return a partial result if some
     * elements exist within the range. */
    size_t count = 1;
    UA_STACKARRAY(UA_UInt32, realmax, dims_count);
    if(range.dimensionsSize != dims_count)
        return UA_STATUSCODE_BADINDEXRANGENODATA;
    for(size_t i = 0; i < dims_count; ++i) {
        if(range.dimensions[i].min > range.dimensions[i].max)
            return UA_STATUSCODE_BADINDEXRANGEINVALID;
        if(range.dimensions[i].min >= dims[i])
            return UA_STATUSCODE_BADINDEXRANGENODATA;

        if(range.dimensions[i].max < dims[i])
            realmax[i] = range.dimensions[i].max;
        else
            realmax[i] = dims[i] - 1;

        count *= (realmax[i] - range.dimensions[i].min) + 1;
    }

    *total = count;

    /* Compute the stride length and the position of the first element */
    *block = count;           /* Assume the range describes the entire array. */
    *stride = v->arrayLength; /* So it can be copied as a contiguous block.   */
    *first = 0;
    size_t running_dimssize = 1;
    UA_Boolean found_contiguous = false;
    for(size_t k = dims_count; k > 0;) {
        --k;
        size_t dimrange = 1 + realmax[k] - range.dimensions[k].min;
        if(!found_contiguous && dimrange != dims[k]) {
            /* Found the maximum block that can be copied contiguously */
            found_contiguous = true;
            *block = running_dimssize * dimrange;
            *stride = running_dimssize * dims[k];
        }
        *first += running_dimssize * range.dimensions[k].min;
        running_dimssize *= dims[k];
    }
    return UA_STATUSCODE_GOOD;
}

/* Is the type string-like? */
static UA_Boolean
isStringLike(const UA_DataType *type) {
    if(type == &UA_TYPES[UA_TYPES_STRING] ||
       type == &UA_TYPES[UA_TYPES_BYTESTRING] ||
       type == &UA_TYPES[UA_TYPES_XMLELEMENT])
        return true;
    return false;
}

/* Returns the part of the string that lies within the rangedimension */
static UA_StatusCode
copySubString(const UA_String *src, UA_String *dst,
              const UA_NumericRangeDimension *dim) {
    if(dim->min > dim->max)
        return UA_STATUSCODE_BADINDEXRANGEINVALID;
    if(dim->min >= src->length)
        return UA_STATUSCODE_BADINDEXRANGENODATA;

    size_t length;
    if(dim->max < src->length)
       length = dim->max - dim->min + 1;
    else
        length = src->length - dim->min;

    UA_StatusCode retval = UA_ByteString_allocBuffer(dst, length);
    if(retval != UA_STATUSCODE_GOOD)
        return retval;

    memcpy(dst->data, &src->data[dim->min], length);
    return UA_STATUSCODE_GOOD;
}

UA_StatusCode
UA_Variant_copyRange(const UA_Variant *src, UA_Variant *dst,
                     const UA_NumericRange range) {
    if(!src->type)
        return UA_STATUSCODE_BADINVALIDARGUMENT;
    UA_Boolean isScalar = UA_Variant_isScalar(src);
    UA_Boolean stringLike = isStringLike(src->type);
    UA_Variant arraySrc;

    /* Extract the range for copying at this level. The remaining range is dealt
     * with in the "scalar" type that may define an array by itself (string,
     * variant, ...). */
    UA_NumericRange thisrange, nextrange;
    UA_NumericRangeDimension scalarThisDimension = {0,0}; /* a single entry */
    if(isScalar) {
        /* Replace scalar src with array of length 1 */
        arraySrc = *src;
        arraySrc.arrayLength = 1;
        src = &arraySrc;
        /* Deal with all range dimensions within the scalar */
        thisrange.dimensions = &scalarThisDimension;
        thisrange.dimensionsSize = 1;
        nextrange = range;
    } else {
        /* Deal with as many range dimensions as possible right now */
        size_t dims = src->arrayDimensionsSize;
        if(dims == 0)
            dims = 1;
        if(dims > range.dimensionsSize)
            return UA_STATUSCODE_BADINDEXRANGEINVALID;
       thisrange = range;
       thisrange.dimensionsSize = dims;
       nextrange.dimensions = &range.dimensions[dims];
       nextrange.dimensionsSize = range.dimensionsSize - dims;
    }

    /* Compute the strides */
    size_t count, block, stride, first;
    UA_StatusCode retval = computeStrides(src, thisrange, &count,
                                          &block, &stride, &first);
    if(retval != UA_STATUSCODE_GOOD)
        return retval;

    /* Allocate the array */
    UA_Variant_init(dst);
    dst->data = UA_Array_new(count, src->type);
    if(!dst->data)
        return UA_STATUSCODE_BADOUTOFMEMORY;

    /* Copy the range */
    size_t block_count = count / block;
    size_t elem_size = src->type->memSize;
    uintptr_t nextdst = (uintptr_t)dst->data;
    uintptr_t nextsrc = (uintptr_t)src->data + (elem_size * first);
    if(nextrange.dimensionsSize == 0) {
        /* no nextrange */
        if(src->type->pointerFree) {
            for(size_t i = 0; i < block_count; ++i) {
                memcpy((void*)nextdst, (void*)nextsrc, elem_size * block);
                nextdst += block * elem_size;
                nextsrc += stride * elem_size;
            }
        } else {
            for(size_t i = 0; i < block_count; ++i) {
                for(size_t j = 0; j < block; ++j) {
                    retval = UA_copy((const void*)nextsrc,
                                     (void*)nextdst, src->type);
                    nextdst += elem_size;
                    nextsrc += elem_size;
                }
                nextsrc += (stride - block) * elem_size;
            }
        }
    } else {
        /* nextrange can only be used for variants and stringlike with remaining
         * range of dimension 1 */
        if(src->type != &UA_TYPES[UA_TYPES_VARIANT]) {
            if(!stringLike)
                retval = UA_STATUSCODE_BADINDEXRANGENODATA;
            if(nextrange.dimensionsSize != 1)
                retval = UA_STATUSCODE_BADINDEXRANGENODATA;
        }

        /* Copy the content */
        for(size_t i = 0; i < block_count; ++i) {
            for(size_t j = 0; j < block && retval == UA_STATUSCODE_GOOD; ++j) {
                if(stringLike)
                    retval = copySubString((const UA_String*)nextsrc,
                                           (UA_String*)nextdst,
                                           nextrange.dimensions);
                else
                    retval = UA_Variant_copyRange((const UA_Variant*)nextsrc,
                                                  (UA_Variant*)nextdst,
                                                  nextrange);
                nextdst += elem_size;
                nextsrc += elem_size;
            }
            nextsrc += (stride - block) * elem_size;
        }
    }

    /* Clean up if copying failed */
    if(retval != UA_STATUSCODE_GOOD) {
        UA_Array_delete(dst->data, count, src->type);
        dst->data = NULL;
        return retval;
    }

    /* Done if scalar */
    dst->type = src->type;
    if(isScalar)
        return retval;

    /* Copy array dimensions */
    dst->arrayLength = count;
    if(src->arrayDimensionsSize > 0) {
        dst->arrayDimensions =
            (u32*)UA_Array_new(thisrange.dimensionsSize, &UA_TYPES[UA_TYPES_UINT32]);
        if(!dst->arrayDimensions) {
            Variant_clear(dst, NULL);
            return UA_STATUSCODE_BADOUTOFMEMORY;
        }
        dst->arrayDimensionsSize = thisrange.dimensionsSize;
        for(size_t k = 0; k < thisrange.dimensionsSize; ++k)
            dst->arrayDimensions[k] =
                thisrange.dimensions[k].max - thisrange.dimensions[k].min + 1;
    }
    return UA_STATUSCODE_GOOD;
}

/* TODO: Allow ranges to reach inside a scalars that are array-like, e.g.
 * variant and strings. This is already possible for reading... */
static UA_StatusCode
Variant_setRange(UA_Variant *v, void *array, size_t arraySize,
                 const UA_NumericRange range, UA_Boolean copy) {
    /* Compute the strides */
    size_t count, block, stride, first;
    UA_StatusCode retval = computeStrides(v, range, &count,
                                          &block, &stride, &first);
    if(retval != UA_STATUSCODE_GOOD)
        return retval;
    if(count != arraySize)
        return UA_STATUSCODE_BADINDEXRANGEINVALID;

    /* Move/copy the elements */
    size_t block_count = count / block;
    size_t elem_size = v->type->memSize;
    uintptr_t nextdst = (uintptr_t)v->data + (first * elem_size);
    uintptr_t nextsrc = (uintptr_t)array;
    if(v->type->pointerFree || !copy) {
        for(size_t i = 0; i < block_count; ++i) {
            memcpy((void*)nextdst, (void*)nextsrc, elem_size * block);
            nextsrc += block * elem_size;
            nextdst += stride * elem_size;
        }
    } else {
        for(size_t i = 0; i < block_count; ++i) {
            for(size_t j = 0; j < block; ++j) {
                clearJumpTable[v->type->typeKind]((void*)nextdst, v->type);
                retval |= UA_copy((void*)nextsrc, (void*)nextdst, v->type);
                nextdst += elem_size;
                nextsrc += elem_size;
            }
            nextdst += (stride - block) * elem_size;
        }
    }

    /* If members were moved, initialize original array to prevent reuse */
    if(!copy && !v->type->pointerFree)
        memset(array, 0, sizeof(elem_size)*arraySize);

    return retval;
}

UA_StatusCode
UA_Variant_setRange(UA_Variant *v, void * UA_RESTRICT array,
                    size_t arraySize, const UA_NumericRange range) {
    return Variant_setRange(v, array, arraySize, range, false);
}

UA_StatusCode
UA_Variant_setRangeCopy(UA_Variant *v, const void *array,
                        size_t arraySize, const UA_NumericRange range) {
    return Variant_setRange(v, (void*)(uintptr_t)array,
                            arraySize, range, true);
}

/* LocalizedText */
static void
LocalizedText_clear(UA_LocalizedText *p, const UA_DataType *_) {
    String_clear(&p->locale, NULL);
    String_clear(&p->text, NULL);
}

static UA_StatusCode
LocalizedText_copy(UA_LocalizedText const *src, UA_LocalizedText *dst,
                   const UA_DataType *_) {
    UA_StatusCode retval = UA_String_copy(&src->locale, &dst->locale);
    retval |= UA_String_copy(&src->text, &dst->text);
    return retval;
}

/* DataValue */
static void
DataValue_clear(UA_DataValue *p, const UA_DataType *_) {
    Variant_clear(&p->value, NULL);
}

static UA_StatusCode
DataValue_copy(UA_DataValue const *src, UA_DataValue *dst,
               const UA_DataType *_) {
    memcpy(dst, src, sizeof(UA_DataValue));
    UA_Variant_init(&dst->value);
    UA_StatusCode retval = Variant_copy(&src->value, &dst->value, NULL);
    if(retval != UA_STATUSCODE_GOOD)
        DataValue_clear(dst, NULL);
    return retval;
}

/* DiagnosticInfo */
static void
DiagnosticInfo_clear(UA_DiagnosticInfo *p, const UA_DataType *_) {
    String_clear(&p->additionalInfo, NULL);
    if(p->hasInnerDiagnosticInfo && p->innerDiagnosticInfo) {
        DiagnosticInfo_clear(p->innerDiagnosticInfo, NULL);
        UA_free(p->innerDiagnosticInfo);
    }
}

static UA_StatusCode
DiagnosticInfo_copy(UA_DiagnosticInfo const *src, UA_DiagnosticInfo *dst,
                    const UA_DataType *_) {
    memcpy(dst, src, sizeof(UA_DiagnosticInfo));
    UA_String_init(&dst->additionalInfo);
    dst->innerDiagnosticInfo = NULL;
    UA_StatusCode retval = UA_STATUSCODE_GOOD;
    if(src->hasAdditionalInfo)
       retval = UA_String_copy(&src->additionalInfo, &dst->additionalInfo);
    if(src->hasInnerDiagnosticInfo && src->innerDiagnosticInfo) {
        dst->innerDiagnosticInfo = (UA_DiagnosticInfo*)UA_malloc(sizeof(UA_DiagnosticInfo));
        if(dst->innerDiagnosticInfo) {
            retval |= DiagnosticInfo_copy(src->innerDiagnosticInfo,
                                          dst->innerDiagnosticInfo, NULL);
            dst->hasInnerDiagnosticInfo = true;
        } else {
            dst->hasInnerDiagnosticInfo = false;
            retval |= UA_STATUSCODE_BADOUTOFMEMORY;
        }
    }
    return retval;
}

/********************/
/* Structured Types */
/********************/

void *
UA_new(const UA_DataType *type) {
    void *p = UA_calloc(1, type->memSize);
    return p;
}

static UA_StatusCode
copyByte(const u8 *src, u8 *dst, const UA_DataType *_) {
    *dst = *src;
    return UA_STATUSCODE_GOOD;
}

static UA_StatusCode
copy2Byte(const u16 *src, u16 *dst, const UA_DataType *_) {
    *dst = *src;
    return UA_STATUSCODE_GOOD;
}

static UA_StatusCode
copy4Byte(const u32 *src, u32 *dst, const UA_DataType *_) {
    *dst = *src;
    return UA_STATUSCODE_GOOD;
}

static UA_StatusCode
copy8Byte(const u64 *src, u64 *dst, const UA_DataType *_) {
    *dst = *src;
    return UA_STATUSCODE_GOOD;
}

static UA_StatusCode
copyGuid(const UA_Guid *src, UA_Guid *dst, const UA_DataType *_) {
    *dst = *src;
    return UA_STATUSCODE_GOOD;
}

static UA_StatusCode
copyStructure(const void *src, void *dst, const UA_DataType *type) {
    UA_StatusCode retval = UA_STATUSCODE_GOOD;
    uintptr_t ptrs = (uintptr_t)src;
    uintptr_t ptrd = (uintptr_t)dst;
    const UA_DataType *typelists[2] = { UA_TYPES, &type[-type->typeIndex] };
    for(size_t i = 0; i < type->membersSize; ++i) {
        const UA_DataTypeMember *m= &type->members[i];
        const UA_DataType *mt = &typelists[!m->namespaceZero][m->memberTypeIndex];
        if(!m->isArray) {
            ptrs += m->padding;
            ptrd += m->padding;
            retval |= copyJumpTable[mt->typeKind]((const void*)ptrs, (void*)ptrd, mt);
            ptrs += mt->memSize;
            ptrd += mt->memSize;
        } else {
            ptrs += m->padding;
            ptrd += m->padding;
            size_t *dst_size = (size_t*)ptrd;
            const size_t size = *((const size_t*)ptrs);
            ptrs += sizeof(size_t);
            ptrd += sizeof(size_t);
            retval |= UA_Array_copy(*(void* const*)ptrs, size, (void**)ptrd, mt);
            if(retval == UA_STATUSCODE_GOOD)
                *dst_size = size;
            else
                *dst_size = 0;
            ptrs += sizeof(void*);
            ptrd += sizeof(void*);
        }
    }
    return retval;
}

static UA_StatusCode
copyNotImplemented(const void *src, void *dst, const UA_DataType *type) {
    return UA_STATUSCODE_BADNOTIMPLEMENTED;
}

const UA_copySignature copyJumpTable[UA_DATATYPEKINDS] = {
    (UA_copySignature)copyByte, /* Boolean */
    (UA_copySignature)copyByte, /* SByte */
    (UA_copySignature)copyByte, /* Byte */
    (UA_copySignature)copy2Byte, /* Int16 */
    (UA_copySignature)copy2Byte, /* UInt16 */
    (UA_copySignature)copy4Byte, /* Int32 */
    (UA_copySignature)copy4Byte, /* UInt32 */
    (UA_copySignature)copy8Byte, /* Int64 */
    (UA_copySignature)copy8Byte, /* UInt64 */
    (UA_copySignature)copy4Byte, /* Float */
    (UA_copySignature)copy8Byte, /* Double */
    (UA_copySignature)String_copy,
    (UA_copySignature)copy8Byte, /* DateTime */
    (UA_copySignature)copyGuid, /* Guid */
    (UA_copySignature)String_copy, /* ByteString */
    (UA_copySignature)String_copy, /* XmlElement */
    (UA_copySignature)NodeId_copy,
    (UA_copySignature)ExpandedNodeId_copy,
    (UA_copySignature)copy4Byte, /* StatusCode */
    (UA_copySignature)QualifiedName_copy,
    (UA_copySignature)LocalizedText_copy,
    (UA_copySignature)ExtensionObject_copy,
    (UA_copySignature)DataValue_copy,
    (UA_copySignature)Variant_copy,
    (UA_copySignature)DiagnosticInfo_copy,
    (UA_copySignature)copyNotImplemented, /* Decimal */
    (UA_copySignature)copy4Byte, /* Enumeration */
    (UA_copySignature)copyStructure,
    (UA_copySignature)copyNotImplemented, /* Structure with Optional Fields */
    (UA_copySignature)copyNotImplemented, /* Union */
    (UA_copySignature)copyNotImplemented /* BitfieldCluster*/
};

UA_StatusCode
UA_copy(const void *src, void *dst, const UA_DataType *type) {
    memset(dst, 0, type->memSize); /* init */
    UA_StatusCode retval = copyJumpTable[type->typeKind](src, dst, type);
    if(retval != UA_STATUSCODE_GOOD)
        UA_clear(dst, type);
    return retval;
}

static void
clearStructure(void *p, const UA_DataType *type) {
    uintptr_t ptr = (uintptr_t)p;
    const UA_DataType *typelists[2] = { UA_TYPES, &type[-type->typeIndex] };
    for(size_t i = 0; i < type->membersSize; ++i) {
        const UA_DataTypeMember *m = &type->members[i];
        const UA_DataType *mt = &typelists[!m->namespaceZero][m->memberTypeIndex];
        if(!m->isArray) {
            ptr += m->padding;
            clearJumpTable[mt->typeKind]((void*)ptr, mt);
            ptr += mt->memSize;
        } else {
            ptr += m->padding;
            size_t length = *(size_t*)ptr;
            ptr += sizeof(size_t);
            UA_Array_delete(*(void**)ptr, length, mt);
            ptr += sizeof(void*);
        }
    }
}

static void nopClear(void *p, const UA_DataType *type) { }

const
UA_clearSignature clearJumpTable[UA_DATATYPEKINDS] = {
    (UA_clearSignature)nopClear, /* Boolean */
    (UA_clearSignature)nopClear, /* SByte */
    (UA_clearSignature)nopClear, /* Byte */
    (UA_clearSignature)nopClear, /* Int16 */
    (UA_clearSignature)nopClear, /* UInt16 */
    (UA_clearSignature)nopClear, /* Int32 */
    (UA_clearSignature)nopClear, /* UInt32 */
    (UA_clearSignature)nopClear, /* Int64 */
    (UA_clearSignature)nopClear, /* UInt64 */
    (UA_clearSignature)nopClear, /* Float */
    (UA_clearSignature)nopClear, /* Double */
    (UA_clearSignature)String_clear, /* String */
    (UA_clearSignature)nopClear, /* DateTime */
    (UA_clearSignature)nopClear, /* Guid */
    (UA_clearSignature)String_clear, /* ByteString */
    (UA_clearSignature)String_clear, /* XmlElement */
    (UA_clearSignature)NodeId_clear,
    (UA_clearSignature)ExpandedNodeId_clear,
    (UA_clearSignature)nopClear, /* StatusCode */
    (UA_clearSignature)QualifiedName_clear,
    (UA_clearSignature)LocalizedText_clear,
    (UA_clearSignature)ExtensionObject_clear,
    (UA_clearSignature)DataValue_clear,
    (UA_clearSignature)Variant_clear,
    (UA_clearSignature)DiagnosticInfo_clear,
    (UA_clearSignature)nopClear, /* Decimal, not implemented */
    (UA_clearSignature)nopClear, /* Enumeration */
    (UA_clearSignature)clearStructure,
    (UA_clearSignature)nopClear, /* Struct with Optional Fields, not implemented*/
    (UA_clearSignature)nopClear, /* Union, not implemented*/
    (UA_clearSignature)nopClear /* BitfieldCluster, not implemented*/
};

void
UA_clear(void *p, const UA_DataType *type) {
    clearJumpTable[type->typeKind](p, type);
    memset(p, 0, type->memSize); /* init */
}

void
UA_delete(void *p, const UA_DataType *type) {
    clearJumpTable[type->typeKind](p, type);
    UA_free(p);
}

/******************/
/* Array Handling */
/******************/

void *
UA_Array_new(size_t size, const UA_DataType *type) {
    if(size > UA_INT32_MAX)
        return NULL;
    if(size == 0)
        return UA_EMPTY_ARRAY_SENTINEL;
    return UA_calloc(size, type->memSize);
}

UA_StatusCode
UA_Array_copy(const void *src, size_t size,
              void **dst, const UA_DataType *type) {
    if(size == 0) {
        if(src == NULL)
            *dst = NULL;
        else
            *dst= UA_EMPTY_ARRAY_SENTINEL;
        return UA_STATUSCODE_GOOD;
    }

    if(!type)
        return UA_STATUSCODE_BADINTERNALERROR;

    /* calloc, so we don't have to check retval in every iteration of copying */
    *dst = UA_calloc(size, type->memSize);
    if(!*dst)
        return UA_STATUSCODE_BADOUTOFMEMORY;

    if(type->pointerFree) {
        memcpy(*dst, src, type->memSize * size);
        return UA_STATUSCODE_GOOD;
    }

    uintptr_t ptrs = (uintptr_t)src;
    uintptr_t ptrd = (uintptr_t)*dst;
    UA_StatusCode retval = UA_STATUSCODE_GOOD;
    for(size_t i = 0; i < size; ++i) {
        retval |= UA_copy((void*)ptrs, (void*)ptrd, type);
        ptrs += type->memSize;
        ptrd += type->memSize;
    }
    if(retval != UA_STATUSCODE_GOOD) {
        UA_Array_delete(*dst, size, type);
        *dst = NULL;
    }
    return retval;
}

void
UA_Array_delete(void *p, size_t size, const UA_DataType *type) {
    if(!type->pointerFree) {
        uintptr_t ptr = (uintptr_t)p;
        for(size_t i = 0; i < size; ++i) {
            UA_clear((void*)ptr, type);
            ptr += type->memSize;
        }
    }
    UA_free((void*)((uintptr_t)p & ~(uintptr_t)UA_EMPTY_ARRAY_SENTINEL));
}

UA_Boolean
UA_DataType_isNumeric(const UA_DataType *type) {
    /* All data types between UA_TYPES_BOOLEAN and UA_TYPES_DOUBLE are numeric */
    for(size_t i = UA_TYPES_BOOLEAN; i <= UA_TYPES_DOUBLE; ++i)
        if(&UA_TYPES[i] == type)
            return true;
    return false;
}

/**********************/
/* Parse NumericRange */
/**********************/

static size_t
readDimension(UA_Byte *buf, size_t buflen, UA_NumericRangeDimension *dim) {
    size_t progress = UA_readNumber(buf, buflen, &dim->min);
    if(progress == 0)
        return 0;
    if(buflen <= progress + 1 || buf[progress] != ':') {
        dim->max = dim->min;
        return progress;
    }

    ++progress;
    size_t progress2 = UA_readNumber(&buf[progress], buflen - progress, &dim->max);
    if(progress2 == 0)
        return 0;

    /* invalid range */
    if(dim->min >= dim->max)
        return 0;

    return progress + progress2;
}

UA_StatusCode
UA_NumericRange_parseFromString(UA_NumericRange *range, const UA_String *str) {
    size_t idx = 0;
    size_t dimensionsMax = 0;
    UA_NumericRangeDimension *dimensions = NULL;
    UA_StatusCode retval = UA_STATUSCODE_GOOD;
    size_t offset = 0;
    while(true) {
        /* alloc dimensions */
        if(idx >= dimensionsMax) {
            UA_NumericRangeDimension *newds;
            size_t newdssize = sizeof(UA_NumericRangeDimension) * (dimensionsMax + 2);
            newds = (UA_NumericRangeDimension*)UA_realloc(dimensions, newdssize);
            if(!newds) {
                retval = UA_STATUSCODE_BADOUTOFMEMORY;
                break;
            }
            dimensions = newds;
            dimensionsMax = dimensionsMax + 2;
        }

        /* read the dimension */
        size_t progress = readDimension(&str->data[offset], str->length - offset,
                                        &dimensions[idx]);
        if(progress == 0) {
            retval = UA_STATUSCODE_BADINDEXRANGEINVALID;
            break;
        }
        offset += progress;
        ++idx;

        /* loop into the next dimension */
        if(offset >= str->length)
            break;

        if(str->data[offset] != ',') {
            retval = UA_STATUSCODE_BADINDEXRANGEINVALID;
            break;
        }
        ++offset;
    }

    if(retval == UA_STATUSCODE_GOOD && idx > 0) {
        range->dimensions = dimensions;
        range->dimensionsSize = idx;
    } else
        UA_free(dimensions);

    return retval;
}