log2.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417
  1. /*************************************************************************/ /*!
  2. @Title Integer log2 and related functions
  3. @Copyright Copyright (c) Imagination Technologies Ltd. All Rights Reserved
  4. @License Dual MIT/GPLv2
  5. The contents of this file are subject to the MIT license as set out below.
  6. Permission is hereby granted, free of charge, to any person obtaining a copy
  7. of this software and associated documentation files (the "Software"), to deal
  8. in the Software without restriction, including without limitation the rights
  9. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10. copies of the Software, and to permit persons to whom the Software is
  11. furnished to do so, subject to the following conditions:
  12. The above copyright notice and this permission notice shall be included in
  13. all copies or substantial portions of the Software.
  14. Alternatively, the contents of this file may be used under the terms of
  15. the GNU General Public License Version 2 ("GPL") in which case the provisions
  16. of GPL are applicable instead of those above.
  17. If you wish to allow use of your version of this file only under the terms of
  18. GPL, and not to allow others to use your version of this file under the terms
  19. of the MIT license, indicate your decision by deleting the provisions above
  20. and replace them with the notice and other provisions required by GPL as set
  21. out in the file called "GPL-COPYING" included in this distribution. If you do
  22. not delete the provisions above, a recipient may use your version of this file
  23. under the terms of either the MIT license or GPL.
  24. This License is also included in this distribution in the file called
  25. "MIT-COPYING".
  26. EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS
  27. PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
  28. BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  29. PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR
  30. COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  31. IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  32. CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  33. */ /**************************************************************************/
  34. #ifndef LOG2_H
  35. #define LOG2_H
  36. #include "img_defs.h"
  37. /*************************************************************************/ /*!
  38. @Description Determine if a number is a power of two.
  39. @Input n
  40. @Return True if n is a power of 2, false otherwise. True if n == 0.
  41. */ /**************************************************************************/
  42. static INLINE IMG_BOOL __const_function IsPower2(uint32_t n)
  43. {
  44. /* C++ needs this cast. */
  45. return (IMG_BOOL)((n & (n - 1U)) == 0U);
  46. }
  47. /*************************************************************************/ /*!
  48. @Description Determine if a number is a power of two.
  49. @Input n
  50. @Return True if n is a power of 2, false otherwise. True if n == 0.
  51. */ /**************************************************************************/
  52. static INLINE IMG_BOOL __const_function IsPower2_64(uint64_t n)
  53. {
  54. /* C++ needs this cast. */
  55. return (IMG_BOOL)((n & (n - 1U)) == 0U);
  56. }
  57. /* Code using GNU GCC intrinsics */
  58. #if (defined(__GNUC__) || defined(__GNUG__)) && !(defined(__clang__) || defined(__INTEL_COMPILER))
  59. /* CHAR_BIT is typically found in <limits.h>. For all the platforms where
  60. * CHAR_BIT is not available, defined it here with the assumption that there
  61. * are 8 bits in a byte */
  62. #ifndef CHAR_BIT
  63. #define CHAR_BIT 8U
  64. #endif
  65. /*************************************************************************/ /*!
  66. @Description Compute floor(log2(n))
  67. @Input n
  68. @Return log2(n) rounded down to the nearest integer. Returns 0 if n == 0
  69. */ /**************************************************************************/
  70. static INLINE uint32_t __const_function FloorLog2(uint32_t n)
  71. {
  72. if (unlikely(n == 0U))
  73. {
  74. return 0;
  75. }
  76. else
  77. {
  78. uint32_t uNumBits = (uint32_t)CHAR_BIT * (uint32_t)sizeof(n);
  79. return uNumBits - (uint32_t)__builtin_clz(n) - 1U;
  80. }
  81. }
  82. /*************************************************************************/ /*!
  83. @Description Compute floor(log2(n))
  84. @Input n
  85. @Return log2(n) rounded down to the nearest integer. Returns 0 if n == 0
  86. */ /**************************************************************************/
  87. static INLINE uint32_t __const_function FloorLog2_64(uint64_t n)
  88. {
  89. if (unlikely(n == 0U))
  90. {
  91. return 0;
  92. }
  93. else
  94. {
  95. uint32_t uNumBits = (uint32_t)CHAR_BIT * (uint32_t)sizeof(n);
  96. return uNumBits - (uint32_t)__builtin_clzll(n) - 1U;
  97. }
  98. }
  99. /*************************************************************************/ /*!
  100. @Description Compute ceil(log2(n))
  101. @Input n
  102. @Return log2(n) rounded up to the nearest integer. Returns 0 if n == 0
  103. */ /**************************************************************************/
  104. static INLINE uint32_t __const_function CeilLog2(uint32_t n)
  105. {
  106. if (unlikely(n == 0U || n == 1U))
  107. {
  108. return 0;
  109. }
  110. else
  111. {
  112. uint32_t uNumBits = (uint32_t)CHAR_BIT * (uint32_t)sizeof(n);
  113. n--; /* Handle powers of 2 */
  114. return uNumBits - (uint32_t)__builtin_clz(n);
  115. }
  116. }
  117. /*************************************************************************/ /*!
  118. @Description Compute ceil(log2(n))
  119. @Input n
  120. @Return log2(n) rounded up to the nearest integer. Returns 0 if n == 0
  121. */ /**************************************************************************/
  122. static INLINE uint32_t __const_function CeilLog2_64(uint64_t n)
  123. {
  124. if (unlikely(n == 0U || n == 1U))
  125. {
  126. return 0;
  127. }
  128. else
  129. {
  130. uint32_t uNumBits = (uint32_t)CHAR_BIT * (uint32_t)sizeof(n);
  131. n--; /* Handle powers of 2 */
  132. return uNumBits - (uint32_t)__builtin_clzll(n);
  133. }
  134. }
  135. /*************************************************************************/ /*!
  136. @Description Compute log2(n) for exact powers of two only
  137. @Input n Must be a power of two
  138. @Return log2(n)
  139. */ /**************************************************************************/
  140. static INLINE uint32_t __const_function ExactLog2(uint32_t n)
  141. {
  142. return (uint32_t)CHAR_BIT * (uint32_t)sizeof(n) - (uint32_t)__builtin_clz(n) - 1U;
  143. }
  144. /*************************************************************************/ /*!
  145. @Description Compute log2(n) for exact powers of two only
  146. @Input n Must be a power of two
  147. @Return log2(n)
  148. */ /**************************************************************************/
  149. static INLINE uint32_t __const_function ExactLog2_64(uint64_t n)
  150. {
  151. return (uint32_t)CHAR_BIT * (uint32_t)sizeof(n) - (uint32_t)__builtin_clzll(n) - 1U;
  152. }
  153. /*************************************************************************/ /*!
  154. @Description Round a non-power-of-two number up to the next power of two.
  155. @Input n
  156. @Return n rounded up to the next power of two. If n is zero or
  157. already a power of two, return n unmodified.
  158. */ /**************************************************************************/
  159. static INLINE uint32_t __const_function RoundUpToNextPowerOfTwo(uint32_t n)
  160. {
  161. /* Cases with n greater than 2^31 needs separate handling
  162. * as result of (1<<32) is undefined. */
  163. if (unlikely( n == 0U || n > (uint32_t)1 << ((uint32_t)CHAR_BIT * sizeof(n) - 1U)))
  164. {
  165. return 0;
  166. }
  167. /* Return n if it is already a power of 2 */
  168. if ((IMG_BOOL)((n & (n - 1U)) == 0U))
  169. {
  170. return n;
  171. }
  172. return (uint32_t)1 << ((uint32_t)CHAR_BIT * sizeof(n) - (uint32_t)__builtin_clz(n));
  173. }
  174. /*************************************************************************/ /*!
  175. @Description Round a non-power-of-two number up to the next power of two.
  176. @Input n
  177. @Return n rounded up to the next power of two. If n is zero or
  178. already a power of two, return n unmodified.
  179. */ /**************************************************************************/
  180. static INLINE uint64_t __const_function RoundUpToNextPowerOfTwo_64(uint64_t n)
  181. {
  182. /* Cases with n greater than 2^63 needs separate handling
  183. * as result of (1<<64) is undefined. */
  184. if (unlikely( n == 0U || n > (uint64_t)1 << ((uint32_t)CHAR_BIT * sizeof(n) - 1U)))
  185. {
  186. return 0;
  187. }
  188. /* Return n if it is already a power of 2 */
  189. if ((IMG_BOOL)((n & (n - 1U)) == 0U))
  190. {
  191. return n;
  192. }
  193. return (uint64_t)1 << ((uint64_t)CHAR_BIT * sizeof(n) - (uint64_t)__builtin_clzll(n));
  194. }
  195. #else /* #if (defined(__GNUC__) || defined(__GNUG__)) && !(defined(__clang__) || defined(__INTEL_COMPILER)) */
  196. /*************************************************************************/ /*!
  197. @Description Round a non-power-of-two number up to the next power of two.
  198. @Input n
  199. @Return n rounded up to the next power of two. If n is zero or
  200. already a power of two, return n unmodified.
  201. */ /**************************************************************************/
  202. static INLINE uint32_t __const_function RoundUpToNextPowerOfTwo(uint32_t n)
  203. {
  204. n--;
  205. n |= n >> 1; /* handle 2 bit numbers */
  206. n |= n >> 2; /* handle 4 bit numbers */
  207. n |= n >> 4; /* handle 8 bit numbers */
  208. n |= n >> 8; /* handle 16 bit numbers */
  209. n |= n >> 16; /* handle 32 bit numbers */
  210. n++;
  211. return n;
  212. }
  213. /*************************************************************************/ /*!
  214. @Description Round a non-power-of-two number up to the next power of two.
  215. @Input n
  216. @Return n rounded up to the next power of two. If n is zero or
  217. already a power of two, return n unmodified.
  218. */ /**************************************************************************/
  219. static INLINE uint64_t __const_function RoundUpToNextPowerOfTwo_64(uint64_t n)
  220. {
  221. n--;
  222. n |= n >> 1; /* handle 2 bit numbers */
  223. n |= n >> 2; /* handle 4 bit numbers */
  224. n |= n >> 4; /* handle 8 bit numbers */
  225. n |= n >> 8; /* handle 16 bit numbers */
  226. n |= n >> 16; /* handle 32 bit numbers */
  227. n |= n >> 32; /* handle 64 bit numbers */
  228. n++;
  229. return n;
  230. }
  231. /*************************************************************************/ /*!
  232. @Description Compute floor(log2(n))
  233. @Input n
  234. @Return log2(n) rounded down to the nearest integer. Returns 0 if n == 0
  235. */ /**************************************************************************/
  236. static INLINE uint32_t __const_function FloorLog2(uint32_t n)
  237. {
  238. uint32_t ui32log2 = 0;
  239. while (n >>= 1)
  240. {
  241. ui32log2++;
  242. }
  243. return ui32log2;
  244. }
  245. /*************************************************************************/ /*!
  246. @Description Compute floor(log2(n))
  247. @Input n
  248. @Return log2(n) rounded down to the nearest integer. Returns 0 if n == 0
  249. */ /**************************************************************************/
  250. static INLINE uint32_t __const_function FloorLog2_64(uint64_t n)
  251. {
  252. uint32_t ui32log2 = 0;
  253. while (n >>= 1)
  254. {
  255. ui32log2++;
  256. }
  257. return ui32log2;
  258. }
  259. /*************************************************************************/ /*!
  260. @Description Compute ceil(log2(n))
  261. @Input n
  262. @Return log2(n) rounded up to the nearest integer. Returns 0 if n == 0
  263. */ /**************************************************************************/
  264. static INLINE uint32_t __const_function CeilLog2(uint32_t n)
  265. {
  266. uint32_t ui32log2 = 0;
  267. if (n == 0U)
  268. {
  269. return 0;
  270. }
  271. n--; /* Handle powers of 2 */
  272. while (n)
  273. {
  274. ui32log2++;
  275. n >>= 1;
  276. }
  277. return ui32log2;
  278. }
  279. /*************************************************************************/ /*!
  280. @Description Compute ceil(log2(n))
  281. @Input n
  282. @Return log2(n) rounded up to the nearest integer. Returns 0 if n == 0
  283. */ /**************************************************************************/
  284. static INLINE uint32_t __const_function CeilLog2_64(uint64_t n)
  285. {
  286. uint32_t ui32log2 = 0;
  287. if (n == 0U)
  288. {
  289. return 0;
  290. }
  291. n--; /* Handle powers of 2 */
  292. while (n)
  293. {
  294. ui32log2++;
  295. n >>= 1;
  296. }
  297. return ui32log2;
  298. }
  299. /*************************************************************************/ /*!
  300. @Description Compute log2(n) for exact powers of two only
  301. @Input n Must be a power of two
  302. @Return log2(n)
  303. */ /**************************************************************************/
  304. static INLINE uint32_t __const_function ExactLog2(uint32_t n)
  305. {
  306. static const uint32_t b[] =
  307. {0xAAAAAAAAU, 0xCCCCCCCCU, 0xF0F0F0F0U, 0xFF00FF00U, 0xFFFF0000U};
  308. uint32_t r = (n & b[0]) != 0U;
  309. r |= (uint32_t) ((n & b[4]) != 0U) << 4;
  310. r |= (uint32_t) ((n & b[3]) != 0U) << 3;
  311. r |= (uint32_t) ((n & b[2]) != 0U) << 2;
  312. r |= (uint32_t) ((n & b[1]) != 0U) << 1;
  313. return r;
  314. }
  315. /*************************************************************************/ /*!
  316. @Description Compute log2(n) for exact powers of two only
  317. @Input n Must be a power of two
  318. @Return log2(n)
  319. */ /**************************************************************************/
  320. static INLINE uint32_t __const_function ExactLog2_64(uint64_t n)
  321. {
  322. static const uint64_t b[] =
  323. {0xAAAAAAAAAAAAAAAAULL, 0xCCCCCCCCCCCCCCCCULL,
  324. 0xF0F0F0F0F0F0F0F0ULL, 0xFF00FF00FF00FF00ULL,
  325. 0xFFFF0000FFFF0000ULL, 0xFFFFFFFF00000000ULL};
  326. uint32_t r = (n & b[0]) != 0U;
  327. r |= (uint32_t) ((n & b[5]) != 0U) << 5;
  328. r |= (uint32_t) ((n & b[4]) != 0U) << 4;
  329. r |= (uint32_t) ((n & b[3]) != 0U) << 3;
  330. r |= (uint32_t) ((n & b[2]) != 0U) << 2;
  331. r |= (uint32_t) ((n & b[1]) != 0U) << 1;
  332. return r;
  333. }
  334. #endif /* #if (defined(__GNUC__) || defined(__GNUG__)) && !(defined(__clang__) || defined(__INTEL_COMPILER)) */
  335. /*************************************************************************/ /*!
  336. @Description Compute floor(log2(size)) , where size is the max of 3 sizes
  337. This is almost always the ONLY EVER valid use of FloorLog2.
  338. Usually CeilLog2() should be used instead.
  339. For a 5x5x1 texture, the 3 miplevels are:
  340. 0: 5x5x1
  341. 1: 2x2x1
  342. 2: 1x1x1
  343. For an 8x8x1 texture, the 4 miplevels are:
  344. 0: 8x8x1
  345. 1: 4x4x1
  346. 2: 2x2x1
  347. 3: 1x1x1
  348. @Input sizeX, sizeY, sizeZ
  349. @Return Count of mipmap levels for given dimensions
  350. */ /**************************************************************************/
  351. static INLINE uint32_t __const_function NumMipLevels(uint32_t sizeX, uint32_t sizeY, uint32_t sizeZ)
  352. {
  353. uint32_t maxSize = MAX(MAX(sizeX, sizeY), sizeZ);
  354. return FloorLog2(maxSize) + 1U;
  355. }
  356. #endif /* LOG2_H */