Divsufsort RS

https://docs.rs/divsufsort-rs/0.6.0
Admin
Divsufsort RS is a Rust library that implements efficient suffix array construction and...
Tokens:43,155
Snippets:160
Trust Score:9.1
Update:6 months ago
Show doc for...
Tokens:
Raw
### divsufsort - Suffix Array Construction

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/divsufsort.rs.html

Constructs the suffix array of a given byte slice `t` in O(n) time using the induced-sorting algorithm. The resulting suffix array `sa` will contain the starting positions of the lexicographically sorted suffixes of `t`. It includes error handling for invalid input sizes.

```APIDOC
## POST /api/divsufsort

### Description
Constructs the suffix array of `t` in O(n) time using the induced-sorting algorithm.

On success, `sa[i]` holds the starting position of the `i`-th lexicographically smallest suffix of `t`.

### Method
POST

### Endpoint
/api/divsufsort

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
- **t** (bytes) - The input byte slice for which to construct the suffix array.
- **sa** (array of i32) - A mutable slice to store the resulting suffix array. Must have the same length as `t`.

### Request Example
```json
{
  "t": "banana",
  "sa": [0, 0, 0, 0, 0, 0]
}
```

### Response
#### Success Response (200)
- **sa** (array of i32) - The constructed suffix array.
- **primary_index** (usize) - The primary index needed for BWT inversion (if applicable).

#### Response Example
```json
{
  "sa": [5, 3, 1, 0, 4, 2],
  "primary_index": 3
}
```

### Errors
- **DivSufSortError::InvalidArgument**: If `sa.len() != t.len()`.
```

--------------------------------

### Function divsufsort

Source: https://docs.rs/divsufsort-rs/0.6.0/divsufsort_rs/fn.divsufsort.html

Constructs the suffix array of `t` in O(n) time using the induced-sorting algorithm. On success, `sa[i]` holds the starting position of the `i`-th lexicographically smallest suffix of `t`.

```APIDOC
## Function divsufsort

### Description
Constructs the suffix array of `t` in O(n) time using the induced-sorting algorithm. On success, `sa[i]` holds the starting position of the `i`-th lexicographically smallest suffix of `t`.

### Method
Rust Function

### Endpoint
N/A (Rust function)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
```rust
// Example usage would be within a Rust program
```

### Response
#### Success Response
Returns `Ok(())` on successful construction of the suffix array.

#### Error Response
- **DivSufSortError::InvalidArgument** - If `sa.len() != t.len()`.

#### Response Example
```rust
// Success:
Ok(())

// Error:
Err(DivSufSortError::InvalidArgument)
```
```

--------------------------------

### Search Pattern in Suffix Array

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/utils.rs.html

Searches for a pattern in the text using a precomputed suffix array. Returns the count of occurrences and the starting index.

```rust
pub fn sa_search(t: &[u8], p: &[u8], sa: &[i32]) -> (i32, i32) {
    let tsize = t.len() as i32;
    let psize = p.len() as i32;
    let sasize = sa.len() as i32;

    if sasize == 0 || tsize == 0 {
        return (0, -1);
    }
    if psize == 0 {
        return (sasize, 0);
    }

    let mut i = 0i32;
    let mut j = 0i32;
    let mut k = 0i32;
    let mut lmatch = 0i32;
    let mut rmatch = 0i32;
    let mut size = sasize;
```

--------------------------------

### Suffix Sorting Context and Entry Point

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Defines the context structure for B*-suffix sorting and the main entry point function for the sorting process.

```rust
pub struct SsortCtx<'a> {
    pub t: &'a [u8],
    pub pa: &'a [i32],
    pub pab: usize,
    pub depth: Depth,
    pub n: i32,
}
```

```rust
pub fn sssort(
    ctx: &SsortCtx,
    sa: &mut [i32],
    first: usize,
    last: usize,
    buf: usize,
    bufsize: i32,
    lastsuffix: bool,
) {
    let (t, pa, pab, depth, n) = (ctx.t, ctx.pa, ctx.pab, ctx.depth, ctx.n);
    let pa_slice = &pa[pab..];
    let mut first = first;
    if lastsuffix {
        first += 1;
    }

    let (middle, limit, bufsize, buf) =
        if (bufsize as usize) < SS_BLOCKSIZE && (bufsize as usize) < last - first {
            let limit = ss_isqrt((last - first) as i32);
            let limit = limit.min(SS_BLOCKSIZE as i32);
            let middle = last - limit as usize;
```

