1/* 2 * [The "BSD licence"] 3 * Copyright (c) 2010 Ben Gruver (JesusFreke) 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29package org.jf.dexlib.Util; 30 31import org.jf.dexlib.CodeItem; 32import org.jf.dexlib.TypeIdItem; 33 34import java.util.ArrayList; 35import java.util.HashMap; 36import java.util.LinkedList; 37import java.util.List; 38 39public class TryListBuilder 40{ 41 /*TODO: add logic to merge adjacent, identical try blocks, and remove superflous handlers 42 Also provide a "strict" mode, where the above isn't performed, which will be useful to be able to 43 exactly reproduce the original .dex file (for testing/verification purposes)*/ 44 45 46 private TryRange firstTryRange = new TryRange(0,0); 47 private TryRange lastTryRange = new TryRange(0,0); 48 49 public TryListBuilder() { 50 firstTryRange.next = lastTryRange; 51 lastTryRange.previous = firstTryRange; 52 } 53 54 private class TryRange 55 { 56 public TryRange previous = null; 57 public TryRange next = null; 58 59 public int startAddress; 60 public int endAddress; 61 public LinkedList<Handler> handlers; 62 63 public int catchAllHandlerAddress; 64 65 public TryRange(int startAddress, int endAddress) { 66 this.startAddress = startAddress; 67 this.endAddress = endAddress; 68 this.handlers = new LinkedList<Handler>(); 69 this.previous = null; 70 this.next = null; 71 catchAllHandlerAddress = -1; 72 } 73 74 public void append(TryRange tryRange) { 75 /*we use a dummy last item, so this.next will always 76 have a value*/ 77 this.next.previous = tryRange; 78 tryRange.next = this.next; 79 80 this.next = tryRange; 81 tryRange.previous = this; 82 } 83 84 public void prepend(TryRange tryRange){ 85 /*we use a dummy first item, so this.previous will always 86 have a value*/ 87 this.previous.next = tryRange; 88 tryRange.previous = this.previous; 89 90 this.previous = tryRange; 91 tryRange.next = this; 92 } 93 94 /** 95 * This splits the current range into two ranges at the given 96 * address. The existing range will be shortened to the first 97 * half, and a new range will be created and returned for the 98 * 2nd half. 99 * @param address The address to split at 100 * @return The 2nd half of the 101 */ 102 public TryRange split(int address) { 103 //this is a private class, so address is assumed 104 //to be valid 105 106 TryRange tryRange = new TryRange(address, endAddress); 107 tryRange.catchAllHandlerAddress = this.catchAllHandlerAddress; 108 tryRange.handlers.addAll(this.handlers); 109 append(tryRange); 110 111 this.endAddress = address; 112 113 return tryRange; 114 } 115 116 public void appendHandler(Handler handler) { 117 handlers.addLast(handler); 118 } 119 120 public void prependHandler(Handler handler) { 121 handlers.addFirst(handler); 122 } 123 } 124 125 private class Handler 126 { 127 public final TypeIdItem type; 128 public final int handlerAddress; 129 130 public Handler(TypeIdItem type, int handlerAddress) { 131 this.type = type; 132 this.handlerAddress = handlerAddress; 133 } 134 } 135 136 public Pair<List<CodeItem.TryItem>, List<CodeItem.EncodedCatchHandler>> encodeTries() { 137 if (firstTryRange.next == lastTryRange) { 138 return new Pair<List<CodeItem.TryItem>, List<CodeItem.EncodedCatchHandler>>(null, null); 139 } 140 141 ArrayList<CodeItem.TryItem> tries = new ArrayList<CodeItem.TryItem>(); 142 ArrayList<CodeItem.EncodedCatchHandler> handlers = new ArrayList<CodeItem.EncodedCatchHandler>(); 143 144 HashMap<CodeItem.EncodedCatchHandler, CodeItem.EncodedCatchHandler> handlerDict = 145 new HashMap<CodeItem.EncodedCatchHandler, CodeItem.EncodedCatchHandler>(); 146 147 TryRange tryRange = firstTryRange.next; 148 149 while (tryRange != lastTryRange) { 150 CodeItem.EncodedTypeAddrPair[] encodedTypeAddrPairs = 151 new CodeItem.EncodedTypeAddrPair[tryRange.handlers.size()]; 152 153 int index = 0; 154 for (Handler handler: tryRange.handlers) { 155 CodeItem.EncodedTypeAddrPair encodedTypeAddrPair = new CodeItem.EncodedTypeAddrPair( 156 handler.type, 157 handler.handlerAddress); 158 encodedTypeAddrPairs[index++] = encodedTypeAddrPair; 159 } 160 161 CodeItem.EncodedCatchHandler encodedCatchHandler = new CodeItem.EncodedCatchHandler( 162 encodedTypeAddrPairs, 163 tryRange.catchAllHandlerAddress); 164 CodeItem.EncodedCatchHandler internedEncodedCatchHandler = handlerDict.get(encodedCatchHandler); 165 if (internedEncodedCatchHandler == null) { 166 handlerDict.put(encodedCatchHandler, encodedCatchHandler); 167 handlers.add(encodedCatchHandler); 168 } else { 169 encodedCatchHandler = internedEncodedCatchHandler; 170 } 171 172 CodeItem.TryItem tryItem = new CodeItem.TryItem( 173 tryRange.startAddress, 174 tryRange.endAddress - tryRange.startAddress, 175 encodedCatchHandler); 176 tries.add(tryItem); 177 178 tryRange = tryRange.next; 179 } 180 181 return new Pair<List<CodeItem.TryItem>, List<CodeItem.EncodedCatchHandler>>(tries, handlers); 182 } 183 184 public void addCatchAllHandler(int startAddress, int endAddress, int handlerAddress) { 185 TryRange startRange; 186 TryRange endRange; 187 188 Pair<TryRange, TryRange> ranges = getBoundingRanges(startAddress, endAddress); 189 startRange = ranges.first; 190 endRange = ranges.second; 191 192 int previousEnd = startAddress; 193 TryRange tryRange = startRange; 194 195 /*Now we have the start and end ranges that exactly match the start and end 196 of the range being added. We need to iterate over all the ranges from the start 197 to end range inclusively, and append the handler to the end of each range's handler 198 list. We also need to create a new range for any "holes" in the existing ranges*/ 199 do 200 { 201 //is there a hole? If so, add a new range to fill the hole 202 if (tryRange.startAddress > previousEnd) { 203 TryRange newRange = new TryRange(previousEnd, tryRange.startAddress); 204 tryRange.prepend(newRange); 205 tryRange = newRange; 206 } 207 208 if (tryRange.catchAllHandlerAddress == -1) { 209 tryRange.catchAllHandlerAddress = handlerAddress; 210 } 211 212 previousEnd = tryRange.endAddress; 213 tryRange = tryRange.next; 214 } while (tryRange.previous != endRange); 215 } 216 217 public Pair<TryRange, TryRange> getBoundingRanges(int startAddress, int endAddress) { 218 TryRange startRange = null; 219 TryRange endRange = null; 220 221 TryRange tryRange = firstTryRange.next; 222 while (tryRange != lastTryRange) { 223 if (startAddress == tryRange.startAddress) { 224 //|-----| 225 //^------ 226 /*Bam. We hit the start of the range right on the head*/ 227 startRange = tryRange; 228 break; 229 } else if (startAddress > tryRange.startAddress && startAddress < tryRange.endAddress) { 230 //|-----| 231 // ^---- 232 /*Almost. The start of the range being added is in the middle 233 of an existing try range. We need to split the existing range 234 at the start address of the range being added*/ 235 startRange = tryRange.split(startAddress); 236 break; 237 }else if (startAddress < tryRange.startAddress) { 238 if (endAddress <= tryRange.startAddress) { 239 // |-----| 240 //^--^ 241 /*Oops, totally too far! The new range doesn't overlap any existing 242 ones, so we just add it and return*/ 243 startRange = new TryRange(startAddress, endAddress); 244 tryRange.prepend(startRange); 245 return new Pair<TryRange, TryRange>(startRange, startRange); 246 } else { 247 // |-----| 248 //^--------- 249 /*Oops, too far! We've passed the start of the range being added, but 250 the new range does overlap this one. We need to add a new range just 251 before this one*/ 252 startRange = new TryRange(startAddress, tryRange.startAddress); 253 tryRange.prepend(startRange); 254 break; 255 } 256 } 257 258 tryRange = tryRange.next; 259 } 260 261 //|-----| 262 // ^----- 263 /*Either the list of tries is blank, or all the tries in the list 264 end before the range being added starts. In either case, we just need 265 to add a new range at the end of the list*/ 266 if (startRange == null) { 267 startRange = new TryRange(startAddress, endAddress); 268 lastTryRange.prepend(startRange); 269 return new Pair<TryRange, TryRange>(startRange, startRange); 270 } 271 272 tryRange = startRange; 273 while (tryRange != lastTryRange) { 274 if (tryRange.endAddress == endAddress) { 275 //|-----| 276 //------^ 277 /*Bam! We hit the end right on the head.*/ 278 endRange = tryRange; 279 break; 280 } else if (tryRange.startAddress < endAddress && tryRange.endAddress > endAddress) { 281 //|-----| 282 //--^ 283 /*Almost. The range being added ends in the middle of an 284 existing range. We need to split the existing range 285 at the end of the range being added.*/ 286 tryRange.split(endAddress); 287 endRange = tryRange; 288 break; 289 } else if (tryRange.startAddress >= endAddress) { 290 //|-----| |-----| 291 //-----------^ 292 /*Oops, too far! The current range starts after the range being added 293 ends. We need to create a new range that starts at the end of the 294 previous range, and ends at the end of the range being added*/ 295 endRange = new TryRange(tryRange.previous.endAddress, endAddress); 296 tryRange.prepend(endRange); 297 break; 298 } 299 tryRange = tryRange.next; 300 } 301 302 //|-----| 303 //--------^ 304 /*The last range in the list ended before the end of the range being added. 305 We need to add a new range that starts at the end of the last range in the 306 list, and ends at the end of the range being added.*/ 307 if (endRange == null) { 308 endRange = new TryRange(lastTryRange.previous.endAddress, endAddress); 309 lastTryRange.prepend(endRange); 310 } 311 312 return new Pair<TryRange, TryRange>(startRange, endRange); 313 } 314 315 public void addHandler(TypeIdItem type, int startAddress, int endAddress, int handlerAddress) { 316 TryRange startRange; 317 TryRange endRange; 318 319 //TODO: need to check for pre-existing exception types in the handler list? 320 321 Pair<TryRange, TryRange> ranges = getBoundingRanges(startAddress, endAddress); 322 startRange = ranges.first; 323 endRange = ranges.second; 324 Handler handler = new Handler(type, handlerAddress); 325 326 int previousEnd = startAddress; 327 TryRange tryRange = startRange; 328 329 /*Now we have the start and end ranges that exactly match the start and end 330 of the range being added. We need to iterate over all the ranges from the start 331 to end range inclusively, and append the handler to the end of each range's handler 332 list. We also need to create a new range for any "holes" in the existing ranges*/ 333 do 334 { 335 //is there a hole? If so, add a new range to fill the hole 336 if (tryRange.startAddress > previousEnd) { 337 TryRange newRange = new TryRange(previousEnd, tryRange.startAddress); 338 tryRange.prepend(newRange); 339 tryRange = newRange; 340 } 341 342 tryRange.appendHandler(handler); 343 previousEnd = tryRange.endAddress; 344 tryRange = tryRange.next; 345 } while (tryRange.previous != endRange); 346 } 347} 348