Added 64-bit version of divsufsort.

10 files changed, 137 insertions, 49 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index bceca8f..83c2726 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -44,6 +44,7 @@ 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)
 
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index ebbef28..6c40cb4 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -99,6 +99,40 @@ else(HAVE_INT32_T)
     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 "\"ldd\"")
+    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 "")
@@ -111,9 +145,18 @@ if(BUILD_SHARED_LIBS)
     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 include)
+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 include)
+endif(BUILD_DIVSUFSORT64)
diff --git a/include/divsufsort.h.cmake b/include/divsufsort.h.cmake
index 45c7b04..a3b8968 100644
--- a/include/divsufsort.h.cmake
+++ b/include/divsufsort.h.cmake
@@ -1,5 +1,5 @@
 /*
- * divsufsort.h for libdivsufsort
+ * 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
@@ -24,8 +24,8 @@
  * OTHER DEALINGS IN THE SOFTWARE.
  */
 
-#ifndef _DIVSUFSORT_H
-#define _DIVSUFSORT_H 1
+#ifndef _DIVSUFSORT@W64BIT@_H
+#define _DIVSUFSORT@W64BIT@_H 1
 
 #ifdef __cplusplus
 extern "C" {
@@ -50,16 +50,16 @@ typedef @SAUCHAR_TYPE@ sauchar_t;
 #define SAINT_T
 typedef @SAINT32_TYPE@ saint_t;
 #endif /* SAINT_T */
-#ifndef SAIDX_T
-#define SAIDX_T
-typedef @SAINDEX_TYPE@ saidx_t;
-#endif /* SAIDX_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_T
-#define PRIdSAIDX_T @SAINDEX_PRId@
-#endif /* PRIdSAIDX_T */
+#ifndef PRIdSAIDX@W64BIT@_T
+#define PRIdSAIDX@W64BIT@_T @SAINDEX_PRId@
+#endif /* PRIdSAIDX@W64BIT@_T */
 
 
 /*- Prototypes -*/
@@ -73,7 +73,7 @@ typedef @SAINDEX_TYPE@ saidx_t;
  */
 DIVSUFSORT_API
 saint_t
-divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n);
+divsufsort@W64BIT@(const sauchar_t *T, saidx@W64BIT@_t *SA, saidx@W64BIT@_t n);
 
 /**
  * Constructs the burrows-wheeler transformed string of a given string.
@@ -84,8 +84,8 @@ divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n);
  * @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);
+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.
@@ -93,54 +93,54 @@ divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n);
  */
 DIVSUFSORT_API
 const char *
-divsufsort_version(void);
+divsufsort@W64BIT@_version(void);
 
 
 /* Burrows-Wheeler transform. */
 DIVSUFSORT_API
 saint_t
-bw_transform(const sauchar_t *T, sauchar_t *U,
-             saidx_t *SA /* can NULL */,
-             saidx_t n, saidx_t *idx);
+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 Burrows-Wheeler transform. */
 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);
+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 SA[0..n] 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);
+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. */
 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);
+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. */
 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);
+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_H */
+#endif /* _DIVSUFSORT@W64BIT@_H */
diff --git a/include/divsufsort_private.h b/include/divsufsort_private.h
index c0ab5a6..7e261c1 100644
--- a/include/divsufsort_private.h
+++ b/include/divsufsort_private.h
@@ -58,7 +58,28 @@ extern "C" {
 #  include <stdint.h>
 # endif
 #endif
-#include "divsufsort.h"
+#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 -*/
diff --git a/lib/CMakeLists.txt b/lib/CMakeLists.txt
index cbcb427..56e7942 100644
--- a/lib/CMakeLists.txt
+++ b/lib/CMakeLists.txt
@@ -1,8 +1,10 @@
 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.c sssort.c trsort.c utils.c)
