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 }