/* ***** BEGIN LICENSE BLOCK *****
 *
 * Copyright (C) 2015 The Android Open Source Project
 *
 * 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.
 *
 * ***** END LICENSE BLOCK ***** */

#include <unicode/uchar.h>

#include <algorithm>
#include <memory>

// HACK: for reading pattern file
#include <fcntl.h>

#include "base/compiler_specific.h"
#include "base/containers/span.h"
#include "third_party/blink/renderer/platform/text/hyphenation/hyphenator_aosp.h"

namespace android {

using blink::wtf_size_t;

static const uint16_t CHAR_SOFT_HYPHEN = 0x00AD;

// The following are structs that correspond to tables inside the hyb file
// format

struct AlphabetTable0 {
  uint32_t version;
  uint32_t min_codepoint;
  uint32_t max_codepoint;
  uint8_t data[1];  // actually flexible array, size is known at runtime
};

struct AlphabetTable1 {
  uint32_t version;
  uint32_t n_entries;
  uint32_t data[1];  // actually flexible array, size is known at runtime

  static uint32_t codepoint(uint32_t entry) { return entry >> 11; }
  static uint32_t value(uint32_t entry) { return entry & 0x7ff; }
};

struct Trie {
  uint32_t version;
  uint32_t char_mask;
  uint32_t link_shift;
  uint32_t link_mask;
  uint32_t pattern_shift;
  uint32_t n_entries;
  uint32_t data[1];  // actually flexible array, size is known at runtime
};

struct Pattern {
  uint32_t version;
  uint32_t n_entries;
  uint32_t pattern_offset;
  uint32_t pattern_size;
  uint32_t data[1];  // actually flexible array, size is known at runtime

  // accessors
  static uint32_t len(uint32_t entry) { return entry >> 26; }
  static uint32_t shift(uint32_t entry) { return (entry >> 20) & 0x3f; }
  const uint8_t* buf(uint32_t entry) const {
    // SAFETY: The Pattern struct is embedded in a binary hyb file blob, and
    // `pattern_offset + (entry & 0xfffff)` is a valid offset into that blob
    // as defined by the hyb file format.
    return UNSAFE_BUFFERS(reinterpret_cast<const uint8_t*>(this) +
                          pattern_offset + (entry & 0xfffff));
  }
};

struct Header {
  uint32_t magic;
  uint32_t version;
  uint32_t alphabet_offset;
  uint32_t trie_offset;
  uint32_t pattern_offset;
  uint32_t file_size;

