1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2008 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.util; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Reads and writes DWARFv3 LEB 128 signed and unsigned integers. See DWARF v3 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * section 7.6. 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic final class Leb128Utils { 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * This class is uninstantiable. 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private Leb128Utils() { 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // This space intentionally left blank. 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the number of bytes in the unsigned LEB128 encoding of the 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * given value. 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value the value in question 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return its write size, in bytes 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static int unsignedLeb128Size(int value) { 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // TODO: This could be much cleverer. 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int remaining = value >> 7; 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int count = 0; 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (remaining != 0) { 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson remaining >>= 7; 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson count++; 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return count + 1; 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the number of bytes in the signed LEB128 encoding of the 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * given value. 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param value the value in question 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return its write size, in bytes 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static int signedLeb128Size(int value) { 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // TODO: This could be much cleverer. 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int remaining = value >> 7; 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int count = 0; 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean hasMore = true; 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int end = ((value & Integer.MIN_VALUE) == 0) ? 0 : -1; 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (hasMore) { 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson hasMore = (remaining != end) 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || ((remaining & 1) != ((value >> 6) & 1)); 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson value = remaining; 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson remaining >>= 7; 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson count++; 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return count; 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Reads an signed integer from {@code in}. 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static int readSignedLeb128(ByteInput in) { 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int result = 0; 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int cur; 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int count = 0; 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int signBits = -1; 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson do { 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson cur = in.readByte() & 0xff; 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result |= (cur & 0x7f) << (count * 7); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson signBits <<= 7; 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson count++; 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } while (((cur & 0x80) == 0x80) && count < 5); 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if ((cur & 0x80) == 0x80) { 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new DexException("invalid LEB128 sequence"); 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Sign extend if appropriate 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (((signBits >> 1) & result) != 0 ) { 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result |= signBits; 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Reads an unsigned integer from {@code in}. 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static int readUnsignedLeb128(ByteInput in) { 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int result = 0; 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int cur; 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int count = 0; 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson do { 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson cur = in.readByte() & 0xff; 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result |= (cur & 0x7f) << (count * 7); 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson count++; 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } while (((cur & 0x80) == 0x80) && count < 5); 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if ((cur & 0x80) == 0x80) { 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new DexException("invalid LEB128 sequence"); 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Writes {@code value} as an unsigned integer to {@code out}, starting at 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code offset}. Returns the number of bytes written. 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static void writeUnsignedLeb128(ByteOutput out, int value) { 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int remaining = value >>> 7; 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (remaining != 0) { 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeByte((byte) ((value & 0x7f) | 0x80)); 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson value = remaining; 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson remaining >>>= 7; 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeByte((byte) (value & 0x7f)); 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Writes {@code value} as a signed integer to {@code out}, starting at 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code offset}. Returns the number of bytes written. 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public static void writeSignedLeb128(ByteOutput out, int value) { 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int remaining = value >> 7; 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson boolean hasMore = true; 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int end = ((value & Integer.MIN_VALUE) == 0) ? 0 : -1; 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson while (hasMore) { 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson hasMore = (remaining != end) 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || ((remaining & 1) != ((value >> 6) & 1)); 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson out.writeByte((byte) ((value & 0x7f) | (hasMore ? 0x80 : 0))); 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson value = remaining; 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson remaining >>= 7; 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 163