Encoder.java - pwnide - Project Hosting on Google Code

‹r172

r180

r181›

Source path: svn/ trunk/ Base/ lang/ Encoder.java

package lang;

import model.Project;
import model.Segment;
import model.code.*;
import model.code.line.Line;
import model.code.line.SyntaxError;
import model.symbol.Symbol;
import observer.Copiable;
import util.ByteList;
import util.FileUtil;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.concurrent.CyclicBarrier;

/**
 * This is the superclass of all language encoding classes.
 *
 * @author Neil Dickson
 */
public abstract class Encoder {
	private static final short	SIZEOF_PE32_HEADER		= 224;//224-24;	// NOTE: The last 3 RVA/size pair entries aren't needed, saving 24 bytes.
	private static final short	SIZEOF_PE32PLUS_HEADER	= 240;//240-24;	//
	private static final int	NUM_RVA_TABLE_ENTRIES	= 13;		//
	private static final short	PE32_MARKER				= 0x10B;
	private static final short	PE32PLUS_MARKER			= 0x20B;
	private static final short	HEADER_FLAG_FIXED		= 0x0001;
	private static final short	HEADER_FLAG_EXECUTABLE	= 0x0002;
	private static final short	HEADER_FLAG_LARGE_ADDR	= 0x0020;
	private static final short	HEADER_FLAG_LIBRARY		= 0x2000;
	private static final int	FILE_ALIGNMENT			= 0x200;	// 512-byte sector size
	private static final int	SECTION_ALIGNMENT		= 0x1000;	// 4KB page size; 0x200000 for 2MB page size
	public static final long	IMAGE_BASE_EXE			= 0x400000;
	private static final long	IMAGE_BASE_DLL			= 0x10000000;
	private static final int	SIZEOF_SECTION_ENTRY	= 0x28;

	private static final int SECTION_FLAG_CONTAINS_CODE		= 0x20;
	private static final int SECTION_FLAG_CONTAINS_INIT_DATA= 0x40;
	private static final int SECTION_FLAG_EXECUTABLE		= 0x20000000;
	private static final int SECTION_FLAG_READABLE			= 0x40000000;
	private static final int SECTION_FLAG_WRITABLE			= 0x80000000;

	/**
	 * An absolute 2/4-byte relocation (remains a relocation in an executable).
	 */
	public static final int		RELOC_NORMAL	= 0;
	/**
	 * A relative 2/4-byte relocation (relative to RIP).
	 */
	public static final int		RELOC_REL		= 1;
	/**
	 * A 2/4-byte relocation that's the difference between two addresses.
	 * (Assumed to be 2/4-byte even if could be done in 1 byte, for simplicity.)
	 */
	public static final int		RELOC_DIFF	= 2;
	/**
	 * If exceeds range (-128 to +127), turns into RELOC_REL with 2/4-byte relocation,
	 * 0Fh is inserted before previous byte, and 10h is added to previous byte (7x to 0F 8x).
	 */
	public static final int		RELOC_JCC_SHORT	= 3;
	/**
	 * If exceeds range (-128 to +127), turns into RELOC_REL with 2/4-byte relocation
	 * and 1 is added to previous byte (E8 to E9).
	 */
	public static final int		RELOC_JMP_SHORT	= 4;
	/**
	 * If exceeds range (-128 to +127), an error occurs, because there is no longer encoding.
	 */
	public static final int		RELOC_JMP_SHORT_ONLY	= 5;

