src/utils.c

// 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);
}