<commit_before>package bsdiff

import (
	"bytes"
	"fmt"
	"os"

	"github.com/itchio/wharf/state"
)

var parallel = os.Getenv("PARALLEL_BSDIFF") == "1"

// Ternary-Split Quicksort, cf. http://www.larsson.dogma.net/ssrev-tr.pdf
func split(I, V, V2 []int32, start, length, h int32, consumer *state.Consumer) {
	// fmt.Fprintf(os.Stderr, "split(%d, %d)\n", start, length)

	var i, j, k, x, jj, kk int32

	// if length < 16 {
	// 	for k = start; k < start+length; k += j {
	// 		j = 1
	// 		x = V[I[k]+h]
	// 		for i = 1; k+i < start+length; i++ {
	// 			if V[I[k+i]+h] < x {
	// 				x = V[I[k+i]+h]
	// 				j = 0
	// 			}
	// 			if V[I[k+i]+h] == x {
	// 				I[k+i], I[k+j] = I[k+j], I[k+i]
	// 				j++
	// 			}
	// 		}
	// 		for i = 0; i < j; i++ {
	// 			V[I[k+i]] = k + j - 1
	// 		}
	// 		if j == 1 {
	// 			I[k] = -1
	// 		}
	// 	}
	// 	return
	// }

	// fmt.Fprintf(os.Stderr, "start+length/2 = %d, len(I) = %d\n", start+length/2, len(I))
	// fmt.Fprintf(os.Stderr, "V[%d] (read)\n", I[start+length/2]+h)
	x = V[I[start+length/2]+h]
	jj = 0
	kk = 0
	for i = start; i < start+length; i++ {
		if V[I[i]+h] < x {
			jj++
		}
		if V[I[i]+h] == x {
			kk++
		}
	}
	jj += start
	kk += jj

	i = start
	j = 0
	k = 0
	for i < jj {
		if V[I[i]+h] < x {
			i++
		} else if V[I[i]+h] == x {
			I[i], I[jj+j] = I[jj+j], I[i]
			j++
		} else {
			I[i], I[kk+k] = I[kk+k], I[i]
			k++
		}
	}

	for jj+j < kk {
		if V[I[jj+j]+h] == x {
			j++
		} else {
			I[jj+j], I[kk+k] = I[kk+k], I[jj+j]
			k++
		}
	}

	if jj > start {
		// fmt.Fprintf(os.Stderr, "lsplit I[%d-%d]\n", start, jj)
		split(I, V, V2, start, jj-start, h, consumer)
	}

	for i = 0; i < kk-jj; i++ {
		// fmt.Fprintf(os.Stderr, "V[%d] = %d\n", I[jj+i], kk-1)
		V2[I[jj+i]] = kk - 1
	}
	if jj == kk-1 {
		// fmt.Fprintf(os.Stderr, "I[%d] = %d\n", I[jj], -1)
		I[jj] = -1
	}

	if start+length > kk {
		// fmt.Fprintf(os.Stderr, "rsplit I[%d-%d]\n", kk, start+length)
		split(I, V, V2, kk, start+length-kk, h, consumer)
	}
}

type mark struct {
	index int32
	value int32
}

