/*
 * kqsort_depth_harness.c  --  DF-2245 proof-of-defect (standalone)
 *
 * Replicates the EXACT algorithm of sys/libkern/qsort.c (kqsort) twice:
 *   (1) kqsort_VULN  : identical to the in-kernel code (recurse on the
 *                      "< pivot" band, iterate on the "> pivot" band).
 *   (2) kqsort_FIXED : recurse on the SMALLER band, iterate on the larger
 *                      one  -> recursion depth bounded to O(log2 n).
 *
 * Both carry a global max-recursion-depth counter. We feed each:
 *   - random input
 *   - sorted ascending / descending
 *   - "organ-pipe"
 *   - an adaptive median-of-3 killer adversary (McIlroy-style)
 *
 * The vulnerable variant reaches O(n) depth on the killer input; the fixed
 * variant stays at O(log n). This proves the code defect WITHOUT depending
 * on any kernel path -- the defect is a pure algorithmic property of
 * qsort.c lines 173-184.
 *
 * Build:  cc -O2 -o kqsort_depth_harness kqsort_depth_harness.c
 * Run:    ./kqsort_depth_harness
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

static int g_maxdepth;          /* observed max recursion depth (VULN or FIXED) */
static int g_curdepth;
static int g_cap;               /* hard recursion cap (prevents userspace stack overflow so we can print) */
static int g_overflow;          /* set if cap hit */

#define DEPTH_PROLOG()  do { ++g_curdepth; if(g_curdepth>g_maxdepth) g_maxdepth=g_curdepth; \
                             if (g_cap && g_curdepth>=g_cap){ g_overflow=1; --g_curdepth; return; } } while(0)

/* ----------------------------- common qsort guts -------------------------- */
typedef int cmp_t(const void *, const void *);

static inline char *med3(char *a, char *b, char *c, cmp_t *cmp) {
    return cmp(a, b) < 0 ?
        (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a)) :
        (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
}
static inline void swapfunc(char *a, char *b, int n, int st) {
    long i; char *pi, *pj;
    if (st <= 1) { i=n/sizeof(long); pi=a; pj=b;
        do { long t=*(long*)pi; *(long*)pi=*(long*)pj; *(long*)pj=t; pi++; pj++; } while(--i>0); }
    else { i=n; pi=a; pj=b; do { char t=*pi; *pi=*pj; *pj=t; pi++; pj++; } while(--i>0); }
}
#define SWAPINIT(a,es) st = ((char*)(a)-(char*)0)%sizeof(long)||es%sizeof(long)?2:es==sizeof(long)?0:1
#define min(a,b) ((a)<(b)?(a):(b))
#define vecswap(a,b,n,st) if((n)>0) swapfunc(a,b,n,st)

/* --------------------------- VULNERABLE (as in kernel) -------------------- */
static void kqsort_VULN(char *a, size_t n, size_t es, cmp_t *cmp) {
    char *pa,*pb,*pc,*pd,*pl,*pm,*pn; int d,r,st,sc;
    DEPTH_PROLOG();
loop:   SWAPINIT(a,es); sc=0;
    if (n<7){ for(pm=a+es;pm<a+n*es;pm+=es) for(pl=pm;pl>a&&cmp(pl-es,pl)>0;pl-=es) swapfunc(pl,pl-es,es,st); --g_curdepth; return; }
    pm=a+(n/2)*es;
    if(n>7){pl=a;pn=a+(n-1)*es; if(n>40){d=(n/8)*es;pl=med3(pl,pl+d,pl+2*d,cmp);pm=med3(pm-d,pm,pm+d,cmp);pn=med3(pn-2*d,pn-d,pn,cmp);} pm=med3(pl,pm,pn,cmp);}
    {swapfunc(a,pm,es,st);}
    pa=pb=a+es; pc=pd=a+(n-1)*es;
    for(;;){ while(pb<=pc&&(r=cmp(pb,a))<=0){ if(r==0){sc=1;swapfunc(pa,pb,es,st);pa+=es;} pb+=es;} while(pb<=pc&&(r=cmp(pc,a))>=0){ if(r==0){sc=1;swapfunc(pd,pc,es,st);pd-=es;} pc-=es;} if(pb>pc)break; swapfunc(pb,pc,es,st); sc=1; pb+=es; pc-=es; }
    if(sc==0){ for(pm=a+es;pm<a+n*es;pm+=es) for(pl=pm;pl>a&&cmp(pl-es,pl)>0;pl-=es){swapfunc(pl,pl-es,es,st);} --g_curdepth; return; }
    pn=a+n*es; r=min(pa-a,pb-pa); vecswap(a,pb-r,r,st); r=min(pd-pc,pn-pd-es); vecswap(pb,pn-r,r,st);
    if((r=pb-pa)>es) kqsort_VULN(a,r/es,es,cmp);              /* RECURSE on "<" */
    if((r=pd-pc)>es){ a=pn-r; n=r/es; goto loop; }             /* ITERATE on ">" */
    --g_curdepth;
}

