12bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson/* 22bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Copyright (C) 2008 The Android Open Source Project 32bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * 42bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 52bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * you may not use this file except in compliance with the License. 62bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * You may obtain a copy of the License at 72bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * 82bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 92bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * 102bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Unless required by applicable law or agreed to in writing, software 112bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 122bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * See the License for the specific language governing permissions and 142bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * limitations under the License. 152bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson */ 162bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 172bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilsonpackage com.android.dex; 182bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 192bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilsonimport com.android.dex.util.ByteInput; 202bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilsonimport com.android.dex.util.ByteOutput; 212bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 222bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson/** 232bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Reads and writes DWARFv3 LEB 128 signed and unsigned integers. See DWARF v3 242bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * section 7.6. 252bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson */ 262bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilsonpublic final class Leb128 { 272bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson private Leb128() { 282bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 292bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 302bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson /** 312bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Gets the number of bytes in the unsigned LEB128 encoding of the 322bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * given value. 332bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * 342bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * @param value the value in question 352bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * @return its write size, in bytes 362bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson */ 372bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson public static int unsignedLeb128Size(int value) { 382bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson // TODO: This could be much cleverer. 392bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 402bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int remaining = value >> 7; 412bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int count = 0; 422bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 432bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson while (remaining != 0) { 442bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson remaining >>= 7; 452bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson count++; 462bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 472bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 482bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson return count + 1; 492bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 502bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 512bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson /** 522bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Gets the number of bytes in the signed LEB128 encoding of the 532bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * given value. 542bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * 552bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * @param value the value in question 562bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * @return its write size, in bytes 572bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson */ 582bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson public static int signedLeb128Size(int value) { 592bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson // TODO: This could be much cleverer. 602bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 612bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int remaining = value >> 7; 622bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int count = 0; 632bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson boolean hasMore = true; 642bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int end = ((value & Integer.MIN_VALUE) == 0) ? 0 : -1; 652bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 662bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson while (hasMore) { 672bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson hasMore = (remaining != end) 682bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson || ((remaining & 1) != ((value >> 6) & 1)); 692bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 702bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson value = remaining; 712bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson remaining >>= 7; 722bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson count++; 732bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 742bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 752bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson return count; 762bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 772bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 782bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson /** 792bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Reads an signed integer from {@code in}. 802bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson */ 812bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson public static int readSignedLeb128(ByteInput in) { 822bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int result = 0; 832bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int cur; 842bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int count = 0; 852bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int signBits = -1; 862bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 872bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson do { 882bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson cur = in.readByte() & 0xff; 892bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson result |= (cur & 0x7f) << (count * 7); 902bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson signBits <<= 7; 912bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson count++; 922bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } while (((cur & 0x80) == 0x80) && count < 5); 932bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 942bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson if ((cur & 0x80) == 0x80) { 952bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson throw new DexException("invalid LEB128 sequence"); 962bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 972bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 982bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson // Sign extend if appropriate 992bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson if (((signBits >> 1) & result) != 0 ) { 1002bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson result |= signBits; 1012bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 1022bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1032bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson return result; 1042bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 1052bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1062bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson /** 1072bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Reads an unsigned integer from {@code in}. 1082bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson */ 1092bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson public static int readUnsignedLeb128(ByteInput in) { 1102bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int result = 0; 1112bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int cur; 1122bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int count = 0; 1132bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1142bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson do { 1152bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson cur = in.readByte() & 0xff; 1162bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson result |= (cur & 0x7f) << (count * 7); 1172bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson count++; 1182bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } while (((cur & 0x80) == 0x80) && count < 5); 1192bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1202bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson if ((cur & 0x80) == 0x80) { 1212bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson throw new DexException("invalid LEB128 sequence"); 1222bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 1232bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1242bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson return result; 1252bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 1262bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1272bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson /** 1282bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Writes {@code value} as an unsigned integer to {@code out}, starting at 1292bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * {@code offset}. Returns the number of bytes written. 1302bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson */ 1312bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson public static void writeUnsignedLeb128(ByteOutput out, int value) { 1322bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int remaining = value >>> 7; 1332bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1342bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson while (remaining != 0) { 1352bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson out.writeByte((byte) ((value & 0x7f) | 0x80)); 1362bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson value = remaining; 1372bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson remaining >>>= 7; 1382bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 1392bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1402bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson out.writeByte((byte) (value & 0x7f)); 1412bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 1422bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1432bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson /** 1442bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * Writes {@code value} as a signed integer to {@code out}, starting at 1452bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson * {@code offset}. Returns the number of bytes written. 1462bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson */ 1472bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson public static void writeSignedLeb128(ByteOutput out, int value) { 1482bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int remaining = value >> 7; 1492bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson boolean hasMore = true; 1502bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson int end = ((value & Integer.MIN_VALUE) == 0) ? 0 : -1; 1512bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1522bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson while (hasMore) { 1532bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson hasMore = (remaining != end) 1542bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson || ((remaining & 1) != ((value >> 6) & 1)); 1552bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson 1562bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson out.writeByte((byte) ((value & 0x7f) | (hasMore ? 0x80 : 0))); 1572bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson value = remaining; 1582bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson remaining >>= 7; 1592bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 1602bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson } 1612bea5ee615b0f4add658d5660bd81c5145a0d05eJesse Wilson} 162