--------------------------------

### Suffix Comparison Function

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Compares two suffixes starting at given indices within potentially different slices. Used for sorting suffixes.

```rust
/// Corresponds to ss_compare in C.
/// p1 and p2 are separate slices (for lastsuffix, PAi and PA are different slices).
/// p1_idx and p2_idx are indices within their respective slices.
#[inline(always)]
fn ss_compare(t: &[u8], p1: &[i32], p1_idx: usize, p2: &[i32], p2_idx: usize, depth: Depth) -> i32 {
    let u1_start = (depth + p1[p1_idx]) as usize;
    let u2_start = (depth + p2[p2_idx]) as usize;
    let u1n = (p1[p1_idx + 1] + 2) as usize;
    let u2n = (p2[p2_idx + 1] + 2) as usize;

    let mut u1 = u1_start;
    let mut u2 = u2_start;

```

--------------------------------

### Structs

Source: https://docs.rs/divsufsort-rs/0.6.0/index.html

Information about the structs available in the divsufsort_rs crate.

```APIDOC
## Structs

### SufCheckError

Error returned by `sufcheck` when the suffix array is found to be invalid.
```

--------------------------------

### Suffix Array Partitioning and Stack Management

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Handles the logic for partitioning suffix array segments and pushing sub-problems onto a stack for iterative processing.

```rust
585                        break;
586                    }
587                    v = x;
588                    first = a;
589                }
590                a += 1;
591            }
592            let check_idx_hs = td_offset as i64 + pa_val(pa, pab, sa[first]) as i64 - 1;
593            if (t[check_idx_hs as usize] as i32) < v {
594                first = ss_partition(pa, pab, sa, first, a, depth);
595            }
596            if a - first <= last - a {
597                if a - first > 1 {
598                    stack.push(MiSortFrame {
599                        first: a,
600                        last,
601                        depth,
602                        limit: -1,
603                    });
604                    last = a;
605                    depth += 1;
606                    limit = ss_ilg((a - first) as i32);
607                } else {
608                    first = a;
609                    limit = -1;
610                }
611            } else if last - a > 1 {
612                stack.push(MiSortFrame {
613                    first,
614                    last: a,
615                    depth: depth + 1,
616                    limit: ss_ilg((a - first) as i32),
617                });
618                first = a;
619                limit = -1;
620            } else {
621                last = a;
622                depth += 1;
623                limit = ss_ilg((a - first) as i32);
624            }
625            continue;
626        }
627
628        let pivot_idx = ss_pivot_idx(&t[td_offset..], pa, pab, sa, first, last);
629        let v = t[td_offset + pa_val(pa, pab, sa[pivot_idx]) as usize] as i32;
630        sa.swap(first, pivot_idx);
631
632        if let Some((new_a, b2, new_c)) =
633            ss_three_way_partition(t, pa, pab, sa, first, last, depth, v)
634        {
635            // Push three sub-problems [first..new_a), [b2..new_c), [new_c..last)
636            // in size order (smallest processed next via loop vars, larger two on stack).
637            if new_a - first <= last - new_c {
638                if last - new_c <= new_c - b2 {
639                    stack.push(MiSortFrame {
640                        first: b2,
641                        last: new_c,
642                        depth: depth + 1,
643                        limit: ss_ilg((new_c - b2) as i32),
644                    });
645                    stack.push(MiSortFrame {
646                        first: new_c,
647                        last,
648                        depth,
649                        limit,
650                    });
651                    last = new_a;
652                } else if new_a - first <= new_c - b2 {
653                    stack.push(MiSortFrame {
654                        first: new_c,
655                        last,
656                        depth,
657                        limit,
658                    });
659                    stack.push(MiSortFrame {
660                        first: b2,
661                        last: new_c,
662                        depth: depth + 1,
663                        limit: ss_ilg((new_c - b2) as i32),
664                    });
665                    last = new_a;
666                } else {
667                    stack.push(MiSortFrame {
668                        first: new_c,
669                        last,
670                        depth,
671                        limit,
672                    });
673                    stack.push(MiSortFrame {
674                        first,
675                        last: new_a,
676                        depth,
677                        limit,
678                    });
679                    first = b2;
680                    last = new_c;
681                    depth += 1;
682                    limit = ss_ilg((new_c - b2) as i32);
683                }
684            } else if new_a - first <= new_c - b2 {
685                stack.push(MiSortFrame {
686                    first: b2,
687                    last: new_c,
688                    depth: depth + 1,
689                    limit: ss_ilg((new_c - b2) as i32),
690                });
691                stack.push(MiSortFrame {
692                    first,
693                    last: new_a,
694                    depth,
695                    limit,
696                });
697                first = new_c;
698            } else if last - new_c <= new_c - b2 {
699                stack.push(MiSortFrame {
700                    first,
701                    last: new_a,
702                    depth,
703                    limit,
704                });
705                stack.push(MiSortFrame {
706                    first: b2,
707                    last: new_c,
708                    depth: depth + 1,
709                    limit: ss_ilg((new_c - b2) as i32),
710                });
711                first = new_c;
712            } else {
713                stack.push(MiSortFrame {
714                    first,

```

