PrivacyScanData/Target/Hash/generate_hash_macro_1.py

def generate_pw_tokenizer_65599_fixed_length_hash_macro(hash_length):
    """Generate macro that hashes a string literal using a modified x65599 hash.

    The macros generated by this function only operate on string literals.

    Since macros can only operate on fixed-length strings, the hash macro only
    hashes up to a fixed length, and characters beyond that length are ignored.
    To eliminate some collisions, the length of the string is hashed as if it
    were the first character.

    This hash is calculated with the following equation, where s is the string
    and k is the maximum hash length:

       H(s, k) = len(s) + 65599 * s[0] + 65599^2 * s[1] + ... + 65599^k * s[k-1]

    The hash algorithm is a modified version of the x65599 hash used by the SDBM
    open source project. This hash has the following differences from x65599:
      - Characters are only hashed up to a fixed maximum string length.
      - Characters are hashed in reverse order.
      - The string length is hashed as the first character in the string.

    The code generated by this function is intentionally sparse. Each character
    appears hash_length times per log message, so using fewer characters results
    in faster compilation times.

    Args:
      hash_length: maximum string size to hash; extra characters are ignored

    Returns:
      the macro header file as a string
  """

    first_hash_term = ('(uint32_t)(sizeof(str "") - 1 + '
                       '/* The argument must be a string literal. */ \\\n')

    # Use this to add the aligned backslash at the end of the macro lines.
    line_format = '{{:<{}}}\\\n'.format(len(first_hash_term))

    lines = [
        FILE_HEADER.format(script=os.path.basename(__file__),
                           hash_length=hash_length,
                           year=datetime.date.today().year)
    ]

    lines.append(
        line_format.format('#define {}_{}_HASH(str)'.format(
            HASH_NAME.upper(), hash_length)))
    lines.append('  ' + first_hash_term)  # add indendation and the macro line

    indent = ' ' * len('  (uint32_t)(')
    coefficient_format = '0x{coefficient:0>8x}u'

    # The string will have at least a null terminator
    lines.append(
        line_format.format('{}0x{:0>8x}u * (uint8_t)str[0] +'.format(
            indent, HASH_CONSTANT)))

    # Format string to use for the remaining terms.
    term_format = (
        '{indent}{coefficient} * '
        '(uint8_t)({index} < sizeof(str) ? str[{index}] : 0) +').format(
            indent=indent,
            coefficient=coefficient_format,
            index='{{index:>{}}}'.format(len(str(hash_length - 1))))

    for i in range(1, hash_length):
        coefficient = HASH_CONSTANT**(i + 1) % 2**32
        term = term_format.format(index=i, coefficient=coefficient)
        lines.append(line_format.format(term))

    # Remove the extra + and \ and add the closing )
    lines[-1] = lines[-1].rstrip(' +\\\n') + ')'

    lines.append('\n\n// clang-format on\n')

    return ''.join(lines)