path: root/src/H5Tbit.c

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Copyright by The HDF Group.                                               *
 * Copyright by the Board of Trustees of the University of Illinois.         *
 * All rights reserved.                                                      *
 *                                                                           *
 * This file is part of HDF5.  The full HDF5 copyright notice, including     *
 * terms governing use, modification, and redistribution, is contained in    *
 * the COPYING file, which can be found at the root of the source code       *
 * distribution tree, or in https://www.hdfgroup.org/licenses.               *
 * If you do not have access to either file, you may request a copy from     *
 * help@hdfgroup.org.                                                        *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/* Module Info: Operations on bit vectors.  A bit vector is an array of bytes
 *              with the least-significant bits in the first byte.  That is,
 *              the bytes are in little-endian order.
 */

#include "H5Tmodule.h" /* This source code file is part of the H5T module */

#include "H5private.h"   /*generic functions			  */
#include "H5Eprivate.h"  /*error handling			  */
#include "H5MMprivate.h" /* Memory management			*/
#include "H5Tpkg.h"      /*data-type functions			  */
#include "H5WBprivate.h" /* Wrapped Buffers                      */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_copy
 *
 * Purpose:     Copies bits from one vector to another.
 *
 * Return:      void
 *
 *-------------------------------------------------------------------------
 */