--------------------------------

### Three-Way Partitioning for Suffix Arrays

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Performs a Bentley-McIlroy 3-way partition on a suffix array segment around a pivot value. Assumes the pivot is already at `sa[first]`.

```rust
fn ss_three_way_partition(
    t: &[u8],
    pa: &[i32],
    pab: usize,
    sa: &mut [i32],
    first: usize,
    last: usize,
    depth: Depth,
    v: i32,
) -> Option<(usize, usize, usize)> {
    let td_offset = depth as usize;
    let mut b = first + 1;
    let mut x = 0i32;
    while b < last {
        x = t[td_offset + pa_val(pa, pab, sa[b]) as usize] as i32;
        if x != v {
            break;
        }
        b += 1;
    }
    let mut a = b;
    if a < last && x < v {
        loop {
            b += 1;
            if b >= last {
                break;
            }
            x = t[td_offset + pa_val(pa, pab, sa[b]) as usize] as i32;
            if x > v {
                break;
            }
            if x == v {
                sa.swap(b, a);
                a += 1;
            }
        }
    }
    Some((first + 1, a, b))
}
```

--------------------------------

### Compare Suffixes with Depth

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Compares two suffixes starting at given positions in text `t` up to a specified `depth`. Handles negative group markers in `sa` by using `!sa[j]` as an index into `pa`.

```rust
fn ss_compare(t: &[u8], pa: &[i32], tv: usize, pa2: &[i32], sj: usize, depth: Depth) -> i32 {
    let mut u1 = tv;
    let mut u2 = sj;
    let u1n = t.len();
    let u2n = t.len();
    while u1 < u1n && u2 < u2n && t[u1] == t[u2] {
        u1 += 1;
        u2 += 1;
    }

    if u1 < u1n {
        if u2 < u2n {
            t[u1] as i32 - t[u2] as i32
        } else {
            1
        }
    } else if u2 < u2n {
        -1
    } else {
        0
    }
}
```

--------------------------------

### Functions

Source: https://docs.rs/divsufsort-rs/0.6.0/divsufsort_rs/all.html

Documentation for the functions available in the divsufsort-rs library.

```APIDOC
## Functions

### bw_transform

Performs the Burrows-Wheeler Transform on the input sequence.

### divbwt

Applies the DivSufSort algorithm with BWT.

### divsufsort

Computes the suffix array using the DivSufSort algorithm.

### inverse_bw_transform

Performs the inverse Burrows-Wheeler Transform.

### sa_search

Performs a search on the suffix array.

### sa_simplesearch

Performs a simple search on the suffix array.

### sufcheck

Checks the validity of a suffix array.
```

--------------------------------

### Suffix Sorting Utility Tests

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Unit tests for logarithmic and square root utility functions used in the sorting algorithm.

```rust
    #[test]
    fn test_ss_ilg() {
        assert_eq!(ss_ilg(1), 0);
        assert_eq!(ss_ilg(2), 1);
        assert_eq!(ss_ilg(4), 2);
        assert_eq!(ss_ilg(255), 7);
        assert_eq!(ss_ilg(256), 8);
        assert_eq!(ss_ilg(1024), 10);
    }
```

```rust
    #[test]
    fn test_ss_isqrt() {
        assert_eq!(ss_isqrt(0), 0);
        assert_eq!(ss_isqrt(1), 1);
        assert_eq!(ss_isqrt(4), 2);
        assert_eq!(ss_isqrt(9), 3);
        assert_eq!(ss_isqrt(16), 4);
        assert_eq!(ss_isqrt(100), 10);
        // boundary where x = y*y
        for y in 1..=32i32 {
            let x = y * y;
            assert_eq!(ss_isqrt(x), y, "ss_isqrt({x}) should be {y}");
            assert_eq!(
                ss_isqrt(x - 1),
                y - 1,
                "ss_isqrt({}) should be {}",
                x - 1,
                y - 1
            );
        }
    }
```

