0N/A/*
3261N/A * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/A
0N/Apackage com.sun.java.util.jar.pack;
0N/A
3063N/Aimport com.sun.java.util.jar.pack.ConstantPool.Entry;
3063N/Aimport java.util.AbstractCollection;
3063N/Aimport java.util.ArrayList;
3063N/Aimport java.util.Collection;
3063N/Aimport java.util.Iterator;
0N/A
0N/A/**
0N/A * Collection of relocatable constant pool references.
0N/A * It operates with respect to a particular byte array,
0N/A * and stores some of its state in the bytes themselves.
0N/A * <p>
0N/A * As a Collection, it can be iterated over, but it is not a List,
0N/A * since it does not natively support indexed access.
0N/A * <p>
0N/A *
0N/A * @author John Rose
0N/A */
3315N/Afinal class Fixups extends AbstractCollection {
0N/A byte[] bytes; // the subject of the relocations
0N/A int head; // desc locating first reloc
0N/A int tail; // desc locating last reloc
0N/A int size; // number of relocations
0N/A Entry[] entries; // [0..size-1] relocations
0N/A int[] bigDescs; // descs which cannot be stored in the bytes
0N/A
0N/A // A "desc" (descriptor) is a bit-encoded pair of a location
0N/A // and format. Every fixup occurs at a "desc". Until final
0N/A // patching, bytes addressed by descs may also be used to
0N/A // link this data structure together. If the bytes are missing,
0N/A // or if the "desc" is too large to encode in the bytes,
0N/A // it is kept in the bigDescs array.
0N/A
0N/A Fixups(byte[] bytes) {
0N/A this.bytes = bytes;
0N/A entries = new Entry[3];
0N/A bigDescs = noBigDescs;
0N/A }
0N/A Fixups() {
0N/A // If there are no bytes, all descs are kept in bigDescs.
0N/A this((byte[])null);
0N/A }
0N/A Fixups(byte[] bytes, Collection fixups) {
0N/A this(bytes);
0N/A addAll(fixups);
0N/A }
0N/A Fixups(Collection fixups) {
0N/A this((byte[])null);
0N/A addAll(fixups);
0N/A }
0N/A
0N/A private static final int MINBIGSIZE = 1;
0N/A // cleverly share empty bigDescs:
0N/A private static int[] noBigDescs = {MINBIGSIZE};
0N/A
0N/A public int size() {
0N/A return size;
0N/A }
0N/A
0N/A public void trimToSize() {
0N/A if (size != entries.length) {
0N/A Entry[] oldEntries = entries;
0N/A entries = new Entry[size];
0N/A System.arraycopy(oldEntries, 0, entries, 0, size);
0N/A }
0N/A int bigSize = bigDescs[BIGSIZE];
0N/A if (bigSize == MINBIGSIZE) {
0N/A bigDescs = noBigDescs;
0N/A } else if (bigSize != bigDescs.length) {
0N/A int[] oldBigDescs = bigDescs;
0N/A bigDescs = new int[bigSize];
0N/A System.arraycopy(oldBigDescs, 0, bigDescs, 0, bigSize);
0N/A }
0N/A }
0N/A
3315N/A public void visitRefs(Collection<Entry> refs) {
0N/A for (int i = 0; i < size; i++) {
0N/A refs.add(entries[i]);
0N/A }
0N/A }
0N/A
0N/A public void clear() {
0N/A if (bytes != null) {
0N/A // Clean the bytes:
0N/A for (Iterator i = iterator(); i.hasNext(); ) {
0N/A Fixup fx = (Fixup) i.next();
0N/A //System.out.println("clean "+fx);
0N/A storeIndex(fx.location(), fx.format(), 0);
0N/A }
0N/A }
0N/A size = 0;
0N/A if (bigDescs != noBigDescs)
0N/A bigDescs[BIGSIZE] = MINBIGSIZE;
0N/A // do not trim to size, however
0N/A }
0N/A
0N/A public byte[] getBytes() {
0N/A return bytes;
0N/A }
0N/A
3315N/A @SuppressWarnings("unchecked")
0N/A public void setBytes(byte[] newBytes) {
0N/A if (bytes == newBytes) return;
0N/A ArrayList old = null;
0N/A assert((old = new ArrayList(this)) != null);
0N/A if (bytes == null || newBytes == null) {
0N/A // One or the other representations is deficient.
0N/A // Construct a checkpoint.
0N/A ArrayList save = new ArrayList(this);
0N/A clear();
0N/A bytes = newBytes;
0N/A addAll(save);
0N/A } else {
0N/A // assume newBytes is some sort of bitwise copy of the old bytes
0N/A bytes = newBytes;
0N/A }
0N/A assert(old.equals(new ArrayList(this)));
0N/A }
0N/A
0N/A static final int LOC_SHIFT = 1;
0N/A static final int FMT_MASK = 0x1;
0N/A static final byte UNUSED_BYTE = 0;
0N/A static final byte OVERFLOW_BYTE = -1;
0N/A // fill pointer of bigDescs array is in element [0]
0N/A static final int BIGSIZE = 0;
0N/A
0N/A // Format values:
0N/A public static final int U2_FORMAT = 0;
0N/A public static final int U1_FORMAT = 1;
0N/A
0N/A // Special values for the static methods.
0N/A private static final int SPECIAL_LOC = 0;
0N/A private static final int SPECIAL_FMT = U2_FORMAT;
0N/A
0N/A static int fmtLen(int fmt) { return 1+(fmt-U1_FORMAT)/(U2_FORMAT-U1_FORMAT); }
0N/A static int descLoc(int desc) { return desc >>> LOC_SHIFT; }
0N/A static int descFmt(int desc) { return desc & FMT_MASK; }
0N/A static int descEnd(int desc) { return descLoc(desc) + fmtLen(descFmt(desc)); }
0N/A static int makeDesc(int loc, int fmt) {
0N/A int desc = (loc << LOC_SHIFT) | fmt;
0N/A assert(descLoc(desc) == loc);
0N/A assert(descFmt(desc) == fmt);
0N/A return desc;
0N/A }
0N/A int fetchDesc(int loc, int fmt) {
0N/A byte b1 = bytes[loc];
0N/A assert(b1 != OVERFLOW_BYTE);
0N/A int value;
0N/A if (fmt == U2_FORMAT) {
0N/A byte b2 = bytes[loc+1];
0N/A value = ((b1 & 0xFF) << 8) + (b2 & 0xFF);
0N/A } else {
0N/A value = (b1 & 0xFF);
0N/A }
0N/A // Stored loc field is difference between its own loc and next loc.
0N/A return value + (loc << LOC_SHIFT);
0N/A }
0N/A boolean storeDesc(int loc, int fmt, int desc) {
0N/A if (bytes == null)
0N/A return false;
0N/A int value = desc - (loc << LOC_SHIFT);
0N/A byte b1, b2;
0N/A switch (fmt) {
0N/A case U2_FORMAT:
0N/A assert(bytes[loc+0] == UNUSED_BYTE);
0N/A assert(bytes[loc+1] == UNUSED_BYTE);
0N/A b1 = (byte)(value >> 8);
0N/A b2 = (byte)(value >> 0);
0N/A if (value == (value & 0xFFFF) && b1 != OVERFLOW_BYTE) {
0N/A bytes[loc+0] = b1;
0N/A bytes[loc+1] = b2;
0N/A assert(fetchDesc(loc, fmt) == desc);
0N/A return true;
0N/A }
0N/A break;
0N/A case U1_FORMAT:
0N/A assert(bytes[loc] == UNUSED_BYTE);
0N/A b1 = (byte)value;
0N/A if (value == (value & 0xFF) && b1 != OVERFLOW_BYTE) {
0N/A bytes[loc] = b1;
0N/A assert(fetchDesc(loc, fmt) == desc);
0N/A return true;
0N/A }
0N/A break;
0N/A default: assert(false);
0N/A }
0N/A // Failure. Caller must allocate a bigDesc.
0N/A bytes[loc] = OVERFLOW_BYTE;
0N/A assert(fmt==U1_FORMAT || (bytes[loc+1]=(byte)bigDescs[BIGSIZE])!=999);
0N/A return false;
0N/A }
0N/A void storeIndex(int loc, int fmt, int value) {
0N/A storeIndex(bytes, loc, fmt, value);
0N/A }
0N/A static
0N/A void storeIndex(byte[] bytes, int loc, int fmt, int value) {
0N/A switch (fmt) {
0N/A case U2_FORMAT:
0N/A assert(value == (value & 0xFFFF)) : (value);
0N/A bytes[loc+0] = (byte)(value >> 8);
0N/A bytes[loc+1] = (byte)(value >> 0);
0N/A break;
0N/A case U1_FORMAT:
0N/A assert(value == (value & 0xFF)) : (value);
0N/A bytes[loc] = (byte)value;
0N/A break;
0N/A default: assert(false);
0N/A }
0N/A }
0N/A
0N/A /** Simple and necessary tuple to present each fixup. */
0N/A public static
0N/A class Fixup implements Comparable {
0N/A int desc; // location and format of reloc
0N/A Entry entry; // which entry to plug into the bytes
0N/A Fixup(int desc, Entry entry) {
0N/A this.desc = desc;
0N/A this.entry = entry;
0N/A }
0N/A public Fixup(int loc, int fmt, Entry entry) {
0N/A this.desc = makeDesc(loc, fmt);
0N/A this.entry = entry;
0N/A }
0N/A public int location() { return descLoc(desc); }
0N/A public int format() { return descFmt(desc); }
0N/A public Entry entry() { return entry; }
0N/A public int compareTo(Fixup that) {
0N/A // Ordering depends only on location.
0N/A return this.location() - that.location();
0N/A }
0N/A public int compareTo(Object that) {
0N/A return compareTo((Fixup)that);
0N/A }
0N/A public boolean equals(Object x) {
0N/A if (!(x instanceof Fixup)) return false;
0N/A Fixup that = (Fixup) x;
0N/A return this.desc == that.desc && this.entry == that.entry;
0N/A }
0N/A public String toString() {
0N/A return "@"+location()+(format()==U1_FORMAT?".1":"")+"="+entry;
0N/A }
0N/A }
0N/A
0N/A private
0N/A class Itr implements Iterator {
0N/A int index = 0; // index into entries
0N/A int bigIndex = BIGSIZE+1; // index into bigDescs
0N/A int next = head; // desc pointing to next fixup
0N/A public boolean hasNext() { return index < size; }
0N/A public void remove() { throw new UnsupportedOperationException(); }
0N/A public Object next() {
0N/A int thisIndex = index;
0N/A return new Fixup(nextDesc(), entries[thisIndex]);
0N/A }
0N/A int nextDesc() {
3315N/A index++;
0N/A int thisDesc = next;
0N/A if (index < size) {
0N/A // Fetch next desc eagerly, in case this fixup gets finalized.
0N/A int loc = descLoc(thisDesc);
0N/A int fmt = descFmt(thisDesc);
0N/A if (bytes != null && bytes[loc] != OVERFLOW_BYTE) {
0N/A next = fetchDesc(loc, fmt);
0N/A } else {
0N/A // The unused extra byte is "asserted" to be equal to BI.
0N/A // This helps keep the overflow descs in sync.
0N/A assert(fmt==U1_FORMAT || bytes == null || bytes[loc+1]==(byte)bigIndex);
0N/A next = bigDescs[bigIndex++];
0N/A }
0N/A }
0N/A return thisDesc;
0N/A }
0N/A }
0N/A
0N/A public Iterator iterator() {
0N/A return new Itr();
0N/A }
0N/A public void add(int location, int format, Entry entry) {
0N/A addDesc(makeDesc(location, format), entry);
0N/A }
0N/A public boolean add(Fixup f) {
0N/A addDesc(f.desc, f.entry);
0N/A return true;
0N/A }
0N/A public boolean add(Object fixup) {
0N/A return add((Fixup) fixup);
0N/A }
3315N/A @SuppressWarnings("unchecked")
0N/A public boolean addAll(Collection c) {
0N/A if (c instanceof Fixups) {
0N/A // Use knowledge of Itr structure to avoid building little structs.
0N/A Fixups that = (Fixups) c;
0N/A if (that.size == 0) return false;
0N/A if (this.size == 0 && entries.length < that.size)
0N/A growEntries(that.size); // presize exactly
0N/A Entry[] thatEntries = that.entries;
0N/A for (Itr i = that.new Itr(); i.hasNext(); ) {
0N/A int ni = i.index;
0N/A addDesc(i.nextDesc(), thatEntries[ni]);
0N/A }
0N/A return true;
0N/A } else {
0N/A return super.addAll(c);
0N/A }
0N/A }
0N/A // Here is how things get added:
0N/A private void addDesc(int thisDesc, Entry entry) {
0N/A if (entries.length == size)
0N/A growEntries(size * 2);
0N/A entries[size] = entry;
0N/A if (size == 0) {
0N/A head = tail = thisDesc;
0N/A } else {
0N/A int prevDesc = tail;
0N/A // Store new desc in previous tail.
0N/A int prevLoc = descLoc(prevDesc);
0N/A int prevFmt = descFmt(prevDesc);
0N/A int prevLen = fmtLen(prevFmt);
0N/A int thisLoc = descLoc(thisDesc);
0N/A // The collection must go in ascending order, and not overlap.
0N/A if (thisLoc < prevLoc + prevLen)
0N/A badOverlap(thisLoc);
0N/A tail = thisDesc;
0N/A if (!storeDesc(prevLoc, prevFmt, thisDesc)) {
0N/A // overflow
0N/A int bigSize = bigDescs[BIGSIZE];
0N/A if (bigDescs.length == bigSize)
0N/A growBigDescs();
0N/A //System.out.println("bigDescs["+bigSize+"] = "+thisDesc);
0N/A bigDescs[bigSize++] = thisDesc;
0N/A bigDescs[BIGSIZE] = bigSize;
0N/A }
0N/A }
0N/A size += 1;
0N/A }
0N/A private void badOverlap(int thisLoc) {
0N/A throw new IllegalArgumentException("locs must be ascending and must not overlap: "+thisLoc+" >> "+this);
0N/A }
0N/A
0N/A private void growEntries(int newSize) {
0N/A Entry[] oldEntries = entries;
0N/A entries = new Entry[Math.max(3, newSize)];
0N/A System.arraycopy(oldEntries, 0, entries, 0, oldEntries.length);
0N/A }
0N/A private void growBigDescs() {
0N/A int[] oldBigDescs = bigDescs;
0N/A bigDescs = new int[oldBigDescs.length * 2];
0N/A System.arraycopy(oldBigDescs, 0, bigDescs, 0, oldBigDescs.length);
0N/A }
0N/A
0N/A /// Static methods that optimize the use of this class.
0N/A public static
0N/A Object add(Object prevFixups,
0N/A byte[] bytes, int loc, int fmt,
0N/A Entry e) {
0N/A Fixups f;
0N/A if (prevFixups == null) {
0N/A if (loc == SPECIAL_LOC && fmt == SPECIAL_FMT) {
0N/A // Special convention: If the attribute has a
0N/A // U2 relocation at position zero, store the Entry
0N/A // rather than building a Fixups structure.
0N/A return e;
0N/A }
0N/A f = new Fixups(bytes);
0N/A } else if (!(prevFixups instanceof Fixups)) {
0N/A // Recognize the special convention:
0N/A Entry firstEntry = (Entry) prevFixups;
0N/A f = new Fixups(bytes);
0N/A f.add(SPECIAL_LOC, SPECIAL_FMT, firstEntry);
0N/A } else {
0N/A f = (Fixups) prevFixups;
0N/A assert(f.bytes == bytes);
0N/A }
0N/A f.add(loc, fmt, e);
0N/A return f;
0N/A }
0N/A
0N/A public static
0N/A void setBytes(Object fixups, byte[] bytes) {
0N/A if (fixups instanceof Fixups) {
0N/A Fixups f = (Fixups) fixups;
0N/A f.setBytes(bytes);
0N/A }
0N/A }
0N/A
0N/A public static
0N/A Object trimToSize(Object fixups) {
0N/A if (fixups instanceof Fixups) {
0N/A Fixups f = (Fixups) fixups;
0N/A f.trimToSize();
0N/A if (f.size() == 0)
0N/A fixups = null;
0N/A }
0N/A return fixups;
0N/A }
0N/A
0N/A // Iterate over all the references in this set of fixups.
0N/A public static
3315N/A void visitRefs(Object fixups, Collection<Entry> refs) {
0N/A if (fixups == null) {
0N/A } else if (!(fixups instanceof Fixups)) {
0N/A // Special convention; see above.
0N/A refs.add((Entry) fixups);
0N/A } else {
0N/A Fixups f = (Fixups) fixups;
0N/A f.visitRefs(refs);
0N/A }
0N/A }
0N/A
0N/A // Clear out this set of fixups by replacing each reference
0N/A // by a hardcoded coding of its reference, drawn from ix.
0N/A public static
0N/A void finishRefs(Object fixups, byte[] bytes, ConstantPool.Index ix) {
0N/A if (fixups == null)
0N/A return;
0N/A if (!(fixups instanceof Fixups)) {
0N/A // Special convention; see above.
0N/A int index = ix.indexOf((Entry) fixups);
0N/A storeIndex(bytes, SPECIAL_LOC, SPECIAL_FMT, index);
0N/A return;
0N/A }
0N/A Fixups f = (Fixups) fixups;
0N/A assert(f.bytes == bytes);
0N/A f.finishRefs(ix);
0N/A }
0N/A
0N/A void finishRefs(ConstantPool.Index ix) {
0N/A if (isEmpty())
0N/A return;
0N/A for (Iterator i = iterator(); i.hasNext(); ) {
0N/A Fixup fx = (Fixup) i.next();
0N/A int index = ix.indexOf(fx.entry);
0N/A //System.out.println("finish "+fx+" = "+index);
0N/A // Note that the iterator has already fetched the
0N/A // bytes we are about to overwrite.
0N/A storeIndex(fx.location(), fx.format(), index);
0N/A }
0N/A // Further iterations should do nothing:
0N/A bytes = null; // do not clean them
0N/A clear();
0N/A }
0N/A
0N/A/*
0N/A /// Testing.
0N/A public static void main(String[] av) {
0N/A byte[] bytes = new byte[1 << 20];
0N/A ConstantPool cp = new ConstantPool();
0N/A Fixups f = new Fixups(bytes);
0N/A boolean isU1 = false;
0N/A int span = 3;
0N/A int nextLoc = 0;
0N/A int[] locs = new int[100];
0N/A final int[] indexes = new int[100];
0N/A int iptr = 1;
0N/A for (int loc = 0; loc < bytes.length; loc++) {
0N/A if (loc == nextLoc && loc+1 < bytes.length) {
0N/A int fmt = (isU1 ? U1_FORMAT : U2_FORMAT);
0N/A Entry e = ConstantPool.getUtf8Entry("L"+loc);
0N/A f.add(loc, fmt, e);
0N/A isU1 ^= true;
0N/A if (iptr < 10) {
0N/A // Make it close in.
0N/A nextLoc += fmtLen(fmt) + (iptr < 5 ? 0 : 1);
0N/A } else {
0N/A nextLoc += span;
0N/A span = (int)(span * 1.77);
0N/A }
0N/A // Here are the bytes that would have gone here:
0N/A locs[iptr] = loc;
0N/A if (fmt == U1_FORMAT) {
0N/A indexes[iptr++] = (loc & 0xFF);
0N/A } else {
0N/A indexes[iptr++] = ((loc & 0xFF) << 8) | ((loc+1) & 0xFF);
0N/A ++loc; // skip a byte
0N/A }
0N/A continue;
0N/A }
0N/A bytes[loc] = (byte)loc;
0N/A }
0N/A System.out.println("size="+f.size()
0N/A +" overflow="+(f.bigDescs[BIGSIZE]-1));
0N/A System.out.println("Fixups: "+f);
0N/A // Test collection contents.
0N/A assert(iptr == 1+f.size());
0N/A List l = new ArrayList(f);
0N/A Collections.sort(l); // should not change the order
0N/A if (!l.equals(new ArrayList(f))) System.out.println("** disordered");
0N/A f.setBytes(null);
0N/A if (!l.equals(new ArrayList(f))) System.out.println("** bad set 1");
0N/A f.setBytes(bytes);
0N/A if (!l.equals(new ArrayList(f))) System.out.println("** bad set 2");
0N/A Fixups f3 = new Fixups(f);
0N/A if (!l.equals(new ArrayList(f3))) System.out.println("** bad set 3");
0N/A Iterator fi = f.iterator();
0N/A for (int i = 1; i < iptr; i++) {
0N/A Fixup fx = (Fixup) fi.next();
0N/A if (fx.location() != locs[i]) {
0N/A System.out.println("** "+fx+" != "+locs[i]);
0N/A }
0N/A if (fx.format() == U1_FORMAT)
0N/A System.out.println(fx+" -> "+bytes[locs[i]]);
0N/A else
0N/A System.out.println(fx+" -> "+bytes[locs[i]]+" "+bytes[locs[i]+1]);
0N/A }
0N/A assert(!fi.hasNext());
0N/A indexes[0] = 1; // like iptr
0N/A Index ix = new Index("ix") {
0N/A public int indexOf(Entry e) {
0N/A return indexes[indexes[0]++];
0N/A }
0N/A };
0N/A f.finishRefs(ix);
0N/A for (int loc = 0; loc < bytes.length; loc++) {
0N/A if (bytes[loc] != (byte)loc) {
0N/A System.out.println("** ["+loc+"] = "+bytes[loc]+" != "+(byte)loc);
0N/A }
0N/A }
0N/A }
0N/A//*/
0N/A}