1 /* 2 * divsufsort_private.h for libdivsufsort 3 * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. 4 * 5 * Permission is hereby granted, free of charge, to any person 6 * obtaining a copy of this software and associated documentation 7 * files (the "Software"), to deal in the Software without 8 * restriction, including without limitation the rights to use, 9 * copy, modify, merge, publish, distribute, sublicense, and/or sell 10 * copies of the Software, and to permit persons to whom the 11 * Software is furnished to do so, subject to the following 12 * conditions: 13 * 14 * The above copyright notice and this permission notice shall be 15 * included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 24 * OTHER DEALINGS IN THE SOFTWARE. 25 */ 26 27 #ifndef _DIVSUFSORT_PRIVATE_H 28 #define _DIVSUFSORT_PRIVATE_H 1 29 30 #if HAVE_CONFIG_H 31 # include "config.h" 32 #endif 33 #include <assert.h> 34 #include <stdio.h> 35 #if HAVE_STRING_H 36 # include <string.h> 37 #endif 38 #if HAVE_STDLIB_H 39 # include <stdlib.h> 40 #endif 41 #if HAVE_MEMORY_H 42 # include <memory.h> 43 #endif 44 #if HAVE_STDDEF_H 45 # include <stddef.h> 46 #endif 47 #if HAVE_STRINGS_H 48 # include <strings.h> 49 #endif 50 #if HAVE_INTTYPES_H 51 # include <inttypes.h> 52 #else 53 # if HAVE_STDINT_H 54 # include <stdint.h> 55 # endif 56 #endif 57 58 #include <tuple> 59 #include "said_traits.hpp" 60 61 62 /* for sssort.c */ 63 #if defined(SS_INSERTIONSORT_THRESHOLD) 64 # if SS_INSERTIONSORT_THRESHOLD < 1 65 # undef SS_INSERTIONSORT_THRESHOLD 66 # define SS_INSERTIONSORT_THRESHOLD (1) 67 # endif 68 #else 69 # define SS_INSERTIONSORT_THRESHOLD (8) 70 #endif 71 #if defined(SS_BLOCKSIZE) 72 # if SS_BLOCKSIZE < 0 73 # undef SS_BLOCKSIZE 74 # define SS_BLOCKSIZE (0) 75 # elif 32768 <= SS_BLOCKSIZE 76 # undef SS_BLOCKSIZE 77 # define SS_BLOCKSIZE (32767) 78 # endif 79 #else 80 # define SS_BLOCKSIZE (1024) 81 #endif 82 /* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */ 83 #if SS_BLOCKSIZE == 0 84 # define SS_MISORT_STACKSIZE (96) 85 #elif SS_BLOCKSIZE <= 4096 86 # define SS_MISORT_STACKSIZE (16) 87 #else 88 # define SS_MISORT_STACKSIZE (24) 89 #endif 90 91 #define SS_SMERGE_STACKSIZE (32) 92 93 /* for trsort.c */ 94 #define TR_INSERTIONSORT_THRESHOLD (8) 95 #define TR_STACKSIZE (96) 96 97 namespace compactsufsort_imp { 98 extern const saint_t lg_table[256]; 99 100 template<typename T, int L> 101 struct ilg_imp { }; 102 103 template<typename T> 104 struct ilg_imp<T, 4> { 105 static saint_t ilg(T n) { 106 return ((n & 0xffff0000) ? 107 ((n & 0xff000000) ? 108 24 + lg_table[(n >> 24) & 0xff] : 109 16 + lg_table[(n >> 16) & 0xff]) : 110 ((n & 0x0000ff00) ? 111 8 + lg_table[(n >> 8) & 0xff] : 112 0 + lg_table[(n ) & 0xff])); 113 } 114 }; 115 116 template<typename T> 117 struct ilg_imp<T, 8> { 118 static inline saint_t ilg(T n) { 119 return ((n >> 32) ? 32 + ilg_imp<T, 4>::ilg((int32_t)(n >> 32)) : ilg_imp<T, 4>::ilg((int32_t)(n & 0xffffffff))); 120 } 121 }; 122 123 template<typename T> 124 inline saint_t ilg(T n) { 125 return ilg_imp<T, sizeof(T)>::ilg(n); 126 } 127 128 extern const saint_t sqq_table[256]; 129 130 template<typename SAIDX> 131 SAIDX 132 isqrt(SAIDX x) { 133 SAIDX y, e; 134 135 if(x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; } 136 e = (x & 0xffff0000) ? 137 ((x & 0xff000000) ? 138 24 + lg_table[(x >> 24) & 0xff] : 139 16 + lg_table[(x >> 16) & 0xff]) : 140 ((x & 0x0000ff00) ? 141 8 + lg_table[(x >> 8) & 0xff] : 142 0 + lg_table[(x >> 0) & 0xff]); 143 144 if(e >= 16) { 145 y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7); 146 if(e >= 24) { y = (y + 1 + x / y) >> 1; } 147 y = (y + 1 + x / y) >> 1; 148 } else if(e >= 8) { 149 y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1; 150 } else { 151 return sqq_table[x] >> 4; 152 } 153 154 return (x < (y * y)) ? y - 1 : y; 155 } 156 157 158 } // namespace compactsufsort_imp 159 160 #endif /* _DIVSUFSORT_PRIVATE_H */ 161