// PureNoise CryptoLib (c) 1997-2004, PureNoise Ltd Vaduz <www.cryptolib.com>
// Ruptor's fastest sorting routines in pure C

#include "qsort.h"

#define swap(i, j) (t = *i, *i = *j, *j = t)
#define rotate(i, j, k) (t = *i, *i = *j, *j = *k, *k = t)

void qsort8 (unsigned char *av, unsigned long rn)
{
    unsigned char		*l = av;
	unsigned char		*r = l + rn - 1;
	unsigned char		*i, *j, *m;
	unsigned char		*s[sizeof (unsigned long) * 16], **p = s;
	unsigned char		t;
	
    if (l < r) for (;;)
	{
        m = l + (r - l) / 2;
		
        if (*m <= *r)
		{
            if ((l < m) && (*l > *m))
                if (*l <= *r) swap (l, m);
				else rotate (m, r, l);
		}
        else if ((l >= m) || (*l > *m)) swap (l, r);
		else if (*l <= *r) swap (m, r);
		else rotate (m, l, r);
		
		if ((i = l + 1) < (j = r - 1))
		{
			for (;;)
			{
				while ((i < m) && (*i < *m)) i++;
				while ((m < j) && (*m < *j)) j--;
				if (i < j) swap (i, j); else break;
				if (m == j) m = i, j--;
				else if (i == m) m = j, i++;
				else j--, i++;
			}
			
			if ((i--) - l <= r - (j++))
			{
				if (l < i) *(p++) = j, *(p++) = r, r = i; else l = j;
			}
			else
			{
				if (j < r) *(p++) = l, *(p++) = i, l = j; else r = i;
			}
		}
		else
		{
			if (s < p) r = *(--p), l = *(--p); else break;
		}
	}
}

void qsort_32 (unsigned long *av, unsigned long rn)
{
    unsigned long		*l = av;
	unsigned long		*r = l + rn - 1;
	unsigned long		*i, *j, *m;
	unsigned long		*s[sizeof (unsigned long) * 16], **p = s;
	unsigned long		t;
	
    if (l < r) for (;;)
	{
        m = l + (r - l) / 2;
		
        if (*m <= *r)
		{
            if ((l < m) && (*l > *m))
                if (*l <= *r) swap (l, m);
				else rotate (m, r, l);
		}
        else if ((l >= m) || (*l > *m)) swap (l, r);
		else if (*l <= *r) swap (m, r);
		else rotate (m, l, r);
		
		if ((i = l + 1) < (j = r - 1))
		{
			for (;;)
			{
				while ((i < m) && (*i < *m)) i++;
				while ((m < j) && (*m < *j)) j--;
				if (i < j) swap (i, j); else break;
				if (m == j) m = i, j--;
				else if (i == m) m = j, i++;
				else j--, i++;
			}
			
			if ((i--) - l <= r - (j++))
			{
				if (l < i) *(p++) = j, *(p++) = r, r = i; else l = j;
			}
			else
			{
				if (j < r) *(p++) = l, *(p++) = i, l = j; else r = i;
			}
		}
		else
		{
			if (s < p) r = *(--p), l = *(--p); else break;
		}
	}
}

// ->D[0] = original index or pointer
// ->D[1] = data value

void qsort_2x32 (OCTET *av, unsigned long rn)
{
	OCTET		*l = av;
	OCTET		*r = l + rn - 1;
	OCTET		*i, *j, *m;
	OCTET		*s[sizeof (unsigned long) * 16], **p = s;
	OCTET		t;
	
    if (l < r) for (;;)
	{
        m = l + (r - l) / 2;
		
        if (m->D[1] <= r->D[1])
		{
            if ((l < m) && (l->D[1] > m->D[1]))
                if (l->D[1] <= r->D[1]) swap (l, m);
				else rotate (m, r, l);
		}
        else if ((l >= m) || (l->D[1] > m->D[1])) swap (l, r);
		else if (l->D[1] <= r->D[1]) swap (m, r);
		else rotate (m, l, r);
		
		if ((i = l + 1) < (j = r - 1))
		{
			for (;;)
			{
				while ((i < m) && (i->D[1] < m->D[1])) i++;
				while ((m < j) && (m->D[1] < j->D[1])) j--;
				if (i < j) swap (i, j); else break;
				if (m == j) m = i, j--;
				else if (i == m) m = j, i++;
				else j--, i++;
			}
			
			if ((i--) - l <= r - (j++))
			{
				if (l < i) *(p++) = j, *(p++) = r, r = i; else l = j;
			}
			else
			{
				if (j < r) *(p++) = l, *(p++) = i, l = j; else r = i;
			}
		}
		else
		{
			if (s < p) r = *(--p), l = *(--p); else break;
		}
	}
}