1 /* 2 * Copyright 2008 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "src/base/SkMathPriv.h" 9 10 #include "include/private/base/SkAssert.h" 11 12 #include <cstdint> 13 14 /////////////////////////////////////////////////////////////////////////////// 15 16 /* www.worldserver.com/turk/computergraphics/FixedSqrt.pdf 17 */ SkSqrtBits(int32_t x,int count)18int32_t SkSqrtBits(int32_t x, int count) { 19 SkASSERT(x >= 0 && count > 0 && (unsigned)count <= 30); 20 21 uint32_t root = 0; 22 uint32_t remHi = 0; 23 uint32_t remLo = x; 24 25 do { 26 root <<= 1; 27 28 remHi = (remHi<<2) | (remLo>>30); 29 remLo <<= 2; 30 31 uint32_t testDiv = (root << 1) + 1; 32 if (remHi >= testDiv) { 33 remHi -= testDiv; 34 root++; 35 } 36 } while (--count >= 0); 37 38 return root; 39 } 40 41 // Kernighan's method SkPopCount_portable(uint32_t n)42int SkPopCount_portable(uint32_t n) { 43 int count = 0; 44 45 while (n) { 46 n &= (n - 1); // Remove the lowest bit in the integer. 47 count++; 48 } 49 return count; 50 } 51 52 // Here we strip off the unwanted bits and then return the number of trailing zero bits SkNthSet(uint32_t target,int n)53int SkNthSet(uint32_t target, int n) { 54 SkASSERT(n < SkPopCount(target)); 55 56 for (int i = 0; i < n; ++i) { 57 target &= (target - 1); // Remove the lowest bit in the integer. 58 } 59 60 return SkCTZ(target); 61 } 62