// Faster Suffix Sorting, see: http://www.larsson.dogma.net/ssrev-tr.pdf
// Output `I` is a sorted suffix array.
// TODO: implement parallel sorting as a faster alternative for high-RAM environments
// see http://www.zbh.uni-hamburg.de/pubs/pdf/FutAluKur2001.pdf
func qsufsort(obuf []byte, consumer *state.Consumer) []int32 {
	var buckets [256]int32
	var i, h int32
	var obuflen = int32(len(obuf))

	I := make([]int32, obuflen+1)
	V := make([]int32, obuflen+1)

	for _, c := range obuf {
		buckets[c]++
	}
	for i = 1; i < 256; i++ {
		buckets[i] += buckets[i-1]
	}
	copy(buckets[1:], buckets[:])
	buckets[0] = 0

	for i, c := range obuf {
		buckets[c]++
		I[buckets[c]] = int32(i)
	}

	I[0] = obuflen
	for i, c := range obuf {
		V[i] = buckets[c]
	}

	V[obuflen] = 0
	for i = 1; i < 256; i++ {
		if buckets[i] == buckets[i-1]+1 {
			I[buckets[i]] = -1
		}
	}
	I[0] = -1

	const progressInterval = 64 * 1024

	V2 := append([]int32{}, V...)
	marks := make([]mark, 0)

	for h = 1; I[0] != -(obuflen + 1); h += h {
		consumer.ProgressLabel(fmt.Sprintf("Suffix sorting (%d-order)", h))
		// consumer.Debugf("\n>> Pass %d", h)

		var lastI int32
		var n int32<commit_msg>Restore <16 quick sort path<commit_after>package bsdiff

import (
	"bytes"
	"fmt"
	"os"

	"github.com/itchio/wharf/state"
)

var parallel = os.Getenv("PARALLEL_BSDIFF") == "1"

// Ternary-Split Quicksort, cf. http://www.larsson.dogma.net/ssrev-tr.pdf
func split(I, V, V2 []int32, start, length, h int32, consumer *state.Consumer) {
	// fmt.Fprintf(os.Stderr, "split(%d, %d)\n", start, length)

	var i, j, k, x, jj, kk int32

	if length < 16 {
		for k = start; k < start+length; k += j {
			j = 1
			x = V2[I[k]+h]
			for i = 1; k+i < start+length; i++ {
				if V2[I[k+i]+h] < x {
					x = V2[I[k+i]+h]
					j = 0
				}
				if V2[I[k+i]+h] == x {
					I[k+i], I[k+j] = I[k+j], I[k+i]
					j++
				}
			}
			for i = 0; i < j; i++ {
				V2[I[k+i]] = k + j - 1
			}
			if j == 1 {
				I[k] = -1
			}
		}
		return
	}

	// fmt.Fprintf(os.Stderr, "start+length/2 = %d, len(I) = %d\n", start+length/2, len(I))
	// fmt.Fprintf(os.Stderr, "V[%d] (read)\n", I[start+length/2]+h)
	x = V[I[start+length/2]+h]
	jj = 0
	kk = 0
	for i = start; i < start+length; i++ {
		if V[I[i]+h] < x {
			jj++
		}
		if V[I[i]+h] == x {
			kk++
		}
	}
	jj += start
	kk += jj

	i = start
	j = 0
	k = 0
	for i < jj {
		if V[I[i]+h] < x {
			i++
		} else if V[I[i]+h] == x {
			I[i], I[jj+j] = I[jj+j], I[i]
			j++
		} else {
			I[i], I[kk+k] = I[kk+k], I[i]
			k++
		}
	}

	for jj+j < kk {
		if V[I[jj+j]+h] == x {
			j++
		} else {
			I[jj+j], I[kk+k] = I[kk+k], I[jj+j]
			k++
		}
	}

	if jj > start {
		// fmt.Fprintf(os.Stderr, "lsplit I[%d-%d]\n", start, jj)
		split(I, V, V2, start, jj-start, h, consumer)
	}

	for i = 0; i < kk-jj; i++ {
		// fmt.Fprintf(os.Stderr, "V[%d] = %d\n", I[jj+i], kk-1)
		V2[I[jj+i]] = kk - 1
	}
	if jj == kk-1 {
		// fmt.Fprintf(os.Stderr, "I[%d] = %d\n", I[jj], -1)
		I[jj] = -1
	}

	if start+length > kk {
		// fmt.Fprintf(os.Stderr, "rsplit I[%d-%d]\n", kk, start+length)
		split(I, V, V2, kk, start+length-kk, h, consumer)
	}
}

type mark struct {
	index int32
	value int32
}

type sortTask struct {
	start  int32
	length int32
	h      int32
}

// Faster Suffix Sorting, see: http://www.larsson.dogma.net/ssrev-tr.pdf
// Output `I` is a sorted suffix array.
// TODO: implement parallel sorting as a faster alternative for high-RAM environments
// see http://www.zbh.uni-hamburg.de/pubs/pdf/FutAluKur2001.pdf
func qsufsort(obuf []byte, consumer *state.Consumer) []int32 {
	var buckets [256]int32
	var i, h int32
	var obuflen = int32(len(obuf))

	I := make([]int32, obuflen+1)
	V := make([]int32, obuflen+1)

	for _, c := range obuf {
		buckets[c]++
	}
	for i = 1; i < 256; i++ {
		buckets[i] += buckets[i-1]
	}
	copy(buckets[1:], buckets[:])
	buckets[0] = 0

	for i, c := range obuf {
		buckets[c]++
		I[buckets[c]] = int32(i)
	}

	I[0] = obuflen
	for i, c := range obuf {
		V[i] = buckets[c]
	}

	V[obuflen] = 0
	for i = 1; i < 256; i++ {
		if buckets[i] == buckets[i-1]+1 {
			I[buckets[i]] = -1
		}
	}
	I[0] = -1

	const progressInterval = 64 * 1024

	V2 := append([]int32{}, V...)
	marks := make([]mark, 0)

	for h = 1; I[0] != -(obuflen + 1); h += h {
		marks = marks[:0]

		consumer.ProgressLabel(fmt.Sprintf("Suffix sorting (%d-order)", h))
		// consumer.Debugf("\n>> Pass %d", h)

		var lastI int32
		var n int32
{'fraction_non_alphanumeric': 0.2296896928114767, 'fraction_numerical': 0.03243411819741151, 'mean_word_length': 2.4764227642276424, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 6, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1248799', 'n_tokens_mistral': 3554, 'n_tokens_neox': 3182, 'n_words': 724}