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)28 inline 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)42 inline 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)68 inline 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)97 inline 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)102 inline 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