  // accessors
  const uint8_t* bytes() const {
    return reinterpret_cast<const uint8_t*>(this);
  }
  // SAFETY: The Header struct is at the start of a binary hyb file blob.
  // The offset fields (alphabet_offset, trie_offset, pattern_offset) are
  // valid offsets into that blob as defined by the hyb file format.
  uint32_t alphabetVersion() const {
    return *reinterpret_cast<const uint32_t*>(
        UNSAFE_BUFFERS(bytes() + alphabet_offset));
  }
  const AlphabetTable0* alphabetTable0() const {
    return reinterpret_cast<const AlphabetTable0*>(
        UNSAFE_BUFFERS(bytes() + alphabet_offset));
  }
  const AlphabetTable1* alphabetTable1() const {
    return reinterpret_cast<const AlphabetTable1*>(
        UNSAFE_BUFFERS(bytes() + alphabet_offset));
  }
  const Trie* trieTable() const {
    return reinterpret_cast<const Trie*>(UNSAFE_BUFFERS(bytes() + trie_offset));
  }
  const Pattern* patternTable() const {
    return reinterpret_cast<const Pattern*>(
        UNSAFE_BUFFERS(bytes() + pattern_offset));
  }
};

Hyphenator* Hyphenator::loadBinary(const uint8_t* patternData) {
  Hyphenator* result = new Hyphenator;
  result->patternData = patternData;
  return result;
}

void Hyphenator::hyphenate(blink::Vector<uint8_t>* result,
                           base::span<const uint16_t> word) {
  const wtf_size_t len = static_cast<wtf_size_t>(word.size());
  result->clear();
  result->resize(len);
  auto result_span = base::span(*result);
  const wtf_size_t paddedLen = len + 2;  // start and stop code each count for 1
  if (patternData != nullptr && (int)len >= MIN_PREFIX + MIN_SUFFIX &&
      paddedLen <= MAX_HYPHENATED_SIZE) {
    uint16_t alpha_codes[MAX_HYPHENATED_SIZE];
    if (alphabetLookup(base::span(alpha_codes).first(paddedLen), word)) {
      hyphenateFromCodes(result_span, base::span(alpha_codes).first(paddedLen));
      return;
    }
    // TODO: try NFC normalization
    // TODO: handle non-BMP Unicode (requires remapping of offsets)
  }
  hyphenateSoft(result_span, word);
}

// If any soft hyphen is present in the word, use soft hyphens to decide
// hyphenation, as recommended in UAX #14 (Use of Soft Hyphen)
void Hyphenator::hyphenateSoft(base::span<uint8_t> result,
                               base::span<const uint16_t> word) {
  result[0] = 0;
  for (wtf_size_t i = 1; i < result.size(); i++) {
    result[i] = word[i - 1] == CHAR_SOFT_HYPHEN;
  }
}

bool Hyphenator::alphabetLookup(base::span<uint16_t> alpha_codes,
                                base::span<const uint16_t> word) {
  const Header* header = getHeader();
  const wtf_size_t len = static_cast<wtf_size_t>(word.size());
  // TODO: check header magic
  uint32_t alphabetVersion = header->alphabetVersion();
  if (alphabetVersion == 0) {
    const AlphabetTable0* alphabet = header->alphabetTable0();
    uint32_t min_codepoint = alphabet->min_codepoint;
    uint32_t max_codepoint = alphabet->max_codepoint;
    // SAFETY: `alphabet->data` is a flexible array with
    // `max_codepoint - min_codepoint` entries as defined by the hyb file
    // format.
    auto alphabet_data = UNSAFE_BUFFERS(
        base::span(alphabet->data, max_codepoint - min_codepoint));
    alpha_codes[0] = 0;  // word start
    for (wtf_size_t i = 0; i < len; i++) {
      uint16_t c = word[i];
      if (c < min_codepoint || c >= max_codepoint) {
        return false;
      }
      uint8_t code = alphabet_data[c - min_codepoint];
      if (code == 0) {
        return false;
      }
      alpha_codes[i + 1] = code;
    }
    alpha_codes[len + 1] = 0;  // word termination
    return true;
  } else if (alphabetVersion == 1) {
    const AlphabetTable1* alphabet = header->alphabetTable1();
    size_t n_entries = alphabet->n_entries;
    // SAFETY: `alphabet->data` is a flexible array with `n_entries` elements
    // as defined by the hyb file format.
    auto alphabet_data = UNSAFE_BUFFERS(base::span(alphabet->data, n_entries));
    alpha_codes[0] = 0;
    for (wtf_size_t i = 0; i < len; i++) {
      uint16_t c = word[i];
      auto it = std::ranges::lower_bound(alphabet_data, c << 11);
      if (it == alphabet_data.end()) {
        return false;
      }
      uint32_t entry = *it;
      if (AlphabetTable1::codepoint(entry) != c) {
        return false;
      }
      alpha_codes[i + 1] = AlphabetTable1::value(entry);
    }
    alpha_codes[len + 1] = 0;
    return true;
  }
  return false;
}

/**
 * Internal implementation, after conversion to codes. All case folding and
 * normalization has been done by now, and all characters have been found in the
 * alphabet.  Note: len here is the padded length including 0 codes at start and
 * end.
 **/
void Hyphenator::hyphenateFromCodes(base::span<uint8_t> result,
                                    base::span<const uint16_t> codes) {
  const wtf_size_t len = static_cast<wtf_size_t>(codes.size());
  const Header* header = getHeader();
  const Trie* trie = header->trieTable();
  const Pattern* pattern = header->patternTable();
  uint32_t char_mask = trie->char_mask;
  uint32_t link_shift = trie->link_shift;
  uint32_t link_mask = trie->link_mask;
  uint32_t pattern_shift = trie->pattern_shift;
  // SAFETY: `trie->data` is a flexible array with `n_entries` elements as
  // defined by the hyb file format. The trie traversal below guarantees
  // indices stay within bounds.
  auto trie_data = UNSAFE_BUFFERS(base::span(trie->data, trie->n_entries));
  // SAFETY: `pattern->data` is a flexible array with `n_entries` elements as
  // defined by the hyb file format.
  auto pattern_data =
      UNSAFE_BUFFERS(base::span(pattern->data, pattern->n_entries));
  wtf_size_t maxOffset = len - MIN_SUFFIX - 1;
  for (wtf_size_t i = 0; i < len - 1; i++) {
    uint32_t node = 0;  // index into Trie table
    for (wtf_size_t j = i; j < len; j++) {
      uint16_t c = codes[j];
      uint32_t entry = trie_data[node + c];
      if ((entry & char_mask) == c) {
        node = (entry & link_mask) >> link_shift;
      } else {
        break;
      }
      uint32_t pat_ix = trie_data[node] >> pattern_shift;
      // pat_ix contains a 3-tuple of length, shift (number of trailing zeros),
      // and an offset into the buf pool. This is the pattern for the substring
      // (i..j) we just matched,
      // which we combine (via point-wise max) into the result vector.
      if (pat_ix != 0) {
        uint32_t pat_entry = pattern_data[pat_ix];
        int pat_len = Pattern::len(pat_entry);
        int pat_shift = Pattern::shift(pat_entry);
        // SAFETY: `pattern->buf()` returns a pointer into the pattern data
        // blob with at least `pat_len` bytes as defined by the hyb file format.
        auto pat_buf = UNSAFE_BUFFERS(
            base::span(pattern->buf(pat_entry), static_cast<size_t>(pat_len)));
        int offset = j + 1 - (pat_len + pat_shift);
        // offset is the index within result that lines up with the start of
        // pat_buf
        int start = std::max(MIN_PREFIX - offset, 0);
        int end = std::min(pat_len, (int)maxOffset - offset);
        for (int k = start; k < end; k++) {
          result[offset + k] = std::max(result[offset + k], pat_buf[k]);
        }
      }
    }
  }
  // Since the above calculation does not modify values outside
  // [MIN_PREFIX, len - MIN_SUFFIX], they are left as 0.
  for (wtf_size_t i = MIN_PREFIX; i < maxOffset; i++) {
    result[i] &= 1;
  }
}

}  // namespace android