--------------------------------

### Enums

Source: https://docs.rs/divsufsort-rs/0.6.0/index.html

Information about the enums available in the divsufsort_rs crate.

```APIDOC
## Enums

### DivSufSortError

Errors returned by the public API of this crate.
```

--------------------------------

### Compare Suffixes

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/utils.rs.html

Compares a suffix of the text with a pattern, updating the match length.

```rust
fn compare(t: &[u8], p: &[u8], suf: i32, match_len: &mut i32) -> i32 {
    let tsize = t.len() as i32;
    let psize = p.len() as i32;
    let mut i = suf + *match_len;
    let mut j = *match_len;
    let mut r = 0i32;
    while i < tsize && j < psize {
        r = t[i as usize] as i32 - p[j as usize] as i32;
        if r != 0 {
            break;
        }
        i += 1;
        j += 1;
    }
    *match_len = j;
    if r == 0 {
        -(if j != psize { 1 } else { 0 })
    } else {
        r
    }
}
```

--------------------------------

### Test Heapsort Implementation

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Tests the `ss_heapsort` function with a sample byte string 'banana'. It verifies that the suffix array is correctly sorted by comparing adjacent suffix characters.

```rust
fn test_ss_heapsort() {
        let t = b"banana\x00";
        // PA = [5, 3, 1, 0, 4, 2] (suffix array of "banana")
        // SA values are indices into PA
        let pa = [5i32, 3, 1, 0, 4, 2, 0]; // extra 0 for sentinel
        let mut sa = [0i32, 1, 2, 3, 4, 5]; // indices to sort
        let td_offset = 0usize;
        let pab = 0usize; // pa is indexed directly (pab=0 means pa[0+i] = pa[i])
        ss_heapsort(&t[td_offset..], &pa, pab, &mut sa, 0, 6);
        // verify sorted by t[pa[pab + sa[i]]]
        for i in 1..6 {
            assert!(
                t[pa[sa[i - 1] as usize] as usize] <= t[pa[sa[i] as usize] as usize],
                "not sorted at {i}"
            );
        }
    }
```

--------------------------------

### Functions

Source: https://docs.rs/divsufsort-rs/0.6.0/index.html

Details on the functions provided by the divsufsort_rs crate for BWT and suffix array operations.

```APIDOC
## Functions

### bw_transform

Computes the Burrows-Wheeler Transform of `t`, writing the result into `u`.

### divbwt

Constructs the Burrows-Wheeler Transform (BWT) of `t` in O(n) time.

### divsufsort

Constructs the suffix array of `t` in O(n) time using the induced-sorting algorithm.

### inverse_bw_transform

Inverts the Burrows-Wheeler Transform.

### sa_search

Searches for pattern `p` in text `t` using the suffix array `sa`.

### sa_simplesearch

Searches for a single character `c` in text `t` using the suffix array `sa`.

### sufcheck

Verifies that `sa` is the correct suffix array of `t`.
```

--------------------------------

### Test Insertion Sort Implementation

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Tests the `ss_insertionsort_impl` function with the string 'dcba'. It verifies that the suffix array is sorted according to the `ss_compare` function, ensuring correct lexicographical ordering of suffixes.

```rust
fn test_ss_insertionsort_impl() {
        // T = "dcba____" (8 bytes)
        // PA = [3, 2, 1, 0, 0]: PA[i] = string position of i-th B* suffix
        //   PA[0]=3→'a', PA[1]=2→'b', PA[2]=1→'c', PA[3]=0→'d', PA[4]=0(sentinel)
        // SA values (0..3) are indices into PA; we sort by ss_compare
        // Initial SA = [3,2,1,0] (reverse order by key 'd','c','b','a')
        // Expected: after sort, adjacent pairs satisfy ss_compare <= 0
        let t = b"dcba\x00\x00\x00\x00";
        let pa = [3i32, 2, 1, 0, 0];
        let mut sa = [3i32, 2, 1, 0];
        ss_insertionsort_impl(t, &pa, &mut sa, 0, 4, 0);
        for i in 1..4 {
            let a = if sa[i - 1] >= 0 {
                sa[i - 1] as usize
            } else {
                !sa[i - 1] as usize
            };
            let b = if sa[i] >= 0 {
                sa[i] as usize
            } else {
                !sa[i] as usize
            };
            assert!(
                ss_compare(t, &pa, a, &pa, b, 0) <= 0,
                "not sorted at {i}: sa[{}]={} sa[{}]={}",
                i - 1,
                sa[i - 1],
                i,
                sa[i]
            );
        }
    }
```

