1 /* 2 * Copyright 2013, Google Inc. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following disclaimer 13 * in the documentation and/or other materials provided with the 14 * distribution. 15 * * Neither the name of Google Inc. nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 package org.jf.dexlib2.util; 33 34 import com.google.common.base.Strings; 35 import com.google.common.collect.Lists; 36 import com.google.common.collect.Maps; 37 38 import org.jf.util.ExceptionWithContext; 39 import org.jf.util.Hex; 40 import org.jf.util.TwoColumnOutput; 41 42 import javax.annotation.Nonnull; 43 import javax.annotation.Nullable; 44 import java.io.IOException; 45 import java.io.Writer; 46 import java.util.List; 47 import java.util.Map; 48 import java.util.TreeMap; 49 50 /** 51 * Collects/presents a set of textual annotations, each associated with a range of bytes or a specific point 52 * between bytes. 53 * 54 * Point annotations cannot occur within the middle of a range annotation, only at the endpoints, or some other area 55 * with no range annotation. 56 * 57 * Multiple point annotations can be defined for a given point. They will be printed in insertion order. 58 * 59 * Only a single range annotation may exist for any given range of bytes. Range annotations may not overlap. 60 */ 61 public class AnnotatedBytes { 62 /** 63 * This defines the bytes ranges and their associated range and point annotations. 64 * 65 * A range is defined by 2 consecutive keys in the map. The first key is the inclusive start point, the second key 66 * is the exclusive end point. The range annotation for a range is associated with the first key for that range. 67 * The point annotations for a point are associated with the key at that point. 68 */ 69 @Nonnull private TreeMap<Integer, AnnotationEndpoint> annotatations = Maps.newTreeMap(); 70 71 private int cursor; 72 private int indentLevel; 73 74 /** >= 40 (if used); the desired maximum output width */ 75 private int outputWidth; 76 77 /** 78 * >= 8 (if used); the number of bytes of hex output to use 79 * in annotations 80 */ 81 private int hexCols = 8; 82 83 private int startLimit = -1; 84 private int endLimit = -1; 85 86 public AnnotatedBytes(int width) { 87 this.outputWidth = width; 88 } 89 90 /** 91 * Moves the cursor to a new location 92 * 93 * @param offset The offset to move to 94 */ 95 public void moveTo(int offset) { 96 cursor = offset; 97 } 98 99 /** 100 * Moves the cursor forward or backward by some amount 101 * 102 * @param offset The amount to move the cursor 103 */ 104 public void moveBy(int offset) { 105 cursor += offset; 106 } 107 108 public void annotateTo(int offset, @Nonnull String msg, Object... formatArgs) { 109 annotate(offset - cursor, msg, formatArgs); 110 } 111 112 /** 113 * Add an annotation of the given length at the current location. 114 * 115 * The location 116 * 117 * 118 * @param length the length of data being annotated 119 * @param msg the annotation message 120 * @param formatArgs format arguments to pass to String.format 121 */ 122 public void annotate(int length, @Nonnull String msg, Object... formatArgs) { 123 if (startLimit != -1 && endLimit != -1 && (cursor < startLimit || cursor >= endLimit)) { 124 throw new ExceptionWithContext("Annotating outside the parent bounds"); 125 } 126 127 String formattedMsg; 128 if (formatArgs != null && formatArgs.length > 0) { 129 formattedMsg = String.format(msg, formatArgs); 130 } else { 131 formattedMsg = msg; 132 } 133 int exclusiveEndOffset = cursor + length; 134 135 AnnotationEndpoint endPoint = null; 136 137 // Do we have an endpoint at the beginning of this annotation already? 138 AnnotationEndpoint startPoint = annotatations.get(cursor); 139 if (startPoint == null) { 140 // Nope. We need to check that we're not in the middle of an existing range annotation. 141 Map.Entry<Integer, AnnotationEndpoint> previousEntry = annotatations.lowerEntry(cursor); 142 if (previousEntry != null) { 143 AnnotationEndpoint previousAnnotations = previousEntry.getValue(); 144 AnnotationItem previousRangeAnnotation = previousAnnotations.rangeAnnotation; 145 if (previousRangeAnnotation != null) { 146 throw new ExceptionWithContext( 147 "Cannot add annotation %s, due to existing annotation %s", 148 formatAnnotation(cursor, cursor + length, formattedMsg), 149 formatAnnotation(previousEntry.getKey(), 150 previousRangeAnnotation.annotation)); 151 } 152 } 153 } else if (length > 0) { 154 AnnotationItem existingRangeAnnotation = startPoint.rangeAnnotation; 155 if (existingRangeAnnotation != null) { 156 throw new ExceptionWithContext( 157 "Cannot add annotation %s, due to existing annotation %s", 158 formatAnnotation(cursor, cursor + length, formattedMsg), 159 formatAnnotation(cursor, existingRangeAnnotation.annotation)); 160 } 161 } 162 163 if (length > 0) { 164 // Ensure that there is no later annotation that would intersect with this one 165 Map.Entry<Integer, AnnotationEndpoint> nextEntry = annotatations.higherEntry(cursor); 166 if (nextEntry != null) { 167 int nextKey = nextEntry.getKey(); 168 if (nextKey < exclusiveEndOffset) { 169 // there is an endpoint that would intersect with this annotation. Find one of the annotations 170 // associated with the endpoint, to print in the error message 171 AnnotationEndpoint nextEndpoint = nextEntry.getValue(); 172 AnnotationItem nextRangeAnnotation = nextEndpoint.rangeAnnotation; 173 if (nextRangeAnnotation != null) { 174 throw new ExceptionWithContext( 175 "Cannot add annotation %s, due to existing annotation %s", 176 formatAnnotation(cursor, cursor + length, formattedMsg), 177 formatAnnotation(nextKey, nextRangeAnnotation.annotation)); 178 } 179 if (nextEndpoint.pointAnnotations.size() > 0) { 180 throw new ExceptionWithContext( 181 "Cannot add annotation %s, due to existing annotation %s", 182 formatAnnotation(cursor, cursor + length, formattedMsg), 183 formatAnnotation(nextKey, nextKey, 184 nextEndpoint.pointAnnotations.get(0).annotation)); 185 } 186 // There are no annotations on this endpoint. This "shouldn't" happen. We can still throw an exception. 187 throw new ExceptionWithContext( 188 "Cannot add annotation %s, due to existing annotation endpoint at %d", 189 formatAnnotation(cursor, cursor + length, formattedMsg), 190 nextKey); 191 } 192 193 if (nextKey == exclusiveEndOffset) { 194 // the next endpoint matches the end of the annotation we are adding 195 endPoint = nextEntry.getValue(); 196 } 197 } 198 } 199 200 // Now, actually add the annotation 201 // If startPoint is null, we need to create a new one and add it to annotations. Otherwise, we just need to add 202 // the annotation to the existing AnnotationEndpoint 203 // the range annotation 204 if (startPoint == null) { 205 startPoint = new AnnotationEndpoint(); 206 annotatations.put(cursor, startPoint); 207 } 208 if (length == 0) { 209 startPoint.pointAnnotations.add(new AnnotationItem(indentLevel, formattedMsg)); 210 } else { 211 startPoint.rangeAnnotation = new AnnotationItem(indentLevel, formattedMsg); 212 213 // If endPoint is null, we need to create a new, empty one and add it to annotations 214 if (endPoint == null) { 215 endPoint = new AnnotationEndpoint(); 216 annotatations.put(exclusiveEndOffset, endPoint); 217 } 218 } 219 220 cursor += length; 221 } 222 223 private String formatAnnotation(int offset, String annotationMsg) { 224 Integer endOffset = annotatations.higherKey(offset); 225 return formatAnnotation(offset, endOffset, annotationMsg); 226 } 227 228 private String formatAnnotation(int offset, Integer endOffset, String annotationMsg) { 229 if (endOffset != null) { 230 return String.format("[0x%x, 0x%x) \"%s\"", offset, endOffset, annotationMsg); 231 } else { 232 return String.format("[0x%x, ) \"%s\"", offset, annotationMsg); 233 } 234 } 235 236 public void indent() { 237 indentLevel++; 238 } 239 240 public void deindent() { 241 indentLevel--; 242 if (indentLevel < 0) { 243 indentLevel = 0; 244 } 245 } 246 247 public int getCursor() { 248 return cursor; 249 } 250 251 private static class AnnotationEndpoint { 252 /** Annotations that are associated with a specific point between bytes */ 253 @Nonnull 254 public final List<AnnotationItem> pointAnnotations = Lists.newArrayList(); 255 /** Annotations that are associated with a range of bytes */ 256 @Nullable 257 public AnnotationItem rangeAnnotation = null; 258 } 259 260 private static class AnnotationItem { 261 public final int indentLevel; 262 public final String annotation; 263 264 public AnnotationItem(int indentLevel, String annotation) { 265 this.indentLevel = indentLevel; 266 this.annotation = annotation; 267 } 268 } 269 270 /** 271 * Gets the width of the right side containing the annotations 272 * @return 273 */ 274 public int getAnnotationWidth() { 275 int leftWidth = 8 + (hexCols * 2) + (hexCols / 2); 276 277 return outputWidth - leftWidth; 278 } 279 280 /** 281 * Writes the annotated content of this instance to the given writer. 282 * 283 * @param out non-null; where to write to 284 */ 285 public void writeAnnotations(Writer out, byte[] data) throws IOException { 286 int rightWidth = getAnnotationWidth(); 287 int leftWidth = outputWidth - rightWidth - 1; 288 289 String padding = Strings.repeat(" ", 1000); 290 291 TwoColumnOutput twoc = new TwoColumnOutput(out, leftWidth, rightWidth, "|"); 292 293 Integer[] keys = new Integer[annotatations.size()]; 294 keys = annotatations.keySet().toArray(keys); 295 296 AnnotationEndpoint[] values = new AnnotationEndpoint[annotatations.size()]; 297 values = annotatations.values().toArray(values); 298 299 for (int i=0; i<keys.length-1; i++) { 300 int rangeStart = keys[i]; 301 int rangeEnd = keys[i+1]; 302 303 AnnotationEndpoint annotations = values[i]; 304 305 for (AnnotationItem pointAnnotation: annotations.pointAnnotations) { 306 String paddingSub = padding.substring(0, pointAnnotation.indentLevel*2); 307 twoc.write("", paddingSub + pointAnnotation.annotation); 308 } 309 310 String right; 311 AnnotationItem rangeAnnotation = annotations.rangeAnnotation; 312 if (rangeAnnotation != null) { 313 right = padding.substring(0, rangeAnnotation.indentLevel*2); 314 right += rangeAnnotation.annotation; 315 } else { 316 right = ""; 317 } 318 319 String left = Hex.dump(data, rangeStart, rangeEnd - rangeStart, rangeStart, hexCols, 6); 320 321 twoc.write(left, right); 322 } 323 324 int lastKey = keys[keys.length-1]; 325 if (lastKey < data.length) { 326 String left = Hex.dump(data, lastKey, data.length - lastKey, lastKey, hexCols, 6); 327 twoc.write(left, ""); 328 } 329 } 330 331 public void setLimit(int start, int end) { 332 this.startLimit = start; 333 this.endLimit = end; 334 } 335 336 public void clearLimit() { 337 this.startLimit = -1; 338 this.endLimit = -1; 339 } 340 }