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