    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.imaging.common;
    018
    019import java.text.NumberFormat;
    020
    021/**
    022 * Rational number, as used by the TIFF image format.
    023 * <p>
    024 * The TIFF format specifies two data types for rational numbers based on a pair of 32-bit integers. Rational is based on unsigned 32-bit integers and SRational
    025 * is based on signed 32-bit integers. This treatment is problematic in Java because Java does not support unsigned types. To address this challenge, this class
    026 * stores the numerator and divisor in long (64-bit) integers, applying masks as necessary for the unsigned type.
    027 */
    028public class RationalNumber extends Number {
    029
    030    private static final class Option {
    031        public static Option factory(final RationalNumber rationalNumber, final double value) {
    032            return new Option(rationalNumber, Math.abs(rationalNumber.doubleValue() - value));
    033        }
    034
    035        public final RationalNumber rationalNumber;
    036
    037        public final double error;
    038
    039        private Option(final RationalNumber rationalNumber, final double error) {
    040            this.rationalNumber = rationalNumber;
    041            this.error = error;
    042        }
    043
    044        @Override
    045        public String toString() {
    046            return rationalNumber.toString();
    047        }
    048    }
    049
    050    private static final long serialVersionUID = -1;
    051
    052    // int-precision tolerance
    053    private static final double TOLERANCE = 1E-8;
    054    public static final int SHALLOW_SIZE = 32;
    055
    056    static RationalNumber factoryMethod(long n, long d) {
    057        // safer than constructor - handles values outside min/max range.
    058        // also does some simple finding of common denominators.
    059
    060        if (n > Integer.MAX_VALUE || n < Integer.MIN_VALUE || d > Integer.MAX_VALUE || d < Integer.MIN_VALUE) {
    061            while ((n > Integer.MAX_VALUE || n < Integer.MIN_VALUE || d > Integer.MAX_VALUE || d < Integer.MIN_VALUE) && Math.abs(n) > 1 && Math.abs(d) > 1) {
    062                // brutal, imprecise truncation =(
    063                // use the sign-preserving right shift operator.
    064                n >>= 1;
    065                d >>= 1;
    066            }
    067
    068            if (d == 0) {
    069                throw new NumberFormatException("Invalid value, numerator: " + n + ", divisor: " + d);
    070            }
    071        }
    072
    073        final long gcd = gcd(n, d);
    074        d /= gcd;
    075        n /= gcd;
    076
    077        return new RationalNumber((int) n, (int) d);
    078    }
    079
    080    /**
    081     * Gets the greatest common divisor
    082     */
    083    private static long gcd(final long a, final long b) {
    084        if (b == 0) {
    085            return a;
    086        }
    087        return gcd(b, a % b);
    088    }
    089
    090    /**
    091     * Calculate rational number using successive approximations.
    092     *
    093     * @param value rational number double value
    094     * @return the RationalNumber representation of the double value
    095     */
    096    public static RationalNumber valueOf(double value) {
    097        if (value >= Integer.MAX_VALUE) {
    098            return new RationalNumber(Integer.MAX_VALUE, 1);
    099        }
    100        if (value <= -Integer.MAX_VALUE) {
    101            return new RationalNumber(-Integer.MAX_VALUE, 1);
    102        }
    103
    104        boolean negative = false;
    105        if (value < 0) {
    106            negative = true;
    107            value = Math.abs(value);
    108        }
    109
    110        final RationalNumber l;
    111        final RationalNumber h;
    112
    113        if (value == 0) {
    114            return new RationalNumber(0, 1);
    115        }
    116        if (value >= 1) {
    117            final int approx = (int) value;
    118            if (approx < value) {
    119                l = new RationalNumber(approx, 1);
    120                h = new RationalNumber(approx + 1, 1);
    121            } else {
    122                l = new RationalNumber(approx - 1, 1);
    123                h = new RationalNumber(approx, 1);
    124            }
    125        } else {
    126            final int approx = (int) (1.0 / value);
    127            if (1.0 / approx < value) {
    128                l = new RationalNumber(1, approx);
    129                h = new RationalNumber(1, approx - 1);
    130            } else {
    131                l = new RationalNumber(1, approx + 1);
    132                h = new RationalNumber(1, approx);
    133            }
    134        }
    135        Option low = Option.factory(l, value);
    136        Option high = Option.factory(h, value);
    137
    138        Option bestOption = low.error < high.error ? low : high;
    139
    140        final int maxIterations = 100; // value is quite high, actually.
    141                                       // shouldn't matter.
    142        for (int count = 0; bestOption.error > TOLERANCE && count < maxIterations; count++) {
    143            final RationalNumber mediant = factoryMethod(low.rationalNumber.numerator + high.rationalNumber.numerator,
    144                    low.rationalNumber.divisor + high.rationalNumber.divisor);
    145            final Option mediantOption = Option.factory(mediant, value);
    146
    147            if (value < mediant.doubleValue()) {
    148                if (high.error <= mediantOption.error) {
    149                    break;
    150                }
    151
    152                high = mediantOption;
    153            } else {
    154                if (low.error <= mediantOption.error) {
    155                    break;
    156                }
    157
    158                low = mediantOption;
    159            }
    160
    161            if (mediantOption.error < bestOption.error) {
    162                bestOption = mediantOption;
    163            }
    164        }
    165
    166        return negative ? bestOption.rationalNumber.negate() : bestOption.rationalNumber;
    167    }
    168
    169    // The TIFF and EXIF specifications call for the use
    170    // of 32 bit unsigned integers. Since Java does not have an
    171    // unsigned type, this class widens the type to long in order
    172    // to avoid unintended negative numbers.
    173    public final long numerator;
    174
    175    public final long divisor;
    176
    177    public final boolean unsignedType;
    178
    179    /**
    180     * Constructs an instance based on signed integers
    181     *
    182     * @param numerator a 32-bit signed integer
    183     * @param divisor   a non-zero 32-bit signed integer
    184     */
    185    public RationalNumber(final int numerator, final int divisor) {
    186        this.numerator = numerator;
    187        this.divisor = divisor;
    188        this.unsignedType = false;
    189    }
    190
    191    /**
    192     * Constructs an instance supports either signed or unsigned integers.
    193     *
    194     * @param numerator    a numerator in the indicated form (signed or unsigned)
    195     * @param divisor      a non-zero divisor in the indicated form (signed or unsigned)
    196     * @param unsignedType indicates whether the input values are to be treated as unsigned.
    197     */
    198    public RationalNumber(final int numerator, final int divisor, final boolean unsignedType) {
    199        this.unsignedType = unsignedType;
    200        if (unsignedType) {
    201            this.numerator = numerator & 0xffffffffL;
    202            this.divisor = divisor & 0xffffffffL;
    203        } else {
    204            this.numerator = numerator;
    205            this.divisor = divisor;
    206        }
    207    }
    208
    209    /**
    210     * A private constructor for methods such as negate() that create instances of this class using the content of the current instance.
    211     *
    212     * @param numerator    a valid numerator
    213     * @param divisor      a valid denominator
    214     * @param unsignedType indicates how numerator and divisor values are to be interpreted.
    215     */
    216    private RationalNumber(final long numerator, final long divisor, final boolean unsignedType) {
    217        this.numerator = numerator;
    218        this.divisor = divisor;
    219        this.unsignedType = unsignedType;
    220    }
    221
    222    @Override
    223    public double doubleValue() {
    224        return (double) numerator / (double) divisor;
    225    }
    226
    227    @Override
    228    public float floatValue() {
    229        // The computation uses double value in order to preserve
    230        // as much of the precision of the source numerator and denominator
    231        // as possible. Note that the expression
    232        // return (float)numerator/(float) denominator
    233        // could lose precision since a Java float only carries 24 bits
    234        // of precision while an integer carries 32.
    235        return (float) doubleValue();
    236    }
    237
    238    @Override
    239    public int intValue() {
    240        return (int) (numerator / divisor);
    241    }
    242
    243    @Override
    244    public long longValue() {
    245        return numerator / divisor;
    246    }
    247
    248    /**
    249     * Negates the value of the RationalNumber. If the numerator of this instance has its high-order bit set, then its value is too large to be treated as a
    250     * Java 32-bit signed integer. In such a case, the only way that a RationalNumber instance can be negated is to divide both terms by a common divisor, if a
    251     * non-zero common divisor exists. However, if no such divisor exists, there is no numerically correct way to perform the negation. When a negation cannot
    252     * be performed correctly, this method throws an unchecked exception.
    253     *
    254     * @return a valid instance with a negated value.
    255     */
    256    public RationalNumber negate() {
    257        long n = numerator;
    258        long d = divisor;
    259        // An instance of an unsigned type can be negated if and only if
    260        // its high-order bit (the sign bit) is clear. If the bit is set,
    261        // the value will be too large to convert to a signed type.
    262        // In such a case it is necessary to adjust the numerator and denominator
    263        // by their greatest common divisor (gcd), if one exists.
    264        // If no non-zero common divisor exists, an exception is thrown.
    265        if (unsignedType && n >> 31 == 1) {
    266            // the unsigned value is so large that the high-order bit is set
    267            // it cannot be converted to a negative number. Check to see
    268            // whether there is an option to reduce its magnitude.
    269            final long g = gcd(numerator, divisor);
    270            if (g != 0) {
    271                n /= g;
    272                d /= g;
    273            }
    274            if (n >> 31 == 1) {
    275                throw new NumberFormatException("Unsigned numerator is too large to negate " + numerator);
    276            }
    277        }
    278        return new RationalNumber(-n, d, false);
    279    }
    280
    281    public String toDisplayString() {
    282        if (numerator % divisor == 0) {
    283            return Long.toString(numerator / divisor);
    284        }
    285        final NumberFormat nf = NumberFormat.getInstance();
    286        nf.setMaximumFractionDigits(3);
    287        return nf.format((double) numerator / (double) divisor);
    288    }
    289
    290    @Override
    291    public String toString() {
    292        if (divisor == 0) {
    293            return "Invalid rational (" + numerator + "/" + divisor + ")";
    294        }
    295        final NumberFormat nf = NumberFormat.getInstance();
    296
    297        if (numerator % divisor == 0) {
    298            return nf.format(numerator / divisor);
    299        }
    300        return numerator + "/" + divisor + " (" + nf.format((double) numerator / divisor) + ")";
    301    }
    302
    303}