123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479 |
- // Copyright 2020 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
- //
- // http://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.
- #include "transcription.h"
- #include <cstdint>
- #include <random>
- #include <vector>
- #include <gmock/gmock.h>
- #include <gtest/gtest.h>
- #include "absl/numeric/int128.h"
- #include "integral_types.h"
- #include "status_macros.h"
- #include "testing/status_matchers.h"
- #include "testing/status_testing.h"
- namespace rlwe {
- namespace {
- using ::rlwe::testing::StatusIs;
- using ::testing::HasSubstr;
- template <typename Int>
- class TranscribeTest : public ::testing::Test {};
- const int kLength = 10;
- using MyTypes = ::testing::Types<Uint8, Uint16, Uint32, absl::uint128>;
- TYPED_TEST_SUITE(TranscribeTest, MyTypes);
- // Generate a random integer of a specified number of bits.
- template <class TypeParam>
- TypeParam generate_random(int number_bits, unsigned int* seed) {
- if (number_bits == 0) return 0;
- TypeParam random_value = static_cast<TypeParam>(rand_r(seed));
- if (number_bits >= 8 * sizeof(TypeParam)) {
- return random_value;
- } else {
- TypeParam mask = (static_cast<TypeParam>(1) << number_bits) - 1;
- return random_value & mask;
- }
- }
- // Specialization for uint128.
- template <>
- absl::uint128 generate_random(int number_bits, unsigned int* seed) {
- int number_bits_hi = number_bits - std::min(64, number_bits);
- int number_bits_lo = number_bits % 64;
- uint64_t hi = generate_random<uint64_t>(number_bits_hi, seed);
- uint64_t lo = generate_random<uint64_t>(number_bits_lo, seed);
- return absl::MakeUint128(hi, lo);
- }
- // Verifies that the input_vector is long enough.
- TYPED_TEST(TranscribeTest, InputLongEnough) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- for (auto input_bit_length : {1, 100, 1000, 10000}) {
- for (int i = 1; i < input_number_of_bits; i++) {
- int necessary_number_of_chunks = (input_bit_length + i - 1) / i;
- std::vector<InputInt> input(necessary_number_of_chunks - 1, 0);
- for (int j = 1; j < output_number_of_bits; j++) {
- EXPECT_THAT(
- (TranscribeBits<InputInt, OutputInt>(input, input_bit_length, i,
- j)),
- StatusIs(::absl::StatusCode::kInvalidArgument,
- HasSubstr(absl::StrCat("The input vector of size ",
- (necessary_number_of_chunks - 1),
- " is too small to contain ",
- input_bit_length, " bits."))));
- }
- }
- }
- }
- // Verifies that the input and output types are consistent.
- TYPED_TEST(TranscribeTest, InconsistentInputType) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- // Try to extract too many bits.
- const int input_bits_per_int = input_number_of_bits + 1;
- for (int len = 1; len <= kLength; len++) {
- int input_bit_length = input_bits_per_int * len;
- int necessary_number_of_chunks =
- (input_bit_length + input_number_of_bits - 1) / input_number_of_bits;
- std::vector<InputInt> input(necessary_number_of_chunks, 0);
- for (int j = 1; j <= output_number_of_bits; j++) {
- EXPECT_THAT(
- (TranscribeBits<InputInt, OutputInt>(input, input_bit_length,
- input_bits_per_int, j)),
- StatusIs(::absl::StatusCode::kInvalidArgument,
- HasSubstr(absl::StrCat(
- "The input type only contains ", input_number_of_bits,
- " bits, hence we cannot extract ", input_bits_per_int,
- " bits out of each integer."))));
- }
- }
- }
- TYPED_TEST(TranscribeTest, InconsistentOutputType) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- // Try to store too many bits.
- const int output_bits_per_int = output_number_of_bits + 1;
- for (int len = 1; len <= kLength; len++) {
- std::vector<InputInt> input(len, 0);
- for (int i = 1; i <= input_number_of_bits; i++) {
- EXPECT_THAT(
- (TranscribeBits<InputInt, OutputInt>(input, i * len, i,
- output_bits_per_int)),
- StatusIs(::absl::StatusCode::kInvalidArgument,
- HasSubstr(absl::StrCat(
- "The output type only contains ", output_number_of_bits,
- " bits, hence we cannot save ", output_bits_per_int,
- " bits in each integer."))));
- }
- }
- }
- TYPED_TEST(TranscribeTest, NegativeInputLength) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_bit_length = -1;
- // create a zero string
- std::vector<InputInt> bits_i(kLength, 0);
- EXPECT_THAT(
- (TranscribeBits<InputInt, OutputInt>(bits_i, input_bit_length, 0, 0)),
- StatusIs(
- ::absl::StatusCode::kInvalidArgument,
- HasSubstr(absl::StrCat("The input bit length, ", input_bit_length,
- ", cannot be negative."))));
- }
- TYPED_TEST(TranscribeTest, NonEmptyInputToEmptyOutput) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_bit_length = 0;
- // Create a zero string
- std::vector<InputInt> bits_i(kLength, 0);
- EXPECT_THAT(
- (TranscribeBits<InputInt, OutputInt>(bits_i, input_bit_length, 1, 1)),
- StatusIs(::absl::StatusCode::kInvalidArgument,
- HasSubstr("Cannot transcribe an empty output "
- "vector with a non-empty input "
- "vector.")));
- }
- // Convert a sequence in chunks of i bits into a sequence in chunks of j
- // bits.
- TYPED_TEST(TranscribeTest, TranscribeTypeToType) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- unsigned int seed = 0;
- for (int i = 1; i <= input_number_of_bits; i++) {
- for (int j = 1; j <= output_number_of_bits; j++) {
- for (int len = 1; len <= kLength; len++) {
- // Create a random string of len bytes.
- std::vector<InputInt> bits_i(len, 0);
- for (InputInt& byte : bits_i) {
- byte = generate_random<InputInt>(i, &seed);
- }
- // Convert to j bits.
- ASSERT_OK_AND_ASSIGN(
- std::vector<OutputInt> bits_j,
- (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
- // Ensure that bits_j has the right length.
- EXPECT_EQ(bits_j.size(), (len * i + (j - 1)) / j);
- // Ensure that the bits came out the same.
- for (int bit = 0; bit < i * len; bit++) {
- InputInt bit_i = bits_i[bit / i] >> (bit % i);
- OutputInt bit_j = bits_j[bit / j] >> (bit % j);
- EXPECT_EQ(bit_i & 1, bit_j & 1);
- }
- // Ensure that all other bits in bits_j are zeros.
- for (int byte = 0; byte < bits_j.size(); byte++) {
- if (j == output_number_of_bits) continue; // no remaining bits
- EXPECT_EQ(bits_j[byte] >> j, 0);
- }
- }
- }
- }
- }
- TYPED_TEST(TranscribeTest, TranscribeTypeToTypeAndBack) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- unsigned int seed = 0;
- for (int i = 1; i <= input_number_of_bits; i++) {
- for (int j = 1; j <= output_number_of_bits; j++) {
- for (int len = 1; len <= kLength; len++) {
- // Create a random string of len bytes.
- std::vector<InputInt> bits_i(len, 0);
- for (InputInt& byte : bits_i) {
- byte = generate_random<InputInt>(i, &seed);
- }
- // Convert to j bits.
- ASSERT_OK_AND_ASSIGN(
- std::vector<OutputInt> bits_j,
- (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
- // Convert back.
- ASSERT_OK_AND_ASSIGN(
- std::vector<InputInt> bits_i2,
- (TranscribeBits<InputInt, OutputInt>(bits_j, len * i, j, i)));
- EXPECT_EQ(bits_i, bits_i2);
- }
- }
- }
- }
- // Test when the input bit length is not a multiple of the number of bits per
- // int.
- TYPED_TEST(TranscribeTest, InputBitLengthNotMultipleBitsPerInt) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- unsigned int seed = 0;
- // Reduce the number of elements to speed up the test.
- for (auto i : {2, 7, input_number_of_bits / 2, input_number_of_bits / 2 + 1,
- input_number_of_bits}) {
- for (int j = 1; j <= output_number_of_bits; j++) {
- // Reduce the number of elements to speed up the test.
- for (int len = 1; len <= kLength / 4 + 1; len++) {
- for (int input_bit_length = len * i + 1;
- input_bit_length < (len + 1) * i; input_bit_length++) {
- int necessary_number_of_chunks = (input_bit_length + i - 1) / i;
- // Create a random string of necessary_number_of_chunks bytes.
- std::vector<InputInt> bits_i(necessary_number_of_chunks, 0);
- for (InputInt& byte : bits_i) {
- byte = generate_random<InputInt>(i, &seed);
- }
- // Convert to j bits.
- ASSERT_OK_AND_ASSIGN(std::vector<OutputInt> bits_j,
- (TranscribeBits<InputInt, OutputInt>(
- bits_i, input_bit_length, i, j)));
- // Ensure that the bits came out the same.
- for (int bit = 0; bit < input_bit_length; bit++) {
- InputInt bit_i = bits_i[bit / i] >> (bit % i);
- OutputInt bit_j = bits_j[bit / j] >> (bit % j);
- EXPECT_EQ(bit_i & 1, bit_j & 1);
- }
- // Ensure that all other bits in bits_j are zeros.
- for (int byte = 0; byte < bits_j.size(); byte++) {
- if (j == output_number_of_bits) continue; // no remaining bits
- EXPECT_EQ(bits_j[byte] >> j, 0);
- }
- // The last element will only have input_bit_length % j bits sets.
- // Check that all the other bits are 0. The test is only meaningful
- // when input_bit_length % j != 0.
- if (input_bit_length % j != 0) {
- EXPECT_EQ(bits_j[bits_j.size() - 1] >> (input_bit_length % j), 0);
- }
- }
- }
- }
- }
- }
- TYPED_TEST(TranscribeTest, TranscribeTypeToUint64) {
- using InputInt = TypeParam;
- using OutputInt = uint64_t;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- unsigned int seed = 0;
- for (int i = 1; i <= input_number_of_bits; i++) {
- for (int j = 1; j <= output_number_of_bits; j++) {
- for (int len = 1; len <= kLength; len++) {
- // Create a random string of len bytes.
- std::vector<InputInt> bits_i(len, 0);
- for (InputInt& byte : bits_i) {
- byte = generate_random<InputInt>(i, &seed);
- }
- // Convert to j bits.
- ASSERT_OK_AND_ASSIGN(
- std::vector<OutputInt> bits_j,
- (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
- // Ensure that bits_j has the right length.
- EXPECT_EQ(bits_j.size(), (len * i + (j - 1)) / j);
- // Ensure that the bits came out the same.
- for (int bit = 0; bit < i * len; bit++) {
- Uint8 bit_i = static_cast<Uint8>(bits_i[bit / i] >> (bit % i));
- Uint8 bit_j = static_cast<Uint8>(bits_j[bit / j] >> (bit % j));
- EXPECT_EQ(bit_i & 0x01, bit_j & 0x01);
- }
- // Ensure that all other bits in bits_j are zeros.
- for (int byte = 0; byte < bits_j.size(); byte++) {
- if (j == output_number_of_bits) continue; // no remaining bits
- EXPECT_EQ(bits_j[byte] >> j, 0);
- }
- }
- }
- }
- }
- TYPED_TEST(TranscribeTest, TranscribeTypeToUint128) {
- using InputInt = TypeParam;
- using OutputInt = absl::uint128;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- unsigned int seed = 0;
- for (int i = 1; i <= input_number_of_bits; i++) {
- // Reduce the number of elements to speed up the test.
- for (auto j : {2, 7, output_number_of_bits / 2,
- output_number_of_bits / 2 + 1, output_number_of_bits}) {
- for (int len = 1; len <= kLength; len++) {
- // Create a random string of len bytes.
- std::vector<InputInt> bits_i(len, 0);
- for (InputInt& byte : bits_i) {
- byte = generate_random<InputInt>(i, &seed);
- }
- // Convert to j bits.
- ASSERT_OK_AND_ASSIGN(
- std::vector<OutputInt> bits_j,
- (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
- // Ensure that bits_j has the right length.
- EXPECT_EQ(bits_j.size(), (len * i + (j - 1)) / j);
- // Ensure that the bits came out the same.
- for (int bit = 0; bit < i * len; bit++) {
- Uint8 bit_i = static_cast<Uint8>(bits_i[bit / i] >> (bit % i));
- Uint8 bit_j = static_cast<Uint8>(bits_j[bit / j] >> (bit % j));
- EXPECT_EQ(bit_i & 0x01, bit_j & 0x01);
- }
- // Ensure that all other bits in bits_j are zeros.
- for (int byte = 0; byte < bits_j.size(); byte++) {
- if (j == output_number_of_bits) continue; // no remaining bits
- EXPECT_EQ(bits_j[byte] >> j, 0);
- }
- }
- }
- }
- }
- TYPED_TEST(TranscribeTest, TranscribeTypeToUint8) {
- using InputInt = TypeParam;
- using OutputInt = Uint8;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- unsigned int seed = 0;
- for (int i = 1; i <= input_number_of_bits; i++) {
- for (int j = 1; j <= output_number_of_bits; j++) {
- for (int len = 1; len <= kLength; len++) {
- // Create a random string of len bytes.
- std::vector<InputInt> bits_i(len, 0);
- for (InputInt& byte : bits_i) {
- byte = generate_random<InputInt>(i, &seed);
- }
- // Convert to j bits.
- ASSERT_OK_AND_ASSIGN(
- std::vector<OutputInt> bits_j,
- (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
- // Ensure that bits_j has the right length.
- EXPECT_EQ(bits_j.size(), (len * i + (j - 1)) / j);
- // Ensure that the bits came out the same.
- for (int bit = 0; bit < i * len; bit++) {
- Uint8 bit_i = static_cast<Uint8>(bits_i[bit / i] >> (bit % i));
- Uint8 bit_j = static_cast<Uint8>(bits_j[bit / j] >> (bit % j));
- EXPECT_EQ(bit_i & 0x01, bit_j & 0x01);
- }
- // Ensure that all other bits in bits_j are zeros.
- for (int byte = 0; byte < bits_j.size(); byte++) {
- if (j == output_number_of_bits) continue; // no remaining bits
- EXPECT_EQ(bits_j[byte] >> j, 0);
- }
- }
- }
- }
- }
- TYPED_TEST(TranscribeTest, InputLengthSmallerThanNumberOfBitsPerInput) {
- using InputInt = TypeParam;
- using OutputInt = TypeParam;
- const int input_number_of_bits = 8 * sizeof(InputInt);
- const int output_number_of_bits = 8 * sizeof(OutputInt);
- unsigned int seed = 0;
- for (int input_bit_length = 1; input_bit_length < input_number_of_bits;
- input_bit_length++) {
- // Create a random string of 1 byte.
- std::vector<InputInt> bits_i(
- {generate_random<InputInt>(input_bit_length, &seed)});
- for (int j = 1; j <= output_number_of_bits; j++) {
- // Convert to j bits.
- ASSERT_OK_AND_ASSIGN(
- std::vector<OutputInt> bits_j,
- (TranscribeBits<InputInt, OutputInt>(bits_i, input_bit_length,
- input_number_of_bits, j)));
- // Ensure that bits_j has the right length.
- EXPECT_EQ(bits_j.size(), (input_bit_length + (j - 1)) / j);
- // Ensure that the bits came out the same.
- for (int bit = 0; bit < input_bit_length; bit++) {
- Uint8 bit_i = static_cast<Uint8>(bits_i[0] >> bit);
- Uint8 bit_j = static_cast<Uint8>(bits_j[bit / j] >> (bit % j));
- EXPECT_EQ(bit_i & 0x01, bit_j & 0x01);
- }
- // Ensure that all other bits in bits_j are zeros.
- for (int byte = 0; byte < bits_j.size(); byte++) {
- if (j == output_number_of_bits) continue; // no remaining bits
- EXPECT_EQ(bits_j[byte] >> j, 0);
- }
- // The last element will only have input_bit_length % j bits sets.
- // Check that all the other bits are 0. The test is only meaningful
- // when input_bit_length % j != 0.
- if (input_bit_length % j != 0) {
- EXPECT_EQ(bits_j[bits_j.size() - 1] >> (input_bit_length % j), 0);
- }
- }
- }
- } // namespace
- } // namespace
- } // namespace rlwe
|