// Copyright 2012 Google Inc. All Rights Reserved.

//

// 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.

//

// Author: ericv@google.com (Eric Veach)

#include "s2/s2shape_index.h"

#include <cstdint>

#include <limits>

#include "absl/base/optimization.h"

#include "absl/log/absl_check.h"

#include "s2/util/coding/coder.h"

#include "s2/util/coding/varint.h"

#include "s2/util/gtl/compact_array.h"

bool S2ClippedShape::ContainsEdge(int id) const {

  // Linear search is fast because the number of edges per shape is typically

  // very small (less than 10).

  for (int e = 0; e < num_edges(); ++e) {

    if (edge(e) == id) return true;

  }

  return false;

}

S2ShapeIndexCell::~S2ShapeIndexCell() {

  // Free memory for all shapes owned by this cell.

  for (S2ClippedShape& s : shapes_)

    s.Destruct();

  shapes_.clear();

}

const S2ClippedShape*

S2ShapeIndexCell::find_clipped(int shape_id) const {

  // Linear search is fine because the number of shapes per cell is typically

  // very small (most often 1), and is large only for pathological inputs

  // (e.g. very deeply nested loops).

  for (const auto& s : shapes_) {

    if (s.shape_id() == shape_id) return &s;

  }

  return nullptr;

}

// Allocate room for "n" additional clipped shapes in the cell, and return a

// pointer to the first new clipped shape.  Expects that all new clipped

// shapes will have a larger shape id than any current shape, and that shapes

// will be added in increasing shape id order.

S2ClippedShape* S2ShapeIndexCell::add_shapes(int n) {

  if (n > 0) {

    int size = shapes_.size();

    shapes_.resize(size + n);

    return &shapes_[size];

  }

  return nullptr;

}

void S2ShapeIndexCell::Encode(int num_shape_ids, Encoder* encoder) const {

  // The encoding is designed to be especially compact in certain common

  // situations:

  //

  // 1. The S2ShapeIndex contains exactly one shape.

  //

  // 2. The S2ShapeIndex contains more than one shape, but a particular index

  //    cell contains only one shape (num_clipped == 1).

  //

  // 3. The edge ids for a given shape in a cell form a contiguous range.

  //

  // The details were optimized by constructing an S2ShapeIndex for each

  // feature in Google's geographic repository and measuring their total

  // encoded size.  The MutableS2ShapeIndex encoding (of which this function

  // is just one part) uses an average of 1.88 bytes per vertex for features

  // consisting of polygons or polylines.

  //

  // Note that this code does not bother handling num_shapes >= 2**28 or

  // num_edges >= 2**29.  This could be fixed using varint64 in a few more

  // places, but if a single cell contains this many shapes or edges then we

  // have bigger problems than just the encoding format :)

  if (num_shape_ids == 1) {

    // If the entire S2ShapeIndex contains just one shape, then we don't need

    // to encode any shape ids.  This is a very important and common case.

    ABSL_DCHECK_EQ(num_clipped(), 1);  // Index invariant: no empty cells.

    const S2ClippedShape& clipped = this->clipped(0);

    ABSL_DCHECK_EQ(clipped.shape_id(), 0);

    int n = clipped.num_edges();

    encoder->Ensure(Varint::kMax64 + n * Varint::kMax32);

    if (n >= 2 && n <= 17 && clipped.edge(n - 1) - clipped.edge(0) == n - 1) {

      // The cell contains a contiguous range of edges (*most common case*).

      // If the starting edge id is small then we can encode the cell in one

      // byte.  (The n == 0 and n == 1 cases are encoded compactly below.)

      // This encoding uses a 1-bit tag because it is by far the most common.

      //

      // Encoding: bit 0: 0

      //           bit 1: contains_center

      //           bits 2-5: (num_edges - 2)

      //           bits 6+: edge_id

      encoder->put_varint64(static_cast<uint64_t>(clipped.edge(0)) << 6 |

                            (n - 2) << 2 | clipped.contains_center() << 1 | 0);

    } else if (n == 1) {

      // The cell contains only one edge.  For edge ids up to 15, we can

      // encode the cell in a single byte.

      //

      // Encoding: bits 0-1: 1

      //           bit 2: contains_center

      //           bits 3+: edge_id

      encoder->put_varint64(static_cast<uint64_t>(clipped.edge(0)) << 3 |

                            clipped.contains_center() << 2 | 1);

    } else {

      // General case (including n == 0, which is encoded compactly here).

      //

      // Encoding: bits 0-1: 3

      //           bit 2: contains_center

      //           bits 3+: num_edges

      encoder->put_varint64(static_cast<uint64_t>(n) << 3 |

                            clipped.contains_center() << 2 | 3);

      EncodeEdges(clipped, encoder);

    }

  } else {

    if (num_clipped() > 1) {

      // The cell contains more than one shape.  The tag for this encoding

      // must be distinguishable from the cases encoded below.  We can afford

      // to use a 3-bit tag because num_clipped is generally small.

      encoder->Ensure(Varint::kMax32);

      encoder->put_varint32((num_clipped() << 3) | 3);

    }

    // The shape ids are delta-encoded.

    int shape_id_base = 0;

    for (int j = 0; j < num_clipped(); ++j) {

      const S2ClippedShape& clipped = this->clipped(j);

      ABSL_DCHECK_GE(clipped.shape_id(), shape_id_base);

      int shape_delta = clipped.shape_id() - shape_id_base;

      shape_id_base = clipped.shape_id() + 1;

      // Like the code above except that we also need to encode shape_id(s).

      // Because of this some choices are slightly different.

      int n = clipped.num_edges();

      encoder->Ensure((n + 2) * Varint::kMax32);

      if (n >= 1 && n <= 16 && clipped.edge(n - 1) - clipped.edge(0) == n - 1) {

        // The clipped shape has a contiguous range of up to 16 edges.  This

        // encoding uses a 1-bit tag because it is by far the most common.

        //

        // Encoding: bit 0: 0

        //           bit 1: contains_center

        //           bits 2+: edge_id

        // Next value: bits 0-3: (num_edges - 1)

        //             bits 4+: shape_delta

        encoder->put_varint32(clipped.edge(0) << 2 |

                              clipped.contains_center() << 1 | 0);

        encoder->put_varint32(shape_delta << 4 | (n - 1));

      } else if (n == 0) {

        // Special encoding for clipped shapes with no edges.  Such shapes are

        // common in polygon interiors.  This encoding uses a 3-bit tag in

        // order to leave more bits available for the other encodings.

        //

        // NOTE(ericv): When num_clipped > 1, this tag could be 2 bits

        // (because the tag used to indicate num_clipped > 1 can't appear).

        // Alternatively, that tag can be considered reserved for future use.

        //

        // Encoding: bits 0-2: 7

        //           bit 3: contains_center

        //           bits 4+: shape_delta

        encoder->put_varint32(shape_delta << 4 |

                              clipped.contains_center() << 3 | 7);

      } else {

        // General case.  This encoding uses a 2-bit tag, and the first value

        // typically is encoded into one byte.

        //

        // Encoding: bits 0-1: 1

        //           bit 2: contains_center

        //           bits 3+: (num_edges - 1)

        // Next value: shape_delta

        encoder->put_varint32((n - 1) << 3 |

                              clipped.contains_center() << 2 | 1);

        encoder->put_varint32(shape_delta);

        EncodeEdges(clipped, encoder);

      }

    }

  }

}

