1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
#!/usr/bin/env python3
# Copyright 2020 The Pigweed Authors
#
# Licensed under the Apache License, Version 2.0 (the "License"); you may not
# use this file except in compliance with the License. You may obtain a copy of
# the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
# License for the specific language governing permissions and limitations under
# the License.
"""Generates a C macro for the PW tokenizer 65599 fixed length hash."""
import datetime
import os
HASH_CONSTANT = 65599
HASH_NAME = 'pw_tokenizer_65599_fixed_length'
HASH_LENGTHS = 80, 96, 128
FILE_HEADER = """\
// Copyright {year} The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
// AUTOGENERATED - DO NOT EDIT
//
// This file was generated by {script}.
// To make changes, update the script and run it to regenerate the files.
#pragma once
#include <stdint.h>
// {hash_length}-character version of the tokenizer hash function.
//
// The argument must be a string literal. It is concatenated with "" to ensure
// that this is the case.
//
// clang-format off
"""
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)
def _main():
base = os.path.abspath(
os.path.join(os.path.dirname(__file__), '..', 'public', 'pw_tokenizer',
'internal'))
# Generate macros for hashes of the specified lengths.
for hash_length in HASH_LENGTHS:
path = os.path.join(
base, '{}_{}_hash_macro.h'.format(HASH_NAME, hash_length))
with open(path, 'w') as header_file:
header_file.write(
generate_pw_tokenizer_65599_fixed_length_hash_macro(
hash_length))
print('Generated {}-character hash macro at {}'.format(
hash_length, path))
if __name__ == '__main__':
_main()
|
