tudocomp
– The TU Dortmund Compression Framework
divsufsort_def.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <tudocomp/def.hpp>
4 
6 namespace tdc {
7 namespace libdivsufsort {
8 
9 // core type definitions
10 using saidx_t = ssize_t;
11 using saint_t = int;
12 using sauchar_t = uliteral_t;
13 
14 // flag for 64-bit
15 const bool divsufsort64 = (sizeof(saidx_t) > 4);
16 
17 // common definitions
18 const saint_t lg_table[256]= {
19  -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,
20  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,
21  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,
22  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,
23  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,
24  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,
25  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,
26  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
27 };
28 
29 #if SS_BLOCKSIZE == 0
30 
31 template<typename T, typename X = void>
32 struct ilg_dispatch_t {};
33 
34 template<typename T>
35 struct ilg_dispatch_t<T, typename std::enable_if<sizeof(T) * CHAR_BIT == 32>::type> {
36  inline static saint_t calc(T x) {
37  int32_t n = x;
38  return (n & 0xffff0000) ?
39  ((n & 0xff000000) ?
40  24 + lg_table[(n >> 24) & 0xff] :
41  16 + lg_table[(n >> 16) & 0xff]) :
42  ((n & 0x0000ff00) ?
43  8 + lg_table[(n >> 8) & 0xff] :
44  0 + lg_table[(n >> 0) & 0xff]);
45  }
46 };
47 
48 template<typename T>
49 struct ilg_dispatch_t<T, typename std::enable_if<sizeof(T) * CHAR_BIT == 64>::type> {
50  inline static saint_t calc(T x) {
51  int64_t n = x;
52  return (n >> 32) ?
53  ((n >> 48) ?
54  ((n >> 56) ?
55  56 + lg_table[(n >> 56) & 0xff] :
56  48 + lg_table[(n >> 48) & 0xff]) :
57  ((n >> 40) ?
58  40 + lg_table[(n >> 40) & 0xff] :
59  32 + lg_table[(n >> 32) & 0xff])) :
60  ((n & 0xffff0000) ?
61  ((n & 0xff000000) ?
62  24 + lg_table[(n >> 24) & 0xff] :
63  16 + lg_table[(n >> 16) & 0xff]) :
64  ((n & 0x0000ff00) ?
65  8 + lg_table[(n >> 8) & 0xff] :
66  0 + lg_table[(n >> 0) & 0xff]));
67  }
68 };
69 
70 template<typename idx_t>
71 inline saint_t ilg(idx_t n) {
72  return ilg_dispatch_t<idx_t>::calc(n);
73 }
74 
75 #else
76 
77 inline saint_t ilg(saidx_t n) {
78  #if SS_BLOCKSIZE < 256
79  return lg_table[n];
80  #else
81  return (n & 0xff00) ?
82  8 + lg_table[(n >> 8) & 0xff] :
83  0 + lg_table[(n >> 0) & 0xff];
84  #endif
85 }
86 
87 #endif
88 
89 }} //ns
91 
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
uint8_t uliteral_t
Type to represent signed single literals.
Definition: def.hpp:131