+add_library(divsufsort ${divsufsort_SRCS})
 install(TARGETS divsufsort
   RUNTIME DESTINATION bin
   LIBRARY DESTINATION lib
@@ -12,3 +14,18 @@ set_target_properties(divsufsort PROPERTIES
   SOVERSION "${LIBRARY_VERSION_MAJOR}"
   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 bin
+    LIBRARY DESTINATION lib
+    ARCHIVE DESTINATION lib)
+  set_target_properties(divsufsort64 PROPERTIES
+    VERSION   "${LIBRARY_VERSION_FULL}"
+    SOVERSION "${LIBRARY_VERSION_MAJOR}"
+    DEFINE_SYMBOL DIVSUFSORT_BUILD_DLL
+    COMPILE_FLAGS "-DBUILD_DIVSUFSORT64"
+    RUNTIME_OUTPUT_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}/../examples")
+endif(BUILD_DIVSUFSORT64)
diff --git a/lib/divsufsort.c b/lib/divsufsort.c
index 568803f..85c3c43 100644
--- a/lib/divsufsort.c
+++ b/lib/divsufsort.c
@@ -340,8 +340,8 @@ divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n) {
   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 = malloc(BUCKET_A_SIZE * sizeof(saidx_t));
-  bucket_B = malloc(BUCKET_B_SIZE * 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));
 
   /* Suffixsort. */
   if((bucket_A != NULL) && (bucket_B != NULL)) {
@@ -367,9 +367,9 @@ divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n) {
   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 = malloc((n + 1) * sizeof(saidx_t)); }
-  bucket_A = malloc(BUCKET_A_SIZE * sizeof(saidx_t));
-  bucket_B = malloc(BUCKET_B_SIZE * sizeof(saidx_t));
+  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)) {
diff --git a/lib/trsort.c b/lib/trsort.c
index 4ec6a17..6fe3e67 100644
--- a/lib/trsort.c
+++ b/lib/trsort.c
@@ -44,19 +44,19 @@ static INLINE
 saint_t
 tr_ilg(saidx_t n) {
 #if defined(BUILD_DIVSUFSORT64)
-  return (n & 0xffffffff00000000) ?
-          ((n & 0xffff000000000000) ?
-            ((n & 0xff00000000000000) ?
+  return (n >> 32) ?
+          ((n >> 48) ?
+            ((n >> 56) ?
               56 + lg_table[(n >> 56) & 0xff] :
               48 + lg_table[(n >> 48) & 0xff]) :
-            ((n & 0x0000ff0000000000) ?
+            ((n >> 40) ?
               40 + lg_table[(n >> 40) & 0xff] :
               32 + lg_table[(n >> 32) & 0xff])) :
-          ((n & 0x00000000ffff0000) ?
-            ((n & 0x00000000ff000000) ?
+          ((n & 0xffff0000) ?
+            ((n & 0xff000000) ?
               24 + lg_table[(n >> 24) & 0xff] :
               16 + lg_table[(n >> 16) & 0xff]) :
-            ((n & 0x000000000000ff00) ?
+            ((n & 0x0000ff00) ?
                8 + lg_table[(n >>  8) & 0xff] :
                0 + lg_table[(n >>  0) & 0xff]));
 #else
diff --git a/lib/utils.c b/lib/utils.c
index 75bd274..90fb23e 100644
--- a/lib/utils.c
+++ b/lib/utils.c
@@ -126,7 +126,7 @@ inverse_bw_transform(const sauchar_t *T, sauchar_t *U, saidx_t *A,
 
   if((B = A) == NULL) {
     /* Allocate n*sizeof(saidx_t) bytes of memory. */
-    if((B = malloc(n * sizeof(saidx_t))) == NULL) { return -2; }
+    if((B = (saidx_t *)malloc((size_t)n * sizeof(saidx_t))) == NULL) { return -2; }
   }
 
   /* Inverse BW transform. */
diff --git a/pkgconfig/CMakeLists.txt b/pkgconfig/CMakeLists.txt
index c9e57ab..06470be 100644
--- a/pkgconfig/CMakeLists.txt
+++ b/pkgconfig/CMakeLists.txt
@@ -1,3 +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 lib/pkgconfig)
+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 lib/pkgconfig)
+endif(BUILD_DIVSUFSORT64)
diff --git a/pkgconfig/libdivsufsort.pc.cmake b/pkgconfig/libdivsufsort.pc.cmake
index 878e47e..1645a8b 100644
--- a/pkgconfig/libdivsufsort.pc.cmake
+++ b/pkgconfig/libdivsufsort.pc.cmake
@@ -3,9 +3,9 @@ exec_prefix=${prefix}
 libdir=${exec_prefix}/lib
 includedir=${prefix}/include
 
-Name: @PROJECT_NAME@
+Name: @PROJECT_NAME@@W64BIT@
 Description: @PROJECT_DESCRIPTION@
 Version: @PROJECT_VERSION_FULL@
 URL: @PROJECT_URL@
-Libs: -L${libdir} -ldivsufsort
+Libs: -L${libdir} -ldivsufsort@W64BIT@
 Cflags: -I${includedir}