1 /* libs/corecg/Sk64.cpp 2 ** 3 ** Copyright 2006, The Android Open Source Project 4 ** 5 ** Licensed under the Apache License, Version 2.0 (the "License"); 6 ** you may not use this file except in compliance with the License. 7 ** 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 18 #include "Sk64.h" 19 20 #define shift_left(hi, lo) \ 21 hi = (hi << 1) | (lo >> 31); \ 22 lo <<= 1 23 24 #define shift_left_bits(hi, lo, bits) \ 25 SkASSERT((unsigned)(bits) < 31); \ 26 hi = (hi << (bits)) | (lo >> (32 - (bits))); \ 27 lo <<= (bits) 28 29 ////////////////////////////////////////////////////////////////////// 30 31 int Sk64::getClzAbs() const 32 { 33 int32_t hi = fHi; 34 uint32_t lo = fLo; 35 36 // get abs 37 if (hi < 0) 38 { 39 hi = -hi - Sk32ToBool(lo); 40 lo = 0 - lo; 41 } 42 return hi ? SkCLZ(hi) : SkCLZ(lo) + 32; 43 } 44 45 void Sk64::shiftLeft(unsigned bits) 46 { 47 SkASSERT(bits <= 63); 48 if (bits == 0) 49 return; 50 51 if (bits >= 32) 52 { 53 fHi = fLo << (bits - 32); 54 fLo = 0; 55 } 56 else 57 { 58 fHi = (fHi << bits) | (fLo >> (32 - bits)); 59 fLo <<= bits; 60 } 61 } 62 63 int32_t Sk64::getShiftRight(unsigned bits) const 64 { 65 SkASSERT(bits <= 63); 66 67 if (bits == 0) 68 return fLo; 69 70 if (bits >= 32) 71 return fHi >> (bits - 32); 72 else 73 { 74 #ifdef SK_DEBUG 75 int32_t tmp = fHi >> bits; 76 SkASSERT(tmp == 0 || tmp == -1); 77 #endif 78 return (fHi << (32 - bits)) | (fLo >> bits); 79 } 80 } 81 82 void Sk64::shiftRight(unsigned bits) 83 { 84 SkASSERT(bits <= 63); 85 if (bits == 0) 86 return; 87 88 if (bits >= 32) 89 { 90 fLo = fHi >> (bits - 32); 91 fHi >>= 31; 92 } 93 else 94 { 95 fLo = (fHi << (32 - bits)) | (fLo >> bits); 96 fHi >>= bits; 97 } 98 } 99 100 void Sk64::roundRight(unsigned bits) 101 { 102 SkASSERT(bits <= 63); 103 if (bits) 104 { 105 Sk64 one; 106 one.set(1); 107 one.shiftLeft(bits - 1); 108 this->add(one); 109 this->shiftRight(bits); 110 } 111 } 112 113 int Sk64::shiftToMake32() const 114 { 115 int32_t hi = fHi; 116 uint32_t lo = fLo; 117 118 if (hi < 0) // make it positive 119 { 120 hi = -hi - Sk32ToBool(lo); 121 lo = 0 - lo; 122 } 123 124 if (hi == 0) 125 return lo >> 31; 126 else 127 return 33 - SkCLZ(hi); 128 } 129 130 void Sk64::negate() 131 { 132 fHi = -fHi - Sk32ToBool(fLo); 133 fLo = 0 - fLo; 134 } 135 136 void Sk64::abs() 137 { 138 if (fHi < 0) 139 { 140 fHi = -fHi - Sk32ToBool(fLo); 141 fLo = 0 - fLo; 142 } 143 } 144 145 //////////////////////////////////////////////////////////////// 146 147 static inline int32_t round_right_16(int32_t hi, uint32_t lo) 148 { 149 uint32_t sum = lo + (1 << 15); 150 hi += (sum < lo); 151 return (hi << 16) | (sum >> 16); 152 } 153 154 SkBool Sk64::isFixed() const 155 { 156 Sk64 tmp = *this; 157 tmp.roundRight(16); 158 return tmp.is32(); 159 } 160 161 SkFract Sk64::getFract() const 162 { 163 Sk64 tmp = *this; 164 tmp.roundRight(30); 165 return tmp.get32(); 166 } 167 168 void Sk64::sub(const Sk64& a) 169 { 170 fHi = fHi - a.fHi - (fLo < a.fLo); 171 fLo = fLo - a.fLo; 172 } 173 174 void Sk64::rsub(const Sk64& a) 175 { 176 fHi = a.fHi - fHi - (a.fLo < fLo); 177 fLo = a.fLo - fLo; 178 } 179 180 void Sk64::setMul(int32_t a, int32_t b) 181 { 182 int sa = a >> 31; 183 int sb = b >> 31; 184 // now make them positive 185 a = (a ^ sa) - sa; 186 b = (b ^ sb) - sb; 187 188 uint32_t ah = a >> 16; 189 uint32_t al = a & 0xFFFF; 190 uint32_t bh = b >> 16; 191 uint32_t bl = b & 0xFFFF; 192 193 uint32_t A = ah * bh; 194 uint32_t B = ah * bl + al * bh; 195 uint32_t C = al * bl; 196 197 /* [ A ] 198 [ B ] 199 [ C ] 200 */ 201 fLo = C + (B << 16); 202 fHi = A + (B >>16) + (fLo < C); 203 204 if (sa != sb) 205 this->negate(); 206 } 207 208 void Sk64::div(int32_t denom, DivOptions option) 209 { 210 SkASSERT(denom); 211 212 int32_t hi = fHi; 213 uint32_t lo = fLo; 214 int sign = denom ^ hi; 215 216 denom = SkAbs32(denom); 217 if (hi < 0) 218 { 219 hi = -hi - Sk32ToBool(lo); 220 lo = 0 - lo; 221 } 222 223 if (option == kRound_DivOption) // add denom/2 224 { 225 uint32_t newLo = lo + (denom >> 1); 226 hi += (newLo < lo); 227 lo = newLo; 228 } 229 230 if (hi == 0) // fast-case 231 { 232 if (lo < (uint32_t)denom) 233 this->set(0, 0); 234 else 235 { 236 this->set(0, lo / denom); 237 if (sign < 0) 238 this->negate(); 239 } 240 return; 241 } 242 243 int bits; 244 245 { 246 int dbits = SkCLZ(denom); 247 int nbits = SkCLZ(hi); 248 249 bits = 32 + dbits - nbits; 250 SkASSERT(bits <= 63); 251 if (bits <= 0) 252 { 253 this->set(0, 0); 254 return; 255 } 256 denom <<= (dbits - 1); 257 shift_left_bits(hi, lo, nbits - 1); 258 } 259 260 int32_t rhi = 0; 261 uint32_t rlo = 0; 262 263 do { 264 shift_left(rhi, rlo); 265 #ifdef SK_CPU_HAS_CONDITIONAL_INSTR 266 if ((uint32_t)denom <= (uint32_t)hi) 267 { 268 hi -= denom; 269 rlo |= 1; 270 } 271 #else 272 int32_t diff = (denom - hi - 1) >> 31; 273 hi -= denom & diff; 274 rlo -= diff; 275 #endif 276 shift_left(hi, lo); 277 } while (--bits >= 0); 278 SkASSERT(rhi >= 0); 279 280 fHi = rhi; 281 fLo = rlo; 282 if (sign < 0) 283 this->negate(); 284 } 285 286 #define shift_left_2(a, b, c) \ 287 a = (a << 2) | (b >> 30); \ 288 b = (b << 2) | (c >> 30); \ 289 c <<= 2 290 291 int32_t Sk64::getSqrt() const 292 { 293 SkASSERT(!this->isNeg()); 294 295 uint32_t hi = fHi; 296 uint32_t lo = fLo; 297 uint32_t sqr = 0; 298 uint32_t root = 0; 299 int count = 31; 300 301 do { 302 root <<= 1; 303 shift_left_2(sqr, hi, lo); 304 305 uint32_t testDiv = (root << 1) + 1; 306 if (sqr >= testDiv) 307 { 308 sqr -= testDiv; 309 root++; 310 } 311 } while (--count >= 0); 312 SkASSERT((int32_t)root >= 0); 313 314 return root; 315 } 316 317 #ifdef SkLONGLONG 318 SkLONGLONG Sk64::getLongLong() const 319 { 320 SkLONGLONG value = fHi; 321 value <<= 32; 322 return value | fLo; 323 } 324 #endif 325 326 SkFixed Sk64::getFixedDiv(const Sk64& denom) const 327 { 328 Sk64 N = *this; 329 Sk64 D = denom; 330 int32_t sign = SkExtractSign(N.fHi ^ D.fHi); 331 SkFixed result; 332 333 N.abs(); 334 D.abs(); 335 336 // need to knock D down to just 31 bits 337 // either by rounding it to the right, or shifting N to the left 338 // then we can just call 64/32 div 339 340 int nclz = N.fHi ? SkCLZ(N.fHi) : 32; 341 int dclz = D.fHi ? SkCLZ(D.fHi) : (33 - (D.fLo >> 31)); 342 343 int shiftN = nclz - 1; 344 SkASSERT(shiftN >= 0); 345 int shiftD = 33 - dclz; 346 SkASSERT(shiftD >= 0); 347 348 if (shiftD + shiftN < 16) 349 shiftD = 16 - shiftN; 350 else 351 shiftN = 16 - shiftD; 352 353 D.roundRight(shiftD); 354 if (D.isZero()) 355 result = SK_MaxS32; 356 else 357 { 358 if (shiftN >= 0) 359 N.shiftLeft(shiftN); 360 else 361 N.roundRight(-shiftN); 362 N.div(D.get32(), Sk64::kTrunc_DivOption); 363 if (N.is32()) 364 result = N.get32(); 365 else 366 result = SK_MaxS32; 367 } 368 return SkApplySign(result, sign); 369 } 370 371