--------------------------------

### Tandem Repeat Sorting Unit Tests

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/trsort.rs.html

Unit tests verifying logarithmic calculations, budget management, and basic sorting algorithm behavior.

```rust
#[test]
fn test_tr_ilg() {
    assert_eq!(tr_ilg(1), 0);
    assert_eq!(tr_ilg(2), 1);
    assert_eq!(tr_ilg(3), 1);
    assert_eq!(tr_ilg(4), 2);
    assert_eq!(tr_ilg(256), 8);
    assert_eq!(tr_ilg(255), 7);
}
```

```rust
#[test]
fn test_trbudget_check() {
    let mut b = TrBudget::new(2, 10);
    assert!(b.check(5));
    assert_eq!(b.remain, 5);
    assert!(b.check(5));
    assert_eq!(b.remain, 0);
    // remain=0, chance=2: should use a chance
    assert!(b.check(3));
    assert_eq!(b.chance, 1);
    assert_eq!(b.remain, 7);
    // exhaust chances
    assert!(b.check(20));
    assert_eq!(b.chance, 0);
    assert!(!b.check(1));
    assert_eq!(b.count, 1);
}
```

```rust
#[test]
fn test_tr_insertionsort_simple() {
    // ISAd = [3, 1, 4, 1, 5, 9, 2, 6]
    // SA = [0, 1, 2, 3, 4, 5, 6, 7] initially
    // after sort by ISAd values: order by ISAd[sa[i]]
    let isad = [3i32, 1, 4, 1, 5, 9, 2, 6];
    let mut sa = [1i32, 3, 0, 6, 2, 4, 7, 5];
    tr_insertionsort(&isad, &mut sa, 0, 8);
    // verify sorted by isad values (ignoring negative markers)
    for i in 1..sa.len() {
        let a = sa[i - 1];
        let b = sa[i];
        // negative values are duplicates of preceding
        if a >= 0 && b >= 0 {
            assert!(isad[a as usize] <= isad[b as usize]);
        }
    }
}
```

```rust
#[test]
fn test_tr_heapsort_simple() {
    let isad = [3i32, 1, 4, 1, 5, 9, 2, 6];
    let mut sa = [1i32, 3, 0, 6, 2, 4, 7, 5];
    tr_heapsort(&isad, &mut sa, 0, 8);
    for i in 1..sa.len() {
        assert!(isad[sa[i - 1] as usize] <= isad[sa[i] as usize]);
    }
}
```

--------------------------------

### Construct Suffix Array

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/divsufsort.rs.html

Constructs the suffix array of a byte slice in O(n) time using the induced-sorting algorithm. Returns an error if the suffix array buffer size does not match the input length.

```rust
pub fn divsufsort(t: &[u8], sa: &mut [i32]) -> Result<(), DivSufSortError> {
    let n = t.len();
    if sa.len() != n {
        return Err(DivSufSortError::InvalidArgument);
    }
    if n == 0 {
        return Ok(());
    }
    if n == 1 {
        sa[0] = 0;
        return Ok(());
    }
    if n == 2 {
        let m = (t[0] < t[1]) as usize;
        sa[m ^ 1] = 0;
        sa[m] = 1;
        return Ok(());
    }

    let mut bkt_a = vec![0i32; BUCKET_A_SIZE];
    let mut bkt_b = vec![0i32; BUCKET_B_SIZE];

    // Allocate one extra element so that sa[n] == 0 serves as a sentinel for ss_compare.
    // ss_compare reads pa[pab + k + 1] where k can be m-1 (the last B*-suffix index),
    // making the access pa[n] = sa[n].  The extra zero is never written by any algorithm
    // phase, so it remains 0 throughout.  The caller's sa[0..n] is copied back at the end.
    let mut sa_buf = vec![0i32; n + 1];
    let m = sort_typebstar(t, &mut sa_buf, &mut bkt_a, &mut bkt_b, n);
    construct_sa(t, &mut sa_buf, &mut bkt_a, &mut bkt_b, n, m);
    sa.copy_from_slice(&sa_buf[..n]);

    Ok(())
}
```

