// Copyright 2019 Joe Drago. All rights reserved.

// SPDX-License-Identifier: BSD-2-Clause

#include "avif/internal.h"

#include <assert.h>

#include <math.h>

#include <stdint.h>

#include <string.h>

float avifRoundf(float v)

{

    return floorf(v + 0.5f);

}

// Thanks, Rob Pike! https://commandcenter.blogspot.nl/2012/04/byte-order-fallacy.html

uint16_t avifHTONS(uint16_t s)

{

    uint16_t result = 0;

    uint8_t * data = (uint8_t *)&result;

    data[0] = (s >> 8) & 0xff;

    data[1] = (s >> 0) & 0xff;

    return result;

}

uint16_t avifNTOHS(uint16_t s)

{

    const uint8_t * data = (const uint8_t *)&s;

    return (uint16_t)((data[1] << 0) | (data[0] << 8));

}

uint16_t avifCTOHS(uint16_t s)

{

    const uint8_t * data = (const uint8_t *)&s;

    return (uint16_t)((data[0] << 0) | (data[1] << 8));

}

uint32_t avifHTONL(uint32_t l)

{

    uint32_t result = 0;

    uint8_t * data = (uint8_t *)&result;

    data[0] = (l >> 24) & 0xff;

    data[1] = (l >> 16) & 0xff;

    data[2] = (l >> 8) & 0xff;

    data[3] = (l >> 0) & 0xff;

    return result;

}

uint32_t avifNTOHL(uint32_t l)

{

    const uint8_t * data = (const uint8_t *)&l;

    return ((uint32_t)data[3] << 0) | ((uint32_t)data[2] << 8) | ((uint32_t)data[1] << 16) | ((uint32_t)data[0] << 24);

}

uint32_t avifCTOHL(uint32_t l)

{

    const uint8_t * data = (const uint8_t *)&l;

    return ((uint32_t)data[0] << 0) | ((uint32_t)data[1] << 8) | ((uint32_t)data[2] << 16) | ((uint32_t)data[3] << 24);

}

uint64_t avifHTON64(uint64_t l)

{

    uint64_t result = 0;

    uint8_t * data = (uint8_t *)&result;

    data[0] = (l >> 56) & 0xff;

    data[1] = (l >> 48) & 0xff;

    data[2] = (l >> 40) & 0xff;

    data[3] = (l >> 32) & 0xff;

    data[4] = (l >> 24) & 0xff;

    data[5] = (l >> 16) & 0xff;

    data[6] = (l >> 8) & 0xff;

    data[7] = (l >> 0) & 0xff;

    return result;

}

uint64_t avifNTOH64(uint64_t l)

{

    const uint8_t * data = (const uint8_t *)&l;

    return ((uint64_t)data[7] << 0) | ((uint64_t)data[6] << 8) | ((uint64_t)data[5] << 16) | ((uint64_t)data[4] << 24) |

           ((uint64_t)data[3] << 32) | ((uint64_t)data[2] << 40) | ((uint64_t)data[1] << 48) | ((uint64_t)data[0] << 56);

}

AVIF_ARRAY_DECLARE(avifArrayInternal, uint8_t, ptr);

// On error, this function must set arr->ptr to NULL and both arr->count and arr->capacity to 0.

avifBool avifArrayCreate(void * arrayStruct, uint32_t elementSize, uint32_t initialCapacity)

{

    avifArrayInternal * arr = (avifArrayInternal *)arrayStruct;

    arr->elementSize = elementSize ? elementSize : 1;

    arr->count = 0;

    arr->capacity = initialCapacity;

    if (arr->capacity > SIZE_MAX / arr->elementSize) {

        arr->ptr = NULL;

        arr->capacity = 0;

        return AVIF_FALSE;

    }

    size_t byteCount = (size_t)arr->elementSize * arr->capacity;

    arr->ptr = (uint8_t *)avifAlloc(byteCount);

    if (!arr->ptr) {

        arr->capacity = 0;

        return AVIF_FALSE;

    }

    memset(arr->ptr, 0, byteCount);

    return AVIF_TRUE;

}

void * avifArrayPush(void * arrayStruct)

{

    avifArrayInternal * arr = (avifArrayInternal *)arrayStruct;

    if (arr->count == arr->capacity) {

        uint8_t * oldPtr = arr->ptr;

        size_t oldByteCount = (size_t)arr->elementSize * arr->capacity;

        if (oldByteCount > SIZE_MAX / 2 || arr->capacity > UINT32_MAX / 2) {

            return NULL;

        }

        size_t newByteCount = oldByteCount * 2;

        uint8_t * newPtr = (uint8_t *)avifAlloc(newByteCount);

        if (newPtr == NULL) {

            return NULL;

        }

        arr->ptr = newPtr;

        memset(arr->ptr + oldByteCount, 0, oldByteCount);

        memcpy(arr->ptr, oldPtr, oldByteCount);

        arr->capacity *= 2;

        avifFree(oldPtr);

    }

    ++arr->count;

    return &arr->ptr[(arr->count - 1) * (size_t)arr->elementSize];

}

void avifArrayPop(void * arrayStruct)

{

    avifArrayInternal * arr = (avifArrayInternal *)arrayStruct;

    assert(arr->count > 0);

    --arr->count;

    memset(&arr->ptr[arr->count * (size_t)arr->elementSize], 0, arr->elementSize);

}

void avifArrayDestroy(void * arrayStruct)

