10
\$\begingroup\$

Input

A string S of length between 10 and 16 inclusive. The characters are taken from the 95 printable ASCII characters, byte values 32 (0x20) to 126 (0x7E) ( to ~)

Output

Your code must compute and output all strings within Levenshtein distance 2 of S. You can have duplicates as long as you also have all the different strings and the output can be in any order.

Scoring

I will generate a set of 5 strings of random lengths between 10 and 16, each consisting of a selection of printable ASCII characters. Each answer will be tested on the same set of strings, and your score is the total runtime over all 5, when run on my computer (spec details below). This means you need to give me simple and complete instructions on how to compile and run your code in Linux.

Example

Input string obenquillo. Using my test code the first output string is 8benquifllo and the last is o^be9quillo. There are 1871386 different strings in the output.

My PC

I have an AMD Ryzen 5 3400G running Ubuntu 20.04.

Winning

The fastest code wins.

League table

  • My test Python code. 14.00s
  • C++ by the default. 0.15s. Bounty awarded.
  • C by ngn. 0.07s
  • Python by ReedsShorts sped up by ovs. 10.5s
  • Rust by wizzwizz4 . 2.45s
\$\endgroup\$
22
  • 4
    \$\begingroup\$ For fastest code, you typically need to define computer architecture details, so people can optimize. Take a look at recent fastest-code challenges \$\endgroup\$ – Luis Mendo Dec 26 '20 at 17:22
  • 2
    \$\begingroup\$ Also, I'm not sure if this was posting in the Sandbox, but if not, I'd suggest posting future questions there first for feedback before posting on the main site \$\endgroup\$ – caird coinheringaahing Dec 26 '20 at 17:33
  • 1
    \$\begingroup\$ @cairdcoinheringaahing Ignoring lengths other than 10 would be optimizing for the given test cases \$\endgroup\$ – pppery Dec 26 '20 at 17:35
  • 1
    \$\begingroup\$ Does "within Levenshtein distance 2" mean the Levenshtein distance is at most 2 or exactly 2? \$\endgroup\$ – wastl Dec 26 '20 at 18:00
  • 2
    \$\begingroup\$ This is a draft of an updated version of the question. The two main things I've changed are the testing set (expanded it to be 30 random strings) and the rules on the "correctness testing" (requiring answers to output all strings generated, which can be suppressed with >/dev/null when you test them). Feel free to use/modify/ignore this draft to better fit your view of the challenge, but I think this should address the issues pointed out in comments \$\endgroup\$ – caird coinheringaahing Dec 27 '20 at 15:06
12
\$\begingroup\$

C

cat >a.c <<.
#define _(a...) {return({a;});}
#define F(i,x,n,a...) for(I i=(x),n_=(n);i<n_;i++){a;}
#define i(a...) F(i,0,a)
#define j(a...) F(j,0,a)
#define k(a...) F(k,0,a)
#define I(a...) F(i,a)
#define S static
#define O const
#define mc __builtin_memcpy
#define sl __builtin_strlen
typedef void V;typedef char C;typedef int I;

#include<sys/syscall.h>
#define M1(x) #x
#define M2(x) M1(x)
#define h(x,a...) ".globl "#x";"#x":"a"mov $"M2(SYS_##x)",%rax;syscall;ret;"
asm(".globl _start;_start:pop %rdi;mov %rsp,%rsi;call main;"h(write)h(exit));I write(I,C*,I);V exit(I);
V*memcpy(V*x,O V*y,I n)_(C*a=x;O C*b=y;i(n,a[i]=b[i])a)I strlen(O C*s)_(I r=0;while(*s++)r++;r)

