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 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 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 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 201 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 214 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 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 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