bool S2ShapeIndexCell::Decode(int num_shape_ids, Decoder* decoder) {

  // This function inverts the encodings documented above.

  if (num_shape_ids == 1) {

    // Entire S2ShapeIndex contains only one shape.

    S2ClippedShape* clipped = add_shapes(1);

    uint64_t header = 0;

    if (!decoder->get_varint64(&header)) return false;

    if ((header & 1) == 0) {

      // The cell contains a contiguous range of edges.

      int num_edges = ((header >> 2) & 15) + 2;

      clipped->Init(0 /*shape_id*/, num_edges);

      clipped->set_contains_center((header & 2) != 0);

      // Edge ids are int32, but we use int64 to guard against overflow.

      const int64_t edge_id = header >> 6;

      if (ABSL_PREDICT_FALSE(edge_id + num_edges >

                             std::numeric_limits<int32_t>::max())) {

        return false;

      }

      for (int i = 0; i < num_edges; ++i) {

        // Range check for `edge_id + i` is performed above.

        clipped->set_edge(i, static_cast<int>(edge_id + i));

      }

      return true;

    }

    if ((header & 2) == 0) {

      // The cell contains a single edge.

      clipped->Init(0 /*shape_id*/, 1 /*num_edges*/);

      clipped->set_contains_center((header & 4) != 0);

      const int64_t edge_id = header >> 3;

      if (ABSL_PREDICT_FALSE(edge_id > std::numeric_limits<int32_t>::max())) {

        return false;

      }

      clipped->set_edge(0, edge_id);

      return true;

    }

    // The cell contains some other combination of edges.

    int num_edges = header >> 3;

    clipped->Init(0 /*shape_id*/, num_edges);

    clipped->set_contains_center((header & 4) != 0);

    return DecodeEdges(num_edges, clipped, decoder);

  }

  // S2ShapeIndex contains more than one shape.

  uint32_t header = 0;

  if (!decoder->get_varint32(&header)) return false;

  int num_clipped = 1;

  if ((header & 7) == 3) {

    // This cell contains more than one shape.

    num_clipped = header >> 3;

    if (!decoder->get_varint32(&header)) return false;

  }

  int64_t shape_id = 0;  // Shape id is 32-bit, but we guard against overflow.

  S2ClippedShape* clipped = add_shapes(num_clipped);

  for (int j = 0; j < num_clipped; ++j, ++clipped, ++shape_id) {

    // Ensure we don't overflow a 32 bit shape id.

    if (shape_id >= std::numeric_limits<int>::max()) {

      return false;

    }

    if (j > 0 && !decoder->get_varint32(&header)) return false;

    if ((header & 1) == 0) {

      // The clipped shape contains a contiguous range of edges.

      uint32_t shape_id_count = 0;

      if (!decoder->get_varint32(&shape_id_count)) return false;

      shape_id += shape_id_count >> 4;

      int num_edges = (shape_id_count & 15) + 1;

      clipped->Init(shape_id, num_edges);

      clipped->set_contains_center((header & 2) != 0);

      const int64_t edge_id = header >> 2;

      if (ABSL_PREDICT_FALSE(edge_id + num_edges >

                             std::numeric_limits<int32_t>::max())) {

        return false;

      }

      for (int i = 0; i < num_edges; ++i) {

        clipped->set_edge(i, static_cast<int>(edge_id + i));

      }

    } else if ((header & 7) == 7) {

      // The clipped shape has no edges.

      shape_id += header >> 4;

      clipped->Init(shape_id, 0);

      clipped->set_contains_center((header & 8) != 0);

    } else {

      // The clipped shape contains some other combination of edges.

      if ((header & 3) != 1) {

        return false;

      }

      uint32_t shape_delta = 0;

      if (!decoder->get_varint32(&shape_delta)) return false;

      shape_id += shape_delta;

      int num_edges = (header >> 3) + 1;

      clipped->Init(shape_id, num_edges);

      clipped->set_contains_center((header & 4) != 0);

      if (!DecodeEdges(num_edges, clipped, decoder)) return false;

    }

  }

  return true;

}