/* --------------------------- FIXED (recurse on smaller) ------------------- */
static void kqsort_FIXED(char *a, size_t n, size_t es, cmp_t *cmp) {
    char *pa,*pb,*pc,*pd,*pl,*pm,*pn; int d,r,st,sc;
    DEPTH_PROLOG();
loop:   SWAPINIT(a,es); sc=0;
    if (n<7){ for(pm=a+es;pm<a+n*es;pm+=es) for(pl=pm;pl>a&&cmp(pl-es,pl)>0;pl-=es) swapfunc(pl,pl-es,es,st); --g_curdepth; return; }
    pm=a+(n/2)*es;
    if(n>7){pl=a;pn=a+(n-1)*es; if(n>40){d=(n/8)*es;pl=med3(pl,pl+d,pl+2*d,cmp);pm=med3(pm-d,pm,pm+d,cmp);pn=med3(pn-2*d,pn-d,pn,cmp);} pm=med3(pl,pm,pn,cmp);}
    {swapfunc(a,pm,es,st);}
    pa=pb=a+es; pc=pd=a+(n-1)*es;
    for(;;){ while(pb<=pc&&(r=cmp(pb,a))<=0){ if(r==0){sc=1;swapfunc(pa,pb,es,st);pa+=es;} pb+=es;} while(pb<=pc&&(r=cmp(pc,a))>=0){ if(r==0){sc=1;swapfunc(pd,pc,es,st);pd-=es;} pc-=es;} if(pb>pc)break; swapfunc(pb,pc,es,st); sc=1; pb+=es; pc-=es; }
    if(sc==0){ for(pm=a+es;pm<a+n*es;pm+=es) for(pl=pm;pl>a&&cmp(pl-es,pl)>0;pl-=es){swapfunc(pl,pl-es,es,st);} --g_curdepth; return; }
    pn=a+n*es; r=min(pa-a,pb-pa); vecswap(a,pb-r,r,st); r=min(pd-pc,pn-pd-es); vecswap(pb,pn-r,r,st);
    {
        size_t nl = (pb-pa)/es;   /* "<" partition count */
        size_t nr = (pd-pc)/es;   /* ">" partition count */
        char *larger_a; size_t larger_n; char *smaller_a; size_t smaller_n;
        if (nl >= nr) { larger_a=a; larger_n=nl; smaller_a=pn-(pd-pc); smaller_n=nr; }
        else          { larger_a=pn-(pd-pc); larger_n=nr; smaller_a=a; smaller_n=nl; }
        /* recurse on the SMALLER half -> O(log n) depth bound */
        if (smaller_n*es > es) kqsort_FIXED(smaller_a, smaller_n, es, cmp);
        /* iterate on the larger half */
        if (larger_n*es > es) { a=larger_a; n=larger_n; goto loop; }
    }
    --g_curdepth;
}

/* ----------------------------- inputs ------------------------------------- */
static cmp_t icmp;            /* plain int comparator */
static int icmp(const void *a, const void *b){ int x=*(const int*)a, y=*(const int*)b; return (x>y)-(x<y); }

