2 * Copyright (C) 2011 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #define __STDC_LIMIT_MACROS
19 #include "LinearTransform.h"
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")))
28 #define ATTRIBUTE_NO_SANITIZE_INTEGER
33 // sanitize failure with T = int32_t and x = 0x80000000
35 ATTRIBUTE_NO_SANITIZE_INTEGER
36 static inline T ABS(T x) { return (x < 0) ? -x : x; }
38 // Static math methods involving linear transformations
39 // remote sanitize failure on overflow case.
40 ATTRIBUTE_NO_SANITIZE_INTEGER
41 static bool scale_u64_to_u64(
46 bool round_up_not_down) {
53 // Let U32(X) denote a uint32_t containing the upper 32 bits of a 64 bit
55 // Let L32(X) denote a uint32_t containing the lower 32 bits of a 64 bit
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
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)
66 // M = val * N = (tmp2 << 32) + tmp1
67 tmp2 = (val >> 32) * N;
68 tmp1 = (val & UINT32_MAX) * N;
71 // tmp2 = tmp2 + U32(tmp1)
72 // = (U32(val) * N) + U32(L32(val) * N)
76 // if M[64, 95] >= D, then M/D has bits > 63 set and we have
78 if ((tmp2 >> 32) >= D) {
83 // Divide. Going in we know
90 // tmp1 = L32(val) * N
91 // tmp2 = M[32, 95] / D
96 // compute tmp1 = (r | M[0, 31])
97 tmp1 = (tmp1 & UINT32_MAX) | ((uint64_t)r << 32);
99 // Divide again. Keep the remainder around in order to round properly.
104 // tmp2 = (M / D)[32, 95]
105 // tmp1 = (M / D)[ 0, 31]
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) {
124 // at least one known sanitize failure (see comment below)
125 ATTRIBUTE_NO_SANITIZE_INTEGER
126 static bool linear_transform_s64_to_s64(
134 uint64_t scaled, res;
141 // Compute abs(val - basis_64). Keep track of whether or not this delta
142 // will be negative after the scale opertaion.
145 abs_val = basis1 - val;
148 abs_val = val - basis1;
154 if (!scale_u64_to_u64(abs_val,
155 invert_frac ? D : ABS(N),
156 invert_frac ? ABS(N) : D,
159 return false; // overflow/undeflow
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
168 if (!is_neg && (basis2 >= 0))
169 return false; // certain overflow
171 if (ABS(basis2) <= static_cast<int64_t>(scaled & INT64_MAX))
172 return false; // not enough
174 // Looks like we are OK
175 *out = (is_neg ? (-scaled) : scaled) + basis2;
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
182 // (scaled_signbit XNOR basis_signbit) &&
183 // (scaled_signbit XOR res_signbit)
185 // (scaled_signbit XOR basis_signbit XOR 1) &&
186 // (scaled_signbit XOR res_signbit)
189 scaled = -scaled; // known sanitize failure
190 res = scaled + basis2;
192 if ((scaled ^ basis2 ^ INT64_MIN) & (scaled ^ res) & INT64_MIN)
201 bool LinearTransform::doForwardTransform(int64_t a_in, int64_t* b_out) const {
202 if (0 == a_to_b_denom)
205 return linear_transform_s64_to_s64(a_in,
214 bool LinearTransform::doReverseTransform(int64_t b_in, int64_t* a_out) const {
215 if (0 == a_to_b_numer)
218 return linear_transform_s64_to_s64(b_in,
227 template <class T> void LinearTransform::reduce(T* N, T* D) {
229 if (!N || !D || !(*D)) {
242 // This implements Euclid's method to find GCD.
250 // a is now the greater of the two.
251 const T remainder = a % b;
252 if (remainder == 0) {
257 // by swapping remainder and b, we are guaranteeing that a is
258 // still the greater of the two upon entrance to the loop.
264 template void LinearTransform::reduce<uint64_t>(uint64_t* N, uint64_t* D);
265 template void LinearTransform::reduce<uint32_t>(uint32_t* N, uint32_t* D);
267 // sanitize failure if *N = 0x80000000
268 ATTRIBUTE_NO_SANITIZE_INTEGER
269 void LinearTransform::reduce(int32_t* N, uint32_t* D) {
273 reduce(reinterpret_cast<uint32_t*>(N), D);
276 reduce(reinterpret_cast<uint32_t*>(N), D);
281 } // namespace android