scripts/gen-crc-consts.py

Source file repositories/reference/linux-study-clean/scripts/gen-crc-consts.py

File Facts

System
Linux kernel
Corpus path
scripts/gen-crc-consts.py
Extension
.py
Size
11939 bytes
Lines
292
Domain
Support Tooling And Documentation
Bucket
scripts
Inferred role
Support Tooling And Documentation: scripts
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

#!/usr/bin/env python3
# SPDX-License-Identifier: GPL-2.0-or-later
#
# Script that generates constants for computing the given CRC variant(s).
#
# Copyright 2025 Google LLC
#
# Author: Eric Biggers <ebiggers@google.com>

import sys

# XOR (add) an iterable of polynomials.
def xor(iterable):
    res = 0
    for val in iterable:
        res ^= val
    return res

# Multiply two polynomials.
def clmul(a, b):
    return xor(a << i for i in range(b.bit_length()) if (b & (1 << i)) != 0)

# Polynomial division floor(a / b).
def div(a, b):
    q = 0
    while a.bit_length() >= b.bit_length():
        q ^= 1 << (a.bit_length() - b.bit_length())
        a ^= b << (a.bit_length() - b.bit_length())
    return q

# Reduce the polynomial 'a' modulo the polynomial 'b'.
def reduce(a, b):
    return a ^ clmul(div(a, b), b)

# Reflect the bits of a polynomial.
def bitreflect(poly, num_bits):
    assert poly.bit_length() <= num_bits
    return xor(((poly >> i) & 1) << (num_bits - 1 - i) for i in range(num_bits))

# Format a polynomial as hex.  Bit-reflect it if the CRC is lsb-first.
def fmt_poly(variant, poly, num_bits):
    if variant.lsb:
        poly = bitreflect(poly, num_bits)
    return f'0x{poly:0{2*num_bits//8}x}'

# Print a pair of 64-bit polynomial multipliers.  They are always passed in the
# order [HI64_TERMS, LO64_TERMS] but will be printed in the appropriate order.
def print_mult_pair(variant, mults):
    mults = list(mults if variant.lsb else reversed(mults))
    terms = ['HI64_TERMS', 'LO64_TERMS'] if variant.lsb else ['LO64_TERMS', 'HI64_TERMS']
    for i in range(2):
        print(f'\t\t{fmt_poly(variant, mults[i]["val"], 64)},\t/* {terms[i]}: {mults[i]["desc"]} */')

# Pretty-print a polynomial.
def pprint_poly(prefix, poly):
    terms = [f'x^{i}' for i in reversed(range(poly.bit_length()))
             if (poly & (1 << i)) != 0]
    j = 0
    while j < len(terms):
        s = prefix + terms[j] + (' +' if j < len(terms) - 1 else '')
        j += 1
        while j < len(terms) and len(s) < 73:
            s += ' ' + terms[j] + (' +' if j < len(terms) - 1 else '')
            j += 1
        print(s)
        prefix = ' * ' + (' ' * (len(prefix) - 3))

# Print a comment describing constants generated for the given CRC variant.
def print_header(variant, what):
    print('/*')

Annotation

Implementation Notes