	/**
	 * Encodes and links the given project as a series of {@link Segment}s, and fills in errors if any are present.
	 * @param project the project to encode
	 * @param errors an empty list to receive any errors that occur in compilation
	 * @return the encoded project, or null if fatal errors occur
	 */
	public static COFFData encodeProject(final Project project,final ArrayList<SyntaxError> errors) {
		final ArrayList<Segment> segments = project.getSegments();
		boolean is64Bit = false;
		for (Segment segment : segments) {
			if (segment.getnBits().get()==64) {
				is64Bit = true;
				break;
			}
		}
		ArrayList<Directory> directories = new ArrayList<Directory>();
		final ArrayList<CodeFile> files = new ArrayList<CodeFile>();
		directories.addAll(project.getDirectory().getDirectories().values());
		files.addAll(project.getDirectory().getCodeFiles().values());
		while (!directories.isEmpty()) {
			Directory directory = directories.remove(directories.size()-1);
			directories.addAll(directory.getDirectories().values());
			files.addAll(directory.getCodeFiles().values());
		}
		final HashMap<Long,Function> importSet = new HashMap<Long,Function>();
		final int numProcessors = Runtime.getRuntime().availableProcessors();
		final HashMap<Segment,SegmentData>[] threadSegmentData = new HashMap[numProcessors];
		for (int i=0;i<numProcessors;++i) {
			threadSegmentData[i] = new HashMap<Segment,SegmentData>(project.getSegments().size());
			for (Segment segment : segments) {
				threadSegmentData[i].put(segment,new SegmentData(new ByteList(4096),new ArrayList<Relocation>(),new ArrayList<SymbolOffset>()));
			}
		}
		final CyclicBarrier barrier = new CyclicBarrier(numProcessors);
		for (int i=0;i<numProcessors;++i) {
			final int threadNumber = i;
			final HashMap<Segment,SegmentData> segmentData = threadSegmentData[i];
			Thread thread = new Thread(){
				public void run() {
					while (true) {
						CodeFile file;
						synchronized (files) {
							if (files.isEmpty()) {
								break;
							}
							file = files.remove(files.size()-1);
						}
						file.getLanguage().getEncoder().encode(file,segmentData,importSet,errors);
					}
					try {
						barrier.await();
					}
					catch (Exception e) {
						e.printStackTrace();
					}
					if (threadNumber>0) {
						for (Segment segment : segments) {
							int sumPrevious = 0;
							for (int j=0;j<threadNumber;++j) {
								sumPrevious += threadSegmentData[j].get(segment).encoded.size();
							}
							if (sumPrevious>0) {
								SegmentData segmentData = threadSegmentData[threadNumber].get(segment);
								for (Relocation r : segmentData.relocations) {
									r.offset += sumPrevious;
								}
								for (SymbolOffset s : segmentData.symbolOffsets) {
									s.offset += sumPrevious;
								}
							}
						}
					}
					else { // threadNumber==0
						for (Segment segment : segments) {
							int totalSize = 0;
							int totalRelocations = 0;
							int totalSymbols = 0;
							for (int j=0;j<numProcessors;++j) {
								SegmentData data = threadSegmentData[j].get(segment);
								totalSize += data.encoded.size();
								totalRelocations += data.relocations.size();
								totalSymbols += data.symbolOffsets.size();
							}
							SegmentData segmentData = threadSegmentData[0].get(segment);
							segmentData.encoded.ensureCapacity(totalSize);
							segmentData.relocations.ensureCapacity(totalRelocations);
							segmentData.symbolOffsets.ensureCapacity(totalSymbols);
						}
					}
					try {
						barrier.await();
					}
					catch (Exception e) {
						e.printStackTrace();
					}
					if (threadNumber==0) {
						// TODO: Eventually do this the parallel way (have each thread insert its elements directly into the arrays at the right locations)
						for (Segment segment : segments) {
							SegmentData segmentData = threadSegmentData[0].get(segment);
							for (int j=1;j<numProcessors;++j) {
								SegmentData data = threadSegmentData[j].get(segment);
								// Handle alignment of each file
								long offset = segmentData.encoded.size();
								offset = (offset+data.alignment-1)&~(data.alignment-1);
								while (segmentData.encoded.size()<offset) {
									segmentData.encoded.add((byte)0);
								}
								segmentData.alignment = Math.max(segmentData.alignment,data.alignment);
								segmentData.encoded.addAll(data.encoded);
								segmentData.relocations.addAll(data.relocations);
								segmentData.symbolOffsets.addAll(data.symbolOffsets);
							}
						}
						synchronized (threadSegmentData) {
							threadSegmentData.notify();
						}
					}
				}
			};
			thread.start();
		}
		try {
			synchronized (threadSegmentData) {
				threadSegmentData.wait();
			}
		}
		catch (InterruptedException e) {
			e.printStackTrace();
		}


		if (!errors.isEmpty()) {
			return null;
		}

		// First resolve all short jump relocations
		for (Segment segment : segments) {
//			System.out.println("Segment "+segment.getName()+" has "+threadSegmentData[0].get(segment).relocations.size()+" relocations and "+threadSegmentData[0].get(segment).symbolOffsets.size()+" symbols before resolving jumps.");
			SegmentData segmentData = threadSegmentData[0].get(segment);
			resolveJumps(segmentData,segment.getnBits().get(),errors);
//			System.out.println("Segment "+segment.getName()+" has "+threadSegmentData[0].get(segment).relocations.size()+" relocations and "+threadSegmentData[0].get(segment).symbolOffsets.size()+" symbols after resolving jumps.");
		}

		if (!errors.isEmpty()) {
			return null;
		}

		// Data about imports / exports / other stuff in ".rdata" segment
		int exportsOffset = 0;
		int exportsLength = 0;
		int importsOffset = 0;
		int importsLength = 0;
		int relocationsOffset = 0;
		int relocationsLength = 0;
		int IATOffset = 0;
		int IATLength = 0;
		HashMap<Long,Long> symbolAddresses = new HashMap<Long,Long>();

		// Then determine the addresses of each segment
		long[] segmentAddresses = new long[segments.size()];
		int[] segmentSizes = new int[segments.size()];
		for (int i=0;i<segments.size();++i) {
			Segment segment = segments.get(i);
			if (segment.getAddress().get()!=Segment.ANY_ADDRESS) {
				segmentAddresses[i] = segment.getAddress().get();
			}
			else if (i>0) {
				long alignment = segment.getAlignment().get();
				// Round up to next multiple of alignment from previous segment
				segmentAddresses[i] = (segmentAddresses[i-1]+segmentSizes[i-1]+alignment-1)&~(alignment-1);
			}
			else {
				// If the first segment has no address, just make it 0 for now
				// Absolute relocations will need to be kept
				segmentAddresses[i] = 0;
			}
			System.out.println("Segment "+segment.getName()+" is at "+Long.toHexString(segmentAddresses[i])+"h");
			// Set up imports in the read-only data segment
			if (segment.getName().equals(Segment.DEFAULT_READ_ONLY_DATA_SEG_NAME)) {
				if (!importSet.isEmpty()) {
					HashMap<String,ArrayList<Function>> libraries = new HashMap<String,ArrayList<Function>>();
					// Arrange the functions by library, sorted by name.
					for (Function function : importSet.values()) {
						String library = function.getFile().getName().toString();
						ArrayList<Function> functions = libraries.get(library);
						if (functions==null) {
							functions = new ArrayList<Function>();
							libraries.put(library,functions);
							functions.add(function);
						}
						else {
							String name = function.getName().toString();
							int j=0;
							while (j<functions.size() && functions.get(j).getName().compareTo(name)<0) {
								++j;
							}
							functions.add(j,function);
						}
					}

					long rdataAddress = (int)segmentAddresses[i];
					if (segment==null) {
						String name = libraries.keySet().iterator().next();
						name = name.substring(0,name.length()-Loader.LIBRARY_INCLUDE_EXTENSION.length())+".dll";
						errors.add(new SyntaxError(null,0,0,"Operating system code can't have dynamic imports. "+name+" is one library being imported"));
					}
					// Find the sizes of the Import Address Table (IAT) and Import Directory Table (IDT)
					// The IAT is split up by library, with one null entry marking the end of each library
					int IATSize = (is64Bit?8:4)*(importSet.size()+libraries.size());
					// The IDT entries are each 20 bytes, with one at the end that's zero.
					int IDTSize = 20*(libraries.size()+1);
					// Import Lookup Table (ILT) starts after IDT and has same content/size as IAT.
					IATOffset = 0;
					IATLength = IATSize;
					importsOffset = IATSize;
					importsLength = IDTSize;
					int IATTempOffset = (int)(rdataAddress-segmentAddresses[0]+SECTION_ALIGNMENT);
					int ILTOffset = IATTempOffset+IATSize+IDTSize;
					int ILTNamesOffset = ILTOffset+IATSize;
					// Put together the list of all imported function names; most names are probably <=25 characters long.
					ByteList nameTable = new ByteList(28*importSet.size());
					ByteList IAT = new ByteList(IATSize);
					ByteList IDT = new ByteList(IDTSize);
					for (String library : libraries.keySet()) {
						for (Function function : libraries.get(library)) {
//							System.out.println("Putting in id="+function.getID()+" addr="+Long.toHexString(rdataAddress+IAT.size()));
							symbolAddresses.put(function.getID(),rdataAddress+IAT.size());
							int start = nameTable.size();
							if (is64Bit) {
								IAT.addLong(ILTNamesOffset+start);
							}
							else {
								IAT.addInt(ILTNamesOffset+start);
							}
							// Don't know the actual ordinal, so just guess zero
							nameTable.addShort((short)0);
							nameTable.addAll(function.getName().toString().getBytes());
							// Need to put one or two zeros, to make the size an even number
							if (((nameTable.size()-start)&1) != 0) {
								nameTable.add((byte)0);
							}
							else {
								nameTable.addShort((short)0);
							}
						}
						if (is64Bit) {
							IAT.addLong(0);
						}
						else {
							IAT.addInt(0);
						}
						IDT.addInt(ILTOffset);
						IDT.addLong(0);
						IDT.addInt(ILTNamesOffset+nameTable.size());
						IDT.addInt(IATTempOffset);
						int start = nameTable.size();
						nameTable.addAll((library.substring(0,library.length()-Loader.LIBRARY_INCLUDE_EXTENSION.length())+".dll").getBytes());
						// Need to put one or two zeros, to make the size an even number
						if (((nameTable.size()-start)&1) != 0) {
							nameTable.add((byte)0);
						}
						else {
							nameTable.addShort((short)0);
						}
						int nFunctions = libraries.get(library).size();
						int lookupSize = (is64Bit?8:4)*(nFunctions+1);
						ILTOffset += lookupSize;
						IATTempOffset += lookupSize;
					}
					IDT.addInt(0);
					IDT.addLong(0);
					IDT.addLong(0);
					ByteList encoded = threadSegmentData[0].get(segment).encoded;
					encoded.addAll(IAT);
					encoded.addAll(IDT);
					encoded.addAll(IAT);
					encoded.addAll(nameTable);
					segmentSizes[i] = encoded.size();
				}
			}
			segmentSizes[i] = threadSegmentData[0].get(segment).encoded.size();
			// Check for overlap, which would be problematic
			for (int j=0;j<i;++j) {
				if ((segmentAddresses[i]<segmentAddresses[j] && segmentAddresses[i]+segmentSizes[i]>segmentAddresses[j])
						|| (segmentAddresses[j]<segmentAddresses[i] && segmentAddresses[j]+segmentSizes[j]>segmentAddresses[i])
						|| (segmentAddresses[i]==segmentAddresses[j] && segmentSizes[i]>0 && segmentSizes[j]>0)) {
					synchronized (errors) {
						errors.add(new SyntaxError(null,0,0,"The segments "+segments.get(i).getName()+" ("+Long.toHexString(segmentAddresses[i])+"h-"+Long.toHexString(segmentAddresses[i]+segmentSizes[i])+"h) and "+segments.get(j).getName()+" ("+Long.toHexString(segmentAddresses[j])+"h-"+Long.toHexString(segmentAddresses[j]+segmentSizes[j])+"h) overlap."));
					}
				}
			}
		}

		if (!errors.isEmpty()) {
			return null;
		}

		// Then find the addresses of all symbols
		for (int i = 0; i<segments.size(); i++) {
			Segment segment = segments.get(i);
			SegmentData segmentData = threadSegmentData[0].get(segment);
			for (SymbolOffset o : segmentData.symbolOffsets) {
				symbolAddresses.put(o.id,o.offset+segmentAddresses[i]);
			}
		}

		// Lastly, resolve all relocations
		System.out.println("About to resolve relocations");
		for (int i = 0; i<segments.size(); i++) {
			Segment segment = segments.get(i);
			SegmentData segmentData = threadSegmentData[0].get(segment);
			int segmentAddress = (int)segmentAddresses[i];
			int mode = segment.getnBits().get();
			System.out.println("Segment " + segment.getName() + " has " + segmentData.relocations.size() + " relocations.");
			for (Relocation r : segmentData.relocations) {
				Long address = null;
				switch (r.type) {
					case RELOC_NORMAL: {
						address = symbolAddresses.get(r.symbolID);
						break;
					}
					case RELOC_DIFF: {
						Long addressA = symbolAddresses.get(r.symbolID);
						Long addressB = symbolAddresses.get(r.negativeSymbolID);
						if (addressA!=null && addressB!=null) {
							address = addressA - addressB;
						}
						break;
					}
					case RELOC_REL: {
						if (!symbolAddresses.containsKey(r.symbolID)) {
							System.err.println("Oh noes! a symbol (referenced at " + Long.toHexString(r.offset) + "h) that's not in symbolAddresses");
						}
						else {
							address = symbolAddresses.get(r.symbolID);
//							System.out.println("Getting out id="+r.symbolID+" addr="+Long.toHexString(address));
//							System.out.println("Symbol found at " + Long.toHexString(address) + "h");
							// NOTE: The +4 or +2 is because these relocations are relative to just after them.
							address -= segmentAddress + r.offset + ((mode!=16) ? 4 : 2);
						}
						break;
					}
				}
				if (address!=null) {
//					System.out.println("Found address " + Long.toHexString(address) + "h for relocation at " + Long.toHexString(r.offset));
					if (mode!=16) {
						segmentData.encoded.setInt((int)r.offset, (int)(address + segmentData.encoded.getInt((int)r.offset)));
					}
					else {
						segmentData.encoded.setShort((int)r.offset, (short)(address + segmentData.encoded.getShort((int)r.offset)));
					}
				}
			}
		}


//		// DEBUGGING: Save the segments out to files.
//		for (Segment segment : segments) {
//			SegmentData segmentData = threadSegmentData[0].get(segment);
//			try {
//				FileOutputStream output = new FileOutputStream(segment.getName().toString()+".bin");
//				output.write(segmentData.encoded.toArray());
//				output.close();
//			}
//			catch (IOException e) {
//				e.printStackTrace();
//			}
//		}

		COFFData executableData = new COFFData();
		executableData.type = COFFData.TYPE_EXE;
		executableData.entryPoint = 0;
		executableData.stackSize = 0x00200000;	// 2MB
		executableData.heapSize = 0x00200000;	// 2MB
		for (int i=0;i<segments.size();++i) {
			Segment seg = segments.get(i);
			if (seg.getName().equals(Segment.DEFAULT_CODE_SEG_NAME)) {
				executableData.code = threadSegmentData[0].get(seg).encoded.toArray();
				Function main = project.getEntryPoint();
				if (main!=null) {
					executableData.entryPoint = (int)(symbolAddresses.get(main.getID())-segmentAddresses[0]);
				}
			}
			else if (seg.getName().equals(Segment.DEFAULT_INIT_DATA_SEG_NAME)) {
				executableData.initData = threadSegmentData[0].get(seg).encoded.toArray();
			}
			else if (seg.getName().equals(Segment.DEFAULT_READ_ONLY_DATA_SEG_NAME)) {
				executableData.readOnlyData = threadSegmentData[0].get(seg).encoded.toArray();
			}
			else if (seg.getName().equals(Segment.DEFAULT_UNINIT_DATA_SEG_NAME)) {
				executableData.uninitDataSize = threadSegmentData[0].get(seg).encoded.size();
			}
		}
		executableData.exportsOffset = exportsOffset;
		executableData.exportsLength = exportsLength;
		executableData.importsOffset = importsOffset;
		executableData.importsLength = importsLength;
		executableData.relocationsOffset = relocationsOffset;
		executableData.relocationsLength = relocationsLength;
		executableData.IATOffset = IATOffset;
		executableData.IATLength = IATLength;
		return executableData;
	}

