1 /*
2 * Copyright 2018 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 * https://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
17 #include "fcp/secagg/shared/math.h"
18
19 #include <cstdint>
20
21 #include "gmock/gmock.h"
22 #include "gtest/gtest.h"
23
24 namespace fcp {
25 namespace secagg {
26 namespace {
27
28 using ::testing::Eq;
29
TEST(MathTest,DivideRoundUpIsAccurate)30 TEST(MathTest, DivideRoundUpIsAccurate) {
31 EXPECT_THAT(DivideRoundUp(0, 8), Eq(0));
32 EXPECT_THAT(DivideRoundUp(1, 8), Eq(1));
33 EXPECT_THAT(DivideRoundUp(8, 8), Eq(1));
34 EXPECT_THAT(DivideRoundUp(12, 8), Eq(2));
35 EXPECT_THAT(DivideRoundUp(31, 8), Eq(4));
36 EXPECT_THAT(DivideRoundUp(32, 8), Eq(4));
37 EXPECT_THAT(DivideRoundUp(33, 8), Eq(5));
38 }
39
TEST(MathTest,AddModIsAccurate)40 TEST(MathTest, AddModIsAccurate) {
41 // power-of-2 moduli
42 EXPECT_THAT(AddMod(2, 5, 8), Eq(7));
43 EXPECT_THAT(AddMod(4, 5, 8), Eq(1));
44 EXPECT_THAT(AddMod(0, 5, 8), Eq(5));
45 EXPECT_THAT(AddMod(5, 0, 8), Eq(5));
46 EXPECT_THAT(AddMod(7, 7, 8), Eq(6));
47 EXPECT_THAT(AddMod(9223372036854775806ULL, 9223372036854775807ULL,
48 9223372036854775808ULL),
49 Eq(9223372036854775805ULL));
50
51 // non-power-of-2 moduli
52 EXPECT_THAT(AddMod(2, 5, 7), Eq(0));
53 EXPECT_THAT(AddMod(4, 5, 7), Eq(2));
54 EXPECT_THAT(AddMod(0, 5, 7), Eq(5));
55 EXPECT_THAT(AddMod(5, 0, 7), Eq(5));
56 EXPECT_THAT(AddMod(7, 7, 7), Eq(0));
57 EXPECT_THAT(AddMod(9223372036854775805ULL, 9223372036854775806ULL,
58 9223372036854775807ULL),
59 Eq(9223372036854775804ULL));
60 }
61
TEST(MathTest,AddModOptIsAccurate)62 TEST(MathTest, AddModOptIsAccurate) {
63 // power-of-2 moduli
64 EXPECT_THAT(AddModOpt(2, 5, 8), Eq(7));
65 EXPECT_THAT(AddModOpt(4, 5, 8), Eq(1));
66 EXPECT_THAT(AddModOpt(0, 5, 8), Eq(5));
67 EXPECT_THAT(AddModOpt(5, 0, 8), Eq(5));
68 EXPECT_THAT(AddModOpt(7, 7, 8), Eq(6));
69 EXPECT_THAT(AddModOpt(9223372036854775806ULL, 9223372036854775807ULL,
70 9223372036854775808ULL),
71 Eq(9223372036854775805ULL));
72
73 // non-power-of-2 moduli
74 EXPECT_THAT(AddModOpt(2, 5, 7), Eq(0));
75 EXPECT_THAT(AddModOpt(4, 5, 7), Eq(2));
76 EXPECT_THAT(AddModOpt(0, 5, 7), Eq(5));
77 EXPECT_THAT(AddModOpt(5, 0, 7), Eq(5));
78 EXPECT_THAT(AddModOpt(6, 6, 7), Eq(5));
79 EXPECT_THAT(AddModOpt(9223372036854775805ULL, 9223372036854775806ULL,
80 9223372036854775807ULL),
81 Eq(9223372036854775804ULL));
82 }
83
TEST(MathTest,SubtractModWorksAndHandlesUnderflow)84 TEST(MathTest, SubtractModWorksAndHandlesUnderflow) {
85 EXPECT_THAT(SubtractMod(3, 4, 10), Eq(9));
86 EXPECT_THAT(SubtractMod(2, 9, 10), Eq(3));
87 EXPECT_THAT(SubtractMod(0, 6, 10), Eq(4));
88 EXPECT_THAT(SubtractMod(0, 5, 10), Eq(5));
89 EXPECT_THAT(SubtractMod(7, 3, 10), Eq(4));
90 EXPECT_THAT(SubtractMod(9, 0, 10), Eq(9));
91 EXPECT_THAT(SubtractMod(0, 0, 10), Eq(0));
92 EXPECT_THAT(SubtractMod(7, 7, 10), Eq(0));
93 EXPECT_THAT(SubtractMod(9223372036854775807ULL, 0, 9223372036854775808ULL),
94 Eq(9223372036854775807ULL));
95 EXPECT_THAT(SubtractMod(0, 9223372036854775807ULL, 9223372036854775808ULL),
96 Eq(1));
97 EXPECT_THAT(SubtractMod(9223372036854775805ULL, 9223372036854775807ULL,
98 9223372036854775808ULL),
99 Eq(9223372036854775806ULL));
100
101 EXPECT_THAT(SubtractMod(9223372036854775806ULL, 0, 9223372036854775807ULL),
102 Eq(9223372036854775806ULL));
103 EXPECT_THAT(SubtractMod(0, 9223372036854775806ULL, 9223372036854775807ULL),
104 Eq(1));
105 EXPECT_THAT(SubtractMod(9223372036854775805ULL, 9223372036854775806ULL,
106 9223372036854775807ULL),
107 Eq(9223372036854775806ULL));
108 }
109
TEST(MathTest,SubtractModOptWorksAndHandlesUnderflow)110 TEST(MathTest, SubtractModOptWorksAndHandlesUnderflow) {
111 EXPECT_THAT(SubtractModOpt(3, 4, 10), Eq(9));
112 EXPECT_THAT(SubtractModOpt(2, 9, 10), Eq(3));
113 EXPECT_THAT(SubtractModOpt(0, 6, 10), Eq(4));
114 EXPECT_THAT(SubtractModOpt(0, 5, 10), Eq(5));
115 EXPECT_THAT(SubtractModOpt(7, 3, 10), Eq(4));
116 EXPECT_THAT(SubtractModOpt(9, 0, 10), Eq(9));
117 EXPECT_THAT(SubtractModOpt(0, 0, 10), Eq(0));
118 EXPECT_THAT(SubtractModOpt(7, 7, 10), Eq(0));
119 EXPECT_THAT(SubtractModOpt(9223372036854775807ULL, 0, 9223372036854775808ULL),
120 Eq(9223372036854775807ULL));
121 EXPECT_THAT(SubtractModOpt(0, 9223372036854775807ULL, 9223372036854775808ULL),
122 Eq(1));
123 EXPECT_THAT(SubtractModOpt(9223372036854775805ULL, 9223372036854775807ULL,
124 9223372036854775808ULL),
125 Eq(9223372036854775806ULL));
126
127 EXPECT_THAT(SubtractModOpt(9223372036854775806ULL, 0, 9223372036854775807ULL),
128 Eq(9223372036854775806ULL));
129 EXPECT_THAT(SubtractModOpt(0, 9223372036854775806ULL, 9223372036854775807ULL),
130 Eq(1));
131 EXPECT_THAT(SubtractModOpt(9223372036854775805ULL, 9223372036854775806ULL,
132 9223372036854775807ULL),
133 Eq(9223372036854775806ULL));
134 }
135
TEST(MathTest,MultiplyModAvoidsOverflow)136 TEST(MathTest, MultiplyModAvoidsOverflow) {
137 uint64_t p = 2147483659ULL; // 2 ^ 31 + 11; a prime number
138 uint32_t a = 2147483646; // 2 ^ 31 - 2; -13 mod p
139 uint32_t b = 2147483640; // 2 ^ 31 - 8; -19 mod p
140 uint32_t res1 = 169; // -13 * -13
141 uint32_t res2 = 247; // -13 * -19
142 uint32_t res3 = 361; // -19 * -19
143 EXPECT_THAT(MultiplyMod(a, a, p), Eq(res1));
144 EXPECT_THAT(MultiplyMod(a, b, p), Eq(res2));
145 EXPECT_THAT(MultiplyMod(b, a, p), Eq(res2));
146 EXPECT_THAT(MultiplyMod(b, b, p), Eq(res3));
147 }
148
TEST(MathTest,MultiplyMod64AvoidsOverflow)149 TEST(MathTest, MultiplyMod64AvoidsOverflow) {
150 {
151 uint64_t p = 2147483659ULL; // 2 ^ 31 + 11; a prime number
152 uint32_t a = 2147483646; // 2 ^ 31 - 2; -13 mod p
153 uint32_t b = 2147483640; // 2 ^ 31 - 8; -19 mod p
154 uint32_t res1 = 169; // -13 * -13
155 uint32_t res2 = 247; // -13 * -19
156 uint32_t res3 = 361; // -19 * -19
157 EXPECT_THAT(MultiplyMod64(a, a, p), Eq(res1));
158 EXPECT_THAT(MultiplyMod64(a, b, p), Eq(res2));
159 EXPECT_THAT(MultiplyMod64(b, a, p), Eq(res2));
160 EXPECT_THAT(MultiplyMod64(b, b, p), Eq(res3));
161 }
162
163 {
164 uint64_t p = 4503599627371499ULL; // 2 ^ 52 + 1003; a prime number
165 uint64_t a = 1099511627776ULL; // 2 ^ 40
166 uint64_t b = 36028797018963971ULL; // 2 ^ 55 + 3
167 uint64_t res1 = 4503330386609131ULL; // a * a
168 uint64_t res2 = 188016488351702ULL; // a * b
169 uint64_t res3 = 64336441ULL; // b * b
170 EXPECT_THAT(MultiplyMod64(a, a, p), Eq(res1));
171 EXPECT_THAT(MultiplyMod64(a, b, p), Eq(res2));
172 EXPECT_THAT(MultiplyMod64(b, a, p), Eq(res2));
173 EXPECT_THAT(MultiplyMod64(b, b, p), Eq(res3));
174 }
175 }
TEST(MathTest,InverseModPrimeIsAccurate)176 TEST(MathTest, InverseModPrimeIsAccurate) {
177 // All mods assumed to be prime
178 EXPECT_THAT(InverseModPrime(12, 31), Eq(13));
179 EXPECT_THAT(InverseModPrime(13, 31), Eq(12));
180 EXPECT_THAT(InverseModPrime(13, 2147483659ULL), Eq(1651910507));
181 EXPECT_THAT(InverseModPrime(2147483646, 2147483659ULL), Eq(495573152));
182 }
183
TEST(MathTest,IntToByteStringProvidesBigEndianString)184 TEST(MathTest, IntToByteStringProvidesBigEndianString) {
185 uint32_t big_low_bits = 0x01234567;
186 uint32_t big_high_bits = 0xFEDCBA98;
187 uint32_t max_val = 0xFFFFFFFF;
188 uint32_t min_val = 0x00000000;
189 uint8_t expected0[4] = {0x1, 0x23, 0x45, 0x67};
190 EXPECT_THAT(IntToByteString(big_low_bits),
191 Eq(std::string(reinterpret_cast<char*>(expected0), 4)));
192 uint8_t expected1[4] = {0xFE, 0xDC, 0xBA, 0x98};
193 EXPECT_THAT(IntToByteString(big_high_bits),
194 Eq(std::string(reinterpret_cast<char*>(expected1), 4)));
195 uint8_t expected2[4] = {0xFF, 0xFF, 0xFF, 0xFF};
196 EXPECT_THAT(IntToByteString(max_val),
197 Eq(std::string(reinterpret_cast<char*>(expected2), 4)));
198 uint8_t expected3[4] = {0x0, 0x0, 0x0, 0x0};
199 EXPECT_THAT(IntToByteString(min_val),
200 Eq(std::string(reinterpret_cast<char*>(expected3), 4)));
201 }
202
203 } // namespace
204 } // namespace secagg
205 } // namespace fcp
206