transcription.h 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
  1. /*
  2. * Copyright 2019 Google LLC.
  3. * Licensed under the Apache License, Version 2.0 (the "License");
  4. * you may not use this file except in compliance with the License.
  5. * You may obtain a copy of the License at
  6. *
  7. * https://www.apache.org/licenses/LICENSE-2.0
  8. *
  9. * Unless required by applicable law or agreed to in writing, software
  10. * distributed under the License is distributed on an "AS IS" BASIS,
  11. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. * See the License for the specific language governing permissions and
  13. * limitations under the License.
  14. */
  15. // Implementation of transcription for serialization.
  16. //
  17. // Input is a sequence of integers, each containing a j-bit chunk of
  18. // a message. Output encodes the same message in a vector of Ints storing
  19. // the message broken into k-bit chunks. Performs this transcription for the
  20. // first input_bit_length bits encoded in input.
  21. #ifndef RLWE_TRANSCRIPTION_H_
  22. #define RLWE_TRANSCRIPTION_H_
  23. #include <vector>
  24. #include "absl/strings/str_cat.h"
  25. #include "statusor.h"
  26. namespace rlwe {
  27. // Takes as template arguments the input and output integer types. It must hold
  28. // that the input_vector is large enough to contain the input_bit_length bits.
  29. template <typename InputInt, typename OutputInt>
  30. rlwe::StatusOr<std::vector<OutputInt>> TranscribeBits(
  31. const std::vector<InputInt>& input_vector, int input_bit_length,
  32. int input_bits_per_int, int output_bits_per_int) {
  33. // Check that the templating is consistent, i.e., that we do not try to
  34. // extract/save more bits than available in each type.
  35. const int bit_size_input_type = sizeof(InputInt) * 8;
  36. const int bit_size_output_type = sizeof(OutputInt) * 8;
  37. if (input_bits_per_int > bit_size_input_type) {
  38. return absl::InvalidArgumentError(
  39. absl::StrCat("The input type only contains ", bit_size_input_type,
  40. " bits, hence we cannot extract ", input_bits_per_int,
  41. " bits out of each integer."));
  42. }
  43. if (output_bits_per_int > bit_size_output_type) {
  44. return absl::InvalidArgumentError(
  45. absl::StrCat("The output type only contains ", bit_size_output_type,
  46. " bits, hence we cannot save ", output_bits_per_int,
  47. " bits in each integer."));
  48. }
  49. if (input_bit_length < 0) {
  50. return absl::InvalidArgumentError(absl::StrCat(
  51. "The input bit length, ", input_bit_length, ", cannot be negative."));
  52. }
  53. if (input_bit_length == 0) {
  54. if (input_vector.empty()) {
  55. return std::vector<OutputInt>();
  56. } else {
  57. return absl::InvalidArgumentError(
  58. "Cannot transcribe an empty output vector with a non-empty input "
  59. "vector.");
  60. }
  61. }
  62. // Compute the number of input chunks
  63. const int input_chunks =
  64. (input_bit_length + input_bits_per_int - 1) / input_bits_per_int;
  65. // Check that the input_vector is of size at least input_chunks.
  66. if (input_vector.size() < input_chunks) {
  67. return absl::InvalidArgumentError(
  68. absl::StrCat("The input vector of size ", input_vector.size(),
  69. " is too small to contain ", input_bit_length, " bits."));
  70. }
  71. // Initialize the output string.
  72. const int output_chunks =
  73. (input_bit_length + (output_bits_per_int - 1)) / output_bits_per_int;
  74. std::vector<OutputInt> output(output_chunks, 0);
  75. // Keep track of how many bits remain in input
  76. int remaining_bits_in_input = input_bit_length;
  77. // Iterate over the input elements and process each one completely before
  78. // moving to the next one. One or several output elements will be filled with
  79. // the entire input chunk considered.
  80. OutputInt* output_ptr = output.data();
  81. int size_output_chunk =
  82. std::min(remaining_bits_in_input, output_bits_per_int);
  83. int number_output_bits_needed = size_output_chunk;
  84. // Loop over all the input chunks.
  85. for (int i = 0; i < input_chunks; i++) {
  86. // Number of bits in "input"
  87. int number_bits_in_input =
  88. std::min(input_bits_per_int, remaining_bits_in_input);
  89. // Load input and put the bits in the most significant bits of in.
  90. InputInt input = input_vector[i]
  91. << (sizeof(InputInt) * 8 - number_bits_in_input);
  92. // Use all the bits in "in" before loading the next input
  93. while (number_bits_in_input > 0) {
  94. // If no bit is needed in output, go to the next element, and set the
  95. // number of bits needed to the minimum of output_bits_per_int and number
  96. // of remaining bits in case the last output cannot be filled completely.
  97. if (number_output_bits_needed == 0) {
  98. output_ptr++;
  99. size_output_chunk =
  100. std::min(remaining_bits_in_input, output_bits_per_int);
  101. number_output_bits_needed = size_output_chunk;
  102. }
  103. // Compute the number of bits we can process
  104. int number_bits_to_process =
  105. std::min(number_bits_in_input, number_output_bits_needed);
  106. // Keep only number_bits_to_process bits in the most significant bits of
  107. // "input" (so shift left by the difference).
  108. InputInt bits_left = input
  109. << (number_bits_in_input - number_bits_to_process);
  110. // Move these bits to the least significant bits of an OutputInt (hence,
  111. // shift right by the size of an InputInt minus the number of bits that
  112. // are being processed.
  113. OutputInt mask = static_cast<OutputInt>(
  114. bits_left >> (sizeof(InputInt) * 8 - number_bits_to_process));
  115. // Xor the mask at the right place (hence shift left by the number of
  116. // output bits already processed).
  117. *output_ptr |= (mask << (size_output_chunk - number_output_bits_needed));
  118. // Update the number of output bits needed and in "input".
  119. number_bits_in_input -= number_bits_to_process;
  120. number_output_bits_needed -= number_bits_to_process;
  121. }
  122. // At most input_bits_per_int bits just got read, so we update the number of
  123. // remaining bits in input. This may end up to be negative, but only when we
  124. // are exiting the loop.
  125. remaining_bits_in_input -= input_bits_per_int;
  126. }
  127. return output;
  128. }
  129. } // namespace rlwe
  130. #endif // RLWE_TRANSCRIPTION_H_