	/**
	 * This encodes a Section (including {@link CodeFile}s)
	 * @param section the Section to encode
	 * @param segmentData the set of all segments and their currently-encoded data
	 * @param importSet the set of all imports used.  NOTE: This must be synchronized-on before use, because multiple threads add to it.
	 * @param errors the list of errors as they are discovered.  NOTE: This must be synchronized-on before use, because multiple threads add to it.
	 */
	private void encode(Section section,HashMap<Segment, SegmentData> segmentData,HashMap<Long,Function> importSet,ArrayList<SyntaxError> errors) {
		for (CodeFileChunk chunk : section.getContent()) {
			if (chunk instanceof Function) {
				encode((Function)chunk,segmentData.get(chunk.getSegment()),importSet,errors);
			}
			else if (chunk instanceof GlobalVariable) {
				encode((GlobalVariable)chunk,segmentData.get(chunk.getSegment()),errors);
			}
			else if (chunk instanceof Section) {
				encode((Section)chunk,segmentData,importSet,errors);
			}
		}
	}

	protected abstract boolean encode(GlobalVariable variable,SegmentData segmentData,ArrayList<SyntaxError> errors);
	protected abstract boolean encode(Function function,SegmentData segmentData,HashMap<Long,Function> importSet,ArrayList<SyntaxError> errors);