void
H5T__bit_copy(uint8_t *dst, size_t dst_offset, const uint8_t *src, size_t src_offset, size_t size)
{
    size_t shift;
    size_t mask_lo, mask_hi;
    size_t s_idx, d_idx;

    FUNC_ENTER_PACKAGE_NOERR

    /* Normalize the offset to be a byte number and a bit offset within that
     * byte.
     */
    s_idx = src_offset / 8;
    d_idx = dst_offset / 8;
    src_offset %= 8;
    dst_offset %= 8;

    /* Get things rolling. This means copying bits until we're aligned on a
     * source byte.  This the following example, five bits are copied to the
     * destination.
     *
     *                      src[s_idx]
     *   +---------------+---------------+
     *   |7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|
     *   +---------------+---------------+
     *      ... : : : : : | | | | |
     *      ... v v v v v V V V V V
     *      ...+---------------+---------------+
     *      ...|7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|
     *      ...+---------------+---------------+
     *           dst[d_idx+1]      dst[d_idx]
     */
    while (src_offset && size > 0) {
        size_t nbits = MIN3(size, 8 - dst_offset, 8 - src_offset);
        size_t mask  = ((size_t)1 << nbits) - 1;

        dst[d_idx] &= (uint8_t) ~(mask << dst_offset);
        dst[d_idx] = (uint8_t)(dst[d_idx] | (((src[s_idx] >> src_offset) & (uint8_t)mask) << dst_offset));

        src_offset += nbits;
        if (src_offset >= 8) {
            s_idx++;
            src_offset %= 8;
        }

        dst_offset += nbits;
        if (dst_offset >= 8) {
            d_idx++;
            dst_offset %= 8;
        }

        size -= nbits;
    }

    /* The middle bits. We are aligned on a source byte which needs to be
     * copied to two (or one in the degenerate case) destination bytes.
     *
     * 		      src[s_idx]
     * 		   +---------------+
     *  	   |7 6 5 4 3 2 1 0|
     * 		   +---------------+
     *              | | | | | | | |
     * 		    V V V V V V V V
     *   +---------------+---------------+
     *   |7 6 5 4 3 2 1 0|7 6 5 4 3 2 1 0|
     *   +---------------+---------------+
     *     dst[d_idx+1]      dst[d_idx]
     *
     *
     * Calculate shifts and masks.  See diagrams below.  MASK_LO in this
     * example is 0x1f (the low five bits) and MASK_HI is 0xe0 (the high three
     * bits). SHIFT is three since the source must be shifted right three bits
     * to line up with the destination.
     */
    shift   = dst_offset;
    mask_lo = ((size_t)1 << (8 - shift)) - 1;
    mask_hi = (~mask_lo) & 0xff;

    for (/*void*/; size > 8; size -= 8, d_idx++, s_idx++) {
        if (shift) {
            dst[d_idx + 0] &= (uint8_t)(~(mask_lo << shift));
            dst[d_idx + 0] |= (uint8_t)((src[s_idx] & mask_lo) << shift);
            dst[d_idx + 1] &= (uint8_t)(~(mask_hi >> (8 - shift)));
            dst[d_idx + 1] |= (uint8_t)((src[s_idx] & mask_hi) >> (8 - shift));
        }
        else
            dst[d_idx] = src[s_idx];
    }

    /* Finish up */
    while (size > 0) {
        size_t nbits = (size_t)MIN3(size, 8 - dst_offset, 8 - src_offset);
        size_t mask  = ((size_t)1 << nbits) - 1;

        dst[d_idx] &= (uint8_t)(~(mask << dst_offset));
        dst[d_idx] = (uint8_t)(dst[d_idx] | (((src[s_idx] >> src_offset) & (uint8_t)mask) << dst_offset));

        src_offset += nbits;
        if (src_offset >= 8) {
            s_idx++;
            src_offset %= 8;
        }

        dst_offset += nbits;
        if (dst_offset >= 8) {
            d_idx++;
            dst_offset %= 8;
        }

        size -= nbits;
    }

    FUNC_LEAVE_NOAPI_VOID
} /* end H5T__bit_copy() */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_shift
 *
 * Purpose:     Simulation of hardware shifting.  Shifts a bit vector
 *              in a way similar to shifting a variable value, like
 *              value <<= 3, or value >>= 16.  SHIFT_DIST is positive for
 *              left shift, negative for right shift.  The bit vector starts
 *              at OFFSET and is SIZE long.  The caller has to make sure
 *              SIZE+OFFSET doesn't exceed the size of BUF.
 *
 *              For example, if we have a bit sequence 00011100, offset=2,
 *              size=3, shift_dist=2, the result will be 00010000.
 *
 * Return:      void
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5T__bit_shift(uint8_t *buf, ssize_t shift_dist, size_t offset, size_t size)
{
    uint8_t tmp_buf[512];        /* Temporary buffer */
    H5WB_t *wb        = NULL;    /* Wrapped buffer for temporary buffer */
    herr_t  ret_value = SUCCEED; /* Return value */

    FUNC_ENTER_PACKAGE

    /* Sanity check */
    HDassert(buf);
    HDassert(size);

    if (shift_dist) {
        size_t abs_shift_dist = (size_t)ABS(shift_dist);

        if (abs_shift_dist >= size)
            H5T__bit_set(buf, offset, size, 0);
        else {
            size_t   buf_size = (size / 8) + 1; /* Size of shift buffer needed */
            uint8_t *shift_buf;                 /* Pointer to shift buffer */

            /* Wrap the local buffer for serialized header info */
            if (NULL == (wb = H5WB_wrap(tmp_buf, sizeof(tmp_buf))))
                HGOTO_ERROR(H5E_DATATYPE, H5E_CANTINIT, FAIL, "can't wrap buffer")

            /* Get a pointer to a buffer that's large enough  */
            if (NULL == (shift_buf = (uint8_t *)H5WB_actual(wb, buf_size)))
                HGOTO_ERROR(H5E_DATATYPE, H5E_NOSPACE, FAIL, "can't get actual buffer")

            /* Shift vector by making copies */
            if (shift_dist > 0) { /* left shift */
                /* Copy part to be shifted to a temporary buffer */
                H5T__bit_copy(shift_buf, (size_t)0, buf, offset, size - abs_shift_dist);

                /* Copy it back to the original buffer */
                H5T__bit_copy(buf, offset + abs_shift_dist, shift_buf, (size_t)0, size - abs_shift_dist);

                /* Zero-set the left part*/
                H5T__bit_set(buf, offset, abs_shift_dist, 0);
            }
            else { /* right shift */
                H5T__bit_copy(shift_buf, (size_t)0, buf, offset + abs_shift_dist, size - abs_shift_dist);
                H5T__bit_copy(buf, offset, shift_buf, (size_t)0, size - abs_shift_dist);
                H5T__bit_set(buf, offset + size - abs_shift_dist, abs_shift_dist, 0);
            }
        } /* end else */
    }     /* end if */

done:
    /* Release resources */
    if (wb && H5WB_unwrap(wb) < 0)
        HDONE_ERROR(H5E_DATATYPE, H5E_CLOSEERROR, FAIL, "can't close wrapped buffer")

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5T__bit_shift() */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_get_d
 *
 * Purpose:     Return a small bit sequence as a number.  Bit vector starts
 *              at OFFSET and is SIZE bits long.
 *
 * Return:      The bit sequence interpreted as an unsigned integer
 *
 *-------------------------------------------------------------------------
 */
uint64_t
H5T__bit_get_d(uint8_t *buf, size_t offset, size_t size)
{
    uint64_t val = 0;
    size_t   i, hs;
    uint64_t ret_value = 0; /* Return value */

    FUNC_ENTER_PACKAGE_NOERR

    HDassert(8 * sizeof(val) >= size);

    H5T__bit_copy((uint8_t *)&val, (size_t)0, buf, offset, size);
    switch (H5T_native_order_g) {
        case H5T_ORDER_LE:
            break;

        case H5T_ORDER_BE:
            for (i = 0, hs = sizeof(val) / 2; i < hs; i++) {
                uint8_t tmp                              = ((uint8_t *)&val)[i];
                ((uint8_t *)&val)[i]                     = ((uint8_t *)&val)[sizeof(val) - (i + 1)];
                ((uint8_t *)&val)[sizeof(val) - (i + 1)] = tmp;
            }
            break;

        case H5T_ORDER_ERROR:
        case H5T_ORDER_VAX:
        case H5T_ORDER_NONE:
        case H5T_ORDER_MIXED:
        default:
            /* This function can't return errors */
            HDassert(0 && "unknown byte order");
    }

    /* Set return value */
    ret_value = val;

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5T__bit_get_d() */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_set_d
 *
 * Purpose:     Sets part of a bit vector to the specified unsigned value.
 *
 * Return:      void
 *
 *-------------------------------------------------------------------------
 */
void
H5T__bit_set_d(uint8_t *buf, size_t offset, size_t size, uint64_t val)
{
    size_t i, hs;

    FUNC_ENTER_PACKAGE_NOERR

    HDassert(8 * sizeof(val) >= size);

    switch (H5T_native_order_g) {
        case H5T_ORDER_LE:
            break;

        case H5T_ORDER_BE:
            for (i = 0, hs = sizeof(val) / 2; i < hs; i++) {
                uint8_t tmp                              = ((uint8_t *)&val)[i];
                ((uint8_t *)&val)[i]                     = ((uint8_t *)&val)[sizeof(val) - (i + 1)];
                ((uint8_t *)&val)[sizeof(val) - (i + 1)] = tmp;
            }
            break;

        case H5T_ORDER_ERROR:
        case H5T_ORDER_VAX:
        case H5T_ORDER_NONE:
        case H5T_ORDER_MIXED:
        default:
            HDabort();
    }

    H5T__bit_copy(buf, offset, (uint8_t *)&val, (size_t)0, size);

    FUNC_LEAVE_NOAPI_VOID
} /* end H5T__bit_set_d() */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_set
 *
 * Purpose:     Sets or clears bits in a contiguous region of a vector
 *              beginning at bit OFFSET and continuing for SIZE bits.
 *
 * Return:      void
 *
 *-------------------------------------------------------------------------
 */
void
H5T__bit_set(uint8_t *buf, size_t offset, size_t size, hbool_t value)
{
    int idx;

    FUNC_ENTER_PACKAGE_NOERR

    /* Normalize */
    idx = (int)offset / 8;
    offset %= 8;

    /* The first partial byte */
    if (size && offset % 8) {
        size_t   nbits = MIN(size, 8 - offset);
        unsigned mask  = ((unsigned)1 << nbits) - 1;

        if (value)
            buf[idx] = (uint8_t)(buf[idx] | (mask << offset));
        else
            buf[idx] &= (uint8_t)(~(mask << offset));

        idx++;
        size -= nbits;
    }

    /* The middle bytes */
    while (size >= 8) {
        buf[idx++] = (uint8_t)(value ? 0xff : 0x00);
        size -= 8;
    }

    /* The last partial byte */
    if (size) {
        if (value)
            buf[idx] |= (uint8_t)(((unsigned)1 << size) - 1);
        else
            buf[idx] &= (uint8_t)(~(((unsigned)1 << size) - 1));
    }

    FUNC_LEAVE_NOAPI_VOID
} /* end H5T__bit_set() */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_find
 *
 * Purpose:     Finds the first bit with the specified VALUE within a region
 *              of a bit vector.  The region begins at OFFSET and continues
 *              for SIZE bits, but the region can be searched from the least
 *              significant end toward the most significant end(H5T_BIT_LSB
 *              as DIRECTION), or from the most significant end to the least
 *              significant end(H5T_BIT_MSB as DIRECTION).
 *
 * Return:      Success:    The position of the bit found, relative to
 *                          the offset.
 *
 *              Failure:    -1
 *
 *-------------------------------------------------------------------------
 */
ssize_t
H5T__bit_find(const uint8_t *buf, size_t offset, size_t size, H5T_sdir_t direction, hbool_t value)
{
    ssize_t base = (ssize_t)offset;
    ssize_t idx, i;
    size_t  iu;
    ssize_t ret_value = (-1); /* Return value */

    /* Use FUNC_ENTER_PACKAGE_NOERR here to avoid performance issues */
    FUNC_ENTER_PACKAGE_NOERR

    /* Some functions call this with value=TRUE */
    HDassert(TRUE == 1);

    switch (direction) {
        case H5T_BIT_LSB:
            /* Calculate index */
            idx = (ssize_t)(offset / 8);
            offset %= 8;

            /* Beginning */
            if (offset) {
                for (iu = offset; iu < 8 && size > 0; iu++, size--)
                    if (value == (hbool_t)((buf[idx] >> iu) & 0x01))
                        HGOTO_DONE(8 * idx + (ssize_t)iu - base);

                offset = 0;
                idx++;
            } /* end if */

            /* Middle */
            while (size >= 8) {
                if ((value ? 0x00 : 0xff) != buf[idx])
                    for (i = 0; i < 8; i++)
                        if (value == (hbool_t)((buf[idx] >> i) & 0x01))
                            HGOTO_DONE(8 * idx + i - base);

                size -= 8;
                idx++;
            } /* end while */

            /* End */
            for (i = 0; i < (ssize_t)size; i++)
                if (value == (hbool_t)((buf[idx] >> i) & 0x01))
                    HGOTO_DONE(8 * idx + i - base);
            break;

        case H5T_BIT_MSB:
            /* Calculate index */
            idx = (ssize_t)((offset + size - 1) / 8);
            offset %= 8;

            /* Beginning */
            if (size > 8 - offset && (offset + size) % 8) {
                for (iu = (offset + size) % 8; iu > 0; --iu, --size)
                    if (value == (hbool_t)((buf[idx] >> (iu - 1)) & 0x01))
                        HGOTO_DONE(8 * idx + (ssize_t)(iu - 1) - base);

                --idx;
            } /* end if */

            /* Middle */
            while (size >= 8) {
                if ((value ? 0x00 : 0xff) != buf[idx]) {
                    for (i = 7; i >= 0; --i)
                        if (value == (hbool_t)((buf[idx] >> i) & 0x01))
                            HGOTO_DONE(8 * idx + i - base);
                } /* end if */

                size -= 8;
                --idx;
            } /* end while */

            /* End */
            if (size > 0) {
                for (iu = offset + size; iu > offset; --iu)
                    if (value == (hbool_t)((buf[idx] >> (iu - 1)) & 0x01))
                        HGOTO_DONE(8 * idx + (ssize_t)(iu - 1) - base);
            }
            break;

        default:
            HDassert(0 && "Unknown bit search direction");
    } /* end switch */

done:
    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5T__bit_find() */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_inc
 *
 * Purpose:     Increment part of a bit field by adding 1.  The bit field
 *              starts with bit position START and is SIZE bits long.
 *
 * Return:      The carry-out value.  TRUE if overflows, FALSE otherwise.
 *
 *-------------------------------------------------------------------------
 */
hbool_t
H5T__bit_inc(uint8_t *buf, size_t start, size_t size)
{
    size_t   idx   = start / 8;
    unsigned carry = 1;
    unsigned acc, mask;

    /* Use FUNC_ENTER_PACKAGE_NOERR here to avoid performance issues */
    FUNC_ENTER_PACKAGE_NOERR

    HDassert(buf);

    start %= 8;

    /* The first partial byte */
    if (start) {
        if (size + start < 8)
            mask = ((unsigned)1 << size) - 1;
        else
            mask = ((unsigned)1 << (8 - start)) - 1;
        acc = ((unsigned)buf[idx] >> start) & mask;
        acc++;
        carry = acc & ((unsigned)1 << MIN(size, 8 - start));
        buf[idx] &= (uint8_t)(~(mask << start));
        buf[idx] = (uint8_t)(buf[idx] | ((acc & mask) << start));
        size -= MIN(size, 8 - start);
        start = 0;
        idx++;
    }

    /* The middle */
    while (carry && size >= 8) {
        acc = buf[idx];
        acc++;
        carry    = acc & 0x100;
        buf[idx] = (uint8_t)(acc & 0xff);
        idx++;
        size -= 8;
    }

    /* The last bits */
    if (carry && size > 0) {
        mask = ((unsigned)1 << size) - 1;
        acc  = buf[idx] & mask;
        acc++;
        carry = acc & ((unsigned)1 << size);
        buf[idx] &= (uint8_t)(~mask);
        buf[idx] |= (uint8_t)(acc & mask);
    }

    FUNC_LEAVE_NOAPI(carry ? TRUE : FALSE)
} /* end H5T__bit_inc() */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_dec
 *
 * Purpose:     Decrement part of a bit field by subtracting 1.  The bit
 *              field starts with bit position START and is SIZE bits long.
 *
 * Return:      The "borrow-in" value. It's TRUE if underflows, FALSE
 *              otherwise.
 *
 *-------------------------------------------------------------------------
 */
hbool_t
H5T__bit_dec(uint8_t *buf, size_t start, size_t size)
{
    size_t   idx = start / 8;
    size_t   pos = start % 8;
    uint8_t  tmp;
    unsigned borrow = 0;

    /* Use FUNC_ENTER_PACKAGE_NOERR here to avoid performance issues */
    FUNC_ENTER_PACKAGE_NOERR

    HDassert(buf);
    HDassert(size);

    /* The first partial byte */
    if ((size + start - 1) / 8 > idx) {
        /* The bit sequence doesn't end in the same byte as starts */

        /* Example:  a sequence like 11000100 and start = 3.  We subtract 00001000 from
         * it and get 10111100.  If a sequence is 00000111, we do right shift for START
         * bits and get 00000000.  So we need to borrow from higher byte when we subtract
         * 00001000.
         */
        if (!(buf[idx] >> pos))
            borrow = 1;
        buf[idx] = (uint8_t)(buf[idx] - (1 << pos));
        idx++;
        size -= (8 - pos);

        /* The middle bytes */
        while (borrow && size >= 8) {
            if (buf[idx])
                borrow = 0;
            buf[idx]--;

            idx++;
            size -= 8;
        }

        /* The last partial byte */
        if (borrow && size > 0) {
            /* Similar to the first byte case, where sequence ends in the same byte as starts */
            tmp = buf[idx];
            buf[idx]--;
            if ((buf[idx] >> size) != tmp >> size)
                buf[idx] = (uint8_t)(buf[idx] + (1 << size));
        }
    }
    else {
        /* The bit sequence ends in the same byte as starts */

        /* Example: a sequence like 11000100 and pos=3, size=3.  We subtract 00001000
         * and get 10111100.  A bit is borrowed from 6th bit(buf[idx]>>6=00000010, tmp>>6=00000011,
         * not equal).  We need to put this bit back by increment 1000000.
         */
        tmp      = buf[idx];
        buf[idx] = (uint8_t)(buf[idx] - (1 << pos));
        if ((buf[idx] >> (pos + size)) != tmp >> (pos + size)) {
            buf[idx] = (uint8_t)(buf[idx] + (1 << (pos + size)));
            borrow   = 1;
        }
    }

    FUNC_LEAVE_NOAPI(borrow ? TRUE : FALSE)
} /* end H5T__bit_dec() */

/*-------------------------------------------------------------------------
 * Function:    H5T__bit_neg
 *
 * Purpose:     Negate part of a bit sequence.  The bit field starts with
 *              bit position START and is SIZE bits long.
 *
 * Return:      void
 *
 *-------------------------------------------------------------------------
 */
void
H5T__bit_neg(uint8_t *buf, size_t start, size_t size)
{
    size_t  idx = start / 8;
    size_t  pos = start % 8;
    uint8_t tmp[1];

    /* Use FUNC_ENTER_PACKAGE_NOERR here to avoid performance issues */
    FUNC_ENTER_PACKAGE_NOERR

    HDassert(buf);
    HDassert(size);

    /* The first partial byte */
    tmp[0] = (uint8_t)~buf[idx];

    /* Simply copy the negated bit field back to the original byte */
    if ((size + start - 1) / 8 > idx) { /*bit sequence doesn't end in the same byte as starts*/
        H5T__bit_copy(&(buf[idx]), pos, tmp, pos, (8 - pos));
        idx++;
        size -= (8 - pos);

        /* The middle bytes */
        while (size >= 8) {
            buf[idx] = (uint8_t) ~(buf[idx]);
            idx++;
            size -= 8;
        }

        /* The last partial byte */
        if (size > 0) {
            /* Similar to the first byte case, where sequence ends in the same byte as starts */
            tmp[0] = (uint8_t)~buf[idx];
            H5T__bit_copy(&(buf[idx]), (size_t)0, tmp, (size_t)0, size);
        }
    }
    else {
        /* bit sequence ends in the same byte as starts */
        H5T__bit_copy(&(buf[idx]), pos, tmp, pos, size);
    }

    FUNC_LEAVE_NOAPI_VOID
} /* end H5T__bit_neg() */