Linux Assemblycollection of fast libraries

Sequence librarySequence.h

Sequence library is developed to provide fast algorithms for subsequence searching. It implements only Boyer-Moore-Horspool searching algorithm now, but in future it may be extended with more specific algorithms for sequence matching.

Contents

Function list

C function nameFunctionsC++ function nameFunctions
BMH10 functionsBMH::BMH10 functions
Find10 functionsFind10 functions
C function nameFunctionsC++ function nameFunctions

Boyer-Moore-Horspool pattern hash

C
Unsigned integer types
void BMH_uint8 (struct BMH *hash, const uint8_t pattern[], size_t size, bool backward);
void BMH_uint16 (struct BMH *hash, const uint16_t pattern[], size_t size, bool backward);
void BMH_uint32 (struct BMH *hash, const uint32_t pattern[], size_t size, bool backward);
void BMH_uint64 (struct BMH *hash, const uint64_t pattern[], size_t size, bool backward);

Signed integer types
void BMH_sint8 (struct BMH *hash, const sint8_t pattern[], size_t size, bool backward);
void BMH_sint16 (struct BMH *hash, const sint16_t pattern[], size_t size, bool backward);
void BMH_sint32 (struct BMH *hash, const sint32_t pattern[], size_t size, bool backward);
void BMH_sint64 (struct BMH *hash, const sint64_t pattern[], size_t size, bool backward);

Other types
void BMH_size (struct BMH *hash, const size_t pattern[], size_t size, bool backward);
void BMH (struct BMH *hash, const void *pattern, size_t size, bool backward);
C++
Unsigned integer types
BMH::BMH (const uint8_t pattern[], size_t size, bool backward);
BMH::BMH (const uint16_t pattern[], size_t size, bool backward);
BMH::BMH (const uint32_t pattern[], size_t size, bool backward);
BMH::BMH (const uint64_t pattern[], size_t size, bool backward);

Signed integer types
BMH::BMH (const sint8_t pattern[], size_t size, bool backward);
BMH::BMH (const sint16_t pattern[], size_t size, bool backward);
BMH::BMH (const sint32_t pattern[], size_t size, bool backward);
BMH::BMH (const sint64_t pattern[], size_t size, bool backward);

Other types
BMH::BMH (const size_t pattern[], size_t size, bool backward);
BMH::BMH (const void *pattern, size_t size, bool backward);

Description: These functions are BMH object/structure constructors which compute hash function for sequence pattern, using Boyer-Moore-Horspool searching algorithm and specified search direction.

Parameters:

  • hash - pointer to Boyer-Moore-Horspool pattern hash structure
  • pattern - pointer to sequence pattern to preprocess
  • size - size of pattern sequence. If pattern is regular string, then size is length of this string. For regular arrays it specifies array size.
  • backward - search direction flag. FALSE - for forward direction (which is default), TRUE - for backward.

Return value: None.

Boyer-Moore-Horspool subsequence searching algorithm

C
Unsigned integer types
size_t Sequence_Find_uint8 (const uint8_t source[], size_t size, const struct BMH *pattern);
size_t Sequence_Find_uint16 (const uint16_t source[], size_t size, const struct BMH *pattern);
size_t Sequence_Find_uint32 (const uint32_t source[], size_t size, const struct BMH *pattern);
size_t Sequence_Find_uint64 (const uint64_t source[], size_t size, const struct BMH *pattern);

Signed integer types
size_t Sequence_Find_sint8 (const sint8_t source[], size_t size, const struct BMH *pattern);
size_t Sequence_Find_sint16 (const sint16_t source[], size_t size, const struct BMH *pattern);
size_t Sequence_Find_sint32 (const sint32_t source[], size_t size, const struct BMH *pattern);
size_t Sequence_Find_sint64 (const sint64_t source[], size_t size, const struct BMH *pattern);

Other types
size_t Sequence_Find_size (const size_t source[], size_t size, const struct BMH *pattern);
size_t Sequence_Find (const void *source, size_t size, const struct BMH *pattern);
C++
Unsigned integer types
size_t Sequence::Find (const uint8_t source[], size_t size, const BMH *pattern);
size_t Sequence::Find (const uint16_t source[], size_t size, const BMH *pattern);
size_t Sequence::Find (const uint32_t source[], size_t size, const BMH *pattern);
size_t Sequence::Find (const uint64_t source[], size_t size, const BMH *pattern);

Signed integer types
size_t Sequence::Find (const sint8_t source[], size_t size, const BMH *pattern);
size_t Sequence::Find (const sint16_t source[], size_t size, const BMH *pattern);
size_t Sequence::Find (const sint32_t source[], size_t size, const BMH *pattern);
size_t Sequence::Find (const sint64_t source[], size_t size, const BMH *pattern);

Other types
size_t Sequence::Find (const size_t source[], size_t size, const BMH *pattern);
size_t Sequence::Find (const void *source, size_t size, const BMH *pattern);

Description: Search source sequence for pattern, using Boyer-Moore-Horspool searching algorithm and specified search direction.

Parameters:

  • source - pointer to source sequence, in which pattern should be find
  • size - size of source sequence. If source is null symbol ('0x0') terminating string, then size is length of this string. For regular arrays it specifies array size.
  • pattern - BMH object/structure which holds pattern sequence, its hash function and search direction flag

Return value:

  • An index of the pattern position (its first or last occurrence, depending of direction flag) into source array.
  • -1 if pattern is not found.

Tip:If you are looking for substring searching algorithms, please use functions String::FindSubString from String library.

Copyright 2012-2016 Jack Black. All rights reserved.