	/**
	 * Resolves jumps in the given segment data.  All jumps to labels in the segment data are resolved as much as possible.
	 * If there are jumps to outside the segment data, they are assumed to be long, but cannot be resolved completely.
	 * NOTE: For an explanation of the algorithm, see <a href="http://arxiv.org/abs/0812.4973/">the paper on it</a>.
	 * @param segmentData the segment data to crawl for jumps
	 * @param mode the current CPU mode (16-bit, 32-bit, or 64-bit)
	 * @param errors the list of errors to be filled with any errors due to jump resolution.  NOTE: This must be synchronized-on before use, because multiple threads add to it.
	 * @return true if no RELOC_JMP_SHORT_ONLY that ended up being long, else false
	 */
	private static boolean resolveJumps(SegmentData segmentData,int mode,ArrayList<SyntaxError> errors) {
		boolean isSuccessful = true;
		ArrayList<Relocation> jumpRelocations = new ArrayList<Relocation>();
		for (Relocation r : segmentData.relocations) {
			if (r.type==RELOC_JCC_SHORT || r.type==RELOC_JMP_SHORT || r.type==RELOC_JMP_SHORT_ONLY) {
				jumpRelocations.add(r);
			}
		}
//		System.out.println("Jump Relocations: "+jumpRelocations.size());
		if (!jumpRelocations.isEmpty()) {
			HashMap<Long,Long> symbolOffsets = new HashMap<Long,Long>(segmentData.symbolOffsets.size());
			for (SymbolOffset s : segmentData.symbolOffsets) {
				symbolOffsets.put(s.id,s.offset);
			}
			final byte longUnconditionalSizeDelta = (byte)((mode!=16) ? 3 : 1);
			final byte longConditionalSizeDelta = (byte)((mode!=16) ? 4 : 2);
			LinkedList<Integer> longQueue = new LinkedList<Integer>();
			// Determine the current jump distances
			long[] jumpShortDistances = new long[jumpRelocations.size()];
			byte[] jumpSizeDeltas = new byte[jumpRelocations.size()];
			int totalSize = segmentData.encoded.size();
			// Find the jumps that are long even if all other jumps could be encoded as short.
			for (int i=0;i<jumpRelocations.size();++i) {
				Relocation r = jumpRelocations.get(i);
				jumpSizeDeltas[i] = (r.type==RELOC_JCC_SHORT) ? longConditionalSizeDelta : longUnconditionalSizeDelta;
				Long symbolOffset = symbolOffsets.get(r.symbolID);
				if (symbolOffset!=null) {
					// NOTE: The +2 is the length of a short jump, because jumps are relative to the next instruction.
					// NOTE: The -1 is because the relocation is 1 byte after the start of the jump
					jumpShortDistances[i] = r.offset+2-1-symbolOffset;
					// If guaranteed to be a long jump
					if (jumpShortDistances[i]<-128 || jumpShortDistances[i]>127) {
						if (r.type==RELOC_JMP_SHORT_ONLY) {
							isSuccessful = false;
							addShortJumpError(r,errors);

						}
						// Mark it as a long jump and add it to the queue
						r.type = RELOC_REL;
						longQueue.addLast(i);
						totalSize += jumpSizeDeltas[i];
					}
					// If guaranteed to be a short jump (i.e. still short even if all instructions it jumps over but itself turn out to be conditional long jumps)
					else if (jumpShortDistances[i]>=-44 && jumpShortDistances[i]<=42) {
						// TODO: Figure out a good way of removing these jumps from consideration without wasting too much time.
					}
				}
				// If jumping to otuside the segment data
				else {
					if (r.type==RELOC_JMP_SHORT_ONLY) {
						isSuccessful = false;
						addShortJumpError(r, errors);
					}
					// Force the jump to be long, while clearly marking it as unresolved
					jumpShortDistances[i] = Long.MAX_VALUE;
					r.type = RELOC_REL;
					longQueue.addLast(i);
					totalSize += jumpSizeDeltas[i];
				}
			}
			long[] jumpDistances = new long[jumpShortDistances.length];
			System.arraycopy(jumpShortDistances,0,jumpDistances,0,jumpShortDistances.length);
			// Go through and determine all long jumps.
			while (!longQueue.isEmpty()) {
				int longJumpIndex = longQueue.removeFirst();
				long longJumpOffset = jumpRelocations.get(longJumpIndex).offset;
				int sizeDelta = jumpSizeDeltas[longJumpIndex];
				// For each jump up to 128 bytes back
				for (int i=longJumpIndex-1; i>=0 && (longJumpOffset-jumpRelocations.get(i).offset)<128; --i) {
					Relocation r = jumpRelocations.get(i);
					// If this jump is still a short, forward jump that jumps over the new long jump
					// NOTE: The -1 from above isn't needed here since both sides of the ">" are relocation offsets.
					if (r.type!=RELOC_REL && jumpShortDistances[i]>0 && (r.offset+2+jumpShortDistances[i])>longJumpOffset) {
						jumpDistances[i] += sizeDelta;
						if (jumpDistances[i]>=128) {
							if (r.type==RELOC_JMP_SHORT_ONLY) {
								isSuccessful = false;
								addShortJumpError(r, errors);
							}
							r.type = RELOC_REL;
							longQueue.addLast(i);
							totalSize += jumpSizeDeltas[i];
						}
					}
				}
				// For each jump up to 128 bytes forward
				for (int i=longJumpIndex+1; i<jumpRelocations.size() && (jumpRelocations.get(i).offset-longJumpOffset)<=128; ++i) {
					Relocation r = jumpRelocations.get(i);
					// If this jump is still a short, backward jump that jumps over the new long jump
					// NOTE: The -1 from above isn't needed here since both sides of the "<=" are relocation offsets.
					if (r.type!=RELOC_REL && jumpShortDistances[i]<0 && (r.offset+2+jumpShortDistances[i])<=longJumpOffset) {
						jumpDistances[i] -= sizeDelta;
						if (jumpDistances[i]<-128) {
							if (r.type==RELOC_JMP_SHORT_ONLY) {
								isSuccessful = false;
								addShortJumpError(r, errors);
							}
							r.type = RELOC_REL;
							longQueue.addLast(i);
							totalSize += jumpSizeDeltas[i];
						}
					}
				}
			}
			ByteList encoded = new ByteList(totalSize);
			int start = 0;
			int symbolIndex = 0;
			int relocIndex = 0;
			int increase = 0;
			// Take the existing encoding and create a new encoding with space for the long jumps, and update the relocation offsets and symbol offsets.
			for (int i=0;i<jumpRelocations.size();++i) {
				Relocation r = jumpRelocations.get(i);
				if (r.type==RELOC_REL) {
					// NOTE: The -1 is because the relocation is 1 byte after the start of the jump
					encoded.addRange(segmentData.encoded,start,(int)(r.offset-1));
					if (jumpSizeDeltas[i]==longConditionalSizeDelta) {
						// Insert 0Fh and add 10h to turn 7x (jcc short) into 0F 8x (jcc near)
						encoded.addShort((short)((segmentData.encoded.get((int)r.offset-1)<<8) + 0x100F));
					}
					else {
						// Subtracting 2 turns EBh (jmp short) into E9h (jmp near)
						encoded.add((byte)(segmentData.encoded.get((int)r.offset-1)-2));
					}
					if (mode!=16) {
						encoded.addInt(0);
					}
					else {
						encoded.addShort((short)0);
					}
					// NOTE: The -1 is because the relocation is 1 byte after the start of the jump
					while (symbolIndex<segmentData.symbolOffsets.size() && segmentData.symbolOffsets.get(symbolIndex).offset<=r.offset-1) {
						long offset = segmentData.symbolOffsets.get(symbolIndex).offset+increase;
						segmentData.symbolOffsets.get(symbolIndex).offset = offset;
						symbolOffsets.put(segmentData.symbolOffsets.get(symbolIndex).id,offset);
						++symbolIndex;
					}
					while (segmentData.relocations.get(relocIndex)!=r) {
						segmentData.relocations.get(relocIndex).offset += increase;
						++relocIndex;
					}
					// NOTE: The +2 is the length of a short jump, because jumps are relative to the next instruction.
					// NOTE: The -1 is because the relocation is 1 byte after the start of the jump
					start = (int)(r.offset+2-1);
					// Add 1 to the offset of a long conditional relocation, since it one byte has been added before it.
					r.offset += increase + ((jumpSizeDeltas[i]==longConditionalSizeDelta) ? 1 : 0);
					++relocIndex;
					increase += jumpSizeDeltas[i];
				}
			}
			// Put in the last of the encoding (after all long jumps)
			encoded.addRange(segmentData.encoded,start,segmentData.encoded.size());
			// Update the offsets of symbols after all of the long jumps
			while (symbolIndex<symbolOffsets.size()) {
				long offset = segmentData.symbolOffsets.get(symbolIndex).offset+increase;
				segmentData.symbolOffsets.get(symbolIndex).offset = offset;
				symbolOffsets.put(segmentData.symbolOffsets.get(symbolIndex).id,offset);
				++symbolIndex;
			}
			while (relocIndex<segmentData.relocations.size()) {
				segmentData.relocations.get(relocIndex).offset += increase;
				++relocIndex;
			}
			// Put in the distances of the jumps that can be resolved.
			for (Relocation r : jumpRelocations) {
				Long symbolOffset = symbolOffsets.get(r.symbolID);
				if (symbolOffset!=null) {
					if (r.type==RELOC_REL) {
						int distance = (int)(symbolOffset - (r.offset + ((mode!=16) ? 4 : 2)));
						if (mode!=16) {
							encoded.setInt((int)r.offset, distance);
						}
						else {
							encoded.setShort((int)r.offset, (short)distance);
						}
					}
					else {
						int distance = (int)(symbolOffset - (r.offset + 1));
						encoded.set((int)r.offset, (byte)distance);
					}
					// Mark the relocation for removal.  There will be no short jumps left, so this works to mark it.
					r.type = RELOC_JMP_SHORT;
				}
			}
			// Remove jump relocations that were resolved (they are all marked by type==RELOC_JMP_SHORT).
			int destIndex = 0;
			for (int i=0;i<segmentData.relocations.size();++i) {
				Relocation r = segmentData.relocations.get(i);
				if (r.type!=RELOC_JMP_SHORT) {
					segmentData.relocations.set(destIndex++,r);
				}
			}
			for (int i=segmentData.relocations.size()-1;i>=destIndex;--i) {
				segmentData.relocations.remove(i);
			}
			segmentData.encoded = encoded;
		}
		return isSuccessful;
	}


