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