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    *   http://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) { SA[i++] = buf[j]; buf[j++] = SA[i]; }
572                         SA[i] = buf[j]; buf[j] = t;
573                         return;
574                     }
575                 } while (SA[k] < 0);
576             } else {
577                 SA[k] = ~SA[k];
578                 do {
579                     SA[i++] = buf[j];
580                     if (bufend <= j) {
581                         buf[j] = t;
582                         return;
583                     }
584                     buf[j++] = SA[i];
585                 } while (buf[j] < 0);
586 
587                 do {
588                     SA[i++] = SA[k];
589                     SA[k++] = SA[i];
590                     if (last <= k) {
591                         while (j < bufend) {
592                             SA[i++] = buf[j];
593                             buf[j++] = SA[i];
594                         }
595                         SA[i] = buf[j]; buf[j] = t;
596                         return;
597                     }
598                 } while (SA[k] < 0);
599             }
600         }
601     }
602 
603     private void ssMergeBackward(final int pa, int[] buf, final int bufoffset,
604                                  final int first, final int middle, final int last, final int depth) {
605         final int[] SA = this.SA;
606 
607         int p1, p2;
608         int bufend;
609         int i, j, k;
610         int t;
611         int r;
612         int x;
613 
614         bufend = bufoffset + (last - middle);
615         ssBlockSwap(buf, bufoffset, SA, middle, last - middle);
616 
617         x = 0;
618         if (buf[bufend - 1] < 0) {
619             x |=  1;
620             p1 = pa + ~buf[bufend - 1];
621         } else {
622             p1 = pa +  buf[bufend - 1];
623         }
624         if (SA[middle - 1] < 0) {
625             x |=  2;
626             p2 = pa + ~SA[middle - 1];
627         } else {
628             p2 = pa +  SA[middle - 1];
629         }
630         for (t = SA[last - 1], i = last - 1, j = bufend - 1, k = middle - 1;;) {
631 
632             r = ssCompare(p1, p2, depth);
633             if (r > 0) {
634                 if ((x & 1) != 0) {
635                     do {
636                         SA[i--] = buf[j];
637                         buf[j--] = SA[i];
638                     } while (buf[j] < 0);
639                     x ^= 1;
640                 }
641                 SA[i--] = buf[j];
642                 if (j <= bufoffset) {
643                     buf[j] = t;
644                     return;
645                 }
646                 buf[j--] = SA[i];
647 
648                 if (buf[j] < 0) {
649                     x |=  1;
650                     p1 = pa + ~buf[j];
651                 } else {
652                     p1 = pa +  buf[j];
653                 }
654             } else if (r < 0) {
655                 if ((x & 2) != 0) {
656                     do {
657                         SA[i--] = SA[k];
658                         SA[k--] = SA[i];
659                     } while (SA[k] < 0);
660                     x ^= 2;
661                 }
662                 SA[i--] = SA[k];
663                 SA[k--] = SA[i];
664                 if (k < first) {
665                     while (bufoffset < j) {
666                         SA[i--] = buf[j];
667                         buf[j--] = SA[i];
668                     }
669                     SA[i] = buf[j];
670                     buf[j] = t;
671                     return;
672                 }
673 
674                 if (SA[k] < 0) {
675                     x |=  2;
676                     p2 = pa + ~SA[k];
677                 } else {
678                     p2 = pa +  SA[k];
679                 }
680             } else {
681                 if ((x & 1) != 0) {
682                     do {
683                         SA[i--] = buf[j];
684                         buf[j--] = SA[i];
685                     } while (buf[j] < 0);
686                     x ^= 1;
687                 }
688                 SA[i--] = ~buf[j];
689                 if (j <= bufoffset) {
690                     buf[j] = t;
691                     return;
692                 }
693                 buf[j--] = SA[i];
694 
695                 if ((x & 2) != 0) {
696                     do {
697                         SA[i--] = SA[k];
698                         SA[k--] = SA[i];
699                     } while (SA[k] < 0);
700                     x ^= 2;
701                 }
702                 SA[i--] = SA[k];
703                 SA[k--] = SA[i];
704                 if (k < first) {
705                     while (bufoffset < j) {
706                         SA[i--] = buf[j];
707                         buf[j--] = SA[i];
708                     }
709                     SA[i] = buf[j];
710                     buf[j] = t;
711                     return;
712                 }
713 
714                 if (buf[j] < 0) {
715                     x |=  1;
716                     p1 = pa + ~buf[j];
717                 } else {
718                     p1 = pa +  buf[j];
719                 }
720                 if (SA[k] < 0) {
721                     x |=  2;
722                     p2 = pa + ~SA[k];
723                 } else {
724                     p2 = pa +  SA[k];
725                 }
726             }
727         }
728     }
729 
730     private static int getIDX(final int a) {
731         return 0 <= a ? a : ~a;
732     }
733 
734     private void ssMergeCheckEqual(final int pa, final int depth, final int a) {
735         final int[] SA = this.SA;
736 
737         if (0 <= SA[a] && ssCompare(pa + getIDX(SA[a - 1]), pa + SA[a], depth) == 0) {
738             SA[a] = ~SA[a];
739         }
740     }
741 
742     private void ssMerge(final int pa, int first, int middle, int last, int[] buf,
743                          final int bufoffset, final int bufsize, final int depth) {
744         final int[] SA = this.SA;
745 
746         final StackEntry[] stack = new StackEntry[STACK_SIZE];
747 
748         int i, j;
749         int m, len, half;
750         int ssize;
751         int check, next;
752 
753         for (check = 0, ssize = 0;;) {
754 
755             if (last - middle <= bufsize) {
756                 if (first < middle && middle < last) {
757                     ssMergeBackward(pa, buf, bufoffset, first, middle, last, depth);
758                 }
759 
760                 if ((check & 1) != 0) {
761                     ssMergeCheckEqual(pa, depth, first);
762                 }
763                 if ((check & 2) != 0) {
764                     ssMergeCheckEqual(pa, depth, last);
765                 }
766                 if (ssize == 0) {
767                     return;
768                 }
769                 StackEntry entry = stack[--ssize];
770                 first = entry.a;
771                 middle = entry.b;
772                 last = entry.c;
773                 check = entry.d;
774                 continue;
775             }
776 
777             if (middle - first <= bufsize) {
778                 if (first < middle) {
779                     ssMergeForward(pa, buf, bufoffset, first, middle, last, depth);
780                 }
781                 if ((check & 1) != 0) {
782                     ssMergeCheckEqual(pa, depth, first);
783                 }
784                 if ((check & 2) != 0) {
785                     ssMergeCheckEqual(pa, depth, last);
786                 }
787                 if (ssize == 0) {
788                     return;
789                 }
790                 StackEntry entry = stack[--ssize];
791                 first = entry.a;
792                 middle = entry.b;
793                 last = entry.c;
794                 check = entry.d;
795                 continue;
796             }
797 
798             for (m = 0, len = Math.min(middle - first, last - middle), half = len >> 1;
799                     0 < len;
800                     len = half, half >>= 1) {
801 
802                 if (ssCompare(pa + getIDX(SA[middle + m + half]),
803                         pa + getIDX(SA[middle - m - half - 1]), depth) < 0) {
804                     m += half + 1;
805                     half -= (len & 1) ^ 1;
806                 }
807             }
808 
809             if (0 < m) {
810                 ssBlockSwap(SA, middle - m, SA, middle, m);
811                 i = j = middle;
812                 next = 0;
813                 if (middle + m < last) {
814                     if (SA[middle + m] < 0) {
815                         while (SA[i - 1] < 0) {
816                             --i;
817                         }
818                         SA[middle + m] = ~SA[middle + m];
819                     }
820                     for (j = middle; SA[j] < 0;) {
821                         ++j;
822                     }
823                     next = 1;
824                 }
825                 if (i - first <= last - j) {
826                     stack[ssize++] = new StackEntry(j, middle + m, last, (check &  2) | (next & 1));
827                     middle -= m;
828                     last = i;
829                     check &= 1;
830                 } else {
831                     if (i == middle && middle == j) {
832                         next <<= 1;
833                     }
834                     stack[ssize++] = new StackEntry(first, middle - m, i, (check & 1) | (next & 2));
835                     first = j;
836                     middle += m;
837                     check = (check & 2) | (next & 1);
838                 }
839             } else {
840                 if ((check & 1) != 0) {
841                     ssMergeCheckEqual(pa, depth, first);
842                 }
843                 ssMergeCheckEqual(pa, depth, middle);
844                 if ((check & 2) != 0) {
845                     ssMergeCheckEqual(pa, depth, last);
846                 }
847                 if (ssize == 0) {
848                     return;
849                 }
850                 StackEntry entry = stack[--ssize];
851                 first = entry.a;
852                 middle = entry.b;
853                 last = entry.c;
854                 check = entry.d;
855             }
856         }
857     }
858 
859     private void subStringSort(final int pa, int first, final int last,
860                                final int[] buf, final int bufoffset, final int bufsize,
861                                final int depth, final boolean lastsuffix, final int size) {
862         final int[] SA = this.SA;
863 
864         int a, b;
865         int[] curbuf;
866         int curbufoffset;
867         int i, j, k;
868         int curbufsize;
869 
870         if (lastsuffix) {
871             ++first;
872         }
873         for (a = first, i = 0; a + SS_BLOCKSIZE < last; a += SS_BLOCKSIZE, ++i) {
874             ssMultiKeyIntroSort(pa, a, a + SS_BLOCKSIZE, depth);
875             curbuf = SA;
876             curbufoffset = a + SS_BLOCKSIZE;
877             curbufsize = last - (a + SS_BLOCKSIZE);
878             if (curbufsize <= bufsize) {
879                 curbufsize = bufsize;
880                 curbuf = buf;
881                 curbufoffset = bufoffset;
882             }
883             for (b = a, k = SS_BLOCKSIZE, j = i; (j & 1) != 0; b -= k, k <<= 1, j >>>= 1) {
884                 ssMerge(pa, b - k, b, b + k, curbuf, curbufoffset, curbufsize, depth);
885             }
886         }
887 
888         ssMultiKeyIntroSort(pa, a, last, depth);
889 
890         for (k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
891             if ((i & 1) != 0) {
892                 ssMerge(pa, a - k, a, last, buf, bufoffset, bufsize, depth);
893                 a -= k;
894             }
895         }
896 
897         if (lastsuffix) {
898             int r;
899             for (a = first, i = SA[first - 1], r = 1;
900                     a < last && (SA[a] < 0 || 0 < (r = ssCompareLast(pa, pa + i, pa + SA[a], depth, size)));
901                     ++a) {
902                 SA[a - 1] = SA[a];
903             }
904             if (r == 0) {
905                 SA[a] = ~SA[a];
906             }
907             SA[a - 1] = i;
908         }
909     }
910 
911     /*----------------------------------------------------------------------------*/
912 
913     private int trGetC(final int isa, final int isaD, final int isaN, final int p) {
914         return isaD + p < isaN ?
915                 SA[isaD + p]
916               : SA[isa + ((isaD - isa + p) % (isaN - isa))];
917     }
918 
919     private void trFixdown(final int isa, final int isaD, final int isaN, final int sa, int i, final int size) {
920         final int[] SA = this.SA;
921 
922         int j, k;
923         int v;
924         int c, d, e;
925 
926         for (v = SA[sa + i], c = trGetC(isa, isaD, isaN, v); (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
927             k = j++;
928             d = trGetC(isa, isaD, isaN, SA[sa + k]);
929             if (d < (e = trGetC(isa, isaD, isaN, SA[sa + j]))) {
930                 k = j;
931                 d = e;
932             }
933             if (d <= c) {
934                 break;
935             }
936         }
937         SA[sa + i] = v;
938     }
939 
940     private void trHeapSort(final int isa, final int isaD, final int isaN, final int sa, final int size) {
941         final int[] SA = this.SA;
942 
943         int i, m;
944         int t;
945 
946         m = size;
947         if (size % 2 == 0) {
948             m--;
949             if (trGetC(isa, isaD, isaN, SA[sa + m / 2]) < trGetC(isa, isaD, isaN, SA[sa + m])) {
950                 swapElements(SA, sa + m, SA, sa + m / 2);
951             }
952         }
953 
954         for (i = m / 2 - 1; 0 <= i; --i) {
955             trFixdown(isa, isaD, isaN, sa, i, m);
956         }
957 
958         if (size % 2 == 0) {
959             swapElements(SA, sa, SA, sa + m);
960             trFixdown(isa, isaD, isaN, sa, 0, m);
961         }
962 
963         for (i = m - 1; 0 < i; --i) {
964             t = SA[sa];
965             SA[sa] = SA[sa + i];
966             trFixdown(isa, isaD, isaN, sa, 0, i);
967             SA[sa + i] = t;
968         }
969     }
970 
971     private void trInsertionSort(final int isa, final int isaD, final int isaN, int first, int last) {
972         final int[] SA = this.SA;
973 
974         int a, b;
975         int t, r;
976 
977         for (a = first + 1; a < last; ++a) {
978             for (t = SA[a], b = a - 1; 0 > (r = trGetC(isa, isaD, isaN, t) - trGetC(isa, isaD, isaN, SA[b]));) {
979                 do {
980                     SA[b + 1] = SA[b];
981                 } while (first <= --b && SA[b] < 0);
982                 if (b < first) {
983                     break;
984                 }
985             }
986             if (r == 0) {
987                 SA[b] = ~SA[b];
988             }
989             SA[b + 1] = t;
990         }
991     }
992 
993     private static int trLog(int n) {
994         return (n & 0xffff0000) != 0 ?
995                   (n & 0xff000000) != 0 ? 24 + LOG_2_TABLE[n >> 24 & 0xff] : LOG_2_TABLE[n >> 16 & 0xff + 16]
996                 : (n & 0x0000ff00) != 0 ?  8 + LOG_2_TABLE[n >>  8 & 0xff] : LOG_2_TABLE[n & 0xff];
997     }
998 
999     private int trMedian3(final int isa, final int isaD, final int isaN, int v1, int v2, int v3) {
1000         final int[] SA = this.SA;
1001 
1002         int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
1003         int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
1004         int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
1005 
1006         if (SA_v1 > SA_v2) {
1007             final int temp = v1;
1008             v1 = v2;
1009             v2 = temp;
1010             final int SA_vtemp = SA_v1;
1011             SA_v1 = SA_v2;
1012             SA_v2 = SA_vtemp;
1013         }
1014         if (SA_v2 > SA_v3) {
1015             if (SA_v1 > SA_v3) {
1016                 return v1;
1017             }
1018             return v3;
1019         }
1020 
1021         return v2;
1022     }
1023 
1024     private int trMedian5(final int isa, final int isaD, final int isaN, int v1, int v2, int v3, int v4, int v5) {
1025         final int[] SA = this.SA;
1026 
1027         int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
1028         int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
1029         int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
1030         int SA_v4 = trGetC(isa, isaD, isaN, SA[v4]);
1031         int SA_v5 = trGetC(isa, isaD, isaN, SA[v5]);
1032         int temp;
1033         int SA_vtemp;
1034 
1035         if (SA_v2 > SA_v3) {
1036             temp = v2;
1037             v2 = v3;
1038             v3 = temp;
1039             SA_vtemp = SA_v2;
1040             SA_v2 = SA_v3;
1041             SA_v3 = SA_vtemp;
1042         }
1043         if (SA_v4 > SA_v5) {
1044             temp = v4;
1045             v4 = v5;
1046             v5 = temp;
1047             SA_vtemp = SA_v4;
1048             SA_v4 = SA_v5;
1049             SA_v5 = SA_vtemp;
1050         }
1051         if (SA_v2 > SA_v4) {
1052             temp = v2;
1053             v4 = temp;
1054             SA_vtemp = SA_v2;
1055             SA_v4 = SA_vtemp;
1056             temp = v3;
1057             v3 = v5;
1058             v5 = temp;
1059             SA_vtemp = SA_v3;
1060             SA_v3 = SA_v5;
1061             SA_v5 = SA_vtemp;
1062         }
1063         if (SA_v1 > SA_v3) {
1064             temp = v1;
1065             v1 = v3;
1066             v3 = temp;
1067             SA_vtemp = SA_v1;
1068             SA_v1 = SA_v3;
1069             SA_v3 = SA_vtemp;
1070         }
1071         if (SA_v1 > SA_v4) {
1072             temp = v1;
1073             v4 = temp;
1074             SA_vtemp = SA_v1;
1075             SA_v4 = SA_vtemp;
1076             v3 = v5;
1077             SA_v3 = SA_v5;
1078         }
1079         if (SA_v3 > SA_v4) {
1080             return v4;
1081         }
1082         return v3;
1083     }
1084 
1085     private int trPivot(final int isa, final int isaD, final int isaN, final int first, final int last) {
1086         final int middle;
1087         int t;
1088 
1089         t = last - first;
1090         middle = first + t / 2;
1091 
1092         if (t <= 512) {
1093             if (t <= 32) {
1094                 return trMedian3(isa, isaD, isaN, first, middle, last - 1);
1095             }
1096             t >>= 2;
1097             return trMedian5(
1098                     isa, isaD, isaN,
1099                     first, first + t,
1100                     middle,
1101                     last - 1 - t, last - 1
1102             );
1103         }
1104         t >>= 3;
1105         return trMedian3(
1106                 isa, isaD, isaN,
1107                 trMedian3(isa, isaD, isaN, first, first + t, first + (t << 1)),
1108                 trMedian3(isa, isaD, isaN, middle - t, middle, middle + t),
1109                 trMedian3(isa, isaD, isaN, last - 1 - (t << 1), last - 1 - t, last - 1)
1110         );
1111     }
1112 
1113     /*---------------------------------------------------------------------------*/
1114 
1115     private void lsUpdateGroup(final int isa, final int first, final int last) {
1116         final int[] SA = this.SA;
1117 
1118         int a, b;
1119         int t;
1120 
1121         for (a = first; a < last; ++a) {
1122             if (0 <= SA[a]) {
1123                 b = a;
1124                 do {
1125                     SA[isa + SA[a]] = a;
1126                 } while (++a < last && 0 <= SA[a]);
1127                 SA[b] = b - a;
1128                 if (last <= a) {
1129                     break;
1130                 }
1131             }
1132             b = a;
1133             do {
1134                 SA[a] = ~SA[a];
1135             } while (SA[++a] < 0);
1136             t = a;
1137             do {
1138                 SA[isa + SA[b]] = t;
1139             } while (++b <= a);
1140         }
1141     }
1142 
1143     private void lsIntroSort(final int isa, final int isaD, final int isaN, int first, int last) {
1144         final int[] SA = this.SA;
1145 
1146         final StackEntry[] stack = new StackEntry[STACK_SIZE];
1147 
1148         int a, b, c, d, e, f;
1149         int s, t;
1150         int limit;
1151         int v, x = 0;
1152         int ssize;
1153 
1154         for (ssize = 0, limit = trLog(last - first);;) {
1155             if (last - first <= INSERTIONSORT_THRESHOLD) {
1156                 if (1 < last - first) {
1157                     trInsertionSort(isa, isaD, isaN, first, last);
1158                     lsUpdateGroup(isa, first, last);
1159                 } else if (last - first == 1) {
1160                     SA[first] = -1;
1161                 }
1162                 if (ssize == 0) {
1163                     return;
1164                 }
1165                 StackEntry entry = stack[--ssize];
1166                 first = entry.a;
1167                 last = entry.b;
1168                 limit = entry.c;
1169                 continue;
1170             }
1171 
1172             if (limit-- == 0) {
1173                 trHeapSort(isa, isaD, isaN, first, last - first);
1174                 for (a = last - 1; first < a; a = b) {
1175                     for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
1176                             first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
1177                             --b) {
1178                         SA[b] = ~SA[b];
1179                     }
1180                 }
1181                 lsUpdateGroup(isa, first, last);
1182                 if (ssize == 0) {
1183                     return;
1184                 }
1185                 StackEntry entry = stack[--ssize];
1186                 first = entry.a;
1187                 last = entry.b;
1188                 limit = entry.c;
1189                 continue;
1190             }
1191 
1192             a = trPivot(isa, isaD, isaN, first, last);
1193             swapElements(SA, first, SA, a);
1194             v = trGetC(isa, isaD, isaN, SA[first]);
1195 
1196             b = first + 1;
1197             while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1198                 ++b;
1199             }
1200             if ((a = b) < last && x < v) {
1201                 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1202                     if (x == v) {
1203                         swapElements(SA, b, SA, a);
1204                         ++a;
1205                     }
1206                 }
1207             }
1208 
1209             c = last - 1;
1210             while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1211                 --c;
1212             }
1213             if (b < (d = c) && x > v) {
1214                 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1215                     if (x == v) {
1216                         swapElements(SA, c, SA, d);
1217                         --d;
1218                     }
1219                 }
1220             }
1221             while (b < c) {
1222                 swapElements(SA, b, SA, c);
1223                 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1224                     if (x == v) {
1225                         swapElements(SA, b, SA, a);
1226                         ++a;
1227                     }
1228                 }
1229                 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1230                     if (x == v) {
1231                         swapElements(SA, c, SA, d);
1232                         --d;
1233                     }
1234                 }
1235             }
1236 
1237             if (a <= d) {
1238                 c = b - 1;
1239 
1240                 if ((s = a - first) > (t = b - a)) {
1241                     s = t;
1242                 }
1243                 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1244                     swapElements(SA, e, SA, f);
1245                 }
1246                 if ((s = d - c) > (t = last - d - 1)) {
1247                     s = t;
1248                 }
1249                 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1250                     swapElements(SA, e, SA, f);
1251                 }
1252 
1253                 a = first + (b - a);
1254                 b = last - (d - c);
1255 
1256                 for (c = first, v = a - 1; c < a; ++c) {
1257                     SA[isa + SA[c]] = v;
1258                 }
1259                 if (b < last) {
1260                     for (c = a, v = b - 1; c < b; ++c) {
1261                         SA[isa + SA[c]] = v;
1262                     }
1263                 }
1264                 if ((b - a) == 1) {
1265                     SA[a] = - 1;
1266                 }
1267 
1268                 if (a - first <= last - b) {
1269                     if (first < a) {
1270                         stack[ssize++] = new StackEntry(b, last, limit, 0);
1271                         last = a;
1272                     } else {
1273                         first = b;
1274                     }
1275                 } else {
1276                     if (b < last) {
1277                         stack[ssize++] = new StackEntry(first, a, limit, 0);
1278                         first = b;
1279                     } else {
1280                         last = a;
1281                     }
1282                 }
1283             } else {
1284                 if (ssize == 0) {
1285                     return;
1286                 }
1287                 StackEntry entry = stack[--ssize];
1288                 first = entry.a;
1289                 last = entry.b;
1290                 limit = entry.c;
1291             }
1292         }
1293     }
1294 
1295     private void lsSort(final int isa, final int n, final int depth) {
1296         final int[] SA = this.SA;
1297 
1298         int isaD;
1299         int first, last, i;
1300         int t, skip;
1301 
1302         for (isaD = isa + depth; -n < SA[0]; isaD += isaD - isa) {
1303             first = 0;
1304             skip = 0;
1305             do {
1306                 if ((t = SA[first]) < 0) {
1307                     first -= t;
1308                     skip += t;
1309                 } else {
1310                     if (skip != 0) {
1311                         SA[first + skip] = skip;
1312                         skip = 0;
1313                     }
1314                     last = SA[isa + t] + 1;
1315                     lsIntroSort(isa, isaD, isa + n, first, last);
1316                     first = last;
1317                 }
1318             } while (first < n);
1319             if (skip != 0) {
1320                 SA[first + skip] = skip;
1321             }
1322             if (n < isaD - isa) {
1323                 first = 0;
1324                 do {
1325                     if ((t = SA[first]) < 0) {
1326                         first -= t;
1327                     } else {
1328                         last = SA[isa + t] + 1;
1329                         for (i = first; i < last; ++i) {
1330                             SA[isa + SA[i]] = i;
1331                         }
1332                         first = last;
1333                     }
1334                 } while (first < n);
1335                 break;
1336             }
1337         }
1338     }
1339 
1340     /*---------------------------------------------------------------------------*/
1341 
1342     private static class PartitionResult {
1343         final int first;
1344         final int last;
1345 
1346         PartitionResult(final int first, final int last) {
1347             this.first = first;
1348             this.last = last;
1349         }
1350     }
1351 
1352     private PartitionResult trPartition(final int isa, final int isaD, final int isaN,
1353                                         int first, int last, final int v) {
1354         final int[] SA = this.SA;
1355 
1356         int a, b, c, d, e, f;
1357         int t, s;
1358         int x = 0;
1359 
1360         b = first;
1361         while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1362             ++b;
1363         }
1364         if ((a = b) < last && x < v) {
1365             while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1366                 if (x == v) {
1367                     swapElements(SA, b, SA, a);
1368                     ++a;
1369                 }
1370             }
1371         }
1372 
1373         c = last - 1;
1374         while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1375             --c;
1376         }
1377         if (b < (d = c) && x > v) {
1378             while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1379                 if (x == v) {
1380                     swapElements(SA, c, SA, d);
1381                     --d;
1382                 }
1383             }
1384         }
1385         while (b < c) {
1386             swapElements(SA, b, SA, c);
1387             while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1388                 if (x == v) {
1389                     swapElements(SA, b, SA, a);
1390                     ++a;
1391                 }
1392             }
1393             while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1394                 if (x == v) {
1395                     swapElements(SA, c, SA, d);
1396                     --d;
1397                 }
1398             }
1399         }
1400 
1401         if (a <= d) {
1402             c = b - 1;
1403             if ((s = a - first) > (t = b - a)) {
1404                 s = t;
1405             }
1406             for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1407                 swapElements(SA, e, SA, f);
1408             }
1409             if ((s = d - c) > (t = last - d - 1)) {
1410                 s = t;
1411             }
1412             for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1413                 swapElements(SA, e, SA, f);
1414             }
1415             first += b - a;
1416             last -= d - c;
1417         }
1418         return new PartitionResult(first, last);
1419     }
1420 
1421     private void trCopy(final int isa, final int isaN, final int first,
1422                         final int a, final int b, final int last, final int depth) {
1423         final int[] SA = this.SA;
1424 
1425         int c, d, e;
1426         int s, v;
1427 
1428         v = b - 1;
1429 
1430         for (c = first, d = a - 1; c <= d; ++c) {
1431             if ((s = SA[c] - depth) < 0) {
1432                 s += isaN - isa;
1433             }
1434             if (SA[isa + s] == v) {
1435                 SA[++d] = s;
1436                 SA[isa + s] = d;
1437             }
1438         }
1439         for (c = last - 1, e = d + 1, d = b; e < d; --c) {
1440             if ((s = SA[c] - depth) < 0) {
1441                 s += isaN - isa;
1442             }
1443             if (SA[isa + s] == v) {
1444                 SA[--d] = s;
1445                 SA[isa + s] = d;
1446             }
1447         }
1448     }
1449 
1450     private void trIntroSort(final int isa, int isaD, int isaN, int first,
1451                              int last, final TRBudget budget, final int size) {
1452         final int[] SA = this.SA;
1453 
1454         final StackEntry[] stack = new StackEntry[STACK_SIZE];
1455 
1456         int a, b, c, d, e, f;
1457         int s, t;
1458         int v, x = 0;
1459         int limit, next;
1460         int ssize;
1461 
1462         for (ssize = 0, limit = trLog(last - first);;) {
1463             if (limit < 0) {
1464                 if (limit == -1) {
1465                     if (!budget.update(size, last - first)) {
1466                         break;
1467                     }
1468                     PartitionResult result = trPartition(isa, isaD - 1, isaN, first, last, last - 1);
1469                     a = result.first;
1470                     b = result.last;
1471                     if (first < a || b < last) {
1472                         if (a < last) {
1473                             for (c = first, v = a - 1; c < a; ++c) {
1474                                 SA[isa + SA[c]] = v;
1475                             }
1476                         }
1477                         if (b < last) {
1478                             for (c = a, v = b - 1; c < b; ++c) {
1479                                 SA[isa + SA[c]] = v;
1480                             }
1481                         }
1482 
1483                         stack[ssize++] = new StackEntry(0, a, b, 0);
1484                         stack[ssize++] = new StackEntry(isaD - 1, first, last, -2);
1485                         if (a - first <= last - b) {
1486                             if (1 < a - first) {
1487                                 stack[ssize++] = new StackEntry(isaD, b, last, trLog(last - b));
1488                                 last = a; limit = trLog(a - first);
1489                             } else if (1 < last - b) {
1490                                 first = b; limit = trLog(last - b);
1491                             } else {
1492                                 if (ssize == 0) {
1493                                     return;
1494                                 }
1495                                 StackEntry entry = stack[--ssize];
1496                                 isaD = entry.a;
1497                                 first = entry.b;
1498                                 last = entry.c;
1499                                 limit = entry.d;
1500                             }
1501                         } else {
1502                             if (1 < last - b) {
1503                                 stack[ssize++] = new StackEntry(isaD, first, a, trLog(a - first));
1504                                 first = b;
1505                                 limit = trLog(last - b);
1506                             } else if (1 < a - first) {
1507                                 last = a;
1508                                 limit = trLog(a - first);
1509                             } else {
1510                                 if (ssize == 0) {
1511                                     return;
1512                                 }
1513                                 StackEntry entry = stack[--ssize];
1514                                 isaD = entry.a;
1515                                 first = entry.b;
1516                                 last = entry.c;
1517                                 limit = entry.d;
1518                             }
1519                         }
1520                     } else {
1521                         for (c = first; c < last; ++c) {
1522                             SA[isa + SA[c]] = c;
1523                         }
1524                         if (ssize == 0) {
1525                             return;
1526                         }
1527                         StackEntry entry = stack[--ssize];
1528                         isaD = entry.a;
1529                         first = entry.b;
1530                         last = entry.c;
1531                         limit = entry.d;
1532                     }
1533                 } else if (limit == -2) {
1534                     a = stack[--ssize].b;
1535                     b = stack[ssize].c;
1536                     trCopy(isa, isaN, first, a, b, last, isaD - isa);
1537                     if (ssize == 0) {
1538                         return;
1539                     }
1540                     StackEntry entry = stack[--ssize];
1541                     isaD = entry.a;
1542                     first = entry.b;
1543                     last = entry.c;
1544                     limit = entry.d;
1545                 } else {
1546                     if (0 <= SA[first]) {
1547                         a = first;
1548                         do {
1549                             SA[isa + SA[a]] = a;
1550                         } while (++a < last && 0 <= SA[a]);
1551                         first = a;
1552                     }
1553                     if (first < last) {
1554                         a = first;
1555                         do {
1556                             SA[a] = ~SA[a];
1557                         } while (SA[++a] < 0);
1558                         next = SA[isa + SA[a]] != SA[isaD + SA[a]] ? trLog(a - first + 1) : -1;
1559                         if (++a < last) {
1560                             for (b = first, v = a - 1; b < a; ++b) {
1561                                 SA[isa + SA[b]] = v;
1562                             }
1563                         }
1564 
1565                         if (a - first <= last - a) {
1566                             stack[ssize++] = new StackEntry(isaD, a, last, -3);
1567                             isaD += 1; last = a; limit = next;
1568                         } else {
1569                             if (1 < last - a) {
1570                                 stack[ssize++] = new StackEntry(isaD + 1, first, a, next);
1571                                 first = a; limit = -3;
1572                             } else {
1573                                 isaD += 1; last = a; limit = next;
1574                             }
1575                         }
1576                     } else {
1577                         if (ssize == 0) {
1578                             return;
1579                         }
1580                         StackEntry entry = stack[--ssize];
1581                         isaD = entry.a;
1582                         first = entry.b;
1583                         last = entry.c;
1584                         limit = entry.d;
1585                     }
1586                 }
1587                 continue;
1588             }
1589 
1590             if (last - first <= INSERTIONSORT_THRESHOLD) {
1591                 if (!budget.update(size, last - first)) {
1592                     break;
1593                 }
1594                 trInsertionSort(isa, isaD, isaN, first, last);
1595                 limit = -3;
1596                 continue;
1597             }
1598 
1599             if (limit-- == 0) {
1600                 if (!budget.update(size, last - first)) {
1601                     break;
1602                 }
1603                 trHeapSort(isa, isaD, isaN, first, last - first);
1604                 for (a = last - 1; first < a; a = b) {
1605                     for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
1606                             first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
1607                             --b) {
1608                         SA[b] = ~SA[b];
1609                     }
1610                 }
1611                 limit = -3;
1612                 continue;
1613             }
1614 
1615             a = trPivot(isa, isaD, isaN, first, last);
1616 
1617             swapElements(SA, first, SA, a);
1618             v = trGetC(isa, isaD, isaN, SA[first]);
1619 
1620             b = first + 1;
1621             while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1622                 ++b;
1623             }
1624             if ((a = b) < last && x < v) {
1625                 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1626                     if (x == v) {
1627                         swapElements(SA, b, SA, a);
1628                         ++a;
1629                     }
1630                 }
1631             }
1632 
1633             c = last - 1;
1634             while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1635                 --c;
1636             }
1637             if (b < (d = c) && x > v) {
1638                 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1639                     if (x == v) {
1640                         swapElements(SA, c, SA, d);
1641                         --d;
1642                     }
1643                 }
1644             }
1645             while (b < c) {
1646                 swapElements(SA, b, SA, c);
1647                 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1648                     if (x == v) {
1649                         swapElements(SA, b, SA, a);
1650                         ++a;
1651                     }
1652                 }
1653                 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1654                     if (x == v) {
1655                         swapElements(SA, c, SA, d);
1656                         --d;
1657                     }
1658                 }
1659             }
1660 
1661             if (a <= d) {
1662                 c = b - 1;
1663 
1664                 if ((s = a - first) > (t = b - a)) {
1665                     s = t;
1666                 }
1667                 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1668                     swapElements(SA, e, SA, f);
1669                 }
1670                 if ((s = d - c) > (t = last - d - 1)) {
1671                     s = t;
1672                 }
1673                 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1674                     swapElements(SA, e, SA, f);
1675                 }
1676 
1677                 a = first + (b - a);
1678                 b = last - (d - c);
1679                 next = SA[isa + SA[a]] != v ? trLog(b - a) : -1;
1680 
1681                 for (c = first, v = a - 1; c < a; ++c) {
1682                     SA[isa + SA[c]] = v;
1683                 }
1684                 if (b < last) {
1685                     for (c = a, v = b - 1; c < b; ++c) {
1686                         SA[isa + SA[c]] = v; }
1687                 }
1688 
1689                 if (a - first <= last - b) {
1690                     if (last - b <= b - a) {
1691                         if (1 < a - first) {
1692                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1693                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1694                             last = a;
1695                         } else if (1 < last - b) {
1696                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1697                             first = b;
1698                         } else if (1 < b - a) {
1699                             isaD += 1;
1700                             first = a;
1701                             last = b;
1702                             limit = next;
1703                         } else {
1704                             if (ssize == 0) {
1705                                 return;
1706                             }
1707                             StackEntry entry = stack[--ssize];
1708                             isaD = entry.a;
1709                             first = entry.b;
1710                             last = entry.c;
1711                             limit = entry.d;
1712                         }
1713                     } else if (a - first <= b - a) {
1714                         if (1 < a - first) {
1715                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1716                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1717                             last = a;
1718                         } else if (1 < b - a) {
1719                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1720                             isaD += 1;
1721                             first = a;
1722                             last = b;
1723                             limit = next;
1724                         } else {
1725                             first = b;
1726                         }
1727                     } else {
1728                         if (1 < b - a) {
1729                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1730                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1731                             isaD += 1;
1732                             first = a;
1733                             last = b;
1734                             limit = next;
1735                         } else {
1736                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1737                             last = a;
1738                         }
1739                     }
1740                 } else {
1741                     if (a - first <= b - a) {
1742                         if (1 < last - b) {
1743                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1744                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1745                             first = b;
1746                         } else if (1 < a - first) {
1747                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1748                             last = a;
1749                         } else if (1 < b - a) {
1750                             isaD += 1;
1751                             first = a;
1752                             last = b;
1753                             limit = next;
1754                         } else {
1755                             stack[ssize++] = new StackEntry(isaD, first, last, limit);
1756                         }
1757                     } else if (last - b <= b - a) {
1758                         if (1 < last - b) {
1759                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1760                             stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1761                             first = b;
1762                         } else if (1 < b - a) {
1763                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1764                             isaD += 1;
1765                             first = a;
1766                             last = b;
1767                             limit = next;
1768                         } else {
1769                             last = a;
1770                         }
1771                     } else {
1772                         if (1 < b - a) {
1773                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1774                             stack[ssize++] = new StackEntry(isaD, b, last, limit);
1775                             isaD += 1;
1776                             first = a;
1777                             last = b;
1778                             limit = next;
1779                         } else {
1780                             stack[ssize++] = new StackEntry(isaD, first, a, limit);
1781                             first = b;
1782                         }
1783                     }
1784                 }
1785             } else {
1786                 if (!budget.update(size, last - first)) {
1787                     break; // BUGFIX : Added to prevent an infinite loop in the original code
1788                 }
1789                 limit += 1; isaD += 1;
1790             }
1791         }
1792 
1793         for (s = 0; s < ssize; ++s) {
1794             if (stack[s].d == -3) {
1795                 lsUpdateGroup(isa, stack[s].b, stack[s].c);
1796             }
1797         }
1798     }
1799 
1800     private static class TRBudget {
1801         int budget;
1802         int chance;
1803 
1804         TRBudget(final int budget, final int chance) {
1805             this.budget = budget;
1806             this.chance = chance;
1807         }
1808 
1809         boolean update(final int size, final int n) {
1810             budget -= n;
1811             if (budget <= 0) {
1812                 if (--chance == 0) {
1813                     return false;
1814                 }
1815                 budget += size;
1816             }
1817             return true;
1818         }
1819     }
1820 
1821     private void trSort(final int isa, final int n, final int depth) {
1822         final int[] SA = this.SA;
1823 
1824         int first = 0, last;
1825         int t;
1826 
1827         if (-n < SA[0]) {
1828             TRBudget budget = new TRBudget(n, trLog(n) * 2 / 3 + 1);
1829             do {
1830                 if ((t = SA[first]) < 0) {
1831                     first -= t;
1832                 } else {
1833                     last = SA[isa + t] + 1;
1834                     if (1 < last - first) {
1835                         trIntroSort(isa, isa + depth, isa + n, first, last, budget, n);
1836                         if (budget.chance == 0) {
1837                             /* Switch to Larsson-Sadakane sorting algorithm */
1838                             if (0 < first) {
1839                                 SA[0] = -first;
1840                             }
1841                             lsSort(isa, n, depth);
1842                             break;
1843                         }
1844                     }
1845                     first = last;
1846                 }
1847             } while (first < n);
1848         }
1849     }
1850 
1851     /*---------------------------------------------------------------------------*/
1852 
1853     private static int BUCKET_B(final int c0, final int c1) {
1854         return (c1 << 8) | c0;
1855     }
1856 
1857     private static int BUCKET_BSTAR(final int c0, final int c1) {
1858         return (c0 << 8) | c1;
1859     }
1860 
1861     private int sortTypeBstar(final int[] bucketA, final int[] bucketB) {
1862         final byte[] T = this.T;
1863         final int[] SA = this.SA;
1864         final int n = this.n;
1865         final int[] tempbuf = new int[256];
1866 
1867         int[] buf;
1868         int PAb, ISAb, bufoffset;
1869         int i, j, k, t, m, bufsize;
1870         int c0, c1;
1871         int flag;
1872 
1873         for (i = 1, flag = 1; i < n; ++i) {
1874             if (T[i - 1] != T[i]) {
1875                 if ((T[i - 1] & 0xff) > (T[i] & 0xff)) {
1876                     flag = 0;
1877                 }
1878                 break;
1879             }
1880         }
1881         i = n - 1;
1882         m = n;
1883 
1884         int ti, ti1, t0;
1885         if ((ti = T[i] & 0xff) < (t0 = T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
1886             if (flag == 0) {
1887                 ++bucketB[BUCKET_BSTAR(ti, t0)];
1888                 SA[--m] = i;
1889             } else {
1890                 ++bucketB[BUCKET_B(ti, t0)];
1891             }
1892             for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
1893                 ++bucketB[BUCKET_B(ti, ti1)];
1894             }
1895         }
1896 
1897         while (0 <= i) {
1898             do {
1899                 ++bucketA[T[i] & 0xff];
1900             } while (0 <= --i && (T[i] & 0xff) >= (T[i + 1] & 0xff));
1901             if (0 <= i) {
1902                 ++bucketB[BUCKET_BSTAR(T[i] & 0xff, T[i + 1] & 0xff)];
1903                 SA[--m] = i;
1904                 for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
1905                     ++bucketB[BUCKET_B(ti, ti1)];
1906                 }
1907             }
1908         }
1909         m = n - m;
1910         if (m == 0) {
1911             for (i = 0; i < n; ++i) {
1912                 SA[i] = i;
1913             }
1914             return 0;
1915         }
1916 
1917         for (c0 = 0, i = -1, j = 0; c0 < 256; ++c0) {
1918             t = i + bucketA[c0];
1919             bucketA[c0] = i + j;
1920             i = t + bucketB[BUCKET_B(c0, c0)];
1921             for (c1 = c0 + 1; c1 < 256; ++c1) {
1922                 j += bucketB[BUCKET_BSTAR(c0, c1)];
1923                 bucketB[(c0 << 8) | c1] = j;
1924                 i += bucketB[BUCKET_B(c0, c1)];
1925             }
1926         }
1927 
1928         PAb = n - m;
1929         ISAb = m;
1930         for (i = m - 2; 0 <= i; --i) {
1931             t = SA[PAb + i];
1932             c0 = T[t] & 0xff;
1933             c1 = T[t + 1] & 0xff;
1934             SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = i;
1935         }
1936         t = SA[PAb + m - 1];
1937         c0 = T[t] & 0xff;
1938         c1 = T[t + 1] & 0xff;
1939         SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = m - 1;
1940 
1941         buf = SA;
1942         bufoffset = m;
1943         bufsize = n - 2 * m;
1944         if (bufsize <= 256) {
1945             buf = tempbuf;
1946             bufoffset = 0;
1947             bufsize = 256;
1948         }
1949 
1950         for (c0 = 255, j = m; 0 < j; --c0) {
1951             for (c1 = 255; c0 < c1; j = i, --c1) {
1952                 i = bucketB[BUCKET_BSTAR(c0, c1)];
1953                 if (1 < j - i) {
1954                     subStringSort(PAb, i, j, buf, bufoffset, bufsize, 2, SA[i] == m - 1, n);
1955                 }
1956             }
1957         }
1958 
1959         for (i = m - 1; 0 <= i; --i) {
1960             if (0 <= SA[i]) {
1961                 j = i;
1962                 do {
1963                     SA[ISAb + SA[i]] = i;
1964                 } while (0 <= --i && 0 <= SA[i]);
1965                 SA[i + 1] = i - j;
1966                 if (i <= 0) {
1967                     break;
1968                 }
1969             }
1970             j = i;
1971             do {
1972                 SA[ISAb + (SA[i] = ~SA[i])] = j;
1973             } while (SA[--i] < 0);
1974             SA[ISAb + SA[i]] = j;
1975         }
1976 
1977         trSort(ISAb, m, 1);
1978 
1979         i = n - 1; j = m;
1980         if ((T[i] & 0xff) < (T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
1981             if (flag == 0) {
1982                 SA[SA[ISAb + --j]] = i;
1983             }
1984             for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
1985                 --i;
1986             }
1987         }
1988         while (0 <= i) {
1989             for (--i; 0 <= i && (T[i] & 0xff) >= (T[i + 1] & 0xff);) {
1990                 --i;
1991             }
1992             if (0 <= i) {
1993                 SA[SA[ISAb + --j]] = i;
1994                 for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
1995                     --i;
1996                 }
1997             }
1998         }
1999 
2000         for (c0 = 255, i = n - 1, k = m - 1; 0 <= c0; --c0) {
2001             for (c1 = 255; c0 < c1; --c1) {
2002                 t = i - bucketB[BUCKET_B(c0, c1)];
2003                 bucketB[BUCKET_B(c0, c1)] = i + 1;
2004 
2005                 for (i = t, j = bucketB[BUCKET_BSTAR(c0, c1)]; j <= k; --i, --k) {
2006                     SA[i] = SA[k];
2007                 }
2008             }
2009             t = i - bucketB[BUCKET_B(c0, c0)];
2010             bucketB[BUCKET_B(c0, c0)] = i + 1;
2011             if (c0 < 255) {
2012                 bucketB[BUCKET_BSTAR(c0, c0 + 1)] = t + 1;
2013             }
2014             i = bucketA[c0];
2015         }
2016         return m;
2017     }
2018 
2019     private int constructBWT(final int[] bucketA, final int[] bucketB) {
2020         final byte[] T = this.T;
2021         final int[] SA = this.SA;
2022         final int n = this.n;
2023 
2024         int i, j, t = 0;
2025         int s, s1;
2026         int c0, c1, c2 = 0;
2027         int orig = -1;
2028 
2029         for (c1 = 254; 0 <= c1; --c1) {
2030             for (i = bucketB[BUCKET_BSTAR(c1, c1 + 1)], j = bucketA[c1 + 1], t = 0, c2 = -1;
2031                     i <= j;
2032                     --j) {
2033                 if (0 <= (s1 = s = SA[j])) {
2034                     if (--s < 0) {
2035                         s = n - 1;
2036                     }
2037                     if ((c0 = T[s] & 0xff) <= c1) {
2038                         SA[j] = ~s1;
2039                         if (0 < s && (T[s - 1] & 0xff) > c0) {
2040                             s = ~s;
2041                         }
2042                         if (c2 == c0) {
2043                             SA[--t] = s;
2044                         } else {
2045                             if (0 <= c2) {
2046                                 bucketB[BUCKET_B(c2, c1)] = t;
2047                             }
2048                             SA[t = bucketB[BUCKET_B(c2 = c0, c1)] - 1] = s;
2049                         }
2050                     }
2051                 } else {
2052                     SA[j] = ~s;
2053                 }
2054             }
2055         }
2056 
2057         for (i = 0; i < n; ++i) {
2058             if (0 <= (s1 = s = SA[i])) {
2059                 if (--s < 0) {
2060                     s = n - 1;
2061                 }
2062                 if ((c0 = T[s] & 0xff) >= (T[s + 1] & 0xff)) {
2063                     if (0 < s && (T[s - 1] & 0xff) < c0) {
2064                         s = ~s;
2065                     }
2066                     if (c0 == c2) {
2067                         SA[++t] = s;
2068                     } else {
2069                         if (c2 != -1) {
2070                             bucketA[c2] = t;    // BUGFIX: Original code can write to bucketA[-1]
2071                         }
2072                         SA[t = bucketA[c2 = c0] + 1] = s;
2073                     }
2074                 }
2075             } else {
2076                 s1 = ~s1;
2077             }
2078 
2079             if (s1 == 0) {
2080                 SA[i] = T[n - 1];
2081                 orig = i;
2082             } else {
2083                 SA[i] = T[s1 - 1];
2084             }
2085         }
2086         return orig;
2087     }
2088 
2089     /**
2090      * Performs a Burrows Wheeler Transform on the input array.
2091      * @return the index of the first character of the input array within the output array
2092      */
2093     public int bwt() {
2094         final int[] SA = this.SA;
2095         final byte[] T = this.T;
2096         final int n = this.n;
2097 
2098         final int[] bucketA = new int[BUCKET_A_SIZE];
2099         final int[] bucketB = new int[BUCKET_B_SIZE];
2100 
2101         if (n == 0) {
2102             return 0;
2103         }
2104         if (n == 1) {
2105             SA[0] = T[0];
2106             return 0;
2107         }
2108 
2109         int m = sortTypeBstar(bucketA, bucketB);
2110         if (0 < m) {
2111             return constructBWT(bucketA, bucketB);
2112         }
2113         return 0;
2114     }
2115 }