"Fossies" - the Fresh Open Source Software Archive  

Source code changes of the file "auxil/highwayhash/README.md" between
zeek-4.0.2.tar.gz and zeek-4.0.3.tar.gz

About: Zeek (formerly Bro) is a flexible network analysis framework focusing on network security monitoring. LTS (Long Term Support) release.

README.md  (zeek-4.0.2):README.md  (zeek-4.0.3)
skipping to change at line 304 skipping to change at line 304
list or tree. list or tree.
Our first proposal (suggested by Github user funny-falcon) avoids this overhead Our first proposal (suggested by Github user funny-falcon) avoids this overhead
by always storing one tree per bin. It may also be worthwhile to store the first by always storing one tree per bin. It may also be worthwhile to store the first
entry directly in the bin, which avoids allocating any tree nodes in the common entry directly in the bin, which avoids allocating any tree nodes in the common
case where bins are sparsely populated. What kind of tree should be used? case where bins are sparsely populated. What kind of tree should be used?
Given SipHash and HighwayHash provide high quality randomness, depending on Given SipHash and HighwayHash provide high quality randomness, depending on
expecting attack surface simple non-balancing binary search tree could perform expecting attack surface simple non-balancing binary search tree could perform
reasonably well. [Wikipedia says](https://en.wikipedia.org/wiki/Binary_search_tr ee#Definition) reasonably well. [Wikipedia says](https://en.wikipedia.org/wiki/Binary_search_tr ee#Definition)
> After a long intermixed sequence of random insertion and deletion, the expecte > After a long intermixed sequence of random insertion and deletion, the
d > expected height of the tree approaches square root of the number of keys, √n,
> height of the tree approaches square root of the number of keys, √n, which gro > which grows much faster than log n.
ws
> much faster than log n.
While `O(√n)` is much larger than `O(log n)`, it is still much smaller than `O(n )`. While `O(√n)` is much larger than `O(log n)`, it is still much smaller than `O(n )`.
And it will certainly complicate the timing attack, since the time of operation And it will certainly complicate the timing attack, since the time of operation
on collisioned bin will grow slower. on collisioned bin will grow slower.
If stronger safety guarantees are needed, then a balanced tree should be used. If stronger safety guarantees are needed, then a balanced tree should be used.
Scapegoat and splay trees only offer amortized complexity guarantees, whereas Scapegoat and splay trees only offer amortized complexity guarantees, whereas
treaps require an entropy source and have higher constant factors in practice. treaps require an entropy source and have higher constant factors in practice.
Self-balancing structures such as 2-3 or red-black trees require additional Self-balancing structures such as 2-3 or red-black trees require additional
bookkeeping information. We can hope to reduce rebalancing cost by realizing bookkeeping information. We can hope to reduce rebalancing cost by realizing
skipping to change at line 358 skipping to change at line 358
## Third-party implementations / bindings ## Third-party implementations / bindings
Thanks to Damian Gryski and Frank Wessels for making us aware of these Thanks to Damian Gryski and Frank Wessels for making us aware of these
third-party implementations or bindings. Please feel free to get in touch or third-party implementations or bindings. Please feel free to get in touch or
raise an issue and we'll add yours as well. raise an issue and we'll add yours as well.
By | Language | URL By | Language | URL
--- | --- | --- --- | --- | ---
Damian Gryski | Go and x64 assembly | https://github.com/dgryski/go-highway/ Damian Gryski | Go and x64 assembly | https://github.com/dgryski/go-highway/
Lovell Fuller | node.js bindings | https://github.com/lovell/highwayhash Lovell Fuller | node.js bindings | https://github.com/lovell/highwayhash
Nick Babcock | Rust port | https://github.com/nickbabcock/highway-rs
Vinzent Steinberg | Rust bindings | https://github.com/vks/highwayhash-rs Vinzent Steinberg | Rust bindings | https://github.com/vks/highwayhash-rs
Frank Wessels & Andreas Auernhammer | Go and ARM assembly | https://github.com/m inio/highwayhash Frank Wessels & Andreas Auernhammer | Go and ARM assembly | https://github.com/m inio/highwayhash
Phil Demetriou | Python 3 bindings | https://github.com/kpdemetriou/highwayhash- cffi Phil Demetriou | Python 3 bindings | https://github.com/kpdemetriou/highwayhash- cffi
Jonathan Beard | C++20 constexpr | https://gist.github.com/jonathan-beard/632017 faa1d9d1936eb5948ac9186657
## Modules ## Modules
### Hashes ### Hashes
* c_bindings.h declares C-callable versions of SipHash/HighwayHash. * c_bindings.h declares C-callable versions of SipHash/HighwayHash.
* sip_hash.cc is the compatible implementation of SipHash, and also provides * sip_hash.cc is the compatible implementation of SipHash, and also provides
the final reduction for sip_tree_hash. the final reduction for sip_tree_hash.
* sip_tree_hash.cc is the faster but incompatible SIMD j-lanes tree hash. * sip_tree_hash.cc is the faster but incompatible SIMD j-lanes tree hash.
* scalar_sip_tree_hash.cc is a non-SIMD version. * scalar_sip_tree_hash.cc is a non-SIMD version.
 End of changes. 3 change blocks. 
5 lines changed or deleted 5 lines changed or added

Home  |  About  |  Features  |  All  |  Newest  |  Dox  |  Diffs  |  RSS Feeds  |  Screenshots  |  Comments  |  Imprint  |  Privacy  |  HTTP(S)