rust_lcm_codegen/
fingerprint.rs

1//! Utilities related to LCM fingerprinting
2#![allow(dead_code)]
3#![allow(unused_variables)]
4#![allow(unused_imports)]
5
6use crate::parser::{self, Schema};
7use crate::Environment;
8
9// Hashing operations
10
11const INITIAL_STRUCT_HASH: i64 = 0x12_345_678i64;
12
13fn hash_update(v: i64, c: i8) -> i64 {
14    ((v << 8) ^ (v >> 55)).wrapping_add(c as i64)
15}
16
17fn hash_string_update(mut v: i64, s: &str) -> i64 {
18    v = hash_update(v, s.len() as i8);
19    for c in s.bytes() {
20        v = hash_update(v, c as i8);
21    }
22
23    v
24}
25
26fn primitive_name_for_hash(p: parser::PrimitiveType) -> &'static str {
27    match p {
28        parser::PrimitiveType::Int8 => "int8_t",
29        parser::PrimitiveType::Int16 => "int16_t",
30        parser::PrimitiveType::Int32 => "int32_t",
31        parser::PrimitiveType::Int64 => "int64_t",
32        parser::PrimitiveType::Float => "float",
33        parser::PrimitiveType::Double => "double",
34        parser::PrimitiveType::String => "string",
35        parser::PrimitiveType::Boolean => "boolean",
36        parser::PrimitiveType::Byte => "byte",
37    }
38}
39
40fn dimension_id_for_hash(d: &parser::ArrayDimension) -> i8 {
41    match d {
42        parser::ArrayDimension::Static { .. } => 0,
43        parser::ArrayDimension::Dynamic { .. } => 1,
44    }
45}
46
47fn dimension_name_for_hash(d: &parser::ArrayDimension) -> String {
48    match d {
49        parser::ArrayDimension::Static { size } => format!("{}", size),
50        parser::ArrayDimension::Dynamic { field_name } => field_name.to_owned(),
51    }
52}
53
54fn struct_base_hash(s: &parser::Struct) -> u64 {
55    let mut v = INITIAL_STRUCT_HASH;
56
57    for member in s.members.iter() {
58        match member {
59            parser::StructMember::Const(_) => (),
60            parser::StructMember::Field(f) => {
61                v = hash_string_update(v, &f.name);
62                match &f.ty {
63                    parser::Type::Primitive(p) => {
64                        v = hash_string_update(v, primitive_name_for_hash(*p));
65                        v = hash_update(v, 0); // 0 array dimensions
66                    }
67                    parser::Type::Array(a) => {
68                        if let parser::Type::Primitive(p) = *a.item_type {
69                            v = hash_string_update(v, primitive_name_for_hash(p));
70                        }
71                        v = hash_update(v, a.dimensions.len() as i8);
72                        for dim in a.dimensions.iter() {
73                            v = hash_update(v, dimension_id_for_hash(dim));
74                            v = hash_string_update(v, &dimension_name_for_hash(dim));
75                        }
76                    }
77                    parser::Type::Struct(_) => (),
78                }
79            }
80        }
81    }
82
83    // This implicitly happens via the code generator in the C impl.
84    v as u64
85}
86
87fn struct_child_struct_types(s: &parser::Struct) -> impl Iterator<Item = parser::StructType> + '_ {
88    s.members.iter().flat_map(|mem| match mem {
89        parser::StructMember::Const(_) => None,
90        parser::StructMember::Field(f) => match &f.ty {
91            parser::Type::Struct(st) => Some(st.clone()),
92            parser::Type::Array(a) => match &*a.item_type {
93                parser::Type::Struct(st) => Some(st.clone()),
94                _ => None,
95            },
96            _ => None,
97        },
98    })
99}
100
101fn struct_hash_internal(s: &parser::Struct, env: &Environment, mut stack: &mut Vec<u64>) -> u64 {
102    let mut v = struct_base_hash(s);
103    if stack.contains(&v) {
104        return 0;
105    }
106    stack.push(v);
107
108    for st in struct_child_struct_types(s) {
109        let resolved_struct = env
110            .resolve_struct_type(&st)
111            .unwrap_or_else(|| panic!("Can't resolve struct type {:?}", st));
112        v = v.wrapping_add(struct_hash_internal(&resolved_struct, env, &mut stack));
113    }
114    stack.pop();
115    v = v.rotate_left(1);
116    v
117}
118
119/// Get the fingerprint for struct `s`, in the context of typing environment `env`.
120pub fn struct_hash(s: &parser::Struct, env: &Environment) -> u64 {
121    let mut visited = vec![];
122    struct_hash_internal(s, env, &mut visited)
123}
124
125#[cfg(test)]
126mod test {
127    use super::*;
128
129    #[test]
130    fn test_hash_update() {
131        assert_eq!(hash_update(INITIAL_STRUCT_HASH, 0), 0x1234567800);
132        assert_eq!(hash_update(INITIAL_STRUCT_HASH, 42), 0x123456782a);
133        assert_eq!(hash_update(INITIAL_STRUCT_HASH, -42), 0x12345677d6);
134    }
135
136    #[test]
137    fn test_hash_string_update() {
138        assert_eq!(hash_string_update(INITIAL_STRUCT_HASH, ""), 0x1234567800);
139        assert_eq!(hash_string_update(INITIAL_STRUCT_HASH, "a"), 0x123456780161);
140        assert_eq!(
141            hash_string_update(INITIAL_STRUCT_HASH, "test"),
142            0x3456780474657398
143        );
144
145        assert_eq!(
146            hash_string_update(INITIAL_STRUCT_HASH, "テスト"),
147            0x7d79f9159a2d6b4d
148        );
149
150        // 256 characters
151        assert_eq!(hash_string_update(INITIAL_STRUCT_HASH,
152                                      "asdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdfasdf"),
153                   0x33dc2d5adeb3ed47);
154    }
155
156    #[test]
157    fn test_recursive_struct_hash() {
158        let schema_text = "
159package rec_test;
160struct node {
161  int32_t count;
162  node children[count];
163}";
164        let (_, schema) = parser::schema(schema_text).unwrap();
165
166        let s = &schema.structs[0].clone();
167        assert_eq!(struct_base_hash(&s), 0xAC4115EBB89101A9);
168
169        let env = Environment {
170            local_schema: schema.clone(),
171            all_schemas: vec![schema],
172        };
173
174        // TODO check this against the reference impl
175        assert_eq!(struct_hash(&s, &env), 0xAC4115EBB89101A9u64.rotate_left(1));
176    }
177
178    #[test]
179    fn test_cross_struct_hash() {
180        let schema_text_a = "
181package cross_test;
182struct a {
183  int32_t foo;
184  int16_t bar;
185}";
186        let schema_text_b = "
187package cross_test;
188struct b {
189  int32_t baz;
190  cross_test.a cross;
191}";
192        let (_, schema_a) = parser::schema(schema_text_a).unwrap();
193        let (_, schema_b) = parser::schema(schema_text_b).unwrap();
194        let all_schemas = vec![schema_a.clone(), schema_b.clone()];
195
196        let env = Environment {
197            local_schema: schema_b.clone(),
198            all_schemas,
199        };
200
201        let b = &schema_b.structs[0];
202
203        // TODO check this against the reference impl
204        assert_eq!(struct_hash(&b, &env), 0x1C6222CC3AFC3285);
205    }
206}
rust_lcm_codegen/fingerprint.rs

rust_lcm_codegen/
fingerprint.rs
