180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "Sk64.h" 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkMathPriv.h" 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define shift_left(hi, lo) \ 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = (hi << 1) | (lo >> 31); \ 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lo <<= 1 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define shift_left_bits(hi, lo, bits) \ 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT((unsigned)(bits) < 31); \ 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = (hi << (bits)) | (lo >> (32 - (bits))); \ 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lo <<= (bits) 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru////////////////////////////////////////////////////////////////////// 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint Sk64::getClzAbs() const 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t hi = fHi; 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t lo = fLo; 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // get abs 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (hi < 0) 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = -hi - Sk32ToBool(lo); 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lo = 0 - lo; 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return hi ? SkCLZ(hi) : SkCLZ(lo) + 32; 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::shiftLeft(unsigned bits) 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(bits <= 63); 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (bits == 0) 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (bits >= 32) 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi = fLo << (bits - 32); 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = 0; 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi = (fHi << bits) | (fLo >> (32 - bits)); 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo <<= bits; 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint32_t Sk64::getShiftRight(unsigned bits) const 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(bits <= 63); 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (bits == 0) 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return fLo; 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (bits >= 32) 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return fHi >> (bits - 32); 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_DEBUG 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t tmp = fHi >> bits; 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(tmp == 0 || tmp == -1); 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (fHi << (32 - bits)) | (fLo >> bits); 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::shiftRight(unsigned bits) 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(bits <= 63); 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (bits == 0) 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (bits >= 32) 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = fHi >> (bits - 32); 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi >>= 31; 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = (fHi << (32 - bits)) | (fLo >> bits); 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi >>= bits; 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::roundRight(unsigned bits) 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(bits <= 63); 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (bits) 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 one; 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru one.set(1); 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru one.shiftLeft(bits - 1); 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->add(one); 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->shiftRight(bits); 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint Sk64::shiftToMake32() const 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t hi = fHi; 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t lo = fLo; 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (hi < 0) // make it positive 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = -hi - Sk32ToBool(lo); 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lo = 0 - lo; 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (hi == 0) 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return lo >> 31; 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 33 - SkCLZ(hi); 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::negate() 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi = -fHi - Sk32ToBool(fLo); 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = 0 - fLo; 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::abs() 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fHi < 0) 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi = -fHi - Sk32ToBool(fLo); 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = 0 - fLo; 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//////////////////////////////////////////////////////////////// 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline int32_t round_right_16(int32_t hi, uint32_t lo) 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t sum = lo + (1 << 15); 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi += (sum < lo); 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (hi << 16) | (sum >> 16); 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkBool Sk64::isFixed() const 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 tmp = *this; 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.roundRight(16); 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return tmp.is32(); 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkFract Sk64::getFract() const 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 tmp = *this; 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.roundRight(30); 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return tmp.get32(); 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::sub(const Sk64& a) 16080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 16180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi = fHi - a.fHi - (fLo < a.fLo); 16280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = fLo - a.fLo; 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 16480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::rsub(const Sk64& a) 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi = a.fHi - fHi - (a.fLo < fLo); 16880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = a.fLo - fLo; 16980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 17080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::setMul(int32_t a, int32_t b) 17280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 17380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int sa = a >> 31; 17480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int sb = b >> 31; 17580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // now make them positive 17680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru a = (a ^ sa) - sa; 17780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru b = (b ^ sb) - sb; 17880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t ah = a >> 16; 18080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t al = a & 0xFFFF; 18180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t bh = b >> 16; 18280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t bl = b & 0xFFFF; 18380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t A = ah * bh; 18580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t B = ah * bl + al * bh; 18680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t C = al * bl; 18780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* [ A ] 18980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru [ B ] 19080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru [ C ] 19180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 19280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = C + (B << 16); 19380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi = A + (B >>16) + (fLo < C); 19480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (sa != sb) 19680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->negate(); 19780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 19880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid Sk64::div(int32_t denom, DivOptions option) 20080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 20180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(denom); 20280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t hi = fHi; 20480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t lo = fLo; 20580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int sign = denom ^ hi; 20680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru denom = SkAbs32(denom); 20880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (hi < 0) 20980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 21080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = -hi - Sk32ToBool(lo); 21180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lo = 0 - lo; 21280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 21380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 21480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (option == kRound_DivOption) // add denom/2 21580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 21680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t newLo = lo + (denom >> 1); 21780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi += (newLo < lo); 21880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lo = newLo; 21980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 22080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (hi == 0) // fast-case 22280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 22380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (lo < (uint32_t)denom) 22480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->set(0, 0); 22580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 22680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 22780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->set(0, lo / denom); 22880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (sign < 0) 22980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->negate(); 23080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 23180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 23280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 23380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int bits; 23580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 23780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int dbits = SkCLZ(denom); 23880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int nbits = SkCLZ(hi); 23980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bits = 32 + dbits - nbits; 24180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(bits <= 63); 24280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (bits <= 0) 24380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 24480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->set(0, 0); 24580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 24680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 24780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru denom <<= (dbits - 1); 24880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru shift_left_bits(hi, lo, nbits - 1); 24980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 25080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 25180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t rhi = 0; 25280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t rlo = 0; 25380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 25480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 25580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru shift_left(rhi, rlo); 25680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_CPU_HAS_CONDITIONAL_INSTR 25780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((uint32_t)denom <= (uint32_t)hi) 25880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 25980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi -= denom; 26080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru rlo |= 1; 26180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 26280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#else 26380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t diff = (denom - hi - 1) >> 31; 26480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi -= denom & diff; 26580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru rlo -= diff; 26680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 26780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru shift_left(hi, lo); 26880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while (--bits >= 0); 26980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(rhi >= 0); 27080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fHi = rhi; 27280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLo = rlo; 27380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (sign < 0) 27480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->negate(); 27580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 27680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define shift_left_2(a, b, c) \ 27880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru a = (a << 2) | (b >> 30); \ 27980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru b = (b << 2) | (c >> 30); \ 28080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru c <<= 2 28180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 28280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint32_t Sk64::getSqrt() const 28380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 28480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(!this->isNeg()); 28580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 28680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t hi = fHi; 28780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t lo = fLo; 28880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t sqr = 0; 28980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t root = 0; 29080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = 31; 29180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 29280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 29380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru root <<= 1; 29480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru shift_left_2(sqr, hi, lo); 29580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 29680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t testDiv = (root << 1) + 1; 29780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (sqr >= testDiv) 29880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 29980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru sqr -= testDiv; 30080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru root++; 30180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 30280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while (--count >= 0); 30380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT((int32_t)root >= 0); 30480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 30580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return root; 30680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 30780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 30880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SkLONGLONG 30980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkLONGLONG Sk64::getLongLong() const 31080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 31180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkLONGLONG value = fHi; 31280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru value <<= 32; 31380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return value | fLo; 31480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 31580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 31680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 31780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkFixed Sk64::getFixedDiv(const Sk64& denom) const 31880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 31980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 N = *this; 32080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 D = denom; 32180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int32_t sign = SkExtractSign(N.fHi ^ D.fHi); 32280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkFixed result; 32380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 32480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru N.abs(); 32580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru D.abs(); 32680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 32780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // need to knock D down to just 31 bits 32880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // either by rounding it to the right, or shifting N to the left 32980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // then we can just call 64/32 div 33080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int nclz = N.fHi ? SkCLZ(N.fHi) : 32; 33280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int dclz = D.fHi ? SkCLZ(D.fHi) : (33 - (D.fLo >> 31)); 33380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int shiftN = nclz - 1; 33580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(shiftN >= 0); 33680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int shiftD = 33 - dclz; 33780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(shiftD >= 0); 33880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (shiftD + shiftN < 16) 34080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru shiftD = 16 - shiftN; 34180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 34280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru shiftN = 16 - shiftD; 34380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 34480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru D.roundRight(shiftD); 34580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (D.isZero()) 34680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result = SK_MaxS32; 34780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 34880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 34980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (shiftN >= 0) 35080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru N.shiftLeft(shiftN); 35180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 35280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru N.roundRight(-shiftN); 35380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru N.div(D.get32(), Sk64::kTrunc_DivOption); 35480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (N.is32()) 35580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result = N.get32(); 35680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 35780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru result = SK_MaxS32; 35880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 35980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkApplySign(result, sign); 36080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 361