001: /*
002: * Copyright 2003 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package com.sun.java.util.jar.pack;
027:
028: import java.io.*;
029: import java.util.*;
030: import com.sun.java.util.jar.pack.ConstantPool.*;
031:
032: /**
033: * Collection of relocatable constant pool references.
034: * It operates with respect to a particular byte array,
035: * and stores some of its state in the bytes themselves.
036: * <p>
037: * As a Collection, it can be iterated over, but it is not a List,
038: * since it does not natively support indexed access.
039: * <p>
040: *
041: * @author John Rose
042: * @version 1.13, 05/05/07
043: */
044: class Fixups extends AbstractCollection implements Constants {
045: byte[] bytes; // the subject of the relocations
046: int head; // desc locating first reloc
047: int tail; // desc locating last reloc
048: int size; // number of relocations
049: Entry[] entries; // [0..size-1] relocations
050: int[] bigDescs; // descs which cannot be stored in the bytes
051:
052: // A "desc" (descriptor) is a bit-encoded pair of a location
053: // and format. Every fixup occurs at a "desc". Until final
054: // patching, bytes addressed by descs may also be used to
055: // link this data structure together. If the bytes are missing,
056: // or if the "desc" is too large to encode in the bytes,
057: // it is kept in the bigDescs array.
058:
059: Fixups(byte[] bytes) {
060: this .bytes = bytes;
061: entries = new Entry[3];
062: bigDescs = noBigDescs;
063: }
064:
065: Fixups() {
066: // If there are no bytes, all descs are kept in bigDescs.
067: this ((byte[]) null);
068: }
069:
070: Fixups(byte[] bytes, Collection fixups) {
071: this (bytes);
072: addAll(fixups);
073: }
074:
075: Fixups(Collection fixups) {
076: this ((byte[]) null);
077: addAll(fixups);
078: }
079:
080: private static final int MINBIGSIZE = 1;
081: // cleverly share empty bigDescs:
082: private static int[] noBigDescs = { MINBIGSIZE };
083:
084: public int size() {
085: return size;
086: }
087:
088: public void trimToSize() {
089: if (size != entries.length) {
090: Entry[] oldEntries = entries;
091: entries = new Entry[size];
092: System.arraycopy(oldEntries, 0, entries, 0, size);
093: }
094: int bigSize = bigDescs[BIGSIZE];
095: if (bigSize == MINBIGSIZE) {
096: bigDescs = noBigDescs;
097: } else if (bigSize != bigDescs.length) {
098: int[] oldBigDescs = bigDescs;
099: bigDescs = new int[bigSize];
100: System.arraycopy(oldBigDescs, 0, bigDescs, 0, bigSize);
101: }
102: }
103:
104: public void visitRefs(Collection refs) {
105: for (int i = 0; i < size; i++) {
106: refs.add(entries[i]);
107: }
108: }
109:
110: public void clear() {
111: if (bytes != null) {
112: // Clean the bytes:
113: for (Iterator i = iterator(); i.hasNext();) {
114: Fixup fx = (Fixup) i.next();
115: //System.out.println("clean "+fx);
116: storeIndex(fx.location(), fx.format(), 0);
117: }
118: }
119: size = 0;
120: if (bigDescs != noBigDescs)
121: bigDescs[BIGSIZE] = MINBIGSIZE;
122: // do not trim to size, however
123: }
124:
125: public byte[] getBytes() {
126: return bytes;
127: }
128:
129: public void setBytes(byte[] newBytes) {
130: if (bytes == newBytes)
131: return;
132: ArrayList old = null;
133: assert ((old = new ArrayList(this )) != null);
134: if (bytes == null || newBytes == null) {
135: // One or the other representations is deficient.
136: // Construct a checkpoint.
137: ArrayList save = new ArrayList(this );
138: clear();
139: bytes = newBytes;
140: addAll(save);
141: } else {
142: // assume newBytes is some sort of bitwise copy of the old bytes
143: bytes = newBytes;
144: }
145: assert (old.equals(new ArrayList(this )));
146: }
147:
148: static final int LOC_SHIFT = 1;
149: static final int FMT_MASK = 0x1;
150: static final byte UNUSED_BYTE = 0;
151: static final byte OVERFLOW_BYTE = -1;
152: // fill pointer of bigDescs array is in element [0]
153: static final int BIGSIZE = 0;
154:
155: // Format values:
156: public static final int U2_FORMAT = 0;
157: public static final int U1_FORMAT = 1;
158:
159: // Special values for the static methods.
160: private static final int SPECIAL_LOC = 0;
161: private static final int SPECIAL_FMT = U2_FORMAT;
162:
163: static int fmtLen(int fmt) {
164: return 1 + (fmt - U1_FORMAT) / (U2_FORMAT - U1_FORMAT);
165: }
166:
167: static int descLoc(int desc) {
168: return desc >>> LOC_SHIFT;
169: }
170:
171: static int descFmt(int desc) {
172: return desc & FMT_MASK;
173: }
174:
175: static int descEnd(int desc) {
176: return descLoc(desc) + fmtLen(descFmt(desc));
177: }
178:
179: static int makeDesc(int loc, int fmt) {
180: int desc = (loc << LOC_SHIFT) | fmt;
181: assert (descLoc(desc) == loc);
182: assert (descFmt(desc) == fmt);
183: return desc;
184: }
185:
186: int fetchDesc(int loc, int fmt) {
187: byte b1 = bytes[loc];
188: assert (b1 != OVERFLOW_BYTE);
189: int value;
190: if (fmt == U2_FORMAT) {
191: byte b2 = bytes[loc + 1];
192: value = ((b1 & 0xFF) << 8) + (b2 & 0xFF);
193: } else {
194: value = (b1 & 0xFF);
195: }
196: // Stored loc field is difference between its own loc and next loc.
197: return value + (loc << LOC_SHIFT);
198: }
199:
200: boolean storeDesc(int loc, int fmt, int desc) {
201: if (bytes == null)
202: return false;
203: int value = desc - (loc << LOC_SHIFT);
204: byte b1, b2;
205: switch (fmt) {
206: case U2_FORMAT:
207: assert (bytes[loc + 0] == UNUSED_BYTE);
208: assert (bytes[loc + 1] == UNUSED_BYTE);
209: b1 = (byte) (value >> 8);
210: b2 = (byte) (value >> 0);
211: if (value == (value & 0xFFFF) && b1 != OVERFLOW_BYTE) {
212: bytes[loc + 0] = b1;
213: bytes[loc + 1] = b2;
214: assert (fetchDesc(loc, fmt) == desc);
215: return true;
216: }
217: break;
218: case U1_FORMAT:
219: assert (bytes[loc] == UNUSED_BYTE);
220: b1 = (byte) value;
221: if (value == (value & 0xFF) && b1 != OVERFLOW_BYTE) {
222: bytes[loc] = b1;
223: assert (fetchDesc(loc, fmt) == desc);
224: return true;
225: }
226: break;
227: default:
228: assert (false);
229: }
230: // Failure. Caller must allocate a bigDesc.
231: bytes[loc] = OVERFLOW_BYTE;
232: assert (fmt == U1_FORMAT || (bytes[loc + 1] = (byte) bigDescs[BIGSIZE]) != 999);
233: return false;
234: }
235:
236: void storeIndex(int loc, int fmt, int value) {
237: storeIndex(bytes, loc, fmt, value);
238: }
239:
240: static void storeIndex(byte[] bytes, int loc, int fmt, int value) {
241: switch (fmt) {
242: case U2_FORMAT:
243: assert (value == (value & 0xFFFF)) : (value);
244: bytes[loc + 0] = (byte) (value >> 8);
245: bytes[loc + 1] = (byte) (value >> 0);
246: break;
247: case U1_FORMAT:
248: assert (value == (value & 0xFF)) : (value);
249: bytes[loc] = (byte) value;
250: break;
251: default:
252: assert (false);
253: }
254: }
255:
256: /** Simple and necessary tuple to present each fixup. */
257: public static class Fixup implements Comparable {
258: int desc; // location and format of reloc
259: Entry entry; // which entry to plug into the bytes
260:
261: Fixup(int desc, Entry entry) {
262: this .desc = desc;
263: this .entry = entry;
264: }
265:
266: public Fixup(int loc, int fmt, Entry entry) {
267: this .desc = makeDesc(loc, fmt);
268: this .entry = entry;
269: }
270:
271: public int location() {
272: return descLoc(desc);
273: }
274:
275: public int format() {
276: return descFmt(desc);
277: }
278:
279: public Entry entry() {
280: return entry;
281: }
282:
283: public int compareTo(Fixup that) {
284: // Ordering depends only on location.
285: return this .location() - that.location();
286: }
287:
288: public int compareTo(Object that) {
289: return compareTo((Fixup) that);
290: }
291:
292: public boolean equals(Object x) {
293: if (!(x instanceof Fixup))
294: return false;
295: Fixup that = (Fixup) x;
296: return this .desc == that.desc && this .entry == that.entry;
297: }
298:
299: public String toString() {
300: return "@" + location()
301: + (format() == U1_FORMAT ? ".1" : "") + "=" + entry;
302: }
303: }
304:
305: private class Itr implements Iterator {
306: int index = 0; // index into entries
307: int bigIndex = BIGSIZE + 1; // index into bigDescs
308: int next = head; // desc pointing to next fixup
309:
310: public boolean hasNext() {
311: return index < size;
312: }
313:
314: public void remove() {
315: throw new UnsupportedOperationException();
316: }
317:
318: public Object next() {
319: int this Index = index;
320: return new Fixup(nextDesc(), entries[this Index]);
321: }
322:
323: int nextDesc() {
324: int this Index = index++;
325: int this Desc = next;
326: if (index < size) {
327: // Fetch next desc eagerly, in case this fixup gets finalized.
328: int loc = descLoc(this Desc);
329: int fmt = descFmt(this Desc);
330: if (bytes != null && bytes[loc] != OVERFLOW_BYTE) {
331: next = fetchDesc(loc, fmt);
332: } else {
333: // The unused extra byte is "asserted" to be equal to BI.
334: // This helps keep the overflow descs in sync.
335: assert (fmt == U1_FORMAT || bytes == null || bytes[loc + 1] == (byte) bigIndex);
336: next = bigDescs[bigIndex++];
337: }
338: }
339: return this Desc;
340: }
341: }
342:
343: public Iterator iterator() {
344: return new Itr();
345: }
346:
347: public void add(int location, int format, Entry entry) {
348: addDesc(makeDesc(location, format), entry);
349: }
350:
351: public boolean add(Fixup f) {
352: addDesc(f.desc, f.entry);
353: return true;
354: }
355:
356: public boolean add(Object fixup) {
357: return add((Fixup) fixup);
358: }
359:
360: public boolean addAll(Collection c) {
361: if (c instanceof Fixups) {
362: // Use knowledge of Itr structure to avoid building little structs.
363: Fixups that = (Fixups) c;
364: if (that.size == 0)
365: return false;
366: if (this .size == 0 && entries.length < that.size)
367: growEntries(that.size); // presize exactly
368: Entry[] thatEntries = that.entries;
369: for (Itr i = that.new Itr(); i.hasNext();) {
370: int ni = i.index;
371: addDesc(i.nextDesc(), thatEntries[ni]);
372: }
373: return true;
374: } else {
375: return super .addAll(c);
376: }
377: }
378:
379: // Here is how things get added:
380: private void addDesc(int this Desc, Entry entry) {
381: if (entries.length == size)
382: growEntries(size * 2);
383: entries[size] = entry;
384: if (size == 0) {
385: head = tail = this Desc;
386: } else {
387: int prevDesc = tail;
388: // Store new desc in previous tail.
389: int prevLoc = descLoc(prevDesc);
390: int prevFmt = descFmt(prevDesc);
391: int prevLen = fmtLen(prevFmt);
392: int this Loc = descLoc(this Desc);
393: // The collection must go in ascending order, and not overlap.
394: if (this Loc < prevLoc + prevLen)
395: badOverlap(this Loc);
396: tail = this Desc;
397: if (!storeDesc(prevLoc, prevFmt, this Desc)) {
398: // overflow
399: int bigSize = bigDescs[BIGSIZE];
400: if (bigDescs.length == bigSize)
401: growBigDescs();
402: //System.out.println("bigDescs["+bigSize+"] = "+thisDesc);
403: bigDescs[bigSize++] = this Desc;
404: bigDescs[BIGSIZE] = bigSize;
405: }
406: }
407: size += 1;
408: }
409:
410: private void badOverlap(int this Loc) {
411: throw new IllegalArgumentException(
412: "locs must be ascending and must not overlap: "
413: + this Loc + " >> " + this );
414: }
415:
416: private void growEntries(int newSize) {
417: Entry[] oldEntries = entries;
418: entries = new Entry[Math.max(3, newSize)];
419: System.arraycopy(oldEntries, 0, entries, 0, oldEntries.length);
420: }
421:
422: private void growBigDescs() {
423: int[] oldBigDescs = bigDescs;
424: bigDescs = new int[oldBigDescs.length * 2];
425: System.arraycopy(oldBigDescs, 0, bigDescs, 0,
426: oldBigDescs.length);
427: }
428:
429: /// Static methods that optimize the use of this class.
430: public static Object add(Object prevFixups, byte[] bytes, int loc,
431: int fmt, Entry e) {
432: Fixups f;
433: if (prevFixups == null) {
434: if (loc == SPECIAL_LOC && fmt == SPECIAL_FMT) {
435: // Special convention: If the attribute has a
436: // U2 relocation at position zero, store the Entry
437: // rather than building a Fixups structure.
438: return e;
439: }
440: f = new Fixups(bytes);
441: } else if (!(prevFixups instanceof Fixups)) {
442: // Recognize the special convention:
443: Entry firstEntry = (Entry) prevFixups;
444: f = new Fixups(bytes);
445: f.add(SPECIAL_LOC, SPECIAL_FMT, firstEntry);
446: } else {
447: f = (Fixups) prevFixups;
448: assert (f.bytes == bytes);
449: }
450: f.add(loc, fmt, e);
451: return f;
452: }
453:
454: public static void setBytes(Object fixups, byte[] bytes) {
455: if (fixups instanceof Fixups) {
456: Fixups f = (Fixups) fixups;
457: f.setBytes(bytes);
458: }
459: }
460:
461: public static Object trimToSize(Object fixups) {
462: if (fixups instanceof Fixups) {
463: Fixups f = (Fixups) fixups;
464: f.trimToSize();
465: if (f.size() == 0)
466: fixups = null;
467: }
468: return fixups;
469: }
470:
471: // Iterate over all the references in this set of fixups.
472: public static void visitRefs(Object fixups, Collection refs) {
473: if (fixups == null) {
474: } else if (!(fixups instanceof Fixups)) {
475: // Special convention; see above.
476: refs.add((Entry) fixups);
477: } else {
478: Fixups f = (Fixups) fixups;
479: f.visitRefs(refs);
480: }
481: }
482:
483: // Clear out this set of fixups by replacing each reference
484: // by a hardcoded coding of its reference, drawn from ix.
485: public static void finishRefs(Object fixups, byte[] bytes,
486: ConstantPool.Index ix) {
487: if (fixups == null)
488: return;
489: if (!(fixups instanceof Fixups)) {
490: // Special convention; see above.
491: int index = ix.indexOf((Entry) fixups);
492: storeIndex(bytes, SPECIAL_LOC, SPECIAL_FMT, index);
493: return;
494: }
495: Fixups f = (Fixups) fixups;
496: assert (f.bytes == bytes);
497: f.finishRefs(ix);
498: }
499:
500: void finishRefs(ConstantPool.Index ix) {
501: if (isEmpty())
502: return;
503: for (Iterator i = iterator(); i.hasNext();) {
504: Fixup fx = (Fixup) i.next();
505: int index = ix.indexOf(fx.entry);
506: //System.out.println("finish "+fx+" = "+index);
507: // Note that the iterator has already fetched the
508: // bytes we are about to overwrite.
509: storeIndex(fx.location(), fx.format(), index);
510: }
511: // Further iterations should do nothing:
512: bytes = null; // do not clean them
513: clear();
514: }
515:
516: /*
517: /// Testing.
518: public static void main(String[] av) {
519: byte[] bytes = new byte[1 << 20];
520: ConstantPool cp = new ConstantPool();
521: Fixups f = new Fixups(bytes);
522: boolean isU1 = false;
523: int span = 3;
524: int nextLoc = 0;
525: int[] locs = new int[100];
526: final int[] indexes = new int[100];
527: int iptr = 1;
528: for (int loc = 0; loc < bytes.length; loc++) {
529: if (loc == nextLoc && loc+1 < bytes.length) {
530: int fmt = (isU1 ? U1_FORMAT : U2_FORMAT);
531: Entry e = ConstantPool.getUtf8Entry("L"+loc);
532: f.add(loc, fmt, e);
533: isU1 ^= true;
534: if (iptr < 10) {
535: // Make it close in.
536: nextLoc += fmtLen(fmt) + (iptr < 5 ? 0 : 1);
537: } else {
538: nextLoc += span;
539: span = (int)(span * 1.77);
540: }
541: // Here are the bytes that would have gone here:
542: locs[iptr] = loc;
543: if (fmt == U1_FORMAT) {
544: indexes[iptr++] = (loc & 0xFF);
545: } else {
546: indexes[iptr++] = ((loc & 0xFF) << 8) | ((loc+1) & 0xFF);
547: ++loc; // skip a byte
548: }
549: continue;
550: }
551: bytes[loc] = (byte)loc;
552: }
553: System.out.println("size="+f.size()
554: +" overflow="+(f.bigDescs[BIGSIZE]-1));
555: System.out.println("Fixups: "+f);
556: // Test collection contents.
557: assert(iptr == 1+f.size());
558: List l = new ArrayList(f);
559: Collections.sort(l); // should not change the order
560: if (!l.equals(new ArrayList(f))) System.out.println("** disordered");
561: f.setBytes(null);
562: if (!l.equals(new ArrayList(f))) System.out.println("** bad set 1");
563: f.setBytes(bytes);
564: if (!l.equals(new ArrayList(f))) System.out.println("** bad set 2");
565: Fixups f3 = new Fixups(f);
566: if (!l.equals(new ArrayList(f3))) System.out.println("** bad set 3");
567: Iterator fi = f.iterator();
568: for (int i = 1; i < iptr; i++) {
569: Fixup fx = (Fixup) fi.next();
570: if (fx.location() != locs[i]) {
571: System.out.println("** "+fx+" != "+locs[i]);
572: }
573: if (fx.format() == U1_FORMAT)
574: System.out.println(fx+" -> "+bytes[locs[i]]);
575: else
576: System.out.println(fx+" -> "+bytes[locs[i]]+" "+bytes[locs[i]+1]);
577: }
578: assert(!fi.hasNext());
579: indexes[0] = 1; // like iptr
580: Index ix = new Index("ix") {
581: public int indexOf(Entry e) {
582: return indexes[indexes[0]++];
583: }
584: };
585: f.finishRefs(ix);
586: for (int loc = 0; loc < bytes.length; loc++) {
587: if (bytes[loc] != (byte)loc) {
588: System.out.println("** ["+loc+"] = "+bytes[loc]+" != "+(byte)loc);
589: }
590: }
591: }
592: //*/
593: }
|