001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: /**
019: * @author Alexander Y. Kleymenov
020: * @version $Revision$
021: */package org.apache.harmony.security.provider.cert;
022:
023: import java.util.Arrays;
024:
025: /**
026: * The caching mechanism designed to speed up the process
027: * of Certificates/CRLs generation in the case of their repeated
028: * generation.
029: *
030: * It keeps correspondences between Objects (Certificates or CLRs)
031: * and arrays of bytes on the base of which the Objects have been generated,
032: * and provides the means to determine whether it contains the object built on
033: * the base of particular encoded form or not. If there are such
034: * objects they are returned from the cache, if not - newly generated
035: * objects can be saved in the cache.<br>
036: *
037: * The process of Certificate/CRL generation
038: * (implemented in <code>X509CertFactoryImpl</code>) is accompanied with
039: * prereading of the beginning of encoded form. This prefix is used to determine
040: * whether provided form is PEM encoding or not.<br>
041: *
042: * So the use of the prefix is the first point to (approximately)
043: * determine whether object to be generated is in the cache or not.
044: *
045: * The failure of the predetermination process tells us that there were not
046: * object generated from the encoded form with such prefix and we should
047: * generate (decode) the object. If predetermination is successful,
048: * we conduct the accurate search on the base of whole encoded form. <br>
049: *
050: * So to speed up the object generation process this caching mechanism provides
051: * the following functionality:<br>
052: *
053: * 1. With having of the beginning of the encoded form (prefix)
054: * it is possible to predetermine whether object has already been
055: * generated on the base of the encoding with the SIMILAR prefix or not.
056: * This process is not computationally expensive and takes a little time.
057: * But it prevents us from use of expensive full encoding
058: * search in the case of its failure.<br>
059: *
060: * 2. If predetermination ends with success, the whole encoding
061: * form should be provided to make the final answer: whether object has
062: * already been generated on the base of this PARTICULAR encoded form or not.
063: * If it is so - the cached object is returned from the cache,
064: * if not - new object should be generated and saved in the cache.<br>
065: *
066: * Note: The length of the prefixes of the encoded forms should not be
067: * less than correspondence (default value is 28).
068: */
069: public class Cache {
070:
071: // Hash code consist of 6 bytes: AABB00
072: // where:
073: // AA - 2 bytes for prefix hash
074: // value generated on the base of the prefix of encoding
075: // BB - 2 bytes for tail hash
076: // value generated on the base of the tail of encoding
077: // 00 - 2 reserved bytes equals to 0
078: //
079: // Note, that it is possible for 2 different arrays to have
080: // the similar hash codes.
081:
082: // The masks to work with hash codes:
083: // the hash code without the reserved bytes
084: private static final long HASH_MASK = 0xFFFFFFFFFFFF0000L;
085: // the hash code of the prefix
086: private static final long PREFIX_HASH_MASK = 0xFFFFFFFF00000000L;
087: // the index value contained in reserved bytes
088: private static final int INDEX_MASK = 0x00FFFF;
089:
090: // size of the cache
091: private final int cache_size;
092: // the number of bytes which will be used for array hash generation.
093: private final int prefix_size;
094:
095: // The following 3 arrays contain the information about cached objects.
096: // This information includes: hash of the array, encoded form of the object,
097: // and the object itself.
098: // The hash-encoding-object correspondence is made by means of index
099: // in the particular array. I.e. for index N hash contained in hashes[N]
100: // corresponds to the encoding contained in encodings[N] which corresponds
101: // to the object cached at cache[N]
102:
103: // array containing the hash codes of encodings
104: private final long[] hashes;
105: // array containing the encodings of the cached objects
106: private final byte[][] encodings;
107: // array containing the cached objects
108: private final Object[] cache;
109:
110: // This array is used to speed up the process of the search in the cache.
111: // This is an ordered array of the hash codes from 'hashes' array (described
112: // above) with last 2 (reserved) bytes equals to the index of
113: // the hash in the 'hashes' array. I.e. hash code ABCD00 with index 10 in
114: // the hashes array will be represented in this array as ABCD0A (10==0x0A)
115: // So this array contains ordered <hash to index> correspondences.
116: // Note, that every item in this array is unique.
117: private final long[] hashes_idx;
118:
119: // the index of the last cached object
120: private int last_cached = 0;
121: // cache population indicator
122: private boolean cache_is_full = false;
123:
124: /**
125: * Creates the Cache object.
126: * @param pref_size specifies how many leading/trailing bytes of object's
127: * encoded form will be used for hash computation
128: * @param size capacity of the cache to be created.
129: */
130: public Cache(int pref_size, int size) {
131: cache_size = size;
132: prefix_size = pref_size;
133: hashes = new long[cache_size];
134: hashes_idx = new long[cache_size];
135: encodings = new byte[cache_size][];
136: cache = new Object[cache_size];
137: }
138:
139: /**
140: * Creates the Cache object of size of 900.
141: * @param pref_size specifies how many leading/trailing bytes of object's
142: * encoded form will be used for hash computation
143: */
144: public Cache(int pref_size) {
145: this (pref_size, 900);
146: }
147:
148: /**
149: * Creates the Cache object of size of 900.
150: */
151: public Cache() {
152: this (28, 900);
153: }
154:
155: /**
156: * Returns the hash code for the array. This code is used to
157: * predetermine whether the object was built on the base of the
158: * similar encoding or not (by means of <code>contains(long)</code> method),
159: * to exactly determine whether object is contained in the cache or not,
160: * and to put the object in the cache.
161: * Note: parameter array should be of length not less than
162: * specified by <code>prefix_size</code> (default 28)
163: * @param arr the byte array containing at least prefix_size leading bytes
164: * of the encoding.
165: * @return hash code for specified encoding prefix
166: */
167: public long getHash(byte[] arr) {
168: long hash = 0;
169: for (int i = 1; i < prefix_size; i++) {
170: hash += (arr[i] & 0xFF);
171: } // it takes about 2 bytes for prefix_size == 28
172:
173: // shift to the correct place
174: hash = hash << 32;
175: return hash;
176: }
177:
178: /**
179: * Checks if there are any object in the cache generated
180: * on the base of encoding with prefix corresponding
181: * to the specified hash code.
182: * @param prefix_hash the hash code for the prefix
183: * of the encoding (retrieved by method <code>getHash(byte[]))</code>
184: * @return false if there were not any object generated
185: * on the base of encoding with specified hash code, true
186: * otherwise.
187: */
188: public boolean contains(long prefix_hash) {
189: int idx = -1 * Arrays.binarySearch(hashes_idx, prefix_hash) - 1;
190: if (idx == cache_size) {
191: return false;
192: } else {
193: return (hashes_idx[idx] & PREFIX_HASH_MASK) == prefix_hash;
194: }
195: }
196:
197: /**
198: * Returns the object built on the base on the specified encoded
199: * form if it is contained in the cache and null otherwise.
200: * This method is computationally expensive and should be called only if
201: * the method <code>contains(long)</code> for the hash code returned true.
202: * @param hash the hash code for the prefix of the encoding
203: * (retrieved by method <code>getHash(byte[])</code>)
204: * @param encoding encoded form of the required object.
205: * @return the object corresponding to specified encoding or null if
206: * there is no such correspondence.
207: */
208: public Object get(long hash, byte[] encoding) {
209: hash |= getSuffHash(encoding);
210: int idx = -1 * Arrays.binarySearch(hashes_idx, hash) - 1;
211: if (idx == cache_size) {
212: return null;
213: }
214: while ((hashes_idx[idx] & HASH_MASK) == hash) {
215: int i = (int) (hashes_idx[idx] & INDEX_MASK) - 1;
216: if (Arrays.equals(encoding, encodings[i])) {
217: return cache[i];
218: }
219: idx++;
220: if (idx == cache_size) {
221: return null;
222: }
223: }
224: return null;
225: }
226:
227: /**
228: * Puts the object into the cache.
229: * @param hash hash code for the prefix of the encoding
230: * @param encoding the encoded form of the object
231: * @param object the object to be saved in the cache
232: */
233: public void put(long hash, byte[] encoding, Object object) {
234: // check for empty space in the cache
235: if (last_cached == cache_size) {
236: // so cache is full, will erase the first entry in the
237: // cache (oldest entry). it could be better to throw out
238: // rarely used value instead of oldest one..
239: last_cached = 0;
240: cache_is_full = true;
241: }
242: // index pointing to the item of the table to be overwritten
243: int index = last_cached++;
244:
245: // improve the hash value with info from the tail of encoding
246: hash |= getSuffHash(encoding);
247:
248: if (cache_is_full) {
249: // indexing hash value to be overwritten:
250: long idx_hash = (hashes[index] | (index + 1));
251: int idx = Arrays.binarySearch(hashes_idx, idx_hash);
252: if (idx < 0) {
253: // it will never happen because we use saved hash value
254: // (hashes[index])
255: System.out.println("WARNING! " + idx); //$NON-NLS-1$
256: idx = -(idx + 1);
257: }
258: long new_hash_idx = (hash | (index + 1));
259: int new_idx = Arrays.binarySearch(hashes_idx, new_hash_idx);
260: if (new_idx >= 0) {
261: // it's possible when we write the same hash in the same cell
262: if (idx != new_idx) {
263: // it will never happen because we use the same
264: // hash and the same index in hash table
265: System.out.println("WARNING: "); //$NON-NLS-1$
266: System.out
267: .println(">> idx: " + idx + " new_idx: " + new_idx); //$NON-NLS-1$ //$NON-NLS-2$
268: }
269: } else {
270: new_idx = -(new_idx + 1);
271: // replace in sorted array
272: if (new_idx > idx) {
273: System.arraycopy(hashes_idx, idx + 1, hashes_idx,
274: idx, new_idx - idx - 1);
275: hashes_idx[new_idx - 1] = new_hash_idx;
276: } else if (idx > new_idx) {
277: System.arraycopy(hashes_idx, new_idx, hashes_idx,
278: new_idx + 1, idx - new_idx);
279: hashes_idx[new_idx] = new_hash_idx;
280: } else { // idx == new_idx
281: hashes_idx[new_idx] = new_hash_idx;
282: }
283: }
284: } else {
285: long idx_hash = (hash | (index + 1));
286: int idx = Arrays.binarySearch(hashes_idx, idx_hash);
287: if (idx < 0) {
288: // it will always be true because idx_hash depends on index
289: idx = -(idx + 1);
290: }
291: idx = idx - 1;
292: if (idx != cache_size - index - 1) {
293: // if not in the cell containing 0 (free cell), do copy:
294: System.arraycopy(hashes_idx, cache_size - index,
295: hashes_idx, cache_size - index - 1, idx
296: - (cache_size - index) + 1);
297: }
298: hashes_idx[idx] = idx_hash;
299: }
300: // overwrite the values in the tables:
301: hashes[index] = hash;
302: encodings[index] = encoding;
303: cache[index] = object;
304: }
305:
306: // Returns the hash code built on the base of the tail of the encoded form
307: // @param arr - the array containing at least prefix_size trailing bytes
308: // of encoded form
309: private long getSuffHash(byte[] arr) {
310: long hash_addon = 0;
311: for (int i = arr.length - 1; i > arr.length - prefix_size; i--) {
312: hash_addon += (arr[i] & 0xFF);
313: }
314: return hash_addon << 16;
315: }
316:
317: }
|