View Javadoc
1   /*
2    * Copyright 2014 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   https://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  package io.netty.handler.codec.compression;
17  
18  /**
19   * DivSufSort suffix array generator.<br>
20   *
21   * Based on <a href="https://code.google.com/p/libdivsufsort/">libdivsufsort</a> 1.2.3 patched to support Bzip2.<br>
22   * This is a simple conversion of the original C with two minor bugfixes applied (see "BUGFIX"
23   * comments within the class). Documentation within the class is largely absent.
24   */
25  final class Bzip2DivSufSort {
26  
27      private static final int STACK_SIZE = 64;
28      private static final int BUCKET_A_SIZE = 256;
29      private static final int BUCKET_B_SIZE = 65536;
30      private static final int SS_BLOCKSIZE = 1024;
31      private static final int INSERTIONSORT_THRESHOLD = 8;
32  
33      private static final int[] LOG_2_TABLE = {
34          -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,
35           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,
36           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,
37           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,
38           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,
39           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,
40           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,
41           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
42      };
43  
44      private final int[] SA;
45      private final byte[] T;
46      private final int n;
47  
48      /**
49       * @param block The input array
50       * @param bwtBlock The output array
51       * @param blockLength The length of the input data
52       */
53      Bzip2DivSufSort(final byte[] block, final int[] bwtBlock, final int blockLength) {
54          T = block;
55          SA = bwtBlock;
56          n = blockLength;
57      }
58  
59      private static void swapElements(final int[] array1, final int idx1, final int[] array2, final int idx2) {
60          final int temp = array1[idx1];
61          array1[idx1] = array2[idx2];
62          array2[idx2] = temp;
63      }
64  
65      private int ssCompare(final int p1, final int p2, final int depth) {
66          final int[] SA = this.SA;
67          final byte[] T = this.T;
68  
69          // pointers within T
70          final int U1n = SA[p1 + 1] + 2;
71          final int  U2n = SA[p2 + 1] + 2;
72  
73          int U1 = depth + SA[p1];
74          int U2 = depth + SA[p2];
75  
76          while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
77              ++U1;
78              ++U2;
79          }
80  
81          return U1 < U1n ?
82                     U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1
83                   : U2 < U2n ? -1 : 0;
84      }
85  
86      private int ssCompareLast(int pa, int p1, int p2, int depth, int size) {
87          final int[] SA = this.SA;
88          final byte[] T = this.T;
89  
90          int U1 = depth + SA[p1];
91          int U2 = depth + SA[p2];
92          int U1n = size;
93          int U2n = SA[p2 + 1] + 2;
94  
95          while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
96              ++U1;
97              ++U2;
98          }
99  
100         if (U1 < U1n) {
101             return U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1;
102         }
103         if (U2 == U2n) {
104             return 1;
105         }
106 
107         U1 %= size;
108         U1n = SA[pa] + 2;
109         while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
110             ++U1;
111             ++U2;
112         }
113 
114         return U1 < U1n ?
115                    U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1
116                  : U2 < U2n ? -1 : 0;
117     }
118 
119     private void ssInsertionSort(int pa, int first, int last, int depth) {
120         final int[] SA = this.SA;
121 
122         int i, j; // pointer within SA
123         int t;
124         int r;
125 
126         for (i = last - 2; first <= i; --i) {
127             for (t = SA[i], j = i + 1; 0 < (r = ssCompare(pa + t, pa + SA[j], depth));) {
128                 do {
129                     SA[j - 1] = SA[j];
130                 } while (++j < last && SA[j] < 0);
131                 if (last <= j) {
132                     break;
133                 }
134             }
135             if (r == 0) {
136                 SA[j] = ~SA[j];
137             }
138             SA[j - 1] = t;
139         }
140     }
141 
142     private void ssFixdown(int td, int pa, int sa, int i, int size) {
143         final int[] SA = this.SA;
144         final byte[] T = this.T;
145 
146         int j, k;
147         int v;
148         int c, d, e;
149 
150         for (v = SA[sa + i], c = T[td + SA[pa + v]] & 0xff; (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
151             d = T[td + SA[pa + SA[sa + (k = j++)]]] & 0xff;
152             if (d < (e = T[td + SA[pa + SA[sa + j]]] & 0xff)) {
153                 k = j;
154                 d = e;
155             }
156             if (d <= c) {
157                 break;
158             }
159         }
160         SA[sa + i] = v;
161     }
162 
163     private void ssHeapSort(int td, int pa, int sa, int size) {
164         final int[] SA = this.SA;
165         final byte[] T = this.T;
166 
167         int i, m;
168         int t;
169 
170         m = size;
171         if (size % 2 == 0) {
172             m--;
173             if ((T[td + SA[pa + SA[sa + m / 2]]] & 0xff) < (T[td + SA[pa + SA[sa + m]]] & 0xff)) {
174                 swapElements(SA, sa + m, SA, sa + m / 2);
175             }
176         }
177 
178         for (i = m / 2 - 1; 0 <= i; --i) {
179             ssFixdown(td, pa, sa, i, m);
180         }
181 
182         if (size % 2 == 0) {
183             swapElements(SA, sa, SA, sa + m);
184             ssFixdown(td, pa, sa, 0, m);
185         }
186 
187         for (i = m - 1; 0 < i; --i) {
188             t = SA[sa];
189             SA[sa] = SA[sa + i];
190             ssFixdown(td, pa, sa, 0, i);
191             SA[sa + i] = t;
192         }
193     }
194 
195     private int ssMedian3(final int td, final int pa, int v1, int v2, int v3) {
196         final int[] SA = this.SA;
197         final byte[] T = this.T;
198 
199         int T_v1 = T[td + SA[pa + SA[v1]]] & 0xff;
200         int T_v2 = T[td + SA[pa + SA[v2]]] & 0xff;
201         int T_v3 = T[td + SA[pa + SA[v3]]] & 0xff;
202 
203         if (T_v1 > T_v2) {
204             final int temp = v1;
205             v1 = v2;
206             v2 = temp;
207             final int T_vtemp = T_v1;
208             T_v1 = T_v2;
209             T_v2 = T_vtemp;
210         }
211         if (T_v2 > T_v3) {
212             if (T_v1 > T_v3) {
213                 return v1;
214             }
215             return v3;
216         }
217         return v2;
218     }
219 
220     private int ssMedian5(final int td, final int pa, int v1, int v2, int v3, int v4, int v5) {
221         final int[] SA = this.SA;
222         final byte[] T = this.T;
223 
224         int T_v1 = T[td + SA[pa + SA[v1]]] & 0xff;
225         int T_v2 = T[td + SA[pa + SA[v2]]] & 0xff;
226         int T_v3 = T[td + SA[pa + SA[v3]]] & 0xff;
227         int T_v4 = T[td + SA[pa + SA[v4]]] & 0xff;
228         int T_v5 = T[td + SA[pa + SA[v5]]] & 0xff;
229         int temp;
230         int T_vtemp;
231 
232         if (T_v2 > T_v3) {
233             temp = v2;
234             v2 = v3;
235             v3 = temp;
236             T_vtemp = T_v2;
237             T_v2 = T_v3;
238             T_v3 = T_vtemp;
239         }
240         if (T_v4 > T_v5) {
241             temp = v4;
242             v4 = v5;
243             v5 = temp;
244             T_vtemp = T_v4;
245             T_v4 = T_v5;
246             T_v5 = T_vtemp;
247         }
248         if (T_v2 > T_v4) {
249             temp = v2;
250             v4 = temp;
251             T_vtemp = T_v2;
252             T_v4 = T_vtemp;
253             temp = v3;
254             v3 = v5;
255             v5 = temp;
256             T_vtemp = T_v3;
257             T_v3 = T_v5;
258             T_v5 = T_vtemp;
259         }
260         if (T_v1 > T_v3) {
261             temp = v1;
262             v1 = v3;
263             v3 = temp;
264             T_vtemp = T_v1;
265             T_v1 = T_v3;
266             T_v3 = T_vtemp;
267         }
268         if (T_v1 > T_v4) {
269             temp = v1;
270             v4 = temp;
271             T_vtemp = T_v1;
272             T_v4 = T_vtemp;
273             v3 = v5;
274             T_v3 = T_v5;
275         }
276         if (T_v3 > T_v4) {
277             return v4;
278         }
279         return v3;
280     }
281 
282     private int ssPivot(final int td, final int pa, final int first, final int last) {
283         int middle;
284         int t;
285 
286         t = last - first;
287         middle = first + t / 2;
288 
289         if (t <= 512) {
290             if (t <= 32) {
291                 return ssMedian3(td, pa, first, middle, last - 1);
292             }
293             t >>= 2;
294             return ssMedian5(td, pa, first, first + t, middle, last - 1 - t, last - 1);
295         }
296         t >>= 3;
297         return ssMedian3(
298                 td, pa,
299                 ssMedian3(td, pa, first, first + t, first + (t << 1)),
300                 ssMedian3(td, pa, middle - t, middle, middle + t),
301                 ssMedian3(td, pa, last - 1 - (t << 1), last - 1 - t, last - 1)
302         );
303     }
304 
305     private static int ssLog(final int n) {
306         return (n & 0xff00) != 0 ?
307                   8 + LOG_2_TABLE[n >> 8 & 0xff]
308                 : LOG_2_TABLE[n & 0xff];
309     }
310 
311     private int ssSubstringPartition(final int pa, final int first, final int last, final int depth) {
312         final int[] SA = this.SA;
313 
314         int a, b;
315         int t;
316 
317         for (a = first - 1, b = last;;) {
318             while (++a < b && (SA[pa + SA[a]] + depth >= SA[pa + SA[a] + 1] + 1)) {
319                 SA[a] = ~SA[a];
320             }
321             --b;
322             while (a < b && (SA[pa + SA[b]] + depth < SA[pa + SA[b] + 1] + 1)) {
323                 --b;
324             }
325 
326             if (b <= a) {
327                 break;
328             }
329             t = ~SA[b];
330             SA[b] = SA[a];
331             SA[a] = t;
332         }
333         if (first < a) {
334             SA[first] = ~SA[first];
335         }
336         return a;
337     }
338 
339     private static class StackEntry {
340         final int a;
341         final int b;
342         final int c;
343         final int d;
344 
345         StackEntry(final int a, final int b, final int c, final int d) {
346             this.a = a;
347             this.b = b;
348             this.c = c;
349             this.d = d;
350         }
351     }
352 
353     private void ssMultiKeyIntroSort(final int pa, int first, int last, int depth) {
354         final int[] SA = this.SA;
355         final byte[] T = this.T;
356 
357         final StackEntry[] stack = new StackEntry[STACK_SIZE];
358 
359         int Td;
360         int a, b, c, d, e, f;
361         int s, t;
362         int ssize;
363         int limit;
364         int v, x = 0;
365 
366         for (ssize = 0, limit = ssLog(last - first);;) {
367             if (last - first <= INSERTIONSORT_THRESHOLD) {
368                 if (1 < last - first) {
369                     ssInsertionSort(pa, first, last, depth);
370                 }
371                 if (ssize == 0) {
372                     return;
373                 }
374                 StackEntry entry = stack[--ssize];
375                 first = entry.a;
376                 last = entry.b;
377                 depth = entry.c;
378                 limit = entry.d;
379                 continue;
380             }
381 
382             Td = depth;
383             if (limit-- == 0) {
384                 ssHeapSort(Td, pa, first, last - first);
385             }
386             if (limit < 0) {
387                 for (a = first + 1, v = T[Td + SA[pa + SA[first]]] & 0xff; a < last; ++a) {
388                     if ((x = T[Td + SA[pa + SA[a]]] & 0xff) != v) {
389                         if (1 < a - first) {
390                             break;
391                         }
392                         v = x;
393                         first = a;
394                     }
395                 }
396                 if ((T[Td + SA[pa + SA[first]] - 1] & 0xff) < v) {
397                     first = ssSubstringPartition(pa, first, a, depth);
398                 }
399                 if (a - first <= last - a) {
400                     if (1 < a - first) {
401                         stack[ssize++] = new StackEntry(a, last, depth, -1);
402                         last = a;
403                         depth += 1;
404                         limit = ssLog(a - first);
405                     } else {
406                         first = a;
407                         limit = -1;
408                     }
409                 } else {
410                     if (1 < last - a) {
411                         stack[ssize++] = new StackEntry(first, a, depth + 1, ssLog(a - first));
412                         first = a;
413                         limit = -1;
414                     } else {
415                         last = a;
416                         depth += 1;
417                         limit = ssLog(a - first);
418                     }
419                 }
420                 continue;
421             }
422 
423             a = ssPivot(Td, pa, first, last);
424             v = T[Td + SA[pa + SA[a]]] & 0xff;
425             swapElements(SA, first, SA, a);
426 
427             b = first + 1;
428             while (b < last && (x = T[Td + SA[pa + SA[b]]] & 0xff) == v) {
429                 ++b;
430             }
431             if ((a = b) < last && x < v) {
432                 while (++b < last && (x = T[Td + SA[pa + SA[b]]] & 0xff) <= v) {
433                     if (x == v) {
434                         swapElements(SA, b, SA, a);
435                         ++a;
436                     }
437                 }
438             }
439 
440             c = last - 1;
441             while (b < c && (x = T[Td + SA[pa + SA[c]]] & 0xff) == v) {
442                 --c;
443             }
444             if (b < (d = c) && x > v) {
445                 while (b < --c && (x = T[Td + SA[pa + SA[c]]] & 0xff) >= v) {
446                     if (x == v) {
447                         swapElements(SA, c, SA, d);
448                         --d;
449                     }
450                 }
451             }
452             while (b < c) {
453                 swapElements(SA, b, SA, c);
454                 while (++b < c && (x = T[Td + SA[pa + SA[b]]] & 0xff) <= v) {
455                     if (x == v) {
456                         swapElements(SA, b, SA, a);
457                         ++a;
458                     }
459                 }
460                 while (b < --c && (x = T[Td + SA[pa + SA[c]]] & 0xff) >= v) {
461                     if (x == v) {
462                         swapElements(SA, c, SA, d);
463                         --d;
464                     }
465                 }
466             }
467 
468             if (a <= d) {
469                 c = b - 1;
470 
471                 if ((s = a - first) > (t = b - a)) {
472                     s = t;
473                 }
474                 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
475                     swapElements(SA, e, SA, f);
476                 }
477                 if ((s = d - c) > (t = last - d - 1)) {
478                     s = t;
479                 }
480                 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
481                     swapElements(SA, e, SA, f);
482                 }
483 
484                 a = first + (b - a);
485                 c = last - (d - c);
486                 b = v <= (T[Td + SA[pa + SA[a]] - 1] & 0xff) ? a : ssSubstringPartition(pa, a, c, depth);
487 
488                 if (a - first <= last - c) {
489                     if (last - c <= c - b) {
490                         stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
491                         stack[ssize++] = new StackEntry(c, last, depth, limit);
492                         last = a;
493                     } else if (a - first <= c - b) {
494                         stack[ssize++] = new StackEntry(c, last, depth, limit);
495                         stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
496                         last = a;
497                     } else {
498                         stack[ssize++] = new StackEntry(c, last, depth, limit);
499                         stack[ssize++] = new StackEntry(first, a, depth, limit);
500                         first = b;
501                         last = c;
502                         depth += 1;
503                         limit = ssLog(c - b);
504                     }
505                 } else {
506                     if (a - first <= c - b) {
507                         stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
508                         stack[ssize++] = new StackEntry(first, a, depth, limit);
509                         first = c;
510                     } else if (last - c <= c - b) {
511                         stack[ssize++] = new StackEntry(first, a, depth, limit);
512                         stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
513                         first = c;
514                     } else {
515                         stack[ssize++] = new StackEntry(first, a, depth, limit);
516                         stack[ssize++] = new StackEntry(c, last, depth, limit);
517                         first = b;
518                         last = c;
519                         depth += 1;
520                         limit = ssLog(c - b);
521                     }
522                 }
523             } else {
524                 limit += 1;
525                 if ((T[Td + SA[pa + SA[first]] - 1] & 0xff) < v) {
526                     first = ssSubstringPartition(pa, first, last, depth);
527                     limit = ssLog(last - first);
528                 }
529                 depth += 1;
530             }
531         }
532     }
533 
534     private static void ssBlockSwap(final int[] array1, final int first1,
535                                     final int[] array2, final int first2, final int size) {
536         int a, b;
537         int i;
538         for (i = size, a = first1, b = first2; 0 < i; --i, ++a, ++b) {
539             swapElements(array1, a, array2, b);
540         }
541     }
542 
543     private void ssMergeForward(final int pa, int[] buf, final int bufoffset,
544                                 final int first, final int middle, final int last, final int depth) {
545         final int[] SA = this.SA;
546 
547         int bufend;
548         int i, j, k;
549         int t;
550         int r;
551 
552         bufend = bufoffset + (middle - first) - 1;
553         ssBlockSwap(buf, bufoffset, SA, first, middle - first);
554 
555         for (t = SA[first], i = first, j = bufoffset, k = middle;;) {
556             r = ssCompare(pa + buf[j], pa + SA[k], depth);
557             if (r < 0) {
558                 do {
559                     SA[i++] = buf[j];
560                     if (bufend <= j) {
561                         buf[j] = t;
562                         return;
563                     }
564                     buf[j++] = SA[i];
565                 } while (buf[j] < 0);
566             } else if (r > 0) {
567                 do {
568                     SA[i++] = SA[k];
569                     SA[k++] = SA[i];
570                     if (last <= k) {
571                         while (j < bufend) {
572                             SA[i++] = buf[j]; buf[j++] = SA[i];
573                         }
574                         SA[i] = buf[j]; buf[j] = t;
575                         return;
576                     }
577                 } while (SA[k] < 0);
578             } else {
579                 SA[k] = ~SA[k];
580                 do {
581                     SA[i++] = buf[j];
582                     if (bufend <= j) {
583                         buf[j] = t;
584                         return;
585                     }
586                     buf[j++] = SA[i];
587                 } while (buf[j] < 0);
588 
589                 do {
590                     SA[i++] = SA[k];
591                     SA[k++] = SA[i];
592                     if (last <= k) {
593                         while (j < bufend) {
594                             SA[i++] = buf[j];
595                             buf[j++] = SA[i];
596                         }
597                         SA[i] = buf[j]; buf[j] = t;
598                         return;
599                     }
600                 } while (SA[k] < 0);
601             }
602         }
603     }
604 
605     private void ssMergeBackward(final int pa, int[] buf, final int bufoffset,
606                                  final int first, final int middle, final int last, final int depth) {
607         final int[] SA = this.SA;
608 
609         int p1, p2;
610         int bufend;
611         int i, j, k;
612         int t;
613         int r;
614         int x;
615 
616         bufend = bufoffset + (last - middle);
617         ssBlockSwap(buf, bufoffset, SA, middle, last - middle);
618 
619         x = 0;
620         if (buf[bufend - 1] < 0) {
621             x |=  1;
622             p1 = pa + ~buf[bufend - 1];
623         } else {
624             p1 = pa +  buf[bufend - 1];
625         }
626         if (SA[middle - 1] < 0) {
627             x |=  2;
628             p2 = pa + ~SA[middle - 1];
629         } else {
630             p2 = pa +  SA[middle - 1];
631         }
632         for (t = SA[last - 1], i = last - 1, j = bufend - 1, k = middle - 1;;) {
633 
634             r = ssCompare(p1, p2, depth);
635             if (r > 0) {
636                 if ((x & 1) != 0) {
637                     do {
638                         SA[i--] = buf[j];
639                         buf[j--] = SA[i];
640                     } while (buf[j] < 0);
641                     x ^= 1;
642                 }
643                 SA[i--] = buf[j];
644                 if (j <= bufoffset) {
645                     buf[j] = t;
646                     return;
647                 }
648                 buf[j--] = SA[i];
649 
650                 if (buf[j] < 0) {
651                     x |=  1;
652                     p1 = pa + ~buf[j];
653                 } else {
654                     p1 = pa +  buf[j];
655                 }
656             } else if (r < 0) {
657                 if ((x & 2) != 0) {
658                     do {
659                         SA[i--] = SA[k];
660                         SA[k--] = SA[i];
661                     } while (SA[k] < 0);
662                     x ^= 2;
663                 }
664                 SA[i--] = SA[k];
665                 SA[k--] = SA[i];
666                 if (k < first) {
667                     while (bufoffset < j) {
668                         SA[i--] = buf[j];
669                         buf[j--] = SA[i];
670                     }
671                     SA[i] = buf[j];
672                     buf[j] = t;
673                     return;
674                 }
675 
676                 if (SA[k] < 0) {
677                     x |=  2;
678                     p2 = pa + ~SA[k];
679                 } else {
680                     p2 = pa +  SA[k];
681                 }
682             } else {
683                 if ((x & 1) != 0) {
684                     do {
685                         SA[i--] = buf[j];
686                         buf[j--] = SA[i];
687                     } while (buf[j] < 0);
688                     x ^= 1;
689                 }
690                 SA[i--] = ~buf[j];
691                 if (j <= bufoffset) {
692                     buf[j] = t;
693                     return;
694                 }
695                 buf[j--] = SA[i];
696 
697                 if ((x & 2) != 0) {
698                     do {
699                         SA[i--] = SA[k];
700                         SA[k--] = SA[i];
701                     } while (SA[k] < 0);
702                     x ^= 2;
703                 }
704                 SA[i--] = SA[k];
705                 SA[k--] = SA[i];
706                 if (k < first) {
707                     while (bufoffset < j) {
708                         SA[i--] = buf[j];
709                         buf[j--] = SA[i];
710                     }
711                     SA[i] = buf[j];
712                     buf[j] = t;
713                     return;
714                 }
715 
716                 if (buf[j] < 0) {
717                     x |=  1;
718                     p1 = pa + ~buf[j];
719                 } else {
720                     p1 = pa +  buf[j];
721                 }
722                 if (SA[k] < 0) {
723                     x |=  2;
724                     p2 = pa + ~SA[k];
725                 } else {
726                     p2 = pa +  SA[k];
727                 }
728             }
729         }
730     }
731 
732     private static int getIDX(final int a) {
733         return 0 <= a ? a : ~a;
734     }
735 
736     private void ssMergeCheckEqual(final int pa, final int depth, final int a) {
737         final int[] SA = this.SA;
738 
739         if (0 <= SA[a] && ssCompare(pa + getIDX(SA[a - 1]), pa + SA[a], depth) == 0) {
740             SA[a] = ~SA[a];
741         }
742     }
743 
744     private void ssMerge(final int pa, int first, int middle, int last, int[] buf,
745                          final int bufoffset, final int bufsize, final int depth) {
746         final int[] SA = this.SA;
747 
748         final StackEntry[] stack = new StackEntry[STACK_SIZE];
749 
750         int i, j;
751         int m, len, half;
752         int ssize;
753         int check, next;
754 
755         for (check = 0, ssize = 0;;) {
756 
757             if (last - middle <= bufsize) {
758                 if (first < middle && middle < last) {
759                     ssMergeBackward(pa, buf, bufoffset, first, middle, last, depth);
760                 }
761 
762                 if ((check & 1) != 0) {
763                     ssMergeCheckEqual(pa, depth, first);
764                 }
765                 if ((check & 2) != 0) {
766                     ssMergeCheckEqual(pa, depth, last);
767                 }
768                 if (ssize == 0) {
769                     return;
770                 }
771                 StackEntry entry = stack[--ssize];
772                 first = entry.a;
773                 middle = entry.b;
774                 last = entry.c;
775                 check = entry.d;
776                 continue;
777             }
778 
779             if (middle - first <= bufsize) {
780                 if (first < middle) {
781                     ssMergeForward(pa, buf, bufoffset, first, middle, last, depth);
782                 }
783                 if ((check & 1) != 0) {
784                     ssMergeCheckEqual(pa, depth, first);
785                 }
786                 if ((check & 2) != 0) {
787                     ssMergeCheckEqual(pa, depth, last);
788                 }
789                 if (ssize == 0) {
790                     return;
791                 }
792                 StackEntry entry = stack[--ssize];
793                 first = entry.a;
794                 middle = entry.b;
795                 last = entry.c;
796                 check = entry.d;
797                 continue;
798             }
799 
800             for (m = 0, len = Math.min(middle - first, last - middle), half = len >> 1;
801                     0 < len;
802                     len = half, half >>= 1) {
803 
804                 if (ssCompare(pa + getIDX(SA[middle + m + half]),
805                         pa + getIDX(SA[middle - m - half - 1]), depth) < 0) {
806                     m += half + 1;
807                     half -= (len & 1) ^ 1;
808                 }
809             }
810 
811             if (0 < m) {
812                 ssBlockSwap(SA, middle - m, SA, middle, m);
813                 i = j = middle;
814                 next = 0;
815                 if (middle + m < last) {
816                     if (SA[middle + m] < 0) {
817                         while (SA[i - 1] < 0) {
818                             --i;
819                         }
820                         SA[middle + m] = ~SA[middle + m];
821                     }
822                     for (j = middle; SA[j] < 0;) {
823                         ++j;
824                     }
825                     next = 1;
826                 }
827                 if (i - first <= last - j) {
828                     stack[ssize++] = new StackEntry(j, middle + m, last, (check &  2) | (next & 1));
829                     middle -= m;
830                     last = i;
831                     check &= 1;
832                 } else {
833                     if (i == middle && middle == j) {
834                         next <<= 1;
835                     }
836                     stack[ssize++] = new StackEntry(first, middle - m, i, (check & 1) | (next & 2));
837                     first = j;
838                     middle += m;
839                     check = (check & 2) | (next & 1);
840                 }
841             } else {
842                 if ((check & 1) != 0) {
843                     ssMergeCheckEqual(pa, depth, first);
844                 }
845                 ssMergeCheckEqual(pa, depth, middle);
846                 if ((check & 2) != 0) {
847                     ssMergeCheckEqual(pa, depth, last);
848                 }
849                 if (ssize == 0) {
850                     return;
851                 }
852                 StackEntry entry = stack[--ssize];
853                 first = entry.a;
854                 middle = entry.b;
855                 last = entry.c;
856                 check = entry.d;
857             }
858         }
859     }
860 
861     private void subStringSort(final int pa, int first, final int last,
862                                final int[] buf, final int bufoffset, final int bufsize,
863                                final int depth, final boolean lastsuffix, final int size) {
864         final int[] SA = this.SA;
865 
866         int a, b;
867         int[] curbuf;
868         int curbufoffset;
869         int i, j, k;
870         int curbufsize;
871 
872         if (lastsuffix) {
873             ++first;
874         }
875         for (a = first, i = 0; a + SS_BLOCKSIZE < last; a += SS_BLOCKSIZE, ++i) {
876             ssMultiKeyIntroSort(pa, a, a + SS_BLOCKSIZE, depth);
877             curbuf = SA;
878             curbufoffset = a + SS_BLOCKSIZE;
879             curbufsize = last - (a + SS_BLOCKSIZE);
880             if (curbufsize <= bufsize) {
881                 curbufsize = bufsize;
882                 curbuf = buf;
883                 curbufoffset = bufoffset;
884             }
885             for (b = a, k = SS_BLOCKSIZE, j = i; (j & 1) != 0; b -= k, k <<= 1, j >>>= 1) {
886                 ssMerge(pa, b - k, b, b + k, curbuf, curbufoffset, curbufsize, depth);
887             }
888         }
889 
890         ssMultiKeyIntroSort(pa, a, last, depth);
891 
892         for (k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
893             if ((i & 1) != 0) {
894                 ssMerge(pa, a - k, a, last, buf, bufoffset, bufsize, depth);
895                 a -= k;
896             }
897         }
898 
899         if (lastsuffix) {
900             int r;
901             for (a = first, i = SA[first - 1], r = 1;
902                     a < last && (SA[a] < 0 || 0 < (r = ssCompareLast(pa, pa + i, pa + SA[a], depth, size)));
903                     ++a) {
904                 SA[a - 1] = SA[a];
905             }
906             if (r == 0) {
907                 SA[a] = ~SA[a];
908             }
909             SA[a - 1] = i;
910         }
911     }
912 
913     /*----------------------------------------------------------------------------*/
914 
915     private int trGetC(final int isa, final int isaD, final int isaN, final int p) {
916         return isaD + p < isaN ?
917                 SA[isaD + p]
918               : SA[isa + ((isaD - isa + p) % (isaN - isa))];
919     }
920 
921     private void trFixdown(final int isa, final int isaD, final int isaN, final int sa, int i, final int size) {
922         final int[] SA = this.SA;
923 
924         int j, k;
925         int v;
926         int c, d, e;
927 
928         for (v = SA[sa + i], c = trGetC(isa, isaD, isaN, v); (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
929             k = j++;
930             d = trGetC(isa, isaD, isaN, SA[sa + k]);
931             if (d < (e = trGetC(isa, isaD, isaN, SA[sa + j]))) {
932                 k = j;
933                 d = e;
934             }
935             if (d <= c) {
936                 break;
937             }
938         }
939         SA[sa + i] = v;
940     }
941 
942     private void trHeapSort(final int isa, final int isaD, final int isaN, final int sa, final int size) {
943         final int[] SA = this.SA;
944 
945         int i, m;
946         int t;
947 
948         m = size;
949         if (size % 2 == 0) {
950             m--;
951             if (trGetC(isa, isaD, isaN, SA[sa + m / 2]) < trGetC(isa, isaD, isaN, SA[sa + m])) {
952                 swapElements(SA, sa + m, SA, sa + m / 2);
953             }
954         }
955 
956         for (i = m / 2 - 1; 0 <= i; --i) {
957             trFixdown(isa, isaD, isaN, sa, i, m);
958         }
959 
960         if (size % 2 == 0) {
961             swapElements(SA, sa, SA, sa + m);
962             trFixdown(isa, isaD, isaN, sa, 0, m);
963         }
964 
965         for (i = m - 1; 0 < i; --i) {
966             t = SA[sa];
967             SA[sa] = SA[sa + i];
968             trFixdown(isa, isaD, isaN, sa, 0, i);
969             SA[sa + i] = t;
970         }
971     }
972 
973     private void trInsertionSort(final int isa, final int isaD, final int isaN, int first, int last) {
974         final int[] SA = this.SA;
975 
976         int a, b;
977         int t, r;
978 
979         for (a = first + 1; a < last; ++a) {
980             for (t = SA[a], b = a - 1; 0 > (r = trGetC(isa, isaD, isaN, t) - trGetC(isa, isaD, isaN, SA[b]));) {
981                 do {
982                     SA[b + 1] = SA[b];
983                 } while (first <= --b && SA[b] < 0);
984                 if (b < first) {
985                     break;
986                 }
987             }
988             if (r == 0) {
989                 SA[b] = ~SA[b];
990             }
991             SA[b + 1] = t;
992         }
993     }
994 
995     private static int trLog(int n) {
996         return (n & 0xffff0000) != 0 ?
997                   (n & 0xff000000) != 0 ? 24 + LOG_2_TABLE[n >> 24 & 0xff] : LOG_2_TABLE[n >> 16 & 0xff + 16]
998                 : (n & 0x0000ff00) != 0 ?  8 + LOG_2_TABLE[n >>  8 & 0xff] : LOG_2_TABLE[n & 0xff];
999     }
1000 
1001     private int trMedian3(final int isa, final int isaD, final int isaN, int v1, int v2, int v3) {
1002         final int[] SA = this.SA;
1003 
1004         int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
1005         int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
1006         int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
1007 
1008         if (SA_v1 > SA_v2) {
1009             final int temp = v1;
1010             v1 = v2;
1011             v2 = temp;
1012             final int SA_vtemp = SA_v1;
1013             SA_v1 = SA_v2;
1014             SA_v2 = SA_vtemp;
1015         }
1016         if (SA_v2 > SA_v3) {
1017             if (SA_v1 > SA_v3) {
1018                 return v1;
1019             }
1020             return v3;
1021         }
1022 
1023         return v2;
1024     }
1025 
1026     private int trMedian5(final int isa, final int isaD, final int isaN, int v1, int v2, int v3, int v4, int v5) {
1027         final int[] SA = this.SA;
1028 
1029         int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
1030         int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
1031         int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
1032         int SA_v4 = trGetC(isa, isaD, isaN, SA[v4]);
1033         int SA_v5 = trGetC(isa, isaD, isaN, SA[v5]);
1034         int temp;
1035         int SA_vtemp;
1036 
1037         if (SA_v2 > SA_v3) {
1038             temp = v2;
1039             v2 = v3;
1040             v3 = temp;
1041             SA_vtemp = SA_v2;
1042             SA_v2 = SA_v3;
1043             SA_v3 = SA_vtemp;
1044         }
1045         if (SA_v4 > SA_v5) {
1046             temp = v4;
1047             v4 = v5;
1048             v5 = temp;
1049             SA_vtemp = SA_v4;
1050             SA_v4 = SA_v5;
1051             SA_v5 = SA_vtemp;
1052         }
1053         if (SA_v2 > SA_v4) {
1054             temp = v2;
1055             v4 = temp;
1056             SA_vtemp = SA_v2;
1057             SA_v4 = SA_vtemp;
1058             temp = v3;
1059             v3 = v5;
1060             v5 = temp;
1061             SA_vtemp = SA_v3;
1062             SA_v3 = SA_v5;
1063             SA_v5 = SA_vtemp;
1064         }
1065         if (SA_v1 > SA_v3) {
1066             temp = v1;
1067             v1 = v3;
1068             v3 = temp;
1069             SA_vtemp = SA_v1;
1070             SA_v1 = SA_v3;
1071             SA_v3 = SA_vtemp;
1072         }
1073         if (SA_v1 > SA_v4) {
1074             temp = v1;
1075             v4 = temp;
1076             SA_vtemp = SA_v1;
1077             SA_v4 = SA_vtemp;
1078             v3 = v5;
1079             SA_v3 = SA_v5;
1080         }
1081         if (SA_v3 > SA_v4) {
1082             return v4;
1083         }
1084         return v3;
1085     }
1086 
1087     private int trPivot(final int isa, final int isaD, final int isaN, final int first, final int last) {
1088         final int middle;
1089         int t;
1090 
1091         t = last - first;
1092         middle = first + t / 2;
1093 
1094         if (t <= 512) {
1095             if (t <= 32) {
1096                 return trMedian3(isa, isaD, isaN, first, middle, last - 1);
1097             }
1098             t >>= 2;
1099             return trMedian5(
1100                     isa, isaD, isaN,
1101                     first, first + t,
1102                     middle,
1103                     last - 1 - t, last - 1
1104             );
1105         }
1106         t >>= 3;
1107         return trMedian3(
1108                 isa, isaD, isaN,
1109                 trMedian3(isa, isaD, isaN, first, first + t, first + (t << 1)),
1110                 trMedian3(isa, isaD, isaN, middle - t, middle, middle + t),
1111                 trMedian3(isa, isaD, isaN, last - 1 - (t << 1), last - 1 - t, last - 1)
1112         );
1113     }
1114 
1115     /*---------------------------------------------------------------------------*/
1116 
1117     private void lsUpdateGroup(final int isa, final int first, final int last) {
1118         final int[] SA = this.SA;
1119 
1120         int a, b;
1121         int t;
1122 
1123         for (a = first; a < last; ++a) {
1124             if (0 <= SA[a]) {
1125                 b = a;
1126                 do {
1127                     SA[isa + SA[a]] = a;
1128                 } while (++a < last && 0 <= SA[a]);
1129                 SA[b] = b - a;
1130                 if (last <= a) {
1131                     break;
1132                 }
1133             }
1134             b = a;
1135             do {
1136                 SA[a] = ~SA[a];
1137             } while (SA[++a] < 0);
1138             t = a;
1139             do {
1140                 SA[isa + SA[b]] = t;
1141             } while (++b <= a);
1142         }
1143     }
1144 
1145     private void lsIntroSort(final int isa, final int isaD, final int isaN, int first, int last) {
1146         final int[] SA = this.SA;
1147 
1148         final StackEntry[] stack = new StackEntry[STACK_SIZE];
1149 
1150         int a, b, c, d, e, f;
1151         int s, t;
1152         int limit;
1153         int v, x = 0;
1154         int ssize;
1155 
1156         for (ssize = 0, limit = trLog(last - first);;) {
1157             if (last - first <= INSERTIONSORT_THRESHOLD) {
1158                 if (1 < last - first) {
1159                     trInsertionSort(isa, isaD, isaN, first, last);
1160                     lsUpdateGroup(isa, first, last);
1161                 } else if (last - first == 1) {
1162                     SA[first] = -1;
1163                 }
1164                 if (ssize == 0) {
1165                     return;
1166                 }
1167                 StackEntry entry = stack[--ssize];
1168                 first = entry.a;
1169                 last = entry.b;
1170                 limit = entry.c;
1171                 continue;
1172             }
1173 
1174             if (limit-- == 0) {
1175                 trHeapSort(isa, isaD, isaN, first, last - first);
1176                 for (a = last - 1; first < a; a = b) {
1177                     for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
1178                             first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
1179                             --b) {
1180                         SA[b] = ~SA[b];
1181                     }
1182                 }
1183                 lsUpdateGroup(isa, first, last);
1184                 if (ssize == 0) {
1185                     return;
1186                 }
1187                 StackEntry entry = stack[--ssize];
1188                 first = entry.a;
1189                 last = entry.b;
1190                 limit = entry.c;
1191                 continue;
1192             }
1193 
1194             a = trPivot(isa, isaD, isaN, first, last);
1195             swapElements(SA, first, SA, a);
1196             v = trGetC(isa, isaD, isaN, SA[first]);
1197 
1198             b = first + 1;
1199             while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1200                 ++b;
1201             }
1202             if ((a = b) < last && x < v) {
1203                 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1204                     if (x == v) {
1205                         swapElements(SA, b, SA, a);
1206                         ++a;
1207                     }
1208                 }
1209             }
1210 
1211             c = last - 1;
1212             while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1213                 --c;
1214             }
1215             if (b < (d = c) && x > v) {
1216                 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1217                     if (x == v) {
1218                         swapElements(SA, c, SA, d);
1219                         --d;
1220                     }
1221                 }
1222             }
1223             while (b < c) {
1224                 swapElements(SA, b, SA, c);
1225                 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1226                     if (x == v) {
1227                         swapElements(SA, b, SA, a);
1228                         ++a;
1229                     }
1230                 }
1231                 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1232                     if (x == v) {
1233                         swapElements(SA, c, SA, d);
1234                         --d;
1235                     }
1236                 }
1237             }
1238 
1239             if (a <= d) {
1240                 c = b - 1;
1241 
1242                 if ((s = a - first) > (t = b - a)) {
1243                     s = t;
1244                 }
1245                 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1246                     swapElements(SA, e, SA, f);
1247                 }
1248                 if ((s = d - c) > (t = last - d - 1)) {
1249                     s = t;
1250                 }
1251                 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1252                     swapElements(SA, e, SA, f);
1253                 }
1254 
1255                 a = first + (b - a);
1256                 b = last - (d - c);
1257 
1258                 for (c = first, v = a - 1; c < a; ++c) {
1259                     SA[isa + SA[c]] = v;
1260                 }
1261                 if (b < last) {
1262                     for (c = a, v = b - 1; c < b; ++c) {
1263                         SA[isa + SA[c]] = v;
1264                     }
1265                 }
1266                 if ((b - a) == 1) {
1267                     SA[a] = - 1;
1268                 }
1269 
1270                 if (a - first <= last - b) {
1271                     if (first < a) {
1272                         stack[ssize++] = new StackEntry(b, last, limit, 0);
1273                         last = a;
1274                     } else {
1275                         first = b;
1276                     }
1277                 } else {
1278                     if (b < last) {
1279                         stack[ssize++] = new StackEntry(first, a, limit, 0);
1280                         first = b;
1281                     } else {
1282                         last = a;
1283                     }
1284                 }
1285             } else {
1286                 if (ssize == 0) {
1287                     return;
1288                 }
1289                 StackEntry entry = stack[--ssize];
1290                 first = entry.a;
1291                 last = entry.b;
1292                 limit = entry.c;
1293             }
1294         }
1295     }
1296 
1297     private void lsSort(final int isa, final int n, final int depth) {
1298         final int[] SA = this.SA;
1299 
1300         int isaD;
1301         int first, last, i;
1302         int t, skip;
1303 
1304         for (isaD = isa + depth; -n < SA[0]; isaD += isaD - isa) {
1305             first = 0;
1306             skip = 0;
1307             do {
1308                 if ((t = SA[first]) < 0) {
1309                     first -= t;
1310                     skip += t;
1311                 } else {
1312                     if (skip != 0) {
1313                         SA[first + skip] = skip;
1314                         skip = 0;
1315                     }
1316                     last = SA[isa + t] + 1;
1317                     lsIntroSort(isa, isaD, isa + n, first, last);
1318                     first = last;
1319                 }
1320             } while (first < n);
1321             if (skip != 0) {
1322                 SA[first + skip] = skip;
1323             }
1324             if (n < isaD - isa) {
1325                 first = 0;
1326                 do {
1327                     if ((t = SA[first]) < 0) {
1328                         first -= t;
1329                     } else {
1330                         last = SA[isa + t] + 1;
1331                         for (i = first; i < last; ++i) {
1332                             SA[isa + SA[i]] = i;
1333                         }
1334                         first = last;
1335                     }
1336                 } while (first < n);
1337                 break;
1338             }
1339         }
1340     }
1341 
1342     /*---------------------------------------------------------------------------*/
1343 
1344     private static class PartitionResult {
1345         final int first;
1346         final int last;
1347 
1348         PartitionResult(final int first, final int last) {
1349             this.first = first;
1350             this.last = last;
1351         }
1352     }
1353 
1354     private PartitionResult trPartition(final int isa, final int isaD, final int isaN,
1355                                         int first, int last, final int v) {
1356         final int[] SA = this.SA;
1357 
1358         int a, b, c, d, e, f;
1359         int t, s;
1360         int x = 0;
1361 
1362         b = first;
1363         while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1364             ++b;
1365         }
1366         if ((a = b) < last && x < v) {
1367             while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1368                 if (x == v) {
1369                     swapElements(SA, b, SA, a);
1370                     ++a;
1371                 }
1372             }
1373         }
1374 
1375         c = last - 1;
1376         while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1377             --c;
1378         }
1379         if (b < (d = c) && x > v) {
1380             while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1381                 if (x == v) {
1382                     swapElements(SA, c, SA, d);
1383                     --d;
1384                 }
1385             }
1386         }
1387         while (b < c) {
1388             swapElements(SA, b, SA, c);
1389             while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1390                 if (x == v) {
1391                     swapElements(SA, b, SA, a);
1392                     ++a;
1393                 }
1394             }
1395             while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1396                 if (x == v) {
1397                     swapElements(SA, c, SA, d);
1398                     --d;
1399                 }
1400             }
1401         }
1402 
1403         if (a <= d) {
1404             c = b - 1;
1405             if ((s = a - first) > (t = b - a)) {
1406                 s = t;
1407             }
1408             for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1409                 swapElements(SA, e, SA, f);
1410             }
1411             if ((s = d - c) > (t = last - d - 1)) {
1412                 s = t;
1413             }
1414             for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1415                 swapElements(SA, e, SA, f);
1416             }
1417             first += b - a;
1418             last -= d - c;
1419         }
1420         return new PartitionResult(first, last);
1421     }
1422 
1423     private void trCopy(final int isa, final int isaN, final int first,
1424                         final int a, final int b, final int last, final int depth) {
1425         final int[] SA = this.SA;
1426 
1427         int c, d, e;
1428         int s, v;
1429 
1430         v = b - 1;
1431 
1432         for (c = first, d = a - 1; c <= d; ++c) {
1433             if ((s = SA[c] - depth) < 0) {
1434                 s += isaN - isa;
1435             }
1436             if (SA[isa + s] == v) {
1437                 SA[++d] = s;
1438                 SA[isa + s] = d;
1439             }
1440         }
1441         for (c = last - 1, e = d + 1, d = b; e < d; --c) {
1442             if ((s = SA[c] - depth) < 0) {
1443                 s += isaN - isa;
1444             }
1445             if (SA[isa + s] == v) {
1446                 SA[--d] = s;
1447                 SA[isa + s] = d;
1448             }
1449         }
1450     }
1451 
1452     private void trIntroSort(final int isa, int isaD, int isaN, int first,
1453                              int last, final TRBudget budget, final int size) {
1454         final int[] SA = this.SA;
1455 
1456         final StackEntry[] stack = new StackEntry[STACK_SIZE];
1457 
1458         int a, b, c, d, e, f;
1459         int s, t;
1460         int v, x = 0;
1461         int limit, next;
1462         int ssize;
1463 
1464         for (ssize = 0, limit = trLog(last - first);;) {
1465             if (limit < 0) {
1466                 if (limit == -1) {
1467                     if (!budget.update(size, last - first)) {
1468                         break;
1469                     }
1470                     PartitionResult result = trPartition(isa, isaD - 1, isaN, first, last, last - 1);
1471                     a = result.first;
1472                     b = result.last;
1473                     if (first < a || b < last) {
1474                         if (a < last) {
1475                             for (c = first, v = a - 1; c < a; ++c) {
1476                                 SA[isa + SA[c]] = v;
1477                             }
1478                         }
1479                         if (b < last) {
1480                             for (c = a, v = b - 1; c < b; ++c) {
1481                                 SA[isa + SA[c]] = v;
1482                             }
1483                         }
1484 
1485                         stack[ssize++] = new StackEntry(0, a, b, 0);
1486                         stack[ssize++] = new StackEntry(isaD - 1, first, last, -2);
1487                         if (a - first <= last - b) {
1488                             if (1 < a - first) {
1489                                 stack[ssize++] = new StackEntry(isaD, b, last, trLog(last - b));
1490                                 last = a; limit = trLog(a - first);
1491                             } else if (1 < last - b) {
1492                                 first = b; limit = trLog(last - b);
1493                             } else {
1494                                 if (ssize == 0) {
1495                                     return;
1496                                 }
1497                                 StackEntry entry = stack[--ssize];
1498                                 isaD = entry.a;
1499                                 first = entry.b;
1500                                 last = entry.c;
1501                                 limit = entry.d;
1502                             }
1503                         } else {
1504                             if (1 < last - b) {
1505                                 stack[ssize++] = new StackEntry(isaD, first, a, trLog(a - first));
1506                                 first = b;
1507                                 limit = trLog(last - b);
1508                             } else if (1 < a - first) {
1509                                 last = a;
1510                                 limit = trLog(a - first);
1511                             } else {
1512                                 if (ssize == 0) {
1513                                     return;
1514                                 }
1515                                 StackEntry entry = stack[--ssize];
1516                                 isaD = entry.a;
1517                                 first = entry.b;
1518                                 last = entry.c;
1519                                 limit = entry.d;
1520                             }
1521                         }
1522                     } else {
1523                         for (c = first; c < last; ++c) {
1524                             SA[isa + SA[c]] = c;
1525                         }
1526                         if (ssize == 0) {
1527                             return;
1528                         }
1529                         StackEntry entry = stack[--ssize];
1530                         isaD = entry.a;
1531                         first = entry.b;
1532                         last = entry.c;
1533                         limit = entry.d;
1534                     }
1535                 } else if (limit == -2) {
1536                     a = stack[--ssize].b;
1537                     b = stack[ssize].c;
1538                     trCopy(isa, isaN, first, a, b, last, isaD - isa);
1539                     if (ssize == 0) {
1540                         return;
1541                     }
1542                     StackEntry entry = stack[--ssize];
1543                     isaD = entry.a;
1544                     first = entry.b;
1545                     last = entry.c;
1546                     limit = entry.d;
1547                 } else {
1548                     if (0 <= SA[first]) {
1549                         a = first;
1550                         do {
1551                             SA[isa + SA[a]] = a;
1552                         } while (++a < last && 0 <= SA[a]);
1553                         first = a;
1554                     }
1555                     if (first < last) {
1556                         a = first;
1557                         do {
1558                             SA[a] = ~SA[a];
1559                         } while (SA[++a] < 0);
1560                         next = SA[isa + SA[a]] != SA[isaD + SA[a]] ? trLog(a - first + 1) : -1;
1561                         if (++a < last) {
1562                             for (b = first, v = a - 1; b < a; ++b) {
1563                                 SA[isa + SA[b]] = v;
1564                             }
1565                         }
1566 
1567                         if (a - first <= last - a) {
1568                             stack[ssize++] = new StackEntry(isaD, a, last, -3);
1569                             isaD += 1; last = a; limit = next;
1570                         } else {
1571                             if (1 < last - a) {
1572                                 stack[ssize++] = new StackEntry(isaD + 1, first, a, next);
1573                                 first = a; limit = -3;
1574                             } else {
1575                                 isaD += 1; last = a; limit = next;
1576                             }
1577                         }
1578                     } else {
1579                         if (ssize == 0) {
1580                             return;
1581                         }
1582                         StackEntry entry = stack[--ssize];
1583                         isaD = entry.a;
1584                         first = entry.b;
1585                         last = entry.c;
1586                         limit = entry.d;
1587                     }
1588                 }
1589                 continue;
1590             }
1591 
1592             if (last - first <= INSERTIONSORT_THRESHOLD) {
1593                 if (!budget.update(size, last - first)) {
1594                     break;
1595                 }
1596                 trInsertionSort(isa, isaD, isaN, first, last);
1597                 limit = -3;
1598                 continue;
1599             }
1600 
1601             if (limit-- == 0) {
1602                 if (!budget.update(size, last - first)) {
1603                     break;
1604                 }
1605                 trHeapSort(isa, isaD, isaN, first, last - first);
1606                 for (a = last - 1; first < a; a = b) {
1607                     for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
1608                             first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
1609                             --b) {
1610                         SA[b] = ~SA[b];
1611                     }
1612                 }
1613                 limit = -3;
1614                 continue;
1615             }
1616 
1617             a = trPivot(isa, isaD, isaN, first, last);
1618 
1619             swapElements(SA, first, SA, a);
1620             v = trGetC(isa, isaD, isaN, SA[first]);
1621 
1622             b = first + 1;
1623             while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1624                 ++b;
1625             }
1626             if ((a = b) < last && x < v) {
1627                 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1628                     if (x == v) {
1629                         swapElements(SA, b, SA, a);
1630                         ++a;
1631                     }
1632                 }
1633             }
1634 
1635             c = last - 1;
1636             while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1637                 --c;
1638             }
1639             if (b < (d = c) && x > v) {
1640                 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1641                     if (x == v) {
1642                         swapElements(SA, c, SA, d);
1643                         --d;
1644                     }
1645                 }
1646             }
1647             while (b < c) {
1648                 swapElements(SA, b, SA, c);
1649                 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1650                     if (x == v) {
1651                         swapElements(SA, b, SA, a);
1652                         ++a;
1653                     }
1654                 }
1655                 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1656                     if (x == v) {
1657                         swapElements(SA, c, SA, d);
1658                         --d;
1659                     }
1660                 }
1661             }
1662 
1663             if (a <= d) {
1664                 c = b - 1;
1665 
1666                 if ((s = a - first) > (t = b - a)) {
1667                     s = t;
1668                 }
1669                 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1670                     swapElements(SA, e, SA, f);
1671                 }
1672                 if ((s = d - c) > (t = last - d - 1)) {
1673                     s = t;
1674                 }
1675                 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1676                     swapElements(SA, e, SA, f);
1677                 }
1678 
1679                 a = first + (b - a);
1680                 b = last - (d - c);
1681                 next = SA[isa + SA[a]] != v ? trLog(b - a) : -1;
1682 
1683                 for (c = first, v = a - 1; c < a; ++c) {
1684                     SA[isa + SA[c]] = v;
1685                 }
1686                 if (b < last) {
1687                     for (c = a, v = b - 1; c < b; ++c) {
1688                         SA[isa + SA[c]] = v; }
1689                 }
1690 
1691                 if (a - first <= last - b) {
1692                     if (last - b <= b - a) {
1693                         if (1 < a - first) {
1694                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1695                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1696                             last = a;
1697                         } else if (1 < last - b) {
1698                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1699                             first = b;
1700                         } else if (1 < b - a) {
1701                             isaD += 1;
1702                             first = a;
1703                             last = b;
1704                             limit = next;
1705                         } else {
1706                             if (ssize == 0) {
1707                                 return;
1708                             }
1709                             StackEntry entry = stack[--ssize];
1710                             isaD = entry.a;
1711                             first = entry.b;
1712                             last = entry.c;
1713                             limit = entry.d;
1714                         }
1715                     } else if (a - first <= b - a) {
1716                         if (1 < a - first) {
1717                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1718                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1719                             last = a;
1720                         } else if (1 < b - a) {
1721                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1722                             isaD += 1;
1723                             first = a;
1724                             last = b;
1725                             limit = next;
1726                         } else {
1727                             first = b;
1728                         }
1729                     } else {
1730                         if (1 < b - a) {
1731                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1732                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1733                             isaD += 1;
1734                             first = a;
1735                             last = b;
1736                             limit = next;
1737                         } else {
1738                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1739                             last = a;
1740                         }
1741                     }
1742                 } else {
1743                     if (a - first <= b - a) {
1744                         if (1 < last - b) {
1745                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1746                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1747                             first = b;
1748                         } else if (1 < a - first) {
1749                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1750                             last = a;
1751                         } else if (1 < b - a) {
1752                             isaD += 1;
1753                             first = a;
1754                             last = b;
1755                             limit = next;
1756                         } else {
1757                             stack[ssize++] = new StackEntry(isaD, first, last, limit);
1758                         }
1759                     } else if (last - b <= b - a) {
1760                         if (1 < last - b) {
1761                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1762                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1763                             first = b;
1764                         } else if (1 < b - a) {
1765                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1766                             isaD += 1;
1767                             first = a;
1768                             last = b;
1769                             limit = next;
1770                         } else {
1771                             last = a;
1772                         }
1773                     } else {
1774                         if (1 < b - a) {
1775                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1776                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1777                             isaD += 1;
1778                             first = a;
1779                             last = b;
1780                             limit = next;
1781                         } else {
1782                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1783                             first = b;
1784                         }
1785                     }
1786                 }
1787             } else {
1788                 if (!budget.update(size, last - first)) {
1789                     break; // BUGFIX : Added to prevent an infinite loop in the original code
1790                 }
1791                 limit += 1; isaD += 1;
1792             }
1793         }
1794 
1795         for (s = 0; s < ssize; ++s) {
1796             if (stack[s].d == -3) {
1797                 lsUpdateGroup(isa, stack[s].b, stack[s].c);
1798             }
1799         }
1800     }
1801 
1802     private static class TRBudget {
1803         int budget;
1804         int chance;
1805 
1806         TRBudget(final int budget, final int chance) {
1807             this.budget = budget;
1808             this.chance = chance;
1809         }
1810 
1811         boolean update(final int size, final int n) {
1812             budget -= n;
1813             if (budget <= 0) {
1814                 if (--chance == 0) {
1815                     return false;
1816                 }
1817                 budget += size;
1818             }
1819             return true;
1820         }
1821     }
1822 
1823     private void trSort(final int isa, final int n, final int depth) {
1824         final int[] SA = this.SA;
1825 
1826         int first = 0, last;
1827         int t;
1828 
1829         if (-n < SA[0]) {
1830             TRBudget budget = new TRBudget(n, trLog(n) * 2 / 3 + 1);
1831             do {
1832                 if ((t = SA[first]) < 0) {
1833                     first -= t;
1834                 } else {
1835                     last = SA[isa + t] + 1;
1836                     if (1 < last - first) {
1837                         trIntroSort(isa, isa + depth, isa + n, first, last, budget, n);
1838                         if (budget.chance == 0) {
1839                             /* Switch to Larsson-Sadakane sorting algorithm */
1840                             if (0 < first) {
1841                                 SA[0] = -first;
1842                             }
1843                             lsSort(isa, n, depth);
1844                             break;
1845                         }
1846                     }
1847                     first = last;
1848                 }
1849             } while (first < n);
1850         }
1851     }
1852 
1853     /*---------------------------------------------------------------------------*/
1854 
1855     private static int BUCKET_B(final int c0, final int c1) {
1856         return (c1 << 8) | c0;
1857     }
1858 
1859     private static int BUCKET_BSTAR(final int c0, final int c1) {
1860         return (c0 << 8) | c1;
1861     }
1862 
1863     private int sortTypeBstar(final int[] bucketA, final int[] bucketB) {
1864         final byte[] T = this.T;
1865         final int[] SA = this.SA;
1866         final int n = this.n;
1867         final int[] tempbuf = new int[256];
1868 
1869         int[] buf;
1870         int PAb, ISAb, bufoffset;
1871         int i, j, k, t, m, bufsize;
1872         int c0, c1;
1873         int flag;
1874 
1875         for (i = 1, flag = 1; i < n; ++i) {
1876             if (T[i - 1] != T[i]) {
1877                 if ((T[i - 1] & 0xff) > (T[i] & 0xff)) {
1878                     flag = 0;
1879                 }
1880                 break;
1881             }
1882         }
1883         i = n - 1;
1884         m = n;
1885 
1886         int ti, ti1, t0;
1887         if ((ti = T[i] & 0xff) < (t0 = T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
1888             if (flag == 0) {
1889                 ++bucketB[BUCKET_BSTAR(ti, t0)];
1890                 SA[--m] = i;
1891             } else {
1892                 ++bucketB[BUCKET_B(ti, t0)];
1893             }
1894             for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
1895                 ++bucketB[BUCKET_B(ti, ti1)];
1896             }
1897         }
1898 
1899         while (0 <= i) {
1900             do {
1901                 ++bucketA[T[i] & 0xff];
1902             } while (0 <= --i && (T[i] & 0xff) >= (T[i + 1] & 0xff));
1903             if (0 <= i) {
1904                 ++bucketB[BUCKET_BSTAR(T[i] & 0xff, T[i + 1] & 0xff)];
1905                 SA[--m] = i;
1906                 for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
1907                     ++bucketB[BUCKET_B(ti, ti1)];
1908                 }
1909             }
1910         }
1911         m = n - m;
1912         if (m == 0) {
1913             for (i = 0; i < n; ++i) {
1914                 SA[i] = i;
1915             }
1916             return 0;
1917         }
1918 
1919         for (c0 = 0, i = -1, j = 0; c0 < 256; ++c0) {
1920             t = i + bucketA[c0];
1921             bucketA[c0] = i + j;
1922             i = t + bucketB[BUCKET_B(c0, c0)];
1923             for (c1 = c0 + 1; c1 < 256; ++c1) {
1924                 j += bucketB[BUCKET_BSTAR(c0, c1)];
1925                 bucketB[(c0 << 8) | c1] = j;
1926                 i += bucketB[BUCKET_B(c0, c1)];
1927             }
1928         }
1929 
1930         PAb = n - m;
1931         ISAb = m;
1932         for (i = m - 2; 0 <= i; --i) {
1933             t = SA[PAb + i];
1934             c0 = T[t] & 0xff;
1935             c1 = T[t + 1] & 0xff;
1936             SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = i;
1937         }
1938         t = SA[PAb + m - 1];
1939         c0 = T[t] & 0xff;
1940         c1 = T[t + 1] & 0xff;
1941         SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = m - 1;
1942 
1943         buf = SA;
1944         bufoffset = m;
1945         bufsize = n - 2 * m;
1946         if (bufsize <= 256) {
1947             buf = tempbuf;
1948             bufoffset = 0;
1949             bufsize = 256;
1950         }
1951 
1952         for (c0 = 255, j = m; 0 < j; --c0) {
1953             for (c1 = 255; c0 < c1; j = i, --c1) {
1954                 i = bucketB[BUCKET_BSTAR(c0, c1)];
1955                 if (1 < j - i) {
1956                     subStringSort(PAb, i, j, buf, bufoffset, bufsize, 2, SA[i] == m - 1, n);
1957                 }
1958             }
1959         }
1960 
1961         for (i = m - 1; 0 <= i; --i) {
1962             if (0 <= SA[i]) {
1963                 j = i;
1964                 do {
1965                     SA[ISAb + SA[i]] = i;
1966                 } while (0 <= --i && 0 <= SA[i]);
1967                 SA[i + 1] = i - j;
1968                 if (i <= 0) {
1969                     break;
1970                 }
1971             }
1972             j = i;
1973             do {
1974                 SA[ISAb + (SA[i] = ~SA[i])] = j;
1975             } while (SA[--i] < 0);
1976             SA[ISAb + SA[i]] = j;
1977         }
1978 
1979         trSort(ISAb, m, 1);
1980 
1981         i = n - 1; j = m;
1982         if ((T[i] & 0xff) < (T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
1983             if (flag == 0) {
1984                 SA[SA[ISAb + --j]] = i;
1985             }
1986             for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
1987                 --i;
1988             }
1989         }
1990         while (0 <= i) {
1991             for (--i; 0 <= i && (T[i] & 0xff) >= (T[i + 1] & 0xff);) {
1992                 --i;
1993             }
1994             if (0 <= i) {
1995                 SA[SA[ISAb + --j]] = i;
1996                 for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
1997                     --i;
1998                 }
1999             }
2000         }
2001 
2002         for (c0 = 255, i = n - 1, k = m - 1; 0 <= c0; --c0) {
2003             for (c1 = 255; c0 < c1; --c1) {
2004                 t = i - bucketB[BUCKET_B(c0, c1)];
2005                 bucketB[BUCKET_B(c0, c1)] = i + 1;
2006 
2007                 for (i = t, j = bucketB[BUCKET_BSTAR(c0, c1)]; j <= k; --i, --k) {
2008                     SA[i] = SA[k];
2009                 }
2010             }
2011             t = i - bucketB[BUCKET_B(c0, c0)];
2012             bucketB[BUCKET_B(c0, c0)] = i + 1;
2013             if (c0 < 255) {
2014                 bucketB[BUCKET_BSTAR(c0, c0 + 1)] = t + 1;
2015             }
2016             i = bucketA[c0];
2017         }
2018         return m;
2019     }
2020 
2021     private int constructBWT(final int[] bucketA, final int[] bucketB) {
2022         final byte[] T = this.T;
2023         final int[] SA = this.SA;
2024         final int n = this.n;
2025 
2026         int i, j, t = 0;
2027         int s, s1;
2028         int c0, c1, c2 = 0;
2029         int orig = -1;
2030 
2031         for (c1 = 254; 0 <= c1; --c1) {
2032             for (i = bucketB[BUCKET_BSTAR(c1, c1 + 1)], j = bucketA[c1 + 1], t = 0, c2 = -1;
2033                     i <= j;
2034                     --j) {
2035                 if (0 <= (s1 = s = SA[j])) {
2036                     if (--s < 0) {
2037                         s = n - 1;
2038                     }
2039                     if ((c0 = T[s] & 0xff) <= c1) {
2040                         SA[j] = ~s1;
2041                         if (0 < s && (T[s - 1] & 0xff) > c0) {
2042                             s = ~s;
2043                         }
2044                         if (c2 == c0) {
2045                             SA[--t] = s;
2046                         } else {
2047                             if (0 <= c2) {
2048                                 bucketB[BUCKET_B(c2, c1)] = t;
2049                             }
2050                             SA[t = bucketB[BUCKET_B(c2 = c0, c1)] - 1] = s;
2051                         }
2052                     }
2053                 } else {
2054                     SA[j] = ~s;
2055                 }
2056             }
2057         }
2058 
2059         for (i = 0; i < n; ++i) {
2060             if (0 <= (s1 = s = SA[i])) {
2061                 if (--s < 0) {
2062                     s = n - 1;
2063                 }
2064                 if ((c0 = T[s] & 0xff) >= (T[s + 1] & 0xff)) {
2065                     if (0 < s && (T[s - 1] & 0xff) < c0) {
2066                         s = ~s;
2067                     }
2068                     if (c0 == c2) {
2069                         SA[++t] = s;
2070                     } else {
2071                         if (c2 != -1) {
2072                             bucketA[c2] = t;    // BUGFIX: Original code can write to bucketA[-1]
2073                         }
2074                         SA[t = bucketA[c2 = c0] + 1] = s;
2075                     }
2076                 }
2077             } else {
2078                 s1 = ~s1;
2079             }
2080 
2081             if (s1 == 0) {
2082                 SA[i] = T[n - 1];
2083                 orig = i;
2084             } else {
2085                 SA[i] = T[s1 - 1];
2086             }
2087         }
2088         return orig;
2089     }
2090 
2091     /**
2092      * Performs a Burrows Wheeler Transform on the input array.
2093      * @return the index of the first character of the input array within the output array
2094      */
2095     public int bwt() {
2096         final int[] SA = this.SA;
2097         final byte[] T = this.T;
2098         final int n = this.n;
2099 
2100         final int[] bucketA = new int[BUCKET_A_SIZE];
2101         final int[] bucketB = new int[BUCKET_B_SIZE];
2102 
2103         if (n == 0) {
2104             return 0;
2105         }
2106         if (n == 1) {
2107             SA[0] = T[0];
2108             return 0;
2109         }
2110 
2111         int m = sortTypeBstar(bucketA, bucketB);
2112         if (0 < m) {
2113             return constructBWT(bucketA, bucketB);
2114         }
2115         return 0;
2116     }
2117 }