1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.inputmethod.latin.makedict; 18 19 import com.android.inputmethod.annotations.UsedForTesting; 20 import com.android.inputmethod.latin.Constants; 21 22 import java.util.Date; 23 import java.util.HashMap; 24 25 /** 26 * Dictionary File Format Specification. 27 */ 28 public final class FormatSpec { 29 30 /* 31 * File header layout is as follows: 32 * 33 * v | 34 * e | MAGIC_NUMBER + version of the file format, 2 bytes. 35 * r | 36 * sion 37 * 38 * o | 39 * p | not used 3 bits 40 * t | each unigram and bigram entry has a time stamp? 41 * i | 1 bit, 1 = yes, 0 = no : CONTAINS_TIMESTAMP_FLAG 42 * o | 43 * nflags 44 * 45 * h | 46 * e | size of the file header, 4bytes 47 * a | including the size of the magic number, the option flags and the header size 48 * d | 49 * ersize 50 * 51 * | attributes list 52 * 53 * attributes list is: 54 * <key> = | string of characters at the char format described below, with the terminator used 55 * | to signal the end of the string. 56 * <value> = | string of characters at the char format described below, with the terminator used 57 * | to signal the end of the string. 58 * if the size of already read < headersize, goto key. 59 * 60 */ 61 62 /* 63 * Node array (FusionDictionary.PtNodeArray) layout is as follows: 64 * 65 * n | 66 * o | the number of PtNodes, 1 or 2 bytes. 67 * d | 1 byte = bbbbbbbb match 68 * e | case 1xxxxxxx => xxxxxxx << 8 + next byte 69 * c | otherwise => bbbbbbbb 70 * o | 71 * unt 72 * 73 * n | 74 * o | sequence of PtNodes, 75 * d | the layout of each PtNode is described below. 76 * e | 77 * s 78 * 79 * f | 80 * o | forward link address, 3byte 81 * r | 1 byte = bbbbbbbb match 82 * w | case 1xxxxxxx => -((xxxxxxx << 16) + (next byte << 8) + next byte) 83 * a | otherwise => (xxxxxxx << 16) + (next byte << 8) + next byte 84 * r | 85 * dlinkaddress 86 */ 87 88 /* Node (FusionDictionary.PtNode) layout is as follows: 89 * | is moved ? 2 bits, 11 = no : FLAG_IS_NOT_MOVED 90 * | This must be the same as FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES 91 * | 01 = yes : FLAG_IS_MOVED 92 * f | the new address is stored in the same place as the parent address 93 * l | is deleted? 10 = yes : FLAG_IS_DELETED 94 * a | has several chars ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_MULTIPLE_CHARS 95 * g | has a terminal ? 1 bit, 1 = yes, 0 = no : FLAG_IS_TERMINAL 96 * s | has shortcut targets ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_SHORTCUT_TARGETS 97 * | has bigrams ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_BIGRAMS 98 * | is not a word ? 1 bit, 1 = yes, 0 = no : FLAG_IS_NOT_A_WORD 99 * | is blacklisted ? 1 bit, 1 = yes, 0 = no : FLAG_IS_BLACKLISTED 100 * 101 * p | 102 * a | parent address, 3byte 103 * r | 1 byte = bbbbbbbb match 104 * e | case 1xxxxxxx => -((0xxxxxxx << 16) + (next byte << 8) + next byte) 105 * n | otherwise => (bbbbbbbb << 16) + (next byte << 8) + next byte 106 * t | This address is relative to the head of the PtNode. 107 * a | If the node doesn't have a parent, this field is set to 0. 108 * d | 109 * dress 110 * 111 * c | IF FLAG_HAS_MULTIPLE_CHARS 112 * h | char, char, char, char n * (1 or 3 bytes) : use PtNodeInfo for i/o helpers 113 * a | end 1 byte, = 0 114 * r | ELSE 115 * s | char 1 or 3 bytes 116 * | END 117 * 118 * f | 119 * r | IF FLAG_IS_TERMINAL 120 * e | frequency 1 byte 121 * q | 122 * 123 * c | 124 * h | children address, 3 bytes 125 * i | 1 byte = bbbbbbbb match 126 * l | case 1xxxxxxx => -((0xxxxxxx << 16) + (next byte << 8) + next byte) 127 * d | otherwise => (bbbbbbbb<<16) + (next byte << 8) + next byte 128 * r | if this node doesn't have children, this field is set to 0. 129 * e | (see BinaryDictEncoderUtils#writeVariableSignedAddress) 130 * n | This address is relative to the position of this field. 131 * a | 132 * ddress 133 * 134 * | IF FLAG_IS_TERMINAL && FLAG_HAS_SHORTCUT_TARGETS 135 * | shortcut string list 136 * | IF FLAG_IS_TERMINAL && FLAG_HAS_BIGRAMS 137 * | bigrams address list 138 * 139 * Char format is: 140 * 1 byte = bbbbbbbb match 141 * case 000xxxxx: xxxxx << 16 + next byte << 8 + next byte 142 * else: if 00011111 (= 0x1F) : this is the terminator. This is a relevant choice because 143 * unicode code points range from 0 to 0x10FFFF, so any 3-byte value starting with 144 * 00011111 would be outside unicode. 145 * else: iso-latin-1 code 146 * This allows for the whole unicode range to be encoded, including chars outside of 147 * the BMP. Also everything in the iso-latin-1 charset is only 1 byte, except control 148 * characters which should never happen anyway (and still work, but take 3 bytes). 149 * 150 * bigram address list is: 151 * <flags> = | hasNext = 1 bit, 1 = yes, 0 = no : FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT 152 * | addressSign = 1 bit, : FLAG_BIGRAM_ATTR_OFFSET_NEGATIVE 153 * | 1 = must take -address, 0 = must take +address 154 * | xx : mask with MASK_BIGRAM_ATTR_ADDRESS_TYPE 155 * | addressFormat = 2 bits, 00 = unused : FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE 156 * | 01 = 1 byte : FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE 157 * | 10 = 2 bytes : FLAG_BIGRAM_ATTR_ADDRESS_TYPE_TWOBYTES 158 * | 11 = 3 bytes : FLAG_BIGRAM_ATTR_ADDRESS_TYPE_THREEBYTES 159 * | 4 bits : frequency : mask with FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY 160 * <address> | IF (01 == FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE == addressFormat) 161 * | read 1 byte, add top 4 bits 162 * | ELSIF (10 == FLAG_BIGRAM_ATTR_ADDRESS_TYPE_TWOBYTES == addressFormat) 163 * | read 2 bytes, add top 4 bits 164 * | ELSE // 11 == FLAG_BIGRAM_ATTR_ADDRESS_TYPE_THREEBYTES == addressFormat 165 * | read 3 bytes, add top 4 bits 166 * | END 167 * | if (FLAG_BIGRAM_ATTR_OFFSET_NEGATIVE) then address = -address 168 * if (FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT) goto bigram_and_shortcut_address_list_is 169 * 170 * shortcut string list is: 171 * <byte size> = PTNODE_SHORTCUT_LIST_SIZE_SIZE bytes, big-endian: size of the list, in bytes. 172 * <flags> = | hasNext = 1 bit, 1 = yes, 0 = no : FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT 173 * | reserved = 3 bits, must be 0 174 * | 4 bits : frequency : mask with FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY 175 * <shortcut> = | string of characters at the char format described above, with the terminator 176 * | used to signal the end of the string. 177 * if (FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT goto flags 178 */ 179 180 public static final int MAGIC_NUMBER = 0x9BC13AFE; 181 static final int NOT_A_VERSION_NUMBER = -1; 182 static final int FIRST_VERSION_WITH_DYNAMIC_UPDATE = 3; 183 static final int FIRST_VERSION_WITH_TERMINAL_ID = 4; 184 185 // These MUST have the same values as the relevant constants in format_utils.h. 186 // From version 4 on, we use version * 100 + revision as a version number. That allows 187 // us to change the format during development while having testing devices remove 188 // older files with each upgrade, while still having a readable versioning scheme. 189 // When we bump up the dictionary format version, we should update 190 // ExpandableDictionary.needsToMigrateDictionary() and 191 // ExpandableDictionary.matchesExpectedBinaryDictFormatVersionForThisType(). 192 public static final int VERSION2 = 2; 193 // Dictionary version used for testing. 194 public static final int VERSION4_ONLY_FOR_TESTING = 399; 195 public static final int VERSION401 = 401; 196 public static final int VERSION4 = 402; 197 public static final int VERSION4_DEV = 403; 198 static final int MINIMUM_SUPPORTED_VERSION = VERSION2; 199 static final int MAXIMUM_SUPPORTED_VERSION = VERSION4_DEV; 200 201 // TODO: Make this value adaptative to content data, store it in the header, and 202 // use it in the reading code. 203 static final int MAX_WORD_LENGTH = Constants.DICTIONARY_MAX_WORD_LENGTH; 204 205 static final int PARENT_ADDRESS_SIZE = 3; 206 static final int FORWARD_LINK_ADDRESS_SIZE = 3; 207 208 // These flags are used only in the static dictionary. 209 static final int MASK_CHILDREN_ADDRESS_TYPE = 0xC0; 210 static final int FLAG_CHILDREN_ADDRESS_TYPE_NOADDRESS = 0x00; 211 static final int FLAG_CHILDREN_ADDRESS_TYPE_ONEBYTE = 0x40; 212 static final int FLAG_CHILDREN_ADDRESS_TYPE_TWOBYTES = 0x80; 213 static final int FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES = 0xC0; 214 215 static final int FLAG_HAS_MULTIPLE_CHARS = 0x20; 216 217 static final int FLAG_IS_TERMINAL = 0x10; 218 static final int FLAG_HAS_SHORTCUT_TARGETS = 0x08; 219 static final int FLAG_HAS_BIGRAMS = 0x04; 220 static final int FLAG_IS_NOT_A_WORD = 0x02; 221 static final int FLAG_IS_BLACKLISTED = 0x01; 222 223 // These flags are used only in the dynamic dictionary. 224 static final int MASK_MOVE_AND_DELETE_FLAG = 0xC0; 225 static final int FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE = 0x40; 226 static final int FLAG_IS_MOVED = 0x00 | FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE; 227 static final int FLAG_IS_NOT_MOVED = 0x80 | FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE; 228 static final int FLAG_IS_DELETED = 0x80; 229 230 static final int FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT = 0x80; 231 static final int FLAG_BIGRAM_ATTR_OFFSET_NEGATIVE = 0x40; 232 static final int MASK_BIGRAM_ATTR_ADDRESS_TYPE = 0x30; 233 static final int FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE = 0x10; 234 static final int FLAG_BIGRAM_ATTR_ADDRESS_TYPE_TWOBYTES = 0x20; 235 static final int FLAG_BIGRAM_ATTR_ADDRESS_TYPE_THREEBYTES = 0x30; 236 static final int FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY = 0x0F; 237 238 static final int PTNODE_CHARACTERS_TERMINATOR = 0x1F; 239 240 static final int PTNODE_TERMINATOR_SIZE = 1; 241 static final int PTNODE_FLAGS_SIZE = 1; 242 static final int PTNODE_FREQUENCY_SIZE = 1; 243 static final int PTNODE_TERMINAL_ID_SIZE = 4; 244 static final int PTNODE_MAX_ADDRESS_SIZE = 3; 245 static final int PTNODE_ATTRIBUTE_FLAGS_SIZE = 1; 246 static final int PTNODE_ATTRIBUTE_MAX_ADDRESS_SIZE = 3; 247 static final int PTNODE_SHORTCUT_LIST_SIZE_SIZE = 2; 248 249 // These values are used only by version 4 or later. They MUST match the definitions in 250 // ver4_dict_constants.cpp. 251 static final String TRIE_FILE_EXTENSION = ".trie"; 252 public static final String HEADER_FILE_EXTENSION = ".header"; 253 static final String FREQ_FILE_EXTENSION = ".freq"; 254 // tat = Terminal Address Table 255 static final String TERMINAL_ADDRESS_TABLE_FILE_EXTENSION = ".tat"; 256 static final String BIGRAM_FILE_EXTENSION = ".bigram"; 257 static final String SHORTCUT_FILE_EXTENSION = ".shortcut"; 258 static final String LOOKUP_TABLE_FILE_SUFFIX = "_lookup"; 259 static final String CONTENT_TABLE_FILE_SUFFIX = "_index"; 260 static final int FLAGS_IN_FREQ_FILE_SIZE = 1; 261 static final int FREQUENCY_AND_FLAGS_SIZE = 2; 262 static final int TERMINAL_ADDRESS_TABLE_ADDRESS_SIZE = 3; 263 static final int UNIGRAM_TIMESTAMP_SIZE = 4; 264 static final int UNIGRAM_COUNTER_SIZE = 1; 265 static final int UNIGRAM_LEVEL_SIZE = 1; 266 267 // With the English main dictionary as of October 2013, the size of bigram address table is 268 // is 345KB with the block size being 16. 269 // This is 54% of that of full address table. 270 static final int BIGRAM_ADDRESS_TABLE_BLOCK_SIZE = 16; 271 static final int BIGRAM_CONTENT_COUNT = 1; 272 static final int BIGRAM_FREQ_CONTENT_INDEX = 0; 273 static final String BIGRAM_FREQ_CONTENT_ID = "_freq"; 274 static final int BIGRAM_TIMESTAMP_SIZE = 4; 275 static final int BIGRAM_COUNTER_SIZE = 1; 276 static final int BIGRAM_LEVEL_SIZE = 1; 277 278 static final int SHORTCUT_CONTENT_COUNT = 1; 279 static final int SHORTCUT_CONTENT_INDEX = 0; 280 // With the English main dictionary as of October 2013, the size of shortcut address table is 281 // 26KB with the block size being 64. 282 // This is only 4.4% of that of full address table. 283 static final int SHORTCUT_ADDRESS_TABLE_BLOCK_SIZE = 64; 284 static final String SHORTCUT_CONTENT_ID = "_shortcut"; 285 286 static final int NO_CHILDREN_ADDRESS = Integer.MIN_VALUE; 287 static final int NO_PARENT_ADDRESS = 0; 288 static final int NO_FORWARD_LINK_ADDRESS = 0; 289 static final int INVALID_CHARACTER = -1; 290 291 static final int MAX_PTNODES_FOR_ONE_BYTE_PTNODE_COUNT = 0x7F; // 127 292 // Large PtNode array size field size is 2 bytes. 293 static final int LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE_FLAG = 0x8000; 294 static final int MAX_PTNODES_IN_A_PT_NODE_ARRAY = 0x7FFF; // 32767 295 static final int MAX_BIGRAMS_IN_A_PTNODE = 10000; 296 static final int MAX_SHORTCUT_LIST_SIZE_IN_A_PTNODE = 0xFFFF; 297 298 static final int MAX_TERMINAL_FREQUENCY = 255; 299 static final int MAX_BIGRAM_FREQUENCY = 15; 300 301 public static final int SHORTCUT_WHITELIST_FREQUENCY = 15; 302 303 // This option needs to be the same numeric value as the one in binary_format.h. 304 static final int NOT_VALID_WORD = -99; 305 static final int SIGNED_CHILDREN_ADDRESS_SIZE = 3; 306 307 static final int UINT8_MAX = 0xFF; 308 static final int UINT16_MAX = 0xFFFF; 309 static final int UINT24_MAX = 0xFFFFFF; 310 static final int SINT24_MAX = 0x7FFFFF; 311 static final int MSB8 = 0x80; 312 static final int MSB24 = 0x800000; 313 314 /** 315 * Options about file format. 316 */ 317 public static final class FormatOptions { 318 public final int mVersion; 319 public final boolean mHasTimestamp; 320 321 @UsedForTesting 322 public FormatOptions(final int version) { 323 this(version, false /* hasTimestamp */); 324 } 325 326 public FormatOptions(final int version, final boolean hasTimestamp) { 327 mVersion = version; 328 mHasTimestamp = hasTimestamp; 329 } 330 } 331 332 /** 333 * Options global to the dictionary. 334 */ 335 public static final class DictionaryOptions { 336 public final HashMap<String, String> mAttributes; 337 public DictionaryOptions(final HashMap<String, String> attributes) { 338 mAttributes = attributes; 339 } 340 @Override 341 public String toString() { // Convenience method 342 return toString(0, false); 343 } 344 public String toString(final int indentCount, final boolean plumbing) { 345 final StringBuilder indent = new StringBuilder(); 346 if (plumbing) { 347 indent.append("H:"); 348 } else { 349 for (int i = 0; i < indentCount; ++i) { 350 indent.append(" "); 351 } 352 } 353 final StringBuilder s = new StringBuilder(); 354 for (final String optionKey : mAttributes.keySet()) { 355 s.append(indent); 356 s.append(optionKey); 357 s.append(" = "); 358 if ("date".equals(optionKey) && !plumbing) { 359 // Date needs a number of milliseconds, but the dictionary contains seconds 360 s.append(new Date( 361 1000 * Long.parseLong(mAttributes.get(optionKey))).toString()); 362 } else { 363 s.append(mAttributes.get(optionKey)); 364 } 365 s.append("\n"); 366 } 367 return s.toString(); 368 } 369 } 370 371 private FormatSpec() { 372 // This utility class is not publicly instantiable. 373 } 374 } 375