S O C A0=32,A1=126+1,AN=A1-A0;S C o0[1<<20],*o=o0;
S V rpt(C*a,I n,I m){m*=n;while(2*n<m){mc(a+n,a,n);n+=n;}mc(a+n,a,m-n);}
S I fd(C*s,I n,I p)_(i(p,j(n,*o++=s[j+(i<=j)]))p)
S I fc(C*s,I n,I p)_(mc(o,s,n+1);rpt(o,n+1,p*AN);I(A0,A1,j(p,o[j]=i;o+=n+1))p)
S I fi(C*s,I n,I p)_(p++;i(p,j(n+2,o[i*(n+2)+j]=s[j-(i<j)]))rpt(o,p*(n+2),AN);I(A0,A1,j(p,o[j]=i;o+=n+2))p)
I main(I c,C**v)_(S C s[32];I n=sl(v[1]);mc(s,v[1],n);s[n]=10;S typeof(fd)*f[]={fd,fc,fi};
 i(3,o=o0;I g=f[i](s,n,n);j(g*(i?AN:1),C*b=o;k(3,f[k](o0+(n+i)*j,n+i-1,j%g))write(1,b,o-b);o=b))
 exit(0);0)
.
clang -O3 -march=native -nostdlib -ffreestanding a.c && strip a.out -R .comment
time ./a.out abcdefghijklmnop >/dev/null

Try it online!

for the record, here's why this answer didn't win the bounty: https://chat.stackexchange.com/transcript/message/56646474#56646474

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Fast and incomprehensible :) \$\endgroup\$ – Anush Dec 28 '20 at 21:46
  • 1
    \$\begingroup\$ 0/10, not golfed enough. 😏 \$\endgroup\$ – EasyasPi Dec 28 '20 at 22:15
  • 4
    \$\begingroup\$ 6/9 needs lesser comments \$\endgroup\$ – Razetime Dec 29 '20 at 10:34
  • 2
    \$\begingroup\$ For anyone reading this and thinking of adding their own answers, this question is not code-golf! \$\endgroup\$ – fomin Dec 29 '20 at 10:41
6
+50
\$\begingroup\$

C++ ('C with operator overloading')

edit: no longer outputs any duplicates if the set of characters allowed for insertions and substitutions doesn't intersect with the string's character set! (further improvement will probably require something smarter)
edit2: now even less duplicates: doesn't consider cases like inserting abcd -> abbcd twice
edit3: tiny optimization in bufprint. I don't know how to optimize it further :(
edit4: optimized bufprint some more; edit5: found a better bufsize

#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>

