diff options
Diffstat (limited to 'java/src/com/android/inputmethod/latin/makedict')
4 files changed, 786 insertions, 75 deletions
diff --git a/java/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtils.java b/java/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtils.java index 7b0231a6b..e5ec449ea 100644 --- a/java/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtils.java +++ b/java/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtils.java @@ -17,18 +17,30 @@ package com.android.inputmethod.latin.makedict; import com.android.inputmethod.latin.Constants; +import com.android.inputmethod.latin.makedict.BinaryDictInputOutput.CharEncoding; import com.android.inputmethod.latin.makedict.BinaryDictInputOutput.FusionDictionaryBufferInterface; import com.android.inputmethod.latin.makedict.FormatSpec.FileHeader; import com.android.inputmethod.latin.makedict.FormatSpec.FormatOptions; import com.android.inputmethod.latin.makedict.FusionDictionary.CharGroup; +import com.android.inputmethod.latin.makedict.FusionDictionary.WeightedString; import java.io.IOException; +import java.io.OutputStream; import java.util.ArrayList; +import java.util.Arrays; +import java.util.Iterator; import java.util.Map; import java.util.Stack; public final class BinaryDictIOUtils { private static final boolean DBG = false; + private static final int MSB24 = 0x800000; + private static final int SINT24_MAX = 0x7FFFFF; + private static final int MAX_JUMPS = 10000; + + private BinaryDictIOUtils() { + // This utility class is not publicly instantiable. + } private static final class Position { public static final int NOT_READ_GROUPCOUNT = -1; @@ -90,7 +102,9 @@ public final class BinaryDictIOUtils { final boolean isMovedGroup = BinaryDictInputOutput.isMovedGroup(info.mFlags, formatOptions); - if (!isMovedGroup + final boolean isDeletedGroup = BinaryDictInputOutput.isDeletedGroup(info.mFlags, + formatOptions); + if (!isMovedGroup && !isDeletedGroup && info.mFrequency != FusionDictionary.CharGroup.NOT_A_TERMINAL) {// found word words.put(info.mOriginalAddress, new String(pushedChars, 0, index)); frequencies.put(info.mOriginalAddress, info.mFrequency); @@ -165,19 +179,19 @@ public final class BinaryDictIOUtils { if (wordPos >= wordLen) return FormatSpec.NOT_VALID_WORD; do { - int groupOffset = buffer.position() - header.mHeaderSize; final int charGroupCount = BinaryDictInputOutput.readCharGroupCount(buffer); - groupOffset += BinaryDictInputOutput.getGroupCountSize(charGroupCount); - boolean foundNextCharGroup = false; for (int i = 0; i < charGroupCount; ++i) { final int charGroupPos = buffer.position(); final CharGroupInfo currentInfo = BinaryDictInputOutput.readCharGroup(buffer, buffer.position(), header.mFormatOptions); - if (BinaryDictInputOutput.isMovedGroup(currentInfo.mFlags, - header.mFormatOptions)) { - continue; - } + final boolean isMovedGroup = + BinaryDictInputOutput.isMovedGroup(currentInfo.mFlags, + header.mFormatOptions); + final boolean isDeletedGroup = + BinaryDictInputOutput.isDeletedGroup(currentInfo.mFlags, + header.mFormatOptions); + if (isMovedGroup) continue; boolean same = true; for (int p = 0, j = word.offsetByCodePoints(0, wordPos); p < currentInfo.mCharacters.length; @@ -192,7 +206,8 @@ public final class BinaryDictIOUtils { if (same) { // found the group matches the word. if (wordPos + currentInfo.mCharacters.length == wordLen) { - if (currentInfo.mFrequency == CharGroup.NOT_A_TERMINAL) { + if (currentInfo.mFrequency == CharGroup.NOT_A_TERMINAL + || isDeletedGroup) { return FormatSpec.NOT_VALID_WORD; } else { return charGroupPos; @@ -206,7 +221,6 @@ public final class BinaryDictIOUtils { buffer.position(currentInfo.mChildrenAddress); break; } - groupOffset = currentInfo.mEndAddress; } // If we found the next char group, it is under the file pointer. @@ -228,6 +242,10 @@ public final class BinaryDictIOUtils { return FormatSpec.NOT_VALID_WORD; } + private static int markAsDeleted(final int flags) { + return (flags & (~FormatSpec.MASK_GROUP_ADDRESS_TYPE)) | FormatSpec.FLAG_IS_DELETED; + } + /** * Delete the word from the binary file. * @@ -245,21 +263,58 @@ public final class BinaryDictIOUtils { buffer.position(wordPosition); final int flags = buffer.readUnsignedByte(); - final int newFlags = flags ^ FormatSpec.FLAG_IS_TERMINAL; buffer.position(wordPosition); - buffer.put((byte)newFlags); + buffer.put((byte)markAsDeleted(flags)); } - private static void putSInt24(final FusionDictionaryBufferInterface buffer, + /** + * @return the size written, in bytes. Always 3 bytes. + */ + private static int writeSInt24ToBuffer(final FusionDictionaryBufferInterface buffer, final int value) { final int absValue = Math.abs(value); buffer.put((byte)(((value < 0 ? 0x80 : 0) | (absValue >> 16)) & 0xFF)); buffer.put((byte)((absValue >> 8) & 0xFF)); buffer.put((byte)(absValue & 0xFF)); + return 3; } /** - * Update a parent address in a CharGroup that is addressed by groupOriginAddress. + * @return the size written, in bytes. Always 3 bytes. + */ + private static int writeSInt24ToStream(final OutputStream destination, final int value) + throws IOException { + final int absValue = Math.abs(value); + destination.write((byte)(((value < 0 ? 0x80 : 0) | (absValue >> 16)) & 0xFF)); + destination.write((byte)((absValue >> 8) & 0xFF)); + destination.write((byte)(absValue & 0xFF)); + return 3; + } + + /** + * @return the size written, in bytes. 1, 2, or 3 bytes. + */ + private static int writeVariableAddress(final OutputStream destination, final int value) + throws IOException { + switch (BinaryDictInputOutput.getByteSize(value)) { + case 1: + destination.write((byte)value); + break; + case 2: + destination.write((byte)(0xFF & (value >> 8))); + destination.write((byte)(0xFF & value)); + break; + case 3: + destination.write((byte)(0xFF & (value >> 16))); + destination.write((byte)(0xFF & (value >> 8))); + destination.write((byte)(0xFF & value)); + break; + } + return BinaryDictInputOutput.getByteSize(value); + } + + /** + * Update a parent address in a CharGroup that is referred to by groupOriginAddress. * * @param buffer the buffer to write. * @param groupOriginAddress the address of the group. @@ -275,8 +330,621 @@ public final class BinaryDictIOUtils { throw new RuntimeException("this file format does not support parent addresses"); } final int flags = buffer.readUnsignedByte(); + if (BinaryDictInputOutput.isMovedGroup(flags, formatOptions)) { + // if the group is moved, the parent address is stored in the destination group. + // We are guaranteed to process the destination group later, so there is no need to + // update anything here. + buffer.position(originalPosition); + return; + } + if (DBG) { + MakedictLog.d("update parent address flags=" + flags + ", " + groupOriginAddress); + } final int parentOffset = newParentAddress - groupOriginAddress; - putSInt24(buffer, parentOffset); + writeSInt24ToBuffer(buffer, parentOffset); buffer.position(originalPosition); } + + private static void skipCharGroup(final FusionDictionaryBufferInterface buffer, + final FormatOptions formatOptions) { + final int flags = buffer.readUnsignedByte(); + BinaryDictInputOutput.readParentAddress(buffer, formatOptions); + skipString(buffer, (flags & FormatSpec.FLAG_HAS_MULTIPLE_CHARS) != 0); + BinaryDictInputOutput.readChildrenAddress(buffer, flags, formatOptions); + if ((flags & FormatSpec.FLAG_IS_TERMINAL) != 0) buffer.readUnsignedByte(); + if ((flags & FormatSpec.FLAG_HAS_SHORTCUT_TARGETS) != 0) { + final int shortcutsSize = buffer.readUnsignedShort(); + buffer.position(buffer.position() + shortcutsSize + - FormatSpec.GROUP_SHORTCUT_LIST_SIZE_SIZE); + } + if ((flags & FormatSpec.FLAG_HAS_BIGRAMS) != 0) { + int bigramCount = 0; + while (bigramCount++ < FormatSpec.MAX_BIGRAMS_IN_A_GROUP) { + final int bigramFlags = buffer.readUnsignedByte(); + switch (bigramFlags & FormatSpec.MASK_ATTRIBUTE_ADDRESS_TYPE) { + case FormatSpec.FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE: + buffer.readUnsignedByte(); + break; + case FormatSpec.FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES: + buffer.readUnsignedShort(); + break; + case FormatSpec.FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES: + buffer.readUnsignedInt24(); + break; + } + if ((bigramFlags & FormatSpec.FLAG_ATTRIBUTE_HAS_NEXT) == 0) break; + } + if (bigramCount >= FormatSpec.MAX_BIGRAMS_IN_A_GROUP) { + throw new RuntimeException("Too many bigrams in a group."); + } + } + } + + /** + * Update parent addresses in a Node that is referred to by nodeOriginAddress. + * + * @param buffer the buffer to be modified. + * @param nodeOriginAddress the address of a modified Node. + * @param newParentAddress the address to be written. + * @param formatOptions file format options. + */ + public static void updateParentAddresses(final FusionDictionaryBufferInterface buffer, + final int nodeOriginAddress, final int newParentAddress, + final FormatOptions formatOptions) { + final int originalPosition = buffer.position(); + buffer.position(nodeOriginAddress); + do { + final int count = BinaryDictInputOutput.readCharGroupCount(buffer); + for (int i = 0; i < count; ++i) { + updateParentAddress(buffer, buffer.position(), newParentAddress, formatOptions); + skipCharGroup(buffer, formatOptions); + } + final int forwardLinkAddress = buffer.readUnsignedInt24(); + buffer.position(forwardLinkAddress); + } while (formatOptions.mSupportsDynamicUpdate + && buffer.position() != FormatSpec.NO_FORWARD_LINK_ADDRESS); + buffer.position(originalPosition); + } + + private static void skipString(final FusionDictionaryBufferInterface buffer, + final boolean hasMultipleChars) { + if (hasMultipleChars) { + int character = CharEncoding.readChar(buffer); + while (character != FormatSpec.INVALID_CHARACTER) { + character = CharEncoding.readChar(buffer); + } + } else { + CharEncoding.readChar(buffer); + } + } + + /** + * Write a string to a stream. + * + * @param destination the stream to write. + * @param word the string to be written. + * @return the size written, in bytes. + * @throws IOException + */ + private static int writeString(final OutputStream destination, final String word) + throws IOException { + int size = 0; + final int length = word.length(); + for (int i = 0; i < length; i = word.offsetByCodePoints(i, 1)) { + final int codePoint = word.codePointAt(i); + if (CharEncoding.getCharSize(codePoint) == 1) { + destination.write((byte)codePoint); + size++; + } else { + destination.write((byte)(0xFF & (codePoint >> 16))); + destination.write((byte)(0xFF & (codePoint >> 8))); + destination.write((byte)(0xFF & codePoint)); + size += 3; + } + } + destination.write((byte)FormatSpec.GROUP_CHARACTERS_TERMINATOR); + size += FormatSpec.GROUP_TERMINATOR_SIZE; + return size; + } + + /** + * Update a children address in a CharGroup that is addressed by groupOriginAddress. + * + * @param buffer the buffer to write. + * @param groupOriginAddress the address of the group. + * @param newChildrenAddress the absolute address of the child. + * @param formatOptions file format options. + */ + public static void updateChildrenAddress(final FusionDictionaryBufferInterface buffer, + final int groupOriginAddress, final int newChildrenAddress, + final FormatOptions formatOptions) { + final int originalPosition = buffer.position(); + buffer.position(groupOriginAddress); + final int flags = buffer.readUnsignedByte(); + final int parentAddress = BinaryDictInputOutput.readParentAddress(buffer, formatOptions); + skipString(buffer, (flags & FormatSpec.FLAG_HAS_MULTIPLE_CHARS) != 0); + if ((flags & FormatSpec.FLAG_IS_TERMINAL) != 0) buffer.readUnsignedByte(); + final int childrenOffset = newChildrenAddress == FormatSpec.NO_CHILDREN_ADDRESS + ? FormatSpec.NO_CHILDREN_ADDRESS : newChildrenAddress - buffer.position(); + writeSInt24ToBuffer(buffer, childrenOffset); + buffer.position(originalPosition); + } + + /** + * Write a char group to an output stream. + * A char group is an in-memory representation of a node in trie. + * A char group info is an on-disk representation of a node. + * + * @param destination the stream to write. + * @param info the char group info to be written. + * @return the size written, in bytes. + */ + public static int writeCharGroup(final OutputStream destination, final CharGroupInfo info) + throws IOException { + int size = FormatSpec.GROUP_FLAGS_SIZE; + destination.write((byte)info.mFlags); + final int parentOffset = info.mParentAddress == FormatSpec.NO_PARENT_ADDRESS ? + FormatSpec.NO_PARENT_ADDRESS : info.mParentAddress - info.mOriginalAddress; + size += writeSInt24ToStream(destination, parentOffset); + + for (int i = 0; i < info.mCharacters.length; ++i) { + if (CharEncoding.getCharSize(info.mCharacters[i]) == 1) { + destination.write((byte)info.mCharacters[i]); + size++; + } else { + size += writeSInt24ToStream(destination, info.mCharacters[i]); + } + } + if (info.mCharacters.length > 1) { + destination.write((byte)FormatSpec.GROUP_CHARACTERS_TERMINATOR); + size++; + } + + if ((info.mFlags & FormatSpec.FLAG_IS_TERMINAL) != 0) { + destination.write((byte)info.mFrequency); + size++; + } + + if (DBG) { + MakedictLog.d("writeCharGroup origin=" + info.mOriginalAddress + ", size=" + size + + ", child=" + info.mChildrenAddress + ", characters =" + + new String(info.mCharacters, 0, info.mCharacters.length)); + } + final int childrenOffset = info.mChildrenAddress == FormatSpec.NO_CHILDREN_ADDRESS ? + 0 : info.mChildrenAddress - (info.mOriginalAddress + size); + writeSInt24ToStream(destination, childrenOffset); + size += FormatSpec.SIGNED_CHILDREN_ADDRESS_SIZE; + + if (info.mShortcutTargets != null && info.mShortcutTargets.size() > 0) { + final int shortcutListSize = + BinaryDictInputOutput.getShortcutListSize(info.mShortcutTargets); + destination.write((byte)(shortcutListSize >> 8)); + destination.write((byte)(shortcutListSize & 0xFF)); + size += 2; + final Iterator<WeightedString> shortcutIterator = info.mShortcutTargets.iterator(); + while (shortcutIterator.hasNext()) { + final WeightedString target = shortcutIterator.next(); + destination.write((byte)BinaryDictInputOutput.makeShortcutFlags( + shortcutIterator.hasNext(), target.mFrequency)); + size++; + size += writeString(destination, target.mWord); + } + } + + if (info.mBigrams != null) { + // TODO: Consolidate this code with the code that computes the size of the bigram list + // in BinaryDictionaryInputOutput#computeActualNodeSize + for (int i = 0; i < info.mBigrams.size(); ++i) { + final int bigramOffset = info.mBigrams.get(i).mAddress - info.mOriginalAddress; + final int bigramFrequency = info.mBigrams.get(i).mFrequency; + int bigramFlags = (i < info.mBigrams.size() - 1) + ? FormatSpec.FLAG_ATTRIBUTE_HAS_NEXT : 0; + bigramFlags |= (bigramOffset < 0) ? FormatSpec.FLAG_ATTRIBUTE_OFFSET_NEGATIVE : 0; + switch (BinaryDictInputOutput.getByteSize(bigramOffset)) { + case 1: + bigramFlags |= FormatSpec.FLAG_ATTRIBUTE_ADDRESS_TYPE_ONEBYTE; + break; + case 2: + bigramFlags |= FormatSpec.FLAG_ATTRIBUTE_ADDRESS_TYPE_TWOBYTES; + break; + case 3: + bigramFlags |= FormatSpec.FLAG_ATTRIBUTE_ADDRESS_TYPE_THREEBYTES; + break; + } + bigramFlags |= bigramFrequency & FormatSpec.FLAG_ATTRIBUTE_FREQUENCY; + destination.write((byte)bigramFlags); + size++; + size += writeVariableAddress(destination, Math.abs(bigramOffset)); + } + } + return size; + } + + private static void updateForwardLink(final FusionDictionaryBufferInterface buffer, + final int nodeOriginAddress, final int newNodeAddress, + final FormatOptions formatOptions) { + buffer.position(nodeOriginAddress); + int jumpCount = 0; + while (jumpCount++ < MAX_JUMPS) { + final int count = BinaryDictInputOutput.readCharGroupCount(buffer); + for (int i = 0; i < count; ++i) skipCharGroup(buffer, formatOptions); + final int forwardLinkAddress = buffer.readUnsignedInt24(); + if (forwardLinkAddress == FormatSpec.NO_FORWARD_LINK_ADDRESS) { + buffer.position(buffer.position() - FormatSpec.FORWARD_LINK_ADDRESS_SIZE); + writeSInt24ToBuffer(buffer, newNodeAddress); + return; + } + buffer.position(forwardLinkAddress); + } + if (DBG && jumpCount >= MAX_JUMPS) { + throw new RuntimeException("too many jumps, probably a bug."); + } + } + + /** + * Helper method to move a char group to the tail of the file. + */ + private static int moveCharGroup(final OutputStream destination, + final FusionDictionaryBufferInterface buffer, final CharGroupInfo info, + final int nodeOriginAddress, final int oldGroupAddress, + final FormatOptions formatOptions) throws IOException { + updateParentAddress(buffer, oldGroupAddress, buffer.limit() + 1, formatOptions); + buffer.position(oldGroupAddress); + final int currentFlags = buffer.readUnsignedByte(); + buffer.position(oldGroupAddress); + buffer.put((byte)(FormatSpec.FLAG_IS_MOVED | (currentFlags + & (~FormatSpec.MASK_MOVE_AND_DELETE_FLAG)))); + int size = FormatSpec.GROUP_FLAGS_SIZE; + updateForwardLink(buffer, nodeOriginAddress, buffer.limit(), formatOptions); + size += writeNode(destination, new CharGroupInfo[] { info }); + return size; + } + + /** + * Compute the size of the char group. + */ + private static int computeGroupSize(final CharGroupInfo info, + final FormatOptions formatOptions) { + int size = FormatSpec.GROUP_FLAGS_SIZE + FormatSpec.PARENT_ADDRESS_SIZE + + BinaryDictInputOutput.getGroupCharactersSize(info.mCharacters) + + BinaryDictInputOutput.getChildrenAddressSize(info.mFlags, formatOptions); + if ((info.mFlags & FormatSpec.FLAG_IS_TERMINAL) != 0) { + size += FormatSpec.GROUP_FREQUENCY_SIZE; + } + if (info.mShortcutTargets != null && !info.mShortcutTargets.isEmpty()) { + size += BinaryDictInputOutput.getShortcutListSize(info.mShortcutTargets); + } + if (info.mBigrams != null) { + for (final PendingAttribute attr : info.mBigrams) { + size += FormatSpec.GROUP_FLAGS_SIZE; + size += BinaryDictInputOutput.getByteSize(attr.mAddress); + } + } + return size; + } + + /** + * Write a node to the stream. + * + * @param destination the stream to write. + * @param infos groups to be written. + * @return the size written, in bytes. + * @throws IOException + */ + private static int writeNode(final OutputStream destination, final CharGroupInfo[] infos) + throws IOException { + int size = BinaryDictInputOutput.getGroupCountSize(infos.length); + switch (BinaryDictInputOutput.getGroupCountSize(infos.length)) { + case 1: + destination.write((byte)infos.length); + break; + case 2: + destination.write((byte)(infos.length >> 8)); + destination.write((byte)(infos.length & 0xFF)); + break; + default: + throw new RuntimeException("Invalid group count size."); + } + for (final CharGroupInfo info : infos) size += writeCharGroup(destination, info); + writeSInt24ToStream(destination, FormatSpec.NO_FORWARD_LINK_ADDRESS); + return size + FormatSpec.FORWARD_LINK_ADDRESS_SIZE; + } + + /** + * Move a group that is referred to by oldGroupOrigin to the tail of the file. + * And set the children address to the byte after the group. + * + * @param nodeOrigin the address of the tail of the file. + * @param characters + * @param length + * @param flags + * @param frequency + * @param parentAddress + * @param shortcutTargets + * @param bigrams + * @param destination the stream representing the tail of the file. + * @param buffer the buffer representing the (constant-size) body of the file. + * @param oldNodeOrigin + * @param oldGroupOrigin + * @param formatOptions + * @return the size written, in bytes. + * @throws IOException + */ + private static int moveGroup(final int nodeOrigin, final int[] characters, final int length, + final int flags, final int frequency, final int parentAddress, + final ArrayList<WeightedString> shortcutTargets, + final ArrayList<PendingAttribute> bigrams, final OutputStream destination, + final FusionDictionaryBufferInterface buffer, final int oldNodeOrigin, + final int oldGroupOrigin, final FormatOptions formatOptions) throws IOException { + int size = 0; + final int newGroupOrigin = nodeOrigin + 1; + final int[] writtenCharacters = Arrays.copyOfRange(characters, 0, length); + final CharGroupInfo tmpInfo = new CharGroupInfo(newGroupOrigin, -1 /* endAddress */, + flags, writtenCharacters, frequency, parentAddress, FormatSpec.NO_CHILDREN_ADDRESS, + shortcutTargets, bigrams); + size = computeGroupSize(tmpInfo, formatOptions); + final CharGroupInfo newInfo = new CharGroupInfo(newGroupOrigin, newGroupOrigin + size, + flags, writtenCharacters, frequency, parentAddress, + nodeOrigin + 1 + size + FormatSpec.FORWARD_LINK_ADDRESS_SIZE, shortcutTargets, + bigrams); + moveCharGroup(destination, buffer, newInfo, oldNodeOrigin, oldGroupOrigin, formatOptions); + return 1 + size + FormatSpec.FORWARD_LINK_ADDRESS_SIZE; + } + + /** + * Insert a word into a binary dictionary. + * + * @param buffer + * @param destination + * @param word + * @param frequency + * @param bigramStrings + * @param shortcuts + * @throws IOException + * @throws UnsupportedFormatException + */ + // TODO: Support batch insertion. + public static void insertWord(final FusionDictionaryBufferInterface buffer, + final OutputStream destination, final String word, final int frequency, + final ArrayList<WeightedString> bigramStrings, + final ArrayList<WeightedString> shortcuts, final boolean isNotAWord, + final boolean isBlackListEntry) + throws IOException, UnsupportedFormatException { + final ArrayList<PendingAttribute> bigrams = new ArrayList<PendingAttribute>(); + if (bigramStrings != null) { + for (final WeightedString bigram : bigramStrings) { + int position = getTerminalPosition(buffer, bigram.mWord); + if (position == FormatSpec.NOT_VALID_WORD) { + // TODO: figure out what is the correct thing to do here. + } else { + bigrams.add(new PendingAttribute(position, bigram.mFrequency)); + } + } + } + + final boolean isTerminal = true; + final boolean hasBigrams = !bigrams.isEmpty(); + final boolean hasShortcuts = shortcuts != null && !shortcuts.isEmpty(); + + // find the insert position of the word. + if (buffer.position() != 0) buffer.position(0); + final FileHeader header = BinaryDictInputOutput.readHeader(buffer); + + int wordPos = 0, address = buffer.position(), nodeOriginAddress = buffer.position(); + final int[] codePoints = FusionDictionary.getCodePoints(word); + final int wordLen = codePoints.length; + + for (int depth = 0; depth < Constants.Dictionary.MAX_WORD_LENGTH; ++depth) { + if (wordPos >= wordLen) break; + nodeOriginAddress = buffer.position(); + int nodeParentAddress = -1; + final int charGroupCount = BinaryDictInputOutput.readCharGroupCount(buffer); + boolean foundNextGroup = false; + + for (int i = 0; i < charGroupCount; ++i) { + address = buffer.position(); + final CharGroupInfo currentInfo = BinaryDictInputOutput.readCharGroup(buffer, + buffer.position(), header.mFormatOptions); + final boolean isMovedGroup = BinaryDictInputOutput.isMovedGroup(currentInfo.mFlags, + header.mFormatOptions); + if (isMovedGroup) continue; + nodeParentAddress = (currentInfo.mParentAddress == FormatSpec.NO_PARENT_ADDRESS) + ? FormatSpec.NO_PARENT_ADDRESS : currentInfo.mParentAddress + address; + boolean matched = true; + for (int p = 0; p < currentInfo.mCharacters.length; ++p) { + if (wordPos + p >= wordLen) { + /* + * splitting + * before + * abcd - ef + * + * insert "abc" + * + * after + * abc - d - ef + */ + final int newNodeAddress = buffer.limit(); + final int flags = BinaryDictInputOutput.makeCharGroupFlags(p > 1, + isTerminal, 0, hasShortcuts, hasBigrams, false /* isNotAWord */, + false /* isBlackListEntry */, header.mFormatOptions); + int written = moveGroup(newNodeAddress, currentInfo.mCharacters, p, flags, + frequency, nodeParentAddress, shortcuts, bigrams, destination, + buffer, nodeOriginAddress, address, header.mFormatOptions); + + final int[] characters2 = Arrays.copyOfRange(currentInfo.mCharacters, p, + currentInfo.mCharacters.length); + if (currentInfo.mChildrenAddress != FormatSpec.NO_CHILDREN_ADDRESS) { + updateParentAddresses(buffer, currentInfo.mChildrenAddress, + newNodeAddress + written + 1, header.mFormatOptions); + } + final CharGroupInfo newInfo2 = new CharGroupInfo( + newNodeAddress + written + 1, -1 /* endAddress */, + currentInfo.mFlags, characters2, currentInfo.mFrequency, + newNodeAddress + 1, currentInfo.mChildrenAddress, + currentInfo.mShortcutTargets, currentInfo.mBigrams); + writeNode(destination, new CharGroupInfo[] { newInfo2 }); + return; + } else if (codePoints[wordPos + p] != currentInfo.mCharacters[p]) { + if (p > 0) { + /* + * splitting + * before + * ab - cd + * + * insert "ac" + * + * after + * a - b - cd + * | + * - c + */ + + final int newNodeAddress = buffer.limit(); + final int childrenAddress = currentInfo.mChildrenAddress; + + // move prefix + final int prefixFlags = BinaryDictInputOutput.makeCharGroupFlags(p > 1, + false /* isTerminal */, 0 /* childrenAddressSize*/, + false /* hasShortcut */, false /* hasBigrams */, + false /* isNotAWord */, false /* isBlackListEntry */, + header.mFormatOptions); + int written = moveGroup(newNodeAddress, currentInfo.mCharacters, p, + prefixFlags, -1 /* frequency */, nodeParentAddress, null, null, + destination, buffer, nodeOriginAddress, address, + header.mFormatOptions); + + final int[] suffixCharacters = Arrays.copyOfRange( + currentInfo.mCharacters, p, currentInfo.mCharacters.length); + if (currentInfo.mChildrenAddress != FormatSpec.NO_CHILDREN_ADDRESS) { + updateParentAddresses(buffer, currentInfo.mChildrenAddress, + newNodeAddress + written + 1, header.mFormatOptions); + } + final int suffixFlags = BinaryDictInputOutput.makeCharGroupFlags( + suffixCharacters.length > 1, + (currentInfo.mFlags & FormatSpec.FLAG_IS_TERMINAL) != 0, + 0 /* childrenAddressSize */, + (currentInfo.mFlags & FormatSpec.FLAG_HAS_SHORTCUT_TARGETS) + != 0, + (currentInfo.mFlags & FormatSpec.FLAG_HAS_BIGRAMS) != 0, + isNotAWord, isBlackListEntry, header.mFormatOptions); + final CharGroupInfo suffixInfo = new CharGroupInfo( + newNodeAddress + written + 1, -1 /* endAddress */, suffixFlags, + suffixCharacters, currentInfo.mFrequency, newNodeAddress + 1, + currentInfo.mChildrenAddress, currentInfo.mShortcutTargets, + currentInfo.mBigrams); + written += computeGroupSize(suffixInfo, header.mFormatOptions) + 1; + + final int[] newCharacters = Arrays.copyOfRange(codePoints, wordPos + p, + codePoints.length); + final int flags = BinaryDictInputOutput.makeCharGroupFlags( + newCharacters.length > 1, isTerminal, + 0 /* childrenAddressSize */, hasShortcuts, hasBigrams, + isNotAWord, isBlackListEntry, header.mFormatOptions); + final CharGroupInfo newInfo = new CharGroupInfo( + newNodeAddress + written, -1 /* endAddress */, flags, + newCharacters, frequency, newNodeAddress + 1, + FormatSpec.NO_CHILDREN_ADDRESS, shortcuts, bigrams); + writeNode(destination, new CharGroupInfo[] { suffixInfo, newInfo }); + return; + } + matched = false; + break; + } + } + + if (matched) { + if (wordPos + currentInfo.mCharacters.length == wordLen) { + // the word exists in the dictionary. + // only update group. + final int newNodeAddress = buffer.limit(); + final boolean hasMultipleChars = currentInfo.mCharacters.length > 1; + final int flags = BinaryDictInputOutput.makeCharGroupFlags(hasMultipleChars, + isTerminal, 0 /* childrenAddressSize */, hasShortcuts, hasBigrams, + isNotAWord, isBlackListEntry, header.mFormatOptions); + final CharGroupInfo newInfo = new CharGroupInfo(newNodeAddress + 1, + -1 /* endAddress */, flags, currentInfo.mCharacters, frequency, + nodeParentAddress, currentInfo.mChildrenAddress, shortcuts, + bigrams); + moveCharGroup(destination, buffer, newInfo, nodeOriginAddress, address, + header.mFormatOptions); + return; + } + wordPos += currentInfo.mCharacters.length; + if (currentInfo.mChildrenAddress == FormatSpec.NO_CHILDREN_ADDRESS) { + /* + * found the prefix of the word. + * make new node and link to the node from this group. + * + * before + * ab - cd + * + * insert "abcde" + * + * after + * ab - cd - e + */ + final int newNodeAddress = buffer.limit(); + updateChildrenAddress(buffer, address, newNodeAddress, + header.mFormatOptions); + final int newGroupAddress = newNodeAddress + 1; + final boolean hasMultipleChars = (wordLen - wordPos) > 1; + final int flags = BinaryDictInputOutput.makeCharGroupFlags(hasMultipleChars, + isTerminal, 0 /* childrenAddressSize */, hasShortcuts, hasBigrams, + isNotAWord, isBlackListEntry, header.mFormatOptions); + final int[] characters = Arrays.copyOfRange(codePoints, wordPos, wordLen); + final CharGroupInfo newInfo = new CharGroupInfo(newGroupAddress, -1, flags, + characters, frequency, address, FormatSpec.NO_CHILDREN_ADDRESS, + shortcuts, bigrams); + writeNode(destination, new CharGroupInfo[] { newInfo }); + return; + } + buffer.position(currentInfo.mChildrenAddress); + foundNextGroup = true; + break; + } + } + + if (foundNextGroup) continue; + + // reached the end of the array. + final int linkAddressPosition = buffer.position(); + int nextLink = buffer.readUnsignedInt24(); + if ((nextLink & MSB24) != 0) { + nextLink = -(nextLink & SINT24_MAX); + } + if (nextLink == FormatSpec.NO_FORWARD_LINK_ADDRESS) { + /* + * expand this node. + * + * before + * ab - cd + * + * insert "abef" + * + * after + * ab - cd + * | + * - ef + */ + + // change the forward link address. + final int newNodeAddress = buffer.limit(); + buffer.position(linkAddressPosition); + writeSInt24ToBuffer(buffer, newNodeAddress); + + final int[] characters = Arrays.copyOfRange(codePoints, wordPos, wordLen); + final int flags = BinaryDictInputOutput.makeCharGroupFlags(characters.length > 1, + isTerminal, 0 /* childrenAddressSize */, hasShortcuts, hasBigrams, + isNotAWord, isBlackListEntry, header.mFormatOptions); + final CharGroupInfo newInfo = new CharGroupInfo(newNodeAddress + 1, + -1 /* endAddress */, flags, characters, frequency, nodeParentAddress, + FormatSpec.NO_CHILDREN_ADDRESS, shortcuts, bigrams); + writeNode(destination, new CharGroupInfo[]{ newInfo }); + return; + } else { + depth--; + buffer.position(nextLink); + } + } + } } diff --git a/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java b/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java index b431a4da9..2d39094ff 100644 --- a/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java +++ b/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java @@ -124,8 +124,7 @@ public final class BinaryDictInputOutput { /** * A class grouping utility function for our specific character encoding. */ - private static final class CharEncoding { - + static final class CharEncoding { private static final int MINIMAL_ONE_BYTE_CHARACTER_VALUE = 0x20; private static final int MAXIMAL_ONE_BYTE_CHARACTER_VALUE = 0xFF; @@ -154,7 +153,7 @@ public final class BinaryDictInputOutput { * @param character the character code. * @return the size in binary encoded-form, either 1 or 3 bytes. */ - private static int getCharSize(final int character) { + static int getCharSize(final int character) { // See char encoding in FusionDictionary.java if (fitsOnOneByte(character)) return 1; if (FormatSpec.INVALID_CHARACTER == character) return 1; @@ -263,7 +262,7 @@ public final class BinaryDictInputOutput { * @param buffer the buffer, positioned over an encoded character. * @return the character code. */ - private static int readChar(final FusionDictionaryBufferInterface buffer) { + static int readChar(final FusionDictionaryBufferInterface buffer) { int character = buffer.readUnsignedByte(); if (!fitsOnOneByte(character)) { if (FormatSpec.GROUP_CHARACTERS_TERMINATOR == character) { @@ -277,6 +276,21 @@ public final class BinaryDictInputOutput { } /** + * Compute the binary size of the character array. + * + * If only one character, this is the size of this character. If many, it's the sum of their + * sizes + 1 byte for the terminator. + * + * @param characters the character array + * @return the size of the char array, including the terminator if any + */ + static int getGroupCharactersSize(final int[] characters) { + int size = CharEncoding.getCharArraySize(characters); + if (characters.length > 1) size += FormatSpec.GROUP_TERMINATOR_SIZE; + return size; + } + + /** * Compute the binary size of the character array in a group * * If only one character, this is the size of this character. If many, it's the sum of their @@ -286,9 +300,7 @@ public final class BinaryDictInputOutput { * @return the size of the char array, including the terminator if any */ private static int getGroupCharactersSize(final CharGroup group) { - int size = CharEncoding.getCharArraySize(group.mChars); - if (group.hasSeveralChars()) size += FormatSpec.GROUP_TERMINATOR_SIZE; - return size; + return getGroupCharactersSize(group.mChars); } /** @@ -338,7 +350,7 @@ public final class BinaryDictInputOutput { * This is known in advance and does not change according to position in the file * like address lists do. */ - private static int getShortcutListSize(final ArrayList<WeightedString> shortcutList) { + static int getShortcutListSize(final ArrayList<WeightedString> shortcutList) { if (null == shortcutList) return 0; int size = FormatSpec.GROUP_SHORTCUT_LIST_SIZE_SIZE; for (final WeightedString shortcut : shortcutList) { @@ -399,7 +411,16 @@ public final class BinaryDictInputOutput { * Helper method to check whether the group is moved. */ public static boolean isMovedGroup(final int flags, final FormatOptions options) { - return options.mSupportsDynamicUpdate && ((flags & FormatSpec.FLAG_IS_MOVED) == 1); + return options.mSupportsDynamicUpdate + && ((flags & FormatSpec.MASK_GROUP_ADDRESS_TYPE) == FormatSpec.FLAG_IS_MOVED); + } + + /** + * Helper method to check whether the group is deleted. + */ + public static boolean isDeletedGroup(final int flags, final FormatOptions formatOptions) { + return formatOptions.mSupportsDynamicUpdate + && ((flags & FormatSpec.MASK_GROUP_ADDRESS_TYPE) == FormatSpec.FLAG_IS_DELETED); } /** @@ -439,7 +460,7 @@ public final class BinaryDictInputOutput { * @param address the address * @return the byte size. */ - private static int getByteSize(final int address) { + static int getByteSize(final int address) { assert(address <= UINT24_MAX); if (!hasChildrenAddress(address)) { return 0; @@ -721,53 +742,60 @@ public final class BinaryDictInputOutput { return 3; } - private static byte makeCharGroupFlags(final CharGroup group, final int groupAddress, - final int childrenOffset, final FormatOptions formatOptions) { + /** + * Makes the flag value for a char group. + * + * @param hasMultipleChars whether the group has multiple chars. + * @param isTerminal whether the group is terminal. + * @param childrenAddressSize the size of a children address. + * @param hasShortcuts whether the group has shortcuts. + * @param hasBigrams whether the group has bigrams. + * @param isNotAWord whether the group is not a word. + * @param isBlackListEntry whether the group is a blacklist entry. + * @param formatOptions file format options. + * @return the flags + */ + static int makeCharGroupFlags(final boolean hasMultipleChars, final boolean isTerminal, + final int childrenAddressSize, final boolean hasShortcuts, final boolean hasBigrams, + final boolean isNotAWord, final boolean isBlackListEntry, + final FormatOptions formatOptions) { byte flags = 0; - if (group.mChars.length > 1) flags |= FormatSpec.FLAG_HAS_MULTIPLE_CHARS; - if (group.mFrequency >= 0) { - flags |= FormatSpec.FLAG_IS_TERMINAL; - } - if (null != group.mChildren) { - final int byteSize = formatOptions.mSupportsDynamicUpdate - ? FormatSpec.SIGNED_CHILDREN_ADDRESS_SIZE : getByteSize(childrenOffset); - switch (byteSize) { - case 1: - flags |= FormatSpec.FLAG_GROUP_ADDRESS_TYPE_ONEBYTE; - break; - case 2: - flags |= FormatSpec.FLAG_GROUP_ADDRESS_TYPE_TWOBYTES; - break; - case 3: - flags |= FormatSpec.FLAG_GROUP_ADDRESS_TYPE_THREEBYTES; - break; - default: - throw new RuntimeException("Node with a strange address"); - } - } else if (formatOptions.mSupportsDynamicUpdate) { - flags |= FormatSpec.FLAG_GROUP_ADDRESS_TYPE_THREEBYTES; - } - if (null != group.mShortcutTargets) { - if (DBG && 0 == group.mShortcutTargets.size()) { - throw new RuntimeException("0-sized shortcut list must be null"); - } - flags |= FormatSpec.FLAG_HAS_SHORTCUT_TARGETS; - } - if (null != group.mBigrams) { - if (DBG && 0 == group.mBigrams.size()) { - throw new RuntimeException("0-sized bigram list must be null"); + if (hasMultipleChars) flags |= FormatSpec.FLAG_HAS_MULTIPLE_CHARS; + if (isTerminal) flags |= FormatSpec.FLAG_IS_TERMINAL; + if (formatOptions.mSupportsDynamicUpdate) { + flags |= FormatSpec.FLAG_IS_NOT_MOVED; + } else if (true) { + switch (childrenAddressSize) { + case 1: + flags |= FormatSpec.FLAG_GROUP_ADDRESS_TYPE_ONEBYTE; + break; + case 2: + flags |= FormatSpec.FLAG_GROUP_ADDRESS_TYPE_TWOBYTES; + break; + case 3: + flags |= FormatSpec.FLAG_GROUP_ADDRESS_TYPE_THREEBYTES; + break; + case 0: + flags |= FormatSpec.FLAG_GROUP_ADDRESS_TYPE_NOADDRESS; + break; + default: + throw new RuntimeException("Node with a strange address"); } - flags |= FormatSpec.FLAG_HAS_BIGRAMS; - } - if (group.mIsNotAWord) { - flags |= FormatSpec.FLAG_IS_NOT_A_WORD; - } - if (group.mIsBlacklistEntry) { - flags |= FormatSpec.FLAG_IS_BLACKLISTED; } + if (hasShortcuts) flags |= FormatSpec.FLAG_HAS_SHORTCUT_TARGETS; + if (hasBigrams) flags |= FormatSpec.FLAG_HAS_BIGRAMS; + if (isNotAWord) flags |= FormatSpec.FLAG_IS_NOT_A_WORD; + if (isBlackListEntry) flags |= FormatSpec.FLAG_IS_BLACKLISTED; return flags; } + private static byte makeCharGroupFlags(final CharGroup group, final int groupAddress, + final int childrenOffset, final FormatOptions formatOptions) { + return (byte) makeCharGroupFlags(group.mChars.length > 1, group.mFrequency >= 0, + getByteSize(childrenOffset), group.mShortcutTargets != null, group.mBigrams != null, + group.mIsNotAWord, group.mIsBlacklistEntry, formatOptions); + } + /** * Makes the flag value for a bigram. * @@ -859,7 +887,7 @@ public final class BinaryDictInputOutput { * @param frequency the frequency of the attribute, 0..15 * @return the flags */ - private static final int makeShortcutFlags(final boolean more, final int frequency) { + static final int makeShortcutFlags(final boolean more, final int frequency) { return (more ? FormatSpec.FLAG_ATTRIBUTE_HAS_NEXT : 0) + (frequency & FormatSpec.FLAG_ATTRIBUTE_FREQUENCY); } @@ -897,6 +925,7 @@ public final class BinaryDictInputOutput { */ private static int writePlacedNode(final FusionDictionary dict, byte[] buffer, final Node node, final FormatOptions formatOptions) { + // TODO: Make the code in common with BinaryDictIOUtils#writeCharGroup int index = node.mCachedAddress; final int groupCount = node.mData.size(); @@ -1178,7 +1207,7 @@ public final class BinaryDictInputOutput { // Input methods: Read a binary dictionary to memory. // readDictionaryBinary is the public entry point for them. - private static int getChildrenAddressSize(final int optionFlags, + static int getChildrenAddressSize(final int optionFlags, final FormatOptions formatOptions) { if (formatOptions.mSupportsDynamicUpdate) return FormatSpec.SIGNED_CHILDREN_ADDRESS_SIZE; switch (optionFlags & FormatSpec.MASK_GROUP_ADDRESS_TYPE) { @@ -1194,7 +1223,7 @@ public final class BinaryDictInputOutput { } } - private static int readChildrenAddress(final FusionDictionaryBufferInterface buffer, + static int readChildrenAddress(final FusionDictionaryBufferInterface buffer, final int optionFlags, final FormatOptions options) { if (options.mSupportsDynamicUpdate) { final int address = buffer.readUnsignedInt24(); @@ -1219,7 +1248,7 @@ public final class BinaryDictInputOutput { } } - private static int readParentAddress(final FusionDictionaryBufferInterface buffer, + static int readParentAddress(final FusionDictionaryBufferInterface buffer, final FormatOptions formatOptions) { if (supportsDynamicUpdate(formatOptions)) { final int parentAddress = buffer.readUnsignedInt24(); @@ -1290,7 +1319,8 @@ public final class BinaryDictInputOutput { ArrayList<PendingAttribute> bigrams = null; if (0 != (flags & FormatSpec.FLAG_HAS_BIGRAMS)) { bigrams = new ArrayList<PendingAttribute>(); - while (true) { + int bigramCount = 0; + while (bigramCount++ < FormatSpec.MAX_BIGRAMS_IN_A_GROUP) { final int bigramFlags = buffer.readUnsignedByte(); ++addressPointer; final int sign = 0 == (bigramFlags & FormatSpec.FLAG_ATTRIBUTE_OFFSET_NEGATIVE) @@ -1318,6 +1348,9 @@ public final class BinaryDictInputOutput { bigramAddress)); if (0 == (bigramFlags & FormatSpec.FLAG_ATTRIBUTE_HAS_NEXT)) break; } + if (bigramCount >= FormatSpec.MAX_BIGRAMS_IN_A_GROUP) { + MakedictLog.d("too many bigrams in a group."); + } } return new CharGroupInfo(originalGroupAddress, addressPointer, flags, characters, frequency, parentAddress, childrenAddress, shortcutTargets, bigrams); diff --git a/java/src/com/android/inputmethod/latin/makedict/FormatSpec.java b/java/src/com/android/inputmethod/latin/makedict/FormatSpec.java index b3fbb9fb5..e88a4aebf 100644 --- a/java/src/com/android/inputmethod/latin/makedict/FormatSpec.java +++ b/java/src/com/android/inputmethod/latin/makedict/FormatSpec.java @@ -59,9 +59,11 @@ public final class FormatSpec { * l | 10 = 2 bytes : FLAG_GROUP_ADDRESS_TYPE_TWOBYTES * a | 11 = 3 bytes : FLAG_GROUP_ADDRESS_TYPE_THREEBYTES * g | ELSE - * s | is moved ? 2 bits, 11 = no - * | 01 = yes + * s | is moved ? 2 bits, 11 = no : FLAG_IS_NOT_MOVED + * | This must be the same as FLAG_GROUP_ADDRESS_TYPE_THREEBYTES + * | 01 = yes : FLAG_IS_MOVED * | the new address is stored in the same place as the parent address + * | is deleted? 10 = yes : FLAG_IS_DELETED * | has several chars ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_MULTIPLE_CHARS * | has a terminal ? 1 bit, 1 = yes, 0 = no : FLAG_IS_TERMINAL * | has shortcut targets ? 1 bit, 1 = yes, 0 = no : FLAG_HAS_SHORTCUT_TARGETS @@ -170,6 +172,7 @@ public final class FormatSpec { static final int PARENT_ADDRESS_SIZE = 3; static final int FORWARD_LINK_ADDRESS_SIZE = 3; + // These flags are used only in the static dictionary. static final int MASK_GROUP_ADDRESS_TYPE = 0xC0; static final int FLAG_GROUP_ADDRESS_TYPE_NOADDRESS = 0x00; static final int FLAG_GROUP_ADDRESS_TYPE_ONEBYTE = 0x40; @@ -183,7 +186,13 @@ public final class FormatSpec { static final int FLAG_HAS_BIGRAMS = 0x04; static final int FLAG_IS_NOT_A_WORD = 0x02; static final int FLAG_IS_BLACKLISTED = 0x01; - static final int FLAG_IS_MOVED = 0x40; + + // These flags are used only in the dynamic dictionary. + static final int MASK_MOVE_AND_DELETE_FLAG = 0xC0; + static final int FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE = 0x40; + static final int FLAG_IS_MOVED = 0x00 | FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE; + static final int FLAG_IS_NOT_MOVED = 0x80 | FIXED_BIT_OF_DYNAMIC_UPDATE_MOVE; + static final int FLAG_IS_DELETED = 0x80; static final int FLAG_ATTRIBUTE_HAS_NEXT = 0x80; static final int FLAG_ATTRIBUTE_OFFSET_NEGATIVE = 0x40; @@ -210,6 +219,7 @@ public final class FormatSpec { static final int MAX_CHARGROUPS_FOR_ONE_BYTE_CHARGROUP_COUNT = 0x7F; // 127 static final int MAX_CHARGROUPS_IN_A_NODE = 0x7FFF; // 32767 + static final int MAX_BIGRAMS_IN_A_GROUP = 10000; static final int MAX_TERMINAL_FREQUENCY = 255; static final int MAX_BIGRAM_FREQUENCY = 15; diff --git a/java/src/com/android/inputmethod/latin/makedict/FusionDictionary.java b/java/src/com/android/inputmethod/latin/makedict/FusionDictionary.java index 3193ef457..6f1faa192 100644 --- a/java/src/com/android/inputmethod/latin/makedict/FusionDictionary.java +++ b/java/src/com/android/inputmethod/latin/makedict/FusionDictionary.java @@ -279,7 +279,7 @@ public final class FusionDictionary implements Iterable<Word> { /** * Helper method to convert a String to an int array. */ - static private int[] getCodePoints(final String word) { + static int[] getCodePoints(final String word) { // TODO: this is a copy-paste of the contents of StringUtils.toCodePointArray, // which is not visible from the makedict package. Factor this code. final char[] characters = word.toCharArray(); |