transcription_test.cc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479
  1. // Copyright 2020 Google LLC
  2. //
  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. // http://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. #include "transcription.h"
  15. #include <cstdint>
  16. #include <random>
  17. #include <vector>
  18. #include <gmock/gmock.h>
  19. #include <gtest/gtest.h>
  20. #include "absl/numeric/int128.h"
  21. #include "integral_types.h"
  22. #include "status_macros.h"
  23. #include "testing/status_matchers.h"
  24. #include "testing/status_testing.h"
  25. namespace rlwe {
  26. namespace {
  27. using ::rlwe::testing::StatusIs;
  28. using ::testing::HasSubstr;
  29. template <typename Int>
  30. class TranscribeTest : public ::testing::Test {};
  31. const int kLength = 10;
  32. using MyTypes = ::testing::Types<Uint8, Uint16, Uint32, absl::uint128>;
  33. TYPED_TEST_SUITE(TranscribeTest, MyTypes);
  34. // Generate a random integer of a specified number of bits.
  35. template <class TypeParam>
  36. TypeParam generate_random(int number_bits, unsigned int* seed) {
  37. if (number_bits == 0) return 0;
  38. TypeParam random_value = static_cast<TypeParam>(rand_r(seed));
  39. if (number_bits >= 8 * sizeof(TypeParam)) {
  40. return random_value;
  41. } else {
  42. TypeParam mask = (static_cast<TypeParam>(1) << number_bits) - 1;
  43. return random_value & mask;
  44. }
  45. }
  46. // Specialization for uint128.
  47. template <>
  48. absl::uint128 generate_random(int number_bits, unsigned int* seed) {
  49. int number_bits_hi = number_bits - std::min(64, number_bits);
  50. int number_bits_lo = number_bits % 64;
  51. uint64_t hi = generate_random<uint64_t>(number_bits_hi, seed);
  52. uint64_t lo = generate_random<uint64_t>(number_bits_lo, seed);
  53. return absl::MakeUint128(hi, lo);
  54. }
  55. // Verifies that the input_vector is long enough.
  56. TYPED_TEST(TranscribeTest, InputLongEnough) {
  57. using InputInt = TypeParam;
  58. using OutputInt = TypeParam;
  59. const int input_number_of_bits = 8 * sizeof(InputInt);
  60. const int output_number_of_bits = 8 * sizeof(OutputInt);
  61. for (auto input_bit_length : {1, 100, 1000, 10000}) {
  62. for (int i = 1; i < input_number_of_bits; i++) {
  63. int necessary_number_of_chunks = (input_bit_length + i - 1) / i;
  64. std::vector<InputInt> input(necessary_number_of_chunks - 1, 0);
  65. for (int j = 1; j < output_number_of_bits; j++) {
  66. EXPECT_THAT(
  67. (TranscribeBits<InputInt, OutputInt>(input, input_bit_length, i,
  68. j)),
  69. StatusIs(::absl::StatusCode::kInvalidArgument,
  70. HasSubstr(absl::StrCat("The input vector of size ",
  71. (necessary_number_of_chunks - 1),
  72. " is too small to contain ",
  73. input_bit_length, " bits."))));
  74. }
  75. }
  76. }
  77. }
  78. // Verifies that the input and output types are consistent.
  79. TYPED_TEST(TranscribeTest, InconsistentInputType) {
  80. using InputInt = TypeParam;
  81. using OutputInt = TypeParam;
  82. const int input_number_of_bits = 8 * sizeof(InputInt);
  83. const int output_number_of_bits = 8 * sizeof(OutputInt);
  84. // Try to extract too many bits.
  85. const int input_bits_per_int = input_number_of_bits + 1;
  86. for (int len = 1; len <= kLength; len++) {
  87. int input_bit_length = input_bits_per_int * len;
  88. int necessary_number_of_chunks =
  89. (input_bit_length + input_number_of_bits - 1) / input_number_of_bits;
  90. std::vector<InputInt> input(necessary_number_of_chunks, 0);
  91. for (int j = 1; j <= output_number_of_bits; j++) {
  92. EXPECT_THAT(
  93. (TranscribeBits<InputInt, OutputInt>(input, input_bit_length,
  94. input_bits_per_int, j)),
  95. StatusIs(::absl::StatusCode::kInvalidArgument,
  96. HasSubstr(absl::StrCat(
  97. "The input type only contains ", input_number_of_bits,
  98. " bits, hence we cannot extract ", input_bits_per_int,
  99. " bits out of each integer."))));
  100. }
  101. }
  102. }
  103. TYPED_TEST(TranscribeTest, InconsistentOutputType) {
  104. using InputInt = TypeParam;
  105. using OutputInt = TypeParam;
  106. const int input_number_of_bits = 8 * sizeof(InputInt);
  107. const int output_number_of_bits = 8 * sizeof(OutputInt);
  108. // Try to store too many bits.
  109. const int output_bits_per_int = output_number_of_bits + 1;
  110. for (int len = 1; len <= kLength; len++) {
  111. std::vector<InputInt> input(len, 0);
  112. for (int i = 1; i <= input_number_of_bits; i++) {
  113. EXPECT_THAT(
  114. (TranscribeBits<InputInt, OutputInt>(input, i * len, i,
  115. output_bits_per_int)),
  116. StatusIs(::absl::StatusCode::kInvalidArgument,
  117. HasSubstr(absl::StrCat(
  118. "The output type only contains ", output_number_of_bits,
  119. " bits, hence we cannot save ", output_bits_per_int,
  120. " bits in each integer."))));
  121. }
  122. }
  123. }
  124. TYPED_TEST(TranscribeTest, NegativeInputLength) {
  125. using InputInt = TypeParam;
  126. using OutputInt = TypeParam;
  127. const int input_bit_length = -1;
  128. // create a zero string
  129. std::vector<InputInt> bits_i(kLength, 0);
  130. EXPECT_THAT(
  131. (TranscribeBits<InputInt, OutputInt>(bits_i, input_bit_length, 0, 0)),
  132. StatusIs(
  133. ::absl::StatusCode::kInvalidArgument,
  134. HasSubstr(absl::StrCat("The input bit length, ", input_bit_length,
  135. ", cannot be negative."))));
  136. }
  137. TYPED_TEST(TranscribeTest, NonEmptyInputToEmptyOutput) {
  138. using InputInt = TypeParam;
  139. using OutputInt = TypeParam;
  140. const int input_bit_length = 0;
  141. // Create a zero string
  142. std::vector<InputInt> bits_i(kLength, 0);
  143. EXPECT_THAT(
  144. (TranscribeBits<InputInt, OutputInt>(bits_i, input_bit_length, 1, 1)),
  145. StatusIs(::absl::StatusCode::kInvalidArgument,
  146. HasSubstr("Cannot transcribe an empty output "
  147. "vector with a non-empty input "
  148. "vector.")));
  149. }
  150. // Convert a sequence in chunks of i bits into a sequence in chunks of j
  151. // bits.
  152. TYPED_TEST(TranscribeTest, TranscribeTypeToType) {
  153. using InputInt = TypeParam;
  154. using OutputInt = TypeParam;
  155. const int input_number_of_bits = 8 * sizeof(InputInt);
  156. const int output_number_of_bits = 8 * sizeof(OutputInt);
  157. unsigned int seed = 0;
  158. for (int i = 1; i <= input_number_of_bits; i++) {
  159. for (int j = 1; j <= output_number_of_bits; j++) {
  160. for (int len = 1; len <= kLength; len++) {
  161. // Create a random string of len bytes.
  162. std::vector<InputInt> bits_i(len, 0);
  163. for (InputInt& byte : bits_i) {
  164. byte = generate_random<InputInt>(i, &seed);
  165. }
  166. // Convert to j bits.
  167. ASSERT_OK_AND_ASSIGN(
  168. std::vector<OutputInt> bits_j,
  169. (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
  170. // Ensure that bits_j has the right length.
  171. EXPECT_EQ(bits_j.size(), (len * i + (j - 1)) / j);
  172. // Ensure that the bits came out the same.
  173. for (int bit = 0; bit < i * len; bit++) {
  174. InputInt bit_i = bits_i[bit / i] >> (bit % i);
  175. OutputInt bit_j = bits_j[bit / j] >> (bit % j);
  176. EXPECT_EQ(bit_i & 1, bit_j & 1);
  177. }
  178. // Ensure that all other bits in bits_j are zeros.
  179. for (int byte = 0; byte < bits_j.size(); byte++) {
  180. if (j == output_number_of_bits) continue; // no remaining bits
  181. EXPECT_EQ(bits_j[byte] >> j, 0);
  182. }
  183. }
  184. }
  185. }
  186. }
  187. TYPED_TEST(TranscribeTest, TranscribeTypeToTypeAndBack) {
  188. using InputInt = TypeParam;
  189. using OutputInt = TypeParam;
  190. const int input_number_of_bits = 8 * sizeof(InputInt);
  191. const int output_number_of_bits = 8 * sizeof(OutputInt);
  192. unsigned int seed = 0;
  193. for (int i = 1; i <= input_number_of_bits; i++) {
  194. for (int j = 1; j <= output_number_of_bits; j++) {
  195. for (int len = 1; len <= kLength; len++) {
  196. // Create a random string of len bytes.
  197. std::vector<InputInt> bits_i(len, 0);
  198. for (InputInt& byte : bits_i) {
  199. byte = generate_random<InputInt>(i, &seed);
  200. }
  201. // Convert to j bits.
  202. ASSERT_OK_AND_ASSIGN(
  203. std::vector<OutputInt> bits_j,
  204. (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
  205. // Convert back.
  206. ASSERT_OK_AND_ASSIGN(
  207. std::vector<InputInt> bits_i2,
  208. (TranscribeBits<InputInt, OutputInt>(bits_j, len * i, j, i)));
  209. EXPECT_EQ(bits_i, bits_i2);
  210. }
  211. }
  212. }
  213. }
  214. // Test when the input bit length is not a multiple of the number of bits per
  215. // int.
  216. TYPED_TEST(TranscribeTest, InputBitLengthNotMultipleBitsPerInt) {
  217. using InputInt = TypeParam;
  218. using OutputInt = TypeParam;
  219. const int input_number_of_bits = 8 * sizeof(InputInt);
  220. const int output_number_of_bits = 8 * sizeof(OutputInt);
  221. unsigned int seed = 0;
  222. // Reduce the number of elements to speed up the test.
  223. for (auto i : {2, 7, input_number_of_bits / 2, input_number_of_bits / 2 + 1,
  224. input_number_of_bits}) {
  225. for (int j = 1; j <= output_number_of_bits; j++) {
  226. // Reduce the number of elements to speed up the test.
  227. for (int len = 1; len <= kLength / 4 + 1; len++) {
  228. for (int input_bit_length = len * i + 1;
  229. input_bit_length < (len + 1) * i; input_bit_length++) {
  230. int necessary_number_of_chunks = (input_bit_length + i - 1) / i;
  231. // Create a random string of necessary_number_of_chunks bytes.
  232. std::vector<InputInt> bits_i(necessary_number_of_chunks, 0);
  233. for (InputInt& byte : bits_i) {
  234. byte = generate_random<InputInt>(i, &seed);
  235. }
  236. // Convert to j bits.
  237. ASSERT_OK_AND_ASSIGN(std::vector<OutputInt> bits_j,
  238. (TranscribeBits<InputInt, OutputInt>(
  239. bits_i, input_bit_length, i, j)));
  240. // Ensure that the bits came out the same.
  241. for (int bit = 0; bit < input_bit_length; bit++) {
  242. InputInt bit_i = bits_i[bit / i] >> (bit % i);
  243. OutputInt bit_j = bits_j[bit / j] >> (bit % j);
  244. EXPECT_EQ(bit_i & 1, bit_j & 1);
  245. }
  246. // Ensure that all other bits in bits_j are zeros.
  247. for (int byte = 0; byte < bits_j.size(); byte++) {
  248. if (j == output_number_of_bits) continue; // no remaining bits
  249. EXPECT_EQ(bits_j[byte] >> j, 0);
  250. }
  251. // The last element will only have input_bit_length % j bits sets.
  252. // Check that all the other bits are 0. The test is only meaningful
  253. // when input_bit_length % j != 0.
  254. if (input_bit_length % j != 0) {
  255. EXPECT_EQ(bits_j[bits_j.size() - 1] >> (input_bit_length % j), 0);
  256. }
  257. }
  258. }
  259. }
  260. }
  261. }
  262. TYPED_TEST(TranscribeTest, TranscribeTypeToUint64) {
  263. using InputInt = TypeParam;
  264. using OutputInt = uint64_t;
  265. const int input_number_of_bits = 8 * sizeof(InputInt);
  266. const int output_number_of_bits = 8 * sizeof(OutputInt);
  267. unsigned int seed = 0;
  268. for (int i = 1; i <= input_number_of_bits; i++) {
  269. for (int j = 1; j <= output_number_of_bits; j++) {
  270. for (int len = 1; len <= kLength; len++) {
  271. // Create a random string of len bytes.
  272. std::vector<InputInt> bits_i(len, 0);
  273. for (InputInt& byte : bits_i) {
  274. byte = generate_random<InputInt>(i, &seed);
  275. }
  276. // Convert to j bits.
  277. ASSERT_OK_AND_ASSIGN(
  278. std::vector<OutputInt> bits_j,
  279. (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
  280. // Ensure that bits_j has the right length.
  281. EXPECT_EQ(bits_j.size(), (len * i + (j - 1)) / j);
  282. // Ensure that the bits came out the same.
  283. for (int bit = 0; bit < i * len; bit++) {
  284. Uint8 bit_i = static_cast<Uint8>(bits_i[bit / i] >> (bit % i));
  285. Uint8 bit_j = static_cast<Uint8>(bits_j[bit / j] >> (bit % j));
  286. EXPECT_EQ(bit_i & 0x01, bit_j & 0x01);
  287. }
  288. // Ensure that all other bits in bits_j are zeros.
  289. for (int byte = 0; byte < bits_j.size(); byte++) {
  290. if (j == output_number_of_bits) continue; // no remaining bits
  291. EXPECT_EQ(bits_j[byte] >> j, 0);
  292. }
  293. }
  294. }
  295. }
  296. }
  297. TYPED_TEST(TranscribeTest, TranscribeTypeToUint128) {
  298. using InputInt = TypeParam;
  299. using OutputInt = absl::uint128;
  300. const int input_number_of_bits = 8 * sizeof(InputInt);
  301. const int output_number_of_bits = 8 * sizeof(OutputInt);
  302. unsigned int seed = 0;
  303. for (int i = 1; i <= input_number_of_bits; i++) {
  304. // Reduce the number of elements to speed up the test.
  305. for (auto j : {2, 7, output_number_of_bits / 2,
  306. output_number_of_bits / 2 + 1, output_number_of_bits}) {
  307. for (int len = 1; len <= kLength; len++) {
  308. // Create a random string of len bytes.
  309. std::vector<InputInt> bits_i(len, 0);
  310. for (InputInt& byte : bits_i) {
  311. byte = generate_random<InputInt>(i, &seed);
  312. }
  313. // Convert to j bits.
  314. ASSERT_OK_AND_ASSIGN(
  315. std::vector<OutputInt> bits_j,
  316. (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
  317. // Ensure that bits_j has the right length.
  318. EXPECT_EQ(bits_j.size(), (len * i + (j - 1)) / j);
  319. // Ensure that the bits came out the same.
  320. for (int bit = 0; bit < i * len; bit++) {
  321. Uint8 bit_i = static_cast<Uint8>(bits_i[bit / i] >> (bit % i));
  322. Uint8 bit_j = static_cast<Uint8>(bits_j[bit / j] >> (bit % j));
  323. EXPECT_EQ(bit_i & 0x01, bit_j & 0x01);
  324. }
  325. // Ensure that all other bits in bits_j are zeros.
  326. for (int byte = 0; byte < bits_j.size(); byte++) {
  327. if (j == output_number_of_bits) continue; // no remaining bits
  328. EXPECT_EQ(bits_j[byte] >> j, 0);
  329. }
  330. }
  331. }
  332. }
  333. }
  334. TYPED_TEST(TranscribeTest, TranscribeTypeToUint8) {
  335. using InputInt = TypeParam;
  336. using OutputInt = Uint8;
  337. const int input_number_of_bits = 8 * sizeof(InputInt);
  338. const int output_number_of_bits = 8 * sizeof(OutputInt);
  339. unsigned int seed = 0;
  340. for (int i = 1; i <= input_number_of_bits; i++) {
  341. for (int j = 1; j <= output_number_of_bits; j++) {
  342. for (int len = 1; len <= kLength; len++) {
  343. // Create a random string of len bytes.
  344. std::vector<InputInt> bits_i(len, 0);
  345. for (InputInt& byte : bits_i) {
  346. byte = generate_random<InputInt>(i, &seed);
  347. }
  348. // Convert to j bits.
  349. ASSERT_OK_AND_ASSIGN(
  350. std::vector<OutputInt> bits_j,
  351. (TranscribeBits<InputInt, OutputInt>(bits_i, len * i, i, j)));
  352. // Ensure that bits_j has the right length.
  353. EXPECT_EQ(bits_j.size(), (len * i + (j - 1)) / j);
  354. // Ensure that the bits came out the same.
  355. for (int bit = 0; bit < i * len; bit++) {
  356. Uint8 bit_i = static_cast<Uint8>(bits_i[bit / i] >> (bit % i));
  357. Uint8 bit_j = static_cast<Uint8>(bits_j[bit / j] >> (bit % j));
  358. EXPECT_EQ(bit_i & 0x01, bit_j & 0x01);
  359. }
  360. // Ensure that all other bits in bits_j are zeros.
  361. for (int byte = 0; byte < bits_j.size(); byte++) {
  362. if (j == output_number_of_bits) continue; // no remaining bits
  363. EXPECT_EQ(bits_j[byte] >> j, 0);
  364. }
  365. }
  366. }
  367. }
  368. }
  369. TYPED_TEST(TranscribeTest, InputLengthSmallerThanNumberOfBitsPerInput) {
  370. using InputInt = TypeParam;
  371. using OutputInt = TypeParam;
  372. const int input_number_of_bits = 8 * sizeof(InputInt);
  373. const int output_number_of_bits = 8 * sizeof(OutputInt);
  374. unsigned int seed = 0;
  375. for (int input_bit_length = 1; input_bit_length < input_number_of_bits;
  376. input_bit_length++) {
  377. // Create a random string of 1 byte.
  378. std::vector<InputInt> bits_i(
  379. {generate_random<InputInt>(input_bit_length, &seed)});
  380. for (int j = 1; j <= output_number_of_bits; j++) {
  381. // Convert to j bits.
  382. ASSERT_OK_AND_ASSIGN(
  383. std::vector<OutputInt> bits_j,
  384. (TranscribeBits<InputInt, OutputInt>(bits_i, input_bit_length,
  385. input_number_of_bits, j)));
  386. // Ensure that bits_j has the right length.
  387. EXPECT_EQ(bits_j.size(), (input_bit_length + (j - 1)) / j);
  388. // Ensure that the bits came out the same.
  389. for (int bit = 0; bit < input_bit_length; bit++) {
  390. Uint8 bit_i = static_cast<Uint8>(bits_i[0] >> bit);
  391. Uint8 bit_j = static_cast<Uint8>(bits_j[bit / j] >> (bit % j));
  392. EXPECT_EQ(bit_i & 0x01, bit_j & 0x01);
  393. }
  394. // Ensure that all other bits in bits_j are zeros.
  395. for (int byte = 0; byte < bits_j.size(); byte++) {
  396. if (j == output_number_of_bits) continue; // no remaining bits
  397. EXPECT_EQ(bits_j[byte] >> j, 0);
  398. }
  399. // The last element will only have input_bit_length % j bits sets.
  400. // Check that all the other bits are 0. The test is only meaningful
  401. // when input_bit_length % j != 0.
  402. if (input_bit_length % j != 0) {
  403. EXPECT_EQ(bits_j[bits_j.size() - 1] >> (input_bit_length % j), 0);
  404. }
  405. }
  406. }
  407. } // namespace
  408. } // namespace
  409. } // namespace rlwe