bits_util.h 2.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
  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. #ifndef RLWE_BITS_UTIL_H_
  17. #define RLWE_BITS_UTIL_H_
  18. #include <stdint.h>
  19. #include "absl/numeric/int128.h"
  20. #include "integral_types.h"
  21. namespace rlwe {
  22. namespace internal {
  23. inline unsigned int CountOnesInByte(Uint8 x) {
  24. Uint8 x0 = x & 0x55;
  25. Uint8 x1 = (x >> 1) & 0x55;
  26. x = x0 + x1;
  27. x0 = x & 0x33;
  28. x1 = (x >> 2) & 0x33;
  29. x = x0 + x1;
  30. x0 = x & 0x0F;
  31. x1 = (x >> 4) & 0x0F;
  32. return x0 + x1;
  33. }
  34. inline unsigned int CountOnes64(Uint64 x) {
  35. Uint64 x0 = x & 0x5555555555555555;
  36. Uint64 x1 = (x >> 1) & 0x5555555555555555;
  37. x = x0 + x1;
  38. x0 = x & 0x3333333333333333;
  39. x1 = (x >> 2) & 0x3333333333333333;
  40. x = x0 + x1;
  41. x0 = x & 0x0F0F0F0F0F0F0F0F;
  42. x1 = (x >> 4) & 0x0F0F0F0F0F0F0F0F;
  43. x = x0 + x1;
  44. x0 = x & 0x00FF00FF00FF00FF;
  45. x1 = (x >> 8) & 0x00FF00FF00FF00FF;
  46. x = x0 + x1;
  47. x0 = x & 0x0000FFFF0000FFFF;
  48. x1 = (x >> 16) & 0x0000FFFF0000FFFF;
  49. x = x0 + x1;
  50. x0 = x & 0x00000000FFFFFFFF;
  51. x1 = (x >> 32) & 0x00000000FFFFFFFF;
  52. return x0 + x1;
  53. }
  54. inline unsigned int CountLeadingZeros64(Uint64 x) {
  55. unsigned int zeros = 64;
  56. if (x >> 32) {
  57. zeros -= 32;
  58. x >>= 32;
  59. }
  60. if (x >> 16) {
  61. zeros -= 16;
  62. x >>= 16;
  63. }
  64. if (x >> 8) {
  65. zeros -= 8;
  66. x >>= 8;
  67. }
  68. if (x >> 4) {
  69. zeros -= 4;
  70. x >>= 4;
  71. }
  72. if (x >> 2) {
  73. zeros -= 2;
  74. x >>= 2;
  75. }
  76. if (x >> 1) {
  77. zeros -= 1;
  78. x >>= 1;
  79. }
  80. return zeros - x;
  81. }
  82. inline unsigned int CountLeadingZeros128(absl::uint128 x) {
  83. if (Uint64 hi = absl::Uint128High64(x)) return CountLeadingZeros64(hi);
  84. return CountLeadingZeros64(absl::Uint128Low64(x)) + 64;
  85. }
  86. inline unsigned int BitLength(absl::uint128 x) {
  87. return 128 - CountLeadingZeros128(x);
  88. }
  89. } // namespace internal
  90. } // namespace rlwe
  91. #endif // RLWE_BITS_UTIL_H_