LinearTransform.cpp revision 26fddcd74252bdda95dd7c3f819353e79c622012 
1/*
2 * Copyright (C) 2011 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#define __STDC_LIMIT_MACROS
18
19#include "LinearTransform.h"
20#include <assert.h>
21
22
23// disable sanitize as these functions may intentionally overflow (see comments below).
24// the ifdef can be removed when host builds use clang.
25#if defined(__clang__)
26#define ATTRIBUTE_NO_SANITIZE_INTEGER __attribute__((no_sanitize("integer")))
27#else
28#define ATTRIBUTE_NO_SANITIZE_INTEGER
29#endif
30
31namespace android {
32
33// sanitize failure with T = int32_t and x = 0x80000000
34template<class T>
35ATTRIBUTE_NO_SANITIZE_INTEGER
36static inline T ABS(T x) { return (x < 0) ? -x : x; }
37
38// Static math methods involving linear transformations
39// remote sanitize failure on overflow case.
40ATTRIBUTE_NO_SANITIZE_INTEGER
41static bool scale_u64_to_u64(
42        uint64_t val,
43        uint32_t N,
44        uint32_t D,
45        uint64_t* res,
46        bool round_up_not_down) {
47    uint64_t tmp1, tmp2;
48    uint32_t r;
49
50    assert(res);
51    assert(D);
52
53    // Let U32(X) denote a uint32_t containing the upper 32 bits of a 64 bit
54    // integer X.
55    // Let L32(X) denote a uint32_t containing the lower 32 bits of a 64 bit
56    // integer X.
57    // Let X[A, B] with A <= B denote bits A through B of the integer X.
58    // Let (A | B) denote the concatination of two 32 bit ints, A and B.
59    // IOW X = (A | B) => U32(X) == A && L32(X) == B
60    //
61    // compute M = val * N (a 96 bit int)
62    // ---------------------------------
63    // tmp2 = U32(val) * N (a 64 bit int)
64    // tmp1 = L32(val) * N (a 64 bit int)
65    // which means
66    // M = val * N = (tmp2 << 32) + tmp1
67    tmp2 = (val >> 32) * N;
68    tmp1 = (val & UINT32_MAX) * N;
69
70    // compute M[32, 95]
71    // tmp2 = tmp2 + U32(tmp1)
72    //      = (U32(val) * N) + U32(L32(val) * N)
73    //      = M[32, 95]
74    tmp2 += tmp1 >> 32;
75
76    // if M[64, 95] >= D, then M/D has bits > 63 set and we have
77    // an overflow.
78    if ((tmp2 >> 32) >= D) {
79        *res = UINT64_MAX;
80        return false;
81    }
82
83    // Divide.  Going in we know
84    // tmp2 = M[32, 95]
85    // U32(tmp2) < D
86    r = tmp2 % D;
87    tmp2 /= D;
88
89    // At this point
90    // tmp1      = L32(val) * N
91    // tmp2      = M[32, 95] / D
92    //           = (M / D)[32, 95]
93    // r         = M[32, 95] % D
94    // U32(tmp2) = 0
95    //
96    // compute tmp1 = (r | M[0, 31])
97    tmp1 = (tmp1 & UINT32_MAX) | ((uint64_t)r << 32);
98
99    // Divide again.  Keep the remainder around in order to round properly.
100    r = tmp1 % D;
101    tmp1 /= D;
102
103    // At this point
104    // tmp2      = (M / D)[32, 95]
105    // tmp1      = (M / D)[ 0, 31]
106    // r         =  M % D
107    // U32(tmp1) = 0
108    // U32(tmp2) = 0
109
110    // Pack the result and deal with the round-up case (As well as the
111    // remote possiblility over overflow in such a case).
112    *res = (tmp2 << 32) | tmp1;
113    if (r && round_up_not_down) {
114        ++(*res);
115        if (!(*res)) {
116            *res = UINT64_MAX;
117            return false;
118        }
119    }
120
121    return true;
122}
123
124// at least one known sanitize failure (see comment below)
125ATTRIBUTE_NO_SANITIZE_INTEGER
126static bool linear_transform_s64_to_s64(
127        int64_t  val,
128        int64_t  basis1,
129        int32_t  N,
130        uint32_t D,
131        bool     invert_frac,
132        int64_t  basis2,
133        int64_t* out) {
134    uint64_t scaled, res;
135    uint64_t abs_val;
136    bool is_neg;
137
138    if (!out)
139        return false;
140
141    // Compute abs(val - basis_64). Keep track of whether or not this delta
142    // will be negative after the scale opertaion.
143    if (val < basis1) {
144        is_neg = true;
145        abs_val = basis1 - val;
146    } else {
147        is_neg = false;
148        abs_val = val - basis1;
149    }
150
151    if (N < 0)
152        is_neg = !is_neg;
153
154    if (!scale_u64_to_u64(abs_val,
155                          invert_frac ? D : ABS(N),
156                          invert_frac ? ABS(N) : D,
157                          &scaled,
158                          is_neg))
159        return false; // overflow/undeflow
160
161    // if scaled is >= 0x8000<etc>, then we are going to overflow or
162    // underflow unless ABS(basis2) is large enough to pull us back into the
163    // non-overflow/underflow region.
164    if (scaled & INT64_MIN) {
165        if (is_neg && (basis2 < 0))
166            return false; // certain underflow
167
168        if (!is_neg && (basis2 >= 0))
169            return false; // certain overflow
170
171        if (ABS(basis2) <= static_cast<int64_t>(scaled & INT64_MAX))
172            return false; // not enough
173
174        // Looks like we are OK
175        *out = (is_neg ? (-scaled) : scaled) + basis2;
176    } else {
177        // Scaled fits within signed bounds, so we just need to check for
178        // over/underflow for two signed integers.  Basically, if both scaled
179        // and basis2 have the same sign bit, and the result has a different
180        // sign bit, then we have under/overflow.  An easy way to compute this
181        // is
182        // (scaled_signbit XNOR basis_signbit) &&
183        // (scaled_signbit XOR res_signbit)
184        // ==
185        // (scaled_signbit XOR basis_signbit XOR 1) &&
186        // (scaled_signbit XOR res_signbit)
187
188        if (is_neg)
189            scaled = -scaled; // known sanitize failure
190        res = scaled + basis2;
191
192        if ((scaled ^ basis2 ^ INT64_MIN) & (scaled ^ res) & INT64_MIN)
193            return false;
194
195        *out = res;
196    }
197
198    return true;
199}
200
201bool LinearTransform::doForwardTransform(int64_t a_in, int64_t* b_out) const {
202    if (0 == a_to_b_denom)
203        return false;
204
205    return linear_transform_s64_to_s64(a_in,
206                                       a_zero,
207                                       a_to_b_numer,
208                                       a_to_b_denom,
209                                       false,
210                                       b_zero,
211                                       b_out);
212}
213
214bool LinearTransform::doReverseTransform(int64_t b_in, int64_t* a_out) const {
215    if (0 == a_to_b_numer)
216        return false;
217
218    return linear_transform_s64_to_s64(b_in,
219                                       b_zero,
220                                       a_to_b_numer,
221                                       a_to_b_denom,
222                                       true,
223                                       a_zero,
224                                       a_out);
225}
226
227template <class T> void LinearTransform::reduce(T* N, T* D) {
228    T a, b;
229    if (!N || !D || !(*D)) {
230        assert(false);
231        return;
232    }
233
234    a = *N;
235    b = *D;
236
237    if (a == 0) {
238        *D = 1;
239        return;
240    }
241
242    // This implements Euclid's method to find GCD.
243    if (a < b) {
244        T tmp = a;
245        a = b;
246        b = tmp;
247    }
248
249    while (1) {
250        // a is now the greater of the two.
251        const T remainder = a % b;
252        if (remainder == 0) {
253            *N /= b;
254            *D /= b;
255            return;
256        }
257        // by swapping remainder and b, we are guaranteeing that a is
258        // still the greater of the two upon entrance to the loop.
259        a = b;
260        b = remainder;
261    }
262};
263
264template void LinearTransform::reduce<uint64_t>(uint64_t* N, uint64_t* D);
265template void LinearTransform::reduce<uint32_t>(uint32_t* N, uint32_t* D);
266
267// sanitize failure if *N = 0x80000000
268ATTRIBUTE_NO_SANITIZE_INTEGER
269void LinearTransform::reduce(int32_t* N, uint32_t* D) {
270    if (N && D && *D) {
271        if (*N < 0) {
272            *N = -(*N);
273            reduce(reinterpret_cast<uint32_t*>(N), D);
274            *N = -(*N);
275        } else {
276            reduce(reinterpret_cast<uint32_t*>(N), D);
277        }
278    }
279}
280
281}  // namespace android
282