[search] Add Open Location Code library

8 files changed, 936 insertions, 0 deletions

diff --git a/3party/open-location-code/BUILD b/3party/open-location-code/BUILD
new file mode 100644
index 0000000000..d31b6b52f8
--- /dev/null
+++ b/3party/open-location-code/BUILD
@@ -0,0 +1,55 @@
+cc_library(
+    name = "openlocationcode",
+    srcs = [
+        "openlocationcode.cc",
+    ],
+    hdrs = [
+        "codearea.h",
+        "openlocationcode.h",
+    ],
+    copts = ["-pthread"],
+    linkopts = ["-pthread"],
+    visibility = ["//visibility:public"],
+    deps = [
+        ":codearea",
+    ],
+)
+
+cc_library(
+    name = "codearea",
+    srcs = [
+        "codearea.cc",
+    ],
+    hdrs = [
+        "codearea.h",
+    ],
+    visibility = ["//visibility:private"],
+)
+
+cc_test(
+    name = "openlocationcode_test",
+    size = "small",
+    srcs = ["openlocationcode_test.cc"],
+    copts = [
+        "-pthread",
+        "-Iexternal/gtest/include",
+    ],
+    data = [
+        "//test_data",
+    ],
+    linkopts = ["-pthread"],
+    deps = [
+        ":openlocationcode",
+        "@gtest//:main",
+    ],
+)
+
+cc_binary(
+    name = "openlocationcode_example",
+    srcs = [
+        "openlocationcode_example.cc",
+    ],
+    deps = [
+        ":openlocationcode",
+    ],
+)
diff --git a/3party/open-location-code/CMakeLists.txt b/3party/open-location-code/CMakeLists.txt
new file mode 100644
index 0000000000..1ceb85a1e5
--- /dev/null
+++ b/3party/open-location-code/CMakeLists.txt
@@ -0,0 +1,13 @@
+project(openlocationcode)
+
+include_directories(src ../../)
+
+set(
+  SRC
+  codearea.cc
+  codearea.h
+  openlocationcode.cc
+  openlocationcode.h
+)
+
+add_library(${PROJECT_NAME} ${SRC})
diff --git a/3party/open-location-code/LICENSE b/3party/open-location-code/LICENSE
new file mode 100644
index 0000000000..d645695673
--- /dev/null
+++ b/3party/open-location-code/LICENSE
@@ -0,0 +1,202 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   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.
diff --git a/3party/open-location-code/README.md b/3party/open-location-code/README.md
new file mode 100644
index 0000000000..0dc9fcc031
--- /dev/null
+++ b/3party/open-location-code/README.md
@@ -0,0 +1,4 @@
+# Open Location Code C++ API
+This is the C++ implementation of the Open Location Code API.
+
+Copied from [Google's Repository](https://github.com/google/open-location-code).
diff --git a/3party/open-location-code/codearea.cc b/3party/open-location-code/codearea.cc
new file mode 100644
index 0000000000..d4c3e52544
--- /dev/null
+++ b/3party/open-location-code/codearea.cc
@@ -0,0 +1,44 @@
+#include "codearea.h"
+
+#include <algorithm>
+
+namespace openlocationcode {
+
+const double kLatitudeMaxDegrees = 90;
+const double kLongitudeMaxDegrees = 180;
+
+CodeArea::CodeArea(double latitude_lo, double longitude_lo, double latitude_hi,
+                   double longitude_hi, size_t code_length) {
+  latitude_lo_ = latitude_lo;
+  longitude_lo_ = longitude_lo;
+  latitude_hi_ = latitude_hi;
+  longitude_hi_ = longitude_hi;
+  code_length_ = code_length;
+}
+
+double CodeArea::GetLatitudeLo() const{
+  return latitude_lo_;
+}
+
+double CodeArea::GetLongitudeLo() const {
+  return longitude_lo_;
+}
+
+double CodeArea::GetLatitudeHi() const {
+  return latitude_hi_;
+}
+
+double CodeArea::GetLongitudeHi() const {
+  return longitude_hi_;
+}
+
+size_t CodeArea::GetCodeLength() const { return code_length_; }
+
+LatLng CodeArea::GetCenter() const {
+  double latitude_center = std::min(latitude_lo_ + (latitude_hi_ - latitude_lo_) / 2, kLatitudeMaxDegrees);
+  double longitude_center = std::min(longitude_lo_ + (longitude_hi_ - longitude_lo_) / 2, kLongitudeMaxDegrees);
+  LatLng center = {latitude: latitude_center, longitude: longitude_center};
+  return center;
+}
+
+} // namespace openlocationcode
\ No newline at end of file
diff --git a/3party/open-location-code/codearea.h b/3party/open-location-code/codearea.h
new file mode 100644
index 0000000000..ea36216df0
--- /dev/null
+++ b/3party/open-location-code/codearea.h
@@ -0,0 +1,34 @@
+#ifndef LOCATION_OPENLOCATIONCODE_CODEAREA_H_
+#define LOCATION_OPENLOCATIONCODE_CODEAREA_H_
+
+#include <cstdlib>
+
+namespace openlocationcode {
+
+struct LatLng {
+  double latitude;
+  double longitude;
+};
+
+class CodeArea {
+ public:
+  CodeArea(double latitude_lo, double longitude_lo, double latitude_hi,
+           double longitude_hi, size_t code_length);
+  double GetLatitudeLo() const;
+  double GetLongitudeLo() const;
+  double GetLatitudeHi() const;
+  double GetLongitudeHi() const;
+  size_t GetCodeLength() const;
+  LatLng GetCenter() const;
+
+ private:
+  double latitude_lo_;
+  double longitude_lo_;
+  double latitude_hi_;
+  double longitude_hi_;
+  size_t code_length_;
+};
+
+} // namespace openlocationcode
+
+#endif  // LOCATION_OPENLOCATIONCODE_CODEAREA_H_
\ No newline at end of file
diff --git a/3party/open-location-code/openlocationcode.cc b/3party/open-location-code/openlocationcode.cc
new file mode 100644
index 0000000000..9615a540f7
--- /dev/null
+++ b/3party/open-location-code/openlocationcode.cc
@@ -0,0 +1,471 @@
+#include "openlocationcode.h"
+
+#include <ctype.h>
+#include <float.h>
+#include <algorithm>
+#include <cmath>
+
+#include "codearea.h"
+
+namespace openlocationcode {
+namespace internal {
+const char kSeparator = '+';
+const size_t kSeparatorPosition = 8;
+const size_t kMaximumDigitCount = 32;
+const char kPaddingCharacter = '0';
+const char kAlphabet[] = "23456789CFGHJMPQRVWX";
+const size_t kEncodingBase = 20;
+const size_t kPairCodeLength = 10;
+const size_t kGridColumns = 4;
+const size_t kGridRows = kEncodingBase / kGridColumns;
+const double kMinShortenDegrees = 0.05;
+// Work out the encoding base exponent necessary to represent 360 degrees.
+const size_t kInitialExponent = floor(log(360) / log(kEncodingBase));
+// Work out the enclosing resolution (in degrees) for the grid algorithm.
+const double kGridSizeDegrees =
+    1 / pow(kEncodingBase, kPairCodeLength / 2 - (kInitialExponent + 1));
+
+// Latitude bounds are -kLatitudeMaxDegrees degrees and +kLatitudeMaxDegrees
+// degrees which we transpose to 0 and 180 degrees.
+const double kLatitudeMaxDegrees = 90;
+// Longitude bounds are -kLongitudeMaxDegrees degrees and +kLongitudeMaxDegrees
+// degrees which we transpose to 0 and 360.
+const double kLongitudeMaxDegrees = 180;
+}  // namespace internal
+
+namespace {
+
+// Raises a number to an exponent, handling negative exponents.
+double pow_neg(double base, double exponent) {
+  if (exponent == 0) {
+    return 1;
+  } else if (exponent > 0) {
+    return pow(base, exponent);
+  }
+  return 1 / pow(base, fabs(exponent));
+}
+
+// Compute the latitude precision value for a given code length. Lengths <= 10
+// have the same precision for latitude and longitude, but lengths > 10 have
+// different precisions due to the grid method having fewer columns than rows.
+double compute_precision_for_length(int code_length) {
+  if (code_length <= 10) {
+    return pow_neg(internal::kEncodingBase, floor((code_length / -2) + 2));
+  }
+  return pow_neg(internal::kEncodingBase, -3) / pow(5, code_length - 10);
+}
+
+// Finds the position of a char in the encoding alphabet.
+int get_alphabet_position(char c) {
+  const char* end = internal::kAlphabet + internal::kEncodingBase;
+  const char* match = std::find(internal::kAlphabet, end, c);
+  return (end == match)? -1 : (match - internal::kAlphabet);
+}
+
+// Normalize a longitude into the range -180 to 180, not including 180.
+double normalize_longitude(double longitude_degrees) {
+  while (longitude_degrees < -internal::kLongitudeMaxDegrees) {
+    longitude_degrees = longitude_degrees + 360;
+  }
+  while (longitude_degrees >= internal::kLongitudeMaxDegrees) {
+    longitude_degrees = longitude_degrees - 360;
+  }
+  return longitude_degrees;
+}
+
+// Adjusts 90 degree latitude to be lower so that a legal OLC code can be
+// generated.
+double adjust_latitude(double latitude_degrees, size_t code_length) {
+  latitude_degrees = std::min(90.0, std::max(-90.0, latitude_degrees));
+
+  if (latitude_degrees < internal::kLatitudeMaxDegrees) {
+    return latitude_degrees;
+  }
+  // Subtract half the code precision to get the latitude into the code
+  // area.
+  double precision = compute_precision_for_length(code_length);
+  return latitude_degrees - precision / 2;
+}
+
+
+// Encodes positive range lat,lng into a sequence of OLC lat/lng pairs.
+// This uses pairs of characters (latitude and longitude in that order) to
+// represent each step in a 20x20 grid. Each code, therefore, has 1/400th
+// the area of the previous code.
+std::string EncodePairs(double lat, double lng, size_t code_length) {
+  std::string code;
+  code.reserve(code_length + 1);
+  // Provides the value of digits in this place in decimal degrees.
+  double resolution_degrees = pow(
+      internal::kEncodingBase, internal::kInitialExponent);
+  // Add two digits on each pass.
+  for (size_t digit_count = 0; digit_count < code_length;
+      digit_count+=2, resolution_degrees/=internal::kEncodingBase) {
+    // Do the latitude - gets the digit for this place and subtracts that for
+    // the next digit.
+    size_t digit_value = floor(lat / resolution_degrees);
+    lat -= digit_value * resolution_degrees;
+    code += internal::kAlphabet[digit_value];
+    // And do the longitude - gets the digit for this place and subtracts that
+    // for the next digit.
+    digit_value = floor(lng / resolution_degrees);
+    lng -= digit_value * resolution_degrees;
+    code += internal::kAlphabet[digit_value];
+    // Should we add a separator here?
+    if (code.size() == internal::kSeparatorPosition &&
+        code.size() < code_length) {
+      code += internal::kSeparator;
+    }
+  }
+  while (code.size() < internal::kSeparatorPosition) {
+    code += internal::kPaddingCharacter;
+  }
+  if (code.size() == internal::kSeparatorPosition) {
+    code += internal::kSeparator;
+  }
+  return code;
+}
+
+
+// Encodes a location using the grid refinement method into an OLC string.
+// The grid refinement method divides the area into a grid of 4x5, and uses a
+// single character to refine the area. The grid squares use the OLC characters
+// in order to number the squares as follows:
+//   R V W X
+//   J M P Q
+//   C F G H
+//   6 7 8 9
+//   2 3 4 5
+// This allows default accuracy OLC codes to be refined with just a single
+// character.
+std::string EncodeGrid(double lat, double lng, size_t code_length) {
+  std::string code;
+  code.reserve(code_length + 1);
+  double lat_grid_size = internal::kGridSizeDegrees;
+  double lng_grid_size = internal::kGridSizeDegrees;
+  // To avoid problems with floating point, get rid of the degrees.
+  lat = fmod(lat, 1);
+  lng = fmod(lng, 1);
+  lat = fmod(lat, lat_grid_size);
+  lng = fmod(lng, lng_grid_size);
+  for (size_t i = 0; i < code_length; i++) {
+    // The following clause should never execute because of maximum code length
+    // enforcement in other functions, but is here to prevent division-by-zero
+    // crash from underflow.
+    if (lat_grid_size / internal::kGridRows <= DBL_MIN ||
+        lng_grid_size / internal::kGridColumns <= DBL_MIN) {
+      continue;
+    }
+    // Work out the row and column.
+    size_t row = floor(lat / (lat_grid_size / internal::kGridRows));
+    size_t col = floor(lng / (lng_grid_size / internal::kGridColumns));
+    lat_grid_size /= internal::kGridRows;
+    lng_grid_size /= internal::kGridColumns;
+    lat -= row * lat_grid_size;
+    lng -= col * lng_grid_size;
+    code += internal::kAlphabet[row * internal::kGridColumns + col];
+  }
+  return code;
+}
+
+}  // anonymous namespace
+
+std::string Encode(const LatLng &location, size_t code_length) {
+  // Limit the maximum number of digits in the code.
+  code_length = std::min(code_length, internal::kMaximumDigitCount);
+  // Adjust latitude and longitude so they fall into positive ranges.
+  double latitude = adjust_latitude(location.latitude, code_length) +
+                    internal::kLatitudeMaxDegrees;
+  double longitude =
+      normalize_longitude(location.longitude) + internal::kLongitudeMaxDegrees;
+  std::string code = EncodePairs(
+      latitude, longitude, std::min(code_length, internal::kPairCodeLength));
+  // If the requested length indicates we want grid refined codes.
+  if (code_length > internal::kPairCodeLength) {
+    code += EncodeGrid(latitude, longitude,
+        code_length - internal::kPairCodeLength);
+  }
+  return code;
+}
+
+std::string Encode(const LatLng &location) {
+  return Encode(location, internal::kPairCodeLength);
+}
+
+CodeArea Decode(const std::string &code) {
+  // Make a copy that doesn't have the separator and stops at the first padding
+  // character.
+  std::string clean_code(code);
+  clean_code.erase(
+      std::remove(clean_code.begin(), clean_code.end(), internal::kSeparator),
+      clean_code.end());
+  if (clean_code.find(internal::kPaddingCharacter)) {
+    clean_code = clean_code.substr(0,
+        clean_code.find(internal::kPaddingCharacter));
+  }
+  double resolution_degrees = internal::kEncodingBase;
+  double latitude = 0.0;
+  double longitude = 0.0;
+  double latitude_high = 0.0;
+  double longitude_high = 0.0;
+  // Up to the first 10 characters are encoded in pairs. Subsequent characters
+  // represent grid squares.
+  for (size_t i = 0; i < std::min(clean_code.size(), internal::kPairCodeLength);
+       i += 2, resolution_degrees /= internal::kEncodingBase) {
+    // The character at i represents latitude. Retrieve it and convert to
+    // degrees (positive range).
+    double value = get_alphabet_position(toupper(clean_code[i]));
+    value *= resolution_degrees;
+    latitude += value;
+    latitude_high = latitude + resolution_degrees;
+    // Checks if there are no more characters.
+    if (i == std::min(clean_code.size(), internal::kPairCodeLength)) {
+      break;
+    }
+    // The character at i + 1 represents longitude. Retrieve it and convert to
+    // degrees (positive range).
+    value = get_alphabet_position(toupper(clean_code[i + 1]));
+    value *= resolution_degrees;
+    longitude += value;
+    longitude_high = longitude + resolution_degrees;
+  }
+  if (clean_code.size() > internal::kPairCodeLength) {
+    // Now do any grid square characters.
+    // Adjust the resolution back a step because we need the resolution of the
+    // entire grid, not a single grid square.
+    resolution_degrees *= internal::kEncodingBase;
+    // With a grid, the latitude and longitude resolutions are no longer equal.
+    double latitude_resolution = resolution_degrees;
+    double longitude_resolution = resolution_degrees;
+    // Decode only up to the maximum digit count.
+    for (size_t i = internal::kPairCodeLength;
+         i < std::min(internal::kMaximumDigitCount, clean_code.size()); i++) {
+      // Get the value of the character at i and convert it to the degree value.
+      size_t value = get_alphabet_position(toupper(clean_code[i]));
+      size_t row = value / internal::kGridColumns;
+      size_t col = value % internal::kGridColumns;
+      // Lat and lng grid sizes shouldn't underflow due to maximum code length
+      // enforcement, but a hypothetical underflow won't cause fatal errors
+      // here.
+      latitude_resolution /= internal::kGridRows;
+      longitude_resolution /= internal::kGridColumns;
+      latitude += row * latitude_resolution;
+      longitude += col * longitude_resolution;
+      latitude_high = latitude + latitude_resolution;
+      longitude_high = longitude + longitude_resolution;
+    }
+  }
+  return CodeArea(latitude - internal::kLatitudeMaxDegrees,
+                  longitude - internal::kLongitudeMaxDegrees,
+                  latitude_high - internal::kLatitudeMaxDegrees,
+                  longitude_high - internal::kLongitudeMaxDegrees,
+                  CodeLength(code));
+}
+
+std::string Shorten(const std::string &code, const LatLng &reference_location) {
+  if (!IsFull(code)) {
+    return code;
+  }
+  if (code.find(internal::kPaddingCharacter) != std::string::npos) {
+    return code;
+  }
+  CodeArea code_area = Decode(code);
+  LatLng center = code_area.GetCenter();
+  // Ensure that latitude and longitude are valid.
+  double latitude =
+      adjust_latitude(reference_location.latitude, CodeLength(code));
+  double longitude = normalize_longitude(reference_location.longitude);
+  // How close are the latitude and longitude to the code center.
+  double range = std::max(fabs(center.latitude - latitude),
+                          fabs(center.longitude - longitude));
+  std::string code_copy(code);
+  const double safety_factor = 0.3;
+  const int removal_lengths[3] = {8, 6, 4};
+  for (int removal_length : removal_lengths) {
+    // Check if we're close enough to shorten. The range must be less than 1/2
+    // the resolution to shorten at all, and we want to allow some safety, so
+    // use 0.3 instead of 0.5 as a multiplier.
+    double area_edge =
+        compute_precision_for_length(removal_length) * safety_factor;
+    if (range < area_edge) {
+      code_copy = code_copy.substr(removal_length);
+      break;
+    }
+  }
+  return code_copy;
+}
+
+std::string RecoverNearest(const std::string &short_code,
+                           const LatLng &reference_location) {
+  if (!IsShort(short_code)) {
+    return short_code;
+  }
+  // Ensure that latitude and longitude are valid.
+  double latitude =
+      adjust_latitude(reference_location.latitude, CodeLength(short_code));
+  double longitude = normalize_longitude(reference_location.longitude);
+  // Compute the number of digits we need to recover.
+  size_t padding_length = internal::kSeparatorPosition -
+      short_code.find(internal::kSeparator);
+  // The resolution (height and width) of the padded area in degrees.
+  double resolution = pow_neg(
+      internal::kEncodingBase, 2.0 - (padding_length / 2.0));
+  // Distance from the center to an edge (in degrees).
+  double half_res = resolution / 2.0;
+  // Use the reference location to pad the supplied short code and decode it.
+  LatLng latlng = {latitude, longitude};
+  std::string padding_code = Encode(latlng);
+  CodeArea code_rect =
+      Decode(std::string(padding_code.substr(0, padding_length)) +
+             std::string(short_code));
+  // How many degrees latitude is the code from the reference? If it is more
+  // than half the resolution, we need to move it north or south but keep it
+  // within -90 to 90 degrees.
+  double center_lat = code_rect.GetCenter().latitude;
+  double center_lng = code_rect.GetCenter().longitude;
+  if (latitude + half_res < center_lat && center_lat - resolution > -internal::kLatitudeMaxDegrees) {
+    // If the proposed code is more than half a cell north of the reference location,
+    // it's too far, and the best match will be one cell south.
+    center_lat -= resolution;
+  } else if (latitude - half_res > center_lat && center_lat + resolution < internal::kLatitudeMaxDegrees) {
+    // If the proposed code is more than half a cell south of the reference location,
+    // it's too far, and the best match will be one cell north.
+    center_lat += resolution;
+  }
+  // How many degrees longitude is the code from the reference?
+  if (longitude + half_res < center_lng) {
+    center_lng -= resolution;
+  } else if (longitude - half_res > center_lng) {
+    center_lng += resolution;
+  }
+  LatLng center_latlng = {center_lat, center_lng};
+  return Encode(center_latlng, CodeLength(short_code) + padding_length);
+}
+
+bool IsValid(const std::string &code) {
+  if (code.empty()) {
+    return false;
+  }
+  size_t separatorPos = code.find(internal::kSeparator);
+  // The separator is required.
+  if (separatorPos == std::string::npos) {
+    return false;
+  }
+  // There must only be one separator.
+  if (code.find_first_of(internal::kSeparator) !=
+      code.find_last_of(internal::kSeparator)) {
+    return false;
+  }
+  // Is the separator the only character?
+  if (code.length() == 1) {
+    return false;
+  }
+  // Is the separator in an illegal position?
+  if (separatorPos > internal::kSeparatorPosition || separatorPos % 2 == 1) {
+    return false;
+  }
+  // We can have an even number of padding characters before the separator,
+  // but then it must be the final character.
+  std::size_t paddingStart = code.find_first_of(internal::kPaddingCharacter);
+  if (paddingStart != std::string::npos) {
+    // The first padding character needs to be in an odd position.
+    if (paddingStart == 0 || paddingStart % 2) {
+      return false;
+    }
+    // Padded codes must not have anything after the separator
+    if (code.size() > separatorPos + 1) {
+      return false;
+    }
+    // Get from the first padding character to the separator
+    std::string paddingSection =
+        code.substr(paddingStart, internal::kSeparatorPosition - paddingStart);
+    paddingSection.erase(
+        std::remove(paddingSection.begin(), paddingSection.end(),
+                    internal::kPaddingCharacter),
+        paddingSection.end());
+    // After removing padding characters, we mustn't have anything left.
+    if (!paddingSection.empty()) {
+      return false;
+    }
+  }
+  // If there are characters after the separator, make sure there isn't just
+  // one of them (not legal).
+  if (code.size() - code.find(internal::kSeparator) - 1 == 1) {
+    return false;
+  }
+  // Make sure the code does not have too many digits in total.
+  if (code.size() - 1 > internal::kMaximumDigitCount) {
+    return false;
+  }
+  // Make sure the code does not have too many digits after the separator.
+  // The number of digits is the length of the code, minus the position of the
+  // separator, minus one because the separator position is zero indexed.
+  if (code.size() - code.find(internal::kSeparator) - 1 >
+      internal::kMaximumDigitCount - internal::kSeparatorPosition) {
+    return false;
+  }
+  // Are there any invalid characters?
+  for (char c : code) {
+    if (c != internal::kSeparator && c != internal::kPaddingCharacter &&
+        std::find(std::begin(internal::kAlphabet),
+                  std::end(internal::kAlphabet),
+                  (char)toupper(c)) == std::end(internal::kAlphabet)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+bool IsShort(const std::string &code) {
+  // Check it's valid.
+  if (!IsValid(code)) {
+    return false;
+  }
+  // If there are less characters than expected before the SEPARATOR.
+  if (code.find(internal::kSeparator) < internal::kSeparatorPosition) {
+    return true;
+  }
+  return false;
+}
+
+bool IsFull(const std::string &code) {
+  if (!IsValid(code)) {
+    return false;
+  }
+  // If it's short, it's not full.
+  if (IsShort(code)) {
+    return false;
+  }
+  // Work out what the first latitude character indicates for latitude.
+  size_t firstLatValue = get_alphabet_position(toupper(code.at(0)));
+  firstLatValue *= internal::kEncodingBase;
+  if (firstLatValue >= internal::kLatitudeMaxDegrees * 2) {
+    // The code would decode to a latitude of >= 90 degrees.
+    return false;
+  }
+  if (code.size() > 1) {
+    // Work out what the first longitude character indicates for longitude.
+    size_t firstLngValue = get_alphabet_position(toupper(code.at(1)));
+    firstLngValue *= internal::kEncodingBase;
+    if (firstLngValue >= internal::kLongitudeMaxDegrees * 2) {
+      // The code would decode to a longitude of >= 180 degrees.
+      return false;
+    }
+  }
+  return true;
+}
+
+size_t CodeLength(const std::string &code) {
+  // Remove the separator and any padding characters.
+  std::string clean_code(code);
+  clean_code.erase(
+      std::remove(clean_code.begin(), clean_code.end(), internal::kSeparator),
+      clean_code.end());
+  if (clean_code.find(internal::kPaddingCharacter)) {
+    clean_code = clean_code.substr(
+        0, clean_code.find(internal::kPaddingCharacter));
+  }
+  return clean_code.size();
+}
+
+}  // namespace openlocationcode
diff --git a/3party/open-location-code/openlocationcode.h b/3party/open-location-code/openlocationcode.h
new file mode 100644
index 0000000000..057db440b0
--- /dev/null
+++ b/3party/open-location-code/openlocationcode.h
@@ -0,0 +1,113 @@
+// The OpenLocationCode namespace provides a way of encoding between geographic
+// coordinates and character strings that use a disambiguated character set.
+// The aim is to provide a more convenient way for humans to handle geographic
+// coordinates than latitude and longitude pairs.
+//
+// The codes can be easily read and remembered, and truncating codes converts
+// them from a point to an area, meaning that where extreme accuracy is not
+// required the codes can be shortened.
+#ifndef LOCATION_OPENLOCATIONCODE_OPENLOCATIONCODE_H_
+#define LOCATION_OPENLOCATIONCODE_OPENLOCATIONCODE_H_
+
+#include <string>
+
+#include "codearea.h"
+
+namespace openlocationcode {
+
+// Encodes a pair of coordinates and return an Open Location Code representing a
+// rectangle that encloses the coordinates. The accuracy of the code is
+// controlled by the code length.
+//
+// Returns an Open Location Code with code_length significant digits. The string
+// returned may be one character longer if it includes a separator character
+// for formatting.
+std::string Encode(const LatLng &location, size_t code_length);
+
+// Encodes a pair of coordinates and return an Open Location Code representing a
+// rectangle that encloses the coordinates. The accuracy of the code is
+// sufficient to represent a building such as a house, and is approximately
+// 13x13 meters at Earth's equator.
+std::string Encode(const LatLng &location);
+
+// Decodes an Open Location Code and returns a rectangle that describes the area
+// represented by the code.
+CodeArea Decode(const std::string &code);
+
+// Removes characters from the start of an OLC code.
+// This uses a reference location to determine how many initial characters
+// can be removed from the OLC code. The number of characters that can be
+// removed depends on the distance between the code center and the reference
+// location.
+//
+// The reference location must be within a safety factor of the maximum range.
+// This ensures that the shortened code will be able to be recovered using
+// slightly different locations.
+//
+// If the code isn't a valid full code or is padded, it cannot be shortened and
+// the code is returned as-is.
+std::string Shorten(const std::string &code, const LatLng &reference_location);
+
+// Recovers the nearest matching code to a specified location.
+// Given a short Open Location Code of between four and seven characters,
+// this recovers the nearest matching full code to the specified location.
+//
+// If the code isn't a valid short code, it cannot be recovered and the code
+// is returned as-is.
+std::string RecoverNearest(const std::string &short_code,
+                           const LatLng &reference_location);
+
+// Returns the number of valid Open Location Code characters in a string. This
+// excludes invalid characters and separators.
+size_t CodeLength(const std::string &code);
+
+// Determines if a code is valid and can be decoded.
+// The empty string is a valid code, but whitespace included in a code is not
+// valid.
+bool IsValid(const std::string &code);
+
+// Determines if a code is a valid short code.
+bool IsShort(const std::string &code);
+
+// Determines if a code is a valid full Open Location Code.
+//
+// Not all possible combinations of Open Location Code characters decode to
+// valid latitude and longitude values. This checks that a code is valid
+// and also that the latitude and longitude values are legal. If the prefix
+// character is present, it must be the first character. If the separator
+// character is present, it must be after four characters.
+bool IsFull(const std::string &code);
+
+namespace internal {
+// The separator character is used to identify strings as OLC codes.
+extern const char kSeparator;
+// Provides the position of the separator.
+extern const size_t kSeparatorPosition;
+// Defines the maximum number of digits in a code (excluding separator). Codes
+// with this length have a precision of less than 1e-10 cm at the equator.
+extern const size_t kMaximumDigitCount;
+// Padding is used when less precise codes are desired.
+extern const char kPaddingCharacter;
+// The alphabet of the codes.
+extern const char kAlphabet[];
+// The number base used for the encoding.
+extern const size_t kEncodingBase;
+// How many characters use the pair algorithm.
+extern const size_t kPairCodeLength;
+// Number of columns in the grid refinement method.
+extern const size_t kGridColumns;
+// Number of rows in the grid refinement method.
+extern const size_t kGridRows;
+// Defines the minimum pair resolution (in degrees) to remove when shortening a
+// code.
+extern const double kMinShortenDegrees;
+// Gives the exponent used for the first pair.
+extern const size_t kInitialExponent;
+// Size of the initial grid in degrees. This is the size of the area represented
+// by a 10 character code, and is kEncodingBase ^ (2 - kPairCodeLength / 2).
+extern const double kGridSizeDegrees;
+}  // namespace internal
+
+}  // namespace openlocationcode
+
+#endif  // LOCATION_OPENLOCATIONCODE_OPENLOCATIONCODE_H_