org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/event/io/BitBuffer.java

   1 /*******************************************************************************.
   2  * Copyright (c) 2011, 2014 Ericsson, Ecole Polytechnique de Montreal and others
   3  *
   4  * All rights reserved. This program and the accompanying materials are made
   5  * available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *  Matthew Khouzam - Initial Design and implementation + overhaul
  11  *  Francis Giraldeau - Initial API and implementation
  12  *  Philippe Proulx - Some refinement and optimization
  13  *  Etienne Bergeron <Etienne.Bergeron@gmail.com> - fix zero size read + cleanup
  14  *******************************************************************************/
  15
  16 package org.eclipse.tracecompass.ctf.core.event.io;
  17
  18 import java.nio.BufferUnderflowException;
  19 import java.nio.ByteBuffer;
  20 import java.nio.ByteOrder;
  21
  22 import org.eclipse.jdt.annotation.NonNull;
  23 import org.eclipse.tracecompass.ctf.core.trace.CTFReaderException;
  24
  25 /**
  26  * <b><u>BitBuffer</u></b>
  27  * <p>
  28  * A bitwise buffer capable of accessing fields with bit offsets.
  29  *
  30  * @since 2.0
  31  */
  32 public final class BitBuffer {
  33
  34     // ------------------------------------------------------------------------
  35     // Constants
  36     // ------------------------------------------------------------------------
  37
  38     /* default bit width */
  39     private static final int BIT_CHAR = Byte.SIZE; // yum
  40     private static final int BYTE_MASK = (1 << BIT_CHAR) - 1;
  41     private static final int BIT_SHORT = Short.SIZE;
  42     private static final int SHORT_MASK = (1 << BIT_SHORT) - 1;
  43     private static final int BIT_INT = Integer.SIZE;
  44     private static final long INT_MASK = (1L << BIT_INT) - 1;
  45     private static final int BIT_LONG = Long.SIZE;
  46
  47     // ------------------------------------------------------------------------
  48     // Attributes
  49     // ------------------------------------------------------------------------
  50
  51     private final @NonNull ByteBuffer fBuffer;
  52     private final long fBitCapacity;
  53
  54     /**
  55      * Bit-buffer's position, maximum value = Integer.MAX_VALUE * 8
  56      */
  57     private long fPosition;
  58     private ByteOrder fByteOrder;
  59
  60     // ------------------------------------------------------------------------
  61     // Constructors
  62     // ------------------------------------------------------------------------
  63     /**
  64      * Default constructor, makes a big-endian buffer
  65      */
  66     @SuppressWarnings("null")
  67     public BitBuffer() {
  68         this(ByteBuffer.allocateDirect(0), ByteOrder.BIG_ENDIAN);
  69     }
  70
  71     /**
  72      * Constructor, makes a big-endian buffer
  73      *
  74      * @param buf
  75      *            the bytebuffer to read
  76      */
  77     public BitBuffer(@NonNull ByteBuffer buf) {
  78         this(buf, ByteOrder.BIG_ENDIAN);
  79     }
  80
  81     /**
  82      * Constructor that is fully parameterizable
  83      *
  84      * @param buf
  85      *            the buffer to read
  86      * @param order
  87      *            the byte order (big-endian, little-endian, network?)
  88      */
  89     public BitBuffer(@NonNull ByteBuffer buf, ByteOrder order) {
  90         fBuffer = buf;
  91         setByteOrder(order);
  92         resetPosition();
  93         fBitCapacity = (long) fBuffer.capacity() * BIT_CHAR;
  94     }
  95
  96     private void resetPosition() {
  97         fPosition = 0;
  98     }
  99
 100     // ------------------------------------------------------------------------
 101     // 'Get' operations on buffer
 102     // ------------------------------------------------------------------------
 103
 104     /**
 105      * Relative <i>get</i> method for reading 32-bit integer.
 106      *
 107      * Reads next four bytes from the current bit position according to current
 108      * byte order.
 109      *
 110      * @return The int value (signed) read from the buffer
 111      * @throws CTFReaderException
 112      *             An error occurred reading the long. This exception can be
 113      *             raised if the buffer tries to read out of bounds
 114      */
 115     public int getInt() throws CTFReaderException {
 116         return getInt(BIT_INT, true);
 117     }
 118
 119     /**
 120      * Relative <i>get</i> method for reading 64-bit integer.
 121      *
 122      * Reads next eight bytes from the current bit position according to current
 123      * byte order.
 124      *
 125      * @return The long value (signed) read from the buffer
 126      * @throws CTFReaderException
 127      *             An error occurred reading the long. This exception can be
 128      *             raised if the buffer tries to read out of bounds
 129      * @since 3.0
 130      */
 131     public long getLong() throws CTFReaderException {
 132         return get(BIT_LONG, true);
 133     }
 134
 135     /**
 136      * Relative <i>get</i> method for reading long of <i>length</i> bits.
 137      *
 138      * Reads <i>length</i> bits starting at the current position. The result is
 139      * signed extended if <i>signed</i> is true. The current position is
 140      * increased of <i>length</i> bits.
 141      *
 142      * @param length
 143      *            The length in bits of this integer
 144      * @param signed
 145      *            The sign extended flag
 146      * @return The long value read from the buffer
 147      * @throws CTFReaderException
 148      *             An error occurred reading the data. If more than 64 bits at a
 149      *             time are read, or the buffer is read beyond its end, this
 150      *             exception will be raised.
 151      * @since 3.0
 152      */
 153     public long get(int length, boolean signed) throws CTFReaderException {
 154         if (length > BIT_LONG) {
 155             throw new CTFReaderException("Cannot read a long longer than 64 bits. Rquested: " + length); //$NON-NLS-1$
 156         }
 157         if (length > BIT_INT) {
 158             final int highShift = length - BIT_INT;
 159             long a = getInt();
 160             long b = getInt(highShift, false);
 161             long retVal;
 162             /* Cast the signed-extended int into a unsigned int. */
 163             a &= INT_MASK;
 164             b &= (1L << highShift) - 1L;
 165
 166             retVal = (fByteOrder == ByteOrder.BIG_ENDIAN) ? ((a << highShift) | b) : ((b << BIT_INT) | a);
 167             /* sign extend */
 168             if (signed) {
 169                 int signExtendBits = BIT_LONG - length;
 170                 retVal = (retVal << signExtendBits) >> signExtendBits;
 171             }
 172             return retVal;
 173         }
 174         long retVal = getInt(length, signed);
 175         return (signed ? retVal : (retVal & INT_MASK));
 176     }
 177
 178     /**
 179      * Relative bulk <i>get</i> method.
 180      *
 181      * <p>
 182      * This method transfers <strong>bytes</strong> from this buffer into the
 183      * given destination array. This method currently only supports reads
 184      * aligned to 8 bytes. It is up to the developer to shift the bits in
 185      * post-processing to do unaligned reads.
 186      *
 187      * @param dst
 188      *            the bytes to write to
 189      * @throws BufferUnderflowException
 190      *             - If there are fewer than length bytes remaining in this
 191      *             buffer
 192      * @since 3.1
 193      */
 194     public void get(@NonNull byte[] dst) {
 195         fBuffer.position((int) (fPosition / BIT_CHAR));
 196         fBuffer.get(dst);
 197         fPosition += dst.length * BIT_CHAR;
 198     }
 199
 200     /**
 201      * Relative <i>get</i> method for reading integer of <i>length</i> bits.
 202      *
 203      * Reads <i>length</i> bits starting at the current position. The result is
 204      * signed extended if <i>signed</i> is true. The current position is
 205      * increased of <i>length</i> bits.
 206      *
 207      * @param length
 208      *            The length in bits of this integer
 209      * @param signed
 210      *            The sign extended flag
 211      * @return The int value read from the buffer
 212      * @throws CTFReaderException
 213      *             An error occurred reading the data. When the buffer is read
 214      *             beyond its end, this exception will be raised.
 215      */
 216     private int getInt(int length, boolean signed) throws CTFReaderException {
 217
 218         /* Nothing to read. */
 219         if (length == 0) {
 220             return 0;
 221         }
 222
 223         /* Validate that the buffer has enough bits. */
 224         if (!canRead(length)) {
 225             throw new CTFReaderException("Cannot read the integer, " + //$NON-NLS-1$
 226                     "the buffer does not have enough remaining space. " + //$NON-NLS-1$
 227                     "Requested:" + length); //$NON-NLS-1$
 228         }
 229
 230         /* Get the value from the byte buffer. */
 231         int val = 0;
 232         boolean gotIt = false;
 233
 234         /*
 235          * Try a fast read when the position is byte-aligned by using
 236          * java.nio.ByteBuffer's native methods
 237          */
 238         /*
 239          * A faster alignment detection as the compiler cannot guaranty that pos
 240          * is always positive.
 241          */
 242         if ((fPosition & (BitBuffer.BIT_CHAR - 1)) == 0) {
 243             switch (length) {
 244             case BitBuffer.BIT_CHAR:
 245                 // Byte
 246                 val = fBuffer.get((int) (fPosition / BIT_CHAR));
 247                 if (!signed) {
 248                     val = val & BYTE_MASK;
 249                 }
 250                 gotIt = true;
 251                 break;
 252
 253             case BitBuffer.BIT_SHORT:
 254                 // Word
 255                 val = fBuffer.getShort((int) (fPosition / BIT_CHAR));
 256                 if (!signed) {
 257                     val = val & SHORT_MASK;
 258                 }
 259                 gotIt = true;
 260                 break;
 261
 262             case BitBuffer.BIT_INT:
 263                 // Double word
 264                 val = fBuffer.getInt((int) (fPosition / BIT_CHAR));
 265                 gotIt = true;
 266                 break;
 267
 268             default:
 269                 break;
 270             }
 271         }
 272
 273         /* When not byte-aligned, fall-back to a general decoder. */
 274         if (!gotIt) {
 275             // Nothing read yet: use longer methods
 276             if (fByteOrder == ByteOrder.LITTLE_ENDIAN) {
 277                 val = getIntLE(fPosition, length, signed);
 278             } else {
 279                 val = getIntBE(fPosition, length, signed);
 280             }
 281         }
 282         fPosition += length;
 283
 284         return val;
 285     }
 286
 287     private int getIntBE(long index, int length, boolean signed) {
 288         if ((length <= 0) || (length > BIT_INT)) {
 289             throw new IllegalArgumentException("Length must be between 1-32 bits"); //$NON-NLS-1$
 290         }
 291         long end = index + length;
 292         int startByte = (int) (index / BIT_CHAR);
 293         int endByte = (int) ((end + (BIT_CHAR - 1)) / BIT_CHAR);
 294         int currByte, lshift, cshift, mask, cmask, cache;
 295         int value = 0;
 296
 297         currByte = startByte;
 298         cache = fBuffer.get(currByte) & BYTE_MASK;
 299         boolean isNeg = (cache & (1 << (BIT_CHAR - (index % BIT_CHAR) - 1))) != 0;
 300         if (signed && isNeg) {
 301             value = ~0;
 302         }
 303         if (startByte == (endByte - 1)) {
 304             cmask = cache >>> ((BIT_CHAR - (end % BIT_CHAR)) % BIT_CHAR);
 305             if (((length) % BIT_CHAR) > 0) {
 306                 mask = ~((~0) << length);
 307                 cmask &= mask;
 308             }
 309             value <<= length;
 310             value |= cmask;
 311             return value;
 312         }
 313         cshift = (int) (index % BIT_CHAR);
 314         if (cshift > 0) {
 315             mask = ~((~0) << (BIT_CHAR - cshift));
 316             cmask = cache & mask;
 317             lshift = BIT_CHAR - cshift;
 318             value <<= lshift;
 319             value |= cmask;
 320             currByte++;
 321         }
 322         for (; currByte < (endByte - 1); currByte++) {
 323             value <<= BIT_CHAR;
 324             value |= fBuffer.get(currByte) & BYTE_MASK;
 325         }
 326         lshift = (int) (end % BIT_CHAR);
 327         if (lshift > 0) {
 328             mask = ~((~0) << lshift);
 329             cmask = fBuffer.get(currByte) & BYTE_MASK;
 330             cmask >>>= BIT_CHAR - lshift;
 331             cmask &= mask;
 332             value <<= lshift;
 333             value |= cmask;
 334         } else {
 335             value <<= BIT_CHAR;
 336             value |= fBuffer.get(currByte) & BYTE_MASK;
 337         }
 338         return value;
 339     }
 340
 341     private int getIntLE(long index, int length, boolean signed) {
 342         if ((length <= 0) || (length > BIT_INT)) {
 343             throw new IllegalArgumentException("Length must be between 1-32 bits"); //$NON-NLS-1$
 344         }
 345         long end = index + length;
 346         int startByte = (int) (index / BIT_CHAR);
 347         int endByte = (int) ((end + (BIT_CHAR - 1)) / BIT_CHAR);
 348         int currByte, lshift, cshift, mask, cmask, cache, mod;
 349         int value = 0;
 350
 351         currByte = endByte - 1;
 352         cache = fBuffer.get(currByte) & BYTE_MASK;
 353         mod = (int) (end % BIT_CHAR);
 354         lshift = (mod > 0) ? mod : BIT_CHAR;
 355         boolean isNeg = (cache & (1 << (lshift - 1))) != 0;
 356         if (signed && isNeg) {
 357             value = ~0;
 358         }
 359         if (startByte == (endByte - 1)) {
 360             cmask = cache >>> (index % BIT_CHAR);
 361             if (((length) % BIT_CHAR) > 0) {
 362                 mask = ~((~0) << length);
 363                 cmask &= mask;
 364             }
 365             value <<= length;
 366             value |= cmask;
 367             return value;
 368         }
 369         cshift = (int) (end % BIT_CHAR);
 370         if (cshift > 0) {
 371             mask = ~((~0) << cshift);
 372             cmask = cache & mask;
 373             value <<= cshift;
 374             value |= cmask;
 375             currByte--;
 376         }
 377         for (; currByte >= (startByte + 1); currByte--) {
 378             value <<= BIT_CHAR;
 379             value |= fBuffer.get(currByte) & BYTE_MASK;
 380         }
 381         lshift = (int) (index % BIT_CHAR);
 382         if (lshift > 0) {
 383             mask = ~((~0) << (BIT_CHAR - lshift));
 384             cmask = fBuffer.get(currByte) & BYTE_MASK;
 385             cmask >>>= lshift;
 386             cmask &= mask;
 387             value <<= (BIT_CHAR - lshift);
 388             value |= cmask;
 389         } else {
 390             value <<= BIT_CHAR;
 391             value |= fBuffer.get(currByte) & BYTE_MASK;
 392         }
 393         return value;
 394     }
 395
 396     // ------------------------------------------------------------------------
 397     // 'Put' operations on buffer
 398     // ------------------------------------------------------------------------
 399
 400     /**
 401      * Relative <i>put</i> method to write signed 32-bit integer.
 402      *
 403      * Write four bytes starting from current bit position in the buffer
 404      * according to the current byte order. The current position is increased of
 405      * <i>length</i> bits.
 406      *
 407      * @param value
 408      *            The int value to write
 409      * @throws CTFReaderException
 410      *             An error occurred writing the data. If the buffer is written
 411      *             beyond its end, this exception will be raised.
 412      */
 413     public void putInt(int value) throws CTFReaderException {
 414         putInt(BIT_INT, value);
 415     }
 416
 417     /**
 418      * Relative <i>put</i> method to write <i>length</i> bits integer.
 419      *
 420      * Writes <i>length</i> lower-order bits from the provided <i>value</i>,
 421      * starting from current bit position in the buffer. Sequential bytes are
 422      * written according to the current byte order. The sign bit is carried to
 423      * the MSB if signed is true. The sign bit is included in <i>length</i>. The
 424      * current position is increased of <i>length</i>.
 425      *
 426      * @param length
 427      *            The number of bits to write
 428      * @param value
 429      *            The value to write
 430      * @throws CTFReaderException
 431      *             An error occurred writing the data. If the buffer is written
 432      *             beyond its end, this exception will be raised.
 433      */
 434     public void putInt(int length, int value) throws CTFReaderException {
 435         final long curPos = fPosition;
 436
 437         if (!canRead(length)) {
 438             throw new CTFReaderException("Cannot write to bitbuffer, " //$NON-NLS-1$
 439                     + "insufficient space. Requested: " + length); //$NON-NLS-1$
 440         }
 441         if (length == 0) {
 442             return;
 443         }
 444         if (fByteOrder == ByteOrder.LITTLE_ENDIAN) {
 445             putIntLE(curPos, length, value);
 446         } else {
 447             putIntBE(curPos, length, value);
 448         }
 449         fPosition += length;
 450     }
 451
 452     private void putIntBE(long index, int length, int value) {
 453         if ((length <= 0) || (length > BIT_INT)) {
 454             throw new IllegalArgumentException("Length must be between 1-32 bits"); //$NON-NLS-1$
 455         }
 456         long end = index + length;
 457         int startByte = (int) (index / BIT_CHAR);
 458         int endByte = (int) ((end + (BIT_CHAR - 1)) / BIT_CHAR);
 459         int currByte, lshift, cshift, mask, cmask;
 460         int correctedValue = value;
 461
 462         /*
 463          * mask v high bits. Works for unsigned and two complement signed
 464          * numbers which value do not overflow on length bits.
 465          */
 466
 467         if (length < BIT_INT) {
 468             correctedValue &= ~(~0 << length);
 469         }
 470
 471         /* sub byte */
 472         if (startByte == (endByte - 1)) {
 473             lshift = (int) ((BIT_CHAR - (end % BIT_CHAR)) % BIT_CHAR);
 474             mask = ~((~0) << lshift);
 475             if ((index % BIT_CHAR) > 0) {
 476                 mask |= (~(0)) << (BIT_CHAR - (index % BIT_CHAR));
 477             }
 478             cmask = correctedValue << lshift;
 479             /*
 480              * low bits are cleared because of left-shift and high bits are
 481              * already cleared
 482              */
 483             cmask &= ~mask;
 484             int b = fBuffer.get(startByte) & BYTE_MASK;
 485             fBuffer.put(startByte, (byte) ((b & mask) | cmask));
 486             return;
 487         }
 488
 489         /* head byte contains MSB */
 490         currByte = endByte - 1;
 491         cshift = (int) (end % BIT_CHAR);
 492         if (cshift > 0) {
 493             lshift = BIT_CHAR - cshift;
 494             mask = ~((~0) << lshift);
 495             cmask = correctedValue << lshift;
 496             cmask &= ~mask;
 497             int b = fBuffer.get(currByte) & BYTE_MASK;
 498             fBuffer.put(currByte, (byte) ((b & mask) | cmask));
 499             correctedValue >>>= cshift;
 500             currByte--;
 501         }
 502
 503         /* middle byte(s) */
 504         for (; currByte >= (startByte + 1); currByte--) {
 505             fBuffer.put(currByte, (byte) correctedValue);
 506             correctedValue >>>= BIT_CHAR;
 507         }
 508         /* end byte contains LSB */
 509         if ((index % BIT_CHAR) > 0) {
 510             mask = (~0) << (BIT_CHAR - (index % BIT_CHAR));
 511             cmask = correctedValue & ~mask;
 512             int b = fBuffer.get(currByte) & BYTE_MASK;
 513             fBuffer.put(currByte, (byte) ((b & mask) | cmask));
 514         } else {
 515             fBuffer.put(currByte, (byte) correctedValue);
 516         }
 517     }
 518
 519     private void putIntLE(long index, int length, int value) {
 520         if ((length <= 0) || (length > BIT_INT)) {
 521             throw new IllegalArgumentException("Length must be between 1-32 bits"); //$NON-NLS-1$
 522         }
 523         long end = index + length;
 524         int startByte = (int) (index / BIT_CHAR);
 525         int endByte = (int) ((end + (BIT_CHAR - 1)) / BIT_CHAR);
 526         int currByte, lshift, cshift, mask, cmask;
 527         int correctedValue = value;
 528
 529         /*
 530          * mask v high bits. Works for unsigned and two complement signed
 531          * numbers which value do not overflow on length bits.
 532          */
 533
 534         if (length < BIT_INT) {
 535             correctedValue &= ~(~0 << length);
 536         }
 537
 538         /* sub byte */
 539         if (startByte == (endByte - 1)) {
 540             lshift = (int) (index % BIT_CHAR);
 541             mask = ~((~0) << lshift);
 542             if ((end % BIT_CHAR) > 0) {
 543                 mask |= (~(0)) << (end % BIT_CHAR);
 544             }
 545             cmask = correctedValue << lshift;
 546             /*
 547              * low bits are cleared because of left-shift and high bits are
 548              * already cleared
 549              */
 550             cmask &= ~mask;
 551             int b = fBuffer.get(startByte) & BYTE_MASK;
 552             fBuffer.put(startByte, (byte) ((b & mask) | cmask));
 553             return;
 554         }
 555
 556         /* head byte */
 557         currByte = startByte;
 558         cshift = (int) (index % BIT_CHAR);
 559         if (cshift > 0) {
 560             mask = ~((~0) << cshift);
 561             cmask = correctedValue << cshift;
 562             cmask &= ~mask;
 563             int b = fBuffer.get(currByte) & BYTE_MASK;
 564             fBuffer.put(currByte, (byte) ((b & mask) | cmask));
 565             correctedValue >>>= BIT_CHAR - cshift;
 566             currByte++;
 567         }
 568
 569         /* middle byte(s) */
 570         for (; currByte < (endByte - 1); currByte++) {
 571             fBuffer.put(currByte, (byte) correctedValue);
 572             correctedValue >>>= BIT_CHAR;
 573         }
 574         /* end byte */
 575         if ((end % BIT_CHAR) > 0) {
 576             mask = (~0) << (end % BIT_CHAR);
 577             cmask = correctedValue & ~mask;
 578             int b = fBuffer.get(currByte) & BYTE_MASK;
 579             fBuffer.put(currByte, (byte) ((b & mask) | cmask));
 580         } else {
 581             fBuffer.put(currByte, (byte) correctedValue);
 582         }
 583     }
 584
 585     // ------------------------------------------------------------------------
 586     // Buffer attributes handling
 587     // ------------------------------------------------------------------------
 588
 589     /**
 590      * Can this buffer be read for thus amount of bits?
 591      *
 592      * @param length
 593      *            the length in bits to read
 594      * @return does the buffer have enough room to read the next "length"
 595      */
 596     public boolean canRead(int length) {
 597         return ((fPosition + length) <= fBitCapacity);
 598     }
 599
 600     /**
 601      * Sets the order of the buffer.
 602      *
 603      * @param order
 604      *            The order of the buffer.
 605      */
 606     public void setByteOrder(ByteOrder order) {
 607         fByteOrder = order;
 608         fBuffer.order(order);
 609     }
 610
 611     /**
 612      * Sets the order of the buffer.
 613      *
 614      * @return The order of the buffer.
 615      */
 616     public ByteOrder getByteOrder() {
 617         return fByteOrder;
 618     }
 619
 620     /**
 621      * Sets the position in the buffer.
 622      *
 623      * @param newPosition
 624      *            The new position of the buffer.
 625      * @throws CTFReaderException
 626      *             Thrown on out of bounds exceptions
 627      * @since 3.0
 628      */
 629     public void position(long newPosition) throws CTFReaderException {
 630
 631         if (newPosition > fBitCapacity) {
 632             throw new CTFReaderException("Out of bounds exception on a position move, attempting to access position: " + newPosition); //$NON-NLS-1$
 633         }
 634         fPosition = newPosition;
 635     }
 636
 637     /**
 638      *
 639      * Sets the position in the buffer.
 640      *
 641      * @return order The position of the buffer.
 642      * @since 3.0
 643      */
 644     public long position() {
 645         return fPosition;
 646     }
 647
 648     /**
 649      * Sets the byte buffer
 650      *
 651      * @param buf
 652      *            the byte buffer
 653      */
 654     @Deprecated
 655     public void setByteBuffer(ByteBuffer buf) {
 656         /*
 657          * to avoid "The method setByteBuffer(ByteBuffer) from the type
 658          * BitBuffer can be declared as static"
 659          */
 660         long data = fPosition;
 661         fPosition = data;
 662         throw new UnsupportedOperationException("Bytebuffers are now final"); //$NON-NLS-1$
 663
 664     }
 665
 666     /**
 667      * Gets the byte buffer
 668      *
 669      * @return The byte buffer
 670      */
 671     public ByteBuffer getByteBuffer() {
 672         return fBuffer;
 673     }
 674
 675     /**
 676      * Resets the bitbuffer.
 677      */
 678     public void clear() {
 679         resetPosition();
 680         fBuffer.clear();
 681     }
 682
 683 }