algorithms/forculus/field_element_test.cc

// Copyright 2016 The Fuchsia Authors
//
// 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 "algorithms/forculus/field_element.h"

#include "third_party/googletest/googletest/include/gtest/gtest.h"

namespace cobalt {
namespace forculus {

/****************************** Notice *************************************
*
* The tests currently in this file are based on the temporary, insecure
* implementation of FieldElement that interprets the first 32 bits of
* data as an integer in little-endian and discards the rest of the bytes.
* These will be replaced by different tests when the field changes to GF(2^128).
*
*****************************************************************************/

namespace {
// Make the FieldElement with the given vector of bytes. This wrapper around the
// constructor is necessary because the compiler can't tell which constructor
// to use with an expression like FieldElement({2}).
FieldElement FromBytes(std::vector<byte>&& bytes) {
  return FieldElement(std::move(bytes));
}
FieldElement FromString(const std::string& data) {
  return FieldElement(data);
}

FieldElement FromInt(uint32_t x) {
  std::vector<byte> bytes(sizeof(x));
  std::memcpy(bytes.data(), &x, sizeof(x));
  return FieldElement(std::move(bytes));
}

}  // namespace

TEST(FieldElementTest, TestConstructors) {
  // Expect that the byte constructor discards all but the first 4 bytes.
  FieldElement el = FromBytes({0, 1, 2, 3, 4, 5});
  const byte* bytes = el.KeyBytes();
  EXPECT_EQ(0, bytes[0]);
  EXPECT_EQ(1, bytes[1]);
  EXPECT_EQ(2, bytes[2]);
  EXPECT_EQ(3, bytes[3]);
  EXPECT_EQ(0, bytes[4]);
  EXPECT_EQ(0, bytes[5]);

  // Expect that the string constructor discards all but the first 4 bytes.
  el = FromString({0, 1, 2, 3, 4, 5, 6});
  bytes = el.KeyBytes();
  EXPECT_EQ(0, bytes[0]);
  EXPECT_EQ(1, bytes[1]);
  EXPECT_EQ(2, bytes[2]);
  EXPECT_EQ(3, bytes[3]);
  EXPECT_EQ(0, bytes[4]);
  EXPECT_EQ(0, bytes[5]);

  // Expect that 1 is represented in little-endian as 1 0 0 0 ...
  el = FieldElement(true);
  bytes = el.KeyBytes();
  EXPECT_EQ(1, bytes[0]);
  EXPECT_EQ(0, bytes[1]);
  EXPECT_EQ(0, bytes[2]);
  EXPECT_EQ(0, bytes[3]);
  EXPECT_EQ(0, bytes[4]);
  EXPECT_EQ(0, bytes[5]);

  // Expect that 0 is represented as 0 0 0 ...
  el = FieldElement(0);
  bytes = el.KeyBytes();
  EXPECT_EQ(0, bytes[0]);
  EXPECT_EQ(0, bytes[1]);
  EXPECT_EQ(0, bytes[2]);
  EXPECT_EQ(0, bytes[3]);
  EXPECT_EQ(0, bytes[4]);
  EXPECT_EQ(0, bytes[5]);

  // Test the copy constructor
  FieldElement x = FromBytes({0, 1, 2, 3, 4, 5});
  FieldElement y(x);
  EXPECT_EQ(x, y);

  // Test the move constructor
  FieldElement z(std::move(y));
  EXPECT_EQ(x, z);
  EXPECT_NE(x, y);

  // Test the copy assignment operator
  y = x;
  EXPECT_EQ(x, y);

  // Test the move assignment operator
  z = std::move(y);
  EXPECT_EQ(x, z);
  EXPECT_NE(x, y);
}

TEST(FieldElementTest, TestCopyBytesToString) {
  FieldElement el = FromBytes({0, 1, 2, 3, 4, 5});
  std::string s;
  el.CopyBytesToString(&s);
  EXPECT_EQ(FieldElement::kDataSize, s.size());
  std::string expected_string = std::string("\0\x1\x2\x3", 4) +
      std::string(FieldElement::kDataSize - 4, 0);
  EXPECT_EQ(expected_string, s);
}


TEST(FieldElementTest, TestArithmetic) {
  // Test that 2 + 3 = 5.
  EXPECT_EQ(FromInt(5), FromInt(2) + FromInt(3));

  // Test that 2 + 3 = 5 with +=
  FieldElement x = FromInt(2);
  FieldElement y = FromInt(3);
  FieldElement z = FromInt(5);
  x+= y;
  EXPECT_EQ(z, x);

  // Test that -1 + 1 = 0.
  // The bytes are kLargestPrime -1 in little-endian.
  static const FieldElement kMinusOne = FromBytes({0xF4, 0xFE, 0xFF, 0xFF});
  EXPECT_EQ(FieldElement(false), kMinusOne + FieldElement(true));

  // Test that -1 + 1 = 0 with +=.
  x = kMinusOne;
  x+= FieldElement(true);
  EXPECT_EQ(FieldElement(false), x);

  // Test that 5 - 2 = 3
  EXPECT_EQ(FromInt(3), FromInt(5) - FromInt(2));

  // Test that 5 - 2 = 3 using -=.
  x = FromInt(5);
  y = FromInt(2);
  x-= y;
  EXPECT_EQ(FromInt(3), x);

  // Test that 0 - 1 = -1
  EXPECT_EQ(kMinusOne, FieldElement(false) - FieldElement(true));

  // Test that 0 - 1 = -1 using -=.
  x = FieldElement(false);
  x -= FieldElement(true);
  EXPECT_EQ(kMinusOne, x);

  // Test that 1999000 - 1998999 = 1
  EXPECT_EQ(FieldElement(true), FromInt(1999000) - FromInt(1998999));

  // Test that 1999000 - 1998999 = 1 using -=
  x = FromInt(1999000);
  x -= FromInt(1998999);
  EXPECT_EQ(FieldElement(true), x);

  // Test that 3 * 5 = 15.
  EXPECT_EQ(FromInt(15), FromInt(3) * FromInt(5));

  // Test that 3 * 5 = 15 using *=
  x = FromInt(3);
  x*= FromInt(5);
  EXPECT_EQ(FromInt(15), x);

  // Test that -1 * 2 = -2.
  static const FieldElement kMinus2 = FromBytes({0xF3, 0xFE, 0xFF, 0xFF});
  EXPECT_EQ(kMinus2, kMinusOne * FromInt(2));

  // Test that -1 * 2 = -2 using *=
  x = kMinusOne;
  x*= FromInt(2);
  EXPECT_EQ(kMinus2, x);

  // Check that 1/1 = 1.
  x = FieldElement(true);
  EXPECT_EQ(x, x/x);

  // Check that 5/5 = 1
  x = FromInt(5);
  EXPECT_EQ(FieldElement(true), x/x);

  // Check that 10/5 = 2
  y = FromInt(10);
  EXPECT_EQ(FromInt(2), y/x);

  // Check that 10/5 = 2 using /=
  y = FromInt(10);
  y/=x;
  EXPECT_EQ(FromInt(2), y);

  // Check that 0/5 = 0
  y = FieldElement(false);
  EXPECT_EQ(y, y/x);

  // Check that 1/2 * 2 = 1.
  x = FieldElement(true)/FromInt(2);
  x *= FromInt(2);
  EXPECT_EQ(FieldElement(true), x);

  // Check that 2/3 * 3 = 2.
  x = FromInt(2)/FromInt(3);
  x *= FromInt(3);
  EXPECT_EQ(FromInt(2), x);

  // Check that 2/3 * 2/3 = 4/9
  x = FromInt(2)/FromInt(3);
  x*= x;
  EXPECT_EQ(FromInt(4)/FromInt(9), x);

  // Check that 1999*1000/(1000 - 999) + 2001*999/(999 - 1000) = 1.
  FieldElement x0 = FromInt(999);
  FieldElement y0 = FromInt(1999);
  FieldElement x1 = FromInt(1000);
  FieldElement y1 = FromInt(2001);
  EXPECT_EQ(FieldElement(true), y0*x1/(x1-x0) + y1*x0/(x0 -x1));
}

}  // namespace forculus

}  // namespace cobalt