--------------------------------

### Three-Way Partitioning

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/trsort.rs.html

Partitions a range into three parts using a pivot value.

```rust
/// Partitions [first..last) into three parts using v as pivot; returns the equal-range as [*pa..*pb).
fn tr_partition(
    isad: &[i32],
    sa: &mut [i32],
    first: usize,
    middle: usize,
    last: usize,
    v: i32,
) -> (usize, usize) {
    let mut b = middle;
    let mut x = 0i32;
    while b < last {
        x = isad[sa[b] as usize];
        if x != v {
            break;
        }
        b += 1;
    }
    let mut a = b;
    if a < last && x < v {
        b += 1;
        while b < last {
            x = isad[sa[b] as usize];
            if x > v {
                break;
            }
            if x == v {
                sa.swap(b, a);
                a += 1;
            }
            b += 1;
        }
    }
    // Right scan: for(c = last; (b < --c) && ((x = ISAd[*c]) == v);)
    let mut c = last;
    loop {
        if c == 0 {
            break;
        }
        c -= 1;
        if c <= b {
            break;
        } // b < --c failed
        x = isad[sa[c] as usize];
        if x != v {
            break;
        }
    }
    // d = c  (C: if((b < (d = c)) && (x > v)))
    let mut d = c;
    if b < c && x > v {
        loop {
            if c == 0 {
                break;
            }
            c -= 1;
            if c <= b {
                break;
            }
            x = isad[sa[c] as usize];
            if x < v {
                break;
            }
            if x == v {
                sa.swap(c, d);
                d -= 1;
            } // C: SWAP(*c,*d); --d
        }
    }
    // Main loop: for(; b < c;)
    while b < c {
        sa.swap(b, c);
        // Inner left: for(; (++b < c) && ((x = ISAd[*b]) <= v);)
        loop {
            b += 1;
            if b >= c {
                break;
            }
            x = isad[sa[b] as usize];
            if x > v {
                break;
            }
            if x == v {
                sa.swap(b, a);
                a += 1;
            }
        }
```

--------------------------------

### Integer Logarithm (16-bit)

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Calculates the integer base-2 logarithm for 16-bit values using a precomputed lookup table. Efficient for bit manipulation.

```rust
/// Integer log2 for 16-bit values, using the lookup table.
fn ss_ilg(n: i32) -> i32 {
    if n & 0xff00 != 0 {
        8 + LG_TABLE[((n >> 8) & 0xff) as usize]
    } else {
        LG_TABLE[(n & 0xff) as usize]
    }
}
```

--------------------------------

### Inverse Suffix Array Construction

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/divsufsort.rs.html

Builds the inverse suffix array (ISA) from sorted B*-suffixes by processing group labels.

```rust
/// Builds the inverse suffix array (ISA) from sorted B*-suffixes.
/// Processes sa[0..m] and writes group labels into sa[isab..isab+m].
#[inline(always)]
fn build_isa_from_sorted_bstar(sa: &mut [i32], isab: usize, m: usize) {
    let mut i = m as isize - 1;
    while 0 <= i {
        if sa[i as usize] >= 0 {
            let j_val = i;
            loop {
                sa[isab + sa[i as usize] as usize] = i as i32;
                i -= 1;
                if i < 0 || sa[i as usize] < 0 {
                    break;
                }
            }
            sa[(i + 1) as usize] = (i - j_val) as i32;
            if i <= 0 {
                break;
            }
        }
        let j_val = i;
        loop {
            sa[i as usize] = !sa[i as usize];
            sa[isab + sa[i as usize] as usize] = j_val as i32;
            i -= 1;
            if i < 0 || sa[i as usize] >= 0 {
                break;
            }
        }
        if i >= 0 {
            sa[isab + sa[i as usize] as usize] = j_val as i32;
        }
        i -= 1;
    }
}
```

--------------------------------

### Suffix Array Construction

Source: https://docs.rs/divsufsort-rs/0.6.0/divsufsort_rs/index.html

Functions for constructing and verifying suffix arrays.

```APIDOC
## divsufsort

### Description
Constructs the suffix array of `t` in O(n) time using the induced-sorting algorithm.

## sufcheck

### Description
Verifies that `sa` is the correct suffix array of `t`.

### Parameters
- **t** (slice) - Input text
- **sa** (slice) - Suffix array to verify
```

