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. --- tools/apultra/src/libdivsufsort/CHANGELOG.md | 21 ++ tools/apultra/src/libdivsufsort/CMakeLists.txt | 99 ++++++++++ .../CMakeModules/AppendCompilerFlags.cmake | 38 ++++ .../CMakeModules/CheckFunctionKeywords.cmake | 15 ++ .../src/libdivsufsort/CMakeModules/CheckLFS.cmake | 109 ++++++++++ .../libdivsufsort/CMakeModules/ProjectCPack.cmake | 38 ++++ .../CMakeModules/cmake_uninstall.cmake.in | 36 ++++ tools/apultra/src/libdivsufsort/LICENSE | 21 ++ tools/apultra/src/libdivsufsort/README.md | 140 +++++++++++++ tools/apultra/src/libdivsufsort/VERSION.cmake | 23 +++ .../src/libdivsufsort/examples/CMakeLists.txt | 11 ++ tools/apultra/src/libdivsufsort/examples/bwt.c | 220 +++++++++++++++++++++ tools/apultra/src/libdivsufsort/examples/mksary.c | 193 ++++++++++++++++++ .../apultra/src/libdivsufsort/examples/sasearch.c | 165 ++++++++++++++++ tools/apultra/src/libdivsufsort/examples/suftest.c | 164 +++++++++++++++ tools/apultra/src/libdivsufsort/examples/unbwt.c | 207 +++++++++++++++++++ .../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 ++++++ .../src/libdivsufsort/pkgconfig/CMakeLists.txt | 9 + .../libdivsufsort/pkgconfig/libdivsufsort.pc.cmake | 11 ++ 25 files changed, 2402 insertions(+) create mode 100644 tools/apultra/src/libdivsufsort/CHANGELOG.md create mode 100644 tools/apultra/src/libdivsufsort/CMakeLists.txt create mode 100644 tools/apultra/src/libdivsufsort/CMakeModules/AppendCompilerFlags.cmake create mode 100644 tools/apultra/src/libdivsufsort/CMakeModules/CheckFunctionKeywords.cmake create mode 100644 tools/apultra/src/libdivsufsort/CMakeModules/CheckLFS.cmake create mode 100644 tools/apultra/src/libdivsufsort/CMakeModules/ProjectCPack.cmake create mode 100644 tools/apultra/src/libdivsufsort/CMakeModules/cmake_uninstall.cmake.in create mode 100644 tools/apultra/src/libdivsufsort/LICENSE create mode 100644 tools/apultra/src/libdivsufsort/README.md create mode 100644 tools/apultra/src/libdivsufsort/VERSION.cmake create mode 100644 tools/apultra/src/libdivsufsort/examples/CMakeLists.txt create mode 100644 tools/apultra/src/libdivsufsort/examples/bwt.c create mode 100644 tools/apultra/src/libdivsufsort/examples/mksary.c create mode 100644 tools/apultra/src/libdivsufsort/examples/sasearch.c create mode 100644 tools/apultra/src/libdivsufsort/examples/suftest.c create mode 100644 tools/apultra/src/libdivsufsort/examples/unbwt.c 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 create mode 100644 tools/apultra/src/libdivsufsort/pkgconfig/CMakeLists.txt create mode 100644 tools/apultra/src/libdivsufsort/pkgconfig/libdivsufsort.pc.cmake (limited to 'tools/apultra/src/libdivsufsort') diff --git a/tools/apultra/src/libdivsufsort/CHANGELOG.md b/tools/apultra/src/libdivsufsort/CHANGELOG.md new file mode 100644 index 0000000..fe9d004 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/CHANGELOG.md @@ -0,0 +1,21 @@ +# libdivsufsort Change Log + +See full changelog at: https://github.com/y-256/libdivsufsort/commits + +## [2.0.1] - 2010-11-11 +### Fixed +* Wrong variable used in `divbwt` function +* Enclose some string variables with double quotation marks in include/CMakeLists.txt +* Fix typo in include/CMakeLists.txt + +## 2.0.0 - 2008-08-23 +### Changed +* Switch the build system to [CMake](http://www.cmake.org/) +* Improve the performance of the suffix-sorting algorithm + +### Added +* OpenMP support +* 64-bit version of divsufsort + +[Unreleased]: https://github.com/y-256/libdivsufsort/compare/2.0.1...HEAD +[2.0.1]: https://github.com/y-256/libdivsufsort/compare/2.0.0...2.0.1 diff --git a/tools/apultra/src/libdivsufsort/CMakeLists.txt b/tools/apultra/src/libdivsufsort/CMakeLists.txt new file mode 100644 index 0000000..7859943 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/CMakeLists.txt @@ -0,0 +1,99 @@ +### cmake file for building libdivsufsort Package ### +cmake_minimum_required(VERSION 2.4.4) +set(CMAKE_MODULE_PATH "${CMAKE_CURRENT_SOURCE_DIR}/CMakeModules") +include(AppendCompilerFlags) + +## Project information ## +project(libdivsufsort C) +set(PROJECT_VENDOR "Yuta Mori") +set(PROJECT_CONTACT "yuta.256@gmail.com") +set(PROJECT_URL "https://github.com/y-256/libdivsufsort") +set(PROJECT_DESCRIPTION "A lightweight suffix sorting library") +include(VERSION.cmake) + +## CPack configuration ## +set(CPACK_GENERATOR "TGZ;TBZ2;ZIP") +set(CPACK_SOURCE_GENERATOR "TGZ;TBZ2;ZIP") +include(ProjectCPack) + +## Project options ## +option(BUILD_SHARED_LIBS "Set to OFF to build static libraries" ON) +option(BUILD_EXAMPLES "Build examples" ON) +option(BUILD_DIVSUFSORT64 "Build libdivsufsort64" OFF) +option(USE_OPENMP "Use OpenMP for parallelization" OFF) +option(WITH_LFS "Enable Large File Support" ON) + +## Installation directories ## +set(LIB_SUFFIX "" CACHE STRING "Define suffix of directory name (32 or 64)") + +set(CMAKE_INSTALL_RUNTIMEDIR "" CACHE PATH "Specify the output directory for dll runtimes (default is bin)") +if(NOT CMAKE_INSTALL_RUNTIMEDIR) + set(CMAKE_INSTALL_RUNTIMEDIR "${CMAKE_INSTALL_PREFIX}/bin") +endif(NOT CMAKE_INSTALL_RUNTIMEDIR) + +set(CMAKE_INSTALL_LIBDIR "" CACHE PATH "Specify the output directory for libraries (default is lib)") +if(NOT CMAKE_INSTALL_LIBDIR) + set(CMAKE_INSTALL_LIBDIR "${CMAKE_INSTALL_PREFIX}/lib${LIB_SUFFIX}") +endif(NOT CMAKE_INSTALL_LIBDIR) + +set(CMAKE_INSTALL_INCLUDEDIR "" CACHE PATH "Specify the output directory for header files (default is include)") +if(NOT CMAKE_INSTALL_INCLUDEDIR) + set(CMAKE_INSTALL_INCLUDEDIR "${CMAKE_INSTALL_PREFIX}/include") +endif(NOT CMAKE_INSTALL_INCLUDEDIR) + +set(CMAKE_INSTALL_PKGCONFIGDIR "" CACHE PATH "Specify the output directory for pkgconfig files (default is lib/pkgconfig)") +if(NOT CMAKE_INSTALL_PKGCONFIGDIR) + set(CMAKE_INSTALL_PKGCONFIGDIR "${CMAKE_INSTALL_LIBDIR}/pkgconfig") +endif(NOT CMAKE_INSTALL_PKGCONFIGDIR) + +## Build type ## +if(NOT CMAKE_BUILD_TYPE) + set(CMAKE_BUILD_TYPE "Release") +elseif(CMAKE_BUILD_TYPE STREQUAL "Debug") + set(CMAKE_VERBOSE_MAKEFILE ON) +endif(NOT CMAKE_BUILD_TYPE) + +## Compiler options ## +if(MSVC) + append_c_compiler_flags("/W4" "VC" CMAKE_C_FLAGS) + append_c_compiler_flags("/Oi;/Ot;/Ox;/Oy" "VC" CMAKE_C_FLAGS_RELEASE) + if(USE_OPENMP) + append_c_compiler_flags("/openmp" "VC" CMAKE_C_FLAGS) + endif(USE_OPENMP) +elseif(BORLAND) + append_c_compiler_flags("-w" "BCC" CMAKE_C_FLAGS) + append_c_compiler_flags("-Oi;-Og;-Os;-Ov;-Ox" "BCC" CMAKE_C_FLAGS_RELEASE) +else(MSVC) + if(CMAKE_COMPILER_IS_GNUCC) + append_c_compiler_flags("-Wall" "GCC" CMAKE_C_FLAGS) + append_c_compiler_flags("-fomit-frame-pointer" "GCC" CMAKE_C_FLAGS_RELEASE) + if(USE_OPENMP) + append_c_compiler_flags("-fopenmp" "GCC" CMAKE_C_FLAGS) + endif(USE_OPENMP) + else(CMAKE_COMPILER_IS_GNUCC) + append_c_compiler_flags("-Wall" "UNKNOWN" CMAKE_C_FLAGS) + append_c_compiler_flags("-fomit-frame-pointer" "UNKNOWN" CMAKE_C_FLAGS_RELEASE) + if(USE_OPENMP) + append_c_compiler_flags("-fopenmp;-openmp;-omp" "UNKNOWN" CMAKE_C_FLAGS) + endif(USE_OPENMP) + endif(CMAKE_COMPILER_IS_GNUCC) +endif(MSVC) + +## Add definitions ## +add_definitions(-DHAVE_CONFIG_H=1 -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS) + +## Add subdirectories ## +add_subdirectory(pkgconfig) +add_subdirectory(include) +add_subdirectory(lib) +if(BUILD_EXAMPLES) + add_subdirectory(examples) +endif(BUILD_EXAMPLES) + +## Add 'uninstall' target ## +CONFIGURE_FILE( + "${CMAKE_CURRENT_SOURCE_DIR}/CMakeModules/cmake_uninstall.cmake.in" + "${CMAKE_CURRENT_BINARY_DIR}/CMakeModules/cmake_uninstall.cmake" + IMMEDIATE @ONLY) +ADD_CUSTOM_TARGET(uninstall + "${CMAKE_COMMAND}" -P "${CMAKE_CURRENT_BINARY_DIR}/CMakeModules/cmake_uninstall.cmake") diff --git a/tools/apultra/src/libdivsufsort/CMakeModules/AppendCompilerFlags.cmake b/tools/apultra/src/libdivsufsort/CMakeModules/AppendCompilerFlags.cmake new file mode 100644 index 0000000..58d3f99 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/CMakeModules/AppendCompilerFlags.cmake @@ -0,0 +1,38 @@ +include(CheckCSourceCompiles) +include(CheckCXXSourceCompiles) + +macro(append_c_compiler_flags _flags _name _result) + set(SAFE_CMAKE_REQUIRED_FLAGS ${CMAKE_REQUIRED_FLAGS}) + string(REGEX REPLACE "[-+/ ]" "_" cname "${_name}") + string(TOUPPER "${cname}" cname) + foreach(flag ${_flags}) + string(REGEX REPLACE "^[-+/ ]+(.*)[-+/ ]*$" "\\1" flagname "${flag}") + string(REGEX REPLACE "[-+/ ]" "_" flagname "${flagname}") + string(TOUPPER "${flagname}" flagname) + set(have_flag "HAVE_${cname}_${flagname}") + set(CMAKE_REQUIRED_FLAGS "${flag}") + check_c_source_compiles("int main() { return 0; }" ${have_flag}) + if(${have_flag}) + set(${_result} "${${_result}} ${flag}") + endif(${have_flag}) + endforeach(flag) + set(CMAKE_REQUIRED_FLAGS ${SAFE_CMAKE_REQUIRED_FLAGS}) +endmacro(append_c_compiler_flags) + +macro(append_cxx_compiler_flags _flags _name _result) + set(SAFE_CMAKE_REQUIRED_FLAGS ${CMAKE_REQUIRED_FLAGS}) + string(REGEX REPLACE "[-+/ ]" "_" cname "${_name}") + string(TOUPPER "${cname}" cname) + foreach(flag ${_flags}) + string(REGEX REPLACE "^[-+/ ]+(.*)[-+/ ]*$" "\\1" flagname "${flag}") + string(REGEX REPLACE "[-+/ ]" "_" flagname "${flagname}") + string(TOUPPER "${flagname}" flagname) + set(have_flag "HAVE_${cname}_${flagname}") + set(CMAKE_REQUIRED_FLAGS "${flag}") + check_cxx_source_compiles("int main() { return 0; }" ${have_flag}) + if(${have_flag}) + set(${_result} "${${_result}} ${flag}") + endif(${have_flag}) + endforeach(flag) + set(CMAKE_REQUIRED_FLAGS ${SAFE_CMAKE_REQUIRED_FLAGS}) +endmacro(append_cxx_compiler_flags) diff --git a/tools/apultra/src/libdivsufsort/CMakeModules/CheckFunctionKeywords.cmake b/tools/apultra/src/libdivsufsort/CMakeModules/CheckFunctionKeywords.cmake new file mode 100644 index 0000000..44601fd --- /dev/null +++ b/tools/apultra/src/libdivsufsort/CMakeModules/CheckFunctionKeywords.cmake @@ -0,0 +1,15 @@ +include(CheckCSourceCompiles) + +macro(check_function_keywords _wordlist) + set(${_result} "") + foreach(flag ${_wordlist}) + string(REGEX REPLACE "[-+/ ()]" "_" flagname "${flag}") + string(TOUPPER "${flagname}" flagname) + set(have_flag "HAVE_${flagname}") + check_c_source_compiles("${flag} void func(); void func() { } int main() { func(); return 0; }" ${have_flag}) + if(${have_flag} AND NOT ${_result}) + set(${_result} "${flag}") +# break() + endif(${have_flag} AND NOT ${_result}) + endforeach(flag) +endmacro(check_function_keywords) diff --git a/tools/apultra/src/libdivsufsort/CMakeModules/CheckLFS.cmake b/tools/apultra/src/libdivsufsort/CMakeModules/CheckLFS.cmake new file mode 100644 index 0000000..e2b0099 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/CMakeModules/CheckLFS.cmake @@ -0,0 +1,109 @@ +## Checks for large file support ## +include(CheckIncludeFile) +include(CheckSymbolExists) +include(CheckTypeSize) + +macro(check_lfs _isenable) + set(LFS_OFF_T "") + set(LFS_FOPEN "") + set(LFS_FSEEK "") + set(LFS_FTELL "") + set(LFS_PRID "") + + if(${_isenable}) + set(SAFE_CMAKE_REQUIRED_DEFINITIONS "${CMAKE_REQUIRED_DEFINITIONS}") + set(CMAKE_REQUIRED_DEFINITIONS ${CMAKE_REQUIRED_DEFINITIONS} + -D_LARGEFILE_SOURCE -D_LARGE_FILES -D_FILE_OFFSET_BITS=64 + -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS) + + check_include_file("sys/types.h" HAVE_SYS_TYPES_H) + check_include_file("inttypes.h" HAVE_INTTYPES_H) + check_include_file("stddef.h" HAVE_STDDEF_H) + check_include_file("stdint.h" HAVE_STDINT_H) + + # LFS type1: 8 <= sizeof(off_t), fseeko, ftello + check_type_size("off_t" SIZEOF_OFF_T) + if(SIZEOF_OFF_T GREATER 7) + check_symbol_exists("fseeko" "stdio.h" HAVE_FSEEKO) + check_symbol_exists("ftello" "stdio.h" HAVE_FTELLO) + if(HAVE_FSEEKO AND HAVE_FTELLO) + set(LFS_OFF_T "off_t") + set(LFS_FOPEN "fopen") + set(LFS_FSEEK "fseeko") + set(LFS_FTELL "ftello") + check_symbol_exists("PRIdMAX" "inttypes.h" HAVE_PRIDMAX) + if(HAVE_PRIDMAX) + set(LFS_PRID "PRIdMAX") + else(HAVE_PRIDMAX) + check_type_size("long" SIZEOF_LONG) + check_type_size("int" SIZEOF_INT) + if(SIZEOF_OFF_T GREATER SIZEOF_LONG) + set(LFS_PRID "\"lld\"") + elseif(SIZEOF_LONG GREATER SIZEOF_INT) + set(LFS_PRID "\"ld\"") + else(SIZEOF_OFF_T GREATER SIZEOF_LONG) + set(LFS_PRID "\"d\"") + endif(SIZEOF_OFF_T GREATER SIZEOF_LONG) + endif(HAVE_PRIDMAX) + endif(HAVE_FSEEKO AND HAVE_FTELLO) + endif(SIZEOF_OFF_T GREATER 7) + + # LFS type2: 8 <= sizeof(off64_t), fopen64, fseeko64, ftello64 + if(NOT LFS_OFF_T) + check_type_size("off64_t" SIZEOF_OFF64_T) + if(SIZEOF_OFF64_T GREATER 7) + check_symbol_exists("fopen64" "stdio.h" HAVE_FOPEN64) + check_symbol_exists("fseeko64" "stdio.h" HAVE_FSEEKO64) + check_symbol_exists("ftello64" "stdio.h" HAVE_FTELLO64) + if(HAVE_FOPEN64 AND HAVE_FSEEKO64 AND HAVE_FTELLO64) + set(LFS_OFF_T "off64_t") + set(LFS_FOPEN "fopen64") + set(LFS_FSEEK "fseeko64") + set(LFS_FTELL "ftello64") + check_symbol_exists("PRIdMAX" "inttypes.h" HAVE_PRIDMAX) + if(HAVE_PRIDMAX) + set(LFS_PRID "PRIdMAX") + else(HAVE_PRIDMAX) + check_type_size("long" SIZEOF_LONG) + check_type_size("int" SIZEOF_INT) + if(SIZEOF_OFF64_T GREATER SIZEOF_LONG) + set(LFS_PRID "\"lld\"") + elseif(SIZEOF_LONG GREATER SIZEOF_INT) + set(LFS_PRID "\"ld\"") + else(SIZEOF_OFF64_T GREATER SIZEOF_LONG) + set(LFS_PRID "\"d\"") + endif(SIZEOF_OFF64_T GREATER SIZEOF_LONG) + endif(HAVE_PRIDMAX) + endif(HAVE_FOPEN64 AND HAVE_FSEEKO64 AND HAVE_FTELLO64) + endif(SIZEOF_OFF64_T GREATER 7) + endif(NOT LFS_OFF_T) + + # LFS type3: 8 <= sizeof(__int64), _fseeki64, _ftelli64 + if(NOT LFS_OFF_T) + check_type_size("__int64" SIZEOF___INT64) + if(SIZEOF___INT64 GREATER 7) + check_symbol_exists("_fseeki64" "stdio.h" HAVE__FSEEKI64) + check_symbol_exists("_ftelli64" "stdio.h" HAVE__FTELLI64) + if(HAVE__FSEEKI64 AND HAVE__FTELLI64) + set(LFS_OFF_T "__int64") + set(LFS_FOPEN "fopen") + set(LFS_FSEEK "_fseeki64") + set(LFS_FTELL "_ftelli64") + set(LFS_PRID "\"I64d\"") + endif(HAVE__FSEEKI64 AND HAVE__FTELLI64) + endif(SIZEOF___INT64 GREATER 7) + endif(NOT LFS_OFF_T) + + set(CMAKE_REQUIRED_DEFINITIONS "${SAFE_CMAKE_REQUIRED_DEFINITIONS}") + endif(${_isenable}) + + if(NOT LFS_OFF_T) + ## not found + set(LFS_OFF_T "long") + set(LFS_FOPEN "fopen") + set(LFS_FSEEK "fseek") + set(LFS_FTELL "ftell") + set(LFS_PRID "\"ld\"") + endif(NOT LFS_OFF_T) + +endmacro(check_lfs) diff --git a/tools/apultra/src/libdivsufsort/CMakeModules/ProjectCPack.cmake b/tools/apultra/src/libdivsufsort/CMakeModules/ProjectCPack.cmake new file mode 100644 index 0000000..7c105f9 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/CMakeModules/ProjectCPack.cmake @@ -0,0 +1,38 @@ +# If the cmake version includes cpack, use it +IF(EXISTS "${CMAKE_ROOT}/Modules/CPack.cmake") + SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY "${PROJECT_DESCRIPTION}") + SET(CPACK_PACKAGE_VENDOR "${PROJECT_VENDOR}") + SET(CPACK_PACKAGE_DESCRIPTION_FILE "${CMAKE_CURRENT_SOURCE_DIR}/README.md") + SET(CPACK_RESOURCE_FILE_LICENSE "${CMAKE_CURRENT_SOURCE_DIR}/LICENSE") + SET(CPACK_PACKAGE_VERSION_MAJOR "${PROJECT_VERSION_MAJOR}") + SET(CPACK_PACKAGE_VERSION_MINOR "${PROJECT_VERSION_MINOR}") + SET(CPACK_PACKAGE_VERSION_PATCH "${PROJECT_VERSION_PATCH}") +# SET(CPACK_PACKAGE_INSTALL_DIRECTORY "${PROJECT_NAME} ${PROJECT_VERSION}") + SET(CPACK_SOURCE_PACKAGE_FILE_NAME "${PROJECT_NAME}-${PROJECT_VERSION_FULL}") + + IF(NOT DEFINED CPACK_SYSTEM_NAME) + SET(CPACK_SYSTEM_NAME "${CMAKE_SYSTEM_NAME}-${CMAKE_SYSTEM_PROCESSOR}") + ENDIF(NOT DEFINED CPACK_SYSTEM_NAME) + + IF(${CPACK_SYSTEM_NAME} MATCHES Windows) + IF(CMAKE_CL_64) + SET(CPACK_SYSTEM_NAME win64-${CMAKE_SYSTEM_PROCESSOR}) + ELSE(CMAKE_CL_64) + SET(CPACK_SYSTEM_NAME win32-${CMAKE_SYSTEM_PROCESSOR}) + ENDIF(CMAKE_CL_64) + ENDIF(${CPACK_SYSTEM_NAME} MATCHES Windows) + + IF(NOT DEFINED CPACK_PACKAGE_FILE_NAME) + SET(CPACK_PACKAGE_FILE_NAME "${CPACK_SOURCE_PACKAGE_FILE_NAME}-${CPACK_SYSTEM_NAME}") + ENDIF(NOT DEFINED CPACK_PACKAGE_FILE_NAME) + + SET(CPACK_PACKAGE_CONTACT "${PROJECT_CONTACT}") + IF(UNIX) + SET(CPACK_STRIP_FILES "") + SET(CPACK_SOURCE_STRIP_FILES "") +# SET(CPACK_PACKAGE_EXECUTABLES "ccmake" "CMake") + ENDIF(UNIX) + SET(CPACK_SOURCE_IGNORE_FILES "/CVS/" "/build/" "/\\\\.build/" "/\\\\.svn/" "~$") + # include CPack model once all variables are set + INCLUDE(CPack) +ENDIF(EXISTS "${CMAKE_ROOT}/Modules/CPack.cmake") diff --git a/tools/apultra/src/libdivsufsort/CMakeModules/cmake_uninstall.cmake.in b/tools/apultra/src/libdivsufsort/CMakeModules/cmake_uninstall.cmake.in new file mode 100644 index 0000000..8366a83 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/CMakeModules/cmake_uninstall.cmake.in @@ -0,0 +1,36 @@ +IF(NOT EXISTS "@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt") + MESSAGE(FATAL_ERROR "Cannot find install manifest: \"@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt\"") +ENDIF(NOT EXISTS "@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt") + +FILE(READ "@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt" files) +STRING(REGEX REPLACE "\n" ";" files "${files}") + +SET(NUM 0) +FOREACH(file ${files}) + IF(EXISTS "$ENV{DESTDIR}${file}") + MESSAGE(STATUS "Looking for \"$ENV{DESTDIR}${file}\" - found") + SET(UNINSTALL_CHECK_${NUM} 1) + ELSE(EXISTS "$ENV{DESTDIR}${file}") + MESSAGE(STATUS "Looking for \"$ENV{DESTDIR}${file}\" - not found") + SET(UNINSTALL_CHECK_${NUM} 0) + ENDIF(EXISTS "$ENV{DESTDIR}${file}") + MATH(EXPR NUM "1 + ${NUM}") +ENDFOREACH(file) + +SET(NUM 0) +FOREACH(file ${files}) + IF(${UNINSTALL_CHECK_${NUM}}) + MESSAGE(STATUS "Uninstalling \"$ENV{DESTDIR}${file}\"") + EXEC_PROGRAM( + "@CMAKE_COMMAND@" ARGS "-E remove \"$ENV{DESTDIR}${file}\"" + OUTPUT_VARIABLE rm_out + RETURN_VALUE rm_retval + ) + IF(NOT "${rm_retval}" STREQUAL 0) + MESSAGE(FATAL_ERROR "Problem when removing \"$ENV{DESTDIR}${file}\"") + ENDIF(NOT "${rm_retval}" STREQUAL 0) + ENDIF(${UNINSTALL_CHECK_${NUM}}) + MATH(EXPR NUM "1 + ${NUM}") +ENDFOREACH(file) + +FILE(REMOVE "@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt") diff --git a/tools/apultra/src/libdivsufsort/LICENSE b/tools/apultra/src/libdivsufsort/LICENSE new file mode 100644 index 0000000..249efa4 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/LICENSE @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2003 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. diff --git a/tools/apultra/src/libdivsufsort/README.md b/tools/apultra/src/libdivsufsort/README.md new file mode 100644 index 0000000..381a188 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/README.md @@ -0,0 +1,140 @@ +# libdivsufsort + +libdivsufsort is a software library that implements a lightweight suffix array construction algorithm. + +## News +* 2015-03-21: The project has moved from [Google Code](http://code.google.com/p/libdivsufsort/) to [GitHub](https://github.com/y-256/libdivsufsort) + +## Introduction +This library provides a simple and an efficient C API to construct a suffix array and a Burrows-Wheeler transformed string from a given string over a constant-size alphabet. +The algorithm runs in O(n log n) worst-case time using only 5n+O(1) bytes of memory space, where n is the length of +the string. + +## Build requirements +* An ANSI C Compiler (e.g. GNU GCC) +* [CMake](http://www.cmake.org/ "CMake") version 2.4.2 or newer +* CMake-supported build tool + +## Building on GNU/Linux +1. Get the source code from GitHub. You can either + * use git to clone the repository + ``` + git clone https://github.com/y-256/libdivsufsort.git + ``` + * or download a [zip file](../../archive/master.zip) directly +2. Create a `build` directory in the package source directory. +```shell +$ cd libdivsufsort +$ mkdir build +$ cd build +``` +3. Configure the package for your system. +If you want to install to a different location, change the -DCMAKE_INSTALL_PREFIX option. +```shell +$ cmake -DCMAKE_BUILD_TYPE="Release" \ +-DCMAKE_INSTALL_PREFIX="/usr/local" .. +``` +4. Compile the package. +```shell +$ make +``` +5. (Optional) Install the library and header files. +```shell +$ sudo make install +``` + +## API +```c +/* Data types */ +typedef int32_t saint_t; +typedef int32_t saidx_t; +typedef uint8_t sauchar_t; + +/* + * Constructs the suffix array of a given string. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The output array or suffixes. + * @param n The length of the given string. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +saint_t +divsufsort(const sauchar_t *T, saidx_t *SA, saidx_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. + */ +saidx_t +divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n); +``` + +## Example Usage +```c +#include +#include +#include + +#include + +int main() { + // intput data + char *Text = "abracadabra"; + int n = strlen(Text); + int i, j; + + // allocate + int *SA = (int *)malloc(n * sizeof(int)); + + // sort + divsufsort((unsigned char *)Text, SA, n); + + // output + for(i = 0; i < n; ++i) { + printf("SA[%2d] = %2d: ", i, SA[i]); + for(j = SA[i]; j < n; ++j) { + printf("%c", Text[j]); + } + printf("$\n"); + } + + // deallocate + free(SA); + + return 0; +} +``` +See the [examples](examples) directory for a few other examples. + +## Benchmarks +See [Benchmarks](https://github.com/y-256/libdivsufsort/blob/wiki/SACA_Benchmarks.md) page for details. + +## License +libdivsufsort is released under the [MIT license](LICENSE "MIT license"). +> The MIT License (MIT) +> +> Copyright (c) 2003 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. + +## Author +* Yuta Mori diff --git a/tools/apultra/src/libdivsufsort/VERSION.cmake b/tools/apultra/src/libdivsufsort/VERSION.cmake new file mode 100644 index 0000000..3f11ac1 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/VERSION.cmake @@ -0,0 +1,23 @@ +set(PROJECT_VERSION_MAJOR "2") +set(PROJECT_VERSION_MINOR "0") +set(PROJECT_VERSION_PATCH "2") +set(PROJECT_VERSION_EXTRA "-1") +set(PROJECT_VERSION "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}") +set(PROJECT_VERSION_FULL "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}${PROJECT_VERSION_EXTRA}") + +set(LIBRARY_VERSION "3.0.1") +set(LIBRARY_SOVERSION "3") + +## Git revision number ## +if(EXISTS "${CMAKE_CURRENT_SOURCE_DIR}/.git") + execute_process(COMMAND git describe --tags HEAD + WORKING_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}" + OUTPUT_VARIABLE GIT_DESCRIBE_TAGS ERROR_QUIET) + if(GIT_DESCRIBE_TAGS) + string(REGEX REPLACE "^v(.*)" "\\1" GIT_REVISION "${GIT_DESCRIBE_TAGS}") + string(STRIP "${GIT_REVISION}" GIT_REVISION) + if(GIT_REVISION) + set(PROJECT_VERSION_FULL "${GIT_REVISION}") + endif(GIT_REVISION) + endif(GIT_DESCRIBE_TAGS) +endif(EXISTS "${CMAKE_CURRENT_SOURCE_DIR}/.git") diff --git a/tools/apultra/src/libdivsufsort/examples/CMakeLists.txt b/tools/apultra/src/libdivsufsort/examples/CMakeLists.txt new file mode 100644 index 0000000..e801c81 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/examples/CMakeLists.txt @@ -0,0 +1,11 @@ +## Add definitions ## +add_definitions(-D_LARGEFILE_SOURCE -D_LARGE_FILES -D_FILE_OFFSET_BITS=64) + +## Targets ## +include_directories("${CMAKE_CURRENT_SOURCE_DIR}/../include" + "${CMAKE_CURRENT_BINARY_DIR}/../include") +link_directories("${CMAKE_CURRENT_BINARY_DIR}/../lib") +foreach(src suftest mksary sasearch bwt unbwt) + add_executable(${src} ${src}.c) + target_link_libraries(${src} divsufsort) +endforeach(src) diff --git a/tools/apultra/src/libdivsufsort/examples/bwt.c b/tools/apultra/src/libdivsufsort/examples/bwt.c new file mode 100644 index 0000000..5a362d0 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/examples/bwt.c @@ -0,0 +1,220 @@ +/* + * bwt.c 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. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif +#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_SYS_TYPES_H +# include +#endif +#if HAVE_IO_H && HAVE_FCNTL_H +# include +# include +#endif +#include +#include +#include "lfs.h" + + +static +size_t +write_int(FILE *fp, saidx_t n) { + unsigned char c[4]; + c[0] = (unsigned char)((n >> 0) & 0xff), c[1] = (unsigned char)((n >> 8) & 0xff), + c[2] = (unsigned char)((n >> 16) & 0xff), c[3] = (unsigned char)((n >> 24) & 0xff); + return fwrite(c, sizeof(unsigned char), 4, fp); +} + +static +void +print_help(const char *progname, int status) { + fprintf(stderr, + "bwt, a burrows-wheeler transform program, version %s.\n", + divsufsort_version()); + fprintf(stderr, "usage: %s [-b num] INFILE OUTFILE\n", progname); + fprintf(stderr, " -b num set block size to num MiB [1..512] (default: 32)\n\n"); + exit(status); +} + +int +main(int argc, const char *argv[]) { + FILE *fp, *ofp; + const char *fname, *ofname; + sauchar_t *T; + saidx_t *SA; + LFS_OFF_T n; + size_t m; + saidx_t pidx; + clock_t start,finish; + saint_t i, blocksize = 32, needclose = 3; + + /* Check arguments. */ + if((argc == 1) || + (strcmp(argv[1], "-h") == 0) || + (strcmp(argv[1], "--help") == 0)) { print_help(argv[0], EXIT_SUCCESS); } + if((argc != 3) && (argc != 5)) { print_help(argv[0], EXIT_FAILURE); } + i = 1; + if(argc == 5) { + if(strcmp(argv[i], "-b") != 0) { print_help(argv[0], EXIT_FAILURE); } + blocksize = atoi(argv[i + 1]); + if(blocksize < 0) { blocksize = 1; } + else if(512 < blocksize) { blocksize = 512; } + i += 2; + } + blocksize <<= 20; + + /* Open a file for reading. */ + if(strcmp(argv[i], "-") != 0) { +#if HAVE_FOPEN_S + if(fopen_s(&fp, fname = argv[i], "rb") != 0) { +#else + if((fp = LFS_FOPEN(fname = argv[i], "rb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + } else { +#if HAVE__SETMODE && HAVE__FILENO + if(_setmode(_fileno(stdin), _O_BINARY) == -1) { + fprintf(stderr, "%s: Cannot set mode: ", argv[0]); + perror(NULL); + exit(EXIT_FAILURE); + } +#endif + fp = stdin; + fname = "stdin"; + needclose ^= 1; + } + i += 1; + + /* Open a file for writing. */ + if(strcmp(argv[i], "-") != 0) { +#if HAVE_FOPEN_S + if(fopen_s(&ofp, ofname = argv[i], "wb") != 0) { +#else + if((ofp = LFS_FOPEN(ofname = argv[i], "wb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], ofname); + perror(NULL); + exit(EXIT_FAILURE); + } + } else { +#if HAVE__SETMODE && HAVE__FILENO + if(_setmode(_fileno(stdout), _O_BINARY) == -1) { + fprintf(stderr, "%s: Cannot set mode: ", argv[0]); + perror(NULL); + exit(EXIT_FAILURE); + } +#endif + ofp = stdout; + ofname = "stdout"; + needclose ^= 2; + } + + /* Get the file size. */ + if(LFS_FSEEK(fp, 0, SEEK_END) == 0) { + n = LFS_FTELL(fp); + rewind(fp); + if(n < 0) { + fprintf(stderr, "%s: Cannot ftell `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + if(0x20000000L < n) { n = 0x20000000L; } + if((blocksize == 0) || (n < blocksize)) { blocksize = (saidx_t)n; } + } else if(blocksize == 0) { blocksize = 32 << 20; } + + /* Allocate 5blocksize bytes of memory. */ + T = (sauchar_t *)malloc(blocksize * sizeof(sauchar_t)); + SA = (saidx_t *)malloc(blocksize * sizeof(saidx_t)); + if((T == NULL) || (SA == NULL)) { + fprintf(stderr, "%s: Cannot allocate memory.\n", argv[0]); + exit(EXIT_FAILURE); + } + + /* Write the blocksize. */ + if(write_int(ofp, blocksize) != 4) { + fprintf(stderr, "%s: Cannot write to `%s': ", argv[0], ofname); + perror(NULL); + exit(EXIT_FAILURE); + } + + fprintf(stderr, " BWT (blocksize %" PRIdSAINT_T ") ... ", blocksize); + start = clock(); + for(n = 0; 0 < (m = fread(T, sizeof(sauchar_t), blocksize, fp)); n += m) { + /* Burrows-Wheeler Transform. */ + pidx = divbwt(T, T, SA, m); + if(pidx < 0) { + fprintf(stderr, "%s (bw_transform): %s.\n", + argv[0], + (pidx == -1) ? "Invalid arguments" : "Cannot allocate memory"); + exit(EXIT_FAILURE); + } + + /* Write the bwted data. */ + if((write_int(ofp, pidx) != 4) || + (fwrite(T, sizeof(sauchar_t), m, ofp) != m)) { + fprintf(stderr, "%s: Cannot write to `%s': ", argv[0], ofname); + perror(NULL); + exit(EXIT_FAILURE); + } + } + if(ferror(fp)) { + fprintf(stderr, "%s: Cannot read from `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + finish = clock(); + fprintf(stderr, "%" PRIdOFF_T " bytes: %.4f sec\n", + n, (double)(finish - start) / (double)CLOCKS_PER_SEC); + + /* Close files */ + if(needclose & 1) { fclose(fp); } + if(needclose & 2) { fclose(ofp); } + + /* Deallocate memory. */ + free(SA); + free(T); + + return 0; +} diff --git a/tools/apultra/src/libdivsufsort/examples/mksary.c b/tools/apultra/src/libdivsufsort/examples/mksary.c new file mode 100644 index 0000000..b48177c --- /dev/null +++ b/tools/apultra/src/libdivsufsort/examples/mksary.c @@ -0,0 +1,193 @@ +/* + * mksary.c 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. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif +#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_SYS_TYPES_H +# include +#endif +#if HAVE_IO_H && HAVE_FCNTL_H +# include +# include +#endif +#include +#include +#include "lfs.h" + + +static +void +print_help(const char *progname, int status) { + fprintf(stderr, + "mksary, a simple suffix array builder, version %s.\n", + divsufsort_version()); + fprintf(stderr, "usage: %s INFILE OUTFILE\n\n", progname); + exit(status); +} + +int +main(int argc, const char *argv[]) { + FILE *fp, *ofp; + const char *fname, *ofname; + sauchar_t *T; + saidx_t *SA; + LFS_OFF_T n; + clock_t start, finish; + saint_t needclose = 3; + + /* Check arguments. */ + if((argc == 1) || + (strcmp(argv[1], "-h") == 0) || + (strcmp(argv[1], "--help") == 0)) { print_help(argv[0], EXIT_SUCCESS); } + if(argc != 3) { print_help(argv[0], EXIT_FAILURE); } + + /* Open a file for reading. */ + if(strcmp(argv[1], "-") != 0) { +#if HAVE_FOPEN_S + if(fopen_s(&fp, fname = argv[1], "rb") != 0) { +#else + if((fp = LFS_FOPEN(fname = argv[1], "rb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + } else { +#if HAVE__SETMODE && HAVE__FILENO + if(_setmode(_fileno(stdin), _O_BINARY) == -1) { + fprintf(stderr, "%s: Cannot set mode: ", argv[0]); + perror(NULL); + exit(EXIT_FAILURE); + } +#endif + fp = stdin; + fname = "stdin"; + needclose ^= 1; + } + + /* Open a file for writing. */ + if(strcmp(argv[2], "-") != 0) { +#if HAVE_FOPEN_S + if(fopen_s(&ofp, ofname = argv[2], "wb") != 0) { +#else + if((ofp = LFS_FOPEN(ofname = argv[2], "wb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], ofname); + perror(NULL); + exit(EXIT_FAILURE); + } + } else { +#if HAVE__SETMODE && HAVE__FILENO + if(_setmode(_fileno(stdout), _O_BINARY) == -1) { + fprintf(stderr, "%s: Cannot set mode: ", argv[0]); + perror(NULL); + exit(EXIT_FAILURE); + } +#endif + ofp = stdout; + ofname = "stdout"; + needclose ^= 2; + } + + /* Get the file size. */ + if(LFS_FSEEK(fp, 0, SEEK_END) == 0) { + n = LFS_FTELL(fp); + rewind(fp); + if(n < 0) { + fprintf(stderr, "%s: Cannot ftell `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + if(0x7fffffff <= n) { + fprintf(stderr, "%s: Input file `%s' is too big.\n", argv[0], fname); + exit(EXIT_FAILURE); + } + } else { + fprintf(stderr, "%s: Cannot fseek `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + + /* Allocate 5blocksize bytes of memory. */ + T = (sauchar_t *)malloc((size_t)n * sizeof(sauchar_t)); + SA = (saidx_t *)malloc((size_t)n * sizeof(saidx_t)); + if((T == NULL) || (SA == NULL)) { + fprintf(stderr, "%s: Cannot allocate memory.\n", argv[0]); + exit(EXIT_FAILURE); + } + + /* Read n bytes of data. */ + if(fread(T, sizeof(sauchar_t), (size_t)n, fp) != (size_t)n) { + fprintf(stderr, "%s: %s `%s': ", + argv[0], + (ferror(fp) || !feof(fp)) ? "Cannot read from" : "Unexpected EOF in", + fname); + perror(NULL); + exit(EXIT_FAILURE); + } + if(needclose & 1) { fclose(fp); } + + /* Construct the suffix array. */ + fprintf(stderr, "%s: %" PRIdOFF_T " bytes ... ", fname, n); + start = clock(); + if(divsufsort(T, SA, (saidx_t)n) != 0) { + fprintf(stderr, "%s: Cannot allocate memory.\n", argv[0]); + exit(EXIT_FAILURE); + } + finish = clock(); + fprintf(stderr, "%.4f sec\n", (double)(finish - start) / (double)CLOCKS_PER_SEC); + + /* Write the suffix array. */ + if(fwrite(SA, sizeof(saidx_t), (size_t)n, ofp) != (size_t)n) { + fprintf(stderr, "%s: Cannot write to `%s': ", argv[0], ofname); + perror(NULL); + exit(EXIT_FAILURE); + } + if(needclose & 2) { fclose(ofp); } + + /* Deallocate memory. */ + free(SA); + free(T); + + return 0; +} diff --git a/tools/apultra/src/libdivsufsort/examples/sasearch.c b/tools/apultra/src/libdivsufsort/examples/sasearch.c new file mode 100644 index 0000000..7e5ca4f --- /dev/null +++ b/tools/apultra/src/libdivsufsort/examples/sasearch.c @@ -0,0 +1,165 @@ +/* + * sasearch.c 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. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif +#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_SYS_TYPES_H +# include +#endif +#if HAVE_IO_H && HAVE_FCNTL_H +# include +# include +#endif +#include +#include "lfs.h" + + +static +void +print_help(const char *progname, int status) { + fprintf(stderr, + "sasearch, a simple SA-based full-text search tool, version %s\n", + divsufsort_version()); + fprintf(stderr, "usage: %s PATTERN FILE SAFILE\n\n", progname); + exit(status); +} + +int +main(int argc, const char *argv[]) { + FILE *fp; + const char *P; + sauchar_t *T; + saidx_t *SA; + LFS_OFF_T n; + size_t Psize; + saidx_t i, size, left; + + if((argc == 1) || + (strcmp(argv[1], "-h") == 0) || + (strcmp(argv[1], "--help") == 0)) { print_help(argv[0], EXIT_SUCCESS); } + if(argc != 4) { print_help(argv[0], EXIT_FAILURE); } + + P = argv[1]; + Psize = strlen(P); + + /* Open a file for reading. */ +#if HAVE_FOPEN_S + if(fopen_s(&fp, argv[2], "rb") != 0) { +#else + if((fp = LFS_FOPEN(argv[2], "rb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], argv[2]); + perror(NULL); + exit(EXIT_FAILURE); + } + + /* Get the file size. */ + if(LFS_FSEEK(fp, 0, SEEK_END) == 0) { + n = LFS_FTELL(fp); + rewind(fp); + if(n < 0) { + fprintf(stderr, "%s: Cannot ftell `%s': ", argv[0], argv[2]); + perror(NULL); + exit(EXIT_FAILURE); + } + } else { + fprintf(stderr, "%s: Cannot fseek `%s': ", argv[0], argv[2]); + perror(NULL); + exit(EXIT_FAILURE); + } + + /* Allocate 5n bytes of memory. */ + T = (sauchar_t *)malloc((size_t)n * sizeof(sauchar_t)); + SA = (saidx_t *)malloc((size_t)n * sizeof(saidx_t)); + if((T == NULL) || (SA == NULL)) { + fprintf(stderr, "%s: Cannot allocate memory.\n", argv[0]); + exit(EXIT_FAILURE); + } + + /* Read n bytes of data. */ + if(fread(T, sizeof(sauchar_t), (size_t)n, fp) != (size_t)n) { + fprintf(stderr, "%s: %s `%s': ", + argv[0], + (ferror(fp) || !feof(fp)) ? "Cannot read from" : "Unexpected EOF in", + argv[2]); + perror(NULL); + exit(EXIT_FAILURE); + } + fclose(fp); + + /* Open the SA file for reading. */ +#if HAVE_FOPEN_S + if(fopen_s(&fp, argv[3], "rb") != 0) { +#else + if((fp = LFS_FOPEN(argv[3], "rb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], argv[3]); + perror(NULL); + exit(EXIT_FAILURE); + } + + /* Read n * sizeof(saidx_t) bytes of data. */ + if(fread(SA, sizeof(saidx_t), (size_t)n, fp) != (size_t)n) { + fprintf(stderr, "%s: %s `%s': ", + argv[0], + (ferror(fp) || !feof(fp)) ? "Cannot read from" : "Unexpected EOF in", + argv[3]); + perror(NULL); + exit(EXIT_FAILURE); + } + fclose(fp); + + /* Search and print */ + size = sa_search(T, (saidx_t)n, + (const sauchar_t *)P, (saidx_t)Psize, + SA, (saidx_t)n, &left); + for(i = 0; i < size; ++i) { + fprintf(stdout, "%" PRIdSAIDX_T "\n", SA[left + i]); + } + + /* Deallocate memory. */ + free(SA); + free(T); + + return 0; +} diff --git a/tools/apultra/src/libdivsufsort/examples/suftest.c b/tools/apultra/src/libdivsufsort/examples/suftest.c new file mode 100644 index 0000000..71892ac --- /dev/null +++ b/tools/apultra/src/libdivsufsort/examples/suftest.c @@ -0,0 +1,164 @@ +/* + * suftest.c 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. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif +#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_SYS_TYPES_H +# include +#endif +#if HAVE_IO_H && HAVE_FCNTL_H +# include +# include +#endif +#include +#include +#include "lfs.h" + + +static +void +print_help(const char *progname, int status) { + fprintf(stderr, + "suftest, a suffixsort tester, version %s.\n", + divsufsort_version()); + fprintf(stderr, "usage: %s FILE\n\n", progname); + exit(status); +} + +int +main(int argc, const char *argv[]) { + FILE *fp; + const char *fname; + sauchar_t *T; + saidx_t *SA; + LFS_OFF_T n; + clock_t start, finish; + saint_t needclose = 1; + + /* Check arguments. */ + if((argc == 1) || + (strcmp(argv[1], "-h") == 0) || + (strcmp(argv[1], "--help") == 0)) { print_help(argv[0], EXIT_SUCCESS); } + if(argc != 2) { print_help(argv[0], EXIT_FAILURE); } + + /* Open a file for reading. */ + if(strcmp(argv[1], "-") != 0) { +#if HAVE_FOPEN_S + if(fopen_s(&fp, fname = argv[1], "rb") != 0) { +#else + if((fp = LFS_FOPEN(fname = argv[1], "rb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + } else { +#if HAVE__SETMODE && HAVE__FILENO + if(_setmode(_fileno(stdin), _O_BINARY) == -1) { + fprintf(stderr, "%s: Cannot set mode: ", argv[0]); + perror(NULL); + exit(EXIT_FAILURE); + } +#endif + fp = stdin; + fname = "stdin"; + needclose = 0; + } + + /* Get the file size. */ + if(LFS_FSEEK(fp, 0, SEEK_END) == 0) { + n = LFS_FTELL(fp); + rewind(fp); + if(n < 0) { + fprintf(stderr, "%s: Cannot ftell `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + if(0x7fffffff <= n) { + fprintf(stderr, "%s: Input file `%s' is too big.\n", argv[0], fname); + exit(EXIT_FAILURE); + } + } else { + fprintf(stderr, "%s: Cannot fseek `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + + /* Allocate 5n bytes of memory. */ + T = (sauchar_t *)malloc((size_t)n * sizeof(sauchar_t)); + SA = (saidx_t *)malloc((size_t)n * sizeof(saidx_t)); + if((T == NULL) || (SA == NULL)) { + fprintf(stderr, "%s: Cannot allocate memory.\n", argv[0]); + exit(EXIT_FAILURE); + } + + /* Read n bytes of data. */ + if(fread(T, sizeof(sauchar_t), (size_t)n, fp) != (size_t)n) { + fprintf(stderr, "%s: %s `%s': ", + argv[0], + (ferror(fp) || !feof(fp)) ? "Cannot read from" : "Unexpected EOF in", + argv[1]); + perror(NULL); + exit(EXIT_FAILURE); + } + if(needclose & 1) { fclose(fp); } + + /* Construct the suffix array. */ + fprintf(stderr, "%s: %" PRIdOFF_T " bytes ... ", fname, n); + start = clock(); + if(divsufsort(T, SA, (saidx_t)n) != 0) { + fprintf(stderr, "%s: Cannot allocate memory.\n", argv[0]); + exit(EXIT_FAILURE); + } + finish = clock(); + fprintf(stderr, "%.4f sec\n", (double)(finish - start) / (double)CLOCKS_PER_SEC); + + /* Check the suffix array. */ + if(sufcheck(T, SA, (saidx_t)n, 1) != 0) { exit(EXIT_FAILURE); } + + /* Deallocate memory. */ + free(SA); + free(T); + + return 0; +} diff --git a/tools/apultra/src/libdivsufsort/examples/unbwt.c b/tools/apultra/src/libdivsufsort/examples/unbwt.c new file mode 100644 index 0000000..c0f19e9 --- /dev/null +++ b/tools/apultra/src/libdivsufsort/examples/unbwt.c @@ -0,0 +1,207 @@ +/* + * unbwt.c 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. + */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif +#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_SYS_TYPES_H +# include +#endif +#if HAVE_IO_H && HAVE_FCNTL_H +# include +# include +#endif +#include +#include +#include "lfs.h" + + +static +size_t +read_int(FILE *fp, saidx_t *n) { + unsigned char c[4]; + size_t m = fread(c, sizeof(unsigned char), 4, fp); + if(m == 4) { + *n = (c[0] << 0) | (c[1] << 8) | + (c[2] << 16) | (c[3] << 24); + } + return m; +} + +static +void +print_help(const char *progname, int status) { + fprintf(stderr, + "unbwt, an inverse burrows-wheeler transform program, version %s.\n", + divsufsort_version()); + fprintf(stderr, "usage: %s INFILE OUTFILE\n\n", progname); + exit(status); +} + +int +main(int argc, const char *argv[]) { + FILE *fp, *ofp; + const char *fname, *ofname; + sauchar_t *T; + saidx_t *A; + LFS_OFF_T n; + size_t m; + saidx_t pidx; + clock_t start, finish; + saint_t err, blocksize, needclose = 3; + + /* Check arguments. */ + if((argc == 1) || + (strcmp(argv[1], "-h") == 0) || + (strcmp(argv[1], "--help") == 0)) { print_help(argv[0], EXIT_SUCCESS); } + if(argc != 3) { print_help(argv[0], EXIT_FAILURE); } + + /* Open a file for reading. */ + if(strcmp(argv[1], "-") != 0) { +#if HAVE_FOPEN_S + if(fopen_s(&fp, fname = argv[1], "rb") != 0) { +#else + if((fp = LFS_FOPEN(fname = argv[1], "rb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + } else { +#if HAVE__SETMODE && HAVE__FILENO + if(_setmode(_fileno(stdin), _O_BINARY) == -1) { + fprintf(stderr, "%s: Cannot set mode: ", argv[0]); + perror(NULL); + exit(EXIT_FAILURE); + } +#endif + fp = stdin; + fname = "stdin"; + needclose ^= 1; + } + + /* Open a file for writing. */ + if(strcmp(argv[2], "-") != 0) { +#if HAVE_FOPEN_S + if(fopen_s(&ofp, ofname = argv[2], "wb") != 0) { +#else + if((ofp = LFS_FOPEN(ofname = argv[2], "wb")) == NULL) { +#endif + fprintf(stderr, "%s: Cannot open file `%s': ", argv[0], ofname); + perror(NULL); + exit(EXIT_FAILURE); + } + } else { +#if HAVE__SETMODE && HAVE__FILENO + if(_setmode(_fileno(stdout), _O_BINARY) == -1) { + fprintf(stderr, "%s: Cannot set mode: ", argv[0]); + perror(NULL); + exit(EXIT_FAILURE); + } +#endif + ofp = stdout; + ofname = "stdout"; + needclose ^= 2; + } + + /* Read the blocksize. */ + if(read_int(fp, &blocksize) != 4) { + fprintf(stderr, "%s: Cannot read from `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + + /* Allocate 5blocksize bytes of memory. */ + T = (sauchar_t *)malloc(blocksize * sizeof(sauchar_t)); + A = (saidx_t *)malloc(blocksize * sizeof(saidx_t)); + if((T == NULL) || (A == NULL)) { + fprintf(stderr, "%s: Cannot allocate memory.\n", argv[0]); + exit(EXIT_FAILURE); + } + + fprintf(stderr, "UnBWT (blocksize %" PRIdSAINT_T ") ... ", blocksize); + start = clock(); + for(n = 0; (m = read_int(fp, &pidx)) != 0; n += m) { + /* Read blocksize bytes of data. */ + if((m != 4) || ((m = fread(T, sizeof(sauchar_t), blocksize, fp)) == 0)) { + fprintf(stderr, "%s: %s `%s': ", + argv[0], + (ferror(fp) || !feof(fp)) ? "Cannot read from" : "Unexpected EOF in", + fname); + perror(NULL); + exit(EXIT_FAILURE); + } + + /* Inverse Burrows-Wheeler Transform. */ + if((err = inverse_bw_transform(T, T, A, m, pidx)) != 0) { + fprintf(stderr, "%s (reverseBWT): %s.\n", + argv[0], + (err == -1) ? "Invalid data" : "Cannot allocate memory"); + exit(EXIT_FAILURE); + } + + /* Write m bytes of data. */ + if(fwrite(T, sizeof(sauchar_t), m, ofp) != m) { + fprintf(stderr, "%s: Cannot write to `%s': ", argv[0], ofname); + perror(NULL); + exit(EXIT_FAILURE); + } + } + if(ferror(fp)) { + fprintf(stderr, "%s: Cannot read from `%s': ", argv[0], fname); + perror(NULL); + exit(EXIT_FAILURE); + } + finish = clock(); + fprintf(stderr, "%" PRIdOFF_T " bytes: %.4f sec\n", + n, (double)(finish - start) / (double)CLOCKS_PER_SEC); + + /* Close files */ + if(needclose & 1) { fclose(fp); } + if(needclose & 2) { fclose(ofp); } + + /* Deallocate memory. */ + free(A); + free(T); + + return 0; +} 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 */ diff --git a/tools/apultra/src/libdivsufsort/pkgconfig/CMakeLists.txt b/tools/apultra/src/libdivsufsort/pkgconfig/CMakeLists.txt new file mode 100644 index 0000000..ee7063c --- /dev/null +++ b/tools/apultra/src/libdivsufsort/pkgconfig/CMakeLists.txt @@ -0,0 +1,9 @@ +## generate libdivsufsort.pc ## +set(W64BIT "") +configure_file("${CMAKE_CURRENT_SOURCE_DIR}/libdivsufsort.pc.cmake" "${CMAKE_CURRENT_BINARY_DIR}/libdivsufsort.pc" @ONLY) +install(FILES "${CMAKE_CURRENT_BINARY_DIR}/libdivsufsort.pc" DESTINATION ${CMAKE_INSTALL_PKGCONFIGDIR}) +if(BUILD_DIVSUFSORT64) + set(W64BIT "64") + configure_file("${CMAKE_CURRENT_SOURCE_DIR}/libdivsufsort.pc.cmake" "${CMAKE_CURRENT_BINARY_DIR}/libdivsufsort64.pc" @ONLY) + install(FILES "${CMAKE_CURRENT_BINARY_DIR}/libdivsufsort64.pc" DESTINATION ${CMAKE_INSTALL_PKGCONFIGDIR}) +endif(BUILD_DIVSUFSORT64) diff --git a/tools/apultra/src/libdivsufsort/pkgconfig/libdivsufsort.pc.cmake b/tools/apultra/src/libdivsufsort/pkgconfig/libdivsufsort.pc.cmake new file mode 100644 index 0000000..6419d1e --- /dev/null +++ b/tools/apultra/src/libdivsufsort/pkgconfig/libdivsufsort.pc.cmake @@ -0,0 +1,11 @@ +prefix=@CMAKE_INSTALL_PREFIX@ +exec_prefix=${prefix} +libdir=@CMAKE_INSTALL_LIBDIR@ +includedir=@CMAKE_INSTALL_INCLUDEDIR@ + +Name: @PROJECT_NAME@@W64BIT@ +Description: @PROJECT_DESCRIPTION@ +Version: @PROJECT_VERSION_FULL@ +URL: @PROJECT_URL@ +Libs: -L${libdir} -ldivsufsort@W64BIT@ +Cflags: -I${includedir} -- cgit v1.2.3