const char rStart = 32; //for testing purposes, I often set these to 48 and 49
const char rEnd = 126;
const bool enableio = true;
const int bufsize = 524288;
//char printbuf[bufsize];
int printbuf[bufsize / 32][8]; //using a size of 24 bytes per fixed-length string caused a SIMD unaligned store and was slightly slower
int printbufi = 0;
void bufflush()
{
    if(enableio) fwrite(printbuf, 32, printbufi, stdout);
    printbufi = 0;
}
void bufprint(const char* x) //not confusing because printbuf is the print buffer and bufprint prints using the buffer
{
    //most of the time is spent in this function
    if(printbufi >= bufsize/32 - 1)
        bufflush();
    __builtin_memcpy(&printbuf[printbufi], x, 20);
    //printbuf[printbufi][5] = 0x0a0a0a0a; //not necessary! it's possible to just set these newlines in the beginning and never change them again
    printbufi++;
    //bufflush();
}
struct string //not null-terminated
{
    char data[20] = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 };
    int len;
    bool operator < (const string& rhs) const
    {
        return memcmp(data, rhs.data, 24) < 0;
    }
    bool operator == (const string& rhs) const
    {
        const uint64_t* p1 = (const uint64_t*)this, *p2 = (const uint64_t*)&rhs;
        bool eq = p1[0] == p2[0] && p1[1] == p2[1] && p1[2] == p2[2];
        return eq;
    }
    string insert(int i, char c) const
    {
        string copy;
        copy.len = len + 1;
        for(int j = 0; j < i; j++)
            copy[j] = data[j];
        for(int j = i; j < len; j++)
            copy[j+1] = data[j];
        copy[i] = c;
        return copy;
    }
    string prepend(char c) const
    {
        string copy;
        copy.len = len + 1;
        for(int j = 0; j < len; j++)
            copy[j+1] = data[j];
        copy[0] = c;
        return copy;
    }
    string pop_front() const
    {
        string copy;
        copy.len = len - 1;
        for(int j = 0; j < len-1; j++)
            copy[j] = data[j+1];
        return copy;
    }
    string erase(int i) const
    {
        string copy;
        copy.len = len - 1;
        for(int j = 0; j < i; j++)
            copy[j] = data[j];
        for(int j = i; j < len; j++)
            copy[j] = data[j+1];
        return copy;
    }
    inline char& operator[](int i)
    {
        //if(i >= len) while(true) throw "abc";
        return data[i];
    }
    void print() const
    {
        bufprint(data);
    }
};
void changeloop(string x, int skip = -2) //all strings exactly 1 change away
{
    for(int i = 0; i < x.len; i++)
    {
        if(i == skip || i == skip+1) continue;
        char oc = x[i];
        for(int nc = rStart; nc <= rEnd; nc++)
        {
            if(nc == oc) continue;
            x[i] = nc, x.print();
        }
        x[i] = oc;
    }
}
void changeloop2(string x, int skip = -2) //same with different skip
{
    for(int i = 0; i < x.len; i++)
    {
        if(i == skip) continue;
        char oc = x[i];
        for(int nc = rStart; nc <= rEnd; nc++)
        {
            if(nc == oc) continue;
            x[i] = nc, x.print();
        }
        x[i] = oc;
    }
}
void insertloop(string x, int max = INT_MAX) //all strings exactly 1 insertion away
{
    //example:
    //?abcd
    //a?bcd
    //ab?cd
    //abc?d
    //abcd?
    //it can be observed that each character simply iterates over all possible values, and then gets set to the ith character of the string
    string s = x.prepend(x[0]);
    max = std::min(max, s.len);
    for(int i = 0; i < max; i++)
    {
        for(char nc = rStart; nc <= rEnd; nc++)
        {
            if(i != 0 && x[i-1] == nc) continue;
            s[i] = nc, s.print();
        }
        if(i < x.len) s[i] = x[i];
    }
}
void deleteloop(string x, int max = INT_MAX)
{
    //example:
    //bcde
    //acde
    //abde
    //abce
    //abcd
    //erase first character, print and then copy the original character n-1 times
    string s = x.pop_front();
    s.print();
    max = std::min(max, x.len - 1);
    for(int i = 0; i < max; i++)
    {
        s[i] = x[i];
        s.print();
    }
}
void dist1(string x)
{
    x.print();
    changeloop(x);
    insertloop(x);
    deleteloop(x);
}
//options:
//insert
//insert, change
//insert, insert
//change
//change, change
//delete
//strings with distance at most 1 from delete
void dist2(string x)
{
    string s = x.prepend(x[0]);
    for(int i = 0; i < x.len+1; i++)
    {
        for(char nc = rStart; nc <= rEnd; nc++)
        {
            //string s = x.insert(i, nc);
            if(i != s.len-1 && s[i+1] == nc) continue;
            s[i] = nc;
            //s[s.len] = 0;
            s.print(); //insert
            insertloop(s, i+1); //insert, insert. only do the second insert before this one
            changeloop(s, i); //insert, change. the change can be anywhere except i and i+1
        }
        if(i < x.len) s[i] = x[i];
    }
    //changeloop(x); //change. can always be replaced by delete->reinsert
    for(int i = 0; i < x.len; i++)
    for(int j = i+1; j < x.len; j++)
    {
        char oci = x[i], ocj = x[j];
        for(int nci = rStart; nci <= rEnd; nci++)
        for(int ncj = rStart; ncj <= rEnd; ncj++)
        {
            if(nci == oci) continue;
            if(ncj == ocj) continue;
            x[i] = nci; x[j] = ncj;
            x.print(); //change, change
        }
        x[i] = oci; x[j] = ocj;
    }
    s = x.pop_front();
    s.print();
    changeloop(s);
    insertloop(s);
    for(int i = 0; i < x.len-1; i++)
    {
        s[i] = x[i];
        //s[s.len] = 0;
        s.print();
        changeloop2(s, i);
        insertloop(s);
        deleteloop(s, i); //deletion must be before i
    }
}

