1 /*

     2  * Copyright (c) 1999, 2012, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 /*

    27  *

    28  * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved

    29  * (C) Copyright IBM Corp. 1996 - 2002 - All Rights Reserved

    30  *

    31  * The original version of this source code and documentation

    32  * is copyrighted and owned by Taligent, Inc., a wholly-owned

    33  * subsidiary of IBM. These materials are provided under terms

    34  * of a License Agreement between Taligent and Sun. This technology

    35  * is protected by multiple US and International patents.

    36  *

    37  * This notice and attribution to Taligent may not be removed.

    38  * Taligent is a registered trademark of Taligent, Inc.

    39  */

    40 package sun.util.locale.provider;

    41 

    42 import java.io.BufferedInputStream;

    43 import java.io.IOException;

    44 import java.security.AccessController;

    45 import java.security.PrivilegedActionException;

    46 import java.security.PrivilegedExceptionAction;

    47 import java.util.MissingResourceException;

    48 import sun.text.CompactByteArray;

    49 import sun.text.SupplementaryCharacterData;

    50 

    51 /**

    52  * This is the class that represents the list of known words used by

    53  * DictionaryBasedBreakIterator.  The conceptual data structure used

    54  * here is a trie: there is a node hanging off the root node for every

    55  * letter that can start a word.  Each of these nodes has a node hanging

    56  * off of it for every letter that can be the second letter of a word

    57  * if this node is the first letter, and so on.  The trie is represented

    58  * as a two-dimensional array that can be treated as a table of state

    59  * transitions.  Indexes are used to compress this array, taking

    60  * advantage of the fact that this array will always be very sparse.

    61  */

    62 class BreakDictionary {

    63 

    64     //=========================================================================

    65     // data members

    66     //=========================================================================

    67 

    68     /**

    69       * The version of the dictionary that was read in.

    70       */

    71     private static int supportedVersion = 1;

    72 

    73     /**

    74      * Maps from characters to column numbers.  The main use of this is to

    75      * avoid making room in the array for empty columns.

    76      */

    77     private CompactByteArray columnMap = null;

    78     private SupplementaryCharacterData supplementaryCharColumnMap = null;

    79 

    80     /**

    81      * The number of actual columns in the table

    82      */

    83     private int numCols;

    84 

    85     /**

    86      * Columns are organized into groups of 32.  This says how many

    87      * column groups.  (We could calculate this, but we store the

    88      * value to avoid having to repeatedly calculate it.)

    89      */

    90     private int numColGroups;

    91 

    92     /**

    93      * The actual compressed state table.  Each conceptual row represents

    94      * a state, and the cells in it contain the row numbers of the states

    95      * to transition to for each possible letter.  0 is used to indicate

    96      * an illegal combination of letters (i.e., the error state).  The

    97      * table is compressed by eliminating all the unpopulated (i.e., zero)

    98      * cells.  Multiple conceptual rows can then be doubled up in a single

    99      * physical row by sliding them up and possibly shifting them to one

   100      * side or the other so the populated cells don't collide.  Indexes

   101      * are used to identify unpopulated cells and to locate populated cells.

   102      */

   103     private short[] table = null;

   104 

   105     /**

   106      * This index maps logical row numbers to physical row numbers

   107      */

   108     private short[] rowIndex = null;

   109 

   110     /**

   111      * A bitmap is used to tell which cells in the comceptual table are

   112      * populated.  This array contains all the unique bit combinations

   113      * in that bitmap.  If the table is more than 32 columns wide,

   114      * successive entries in this array are used for a single row.

   115      */

   116     private int[] rowIndexFlags = null;

   117 

   118     /**

   119      * This index maps from a logical row number into the bitmap table above.

   120      * (This keeps us from storing duplicate bitmap combinations.)  Since there

   121      * are a lot of rows with only one populated cell, instead of wasting space

   122      * in the bitmap table, we just store a negative number in this index for

   123      * rows with one populated cell.  The absolute value of that number is

   124      * the column number of the populated cell.

   125      */

   126     private short[] rowIndexFlagsIndex = null;

   127 

   128     /**

   129      * For each logical row, this index contains a constant that is added to

   130      * the logical column number to get the physical column number

   131      */

   132     private byte[] rowIndexShifts = null;

   133 

   134     //=========================================================================

   135     // deserialization

   136     //=========================================================================

   137 

   138     BreakDictionary(String dictionaryName)

   139         throws IOException, MissingResourceException {

   140 

   141         readDictionaryFile(dictionaryName);

   142     }

   143 

   144     private void readDictionaryFile(final String dictionaryName)

   145         throws IOException, MissingResourceException {

   146 

   147         BufferedInputStream in;

   148         try {

   149             in = AccessController.doPrivileged(

   150                 new PrivilegedExceptionAction<BufferedInputStream>() {

   151                     @Override

   152                     public BufferedInputStream run() throws Exception {

   153                         return new BufferedInputStream(getClass().getResourceAsStream("/sun/text/resources/" + dictionaryName));

   154                     }

   155                 }

   156             );

   157         }

   158         catch (PrivilegedActionException e) {

   159             throw new InternalError(e.toString(), e);

   160         }

   161 

   162         byte[] buf = new byte[8];

   163         if (in.read(buf) != 8) {

   164             throw new MissingResourceException("Wrong data length",

   165                                                dictionaryName, "");

   166         }

   167 

   168         // check version

   169         int version = RuleBasedBreakIterator.getInt(buf, 0);

   170         if (version != supportedVersion) {

   171             throw new MissingResourceException("Dictionary version(" + version + ") is unsupported",

   172                                                            dictionaryName, "");

   173         }

   174 

   175         // get data size

   176         int len = RuleBasedBreakIterator.getInt(buf, 4);

   177         buf = new byte[len];

   178         if (in.read(buf) != len) {

   179             throw new MissingResourceException("Wrong data length",

   180                                                dictionaryName, "");

   181         }

   182 

   183         // close the stream

   184         in.close();

   185 

   186         int l;

   187         int offset = 0;

   188 

   189         // read in the column map for BMP characteres (this is serialized in

   190         // its internal form: an index array followed by a data array)

   191         l = RuleBasedBreakIterator.getInt(buf, offset);

   192         offset += 4;

   193         short[] temp = new short[l];

   194         for (int i = 0; i < l; i++, offset+=2) {

   195             temp[i] = RuleBasedBreakIterator.getShort(buf, offset);

   196         }

   197         l = RuleBasedBreakIterator.getInt(buf, offset);

   198         offset += 4;

   199         byte[] temp2 = new byte[l];

   200         for (int i = 0; i < l; i++, offset++) {

   201             temp2[i] = buf[offset];

   202         }

   203         columnMap = new CompactByteArray(temp, temp2);

   204 

   205         // read in numCols and numColGroups

   206         numCols = RuleBasedBreakIterator.getInt(buf, offset);

   207         offset += 4;

   208         numColGroups = RuleBasedBreakIterator.getInt(buf, offset);

   209         offset += 4;

   210 

   211         // read in the row-number index

   212         l = RuleBasedBreakIterator.getInt(buf, offset);

   213         offset += 4;

   214         rowIndex = new short[l];

   215         for (int i = 0; i < l; i++, offset+=2) {

   216             rowIndex[i] = RuleBasedBreakIterator.getShort(buf, offset);

   217         }

   218 

   219         // load in the populated-cells bitmap: index first, then bitmap list

   220         l = RuleBasedBreakIterator.getInt(buf, offset);

   221         offset += 4;

   222         rowIndexFlagsIndex = new short[l];

   223         for (int i = 0; i < l; i++, offset+=2) {

   224             rowIndexFlagsIndex[i] = RuleBasedBreakIterator.getShort(buf, offset);

   225         }

   226         l = RuleBasedBreakIterator.getInt(buf, offset);

   227         offset += 4;

   228         rowIndexFlags = new int[l];

   229         for (int i = 0; i < l; i++, offset+=4) {

   230             rowIndexFlags[i] = RuleBasedBreakIterator.getInt(buf, offset);

   231         }

   232 

   233         // load in the row-shift index

   234         l = RuleBasedBreakIterator.getInt(buf, offset);

   235         offset += 4;

   236         rowIndexShifts = new byte[l];

   237         for (int i = 0; i < l; i++, offset++) {

   238             rowIndexShifts[i] = buf[offset];

   239         }

   240 

   241         // load in the actual state table

   242         l = RuleBasedBreakIterator.getInt(buf, offset);

   243         offset += 4;

   244         table = new short[l];

   245         for (int i = 0; i < l; i++, offset+=2) {

   246             table[i] = RuleBasedBreakIterator.getShort(buf, offset);

   247         }

   248 

   249         // finally, prepare the column map for supplementary characters

   250         l = RuleBasedBreakIterator.getInt(buf, offset);

   251         offset += 4;

   252         int[] temp3 = new int[l];

   253         for (int i = 0; i < l; i++, offset+=4) {

   254             temp3[i] = RuleBasedBreakIterator.getInt(buf, offset);

   255         }

   256         supplementaryCharColumnMap = new SupplementaryCharacterData(temp3);

   257     }

   258 

   259     //=========================================================================

   260     // access to the words

   261     //=========================================================================

   262 

   263     /**

   264      * Uses the column map to map the character to a column number, then

   265      * passes the row and column number to getNextState()

   266      * @param row The current state

   267      * @param ch The character whose column we're interested in

   268      * @return The new state to transition to

   269      */

   270     public final short getNextStateFromCharacter(int row, int ch) {

   271         int col;

   272         if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {

   273             col = columnMap.elementAt((char)ch);

   274         } else {

   275             col = supplementaryCharColumnMap.getValue(ch);

   276         }

   277         return getNextState(row, col);

   278     }

   279 

   280     /**

   281      * Returns the value in the cell with the specified (logical) row and

   282      * column numbers.  In DictionaryBasedBreakIterator, the row number is

   283      * a state number, the column number is an input, and the return value

   284      * is the row number of the new state to transition to.  (0 is the

   285      * "error" state, and -1 is the "end of word" state in a dictionary)

   286      * @param row The row number of the current state

   287      * @param col The column number of the input character (0 means "not a

   288      * dictionary character")

   289      * @return The row number of the new state to transition to

   290      */

   291     public final short getNextState(int row, int col) {

   292         if (cellIsPopulated(row, col)) {

   293             // we map from logical to physical row number by looking up the

   294             // mapping in rowIndex; we map from logical column number to

   295             // physical column number by looking up a shift value for this

   296             // logical row and offsetting the logical column number by

   297             // the shift amount.  Then we can use internalAt() to actually

   298             // get the value out of the table.

   299             return internalAt(rowIndex[row], col + rowIndexShifts[row]);

   300         }

   301         else {

   302             return 0;

   303         }

   304     }

   305 

   306     /**

   307      * Given (logical) row and column numbers, returns true if the

   308      * cell in that position is populated

   309      */

   310     private boolean cellIsPopulated(int row, int col) {

   311         // look up the entry in the bitmap index for the specified row.

   312         // If it's a negative number, it's the column number of the only

   313         // populated cell in the row

   314         if (rowIndexFlagsIndex[row] < 0) {

   315             return col == -rowIndexFlagsIndex[row];

   316         }

   317 

   318         // if it's a positive number, it's the offset of an entry in the bitmap

   319         // list.  If the table is more than 32 columns wide, the bitmap is stored

   320         // successive entries in the bitmap list, so we have to divide the column

   321         // number by 32 and offset the number we got out of the index by the result.

   322         // Once we have the appropriate piece of the bitmap, test the appropriate

   323         // bit and return the result.

   324         else {

   325             int flags = rowIndexFlags[rowIndexFlagsIndex[row] + (col >> 5)];

   326             return (flags & (1 << (col & 0x1f))) != 0;

   327         }

   328     }

   329 

   330     /**

   331      * Implementation of getNextState() when we know the specified cell is

   332      * populated.

   333      * @param row The PHYSICAL row number of the cell

   334      * @param col The PHYSICAL column number of the cell

   335      * @return The value stored in the cell

   336      */

   337     private short internalAt(int row, int col) {

   338         // the table is a one-dimensional array, so this just does the math necessary

   339         // to treat it as a two-dimensional array (we don't just use a two-dimensional

   340         // array because two-dimensional arrays are inefficient in Java)

   341         return table[row * numCols + col];

   342     }

   343 }