basisu.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468
  1. // basisu.h
  2. // Copyright (C) 2019-2021 Binomial LLC. All Rights Reserved.
  3. // Important: If compiling with gcc, be sure strict aliasing is disabled: -fno-strict-aliasing
  4. //
  5. // Licensed under the Apache License, Version 2.0 (the "License");
  6. // you may not use this file except in compliance with the License.
  7. // You may obtain a copy of the License at
  8. //
  9. // http://www.apache.org/licenses/LICENSE-2.0
  10. //
  11. // Unless required by applicable law or agreed to in writing, software
  12. // distributed under the License is distributed on an "AS IS" BASIS,
  13. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14. // See the License for the specific language governing permissions and
  15. // limitations under the License.
  16. #pragma once
  17. #ifdef _MSC_VER
  18. #pragma warning (disable : 4201)
  19. #pragma warning (disable : 4127) // warning C4127: conditional expression is constant
  20. #pragma warning (disable : 4530) // C++ exception handler used, but unwind semantics are not enabled.
  21. #ifndef BASISU_NO_ITERATOR_DEBUG_LEVEL
  22. //#define _HAS_ITERATOR_DEBUGGING 0
  23. #if defined(_DEBUG) || defined(DEBUG)
  24. // This is madness, but we need to disable iterator debugging in debug builds or the encoder is unsable because MSVC's iterator debugging implementation is totally broken.
  25. #ifndef _ITERATOR_DEBUG_LEVEL
  26. #define _ITERATOR_DEBUG_LEVEL 1
  27. #endif
  28. #ifndef _SECURE_SCL
  29. #define _SECURE_SCL 1
  30. #endif
  31. #else // defined(_DEBUG) || defined(DEBUG)
  32. #ifndef _SECURE_SCL
  33. #define _SECURE_SCL 0
  34. #endif
  35. #ifndef _ITERATOR_DEBUG_LEVEL
  36. #define _ITERATOR_DEBUG_LEVEL 0
  37. #endif
  38. #endif // defined(_DEBUG) || defined(DEBUG)
  39. #endif // BASISU_NO_ITERATOR_DEBUG_LEVEL
  40. #endif // _MSC_VER
  41. #include <stdlib.h>
  42. #include <stdio.h>
  43. #include <math.h>
  44. #include <stdarg.h>
  45. #include <string.h>
  46. #include <memory.h>
  47. #include <limits.h>
  48. #include <stdint.h>
  49. #include <algorithm>
  50. #include <limits>
  51. #include <functional>
  52. #include <iterator>
  53. #include <type_traits>
  54. #include <assert.h>
  55. #include <random>
  56. #include "basisu_containers.h"
  57. #ifdef max
  58. #undef max
  59. #endif
  60. #ifdef min
  61. #undef min
  62. #endif
  63. #ifdef _WIN32
  64. #define strcasecmp _stricmp
  65. #endif
  66. // Set to one to enable debug printf()'s when any errors occur, for development/debugging. Especially useful for WebGL development.
  67. #ifndef BASISU_FORCE_DEVEL_MESSAGES
  68. #define BASISU_FORCE_DEVEL_MESSAGES 0
  69. #endif
  70. #define BASISU_NOTE_UNUSED(x) (void)(x)
  71. #define BASISU_ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))
  72. #define BASISU_NO_EQUALS_OR_COPY_CONSTRUCT(x) x(const x &) = delete; x& operator= (const x &) = delete;
  73. #define BASISU_ASSUME(x) static_assert(x, #x);
  74. #define BASISU_OFFSETOF(s, m) offsetof(s, m)
  75. #define BASISU_STRINGIZE(x) #x
  76. #define BASISU_STRINGIZE2(x) BASISU_STRINGIZE(x)
  77. #if BASISU_FORCE_DEVEL_MESSAGES
  78. #define BASISU_DEVEL_ERROR(...) do { basisu::debug_printf(__VA_ARGS__); } while(0)
  79. #else
  80. #define BASISU_DEVEL_ERROR(...)
  81. #endif
  82. namespace basisu
  83. {
  84. // Types/utilities
  85. #ifdef _WIN32
  86. const char BASISU_PATH_SEPERATOR_CHAR = '\\';
  87. #else
  88. const char BASISU_PATH_SEPERATOR_CHAR = '/';
  89. #endif
  90. typedef basisu::vector<uint8_t> uint8_vec;
  91. typedef basisu::vector<int16_t> int16_vec;
  92. typedef basisu::vector<uint16_t> uint16_vec;
  93. typedef basisu::vector<uint32_t> uint_vec;
  94. typedef basisu::vector<uint64_t> uint64_vec;
  95. typedef basisu::vector<int> int_vec;
  96. typedef basisu::vector<bool> bool_vec;
  97. void enable_debug_printf(bool enabled);
  98. void debug_printf(const char *pFmt, ...);
  99. template <typename T> inline void clear_obj(T& obj) { memset(&obj, 0, sizeof(obj)); }
  100. template <typename T0, typename T1> inline T0 lerp(T0 a, T0 b, T1 c) { return a + (b - a) * c; }
  101. template <typename S> inline S maximum(S a, S b) { return (a > b) ? a : b; }
  102. template <typename S> inline S maximum(S a, S b, S c) { return maximum(maximum(a, b), c); }
  103. template <typename S> inline S maximum(S a, S b, S c, S d) { return maximum(maximum(maximum(a, b), c), d); }
  104. template <typename S> inline S minimum(S a, S b) { return (a < b) ? a : b; }
  105. template <typename S> inline S minimum(S a, S b, S c) { return minimum(minimum(a, b), c); }
  106. template <typename S> inline S minimum(S a, S b, S c, S d) { return minimum(minimum(minimum(a, b), c), d); }
  107. inline float clampf(float value, float low, float high) { if (value < low) value = low; else if (value > high) value = high; return value; }
  108. inline float saturate(float value) { return clampf(value, 0, 1.0f); }
  109. inline uint8_t minimumub(uint8_t a, uint8_t b) { return (a < b) ? a : b; }
  110. inline uint32_t minimumu(uint32_t a, uint32_t b) { return (a < b) ? a : b; }
  111. inline int32_t minimumi(int32_t a, int32_t b) { return (a < b) ? a : b; }
  112. inline float minimumf(float a, float b) { return (a < b) ? a : b; }
  113. inline uint8_t maximumub(uint8_t a, uint8_t b) { return (a > b) ? a : b; }
  114. inline uint32_t maximumu(uint32_t a, uint32_t b) { return (a > b) ? a : b; }
  115. inline int32_t maximumi(int32_t a, int32_t b) { return (a > b) ? a : b; }
  116. inline float maximumf(float a, float b) { return (a > b) ? a : b; }
  117. inline int squarei(int i) { return i * i; }
  118. inline float squaref(float i) { return i * i; }
  119. template<typename T> inline T square(T a) { return a * a; }
  120. template <typename S> inline S clamp(S value, S low, S high) { return (value < low) ? low : ((value > high) ? high : value); }
  121. inline uint32_t iabs(int32_t i) { return (i < 0) ? static_cast<uint32_t>(-i) : static_cast<uint32_t>(i); }
  122. inline uint64_t iabs64(int64_t i) { return (i < 0) ? static_cast<uint64_t>(-i) : static_cast<uint64_t>(i); }
  123. template<typename T> inline void clear_vector(T &vec) { vec.erase(vec.begin(), vec.end()); }
  124. template<typename T> inline typename T::value_type *enlarge_vector(T &vec, size_t n) { size_t cs = vec.size(); vec.resize(cs + n); return &vec[cs]; }
  125. inline bool is_pow2(uint32_t x) { return x && ((x & (x - 1U)) == 0U); }
  126. inline bool is_pow2(uint64_t x) { return x && ((x & (x - 1U)) == 0U); }
  127. template<typename T> inline T open_range_check(T v, T minv, T maxv) { assert(v >= minv && v < maxv); BASISU_NOTE_UNUSED(minv); BASISU_NOTE_UNUSED(maxv); return v; }
  128. template<typename T> inline T open_range_check(T v, T maxv) { assert(v < maxv); BASISU_NOTE_UNUSED(maxv); return v; }
  129. inline uint32_t total_bits(uint32_t v) { uint32_t l = 0; for ( ; v > 0U; ++l) v >>= 1; return l; }
  130. template<typename T> inline T saturate(T val) { return clamp(val, 0.0f, 1.0f); }
  131. template<typename T, typename R> inline void append_vector(T &vec, const R *pObjs, size_t n)
  132. {
  133. if (n)
  134. {
  135. const size_t cur_s = vec.size();
  136. vec.resize(cur_s + n);
  137. memcpy(&vec[cur_s], pObjs, sizeof(R) * n);
  138. }
  139. }
  140. template<typename T> inline void append_vector(T &vec, const T &other_vec)
  141. {
  142. if (other_vec.size())
  143. append_vector(vec, &other_vec[0], other_vec.size());
  144. }
  145. template<typename T> inline void vector_ensure_element_is_valid(T &vec, size_t idx)
  146. {
  147. if (idx >= vec.size())
  148. vec.resize(idx + 1);
  149. }
  150. template<typename T> inline void vector_sort(T &vec)
  151. {
  152. if (vec.size())
  153. std::sort(vec.begin(), vec.end());
  154. }
  155. template<typename T, typename U> inline bool unordered_set_contains(T& set, const U&obj)
  156. {
  157. return set.find(obj) != set.end();
  158. }
  159. template<typename T> int vector_find(const T &vec, const typename T::value_type &obj)
  160. {
  161. assert(vec.size() <= INT_MAX);
  162. for (size_t i = 0; i < vec.size(); i++)
  163. if (vec[i] == obj)
  164. return static_cast<int>(i);
  165. return -1;
  166. }
  167. template<typename T> void vector_set_all(T &vec, const typename T::value_type &obj)
  168. {
  169. for (size_t i = 0; i < vec.size(); i++)
  170. vec[i] = obj;
  171. }
  172. inline uint64_t read_be64(const void *p)
  173. {
  174. uint64_t val = 0;
  175. for (uint32_t i = 0; i < 8; i++)
  176. val |= (static_cast<uint64_t>(static_cast<const uint8_t *>(p)[7 - i]) << (i * 8));
  177. return val;
  178. }
  179. inline void write_be64(void *p, uint64_t x)
  180. {
  181. for (uint32_t i = 0; i < 8; i++)
  182. static_cast<uint8_t *>(p)[7 - i] = static_cast<uint8_t>(x >> (i * 8));
  183. }
  184. static inline uint16_t byteswap16(uint16_t x) { return static_cast<uint16_t>((x << 8) | (x >> 8)); }
  185. static inline uint32_t byteswap32(uint32_t x) { return ((x << 24) | ((x << 8) & 0x00FF0000) | ((x >> 8) & 0x0000FF00) | (x >> 24)); }
  186. inline uint32_t floor_log2i(uint32_t v)
  187. {
  188. uint32_t b = 0;
  189. for (; v > 1U; ++b)
  190. v >>= 1;
  191. return b;
  192. }
  193. inline uint32_t ceil_log2i(uint32_t v)
  194. {
  195. uint32_t b = floor_log2i(v);
  196. if ((b != 32) && (v > (1U << b)))
  197. ++b;
  198. return b;
  199. }
  200. inline int posmod(int x, int y)
  201. {
  202. if (x >= 0)
  203. return (x < y) ? x : (x % y);
  204. int m = (-x) % y;
  205. return (m != 0) ? (y - m) : m;
  206. }
  207. inline bool do_excl_ranges_overlap(int la, int ha, int lb, int hb)
  208. {
  209. assert(la < ha && lb < hb);
  210. if ((ha <= lb) || (la >= hb)) return false;
  211. return true;
  212. }
  213. static inline uint32_t read_le_dword(const uint8_t *pBytes)
  214. {
  215. return (pBytes[3] << 24U) | (pBytes[2] << 16U) | (pBytes[1] << 8U) | (pBytes[0]);
  216. }
  217. static inline void write_le_dword(uint8_t* pBytes, uint32_t val)
  218. {
  219. pBytes[0] = (uint8_t)val;
  220. pBytes[1] = (uint8_t)(val >> 8U);
  221. pBytes[2] = (uint8_t)(val >> 16U);
  222. pBytes[3] = (uint8_t)(val >> 24U);
  223. }
  224. // Always little endian 1-8 byte unsigned int
  225. template<uint32_t NumBytes>
  226. struct packed_uint
  227. {
  228. uint8_t m_bytes[NumBytes];
  229. inline packed_uint() { static_assert(NumBytes <= sizeof(uint64_t), "Invalid NumBytes"); }
  230. inline packed_uint(uint64_t v) { *this = v; }
  231. inline packed_uint(const packed_uint& other) { *this = other; }
  232. inline packed_uint& operator= (uint64_t v)
  233. {
  234. for (uint32_t i = 0; i < NumBytes; i++)
  235. m_bytes[i] = static_cast<uint8_t>(v >> (i * 8));
  236. return *this;
  237. }
  238. inline packed_uint& operator= (const packed_uint& rhs)
  239. {
  240. memcpy(m_bytes, rhs.m_bytes, sizeof(m_bytes));
  241. return *this;
  242. }
  243. inline operator uint32_t() const
  244. {
  245. switch (NumBytes)
  246. {
  247. case 1:
  248. {
  249. return m_bytes[0];
  250. }
  251. case 2:
  252. {
  253. return (m_bytes[1] << 8U) | m_bytes[0];
  254. }
  255. case 3:
  256. {
  257. return (m_bytes[2] << 16U) | (m_bytes[1] << 8U) | m_bytes[0];
  258. }
  259. case 4:
  260. {
  261. return read_le_dword(m_bytes);
  262. }
  263. case 5:
  264. {
  265. uint32_t l = read_le_dword(m_bytes);
  266. uint32_t h = m_bytes[4];
  267. return static_cast<uint64_t>(l) | (static_cast<uint64_t>(h) << 32U);
  268. }
  269. case 6:
  270. {
  271. uint32_t l = read_le_dword(m_bytes);
  272. uint32_t h = (m_bytes[5] << 8U) | m_bytes[4];
  273. return static_cast<uint64_t>(l) | (static_cast<uint64_t>(h) << 32U);
  274. }
  275. case 7:
  276. {
  277. uint32_t l = read_le_dword(m_bytes);
  278. uint32_t h = (m_bytes[6] << 16U) | (m_bytes[5] << 8U) | m_bytes[4];
  279. return static_cast<uint64_t>(l) | (static_cast<uint64_t>(h) << 32U);
  280. }
  281. case 8:
  282. {
  283. uint32_t l = read_le_dword(m_bytes);
  284. uint32_t h = read_le_dword(m_bytes + 4);
  285. return static_cast<uint64_t>(l) | (static_cast<uint64_t>(h) << 32U);
  286. }
  287. default:
  288. {
  289. assert(0);
  290. return 0;
  291. }
  292. }
  293. }
  294. };
  295. enum eZero { cZero };
  296. enum eNoClamp { cNoClamp };
  297. // Rice/Huffman entropy coding
  298. // This is basically Deflate-style canonical Huffman, except we allow for a lot more symbols.
  299. enum
  300. {
  301. cHuffmanMaxSupportedCodeSize = 16, cHuffmanMaxSupportedInternalCodeSize = 31,
  302. cHuffmanFastLookupBits = 10,
  303. cHuffmanMaxSymsLog2 = 14, cHuffmanMaxSyms = 1 << cHuffmanMaxSymsLog2,
  304. // Small zero runs
  305. cHuffmanSmallZeroRunSizeMin = 3, cHuffmanSmallZeroRunSizeMax = 10, cHuffmanSmallZeroRunExtraBits = 3,
  306. // Big zero run
  307. cHuffmanBigZeroRunSizeMin = 11, cHuffmanBigZeroRunSizeMax = 138, cHuffmanBigZeroRunExtraBits = 7,
  308. // Small non-zero run
  309. cHuffmanSmallRepeatSizeMin = 3, cHuffmanSmallRepeatSizeMax = 6, cHuffmanSmallRepeatExtraBits = 2,
  310. // Big non-zero run
  311. cHuffmanBigRepeatSizeMin = 7, cHuffmanBigRepeatSizeMax = 134, cHuffmanBigRepeatExtraBits = 7,
  312. cHuffmanTotalCodelengthCodes = 21, cHuffmanSmallZeroRunCode = 17, cHuffmanBigZeroRunCode = 18, cHuffmanSmallRepeatCode = 19, cHuffmanBigRepeatCode = 20
  313. };
  314. static const uint8_t g_huffman_sorted_codelength_codes[] = { cHuffmanSmallZeroRunCode, cHuffmanBigZeroRunCode, cHuffmanSmallRepeatCode, cHuffmanBigRepeatCode, 0, 8, 7, 9, 6, 0xA, 5, 0xB, 4, 0xC, 3, 0xD, 2, 0xE, 1, 0xF, 0x10 };
  315. const uint32_t cHuffmanTotalSortedCodelengthCodes = sizeof(g_huffman_sorted_codelength_codes) / sizeof(g_huffman_sorted_codelength_codes[0]);
  316. // GPU texture formats
  317. enum class texture_format
  318. {
  319. cInvalidTextureFormat = -1,
  320. // Block-based formats
  321. cETC1, // ETC1
  322. cETC1S, // ETC1 (subset: diff colors only, no subblocks)
  323. cETC2_RGB, // ETC2 color block (basisu doesn't support ETC2 planar/T/H modes - just basic ETC1)
  324. cETC2_RGBA, // ETC2 EAC alpha block followed by ETC2 color block
  325. cETC2_ALPHA, // ETC2 EAC alpha block
  326. cBC1, // DXT1
  327. cBC3, // DXT5 (BC4/DXT5A block followed by a BC1/DXT1 block)
  328. cBC4, // DXT5A
  329. cBC5, // 3DC/DXN (two BC4/DXT5A blocks)
  330. cBC7,
  331. cASTC4x4, // LDR only
  332. cPVRTC1_4_RGB,
  333. cPVRTC1_4_RGBA,
  334. cATC_RGB,
  335. cATC_RGBA_INTERPOLATED_ALPHA,
  336. cFXT1_RGB,
  337. cPVRTC2_4_RGBA,
  338. cETC2_R11_EAC,
  339. cETC2_RG11_EAC,
  340. cUASTC4x4,
  341. cBC1_NV,
  342. cBC1_AMD,
  343. // Uncompressed/raw pixels
  344. cRGBA32,
  345. cRGB565,
  346. cBGR565,
  347. cRGBA4444,
  348. cABGR4444
  349. };
  350. inline uint32_t get_bytes_per_block(texture_format fmt)
  351. {
  352. switch (fmt)
  353. {
  354. case texture_format::cETC1:
  355. case texture_format::cETC1S:
  356. case texture_format::cETC2_RGB:
  357. case texture_format::cETC2_ALPHA:
  358. case texture_format::cBC1:
  359. case texture_format::cBC1_NV:
  360. case texture_format::cBC1_AMD:
  361. case texture_format::cBC4:
  362. case texture_format::cPVRTC1_4_RGB:
  363. case texture_format::cPVRTC1_4_RGBA:
  364. case texture_format::cATC_RGB:
  365. case texture_format::cPVRTC2_4_RGBA:
  366. case texture_format::cETC2_R11_EAC:
  367. return 8;
  368. case texture_format::cRGBA32:
  369. return sizeof(uint32_t) * 16;
  370. default:
  371. break;
  372. }
  373. return 16;
  374. }
  375. inline uint32_t get_qwords_per_block(texture_format fmt)
  376. {
  377. return get_bytes_per_block(fmt) >> 3;
  378. }
  379. inline uint32_t get_block_width(texture_format fmt)
  380. {
  381. BASISU_NOTE_UNUSED(fmt);
  382. switch (fmt)
  383. {
  384. case texture_format::cFXT1_RGB:
  385. return 8;
  386. default:
  387. break;
  388. }
  389. return 4;
  390. }
  391. inline uint32_t get_block_height(texture_format fmt)
  392. {
  393. BASISU_NOTE_UNUSED(fmt);
  394. return 4;
  395. }
  396. } // namespace basisu