15cdad92c300a65cab89b172e952186f0c5870657Raph Levien/* 25cdad92c300a65cab89b172e952186f0c5870657Raph Levien * Copyright (C) 2015 The Android Open Source Project 35cdad92c300a65cab89b172e952186f0c5870657Raph Levien * 45cdad92c300a65cab89b172e952186f0c5870657Raph Levien * Licensed under the Apache License, Version 2.0 (the "License"); 55cdad92c300a65cab89b172e952186f0c5870657Raph Levien * you may not use this file except in compliance with the License. 65cdad92c300a65cab89b172e952186f0c5870657Raph Levien * You may obtain a copy of the License at 75cdad92c300a65cab89b172e952186f0c5870657Raph Levien * 85cdad92c300a65cab89b172e952186f0c5870657Raph Levien * http://www.apache.org/licenses/LICENSE-2.0 95cdad92c300a65cab89b172e952186f0c5870657Raph Levien * 105cdad92c300a65cab89b172e952186f0c5870657Raph Levien * Unless required by applicable law or agreed to in writing, software 115cdad92c300a65cab89b172e952186f0c5870657Raph Levien * distributed under the License is distributed on an "AS IS" BASIS, 125cdad92c300a65cab89b172e952186f0c5870657Raph Levien * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 135cdad92c300a65cab89b172e952186f0c5870657Raph Levien * See the License for the specific language governing permissions and 145cdad92c300a65cab89b172e952186f0c5870657Raph Levien * limitations under the License. 155cdad92c300a65cab89b172e952186f0c5870657Raph Levien */ 165cdad92c300a65cab89b172e952186f0c5870657Raph Levien 175cdad92c300a65cab89b172e952186f0c5870657Raph Levien#include <vector> 185cdad92c300a65cab89b172e952186f0c5870657Raph Levien#include <memory> 195cdad92c300a65cab89b172e952186f0c5870657Raph Levien#include <algorithm> 205cdad92c300a65cab89b172e952186f0c5870657Raph Levien#include <string> 21cdd19dadd11a611409c24bb69e6629eab6812d98Roozbeh Pournader#include <unicode/uchar.h> 225cdad92c300a65cab89b172e952186f0c5870657Raph Levien 235cdad92c300a65cab89b172e952186f0c5870657Raph Levien// HACK: for reading pattern file 245cdad92c300a65cab89b172e952186f0c5870657Raph Levien#include <fcntl.h> 255cdad92c300a65cab89b172e952186f0c5870657Raph Levien 265cdad92c300a65cab89b172e952186f0c5870657Raph Levien#define LOG_TAG "Minikin" 275cdad92c300a65cab89b172e952186f0c5870657Raph Levien#include "utils/Log.h" 285cdad92c300a65cab89b172e952186f0c5870657Raph Levien 295cdad92c300a65cab89b172e952186f0c5870657Raph Levien#include "minikin/Hyphenator.h" 305cdad92c300a65cab89b172e952186f0c5870657Raph Levien 315cdad92c300a65cab89b172e952186f0c5870657Raph Levienusing std::vector; 325cdad92c300a65cab89b172e952186f0c5870657Raph Levien 335cdad92c300a65cab89b172e952186f0c5870657Raph Leviennamespace android { 345cdad92c300a65cab89b172e952186f0c5870657Raph Levien 355cdad92c300a65cab89b172e952186f0c5870657Raph Levienstatic const uint16_t CHAR_SOFT_HYPHEN = 0x00AD; 365cdad92c300a65cab89b172e952186f0c5870657Raph Levien 37f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien// The following are structs that correspond to tables inside the hyb file format 38f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 39f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienstruct AlphabetTable0 { 40f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t version; 41f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t min_codepoint; 42f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t max_codepoint; 43f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint8_t data[1]; // actually flexible array, size is known at runtime 44f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien}; 45f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 46f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienstruct AlphabetTable1 { 47f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t version; 48f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t n_entries; 49f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t data[1]; // actually flexible array, size is known at runtime 50f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 51f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien static uint32_t codepoint(uint32_t entry) { return entry >> 11; } 52f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien static uint32_t value(uint32_t entry) { return entry & 0x7ff; } 53f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien}; 54f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 55f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienstruct Trie { 56f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t version; 57f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t char_mask; 58f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t link_shift; 59f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t link_mask; 60f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t pattern_shift; 61f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t n_entries; 62f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t data[1]; // actually flexible array, size is known at runtime 63f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien}; 64f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 65f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienstruct Pattern { 66f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t version; 67f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t n_entries; 68f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t pattern_offset; 69f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t pattern_size; 70f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t data[1]; // actually flexible array, size is known at runtime 71f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 72f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // accessors 73f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien static uint32_t len(uint32_t entry) { return entry >> 26; } 74f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien static uint32_t shift(uint32_t entry) { return (entry >> 20) & 0x3f; } 75f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const uint8_t* buf(uint32_t entry) const { 76f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return reinterpret_cast<const uint8_t*>(this) + pattern_offset + (entry & 0xfffff); 77f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 78f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien}; 79f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 80f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienstruct Header { 81f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t magic; 82f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t version; 83f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t alphabet_offset; 84f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t trie_offset; 85f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t pattern_offset; 86f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t file_size; 87f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 88f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // accessors 89f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const uint8_t* bytes() const { return reinterpret_cast<const uint8_t*>(this); } 90f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t alphabetVersion() const { 91f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return *reinterpret_cast<const uint32_t*>(bytes() + alphabet_offset); 925cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 93f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const AlphabetTable0* alphabetTable0() const { 94f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return reinterpret_cast<const AlphabetTable0*>(bytes() + alphabet_offset); 955cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 96f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const AlphabetTable1* alphabetTable1() const { 97f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return reinterpret_cast<const AlphabetTable1*>(bytes() + alphabet_offset); 98f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 99f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const Trie* trieTable() const { 100f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return reinterpret_cast<const Trie*>(bytes() + trie_offset); 101f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 102f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const Pattern* patternTable() const { 103f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return reinterpret_cast<const Pattern*>(bytes() + pattern_offset); 104f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 105f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien}; 106f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 107f0be43de02a1e07308d3d95408349c3c7f973430Raph LevienHyphenator* Hyphenator::loadBinary(const uint8_t* patternData) { 108f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien Hyphenator* result = new Hyphenator; 109f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien result->patternData = patternData; 110f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return result; 111f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien} 112f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 113f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienvoid Hyphenator::hyphenate(vector<uint8_t>* result, const uint16_t* word, size_t len) { 114f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien result->clear(); 115f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien result->resize(len); 116f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const size_t paddedLen = len + 2; // start and stop code each count for 1 117f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if (patternData != nullptr && 118f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien (int)len >= MIN_PREFIX + MIN_SUFFIX && paddedLen <= MAX_HYPHENATED_SIZE) { 119f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint16_t alpha_codes[MAX_HYPHENATED_SIZE]; 120f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if (alphabetLookup(alpha_codes, word, len)) { 121f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien hyphenateFromCodes(result->data(), alpha_codes, paddedLen); 122f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return; 123f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 124f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // TODO: try NFC normalization 125f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // TODO: handle non-BMP Unicode (requires remapping of offsets) 1265cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 127f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien hyphenateSoft(result->data(), word, len); 1285cdad92c300a65cab89b172e952186f0c5870657Raph Levien} 1295cdad92c300a65cab89b172e952186f0c5870657Raph Levien 1305cdad92c300a65cab89b172e952186f0c5870657Raph Levien// If any soft hyphen is present in the word, use soft hyphens to decide hyphenation, 1315cdad92c300a65cab89b172e952186f0c5870657Raph Levien// as recommended in UAX #14 (Use of Soft Hyphen) 132f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienvoid Hyphenator::hyphenateSoft(uint8_t* result, const uint16_t* word, size_t len) { 133f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien result[0] = 0; 1345cdad92c300a65cab89b172e952186f0c5870657Raph Levien for (size_t i = 1; i < len; i++) { 135f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien result[i] = word[i - 1] == CHAR_SOFT_HYPHEN; 136f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 1375cdad92c300a65cab89b172e952186f0c5870657Raph Levien} 1385cdad92c300a65cab89b172e952186f0c5870657Raph Levien 139f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienbool Hyphenator::alphabetLookup(uint16_t* alpha_codes, const uint16_t* word, size_t len) { 140f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const Header* header = getHeader(); 141f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // TODO: check header magic 142f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t alphabetVersion = header->alphabetVersion(); 143f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if (alphabetVersion == 0) { 144f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const AlphabetTable0* alphabet = header->alphabetTable0(); 145f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t min_codepoint = alphabet->min_codepoint; 146f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t max_codepoint = alphabet->max_codepoint; 147f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien alpha_codes[0] = 0; // word start 148f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien for (size_t i = 0; i < len; i++) { 149f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint16_t c = word[i]; 150f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if (c < min_codepoint || c >= max_codepoint) { 151f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return false; 152f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 153f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint8_t code = alphabet->data[c - min_codepoint]; 154f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if (code == 0) { 155f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return false; 156f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 157f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien alpha_codes[i + 1] = code; 158f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 159f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien alpha_codes[len + 1] = 0; // word termination 160f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return true; 161f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } else if (alphabetVersion == 1) { 162f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const AlphabetTable1* alphabet = header->alphabetTable1(); 163f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien size_t n_entries = alphabet->n_entries; 164f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const uint32_t* begin = alphabet->data; 165f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const uint32_t* end = begin + n_entries; 166f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien alpha_codes[0] = 0; 167f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien for (size_t i = 0; i < len; i++) { 168f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint16_t c = word[i]; 169f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien auto p = std::lower_bound(begin, end, c << 11); 170f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if (p == end) { 171f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return false; 1725cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 173f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t entry = *p; 174f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if (AlphabetTable1::codepoint(entry) != c) { 175f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return false; 176f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 177f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien alpha_codes[i + 1] = AlphabetTable1::value(entry); 178f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 179f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien alpha_codes[len + 1] = 0; 180f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return true; 181f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien } 182f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien return false; 183f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien} 184f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien 185f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien/** 186f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien * Internal implementation, after conversion to codes. All case folding and normalization 187f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien * has been done by now, and all characters have been found in the alphabet. 188f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien * Note: len here is the padded length including 0 codes at start and end. 189f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien **/ 190f0be43de02a1e07308d3d95408349c3c7f973430Raph Levienvoid Hyphenator::hyphenateFromCodes(uint8_t* result, const uint16_t* codes, size_t len) { 191f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const Header* header = getHeader(); 192f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const Trie* trie = header->trieTable(); 193f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const Pattern* pattern = header->patternTable(); 194f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t char_mask = trie->char_mask; 195f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t link_shift = trie->link_shift; 196f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t link_mask = trie->link_mask; 197f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t pattern_shift = trie->pattern_shift; 198f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien size_t maxOffset = len - MIN_SUFFIX - 1; 199f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien for (size_t i = 0; i < len - 1; i++) { 200f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t node = 0; // index into Trie table 201f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien for (size_t j = i; j < len; j++) { 202f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint16_t c = codes[j]; 203f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t entry = trie->data[node + c]; 204f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if ((entry & char_mask) == c) { 205f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien node = (entry & link_mask) >> link_shift; 2065cdad92c300a65cab89b172e952186f0c5870657Raph Levien } else { 2075cdad92c300a65cab89b172e952186f0c5870657Raph Levien break; 2085cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 209f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t pat_ix = trie->data[node] >> pattern_shift; 210f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // pat_ix contains a 3-tuple of length, shift (number of trailing zeros), and an offset 211f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // into the buf pool. This is the pattern for the substring (i..j) we just matched, 212f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // which we combine (via point-wise max) into the result vector. 213f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien if (pat_ix != 0) { 214f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien uint32_t pat_entry = pattern->data[pat_ix]; 215f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien int pat_len = Pattern::len(pat_entry); 216f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien int pat_shift = Pattern::shift(pat_entry); 217f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien const uint8_t* pat_buf = pattern->buf(pat_entry); 218f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien int offset = j + 1 - (pat_len + pat_shift); 219f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien // offset is the index within result that lines up with the start of pat_buf 2205cdad92c300a65cab89b172e952186f0c5870657Raph Levien int start = std::max(MIN_PREFIX - offset, 0); 221f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien int end = std::min(pat_len, (int)maxOffset - offset); 2225cdad92c300a65cab89b172e952186f0c5870657Raph Levien for (int k = start; k < end; k++) { 223f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien result[offset + k] = std::max(result[offset + k], pat_buf[k]); 2245cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 2255cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 2265cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 2275cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 2285cdad92c300a65cab89b172e952186f0c5870657Raph Levien // Since the above calculation does not modify values outside 2295cdad92c300a65cab89b172e952186f0c5870657Raph Levien // [MIN_PREFIX, len - MIN_SUFFIX], they are left as 0. 2305cdad92c300a65cab89b172e952186f0c5870657Raph Levien for (size_t i = MIN_PREFIX; i < maxOffset; i++) { 231f0be43de02a1e07308d3d95408349c3c7f973430Raph Levien result[i] &= 1; 2325cdad92c300a65cab89b172e952186f0c5870657Raph Levien } 2335cdad92c300a65cab89b172e952186f0c5870657Raph Levien} 2345cdad92c300a65cab89b172e952186f0c5870657Raph Levien 2355cdad92c300a65cab89b172e952186f0c5870657Raph Levien} // namespace android 236