int main(int argc, char*argv[])
{
    if(argc < 2)
    {
        printf("input the string as a command line argument! :(\n");
        return 1;
    }
    memset(printbuf, 0x0a, sizeof(printbuf));
    string s; strcpy(s.data, argv[1]); s.len = strlen(argv[1]);
    s.data[s.len] = 10; //fix the null byte that should not be there
    //for(int i = 0; i < 200; i++)
    //{
    //  dist2(s);
    //  fprintf(stderr, "%d\r", i);
    //}
    dist2(s);
    bufflush();
}

This outputs many empty lines between strings (to avoid unaligned memory writes to the IO buffer). This outputs much fewer duplicates than the C answer: for abcdefghijklmnop the C answer outputs 10237362 lines, and my answer outputs only 4920334 4774446 4724312 non-empty lines, while only 4720038 are necessary. I compile with g++ a.cpp -std=c++17 -march=native -Ofast -no-pie -fno-stack-protector.

\$\endgroup\$
7
  • \$\begingroup\$ Could you say something about how it works ? \$\endgroup\$ – Anush Jan 1 at 9:27
  • \$\begingroup\$ @Anush I thought reading the code would be sufficient to understand how it works, but it simply tries making at most 2 modifications to the string and prints all the results. It also skips many modifications that are likely to produce duplicate results (for example, changeloop(x); in dist2 is commented out because, as the comment says, it can always be replaced by a deletion followed by inserting the modified character, and insertions are not attempted after substitutions because it's always sufficient to perform substitutions after insertions and normal insertions). \$\endgroup\$ – the default. Jan 1 at 9:35
  • \$\begingroup\$ I really like the way you have avoided duplicates. I will time this and others as soon as possible. \$\endgroup\$ – fomin Jan 1 at 17:59
  • \$\begingroup\$ Imma turn it to CUDA and see how fast it can be \$\endgroup\$ – Command Master Jan 3 at 14:42
  • 1
    \$\begingroup\$ @CommandMaster I tried puts and it outputs at around 850 MiB/s (there's a small optimization, but it probably won't push it above 900 MiB/s). Indeed, I should probably read the yes source code and the answers to Fastest yes in the west. \$\endgroup\$ – the default. Jan 3 at 15:12
4
\$\begingroup\$

Python 3

cat >a.py <<.
strs=[input()]
def a(b):
    new = []
    for x in range(32, 127):
        c = chr(x)
        for strn in b:
            for y in range(0, len(strn)):
                start = strn[:y]
                end = strn[y+1:]
                new.append(start + c + end)
                new.append(start + end)
                new.append(start + c + strn[y:])
            new.append(strn + c)
    return new
print(len(a(set(a(strs)))))
.
time python3 a.py <<<abcdefghijklmnop

Try it online!

Optimized by ovs, thanks.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Converting between strings and lists is quite slow, using string slicing and some minor optimizations, this gets twice as fast. \$\endgroup\$ – ovs Jan 1 at 16:59
4
\$\begingroup\$

Rust

Tested with rustc 1.51.0-nightly (e22670468 2020-12-30).
Must be compiled with -O1 (or above) so functions are properly inlined, or it segfaults.

Please build with cargo build, then time the binary in target/debug/q216902. It's segfaulting in release mode at the moment, and I don't know why.

Cargo.toml

[package]
name = "q216902"
version = "0.1.0"
authors = ["wizzwizz4"]
edition = "2018"

[dependencies]
rlibc = "1.0.0"

[profile.dev]
debug-assertions = true
opt-level = 1
panic = "abort"

[profile.release]
panic = "abort"
# debug = 2

main.rs

#![feature(asm)]
#![feature(const_in_array_repeat_expressions)]
#![feature(const_maybe_uninit_assume_init)]
#![feature(link_args)]
#![feature(naked_functions)]
#![feature(test)]
#![no_std]
#![no_main]

#[allow(unused_attributes)]
#[link_args = "-nostartfiles"]
extern "C" {}

extern crate rlibc;

use core::convert::TryInto;
use core::hint::{black_box, spin_loop, unreachable_unchecked};
use core::panic::PanicInfo;
use core::ptr;
use core::slice;
use core::sync::atomic::{AtomicUsize, fence, Ordering};
use core::mem::MaybeUninit;

static PRINTABLES: [u8; 95] = *b" !\"#$%&'()*+,-./0123456789:;<=>?\
                                  @ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_\
                                  `abcdefghijklmnopqrstuvwxyz{|}~";
const FRAMECOUNT: usize = 4;
static mut FRAMES: [Frame; FRAMECOUNT] = [
    unsafe { MaybeUninit::<Frame>::uninit().assume_init() }; FRAMECOUNT
];

static FRAMELENS: [AtomicUsize; FRAMECOUNT] = [
    AtomicUsize::new(0); FRAMECOUNT
];

#[repr(C)]
struct iovec {
    iov_base: *const u8,
    iov_len: usize
}

const FRAMESIZE: usize = 256;
#[repr(C)]
struct Frame {
    iovecs: [MaybeUninit<iovec>; FRAMESIZE]
}

#[no_mangle]
#[naked]
pub unsafe extern "C" fn _start() -> ! {
    // Escape naked without clobbering stack pointer
    // https://fasterthanli.me/series/making-our-own-executable-packer/part-12
    asm!(
        "mov rdi, rsp",
        "call main",
        options(noreturn)
    );
}

#[no_mangle]
pub extern "C" fn main(stack: *const u8) -> ! {
    let input: &'static [u8] = unsafe {
        let arg1 = *stack.offset(16).cast();
        slice::from_raw_parts(arg1, cstr_strlen_cheat(arg1))
    };
    unsafe {
        spawn_printer();
    }

    let mut frame_i = 0;
    let mut frame_j = 0;
    let mut frame = unsafe { get_frame(0) };

    macro_rules! main_write {
        (@iovec $iov: expr) => {{
            frame.iovecs[frame_j] = MaybeUninit::new($iov);
            frame_j += 1;
            if frame_j > FRAMESIZE {
                unsafe { unreachable_unchecked(); }
            }
            if frame_j == FRAMESIZE {
                unsafe { write_frame(frame, frame_i, FRAMESIZE); }
                frame_j = 0;
                frame_i += 1;
                frame_i %= FRAMECOUNT;
                frame = unsafe { get_frame(frame_i) };
            }
        }};

        (@single $slice: expr) => {{
            main_write!(
                @iovec
                iovec {
                    iov_base: &$slice[0],
                    iov_len: $slice.len()
                }
            );
        }};

        ($($x: expr),*) => {{
            $(
                main_write!(@single $x);
            )*
        }};
    }

    macro_rules! main_writeln {
        ($($x: tt)*) => {{
            main_write!($($x)*);
            main_write!(b"\n");
        }};
    }

    ///////////
    // No-op ///
    //   No-op
    // Insert //
    //   I.
    //   .I.
    //   .I
    // Delete /////////
    //   Predel
    //   Delete
    //   Appdel
    // Insert insert //
    //   II.
    //   I.I.
    //   I.I
    //   .II.
    //   .I.I.
    //   Insert append
    //   Append append
    // Insert delete ////// (also includes Substitute)
    //   Prepend predel
    //   Prepend delete
    //   I.D
    //   Insert predel
    //   Insert delete
    //     .I.D.
    //     .S.
    //     .D.I.
    //   Insert appdel
    //   D.I
    //   Append delete
    //   .S
    // Insert substitute //////
    //   IS.
    //   I.S.
    //   Prepend substappend
    //   S.I.
    //   .SI.
    //   .S.I.
    //   Insert substitute
    //   .I.S
    //   Subsprepend append
    //   .S.I
    //   .SI
    // Substitute substitute //
    //   SS.
    //   .SS.
    //   .SS
    //   S.S
    //   S.S.
    //   .S.S.
    //   .S.S
    // Delete delete //////////
    //   Del2 XX.
    //   Del2 .XX.
    //   Del2 .XX
    //   Del2 X.X
    //   Del2 X.X.
    //   Del2 .X.X.
    //   Del2 .X.X
    // Delete substitute //
    //   DS.
    //   .DS.
    //   .DS
    //   D.S
    //   S.D
    //   D.S.
    //   S.D.
    //   .D.S.
    //   .S.D.
    //   .D.S
    //   .S.D
    ///////////////////////

    let len = input.len();

    main_writeln!(input);  // No-op
    main_writeln!(input[1..]);  // Predel
    main_writeln!(input[2..]);  // Del2 XX.
    main_writeln!(input[.. len-1]);  // Appdel
    main_writeln!(input[.. len-2]);  // Del2 .XX
    main_writeln!(input[1 .. len-1]);  // Del2 X.X

    for i in 1 .. len-1 {
        main_writeln!(input[..i], input[i + 1..]);  // Delete
    }

    for i in 1 .. len-2 {
        main_writeln!(input[..i], input[i+2 ..]);  // Del2 .XX.
        main_writeln!(input[1 .. i+1], input[i+2 ..]);  // Del2 X.X.
        main_writeln!(input[..i], input[i+1 .. len-1]); // Del2 .X.X

        for j in i+2 .. len-1 {
            // Del2 .X.X.
            main_writeln!(input[..i], input[i+1 .. j], input[j+1 ..]);
        }
    }

    for ai in 0..PRINTABLES.len() {
        let a = &PRINTABLES[ai .. ai+1];

        main_writeln!(a, input);  // I.
        main_writeln!(input, a);  // .I

        for i in 1..len {
            main_writeln!(input[..i], a, input[i..]);  // .I.
        }

        for bi in 0..PRINTABLES.len() {
            let b = &PRINTABLES[bi..bi + 1];

            main_writeln!(a, b, input);  // II.
            main_writeln!(a, b, input[1..]);  // IS.
            main_writeln!(a, b, input[2..]);  // SS.
            main_writeln!(a, input, b);  // I.I
            main_writeln!(a, input[.. len-1], b);  // Prepend substappend
            main_writeln!(a, input[1 ..], b); // Subsprepend append
            main_writeln!(a, input[1 .. len-1], b); // S.S
            main_writeln!(input, a, b);  // Append append
            main_writeln!(input[.. len-1], a, b);  // .SI
            main_writeln!(input[.. len-2], a, b);  // .SS
            
            for i in 1..len {
                main_writeln!(a, input[..i], b, input[i..]);  // I.I.
                main_writeln!(input[..i], a, input[i..], b);  // Insert append
                main_writeln!(input[..i], a, b, input[i..]);  // .II.
            }

            for i in 1 .. len-1 {
                main_writeln!(a, input[..i], b, input[i+1 ..]);  // I.S.
                main_writeln!(a, input[1 .. i+1], b, input[i+1 ..]); // S.I.
                main_writeln!(input[..i], a, input[i .. len-1], b); // .I.S
                main_writeln!(input[..i], a, b, input[i+1..]);  // .SI.

                for j in i+1 .. len {
                    // .I.I.
                    main_writeln!(input[..i], a, input[i..j], b, input[j..]);
                }

                for j in i+2 .. len {
                    // .S.I.
                    main_writeln!(
                        input[..i], a, input[i+1 .. j], b, input[j..]
                    );
                }

                for j in i+2 .. len-1 {
                    // .S.S.
                    main_writeln!(
                        input[..i], a, input[i+1 .. j], b, input[j+1 ..]
                    );
                }

                for j in 1..i {
                    // Insert substitute
                    main_writeln!(input[..j], a, input[j..i], b, input[i+1..]);
                }

                main_writeln!(input[..i], a, input[i+1 ..], b);  // .S.I
            }

            for i in 1 .. len-2 {
                main_writeln!(input[..i], a, b, input[i+2 ..]);  // .SS.
                main_writeln!(a, input[1 .. i+1], b, input[i+2 ..]);  // S.S.
                main_writeln!(input[..i], a, input[i+1 .. len-1], b);  // .S.S
            }
        }

        main_writeln!(a, input[1..]);  // Prepend predel
        main_writeln!(a, input[2..]);  // DS.
        main_writeln!(a, input[.. len-1]);  // I.D
        main_writeln!(a, input[1 .. len-1]);  // S.D
        main_writeln!(input[1..], a);  // D.I
        main_writeln!(input[1 .. len-1], a);  // D.S
        main_writeln!(input[.. len-1], a);  // .S
        main_writeln!(input[.. len-2], a);  // .DS

        for i in 1..input.len() - 1 {
            main_writeln!(a, input[..i], input[i+1 ..]);  // Prepend delete
            main_writeln!(input[..i], input[i+1 ..], a);  // Append delete
            main_writeln!(input[1 .. i+1], a, input[i+1 ..]); // Insert predel
            main_writeln!(input[..i], a, input[i .. len-1]);  // Insert appdel
            main_writeln!(input[..i], a, input[i+1 ..]);  // .S.

            for j in 1..i {
                // .I.D.
                main_writeln!(input[..j], a, input[j..i], input[i+1 ..]);
            }

            for j in i+2..len {
                // .D.I.
                main_writeln!(input[..i], input[i+1 .. j], a, input[j..]);
            }
        }

        for i in 1 .. len-2 {
            main_writeln!(input[..i], a, input[i+2 ..]);  // .DS.
            main_writeln!(input[1 .. i+1], a, input[i+2 ..]);  // D.S.
            main_writeln!(a, input[1 .. i+1], input[i+2 ..]);  // S.D.
            main_writeln!(input[..i], input[i+1 .. len-1], a);  // .D.S
            main_writeln!(input[..i], a, input[i+1 .. len-1]); // .S.D

            for j in i+2 .. len-1 {
                // .D.S.
                main_writeln!(input[..i], input[i+1 .. j], a, input[j+1 ..]);

                // .S.D.
                main_writeln!(input[..i], a, input[i+1 .. j], input[j+1 ..]);
            }
        }
    }

    unsafe { write_frame(frame, frame_i, frame_j); }

    while FRAMELENS[frame_i].load(Ordering::SeqCst) > 0 {
        sched_yield();
    }
    unsafe { exit_group(0); }
}

