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 
31 namespace android {
32 
33 // sanitize failure with T = int32_t and x = 0x80000000
34 template<class T>
35 ATTRIBUTE_NO_SANITIZE_INTEGER
ABS(T x)36 static 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.
40 ATTRIBUTE_NO_SANITIZE_INTEGER
scale_u64_to_u64(uint64_t val,uint32_t N,uint32_t D,uint64_t * res,bool round_up_not_down)41 static 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)
125 ATTRIBUTE_NO_SANITIZE_INTEGER
linear_transform_s64_to_s64(int64_t val,int64_t basis1,int32_t N,uint32_t D,bool invert_frac,int64_t basis2,int64_t * out)126 static 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 
doForwardTransform(int64_t a_in,int64_t * b_out) const201 bool 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 
doReverseTransform(int64_t b_in,int64_t * a_out) const214 bool 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 
reduce(T * N,T * D)227 template <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 
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);
266 
267 // sanitize failure if *N = 0x80000000
268 ATTRIBUTE_NO_SANITIZE_INTEGER
reduce(int32_t * N,uint32_t * D)269 void 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