1 // SPDX-License-Identifier: 0BSD 2 3 /////////////////////////////////////////////////////////////////////////////// 4 // 5 /// \file crc32.c 6 /// \brief CRC32 calculation 7 // 8 // Authors: Lasse Collin 9 // Ilya Kurdyukov 10 // Hans Jansen 11 // 12 /////////////////////////////////////////////////////////////////////////////// 13 14 #include "check.h" 15 #include "crc_common.h" 16 17 #if defined(CRC_X86_CLMUL) 18 # define BUILDING_CRC32_CLMUL 19 # include "crc_x86_clmul.h" 20 #elif defined(CRC32_ARM64) 21 # include "crc32_arm64.h" 22 #endif 23 24 25 #ifdef CRC32_GENERIC 26 27 /////////////////// 28 // Generic CRC32 // 29 /////////////////// 30 31 static uint32_t 32 crc32_generic(const uint8_t *buf, size_t size, uint32_t crc) 33 { 34 crc = ~crc; 35 36 #ifdef WORDS_BIGENDIAN 37 crc = bswap32(crc); 38 #endif 39 40 if (size > 8) { 41 // Fix the alignment, if needed. The if statement above 42 // ensures that this won't read past the end of buf[]. 43 while ((uintptr_t)(buf) & 7) { 44 crc = lzma_crc32_table[0][*buf++ ^ A(crc)] ^ S8(crc); 45 --size; 46 } 47 48 // Calculate the position where to stop. 49 const uint8_t *const limit = buf + (size & ~(size_t)(7)); 50 51 // Calculate how many bytes must be calculated separately 52 // before returning the result. 53 size &= (size_t)(7); 54 55 // Calculate the CRC32 using the slice-by-eight algorithm. 56 while (buf < limit) { 57 crc ^= aligned_read32ne(buf); 58 buf += 4; 59 60 crc = lzma_crc32_table[7][A(crc)] 61 ^ lzma_crc32_table[6][B(crc)] 62 ^ lzma_crc32_table[5][C(crc)] 63 ^ lzma_crc32_table[4][D(crc)]; 64 65 const uint32_t tmp = aligned_read32ne(buf); 66 buf += 4; 67 68 // At least with some compilers, it is critical for 69 // performance, that the crc variable is XORed 70 // between the two table-lookup pairs. 71 crc = lzma_crc32_table[3][A(tmp)] 72 ^ lzma_crc32_table[2][B(tmp)] 73 ^ crc 74 ^ lzma_crc32_table[1][C(tmp)] 75 ^ lzma_crc32_table[0][D(tmp)]; 76 } 77 } 78 79 while (size-- != 0) 80 crc = lzma_crc32_table[0][*buf++ ^ A(crc)] ^ S8(crc); 81 82 #ifdef WORDS_BIGENDIAN 83 crc = bswap32(crc); 84 #endif 85 86 return ~crc; 87 } 88 #endif 89 90 91 #if defined(CRC32_GENERIC) && defined(CRC32_ARCH_OPTIMIZED) 92 93 ////////////////////////// 94 // Function dispatching // 95 ////////////////////////// 96 97 // If both the generic and arch-optimized implementations are built, then 98 // the function to use is selected at runtime because the system running 99 // the binary might not have the arch-specific instruction set extension(s) 100 // available. The three dispatch methods in order of priority: 101 // 102 // 1. Indirect function (ifunc). This method is slightly more efficient 103 // than the constructor method because it will change the entry in the 104 // Procedure Linkage Table (PLT) for the function either at load time or 105 // at the first call. This avoids having to call the function through a 106 // function pointer and will treat the function call like a regular call 107 // through the PLT. ifuncs are created by using 108 // __attribute__((__ifunc__("resolver"))) on a function which has no 109 // body. The "resolver" is the name of the function that chooses at 110 // runtime which implementation to use. 111 // 112 // 2. Constructor. This method uses __attribute__((__constructor__)) to 113 // set crc32_func at load time. This avoids extra computation (and any 114 // unlikely threading bugs) on the first call to lzma_crc32() to decide 115 // which implementation should be used. 116 // 117 // 3. First Call Resolution. On the very first call to lzma_crc32(), the 118 // call will be directed to crc32_dispatch() instead. This will set the 119 // appropriate implementation function and will not be called again. 120 // This method does not use any kind of locking but is safe because if 121 // multiple threads run the dispatcher simultaneously then they will all 122 // set crc32_func to the same value. 123 124 typedef uint32_t (*crc32_func_type)( 125 const uint8_t *buf, size_t size, uint32_t crc); 126 127 // Clang 16.0.0 and older has a bug where it marks the ifunc resolver 128 // function as unused since it is static and never used outside of 129 // __attribute__((__ifunc__())). 130 #if defined(CRC_USE_IFUNC) && defined(__clang__) 131 # pragma GCC diagnostic push 132 # pragma GCC diagnostic ignored "-Wunused-function" 133 #endif 134 135 // This resolver is shared between all three dispatch methods. It serves as 136 // the ifunc resolver if ifunc is supported, otherwise it is called as a 137 // regular function by the constructor or first call resolution methods. 138 static crc32_func_type 139 crc32_resolve(void) 140 { 141 return is_arch_extension_supported() 142 ? &crc32_arch_optimized : &crc32_generic; 143 } 144 145 #if defined(CRC_USE_IFUNC) && defined(__clang__) 146 # pragma GCC diagnostic pop 147 #endif 148 149 #ifndef CRC_USE_IFUNC 150 151 #ifdef HAVE_FUNC_ATTRIBUTE_CONSTRUCTOR 152 // Constructor method. 153 # define CRC32_SET_FUNC_ATTR __attribute__((__constructor__)) 154 static crc32_func_type crc32_func; 155 #else 156 // First Call Resolution method. 157 # define CRC32_SET_FUNC_ATTR 158 static uint32_t crc32_dispatch(const uint8_t *buf, size_t size, uint32_t crc); 159 static crc32_func_type crc32_func = &crc32_dispatch; 160 #endif 161 162 CRC32_SET_FUNC_ATTR 163 static void 164 crc32_set_func(void) 165 { 166 crc32_func = crc32_resolve(); 167 return; 168 } 169 170 #ifndef HAVE_FUNC_ATTRIBUTE_CONSTRUCTOR 171 static uint32_t 172 crc32_dispatch(const uint8_t *buf, size_t size, uint32_t crc) 173 { 174 // When __attribute__((__ifunc__(...))) and 175 // __attribute__((__constructor__)) isn't supported, set the 176 // function pointer without any locking. If multiple threads run 177 // the detection code in parallel, they will all end up setting 178 // the pointer to the same value. This avoids the use of 179 // mythread_once() on every call to lzma_crc32() but this likely 180 // isn't strictly standards compliant. Let's change it if it breaks. 181 crc32_set_func(); 182 return crc32_func(buf, size, crc); 183 } 184 185 #endif 186 #endif 187 #endif 188 189 190 #ifdef CRC_USE_IFUNC 191 extern LZMA_API(uint32_t) 192 lzma_crc32(const uint8_t *buf, size_t size, uint32_t crc) 193 __attribute__((__ifunc__("crc32_resolve"))); 194 #else 195 extern LZMA_API(uint32_t) 196 lzma_crc32(const uint8_t *buf, size_t size, uint32_t crc) 197 { 198 #if defined(CRC32_GENERIC) && defined(CRC32_ARCH_OPTIMIZED) 199 // On x86-64, if CLMUL is available, it is the best for non-tiny 200 // inputs, being over twice as fast as the generic slice-by-four 201 // version. However, for size <= 16 it's different. In the extreme 202 // case of size == 1 the generic version can be five times faster. 203 // At size >= 8 the CLMUL starts to become reasonable. It 204 // varies depending on the alignment of buf too. 205 // 206 // The above doesn't include the overhead of mythread_once(). 207 // At least on x86-64 GNU/Linux, pthread_once() is very fast but 208 // it still makes lzma_crc32(buf, 1, crc) 50-100 % slower. When 209 // size reaches 12-16 bytes the overhead becomes negligible. 210 // 211 // So using the generic version for size <= 16 may give better 212 // performance with tiny inputs but if such inputs happen rarely 213 // it's not so obvious because then the lookup table of the 214 // generic version may not be in the processor cache. 215 #ifdef CRC_USE_GENERIC_FOR_SMALL_INPUTS 216 if (size <= 16) 217 return crc32_generic(buf, size, crc); 218 #endif 219 220 /* 221 #ifndef HAVE_FUNC_ATTRIBUTE_CONSTRUCTOR 222 // See crc32_dispatch(). This would be the alternative which uses 223 // locking and doesn't use crc32_dispatch(). Note that on Windows 224 // this method needs Vista threads. 225 mythread_once(crc64_set_func); 226 #endif 227 */ 228 return crc32_func(buf, size, crc); 229 230 #elif defined(CRC32_ARCH_OPTIMIZED) 231 return crc32_arch_optimized(buf, size, crc); 232 233 #else 234 return crc32_generic(buf, size, crc); 235 #endif 236 } 237 #endif 238