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