{

    avifArrayInternal * arr = (avifArrayInternal *)arrayStruct;

    if (arr->ptr) {

        avifFree(arr->ptr);

        arr->ptr = NULL;

    }

    memset(arr, 0, sizeof(avifArrayInternal));

}

// |a| and |b| hold int32_t values. The int64_t type is used so that we can negate INT32_MIN without

// overflowing int32_t.

static int64_t calcGCD(int64_t a, int64_t b)

{

    if (a < 0) {

        a *= -1;

    }

    if (b < 0) {

        b *= -1;

    }

    while (b != 0) {

        int64_t r = a % b;

        a = b;

        b = r;

    }

    return a;

}

void avifFractionSimplify(avifFraction * f)

{

    int64_t gcd = calcGCD(f->n, f->d);

    if (gcd > 1) {

        f->n = (int32_t)(f->n / gcd);

        f->d = (int32_t)(f->d / gcd);

    }

}

static avifBool overflowsInt32(int64_t x)

{

    return (x < INT32_MIN) || (x > INT32_MAX);

}

avifBool avifFractionCD(avifFraction * a, avifFraction * b)

{

    avifFractionSimplify(a);

    avifFractionSimplify(b);

    if (a->d != b->d) {

        const int64_t ad = a->d;

        const int64_t bd = b->d;

        const int64_t anNew = a->n * bd;

        const int64_t adNew = a->d * bd;

        const int64_t bnNew = b->n * ad;

        const int64_t bdNew = b->d * ad;

        if (overflowsInt32(anNew) || overflowsInt32(adNew) || overflowsInt32(bnNew) || overflowsInt32(bdNew)) {

            return AVIF_FALSE;

        }

        a->n = (int32_t)anNew;

        a->d = (int32_t)adNew;

        b->n = (int32_t)bnNew;

        b->d = (int32_t)bdNew;

    }

    return AVIF_TRUE;

}

avifBool avifFractionAdd(avifFraction a, avifFraction b, avifFraction * result)

{

    if (!avifFractionCD(&a, &b)) {

        return AVIF_FALSE;

    }

    const int64_t resultN = (int64_t)a.n + b.n;

    if (overflowsInt32(resultN)) {

        return AVIF_FALSE;

    }

    result->n = (int32_t)resultN;

    result->d = a.d;

    avifFractionSimplify(result);

    return AVIF_TRUE;

}

avifBool avifFractionSub(avifFraction a, avifFraction b, avifFraction * result)

{

    if (!avifFractionCD(&a, &b)) {

        return AVIF_FALSE;

    }

    const int64_t resultN = (int64_t)a.n - b.n;

    if (overflowsInt32(resultN)) {

        return AVIF_FALSE;

    }

    result->n = (int32_t)resultN;

    result->d = a.d;

    avifFractionSimplify(result);

    return AVIF_TRUE;

}

static avifBool avifDoubleToUnsignedFractionImpl(double v, uint32_t maxNumerator, uint32_t * numerator, uint32_t * denominator)

{

    if (isnan(v) || v < 0 || v > maxNumerator) {

        return AVIF_FALSE;

    }

    // Maximum denominator: makes sure that the numerator is <= maxNumerator and the denominator is <= UINT32_MAX.

    const uint32_t maxD = (v <= 1) ? UINT32_MAX : (uint32_t)floor(maxNumerator / v);

    // Find the best approximation of v as a fraction using continued fractions, see

    // https://en.wikipedia.org/wiki/Continued_fraction

    *denominator = 1;

    uint32_t previousD = 0;

    double currentV = v - floor(v);

    int iter = 0;

    // Set a maximum number of iterations to be safe. Most numbers should

    // converge in less than ~20 iterations.

    // The golden ratio is the worst case and takes 39 iterations.

    const int maxIter = 39;

    while (iter < maxIter) {

        const double numeratorDouble = (double)(*denominator) * v;

        assert(numeratorDouble <= maxNumerator);

        *numerator = (uint32_t)round(numeratorDouble);

        if (fabs(numeratorDouble - (*numerator)) == 0.0) {

            return AVIF_TRUE;

        }

        currentV = 1.0 / currentV;

        const double newD = previousD + floor(currentV) * (*denominator);

        if (newD > (double)maxD) {

            // This is the best we can do with a denominator <= max_d.

            return AVIF_TRUE;

        }

        previousD = *denominator;

        assert(newD <= UINT32_MAX);

        *denominator = (uint32_t)newD;

        currentV -= floor(currentV);

        ++iter;

    }

    // Maximum number of iterations reached, return what we've found.

    // For max_iter >= 39 we shouldn't get here. max_iter can be set

    // to a lower value to speed up the algorithm if needed.

    *numerator = (uint32_t)round((double)(*denominator) * v);

    return AVIF_TRUE;

}

avifBool avifDoubleToSignedFraction(double v, avifSignedFraction * fraction)

{

    uint32_t positive_numerator;

    if (!avifDoubleToUnsignedFractionImpl(fabs(v), INT32_MAX, &positive_numerator, &fraction->d)) {

        return AVIF_FALSE;

    }

    fraction->n = (int32_t)positive_numerator;

    if (v < 0) {

        fraction->n *= -1;

    }

    return AVIF_TRUE;

}

avifBool avifDoubleToUnsignedFraction(double v, avifUnsignedFraction * fraction)

{

    return avifDoubleToUnsignedFractionImpl(v, UINT32_MAX, &fraction->n, &fraction->d);

}