#### Bzip2 Implementation
#### Copyright (C) 2023-2024 Remilia Scarlet
#### Copyright (C) 2015 Jaime Olivares
#### Copyright (c) 2011 Matthew Francis
#### Copyright (c) 2003-2008 Yuta Mori
#### MIT License
####
#### Ported from the Java implementation by Matthew Francis:
#### https://github.com/MateuszBartosiewicz/bzip2.
####
#### Ported by Remilia Scarlet from the C# implementation by Jamie Olivares:
#### http://github.com/jaime-olivares/bzip2
####
#### Burrows-Wheeler Transform/Suffix Sorting
####
#### Remi: TODO Clean this code up. There are a LOT of while loops that need to be
#### converted to #times, #downto, etc., no comments, and bad variable names.
####
module RemiLib::Compression::BZip2
private class DivSufSort
###
### DivSufSort suffix array generator
### Based on libdivsufsort 1.2.3 patched to support BZip2
###
### This is a port of the C# version, which is a port of the Java version,
### which is a simple conversion of the original C with two minor bugfixes
### applied (see "BUGFIX" comments within the class). Documentation within
### the original code was largely absent.
###
STACK_SIZE = 64
BUCKET_A_SIZE = 256
BUCKET_B_SIZE = 65536
SS_BLOCK_SIZE = 1024
INSERTION_SORT_THRESHOLD = 8
LOG2TABLE = [
-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,
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,
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,
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,
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,
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,
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,
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
]
############################################################################
private class StackEntry
property a : Int32 = 0
property b : Int32 = 0
property c : Int32 = 0
property d : Int32 = 0
def initialize
end
@[AlwaysInline]
def set(@a : Int32, @b : Int32, @c : Int32, @d : Int32) : Nil
end
@[AlwaysInline]
def reset : Nil
@a = 0
@b = 0
@c = 0
@d = 0
end
end
alias Stack = Array(StackEntry)
############################################################################
private struct PartitionResult
getter first : Int32
getter last : Int32
def initialize(@first : Int32, @last : Int32)
end
end
############################################################################
private class TRBudget
@budget : Int32
property chance : Int32
def initialize(@budget : Int32, @chance : Int32)
end
@[AlwaysInline]
def update(size : Int, n : Int) : Bool
@budget -= n
if @budget <= 0
@chance -= 1
return false if @chance == 0
@budget += size
end
true
end
end
############################################################################
@stack : Stack
@ssize : UInt8 = 0u8
@sa : Array(Int32)
@t : Bytes
@n : Int32
# Creates a new `DivSufSort` instance. `t` The input array, `sa` is the
# output array, and `n` is the length of the input data.
def initialize(@t : Bytes, @sa : Array(Int32), @n : Int32, @int32Pool : ArrayPool(Int32))
@stack = Stack.new(STACK_SIZE) { |_| StackEntry.new }
end
@[AlwaysInline]
private def makeStack : Nil
@stack.each &.reset
@ssize = 0u8
end
@[AlwaysInline]
private def pushStack(a : Int32, b : Int32, c : Int32, d : Int32) : Nil
@stack[@ssize].set(a, b, c, d)
@ssize += 1
end
@[AlwaysInline]
private def popStack : StackEntry
@ssize -= 1
@stack[@ssize]
end
@[AlwaysInline]
private def stackEmpty? : Bool
@ssize == 0
end
# Performs a Burrows Wheeler Transform on the input array. Returns the
# index of the first character of the input array within the output array.
def bwt : Int32
case @n
when 0
return 0
when 1
@sa[0] = @t[0].to_i32!
return 0
end
@int32Pool.withRentedArray(BUCKET_A_SIZE) do |bucketA|
@int32Pool.withRentedArray(BUCKET_B_SIZE) do |bucketB|
bucketA.fill(0)
bucketB.fill(0)
m = sortTypeBstar(bucketA, bucketB)
if 0 < m
constructBWT(bucketA, bucketB)
else
0
end
end
end
end
@[AlwaysInline]
private def swap(arr1 : Array, idx1 : Int, arr2 : Array, idx2 : Int) : Nil
tmp = arr1[idx1]
arr1[idx1] = arr2[idx2]
arr2[idx2] = tmp
end
private def ssCompare(p1 : Int32, p2 : Int32, depth : Int32) : Int32
u1n : Int32 = @sa[p1 + 1] + 2
u2n : Int32 = @sa[p2 + 1] + 2
u1 : Int32 = depth + @sa[p1]
u2 : Int32 = depth + @sa[p2]
while u1 < u1n && u2 < u2n && @t[u1] == @t[u2]
u1 += 1
u2 += 1
end
if u1 < u1n
if u2 < u2n
@t[u1].to_i32! - @t[u2].to_i32!
else
1
end
elsif u2 < u2n
-1
else
0
end
end
private def ssCompareLast(pa : Int32, p1 : Int32, p2 : Int32, depth : Int32, size : Int32) : Int32
u1 : Int32 = depth + @sa[p1]
u2 : Int32 = depth + @sa[p2]
u1n : Int32 = size
u2n : Int32 = @sa[p2 + 1] + 2
while u1 < u1n && u2 < u2n && @t[u1] == @t[u2]
u1 += 1
u2 += 1
end
if u1 < u1n
if u2 < u2n
return @t[u1].to_i32! - @t[u2].to_i32!
else
return 1
end
end
return 1 if u2 == u2n
u1 = u1 % size
u1n = @sa[pa] + 2
while u1 < u1n && u2 < u2n && @t[u1] == @t[u2]
u1 += 1
u2 += 1
end
if u1 < u1n
if u2 < u2n
@t[u1].to_i32! - @t[u2].to_i32!
else
1
end
elsif u2 < u2n
-1
else
0
end
end
private def ssInsertionSort(pa : Int32, first : Int32, last : Int32, depth : Int32) : Nil
i : Int32 = last - 2
j : Int32 = 0
t : Int32 = 0
r : Int32 = 0
while first <= i
j = i + 1
t = @sa[i]
while 0 < (r = ssCompare(pa + t, pa + @sa[j], depth))
loop do
@sa[j - 1] = @sa[j]
break unless (j += 1) < last && @sa[j] < 0
end
break if last <= j
end
@sa[j] = ~(@sa[j]) if r == 0
@sa[j - 1] = t
i -= 1
end
end
private def ssFixdown(td : Int32, pa : Int32, sa : Int32, i : Int32, size : Int32) : Nil
v : Int32 = @sa[sa + i]
c : Int32 = @t[td + @sa[pa + v]].to_i32!
j : Int32 = 0
k : Int32 = 0
d : Int32 = 0
e : Int32 = 0
while (j = 2 * i + 1) < size
d = @t[td + @sa[pa + @sa[sa + (k = j)]]].to_i32!
j += 1
if d < (e = @t[td + @sa[pa + @sa[sa + j]]].to_i32!)
k = j
d = e
end
break if d <= c
@sa[sa + i] = @sa[sa + k]
i = k
end
@sa[sa + i] = v
end
private def ssHeapSort(td : Int32, pa : Int32, sa : Int32, size : Int32) : Nil
m : Int32 = size
if size % 2 == 0
m -= 1
if @t[td + @sa[pa + @sa[sa + m.tdiv(2)]]] < @t[td + @sa[pa + @sa[sa + m]]]
swap(@sa, sa + m, @sa, sa + m.tdiv(2))
end
end
(m.tdiv(2) - 1).downto(0) do |i|
ssFixdown(td, pa, sa, i, m)
end
if size % 2 == 0
swap(@sa, sa, @sa, sa + m)
ssFixdown(td, pa, sa, 0, m)
end
t : Int32 = 0
(m - 1).downto(1) do |i|
t = @sa[sa]
@sa[sa] = @sa[sa + i]
ssFixdown(td, pa, sa, 0, i)
@sa[sa + i] = t
end
end
@[AlwaysInline]
private def ssMedian3(td : Int32, pa : Int32, v1 : Int32, v2 : Int32, v3 : Int32) : Int32
tv1 : Int32 = @t[td + @sa[pa + @sa[v1]]].to_i32!
tv2 : Int32 = @t[td + @sa[pa + @sa[v2]]].to_i32!
tv3 : Int32 = @t[td + @sa[pa + @sa[v3]]].to_i32!
if tv1 > tv2
tmp = v1
v1 = v2
v2 = tmp
tmp = tv1
tv1 = tv2
tv2 = tmp
end
if tv2 > tv3
if tv1 > tv3
v1
else
v3
end
else
v2
end
end
private def ssMedian5(td : Int32, pa : Int32, v1 : Int32, v2 : Int32, v3 : Int32, v4 : Int32, v5 : Int32) : Int32
tv1 : Int32 = @t[td + @sa[pa + @sa[v1]]].to_i32!
tv2 : Int32 = @t[td + @sa[pa + @sa[v2]]].to_i32!
tv3 : Int32 = @t[td + @sa[pa + @sa[v3]]].to_i32!
tv4 : Int32 = @t[td + @sa[pa + @sa[v4]]].to_i32!
tv5 : Int32 = @t[td + @sa[pa + @sa[v5]]].to_i32!
temp : Int32 = 0
tvtemp : Int32 = 0
if tv2 > tv3
temp = v2
v2 = v3
v3 = temp
tvtemp = tv2
tv2 = tv3
tv3 = tvtemp
end
if tv4 > tv5
temp = v4
v4 = v5
v5 = temp
tvtemp = tv4
tv4 = tv5
tv5 = tvtemp
end
if tv2 > tv4
temp = v2
#v2 = v4
v4 = temp
tvtemp = tv2
tv2 = tv4
tv4 = tvtemp
temp = v3
v3 = v5
v5 = temp
tvtemp = tv3
tv3 = tv5
tv5 = tvtemp
end
if tv1 > tv3
temp = v1
v1 = v3
v3 = temp
tvtemp = tv1
tv1 = tv3
tv3 = tvtemp
end
if tv1 > tv4
temp = v1
#v1 = v4
v4 = temp
tvtemp = tv1
tv1 = tv4
tv4 = tvtemp
temp = v3
v3 = v5
#v5 = temp
tvtemp = tv3
tv3 = tv5
tv5 = tvtemp
end
tv3 > tv4 ? v4 : v3
end
private def ssPivot(td : Int32, pa : Int32, first : Int32, last : Int32) : Int32
t : Int32 = last - first
middle : Int32 = first + t.tdiv(2)
if t <= 512
if t <= 32
return ssMedian3(td, pa, first, middle, last - 1)
end
t >>= 2
return ssMedian5(td, pa, first, first + t, middle, last - 1 - t, last - 1)
end
t >>= 3
ssMedian3(td, pa,
ssMedian3(td, pa, first, first + t, first + (t << 1)),
ssMedian3(td, pa, middle - t, middle, middle + t),
ssMedian3(td, pa, last - 1 - (t << 1), last - 1 - t, last - 1))
end
@[AlwaysInline]
private def ssLog(x : Int32) : Int32
if (x & 0xff00) != 0
8 + LOG2TABLE[(x >> 8) & 0xff]
else
LOG2TABLE[x & 0xff]
end
end
private def ssSubstringPartition(pa : Int32, first : Int32, last : Int32, depth : Int32) : Int32
a : Int32 = first - 1
b : Int32 = last
t : Int32 = 0
loop do
while (a += 1) < b && ((@sa[pa + @sa[a]] + depth) >= (@sa[pa + @sa[a] + 1] + 1))
@sa[a] = ~(@sa[a])
end
while a < (b -= 1) && ((@sa[pa + @sa[b]] + depth) < (@sa[pa + @sa[b] + 1] + 1))
end
break if b <= a
t = ~(@sa[b])
@sa[b] = @sa[a]
@sa[a] = t
end
@sa[first] = ~(@sa[first]) if first < a
a
end
private def ssMultiKeyIntroSort(pa : Int32, first : Int32, last : Int32, depth : Int32) : Nil
makeStack
x : Int32 = 0
td : Int32 = 0
a : Int32 = 0
v : Int32 = 0
b : Int32 = 0
c : Int32 = 0
d : Int32 = 0
s : Int32 = 0
t : Int32 = 0
e : Int32 = 0
limit : Int32 = ssLog(last - first)
loop do
if last - first <= INSERTION_SORT_THRESHOLD
ssInsertionSort(pa, first, last, depth) if 1 < last - first
return if stackEmpty?
entry : StackEntry = popStack
first = entry.a
last = entry.b
depth = entry.c
limit = entry.d
next
end
td = depth
if limit == 0
ssHeapSort(td, pa, first, last - first)
end
limit -= 1
if limit < 0
a = first + 1
v = @t[td + @sa[pa + @sa[first]]].to_i32!
while a < last
if (x = @t[td + @sa[pa + @sa[a]]].to_i32!) != v
break if 1 < a - first
v = x
first = a
end
a += 1
end
if @t[td + @sa[pa + @sa[first]] - 1] < v
first = ssSubstringPartition(pa, first, a, depth)
end
if a - first <= last - a
if 1 < a - first
pushStack(a, last, depth, -1)
last = a
depth += 1
limit = ssLog(a - first)
else
first = a
limit = -1
end
else
if 1 < last - a
pushStack(first, a, depth + 1, ssLog(a - first))
first = a
limit = -1
else
last = a
depth += 1
limit = ssLog(a - first)
end
end
next
end # if limit < 0
a = ssPivot(td, pa, first, last)
v = @t[td + @sa[pa + @sa[a]]].to_i32!
swap(@sa, first, @sa, a)
b = first
while (b += 1) < last && (x = @t[td + @sa[pa + @sa[b]]].to_i32!) == v
end
if (a = b) < last && x < v
while (b += 1) < last && (x = @t[td + @sa[pa + @sa[b]]].to_i32!) <= v
if x == v
swap(@sa, b, @sa, a)
a += 1
end
end
end
c = last
while b < (c -= 1) && (x = @t[td + @sa[pa + @sa[c]]].to_i32!) == v
end
if b < (d = c) && x > v
while b < (c -= 1) && (x = @t[td + @sa[pa + @sa[c]]].to_i32!) >= v
if x == v
swap(@sa, c, @sa, d)
d -= 1
end
end
end
while b < c
swap(@sa, b, @sa, c)
while (b += 1) < c && (x = @t[td + @sa[pa + @sa[b]]].to_i32!) <= v
if x == v
swap(@sa, b, @sa, a)
a += 1
end
end
while b < (c -= 1) && (x = @t[td + @sa[pa + @sa[c]]].to_i32!) >= v
if x == v
swap(@sa, c, @sa, d)
d -= 1
end
end
end
if a <= d
c = b - 1
if (s = a - first) > (t = b - a)
s = t
end
e = first
f = b - s
while 0 < s
swap(@sa, e, @sa, f)
s -= 1
e += 1
f += 1
end
if (s = d - c) > (t = last - d - 1)
s = t
end
e = b
f = last - s
while 0 < s
swap(@sa, e, @sa, f)
s -= 1
e += 1
f += 1
end
a = first + (b - a)
c = last - (d - c)
b = if v <= @t[td + @sa[pa + @sa[a]] - 1]
a
else
ssSubstringPartition(pa, a, c, depth)
end
if a - first <= last - c
if last - c <= c - b
pushStack(b, c, depth + 1, ssLog(c - b))
pushStack(c, last, depth, limit)
last = a
elsif a - first <= c - b
pushStack(c, last, depth, limit)
pushStack(b, c, depth + 1, ssLog(c - b))
last = a
else
pushStack(c, last, depth, limit)
pushStack(first, a, depth, limit)
first = b
last = c
depth += 1
limit = ssLog(c - b)
end
else
if a - first <= c - b
pushStack(b, c, depth + 1, ssLog(c - b))
pushStack(first, a, depth, limit)
first = c
elsif last - c <= c - b
pushStack(first, a, depth, limit)
pushStack(b, c, depth + 1, ssLog(c - b))
first = c
else
pushStack(first, a, depth, limit)
pushStack(c, last, depth, limit)
first = b
last = c
depth += 1
limit = ssLog(c - b)
end
end # if a - first < last - c
else # if a <= d
limit += 1
if @t[td + @sa[pa + @sa[first]] - 1] < v
first = ssSubstringPartition(pa, first, last, depth)
limit = ssLog(last - first)
end
depth += 1
end
end
end
private def ssBlockSwap(arr1 : Array, first1 : Int32, arr2 : Array, first2 : Int32, size : Int32) : Nil
a : Int32 = first1
b : Int32 = first2
i : Int32 = size
while 0 < i
swap(arr1, a, arr2, b)
i -= 1
a += 1
b += 1
end
end
private def ssMergeForward(pa : Int32, buf : Array(Int32), bufOffset : Int32, first : Int32, middle : Int32,
last : Int32, depth : Int32) : Nil
bufEnd : Int32 = bufOffset + (middle - last) - 1
ssBlockSwap(buf, bufOffset, @sa, first, middle - first)
t : Int32 = @sa[first]
i : Int32 = first
j : Int32 = bufOffset
k : Int32 = middle
r : Int32 = 0
loop do
r = ssCompare(pa + buf[j], pa + @sa[k], depth)
if r < 0
loop do
@sa[i] = buf[j]
i += 1
if bufEnd <= j
buf[j] = t
return
end
buf[j] = @sa[i]
j += 1
break unless buf[j] < 0
end
elsif r > 0
loop do
@sa[i] = @sa[k]
i += 1
@sa[k] = @sa[i]
k += 1
if last <= k
while j < bufEnd
@sa[i] = buf[j]
i += 1
buf[j] = @sa[i]
j += 1
end
@sa[i] = buf[j]
buf[j] = t
return
end
break unless @sa[k] < 0
end
else
@sa[k] = ~(@sa[k])
loop do
@sa[i] = buf[j]
i += 1
if bufEnd <= j
buf[j] = t
return
end
buf[j] = @sa[i]
j += 1
break unless buf[j] < 0
end
loop do
@sa[i] = @sa[k]
i += 1
@sa[k] = @sa[i]
k += 1
if last <= k
while j < bufEnd
@sa[i] = buf[j]
i += 1
buf[j] = @sa[i]
j += 1
end
@sa[i] = buf[j]
buf[j] = t
return
end
break unless @sa[k] < 0
end
end
end
end
private def ssMergeBackward(pa : Int32, buf : Array(Int32), bufOffset : Int32, first : Int32, middle : Int32,
last : Int32, depth : Int32) : Nil
bufEnd : Int32 = bufOffset + (last - middle)
ssBlockSwap(buf, bufOffset, @sa, middle, last - middle)
p1 : Int32 = 0
p2 : Int32 = 0
x : Int32 = 0
if buf[bufEnd - 1] < 0
x |= 1
p1 = pa + ~(buf[bufEnd - 1])
else
p1 = pa + buf[bufEnd - 1]
end
if @sa[middle - 1] < 0
x |= 2
p2 = pa + ~(@sa[middle - 1])
else
p2 = pa + @sa[middle - 1]
end
t : Int32 = @sa[last - 1]
i : Int32 = last - 1
j : Int32 = bufEnd - 1
k : Int32 = middle - 1
r : Int32 = 0
loop do
r = ssCompare(p1, p2, depth)
if r > 0
if (x & 1) != 0
loop do
@sa[i] = buf[j]
i -= 1
buf[j] = @sa[i]
j -= 1
break unless buf[j] < 0
end
x ^= 1
end
@sa[i] = buf[j]
i -= 1
if j <= bufOffset
buf[j] = t
return
end
buf[j] = @sa[i]
j -= 1
if buf[j] < 0
x |= 1
p1 = pa + ~(buf[j])
else
p1 = pa + buf[j]
end
elsif r < 0
if (x & 2) != 0
loop do
@sa[i] = @sa[k]
i -= 1
@sa[k] = @sa[i]
k -= 1
break unless @sa[k] < 0
end
x ^= 2
end
@sa[i] = @sa[k]
i -= 1
@sa[k] = @sa[i]
k -= 1
if k < first
while bufOffset < j
@sa[i] = buf[j]
i -= 1
buf[j] = @sa[i]
j -= 1
end
@sa[i] = buf[j]
buf[j] = t
return
end
if @sa[k] < 0
x |= 2
p2 = pa + ~(@sa[k])
else
p2 = pa + @sa[k]
end
else
if (x & 1) != 0
loop do
@sa[i] = buf[j]
i -= 1
buf[j] = @sa[i]
j -= 1
break unless buf[j] < 0
end
x ^= 1
end
@sa[i] = ~(buf[j])
i -= 1
if j <= bufOffset
buf[j] = t
return
end
buf[j] = @sa[i]
j -= 1
if (x & 2) != 0
loop do
@sa[i] = @sa[k]
i -= 1
@sa[k] = @sa[i]
k -= 1
break unless @sa[k] < 0
end
x ^= 2
end
@sa[i] = @sa[k]
i -= 1
@sa[k] = @sa[i]
k -= 1
if k < first
while bufOffset < j
@sa[i] = buf[j]
i -= 1
buf[j] = @sa[i]
j -= 1
end
@sa[i] = buf[j]
buf[j] = t
return
end
if buf[j] < 0
x |= 1
p1 = pa + ~(buf[j])
else
p1 = pa + buf[j]
end
if @sa[k] < 0
x |= 2
p2 = pa + ~(@sa[k])
else
p2 = pa + @sa[k]
end
end
end
end
@[AlwaysInline]
protected def self.getIdx(a : Int32) : Int32
0 <= a ? a : ~a
end
@[AlwaysInline]
private def ssMergeCheckEqual(pa : Int32, depth : Int32, a : Int32) : Nil
if 0 <= @sa[a] && ssCompare(pa + DivSufSort.getIdx(@sa[a - 1]), pa + @sa[a], depth) == 0
@sa[a] = ~(@sa[a])
end
end
private def ssMerge(pa : Int32, first : Int32, middle : Int32, last : Int32, buf : Array(Int32),
bufOffset : Int32, bufSize : Int32, depth : Int32) : Nil
makeStack
check : Int32 = 0
m : Int32 = 0
len : Int32 = 0
half : Int32 = 0
j : Int32 = 0
i : Int32 = 0
nxt : Int32 = 0
loop do
if last - middle <= bufSize
if first < middle && middle < last
ssMergeBackward(pa, buf, bufOffset, first, middle, last, depth)
end
ssMergeCheckEqual(pa, depth, first) if (check & 1) != 0
ssMergeCheckEqual(pa, depth, last) if (check & 2) != 0
return if stackEmpty?
entry : StackEntry = popStack
first = entry.a
middle = entry.b
last = entry.c
check = entry.d
next
end
if middle - first <= bufSize
if first < middle
ssMergeForward(pa, buf, bufOffset, first, middle, last, depth)
end
ssMergeCheckEqual(pa, depth, first) if (check & 1) != 0
ssMergeCheckEqual(pa, depth, last) if (check & 2) != 0
return if stackEmpty?
entry = popStack
first = entry.a
middle = entry.b
last = entry.c
check = entry.d
next
end
m = 0
len = Math.min(middle - first, last - middle)
half = len >> 1
while 0 < len
if ssCompare(pa + DivSufSort.getIdx(@sa[middle + m + half]),
pa + DivSufSort.getIdx(@sa[middle - m - half - 1]),
depth) < 0
m += half + 1
half -= (len & 1) ^ 1
end
len = half
half >>= 1
end
if 0 < m
ssBlockSwap(@sa, middle - m, @sa, middle, m)
j = middle
i = middle
nxt = 0
if middle + m < last
if @sa[middle + m] < 0
while @sa[i - 1] < 0
i -= 1
end
@sa[middle + m] = ~(@sa[middle + m])
end
j = middle
while @sa[j] < 0
j += 1
end
nxt = 1
end
if i - first <= last - j
pushStack(j, middle + m, last, (check & 2) | (nxt & 1))
middle -= m
last = i
check = check & 1
else
nxt <<= 1 if i == middle && middle == j
pushStack(first, middle - m, i, (check & 1) | (nxt & 2))
first = j
middle += m
check = (check & 2) | (nxt & 1)
end
else # if 0 < m
ssMergeCheckEqual(pa, depth, first) if (check & 1) != 0
ssMergeCheckEqual(pa, depth, middle)
ssMergeCheckEqual(pa, depth, last) if (check & 2) != 0
return if stackEmpty?
entry = popStack
first = entry.a
middle = entry.b
last = entry.c
check = entry.d
end
end
end
private def subStringSort(pa : Int32, first : Int32, last : Int32, buf : Array(Int32),
bufOffset : Int32, bufSize : Int32, depth : Int32,
lastSuffix? : Bool, size : Int32) : Nil
a : Int32 = 0
i : Int32 = 0
k : Int32 = 0
curBufOffset : Int32 = 0
curBufSize : Int32 = 0
b : Int32 = 0
j : Int32 = 0
first += 1 if lastSuffix?
a = first
while (a + SS_BLOCK_SIZE) < last
ssMultiKeyIntroSort(pa, a, a + SS_BLOCK_SIZE, depth)
curBuf : Array(Int32) = @sa
curBufOffset = a + SS_BLOCK_SIZE
curBufSize = last - (a + SS_BLOCK_SIZE)
if curBufSize <= bufSize
curBufSize = bufSize
curBuf = buf
curBufOffset = bufOffset
end
b = a
k = SS_BLOCK_SIZE
j = i
while (j & 1) != 0
ssMerge(pa, b - k, b, b + k, curBuf, curBufOffset, curBufSize, depth)
b -= k
k <<= 1
j >>= 1
end
a += SS_BLOCK_SIZE
i += 1
end
ssMultiKeyIntroSort(pa, a, last, depth)
k = SS_BLOCK_SIZE
while i != 0
if (i & 1) != 0
ssMerge(pa, a - k, a, last, buf, bufOffset, bufSize, depth)
a -= k
end
k <<= 1
i >>= 1
end
if lastSuffix?
a = first
i = @sa[first - 1]
r : Int32 = 1
while a < last &&
(@sa.unsafe_fetch(a) < 0 || 0 < (r = ssCompareLast(pa, pa + i, pa + @sa.unsafe_fetch(a), depth, size)))
@sa.unsafe_put(a - 1, @sa.unsafe_fetch(a))
a += 1
end
@sa.unsafe_put(a, ~(@sa.unsafe_fetch(a))) if r == 0
@sa.unsafe_put(a - 1, i)
end
end
@[AlwaysInline]
private def trGetC(isa : Int32, isad : Int32, isan : Int32, x : Int32) : Int32
if isad + x < isan
@sa[isad + x]
else
@sa[isa + ((isad - isa + x) % (isan - isa))]
end
end
private def trFixdown(isa : Int32, isad : Int32, isan : Int32, sa : Int32, i : Int32, size : Int32) : Nil
j : Int32 = 0
k : Int32 = 0
v : Int32 = @sa[sa + i]
c : Int32 = trGetC(isa, isad, isan, v)
d : Int32 = 0
e : Int32 = 0
while (j = 2 * i + 1) < size
k = j
j += 1
d = trGetC(isa, isad, isan, @sa[sa + k])
if d < (e = trGetC(isa, isad, isan, @sa[sa + j]))
k = j
d = e
end
break if d <= c
@sa[sa + i] = @sa[sa + k]
i = k
end
@sa[sa + i] = v
end
private def trHeapSort(isa : Int32, isad : Int32, isan : Int32, sa : Int32, size : Int32) : Nil
m : Int32 = size
if size % 2 == 0
m -= 1
if trGetC(isa, isad, isan, @sa[sa + m.tdiv(2)]) < trGetC(isa, isad, isan, @sa[sa + m])
swap(@sa, sa + m, @sa, sa + m.tdiv(2))
end
end
(m.tdiv(2) - 1).downto(0) do |i|
trFixdown(isa, isad, isan, sa, i, m)
end
if size % 2 == 0
swap(@sa, sa, @sa, sa + m)
trFixdown(isa, isad, isan, sa, 0, m)
end
t : Int32 = 0
(m - 1).downto(1) do |i|
t = @sa[sa]
@sa[sa] = @sa[sa + i]
trFixdown(isa, isad, isan, sa, 0, i)
@sa[sa + i] = t
end
end
private def trInsertionSort(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32) : Nil
a : Int32 = first + 1
b : Int32 = 0
t : Int32 = 0
r : Int32 = 0
while a < last
t = @sa[a]
b = a - 1
r = 0
while 0 > (r = trGetC(isa, isad, isan, t) - trGetC(isa, isad, isan, @sa[b]))
loop do
@sa[b + 1] = @sa[b]
break unless first <= (b -= 1) && @sa[b] < 0
end
break if b < first
end
@sa[b] = ~(@sa[b]) if r == 0
@sa[b + 1] = t
a += 1
end
end
@[AlwaysInline]
private def trLog(x : Int32) : Int32
if (x & 0xFFFF0000) != 0
if (x & 0xFF000000) != 0
24 + LOG2TABLE[(x >> 24) & 0xFF]
else
16 + LOG2TABLE[(x >> 16) & 0xFF]
end
else
if(x & 0x0000FF00) != 0
8 + LOG2TABLE[(x >> 8) & 0xFF]
else
LOG2TABLE[x & 0xFF]
end
end
end
@[AlwaysInline]
private def trMedian3(isa : Int32, isad : Int32, isan : Int32, v1 : Int32, v2 : Int32, v3 : Int32) : Int32
sav1 : Int32 = trGetC(isa, isad, isan, @sa[v1])
sav2 : Int32 = trGetC(isa, isad, isan, @sa[v2])
sav3 : Int32 = trGetC(isa, isad, isan, @sa[v3])
if sav1 > sav2
temp : Int32 = v1
v1 = v2
v2 = temp
savtemp : Int32 = sav1
sav1 = sav2
sav2 = savtemp
end
if sav2 > sav3
sav1 > sav3 ? v1 : v3
else
v2
end
end
private def trMedian5(isa : Int32, isad : Int32, isan : Int32,
v1 : Int32, v2 : Int32, v3 : Int32, v4 : Int32, v5 : Int32) : Int32
sav1 : Int32 = trGetC(isa, isad, isan, @sa[v1])
sav2 : Int32 = trGetC(isa, isad, isan, @sa[v2])
sav3 : Int32 = trGetC(isa, isad, isan, @sa[v3])
sav4 : Int32 = trGetC(isa, isad, isan, @sa[v4])
sav5 : Int32 = trGetC(isa, isad, isan, @sa[v5])
temp : Int32 = 0
savtemp : Int32 = 0
if sav2 > sav3
temp = v2
v2 = v3
v3 = temp
savtemp = sav2
sav2 = sav3
sav3 = savtemp
end
if sav4 > sav5
temp = v4
v4 = v5
v5 = temp
savtemp = sav4
sav4 = sav5
sav5 = savtemp
end
if sav2 > sav4
temp = v2
#v2 = v4
v4 = temp
savtemp = sav2
sav2 = sav4
sav4 = savtemp
temp = v3
v3 = v5
v5 = temp
savtemp = sav3
sav3 = sav5
sav5 = savtemp
end
if sav1 > sav3
temp = v1
v1 = v3
v3 = temp
savtemp = sav1
sav1 = sav3
sav3 = savtemp
end
if sav1 > sav4
temp = v1
#v1 = v4
v4 = temp
savtemp = sav1
sav1 = sav4
sav4 = savtemp
temp = v3
v3 = v5
#v5 = temp
savtemp = sav3
sav3 = sav5
sav5 = savtemp
end
sav3 > sav4 ? v4 : v3
end
private def trPivot(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32) : Int32
t : Int32 = last - first
middle : Int32 = first + t.tdiv(2)
if t <= 512
if t <= 32
return trMedian3(isa, isad, isan, first, middle, last - 1)
end
t >>= 2
return trMedian5(isa, isad, isan, first, first + t, middle, last - 1 - t, last - 1)
end
t >>= 3
trMedian3(isa, isad, isan,
trMedian3(isa, isad, isan, first, first + t, first + (t << 1)),
trMedian3(isa, isad, isan, middle - t, middle, middle + t),
trMedian3(isa, isad, isan, last - 1 - (t << 1), last - 1 - t, last - 1))
end
private def lsUpdateGroup(isa : Int32, first : Int32, last : Int32) : Nil
b : Int32 = 0
t : Int32 = 0
(first...last).each do |a|
b = 0
if 0 <= @sa[a]
b = a
loop do
@sa[isa + @sa[a]] = a
break unless (a += 1) < last && 0 <= @sa[a]
end
@sa[b] = b - a
break if last <= a
end
b = a
loop do
@sa[a] = ~(@sa[a])
break unless @sa[a += 1] < 0
end
t = a
loop do
@sa[isa + @sa[b]] = t
break unless (b += 1) <= a
end
end
end
private def lsIntroSort(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32) : Nil
makeStack
x : Int32 = 0
a : Int32 = 0
b : Int32 = 0
v : Int32 = 0
c : Int32 = 0
d : Int32 = 0
s : Int32 = 0
t : Int32 = 0
e : Int32 = 0
f : Int32 = 0
limit : Int32 = trLog(last - first)
loop do
if last - first <= INSERTION_SORT_THRESHOLD
if 1 < last - first
trInsertionSort(isa, isad, isan, first, last)
lsUpdateGroup(isa, first, last)
elsif last - first == 1
@sa[first] = -1
end
return if stackEmpty?
entry : StackEntry = popStack
first = entry.a
last = entry.b
limit = entry.c
next
end
a = 0
b = 0
if limit == 0
limit -= 1
trHeapSort(isa, isad, isan, first, last - first)
a = last - 1
while first < a
x = trGetC(isa, isad, isan, @sa[a])
b = a - 1
while first <= b && trGetC(isa, isad, isan, @sa[b]) == x
@sa[b] = ~(@sa[b])
b -= 1
end
a = b
end
lsUpdateGroup(isa, first, last)
return if stackEmpty?
entry = popStack
first = entry.a
last = entry.b
limit = entry.c
next
else
limit -= 1
end
a = trPivot(isa, isad, isan, first, last)
swap(@sa, first, @sa, a)
v = trGetC(isa, isad, isan, @sa[first])
b = first
while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) == v
end
if (a = b) < last && x < v
while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) <= v
if x == v
swap(@sa, b, @sa, a)
a += 1
end
end
end
c = last
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) == v
end
if b < (d = c) && x > v
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
if x == v
swap(@sa, c, @sa, d)
d -= 1
end
end
end
while b < c
swap(@sa, b, @sa, c)
while (b += 1) < c && (c = trGetC(isa, isad, isan, @sa[b])) <= v
if x == v
swap(@sa, b, @sa, a)
a += 1
end
end
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
if x == v
swap(@sa, c, @sa, d)
d -= 1
end
end
end
if a <= d
c = b - 1
if (s = a - first) > (t = b - a)
s = t
end
e = first
f = b - s
while 0 < s
swap(@sa, e, @sa, f)
s -= 1
e += 1
f += 1
end
if (s = d - c) > (t = last - d - 1)
s = t
end
e = b
f = last - s
while 0 < s
swap(@sa, e, @sa, f)
s -= 1
e += 1
f += 1
end
a = first + (b - a)
b = last - (d - c)
c = first
v = a - 1
while c < a
@sa[isa + @sa[c]] = v
c +=1
end
if b < last
c = a
v = b - 1
while c < b
@sa[isa + @sa[c]] = v
c += 1
end
end
@sa[a] = -1 if (b - a) == 1
if a - first <= last - b
if first < a
pushStack(b, last, limit, 0)
last = a
else
first = b
end
else
if b < last
pushStack(first, a, limit, 0)
first = b
else
last = a
end
end
else # if a <= d
return if stackEmpty?
entry = popStack
first = entry.a
last = entry.b
limit = entry.c
end
end
end
private def lsSort(isa : Int32, x : Int32, depth : Int32) : Nil
isad : Int32 = isa + depth
first : Int32 = 0
skip : Int32 = 0
last : Int32 = 0
t : Int32 = 0
while -x < @sa[0]
first = 0
skip = 0
last = 0
t = 0
loop do
if (t = @sa[first]) < 0
first -= t
skip += t
else
if skip != 0
@sa[first + skip] = skip
skip = 0
end
last = @sa[isa + t] + 1
lsIntroSort(isa, isad, isa + x, first, last)
first = last
end
break unless first < x
end
@sa[first + skip] = skip if skip != 0
if x < (isad - isa)
first = 0
loop do
if (t = @sa[first]) < 0
first -= t
else
last = @sa[isa + t] + 1
(first...last).each do |i|
@sa[isa + @sa[i]] = i
end
first = last
end
break unless first < x
end
break
end
isad += (isad - isa)
end
end
private def trPartition(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32,
v : Int32) : PartitionResult
a : Int32 = 0
c : Int32 = 0
d : Int32 = 0
t : Int32 = 0
s : Int32 = 0
e : Int32 = 0
f : Int32 = 0
x : Int32 = 0
b : Int32 = first - 1
while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) == v
end
if (a = b) < last && x < v
while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) <= v
if x == v
swap(@sa, b, @sa, a)
a += 1
end
end
end
c = last
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) == v
end
if b < (d = c) && x > v
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
if x == v
swap(@sa, c, @sa, d)
d -= 1
end
end
end
while b < c
swap(@sa, b, @sa, c)
while (b += 1) < c && (x = trGetC(isa, isad, isan, @sa[b])) <= v
if x == v
swap(@sa, b, @sa, a)
a += 1
end
end
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
if x == v
swap(@sa, c, @sa, d)
d -= 1
end
end
end
if a <= d
c = b - 1
if (s = a - first) > (t = b - a)
s = t
end
e = first
f = b - s
while 0 < s
swap(@sa, e, @sa, f)
s -= 1
e += 1
f += 1
end
if (s = d - c) > (t = last - d - 1)
s = t
end
e = b
f = last - s
while 0 < s
swap(@sa, e, @sa, f)
s -=1
e += 1
f += 1
end
first += (b - a)
last -= (d - c)
end
PartitionResult.new(first, last)
end
private def trCopy(isa : Int32, isan : Int32, first : Int32, a : Int32, b : Int32,
last : Int32, depth : Int32) : Nil
c : Int32 = first
d : Int32 = a - 1
e : Int32 = 0
s : Int32 = 0
v : Int32 = b - 1
while c <= d
if (s = @sa[c] - depth) < 0
s += isan - isa
end
if @sa[isa + s] == v
d += 1
@sa[d] = s
@sa[isa + s] = d
end
c += 1
end
c = last - 1
e = d + 1
d = b
while e < d
if (s = @sa[c] - depth) < 0
s += isan - isa
end
if @sa[isa + s] == v
@sa[d -= 1] = s
@sa[isa + s] = d
end
c -= 1
end
end
private def trIntroSort(isa : Int32, isad : Int32, isan : Int32, first : Int32, last : Int32,
budget : TRBudget, size : Int32) : Nil
makeStack
s : Int32 = 0
x : Int32 = 0
a : Int32 = 0
b : Int32 = 0
c : Int32 = 0
v : Int32 = 0
d : Int32 = 0
t : Int32 = 0
e : Int32 = 0
f : Int32 = 0
nxt : Int32 = 0
limit : Int32 = trLog(last - first)
loop do
a = 0
b = 0
c = 0
v = 0
nxt = 0
if limit < 0
if limit == -1
break unless budget.update(size, last - first)
result : PartitionResult = trPartition(isa, isad - 1, isan, first, last, last - 1)
a = result.first
b = result.last
if first < a || b < last
if a < last
c = first
v = a - 1
while c < a
@sa[isa + @sa[c]] = v
c += 1
end
end
if b < last
c = a
v = b - 1
while c < b
@sa[isa + @sa[c]] = v
c += 1
end
end
pushStack(0, a, b, 0)
pushStack(isad - 1, first, last, -2)
if a - first <= last - b
if 1 < a - first
pushStack(isad, b, last, trLog(last - b))
last = a
limit = trLog(a - first)
elsif 1 < last - b
first = b
limit = trLog(last - b)
else
return if stackEmpty?
entry : StackEntry = popStack
isad = entry.a
first = entry.b
last = entry.c
limit = entry.d
end
else
if 1 < last - b
pushStack(isad, first, a, trLog(a - first))
first = b
limit = trLog(last - b)
elsif 1 < a - first
last = a
limit = trLog(a - first)
else
return if stackEmpty?
entry = popStack
isad = entry.a
first = entry.b
last = entry.c
limit = entry.d
end
end
else
c = first
while c < last
@sa[isa + @sa[c]] = c
c += 1
end
return if stackEmpty?
entry = popStack
isad = entry.a
first = entry.b
last = entry.c
limit = entry.d
end
elsif limit == -2 # if limit == -1
entry = popStack
a = entry.b
b = entry.c
trCopy(isa, isan, first, a, b, last, isad - isa)
return if stackEmpty?
entry = popStack
isad = entry.a
first = entry.b
last = entry.c
limit = entry.d
else
if 0 <= @sa[first]
a = first
loop do
@sa[isa + @sa[a]] = a
break unless (a += 1) < last && 0 <= @sa[a]
end
first = a
end
if first < last
a = first
loop do
@sa[a] = ~(@sa[a])
break unless @sa[a += 1] < 0
end
nxt = if @sa[isa + @sa[a]] != @sa[isad + @sa[a]]
trLog(a - first + 1)
else
-1
end
if (a += 1) < last
b = first
v = a - 1
while b < a
@sa[isa + @sa[b]] = v
b += 1
end
end
if a - first <= last - a
pushStack(isad, a, last, -3)
isad += 1
last = a
limit = nxt
else
if 1 < last - a
pushStack(isad + 1, first, a, nxt)
first = a
limit = -3
else
isad += 1
last = a
limit = nxt
end
end
else # if first < last
return if stackEmpty?
entry = popStack
isad = entry.a
first = entry.b
last = entry.c
limit = entry.d
end
end # if limit == -1
next
end # if limit < 0
if last - first <= INSERTION_SORT_THRESHOLD
break unless budget.update(size, last - first)
trInsertionSort(isa, isad, isan, first, last)
limit = -3
next
end
if limit == 0
limit -= 1
break unless budget.update(size, last - first)
trHeapSort(isa, isad, isan, first, last - first)
a = last - 1
while first < a
x = trGetC(isa, isad, isan, @sa[a])
b = a - 1
while first <= b && trGetC(isa, isad, isan, @sa[b]) == x
@sa[b] = ~(@sa[b])
b -= 1
end
a = b
end
limit = -3
next
else
limit -= 1
end
a = trPivot(isa, isad, isan, first, last)
swap(@sa, first, @sa, a)
v = trGetC(isa, isad, isan, @sa[first])
b = first
while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) == v
end
if (a = b) < last && x < v
while (b += 1) < last && (x = trGetC(isa, isad, isan, @sa[b])) <= v
if x == v
swap(@sa, b, @sa, a)
a += 1
end
end
end
c = last
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) == v
end
if b < (d = c) && x > v
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
if x == v
swap(@sa, c, @sa, d)
d -= 1
end
end
end
while b < c
swap(@sa, b, @sa, c)
while (b += 1) < c && (x = trGetC(isa, isad, isan, @sa[b])) <= v
if x == v
swap(@sa, b, @sa, a)
a += 1
end
end
while b < (c -= 1) && (x = trGetC(isa, isad, isan, @sa[c])) >= v
if x == v
swap(@sa, c, @sa, d)
d -= 1
end
end
end
if a <= d
c = b - 1
if (s = a - first) > (t = b - a)
s = t
end
e = first
f = b - s
while 0 < s
swap(@sa, e, @sa, f)
s -= 1
e += 1
f += 1
end
if (s = d - c) > (t = last - d - 1)
s = t
end
e = b
f = last - s
while 0 < s
swap(@sa, e, @sa, f)
s -= 1
e += 1
f += 1
end
a = first + (b - a)
b = last - (d - c)
nxt = if @sa[isa + @sa[a]] != v
trLog(b - a)
else
-1
end
c = first
v = a - 1
while c < a
@sa[isa + @sa[c]] = v
c += 1
end
if b < last
c = a
v = b - 1
while c < b
@sa[isa + @sa[c]] = v
c += 1
end
end
if a - first <= last - b
if last - b <= b - a
if 1 < a - first
pushStack(isad + 1, a, b, nxt)
pushStack(isad, b, last, limit)
last = a
elsif 1 < last - b
pushStack(isad + 1, a, b, nxt)
first = b
elsif 1 < b - a
isad += 1
first = a
last = b
limit = nxt
else
return if stackEmpty?
entry = popStack
isad = entry.a
first = entry.b
last = entry.c
limit = entry.d
end
elsif a - first <= b - a
if 1 < a - first
pushStack(isad, b, last, limit)
pushStack(isad + 1, a, b, nxt)
last = a
elsif 1 < b - a
pushStack(isad, b, last, limit)
isad += 1
first = a
last = b
limit = nxt
else
first = b
end
else
if 1 < b - a
pushStack(isad, b, last, limit)
pushStack(isad, first, a, limit)
isad += 1
first = a
last = b
limit = nxt
else
pushStack(isad, b, last, limit)
last = a
end
end # if last - b <= b - a
else # if a - first <= last - b
if a - first <= b - a
if 1 < last - b
pushStack(isad + 1, a, b, nxt)
pushStack(isad, first, a, limit)
first = b
elsif 1 < a - first
pushStack(isad + 1, a, b, nxt)
last = a
elsif 1 < b - a
isad += 1
first = a
last = b
limit = nxt
else
pushStack(isad, first, last, limit)
end
elsif last - b <= b - a
if 1 < last - b
pushStack(isad, first, a, limit)
pushStack(isad + 1, a, b, nxt)
first = b
elsif 1 < b - a
pushStack(isad, first, a, limit)
isad += 1
first = a
last = b
limit = nxt
else
last = a
end
else
if 1 < b - a
pushStack(isad, first, a, limit)
pushStack(isad, b, last, limit)
isad += 1
first = a
last = b
limit = nxt
else
pushStack(isad, first, a, limit)
first = b
end
end
end
else
break unless budget.update(size, last - first)
limit += 1
isad += 1
end
end # loop do
@ssize.times do |z|
if @stack[z].d == -3
lsUpdateGroup(isa, @stack[z].b, @stack[z].c)
end
end
end
private def trSort(isa : Int32, x : Int32, depth : Int32) : Nil
first : Int32 = 0
if -x < @sa.unsafe_fetch(0)
budget : TRBudget = TRBudget.new(x, (trLog(x) * 2 / 3 + 1).to_i32!)
t : Int32 = 0
last : Int32 = 0
loop do
if (t = @sa.unsafe_fetch(first)) < 0
first -= t
else
last = @sa.unsafe_fetch(isa + t) + 1
if 1 < (last - first)
trIntroSort(isa, isa + depth, isa + x, first, last, budget, x)
if budget.chance == 0
# Switch to Larsson-Sadakane sorting algorithm.
@sa.unsafe_put(0, -first) if 0 < first
lsSort(isa, x, depth)
break
end
end
first = last
end
break unless first < x
end
end
end
@[AlwaysInline]
protected def self.bucketB(c0 : Int32, c1 : Int32) : Int32
(c1 << 8) | c0
end
@[AlwaysInline]
protected def self.bucketBStar(c0 : Int32, c1 : Int32) : Int32
(c0 << 8) | c1
end
private def sortTypeBstar(bucketA : Array(Int32), bucketB : Array(Int32)) : Int32
@int32Pool.withRentedArray(256) do |tempBuf|
tempBuf.fill(0)
j : Int32 = 0
k : Int32 = 0
t : Int32 = 0
c0 : Int32 = 0
c1 : Int32 = 0
i : Int32 = 1
flag : Int32 = 1
while i < @n
if @t[i - 1] != @t[i]
if @t[i - 1] > @t[i]
flag = 0
end
break
end
i += 1
end
i = @n - 1
m : Int32 = @n
ti : Int32 = @t[i].to_i32!
t0 : Int32 = @t[0].to_i32!
ti1 : Int32 = 0
if ti < t0 || (@t[i] == @t[0] && flag != 0)
if flag == 0
bucketB[DivSufSort.bucketBStar(ti, t0)] += 1
@sa[m -= 1] = i
else
bucketB[DivSufSort.bucketB(ti, t0)] += 1
end
i -= 1
while 0 <= i && (ti = @t[i].to_i32!) <= (ti1 = @t[i + 1].to_i32!)
bucketB[DivSufSort.bucketB(ti, ti1)] += 1
i -= 1
end
end
while 0 <= i
loop do
bucketA[@t[i]] += 1
break unless 0 <= (i -= 1) && @t[i] >= @t[i + 1]
end
if 0 <= i
bucketB[DivSufSort.bucketBStar(@t[i].to_i32!, @t[i + 1].to_i32!)] += 1
@sa[m -= 1] = i
i -= 1
while 0 <= i && (ti = @t[i].to_i32!) <= (ti1 = @t[i + 1].to_i32!)
bucketB[DivSufSort.bucketB(ti, ti1)] += 1
i -= 1
end
end
end
m = @n - m
if m == 0
@n.times { |z| @sa[z] = z }
return 0
end
c0 = 0
i = -1
j = 0
while c0 < 256
t = i + bucketA[c0]
bucketA[c0] = i + j
i = t + bucketB[DivSufSort.bucketB(c0, c0)]
c1 = c0 + 1
while c1 < 256
j += bucketB[DivSufSort.bucketBStar(c0, c1)]
bucketB[(c0 << 8) | c1] = j
i += bucketB[DivSufSort.bucketB(c0, c1)]
c1 += 1
end
c0 += 1
end
pab : Int32 = @n - m
isab : Int32 = m
i = m - 2
while 0 <= i
t = @sa[pab + i]
c0 = @t[t].to_i32!
c1 = @t[t + 1].to_i32!
@sa[(bucketB[DivSufSort.bucketBStar(c0, c1)] -= 1)] = i
i -= 1
end
t = @sa[pab + m - 1]
c0 = @t[t].to_i32!
c1 = @t[t + 1].to_i32!
@sa[bucketB[DivSufSort.bucketBStar(c0, c1)] -= 1] = m - 1
buf : Array(Int32) = @sa
bufOffset : Int32 = m
bufSize : Int32 = @n - (2 * m)
if bufSize <= 256
buf = tempBuf
bufOffset = 0
bufSize = 256
end
c0 = 255
j = m
while 0 < j
c1 = 255
while c0 < c1
i = bucketB[DivSufSort.bucketBStar(c0, c1)]
if 1 < j - i
subStringSort(pab, i, j, buf, bufOffset, bufSize, 2, @sa[i] == (m - 1), @n)
end
j = i
c1 -= 1
end
c0 -= 1
end
i = m - 1
while 0 <= i
if 0 <= @sa[i]
j = i
loop do
@sa[isab + @sa[i]] = i
break unless 0 <= (i -= 1) && 0 <= @sa[i]
end
@sa[i + 1] = i - j
break if i <= 0
end
j = i
loop do
@sa[isab + (@sa[i] = ~(@sa[i]))] = j
break unless @sa[i -= 1] < 0
end
@sa[isab + @sa[i]] = j
i -= 1
end
trSort(isab, m, 1)
i = @n - 1
j = m
if @t[i] < @t[0] || (@t[i] == @t[0] && flag != 0)
if flag == 0
@sa[@sa[isab + (j -= 1)]] = i
end
i -= 1
while 0 <= i && @t[i] <= @t[i + 1]
i -= 1
end
end
while 0 <= i
i -= 1
while 0 <= i && @t[i] >= @t[i + 1]
i -= 1
end
if 0 <= i
@sa[@sa[isab + (j -= 1)]] = i
i -= 1
while 0 <= i && @t[i] <= @t[i + 1]
i -= 1
end
end
end
c0 = 255
i = @n - 1
k = m - 1
while 0 <= c0
c1 = 255
while c0 < c1
t = i - bucketB[DivSufSort.bucketB(c0, c1)]
bucketB[DivSufSort.bucketB(c0, c1)] = i + 1
i = t
j = bucketB[DivSufSort.bucketBStar(c0, c1)]
while j <= k
@sa[i] = @sa[k]
i -= 1
k -= 1
end
c1 -= 1
end
t = i - bucketB[DivSufSort.bucketB(c0, c0)]
bucketB[DivSufSort.bucketB(c0, c0)] = i + 1
if c0 < 255
bucketB[DivSufSort.bucketBStar(c0, c0 + 1)] = t + 1
end
i = bucketA[c0]
c0 -= 1
end
m
end
end
private def constructBWT(bucketA : Array(Int32), bucketB : Array(Int32)) : Int32
i : Int32 = 0
t : Int32 = 0
s : Int32 = 0
s1 : Int32 = 0
c0 : Int32 = 0
c2 : Int32 = 0
orig : Int32 = -1
j : Int32 = 0
c1 : Int32 = 254
while 0 <= c1
i = bucketB[DivSufSort.bucketBStar(c1, c1 + 1)]
j = bucketA[c1 + 1]
t = 0
c2 = -1
while i <= j
s1 = s = @sa[j]
if 0 <= s1
if (s -= 1) < 0
s = @n - 1
end
c0 = @t[s].to_i32!
if c0 <= c1
@sa[j] = ~s1
if 0 < s && @t[s - 1] > c0
s = ~s
end
if c2 == c0
@sa[t -= 1] = s
else
if 0 <= c2
bucketB[DivSufSort.bucketB(c2, c1)] = t
end
c2 = c0
t = bucketB[DivSufSort.bucketB(c2, c1)] - 1
@sa[t] = s
end
end
else
@sa[j] = ~s
end
j -= 1
end
c1 -= 1
end
@n.times do |i|
s1 = s = @sa[i]
if 0 <= s1
if (s -= 1) < 0
s = @n - 1
end
if (c0 = @t[s].to_i32!) >= @t[s + 1]
if 0 < s && @t[s - 1] < c0
s = ~s
end
if c0 == c2
@sa[t += 1] = s
else
if c2 != -1 # BUGFIX: Original code can write to bucketA[-1]
bucketA[c2] = t
end
c2 = c0
t = bucketA[c2] + 1
@sa[t] = s
end
end
else
s1 = ~s1
end
if s1 == 0
@sa[i] = @t[@n - 1].to_i32!
orig = i
else
@sa[i] = @t[s1 - 1].to_i32!
end
end
orig
end
end
end