tudocomp
– The TU Dortmund Compression Framework
divsufsort_private.hpp
Go to the documentation of this file.
1 /*
2  * This file integrates customized parts of divsufsort into tudocomp.
3  * divsufsort is licensed under the MIT License, which follows.
4  *
5  * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved.
6  *
7  * Permission is hereby granted, free of charge, to any person
8  * obtaining a copy of this software and associated documentation
9  * files (the "Software"), to deal in the Software without
10  * restriction, including without limitation the rights to use,
11  * copy, modify, merge, publish, distribute, sublicense, and/or sell
12  * copies of the Software, and to permit persons to whom the
13  * Software is furnished to do so, subject to the following
14  * conditions:
15  *
16  * The above copyright notice and this permission notice shall be
17  * included in all copies or substantial portions of the Software.
18  *
19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
21  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
23  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
24  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
26  * OTHER DEALINGS IN THE SOFTWARE.
27  */
28 
29 #pragma once
30 
31 #include <tudocomp/def.hpp>
32 
34 namespace tdc {
35 namespace libdivsufsort {
36 
37 /*- Constants -*/
38 #define ALPHABET_SIZE (UINT8_MAX + 1)
39 
40 /* for divsufsort.c */
41 #define BUCKET_A_SIZE (ALPHABET_SIZE)
42 #define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE)
43 /* for sssort.c */
44 #if defined(SS_INSERTIONSORT_THRESHOLD)
45 # if SS_INSERTIONSORT_THRESHOLD < 1
46 # undef SS_INSERTIONSORT_THRESHOLD
47 # define SS_INSERTIONSORT_THRESHOLD (1)
48 # endif
49 #else
50 # define SS_INSERTIONSORT_THRESHOLD (8)
51 #endif
52 #if defined(SS_BLOCKSIZE)
53 # if SS_BLOCKSIZE < 0
54 # undef SS_BLOCKSIZE
55 # define SS_BLOCKSIZE (0)
56 # elif 32768 <= SS_BLOCKSIZE
57 # undef SS_BLOCKSIZE
58 # define SS_BLOCKSIZE (32767)
59 # endif
60 #else
61 # define SS_BLOCKSIZE (1024)
62 #endif
63 /* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */
64 #if SS_BLOCKSIZE == 0
65 const ssize_t SS_MISORT_STACKSIZE = divsufsort64 ? 96 : 64;
66 #elif SS_BLOCKSIZE <= 4096
67 # define SS_MISORT_STACKSIZE (16)
68 #else
69 # define SS_MISORT_STACKSIZE (24)
70 #endif
71 
72 const ssize_t SS_SMERGE_STACKSIZE = divsufsort64 ? 64 : 32;
73 
74 /* for trsort.c */
75 #define TR_INSERTIONSORT_THRESHOLD (8)
76 const ssize_t TR_STACKSIZE = divsufsort64 ? 96 : 64;
77 
78 /*- Macros -*/
79 #ifndef SWAP
80 # define SWAP(_a, _b) do { t = (_a); (_a) = (_b); (_b) = t; } while(0)
81 #endif /* SWAP */
82 #ifndef MIN
83 # define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b))
84 #endif /* MIN */
85 #ifndef MAX
86 # define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b))
87 #endif /* MAX */
88 #define STACK_PUSH(_a, _b, _c, _d)\
89  do {\
90  assert(ssize < STACK_SIZE);\
91  stack[ssize].a = (_a), stack[ssize].b = (_b),\
92  stack[ssize].c = (_c), stack[ssize++].d = (_d);\
93  } while(0)
94 #define STACK_PUSH5(_a, _b, _c, _d, _e)\
95  do {\
96  assert(ssize < STACK_SIZE);\
97  stack[ssize].a = (_a), stack[ssize].b = (_b),\
98  stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\
99  } while(0)
100 #define STACK_POP(_a, _b, _c, _d)\
101  do {\
102  assert(0 <= ssize);\
103  if(ssize == 0) { return; }\
104  (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\
105  (_c) = stack[ssize].c, (_d) = stack[ssize].d;\
106  } while(0)
107 #define STACK_POP5(_a, _b, _c, _d, _e)\
108  do {\
109  assert(0 <= ssize);\
110  if(ssize == 0) { return; }\
111  (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\
112  (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\
113  } while(0)
114 /* for divsufsort.c */
115 #define BUCKET_A(_c0) bucket_A[(_c0)]
116 #if ALPHABET_SIZE == 256
117 #define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)])
118 #define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)])
119 #else
120 #define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)])
121 #define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)])
122 #endif
123 
124 }} //ns
126 
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11