1 // Copyright 2022 Google LLC 2 // 3 // This source code is licensed under the BSD-style license found in the 4 // LICENSE file in the root directory of this source tree. 5 6 #include <assert.h> 7 #include <stddef.h> 8 9 #include <xnnpack/math.h> 10 #include <xnnpack/math-stubs.h> 11 12 xnn_math_u32_sqrt__scalar_bitmanip(size_t n,const uint32_t * input,uint32_t * output)13void xnn_math_u32_sqrt__scalar_bitmanip( 14 size_t n, 15 const uint32_t* input, 16 uint32_t* output) 17 { 18 assert(n % sizeof(uint32_t) == 0); 19 20 for (; n != 0; n -= sizeof(uint32_t)) { 21 uint32_t vx = *input++; 22 23 // Based on Hacker's Delight, Figure 11-4. 24 uint32_t vm = UINT32_C(0x40000000); 25 uint32_t vy = 0; 26 for (uint32_t i = 0; i < 16; i++) { 27 const uint32_t vb = vy | vm; 28 vy >>= 1; 29 if XNN_UNPREDICTABLE(vx >= vb) { 30 vx -= vb; 31 vy |= vm; 32 } 33 vm >>= 2; 34 } 35 36 // vy is sqrt(.) rounded down. Do the final rounding up if needed. 37 if XNN_UNPREDICTABLE(vx > vy) { 38 vy += 1; 39 } 40 41 *output++ = vy; 42 } 43 } 44