1 /* 2 * Copyright 2020 Google LLC 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef RLWE_BITS_UTIL_H_ 18 #define RLWE_BITS_UTIL_H_ 19 20 #include <stdint.h> 21 22 #include "absl/numeric/int128.h" 23 #include "integral_types.h" 24 25 namespace rlwe { 26 namespace internal { 27 CountOnesInByte(Uint8 x)28inline unsigned int CountOnesInByte(Uint8 x) { 29 Uint8 x0 = x & 0x55; 30 Uint8 x1 = (x >> 1) & 0x55; 31 x = x0 + x1; 32 33 x0 = x & 0x33; 34 x1 = (x >> 2) & 0x33; 35 x = x0 + x1; 36 37 x0 = x & 0x0F; 38 x1 = (x >> 4) & 0x0F; 39 return x0 + x1; 40 } 41 CountOnes64(Uint64 x)42inline unsigned int CountOnes64(Uint64 x) { 43 Uint64 x0 = x & 0x5555555555555555; 44 Uint64 x1 = (x >> 1) & 0x5555555555555555; 45 x = x0 + x1; 46 47 x0 = x & 0x3333333333333333; 48 x1 = (x >> 2) & 0x3333333333333333; 49 x = x0 + x1; 50 51 x0 = x & 0x0F0F0F0F0F0F0F0F; 52 x1 = (x >> 4) & 0x0F0F0F0F0F0F0F0F; 53 x = x0 + x1; 54 55 x0 = x & 0x00FF00FF00FF00FF; 56 x1 = (x >> 8) & 0x00FF00FF00FF00FF; 57 x = x0 + x1; 58 59 x0 = x & 0x0000FFFF0000FFFF; 60 x1 = (x >> 16) & 0x0000FFFF0000FFFF; 61 x = x0 + x1; 62 63 x0 = x & 0x00000000FFFFFFFF; 64 x1 = (x >> 32) & 0x00000000FFFFFFFF; 65 return x0 + x1; 66 } 67 CountLeadingZeros64(Uint64 x)68inline unsigned int CountLeadingZeros64(Uint64 x) { 69 unsigned int zeros = 64; 70 if (x >> 32) { 71 zeros -= 32; 72 x >>= 32; 73 } 74 if (x >> 16) { 75 zeros -= 16; 76 x >>= 16; 77 } 78 if (x >> 8) { 79 zeros -= 8; 80 x >>= 8; 81 } 82 if (x >> 4) { 83 zeros -= 4; 84 x >>= 4; 85 } 86 if (x >> 2) { 87 zeros -= 2; 88 x >>= 2; 89 } 90 if (x >> 1) { 91 zeros -= 1; 92 x >>= 1; 93 } 94 return zeros - x; 95 } 96 CountLeadingZeros128(absl::uint128 x)97inline unsigned int CountLeadingZeros128(absl::uint128 x) { 98 if (Uint64 hi = absl::Uint128High64(x)) return CountLeadingZeros64(hi); 99 return CountLeadingZeros64(absl::Uint128Low64(x)) + 64; 100 } 101 BitLength(absl::uint128 x)102inline unsigned int BitLength(absl::uint128 x) { 103 return 128 - CountLeadingZeros128(x); 104 } 105 106 } // namespace internal 107 } // namespace rlwe 108 109 #endif // RLWE_BITS_UTIL_H_ 110