	private static void addShortJumpError(Relocation r, ArrayList<SyntaxError> errors) {
		// Find the errant line label or function used as the jump target.
		Object[] refs = r.line.getReferences();
		int index = -1;
		for (int j=0;j<r.line.getNumReferences();++j) {
			if (refs[j]!=null && refs[j] instanceof Symbol && ((Symbol)refs[j]).getID()==r.symbolID) {
				index = j;
				break;
			}
		}
		SyntaxError error = new SyntaxError(r.line,(index>=0)?r.line.getTokenColumn(index):0,(index>=0)?r.line.getTokenColumn(index+1):r.line.length(),"This instruction only allows jumps of up to 128 bytes backward or 127 bytes forward, and it's currently trying to jump farther.\nOther jump instructions don't have this restriction.");
		r.line.addError(error);
		synchronized (errors) {
			errors.add(error);
		}
	}

	public static void savePE32(File file,COFFData data,boolean is64Bit) throws IOException {
		FileOutputStream o = new FileOutputStream(file);
		// Write the DOS header with only the initial signature "MZ" and the relocation offset of 0x40 to indicate non-DOS program.
		// Everything else is 0, because no DOS stub is included.
		byte[] empty = new byte[FILE_ALIGNMENT];
		FileUtil.writeShort(o,(short)('M'+('Z'<<8)));
		FileUtil.writeInt(o,0x30090);
		FileUtil.writeShort(o,(short)0);
		FileUtil.writeInt(o,0x4);
		FileUtil.writeInt(o,0xFFFF);
		FileUtil.writeInt(o,0xB8);
		FileUtil.writeInt(o,0x0);
		FileUtil.writeShort(o,(short)0x40);	// This is needed to indicate that there is a Windows program
		FileUtil.writeShort(o,(short)0);
		FileUtil.writeInt(o,0);
		o.write(empty,0,0x3C-0x20);
		FileUtil.writeInt(o,0xB8);	// This points to the Windows program
		o.write(empty,0,0xB8-0x40);

		// Write COFF header
		FileUtil.writeInt(o,'P'+('E'<<8));				// Signature
		FileUtil.writeShort(o,(short)(is64Bit?0x8664:0x14C));			// CPU Type is x86-64
		short sectionEntryCount = 0;
		if (data.code!=null && data.code.length>0) {
			++sectionEntryCount;
		}
		if (data.readOnlyData!=null && data.readOnlyData.length>0) {
			++sectionEntryCount;
		}
		if ((data.initData!=null && data.initData.length>0) || data.uninitDataSize>0) {
			++sectionEntryCount;
		}
		FileUtil.writeShort(o,sectionEntryCount);		// Number of section table entries
		FileUtil.writeInt(o,(int)(new Date().getTime()/1000));
		FileUtil.writeLong(o,0);
		FileUtil.writeShort(o,is64Bit?SIZEOF_PE32PLUS_HEADER:SIZEOF_PE32_HEADER);
		// Have non-libraries be non-relocatable, to avoid having to do relocation entries
		FileUtil.writeShort(o,(short)(HEADER_FLAG_EXECUTABLE|HEADER_FLAG_LARGE_ADDR|((data.type==COFFData.TYPE_DLL)?HEADER_FLAG_LIBRARY:0)|((data.relocationsLength>0)?0:HEADER_FLAG_FIXED)));

		// Write PE32+ Header
		FileUtil.writeShort(o,is64Bit?PE32PLUS_MARKER:PE32_MARKER);
		FileUtil.writeShort(o,(short)0);				// Linker major and minor version
		int fileAlignMask = FILE_ALIGNMENT-1;
		int sectionAlignMask = SECTION_ALIGNMENT-1;
		int codeSizeF = (data.code!=null)?((data.code.length+fileAlignMask)&~fileAlignMask):0;
		int codeSizeS = (codeSizeF+sectionAlignMask)&~sectionAlignMask;
		int initDataSizeF = (data.initData!=null)?((data.initData.length+fileAlignMask)&~fileAlignMask):0;
		int fullDataSizeF = (data.uninitDataSize+((data.initData!=null)?data.initData.length:0)+fileAlignMask)&~fileAlignMask;
		int fullDataSizeS = (fullDataSizeF+sectionAlignMask)&~sectionAlignMask;
		// This works out such that the headers fit into one multiple of FILE_ALIGNMENT, even if all 3 sections are present.
		int headerSize = 0xB8+0x18+(is64Bit?SIZEOF_PE32PLUS_HEADER:SIZEOF_PE32_HEADER)+sectionEntryCount*SIZEOF_SECTION_ENTRY;
		int headerSizeF = (headerSize+fileAlignMask)&~fileAlignMask;
		int headerSizeS = (headerSizeF+sectionAlignMask)&~sectionAlignMask;
		int readOnlyDataSizeF = (data.readOnlyData!=null)?((data.readOnlyData.length+fileAlignMask)&~fileAlignMask):0;
		int readOnlyDataSizeS = (readOnlyDataSizeF+sectionAlignMask)&~sectionAlignMask;
		int imageSizeS = headerSizeS+codeSizeS+fullDataSizeS+readOnlyDataSizeS;
		int codeRVA = headerSizeS;
		int rdataRVA = codeRVA+codeSizeS;
		int dataRVA = rdataRVA+readOnlyDataSizeS;
		int exportsRVA = (data.exportsLength>0) ? rdataRVA+data.exportsOffset : 0;
		int IATRVA = (data.IATLength>0) ? rdataRVA+data.IATOffset : 0;
		int importsRVA = (data.importsLength>0) ? rdataRVA+data.importsOffset : 0;
		int relocRVA = (data.relocationsLength>0) ? rdataRVA+data.relocationsOffset : 0;
		FileUtil.writeInt(o,codeSizeF);					// Code section size
		FileUtil.writeInt(o,fullDataSizeF);				// Initialized data size, including uninitialized part
		FileUtil.writeInt(o,0);							// Uninitialized data size, if it wasn't being added to the end of the init data section
		FileUtil.writeInt(o,codeRVA+data.entryPoint);
		FileUtil.writeInt(o,codeRVA);
		if (!is64Bit) {
			FileUtil.writeInt(o,rdataRVA);
			FileUtil.writeInt(o,(int)((data.type==COFFData.TYPE_DLL)?IMAGE_BASE_DLL:IMAGE_BASE_EXE));
		}
		else {
			FileUtil.writeLong(o,(data.type==COFFData.TYPE_DLL)?IMAGE_BASE_DLL:IMAGE_BASE_EXE);
		}
		FileUtil.writeInt(o,SECTION_ALIGNMENT);
		FileUtil.writeInt(o,FILE_ALIGNMENT);
		FileUtil.writeInt(o,4);							// OS major and minor version (4 means 4.0)
		FileUtil.writeInt(o,4);							// Image major and minor version
		FileUtil.writeInt(o,4);							// Subsystem major and minor version
		FileUtil.writeInt(o,0);							// Reserved
		FileUtil.writeInt(o,imageSizeS);
		FileUtil.writeInt(o,headerSizeF);
		// TODO: Figure out how to calculate the checksum and store it next
		FileUtil.writeInt(o,0);
		FileUtil.writeInt(o,0x00000002);				// Subsystem and DLL Characteristics
		if (is64Bit) {
			FileUtil.writeLong(o,0x00100000);//data.stackSize);
			FileUtil.writeLong(o,0x00001000);//data.stackSize);
			FileUtil.writeLong(o,0x00100000);//data.heapSize);
			FileUtil.writeLong(o,0x00001000);//data.heapSize);
		}
		else {
			FileUtil.writeInt(o,0x00100000);//(int)data.stackSize);
			FileUtil.writeInt(o,0x00001000);//(int)data.stackSize);
			FileUtil.writeInt(o,0x00100000);//(int)data.heapSize);
			FileUtil.writeInt(o,0x00001000);//(int)data.heapSize);
		}
		FileUtil.writeInt(o,0);
		FileUtil.writeInt(o,NUM_RVA_TABLE_ENTRIES);

		// Write RVAs (Relative Virtual Addresses) & sizes to finish off PE32+ header
		FileUtil.writeInt(o,exportsRVA);
		FileUtil.writeInt(o,data.exportsLength);
		FileUtil.writeInt(o,importsRVA);
		FileUtil.writeInt(o,data.importsLength);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);
		FileUtil.writeInt(o,relocRVA);
		FileUtil.writeInt(o,data.relocationsLength);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);
		FileUtil.writeInt(o,IATRVA);
		FileUtil.writeInt(o,data.IATLength);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);
		FileUtil.writeLong(o,0);

		// Write out the section table
		if (data.code!=null && data.code.length>0) {
			FileUtil.writeString8(o,".text");
			o.write(0);
			o.write(0);
			o.write(0);
			FileUtil.writeInt(o,data.code.length);
			FileUtil.writeInt(o,codeRVA);
			FileUtil.writeInt(o,codeSizeF);
			FileUtil.writeInt(o,headerSizeF);
			FileUtil.writeLong(o,0);
			FileUtil.writeInt(o,0);
			FileUtil.writeInt(o,SECTION_FLAG_READABLE|SECTION_FLAG_EXECUTABLE|SECTION_FLAG_CONTAINS_CODE);
		}
		if (data.readOnlyData!=null && data.readOnlyData.length>0) {
			FileUtil.writeString8(o,".rdata");
			o.write(0);
			o.write(0);
			FileUtil.writeInt(o,data.initData.length);
			FileUtil.writeInt(o,rdataRVA);
			FileUtil.writeInt(o,readOnlyDataSizeF);
			FileUtil.writeInt(o,headerSizeF+codeSizeF);
			FileUtil.writeLong(o,0);
			FileUtil.writeInt(o,0);
			FileUtil.writeInt(o,SECTION_FLAG_READABLE|SECTION_FLAG_CONTAINS_INIT_DATA);
		}
		if ((data.initData!=null && data.initData.length>0) || data.uninitDataSize>0) {
			FileUtil.writeString8(o,".data");
			o.write(0);
			o.write(0);
			o.write(0);
			FileUtil.writeInt(o,data.uninitDataSize+((data.initData!=null)?data.initData.length:0));
			FileUtil.writeInt(o,dataRVA);
			FileUtil.writeInt(o,initDataSizeF);
			FileUtil.writeInt(o,headerSizeF+codeSizeF+readOnlyDataSizeF);
			FileUtil.writeLong(o,0);
			FileUtil.writeInt(o,0);
			FileUtil.writeInt(o,SECTION_FLAG_READABLE|SECTION_FLAG_WRITABLE|((data.initData!=null)?SECTION_FLAG_CONTAINS_INIT_DATA:0));
		}
		o.write(empty,0,headerSizeF-headerSize);
		if (data.code!=null && data.code.length>0) {
			o.write(data.code);
			o.write(empty,0,codeSizeF-data.code.length);
		}
		if (data.readOnlyData!=null && data.readOnlyData.length>0) {
			o.write(data.readOnlyData);
			o.write(empty,0,readOnlyDataSizeF-data.readOnlyData.length);
		}
		if (data.initData!=null && data.initData.length>0) {
			o.write(data.initData);
			o.write(empty,0,initDataSizeF-data.initData.length);
		}
		o.close();
	}

	public static class COFFData {
		public static final byte TYPE_EXE	= 0;
		public static final byte TYPE_DLL	= 1;
		public static final byte TYPE_OBJ	= 2;
		public static final byte TYPE_LIB	= 3;


		byte	type;
		int		uninitDataSize;
		int		entryPoint;		// Relative to code start
		long	stackSize;
		long	heapSize;
		byte[]	initData;
		byte[]	readOnlyData;
		byte[]	code;
		int		exportsOffset;
		int		exportsLength;
		int		IATOffset;
		int		IATLength;
		int		importsOffset;
		int		importsLength;
		int		relocationsOffset;
		int		relocationsLength;
	}
	public static class SegmentData {
		public int						alignment;
		public ByteList					encoded;
		public ArrayList<Relocation>	relocations;
		public ArrayList<SymbolOffset>	symbolOffsets;

		public SegmentData(ByteList encoded, ArrayList<Relocation> relocations, ArrayList<SymbolOffset> symbolOffsets) {
			this.alignment = 1;
			this.encoded = encoded;
			this.relocations = relocations;
			this.symbolOffsets = symbolOffsets;
		}
	}

	public static class Relocation implements Copiable<Relocation> {
		public Line line;
		public int	type;
		public long	offset;
		public long	symbolID;
		public long	negativeSymbolID;

		public Relocation(Line line,Symbol symbol) {
			this(line,RELOC_NORMAL,-1,symbol.getID(),-1);
		}

		public Relocation(Line line,int type, long offset, long symbolID) {
			this(line,type,offset,symbolID,-1);
		}

		public Relocation(Line line,int type, long offset, long symbolID, long negativeSymbolID) {
			this.line = line;
			this.type = type;
			this.offset = offset;
			this.symbolID = symbolID;
			this.negativeSymbolID = negativeSymbolID;
		}

		public boolean equals(Object o) {
			if (!(o instanceof Relocation)) {
				return false;
			}
			Relocation that = (Relocation)o;
			return type==that.type && offset==that.offset && symbolID==that.symbolID && negativeSymbolID==that.negativeSymbolID;
		}

		public Relocation copy() {
			return new Relocation(line,type,offset,symbolID,negativeSymbolID);
		}
	}

	public static class SymbolOffset {
		public long id;
		public long offset;

		public SymbolOffset(long id, long offset) {
			this.id = id;
			this.offset = offset;
		}
	}
}

Show details Hide details

Change log

r177 by hackulous on Mar 29, 2009 Diff

-removed CompileOptions table
-changed MessagePopup to extend JDialog
-executables now appear in the directory
of the project file
-@@ line labels are now supported
-fixed bug where multiple line labels with
the same name were allowed again
-fixed bug parsing immediate values larger
than 2^32-1
-removed many System.out.println() calls
-fixed bug where inline renaming would
only occur if adding letters, not deleting
...

Go to:

Project members, sign in to write a code review

Older revisions

r172 by hackulous on Mar 24, 2009 Diff

-now support alignments properly,
albeit not space-optimally
-now support conditional assembly
(just IF, ENDIF, .ERR)
-put in code to look for an error that
...

r169 by hackulous on Mar 22, 2009 Diff

-added vertical CustomSplitPane,
mostly for displaying errors at the
moment
-fixed silly mistake in encoding
internal "invoke" calls
...

r167 by hackulous on Mar 22, 2009 Diff

-added keyword to handle register
parameters and handled them in
encoding, etc.
-fixed bug with string literals again
(wasn't fixed on last commit)
...

All revisions of this file

File info

Size: 41769 bytes, 988 lines

View raw file