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.
>/dev/nullwhen 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\$