microsoft / security-utilities

Security utilities for key generation, string redaction, etc.
MIT License
24 stars 9 forks source link

Rust/His: Speed up generalized pattern checks #30

Closed beaubelgrave closed 4 months ago

beaubelgrave commented 4 months ago

The existing generalized pattern check code simply linearly scans all definitions for matching packed words. This works well with a few definitions, but as more are added the performance suffers.

Create 32 lanes for UTF8 and UTF16 that split up the packed words. Use the accumulator value to find the right lane to check, then linear scan those. This makes the linear scan faster as UTF8 and UTF16 are isolated to "like" patterns.