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 17import datetime 18import os 19 20HASH_CONSTANT = 65599 21HASH_NAME = 'pw_tokenizer_65599_fixed_length' 22HASH_LENGTHS = 80, 96, 128, 256 23 24FILE_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 57def 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 135def _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 154if __name__ == '__main__': 155 _main() 156