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 * Returns the buffer size 152 * @return the buffer size 153 */ getSize()154 public int getSize() { 155 return ((mBufferCount - 1) * mChunkSize) + mWriteIndex; 156 } 157 158 // 159 // Reading from the read position. 160 // 161 162 /** 163 * Only valid after startEditing. 164 */ getReadPos()165 public int getReadPos() { 166 return ((mReadBufIndex) * mChunkSize) + mReadIndex; 167 } 168 169 /** 170 * Skip over _amount_ bytes. 171 */ skipRead(int amount)172 public void skipRead(int amount) { 173 if (amount < 0) { 174 throw new RuntimeException("skipRead with negative amount=" + amount); 175 } 176 if (amount == 0) { 177 return; 178 } 179 if (amount <= mChunkSize - mReadIndex) { 180 mReadIndex += amount; 181 } else { 182 amount -= mChunkSize - mReadIndex; 183 mReadIndex = amount % mChunkSize; 184 if (mReadIndex == 0) { 185 mReadIndex = mChunkSize; 186 mReadBufIndex += (amount / mChunkSize); 187 } else { 188 mReadBufIndex += 1 + (amount / mChunkSize); 189 } 190 mReadBuffer = mBuffers.get(mReadBufIndex); 191 } 192 } 193 194 /** 195 * Read one byte from the stream and advance the read pointer. 196 * 197 * @throws IndexOutOfBoundsException if the read point is past the end of 198 * the buffer or past the read limit previously set by startEditing(). 199 */ readRawByte()200 public byte readRawByte() { 201 if (mReadBufIndex > mBufferCount 202 || (mReadBufIndex == mBufferCount - 1 && mReadIndex >= mReadLimit)) { 203 throw new IndexOutOfBoundsException("Trying to read too much data" 204 + " mReadBufIndex=" + mReadBufIndex + " mBufferCount=" + mBufferCount 205 + " mReadIndex=" + mReadIndex + " mReadLimit=" + mReadLimit); 206 } 207 if (mReadIndex >= mChunkSize) { 208 mReadBufIndex++; 209 mReadBuffer = mBuffers.get(mReadBufIndex); 210 mReadIndex = 0; 211 } 212 return mReadBuffer[mReadIndex++]; 213 } 214 215 /** 216 * Read an unsigned varint. The value will be returend in a java signed long. 217 */ readRawUnsigned()218 public long readRawUnsigned() { 219 int bits = 0; 220 long result = 0; 221 while (true) { 222 final byte b = readRawByte(); 223 result |= ((long)(b & 0x7F)) << bits; 224 if ((b & 0x80) == 0) { 225 return result; 226 } 227 bits += 7; 228 if (bits > 64) { 229 throw new ProtoParseException("Varint too long -- " + getDebugString()); 230 } 231 } 232 } 233 234 /** 235 * Read 32 little endian bits from the stream. 236 */ readRawFixed32()237 public int readRawFixed32() { 238 return (readRawByte() & 0x0ff) 239 | ((readRawByte() & 0x0ff) << 8) 240 | ((readRawByte() & 0x0ff) << 16) 241 | ((readRawByte() & 0x0ff) << 24); 242 } 243 244 // 245 // Writing at a the end of the stream. 246 // 247 248 /** 249 * Advance to the next write buffer, allocating it if necessary. 250 * 251 * Must be called immediately <b>before</b> the next write, not after a write, 252 * so that a dangling empty buffer is not created. Doing so will interfere 253 * with the expectation that mWriteIndex will point past the end of the buffer 254 * until the next read happens. 255 */ nextWriteBuffer()256 private void nextWriteBuffer() { 257 mWriteBufIndex++; 258 if (mWriteBufIndex >= mBufferCount) { 259 mWriteBuffer = new byte[mChunkSize]; 260 mBuffers.add(mWriteBuffer); 261 mBufferCount++; 262 } else { 263 mWriteBuffer = mBuffers.get(mWriteBufIndex); 264 } 265 mWriteIndex = 0; 266 } 267 268 /** 269 * Write a single byte to the stream. 270 */ writeRawByte(byte val)271 public void writeRawByte(byte val) { 272 if (mWriteIndex >= mChunkSize) { 273 nextWriteBuffer(); 274 } 275 mWriteBuffer[mWriteIndex++] = val; 276 } 277 278 /** 279 * Return how many bytes a 32 bit unsigned varint will take when written to the stream. 280 */ getRawVarint32Size(int val)281 public static int getRawVarint32Size(int val) { 282 if ((val & (0xffffffff << 7)) == 0) return 1; 283 if ((val & (0xffffffff << 14)) == 0) return 2; 284 if ((val & (0xffffffff << 21)) == 0) return 3; 285 if ((val & (0xffffffff << 28)) == 0) return 4; 286 return 5; 287 } 288 289 /** 290 * Write an unsigned varint to the stream. A signed value would need to take 10 bytes. 291 * 292 * @param val treated as unsigned. 293 */ writeRawVarint32(int val)294 public void writeRawVarint32(int val) { 295 while (true) { 296 if ((val & ~0x7F) == 0) { 297 writeRawByte((byte)val); 298 return; 299 } else { 300 writeRawByte((byte)((val & 0x7F) | 0x80)); 301 val >>>= 7; 302 } 303 } 304 } 305 306 /** 307 * Return how many bytes a 32 bit signed zig zag value will take when written to the stream. 308 */ getRawZigZag32Size(int val)309 public static int getRawZigZag32Size(int val) { 310 return getRawVarint32Size(zigZag32(val)); 311 } 312 313 /** 314 * Write a zig-zag encoded value. 315 * 316 * @param val treated as signed 317 */ writeRawZigZag32(int val)318 public void writeRawZigZag32(int val) { 319 writeRawVarint32(zigZag32(val)); 320 } 321 322 /** 323 * Return how many bytes a 64 bit varint will take when written to the stream. 324 */ getRawVarint64Size(long val)325 public static int getRawVarint64Size(long val) { 326 if ((val & (0xffffffffffffffffL << 7)) == 0) return 1; 327 if ((val & (0xffffffffffffffffL << 14)) == 0) return 2; 328 if ((val & (0xffffffffffffffffL << 21)) == 0) return 3; 329 if ((val & (0xffffffffffffffffL << 28)) == 0) return 4; 330 if ((val & (0xffffffffffffffffL << 35)) == 0) return 5; 331 if ((val & (0xffffffffffffffffL << 42)) == 0) return 6; 332 if ((val & (0xffffffffffffffffL << 49)) == 0) return 7; 333 if ((val & (0xffffffffffffffffL << 56)) == 0) return 8; 334 if ((val & (0xffffffffffffffffL << 63)) == 0) return 9; 335 return 10; 336 } 337 338 /** 339 * Write a 64 bit varint to the stream. 340 */ writeRawVarint64(long val)341 public void writeRawVarint64(long val) { 342 while (true) { 343 if ((val & ~0x7FL) == 0) { 344 writeRawByte((byte)val); 345 return; 346 } else { 347 writeRawByte((byte)((val & 0x7F) | 0x80)); 348 val >>>= 7; 349 } 350 } 351 } 352 353 /** 354 * Return how many bytes a signed 64 bit zig zag value will take when written to the stream. 355 */ getRawZigZag64Size(long val)356 public static int getRawZigZag64Size(long val) { 357 return getRawVarint64Size(zigZag64(val)); 358 } 359 360 /** 361 * Write a 64 bit signed zig zag value to the stream. 362 */ writeRawZigZag64(long val)363 public void writeRawZigZag64(long val) { 364 writeRawVarint64(zigZag64(val)); 365 } 366 367 /** 368 * Write 4 little endian bytes to the stream. 369 */ writeRawFixed32(int val)370 public void writeRawFixed32(int val) { 371 writeRawByte((byte)(val)); 372 writeRawByte((byte)(val >> 8)); 373 writeRawByte((byte)(val >> 16)); 374 writeRawByte((byte)(val >> 24)); 375 } 376 377 /** 378 * Write 8 little endian bytes to the stream. 379 */ writeRawFixed64(long val)380 public void writeRawFixed64(long val) { 381 writeRawByte((byte)(val)); 382 writeRawByte((byte)(val >> 8)); 383 writeRawByte((byte)(val >> 16)); 384 writeRawByte((byte)(val >> 24)); 385 writeRawByte((byte)(val >> 32)); 386 writeRawByte((byte)(val >> 40)); 387 writeRawByte((byte)(val >> 48)); 388 writeRawByte((byte)(val >> 56)); 389 } 390 391 /** 392 * Write a buffer to the stream. Writes nothing if val is null or zero-length. 393 */ writeRawBuffer(byte[] val)394 public void writeRawBuffer(byte[] val) { 395 if (val != null && val.length > 0) { 396 writeRawBuffer(val, 0, val.length); 397 } 398 } 399 400 /** 401 * Write part of an array of bytes. 402 */ writeRawBuffer(byte[] val, int offset, int length)403 public void writeRawBuffer(byte[] val, int offset, int length) { 404 if (val == null) { 405 return; 406 } 407 // Write up to the amount left in the first chunk to write. 408 int amt = length < (mChunkSize - mWriteIndex) ? length : (mChunkSize - mWriteIndex); 409 if (amt > 0) { 410 System.arraycopy(val, offset, mWriteBuffer, mWriteIndex, amt); 411 mWriteIndex += amt; 412 length -= amt; 413 offset += amt; 414 } 415 while (length > 0) { 416 // We know we're now at the beginning of a chunk 417 nextWriteBuffer(); 418 amt = length < mChunkSize ? length : mChunkSize; 419 System.arraycopy(val, offset, mWriteBuffer, mWriteIndex, amt); 420 mWriteIndex += amt; 421 length -= amt; 422 offset += amt; 423 } 424 } 425 426 /** 427 * Copies data _size_ bytes of data within this buffer from _srcOffset_ 428 * to the current write position. Like memmov but handles the chunked buffer. 429 */ 430 public void writeFromThisBuffer(int srcOffset, int size) { 431 if (mReadLimit < 0) { 432 throw new IllegalStateException("writeFromThisBuffer before startEditing"); 433 } 434 if (srcOffset < getWritePos()) { 435 throw new IllegalArgumentException("Can only move forward in the buffer --" 436 + " srcOffset=" + srcOffset + " size=" + size + " " + getDebugString()); 437 } 438 if (srcOffset + size > mReadableSize) { 439 throw new IllegalArgumentException("Trying to move more data than there is --" 440 + " srcOffset=" + srcOffset + " size=" + size + " " + getDebugString()); 441 } 442 if (size == 0) { 443 return; 444 } 445 if (srcOffset == ((mWriteBufIndex) * mChunkSize) + mWriteIndex /* write pos */) { 446 // Writing to the same location. Just advance the write pointer. We already 447 // checked that size is in bounds, so we don't need to do any more range 448 // checking. 449 if (size <= mChunkSize - mWriteIndex) { 450 mWriteIndex += size; 451 } else { 452 size -= mChunkSize - mWriteIndex; 453 mWriteIndex = size % mChunkSize; 454 if (mWriteIndex == 0) { 455 // Roll it back so nextWriteBuffer can do its job 456 // on the next call (also makes mBuffers.get() not 457 // fail if we're at the end). 458 mWriteIndex = mChunkSize; 459 mWriteBufIndex += (size / mChunkSize); 460 } else { 461 mWriteBufIndex += 1 + (size / mChunkSize); 462 } 463 mWriteBuffer = mBuffers.get(mWriteBufIndex); 464 } 465 } else { 466 // Loop through the buffer, copying as much as we can each time. 467 // We already bounds checked so we don't need to do it again here, 468 // and nextWriteBuffer will never allocate. 469 int readBufIndex = srcOffset / mChunkSize; 470 byte[] readBuffer = mBuffers.get(readBufIndex); 471 int readIndex = srcOffset % mChunkSize; 472 while (size > 0) { 473 if (mWriteIndex >= mChunkSize) { 474 nextWriteBuffer(); 475 } 476 if (readIndex >= mChunkSize) { 477 readBufIndex++; 478 readBuffer = mBuffers.get(readBufIndex); 479 readIndex = 0; 480 } 481 final int spaceInWriteBuffer = mChunkSize - mWriteIndex; 482 final int availableInReadBuffer = mChunkSize - readIndex; 483 final int amt = Math.min(size, Math.min(spaceInWriteBuffer, availableInReadBuffer)); 484 System.arraycopy(readBuffer, readIndex, mWriteBuffer, mWriteIndex, amt); 485 mWriteIndex += amt; 486 readIndex += amt; 487 size -= amt; 488 } 489 } 490 } 491 492 // 493 // Writing at a particular location. 494 // 495 496 /** 497 * Returns the index into the virtual array of the write pointer. 498 */ 499 public int getWritePos() { 500 return ((mWriteBufIndex) * mChunkSize) + mWriteIndex; 501 } 502 503 /** 504 * Resets the write pointer to a virtual location as returned by getWritePos. 505 */ 506 public void rewindWriteTo(int writePos) { 507 if (writePos > getWritePos()) { 508 throw new RuntimeException("rewindWriteTo only can go backwards" + writePos); 509 } 510 mWriteBufIndex = writePos / mChunkSize; 511 mWriteIndex = writePos % mChunkSize; 512 if (mWriteIndex == 0 && mWriteBufIndex != 0) { 513 // Roll back so nextWriteBuffer can do its job on the next call 514 // but at the first write we're at 0. 515 mWriteIndex = mChunkSize; 516 mWriteBufIndex--; 517 } 518 mWriteBuffer = mBuffers.get(mWriteBufIndex); 519 } 520 521 /** 522 * Read a 32 bit value from the stream. 523 * 524 * Doesn't touch or affect mWritePos. 525 */ 526 public int getRawFixed32At(int pos) { 527 return (0x00ff & (int)mBuffers.get(pos / mChunkSize)[pos % mChunkSize]) 528 | ((0x0ff & (int)mBuffers.get((pos+1) / mChunkSize)[(pos+1) % mChunkSize]) << 8) 529 | ((0x0ff & (int)mBuffers.get((pos+2) / mChunkSize)[(pos+2) % mChunkSize]) << 16) 530 | ((0x0ff & (int)mBuffers.get((pos+3) / mChunkSize)[(pos+3) % mChunkSize]) << 24); 531 } 532 533 /** 534 * Overwrite a 32 bit value in the stream. 535 * 536 * Doesn't touch or affect mWritePos. 537 */ 538 public void editRawFixed32(int pos, int val) { 539 mBuffers.get(pos / mChunkSize)[pos % mChunkSize] = (byte)(val); 540 mBuffers.get((pos+1) / mChunkSize)[(pos+1) % mChunkSize] = (byte)(val >> 8); 541 mBuffers.get((pos+2) / mChunkSize)[(pos+2) % mChunkSize] = (byte)(val >> 16); 542 mBuffers.get((pos+3) / mChunkSize)[(pos+3) % mChunkSize] = (byte)(val >> 24); 543 } 544 545 // 546 // Zigging and zagging 547 // 548 549 /** 550 * Zig-zag encode a 32 bit value. 551 */ 552 private static int zigZag32(int val) { 553 return (val << 1) ^ (val >> 31); 554 } 555 556 /** 557 * Zig-zag encode a 64 bit value. 558 */ 559 private static long zigZag64(long val) { 560 return (val << 1) ^ (val >> 63); 561 } 562 563 // 564 // Debugging / testing 565 // 566 // VisibleForTesting 567 568 /** 569 * Get a copy of the first _size_ bytes of data. This is not range 570 * checked, and if the bounds are outside what has been written you will 571 * get garbage and if it is outside the buffers that have been allocated, 572 * you will get an exception. 573 */ 574 public byte[] getBytes(int size) { 575 final byte[] result = new byte[size]; 576 577 final int bufCount = size / mChunkSize; 578 int bufIndex; 579 int writeIndex = 0; 580 581 for (bufIndex=0; bufIndex<bufCount; bufIndex++) { 582 System.arraycopy(mBuffers.get(bufIndex), 0, result, writeIndex, mChunkSize); 583 writeIndex += mChunkSize; 584 } 585 586 final int lastSize = size - (bufCount * mChunkSize); 587 if (lastSize > 0) { 588 System.arraycopy(mBuffers.get(bufIndex), 0, result, writeIndex, lastSize); 589 } 590 591 return result; 592 } 593 594 /** 595 * Get the number of chunks allocated. 596 */ 597 // VisibleForTesting 598 public int getChunkCount() { 599 return mBuffers.size(); 600 } 601 602 /** 603 * Get the write position inside the current write chunk. 604 */ 605 // VisibleForTesting 606 public int getWriteIndex() { 607 return mWriteIndex; 608 } 609 610 /** 611 * Get the index of the current write chunk in the list of chunks. 612 */ 613 // VisibleForTesting 614 public int getWriteBufIndex() { 615 return mWriteBufIndex; 616 } 617 618 /** 619 * Return debugging information about this EncodedBuffer object. 620 */ 621 public String getDebugString() { 622 return "EncodedBuffer( mChunkSize=" + mChunkSize + " mBuffers.size=" + mBuffers.size() 623 + " mBufferCount=" + mBufferCount + " mWriteIndex=" + mWriteIndex 624 + " mWriteBufIndex=" + mWriteBufIndex + " mReadBufIndex=" + mReadBufIndex 625 + " mReadIndex=" + mReadIndex + " mReadableSize=" + mReadableSize 626 + " mReadLimit=" + mReadLimit + " )"; 627 } 628 629 /** 630 * Print the internal buffer chunks. 631 */ 632 public void dumpBuffers(String tag) { 633 final int N = mBuffers.size(); 634 int start = 0; 635 for (int i=0; i<N; i++) { 636 start += dumpByteString(tag, "{" + i + "} ", start, mBuffers.get(i)); 637 } 638 } 639 640 /** 641 * Print the internal buffer chunks. 642 */ 643 public static void dumpByteString(String tag, String prefix, byte[] buf) { 644 dumpByteString(tag, prefix, 0, buf); 645 } 646 647 /** 648 * Print the internal buffer chunks. 649 */ 650 private static int dumpByteString(String tag, String prefix, int start, byte[] buf) { 651 StringBuffer sb = new StringBuffer(); 652 final int length = buf.length; 653 final int lineLen = 16; 654 int i; 655 for (i=0; i<length; i++) { 656 if (i % lineLen == 0) { 657 if (i != 0) { 658 Log.d(tag, sb.toString()); 659 sb = new StringBuffer(); 660 } 661 sb.append(prefix); 662 sb.append('['); 663 sb.append(start + i); 664 sb.append(']'); 665 sb.append(' '); 666 } else { 667 sb.append(' '); 668 } 669 byte b = buf[i]; 670 byte c = (byte)((b >> 4) & 0x0f); 671 if (c < 10) { 672 sb.append((char)('0' + c)); 673 } else { 674 sb.append((char)('a' - 10 + c)); 675 } 676 byte d = (byte)(b & 0x0f); 677 if (d < 10) { 678 sb.append((char)('0' + d)); 679 } else { 680 sb.append((char)('a' - 10 + d)); 681 } 682 } 683 Log.d(tag, sb.toString()); 684 return length; 685 } 686 } 687