/// strlen, if the string's length is >= 10 and <= 16.
#[inline]
unsafe fn cstr_strlen_cheat(ptr: *const u8) -> usize {
    for i in 10..=16 {
        if *ptr.offset(i) == 0 {
            match i.try_into() {
                Ok::<usize, _>(i) => return i,
                Err(_) => unreachable_unchecked()
            }
        }
    }
    unreachable_unchecked();
}

/// Gets a frame for writing, assuming nobody else has it.
#[inline]
unsafe fn get_frame(i: usize) -> &'static mut Frame {
    loop {
        let count = FRAMELENS[i].load(Ordering::SeqCst);
        if count == 0 {
            break;
        }
        sched_yield();
    }
    &mut FRAMES[i]
}

#[inline]
unsafe fn write_frame(_frame: &'static mut Frame, i: usize, count: usize) {
    FRAMELENS[i].store(count, Ordering::SeqCst);
}

#[inline(never)]  // for correctness
unsafe extern "C" fn spawn_printer() {
    let stack_pointer: *const u8;
    asm!(
        "mov {0}, rsp",
        out(reg) stack_pointer
    );
    let new_stack = stack_pointer.offset(-0x1000);
    let spawn_addr = (new_stack as *mut (extern "C" fn() -> !)).offset(1);
    ptr::write(spawn_addr, printer);
    clone(new_stack)
}

