third_party/pigweed/repo/pw_tokenizer/py/generate_hash_macro.py

   1 #!/usr/bin/env python3
   2 # Copyright 2020 The Pigweed Authors
   3 #
   4 # Licensed under the Apache License, Version 2.0 (the "License"); you may not
   5 # use this file except in compliance with the License. You may obtain a copy of
   6 # the License at
   7 #
   8 #     https://www.apache.org/licenses/LICENSE-2.0
   9 #
  10 # Unless required by applicable law or agreed to in writing, software
  11 # distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  12 # WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  13 # License for the specific language governing permissions and limitations under
  14 # the License.
  15 """Generates a C macro for the PW tokenizer 65599 fixed length hash."""
  16
  17 import datetime
  18 import os
  19
  20 HASH_CONSTANT = 65599
  21 HASH_NAME = 'pw_tokenizer_65599_fixed_length'
  22 HASH_LENGTHS = 80, 96, 128
  23
  24 FILE_HEADER = """\
  25 // Copyright {year} The Pigweed Authors
  26 //
  27 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
  28 // use this file except in compliance with the License. You may obtain a copy of
  29 // the License at
  30 //
  31 //     https://www.apache.org/licenses/LICENSE-2.0
  32 //
  33 // Unless required by applicable law or agreed to in writing, software
  34 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  35 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  36 // License for the specific language governing permissions and limitations under
  37 // the License.
  38
  39 // AUTOGENERATED - DO NOT EDIT
  40 //
  41 // This file was generated by {script}.
  42 // To make changes, update the script and run it to regenerate the files.
  43 #pragma once
  44
  45 #include <stdint.h>
  46
  47 // {hash_length}-character version of the tokenizer hash function.
  48 //
  49 // The argument must be a string literal. It is concatenated with "" to ensure
  50 // that this is the case.
  51 //
  52 // clang-format off
  53
  54 """
  55
  56
  57 def generate_pw_tokenizer_65599_fixed_length_hash_macro(hash_length):
  58     """Generate macro that hashes a string literal using a modified x65599 hash.
  59
  60     The macros generated by this function only operate on string literals.
  61
  62     Since macros can only operate on fixed-length strings, the hash macro only
  63     hashes up to a fixed length, and characters beyond that length are ignored.
  64     To eliminate some collisions, the length of the string is hashed as if it
  65     were the first character.
  66
  67     This hash is calculated with the following equation, where s is the string
  68     and k is the maximum hash length:
  69
  70        H(s, k) = len(s) + 65599 * s[0] + 65599^2 * s[1] + ... + 65599^k * s[k-1]
  71
  72     The hash algorithm is a modified version of the x65599 hash used by the SDBM
  73     open source project. This hash has the following differences from x65599:
  74       - Characters are only hashed up to a fixed maximum string length.
  75       - Characters are hashed in reverse order.
  76       - The string length is hashed as the first character in the string.
  77
  78     The code generated by this function is intentionally sparse. Each character
  79     appears hash_length times per log message, so using fewer characters results
  80     in faster compilation times.
  81
  82     Args:
  83       hash_length: maximum string size to hash; extra characters are ignored
  84
  85     Returns:
  86       the macro header file as a string
  87   """
  88
  89     first_hash_term = ('(uint32_t)(sizeof(str "") - 1 + '
  90                        '/* The argument must be a string literal. */ \\\n')
  91
  92     # Use this to add the aligned backslash at the end of the macro lines.
  93     line_format = '{{:<{}}}\\\n'.format(len(first_hash_term))
  94
  95     lines = [
  96         FILE_HEADER.format(script=os.path.basename(__file__),
  97                            hash_length=hash_length,
  98                            year=datetime.date.today().year)
  99     ]
 100
 101     lines.append(
 102         line_format.format('#define {}_{}_HASH(str)'.format(
 103             HASH_NAME.upper(), hash_length)))
 104     lines.append('  ' + first_hash_term)  # add indendation and the macro line
 105
 106     indent = ' ' * len('  (uint32_t)(')
 107     coefficient_format = '0x{coefficient:0>8x}u'
 108
 109     # The string will have at least a null terminator
 110     lines.append(
 111         line_format.format('{}0x{:0>8x}u * (uint8_t)str[0] +'.format(
 112             indent, HASH_CONSTANT)))
 113
 114     # Format string to use for the remaining terms.
 115     term_format = (
 116         '{indent}{coefficient} * '
 117         '(uint8_t)({index} < sizeof(str) ? str[{index}] : 0) +').format(
 118             indent=indent,
 119             coefficient=coefficient_format,
 120             index='{{index:>{}}}'.format(len(str(hash_length - 1))))
 121
 122     for i in range(1, hash_length):
 123         coefficient = HASH_CONSTANT**(i + 1) % 2**32
 124         term = term_format.format(index=i, coefficient=coefficient)
 125         lines.append(line_format.format(term))
 126
 127     # Remove the extra + and \ and add the closing )
 128     lines[-1] = lines[-1].rstrip(' +\\\n') + ')'
 129
 130     lines.append('\n\n// clang-format on\n')
 131
 132     return ''.join(lines)
 133
 134
 135 def _main():
 136     base = os.path.abspath(
 137         os.path.join(os.path.dirname(__file__), '..', 'public', 'pw_tokenizer',
 138                      'internal'))
 139
 140     # Generate macros for hashes of the specified lengths.
 141     for hash_length in HASH_LENGTHS:
 142         path = os.path.join(
 143             base, '{}_{}_hash_macro.h'.format(HASH_NAME, hash_length))
 144
 145         with open(path, 'w') as header_file:
 146             header_file.write(
 147                 generate_pw_tokenizer_65599_fixed_length_hash_macro(
 148                     hash_length))
 149
 150         print('Generated {}-character hash macro at {}'.format(
 151             hash_length, path))
 152
 153
 154 if __name__ == '__main__':
 155     _main()