/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Copyright by The HDF Group. * * 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() */