inline void S2ShapeIndexCell::EncodeEdges(const S2ClippedShape& clipped,

                                          Encoder* encoder) {

  // Each entry is an (edge_id, count) pair representing a contiguous range of

  // edges.  The edge ids are delta-encoded such that 0 represents the minimum

  // valid next edge id.

  //

  // Encoding: if bits 0-2 < 7: encodes (count - 1)

  //            - bits 3+: edge delta

  //           if bits 0-2 == 7:

  //            - bits 3+ encode (count - 8)

  //            - Next value is edge delta

  //

  // No count is encoded for the last edge (saving 3 bits).

  int edge_id_base = 0;

  int num_edges = clipped.num_edges();

  for (int i = 0; i < num_edges; ++i) {

    int edge_id = clipped.edge(i);

    ABSL_DCHECK_GE(edge_id, edge_id_base);

    int delta = edge_id - edge_id_base;

    if (i + 1 == num_edges) {

      // This is the last edge; no need to encode an edge count.

      encoder->put_varint32(delta);

    } else {

      // Count the edges in this contiguous range.

      int count = 1;

      for (; i + 1 < num_edges && clipped.edge(i + 1) == edge_id + count; ++i) {

        ++count;

      }

      if (count < 8) {

        // Count is encoded in low 3 bits of delta.

        encoder->put_varint32(delta << 3 | (count - 1));

      } else {

        // Count and delta are encoded separately.

        encoder->put_varint32((count - 8) << 3 | 7);

        encoder->put_varint32(delta);

      }

      edge_id_base = edge_id + count;

    }

  }

}

inline bool S2ShapeIndexCell::DecodeEdges(int num_edges,

                                          S2ClippedShape* clipped,

                                          Decoder* decoder) {

  // This function inverts the encodings documented above.

  int64_t edge_id = 0;  // Edge id is 32-bit, but we guard against overflow.

  for (int i = 0; i < num_edges; ) {

    uint32_t delta = 0;

    if (!decoder->get_varint32(&delta)) return false;

    if (i + 1 == num_edges) {

      // The last edge is encoded without an edge count.

      edge_id += delta;

      if (ABSL_PREDICT_FALSE(edge_id > std::numeric_limits<int32_t>::max())) {

        return false;

      }

      clipped->set_edge(i++, edge_id);

    } else {

      // Otherwise decode the count and edge delta.

      uint32_t count = (delta & 7) + 1;

      delta >>= 3;

      if (count == 8) {

        count = delta + 8;

        if (!decoder->get_varint32(&delta)) return false;

      }

      // Guard against overflowing edge memory for bad inputs.

      if (ABSL_PREDICT_FALSE(i + count > static_cast<uint32_t>(num_edges))) {

        return false;

      }

      edge_id += delta;

      // Guard against overflowing edge memory for bad inputs.

      if (ABSL_PREDICT_FALSE(edge_id + count >

                             std::numeric_limits<int32_t>::max())) {

        return false;

      }

      for (; count > 0; --count, ++i, ++edge_id) {

        clipped->set_edge(i, edge_id);

      }

    }

  }

  return true;

}