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 files COPYING and Copyright.html.  COPYING can be found at the root   *
 * of the source code distribution tree; Copyright.html can be found at the  *
 * root level of an installed copy of the electronic HDF5 document set and   *
 * is linked from the top-level documents page.  It can also be found at     *
 * http://hdfgroup.org/HDF5/doc/Copyright.html.  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.
 */

#define H5T_PACKAGE		/*suppress error about including H5Tpkg	  */


#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
 *
 * Programmer:	Robb Matzke
 *              Wednesday, June 10, 1998
 *
 *-------------------------------------------------------------------------
 */
void
H5T_bit_copy(uint8_t *dst, size_t dst_offset, const uint8_t *src,
    size_t src_offset, size_t size)
{
    unsigned	shift;
    unsigned mask_lo, mask_hi;
    unsigned	s_idx, d_idx;

    /*
     * 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) {
	unsigned nbits = MIN3(size, 8 - dst_offset, 8 - src_offset);
	unsigned mask = ((unsigned)1 << nbits) - 1;

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

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

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

	size -= nbits;
    } /* end while */

    /*
     * 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 = ((unsigned)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));
	} /* end if */
        else
	    dst[d_idx] = src[s_idx];
    } /* end for */

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

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

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

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

	size -= nbits;
    } /* end while */
} /* 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
 *
 * Programmer:	Raymond Lu
 *              Monday, April 12, 2004
 *
 *-------------------------------------------------------------------------
 */
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_NOAPI(FAIL)

    /* 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);
            } /* end if */
            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 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:	Success:	The bit sequence interpretted as an unsigned
 *				integer.
 *
 *		Failure:	0
 *
 * Programmer:	Robb Matzke
 *              Tuesday, June 23, 1998
 *
 *-------------------------------------------------------------------------
 */
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;      /* Return value */

    FUNC_ENTER_NOAPI_NOINIT_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;
            } /* end for */
            break;

        case H5T_ORDER_ERROR:
        case H5T_ORDER_VAX:
        case H5T_ORDER_NONE:
        case H5T_ORDER_MIXED:
        default:
            /* Unknown endianness. Bail out. */
            HGOTO_DONE(UFAIL)
    } /* end switch */

    /* Set return value */
    ret_value = val;

done:
    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
 *
 * Programmer:	Robb Matzke
 *              Wednesday, June 24, 1998
 *
 *-------------------------------------------------------------------------
 */
void
H5T_bit_set_d(uint8_t *buf, size_t offset, size_t size, uint64_t val)
{
    size_t	i, hs;

    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;
            } /* end for */
            break;

        case H5T_ORDER_ERROR:
        case H5T_ORDER_VAX:
        case H5T_ORDER_NONE:
        case H5T_ORDER_MIXED:
        default:
            HDabort();
    } /* end switch */

    H5T_bit_copy(buf, offset, (uint8_t*)&val, (size_t)0, size);
} /* 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
 *
 * Programmer:	Robb Matzke
 *              Wednesday, June 10, 1998
 *
 * Modifications:
 *
 *-------------------------------------------------------------------------
 */
void
H5T_bit_set(uint8_t *buf, size_t offset, size_t size, hbool_t value)
{
    int	idx;

    /* 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)(mask << offset);
	else
	    buf[idx++] &= (uint8_t)(~(mask << offset));
	size -= nbits;
    } /* end if */

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

    /* 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));
    } /* end if */
} /* 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
 *		significat 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
 *
 * Programmer:	Robb Matzke
 *              Wednesday, June 10, 1998
 *
 *-------------------------------------------------------------------------
 */
ssize_t
H5T_bit_find(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_NOAPI_NOINIT_NOERR here to avoid performance issues */
    FUNC_ENTER_NOAPI_NOINIT_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);
            } /* end if */
            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:	Success:        The carry-out value.  One if overflows,
 *                              zero otherwise.
 *
 *		Failure:	Negative
 *
 * Programmer:	Robb Matzke
 *              Friday, June 26, 1998
 *
 *-------------------------------------------------------------------------
 */
htri_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_NOAPI_NOINIT_NOERR here to avoid performance issues */
    FUNC_ENTER_NOAPI_NOINIT_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)((acc & mask) << start);
	size -= MIN(size, 8 - start);
	start = 0;
	idx++;
    } /* end if */

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

    /* 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);
    } /* end if */

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


/*-------------------------------------------------------------------------
 * Function:	H5T_bit_dec
 *
 * Purpose:	decrement part of a bit field by substracting 1.  The bit
 *              field starts with bit position START and is SIZE bits long.
 *
 * Return:	Success:        The "borrow-in" value. It's one if underflows,
 *                              zero otherwise.
 *
 *		Failure:	Negative
 *
 * Programmer:	Raymond Lu
 *              March 17, 2004
 *
 *-------------------------------------------------------------------------
 */
htri_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_NOAPI_NOINIT_NOERR here to avoid performance issues */
    FUNC_ENTER_NOAPI_NOINIT_NOERR

    HDassert(buf);
    HDassert(size);

    /* The first partial byte */
    if((size + start - 1) / 8 > idx) { /*bit sequence doesn't end in the same byte as starts*/
        /* Example:  a sequence like 11000100 and start = 3.  We substract 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 substract
         * 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;
        } /* end while */

        /* 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));
        } /* end if */
    } /* end if */
    else { /* bit sequence ends in the same byte as starts */
        /* Example: a sequence like 11000100 and pos=3, size=3.  We substract 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;
        } /* end if */
    } /* end else */

    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
 *
 * Programmer:	Raymond Lu
 *              March 19, 2004
 *
 *-------------------------------------------------------------------------
 */
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_NOAPI_NOINIT_NOERR here to avoid performance issues */
    FUNC_ENTER_NOAPI_NOINIT_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;
        } /* end while */

        /* 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);
        } /* end if */
    } /* end if */
    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() */