--------------------------------

### Construct Suffix Array from Sorted B*-Suffixes (Reverse Scan)

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/divsufsort.rs.html

Constructs the full suffix array by scanning bucket boundaries left-to-right (A-type) and right-to-left (B-type). This function handles the core logic of inducing the suffix array based on character comparisons.

```rust
fn construct_sa(
    t: &[u8],
    sa: &mut [i32],
    bkt_a: &mut [i32],
    bkt_b: &mut [i32],
    n: usize,
    m: usize,
) {
    if m > 0 {
        for c1 in (0..=(ALPHABET_SIZE - 2)).rev() {
            let i_start = bucket_bstar(bkt_b, c1, c1 + 1) as usize;
            let j_end = bucket_a(bkt_a, c1 + 1) as usize;
            let mut k_idx: usize = 0;
            let mut c2: isize = -1;

            let mut j = j_end as isize - 1;
            while i_start as isize <= j {
                let s = sa[j as usize];
                if s > 0 {
                    let s = s as usize;
                    sa[j as usize] = !sa[j as usize];
                    let c0 = t[s - 1] as usize;
                    let s_val = if s > 1 && t[s - 2] as usize > c0 {
                        !((s - 1) as i32)
                    } else {
                        (s - 1) as i32
                    };
                    if c0 != c2 as usize {
                        if c2 >= 0 {
                            *bucket_b_mut(bkt_b, c2 as usize, c1) = k_idx as i32;
                        }
                        c2 = c0 as isize;
                        k_idx = bucket_b(bkt_b, c0, c1) as usize;
                    }
                    sa[k_idx] = s_val;
                    k_idx = k_idx.saturating_sub(1);
                } else {
                    sa[j as usize] = !s;
                }
                j -= 1;
            }
        }
    }

    let c2_init = t[n - 1] as usize;
    let mut k_idx = bucket_a(bkt_a, c2_init) as usize;
    sa[k_idx] = if (t[n - 2] as usize) < c2_init {
        !((n - 1) as i32)
    } else {
        (n - 1) as i32
    };
    k_idx += 1;
    let mut c2 = c2_init as isize;

    for i in 0..n {
        let s = sa[i];
        if s > 0 {
            let s = s as usize;
            let c0 = t[s - 1] as usize;
            let s_val = if s == 1 || (t[s - 2] as usize) < c0 {
                !((s - 1) as i32)
            } else {
                (s - 1) as i32
            };
            if c0 != c2 as usize {
                *bucket_a_mut(bkt_a, c2 as usize) = k_idx as i32;
                c2 = c0 as isize;
                k_idx = bucket_a(bkt_a, c0) as usize;
            }
            sa[k_idx] = s_val;
            k_idx += 1;
        } else {
            sa[i] = !s;
        }
    }
}
```

--------------------------------

### Ternary Quicksort Logic

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/trsort.rs.html

Handles the recursive sorting process, including insertion sort, heapsort, and partitioning logic.

