bitops.h 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
  1. /*************************************************************************/ /*!
  2. @File
  3. @Title Utility functions/macros for bitwise operations
  4. @Copyright Copyright (c) Imagination Technologies Ltd. All Rights Reserved
  5. @License Strictly Confidential.
  6. */ /**************************************************************************/
  7. #if !defined (__BITOPS_H__)
  8. #define __BITOPS_H__
  9. #include "img_defs.h"
  10. #if (_MSC_VER >= 1400)
  11. #include <intrin.h> /* for _BitScanForward */
  12. #endif
  13. /******************************************************************************
  14. Function Name : GetRange
  15. Inputs : auArr[], uTop, uBottom
  16. Outputs : uBitData
  17. Returns : the bits between those offsets into auArr, uTop and uBottom,
  18. inclusive. uTop and uBottom are either offsets into 2
  19. consecutive elements of auArr or in the same element
  20. Description : -
  21. ******************************************************************************/
  22. FORCE_INLINE IMG_UINT32 GetRange(const IMG_UINT32 auArr[],
  23. const IMG_UINT32 uTop,
  24. const IMG_UINT32 uBottom)
  25. {
  26. IMG_UINT32 uBitData;
  27. const IMG_UINT32 uTopLong = uTop >> 5;
  28. const IMG_UINT32 uBottomLong = uBottom >> 5;
  29. const IMG_UINT32 uBottomShift = (IMG_UINT32)uBottom & 0x1FL;
  30. const IMG_UINT32 uRange = (uTop - uBottom) + 1;
  31. const IMG_UINT32 uDataMask = ((uRange == 32) ?
  32. 0xFFFFFFFFU :
  33. ((1U << uRange) - 1));
  34. if (uTopLong == uBottomLong)
  35. {
  36. /* data fits within one of our 32-bit chunks */
  37. uBitData = ((auArr[uBottomLong] >> uBottomShift) & uDataMask);
  38. }
  39. else
  40. {
  41. uBitData = (((auArr[uBottomLong] >> uBottomShift) |
  42. (auArr[uTopLong] << (32 - uBottomShift))) &
  43. uDataMask);
  44. }
  45. return uBitData;
  46. }
  47. FORCE_INLINE IMG_UINT32 GetBit(const IMG_UINT32 auArr[], const IMG_UINT32 uPos)
  48. {
  49. return auArr[uPos >> 5u] & (1u << (uPos % 32)) ? 1u : 0u;
  50. }
  51. /*
  52. Write the given bits into the given index locations of auArr
  53. */
  54. FORCE_INLINE void SetRange(IMG_UINT32 auArr[],
  55. const IMG_UINT32 uTop,
  56. const IMG_UINT32 uBottom,
  57. const IMG_UINT32 uBitData)
  58. {
  59. const IMG_UINT32 uTopLong = uTop >> 5;
  60. const IMG_UINT32 uBottomLong = uBottom >> 5;
  61. const IMG_UINT32 uBottomShift = (IMG_UINT32)uBottom & 0x1FU;
  62. const IMG_UINT32 uRange = (uTop - uBottom) + 1;
  63. const IMG_UINT32 uDataMask = ((uRange == 32) ?
  64. 0xFFFFFFFFU :
  65. ((1U << uRange) - 1));
  66. if (uTopLong == uBottomLong)
  67. {
  68. /*
  69. data fits within one of our 32-bit chunks
  70. */
  71. auArr[uBottomLong] = (auArr[uBottomLong] &
  72. (~(uDataMask << uBottomShift))) |
  73. ((uBitData & uDataMask) << uBottomShift);
  74. }
  75. else
  76. {
  77. const IMG_UINT32 uTopShift = 32 - uBottomShift;
  78. /*
  79. data is split across two of our 32-bit chunks
  80. */
  81. auArr[uTopLong] = (auArr[uTopLong] & (~(uDataMask >> uTopShift))) |
  82. ((uBitData & uDataMask) >> uTopShift);
  83. auArr[uBottomLong] = (auArr[uBottomLong] &
  84. (~(uDataMask << uBottomShift))) |
  85. ((uBitData & uDataMask) << uBottomShift);
  86. }
  87. }
  88. FORCE_INLINE void SetBit(IMG_UINT32 auArr[],
  89. const IMG_UINT32 uBit,
  90. const IMG_UINT32 uBitData)
  91. {
  92. if (uBitData)
  93. {
  94. auArr[uBit >> 5u] |= (1u << (uBit % 32u));
  95. }
  96. else
  97. {
  98. auArr[uBit >> 5u] &= ~(1u << (uBit % 32u));
  99. }
  100. }
  101. FORCE_INLINE IMG_UINT32 CountBits(const IMG_UINT32 auArr[],
  102. const IMG_UINT32 uEnd,
  103. const IMG_UINT32 uStart)
  104. {
  105. IMG_UINT32 uCount, i;
  106. uCount = 0;
  107. for (i = uStart; i <= uEnd; i++)
  108. {
  109. uCount += GetBit(auArr, i);
  110. }
  111. return uCount;
  112. }
  113. FORCE_INLINE
  114. IMG_UINT32 FirstSetBit(IMG_UINT32 v)
  115. /******************************************************************************
  116. FUNCTION : FirstSetBit
  117. PURPOSE : Returns the first set bit in a dword
  118. PARAMETERS : v - Find the first set bit in this dword (must be non-zero).
  119. RETURNS : The (zero-based) index of the first set bit.
  120. ******************************************************************************/
  121. {
  122. #if defined(__GNUC__)
  123. return __builtin_ctz(v);
  124. #elif defined(__linux__)
  125. return ffs(v) - 1;
  126. #else /* defined(__linux__) */
  127. #if (_MSC_VER >= 1400)
  128. IMG_UINT32 uBitPos;
  129. _BitScanForward((unsigned long *)&uBitPos, v);
  130. return uBitPos;
  131. #else /* (_MSC_VER >= 1400) */
  132. #if defined(_MSC_VER) && defined(_M_IX86)
  133. IMG_UINT32 uBitPos;
  134. __asm
  135. {
  136. bsf eax, v
  137. mov uBitPos, eax
  138. }
  139. return uBitPos;
  140. #else /* defined(_MSC_VER) && defined(_M_IX86) */
  141. /*
  142. "Using de Bruijn Sequences to Index a 1 in a Computer Word"
  143. (http://graphics.stanford.edu/~seander/bithacks.html)
  144. */
  145. static const int MultiplyDeBruijnBitPosition[32] =
  146. {
  147. 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  148. 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  149. };
  150. return MultiplyDeBruijnBitPosition[(((v & -(IMG_INT32)v) * 0x077CB531U)) >> 27];
  151. #endif /* defined(_MSC_VER) && defined(_M_IX86) */
  152. #endif /* (_MSC_VER >= 1400) */
  153. #endif /* defined(__linux__) */
  154. }
  155. #endif /* if !defined (__BITOPS_H__) */