FormatSpec.java revision db4f3730047c8a3e25e031aacc07bb02bc47c5ae
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 17package com.android.inputmethod.latin.makedict; 18 19import com.android.inputmethod.annotations.UsedForTesting; 20import com.android.inputmethod.latin.Constants; 21import com.android.inputmethod.latin.makedict.DictDecoder.DictionaryBufferFactory; 22import com.android.inputmethod.latin.makedict.FusionDictionary.DictionaryOptions; 23 24import java.io.File; 25 26/** 27 * Dictionary File Format Specification. 28 */ 29public final class FormatSpec { 30 31 /* 32 * File header layout is as follows: 33 * 34 * v | 35 * e | MAGIC_NUMBER + version of the file format, 2 bytes. 36 * r | 37 * sion 38 * 39 * o | 40 * p | not used 3 bits 41 * t | each unigram and bigram entry has a time stamp? 42 * i | 1 bit, 1 = yes, 0 = no : CONTAINS_TIMESTAMP_FLAG 43 * o | has bigrams ? 1 bit, 1 = yes, 0 = no : CONTAINS_BIGRAMS_FLAG 44 * n | FRENCH_LIGATURE_PROCESSING_FLAG 45 * f | supports dynamic updates ? 1 bit, 1 = yes, 0 = no : SUPPORTS_DYNAMIC_UPDATE 46 * l | GERMAN_UMLAUT_PROCESSING_FLAG 47 * a | 48 * gs 49 * 50 * h | 51 * e | size of the file header, 4bytes 52 * a | including the size of the magic number, the option flags and the header size 53 * d | 54 * ersize 55 * 56 * | attributes list 57 * 58 * attributes list is: 59 * <key> = | string of characters at the char format described below, with the terminator used 60 * | to signal the end of the string. 61 * <value> = | string of characters at the char format described below, with the terminator used 62 * | to signal the end of the string. 63 * if the size of already read < headersize, goto key. 64 * 65 */ 66 67 /* 68 * Node array (FusionDictionary.PtNodeArray) layout is as follows: 69 * 70 * n | 71 * o | the number of PtNodes, 1 or 2 bytes. 72 * d | 1 byte = bbbbbbbb match 73 * e | case 1xxxxxxx => xxxxxxx << 8 + next byte 74 * c | otherwise => bbbbbbbb 75 * o | 76 * unt 77 * 78 * n | 79 * o | sequence of PtNodes, 80 * d | the layout of each PtNode is described below. 81 * e | 82 * s 83 * 84 * f | 85 * o | IF SUPPORTS_DYNAMIC_UPDATE (defined in the file header) 86 * r | forward link address, 3byte 87 * w | 1 byte = bbbbbbbb match 88 * a | case 1xxxxxxx => -((xxxxxxx << 16) + (next byte << 8) + next byte) 89 * r | otherwise => (xxxxxxx << 16) + (next byte << 8) + next byte 90 * d | 91 * linkaddress 92 */ 93 94 /* Node (FusionDictionary.PtNode) layout is as follows: 95 * | IF !SUPPORTS_DYNAMIC_UPDATE 96 * | addressType xx : mask with MASK_CHILDREN_ADDRESS_TYPE 97 * | 2 bits, 00 = no children : FLAG_CHILDREN_ADDRESS_TYPE_NOADDRESS 98 * f | 01 = 1 byte : FLAG_CHILDREN_ADDRESS_TYPE_ONEBYTE 99 * l | 10 = 2 bytes : FLAG_CHILDREN_ADDRESS_TYPE_TWOBYTES 100 * a | 11 = 3 bytes : FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES 101 * g | ELSE 102 * s | is moved ? 2 bits, 11 = no : FLAG_IS_NOT_MOVED 103 * | This must be the same as FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES 104 * | 01 = yes : FLAG_IS_MOVED 105 * | the new address is stored in the same place as the parent address 106 * | is deleted? 10 = yes : FLAG_IS_DELETED 107 * | has several chars ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_MULTIPLE_CHARS 108 * | has a terminal ? 1 bit, 1 = yes, 0 = no : FLAG_IS_TERMINAL 109 * | has shortcut targets ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_SHORTCUT_TARGETS 110 * | has bigrams ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_BIGRAMS 111 * | is not a word ? 1 bit, 1 = yes, 0 = no : FLAG_IS_NOT_A_WORD 112 * | is blacklisted ? 1 bit, 1 = yes, 0 = no : FLAG_IS_BLACKLISTED 113 * 114 * p | 115 * a | IF SUPPORTS_DYNAMIC_UPDATE (defined in the file header) 116 * r | parent address, 3byte 117 * e | 1 byte = bbbbbbbb match 118 * n | case 1xxxxxxx => -((0xxxxxxx << 16) + (next byte << 8) + next byte) 119 * t | otherwise => (bbbbbbbb << 16) + (next byte << 8) + next byte 120 * a | This address is relative to the head of the PtNode. 121 * d | If the node doesn't have a parent, this field is set to 0. 122 * d | 123 * ress 124 * 125 * c | IF FLAG_HAS_MULTIPLE_CHARS 126 * h | char, char, char, char n * (1 or 3 bytes) : use PtNodeInfo for i/o helpers 127 * a | end 1 byte, = 0 128 * r | ELSE 129 * s | char 1 or 3 bytes 130 * | END 131 * 132 * f | 133 * r | IF FLAG_IS_TERMINAL 134 * e | frequency 1 byte 135 * q | 136 * 137 * c | IF SUPPORTS_DYNAMIC_UPDATE 138 * h | children address, 3 bytes 139 * i | 1 byte = bbbbbbbb match 140 * l | case 1xxxxxxx => -((0xxxxxxx << 16) + (next byte << 8) + next byte) 141 * d | otherwise => (bbbbbbbb<<16) + (next byte << 8) + next byte 142 * r | if this node doesn't have children, this field is set to 0. 143 * e | (see BinaryDictEncoderUtils#writeVariableSignedAddress) 144 * n | ELSIF 00 = FLAG_CHILDREN_ADDRESS_TYPE_NOADDRESS == addressType 145 * a | // nothing 146 * d | ELSIF 01 = FLAG_CHILDREN_ADDRESS_TYPE_ONEBYTE == addressType 147 * d | children address, 1 byte 148 * r | ELSIF 10 = FLAG_CHILDREN_ADDRESS_TYPE_TWOBYTES == addressType 149 * e | children address, 2 bytes 150 * s | ELSE // 11 = FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES = addressType 151 * s | children address, 3 bytes 152 * | END 153 * | This address is relative to the position of this field. 154 * 155 * | IF FLAG_IS_TERMINAL && FLAG_HAS_SHORTCUT_TARGETS 156 * | shortcut string list 157 * | IF FLAG_IS_TERMINAL && FLAG_HAS_BIGRAMS 158 * | bigrams address list 159 * 160 * Char format is: 161 * 1 byte = bbbbbbbb match 162 * case 000xxxxx: xxxxx << 16 + next byte << 8 + next byte 163 * else: if 00011111 (= 0x1F) : this is the terminator. This is a relevant choice because 164 * unicode code points range from 0 to 0x10FFFF, so any 3-byte value starting with 165 * 00011111 would be outside unicode. 166 * else: iso-latin-1 code 167 * This allows for the whole unicode range to be encoded, including chars outside of 168 * the BMP. Also everything in the iso-latin-1 charset is only 1 byte, except control 169 * characters which should never happen anyway (and still work, but take 3 bytes). 170 * 171 * bigram address list is: 172 * <flags> = | hasNext = 1 bit, 1 = yes, 0 = no : FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT 173 * | addressSign = 1 bit, : FLAG_BIGRAM_ATTR_OFFSET_NEGATIVE 174 * | 1 = must take -address, 0 = must take +address 175 * | xx : mask with MASK_BIGRAM_ATTR_ADDRESS_TYPE 176 * | addressFormat = 2 bits, 00 = unused : FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE 177 * | 01 = 1 byte : FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE 178 * | 10 = 2 bytes : FLAG_BIGRAM_ATTR_ADDRESS_TYPE_TWOBYTES 179 * | 11 = 3 bytes : FLAG_BIGRAM_ATTR_ADDRESS_TYPE_THREEBYTES 180 * | 4 bits : frequency : mask with FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY 181 * <address> | IF (01 == FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE == addressFormat) 182 * | read 1 byte, add top 4 bits 183 * | ELSIF (10 == FLAG_BIGRAM_ATTR_ADDRESS_TYPE_TWOBYTES == addressFormat) 184 * | read 2 bytes, add top 4 bits 185 * | ELSE // 11 == FLAG_BIGRAM_ATTR_ADDRESS_TYPE_THREEBYTES == addressFormat 186 * | read 3 bytes, add top 4 bits 187 * | END 188 * | if (FLAG_BIGRAM_ATTR_OFFSET_NEGATIVE) then address = -address 189 * if (FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT) goto bigram_and_shortcut_address_list_is 190 * 191 * shortcut string list is: 192 * <byte size> = PTNODE_SHORTCUT_LIST_SIZE_SIZE bytes, big-endian: size of the list, in bytes. 193 * <flags> = | hasNext = 1 bit, 1 = yes, 0 = no : FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT 194 * | reserved = 3 bits, must be 0 195 * | 4 bits : frequency : mask with FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY 196 * <shortcut> = | string of characters at the char format described above, with the terminator 197 * | used to signal the end of the string. 198 * if (FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT goto flags 199 */ 200 201 public static final int MAGIC_NUMBER = 0x9BC13AFE; 202 static final int MINIMUM_SUPPORTED_VERSION = 2; 203 static final int MAXIMUM_SUPPORTED_VERSION = 4; 204 static final int NOT_A_VERSION_NUMBER = -1; 205 static final int FIRST_VERSION_WITH_DYNAMIC_UPDATE = 3; 206 static final int FIRST_VERSION_WITH_TERMINAL_ID = 4; 207 static final int VERSION3 = 3; 208 static final int VERSION4 = 4; 209 210 // These options need to be the same numeric values as the one in the native reading code. 211 static final int GERMAN_UMLAUT_PROCESSING_FLAG = 0x1; 212 // TODO: Make the native reading code read this variable. 213 static final int SUPPORTS_DYNAMIC_UPDATE = 0x2; 214 static final int FRENCH_LIGATURE_PROCESSING_FLAG = 0x4; 215 static final int CONTAINS_BIGRAMS_FLAG = 0x8; 216 static final int CONTAINS_TIMESTAMP_FLAG = 0x10; 217 218 // TODO: Make this value adaptative to content data, store it in the header, and 219 // use it in the reading code. 220 static final int MAX_WORD_LENGTH = Constants.DICTIONARY_MAX_WORD_LENGTH; 221 222 static final int PARENT_ADDRESS_SIZE = 3; 223 static final int FORWARD_LINK_ADDRESS_SIZE = 3; 224 225 // These flags are used only in the static dictionary. 226 static final int MASK_CHILDREN_ADDRESS_TYPE = 0xC0; 227 static final int FLAG_CHILDREN_ADDRESS_TYPE_NOADDRESS = 0x00; 228 static final int FLAG_CHILDREN_ADDRESS_TYPE_ONEBYTE = 0x40; 229 static final int FLAG_CHILDREN_ADDRESS_TYPE_TWOBYTES = 0x80; 230 static final int FLAG_CHILDREN_ADDRESS_TYPE_THREEBYTES = 0xC0; 231 232 static final int FLAG_HAS_MULTIPLE_CHARS = 0x20; 233 234 static final int FLAG_IS_TERMINAL = 0x10; 235 static final int FLAG_HAS_SHORTCUT_TARGETS = 0x08; 236 static final int FLAG_HAS_BIGRAMS = 0x04; 237 static final int FLAG_IS_NOT_A_WORD = 0x02; 238 static final int FLAG_IS_BLACKLISTED = 0x01; 239 240 // These flags are used only in the dynamic dictionary. 241 static final int MASK_MOVE_AND_DELETE_FLAG = 0xC0; 242 static final int FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE = 0x40; 243 static final int FLAG_IS_MOVED = 0x00 | FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE; 244 static final int FLAG_IS_NOT_MOVED = 0x80 | FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE; 245 static final int FLAG_IS_DELETED = 0x80; 246 247 static final int FLAG_BIGRAM_SHORTCUT_ATTR_HAS_NEXT = 0x80; 248 static final int FLAG_BIGRAM_ATTR_OFFSET_NEGATIVE = 0x40; 249 static final int MASK_BIGRAM_ATTR_ADDRESS_TYPE = 0x30; 250 static final int FLAG_BIGRAM_ATTR_ADDRESS_TYPE_ONEBYTE = 0x10; 251 static final int FLAG_BIGRAM_ATTR_ADDRESS_TYPE_TWOBYTES = 0x20; 252 static final int FLAG_BIGRAM_ATTR_ADDRESS_TYPE_THREEBYTES = 0x30; 253 static final int FLAG_BIGRAM_SHORTCUT_ATTR_FREQUENCY = 0x0F; 254 255 static final int PTNODE_CHARACTERS_TERMINATOR = 0x1F; 256 257 static final int PTNODE_TERMINATOR_SIZE = 1; 258 static final int PTNODE_FLAGS_SIZE = 1; 259 static final int PTNODE_FREQUENCY_SIZE = 1; 260 static final int PTNODE_TERMINAL_ID_SIZE = 4; 261 static final int PTNODE_MAX_ADDRESS_SIZE = 3; 262 static final int PTNODE_ATTRIBUTE_FLAGS_SIZE = 1; 263 static final int PTNODE_ATTRIBUTE_MAX_ADDRESS_SIZE = 3; 264 static final int PTNODE_SHORTCUT_LIST_SIZE_SIZE = 2; 265 266 // These values are used only by version 4 or later. 267 static final String TRIE_FILE_EXTENSION = ".trie"; 268 static final String FREQ_FILE_EXTENSION = ".freq"; 269 static final String UNIGRAM_TIMESTAMP_FILE_EXTENSION = ".timestamp"; 270 // tat = Terminal Address Table 271 static final String TERMINAL_ADDRESS_TABLE_FILE_EXTENSION = ".tat"; 272 static final String BIGRAM_FILE_EXTENSION = ".bigram"; 273 static final String SHORTCUT_FILE_EXTENSION = ".shortcut"; 274 static final String LOOKUP_TABLE_FILE_SUFFIX = "_lookup"; 275 static final String CONTENT_TABLE_FILE_SUFFIX = "_index"; 276 static final int FREQUENCY_AND_FLAGS_SIZE = 2; 277 static final int TERMINAL_ADDRESS_TABLE_ADDRESS_SIZE = 3; 278 static final int UNIGRAM_TIMESTAMP_SIZE = 4; 279 280 // With the English main dictionary as of October 2013, the size of bigram address table is 281 // is 584KB with the block size being 4. 282 // This is 91% of that of full address table. 283 static final int BIGRAM_ADDRESS_TABLE_BLOCK_SIZE = 4; 284 static final int BIGRAM_CONTENT_COUNT = 2; 285 static final int BIGRAM_FREQ_CONTENT_INDEX = 0; 286 static final int BIGRAM_TIMESTAMP_CONTENT_INDEX = 1; 287 static final String BIGRAM_FREQ_CONTENT_ID = "_freq"; 288 static final String BIGRAM_TIMESTAMP_CONTENT_ID = "_timestamp"; 289 static final int BIGRAM_TIMESTAMP_SIZE = 4; 290 static final int BIGRAM_COUNTER_SIZE = 1; 291 static final int BIGRAM_LEVEL_SIZE = 1; 292 293 static final int SHORTCUT_CONTENT_COUNT = 1; 294 static final int SHORTCUT_CONTENT_INDEX = 0; 295 // With the English main dictionary as of October 2013, the size of shortcut address table is 296 // 29KB with the block size being 64. 297 // This is only 4.4% of that of full address table. 298 static final int SHORTCUT_ADDRESS_TABLE_BLOCK_SIZE = 64; 299 static final String SHORTCUT_CONTENT_ID = "_shortcut"; 300 301 static final int NO_CHILDREN_ADDRESS = Integer.MIN_VALUE; 302 static final int NO_PARENT_ADDRESS = 0; 303 static final int NO_FORWARD_LINK_ADDRESS = 0; 304 static final int INVALID_CHARACTER = -1; 305 306 static final int MAX_PTNODES_FOR_ONE_BYTE_PTNODE_COUNT = 0x7F; // 127 307 // Large PtNode array size field size is 2 bytes. 308 static final int LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE_FLAG = 0x8000; 309 static final int MAX_PTNODES_IN_A_PT_NODE_ARRAY = 0x7FFF; // 32767 310 static final int MAX_BIGRAMS_IN_A_PTNODE = 10000; 311 static final int MAX_SHORTCUT_LIST_SIZE_IN_A_PTNODE = 0xFFFF; 312 313 static final int MAX_TERMINAL_FREQUENCY = 255; 314 static final int MAX_BIGRAM_FREQUENCY = 15; 315 316 public static final int SHORTCUT_WHITELIST_FREQUENCY = 15; 317 318 // This option needs to be the same numeric value as the one in binary_format.h. 319 static final int NOT_VALID_WORD = -99; 320 static final int SIGNED_CHILDREN_ADDRESS_SIZE = 3; 321 322 static final int UINT8_MAX = 0xFF; 323 static final int UINT16_MAX = 0xFFFF; 324 static final int UINT24_MAX = 0xFFFFFF; 325 static final int SINT24_MAX = 0x7FFFFF; 326 static final int MSB8 = 0x80; 327 static final int MSB24 = 0x800000; 328 329 /** 330 * Options about file format. 331 */ 332 public static final class FormatOptions { 333 public final int mVersion; 334 public final boolean mSupportsDynamicUpdate; 335 public final boolean mHasTerminalId; 336 public final boolean mHasTimestamp; 337 @UsedForTesting 338 public FormatOptions(final int version) { 339 this(version, false); 340 } 341 342 @UsedForTesting 343 public FormatOptions(final int version, final boolean supportsDynamicUpdate) { 344 this(version, supportsDynamicUpdate, false /* hasTimestamp */); 345 } 346 347 public FormatOptions(final int version, final boolean supportsDynamicUpdate, 348 final boolean hasTimestamp) { 349 mVersion = version; 350 if (version < FIRST_VERSION_WITH_DYNAMIC_UPDATE && supportsDynamicUpdate) { 351 throw new RuntimeException("Dynamic updates are only supported with versions " 352 + FIRST_VERSION_WITH_DYNAMIC_UPDATE + " and ulterior."); 353 } 354 mSupportsDynamicUpdate = supportsDynamicUpdate; 355 mHasTerminalId = (version >= FIRST_VERSION_WITH_TERMINAL_ID); 356 mHasTimestamp = hasTimestamp; 357 } 358 } 359 360 /** 361 * Class representing file header. 362 */ 363 public static final class FileHeader { 364 public final int mHeaderSize; 365 public final DictionaryOptions mDictionaryOptions; 366 public final FormatOptions mFormatOptions; 367 // Note that these are corresponding definitions in native code in latinime::HeaderPolicy 368 // and latinime::HeaderReadWriteUtils. 369 public static final String SUPPORTS_DYNAMIC_UPDATE_ATTRIBUTE = "SUPPORTS_DYNAMIC_UPDATE"; 370 public static final String USES_FORGETTING_CURVE_ATTRIBUTE = "USES_FORGETTING_CURVE"; 371 public static final String ATTRIBUTE_VALUE_TRUE = "1"; 372 373 public static final String DICTIONARY_VERSION_ATTRIBUTE = "version"; 374 public static final String DICTIONARY_LOCALE_ATTRIBUTE = "locale"; 375 public static final String DICTIONARY_ID_ATTRIBUTE = "dictionary"; 376 private static final String DICTIONARY_DESCRIPTION_ATTRIBUTE = "description"; 377 public FileHeader(final int headerSize, final DictionaryOptions dictionaryOptions, 378 final FormatOptions formatOptions) { 379 mHeaderSize = headerSize; 380 mDictionaryOptions = dictionaryOptions; 381 mFormatOptions = formatOptions; 382 } 383 384 // Helper method to get the locale as a String 385 public String getLocaleString() { 386 return mDictionaryOptions.mAttributes.get(FileHeader.DICTIONARY_LOCALE_ATTRIBUTE); 387 } 388 389 // Helper method to get the version String 390 public String getVersion() { 391 return mDictionaryOptions.mAttributes.get(FileHeader.DICTIONARY_VERSION_ATTRIBUTE); 392 } 393 394 // Helper method to get the dictionary ID as a String 395 public String getId() { 396 return mDictionaryOptions.mAttributes.get(FileHeader.DICTIONARY_ID_ATTRIBUTE); 397 } 398 399 // Helper method to get the description 400 public String getDescription() { 401 // TODO: Right now each dictionary file comes with a description in its own language. 402 // It will display as is no matter the device's locale. It should be internationalized. 403 return mDictionaryOptions.mAttributes.get(FileHeader.DICTIONARY_DESCRIPTION_ATTRIBUTE); 404 } 405 } 406 407 /** 408 * Returns new dictionary decoder. 409 * 410 * @param dictFile the dictionary file. 411 * @param bufferType The type of buffer, as one of USE_* in DictDecoder. 412 * @return new dictionary decoder if the dictionary file exists, otherwise null. 413 */ 414 public static DictDecoder getDictDecoder(final File dictFile, final int bufferType) { 415 if (dictFile.isDirectory()) { 416 return new Ver4DictDecoder(dictFile, bufferType); 417 } else if (dictFile.isFile()) { 418 return new Ver3DictDecoder(dictFile, bufferType); 419 } 420 return null; 421 } 422 423 public static DictDecoder getDictDecoder(final File dictFile, 424 final DictionaryBufferFactory factory) { 425 if (dictFile.isDirectory()) { 426 return new Ver4DictDecoder(dictFile, factory); 427 } else if (dictFile.isFile()) { 428 return new Ver3DictDecoder(dictFile, factory); 429 } 430 return null; 431 } 432 433 public static DictDecoder getDictDecoder(final File dictFile) { 434 return getDictDecoder(dictFile, DictDecoder.USE_READONLY_BYTEBUFFER); 435 } 436 437 private FormatSpec() { 438 // This utility class is not publicly instantiable. 439 } 440} 441