extern "C" fn printer() -> ! {
    loop {
        for i in 0..FRAMECOUNT {
            let mut count;
            loop {
                count = FRAMELENS[i].load(Ordering::SeqCst);
                if count > 0 {
                    break;
                }
                // sched_yield();
            }
            fence(Ordering::SeqCst);
            unsafe {
                writev((&FRAMES[i].iovecs[0]).as_ptr().cast(), count);
            }
            FRAMELENS[i].store(0, Ordering::SeqCst);
        }
    }
}

// https://thevivekpandey.github.io/posts/2017-09-25-linux-system-calls.html
#[inline]
unsafe fn writev(iovecs: *const iovec, count: usize) {
    asm!(
        "syscall",
        in("rax") 20,
        in("rdi") 1,
        in("rsi") iovecs,
        in("rdx") count,
        options(nostack)
    );
}

#[inline]
fn exit(code: i32) -> ! {
    unsafe {
        asm!(
            "syscall",
            in("rax") 60,
            in("rdi") code,
            options(nostack, noreturn)
        );
    }
}

#[inline]
unsafe fn exit_group(code: i32) -> ! {
    asm!(
        "syscall",
        in("rax") 231,
        in("rdi") code,
        options(nostack, noreturn)
    );
}

#[inline]
unsafe fn just_exit() -> ! {
    asm!(
        "syscall",
        in("rax") 231,
        options(nostack, noreturn)
    )
}

