/** Hilfsfunktion: Multi-Wort-Addition (Vorzeichenlos)
 *
 * @param[in,out] akku: 1. Summand, Summe
 * @param[in] a: 2. Summand
 * @param[in] len: Groesse des Worts
 * @return Overflow J/N */
bool multiwordAdd(uint32_t akku[], uint32_t a, size_t len)
{
    uint64_t tmp = a;
    for( size_t ii = 0; ii<len; ii++ )
    {
        tmp += akku[ii];
        akku[ii] = tmp & 0xFFFFFFFF;
        tmp>>=32;
    }

    if( tmp )
        return 1;
    else
        return 0;
}



/** Hilfsfunktion: Multi-Wort-Multiplikation (Vorzeichenlos)
 *
 * @param[in,out] akku: 1. Multiplikator, Produkt
 * @param[in] a: 2. Multiplikator
 * @param[in] len: Groesse des Worts
 * @return Overflow J/N */
bool multiwordMul(uint32_t akku[], uint32_t a, size_t len)
{
    uint64_t tmp = 0;
    for( size_t ii = 0; ii<len; ii++ )
    {
        tmp += (uint64_t) akku[ii] * a;
        akku[ii] = tmp & 0xFFFFFFFF;
        tmp>>=32;
    }

    if( tmp )
        return 1;
    else
        return 0;
}



/** Hilfsfunktion: Trunkierende Multi-Wort-Division (Vorzeichenlos)
 *
 * @param[in,out] akku: Dividend, Quotient
 * @param[in] d: Divisor
 * @param[in] len: Groesse des Worts
 * @return Unterlaubte Division J/N */
bool multiwordDiv(uint32_t akku[], uint32_t d, size_t len)
{
    if( d == 0 ) return true;

    uint64_t rem = 0;
    uint64_t q = 0;
    for( int ii = len-1; ii>=0; ii-- )
    {
        rem += akku[ii];
        q = rem/d;
        rem = rem%d;
        akku[ii] = q;
        rem <<= 32;
    }

    return false;
}



/** 64-Bit-Integer Skalieren: Multiplizieren und Dividieren (korrekt gerundet)
 *
 * ueberlaufsicher/saettigend
 * @param[in] in
 * @param[in] z Zaehler
 * @param[in] n Nenner
 * @return a*z/n korrekt gerundet */
int64_t scale_s64(int64_t in, int32_t z, int32_t n)
{
    assert( n != 0 );

    uint64_t uin;
    uint32_t uz;
    uint32_t un;


    /* Vorzeichenbehandlung */
    bool negative = false;
    if( in == INT64_MIN )
    {
        negative = !negative;
        uin = (uint64_t)INT64_MAX + 1;
    }
    else if( in < 0 )
    {
        uin = -in;
        negative = !negative;
    }
    else
    {
        uin = in;
    }

    if( z == INT32_MIN )
    {
        uz = (uint32_t)INT32_MAX + 1;
        negative = !negative;
    }
    else if( z < 0 )
    {
        uz = -z;
        negative = !negative;
    }
    else
    {
        uz = z;
    }

    if( n == INT32_MIN )
    {
        un = (uint32_t)INT32_MAX + 1;
        negative = !negative;
    }
    else if( n < 0 )
    {
        un = -n;
        negative = !negative;
    }
    else
    {
        un = n;
    }


    /* Zwischenvariablen */
    uint32_t akku[3];
    akku[0] = uin & 0xFFFFFFFF;
    akku[1] = uin>>32;
    akku[2] = 0;


    /* a * z;
       INT64_MAX * INT32_MAX < 2^94 */
    multiwordMul(akku, uz, 3);

    /* a * z + n/2
       INT64_MAX * INT32_MAX + INT32_MAX/2 < 2^94
      -INT64_MIN * -INT32_MIN - INT32_MIN/2 < 2^96 */
    multiwordAdd(akku, un/2, 3);

    /* (a * z + n/2)/n  */
    multiwordDiv(akku, un, 3);


    /* Rueckgabe vorbereiten */
    uint64_t tmp = ((uint64_t) akku[1]<<32) + akku[0];

    /* Ueberlauf ueber UINT64_T */
    bool overflow0 = !!akku[2];

    /* Ueberlauf ueber INT64_MAX / -(INT64_MIN+1)
       Fuer Ergebnis INT64_MIN trotzdem korrekter Rueckgabewert */
    bool overflow1 = tmp > ((uint64_t) INT64_MAX);


    if( negative )
    {
        if( overflow0 || overflow1 )
        {
            return INT64_MIN;
        }
        else
        {
            return -((uint64_t) tmp);
        }
    }
    else
    {
        if( overflow0 || overflow1 )
        {
            return INT64_MAX;
        }
        else
        {
            return tmp;
        }
    }
}