gbdk-2020 | GameBoy Development Kit |
| download: https://git.y1.nz/archives/gbdk.tar.gz | |
| README | Files | Log | Refs | LICENSE |
gbdk-support/gbcompress/zx0/libdivsufsort/divsufsort_utils.c
1 /*
2 * utils.c 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 #include "divsufsort_private.h"
28
29
30 /*- Private Function -*/
31
32 #if 0
33 /* Binary search for inverse bwt. */
34 static
35 saidx_t
36 binarysearch_lower(const saidx_t *A, saidx_t size, saidx_t value) {
37 saidx_t half, i;
38 for(i = 0, half = size >> 1;
39 0 < size;
40 size = half, half >>= 1) {
41 if(A[i + half] < value) {
42 i += half + 1;
43 half -= (size & 1) ^ 1;
44 }
45 }
46 return i;
47 }
48
49
50 /*- Functions -*/
51
52 /* Burrows-Wheeler transform. */
53 saint_t
54 bw_transform(const sauchar_t *T, sauchar_t *U, saidx_t *SA,
55 saidx_t n, saidx_t *idx) {
56 saidx_t *A, i, j, p, t;
57 saint_t c;
58
59 /* Check arguments. */
60 if((T == NULL) || (U == NULL) || (n < 0) || (idx == NULL)) { return -1; }
61 if(n <= 1) {
62 if(n == 1) { U[0] = T[0]; }
63 *idx = n;
64 return 0;
65 }
66
67 if((A = SA) == NULL) {
68 i = divbwt(T, U, NULL, n);
69 if(0 <= i) { *idx = i; i = 0; }
70 return (saint_t)i;
71 }
72
73 /* BW transform. */
74 if(T == U) {
75 t = n;
76 for(i = 0, j = 0; i < n; ++i) {
77 p = t - 1;
78 t = A[i];
79 if(0 <= p) {
80 c = T[j];
81 U[j] = (j <= p) ? T[p] : (sauchar_t)A[p];
82 A[j] = c;
83 j++;
84 } else {
85 *idx = i;
86 }
87 }
88 p = t - 1;
89 if(0 <= p) {
90 c = T[j];
91 U[j] = (j <= p) ? T[p] : (sauchar_t)A[p];
92 A[j] = c;
93 } else {
94 *idx = i;
95 }
96 } else {
97 U[0] = T[n - 1];
98 for(i = 0; A[i] != 0; ++i) { U[i + 1] = T[A[i] - 1]; }
99 *idx = i + 1;
100 for(++i; i < n; ++i) { U[i] = T[A[i] - 1]; }
101 }
102
103 if(SA == NULL) {
104 /* Deallocate memory. */
105 free(A);
106 }
107
108 return 0;
109 }
110
111 /* Inverse Burrows-Wheeler transform. */
112 saint_t
113 inverse_bw_transform(const sauchar_t *T, sauchar_t *U, saidx_t *A,
114 saidx_t n, saidx_t idx) {
115 saidx_t C[ALPHABET_SIZE];
116 sauchar_t D[ALPHABET_SIZE];
117 saidx_t *B;
118 saidx_t i, p;
119 saint_t c, d;
120
121 /* Check arguments. */
122 if((T == NULL) || (U == NULL) || (n < 0) || (idx < 0) ||
123 (n < idx) || ((0 < n) && (idx == 0))) {
124 return -1;
125 }
126 if(n <= 1) { return 0; }
127
128 if((B = A) == NULL) {
129 /* Allocate n*sizeof(saidx_t) bytes of memory. */
130 if((B = (saidx_t *)malloc((size_t)n * sizeof(saidx_t))) == NULL) { return -2; }
131 }
132
133 /* Inverse BW transform. */
134 for(c = 0; c < ALPHABET_SIZE; ++c) { C[c] = 0; }
135 for(i = 0; i < n; ++i) { ++C[T[i]]; }
136 for(c = 0, d = 0, i = 0; c < ALPHABET_SIZE; ++c) {
137 p = C[c];
138 if(0 < p) {
139 C[c] = i;
140 D[d++] = (sauchar_t)c;
141 i += p;
142 }
143 }
144 for(i = 0; i < idx; ++i) { B[C[T[i]]++] = i; }
145 for( ; i < n; ++i) { B[C[T[i]]++] = i + 1; }
146 for(c = 0; c < d; ++c) { C[c] = C[D[c]]; }
147 for(i = 0, p = idx; i < n; ++i) {
148 U[i] = D[binarysearch_lower(C, d, p)];
149 p = B[p - 1];
150 }
151
152 if(A == NULL) {
153 /* Deallocate memory. */
154 free(B);
155 }
156
157 return 0;
158 }
159
160 /* Checks the suffix array SA of the string T. */
161 saint_t
162 sufcheck(const sauchar_t *T, const saidx_t *SA,
163 saidx_t n, saint_t verbose) {
164 saidx_t C[ALPHABET_SIZE];
165 saidx_t i, p, q, t;
166 saint_t c;
167
168 if(verbose) { fprintf(stderr, "sufcheck: "); }
169
170 /* Check arguments. */
171 if((T == NULL) || (SA == NULL) || (n < 0)) {
172 if(verbose) { fprintf(stderr, "Invalid arguments.\n"); }
173 return -1;
174 }
175 if(n == 0) {
176 if(verbose) { fprintf(stderr, "Done.\n"); }
177 return 0;
178 }
179
180 /* check range: [0..n-1] */
181 for(i = 0; i < n; ++i) {
182 if((SA[i] < 0) || (n <= SA[i])) {
183 if(verbose) {
184 fprintf(stderr, "Out of the range [0,%" PRIdSAIDX_T "].\n"
185 " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "\n",
186 n - 1, i, SA[i]);
187 }
188 return -2;
189 }
190 }
191
192 /* check first characters. */
193 for(i = 1; i < n; ++i) {
194 if(T[SA[i - 1]] > T[SA[i]]) {
195 if(verbose) {
196 fprintf(stderr, "Suffixes in wrong order.\n"
197 " T[SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "]=%d"
198 " > T[SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "]=%d\n",
199 i - 1, SA[i - 1], T[SA[i - 1]], i, SA[i], T[SA[i]]);
200 }
201 return -3;
202 }
203 }
204
205 /* check suffixes. */
206 for(i = 0; i < ALPHABET_SIZE; ++i) { C[i] = 0; }
207 for(i = 0; i < n; ++i) { ++C[T[i]]; }
208 for(i = 0, p = 0; i < ALPHABET_SIZE; ++i) {
209 t = C[i];
210 C[i] = p;
211 p += t;
212 }
213
214 q = C[T[n - 1]];
215 C[T[n - 1]] += 1;
216 for(i = 0; i < n; ++i) {
217 p = SA[i];
218 if(0 < p) {
219 c = T[--p];
220 t = C[c];
221 } else {
222 c = T[p = n - 1];
223 t = q;
224 }
225 if((t < 0) || (p != SA[t])) {
226 if(verbose) {
227 fprintf(stderr, "Suffix in wrong position.\n"
228 " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T " or\n"
229 " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "\n",
230 t, (0 <= t) ? SA[t] : -1, i, SA[i]);
231 }
232 return -4;
233 }
234 if(t != q) {
235 ++C[c];
236 if((n <= C[c]) || (T[SA[C[c]]] != c)) { C[c] = -1; }
237 }
238 }
239
240 if(1 <= verbose) { fprintf(stderr, "Done.\n"); }
241 return 0;
242 }
243
244
245 static
246 int
247 _compare(const sauchar_t *T, saidx_t Tsize,
248 const sauchar_t *P, saidx_t Psize,
249 saidx_t suf, saidx_t *match) {
250 saidx_t i, j;
251 saint_t r;
252 for(i = suf + *match, j = *match, r = 0;
253 (i < Tsize) && (j < Psize) && ((r = T[i] - P[j]) == 0); ++i, ++j) { }
254 *match = j;
255 return (r == 0) ? -(j != Psize) : r;
256 }
257
258 /* Search for the pattern P in the string T. */
259 saidx_t
260 sa_search(const sauchar_t *T, saidx_t Tsize,
261 const sauchar_t *P, saidx_t Psize,
262 const saidx_t *SA, saidx_t SAsize,
263 saidx_t *idx) {
264 saidx_t size, lsize, rsize, half;
265 saidx_t match, lmatch, rmatch;
266 saidx_t llmatch, lrmatch, rlmatch, rrmatch;
267 saidx_t i, j, k;
268 saint_t r;
269
270 if(idx != NULL) { *idx = -1; }
271 if((T == NULL) || (P == NULL) || (SA == NULL) ||
272 (Tsize < 0) || (Psize < 0) || (SAsize < 0)) { return -1; }
273 if((Tsize == 0) || (SAsize == 0)) { return 0; }
274 if(Psize == 0) { if(idx != NULL) { *idx = 0; } return SAsize; }
275
276 for(i = j = k = 0, lmatch = rmatch = 0, size = SAsize, half = size >> 1;
277 0 < size;
278 size = half, half >>= 1) {
279 match = MIN(lmatch, rmatch);
280 r = _compare(T, Tsize, P, Psize, SA[i + half], &match);
281 if(r < 0) {
282 i += half + 1;
283 half -= (size & 1) ^ 1;
284 lmatch = match;
285 } else if(r > 0) {
286 rmatch = match;
287 } else {
288 lsize = half, j = i, rsize = size - half - 1, k = i + half + 1;
289
290 /* left part */
291 for(llmatch = lmatch, lrmatch = match, half = lsize >> 1;
292 0 < lsize;
293 lsize = half, half >>= 1) {
294 lmatch = MIN(llmatch, lrmatch);
295 r = _compare(T, Tsize, P, Psize, SA[j + half], &lmatch);
296 if(r < 0) {
297 j += half + 1;
298 half -= (lsize & 1) ^ 1;
299 llmatch = lmatch;
300 } else {
301 lrmatch = lmatch;
302 }
303 }
304
305 /* right part */
306 for(rlmatch = match, rrmatch = rmatch, half = rsize >> 1;
307 0 < rsize;
308 rsize = half, half >>= 1) {
309 rmatch = MIN(rlmatch, rrmatch);
310 r = _compare(T, Tsize, P, Psize, SA[k + half], &rmatch);
311 if(r <= 0) {
312 k += half + 1;
313 half -= (rsize & 1) ^ 1;
314 rlmatch = rmatch;
315 } else {
316 rrmatch = rmatch;
317 }
318 }
319
320 break;
321 }
322 }
323
324 if(idx != NULL) { *idx = (0 < (k - j)) ? j : i; }
325 return k - j;
326 }
327
328 /* Search for the character c in the string T. */
329 saidx_t
330 sa_simplesearch(const sauchar_t *T, saidx_t Tsize,
331 const saidx_t *SA, saidx_t SAsize,
332 saint_t c, saidx_t *idx) {
333 saidx_t size, lsize, rsize, half;
334 saidx_t i, j, k, p;
335 saint_t r;
336
337 if(idx != NULL) { *idx = -1; }
338 if((T == NULL) || (SA == NULL) || (Tsize < 0) || (SAsize < 0)) { return -1; }
339 if((Tsize == 0) || (SAsize == 0)) { return 0; }
340
341 for(i = j = k = 0, size = SAsize, half = size >> 1;
342 0 < size;
343 size = half, half >>= 1) {
344 p = SA[i + half];
345 r = (p < Tsize) ? T[p] - c : -1;
346 if(r < 0) {
347 i += half + 1;
348 half -= (size & 1) ^ 1;
349 } else if(r == 0) {
350 lsize = half, j = i, rsize = size - half - 1, k = i + half + 1;
351
352 /* left part */
353 for(half = lsize >> 1;
354 0 < lsize;
355 lsize = half, half >>= 1) {
356 p = SA[j + half];
357 r = (p < Tsize) ? T[p] - c : -1;
358 if(r < 0) {
359 j += half + 1;
360 half -= (lsize & 1) ^ 1;
361 }
362 }
363
364 /* right part */
365 for(half = rsize >> 1;
366 0 < rsize;
367 rsize = half, half >>= 1) {
368 p = SA[k + half];
369 r = (p < Tsize) ? T[p] - c : -1;
370 if(r <= 0) {
371 k += half + 1;
372 half -= (rsize & 1) ^ 1;
373 }
374 }
375
376 break;
377 }
378 }
379
380 if(idx != NULL) { *idx = (0 < (k - j)) ? j : i; }
381 return k - j;
382 }
383 #endif
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.