linux-6.15/scripts/gen-crc-consts.py

21     return xor(a << i for i in range(b.bit_length()) if (b & (1 << i)) != 0)
27         q ^= 1 << (a.bit_length() - b.bit_length())
38     return xor(((poly >> i) & 1) << (num_bits - 1 - i) for i in range(num_bits))
57              if (poly & (1 << i)) != 0]
60         s = prefix + terms[j] + (' +' if j < len(terms) - 1 else '')
61         j += 1
63             s += ' ' + terms[j] + (' +' if j < len(terms) - 1 else '')
64             j += 1
73     pprint_poly(' * G(x) = ', variant.G)
85         self.G = generator_poly ^ (1 << bits)
88 # N=1 corresponds to the traditional byte-at-a-time table.
99             next_entry = fmt_poly(v, reduce(poly, v.G), v.bits) + ','
112     (G, n, lsb) = (v.G, v.bits, v.lsb)
114     pow_of_x = 3 * bits_per_long - (1 if lsb else 0)
116                       reduce(1 << pow_of_x, G), f'x^{pow_of_x} mod G')
117     pow_of_x = 2 * bits_per_long - (1 if lsb else 0)
119                       reduce(1 << pow_of_x, G), f'x^{pow_of_x} mod G')
121     pow_of_x = bits_per_long - 1 + n
123                       div(1 << pow_of_x, G), f'floor(x^{pow_of_x} / G)')
125     val = G - (1 << n)
126     desc = f'G - x^{n}'
165         (G, n, lsb) = (v.G, v.bits, v.lsb)
186             # HI64_TERMS that is basically x^(i+64) mod G and one for LO64_TERMS
187             # that is basically x^i mod G.  The exact values however undergo a
196                     # coefficients of x^1 through x^127, not x^0 through x^126.
203                     pow_of_x -= 1
208                 # congruence class mod G and the constant remains 64-bit, but
212                 mults.append({ 'val': reduce(1 << pow_of_x, G) << (64 - n),
213                                'desc': f'(x^{pow_of_x} mod G) * x^{64-n}' })
217         # Shuffle table for handling 1..15 bytes at end
219         print('\t\t' + (16*'-1, ').rstrip())
221         print('\t\t' + (16*'-1, ').rstrip())
228         val = div(1 << (63+n), G)
229         desc = f'floor(x^{63+n} / G)'
231             val = (val << 1) - (1 << 64)
235         val = G - (1 << n)
236         desc = f'G - x^{n}'
238             assert (val & 1) != 0  # The x^0 term should always be nonzero.
239             val >>= 1
242             pow_of_x = 64 - n - (1 if lsb else 0)
267     sys.stderr.write('  CONSTS_TYPE can be sliceby[1-8], riscv_clmul, or x86_pclmul\n')
269     sys.stderr.write('     E.g. crc16_msb_0x8bb7 or crc32_lsb_0xedb88320\n')
271     sys.exit(1)
277 print(f' *\t{sys.argv[0]} {" ".join(sys.argv[1:])}')
281 consts_types = sys.argv[1].split(',')