Merge "Fix typo in PROTOCOL.md"
diff --git a/BUILD b/BUILD
index 4e03973..1d3c2e1 100644
--- a/BUILD
+++ b/BUILD
@@ -44,6 +44,7 @@
 cc_library(
     name = "time_source",
     hdrs = ["time_source.h"],
+    deps = [":protocol"],
 )
 
 cc_library(
diff --git a/client.cc b/client.cc
index 68b1953..8543e0d 100644
--- a/client.cc
+++ b/client.cc
@@ -42,7 +42,7 @@
   return std::string(reinterpret_cast<char*>(query_bytes), query_len);
 }
 
-bool ParseResponse(uint64_t* out_time, uint32_t* out_radius,
+bool ParseResponse(rough_time_t* out_time, uint32_t* out_radius,
                    std::string* out_error,
                    const uint8_t root_public_key[ED25519_PUBLIC_KEY_LEN],
                    const uint8_t* response_bytes, size_t response_len,
@@ -94,7 +94,7 @@
   }
 
   const uint8_t* delegated_public_key;
-  uint64_t min_time, max_time;
+  rough_time_t min_time, max_time;
   Parser delegation(delegation_bytes, delegation_len);
   if (!delegation.is_valid() ||
       !delegation.Get(&min_time, kTagMINT) ||
@@ -144,7 +144,7 @@
   }
 
   const uint8_t* root;
-  uint64_t timestamp;
+  rough_time_t timestamp;
   uint32_t radius;
   if (!signed_response.GetFixedLen(&root, kTagROOT, kNonceLength) ||
       !signed_response.Get(&timestamp, kTagMIDP) ||
diff --git a/client_test.cc b/client_test.cc
index 45c3569..8204de2 100644
--- a/client_test.cc
+++ b/client_test.cc
@@ -75,18 +75,18 @@
   size_t response_len;
 
   std::string out_error;
-  uint64_t out_time;
+  rough_time_t out_time;
   uint32_t out_radius;
 
   // Call the below functions in order to create a response.
   ResponseBuilder();
-  void MakeDelegation(uint64_t mint, uint64_t maxt);
+  void MakeDelegation(rough_time_t mint, rough_time_t maxt);
   void MakeDelegation() { MakeDelegation(999, 1001); }
   void MakeCertificate(const uint8_t* private_key);
   void MakeCertificate() { MakeCertificate(root_private_key); }
   void MakeTree(uint32_t index);
   void MakeTree() { MakeTree(0); }
-  void MakeSigned(uint64_t now);
+  void MakeSigned(rough_time_t now);
   void MakeSigned() { MakeSigned(1000); }
   void MakeResponse(const uint8_t* private_key);
   void MakeResponse() { MakeResponse(delegated_private_key); }
@@ -100,7 +100,7 @@
   ED25519_keypair(root_public_key, root_private_key);
 }
 
-void ResponseBuilder::MakeDelegation(uint64_t mint, uint64_t maxt) {
+void ResponseBuilder::MakeDelegation(rough_time_t mint, rough_time_t maxt) {
   Builder builder(delegation, arraysize(delegation), 3);
   ASSERT_TRUE(builder.AddTagData(kTagPUBK, delegated_public_key,
                                  arraysize(delegated_public_key)));
@@ -142,7 +142,7 @@
   }
 }
 
-void ResponseBuilder::MakeSigned(uint64_t now) {
+void ResponseBuilder::MakeSigned(rough_time_t now) {
   Builder builder(signed_response, arraysize(signed_response), 3);
   static const uint32_t kRadius = 1000000;
   builder.AddTagData(kTagRADI, reinterpret_cast<const uint8_t*>(&kRadius),
diff --git a/go/client/client.go b/go/client/client.go
index 4a9db0b..7938e72 100644
--- a/go/client/client.go
+++ b/go/client/client.go
@@ -206,23 +206,16 @@
 	s.max.Sub(s.max, delta)
 }
 
+// contains returns true iff p belongs to s
+func (s *timeSample) contains(p *big.Int) bool {
+	return s.max.Cmp(p) >= 0 && s.min.Cmp(p) <= 0
+}
+
 // overlaps returns true iff s and other have any timespan in common.
 func (s *timeSample) overlaps(other *timeSample) bool {
 	return s.max.Cmp(other.min) >= 0 && other.max.Cmp(s.min) >= 0
 }
 
-// overlapsAll returns true iff s has s timespan in common with all of the
-// elements of others.
-func (s *timeSample) overlapsAll(others []*timeSample) bool {
-	for _, other := range others {
-		if !s.overlaps(other) {
-			return false
-		}
-	}
-
-	return true
-}
-
 // query sends a request to s, appends it to chain, and returns the resulting
 // timeSample.
 func (c *Client) query(server *config.Server, chain *config.Chain) (*timeSample, error) {
@@ -415,10 +408,10 @@
 
 	for _, sample := range samples[1:] {
 		if ret.min.Cmp(sample.min) < 0 {
-			sample.min.Set(ret.min)
+			ret.min.Set(sample.min)
 		}
 		if ret.max.Cmp(sample.max) > 0 {
-			sample.max.Set(ret.max)
+			ret.max.Set(sample.max)
 		}
 	}
 
@@ -437,11 +430,13 @@
 
 	overlapping := make([]*timeSample, 0, n)
 
-	for i, initial := range samples {
-		overlapping = append(overlapping, initial)
+	for _, initial := range samples {
+		// An intersection of any subset of intervals will be an interval that contains
+		// the starting point of one of the intervals (possibly as its own starting point).
+		point := initial.min
 
-		for _, candidate := range samples[i+1:] {
-			if candidate.overlapsAll(overlapping) {
+		for _, candidate := range samples {
+			if candidate.contains(point) {
 				overlapping = append(overlapping, candidate)
 			}
 
diff --git a/go/client/client_test.go b/go/client/client_test.go
index bebec9f..d08d955 100644
--- a/go/client/client_test.go
+++ b/go/client/client_test.go
@@ -17,6 +17,7 @@
 import (
 	"crypto/rand"
 	"encoding/json"
+	"math/big"
 	"net"
 	"strconv"
 	"sync"
@@ -333,3 +334,56 @@
 		addr:      localAddr,
 	}, nil
 }
+
+func TestFindNOverlapping(t *testing.T) {
+	type sample struct {
+		min int64
+		max int64
+	}
+	testcases := []struct {
+		samples []sample
+		maxN    int
+	}{
+		{
+			samples: []sample{
+				{0, 2},
+				{1, 3},
+			},
+			maxN: 2,
+		},
+		{
+			samples: []sample{
+				{0, 2},
+				{1, 3},
+				{4, 5},
+			},
+			maxN: 2,
+		},
+		{
+			samples: []sample{
+				{0, 10},
+				{1, 2},
+				{5, 10},
+				{6, 10},
+			},
+			maxN: 3,
+		},
+	}
+	for i, tc := range testcases {
+		samples := make([]*timeSample, len(tc.samples))
+		for j, s := range tc.samples {
+			samples[j] = &timeSample{
+				base: big.NewInt(0),
+				min:  big.NewInt(s.min),
+				max:  big.NewInt(s.max),
+			}
+		}
+		for n := 1; n <= len(samples); n++ {
+			expectedOk := n <= tc.maxN
+			_, ok := findNOverlapping(samples, n)
+			if ok != expectedOk {
+				t.Errorf("#%d: findNOverlapping(n=%d) returned %v, wanted %v", i, n, ok, expectedOk)
+			}
+		}
+	}
+}
diff --git a/protocol.cc b/protocol.cc
index 44afcad..358755e 100644
--- a/protocol.cc
+++ b/protocol.cc
@@ -102,7 +102,7 @@
 
 static int tag_cmp(const void *keyp, const void *memberp) {
   tag_t key, member;
-  memcpy(&key, keyp, sizeof(uint32_t));
+  memcpy(&key, keyp, sizeof(tag_t));
   memcpy(&member, memberp, sizeof(uint32_t));
 
   if (key == member) {
diff --git a/protocol.h b/protocol.h
index d0a8515..1ae044d 100644
--- a/protocol.h
+++ b/protocol.h
@@ -35,6 +35,13 @@
 
 typedef uint32_t tag_t;
 
+// rough_time_t is the type of a time stamp. Time is UTC and is given as
+// milliseconds since the UNIX epoch (00:00:00 UTC on 1 January 1970). Leap
+// seconds are linearly smeared over a 24-hour period. That is, the smear
+// extends from UTC noon to noon over 86,401 or 86,399 SI seconds, and all the
+// smeared seconds are the same length.
+typedef uint64_t rough_time_t;
+
 // MakeTag creates an integer value representing a tag.  Requests and responses
 // in the time protocol are made up of tagged data, QUIC-style.  Tags are 4
 // bytes long and meant to be readable-ish, but they cannot be chosen with
diff --git a/protocol_test.cc b/protocol_test.cc
index a912fcf..306e327 100644
--- a/protocol_test.cc
+++ b/protocol_test.cc
@@ -25,8 +25,7 @@
 constexpr tag_t kTagTAG4 = MakeTag('T', 'A', 'G', '4');
 
 TEST(ParserTest, Success) {
-  alignas(4) uint8_t buffer[] = {
-      0x00,                    // misalign the buffer
+  const uint8_t buffer[] = {
       0x03, 0x00, 0x00, 0x00,  // 3 tags
       0x04, 0x00, 0x00, 0x00,  // tag #2 has offset 4
       0x08, 0x00, 0x00, 0x00,  // tag #3 has offset 8
@@ -38,7 +37,7 @@
       0x33, 0x33, 0x33, 0x33,  // data for tag #3
   };
 
-  Parser parser(buffer + 1, sizeof(buffer) - 1);
+  Parser parser(buffer, sizeof(buffer));
   EXPECT_TRUE(parser.is_valid());
   const uint8_t* datap;
   size_t len;
@@ -71,6 +70,42 @@
   EXPECT_FALSE(parser.GetFixedLen(&datap, kTagTAG4, 1));
 }
 
+TEST(ParserTest, UnalignedInput) {
+  alignas(4) const uint8_t buffer[] = {
+      0x00,                    // unalign input.
+      0x02, 0x00, 0x00, 0x00,  // 2 tags
+      0x04, 0x00, 0x00, 0x00,  // tag #2 has offset 4
+      0x54, 0x41, 0x47, 0x31,  // TAG1
+      0x54, 0x41, 0x47, 0x32,  // TAG2
+      0x11, 0x11, 0x11, 0x11,  // data for tag #1
+      0x22, 0x22, 0x22, 0x22,  // data for tag #2
+  };
+
+  Parser parser(buffer + 1, sizeof(buffer) - 1);
+  EXPECT_TRUE(parser.is_valid());
+  const uint8_t* datap;
+  size_t len;
+
+  EXPECT_TRUE(parser.GetTag(&datap, &len, kTagTAG1));
+  EXPECT_EQ(4, len);
+  EXPECT_TRUE(memcmp("\x11\x11\x11\x11", datap, len) == 0);
+  datap = nullptr;
+  EXPECT_TRUE(parser.GetFixedLen(&datap, kTagTAG1, 4));
+  EXPECT_TRUE(memcmp("\x11\x11\x11\x11", datap, len) == 0);
+  datap = nullptr;
+
+  EXPECT_TRUE(parser.GetTag(&datap, &len, kTagTAG2));
+  EXPECT_EQ(4, len);
+  EXPECT_TRUE(memcmp("\x22\x22\x22\x22", datap, len) == 0);
+  datap = nullptr;
+  EXPECT_TRUE(parser.GetFixedLen(&datap, kTagTAG2, 4));
+  EXPECT_TRUE(memcmp("\x22\x22\x22\x22", datap, len) == 0);
+  datap = nullptr;
+
+  EXPECT_FALSE(parser.GetTag(&datap, &len, kTagTAG4));
+  EXPECT_FALSE(parser.GetFixedLen(&datap, kTagTAG4, 1));
+}
+
 TEST(ParserTest, IntegerTypes) {
   uint8_t buffer[128];
   Builder builder(buffer, sizeof(buffer), 2);
diff --git a/server.cc b/server.cc
index 85443db..e10a956 100644
--- a/server.cc
+++ b/server.cc
@@ -81,7 +81,7 @@
   // The signature is over the root hash and the timestamp---that's it!
   tree_.Build(num_leaves_);
   const auto interval = time_source_->Now();
-  const uint64_t now = interval.first;
+  const rough_time_t now = interval.first;
   const uint32_t radius = interval.second;
 
   Builder to_be_signed(to_be_signed_, kToBeSignedSize, 3);
@@ -140,7 +140,7 @@
 // static
 bool CreateCertificate(uint8_t out_cert[kCertSize],
                        const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN],
-                       uint64_t start_time, uint64_t end_time,
+                       rough_time_t start_time, rough_time_t end_time,
                        const uint8_t public_key[ED25519_PUBLIC_KEY_LEN]) {
   GOOGLE_CHECK_LT(start_time, end_time);
   uint8_t to_be_signed_bytes[sizeof(kCertContextString) + kToBeSignedCertSize];
diff --git a/server.h b/server.h
index 7953a38..d10a2e3 100644
--- a/server.h
+++ b/server.h
@@ -42,7 +42,7 @@
 // TODO(mab): Find better home for this, likely in an offline tool.
 bool CreateCertificate(uint8_t out_cert[kCertSize],
                        const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN],
-                       uint64_t start_time, uint64_t end_time,
+                       rough_time_t start_time, rough_time_t end_time,
                        const uint8_t public_key[ED25519_PUBLIC_KEY_LEN]);
 
 // Identity is a server's private key and certificate.  (The certificate is the
diff --git a/simple_client.cc b/simple_client.cc
index 145227a..ab04061 100644
--- a/simple_client.cc
+++ b/simple_client.cc
@@ -269,7 +269,7 @@
     return kExitNetworkError;
   }
 
-  uint64_t timestamp;
+  roughtime::rough_time_t timestamp;
   uint32_t radius;
   std::string error;
   if (!roughtime::ParseResponse(
diff --git a/simple_server.cc b/simple_server.cc
index c0c2261..8b3a764 100644
--- a/simple_server.cc
+++ b/simple_server.cc
@@ -38,8 +38,8 @@
 
 // static
 std::unique_ptr<Identity> SimpleServer::MakeIdentity(
-    const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN], uint64_t mint,
-    uint64_t maxt) {
+    const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN], rough_time_t mint,
+    rough_time_t maxt) {
   GOOGLE_CHECK(mint <= maxt);
   uint8_t delegated_private_key[ED25519_PRIVATE_KEY_LEN];
   uint8_t delegated_public_key[ED25519_PUBLIC_KEY_LEN];
diff --git a/simple_server.h b/simple_server.h
index 159e7ff..30f09f7 100644
--- a/simple_server.h
+++ b/simple_server.h
@@ -47,8 +47,8 @@
   // MakeIdentity creates a dummy server certificate that is valid for the
   // given time range.
   static std::unique_ptr<Identity> MakeIdentity(
-      const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN], uint64_t mint,
-      uint64_t maxt);
+      const uint8_t root_private_key[ED25519_PRIVATE_KEY_LEN],
+      rough_time_t mint, rough_time_t maxt);
 
  private:
   const int fd_;
diff --git a/simple_server_main.cc b/simple_server_main.cc
index bc3002a..99048ef 100644
--- a/simple_server_main.cc
+++ b/simple_server_main.cc
@@ -60,7 +60,8 @@
   std::unique_ptr<roughtime::Identity> identity =
       roughtime::SimpleServer::MakeIdentity(root_private_key, 0,
                                             2147483647000000);
-  std::unique_ptr<TimeSource> time_source(new roughtime::SystemTimeSource);
+  std::unique_ptr<roughtime::TimeSource> time_source(
+      new roughtime::SystemTimeSource);
 
   auto server =
       std::unique_ptr<roughtime::SimpleServer>(new roughtime::SimpleServer(
diff --git a/sys_time.cc b/sys_time.cc
index b0eca57..5fa9532 100644
--- a/sys_time.cc
+++ b/sys_time.cc
@@ -24,7 +24,7 @@
 
 SystemTimeSource::~SystemTimeSource() {}
 
-std::pair<uint64_t, uint32_t> SystemTimeSource::Now() {
+std::pair<rough_time_t, uint32_t> SystemTimeSource::Now() {
   struct timespec ts;
   GOOGLE_CHECK_EQ(0, clock_gettime(CLOCK_REALTIME_COARSE, &ts));
   uint64_t now = ts.tv_sec;
diff --git a/time_source.h b/time_source.h
index 929faaa..022ce86 100644
--- a/time_source.h
+++ b/time_source.h
@@ -19,6 +19,10 @@
 
 #include <utility>
 
+#include "protocol.h"
+
+namespace roughtime {
+
 // TimeSource is an interface that can provide the current time.
 class TimeSource {
  public:
@@ -26,7 +30,9 @@
 
   // Now returns the midpoint time in epoch-microseconds and a radius of
   // uncertainty.
-  virtual std::pair<uint64_t, uint32_t> Now() = 0;
+  virtual std::pair<rough_time_t, uint32_t> Now() = 0;
 };
 
+}  // namespace roughtime
+
 #endif  // SECURITY_ROUGHTIME_TIME_SOURCE_H_