#[inline]
fn sched_yield() {
    unsafe {
        asm!(
            "syscall",
            in("rax") 24,
            options(nostack)
        )
    }
}

/// Wait for signal.
#[inline]
fn pause() {
    unsafe {
        asm!(
            "syscall",
            in("rax") 34,
            options(nostack)
        )
    }
}

#[inline(always)]  // for correctness
unsafe fn clone(new_stack: *const u8) {
    const CLONE_FILES: u64 = 0x400;  // Keep stdout as fd 1
    const CLONE_FS: u64 = 0x200;
    const CLONE_IO: u64 = 0x80000000;  // I/O scheduling efficiency
    const CLONE_PARENT: u64 = 0x8000;
    const CLONE_SIGHAND: u64 = 0x800;
    const CLONE_THREAD: u64 = 0x10000;  // Same thread group
    const CLONE_VM: u64 = 0x100;  // Same memory map
    
    const flags: u64 = CLONE_FILES | CLONE_IO
                       | CLONE_VM
                       | CLONE_THREAD
                       | CLONE_FS | CLONE_PARENT | CLONE_SIGHAND;
    asm!(
        "syscall",
        in("rax") 56,
        in("rdi") flags,
        in("rsi") new_stack,
        options(nostack)
    );
    return;
}

#[panic_handler]
fn panic(_info: &PanicInfo) -> ! {
    unsafe {
        if cfg!(debug_assertions) {
            // just_exit();
        }
        // unreachable_unchecked();
        asm!(
            "ud2",
            options(nostack, noreturn)
        )
    }
}

This is cleaner code; I'm making a better version, hopefully less segfaulty in release mode. I also haven't tweaked the FRAMECOUNT and FRAMESIZE parameters for optimal speed.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.