v0.1.6

What's Changed

• chore: add PREFIX and BINDIR for installation by @chenrui333 in #6

New Contributors

• @chenrui333 made their first contribution in #6

Full Changelog: v0.1.5...v0.1.6

v0.1.5: refactor: Enhancements and Fixes for krep

Enhancements

• Case-Insensitive Search Optimization:
  • Introduced lower_table for efficient case-insensitive comparisons.
  • Removed global cached pattern to simplify code and avoid threading issues.
• Search Functions:
  • Updated boyer_moore_search, kmp_search, rabin_karp_search, simd_search, and avx2_search to use lower_table for case-insensitive searches.
  • Improved SIMD search implementation to handle boundary conditions correctly.
• Main Function:
  • Added initialization of lower_table at the start.
  • Enhanced pattern cleaning to remove stray quotes and commas.
  • Improved handling of string mode and filename.

New Test Cases

• Pathological Patterns:
  • Added tests for patterns that repeat within themselves and cause backtracking.
• Boundary Conditions:
  • Added tests for matches at the start, end, and exact equality of buffers.
• Advanced Case-Insensitive Scenarios:
  • Added tests for mixed case patterns and non-ASCII characters.
• Varying Pattern Lengths:
  • Added tests for performance with patterns of increasing lengths.
• Stress Testing:
  • Added tests on a large dataset (50MB) with known patterns to ensure robustness.

Updated Files

• README.md: Updated version to 0.1.5.
• krep.c: Implemented the above enhancements and optimizations.
• test/test_krep.c: Added new test cases and updated the main test function to include them.

Summary

This release enhances the krep string search utility by optimizing case-insensitive searches, improving SIMD implementations, and adding extensive test cases to ensure robustness and performance. The version has been updated to 0.1.5 to reflect these improvements.

v0.1.4: fix :Out-of-bounds read in simd_search (#2)

Fixed

• Prevent buffer overrun in simd_search:
  • Added a check to ensure at least 16 bytes remain before performing _mm_loadu_si128.
  • Implemented a scalar fallback for handling remaining bytes safely.
  • Fixes #2.

Improved

• Optimized SIMD search logic:

  • Reordered conditions to enhance branch prediction.
  • Ensured correct handling of overlapping matches.

• Memory safety improvements:

  • Replaced direct modification of pattern with strdup().
  • Ensured allocated memory (clean_pattern) is properly freed after use.

v0.1.3

Full Changelog: v0.1.2...v0.1.3

v0.1.2

Summary

• Improved pattern matching by refining match skipping behavior in multiple search functions.
• Ensured all matches are detected by incrementing indices correctly.
• Minor optimizations for search algorithm accuracy.

Changes

Bug Fixes

• Fixed pattern skipping logic:
  • Adjusted boyer_moore_search, kmp_search, simd_search, and avx2_search to increment by 1 instead of pattern_len to ensure all matches are detected.
  • Prevented unintended skips, improving detection of overlapping matches.

Code Improvements

• Refined search behavior:
  • Made index advancement more consistent across different search algorithms.
  • Improved handling of match detection without affecting performance.

Files Modified

• krep.c: Updated search logic in multiple functions.

Version Bump

• Updated version: 0.1.1 → 0.1.2

Author

Davide Santangelo

---

This release ensures more accurate pattern detection while maintaining performance optimizations.

v0.1.1

Summary

• Improved pattern matching performance by implementing non-overlapping search optimizations across multiple algorithms.
• Fixed edge cases in kmp_search, rabin_karp_search, simd_search, and avx2_search functions.
• Introduced an optimized approach for single-character pattern searches in kmp_search.
• Updated SIMD and AVX2 implementations for case-insensitive matching.

Changes

New Features

• Single-character pattern optimization: Improved efficiency of kmp_search by handling single-character patterns separately.
• Non-overlapping match handling: Updated multiple search functions to skip over matched patterns to enhance performance and avoid redundant checks.
• Optimized SIMD/AVX2 pattern matching: Used memory-safe methods to handle case-insensitive matching in vectorized search.

Bug Fixes

• Fixed incorrect prefix table handling in kmp_search.
• Adjusted rabin_karp_search to correctly update text hash during skipping.
• Resolved incorrect AVX2 pattern initialization for case-insensitive searches.
• Prevented overlapping matches from affecting search efficiency.

Code Improvements

• Replaced for-loops with while-loops in kmp_search and rabin_karp_search for better efficiency.
• Applied memset for safer memory initialization in SIMD/AVX2 processing.
• Improved readability and maintainability of search algorithms.

Files Modified

• krep.c: Enhanced search algorithm implementations.
• New Binary Files:
  • krep: Compiled executable
  • krep.o: Compiled object file

Version Bump

• Updated version: 0.1.0 → 0.1.1

Author

Davide Santangelo

---

This update significantly enhances the efficiency and accuracy of krep's pattern matching functionality, ensuring better performance and more reliable results.

v0.1.0

Full Changelog: https://github.com/davidesantangelo/krep/commits/v0.1.0