/* McIlroy-style adaptive median-of-3 killer adversary.
 * val[] holds each item's current rank; ties are broken adversarially by
 * handing out a fresh increasing rank, which steers the med3 pivot so the
 * "< pivot" partition stays large. This drives the vulnerable (recurse-on-<)
 * variant to O(n) depth. */
static int *kval;
static int knext;
static int killer_cmp(const void *a, const void *b){
    int x=*(const int*)a, y=*(const int*)b;   /* x,y are item indices */
    if (kval[x]==kval[y]) { kval[x]=knext++; return 1; }  /* promote x above y */
    return kval[x]<kval[y]?-1:1;
}

static void reset_depth(void){ g_maxdepth=0; g_curdepth=0; g_overflow=0; }

static int *mkarr(int n, const char *kind){
    int *a=malloc(n*sizeof(int)); int i;
    if (!strcmp(kind,"random"))   for(i=0;i<n;i++) a[i]=rand();
    else if(!strcmp(kind,"asc"))  for(i=0;i<n;i++) a[i]=i;
    else if(!strcmp(kind,"desc")) for(i=0;i<n;i++) a[i]=n-i;
    else if(!strcmp(kind,"organ")){ for(i=0;i<n/2;i++) a[i]=i+1; for(;i<n;i++) a[i]=n-i; }
    else if(!strcmp(kind,"killer")){ for(i=0;i<n;i++) a[i]=i; /* indices, val-driven */
        kval=malloc(n*sizeof(int)); memset(kval,0,n*sizeof(int)); knext=1; }
    else { for(i=0;i<n;i++) a[i]=0; }
    return a;
}

static int verify_sorted(int *a, int n, cmp_t *cmp){
    for(int i=1;i<n;i++) if(cmp(a+i-1,a+i)>0) return 0;
    return 1;
}

int main(void){
    int ns[]={64,128,256,512,1024,2048,4096};
    const char *kinds[]={"random","asc","desc","organ","killer"};
    g_cap = 200000;  /* prevent userspace stack overflow; flag if exceeded */
    printf("%-7s %-8s %12s %12s %14s\n","N","input","VULN_depth","FIXED_depth","log2(N)");
    printf("------------------------------------------------------------------------\n");
    for(unsigned k=0;k<sizeof(ns)/sizeof(ns[0]);k++){
        int n=ns[k];
        int log2n=0; while((1<<log2n)<n) log2n++;
        for(unsigned j=0;j<sizeof(kinds)/sizeof(kinds[0]);j++){
            const char *kind=kinds[j];
            /* VULN */
            int *a=mkarr(n,kind);
            reset_depth();
            cmp_t *c = !strcmp(kind,"killer") ? killer_cmp : icmp;
            kqsort_VULN((char*)a,n,sizeof(int),c);
            int vd=g_maxdepth; int vo=g_overflow;
            int okv = strcmp(kind,"killer")==0 ? 1 : verify_sorted(a,n,icmp);
            free(a); if(kval){free(kval);kval=NULL;}
            /* FIXED */
            a=mkarr(n,kind);
            reset_depth();
            c = !strcmp(kind,"killer") ? killer_cmp : icmp;
            kqsort_FIXED((char*)a,n,sizeof(int),c);
            int fd=g_maxdepth; int fo=g_overflow;
            int okf = strcmp(kind,"killer")==0 ? 1 : verify_sorted(a,n,icmp);
            free(a); if(kval){free(kval);kval=NULL;}
            (void)okv;(void)okf;
            char vbuf[24], fbuf[24];
            snprintf(vbuf,sizeof vbuf, vo?"%d(OVF)":"%d", vd);
            snprintf(fbuf,sizeof fbuf, fo?"%d(OVF)":"%d", fd);
            printf("%-7d %-8s %12s %12s %14d\n", n, kind, vbuf, fbuf, log2n);
        }
    }
    /* log2 table for reference */
    printf("\nReference log2(N): ");
    for(unsigned k=0;k<sizeof(ns)/sizeof(ns[0]);k++){
        int n=ns[k], l=0; while((1<<l)<n) l++;
        printf("N=%d->%d  ", n, l);
    }
    printf("\n");
    return 0;
}