math_util.cpp 2.57 KB
Newer Older
Maciej Suminski's avatar
Maciej Suminski committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
/*
 * This program source code file is part of KICAD, a free EDA CAD application.
 *
 * Copyright (c) 2005 Michael Niedermayer <michaelni@gmx.at>
 * Copyright (C) CERN
 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */

#include <cmath>
#include <cstdlib>
#include <climits>
#include <math/math_util.h>

Maciej Suminski's avatar
Maciej Suminski committed
31 32
template <>
int rescale( int aNumerator, int aValue, int aDenominator )
Maciej Suminski's avatar
Maciej Suminski committed
33
{
Maciej Suminski's avatar
Maciej Suminski committed
34
    return (int) ( (int64_t) aNumerator * (int64_t) aValue / (int64_t) aDenominator );
Maciej Suminski's avatar
Maciej Suminski committed
35 36 37
}


Maciej Suminski's avatar
Maciej Suminski committed
38 39
template <>
int64_t rescale( int64_t aNumerator, int64_t aValue, int64_t aDenominator )
Maciej Suminski's avatar
Maciej Suminski committed
40 41
{
    int64_t r = 0;
Maciej Suminski's avatar
Maciej Suminski committed
42 43
    int64_t sign = ( ( aNumerator < 0 ) ? -1 : 1 ) * ( aDenominator < 0 ? -1 : 1 ) *
                                                    ( aValue < 0 ? -1 : 1 );
Maciej Suminski's avatar
Maciej Suminski committed
44

Maciej Suminski's avatar
Maciej Suminski committed
45 46 47
    int64_t a = std::abs( aNumerator );
    int64_t b = std::abs( aValue );
    int64_t c = std::abs( aDenominator );
Maciej Suminski's avatar
Maciej Suminski committed
48 49 50 51 52 53

    r = c / 2;

    if( b <= INT_MAX && c <= INT_MAX )
    {
        if( a <= INT_MAX )
Maciej Suminski's avatar
Maciej Suminski committed
54
            return sign * ( ( a * b + r ) / c );
Maciej Suminski's avatar
Maciej Suminski committed
55
        else
Maciej Suminski's avatar
Maciej Suminski committed
56
            return sign * ( a / c * b + ( a % c * b + r ) / c);
57 58 59
    }
    else
    {
Maciej Suminski's avatar
Maciej Suminski committed
60 61 62 63 64 65 66 67 68
        uint64_t a0 = a & 0xFFFFFFFF;
        uint64_t a1 = a >> 32;
        uint64_t b0 = b & 0xFFFFFFFF;
        uint64_t b1 = b >> 32;
        uint64_t t1 = a0 * b1 + a1 * b0;
        uint64_t t1a = t1 << 32;
        int i;

        a0 = a0 * b0 + t1a;
69
        a1 = a1 * b1 + ( t1 >> 32 ) + ( a0 < t1a );
Maciej Suminski's avatar
Maciej Suminski committed
70
        a0 += r;
71
        a1 += a0 < (uint64_t)r;
Maciej Suminski's avatar
Maciej Suminski committed
72 73 74

        for( i = 63; i >= 0; i-- )
        {
75
            a1  += a1 + ( ( a0 >> i ) & 1 );
Maciej Suminski's avatar
Maciej Suminski committed
76 77
            t1  += t1;

78
            if( (uint64_t) c <= a1 )
Maciej Suminski's avatar
Maciej Suminski committed
79 80 81 82 83 84 85 86 87
            {
                a1 -= c;
                t1++;
            }
        }

        return t1 * sign;
    }
}