/* * Copyright (c) 2005, 2009, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation.  Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. *//* ******************************************************************************* * (C) Copyright IBM Corp. and others, 1996-2009 - All Rights Reserved         * *                                                                             * * The original version of this source code and documentation is copyrighted   * * and owned by IBM, These materials are provided under terms of a License     * * Agreement between IBM and Sun. This technology is protected by multiple     * * US and International patents. This notice and attribution to IBM may not    * * to removed.                                                                 * ******************************************************************************* */ package sun.text.normalizer; import java.io.DataInputStream;import java.io.InputStream;import java.io.IOException; /** * <p>A trie is a kind of compressed, serializable table of values * associated with Unicode code points (0..0x10ffff).</p> * <p>This class defines the basic structure of a trie and provides methods * to <b>retrieve the offsets to the actual data</b>.</p> * <p>Data will be the form of an array of basic types, char or int.</p> * <p>The actual data format will have to be specified by the user in the * inner static interface com.ibm.icu.impl.Trie.DataManipulate.</p> * <p>This trie implementation is optimized for getting offset while walking * forward through a UTF-16 string. * Therefore, the simplest and fastest access macros are the * fromLead() and fromOffsetTrail() methods. * The fromBMP() method are a little more complicated; they get offsets even * for lead surrogate codepoints, while the fromLead() method get special * "folded" offsets for lead surrogate code units if there is relevant data * associated with them. * From such a folded offsets, an offset needs to be extracted to supply * to the fromOffsetTrail() methods. * To handle such supplementary codepoints, some offset information are kept * in the data.</p> * <p>Methods in com.ibm.icu.impl.Trie.DataManipulate are called to retrieve * that offset from the folded value for the lead surrogate unit.</p> * <p>For examples of use, see com.ibm.icu.impl.CharTrie or * com.ibm.icu.impl.IntTrie.</p> * @author synwee * @see com.ibm.icu.impl.CharTrie * @see com.ibm.icu.impl.IntTrie * @since release 2.1, Jan 01 2002 */public abstract class Trie{    // public class declaration ----------------------------------------     /**    * Character data in com.ibm.impl.Trie have different user-specified format    * for different purposes.    * This interface specifies methods to be implemented in order for    * com.ibm.impl.Trie, to surrogate offset information encapsulated within    * the data.    */    public static interface DataManipulate    {        /**        * Called by com.ibm.icu.impl.Trie to extract from a lead surrogate's        * data        * the index array offset of the indexes for that lead surrogate.        * @param value data value for a surrogate from the trie, including the        *        folding offset        * @return data offset or 0 if there is no data for the lead surrogate        */        public int getFoldingOffset(int value);    }     // default implementation    private static class DefaultGetFoldingOffset implements DataManipulate {        public int getFoldingOffset(int value) {            return value;        }    }     // protected constructor -------------------------------------------     /**    * Trie constructor for CharTrie use.    * @param inputStream ICU data file input stream which contains the    *                        trie    * @param dataManipulate object containing the information to parse the    *                       trie data    * @throws IOException thrown when input stream does not have the    *                        right header.    */    protected Trie(InputStream inputStream,                   DataManipulate  dataManipulate) throws IOException    {        DataInputStream input = new DataInputStream(inputStream);        // Magic number to authenticate the data.        int signature = input.readInt();        m_options_    = input.readInt();         if (!checkHeader(signature)) {            throw new IllegalArgumentException("ICU data file error: Trie header authentication failed, please check if you have the most updated ICU data file");        }         if(dataManipulate != null) {            m_dataManipulate_ = dataManipulate;        } else {            m_dataManipulate_ = new DefaultGetFoldingOffset();        }        m_isLatin1Linear_ = (m_options_ &                             HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_) != 0;        m_dataOffset_     = input.readInt();        m_dataLength_     = input.readInt();        unserialize(inputStream);    }     /**    * Trie constructor    * @param index array to be used for index    * @param options used by the trie    * @param dataManipulate object containing the information to parse the    *                       trie data    */    protected Trie(char index[], int options, DataManipulate dataManipulate)    {        m_options_ = options;        if(dataManipulate != null) {            m_dataManipulate_ = dataManipulate;        } else {            m_dataManipulate_ = new DefaultGetFoldingOffset();        }        m_isLatin1Linear_ = (m_options_ &                             HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_) != 0;        m_index_ = index;        m_dataOffset_ = m_index_.length;    }     // protected data members ------------------------------------------     /**    * Lead surrogate code points' index displacement in the index array.    * 0x10000-0xd800=0x2800    * 0x2800 >> INDEX_STAGE_1_SHIFT_    */    protected static final int LEAD_INDEX_OFFSET_ = 0x2800 >> 5;    /**    * Shift size for shifting right the input index. 1..9    */    protected static final int INDEX_STAGE_1_SHIFT_ = 5;    /**    * Shift size for shifting left the index array values.    * Increases possible data size with 16-bit index values at the cost    * of compactability.    * This requires blocks of stage 2 data to be aligned by    * DATA_GRANULARITY.    * 0..INDEX_STAGE_1_SHIFT    */    protected static final int INDEX_STAGE_2_SHIFT_ = 2;    /**     * Number of data values in a stage 2 (data array) block.     */    protected static final int DATA_BLOCK_LENGTH=1<<INDEX_STAGE_1_SHIFT_;    /**    * Mask for getting the lower bits from the input index.    * DATA_BLOCK_LENGTH - 1.    */    protected static final int INDEX_STAGE_3_MASK_ = DATA_BLOCK_LENGTH - 1;    /** Number of bits of a trail surrogate that are used in index table lookups. */    protected static final int SURROGATE_BLOCK_BITS=10-INDEX_STAGE_1_SHIFT_;    /**     * Number of index (stage 1) entries per lead surrogate.     * Same as number of index entries for 1024 trail surrogates,     * ==0x400>>INDEX_STAGE_1_SHIFT_     */    protected static final int SURROGATE_BLOCK_COUNT=(1<<SURROGATE_BLOCK_BITS);    /** Length of the BMP portion of the index (stage 1) array. */    protected static final int BMP_INDEX_LENGTH=0x10000>>INDEX_STAGE_1_SHIFT_;    /**    * Surrogate mask to use when shifting offset to retrieve supplementary    * values    */    protected static final int SURROGATE_MASK_ = 0x3FF;    /**    * Index or UTF16 characters    */    protected char m_index_[];    /**    * Internal TrieValue which handles the parsing of the data value.    * This class is to be implemented by the user    */    protected DataManipulate m_dataManipulate_;    /**    * Start index of the data portion of the trie. CharTrie combines    * index and data into a char array, so this is used to indicate the    * initial offset to the data portion.    * Note this index always points to the initial value.    */    protected int m_dataOffset_;    /**    * Length of the data array    */    protected int m_dataLength_;     // protected methods -----------------------------------------------     /**    * Gets the offset to the data which the surrogate pair points to.    * @param lead lead surrogate    * @param trail trailing surrogate    * @return offset to data    */    protected abstract int getSurrogateOffset(char lead, char trail);     /**    * Gets the value at the argument index    * @param index value at index will be retrieved    * @return 32 bit value    */    protected abstract int getValue(int index);     /**    * Gets the default initial value    * @return 32 bit value    */    protected abstract int getInitialValue();     /**    * Gets the offset to the data which the index ch after variable offset    * points to.    * Note for locating a non-supplementary character data offset, calling    * <p>    * getRawOffset(0, ch);    * </p>    * will do. Otherwise if it is a supplementary character formed by    * surrogates lead and trail. Then we would have to call getRawOffset()    * with getFoldingIndexOffset(). See getSurrogateOffset().    * @param offset index offset which ch is to start from    * @param ch index to be used after offset    * @return offset to the data    */    protected final int getRawOffset(int offset, char ch)    {        return (m_index_[offset + (ch >> INDEX_STAGE_1_SHIFT_)]                << INDEX_STAGE_2_SHIFT_)                + (ch & INDEX_STAGE_3_MASK_);    }     /**    * Gets the offset to data which the BMP character points to    * Treats a lead surrogate as a normal code point.    * @param ch BMP character    * @return offset to data    */    protected final int getBMPOffset(char ch)    {        return (ch >= UTF16.LEAD_SURROGATE_MIN_VALUE                && ch <= UTF16.LEAD_SURROGATE_MAX_VALUE)                ? getRawOffset(LEAD_INDEX_OFFSET_, ch)                : getRawOffset(0, ch);                // using a getRawOffset(ch) makes no diff    }     /**    * Gets the offset to the data which this lead surrogate character points    * to.    * Data at the returned offset may contain folding offset information for    * the next trailing surrogate character.    * @param ch lead surrogate character    * @return offset to data    */    protected final int getLeadOffset(char ch)    {       return getRawOffset(0, ch);    }     /**    * Internal trie getter from a code point.    * Could be faster(?) but longer with    *   if((c32)<=0xd7ff) { (result)=_TRIE_GET_RAW(trie, data, 0, c32); }    * Gets the offset to data which the codepoint points to    * @param ch codepoint    * @return offset to data    */    protected final int getCodePointOffset(int ch)    {        // if ((ch >> 16) == 0) slower        if (ch < 0) {            return -1;        } else if (ch < UTF16.LEAD_SURROGATE_MIN_VALUE) {            // fastpath for the part of the BMP below surrogates (D800) where getRawOffset() works            return getRawOffset(0, (char)ch);        } else if (ch < UTF16.SUPPLEMENTARY_MIN_VALUE) {            // BMP codepoint            return getBMPOffset((char)ch);        } else if (ch <= UCharacter.MAX_VALUE) {            // look at the construction of supplementary characters            // trail forms the ends of it.            return getSurrogateOffset(UTF16.getLeadSurrogate(ch),                                      (char)(ch & SURROGATE_MASK_));        } else {            // return -1 // if there is an error, in this case we return            return -1;        }    }     /**    * <p>Parses the inputstream and creates the trie index with it.</p>    * <p>This is overwritten by the child classes.    * @param inputStream input stream containing the trie information    * @exception IOException thrown when data reading fails.    */    protected void unserialize(InputStream inputStream) throws IOException    {        //indexLength is a multiple of 1024 >> INDEX_STAGE_2_SHIFT_        m_index_              = new char[m_dataOffset_];        DataInputStream input = new DataInputStream(inputStream);        for (int i = 0; i < m_dataOffset_; i ++) {             m_index_[i] = input.readChar();        }    }     /**    * Determines if this is a 32 bit trie    * @return true if options specifies this is a 32 bit trie    */    protected final boolean isIntTrie()    {        return (m_options_ & HEADER_OPTIONS_DATA_IS_32_BIT_) != 0;    }     /**    * Determines if this is a 16 bit trie    * @return true if this is a 16 bit trie    */    protected final boolean isCharTrie()    {        return (m_options_ & HEADER_OPTIONS_DATA_IS_32_BIT_) == 0;    }     // private data members --------------------------------------------     /**    * Latin 1 option mask    */    protected static final int HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_ = 0x200;    /**    * Constant number to authenticate the byte block    */    protected static final int HEADER_SIGNATURE_ = 0x54726965;    /**    * Header option formatting    */    private static final int HEADER_OPTIONS_SHIFT_MASK_ = 0xF;    protected static final int HEADER_OPTIONS_INDEX_SHIFT_ = 4;    protected static final int HEADER_OPTIONS_DATA_IS_32_BIT_ = 0x100;     /**    * Flag indicator for Latin quick access data block    */    private boolean m_isLatin1Linear_;     /**    * <p>Trie options field.</p>    * <p>options bit field:<br>    * 9  1 = Latin-1 data is stored linearly at data + DATA_BLOCK_LENGTH<br>    * 8  0 = 16-bit data, 1=32-bit data<br>    * 7..4  INDEX_STAGE_1_SHIFT   // 0..INDEX_STAGE_2_SHIFT<br>    * 3..0  INDEX_STAGE_2_SHIFT   // 1..9<br>    */    private int m_options_;     // private methods ---------------------------------------------------     /**    * Authenticates raw data header.    * Checking the header information, signature and options.    * @param signature This contains the options and type of a Trie    * @return true if the header is authenticated valid    */    private final boolean checkHeader(int signature)    {        // check the signature        // Trie in big-endian US-ASCII (0x54726965).        // Magic number to authenticate the data.        if (signature != HEADER_SIGNATURE_) {            return false;        }         if ((m_options_ & HEADER_OPTIONS_SHIFT_MASK_) !=                                                    INDEX_STAGE_1_SHIFT_ ||            ((m_options_ >> HEADER_OPTIONS_INDEX_SHIFT_) &                                                HEADER_OPTIONS_SHIFT_MASK_)                                                 != INDEX_STAGE_2_SHIFT_) {            return false;        }        return true;    }}