1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.util.proto; 18 19 import android.annotation.TestApi; 20 import android.util.Log; 21 22 import java.util.ArrayList; 23 24 /** 25 * A stream of bytes containing a read pointer and a write pointer, 26 * backed by a set of fixed-size buffers. There are write functions for the 27 * primitive types stored by protocol buffers, but none of the logic 28 * for tags, inner objects, or any of that. 29 * 30 * Terminology: 31 * *Pos: Position in the whole data set (as if it were a single buffer). 32 * *Index: Position within a buffer. 33 * *BufIndex: Index of a buffer within the mBuffers list 34 * @hide 35 */ 36 @TestApi 37 public final class EncodedBuffer { 38 private static final String TAG = "EncodedBuffer"; 39 40 private final ArrayList<byte[]> mBuffers = new ArrayList<byte[]>(); 41 42 private final int mChunkSize; 43 44 /** 45 * The number of buffers in mBuffers. Stored separately to avoid the extra 46 * function call to size() everywhere for bounds checking. 47 */ 48 private int mBufferCount; 49 50 /** 51 * The buffer we are currently writing to. 52 */ 53 private byte[] mWriteBuffer; 54 55 /** 56 * The index into mWriteBuffer that we will write to next. 57 * It may point to the end of the buffer, in which case, 58 * the NEXT write will allocate a new buffer. 59 */ 60 private int mWriteIndex; 61 62 /** 63 * The index of mWriteBuffer in mBuffers. 64 */ 65 private int mWriteBufIndex; 66 67 /** 68 * The buffer we are currently reading from. 69 */ 70 private byte[] mReadBuffer; 71 72 /** 73 * The index of mReadBuffer in mBuffers. 74 */ 75 private int mReadBufIndex; 76 77 /** 78 * The index into mReadBuffer that we will read from next. 79 * It may point to the end of the buffer, in which case, 80 * the NEXT read will advance to the next buffer. 81 */ 82 private int mReadIndex; 83 84 /** 85 * The amount of data in the last buffer. 86 */ 87 private int mReadLimit = -1; 88 89 /** 90 * How much data there is total. 91 */ 92 private int mReadableSize = -1; 93 EncodedBuffer()94 public EncodedBuffer() { 95 this(0); 96 } 97 98 /** 99 * Construct an EncodedBuffer object. 100 * 101 * @param chunkSize The size of the buffers to use. If chunkSize <= 0, a default 102 * size will be used instead. 103 */ EncodedBuffer(int chunkSize)104 public EncodedBuffer(int chunkSize) { 105 if (chunkSize <= 0) { 106 chunkSize = 8 * 1024; 107 } 108 mChunkSize = chunkSize; 109 mWriteBuffer = new byte[mChunkSize]; 110 mBuffers.add(mWriteBuffer); 111 mBufferCount = 1; 112 } 113 114 // 115 // Buffer management. 116 // 117 118 /** 119 * Rewind the read and write pointers, and record how much data was last written. 120 */ startEditing()121 public void startEditing() { 122 mReadableSize = ((mWriteBufIndex) * mChunkSize) + mWriteIndex; 123 mReadLimit = mWriteIndex; 124 125 mWriteBuffer = mBuffers.get(0); 126 mWriteIndex = 0; 127 mWriteBufIndex = 0; 128 129 mReadBuffer = mWriteBuffer; 130 mReadBufIndex = 0; 131 mReadIndex = 0; 132 } 133 134 /** 135 * Rewind the read pointer. Don't touch the write pointer. 136 */ rewindRead()137 public void rewindRead() { 138 mReadBuffer = mBuffers.get(0); 139 mReadBufIndex = 0; 140 mReadIndex = 0; 141 } 142 143 /** 144 * Only valid after startEditing. Returns -1 before that. 145 */ getReadableSize()146 public int getReadableSize() { 147 return mReadableSize; 148 } 149 150 // 151 // Reading from the read position. 152 // 153 154 /** 155 * Only valid after startEditing. 156 */ getReadPos()157 public int getReadPos() { 158 return ((mReadBufIndex) * mChunkSize) + mReadIndex; 159 } 160 161 /** 162 * Skip over _amount_ bytes. 163 */ skipRead(int amount)164 public void skipRead(int amount) { 165 if (amount < 0) { 166 throw new RuntimeException("skipRead with negative amount=" + amount); 167 } 168 if (amount == 0) { 169 return; 170 } 171 if (amount <= mChunkSize - mReadIndex) { 172 mReadIndex += amount; 173 } else { 174 amount -= mChunkSize - mReadIndex; 175 mReadIndex = amount % mChunkSize; 176 if (mReadIndex == 0) { 177 mReadIndex = mChunkSize; 178 mReadBufIndex += (amount / mChunkSize); 179 } else { 180 mReadBufIndex += 1 + (amount / mChunkSize); 181 } 182 mReadBuffer = mBuffers.get(mReadBufIndex); 183 } 184 } 185 186 /** 187 * Read one byte from the stream and advance the read pointer. 188 * 189 * @throws IndexOutOfBoundsException if the read point is past the end of 190 * the buffer or past the read limit previously set by startEditing(). 191 */ readRawByte()192 public byte readRawByte() { 193 if (mReadBufIndex > mBufferCount 194 || (mReadBufIndex == mBufferCount - 1 && mReadIndex >= mReadLimit)) { 195 throw new IndexOutOfBoundsException("Trying to read too much data" 196 + " mReadBufIndex=" + mReadBufIndex + " mBufferCount=" + mBufferCount 197 + " mReadIndex=" + mReadIndex + " mReadLimit=" + mReadLimit); 198 } 199 if (mReadIndex >= mChunkSize) { 200 mReadBufIndex++; 201 mReadBuffer = mBuffers.get(mReadBufIndex); 202 mReadIndex = 0; 203 } 204 return mReadBuffer[mReadIndex++]; 205 } 206 207 /** 208 * Read an unsigned varint. The value will be returend in a java signed long. 209 */ readRawUnsigned()210 public long readRawUnsigned() { 211 int bits = 0; 212 long result = 0; 213 while (true) { 214 final byte b = readRawByte(); 215 result |= ((long)(b & 0x7F)) << bits; 216 if ((b & 0x80) == 0) { 217 return result; 218 } 219 bits += 7; 220 if (bits > 64) { 221 throw new ProtoParseException("Varint too long -- " + getDebugString()); 222 } 223 } 224 } 225 226 /** 227 * Read 32 little endian bits from the stream. 228 */ readRawFixed32()229 public int readRawFixed32() { 230 return (readRawByte() & 0x0ff) 231 | ((readRawByte() & 0x0ff) << 8) 232 | ((readRawByte() & 0x0ff) << 16) 233 | ((readRawByte() & 0x0ff) << 24); 234 } 235 236 // 237 // Writing at a the end of the stream. 238 // 239 240 /** 241 * Advance to the next write buffer, allocating it if necessary. 242 * 243 * Must be called immediately <b>before</b> the next write, not after a write, 244 * so that a dangling empty buffer is not created. Doing so will interfere 245 * with the expectation that mWriteIndex will point past the end of the buffer 246 * until the next read happens. 247 */ nextWriteBuffer()248 private void nextWriteBuffer() { 249 mWriteBufIndex++; 250 if (mWriteBufIndex >= mBufferCount) { 251 mWriteBuffer = new byte[mChunkSize]; 252 mBuffers.add(mWriteBuffer); 253 mBufferCount++; 254 } else { 255 mWriteBuffer = mBuffers.get(mWriteBufIndex); 256 } 257 mWriteIndex = 0; 258 } 259 260 /** 261 * Write a single byte to the stream. 262 */ writeRawByte(byte val)263 public void writeRawByte(byte val) { 264 if (mWriteIndex >= mChunkSize) { 265 nextWriteBuffer(); 266 } 267 mWriteBuffer[mWriteIndex++] = val; 268 } 269 270 /** 271 * Return how many bytes a 32 bit unsigned varint will take when written to the stream. 272 */ getRawVarint32Size(int val)273 public static int getRawVarint32Size(int val) { 274 if ((val & (0xffffffff << 7)) == 0) return 1; 275 if ((val & (0xffffffff << 14)) == 0) return 2; 276 if ((val & (0xffffffff << 21)) == 0) return 3; 277 if ((val & (0xffffffff << 28)) == 0) return 4; 278 return 5; 279 } 280 281 /** 282 * Write an unsigned varint to the stream. A signed value would need to take 10 bytes. 283 * 284 * @param val treated as unsigned. 285 */ writeRawVarint32(int val)286 public void writeRawVarint32(int val) { 287 while (true) { 288 if ((val & ~0x7F) == 0) { 289 writeRawByte((byte)val); 290 return; 291 } else { 292 writeRawByte((byte)((val & 0x7F) | 0x80)); 293 val >>>= 7; 294 } 295 } 296 } 297 298 /** 299 * Return how many bytes a 32 bit signed zig zag value will take when written to the stream. 300 */ getRawZigZag32Size(int val)301 public static int getRawZigZag32Size(int val) { 302 return getRawVarint32Size(zigZag32(val)); 303 } 304 305 /** 306 * Write a zig-zag encoded value. 307 * 308 * @param val treated as signed 309 */ writeRawZigZag32(int val)310 public void writeRawZigZag32(int val) { 311 writeRawVarint32(zigZag32(val)); 312 } 313 314 /** 315 * Return how many bytes a 64 bit varint will take when written to the stream. 316 */ getRawVarint64Size(long val)317 public static int getRawVarint64Size(long val) { 318 if ((val & (0xffffffffffffffffL << 7)) == 0) return 1; 319 if ((val & (0xffffffffffffffffL << 14)) == 0) return 2; 320 if ((val & (0xffffffffffffffffL << 21)) == 0) return 3; 321 if ((val & (0xffffffffffffffffL << 28)) == 0) return 4; 322 if ((val & (0xffffffffffffffffL << 35)) == 0) return 5; 323 if ((val & (0xffffffffffffffffL << 42)) == 0) return 6; 324 if ((val & (0xffffffffffffffffL << 49)) == 0) return 7; 325 if ((val & (0xffffffffffffffffL << 56)) == 0) return 8; 326 if ((val & (0xffffffffffffffffL << 63)) == 0) return 9; 327 return 10; 328 } 329 330 /** 331 * Write a 64 bit varint to the stream. 332 */ writeRawVarint64(long val)333 public void writeRawVarint64(long val) { 334 while (true) { 335 if ((val & ~0x7FL) == 0) { 336 writeRawByte((byte)val); 337 return; 338 } else { 339 writeRawByte((byte)((val & 0x7F) | 0x80)); 340 val >>>= 7; 341 } 342 } 343 } 344 345 /** 346 * Return how many bytes a signed 64 bit zig zag value will take when written to the stream. 347 */ getRawZigZag64Size(long val)348 public static int getRawZigZag64Size(long val) { 349 return getRawVarint64Size(zigZag64(val)); 350 } 351 352 /** 353 * Write a 64 bit signed zig zag value to the stream. 354 */ writeRawZigZag64(long val)355 public void writeRawZigZag64(long val) { 356 writeRawVarint64(zigZag64(val)); 357 } 358 359 /** 360 * Write 4 little endian bytes to the stream. 361 */ writeRawFixed32(int val)362 public void writeRawFixed32(int val) { 363 writeRawByte((byte)(val)); 364 writeRawByte((byte)(val >> 8)); 365 writeRawByte((byte)(val >> 16)); 366 writeRawByte((byte)(val >> 24)); 367 } 368 369 /** 370 * Write 8 little endian bytes to the stream. 371 */ writeRawFixed64(long val)372 public void writeRawFixed64(long val) { 373 writeRawByte((byte)(val)); 374 writeRawByte((byte)(val >> 8)); 375 writeRawByte((byte)(val >> 16)); 376 writeRawByte((byte)(val >> 24)); 377 writeRawByte((byte)(val >> 32)); 378 writeRawByte((byte)(val >> 40)); 379 writeRawByte((byte)(val >> 48)); 380 writeRawByte((byte)(val >> 56)); 381 } 382 383 /** 384 * Write a buffer to the stream. Writes nothing if val is null or zero-length. 385 */ writeRawBuffer(byte[] val)386 public void writeRawBuffer(byte[] val) { 387 if (val != null && val.length > 0) { 388 writeRawBuffer(val, 0, val.length); 389 } 390 } 391 392 /** 393 * Write part of an array of bytes. 394 */ writeRawBuffer(byte[] val, int offset, int length)395 public void writeRawBuffer(byte[] val, int offset, int length) { 396 if (val == null) { 397 return; 398 } 399 // Write up to the amount left in the first chunk to write. 400 int amt = length < (mChunkSize - mWriteIndex) ? length : (mChunkSize - mWriteIndex); 401 if (amt > 0) { 402 System.arraycopy(val, offset, mWriteBuffer, mWriteIndex, amt); 403 mWriteIndex += amt; 404 length -= amt; 405 offset += amt; 406 } 407 while (length > 0) { 408 // We know we're now at the beginning of a chunk 409 nextWriteBuffer(); 410 amt = length < mChunkSize ? length : mChunkSize; 411 System.arraycopy(val, offset, mWriteBuffer, mWriteIndex, amt); 412 mWriteIndex += amt; 413 length -= amt; 414 offset += amt; 415 } 416 } 417 418 /** 419 * Copies data _size_ bytes of data within this buffer from _srcOffset_ 420 * to the current write position. Like memmov but handles the chunked buffer. 421 */ 422 public void writeFromThisBuffer(int srcOffset, int size) { 423 if (mReadLimit < 0) { 424 throw new IllegalStateException("writeFromThisBuffer before startEditing"); 425 } 426 if (srcOffset < getWritePos()) { 427 throw new IllegalArgumentException("Can only move forward in the buffer --" 428 + " srcOffset=" + srcOffset + " size=" + size + " " + getDebugString()); 429 } 430 if (srcOffset + size > mReadableSize) { 431 throw new IllegalArgumentException("Trying to move more data than there is --" 432 + " srcOffset=" + srcOffset + " size=" + size + " " + getDebugString()); 433 } 434 if (size == 0) { 435 return; 436 } 437 if (srcOffset == ((mWriteBufIndex) * mChunkSize) + mWriteIndex /* write pos */) { 438 // Writing to the same location. Just advance the write pointer. We already 439 // checked that size is in bounds, so we don't need to do any more range 440 // checking. 441 if (size <= mChunkSize - mWriteIndex) { 442 mWriteIndex += size; 443 } else { 444 size -= mChunkSize - mWriteIndex; 445 mWriteIndex = size % mChunkSize; 446 if (mWriteIndex == 0) { 447 // Roll it back so nextWriteBuffer can do its job 448 // on the next call (also makes mBuffers.get() not 449 // fail if we're at the end). 450 mWriteIndex = mChunkSize; 451 mWriteBufIndex += (size / mChunkSize); 452 } else { 453 mWriteBufIndex += 1 + (size / mChunkSize); 454 } 455 mWriteBuffer = mBuffers.get(mWriteBufIndex); 456 } 457 } else { 458 // Loop through the buffer, copying as much as we can each time. 459 // We already bounds checked so we don't need to do it again here, 460 // and nextWriteBuffer will never allocate. 461 int readBufIndex = srcOffset / mChunkSize; 462 byte[] readBuffer = mBuffers.get(readBufIndex); 463 int readIndex = srcOffset % mChunkSize; 464 while (size > 0) { 465 if (mWriteIndex >= mChunkSize) { 466 nextWriteBuffer(); 467 } 468 if (readIndex >= mChunkSize) { 469 readBufIndex++; 470 readBuffer = mBuffers.get(readBufIndex); 471 readIndex = 0; 472 } 473 final int spaceInWriteBuffer = mChunkSize - mWriteIndex; 474 final int availableInReadBuffer = mChunkSize - readIndex; 475 final int amt = Math.min(size, Math.min(spaceInWriteBuffer, availableInReadBuffer)); 476 System.arraycopy(readBuffer, readIndex, mWriteBuffer, mWriteIndex, amt); 477 mWriteIndex += amt; 478 readIndex += amt; 479 size -= amt; 480 } 481 } 482 } 483 484 // 485 // Writing at a particular location. 486 // 487 488 /** 489 * Returns the index into the virtual array of the write pointer. 490 */ 491 public int getWritePos() { 492 return ((mWriteBufIndex) * mChunkSize) + mWriteIndex; 493 } 494 495 /** 496 * Resets the write pointer to a virtual location as returned by getWritePos. 497 */ 498 public void rewindWriteTo(int writePos) { 499 if (writePos > getWritePos()) { 500 throw new RuntimeException("rewindWriteTo only can go backwards" + writePos); 501 } 502 mWriteBufIndex = writePos / mChunkSize; 503 mWriteIndex = writePos % mChunkSize; 504 if (mWriteIndex == 0 && mWriteBufIndex != 0) { 505 // Roll back so nextWriteBuffer can do its job on the next call 506 // but at the first write we're at 0. 507 mWriteIndex = mChunkSize; 508 mWriteBufIndex--; 509 } 510 mWriteBuffer = mBuffers.get(mWriteBufIndex); 511 } 512 513 /** 514 * Read a 32 bit value from the stream. 515 * 516 * Doesn't touch or affect mWritePos. 517 */ 518 public int getRawFixed32At(int pos) { 519 return (0x00ff & (int)mBuffers.get(pos / mChunkSize)[pos % mChunkSize]) 520 | ((0x0ff & (int)mBuffers.get((pos+1) / mChunkSize)[(pos+1) % mChunkSize]) << 8) 521 | ((0x0ff & (int)mBuffers.get((pos+2) / mChunkSize)[(pos+2) % mChunkSize]) << 16) 522 | ((0x0ff & (int)mBuffers.get((pos+3) / mChunkSize)[(pos+3) % mChunkSize]) << 24); 523 } 524 525 /** 526 * Overwrite a 32 bit value in the stream. 527 * 528 * Doesn't touch or affect mWritePos. 529 */ 530 public void editRawFixed32(int pos, int val) { 531 mBuffers.get(pos / mChunkSize)[pos % mChunkSize] = (byte)(val); 532 mBuffers.get((pos+1) / mChunkSize)[(pos+1) % mChunkSize] = (byte)(val >> 8); 533 mBuffers.get((pos+2) / mChunkSize)[(pos+2) % mChunkSize] = (byte)(val >> 16); 534 mBuffers.get((pos+3) / mChunkSize)[(pos+3) % mChunkSize] = (byte)(val >> 24); 535 } 536 537 // 538 // Zigging and zagging 539 // 540 541 /** 542 * Zig-zag encode a 32 bit value. 543 */ 544 private static int zigZag32(int val) { 545 return (val << 1) ^ (val >> 31); 546 } 547 548 /** 549 * Zig-zag encode a 64 bit value. 550 */ 551 private static long zigZag64(long val) { 552 return (val << 1) ^ (val >> 63); 553 } 554 555 // 556 // Debugging / testing 557 // 558 // VisibleForTesting 559 560 /** 561 * Get a copy of the first _size_ bytes of data. This is not range 562 * checked, and if the bounds are outside what has been written you will 563 * get garbage and if it is outside the buffers that have been allocated, 564 * you will get an exception. 565 */ 566 public byte[] getBytes(int size) { 567 final byte[] result = new byte[size]; 568 569 final int bufCount = size / mChunkSize; 570 int bufIndex; 571 int writeIndex = 0; 572 573 for (bufIndex=0; bufIndex<bufCount; bufIndex++) { 574 System.arraycopy(mBuffers.get(bufIndex), 0, result, writeIndex, mChunkSize); 575 writeIndex += mChunkSize; 576 } 577 578 final int lastSize = size - (bufCount * mChunkSize); 579 if (lastSize > 0) { 580 System.arraycopy(mBuffers.get(bufIndex), 0, result, writeIndex, lastSize); 581 } 582 583 return result; 584 } 585 586 /** 587 * Get the number of chunks allocated. 588 */ 589 // VisibleForTesting 590 public int getChunkCount() { 591 return mBuffers.size(); 592 } 593 594 /** 595 * Get the write position inside the current write chunk. 596 */ 597 // VisibleForTesting 598 public int getWriteIndex() { 599 return mWriteIndex; 600 } 601 602 /** 603 * Get the index of the current write chunk in the list of chunks. 604 */ 605 // VisibleForTesting 606 public int getWriteBufIndex() { 607 return mWriteBufIndex; 608 } 609 610 /** 611 * Return debugging information about this EncodedBuffer object. 612 */ 613 public String getDebugString() { 614 return "EncodedBuffer( mChunkSize=" + mChunkSize + " mBuffers.size=" + mBuffers.size() 615 + " mBufferCount=" + mBufferCount + " mWriteIndex=" + mWriteIndex 616 + " mWriteBufIndex=" + mWriteBufIndex + " mReadBufIndex=" + mReadBufIndex 617 + " mReadIndex=" + mReadIndex + " mReadableSize=" + mReadableSize 618 + " mReadLimit=" + mReadLimit + " )"; 619 } 620 621 /** 622 * Print the internal buffer chunks. 623 */ 624 public void dumpBuffers(String tag) { 625 final int N = mBuffers.size(); 626 int start = 0; 627 for (int i=0; i<N; i++) { 628 start += dumpByteString(tag, "{" + i + "} ", start, mBuffers.get(i)); 629 } 630 } 631 632 /** 633 * Print the internal buffer chunks. 634 */ 635 public static void dumpByteString(String tag, String prefix, byte[] buf) { 636 dumpByteString(tag, prefix, 0, buf); 637 } 638 639 /** 640 * Print the internal buffer chunks. 641 */ 642 private static int dumpByteString(String tag, String prefix, int start, byte[] buf) { 643 StringBuffer sb = new StringBuffer(); 644 final int length = buf.length; 645 final int lineLen = 16; 646 int i; 647 for (i=0; i<length; i++) { 648 if (i % lineLen == 0) { 649 if (i != 0) { 650 Log.d(tag, sb.toString()); 651 sb = new StringBuffer(); 652 } 653 sb.append(prefix); 654 sb.append('['); 655 sb.append(start + i); 656 sb.append(']'); 657 sb.append(' '); 658 } else { 659 sb.append(' '); 660 } 661 byte b = buf[i]; 662 byte c = (byte)((b >> 4) & 0x0f); 663 if (c < 10) { 664 sb.append((char)('0' + c)); 665 } else { 666 sb.append((char)('a' - 10 + c)); 667 } 668 byte d = (byte)(b & 0x0f); 669 if (d < 10) { 670 sb.append((char)('0' + d)); 671 } else { 672 sb.append((char)('a' - 10 + d)); 673 } 674 } 675 Log.d(tag, sb.toString()); 676 return length; 677 } 678 } 679