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