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