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