From 9bcf1e97960c0da7322a868efdbc07e2650716fe Mon Sep 17 00:00:00 2001 From: "Juan J. Martinez" Date: Sat, 9 Jan 2021 09:01:05 +0000 Subject: Extra libs: ap.lib aPLib support with apultra. --- .../src/libdivsufsort/include/CMakeLists.txt | 162 ++++++++++++++++ .../src/libdivsufsort/include/config.h.cmake | 81 ++++++++ .../apultra/src/libdivsufsort/include/divsufsort.h | 189 +++++++++++++++++++ .../src/libdivsufsort/include/divsufsort.h.cmake | 180 ++++++++++++++++++ .../src/libdivsufsort/include/divsufsort_config.h | 9 + .../src/libdivsufsort/include/divsufsort_private.h | 205 +++++++++++++++++++++ .../apultra/src/libdivsufsort/include/lfs.h.cmake | 56 ++++++ 7 files changed, 882 insertions(+) create mode 100644 tools/apultra/src/libdivsufsort/include/CMakeLists.txt create mode 100644 tools/apultra/src/libdivsufsort/include/config.h.cmake create mode 100644 tools/apultra/src/libdivsufsort/include/divsufsort.h create mode 100644 tools/apultra/src/libdivsufsort/include/divsufsort.h.cmake create mode 100644 tools/apultra/src/libdivsufsort/include/divsufsort_config.h create mode 100644 tools/apultra/src/libdivsufsort/include/divsufsort_private.h create mode 100644 tools/apultra/src/libdivsufsort/include/lfs.h.cmake (limited to 'tools/apultra/src/libdivsufsort/include') diff --git a/tools/apultra/src/libdivsufsort/include/CMakeLists.txt b/tools/apultra/src/libdivsufsort/include/CMakeLists.txt new file mode 100644 index 0000000..37781cc --- /dev/null +++ b/tools/apultra/src/libdivsufsort/include/CMakeLists.txt @@ -0,0 +1,162 @@ +include(CheckIncludeFiles) +include(CheckIncludeFile) +include(CheckSymbolExists) +include(CheckTypeSize) +include(CheckFunctionKeywords) +include(CheckLFS) + +## Checks for header files ## +check_include_file("inttypes.h" HAVE_INTTYPES_H) +check_include_file("memory.h" HAVE_MEMORY_H) +check_include_file("stddef.h" HAVE_STDDEF_H) +check_include_file("stdint.h" HAVE_STDINT_H) +check_include_file("stdlib.h" HAVE_STDLIB_H) +check_include_file("string.h" HAVE_STRING_H) +check_include_file("strings.h" HAVE_STRINGS_H) +check_include_file("sys/types.h" HAVE_SYS_TYPES_H) +if(HAVE_INTTYPES_H) + set(INCFILE "#include ") +elseif(HAVE_STDINT_H) + set(INCFILE "#include ") +else(HAVE_INTTYPES_H) + set(INCFILE "") +endif(HAVE_INTTYPES_H) + +## create configuration files from .cmake file ## +if(BUILD_EXAMPLES) + ## Checks for WinIO ## + if(WIN32) + check_include_file("io.h" HAVE_IO_H) + check_include_file("fcntl.h" HAVE_FCNTL_H) + check_symbol_exists("_setmode" "io.h;fcntl.h" HAVE__SETMODE) + if(NOT HAVE__SETMODE) + check_symbol_exists("setmode" "io.h;fcntl.h" HAVE_SETMODE) + endif(NOT HAVE__SETMODE) + check_symbol_exists("_fileno" "stdio.h" HAVE__FILENO) + check_symbol_exists("fopen_s" "stdio.h" HAVE_FOPEN_S) + check_symbol_exists("_O_BINARY" "fcntl.h" HAVE__O_BINARY) + endif(WIN32) + + ## Checks for large file support ## + check_lfs(WITH_LFS) + configure_file("${CMAKE_CURRENT_SOURCE_DIR}/lfs.h.cmake" "${CMAKE_CURRENT_BINARY_DIR}/lfs.h" @ONLY) +endif(BUILD_EXAMPLES) + +## generate config.h ## +check_function_keywords("inline;__inline;__inline__;__declspec(dllexport);__declspec(dllimport)") +if(HAVE_INLINE) + set(INLINE "inline") +elseif(HAVE___INLINE) + set(INLINE "__inline") +elseif(HAVE___INLINE__) + set(INLINE "__inline__") +else(HAVE_INLINE) + set(INLINE "") +endif(HAVE_INLINE) +configure_file("${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake" "${CMAKE_CURRENT_BINARY_DIR}/config.h") + +## Checks for types ## +# sauchar_t (8bit) +check_type_size("uint8_t" UINT8_T) +if(HAVE_UINT8_T) + set(SAUCHAR_TYPE "uint8_t") +else(HAVE_UINT8_T) + check_type_size("unsigned char" SIZEOF_UNSIGNED_CHAR) + if("${SIZEOF_UNSIGNED_CHAR}" STREQUAL "1") + set(SAUCHAR_TYPE "unsigned char") + else("${SIZEOF_UNSIGNED_CHAR}" STREQUAL "1") + message(FATAL_ERROR "Cannot find unsigned 8-bit integer type") + endif("${SIZEOF_UNSIGNED_CHAR}" STREQUAL "1") +endif(HAVE_UINT8_T) +# saint_t (32bit) +check_type_size("int32_t" INT32_T) +if(HAVE_INT32_T) + set(SAINT32_TYPE "int32_t") + check_symbol_exists("PRId32" "inttypes.h" HAVE_PRID32) + if(HAVE_PRID32) + set(SAINT32_PRId "PRId32") + else(HAVE_PRID32) + set(SAINT32_PRId "\"d\"") + endif(HAVE_PRID32) +else(HAVE_INT32_T) + check_type_size("int" SIZEOF_INT) + check_type_size("long" SIZEOF_LONG) + check_type_size("short" SIZEOF_SHORT) + check_type_size("__int32" SIZEOF___INT32) + if("${SIZEOF_INT}" STREQUAL "4") + set(SAINT32_TYPE "int") + set(SAINT32_PRId "\"d\"") + elseif("${SIZEOF_LONG}" STREQUAL "4") + set(SAINT32_TYPE "long") + set(SAINT32_PRId "\"ld\"") + elseif("${SIZEOF_SHORT}" STREQUAL "4") + set(SAINT32_TYPE "short") + set(SAINT32_PRId "\"d\"") + elseif("${SIZEOF___INT32}" STREQUAL "4") + set(SAINT32_TYPE "__int32") + set(SAINT32_PRId "\"d\"") + else("${SIZEOF_INT}" STREQUAL "4") + message(FATAL_ERROR "Cannot find 32-bit integer type") + endif("${SIZEOF_INT}" STREQUAL "4") +endif(HAVE_INT32_T) +# saint64_t (64bit) +if(BUILD_DIVSUFSORT64) + check_type_size("int64_t" INT64_T) + if(HAVE_INT64_T) + set(SAINT64_TYPE "int64_t") + check_symbol_exists("PRId64" "inttypes.h" HAVE_PRID64) + if(HAVE_PRID64) + set(SAINT64_PRId "PRId64") + else(HAVE_PRID64) + set(SAINT64_PRId "\"lld\"") + endif(HAVE_PRID64) + else(HAVE_INT64_T) + check_type_size("int" SIZEOF_INT) + check_type_size("long" SIZEOF_LONG) + check_type_size("long long" SIZEOF_LONG_LONG) + check_type_size("__int64" SIZEOF___INT64) + if("${SIZEOF_INT}" STREQUAL "8") + set(SAINT64_TYPE "int") + set(SAINT64_PRId "\"d\"") + elseif("${SIZEOF_LONG}" STREQUAL "8") + set(SAINT64_TYPE "long") + set(SAINT64_PRId "\"ld\"") + elseif("${SIZEOF_LONG_LONG}" STREQUAL "8") + set(SAINT64_TYPE "long long") + set(SAINT64_PRId "\"lld\"") + elseif("${SIZEOF___INT64}" STREQUAL "8") + set(SAINT64_TYPE "__int64") + set(SAINT64_PRId "\"I64d\"") + else("${SIZEOF_INT}" STREQUAL "8") + message(SEND_ERROR "Cannot find 64-bit integer type") + set(BUILD_DIVSUFSORT64 OFF) + endif("${SIZEOF_INT}" STREQUAL "8") + endif(HAVE_INT64_T) +endif(BUILD_DIVSUFSORT64) + +## generate divsufsort.h ## +set(DIVSUFSORT_IMPORT "") +set(DIVSUFSORT_EXPORT "") +if(BUILD_SHARED_LIBS) + if(HAVE___DECLSPEC_DLLIMPORT_) + set(DIVSUFSORT_IMPORT "__declspec(dllimport)") + endif(HAVE___DECLSPEC_DLLIMPORT_) + if(HAVE___DECLSPEC_DLLEXPORT_) + set(DIVSUFSORT_EXPORT "__declspec(dllexport)") + endif(HAVE___DECLSPEC_DLLEXPORT_) +endif(BUILD_SHARED_LIBS) +set(W64BIT "") +set(SAINDEX_TYPE "${SAINT32_TYPE}") +set(SAINDEX_PRId "${SAINT32_PRId}") +set(SAINT_PRId "${SAINT32_PRId}") +configure_file("${CMAKE_CURRENT_SOURCE_DIR}/divsufsort.h.cmake" + "${CMAKE_CURRENT_BINARY_DIR}/divsufsort.h" @ONLY) +install(FILES "${CMAKE_CURRENT_BINARY_DIR}/divsufsort.h" DESTINATION ${CMAKE_INSTALL_INCLUDEDIR}) +if(BUILD_DIVSUFSORT64) + set(W64BIT "64") + set(SAINDEX_TYPE "${SAINT64_TYPE}") + set(SAINDEX_PRId "${SAINT64_PRId}") + configure_file("${CMAKE_CURRENT_SOURCE_DIR}/divsufsort.h.cmake" + "${CMAKE_CURRENT_BINARY_DIR}/divsufsort64.h" @ONLY) + install(FILES "${CMAKE_CURRENT_BINARY_DIR}/divsufsort64.h" DESTINATION ${CMAKE_INSTALL_INCLUDEDIR}) +endif(BUILD_DIVSUFSORT64) diff --git a/tools/apultra/src/libdivsufsort/include/config.h.cmake b/tools/apultra/src/libdivsufsort/include/config.h.cmake new file mode 100644 index 0000000..6a1cf47 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/include/config.h.cmake @@ -0,0 +1,81 @@ +/* + * config.h for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _CONFIG_H +#define _CONFIG_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** Define to the version of this package. **/ +#cmakedefine PROJECT_VERSION_FULL "${PROJECT_VERSION_FULL}" + +/** Define to 1 if you have the header files. **/ +#cmakedefine HAVE_INTTYPES_H 1 +#cmakedefine HAVE_STDDEF_H 1 +#cmakedefine HAVE_STDINT_H 1 +#cmakedefine HAVE_STDLIB_H 1 +#cmakedefine HAVE_STRING_H 1 +#cmakedefine HAVE_STRINGS_H 1 +#cmakedefine HAVE_MEMORY_H 1 +#cmakedefine HAVE_SYS_TYPES_H 1 + +/** for WinIO **/ +#cmakedefine HAVE_IO_H 1 +#cmakedefine HAVE_FCNTL_H 1 +#cmakedefine HAVE__SETMODE 1 +#cmakedefine HAVE_SETMODE 1 +#cmakedefine HAVE__FILENO 1 +#cmakedefine HAVE_FOPEN_S 1 +#cmakedefine HAVE__O_BINARY 1 +#ifndef HAVE__SETMODE +# if HAVE_SETMODE +# define _setmode setmode +# define HAVE__SETMODE 1 +# endif +# if HAVE__SETMODE && !HAVE__O_BINARY +# define _O_BINARY 0 +# define HAVE__O_BINARY 1 +# endif +#endif + +/** for inline **/ +#ifndef INLINE +# define INLINE @INLINE@ +#endif + +/** for VC++ warning **/ +#ifdef _MSC_VER +#pragma warning(disable: 4127) +#endif + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _CONFIG_H */ diff --git a/tools/apultra/src/libdivsufsort/include/divsufsort.h b/tools/apultra/src/libdivsufsort/include/divsufsort.h new file mode 100644 index 0000000..7ebb412 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/include/divsufsort.h @@ -0,0 +1,189 @@ +/* + * divsufsort.h for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _DIVSUFSORT_H +#define _DIVSUFSORT_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#define DIVSUFSORT_API + +/*- Datatypes -*/ +#ifndef SAUCHAR_T +#define SAUCHAR_T +typedef unsigned char sauchar_t; +#endif /* SAUCHAR_T */ +#ifndef SAINT_T +#define SAINT_T +typedef int saint_t; +#endif /* SAINT_T */ +#ifndef SAIDX_T +#define SAIDX_T +typedef int saidx_t; +#endif /* SAIDX_T */ +#ifndef PRIdSAIDX_T +#define PRIdSAIDX_T "d" +#endif + +/*- divsufsort context */ +typedef struct _divsufsort_ctx_t { + saidx_t *bucket_A; + saidx_t *bucket_B; +} divsufsort_ctx_t; + +/*- Prototypes -*/ + +/** + * Initialize suffix array context + * + * @return 0 for success, or non-zero in case of an error + */ +int divsufsort_init(divsufsort_ctx_t *ctx); + +/** + * Destroy suffix array context + * + * @param ctx suffix array context to destroy + */ +void divsufsort_destroy(divsufsort_ctx_t *ctx); + +/** + * Constructs the suffix array of a given string. + * @param ctx suffix array context + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The output array of suffixes. + * @param n The length of the given string. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t divsufsort_build_array(divsufsort_ctx_t *ctx, const sauchar_t *T, saidx_t *SA, saidx_t n); + +#if 0 +/** + * Constructs the burrows-wheeler transformed string of a given string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @return The primary index if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saidx_t +divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n); + +/** + * Returns the version of the divsufsort library. + * @return The version number string. + */ +DIVSUFSORT_API +const char * +divsufsort_version(void); + + +/** + * Constructs the burrows-wheeler transformed string of a given string and suffix array. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param SA[0..n-1] The suffix array. (can be NULL) + * @param n The length of the given string. + * @param idx The output primary index. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +bw_transform(const sauchar_t *T, sauchar_t *U, + saidx_t *SA /* can NULL */, + saidx_t n, saidx_t *idx); + +/** + * Inverse BW-transforms a given BWTed string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @param idx The primary index. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +inverse_bw_transform(const sauchar_t *T, sauchar_t *U, + saidx_t *A /* can NULL */, + saidx_t n, saidx_t idx); + +/** + * Checks the correctness of a given suffix array. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The input suffix array. + * @param n The length of the given string. + * @param verbose The verbose mode. + * @return 0 if no error occurred. + */ +DIVSUFSORT_API +saint_t +sufcheck(const sauchar_t *T, const saidx_t *SA, saidx_t n, saint_t verbose); + +/** + * Search for the pattern P in the string T. + * @param T[0..Tsize-1] The input string. + * @param Tsize The length of the given string. + * @param P[0..Psize-1] The input pattern string. + * @param Psize The length of the given pattern string. + * @param SA[0..SAsize-1] The input suffix array. + * @param SAsize The length of the given suffix array. + * @param idx The output index. + * @return The count of matches if no error occurred, -1 otherwise. + */ +DIVSUFSORT_API +saidx_t +sa_search(const sauchar_t *T, saidx_t Tsize, + const sauchar_t *P, saidx_t Psize, + const saidx_t *SA, saidx_t SAsize, + saidx_t *left); + +/** + * Search for the character c in the string T. + * @param T[0..Tsize-1] The input string. + * @param Tsize The length of the given string. + * @param SA[0..SAsize-1] The input suffix array. + * @param SAsize The length of the given suffix array. + * @param c The input character. + * @param idx The output index. + * @return The count of matches if no error occurred, -1 otherwise. + */ +DIVSUFSORT_API +saidx_t +sa_simplesearch(const sauchar_t *T, saidx_t Tsize, + const saidx_t *SA, saidx_t SAsize, + saint_t c, saidx_t *left); +#endif + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _DIVSUFSORT_H */ diff --git a/tools/apultra/src/libdivsufsort/include/divsufsort.h.cmake b/tools/apultra/src/libdivsufsort/include/divsufsort.h.cmake new file mode 100644 index 0000000..bcaba7c --- /dev/null +++ b/tools/apultra/src/libdivsufsort/include/divsufsort.h.cmake @@ -0,0 +1,180 @@ +/* + * divsufsort@W64BIT@.h for libdivsufsort@W64BIT@ + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _DIVSUFSORT@W64BIT@_H +#define _DIVSUFSORT@W64BIT@_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +@INCFILE@ + +#ifndef DIVSUFSORT_API +# ifdef DIVSUFSORT_BUILD_DLL +# define DIVSUFSORT_API @DIVSUFSORT_EXPORT@ +# else +# define DIVSUFSORT_API @DIVSUFSORT_IMPORT@ +# endif +#endif + +/*- Datatypes -*/ +#ifndef SAUCHAR_T +#define SAUCHAR_T +typedef @SAUCHAR_TYPE@ sauchar_t; +#endif /* SAUCHAR_T */ +#ifndef SAINT_T +#define SAINT_T +typedef @SAINT32_TYPE@ saint_t; +#endif /* SAINT_T */ +#ifndef SAIDX@W64BIT@_T +#define SAIDX@W64BIT@_T +typedef @SAINDEX_TYPE@ saidx@W64BIT@_t; +#endif /* SAIDX@W64BIT@_T */ +#ifndef PRIdSAINT_T +#define PRIdSAINT_T @SAINT_PRId@ +#endif /* PRIdSAINT_T */ +#ifndef PRIdSAIDX@W64BIT@_T +#define PRIdSAIDX@W64BIT@_T @SAINDEX_PRId@ +#endif /* PRIdSAIDX@W64BIT@_T */ + + +/*- Prototypes -*/ + +/** + * Constructs the suffix array of a given string. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The output array of suffixes. + * @param n The length of the given string. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +divsufsort@W64BIT@(const sauchar_t *T, saidx@W64BIT@_t *SA, saidx@W64BIT@_t n); + +/** + * Constructs the burrows-wheeler transformed string of a given string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @return The primary index if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saidx@W64BIT@_t +divbwt@W64BIT@(const sauchar_t *T, sauchar_t *U, saidx@W64BIT@_t *A, saidx@W64BIT@_t n); + +/** + * Returns the version of the divsufsort library. + * @return The version number string. + */ +DIVSUFSORT_API +const char * +divsufsort@W64BIT@_version(void); + + +/** + * Constructs the burrows-wheeler transformed string of a given string and suffix array. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param SA[0..n-1] The suffix array. (can be NULL) + * @param n The length of the given string. + * @param idx The output primary index. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +bw_transform@W64BIT@(const sauchar_t *T, sauchar_t *U, + saidx@W64BIT@_t *SA /* can NULL */, + saidx@W64BIT@_t n, saidx@W64BIT@_t *idx); + +/** + * Inverse BW-transforms a given BWTed string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @param idx The primary index. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +inverse_bw_transform@W64BIT@(const sauchar_t *T, sauchar_t *U, + saidx@W64BIT@_t *A /* can NULL */, + saidx@W64BIT@_t n, saidx@W64BIT@_t idx); + +/** + * Checks the correctness of a given suffix array. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The input suffix array. + * @param n The length of the given string. + * @param verbose The verbose mode. + * @return 0 if no error occurred. + */ +DIVSUFSORT_API +saint_t +sufcheck@W64BIT@(const sauchar_t *T, const saidx@W64BIT@_t *SA, saidx@W64BIT@_t n, saint_t verbose); + +/** + * Search for the pattern P in the string T. + * @param T[0..Tsize-1] The input string. + * @param Tsize The length of the given string. + * @param P[0..Psize-1] The input pattern string. + * @param Psize The length of the given pattern string. + * @param SA[0..SAsize-1] The input suffix array. + * @param SAsize The length of the given suffix array. + * @param idx The output index. + * @return The count of matches if no error occurred, -1 otherwise. + */ +DIVSUFSORT_API +saidx@W64BIT@_t +sa_search@W64BIT@(const sauchar_t *T, saidx@W64BIT@_t Tsize, + const sauchar_t *P, saidx@W64BIT@_t Psize, + const saidx@W64BIT@_t *SA, saidx@W64BIT@_t SAsize, + saidx@W64BIT@_t *left); + +/** + * Search for the character c in the string T. + * @param T[0..Tsize-1] The input string. + * @param Tsize The length of the given string. + * @param SA[0..SAsize-1] The input suffix array. + * @param SAsize The length of the given suffix array. + * @param c The input character. + * @param idx The output index. + * @return The count of matches if no error occurred, -1 otherwise. + */ +DIVSUFSORT_API +saidx@W64BIT@_t +sa_simplesearch@W64BIT@(const sauchar_t *T, saidx@W64BIT@_t Tsize, + const saidx@W64BIT@_t *SA, saidx@W64BIT@_t SAsize, + saint_t c, saidx@W64BIT@_t *left); + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _DIVSUFSORT@W64BIT@_H */ diff --git a/tools/apultra/src/libdivsufsort/include/divsufsort_config.h b/tools/apultra/src/libdivsufsort/include/divsufsort_config.h new file mode 100644 index 0000000..4054a8a --- /dev/null +++ b/tools/apultra/src/libdivsufsort/include/divsufsort_config.h @@ -0,0 +1,9 @@ +#define HAVE_STRING_H 1 +#define HAVE_STDLIB_H 1 +#define HAVE_MEMORY_H 1 +#define HAVE_STDINT_H 1 +#define INLINE inline + +#ifdef _MSC_VER +#pragma warning( disable : 4244 ) +#endif /* _MSC_VER */ diff --git a/tools/apultra/src/libdivsufsort/include/divsufsort_private.h b/tools/apultra/src/libdivsufsort/include/divsufsort_private.h new file mode 100644 index 0000000..b4d97ad --- /dev/null +++ b/tools/apultra/src/libdivsufsort/include/divsufsort_private.h @@ -0,0 +1,205 @@ +/* + * divsufsort_private.h for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _DIVSUFSORT_PRIVATE_H +#define _DIVSUFSORT_PRIVATE_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#include "divsufsort_config.h" +#include +#include +#if HAVE_STRING_H +# include +#endif +#if HAVE_STDLIB_H +# include +#endif +#if HAVE_MEMORY_H +# include +#endif +#if HAVE_STDDEF_H +# include +#endif +#if HAVE_STRINGS_H +# include +#endif +#if HAVE_INTTYPES_H +# include +#else +# if HAVE_STDINT_H +# include +# endif +#endif +#if defined(BUILD_DIVSUFSORT64) +# include "divsufsort64.h" +# ifndef SAIDX_T +# define SAIDX_T +# define saidx_t saidx64_t +# endif /* SAIDX_T */ +# ifndef PRIdSAIDX_T +# define PRIdSAIDX_T PRIdSAIDX64_T +# endif /* PRIdSAIDX_T */ +# define divsufsort divsufsort64 +# define divbwt divbwt64 +# define divsufsort_version divsufsort64_version +# define bw_transform bw_transform64 +# define inverse_bw_transform inverse_bw_transform64 +# define sufcheck sufcheck64 +# define sa_search sa_search64 +# define sa_simplesearch sa_simplesearch64 +# define sssort sssort64 +# define trsort trsort64 +#else +# include "divsufsort.h" +#endif + + +/*- Constants -*/ +#if !defined(UINT8_MAX) +# define UINT8_MAX (255) +#endif /* UINT8_MAX */ +#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1) +# undef ALPHABET_SIZE +#endif +#if !defined(ALPHABET_SIZE) +# define ALPHABET_SIZE (UINT8_MAX + 1) +#endif +/* for divsufsort.c */ +#define BUCKET_A_SIZE (ALPHABET_SIZE) +#define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE) +/* for sssort.c */ +#if defined(SS_INSERTIONSORT_THRESHOLD) +# if SS_INSERTIONSORT_THRESHOLD < 1 +# undef SS_INSERTIONSORT_THRESHOLD +# define SS_INSERTIONSORT_THRESHOLD (1) +# endif +#else +# define SS_INSERTIONSORT_THRESHOLD (8) +#endif +#if defined(SS_BLOCKSIZE) +# if SS_BLOCKSIZE < 0 +# undef SS_BLOCKSIZE +# define SS_BLOCKSIZE (0) +# elif 32768 <= SS_BLOCKSIZE +# undef SS_BLOCKSIZE +# define SS_BLOCKSIZE (32767) +# endif +#else +# define SS_BLOCKSIZE (1024) +#endif +/* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */ +#if SS_BLOCKSIZE == 0 +# if defined(BUILD_DIVSUFSORT64) +# define SS_MISORT_STACKSIZE (96) +# else +# define SS_MISORT_STACKSIZE (64) +# endif +#elif SS_BLOCKSIZE <= 4096 +# define SS_MISORT_STACKSIZE (16) +#else +# define SS_MISORT_STACKSIZE (24) +#endif +#if defined(BUILD_DIVSUFSORT64) +# define SS_SMERGE_STACKSIZE (64) +#else +# define SS_SMERGE_STACKSIZE (32) +#endif +/* for trsort.c */ +#define TR_INSERTIONSORT_THRESHOLD (8) +#if defined(BUILD_DIVSUFSORT64) +# define TR_STACKSIZE (96) +#else +# define TR_STACKSIZE (64) +#endif + + +/*- Macros -*/ +#ifndef SWAP +# define SWAP(_a, _b) do { t = (_a); (_a) = (_b); (_b) = t; } while(0) +#endif /* SWAP */ +#ifndef MIN +# define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b)) +#endif /* MIN */ +#ifndef MAX +# define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b)) +#endif /* MAX */ +#define STACK_PUSH(_a, _b, _c, _d)\ + do {\ + assert(ssize < STACK_SIZE);\ + stack[ssize].a = (_a), stack[ssize].b = (_b),\ + stack[ssize].c = (_c), stack[ssize++].d = (_d);\ + } while(0) +#define STACK_PUSH5(_a, _b, _c, _d, _e)\ + do {\ + assert(ssize < STACK_SIZE);\ + stack[ssize].a = (_a), stack[ssize].b = (_b),\ + stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\ + } while(0) +#define STACK_POP(_a, _b, _c, _d)\ + do {\ + assert(0 <= ssize);\ + if(ssize == 0) { return; }\ + (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ + (_c) = stack[ssize].c, (_d) = stack[ssize].d;\ + } while(0) +#define STACK_POP5(_a, _b, _c, _d, _e)\ + do {\ + assert(0 <= ssize);\ + if(ssize == 0) { return; }\ + (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ + (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\ + } while(0) +/* for divsufsort.c */ +#define BUCKET_A(_c0) bucket_A[(_c0)] +#if ALPHABET_SIZE == 256 +#define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)]) +#define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)]) +#else +#define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)]) +#define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)]) +#endif + + +/*- Private Prototypes -*/ +/* sssort.c */ +void +sssort(const sauchar_t *Td, const saidx_t *PA, + saidx_t *first, saidx_t *last, + saidx_t *buf, saidx_t bufsize, + saidx_t depth, saidx_t n, saint_t lastsuffix); +/* trsort.c */ +void +trsort(saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth); + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _DIVSUFSORT_PRIVATE_H */ diff --git a/tools/apultra/src/libdivsufsort/include/lfs.h.cmake b/tools/apultra/src/libdivsufsort/include/lfs.h.cmake new file mode 100644 index 0000000..d5b84a8 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/include/lfs.h.cmake @@ -0,0 +1,56 @@ +/* + * lfs.h for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _LFS_H +#define _LFS_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#ifndef __STRICT_ANSI__ +# define LFS_OFF_T @LFS_OFF_T@ +# define LFS_FOPEN @LFS_FOPEN@ +# define LFS_FTELL @LFS_FTELL@ +# define LFS_FSEEK @LFS_FSEEK@ +# define LFS_PRId @LFS_PRID@ +#else +# define LFS_OFF_T long +# define LFS_FOPEN fopen +# define LFS_FTELL ftell +# define LFS_FSEEK fseek +# define LFS_PRId "ld" +#endif +#ifndef PRIdOFF_T +# define PRIdOFF_T LFS_PRId +#endif + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _LFS_H */ -- cgit v1.2.3