```rust
792        if last - first <= TR_INSERTIONSORT_THRESHOLD {
793            tr_insertionsort(&isa[isad..], sa, first, last);
794            limit = -3;
795            continue;
796        }
797
798        limit -= 1;
799        if limit == -1 {
800            // limit was 0, now -1 after decrement → use heapsort
801            // restore: C does `if(limit-- == 0)` so heapsort when original limit==0
802            tr_heapsort(&isa[isad..], sa, first, last - first);
803            // after heapsort, mark duplicates
804            let mut a = last - 1;
805            while a > first {
806                let x = isa[isad + sa[a] as usize];
807                let mut b = a;
808                loop {
809                    if b <= first || sa[b - 1] < 0 || isa[isad + sa[b - 1] as usize] != x {
810                        break;
811                    }
812                    b -= 1;
813                    sa[b] = !sa[b];
814                }
815                if b == first {
816                    break;
817                }
818                a = b - 1;
819            }
820            limit = -3;
821            continue;
822        }
823
824        let pivot_idx = tr_pivot_idx(&isa[isad..], sa, first, last);
825        sa.swap(first, pivot_idx);
826        let v = isa[isad + sa[first] as usize];
827
828        // SAFETY: Same aliasing argument as the isad_tandem case above: tr_partition reads from
829        // isad_slice (= isa[isad..]) and swaps within sa; isa and sa are disjoint.
830        // After tr_partition returns the slice is no longer live, so the subsequent reads
831        // and writes to isa are safe with no aliased reference outstanding.
832        let isad_slice: &[i32] =
833            unsafe { core::slice::from_raw_parts(isa.as_ptr().add(isad), isa.len() - isad) };
834        let (a, b) = tr_partition_owned(isad_slice, sa, first, first + 1, last, v);
835
836        if last - first != b - a {
837            let next = if isa[sa[a] as usize] != v {
838                tr_ilg((b - a) as i32)
839            } else {
840                -1
841            };
842
843            let v2 = (a as i32) - 1;
844            for k in first..a {
845                isa[sa[k] as usize] = v2;
846            }
847            if b < last {
848                let v3 = (b as i32) - 1;
849                for k in a..b {
850                    isa[sa[k] as usize] = v3;
851                }
852            }
853
854            if b - a > 1 && budget.check((b - a) as i32) {
855                let mut state = TrSortState {
856                    isad: &mut isad,
857                    first: &mut first,
858                    last: &mut last,
859                    limit: &mut limit,
860                    trlink: &mut trlink,
861                };
862                push5_and_continue(&mut stack, &mut state, incr, a, b, next);
863            } else {
864                if b - a > 1 && trlink >= 0 {
865                    stack[trlink as usize].limit = -1;
866                }
867                if a - first <= last - b {
868                    if a - first > 1 {
869                        stack.push(TrFrame {
870                            isad,
871                            first: b,
872                            last,
873                            limit,
874                            trlink,
875                        });
876                        last = a;
877                    } else if last - b > 1 {
878                        first = b;
879                    } else if let Some(f) = stack.pop() {
880                        isad = f.isad;
881                        first = f.first;
882                        last = f.last;
883                        limit = f.limit;
884                        trlink = f.trlink;
885                    } else {
886                        return;
887                    }
888                } else if last - b > 1 {
889                    stack.push(TrFrame {
890                        isad,
891                        first,
892                        last: a,
893                        limit,
894                        trlink,
895                    });
896                    first = b;
897                } else if a - first > 1 {
898                    last = a;
899                } else if let Some(f) = stack.pop() {
900                    isad = f.isad;
901                    first = f.first;
902                    last = f.last;
903                    limit = f.limit;
904                    trlink = f.trlink;
905                } else {
906                    return;
907                }
908            }
909        } else if budget.check((last - first) as i32) {
910            limit = tr_ilg((last - first) as i32);
911            isad += incr;
912        } else {
913            if trlink >= 0 {
914                stack[trlink as usize].limit = -1;
915            }
916            if let Some(f) = stack.pop() {
917                isad = f.isad;
918                first = f.first;
```

--------------------------------

### Suffix Comparison Tests

Source: https://docs.rs/divsufsort-rs/0.6.0/src/divsufsort_rs/sssort.rs.html

Unit tests verifying the comparison logic for suffixes, including equality and less-than scenarios.

```rust
    #[test]
    fn test_ss_compare_equal() {
        // T = "abab", PA = [0, 2] (next B*-suffix after 0 is at 2)
        // depth=0, p1=0 (PA[0]=0), p2=0 (PA[0]=0) → equal → 0
        let t = b"abab";
        let pa = [0i32, 2];
        assert_eq!(ss_compare(t, &pa, 0, &pa, 0, 0), 0);
    }
```

```rust
    #[test]
    fn test_ss_compare_less() {
        // T = "ba", PA = [1, 0] → depth=0
        // p1_idx=0: PA[0]=1, PA[1]=0 → U1=T[0+1]='a', U1n=T[0+2]=out of bound→2
        // p2_idx=1: PA[1]=0, PA[2] is out of range... extend PA
        let _t = b"bab\x00"; // sentinel (unused; t2 below is used)
        let pa = [1i32, 0, 3]; // PA[0]=1, PA[1]=0, PA[2]=3(sentinel)
        // p1: U1=T[depth+PA[0]]=T[0+1]='a', U1n=T[PA[1]+2]=T[2]='b'
        // p2: U2=T[depth+PA[1]]=T[0+0]='b', U2n=T[PA[2]+2]=T[5] (out of bounds in t)
        // 比較: 'a' vs 'b' → 'a' < 'b' → -1
        // Adjust: need t to be long enough
        let t2 = b"bab\x00\x00\x00";
        let r = ss_compare(t2, &pa, 0, &pa, 1, 0);
        assert!(r < 0, "expected < 0 but got {r}");
    }
```
Tokens:
Raw