<commit_before>#include "common.th"

    .global main
main:
    prologue

#define DATA_LEN (.L_data_end - .L_data_start)
#define ELT_LEN  (.L_data_elt_end - .L_data_elt_start)

    c <- rel(data_start)        // data to sort
    d <- (DATA_LEN / ELT_LEN)   // number of elements
    e <- ELT_LEN                // size of each element
    f <- rel(inteq)             // comparator
    call(qsort)

done:
    i <- .L_data_start
print_loop:
    c <- [i - (. + 0) + p]      // get second field of struct
    c <-  c - (. + 1) + p       // and relocate it
    call(puts)
    c <- rel(nl)
    call(puts)
    i <- i + ELT_LEN
    c <- i < .L_data_end
    jnzrel(c,print_loop)

    illegal

#define elem(Dest, Base, Index) \
    Dest <- Index * E         ; \
    Dest <- Dest + Base       ; \
    //

#define swap(i0, i1)            \
    pushall(c,d,e,f,g)        ; \
    f <- c                    ; \
    g <- e                    ; \
    o <- o - e - 1            ; \
    c <- o + 1                ; \
    elem(d,f,i0)              ; \
    /* E is already width */  ; \
    call(memcpy)              ; \
    elem(c,f,i0)              ; \
    elem(d,f,i1)              ; \
    e <- g                    ; \
    call(memcpy)              ; \
    elem(c,f,i1)              ; \
    d <- o + 1                ; \
    e <- g                    ; \
    call(memcpy)              ; \
    o <- o + g + 1            ; \
    popall(c,d,e,f,g)         ; \
    //

// c <- base
// d <- number of elements
// e <- size of element
// f <- comparator
    .global qsort
qsort:
    pushall(h,i,j,k,l,m)
    h <- d < 2                  // test for base case
    jnzrel(h,L_qsort_done)
    h <- d >> 1                 // H is partition index
    i <- d - 1                  // I is last index
    // partitioning
    swap(h,i)
    m <- 0                      // M is store index
    j <- 0                      // J is i index

L_qsort_partition:
    elem(k, c, j)
    elem(l, c, j)
    pushall(c,d,e)
    c <- k
    d <- l
    callr(f)
    popall(c,d,e)
    k <- b < 0
    jzrel(k,L_qsort_noswap)
    swap(j,m)
    m <- m + 1
L_qsort_noswap:

    j <- j + 1
    k <- j < i
    jnzrel(k,L_qsort_partition)

    swap(j,i)
L_qsort_done:
    popall(h,i,j,k,l,m)
    ret

// c <- pointer to key
// d <- pointer to element
// b -> < 0, 0, > 0
inteq:
    c <- [c]
    d <- [d]
    b <- c - d<commit_msg>Working qsort() in tenyr<commit_after>#include "common.th"

    .global main
main:
    prologue

#define DATA_LEN (.L_data_end - .L_data_start)
#define ELT_LEN  (.L_data_elt_end - .L_data_elt_start)

    c <- rel(data_start)        // data to sort
    d <- (DATA_LEN / ELT_LEN)   // number of elements
    e <- ELT_LEN                // size of each element
    f <- rel(inteq)             // comparator
    call(qsort)

done:
    i <- .L_data_start
print_loop:
    c <- [i - (. + 0) + p]      // get second field of struct
    c <-  c - (. + 1) + p       // and relocate it
    call(puts)
    c <- rel(nl)
    call(puts)
    i <- i + ELT_LEN
    c <- i < .L_data_end
    jnzrel(c,print_loop)

    illegal

#define elem(Dest, Base, Index) \
    Dest <- E * Index         ; \
    Dest <- Dest + Base       ; \
    //

// TODO convert swap to a function ?
// XXX swap() macros is not param-safe
#define swap(i0, i1)            \
    pushall(c,d,e,f,g)        ; \
    f <- c                    ; \
    g <- e                    ; \
    o <- o - e - 1            ; \
    c <- o + 1                ; \
    elem(d,f,i0)              ; \
    /* E is already width */  ; \
    call(memcpy)              ; \
    elem(c,f,i0)              ; \
    elem(d,f,i1)              ; \
    e <- g                    ; \
    call(memcpy)              ; \
    elem(c,f,i1)              ; \
    d <- o + 1                ; \
    e <- g                    ; \
    call(memcpy)              ; \
    o <- o + g + 1            ; \
    popall(c,d,e,f,g)         ; \
    //

// c <- base
// d <- number of elements
// e <- size of element
// f <- comparator
#define SI M
#define II J
#define PI H
#define LI I
#define BASE C

    .global qsort
qsort:
    pushall(h,i,j,k,l,m)
    h <- d < 2                  // test for base case
    jnzrel(h,L_qsort_done)
    PI <- d >> 1                // partition index
    LI <- d - 1                 // last index
    // partitioning
    swap(h,i)
    SI <- 0                     // store index
    II <- 0                     // i index

L_qsort_partition:
    k <- II < LI
    jzrel(k,L_qsort_partition_done)
    elem(k, BASE, II)
    elem(l, BASE, LI)
    pushall(c,d,e)
    c <- k
    d <- l
    callr(f)                    // call comparator
    popall(c,d,e)
    k <- b < 0
    jzrel(k,L_qsort_noswap)
    swap(II,SI)
    SI <- SI + 1
L_qsort_noswap:
    II <- II + 1
    goto(L_qsort_partition)

L_qsort_partition_done:
    swap(SI,LI)
    PI <- SI

    // recursive cases
    pushall(c,d,e,f)
    /* C is already elem(c,c,0) */
    d <- PI
    call(qsort)
    popall(c,d,e,f)

    pushall(c,d,e,f)
    d <- LI - PI
    PI <- PI + 1
    elem(k,BASE,PI)
    c <- k
    call(qsort)
    popall(c,d,e,f)

L_qsort_done:
    popall(h,i,j,k,l,m)
    ret

// c <- pointer to key
// d <- pointer to element
// b -> < 0, 0, > 0
inteq:
    c <- [c]
    d <- [d]
    b <- c - d
{'fraction_non_alphanumeric': 0.14761270686703443, 'fraction_numerical': 0.00913068289899182, 'mean_word_length': 1.097327483047467, 'pattern_counts': {'":': 0, '<': 98, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '4691574', 'n_tokens_mistral': 2162, 'n_tokens_neox': 1986, 'n_words': 492}