Project import
diff --git a/libdivsufsort/Android.mk b/libdivsufsort/Android.mk
new file mode 100644
index 0000000..97277a2
--- /dev/null
+++ b/libdivsufsort/Android.mk
@@ -0,0 +1,75 @@
+#
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+LOCAL_PATH := $(call my-dir)
+
+libdivsufsort_src_files := \
+ lib/divsufsort.c \
+ lib/sssort.c \
+ lib/trsort.c \
+ lib/utils.c
+
+libdivsufsort_c_includes := \
+ $(LOCAL_PATH)/android_include \
+ $(LOCAL_PATH)/include
+
+libdivsufsort_export_c_include_dirs := $(LOCAL_PATH)/android_include
+
+libdivsufsort_cflags := \
+ -Wall \
+ -Werror \
+ -Wextra \
+ -DHAVE_CONFIG_H=1
+
+# libdivsufsort using 32-bit integers for the suffix array (host static lib)
+include $(CLEAR_VARS)
+LOCAL_MODULE := libdivsufsort
+LOCAL_SRC_FILES := $(libdivsufsort_src_files)
+LOCAL_C_INCLUDES := $(libdivsufsort_c_includes)
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(libdivsufsort_export_c_include_dirs)
+LOCAL_CFLAGS := $(libdivsufsort_cflags)
+include $(BUILD_HOST_STATIC_LIBRARY)
+
+# libdivsufsort using 64-bit integers for the suffix array (host static lib)
+include $(CLEAR_VARS)
+LOCAL_MODULE := libdivsufsort64
+LOCAL_SRC_FILES := $(libdivsufsort_src_files)
+LOCAL_C_INCLUDES := $(libdivsufsort_c_includes)
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(libdivsufsort_export_c_include_dirs)
+LOCAL_CFLAGS := \
+ $(libdivsufsort_cflags) \
+ -DBUILD_DIVSUFSORT64
+include $(BUILD_HOST_STATIC_LIBRARY)
+
+# libdivsufsort using 32-bit integers for the suffix array (target static lib)
+include $(CLEAR_VARS)
+LOCAL_MODULE := libdivsufsort
+LOCAL_SRC_FILES := $(libdivsufsort_src_files)
+LOCAL_C_INCLUDES := $(libdivsufsort_c_includes)
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(libdivsufsort_export_c_include_dirs)
+LOCAL_CFLAGS := $(libdivsufsort_cflags)
+include $(BUILD_STATIC_LIBRARY)
+
+# libdivsufsort using 64-bit integers for the suffix array (target static lib)
+include $(CLEAR_VARS)
+LOCAL_MODULE := libdivsufsort64
+LOCAL_SRC_FILES := $(libdivsufsort_src_files)
+LOCAL_C_INCLUDES := $(libdivsufsort_c_includes)
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(libdivsufsort_export_c_include_dirs)
+LOCAL_CFLAGS := \
+ $(libdivsufsort_cflags) \
+ -DBUILD_DIVSUFSORT64
+include $(BUILD_STATIC_LIBRARY)
diff --git a/libdivsufsort/CHANGELOG.md b/libdivsufsort/CHANGELOG.md
new file mode 100644
index 0000000..fe9d004
--- /dev/null
+++ b/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/libdivsufsort/CMakeLists.txt b/libdivsufsort/CMakeLists.txt
new file mode 100644
index 0000000..7859943
--- /dev/null
+++ b/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/libdivsufsort/CMakeModules/AppendCompilerFlags.cmake b/libdivsufsort/CMakeModules/AppendCompilerFlags.cmake
new file mode 100644
index 0000000..58d3f99
--- /dev/null
+++ b/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/libdivsufsort/CMakeModules/CheckFunctionKeywords.cmake b/libdivsufsort/CMakeModules/CheckFunctionKeywords.cmake
new file mode 100644
index 0000000..44601fd
--- /dev/null
+++ b/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/libdivsufsort/CMakeModules/CheckLFS.cmake b/libdivsufsort/CMakeModules/CheckLFS.cmake
new file mode 100644
index 0000000..e2b0099
--- /dev/null
+++ b/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/libdivsufsort/CMakeModules/ProjectCPack.cmake b/libdivsufsort/CMakeModules/ProjectCPack.cmake
new file mode 100644
index 0000000..7c105f9
--- /dev/null
+++ b/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/libdivsufsort/CMakeModules/cmake_uninstall.cmake.in b/libdivsufsort/CMakeModules/cmake_uninstall.cmake.in
new file mode 100644
index 0000000..8366a83
--- /dev/null
+++ b/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/libdivsufsort/LICENSE b/libdivsufsort/LICENSE
new file mode 100644
index 0000000..249efa4
--- /dev/null
+++ b/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/libdivsufsort/MODULE_LICENSE_MIT b/libdivsufsort/MODULE_LICENSE_MIT
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/libdivsufsort/MODULE_LICENSE_MIT
diff --git a/libdivsufsort/NOTICE b/libdivsufsort/NOTICE
new file mode 120000
index 0000000..7a694c9
--- /dev/null
+++ b/libdivsufsort/NOTICE
@@ -0,0 +1 @@
+LICENSE
\ No newline at end of file
diff --git a/libdivsufsort/README.md b/libdivsufsort/README.md
new file mode 100644
index 0000000..381a188
--- /dev/null
+++ b/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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <divsufsort.h>
+
+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/libdivsufsort/VERSION.cmake b/libdivsufsort/VERSION.cmake
new file mode 100644
index 0000000..f7f7e43
--- /dev/null
+++ b/libdivsufsort/VERSION.cmake
@@ -0,0 +1,22 @@
+set(PROJECT_VERSION_MAJOR "2")
+set(PROJECT_VERSION_MINOR "0")
+set(PROJECT_VERSION_PATCH "2")
+set(PROJECT_VERSION "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}")
+set(PROJECT_VERSION_FULL "${PROJECT_VERSION_MAJOR}.${PROJECT_VERSION_MINOR}.${PROJECT_VERSION_PATCH}")
+
+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/libdivsufsort/android_include/config.h b/libdivsufsort/android_include/config.h
new file mode 100644
index 0000000..6e43b26
--- /dev/null
+++ b/libdivsufsort/android_include/config.h
@@ -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. **/
+#define PROJECT_VERSION_FULL "2.0.1-13-gb7f3d18"
+
+/** Define to 1 if you have the header files. **/
+#define HAVE_INTTYPES_H 1
+#define HAVE_STDDEF_H 1
+#define HAVE_STDINT_H 1
+#define HAVE_STDLIB_H 1
+#define HAVE_STRING_H 1
+#define HAVE_STRINGS_H 1
+#define HAVE_MEMORY_H 1
+#define HAVE_SYS_TYPES_H 1
+
+/** for WinIO **/
+/* #undef HAVE_IO_H */
+/* #undef HAVE_FCNTL_H */
+/* #undef HAVE__SETMODE */
+/* #undef HAVE_SETMODE */
+/* #undef HAVE__FILENO */
+/* #undef HAVE_FOPEN_S */
+/* #undef HAVE__O_BINARY */
+#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/libdivsufsort/android_include/divsufsort.h b/libdivsufsort/android_include/divsufsort.h
new file mode 100644
index 0000000..6d3e648
--- /dev/null
+++ b/libdivsufsort/android_include/divsufsort.h
@@ -0,0 +1,180 @@
+/*
+ * 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 */
+
+#include <inttypes.h>
+
+#ifndef DIVSUFSORT_API
+# ifdef DIVSUFSORT_BUILD_DLL
+# define DIVSUFSORT_API
+# else
+# define DIVSUFSORT_API
+# endif
+#endif
+
+/*- Datatypes -*/
+#ifndef SAUCHAR_T
+#define SAUCHAR_T
+typedef uint8_t sauchar_t;
+#endif /* SAUCHAR_T */
+#ifndef SAINT_T
+#define SAINT_T
+typedef int32_t saint_t;
+#endif /* SAINT_T */
+#ifndef SAIDX_T
+#define SAIDX_T
+typedef int32_t saidx_t;
+#endif /* SAIDX_T */
+#ifndef PRIdSAINT_T
+#define PRIdSAINT_T PRId32
+#endif /* PRIdSAINT_T */
+#ifndef PRIdSAIDX_T
+#define PRIdSAIDX_T PRId32
+#endif /* PRIdSAIDX_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(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.
+ */
+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);
+
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif /* __cplusplus */
+
+#endif /* _DIVSUFSORT_H */
diff --git a/libdivsufsort/android_include/divsufsort64.h b/libdivsufsort/android_include/divsufsort64.h
new file mode 100644
index 0000000..2f1c375
--- /dev/null
+++ b/libdivsufsort/android_include/divsufsort64.h
@@ -0,0 +1,180 @@
+/*
+ * divsufsort64.h for libdivsufsort64
+ * 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 _DIVSUFSORT64_H
+#define _DIVSUFSORT64_H 1
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+#include <inttypes.h>
+
+#ifndef DIVSUFSORT_API
+# ifdef DIVSUFSORT_BUILD_DLL
+# define DIVSUFSORT_API
+# else
+# define DIVSUFSORT_API
+# endif
+#endif
+
+/*- Datatypes -*/
+#ifndef SAUCHAR_T
+#define SAUCHAR_T
+typedef uint8_t sauchar_t;
+#endif /* SAUCHAR_T */
+#ifndef SAINT_T
+#define SAINT_T
+typedef int32_t saint_t;
+#endif /* SAINT_T */
+#ifndef SAIDX64_T
+#define SAIDX64_T
+typedef int64_t saidx64_t;
+#endif /* SAIDX64_T */
+#ifndef PRIdSAINT_T
+#define PRIdSAINT_T PRId32
+#endif /* PRIdSAINT_T */
+#ifndef PRIdSAIDX64_T
+#define PRIdSAIDX64_T PRId64
+#endif /* PRIdSAIDX64_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
+divsufsort64(const sauchar_t *T, saidx64_t *SA, saidx64_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
+saidx64_t
+divbwt64(const sauchar_t *T, sauchar_t *U, saidx64_t *A, saidx64_t n);
+
+/**
+ * Returns the version of the divsufsort library.
+ * @return The version number string.
+ */
+DIVSUFSORT_API
+const char *
+divsufsort64_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_transform64(const sauchar_t *T, sauchar_t *U,
+ saidx64_t *SA /* can NULL */,
+ saidx64_t n, saidx64_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_transform64(const sauchar_t *T, sauchar_t *U,
+ saidx64_t *A /* can NULL */,
+ saidx64_t n, saidx64_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
+sufcheck64(const sauchar_t *T, const saidx64_t *SA, saidx64_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
+saidx64_t
+sa_search64(const sauchar_t *T, saidx64_t Tsize,
+ const sauchar_t *P, saidx64_t Psize,
+ const saidx64_t *SA, saidx64_t SAsize,
+ saidx64_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
+saidx64_t
+sa_simplesearch64(const sauchar_t *T, saidx64_t Tsize,
+ const saidx64_t *SA, saidx64_t SAsize,
+ saint_t c, saidx64_t *left);
+
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif /* __cplusplus */
+
+#endif /* _DIVSUFSORT64_H */
diff --git a/libdivsufsort/examples/CMakeLists.txt b/libdivsufsort/examples/CMakeLists.txt
new file mode 100644
index 0000000..e801c81
--- /dev/null
+++ b/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/libdivsufsort/examples/bwt.c b/libdivsufsort/examples/bwt.c
new file mode 100644
index 0000000..5a362d0
--- /dev/null
+++ b/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 <stdio.h>
+#if HAVE_STRING_H
+# include <string.h>
+#endif
+#if HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+#if HAVE_MEMORY_H
+# include <memory.h>
+#endif
+#if HAVE_STDDEF_H
+# include <stddef.h>
+#endif
+#if HAVE_STRINGS_H
+# include <strings.h>
+#endif
+#if HAVE_SYS_TYPES_H
+# include <sys/types.h>
+#endif
+#if HAVE_IO_H && HAVE_FCNTL_H
+# include <io.h>
+# include <fcntl.h>
+#endif
+#include <time.h>
+#include <divsufsort.h>
+#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/libdivsufsort/examples/mksary.c b/libdivsufsort/examples/mksary.c
new file mode 100644
index 0000000..b48177c
--- /dev/null
+++ b/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 <stdio.h>
+#if HAVE_STRING_H
+# include <string.h>
+#endif
+#if HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+#if HAVE_MEMORY_H
+# include <memory.h>
+#endif
+#if HAVE_STDDEF_H
+# include <stddef.h>
+#endif
+#if HAVE_STRINGS_H
+# include <strings.h>
+#endif
+#if HAVE_SYS_TYPES_H
+# include <sys/types.h>
+#endif
+#if HAVE_IO_H && HAVE_FCNTL_H
+# include <io.h>
+# include <fcntl.h>
+#endif
+#include <time.h>
+#include <divsufsort.h>
+#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/libdivsufsort/examples/sasearch.c b/libdivsufsort/examples/sasearch.c
new file mode 100644
index 0000000..7e5ca4f
--- /dev/null
+++ b/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 <stdio.h>
+#if HAVE_STRING_H
+# include <string.h>
+#endif
+#if HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+#if HAVE_MEMORY_H
+# include <memory.h>
+#endif
+#if HAVE_STDDEF_H
+# include <stddef.h>
+#endif
+#if HAVE_STRINGS_H
+# include <strings.h>
+#endif
+#if HAVE_SYS_TYPES_H
+# include <sys/types.h>
+#endif
+#if HAVE_IO_H && HAVE_FCNTL_H
+# include <io.h>
+# include <fcntl.h>
+#endif
+#include <divsufsort.h>
+#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/libdivsufsort/examples/suftest.c b/libdivsufsort/examples/suftest.c
new file mode 100644
index 0000000..71892ac
--- /dev/null
+++ b/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 <stdio.h>
+#if HAVE_STRING_H
+# include <string.h>
+#endif
+#if HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+#if HAVE_MEMORY_H
+# include <memory.h>
+#endif
+#if HAVE_STDDEF_H
+# include <stddef.h>
+#endif
+#if HAVE_STRINGS_H
+# include <strings.h>
+#endif
+#if HAVE_SYS_TYPES_H
+# include <sys/types.h>
+#endif
+#if HAVE_IO_H && HAVE_FCNTL_H
+# include <io.h>
+# include <fcntl.h>
+#endif
+#include <time.h>
+#include <divsufsort.h>
+#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/libdivsufsort/examples/unbwt.c b/libdivsufsort/examples/unbwt.c
new file mode 100644
index 0000000..c0f19e9
--- /dev/null
+++ b/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 <stdio.h>
+#if HAVE_STRING_H
+# include <string.h>
+#endif
+#if HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+#if HAVE_MEMORY_H
+# include <memory.h>
+#endif
+#if HAVE_STDDEF_H
+# include <stddef.h>
+#endif
+#if HAVE_STRINGS_H
+# include <strings.h>
+#endif
+#if HAVE_SYS_TYPES_H
+# include <sys/types.h>
+#endif
+#if HAVE_IO_H && HAVE_FCNTL_H
+# include <io.h>
+# include <fcntl.h>
+#endif
+#include <time.h>
+#include <divsufsort.h>
+#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/libdivsufsort/generate_includes.sh b/libdivsufsort/generate_includes.sh
new file mode 100755
index 0000000..15b976e
--- /dev/null
+++ b/libdivsufsort/generate_includes.sh
@@ -0,0 +1,49 @@
+#!/bin/bash
+#
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+# Generates the android_includes/ directory with the headers that normally will
+# be generated by cmake. Run this command whenever you update the include files.
+
+LOCAL_PATH=$(realpath $(dirname "$0"))
+
+cleanup() {
+ rm -rf "${WORKDIR}"
+}
+trap cleanup INT TERM ERR EXIT
+
+WORKDIR=$(mktemp -d libdivsufsort.XXXXXX)
+INCLUDESDIR="${LOCAL_PATH}/android_include"
+
+pushd "${WORKDIR}"
+cmake "${LOCAL_PATH}" \
+ -DBUILD_DIVSUFSORT64=1 \
+ -DBUILD_EXAMPLES=0 \
+ -DUSE_OPENMP=0 \
+ -DWITH_LFS=1
+
+mkdir -p "${INCLUDESDIR}"
+echo "Copying headers:"
+cp -v include/*.h "${INCLUDESDIR}/"
+popd >/dev/null
+
+cat <<EOF
+=============================================================
+Remember to run the following command to add the new headers:
+
+ git add android_include/*
+
+EOF
diff --git a/libdivsufsort/include/CMakeLists.txt b/libdivsufsort/include/CMakeLists.txt
new file mode 100644
index 0000000..37781cc
--- /dev/null
+++ b/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 <inttypes.h>")
+elseif(HAVE_STDINT_H)
+ set(INCFILE "#include <stdint.h>")
+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/libdivsufsort/include/config.h.cmake b/libdivsufsort/include/config.h.cmake
new file mode 100644
index 0000000..6a1cf47
--- /dev/null
+++ b/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/libdivsufsort/include/divsufsort.h.cmake b/libdivsufsort/include/divsufsort.h.cmake
new file mode 100644
index 0000000..bcaba7c
--- /dev/null
+++ b/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/libdivsufsort/include/divsufsort_private.h b/libdivsufsort/include/divsufsort_private.h
new file mode 100644
index 0000000..7e261c1
--- /dev/null
+++ b/libdivsufsort/include/divsufsort_private.h
@@ -0,0 +1,207 @@
+/*
+ * 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 */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+#include <assert.h>
+#include <stdio.h>
+#if HAVE_STRING_H
+# include <string.h>
+#endif
+#if HAVE_STDLIB_H
+# include <stdlib.h>
+#endif
+#if HAVE_MEMORY_H
+# include <memory.h>
+#endif
+#if HAVE_STDDEF_H
+# include <stddef.h>
+#endif
+#if HAVE_STRINGS_H
+# include <strings.h>
+#endif
+#if HAVE_INTTYPES_H
+# include <inttypes.h>
+#else
+# if HAVE_STDINT_H
+# include <stdint.h>
+# 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/libdivsufsort/include/lfs.h.cmake b/libdivsufsort/include/lfs.h.cmake
new file mode 100644
index 0000000..d5b84a8
--- /dev/null
+++ b/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/libdivsufsort/lib/CMakeLists.txt b/libdivsufsort/lib/CMakeLists.txt
new file mode 100644
index 0000000..abc90e6
--- /dev/null
+++ b/libdivsufsort/lib/CMakeLists.txt
@@ -0,0 +1,31 @@
+include_directories("${CMAKE_CURRENT_SOURCE_DIR}/../include"
+ "${CMAKE_CURRENT_BINARY_DIR}/../include")
+
+set(divsufsort_SRCS divsufsort.c sssort.c trsort.c utils.c)
+
+## libdivsufsort ##
+add_library(divsufsort ${divsufsort_SRCS})
+install(TARGETS divsufsort
+ RUNTIME DESTINATION ${CMAKE_INSTALL_RUNTIMEDIR}
+ LIBRARY DESTINATION ${CMAKE_INSTALL_LIBDIR}
+ ARCHIVE DESTINATION ${CMAKE_INSTALL_LIBDIR})
+set_target_properties(divsufsort PROPERTIES
+ VERSION "${LIBRARY_VERSION}"
+ SOVERSION "${LIBRARY_SOVERSION}"
+ DEFINE_SYMBOL DIVSUFSORT_BUILD_DLL
+ RUNTIME_OUTPUT_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}/../examples")
+
+## libdivsufsort64 ##
+if(BUILD_DIVSUFSORT64)
+ add_library(divsufsort64 ${divsufsort_SRCS})
+ install(TARGETS divsufsort64
+ RUNTIME DESTINATION ${CMAKE_INSTALL_RUNTIMEDIR}
+ LIBRARY DESTINATION ${CMAKE_INSTALL_LIBDIR}
+ ARCHIVE DESTINATION ${CMAKE_INSTALL_LIBDIR})
+ set_target_properties(divsufsort64 PROPERTIES
+ VERSION "${LIBRARY_VERSION}"
+ SOVERSION "${LIBRARY_SOVERSION}"
+ DEFINE_SYMBOL DIVSUFSORT_BUILD_DLL
+ COMPILE_FLAGS "-DBUILD_DIVSUFSORT64"
+ RUNTIME_OUTPUT_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}/../examples")
+endif(BUILD_DIVSUFSORT64)
diff --git a/libdivsufsort/lib/divsufsort.c b/libdivsufsort/lib/divsufsort.c
new file mode 100644
index 0000000..9f64b4f
--- /dev/null
+++ b/libdivsufsort/lib/divsufsort.c
@@ -0,0 +1,398 @@
+/*
+ * divsufsort.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.
+ */
+
+#include "divsufsort_private.h"
+#ifdef _OPENMP
+# include <omp.h>
+#endif
+
+
+/*- Private Functions -*/
+
+/* Sorts suffixes of type B*. */
+static
+saidx_t
+sort_typeBstar(const sauchar_t *T, saidx_t *SA,
+ saidx_t *bucket_A, saidx_t *bucket_B,
+ saidx_t n) {
+ saidx_t *PAb, *ISAb, *buf;
+#ifdef _OPENMP
+ saidx_t *curbuf;
+ saidx_t l;
+#endif
+ saidx_t i, j, k, t, m, bufsize;
+ saint_t c0, c1;
+#ifdef _OPENMP
+ saint_t d0, d1;
+ int tmp;
+#endif
+
+ /* Initialize bucket arrays. */
+ for(i = 0; i < BUCKET_A_SIZE; ++i) { bucket_A[i] = 0; }
+ for(i = 0; i < BUCKET_B_SIZE; ++i) { bucket_B[i] = 0; }
+
+ /* Count the number of occurrences of the first one or two characters of each
+ type A, B and B* suffix. Moreover, store the beginning position of all
+ type B* suffixes into the array SA. */
+ for(i = n - 1, m = n, c0 = T[n - 1]; 0 <= i;) {
+ /* type A suffix. */
+ do { ++BUCKET_A(c1 = c0); } while((0 <= --i) && ((c0 = T[i]) >= c1));
+ if(0 <= i) {
+ /* type B* suffix. */
+ ++BUCKET_BSTAR(c0, c1);
+ SA[--m] = i;
+ /* type B suffix. */
+ for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) {
+ ++BUCKET_B(c0, c1);
+ }
+ }
+ }
+ m = n - m;
+/*
+note:
+ A type B* suffix is lexicographically smaller than a type B suffix that
+ begins with the same first two characters.
+*/
+
+ /* Calculate the index of start/end point of each bucket. */
+ for(c0 = 0, i = 0, j = 0; c0 < ALPHABET_SIZE; ++c0) {
+ t = i + BUCKET_A(c0);
+ BUCKET_A(c0) = i + j; /* start point */
+ i = t + BUCKET_B(c0, c0);
+ for(c1 = c0 + 1; c1 < ALPHABET_SIZE; ++c1) {
+ j += BUCKET_BSTAR(c0, c1);
+ BUCKET_BSTAR(c0, c1) = j; /* end point */
+ i += BUCKET_B(c0, c1);
+ }
+ }
+
+ if(0 < m) {
+ /* Sort the type B* suffixes by their first two characters. */
+ PAb = SA + n - m; ISAb = SA + m;
+ for(i = m - 2; 0 <= i; --i) {
+ t = PAb[i], c0 = T[t], c1 = T[t + 1];
+ SA[--BUCKET_BSTAR(c0, c1)] = i;
+ }
+ t = PAb[m - 1], c0 = T[t], c1 = T[t + 1];
+ SA[--BUCKET_BSTAR(c0, c1)] = m - 1;
+
+ /* Sort the type B* substrings using sssort. */
+#ifdef _OPENMP
+ tmp = omp_get_max_threads();
+ buf = SA + m, bufsize = (n - (2 * m)) / tmp;
+ c0 = ALPHABET_SIZE - 2, c1 = ALPHABET_SIZE - 1, j = m;
+#pragma omp parallel default(shared) private(curbuf, k, l, d0, d1, tmp)
+ {
+ tmp = omp_get_thread_num();
+ curbuf = buf + tmp * bufsize;
+ k = 0;
+ for(;;) {
+ #pragma omp critical(sssort_lock)
+ {
+ if(0 < (l = j)) {
+ d0 = c0, d1 = c1;
+ do {
+ k = BUCKET_BSTAR(d0, d1);
+ if(--d1 <= d0) {
+ d1 = ALPHABET_SIZE - 1;
+ if(--d0 < 0) { break; }
+ }
+ } while(((l - k) <= 1) && (0 < (l = k)));
+ c0 = d0, c1 = d1, j = k;
+ }
+ }
+ if(l == 0) { break; }
+ sssort(T, PAb, SA + k, SA + l,
+ curbuf, bufsize, 2, n, *(SA + k) == (m - 1));
+ }
+ }
+#else
+ buf = SA + m, bufsize = n - (2 * m);
+ for(c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) {
+ for(c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) {
+ i = BUCKET_BSTAR(c0, c1);
+ if(1 < (j - i)) {
+ sssort(T, PAb, SA + i, SA + j,
+ buf, bufsize, 2, n, *(SA + i) == (m - 1));
+ }
+ }
+ }
+#endif
+
+ /* Compute ranks of type B* substrings. */
+ for(i = m - 1; 0 <= i; --i) {
+ if(0 <= SA[i]) {
+ j = i;
+ do { ISAb[SA[i]] = i; } while((0 <= --i) && (0 <= SA[i]));
+ SA[i + 1] = i - j;
+ if(i <= 0) { break; }
+ }
+ j = i;
+ do { ISAb[SA[i] = ~SA[i]] = j; } while(SA[--i] < 0);
+ ISAb[SA[i]] = j;
+ }
+
+ /* Construct the inverse suffix array of type B* suffixes using trsort. */
+ trsort(ISAb, SA, m, 1);
+
+ /* Set the sorted order of tyoe B* suffixes. */
+ for(i = n - 1, j = m, c0 = T[n - 1]; 0 <= i;) {
+ for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) >= c1); --i, c1 = c0) { }
+ if(0 <= i) {
+ t = i;
+ for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) { }
+ SA[ISAb[--j]] = ((t == 0) || (1 < (t - i))) ? t : ~t;
+ }
+ }
+
+ /* Calculate the index of start/end point of each bucket. */
+ BUCKET_B(ALPHABET_SIZE - 1, ALPHABET_SIZE - 1) = n; /* end point */
+ for(c0 = ALPHABET_SIZE - 2, k = m - 1; 0 <= c0; --c0) {
+ i = BUCKET_A(c0 + 1) - 1;
+ for(c1 = ALPHABET_SIZE - 1; c0 < c1; --c1) {
+ t = i - BUCKET_B(c0, c1);
+ BUCKET_B(c0, c1) = i; /* end point */
+
+ /* Move all type B* suffixes to the correct position. */
+ for(i = t, j = BUCKET_BSTAR(c0, c1);
+ j <= k;
+ --i, --k) { SA[i] = SA[k]; }
+ }
+ BUCKET_BSTAR(c0, c0 + 1) = i - BUCKET_B(c0, c0) + 1; /* start point */
+ BUCKET_B(c0, c0) = i; /* end point */
+ }
+ }
+
+ return m;
+}
+
+/* Constructs the suffix array by using the sorted order of type B* suffixes. */
+static
+void
+construct_SA(const sauchar_t *T, saidx_t *SA,
+ saidx_t *bucket_A, saidx_t *bucket_B,
+ saidx_t n, saidx_t m) {
+ saidx_t *i, *j, *k;
+ saidx_t s;
+ saint_t c0, c1, c2;
+
+ if(0 < m) {
+ /* Construct the sorted order of type B suffixes by using
+ the sorted order of type B* suffixes. */
+ for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
+ /* Scan the suffix array from right to left. */
+ for(i = SA + BUCKET_BSTAR(c1, c1 + 1),
+ j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1;
+ i <= j;
+ --j) {
+ if(0 < (s = *j)) {
+ assert(T[s] == c1);
+ assert(((s + 1) < n) && (T[s] <= T[s + 1]));
+ assert(T[s - 1] <= T[s]);
+ *j = ~s;
+ c0 = T[--s];
+ if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
+ if(c0 != c2) {
+ if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
+ k = SA + BUCKET_B(c2 = c0, c1);
+ }
+ assert(k < j);
+ *k-- = s;
+ } else {
+ assert(((s == 0) && (T[s] == c1)) || (s < 0));
+ *j = ~s;
+ }
+ }
+ }
+ }
+
+ /* Construct the suffix array by using
+ the sorted order of type B suffixes. */
+ k = SA + BUCKET_A(c2 = T[n - 1]);
+ *k++ = (T[n - 2] < c2) ? ~(n - 1) : (n - 1);
+ /* Scan the suffix array from left to right. */
+ for(i = SA, j = SA + n; i < j; ++i) {
+ if(0 < (s = *i)) {
+ assert(T[s - 1] >= T[s]);
+ c0 = T[--s];
+ if((s == 0) || (T[s - 1] < c0)) { s = ~s; }
+ if(c0 != c2) {
+ BUCKET_A(c2) = k - SA;
+ k = SA + BUCKET_A(c2 = c0);
+ }
+ assert(i < k);
+ *k++ = s;
+ } else {
+ assert(s < 0);
+ *i = ~s;
+ }
+ }
+}
+
+/* Constructs the burrows-wheeler transformed string directly
+ by using the sorted order of type B* suffixes. */
+static
+saidx_t
+construct_BWT(const sauchar_t *T, saidx_t *SA,
+ saidx_t *bucket_A, saidx_t *bucket_B,
+ saidx_t n, saidx_t m) {
+ saidx_t *i, *j, *k, *orig;
+ saidx_t s;
+ saint_t c0, c1, c2;
+
+ if(0 < m) {
+ /* Construct the sorted order of type B suffixes by using
+ the sorted order of type B* suffixes. */
+ for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) {
+ /* Scan the suffix array from right to left. */
+ for(i = SA + BUCKET_BSTAR(c1, c1 + 1),
+ j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1;
+ i <= j;
+ --j) {
+ if(0 < (s = *j)) {
+ assert(T[s] == c1);
+ assert(((s + 1) < n) && (T[s] <= T[s + 1]));
+ assert(T[s - 1] <= T[s]);
+ c0 = T[--s];
+ *j = ~((saidx_t)c0);
+ if((0 < s) && (T[s - 1] > c0)) { s = ~s; }
+ if(c0 != c2) {
+ if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; }
+ k = SA + BUCKET_B(c2 = c0, c1);
+ }
+ assert(k < j);
+ *k-- = s;
+ } else if(s != 0) {
+ *j = ~s;
+#ifndef NDEBUG
+ } else {
+ assert(T[s] == c1);
+#endif
+ }
+ }
+ }
+ }
+
+ /* Construct the BWTed string by using
+ the sorted order of type B suffixes. */
+ k = SA + BUCKET_A(c2 = T[n - 1]);
+ *k++ = (T[n - 2] < c2) ? ~((saidx_t)T[n - 2]) : (n - 1);
+ /* Scan the suffix array from left to right. */
+ for(i = SA, j = SA + n, orig = SA; i < j; ++i) {
+ if(0 < (s = *i)) {
+ assert(T[s - 1] >= T[s]);
+ c0 = T[--s];
+ *i = c0;
+ if((0 < s) && (T[s - 1] < c0)) { s = ~((saidx_t)T[s - 1]); }
+ if(c0 != c2) {
+ BUCKET_A(c2) = k - SA;
+ k = SA + BUCKET_A(c2 = c0);
+ }
+ assert(i < k);
+ *k++ = s;
+ } else if(s != 0) {
+ *i = ~s;
+ } else {
+ orig = i;
+ }
+ }
+
+ return orig - SA;
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/*- Function -*/
+
+saint_t
+divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n) {
+ saidx_t *bucket_A, *bucket_B;
+ saidx_t m;
+ saint_t err = 0;
+
+ /* Check arguments. */
+ if((T == NULL) || (SA == NULL) || (n < 0)) { return -1; }
+ else if(n == 0) { return 0; }
+ else if(n == 1) { SA[0] = 0; return 0; }
+ else if(n == 2) { m = (T[0] < T[1]); SA[m ^ 1] = 0, SA[m] = 1; return 0; }
+
+ bucket_A = (saidx_t *)malloc(BUCKET_A_SIZE * sizeof(saidx_t));
+ bucket_B = (saidx_t *)malloc(BUCKET_B_SIZE * sizeof(saidx_t));
+
+ /* Suffixsort. */
+ if((bucket_A != NULL) && (bucket_B != NULL)) {
+ m = sort_typeBstar(T, SA, bucket_A, bucket_B, n);
+ construct_SA(T, SA, bucket_A, bucket_B, n, m);
+ } else {
+ err = -2;
+ }
+
+ free(bucket_B);
+ free(bucket_A);
+
+ return err;
+}
+
+saidx_t
+divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n) {
+ saidx_t *B;
+ saidx_t *bucket_A, *bucket_B;
+ saidx_t m, pidx, i;
+
+ /* Check arguments. */
+ if((T == NULL) || (U == NULL) || (n < 0)) { return -1; }
+ else if(n <= 1) { if(n == 1) { U[0] = T[0]; } return n; }
+
+ if((B = A) == NULL) { B = (saidx_t *)malloc((size_t)(n + 1) * sizeof(saidx_t)); }
+ bucket_A = (saidx_t *)malloc(BUCKET_A_SIZE * sizeof(saidx_t));
+ bucket_B = (saidx_t *)malloc(BUCKET_B_SIZE * sizeof(saidx_t));
+
+ /* Burrows-Wheeler Transform. */
+ if((B != NULL) && (bucket_A != NULL) && (bucket_B != NULL)) {
+ m = sort_typeBstar(T, B, bucket_A, bucket_B, n);
+ pidx = construct_BWT(T, B, bucket_A, bucket_B, n, m);
+
+ /* Copy to output string. */
+ U[0] = T[n - 1];
+ for(i = 0; i < pidx; ++i) { U[i + 1] = (sauchar_t)B[i]; }
+ for(i += 1; i < n; ++i) { U[i] = (sauchar_t)B[i]; }
+ pidx += 1;
+ } else {
+ pidx = -2;
+ }
+
+ free(bucket_B);
+ free(bucket_A);
+ if(A == NULL) { free(B); }
+
+ return pidx;
+}
+
+const char *
+divsufsort_version(void) {
+ return PROJECT_VERSION_FULL;
+}
diff --git a/libdivsufsort/lib/sssort.c b/libdivsufsort/lib/sssort.c
new file mode 100644
index 0000000..4a18fd2
--- /dev/null
+++ b/libdivsufsort/lib/sssort.c
@@ -0,0 +1,815 @@
+/*
+ * sssort.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.
+ */
+
+#include "divsufsort_private.h"
+
+
+/*- Private Functions -*/
+
+static const saint_t lg_table[256]= {
+ -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
+ 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
+};
+
+#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
+
+static INLINE
+saint_t
+ss_ilg(saidx_t n) {
+#if SS_BLOCKSIZE == 0
+# if defined(BUILD_DIVSUFSORT64)
+ return (n >> 32) ?
+ ((n >> 48) ?
+ ((n >> 56) ?
+ 56 + lg_table[(n >> 56) & 0xff] :
+ 48 + lg_table[(n >> 48) & 0xff]) :
+ ((n >> 40) ?
+ 40 + lg_table[(n >> 40) & 0xff] :
+ 32 + lg_table[(n >> 32) & 0xff])) :
+ ((n & 0xffff0000) ?
+ ((n & 0xff000000) ?
+ 24 + lg_table[(n >> 24) & 0xff] :
+ 16 + lg_table[(n >> 16) & 0xff]) :
+ ((n & 0x0000ff00) ?
+ 8 + lg_table[(n >> 8) & 0xff] :
+ 0 + lg_table[(n >> 0) & 0xff]));
+# else
+ return (n & 0xffff0000) ?
+ ((n & 0xff000000) ?
+ 24 + lg_table[(n >> 24) & 0xff] :
+ 16 + lg_table[(n >> 16) & 0xff]) :
+ ((n & 0x0000ff00) ?
+ 8 + lg_table[(n >> 8) & 0xff] :
+ 0 + lg_table[(n >> 0) & 0xff]);
+# endif
+#elif SS_BLOCKSIZE < 256
+ return lg_table[n];
+#else
+ return (n & 0xff00) ?
+ 8 + lg_table[(n >> 8) & 0xff] :
+ 0 + lg_table[(n >> 0) & 0xff];
+#endif
+}
+
+#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */
+
+#if SS_BLOCKSIZE != 0
+
+static const saint_t sqq_table[256] = {
+ 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61,
+ 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84, 86, 87, 89,
+ 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109,
+110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126,
+128, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142,
+143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155,
+156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
+169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180,
+181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188, 189, 189, 190, 191,
+192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200, 201, 201,
+202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211,
+212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221,
+221, 222, 222, 223, 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230,
+230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
+239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247,
+247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255
+};
+
+static INLINE
+saidx_t
+ss_isqrt(saidx_t x) {
+ saidx_t y, e;
+
+ if(x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; }
+ e = (x & 0xffff0000) ?
+ ((x & 0xff000000) ?
+ 24 + lg_table[(x >> 24) & 0xff] :
+ 16 + lg_table[(x >> 16) & 0xff]) :
+ ((x & 0x0000ff00) ?
+ 8 + lg_table[(x >> 8) & 0xff] :
+ 0 + lg_table[(x >> 0) & 0xff]);
+
+ if(e >= 16) {
+ y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7);
+ if(e >= 24) { y = (y + 1 + x / y) >> 1; }
+ y = (y + 1 + x / y) >> 1;
+ } else if(e >= 8) {
+ y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1;
+ } else {
+ return sqq_table[x] >> 4;
+ }
+
+ return (x < (y * y)) ? y - 1 : y;
+}
+
+#endif /* SS_BLOCKSIZE != 0 */
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Compares two suffixes. */
+static INLINE
+saint_t
+ss_compare(const sauchar_t *T,
+ const saidx_t *p1, const saidx_t *p2,
+ saidx_t depth) {
+ const sauchar_t *U1, *U2, *U1n, *U2n;
+
+ for(U1 = T + depth + *p1,
+ U2 = T + depth + *p2,
+ U1n = T + *(p1 + 1) + 2,
+ U2n = T + *(p2 + 1) + 2;
+ (U1 < U1n) && (U2 < U2n) && (*U1 == *U2);
+ ++U1, ++U2) {
+ }
+
+ return U1 < U1n ?
+ (U2 < U2n ? *U1 - *U2 : 1) :
+ (U2 < U2n ? -1 : 0);
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+#if (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1)
+
+/* Insertionsort for small size groups */
+static
+void
+ss_insertionsort(const sauchar_t *T, const saidx_t *PA,
+ saidx_t *first, saidx_t *last, saidx_t depth) {
+ saidx_t *i, *j;
+ saidx_t t;
+ saint_t r;
+
+ for(i = last - 2; first <= i; --i) {
+ for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) {
+ do { *(j - 1) = *j; } while((++j < last) && (*j < 0));
+ if(last <= j) { break; }
+ }
+ if(r == 0) { *j = ~*j; }
+ *(j - 1) = t;
+ }
+}
+
+#endif /* (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) */
+
+
+/*---------------------------------------------------------------------------*/
+
+#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE)
+
+static INLINE
+void
+ss_fixdown(const sauchar_t *Td, const saidx_t *PA,
+ saidx_t *SA, saidx_t i, saidx_t size) {
+ saidx_t j, k;
+ saidx_t v;
+ saint_t c, d, e;
+
+ for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
+ d = Td[PA[SA[k = j++]]];
+ if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; }
+ if(d <= c) { break; }
+ }
+ SA[i] = v;
+}
+
+/* Simple top-down heapsort. */
+static
+void
+ss_heapsort(const sauchar_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t size) {
+ saidx_t i, m;
+ saidx_t t;
+
+ m = size;
+ if((size % 2) == 0) {
+ m--;
+ if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); }
+ }
+
+ for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); }
+ if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); }
+ for(i = m - 1; 0 < i; --i) {
+ t = SA[0], SA[0] = SA[i];
+ ss_fixdown(Td, PA, SA, 0, i);
+ SA[i] = t;
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Returns the median of three elements. */
+static INLINE
+saidx_t *
+ss_median3(const sauchar_t *Td, const saidx_t *PA,
+ saidx_t *v1, saidx_t *v2, saidx_t *v3) {
+ saidx_t *t;
+ if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); }
+ if(Td[PA[*v2]] > Td[PA[*v3]]) {
+ if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; }
+ else { return v3; }
+ }
+ return v2;
+}
+
+/* Returns the median of five elements. */
+static INLINE
+saidx_t *
+ss_median5(const sauchar_t *Td, const saidx_t *PA,
+ saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5) {
+ saidx_t *t;
+ if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); }
+ if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); }
+ if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); }
+ if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); }
+ if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); }
+ if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; }
+ return v3;
+}
+
+/* Returns the pivot element. */
+static INLINE
+saidx_t *
+ss_pivot(const sauchar_t *Td, const saidx_t *PA, saidx_t *first, saidx_t *last) {
+ saidx_t *middle;
+ saidx_t t;
+
+ t = last - first;
+ middle = first + t / 2;
+
+ if(t <= 512) {
+ if(t <= 32) {
+ return ss_median3(Td, PA, first, middle, last - 1);
+ } else {
+ t >>= 2;
+ return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1);
+ }
+ }
+ t >>= 3;
+ first = ss_median3(Td, PA, first, first + t, first + (t << 1));
+ middle = ss_median3(Td, PA, middle - t, middle, middle + t);
+ last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1);
+ return ss_median3(Td, PA, first, middle, last);
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Binary partition for substrings. */
+static INLINE
+saidx_t *
+ss_partition(const saidx_t *PA,
+ saidx_t *first, saidx_t *last, saidx_t depth) {
+ saidx_t *a, *b;
+ saidx_t t;
+ for(a = first - 1, b = last;;) {
+ for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; }
+ for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { }
+ if(b <= a) { break; }
+ t = ~*b;
+ *b = *a;
+ *a = t;
+ }
+ if(first < a) { *first = ~*first; }
+ return a;
+}
+
+/* Multikey introsort for medium size groups. */
+static
+void
+ss_mintrosort(const sauchar_t *T, const saidx_t *PA,
+ saidx_t *first, saidx_t *last,
+ saidx_t depth) {
+#define STACK_SIZE SS_MISORT_STACKSIZE
+ struct { saidx_t *a, *b, c; saint_t d; } stack[STACK_SIZE];
+ const sauchar_t *Td;
+ saidx_t *a, *b, *c, *d, *e, *f;
+ saidx_t s, t;
+ saint_t ssize;
+ saint_t limit;
+ saint_t v, x = 0;
+
+ for(ssize = 0, limit = ss_ilg(last - first);;) {
+
+ if((last - first) <= SS_INSERTIONSORT_THRESHOLD) {
+#if 1 < SS_INSERTIONSORT_THRESHOLD
+ if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); }
+#endif
+ STACK_POP(first, last, depth, limit);
+ continue;
+ }
+
+ Td = T + depth;
+ if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); }
+ if(limit < 0) {
+ for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) {
+ if((x = Td[PA[*a]]) != v) {
+ if(1 < (a - first)) { break; }
+ v = x;
+ first = a;
+ }
+ }
+ if(Td[PA[*first] - 1] < v) {
+ first = ss_partition(PA, first, a, depth);
+ }
+ if((a - first) <= (last - a)) {
+ if(1 < (a - first)) {
+ STACK_PUSH(a, last, depth, -1);
+ last = a, depth += 1, limit = ss_ilg(a - first);
+ } else {
+ first = a, limit = -1;
+ }
+ } else {
+ if(1 < (last - a)) {
+ STACK_PUSH(first, a, depth + 1, ss_ilg(a - first));
+ first = a, limit = -1;
+ } else {
+ last = a, depth += 1, limit = ss_ilg(a - first);
+ }
+ }
+ continue;
+ }
+
+ /* choose pivot */
+ a = ss_pivot(Td, PA, first, last);
+ v = Td[PA[*a]];
+ SWAP(*first, *a);
+
+ /* partition */
+ for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { }
+ if(((a = b) < last) && (x < v)) {
+ for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) {
+ if(x == v) { SWAP(*b, *a); ++a; }
+ }
+ }
+ for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { }
+ if((b < (d = c)) && (x > v)) {
+ for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
+ if(x == v) { SWAP(*c, *d); --d; }
+ }
+ }
+ for(; b < c;) {
+ SWAP(*b, *c);
+ for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) {
+ if(x == v) { SWAP(*b, *a); ++a; }
+ }
+ for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
+ if(x == v) { SWAP(*c, *d); --d; }
+ }
+ }
+
+ if(a <= d) {
+ c = b - 1;
+
+ if((s = a - first) > (t = b - a)) { s = t; }
+ for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
+ if((s = d - c) > (t = last - d - 1)) { s = t; }
+ for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
+
+ a = first + (b - a), c = last - (d - c);
+ b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth);
+
+ if((a - first) <= (last - c)) {
+ if((last - c) <= (c - b)) {
+ STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
+ STACK_PUSH(c, last, depth, limit);
+ last = a;
+ } else if((a - first) <= (c - b)) {
+ STACK_PUSH(c, last, depth, limit);
+ STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
+ last = a;
+ } else {
+ STACK_PUSH(c, last, depth, limit);
+ STACK_PUSH(first, a, depth, limit);
+ first = b, last = c, depth += 1, limit = ss_ilg(c - b);
+ }
+ } else {
+ if((a - first) <= (c - b)) {
+ STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
+ STACK_PUSH(first, a, depth, limit);
+ first = c;
+ } else if((last - c) <= (c - b)) {
+ STACK_PUSH(first, a, depth, limit);
+ STACK_PUSH(b, c, depth + 1, ss_ilg(c - b));
+ first = c;
+ } else {
+ STACK_PUSH(first, a, depth, limit);
+ STACK_PUSH(c, last, depth, limit);
+ first = b, last = c, depth += 1, limit = ss_ilg(c - b);
+ }
+ }
+ } else {
+ limit += 1;
+ if(Td[PA[*first] - 1] < v) {
+ first = ss_partition(PA, first, last, depth);
+ limit = ss_ilg(last - first);
+ }
+ depth += 1;
+ }
+ }
+#undef STACK_SIZE
+}
+
+#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */
+
+
+/*---------------------------------------------------------------------------*/
+
+#if SS_BLOCKSIZE != 0
+
+static INLINE
+void
+ss_blockswap(saidx_t *a, saidx_t *b, saidx_t n) {
+ saidx_t t;
+ for(; 0 < n; --n, ++a, ++b) {
+ t = *a, *a = *b, *b = t;
+ }
+}
+
+static INLINE
+void
+ss_rotate(saidx_t *first, saidx_t *middle, saidx_t *last) {
+ saidx_t *a, *b, t;
+ saidx_t l, r;
+ l = middle - first, r = last - middle;
+ for(; (0 < l) && (0 < r);) {
+ if(l == r) { ss_blockswap(first, middle, l); break; }
+ if(l < r) {
+ a = last - 1, b = middle - 1;
+ t = *a;
+ do {
+ *a-- = *b, *b-- = *a;
+ if(b < first) {
+ *a = t;
+ last = a;
+ if((r -= l + 1) <= l) { break; }
+ a -= 1, b = middle - 1;
+ t = *a;
+ }
+ } while(1);
+ } else {
+ a = first, b = middle;
+ t = *a;
+ do {
+ *a++ = *b, *b++ = *a;
+ if(last <= b) {
+ *a = t;
+ first = a + 1;
+ if((l -= r + 1) <= r) { break; }
+ a += 1, b = middle;
+ t = *a;
+ }
+ } while(1);
+ }
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+static
+void
+ss_inplacemerge(const sauchar_t *T, const saidx_t *PA,
+ saidx_t *first, saidx_t *middle, saidx_t *last,
+ saidx_t depth) {
+ const saidx_t *p;
+ saidx_t *a, *b;
+ saidx_t len, half;
+ saint_t q, r;
+ saint_t x;
+
+ for(;;) {
+ if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); }
+ else { x = 0; p = PA + *(last - 1); }
+ for(a = first, len = middle - first, half = len >> 1, r = -1;
+ 0 < len;
+ len = half, half >>= 1) {
+ b = a + half;
+ q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth);
+ if(q < 0) {
+ a = b + 1;
+ half -= (len & 1) ^ 1;
+ } else {
+ r = q;
+ }
+ }
+ if(a < middle) {
+ if(r == 0) { *a = ~*a; }
+ ss_rotate(a, middle, last);
+ last -= middle - a;
+ middle = a;
+ if(first == middle) { break; }
+ }
+ --last;
+ if(x != 0) { while(*--last < 0) { } }
+ if(middle == last) { break; }
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Merge-forward with internal buffer. */
+static
+void
+ss_mergeforward(const sauchar_t *T, const saidx_t *PA,
+ saidx_t *first, saidx_t *middle, saidx_t *last,
+ saidx_t *buf, saidx_t depth) {
+ saidx_t *a, *b, *c, *bufend;
+ saidx_t t;
+ saint_t r;
+
+ bufend = buf + (middle - first) - 1;
+ ss_blockswap(buf, first, middle - first);
+
+ for(t = *(a = first), b = buf, c = middle;;) {
+ r = ss_compare(T, PA + *b, PA + *c, depth);
+ if(r < 0) {
+ do {
+ *a++ = *b;
+ if(bufend <= b) { *bufend = t; return; }
+ *b++ = *a;
+ } while(*b < 0);
+ } else if(r > 0) {
+ do {
+ *a++ = *c, *c++ = *a;
+ if(last <= c) {
+ while(b < bufend) { *a++ = *b, *b++ = *a; }
+ *a = *b, *b = t;
+ return;
+ }
+ } while(*c < 0);
+ } else {
+ *c = ~*c;
+ do {
+ *a++ = *b;
+ if(bufend <= b) { *bufend = t; return; }
+ *b++ = *a;
+ } while(*b < 0);
+
+ do {
+ *a++ = *c, *c++ = *a;
+ if(last <= c) {
+ while(b < bufend) { *a++ = *b, *b++ = *a; }
+ *a = *b, *b = t;
+ return;
+ }
+ } while(*c < 0);
+ }
+ }
+}
+
+/* Merge-backward with internal buffer. */
+static
+void
+ss_mergebackward(const sauchar_t *T, const saidx_t *PA,
+ saidx_t *first, saidx_t *middle, saidx_t *last,
+ saidx_t *buf, saidx_t depth) {
+ const saidx_t *p1, *p2;
+ saidx_t *a, *b, *c, *bufend;
+ saidx_t t;
+ saint_t r;
+ saint_t x;
+
+ bufend = buf + (last - middle) - 1;
+ ss_blockswap(buf, middle, last - middle);
+
+ x = 0;
+ if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; }
+ else { p1 = PA + *bufend; }
+ if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; }
+ else { p2 = PA + *(middle - 1); }
+ for(t = *(a = last - 1), b = bufend, c = middle - 1;;) {
+ r = ss_compare(T, p1, p2, depth);
+ if(0 < r) {
+ if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; }
+ *a-- = *b;
+ if(b <= buf) { *buf = t; break; }
+ *b-- = *a;
+ if(*b < 0) { p1 = PA + ~*b; x |= 1; }
+ else { p1 = PA + *b; }
+ } else if(r < 0) {
+ if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; }
+ *a-- = *c, *c-- = *a;
+ if(c < first) {
+ while(buf < b) { *a-- = *b, *b-- = *a; }
+ *a = *b, *b = t;
+ break;
+ }
+ if(*c < 0) { p2 = PA + ~*c; x |= 2; }
+ else { p2 = PA + *c; }
+ } else {
+ if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; }
+ *a-- = ~*b;
+ if(b <= buf) { *buf = t; break; }
+ *b-- = *a;
+ if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; }
+ *a-- = *c, *c-- = *a;
+ if(c < first) {
+ while(buf < b) { *a-- = *b, *b-- = *a; }
+ *a = *b, *b = t;
+ break;
+ }
+ if(*b < 0) { p1 = PA + ~*b; x |= 1; }
+ else { p1 = PA + *b; }
+ if(*c < 0) { p2 = PA + ~*c; x |= 2; }
+ else { p2 = PA + *c; }
+ }
+ }
+}
+
+/* D&C based merge. */
+static
+void
+ss_swapmerge(const sauchar_t *T, const saidx_t *PA,
+ saidx_t *first, saidx_t *middle, saidx_t *last,
+ saidx_t *buf, saidx_t bufsize, saidx_t depth) {
+#define STACK_SIZE SS_SMERGE_STACKSIZE
+#define GETIDX(a) ((0 <= (a)) ? (a) : (~(a)))
+#define MERGE_CHECK(a, b, c)\
+ do {\
+ if(((c) & 1) ||\
+ (((c) & 2) && (ss_compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0))) {\
+ *(a) = ~*(a);\
+ }\
+ if(((c) & 4) && ((ss_compare(T, PA + GETIDX(*((b) - 1)), PA + *(b), depth) == 0))) {\
+ *(b) = ~*(b);\
+ }\
+ } while(0)
+ struct { saidx_t *a, *b, *c; saint_t d; } stack[STACK_SIZE];
+ saidx_t *l, *r, *lm, *rm;
+ saidx_t m, len, half;
+ saint_t ssize;
+ saint_t check, next;
+
+ for(check = 0, ssize = 0;;) {
+ if((last - middle) <= bufsize) {
+ if((first < middle) && (middle < last)) {
+ ss_mergebackward(T, PA, first, middle, last, buf, depth);
+ }
+ MERGE_CHECK(first, last, check);
+ STACK_POP(first, middle, last, check);
+ continue;
+ }
+
+ if((middle - first) <= bufsize) {
+ if(first < middle) {
+ ss_mergeforward(T, PA, first, middle, last, buf, depth);
+ }
+ MERGE_CHECK(first, last, check);
+ STACK_POP(first, middle, last, check);
+ continue;
+ }
+
+ for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1;
+ 0 < len;
+ len = half, half >>= 1) {
+ if(ss_compare(T, PA + GETIDX(*(middle + m + half)),
+ PA + GETIDX(*(middle - m - half - 1)), depth) < 0) {
+ m += half + 1;
+ half -= (len & 1) ^ 1;
+ }
+ }
+
+ if(0 < m) {
+ lm = middle - m, rm = middle + m;
+ ss_blockswap(lm, middle, m);
+ l = r = middle, next = 0;
+ if(rm < last) {
+ if(*rm < 0) {
+ *rm = ~*rm;
+ if(first < lm) { for(; *--l < 0;) { } next |= 4; }
+ next |= 1;
+ } else if(first < lm) {
+ for(; *r < 0; ++r) { }
+ next |= 2;
+ }
+ }
+
+ if((l - first) <= (last - r)) {
+ STACK_PUSH(r, rm, last, (next & 3) | (check & 4));
+ middle = lm, last = l, check = (check & 3) | (next & 4);
+ } else {
+ if((next & 2) && (r == middle)) { next ^= 6; }
+ STACK_PUSH(first, lm, l, (check & 3) | (next & 4));
+ first = r, middle = rm, check = (next & 3) | (check & 4);
+ }
+ } else {
+ if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) {
+ *middle = ~*middle;
+ }
+ MERGE_CHECK(first, last, check);
+ STACK_POP(first, middle, last, check);
+ }
+ }
+#undef STACK_SIZE
+}
+
+#endif /* SS_BLOCKSIZE != 0 */
+
+
+/*---------------------------------------------------------------------------*/
+
+/*- Function -*/
+
+/* Substring sort */
+void
+sssort(const sauchar_t *T, 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) {
+ saidx_t *a;
+#if SS_BLOCKSIZE != 0
+ saidx_t *b, *middle, *curbuf;
+ saidx_t j, k, curbufsize, limit;
+#endif
+ saidx_t i;
+
+ if(lastsuffix != 0) { ++first; }
+
+#if SS_BLOCKSIZE == 0
+ ss_mintrosort(T, PA, first, last, depth);
+#else
+ if((bufsize < SS_BLOCKSIZE) &&
+ (bufsize < (last - first)) &&
+ (bufsize < (limit = ss_isqrt(last - first)))) {
+ if(SS_BLOCKSIZE < limit) { limit = SS_BLOCKSIZE; }
+ buf = middle = last - limit, bufsize = limit;
+ } else {
+ middle = last, limit = 0;
+ }
+ for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) {
+#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
+ ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth);
+#elif 1 < SS_BLOCKSIZE
+ ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth);
+#endif
+ curbufsize = last - (a + SS_BLOCKSIZE);
+ curbuf = a + SS_BLOCKSIZE;
+ if(curbufsize <= bufsize) { curbufsize = bufsize, curbuf = buf; }
+ for(b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) {
+ ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth);
+ }
+ }
+#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
+ ss_mintrosort(T, PA, a, middle, depth);
+#elif 1 < SS_BLOCKSIZE
+ ss_insertionsort(T, PA, a, middle, depth);
+#endif
+ for(k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
+ if(i & 1) {
+ ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth);
+ a -= k;
+ }
+ }
+ if(limit != 0) {
+#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE
+ ss_mintrosort(T, PA, middle, last, depth);
+#elif 1 < SS_BLOCKSIZE
+ ss_insertionsort(T, PA, middle, last, depth);
+#endif
+ ss_inplacemerge(T, PA, first, middle, last, depth);
+ }
+#endif
+
+ if(lastsuffix != 0) {
+ /* Insert last type B* suffix. */
+ saidx_t PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2;
+ for(a = first, i = *(first - 1);
+ (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth)));
+ ++a) {
+ *(a - 1) = *a;
+ }
+ *(a - 1) = i;
+ }
+}
diff --git a/libdivsufsort/lib/trsort.c b/libdivsufsort/lib/trsort.c
new file mode 100644
index 0000000..6fe3e67
--- /dev/null
+++ b/libdivsufsort/lib/trsort.c
@@ -0,0 +1,586 @@
+/*
+ * trsort.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.
+ */
+
+#include "divsufsort_private.h"
+
+
+/*- Private Functions -*/
+
+static const saint_t lg_table[256]= {
+ -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
+ 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
+};
+
+static INLINE
+saint_t
+tr_ilg(saidx_t n) {
+#if defined(BUILD_DIVSUFSORT64)
+ return (n >> 32) ?
+ ((n >> 48) ?
+ ((n >> 56) ?
+ 56 + lg_table[(n >> 56) & 0xff] :
+ 48 + lg_table[(n >> 48) & 0xff]) :
+ ((n >> 40) ?
+ 40 + lg_table[(n >> 40) & 0xff] :
+ 32 + lg_table[(n >> 32) & 0xff])) :
+ ((n & 0xffff0000) ?
+ ((n & 0xff000000) ?
+ 24 + lg_table[(n >> 24) & 0xff] :
+ 16 + lg_table[(n >> 16) & 0xff]) :
+ ((n & 0x0000ff00) ?
+ 8 + lg_table[(n >> 8) & 0xff] :
+ 0 + lg_table[(n >> 0) & 0xff]));
+#else
+ return (n & 0xffff0000) ?
+ ((n & 0xff000000) ?
+ 24 + lg_table[(n >> 24) & 0xff] :
+ 16 + lg_table[(n >> 16) & 0xff]) :
+ ((n & 0x0000ff00) ?
+ 8 + lg_table[(n >> 8) & 0xff] :
+ 0 + lg_table[(n >> 0) & 0xff]);
+#endif
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Simple insertionsort for small size groups. */
+static
+void
+tr_insertionsort(const saidx_t *ISAd, saidx_t *first, saidx_t *last) {
+ saidx_t *a, *b;
+ saidx_t t, r;
+
+ for(a = first + 1; a < last; ++a) {
+ for(t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) {
+ do { *(b + 1) = *b; } while((first <= --b) && (*b < 0));
+ if(b < first) { break; }
+ }
+ if(r == 0) { *b = ~*b; }
+ *(b + 1) = t;
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+static INLINE
+void
+tr_fixdown(const saidx_t *ISAd, saidx_t *SA, saidx_t i, saidx_t size) {
+ saidx_t j, k;
+ saidx_t v;
+ saidx_t c, d, e;
+
+ for(v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
+ d = ISAd[SA[k = j++]];
+ if(d < (e = ISAd[SA[j]])) { k = j; d = e; }
+ if(d <= c) { break; }
+ }
+ SA[i] = v;
+}
+
+/* Simple top-down heapsort. */
+static
+void
+tr_heapsort(const saidx_t *ISAd, saidx_t *SA, saidx_t size) {
+ saidx_t i, m;
+ saidx_t t;
+
+ m = size;
+ if((size % 2) == 0) {
+ m--;
+ if(ISAd[SA[m / 2]] < ISAd[SA[m]]) { SWAP(SA[m], SA[m / 2]); }
+ }
+
+ for(i = m / 2 - 1; 0 <= i; --i) { tr_fixdown(ISAd, SA, i, m); }
+ if((size % 2) == 0) { SWAP(SA[0], SA[m]); tr_fixdown(ISAd, SA, 0, m); }
+ for(i = m - 1; 0 < i; --i) {
+ t = SA[0], SA[0] = SA[i];
+ tr_fixdown(ISAd, SA, 0, i);
+ SA[i] = t;
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+/* Returns the median of three elements. */
+static INLINE
+saidx_t *
+tr_median3(const saidx_t *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3) {
+ saidx_t *t;
+ if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); }
+ if(ISAd[*v2] > ISAd[*v3]) {
+ if(ISAd[*v1] > ISAd[*v3]) { return v1; }
+ else { return v3; }
+ }
+ return v2;
+}
+
+/* Returns the median of five elements. */
+static INLINE
+saidx_t *
+tr_median5(const saidx_t *ISAd,
+ saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5) {
+ saidx_t *t;
+ if(ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); }
+ if(ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); }
+ if(ISAd[*v2] > ISAd[*v4]) { SWAP(v2, v4); SWAP(v3, v5); }
+ if(ISAd[*v1] > ISAd[*v3]) { SWAP(v1, v3); }
+ if(ISAd[*v1] > ISAd[*v4]) { SWAP(v1, v4); SWAP(v3, v5); }
+ if(ISAd[*v3] > ISAd[*v4]) { return v4; }
+ return v3;
+}
+
+/* Returns the pivot element. */
+static INLINE
+saidx_t *
+tr_pivot(const saidx_t *ISAd, saidx_t *first, saidx_t *last) {
+ saidx_t *middle;
+ saidx_t t;
+
+ t = last - first;
+ middle = first + t / 2;
+
+ if(t <= 512) {
+ if(t <= 32) {
+ return tr_median3(ISAd, first, middle, last - 1);
+ } else {
+ t >>= 2;
+ return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1);
+ }
+ }
+ t >>= 3;
+ first = tr_median3(ISAd, first, first + t, first + (t << 1));
+ middle = tr_median3(ISAd, middle - t, middle, middle + t);
+ last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1);
+ return tr_median3(ISAd, first, middle, last);
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+typedef struct _trbudget_t trbudget_t;
+struct _trbudget_t {
+ saidx_t chance;
+ saidx_t remain;
+ saidx_t incval;
+ saidx_t count;
+};
+
+static INLINE
+void
+trbudget_init(trbudget_t *budget, saidx_t chance, saidx_t incval) {
+ budget->chance = chance;
+ budget->remain = budget->incval = incval;
+}
+
+static INLINE
+saint_t
+trbudget_check(trbudget_t *budget, saidx_t size) {
+ if(size <= budget->remain) { budget->remain -= size; return 1; }
+ if(budget->chance == 0) { budget->count += size; return 0; }
+ budget->remain += budget->incval - size;
+ budget->chance -= 1;
+ return 1;
+}
+
+
+/*---------------------------------------------------------------------------*/
+
+static INLINE
+void
+tr_partition(const saidx_t *ISAd,
+ saidx_t *first, saidx_t *middle, saidx_t *last,
+ saidx_t **pa, saidx_t **pb, saidx_t v) {
+ saidx_t *a, *b, *c, *d, *e, *f;
+ saidx_t t, s;
+ saidx_t x = 0;
+
+ for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { }
+ if(((a = b) < last) && (x < v)) {
+ for(; (++b < last) && ((x = ISAd[*b]) <= v);) {
+ if(x == v) { SWAP(*b, *a); ++a; }
+ }
+ }
+ for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { }
+ if((b < (d = c)) && (x > v)) {
+ for(; (b < --c) && ((x = ISAd[*c]) >= v);) {
+ if(x == v) { SWAP(*c, *d); --d; }
+ }
+ }
+ for(; b < c;) {
+ SWAP(*b, *c);
+ for(; (++b < c) && ((x = ISAd[*b]) <= v);) {
+ if(x == v) { SWAP(*b, *a); ++a; }
+ }
+ for(; (b < --c) && ((x = ISAd[*c]) >= v);) {
+ if(x == v) { SWAP(*c, *d); --d; }
+ }
+ }
+
+ if(a <= d) {
+ c = b - 1;
+ if((s = a - first) > (t = b - a)) { s = t; }
+ for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
+ if((s = d - c) > (t = last - d - 1)) { s = t; }
+ for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); }
+ first += (b - a), last -= (d - c);
+ }
+ *pa = first, *pb = last;
+}
+
+static
+void
+tr_copy(saidx_t *ISA, const saidx_t *SA,
+ saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last,
+ saidx_t depth) {
+ /* sort suffixes of middle partition
+ by using sorted order of suffixes of left and right partition. */
+ saidx_t *c, *d, *e;
+ saidx_t s, v;
+
+ v = b - SA - 1;
+ for(c = first, d = a - 1; c <= d; ++c) {
+ if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
+ *++d = s;
+ ISA[s] = d - SA;
+ }
+ }
+ for(c = last - 1, e = d + 1, d = b; e < d; --c) {
+ if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
+ *--d = s;
+ ISA[s] = d - SA;
+ }
+ }
+}
+
+static
+void
+tr_partialcopy(saidx_t *ISA, const saidx_t *SA,
+ saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last,
+ saidx_t depth) {
+ saidx_t *c, *d, *e;
+ saidx_t s, v;
+ saidx_t rank, lastrank, newrank = -1;
+
+ v = b - SA - 1;
+ lastrank = -1;
+ for(c = first, d = a - 1; c <= d; ++c) {
+ if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
+ *++d = s;
+ rank = ISA[s + depth];
+ if(lastrank != rank) { lastrank = rank; newrank = d - SA; }
+ ISA[s] = newrank;
+ }
+ }
+
+ lastrank = -1;
+ for(e = d; first <= e; --e) {
+ rank = ISA[*e];
+ if(lastrank != rank) { lastrank = rank; newrank = e - SA; }
+ if(newrank != rank) { ISA[*e] = newrank; }
+ }
+
+ lastrank = -1;
+ for(c = last - 1, e = d + 1, d = b; e < d; --c) {
+ if((0 <= (s = *c - depth)) && (ISA[s] == v)) {
+ *--d = s;
+ rank = ISA[s + depth];
+ if(lastrank != rank) { lastrank = rank; newrank = d - SA; }
+ ISA[s] = newrank;
+ }
+ }
+}
+
+static
+void
+tr_introsort(saidx_t *ISA, const saidx_t *ISAd,
+ saidx_t *SA, saidx_t *first, saidx_t *last,
+ trbudget_t *budget) {
+#define STACK_SIZE TR_STACKSIZE
+ struct { const saidx_t *a; saidx_t *b, *c; saint_t d, e; }stack[STACK_SIZE];
+ saidx_t *a, *b, *c;
+ saidx_t t;
+ saidx_t v, x = 0;
+ saidx_t incr = ISAd - ISA;
+ saint_t limit, next;
+ saint_t ssize, trlink = -1;
+
+ for(ssize = 0, limit = tr_ilg(last - first);;) {
+
+ if(limit < 0) {
+ if(limit == -1) {
+ /* tandem repeat partition */
+ tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1);
+
+ /* update ranks */
+ if(a < last) {
+ for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; }
+ }
+ if(b < last) {
+ for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; }
+ }
+
+ /* push */
+ if(1 < (b - a)) {
+ STACK_PUSH5(NULL, a, b, 0, 0);
+ STACK_PUSH5(ISAd - incr, first, last, -2, trlink);
+ trlink = ssize - 2;
+ }
+ if((a - first) <= (last - b)) {
+ if(1 < (a - first)) {
+ STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink);
+ last = a, limit = tr_ilg(a - first);
+ } else if(1 < (last - b)) {
+ first = b, limit = tr_ilg(last - b);
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ } else {
+ if(1 < (last - b)) {
+ STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink);
+ first = b, limit = tr_ilg(last - b);
+ } else if(1 < (a - first)) {
+ last = a, limit = tr_ilg(a - first);
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ } else if(limit == -2) {
+ /* tandem repeat copy */
+ a = stack[--ssize].b, b = stack[ssize].c;
+ if(stack[ssize].d == 0) {
+ tr_copy(ISA, SA, first, a, b, last, ISAd - ISA);
+ } else {
+ if(0 <= trlink) { stack[trlink].d = -1; }
+ tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA);
+ }
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ } else {
+ /* sorted partition */
+ if(0 <= *first) {
+ a = first;
+ do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a));
+ first = a;
+ }
+ if(first < last) {
+ a = first; do { *a = ~*a; } while(*++a < 0);
+ next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1;
+ if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } }
+
+ /* push */
+ if(trbudget_check(budget, a - first)) {
+ if((a - first) <= (last - a)) {
+ STACK_PUSH5(ISAd, a, last, -3, trlink);
+ ISAd += incr, last = a, limit = next;
+ } else {
+ if(1 < (last - a)) {
+ STACK_PUSH5(ISAd + incr, first, a, next, trlink);
+ first = a, limit = -3;
+ } else {
+ ISAd += incr, last = a, limit = next;
+ }
+ }
+ } else {
+ if(0 <= trlink) { stack[trlink].d = -1; }
+ if(1 < (last - a)) {
+ first = a, limit = -3;
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ continue;
+ }
+
+ if((last - first) <= TR_INSERTIONSORT_THRESHOLD) {
+ tr_insertionsort(ISAd, first, last);
+ limit = -3;
+ continue;
+ }
+
+ if(limit-- == 0) {
+ tr_heapsort(ISAd, first, last - first);
+ for(a = last - 1; first < a; a = b) {
+ for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; }
+ }
+ limit = -3;
+ continue;
+ }
+
+ /* choose pivot */
+ a = tr_pivot(ISAd, first, last);
+ SWAP(*first, *a);
+ v = ISAd[*first];
+
+ /* partition */
+ tr_partition(ISAd, first, first + 1, last, &a, &b, v);
+ if((last - first) != (b - a)) {
+ next = (ISA[*a] != v) ? tr_ilg(b - a) : -1;
+
+ /* update ranks */
+ for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; }
+ if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } }
+
+ /* push */
+ if((1 < (b - a)) && (trbudget_check(budget, b - a))) {
+ if((a - first) <= (last - b)) {
+ if((last - b) <= (b - a)) {
+ if(1 < (a - first)) {
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ last = a;
+ } else if(1 < (last - b)) {
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ first = b;
+ } else {
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else if((a - first) <= (b - a)) {
+ if(1 < (a - first)) {
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ last = a;
+ } else {
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else {
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else {
+ if((a - first) <= (b - a)) {
+ if(1 < (last - b)) {
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ first = b;
+ } else if(1 < (a - first)) {
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ last = a;
+ } else {
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else if((last - b) <= (b - a)) {
+ if(1 < (last - b)) {
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ STACK_PUSH5(ISAd + incr, a, b, next, trlink);
+ first = b;
+ } else {
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ } else {
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ ISAd += incr, first = a, last = b, limit = next;
+ }
+ }
+ } else {
+ if((1 < (b - a)) && (0 <= trlink)) { stack[trlink].d = -1; }
+ if((a - first) <= (last - b)) {
+ if(1 < (a - first)) {
+ STACK_PUSH5(ISAd, b, last, limit, trlink);
+ last = a;
+ } else if(1 < (last - b)) {
+ first = b;
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ } else {
+ if(1 < (last - b)) {
+ STACK_PUSH5(ISAd, first, a, limit, trlink);
+ first = b;
+ } else if(1 < (a - first)) {
+ last = a;
+ } else {
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ }
+ } else {
+ if(trbudget_check(budget, last - first)) {
+ limit = tr_ilg(last - first), ISAd += incr;
+ } else {
+ if(0 <= trlink) { stack[trlink].d = -1; }
+ STACK_POP5(ISAd, first, last, limit, trlink);
+ }
+ }
+ }
+#undef STACK_SIZE
+}
+
+
+
+/*---------------------------------------------------------------------------*/
+
+/*- Function -*/
+
+/* Tandem repeat sort */
+void
+trsort(saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth) {
+ saidx_t *ISAd;
+ saidx_t *first, *last;
+ trbudget_t budget;
+ saidx_t t, skip, unsorted;
+
+ trbudget_init(&budget, tr_ilg(n) * 2 / 3, n);
+/* trbudget_init(&budget, tr_ilg(n) * 3 / 4, n); */
+ for(ISAd = ISA + depth; -n < *SA; ISAd += ISAd - ISA) {
+ first = SA;
+ skip = 0;
+ unsorted = 0;
+ do {
+ if((t = *first) < 0) { first -= t; skip += t; }
+ else {
+ if(skip != 0) { *(first + skip) = skip; skip = 0; }
+ last = SA + ISA[t] + 1;
+ if(1 < (last - first)) {
+ budget.count = 0;
+ tr_introsort(ISA, ISAd, SA, first, last, &budget);
+ if(budget.count != 0) { unsorted += budget.count; }
+ else { skip = first - last; }
+ } else if((last - first) == 1) {
+ skip = -1;
+ }
+ first = last;
+ }
+ } while(first < (SA + n));
+ if(skip != 0) { *(first + skip) = skip; }
+ if(unsorted == 0) { break; }
+ }
+}
diff --git a/libdivsufsort/lib/utils.c b/libdivsufsort/lib/utils.c
new file mode 100644
index 0000000..90fb23e
--- /dev/null
+++ b/libdivsufsort/lib/utils.c
@@ -0,0 +1,381 @@
+/*
+ * utils.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.
+ */
+
+#include "divsufsort_private.h"
+
+
+/*- Private Function -*/
+
+/* Binary search for inverse bwt. */
+static
+saidx_t
+binarysearch_lower(const saidx_t *A, saidx_t size, saidx_t value) {
+ saidx_t half, i;
+ for(i = 0, half = size >> 1;
+ 0 < size;
+ size = half, half >>= 1) {
+ if(A[i + half] < value) {
+ i += half + 1;
+ half -= (size & 1) ^ 1;
+ }
+ }
+ return i;
+}
+
+
+/*- Functions -*/
+
+/* Burrows-Wheeler transform. */
+saint_t
+bw_transform(const sauchar_t *T, sauchar_t *U, saidx_t *SA,
+ saidx_t n, saidx_t *idx) {
+ saidx_t *A, i, j, p, t;
+ saint_t c;
+
+ /* Check arguments. */
+ if((T == NULL) || (U == NULL) || (n < 0) || (idx == NULL)) { return -1; }
+ if(n <= 1) {
+ if(n == 1) { U[0] = T[0]; }
+ *idx = n;
+ return 0;
+ }
+
+ if((A = SA) == NULL) {
+ i = divbwt(T, U, NULL, n);
+ if(0 <= i) { *idx = i; i = 0; }
+ return (saint_t)i;
+ }
+
+ /* BW transform. */
+ if(T == U) {
+ t = n;
+ for(i = 0, j = 0; i < n; ++i) {
+ p = t - 1;
+ t = A[i];
+ if(0 <= p) {
+ c = T[j];
+ U[j] = (j <= p) ? T[p] : (sauchar_t)A[p];
+ A[j] = c;
+ j++;
+ } else {
+ *idx = i;
+ }
+ }
+ p = t - 1;
+ if(0 <= p) {
+ c = T[j];
+ U[j] = (j <= p) ? T[p] : (sauchar_t)A[p];
+ A[j] = c;
+ } else {
+ *idx = i;
+ }
+ } else {
+ U[0] = T[n - 1];
+ for(i = 0; A[i] != 0; ++i) { U[i + 1] = T[A[i] - 1]; }
+ *idx = i + 1;
+ for(++i; i < n; ++i) { U[i] = T[A[i] - 1]; }
+ }
+
+ if(SA == NULL) {
+ /* Deallocate memory. */
+ free(A);
+ }
+
+ return 0;
+}
+
+/* Inverse Burrows-Wheeler transform. */
+saint_t
+inverse_bw_transform(const sauchar_t *T, sauchar_t *U, saidx_t *A,
+ saidx_t n, saidx_t idx) {
+ saidx_t C[ALPHABET_SIZE];
+ sauchar_t D[ALPHABET_SIZE];
+ saidx_t *B;
+ saidx_t i, p;
+ saint_t c, d;
+
+ /* Check arguments. */
+ if((T == NULL) || (U == NULL) || (n < 0) || (idx < 0) ||
+ (n < idx) || ((0 < n) && (idx == 0))) {
+ return -1;
+ }
+ if(n <= 1) { return 0; }
+
+ if((B = A) == NULL) {
+ /* Allocate n*sizeof(saidx_t) bytes of memory. */
+ if((B = (saidx_t *)malloc((size_t)n * sizeof(saidx_t))) == NULL) { return -2; }
+ }
+
+ /* Inverse BW transform. */
+ for(c = 0; c < ALPHABET_SIZE; ++c) { C[c] = 0; }
+ for(i = 0; i < n; ++i) { ++C[T[i]]; }
+ for(c = 0, d = 0, i = 0; c < ALPHABET_SIZE; ++c) {
+ p = C[c];
+ if(0 < p) {
+ C[c] = i;
+ D[d++] = (sauchar_t)c;
+ i += p;
+ }
+ }
+ for(i = 0; i < idx; ++i) { B[C[T[i]]++] = i; }
+ for( ; i < n; ++i) { B[C[T[i]]++] = i + 1; }
+ for(c = 0; c < d; ++c) { C[c] = C[D[c]]; }
+ for(i = 0, p = idx; i < n; ++i) {
+ U[i] = D[binarysearch_lower(C, d, p)];
+ p = B[p - 1];
+ }
+
+ if(A == NULL) {
+ /* Deallocate memory. */
+ free(B);
+ }
+
+ return 0;
+}
+
+/* Checks the suffix array SA of the string T. */
+saint_t
+sufcheck(const sauchar_t *T, const saidx_t *SA,
+ saidx_t n, saint_t verbose) {
+ saidx_t C[ALPHABET_SIZE];
+ saidx_t i, p, q, t;
+ saint_t c;
+
+ if(verbose) { fprintf(stderr, "sufcheck: "); }
+
+ /* Check arguments. */
+ if((T == NULL) || (SA == NULL) || (n < 0)) {
+ if(verbose) { fprintf(stderr, "Invalid arguments.\n"); }
+ return -1;
+ }
+ if(n == 0) {
+ if(verbose) { fprintf(stderr, "Done.\n"); }
+ return 0;
+ }
+
+ /* check range: [0..n-1] */
+ for(i = 0; i < n; ++i) {
+ if((SA[i] < 0) || (n <= SA[i])) {
+ if(verbose) {
+ fprintf(stderr, "Out of the range [0,%" PRIdSAIDX_T "].\n"
+ " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "\n",
+ n - 1, i, SA[i]);
+ }
+ return -2;
+ }
+ }
+
+ /* check first characters. */
+ for(i = 1; i < n; ++i) {
+ if(T[SA[i - 1]] > T[SA[i]]) {
+ if(verbose) {
+ fprintf(stderr, "Suffixes in wrong order.\n"
+ " T[SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "]=%d"
+ " > T[SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "]=%d\n",
+ i - 1, SA[i - 1], T[SA[i - 1]], i, SA[i], T[SA[i]]);
+ }
+ return -3;
+ }
+ }
+
+ /* check suffixes. */
+ for(i = 0; i < ALPHABET_SIZE; ++i) { C[i] = 0; }
+ for(i = 0; i < n; ++i) { ++C[T[i]]; }
+ for(i = 0, p = 0; i < ALPHABET_SIZE; ++i) {
+ t = C[i];
+ C[i] = p;
+ p += t;
+ }
+
+ q = C[T[n - 1]];
+ C[T[n - 1]] += 1;
+ for(i = 0; i < n; ++i) {
+ p = SA[i];
+ if(0 < p) {
+ c = T[--p];
+ t = C[c];
+ } else {
+ c = T[p = n - 1];
+ t = q;
+ }
+ if((t < 0) || (p != SA[t])) {
+ if(verbose) {
+ fprintf(stderr, "Suffix in wrong position.\n"
+ " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T " or\n"
+ " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "\n",
+ t, (0 <= t) ? SA[t] : -1, i, SA[i]);
+ }
+ return -4;
+ }
+ if(t != q) {
+ ++C[c];
+ if((n <= C[c]) || (T[SA[C[c]]] != c)) { C[c] = -1; }
+ }
+ }
+
+ if(1 <= verbose) { fprintf(stderr, "Done.\n"); }
+ return 0;
+}
+
+
+static
+int
+_compare(const sauchar_t *T, saidx_t Tsize,
+ const sauchar_t *P, saidx_t Psize,
+ saidx_t suf, saidx_t *match) {
+ saidx_t i, j;
+ saint_t r;
+ for(i = suf + *match, j = *match, r = 0;
+ (i < Tsize) && (j < Psize) && ((r = T[i] - P[j]) == 0); ++i, ++j) { }
+ *match = j;
+ return (r == 0) ? -(j != Psize) : r;
+}
+
+/* Search for the pattern P in the string T. */
+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 *idx) {
+ saidx_t size, lsize, rsize, half;
+ saidx_t match, lmatch, rmatch;
+ saidx_t llmatch, lrmatch, rlmatch, rrmatch;
+ saidx_t i, j, k;
+ saint_t r;
+
+ if(idx != NULL) { *idx = -1; }
+ if((T == NULL) || (P == NULL) || (SA == NULL) ||
+ (Tsize < 0) || (Psize < 0) || (SAsize < 0)) { return -1; }
+ if((Tsize == 0) || (SAsize == 0)) { return 0; }
+ if(Psize == 0) { if(idx != NULL) { *idx = 0; } return SAsize; }
+
+ for(i = j = k = 0, lmatch = rmatch = 0, size = SAsize, half = size >> 1;
+ 0 < size;
+ size = half, half >>= 1) {
+ match = MIN(lmatch, rmatch);
+ r = _compare(T, Tsize, P, Psize, SA[i + half], &match);
+ if(r < 0) {
+ i += half + 1;
+ half -= (size & 1) ^ 1;
+ lmatch = match;
+ } else if(r > 0) {
+ rmatch = match;
+ } else {
+ lsize = half, j = i, rsize = size - half - 1, k = i + half + 1;
+
+ /* left part */
+ for(llmatch = lmatch, lrmatch = match, half = lsize >> 1;
+ 0 < lsize;
+ lsize = half, half >>= 1) {
+ lmatch = MIN(llmatch, lrmatch);
+ r = _compare(T, Tsize, P, Psize, SA[j + half], &lmatch);
+ if(r < 0) {
+ j += half + 1;
+ half -= (lsize & 1) ^ 1;
+ llmatch = lmatch;
+ } else {
+ lrmatch = lmatch;
+ }
+ }
+
+ /* right part */
+ for(rlmatch = match, rrmatch = rmatch, half = rsize >> 1;
+ 0 < rsize;
+ rsize = half, half >>= 1) {
+ rmatch = MIN(rlmatch, rrmatch);
+ r = _compare(T, Tsize, P, Psize, SA[k + half], &rmatch);
+ if(r <= 0) {
+ k += half + 1;
+ half -= (rsize & 1) ^ 1;
+ rlmatch = rmatch;
+ } else {
+ rrmatch = rmatch;
+ }
+ }
+
+ break;
+ }
+ }
+
+ if(idx != NULL) { *idx = (0 < (k - j)) ? j : i; }
+ return k - j;
+}
+
+/* Search for the character c in the string T. */
+saidx_t
+sa_simplesearch(const sauchar_t *T, saidx_t Tsize,
+ const saidx_t *SA, saidx_t SAsize,
+ saint_t c, saidx_t *idx) {
+ saidx_t size, lsize, rsize, half;
+ saidx_t i, j, k, p;
+ saint_t r;
+
+ if(idx != NULL) { *idx = -1; }
+ if((T == NULL) || (SA == NULL) || (Tsize < 0) || (SAsize < 0)) { return -1; }
+ if((Tsize == 0) || (SAsize == 0)) { return 0; }
+
+ for(i = j = k = 0, size = SAsize, half = size >> 1;
+ 0 < size;
+ size = half, half >>= 1) {
+ p = SA[i + half];
+ r = (p < Tsize) ? T[p] - c : -1;
+ if(r < 0) {
+ i += half + 1;
+ half -= (size & 1) ^ 1;
+ } else if(r == 0) {
+ lsize = half, j = i, rsize = size - half - 1, k = i + half + 1;
+
+ /* left part */
+ for(half = lsize >> 1;
+ 0 < lsize;
+ lsize = half, half >>= 1) {
+ p = SA[j + half];
+ r = (p < Tsize) ? T[p] - c : -1;
+ if(r < 0) {
+ j += half + 1;
+ half -= (lsize & 1) ^ 1;
+ }
+ }
+
+ /* right part */
+ for(half = rsize >> 1;
+ 0 < rsize;
+ rsize = half, half >>= 1) {
+ p = SA[k + half];
+ r = (p < Tsize) ? T[p] - c : -1;
+ if(r <= 0) {
+ k += half + 1;
+ half -= (rsize & 1) ^ 1;
+ }
+ }
+
+ break;
+ }
+ }
+
+ if(idx != NULL) { *idx = (0 < (k - j)) ? j : i; }
+ return k - j;
+}
diff --git a/libdivsufsort/pkgconfig/CMakeLists.txt b/libdivsufsort/pkgconfig/CMakeLists.txt
new file mode 100644
index 0000000..ee7063c
--- /dev/null
+++ b/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/libdivsufsort/pkgconfig/libdivsufsort.pc.cmake b/libdivsufsort/pkgconfig/libdivsufsort.pc.cmake
new file mode 100644
index 0000000..6419d1e
--- /dev/null
+++ b/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}
