1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.imaging.common;
18
19 import java.text.NumberFormat;
20
21 /**
22 * Rational number, as used by the TIFF image format.
23 * <p>
24 * 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
25 * 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
26 * stores the numerator and divisor in long (64-bit) integers, applying masks as necessary for the unsigned type.
27 */
28 public class RationalNumber extends Number {
29
30 private static final class Option {
31 public static Option factory(final RationalNumber rationalNumber, final double value) {
32 return new Option(rationalNumber, Math.abs(rationalNumber.doubleValue() - value));
33 }
34
35 public final RationalNumber rationalNumber;
36
37 public final double error;
38
39 private Option(final RationalNumber rationalNumber, final double error) {
40 this.rationalNumber = rationalNumber;
41 this.error = error;
42 }
43
44 @Override
45 public String toString() {
46 return rationalNumber.toString();
47 }
48 }
49
50 private static final long serialVersionUID = -1;
51
52 // int-precision tolerance
53 private static final double TOLERANCE = 1E-8;
54 public static final int SHALLOW_SIZE = 32;
55
56 static RationalNumber factoryMethod(long n, long d) {
57 // safer than constructor - handles values outside min/max range.
58 // also does some simple finding of common denominators.
59
60 if (n > Integer.MAX_VALUE || n < Integer.MIN_VALUE || d > Integer.MAX_VALUE || d < Integer.MIN_VALUE) {
61 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) {
62 // brutal, imprecise truncation =(
63 // use the sign-preserving right shift operator.
64 n >>= 1;
65 d >>= 1;
66 }
67
68 if (d == 0) {
69 throw new NumberFormatException("Invalid value, numerator: " + n + ", divisor: " + d);
70 }
71 }
72
73 final long gcd = gcd(n, d);
74 d /= gcd;
75 n /= gcd;
76
77 return new RationalNumber((int) n, (int) d);
78 }
79
80 /**
81 * Gets the greatest common divisor
82 */
83 private static long gcd(final long a, final long b) {
84 if (b == 0) {
85 return a;
86 }
87 return gcd(b, a % b);
88 }
89
90 /**
91 * Calculate rational number using successive approximations.
92 *
93 * @param value rational number double value
94 * @return the RationalNumber representation of the double value
95 */
96 public static RationalNumber valueOf(double value) {
97 if (value >= Integer.MAX_VALUE) {
98 return new RationalNumber(Integer.MAX_VALUE, 1);
99 }
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 RationalNumber l;
111 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 = RationalNumber.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 if (unsignedType) {
260 // An instance of an unsigned type can be negated if and only if
261 // its high-order bit (the sign bit) is clear. If the bit is set,
262 // the value will be too large to convert to a signed type.
263 // In such a case it is necessary to adjust the numerator and denominator
264 // by their greatest common divisor (gcd), if one exists.
265 // If no non-zero common divisor exists, an exception is thrown.
266 if (n >> 31 == 1) {
267 // the unsigned value is so large that the high-order bit is set
268 // it cannot be converted to a negative number. Check to see
269 // whether there is an option to reduce its magnitude.
270 final long g = gcd(numerator, divisor);
271 if (g != 0) {
272 n /= g;
273 d /= g;
274 }
275 if (n >> 31 == 1) {
276 throw new NumberFormatException("Unsigned numerator is too large to negate " + numerator);
277 }
278 }
279 }
280 return new RationalNumber(-n, d, false);
281 }
282
283 public String toDisplayString() {
284 if (numerator % divisor == 0) {
285 return Long.toString(numerator / divisor);
286 }
287 final NumberFormat nf = NumberFormat.getInstance();
288 nf.setMaximumFractionDigits(3);
289 return nf.format((double) numerator / (double) divisor);
290 }
291
292 @Override
293 public String toString() {
294 if (divisor == 0) {
295 return "Invalid rational (" + numerator + "/" + divisor + ")";
296 }
297 final NumberFormat nf = NumberFormat.getInstance();
298
299 if (numerator % divisor == 0) {
300 return nf.format(numerator / divisor);
301 }
302 return numerator + "/" + divisor + " (" + nf.format((double) numerator / divisor) + ")";
303 }
304
305 }