diff options
Diffstat (limited to 'lib')
66 files changed, 5057 insertions, 0 deletions
diff --git a/lib/cxx_abi.cc b/lib/cxx_abi.cc new file mode 100644 index 0000000..872b4a2 --- /dev/null +++ b/lib/cxx_abi.cc @@ -0,0 +1,37 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +/* + * cxx_abi.cc — Minimal C++ ABI stubs for freestanding kernel + * + * Provides symbols that the compiler/linker expects from the C++ + * runtime library. All error paths are fatal (kernel_panic). + * + * Reference: docs/specs/cpp_runtime.md + */ + +#include <lume/klog.h> + +/* Pure virtual function call trap. + * Generated by the compiler in vtable entries for pure virtual methods. + * Reaching this means a derived class failed to implement a pure virtual. */ +extern "C" void __cxa_pure_virtual() +{ + kernel_panic("pure virtual function call"); +} + +/* Global destructor registration. + * The kernel does not support global object destruction — all global + * objects use Placement New with explicit lifetime management. + * If the compiler emits a call to this, it indicates a code violation. */ +extern "C" int __cxa_atexit(void (*)(void*), void*, void*) +{ + kernel_panic("__cxa_atexit called in kernel"); + return 0; // unreachable +} + +/* DSO handle — required by __cxa_atexit ABI. + * The kernel is statically linked; this symbol just needs to exist. */ +extern "C" { +void* __dso_handle __attribute__((visibility("hidden"))) = nullptr; +} diff --git a/lib/fdt.c b/lib/fdt.c new file mode 100644 index 0000000..1b20383 --- /dev/null +++ b/lib/fdt.c @@ -0,0 +1,2 @@ +#include <lume/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt.c" diff --git a/lib/fdt_addresses.c b/lib/fdt_addresses.c new file mode 100644 index 0000000..d58f896 --- /dev/null +++ b/lib/fdt_addresses.c @@ -0,0 +1,2 @@ +#include <lume/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_addresses.c" diff --git a/lib/fdt_empty_tree.c b/lib/fdt_empty_tree.c new file mode 100644 index 0000000..37f8ef8 --- /dev/null +++ b/lib/fdt_empty_tree.c @@ -0,0 +1,2 @@ +#include <lume/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_empty_tree.c" diff --git a/lib/fdt_ro.c b/lib/fdt_ro.c new file mode 100644 index 0000000..3599d49 --- /dev/null +++ b/lib/fdt_ro.c @@ -0,0 +1,2 @@ +#include <lume/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_ro.c" diff --git a/lib/fdt_rw.c b/lib/fdt_rw.c new file mode 100644 index 0000000..65d7a71 --- /dev/null +++ b/lib/fdt_rw.c @@ -0,0 +1,2 @@ +#include <lume/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_rw.c" diff --git a/lib/fdt_strerror.c b/lib/fdt_strerror.c new file mode 100644 index 0000000..dae35ea --- /dev/null +++ b/lib/fdt_strerror.c @@ -0,0 +1,2 @@ +#include <lume/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_strerror.c" diff --git a/lib/fdt_sw.c b/lib/fdt_sw.c new file mode 100644 index 0000000..d04f220 --- /dev/null +++ b/lib/fdt_sw.c @@ -0,0 +1,2 @@ +#include <lume/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_sw.c" diff --git a/lib/fdt_wip.c b/lib/fdt_wip.c new file mode 100644 index 0000000..ebfb3c1 --- /dev/null +++ b/lib/fdt_wip.c @@ -0,0 +1,2 @@ +#include <lume/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_wip.c" diff --git a/lib/klog.cc b/lib/klog.cc new file mode 100644 index 0000000..86c67f8 --- /dev/null +++ b/lib/klog.cc @@ -0,0 +1,574 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +/* + * klog.cc — Kernel logging subsystem implementation + * + * Implements the ring buffer, spinlock-protected writes, log level + * filtering, and synchronous console output. + * + * Phase 2 TODO: async flush via kernel thread (see docs/specs/klog.md) + */ + +#include <lume/klog.h> +#include <lume/kprintf.h> +#include <lume/console.h> +#include <lume/atomic.h> +#include <kernel/sync/spinlock.h> +#include <arch/cpu.h> + +/* Forward declaration — mpaland/printf */ +extern "C" int vsnprintf_(char* buffer, size_t count, + const char* format, __builtin_va_list va); + +/* ======================================================================== + * Ring Buffer State + * ======================================================================== */ + +struct KlogEntryHdr { + uint32 seq; + uint32 len; + uint64 ts; + uint16 cpu; + uint8 level; + uint8 subsys; + uint16 reserved; +}; + +static struct { + char data[KLOG_BUF_SIZE]; + uint32 head; /* Next write position */ + uint32 tail; /* Next read position (for /proc/kmsg) */ + uint32 console_tail; /* Next position to flush to console */ + uint32 dropped; + lume::atomic<uint32> seq; + uint64 subsys_mask; + Spinlock lock; + KlogLevel console_level; /* Messages <= this level go to UART */ + bool initialized; + bool panic_mode; +} g_klog; + +/* ======================================================================== + * Level name table + * ======================================================================== */ + +static const char* klog_level_name(KlogLevel level) +{ + static const char* names[] = { + "EMERG", "ALERT", "CRIT", "ERR", + "WARN", "NOTICE", "INFO", "DEBUG" + }; + if (level <= KLOG_DEBUG) { + return names[level]; + } + return "?"; +} + +static const char* klog_subsys_name(KlogSubsys subsys) +{ + static const char* names[] = { + "GEN", + "SCHED", + "TRAP", + "IRQ", + "TIMER", + "VMM", + "PMM", + "SLAB", + "FS", + "DRV", + "TEST", + }; + if (subsys < KLOG_SUBSYS_MAX) { + return names[subsys]; + } + return "?"; +} + +static const char* parse_kern_level(const char* fmt, KlogLevel* level) +{ + if (!fmt || !level) { + return fmt; + } + + /* Linux-style "\001n" prefix (KERN_SOH) */ + if (fmt[0] == '\001' && fmt[1] >= '0' && fmt[1] <= '7') { + *level = static_cast<KlogLevel>(fmt[1] - '0'); + return fmt + 2; + } + + /* Alternate "<n>" prefix */ + if (fmt[0] == '<' && fmt[1] >= '0' && fmt[1] <= '7' && fmt[2] == '>') { + *level = static_cast<KlogLevel>(fmt[1] - '0'); + return fmt + 3; + } + + return fmt; +} + +/* ======================================================================== + * Ring Buffer Operations + * ======================================================================== */ + +/* Write a byte to the ring buffer. Overwrites oldest data on overflow. */ +static inline uint32 min_u32(uint32 a, uint32 b) +{ + return (a < b) ? a : b; +} + +static void ring_write_bytes(const void* src, uint32 len) +{ + const char* p = reinterpret_cast<const char*>(src); + for (uint32 i = 0; i < len; ++i) { + g_klog.data[(g_klog.head + i) & (KLOG_BUF_SIZE - 1)] = p[i]; + } + g_klog.head += len; +} + +static void ring_read_bytes(uint32 pos, void* dst, uint32 len) +{ + char* out = reinterpret_cast<char*>(dst); + for (uint32 i = 0; i < len; ++i) { + out[i] = g_klog.data[(pos + i) & (KLOG_BUF_SIZE - 1)]; + } +} + +static void ring_drop_oldest(uint32 needed) +{ + uint32 min_tail = min_u32(g_klog.tail, g_klog.console_tail); + + while (KLOG_BUF_SIZE - (g_klog.head - min_tail) < needed) { + KlogEntryHdr hdr; + ring_read_bytes(min_tail, &hdr, sizeof(hdr)); + + uint32 entry = sizeof(hdr) + hdr.len; + if (entry == 0 || entry > KLOG_BUF_SIZE) { + min_tail++; + g_klog.dropped++; + continue; + } + min_tail += entry; + g_klog.dropped++; + } + + if (g_klog.tail < min_tail) { + g_klog.tail = min_tail; + } + if (g_klog.console_tail < min_tail) { + g_klog.console_tail = min_tail; + } +} + +/* ======================================================================== + * Console Output (synchronous) + * ======================================================================== */ + +static void console_emit(const char* s, int len) +{ + console_write_all(s, len); +} + +static int klog_format_line(char* out, int out_size, + const KlogEntryHdr& hdr, + const char* msg, int msg_len) +{ + const char* lvl = klog_level_name(static_cast<KlogLevel>(hdr.level)); + const char* subsys = klog_subsys_name(static_cast<KlogSubsys>(hdr.subsys)); + + int prefix = ksnprintf(out, out_size, + "[%s][cpu%u][%llu][%s] ", + lvl, (uint32)hdr.cpu, + (unsigned long long)hdr.ts, subsys); + if (prefix < 0) { + return 0; + } + + int total = prefix; + int avail = out_size - 1 - total; + if (avail > 0) { + int to_copy = (msg_len < avail) ? msg_len : avail; + for (int i = 0; i < to_copy; ++i) { + out[total + i] = msg[i]; + } + total += to_copy; + } + + if (total > 0 && out[total - 1] != '\n' && total < out_size - 1) { + out[total++] = '\n'; + } + + out[total] = '\0'; + return total; +} + +static int klog_read_internal(char* buf, int size, uint32* tail_ptr, bool consume) +{ + if (size <= 0) { + return 0; + } + + int written = 0; + uint32 pos = *tail_ptr; + + while (pos != g_klog.head) { + KlogEntryHdr hdr; + ring_read_bytes(pos, &hdr, sizeof(hdr)); + uint32 raw_len = hdr.len; + if (raw_len > KLOG_BUF_SIZE) { + break; + } + uint32 copy_len = raw_len; + if (copy_len > KLOG_LINE_MAX) { + copy_len = KLOG_LINE_MAX; + } + + char msg[KLOG_LINE_MAX + 1]; + ring_read_bytes(pos + sizeof(hdr), msg, copy_len); + msg[copy_len] = '\0'; + + char line[KLOG_LINE_MAX + 64]; + int line_len = klog_format_line(line, sizeof(line), hdr, msg, + static_cast<int>(copy_len)); + + if (line_len <= 0 || written + line_len > size) { + break; + } + + for (int i = 0; i < line_len; ++i) { + buf[written + i] = line[i]; + } + written += line_len; + + pos += sizeof(hdr) + raw_len; + } + + if (consume) { + *tail_ptr = pos; + } + + return written; +} + +static void klog_vex(KlogLevel level, KlogSubsys subsys, + const char* fmt, __builtin_va_list va); + +/* ======================================================================== + * Public API + * ======================================================================== */ + +void klog_init(void) +{ + g_klog.head = 0; + g_klog.tail = 0; + g_klog.console_tail = 0; + g_klog.dropped = 0; + g_klog.seq.store(0, __ATOMIC_RELAXED); + g_klog.subsys_mask = (1ULL << KLOG_SUBSYS_MAX) - 1; + g_klog.console_level = static_cast<KlogLevel>(KLOG_DEFAULT_LEVEL); + g_klog.initialized = true; + g_klog.panic_mode = false; + g_klog.lock.init("klog"); +} + +void klog(KlogLevel level, const char* fmt, ...) +{ + __builtin_va_list va; + __builtin_va_start(va, fmt); + klog_vex(level, KLOG_SUBSYS_GENERIC, fmt, va); + __builtin_va_end(va); +} + +void klog_ex(KlogLevel level, KlogSubsys subsys, const char* fmt, ...) +{ + __builtin_va_list va; + __builtin_va_start(va, fmt); + klog_vex(level, subsys, fmt, va); + __builtin_va_end(va); +} + +static void klog_vex(KlogLevel level, KlogSubsys subsys, + const char* fmt, __builtin_va_list va) +{ + if (subsys >= KLOG_SUBSYS_MAX) { + subsys = KLOG_SUBSYS_GENERIC; + } + + if (g_klog.initialized && ((g_klog.subsys_mask & (1ULL << subsys)) == 0)) { + return; + } + + char msg[KLOG_LINE_MAX + 1]; + int msg_len = vsnprintf_(msg, KLOG_LINE_MAX, fmt, va); + + if (msg_len < 0) { + return; + } + if (msg_len > KLOG_LINE_MAX) { + msg_len = KLOG_LINE_MAX; + } + msg[msg_len] = '\0'; + + KlogEntryHdr hdr; + hdr.seq = g_klog.seq.fetch_add(1, __ATOMIC_RELAXED); + hdr.len = static_cast<uint32>(msg_len); + hdr.ts = arch::cpu::read_time(); + hdr.cpu = static_cast<uint16>(arch::cpu::id()); + hdr.level = static_cast<uint8>(level); + hdr.subsys = static_cast<uint8>(subsys); + hdr.reserved = 0; + + bool do_console = (!g_klog.initialized || level <= g_klog.console_level); + + if (g_klog.initialized && !g_klog.panic_mode) { + LockGuard guard(g_klog.lock); + ring_drop_oldest(sizeof(hdr) + hdr.len); + ring_write_bytes(&hdr, sizeof(hdr)); + ring_write_bytes(msg, hdr.len); + if (do_console) { + g_klog.console_tail = g_klog.head; + /* Emit to UART while holding the lock to prevent + * interleaved output from concurrent CPUs. */ + char line[KLOG_LINE_MAX + 64]; + int line_len = klog_format_line(line, sizeof(line), + hdr, msg, hdr.len); + if (line_len > 0) { + console_emit(line, line_len); + } + } + } else if (do_console) { + /* Pre-init or panic mode: emit without lock */ + char line[KLOG_LINE_MAX + 64]; + int line_len = klog_format_line(line, sizeof(line), + hdr, msg, hdr.len); + if (line_len > 0) { + console_emit(line, line_len); + } + } +} + +int vprintk(const char* fmt, __builtin_va_list va) +{ + KlogLevel level = KLOG_INFO; + const char* real_fmt = parse_kern_level(fmt, &level); + + __builtin_va_list va_copy; + __builtin_va_copy(va_copy, va); + + char tmp[KLOG_LINE_MAX + 1]; + int len = vsnprintf_(tmp, KLOG_LINE_MAX, real_fmt, va_copy); + __builtin_va_end(va_copy); + + klog_vex(level, KLOG_SUBSYS_GENERIC, real_fmt, va); + + if (len < 0) { + return 0; + } + return len; +} + +int printk(const char* fmt, ...) +{ + __builtin_va_list va; + __builtin_va_start(va, fmt); + int ret = vprintk(fmt, va); + __builtin_va_end(va); + return ret; +} + +void klog_set_level(KlogLevel level) +{ + g_klog.console_level = level; +} + +void klog_set_subsys_mask(uint64 mask) +{ + g_klog.subsys_mask = mask; +} + +void klog_enable_subsys(KlogSubsys subsys) +{ + if (subsys < KLOG_SUBSYS_MAX) { + g_klog.subsys_mask |= (1ULL << subsys); + } +} + +void klog_disable_subsys(KlogSubsys subsys) +{ + if (subsys < KLOG_SUBSYS_MAX) { + g_klog.subsys_mask &= ~(1ULL << subsys); + } +} + +int klog_read(char* buf, int size) +{ + if (!g_klog.initialized || size <= 0) { + return 0; + } + + LockGuard guard(g_klog.lock); + return klog_read_internal(buf, size, &g_klog.tail, false); +} + +int klog_read_consume(char* buf, int size) +{ + if (!g_klog.initialized || size <= 0) { + return 0; + } + + LockGuard guard(g_klog.lock); + return klog_read_internal(buf, size, &g_klog.tail, true); +} + +void klog_flush(void) +{ + if (!g_klog.initialized) { + return; + } + + LockGuard guard(g_klog.lock); + + uint32 pos = g_klog.console_tail; + while (pos != g_klog.head) { + KlogEntryHdr hdr; + ring_read_bytes(pos, &hdr, sizeof(hdr)); + uint32 raw_len = hdr.len; + if (raw_len > KLOG_BUF_SIZE) { + break; + } + uint32 copy_len = raw_len; + if (copy_len > KLOG_LINE_MAX) { + copy_len = KLOG_LINE_MAX; + } + + char msg[KLOG_LINE_MAX + 1]; + ring_read_bytes(pos + sizeof(hdr), msg, copy_len); + msg[copy_len] = '\0'; + + char line[KLOG_LINE_MAX + 64]; + int line_len = klog_format_line(line, sizeof(line), hdr, msg, + static_cast<int>(copy_len)); + if (line_len > 0) { + console_emit(line, line_len); + } + + pos += sizeof(hdr) + raw_len; + } + + g_klog.console_tail = pos; +} + +bool klog_ratelimit(KlogRateLimit* rl, uint64 now) +{ + if (!rl) { + return true; + } + + if (rl->interval == 0 || rl->burst == 0) { + return true; + } + + if (now - rl->last_ts >= rl->interval) { + rl->last_ts = now; + rl->printed = 0; + rl->suppressed = 0; + } + + if (rl->printed < rl->burst) { + rl->printed++; + return true; + } + + rl->suppressed++; + return false; +} + +void klog_stats(KlogStats* out) +{ + if (!out) { + return; + } + + out->head = g_klog.head; + out->tail = g_klog.tail; + out->console_tail = g_klog.console_tail; + out->dropped = g_klog.dropped; + out->seq = g_klog.seq.load(__ATOMIC_RELAXED); +} + +/* ======================================================================== + * Kernel Panic — Fatal Error Handler + * + * Dumps all critical S-mode CSRs and the stack pointer to the console, + * then halts the CPU. Uses kprintf (NOT klog) to avoid deadlocking + * if the panic was triggered while holding the klog spinlock. + * ======================================================================== */ + +extern "C" [[noreturn]] void kernel_panic(const char* msg, const char* detail) { + /* Disable interrupts immediately */ + arch::cpu::intr_off(); + + g_klog.panic_mode = true; + + /* ---- Banner ---- */ + kprintf("\n\n"); + kprintf("========================================\n"); + kprintf(" *** KERNEL PANIC ***\n"); + kprintf("========================================\n"); + + if (msg != nullptr) { + kprintf(" Reason : %s", msg); + if (detail != nullptr) { + kprintf(": %s", detail); + } + kprintf("\n"); + } + + /* ---- Read S-mode CSRs ---- */ + uint64 sepc, scause, stval, sstatus, satp, stvec, sscratch, sp_val; + + __asm__ volatile("csrr %0, sepc" : "=r"(sepc)); + __asm__ volatile("csrr %0, scause" : "=r"(scause)); + __asm__ volatile("csrr %0, stval" : "=r"(stval)); + __asm__ volatile("csrr %0, sstatus" : "=r"(sstatus)); + __asm__ volatile("csrr %0, satp" : "=r"(satp)); + __asm__ volatile("csrr %0, stvec" : "=r"(stvec)); + __asm__ volatile("csrr %0, sscratch" : "=r"(sscratch)); + __asm__ volatile("mv %0, sp" : "=r"(sp_val)); + + kprintf("\n--- S-mode CSR Dump ---\n"); + kprintf(" sepc = 0x%016llx\n", sepc); + kprintf(" scause = 0x%016llx", scause); + + /* Decode scause for convenience */ + bool is_interrupt = (scause >> 63) != 0; + uint64 cause_code = scause & 0x7FFFFFFFFFFFFFFFULL; + if (is_interrupt) { + kprintf(" (interrupt, code=%llu)\n", cause_code); + } else { + kprintf(" (exception, code=%llu)\n", cause_code); + } + + kprintf(" stval = 0x%016llx\n", stval); + kprintf(" sstatus = 0x%016llx", sstatus); + kprintf(" [SIE=%llu SPP=%llu SPIE=%llu]\n", + (sstatus >> 1) & 1, /* SIE */ + (sstatus >> 8) & 1, /* SPP */ + (sstatus >> 5) & 1); /* SPIE */ + kprintf(" satp = 0x%016llx", satp); + uint64 satp_mode = satp >> 60; + kprintf(" [mode=%llu]\n", satp_mode); + kprintf(" stvec = 0x%016llx\n", stvec); + kprintf(" sscratch = 0x%016llx\n", sscratch); + kprintf(" sp = 0x%016llx\n", sp_val); + + kprintf(" cpu_id = %llu\n", arch::cpu::id()); + kprintf(" time = %llu\n", arch::cpu::read_time()); + + kprintf("========================================\n\n"); + + /* Halt — spin forever with WFI to save power */ + while (true) { + arch::cpu::halt_until_interrupt(); + } +} diff --git a/lib/kobject.cc b/lib/kobject.cc new file mode 100644 index 0000000..8e8329e --- /dev/null +++ b/lib/kobject.cc @@ -0,0 +1,82 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +/* + * kobject — implementation. + * + * Lives in lib/ (mirroring Linux's lib/kobject.c) because kobject is a + * generic primitive, not tied to the driver model. + * + * Reference: docs/specs/storage_stack.md §4.2 + */ + +#include <lume/kobject.h> +#include <lume/container_of.h> +#include <lume/klog.h> + +void kobject_init(kobject* k, const kobj_type* type) +{ + if (k == nullptr) { + return; + } + k->name = nullptr; + k->parent = nullptr; + k->ktype = type; + k->state_in_sysfs = false; + k->entry.init(); + k->children.init(); + k->lock.init("kobject"); + kref_init(&k->refcount); +} + +int kobject_add(kobject* k, kobject* parent, const char* name) +{ + if (k == nullptr) { + return -1; + } + k->name = name; + if (parent != nullptr) { + kobject_get(parent); + k->parent = parent; + LockGuard g(parent->lock); + list_add_tail(&k->entry, &parent->children); + } + return 0; +} + +void kobject_del(kobject* k) +{ + if (k == nullptr || k->parent == nullptr) { + return; + } + kobject* parent = k->parent; + { + LockGuard g(parent->lock); + list_del_init(&k->entry); + } + k->parent = nullptr; + kobject_put(parent); +} + +void kobject_get(kobject* k) +{ + if (k != nullptr) { + kref_get(&k->refcount); + } +} + +static void kobject_release(kref* r) +{ + kobject* k = container_of(r, kobject, refcount); + if (k->ktype != nullptr && k->ktype->release != nullptr) { + k->ktype->release(k); + } +} + +void kobject_put(kobject* k) +{ + if (k == nullptr) { + return; + } + kref_put(&k->refcount, kobject_release); +} diff --git a/lib/kprintf.cc b/lib/kprintf.cc new file mode 100644 index 0000000..a98de71 --- /dev/null +++ b/lib/kprintf.cc @@ -0,0 +1,91 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +/* + * kprintf.cc — Kernel formatted output + * + * Uses mpaland/printf's vsnprintf_ as the core formatting engine. + * + * Architecture: + * vsnprintf_() ← pure formatting, writes to buffer + * ↓ + * kprintf() ← format + emit via console_write_all() + * kvprintf() ← va_list variant + * ksnprintf() ← format into caller's buffer + * + * Output path: + * Pre-registration: console_write_all() → early_putc() fallback + * Post-registration: console_write_all() → struct console chain + */ + +#include <lume/kprintf.h> +#include <lume/console.h> +#include <lume/atomic.h> +#include <arch/cpu.h> +#include "printf.h" + +/* ------------------------------------------------------------------ */ +/* Console spinlock (raw, no scheduler dependency — safe in panic) */ +/* ------------------------------------------------------------------ */ + +static lume::atomic<uint32> g_console_lock{0}; + +static inline void console_lock_acquire() +{ + while (g_console_lock.exchange(1, __ATOMIC_ACQUIRE) != 0) { + /* spin */ + } +} + +static inline void console_lock_release() +{ + g_console_lock.store(0, __ATOMIC_RELEASE); +} + +/* ------------------------------------------------------------------ */ +/* _putchar: required by mpaland/printf for printf_() / vprintf_() */ +/* ------------------------------------------------------------------ */ + +void _putchar(char character) +{ + early_putc(character); +} + +/* ------------------------------------------------------------------ */ +/* Public API */ +/* ------------------------------------------------------------------ */ + +extern "C" int kprintf(const char* fmt, ...) +{ + char buf[256]; + va_list va; + va_start(va, fmt); + int len = vsnprintf_(buf, sizeof(buf), fmt, va); + va_end(va); + + /* Emit to console under lock */ + console_lock_acquire(); + console_write_all(buf, len); + console_lock_release(); + return len; +} + +extern "C" int kvprintf(const char* fmt, va_list va) +{ + char buf[256]; + int len = vsnprintf_(buf, sizeof(buf), fmt, va); + + console_lock_acquire(); + console_write_all(buf, len); + console_lock_release(); + return len; +} + +extern "C" int ksnprintf(char* buf, int count, const char* fmt, ...) +{ + va_list va; + va_start(va, fmt); + int ret = vsnprintf_(buf, (size_t)count, fmt, va); + va_end(va); + return ret; +} diff --git a/lib/module.mk b/lib/module.mk new file mode 100644 index 0000000..0b178f8 --- /dev/null +++ b/lib/module.mk @@ -0,0 +1,66 @@ +# lib/module.mk +SRCS_CC += lib/cxx_abi.cc +SRCS_CC += lib/rbtree.cc +SRCS_CC += lib/kobject.cc +SRCS_CC += lib/kprintf.cc +SRCS_CC += lib/klog.cc +SRCS_CC += lib/random.cc +SRCS_C += lib/printf.c + +# ============================================================ +# musl string library (cross-platform with arch asm overrides) +# ============================================================ + +# Map LumeOS ARCH to musl string arch directory +# riscv has no musl asm optimizations → pure C fallback +MUSL_STRING_ARCH_riscv := +MUSL_STRING_ARCH_x86_64 := x86_64 +MUSL_STRING_ARCH_i386 := i386 +MUSL_STRING_ARCH_aarch64:= aarch64 +MUSL_STRING_ARCH_arm := arm + +MUSL_STRING_ARCH := $(MUSL_STRING_ARCH_$(ARCH)) + +# Collect arch-specific asm sources (if any for this arch) +MUSL_ASM_SRCS := +ifneq ($(MUSL_STRING_ARCH),) + MUSL_ASM_SRCS += $(wildcard lib/string/$(MUSL_STRING_ARCH)/*.S) \ + $(wildcard lib/string/$(MUSL_STRING_ARCH)/*.s) +endif + +# Derive which C files are overridden by asm (strip path+ext to get base name) +MUSL_ASM_BASENAMES := $(sort $(basename $(notdir $(MUSL_ASM_SRCS)))) + +# All C sources, then filter out those with asm replacements +MUSL_ALL_C := $(wildcard lib/string/*.c) +MUSL_EXCLUDED_C := $(foreach name,$(MUSL_ASM_BASENAMES),lib/string/$(name).c) +MUSL_C_SRCS := $(filter-out $(MUSL_EXCLUDED_C),$(MUSL_ALL_C)) + +SRCS_C += $(MUSL_C_SRCS) +SRCS_S += $(filter %.S,$(MUSL_ASM_SRCS)) +SRCS_s += $(filter %.s,$(MUSL_ASM_SRCS)) + +# ============================================================ +# libfdt — kernel adapter shims around scripts/dtc/libfdt/. +# +# Each shim is two lines: +# #include <linux/libfdt_env.h> +# #include "../scripts/dtc/libfdt/fdt*.c" +# matching Linux lib/fdt*.c verbatim. The compile recipe needs: +# - <linux/libfdt_env.h> reachable via the default -Iinclude path +# - -I scripts/dtc/libfdt so the upstream source's #include <libfdt.h> +# and friends resolve to scripts/dtc/libfdt/libfdt.h +# Overriding CFLAGS_LIBC (which the %.o: %.c rule uses) avoids dragging +# in libc-shim headers — libfdt is freestanding-compatible and uses +# only the string functions forward-declared in <linux/libfdt_env.h>. +# ============================================================ +LIBFDT_FILES := fdt.c fdt_ro.c fdt_wip.c fdt_rw.c fdt_sw.c \ + fdt_strerror.c fdt_empty_tree.c fdt_addresses.c +SRCS_C += $(addprefix lib/,$(LIBFDT_FILES)) + +# Per-target CFLAGS override: plain CFLAGS plus the upstream include dir. +# Use `=` (recursive) not `:=` because $(CFLAGS) is defined in the top +# Makefile AFTER this file is included — `:=` would expand it now (empty) +# and lose -Iinclude, breaking <linux/libfdt_env.h>. +$(addprefix $(BUILD)/lib/,$(LIBFDT_FILES:.c=.o)): CFLAGS_LIBC = \ + $(CFLAGS) -I scripts/dtc/libfdt diff --git a/lib/printf.c b/lib/printf.c new file mode 100644 index 0000000..8a700ad --- /dev/null +++ b/lib/printf.c @@ -0,0 +1,914 @@ +///////////////////////////////////////////////////////////////////////////////
+// \author (c) Marco Paland (info@paland.com)
+// 2014-2019, PALANDesign Hannover, Germany
+//
+// \license The MIT License (MIT)
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+//
+// \brief Tiny printf, sprintf and (v)snprintf implementation, optimized for speed on
+// embedded systems with a very limited resources. These routines are thread
+// safe and reentrant!
+// Use this instead of the bloated standard/newlib printf cause these use
+// malloc for printf (and may not be thread safe).
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#include "printf.h"
+
+
+// define this globally (e.g. gcc -DPRINTF_INCLUDE_CONFIG_H ...) to include the
+// printf_config.h header file
+// default: undefined
+#ifdef PRINTF_INCLUDE_CONFIG_H
+#include "printf_config.h"
+#endif
+
+
+// 'ntoa' conversion buffer size, this must be big enough to hold one converted
+// numeric number including padded zeros (dynamically created on stack)
+// default: 32 byte
+#ifndef PRINTF_NTOA_BUFFER_SIZE
+#define PRINTF_NTOA_BUFFER_SIZE 32U
+#endif
+
+// 'ftoa' conversion buffer size, this must be big enough to hold one converted
+// float number including padded zeros (dynamically created on stack)
+// default: 32 byte
+#ifndef PRINTF_FTOA_BUFFER_SIZE
+#define PRINTF_FTOA_BUFFER_SIZE 32U
+#endif
+
+// support for the floating point type (%f)
+// default: activated
+#ifndef PRINTF_DISABLE_SUPPORT_FLOAT
+#define PRINTF_SUPPORT_FLOAT
+#endif
+
+// support for exponential floating point notation (%e/%g)
+// default: activated
+#ifndef PRINTF_DISABLE_SUPPORT_EXPONENTIAL
+#define PRINTF_SUPPORT_EXPONENTIAL
+#endif
+
+// define the default floating point precision
+// default: 6 digits
+#ifndef PRINTF_DEFAULT_FLOAT_PRECISION
+#define PRINTF_DEFAULT_FLOAT_PRECISION 6U
+#endif
+
+// define the largest float suitable to print with %f
+// default: 1e9
+#ifndef PRINTF_MAX_FLOAT
+#define PRINTF_MAX_FLOAT 1e9
+#endif
+
+// support for the long long types (%llu or %p)
+// default: activated
+#ifndef PRINTF_DISABLE_SUPPORT_LONG_LONG
+#define PRINTF_SUPPORT_LONG_LONG
+#endif
+
+// support for the ptrdiff_t type (%t)
+// ptrdiff_t is normally defined in <stddef.h> as long or long long type
+// default: activated
+#ifndef PRINTF_DISABLE_SUPPORT_PTRDIFF_T
+#define PRINTF_SUPPORT_PTRDIFF_T
+#endif
+
+///////////////////////////////////////////////////////////////////////////////
+
+// internal flag definitions
+#define FLAGS_ZEROPAD (1U << 0U)
+#define FLAGS_LEFT (1U << 1U)
+#define FLAGS_PLUS (1U << 2U)
+#define FLAGS_SPACE (1U << 3U)
+#define FLAGS_HASH (1U << 4U)
+#define FLAGS_UPPERCASE (1U << 5U)
+#define FLAGS_CHAR (1U << 6U)
+#define FLAGS_SHORT (1U << 7U)
+#define FLAGS_LONG (1U << 8U)
+#define FLAGS_LONG_LONG (1U << 9U)
+#define FLAGS_PRECISION (1U << 10U)
+#define FLAGS_ADAPT_EXP (1U << 11U)
+
+
+// import float.h for DBL_MAX
+#if defined(PRINTF_SUPPORT_FLOAT)
+#include <float.h>
+#endif
+
+
+// output function type
+typedef void (*out_fct_type)(char character, void* buffer, size_t idx, size_t maxlen);
+
+
+// wrapper (used as buffer) for output function type
+typedef struct {
+ void (*fct)(char character, void* arg);
+ void* arg;
+} out_fct_wrap_type;
+
+
+// internal buffer output
+static inline void _out_buffer(char character, void* buffer, size_t idx, size_t maxlen)
+{
+ if (idx < maxlen) {
+ ((char*)buffer)[idx] = character;
+ }
+}
+
+
+// internal null output
+static inline void _out_null(char character, void* buffer, size_t idx, size_t maxlen)
+{
+ (void)character; (void)buffer; (void)idx; (void)maxlen;
+}
+
+
+// internal _putchar wrapper
+static inline void _out_char(char character, void* buffer, size_t idx, size_t maxlen)
+{
+ (void)buffer; (void)idx; (void)maxlen;
+ if (character) {
+ _putchar(character);
+ }
+}
+
+
+// internal output function wrapper
+static inline void _out_fct(char character, void* buffer, size_t idx, size_t maxlen)
+{
+ (void)idx; (void)maxlen;
+ if (character) {
+ // buffer is the output fct pointer
+ ((out_fct_wrap_type*)buffer)->fct(character, ((out_fct_wrap_type*)buffer)->arg);
+ }
+}
+
+
+// internal secure strlen
+// \return The length of the string (excluding the terminating 0) limited by 'maxsize'
+static inline unsigned int _strnlen_s(const char* str, size_t maxsize)
+{
+ const char* s;
+ for (s = str; *s && maxsize--; ++s);
+ return (unsigned int)(s - str);
+}
+
+
+// internal test if char is a digit (0-9)
+// \return true if char is a digit
+static inline bool _is_digit(char ch)
+{
+ return (ch >= '0') && (ch <= '9');
+}
+
+
+// internal ASCII string to unsigned int conversion
+static unsigned int _atoi(const char** str)
+{
+ unsigned int i = 0U;
+ while (_is_digit(**str)) {
+ i = i * 10U + (unsigned int)(*((*str)++) - '0');
+ }
+ return i;
+}
+
+
+// output the specified string in reverse, taking care of any zero-padding
+static size_t _out_rev(out_fct_type out, char* buffer, size_t idx, size_t maxlen, const char* buf, size_t len, unsigned int width, unsigned int flags)
+{
+ const size_t start_idx = idx;
+
+ // pad spaces up to given width
+ if (!(flags & FLAGS_LEFT) && !(flags & FLAGS_ZEROPAD)) {
+ for (size_t i = len; i < width; i++) {
+ out(' ', buffer, idx++, maxlen);
+ }
+ }
+
+ // reverse string
+ while (len) {
+ out(buf[--len], buffer, idx++, maxlen);
+ }
+
+ // append pad spaces up to given width
+ if (flags & FLAGS_LEFT) {
+ while (idx - start_idx < width) {
+ out(' ', buffer, idx++, maxlen);
+ }
+ }
+
+ return idx;
+}
+
+
+// internal itoa format
+static size_t _ntoa_format(out_fct_type out, char* buffer, size_t idx, size_t maxlen, char* buf, size_t len, bool negative, unsigned int base, unsigned int prec, unsigned int width, unsigned int flags)
+{
+ // pad leading zeros
+ if (!(flags & FLAGS_LEFT)) {
+ if (width && (flags & FLAGS_ZEROPAD) && (negative || (flags & (FLAGS_PLUS | FLAGS_SPACE)))) {
+ width--;
+ }
+ while ((len < prec) && (len < PRINTF_NTOA_BUFFER_SIZE)) {
+ buf[len++] = '0';
+ }
+ while ((flags & FLAGS_ZEROPAD) && (len < width) && (len < PRINTF_NTOA_BUFFER_SIZE)) {
+ buf[len++] = '0';
+ }
+ }
+
+ // handle hash
+ if (flags & FLAGS_HASH) {
+ if (!(flags & FLAGS_PRECISION) && len && ((len == prec) || (len == width))) {
+ len--;
+ if (len && (base == 16U)) {
+ len--;
+ }
+ }
+ if ((base == 16U) && !(flags & FLAGS_UPPERCASE) && (len < PRINTF_NTOA_BUFFER_SIZE)) {
+ buf[len++] = 'x';
+ }
+ else if ((base == 16U) && (flags & FLAGS_UPPERCASE) && (len < PRINTF_NTOA_BUFFER_SIZE)) {
+ buf[len++] = 'X';
+ }
+ else if ((base == 2U) && (len < PRINTF_NTOA_BUFFER_SIZE)) {
+ buf[len++] = 'b';
+ }
+ if (len < PRINTF_NTOA_BUFFER_SIZE) {
+ buf[len++] = '0';
+ }
+ }
+
+ if (len < PRINTF_NTOA_BUFFER_SIZE) {
+ if (negative) {
+ buf[len++] = '-';
+ }
+ else if (flags & FLAGS_PLUS) {
+ buf[len++] = '+'; // ignore the space if the '+' exists
+ }
+ else if (flags & FLAGS_SPACE) {
+ buf[len++] = ' ';
+ }
+ }
+
+ return _out_rev(out, buffer, idx, maxlen, buf, len, width, flags);
+}
+
+
+// internal itoa for 'long' type
+static size_t _ntoa_long(out_fct_type out, char* buffer, size_t idx, size_t maxlen, unsigned long value, bool negative, unsigned long base, unsigned int prec, unsigned int width, unsigned int flags)
+{
+ char buf[PRINTF_NTOA_BUFFER_SIZE];
+ size_t len = 0U;
+
+ // no hash for 0 values
+ if (!value) {
+ flags &= ~FLAGS_HASH;
+ }
+
+ // write if precision != 0 and value is != 0
+ if (!(flags & FLAGS_PRECISION) || value) {
+ do {
+ const char digit = (char)(value % base);
+ buf[len++] = digit < 10 ? '0' + digit : (flags & FLAGS_UPPERCASE ? 'A' : 'a') + digit - 10;
+ value /= base;
+ } while (value && (len < PRINTF_NTOA_BUFFER_SIZE));
+ }
+
+ return _ntoa_format(out, buffer, idx, maxlen, buf, len, negative, (unsigned int)base, prec, width, flags);
+}
+
+
+// internal itoa for 'long long' type
+#if defined(PRINTF_SUPPORT_LONG_LONG)
+static size_t _ntoa_long_long(out_fct_type out, char* buffer, size_t idx, size_t maxlen, unsigned long long value, bool negative, unsigned long long base, unsigned int prec, unsigned int width, unsigned int flags)
+{
+ char buf[PRINTF_NTOA_BUFFER_SIZE];
+ size_t len = 0U;
+
+ // no hash for 0 values
+ if (!value) {
+ flags &= ~FLAGS_HASH;
+ }
+
+ // write if precision != 0 and value is != 0
+ if (!(flags & FLAGS_PRECISION) || value) {
+ do {
+ const char digit = (char)(value % base);
+ buf[len++] = digit < 10 ? '0' + digit : (flags & FLAGS_UPPERCASE ? 'A' : 'a') + digit - 10;
+ value /= base;
+ } while (value && (len < PRINTF_NTOA_BUFFER_SIZE));
+ }
+
+ return _ntoa_format(out, buffer, idx, maxlen, buf, len, negative, (unsigned int)base, prec, width, flags);
+}
+#endif // PRINTF_SUPPORT_LONG_LONG
+
+
+#if defined(PRINTF_SUPPORT_FLOAT)
+
+#if defined(PRINTF_SUPPORT_EXPONENTIAL)
+// forward declaration so that _ftoa can switch to exp notation for values > PRINTF_MAX_FLOAT
+static size_t _etoa(out_fct_type out, char* buffer, size_t idx, size_t maxlen, double value, unsigned int prec, unsigned int width, unsigned int flags);
+#endif
+
+
+// internal ftoa for fixed decimal floating point
+static size_t _ftoa(out_fct_type out, char* buffer, size_t idx, size_t maxlen, double value, unsigned int prec, unsigned int width, unsigned int flags)
+{
+ char buf[PRINTF_FTOA_BUFFER_SIZE];
+ size_t len = 0U;
+ double diff = 0.0;
+
+ // powers of 10
+ static const double pow10[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
+
+ // test for special values
+ if (value != value)
+ return _out_rev(out, buffer, idx, maxlen, "nan", 3, width, flags);
+ if (value < -DBL_MAX)
+ return _out_rev(out, buffer, idx, maxlen, "fni-", 4, width, flags);
+ if (value > DBL_MAX)
+ return _out_rev(out, buffer, idx, maxlen, (flags & FLAGS_PLUS) ? "fni+" : "fni", (flags & FLAGS_PLUS) ? 4U : 3U, width, flags);
+
+ // test for very large values
+ // standard printf behavior is to print EVERY whole number digit -- which could be 100s of characters overflowing your buffers == bad
+ if ((value > PRINTF_MAX_FLOAT) || (value < -PRINTF_MAX_FLOAT)) {
+#if defined(PRINTF_SUPPORT_EXPONENTIAL)
+ return _etoa(out, buffer, idx, maxlen, value, prec, width, flags);
+#else
+ return 0U;
+#endif
+ }
+
+ // test for negative
+ bool negative = false;
+ if (value < 0) {
+ negative = true;
+ value = 0 - value;
+ }
+
+ // set default precision, if not set explicitly
+ if (!(flags & FLAGS_PRECISION)) {
+ prec = PRINTF_DEFAULT_FLOAT_PRECISION;
+ }
+ // limit precision to 9, cause a prec >= 10 can lead to overflow errors
+ while ((len < PRINTF_FTOA_BUFFER_SIZE) && (prec > 9U)) {
+ buf[len++] = '0';
+ prec--;
+ }
+
+ int whole = (int)value;
+ double tmp = (value - whole) * pow10[prec];
+ unsigned long frac = (unsigned long)tmp;
+ diff = tmp - frac;
+
+ if (diff > 0.5) {
+ ++frac;
+ // handle rollover, e.g. case 0.99 with prec 1 is 1.0
+ if (frac >= pow10[prec]) {
+ frac = 0;
+ ++whole;
+ }
+ }
+ else if (diff < 0.5) {
+ }
+ else if ((frac == 0U) || (frac & 1U)) {
+ // if halfway, round up if odd OR if last digit is 0
+ ++frac;
+ }
+
+ if (prec == 0U) {
+ diff = value - (double)whole;
+ if ((!(diff < 0.5) || (diff > 0.5)) && (whole & 1)) {
+ // exactly 0.5 and ODD, then round up
+ // 1.5 -> 2, but 2.5 -> 2
+ ++whole;
+ }
+ }
+ else {
+ unsigned int count = prec;
+ // now do fractional part, as an unsigned number
+ while (len < PRINTF_FTOA_BUFFER_SIZE) {
+ --count;
+ buf[len++] = (char)(48U + (frac % 10U));
+ if (!(frac /= 10U)) {
+ break;
+ }
+ }
+ // add extra 0s
+ while ((len < PRINTF_FTOA_BUFFER_SIZE) && (count-- > 0U)) {
+ buf[len++] = '0';
+ }
+ if (len < PRINTF_FTOA_BUFFER_SIZE) {
+ // add decimal
+ buf[len++] = '.';
+ }
+ }
+
+ // do whole part, number is reversed
+ while (len < PRINTF_FTOA_BUFFER_SIZE) {
+ buf[len++] = (char)(48 + (whole % 10));
+ if (!(whole /= 10)) {
+ break;
+ }
+ }
+
+ // pad leading zeros
+ if (!(flags & FLAGS_LEFT) && (flags & FLAGS_ZEROPAD)) {
+ if (width && (negative || (flags & (FLAGS_PLUS | FLAGS_SPACE)))) {
+ width--;
+ }
+ while ((len < width) && (len < PRINTF_FTOA_BUFFER_SIZE)) {
+ buf[len++] = '0';
+ }
+ }
+
+ if (len < PRINTF_FTOA_BUFFER_SIZE) {
+ if (negative) {
+ buf[len++] = '-';
+ }
+ else if (flags & FLAGS_PLUS) {
+ buf[len++] = '+'; // ignore the space if the '+' exists
+ }
+ else if (flags & FLAGS_SPACE) {
+ buf[len++] = ' ';
+ }
+ }
+
+ return _out_rev(out, buffer, idx, maxlen, buf, len, width, flags);
+}
+
+
+#if defined(PRINTF_SUPPORT_EXPONENTIAL)
+// internal ftoa variant for exponential floating-point type, contributed by Martijn Jasperse <m.jasperse@gmail.com>
+static size_t _etoa(out_fct_type out, char* buffer, size_t idx, size_t maxlen, double value, unsigned int prec, unsigned int width, unsigned int flags)
+{
+ // check for NaN and special values
+ if ((value != value) || (value > DBL_MAX) || (value < -DBL_MAX)) {
+ return _ftoa(out, buffer, idx, maxlen, value, prec, width, flags);
+ }
+
+ // determine the sign
+ const bool negative = value < 0;
+ if (negative) {
+ value = -value;
+ }
+
+ // default precision
+ if (!(flags & FLAGS_PRECISION)) {
+ prec = PRINTF_DEFAULT_FLOAT_PRECISION;
+ }
+
+ // determine the decimal exponent
+ // based on the algorithm by David Gay (https://www.ampl.com/netlib/fp/dtoa.c)
+ union {
+ uint64_t U;
+ double F;
+ } conv;
+
+ conv.F = value;
+ int exp2 = (int)((conv.U >> 52U) & 0x07FFU) - 1023; // effectively log2
+ conv.U = (conv.U & ((1ULL << 52U) - 1U)) | (1023ULL << 52U); // drop the exponent so conv.F is now in [1,2)
+ // now approximate log10 from the log2 integer part and an expansion of ln around 1.5
+ int expval = (int)(0.1760912590558 + exp2 * 0.301029995663981 + (conv.F - 1.5) * 0.289529654602168);
+ // now we want to compute 10^expval but we want to be sure it won't overflow
+ exp2 = (int)(expval * 3.321928094887362 + 0.5);
+ const double z = expval * 2.302585092994046 - exp2 * 0.6931471805599453;
+ const double z2 = z * z;
+ conv.U = (uint64_t)(exp2 + 1023) << 52U;
+ // compute exp(z) using continued fractions, see https://en.wikipedia.org/wiki/Exponential_function#Continued_fractions_for_ex
+ conv.F *= 1 + 2 * z / (2 - z + (z2 / (6 + (z2 / (10 + z2 / 14)))));
+ // correct for rounding errors
+ if (value < conv.F) {
+ expval--;
+ conv.F /= 10;
+ }
+
+ // the exponent format is "%+03d" and largest value is "307", so set aside 4-5 characters
+ unsigned int minwidth = ((expval < 100) && (expval > -100)) ? 4U : 5U;
+
+ // in "%g" mode, "prec" is the number of *significant figures* not decimals
+ if (flags & FLAGS_ADAPT_EXP) {
+ // do we want to fall-back to "%f" mode?
+ if ((value >= 1e-4) && (value < 1e6)) {
+ if ((int)prec > expval) {
+ prec = (unsigned)((int)prec - expval - 1);
+ }
+ else {
+ prec = 0;
+ }
+ flags |= FLAGS_PRECISION; // make sure _ftoa respects precision
+ // no characters in exponent
+ minwidth = 0U;
+ expval = 0;
+ }
+ else {
+ // we use one sigfig for the whole part
+ if ((prec > 0) && (flags & FLAGS_PRECISION)) {
+ --prec;
+ }
+ }
+ }
+
+ // will everything fit?
+ unsigned int fwidth = width;
+ if (width > minwidth) {
+ // we didn't fall-back so subtract the characters required for the exponent
+ fwidth -= minwidth;
+ } else {
+ // not enough characters, so go back to default sizing
+ fwidth = 0U;
+ }
+ if ((flags & FLAGS_LEFT) && minwidth) {
+ // if we're padding on the right, DON'T pad the floating part
+ fwidth = 0U;
+ }
+
+ // rescale the float value
+ if (expval) {
+ value /= conv.F;
+ }
+
+ // output the floating part
+ const size_t start_idx = idx;
+ idx = _ftoa(out, buffer, idx, maxlen, negative ? -value : value, prec, fwidth, flags & ~FLAGS_ADAPT_EXP);
+
+ // output the exponent part
+ if (minwidth) {
+ // output the exponential symbol
+ out((flags & FLAGS_UPPERCASE) ? 'E' : 'e', buffer, idx++, maxlen);
+ // output the exponent value
+ idx = _ntoa_long(out, buffer, idx, maxlen, (expval < 0) ? -expval : expval, expval < 0, 10, 0, minwidth-1, FLAGS_ZEROPAD | FLAGS_PLUS);
+ // might need to right-pad spaces
+ if (flags & FLAGS_LEFT) {
+ while (idx - start_idx < width) out(' ', buffer, idx++, maxlen);
+ }
+ }
+ return idx;
+}
+#endif // PRINTF_SUPPORT_EXPONENTIAL
+#endif // PRINTF_SUPPORT_FLOAT
+
+
+// internal vsnprintf
+static int _vsnprintf(out_fct_type out, char* buffer, const size_t maxlen, const char* format, va_list va)
+{
+ unsigned int flags, width, precision, n;
+ size_t idx = 0U;
+
+ if (!buffer) {
+ // use null output function
+ out = _out_null;
+ }
+
+ while (*format)
+ {
+ // format specifier? %[flags][width][.precision][length]
+ if (*format != '%') {
+ // no
+ out(*format, buffer, idx++, maxlen);
+ format++;
+ continue;
+ }
+ else {
+ // yes, evaluate it
+ format++;
+ }
+
+ // evaluate flags
+ flags = 0U;
+ do {
+ switch (*format) {
+ case '0': flags |= FLAGS_ZEROPAD; format++; n = 1U; break;
+ case '-': flags |= FLAGS_LEFT; format++; n = 1U; break;
+ case '+': flags |= FLAGS_PLUS; format++; n = 1U; break;
+ case ' ': flags |= FLAGS_SPACE; format++; n = 1U; break;
+ case '#': flags |= FLAGS_HASH; format++; n = 1U; break;
+ default : n = 0U; break;
+ }
+ } while (n);
+
+ // evaluate width field
+ width = 0U;
+ if (_is_digit(*format)) {
+ width = _atoi(&format);
+ }
+ else if (*format == '*') {
+ const int w = va_arg(va, int);
+ if (w < 0) {
+ flags |= FLAGS_LEFT; // reverse padding
+ width = (unsigned int)-w;
+ }
+ else {
+ width = (unsigned int)w;
+ }
+ format++;
+ }
+
+ // evaluate precision field
+ precision = 0U;
+ if (*format == '.') {
+ flags |= FLAGS_PRECISION;
+ format++;
+ if (_is_digit(*format)) {
+ precision = _atoi(&format);
+ }
+ else if (*format == '*') {
+ const int prec = (int)va_arg(va, int);
+ precision = prec > 0 ? (unsigned int)prec : 0U;
+ format++;
+ }
+ }
+
+ // evaluate length field
+ switch (*format) {
+ case 'l' :
+ flags |= FLAGS_LONG;
+ format++;
+ if (*format == 'l') {
+ flags |= FLAGS_LONG_LONG;
+ format++;
+ }
+ break;
+ case 'h' :
+ flags |= FLAGS_SHORT;
+ format++;
+ if (*format == 'h') {
+ flags |= FLAGS_CHAR;
+ format++;
+ }
+ break;
+#if defined(PRINTF_SUPPORT_PTRDIFF_T)
+ case 't' :
+ flags |= (sizeof(ptrdiff_t) == sizeof(long) ? FLAGS_LONG : FLAGS_LONG_LONG);
+ format++;
+ break;
+#endif
+ case 'j' :
+ flags |= (sizeof(intmax_t) == sizeof(long) ? FLAGS_LONG : FLAGS_LONG_LONG);
+ format++;
+ break;
+ case 'z' :
+ flags |= (sizeof(size_t) == sizeof(long) ? FLAGS_LONG : FLAGS_LONG_LONG);
+ format++;
+ break;
+ default :
+ break;
+ }
+
+ // evaluate specifier
+ switch (*format) {
+ case 'd' :
+ case 'i' :
+ case 'u' :
+ case 'x' :
+ case 'X' :
+ case 'o' :
+ case 'b' : {
+ // set the base
+ unsigned int base;
+ if (*format == 'x' || *format == 'X') {
+ base = 16U;
+ }
+ else if (*format == 'o') {
+ base = 8U;
+ }
+ else if (*format == 'b') {
+ base = 2U;
+ }
+ else {
+ base = 10U;
+ flags &= ~FLAGS_HASH; // no hash for dec format
+ }
+ // uppercase
+ if (*format == 'X') {
+ flags |= FLAGS_UPPERCASE;
+ }
+
+ // no plus or space flag for u, x, X, o, b
+ if ((*format != 'i') && (*format != 'd')) {
+ flags &= ~(FLAGS_PLUS | FLAGS_SPACE);
+ }
+
+ // ignore '0' flag when precision is given
+ if (flags & FLAGS_PRECISION) {
+ flags &= ~FLAGS_ZEROPAD;
+ }
+
+ // convert the integer
+ if ((*format == 'i') || (*format == 'd')) {
+ // signed
+ if (flags & FLAGS_LONG_LONG) {
+#if defined(PRINTF_SUPPORT_LONG_LONG)
+ const long long value = va_arg(va, long long);
+ idx = _ntoa_long_long(out, buffer, idx, maxlen, (unsigned long long)(value > 0 ? value : 0 - value), value < 0, base, precision, width, flags);
+#endif
+ }
+ else if (flags & FLAGS_LONG) {
+ const long value = va_arg(va, long);
+ idx = _ntoa_long(out, buffer, idx, maxlen, (unsigned long)(value > 0 ? value : 0 - value), value < 0, base, precision, width, flags);
+ }
+ else {
+ const int value = (flags & FLAGS_CHAR) ? (char)va_arg(va, int) : (flags & FLAGS_SHORT) ? (short int)va_arg(va, int) : va_arg(va, int);
+ idx = _ntoa_long(out, buffer, idx, maxlen, (unsigned int)(value > 0 ? value : 0 - value), value < 0, base, precision, width, flags);
+ }
+ }
+ else {
+ // unsigned
+ if (flags & FLAGS_LONG_LONG) {
+#if defined(PRINTF_SUPPORT_LONG_LONG)
+ idx = _ntoa_long_long(out, buffer, idx, maxlen, va_arg(va, unsigned long long), false, base, precision, width, flags);
+#endif
+ }
+ else if (flags & FLAGS_LONG) {
+ idx = _ntoa_long(out, buffer, idx, maxlen, va_arg(va, unsigned long), false, base, precision, width, flags);
+ }
+ else {
+ const unsigned int value = (flags & FLAGS_CHAR) ? (unsigned char)va_arg(va, unsigned int) : (flags & FLAGS_SHORT) ? (unsigned short int)va_arg(va, unsigned int) : va_arg(va, unsigned int);
+ idx = _ntoa_long(out, buffer, idx, maxlen, value, false, base, precision, width, flags);
+ }
+ }
+ format++;
+ break;
+ }
+#if defined(PRINTF_SUPPORT_FLOAT)
+ case 'f' :
+ case 'F' :
+ if (*format == 'F') flags |= FLAGS_UPPERCASE;
+ idx = _ftoa(out, buffer, idx, maxlen, va_arg(va, double), precision, width, flags);
+ format++;
+ break;
+#if defined(PRINTF_SUPPORT_EXPONENTIAL)
+ case 'e':
+ case 'E':
+ case 'g':
+ case 'G':
+ if ((*format == 'g')||(*format == 'G')) flags |= FLAGS_ADAPT_EXP;
+ if ((*format == 'E')||(*format == 'G')) flags |= FLAGS_UPPERCASE;
+ idx = _etoa(out, buffer, idx, maxlen, va_arg(va, double), precision, width, flags);
+ format++;
+ break;
+#endif // PRINTF_SUPPORT_EXPONENTIAL
+#endif // PRINTF_SUPPORT_FLOAT
+ case 'c' : {
+ unsigned int l = 1U;
+ // pre padding
+ if (!(flags & FLAGS_LEFT)) {
+ while (l++ < width) {
+ out(' ', buffer, idx++, maxlen);
+ }
+ }
+ // char output
+ out((char)va_arg(va, int), buffer, idx++, maxlen);
+ // post padding
+ if (flags & FLAGS_LEFT) {
+ while (l++ < width) {
+ out(' ', buffer, idx++, maxlen);
+ }
+ }
+ format++;
+ break;
+ }
+
+ case 's' : {
+ const char* p = va_arg(va, char*);
+ unsigned int l = _strnlen_s(p, precision ? precision : (size_t)-1);
+ // pre padding
+ if (flags & FLAGS_PRECISION) {
+ l = (l < precision ? l : precision);
+ }
+ if (!(flags & FLAGS_LEFT)) {
+ while (l++ < width) {
+ out(' ', buffer, idx++, maxlen);
+ }
+ }
+ // string output
+ while ((*p != 0) && (!(flags & FLAGS_PRECISION) || precision--)) {
+ out(*(p++), buffer, idx++, maxlen);
+ }
+ // post padding
+ if (flags & FLAGS_LEFT) {
+ while (l++ < width) {
+ out(' ', buffer, idx++, maxlen);
+ }
+ }
+ format++;
+ break;
+ }
+
+ case 'p' : {
+ width = sizeof(void*) * 2U;
+ flags |= FLAGS_ZEROPAD | FLAGS_UPPERCASE;
+#if defined(PRINTF_SUPPORT_LONG_LONG)
+ const bool is_ll = sizeof(uintptr_t) == sizeof(long long);
+ if (is_ll) {
+ idx = _ntoa_long_long(out, buffer, idx, maxlen, (uintptr_t)va_arg(va, void*), false, 16U, precision, width, flags);
+ }
+ else {
+#endif
+ idx = _ntoa_long(out, buffer, idx, maxlen, (unsigned long)((uintptr_t)va_arg(va, void*)), false, 16U, precision, width, flags);
+#if defined(PRINTF_SUPPORT_LONG_LONG)
+ }
+#endif
+ format++;
+ break;
+ }
+
+ case '%' :
+ out('%', buffer, idx++, maxlen);
+ format++;
+ break;
+
+ default :
+ out(*format, buffer, idx++, maxlen);
+ format++;
+ break;
+ }
+ }
+
+ // termination
+ out((char)0, buffer, idx < maxlen ? idx : maxlen - 1U, maxlen);
+
+ // return written chars without terminating \0
+ return (int)idx;
+}
+
+
+///////////////////////////////////////////////////////////////////////////////
+
+int printf_(const char* format, ...)
+{
+ va_list va;
+ va_start(va, format);
+ char buffer[1];
+ const int ret = _vsnprintf(_out_char, buffer, (size_t)-1, format, va);
+ va_end(va);
+ return ret;
+}
+
+
+int sprintf_(char* buffer, const char* format, ...)
+{
+ va_list va;
+ va_start(va, format);
+ const int ret = _vsnprintf(_out_buffer, buffer, (size_t)-1, format, va);
+ va_end(va);
+ return ret;
+}
+
+
+int snprintf_(char* buffer, size_t count, const char* format, ...)
+{
+ va_list va;
+ va_start(va, format);
+ const int ret = _vsnprintf(_out_buffer, buffer, count, format, va);
+ va_end(va);
+ return ret;
+}
+
+
+int vprintf_(const char* format, va_list va)
+{
+ char buffer[1];
+ return _vsnprintf(_out_char, buffer, (size_t)-1, format, va);
+}
+
+
+int vsnprintf_(char* buffer, size_t count, const char* format, va_list va)
+{
+ return _vsnprintf(_out_buffer, buffer, count, format, va);
+}
+
+
+int fctprintf(void (*out)(char character, void* arg), void* arg, const char* format, ...)
+{
+ va_list va;
+ va_start(va, format);
+ const out_fct_wrap_type out_fct_wrap = { out, arg };
+ const int ret = _vsnprintf(_out_fct, (char*)(uintptr_t)&out_fct_wrap, (size_t)-1, format, va);
+ va_end(va);
+ return ret;
+}
diff --git a/lib/printf.h b/lib/printf.h new file mode 100644 index 0000000..8aa23cf --- /dev/null +++ b/lib/printf.h @@ -0,0 +1,129 @@ +///////////////////////////////////////////////////////////////////////////////
+// \author (c) Marco Paland (info@paland.com)
+// 2014-2019, PALANDesign Hannover, Germany
+//
+// \license The MIT License (MIT)
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+//
+// \brief Tiny printf, sprintf and snprintf implementation, optimized for speed on
+// embedded systems with a very limited resources.
+// Use this instead of bloated standard/newlib printf.
+// These routines are thread safe and reentrant.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef _PRINTF_H_
+#define _PRINTF_H_
+
+#include <stdarg.h>
+
+/* LumeOS: avoid stddef.h — define types from compiler builtins directly.
+ * This works in both C and C++ and matches our types.h definition. */
+#ifndef _SIZE_T_DEFINED
+#define _SIZE_T_DEFINED
+typedef __SIZE_TYPE__ size_t;
+typedef __PTRDIFF_TYPE__ ptrdiff_t;
+typedef __INTMAX_TYPE__ intmax_t;
+#endif
+
+/* LumeOS: kernel does not need floating-point formatted output */
+#define PRINTF_DISABLE_SUPPORT_FLOAT
+#define PRINTF_DISABLE_SUPPORT_EXPONENTIAL
+
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+/**
+ * Output a character to a custom device like UART, used by the printf() function
+ * This function is declared here only. You have to write your custom implementation somewhere
+ * \param character Character to output
+ */
+void _putchar(char character);
+
+
+/**
+ * Tiny printf implementation
+ * You have to implement _putchar if you use printf()
+ * To avoid conflicts with the regular printf() API it is overridden by macro defines
+ * and internal underscore-appended functions like printf_() are used
+ * \param format A string that specifies the format of the output
+ * \return The number of characters that are written into the array, not counting the terminating null character
+ */
+#define printf printf_
+int printf_(const char* format, ...);
+
+
+/**
+ * Tiny sprintf implementation
+ * Due to security reasons (buffer overflow) YOU SHOULD CONSIDER USING (V)SNPRINTF INSTEAD!
+ * \param buffer A pointer to the buffer where to store the formatted string. MUST be big enough to store the output!
+ * \param format A string that specifies the format of the output
+ * \return The number of characters that are WRITTEN into the buffer, not counting the terminating null character
+ */
+#define sprintf sprintf_
+int sprintf_(char* buffer, const char* format, ...);
+
+
+/**
+ * Tiny snprintf/vsnprintf implementation
+ * \param buffer A pointer to the buffer where to store the formatted string
+ * \param count The maximum number of characters to store in the buffer, including a terminating null character
+ * \param format A string that specifies the format of the output
+ * \param va A value identifying a variable arguments list
+ * \return The number of characters that COULD have been written into the buffer, not counting the terminating
+ * null character. A value equal or larger than count indicates truncation. Only when the returned value
+ * is non-negative and less than count, the string has been completely written.
+ */
+#define snprintf snprintf_
+#define vsnprintf vsnprintf_
+int snprintf_(char* buffer, size_t count, const char* format, ...);
+int vsnprintf_(char* buffer, size_t count, const char* format, va_list va);
+
+
+/**
+ * Tiny vprintf implementation
+ * \param format A string that specifies the format of the output
+ * \param va A value identifying a variable arguments list
+ * \return The number of characters that are WRITTEN into the buffer, not counting the terminating null character
+ */
+#define vprintf vprintf_
+int vprintf_(const char* format, va_list va);
+
+
+/**
+ * printf with output function
+ * You may use this as dynamic alternative to printf() with its fixed _putchar() output
+ * \param out An output function which takes one character and an argument pointer
+ * \param arg An argument pointer for user data passed to output function
+ * \param format A string that specifies the format of the output
+ * \return The number of characters that are sent to the output function, not counting the terminating null character
+ */
+int fctprintf(void (*out)(char character, void* arg), void* arg, const char* format, ...);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif // _PRINTF_H_
diff --git a/lib/random.cc b/lib/random.cc new file mode 100644 index 0000000..428c75c --- /dev/null +++ b/lib/random.cc @@ -0,0 +1,152 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +#include <lume/random.h> +#include <arch/random.h> +#include <lume/klog.h> + +#include <lume/kprintf.h> + +/* + * Early Boot PRNG (xoshiro256**) + * State size: 256 bits (4 * 64-bit words) + * Extremely fast, excellent statistical properties. + */ + +static uint64 g_state[4]; +static bool g_initialized = false; +static uint64 g_init_seed = 0; +static RandomSeedSource g_seed_source = RandomSeedSource::Unknown; + +static inline uint64 rotl(const uint64 x, int k) { + return (x << k) | (x >> (64 - k)); +} + +/* SplitMix64 used to initialize xoshiro state from a single 64-bit seed */ +static uint64 splitmix64(uint64& state) { + uint64 z = (state += 0x9e3779b97f4a7c15ULL); + z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL; + z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL; + return z ^ (z >> 31); +} + +void random_early_init(uint64 seed) +{ + if (g_initialized) return; + + RandomSeedSource source = RandomSeedSource::Unknown; + + /* If seed is 0 (not provided by bootloader), try hardware */ + if (seed == 0) { + uint64 hw_val; + if (arch::get_hw_random(hw_val)) { + seed = hw_val; + source = RandomSeedSource::HwRandom; + } else { + /* Fallback: use boot cycles mixed with a constant */ + seed = arch::get_cycles() ^ 0xdeadbeefbadc0ffeULL; + source = RandomSeedSource::CycleFallback; + } + } else { + source = RandomSeedSource::FdtProvided; + } + + uint64 sm_state = seed; + g_state[0] = splitmix64(sm_state); + g_state[1] = splitmix64(sm_state); + g_state[2] = splitmix64(sm_state); + g_state[3] = splitmix64(sm_state); + + g_init_seed = seed; + g_seed_source = source; + g_initialized = true; + kprintf("[random] early PRNG initialized, seed=0x%llx, source=%s\n", + seed, random_seed_source_name(source)); +} + +uint64 get_random_u64() +{ + if (!g_initialized) { + random_early_init(0); + } + + const uint64 result = rotl(g_state[1] * 5, 7) * 9; + + const uint64 t = g_state[1] << 17; + + g_state[2] ^= g_state[0]; + g_state[3] ^= g_state[1]; + g_state[1] ^= g_state[2]; + g_state[0] ^= g_state[3]; + + g_state[2] ^= t; + g_state[3] = rotl(g_state[3], 45); + + /* Mix with current cycles for slight additional unpredictability */ + return result ^ arch::get_cycles(); +} + +uint32 get_random_u32() +{ + return static_cast<uint32>(get_random_u64() >> 32); +} + +void get_random_bytes(void* buf, size_t len) +{ + uint8* p = static_cast<uint8*>(buf); + while (len >= 8) { + uint64 val = get_random_u64(); + for (int i = 0; i < 8; i++) { + p[i] = (val >> (i * 8)) & 0xFF; + } + p += 8; + len -= 8; + } + if (len > 0) { + uint64 val = get_random_u64(); + for (size_t i = 0; i < len; i++) { + p[i] = (val >> (i * 8)) & 0xFF; + } + } +} + +void add_device_randomness(const void* buf, size_t len) +{ + /* + * For now, just mix into the xoshiro state using a simple XOR. + * In the future, this will feed the CSPRNG entropy pool. + */ + const uint8* p = static_cast<const uint8*>(buf); + uint64 mix = arch::get_cycles(); + for (size_t i = 0; i < len; i++) { + mix = (mix << 5) ^ (mix >> 59) ^ p[i]; + } + + g_state[0] ^= mix; + g_state[1] ^= arch::get_cycles(); +} + +RandomSeedSource random_early_seed_source() +{ + return g_seed_source; +} + +uint64 random_early_seed_value() +{ + return g_init_seed; +} + +const char* random_seed_source_name(RandomSeedSource source) +{ + switch (source) { + case RandomSeedSource::FdtProvided: + return "fdt"; + case RandomSeedSource::HwRandom: + return "hw"; + case RandomSeedSource::CycleFallback: + return "cycle"; + case RandomSeedSource::Unknown: + default: + return "unknown"; + } +} diff --git a/lib/rbtree.cc b/lib/rbtree.cc new file mode 100644 index 0000000..6718a1a --- /dev/null +++ b/lib/rbtree.cc @@ -0,0 +1,596 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <andrea@suse.de> + (C) 2002 David Woodhouse <dwmw2@infradead.org> + (C) 2012 Michel Lespinasse <walken@google.com> + + + linux/lib/rbtree.c +*/ + +#include <lume/rbtree_augmented.h> + + +/* + * red-black trees properties: https://en.wikipedia.org/wiki/Rbtree + * + * 1) A node is either red or black + * 2) The root is black + * 3) All leaves (nullptr) are black + * 4) Both children of every red node are black + * 5) Every simple path from root to leaves contains the same number + * of black nodes. + * + * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two + * consecutive red nodes in a path and every red node is therefore followed by + * a black. So if B is the number of black nodes on every simple path (as per + * 5), then the longest possible path due to 4 is 2B. + * + * We shall indicate color with case, where black nodes are uppercase and red + * nodes will be lowercase. Unknown color nodes shall be drawn as red within + * parentheses and have some accompanying text comment. + */ + +/* + * Notes on lockless lookups: + * + * All stores to the tree structure (rb_left and rb_right) must be done using + * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the + * tree structure as seen in program order. + * + * These two requirements will allow lockless iteration of the tree -- not + * correct iteration mind you, tree rotations are not atomic so a lookup might + * miss entire subtrees. + * + * But they do guarantee that any such traversal will only see valid elements + * and that it will indeed complete -- does not get stuck in a loop. + * + * It also guarantees that if the lookup returns an element it is the 'correct' + * one. But not returning an element does _NOT_ mean it's not present. + * + * NOTE: + * + * Stores to __rb_parent_color are not important for simple lookups so those + * are left undone as of now. Nor did I check for loops involving parent + * pointers. + */ + +static inline void rb_set_black(struct rb_node *rb) +{ + rb->__rb_parent_color += RB_BLACK; +} + +static inline struct rb_node *rb_red_parent(struct rb_node *red) +{ + return (struct rb_node *)red->__rb_parent_color; +} + +/* + * Helper function for rotations: + * - old's parent and color get assigned to _new + * - old gets assigned _new as a parent and 'color' as a color. + */ +static inline void +__rb_rotate_set_parents(struct rb_node *old, struct rb_node *_new, + struct rb_root *root, int color) +{ + struct rb_node *parent = rb_parent(old); + _new->__rb_parent_color = old->__rb_parent_color; + rb_set_parent_color(old, _new, color); + __rb_change_child(old, _new, parent, root); +} + +static __always_inline void +__rb_insert(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *_new)) +{ + struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; + + while (true) { + /* + * Loop invariant: node is red. + */ + if (unlikely(!parent)) { + /* + * The inserted node is root. Either this is the + * first node, or we recursed at Case 1 below and + * are no longer violating 4). + */ + rb_set_parent_color(node, nullptr, RB_BLACK); + break; + } + + /* + * If there is a black parent, we are done. + * Otherwise, take some corrective action as, + * per 4), we don't want a red root or two + * consecutive red nodes. + */ + if(rb_is_black(parent)) + break; + + gparent = rb_red_parent(parent); + + tmp = gparent->rb_right; + if (parent != tmp) { /* parent == gparent->rb_left */ + if (tmp && rb_is_red(tmp)) { + /* + * Case 1 - node's uncle is red (color flips). + * + * G g + * / \ / \ + * p u --> P U + * / / + * n n + * + * However, since g's parent might be red, and + * 4) does not allow this, we need to recurse + * at g. + */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; + } + + tmp = parent->rb_right; + if (node == tmp) { + /* + * Case 2 - node's uncle is black and node is + * the parent's right child (left rotate at parent). + * + * G G + * / \ / \ + * p U --> n U + * \ / + * n p + * + * This still leaves us in violation of 4), the + * continuation into Case 3 will fix that. + */ + tmp = node->rb_left; + WRITE_ONCE(parent->rb_right, tmp); + WRITE_ONCE(node->rb_left, parent); + if (tmp) + rb_set_parent_color(tmp, parent, + RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); + augment_rotate(parent, node); + parent = node; + tmp = node->rb_right; + } + + /* + * Case 3 - node's uncle is black and node is + * the parent's left child (right rotate at gparent). + * + * G P + * / \ / \ + * p U --> n g + * / \ + * n U + */ + WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */ + WRITE_ONCE(parent->rb_right, gparent); + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); + break; + } else { + tmp = gparent->rb_left; + if (tmp && rb_is_red(tmp)) { + /* Case 1 - color flips */ + rb_set_parent_color(tmp, gparent, RB_BLACK); + rb_set_parent_color(parent, gparent, RB_BLACK); + node = gparent; + parent = rb_parent(node); + rb_set_parent_color(node, parent, RB_RED); + continue; + } + + tmp = parent->rb_left; + if (node == tmp) { + /* Case 2 - right rotate at parent */ + tmp = node->rb_right; + WRITE_ONCE(parent->rb_left, tmp); + WRITE_ONCE(node->rb_right, parent); + if (tmp) + rb_set_parent_color(tmp, parent, + RB_BLACK); + rb_set_parent_color(parent, node, RB_RED); + augment_rotate(parent, node); + parent = node; + tmp = node->rb_left; + } + + /* Case 3 - left rotate at gparent */ + WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */ + WRITE_ONCE(parent->rb_left, gparent); + if (tmp) + rb_set_parent_color(tmp, gparent, RB_BLACK); + __rb_rotate_set_parents(gparent, parent, root, RB_RED); + augment_rotate(gparent, parent); + break; + } + } +} + +/* + * Inline version for rb_erase() use - we want to be able to inline + * and eliminate the dummy_rotate callback there + */ +static __always_inline void +____rb_erase_color(struct rb_node *parent, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *_new)) +{ + struct rb_node *node = nullptr, *sibling, *tmp1, *tmp2; + + while (true) { + /* + * Loop invariants: + * - node is black (or nullptr on first iteration) + * - node is not the root (parent is not nullptr) + * - All leaf paths going through parent and node have a + * black node count that is 1 lower than other leaf paths. + */ + sibling = parent->rb_right; + if (node != sibling) { /* node == parent->rb_left */ + if (rb_is_red(sibling)) { + /* + * Case 1 - left rotate at parent + * + * P S + * / \ / \ + * N s --> p Sr + * / \ / \ + * Sl Sr N Sl + */ + tmp1 = sibling->rb_left; + WRITE_ONCE(parent->rb_right, tmp1); + WRITE_ONCE(sibling->rb_left, parent); + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + augment_rotate(parent, sibling); + sibling = tmp1; + } + tmp1 = sibling->rb_right; + if (!tmp1 || rb_is_black(tmp1)) { + tmp2 = sibling->rb_left; + if (!tmp2 || rb_is_black(tmp2)) { + /* + * Case 2 - sibling color flip + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N s + * / \ / \ + * Sl Sr Sl Sr + * + * This leaves us violating 5) which + * can be fixed by flipping p to black + * if it was red, or by recursing at p. + * p is red when coming from Case 1. + */ + rb_set_parent_color(sibling, parent, + RB_RED); + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; + } + /* + * Case 3 - right rotate at sibling + * (p could be either color here) + * + * (p) (p) + * / \ / \ + * N S --> N sl + * / \ \ + * sl Sr S + * \ + * Sr + * + * Note: p might be red, and then both + * p and sl are red after rotation(which + * breaks property 4). This is fixed in + * Case 4 (in __rb_rotate_set_parents() + * which set sl the color of p + * and set p RB_BLACK) + * + * (p) (sl) + * / \ / \ + * N sl --> P S + * \ / \ + * S N Sr + * \ + * Sr + */ + tmp1 = tmp2->rb_right; + WRITE_ONCE(sibling->rb_left, tmp1); + WRITE_ONCE(tmp2->rb_right, sibling); + WRITE_ONCE(parent->rb_right, tmp2); + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; + } + /* + * Case 4 - left rotate at parent + color flips + * (p and sl could be either color here. + * After rotation, p becomes black, s acquires + * p's color, and sl keeps its color) + * + * (p) (s) + * / \ / \ + * N S --> P Sr + * / \ / \ + * (sl) sr N (sl) + */ + tmp2 = sibling->rb_left; + WRITE_ONCE(parent->rb_right, tmp2); + WRITE_ONCE(sibling->rb_left, parent); + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); + augment_rotate(parent, sibling); + break; + } else { + sibling = parent->rb_left; + if (rb_is_red(sibling)) { + /* Case 1 - right rotate at parent */ + tmp1 = sibling->rb_right; + WRITE_ONCE(parent->rb_left, tmp1); + WRITE_ONCE(sibling->rb_right, parent); + rb_set_parent_color(tmp1, parent, RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, + RB_RED); + augment_rotate(parent, sibling); + sibling = tmp1; + } + tmp1 = sibling->rb_left; + if (!tmp1 || rb_is_black(tmp1)) { + tmp2 = sibling->rb_right; + if (!tmp2 || rb_is_black(tmp2)) { + /* Case 2 - sibling color flip */ + rb_set_parent_color(sibling, parent, + RB_RED); + if (rb_is_red(parent)) + rb_set_black(parent); + else { + node = parent; + parent = rb_parent(node); + if (parent) + continue; + } + break; + } + /* Case 3 - left rotate at sibling */ + tmp1 = tmp2->rb_left; + WRITE_ONCE(sibling->rb_right, tmp1); + WRITE_ONCE(tmp2->rb_left, sibling); + WRITE_ONCE(parent->rb_left, tmp2); + if (tmp1) + rb_set_parent_color(tmp1, sibling, + RB_BLACK); + augment_rotate(sibling, tmp2); + tmp1 = sibling; + sibling = tmp2; + } + /* Case 4 - right rotate at parent + color flips */ + tmp2 = sibling->rb_right; + WRITE_ONCE(parent->rb_left, tmp2); + WRITE_ONCE(sibling->rb_right, parent); + rb_set_parent_color(tmp1, sibling, RB_BLACK); + if (tmp2) + rb_set_parent(tmp2, parent); + __rb_rotate_set_parents(parent, sibling, root, + RB_BLACK); + augment_rotate(parent, sibling); + break; + } + } +} + +/* Non-inline version for rb_erase_augmented() use */ +void __rb_erase_color(struct rb_node *parent, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *_new)) +{ + ____rb_erase_color(parent, root, augment_rotate); +} + +/* + * Non-augmented rbtree manipulation functions. + * + * We use dummy augmented callbacks here, and have the compiler optimize them + * out of the rb_insert_color() and rb_erase() function definitions. + */ + +static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} +static inline void dummy_copy(struct rb_node *old, struct rb_node *_new) {} +static inline void dummy_rotate(struct rb_node *old, struct rb_node *_new) {} + +static const struct rb_augment_callbacks dummy_callbacks = { + .propagate = dummy_propagate, + .copy = dummy_copy, + .rotate = dummy_rotate +}; + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + __rb_insert(node, root, dummy_rotate); +} + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *rebalance; + rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); + if (rebalance) + ____rb_erase_color(rebalance, root, dummy_rotate); +} + + +/* + * Augmented rbtree manipulation functions. + * + * This instantiates the same __always_inline functions as in the non-augmented + * case, but this time with user-defined callbacks. + */ + +void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, + void (*augment_rotate)(struct rb_node *old, struct rb_node *_new)) +{ + __rb_insert(node, root, augment_rotate); +} + +struct rb_node *rb_next(const struct rb_node *node) +{ + struct rb_node *parent; + + if (RB_EMPTY_NODE(node)) + return nullptr; + + /* + * If we have a right-hand child, go down and then left as far + * as we can. + */ + if (node->rb_right) { + node = node->rb_right; + while (node->rb_left) + node = node->rb_left; + return (struct rb_node *)node; + } + + /* + * No right-hand children. Everything down and left is smaller than us, + * so any 'next' node must be in the general direction of our parent. + * Go up the tree; any time the ancestor is a right-hand child of its + * parent, keep going up. First time it's a left-hand child of its + * parent, said parent is our 'next' node. + */ + while ((parent = rb_parent(node)) && node == parent->rb_right) + node = parent; + + return parent; +} + +struct rb_node *rb_prev(const struct rb_node *node) +{ + struct rb_node *parent; + + if (RB_EMPTY_NODE(node)) + return nullptr; + + /* + * If we have a left-hand child, go down and then right as far + * as we can. + */ + if (node->rb_left) { + node = node->rb_left; + while (node->rb_right) + node = node->rb_right; + return (struct rb_node *)node; + } + + /* + * No left-hand children. Go up till we find an ancestor which + * is a right-hand child of its parent. + */ + while ((parent = rb_parent(node)) && node == parent->rb_left) + node = parent; + + return parent; +} + +void rb_replace_node(struct rb_node *victim, struct rb_node *_new, + struct rb_root *root) +{ + struct rb_node *parent = rb_parent(victim); + + /* Copy the pointers/colour from the victim to the replacement */ + *_new = *victim; + + /* Set the surrounding nodes to point to the replacement */ + if (victim->rb_left) + rb_set_parent(victim->rb_left, _new); + if (victim->rb_right) + rb_set_parent(victim->rb_right, _new); + __rb_change_child(victim, _new, parent, root); +} + + +static struct rb_node *rb_left_deepest_node(const struct rb_node *node) +{ + for (;;) { + if (node->rb_left) + node = node->rb_left; + else if (node->rb_right) + node = node->rb_right; + else + return (struct rb_node *)node; + } +} + +struct rb_node *rb_next_postorder(const struct rb_node *node) +{ + const struct rb_node *parent; + if (!node) + return nullptr; + parent = rb_parent(node); + + /* If we're sitting on node, we've already seen our children */ + if (parent && node == parent->rb_left && parent->rb_right) { + /* If we are the parent's left node, go to the parent's right + * node then all the way down to the left */ + return rb_left_deepest_node(parent->rb_right); + } else + /* Otherwise we are the parent's right node, and the parent + * should be next */ + return (struct rb_node *)parent; +} + +struct rb_node *rb_first_postorder(const struct rb_root *root) +{ + if (!root->rb_node) + return nullptr; + + return rb_left_deepest_node(root->rb_node); +} + +struct rb_node *rb_first(const struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return nullptr; + while (n->rb_left) + n = n->rb_left; + return n; +} + +struct rb_node *rb_last(const struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return nullptr; + while (n->rb_right) + n = n->rb_right; + return n; +} diff --git a/lib/string/COPYRIGHT b/lib/string/COPYRIGHT new file mode 100644 index 0000000..2f15edc --- /dev/null +++ b/lib/string/COPYRIGHT @@ -0,0 +1,193 @@ +musl as a whole is licensed under the following standard MIT license: + +---------------------------------------------------------------------- +Copyright © 2005-2020 Rich Felker, et al. + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +---------------------------------------------------------------------- + +Authors/contributors include: + +A. Wilcox +Ada Worcester +Alex Dowad +Alex Suykov +Alexander Monakov +Andre McCurdy +Andrew Kelley +Anthony G. Basile +Aric Belsito +Arvid Picciani +Bartosz Brachaczek +Benjamin Peterson +Bobby Bingham +Boris Brezillon +Brent Cook +Chris Spiegel +Clément Vasseur +Daniel Micay +Daniel Sabogal +Daurnimator +David Carlier +David Edelsohn +Denys Vlasenko +Dmitry Ivanov +Dmitry V. Levin +Drew DeVault +Emil Renner Berthing +Fangrui Song +Felix Fietkau +Felix Janda +Gianluca Anzolin +Hauke Mehrtens +He X +Hiltjo Posthuma +Isaac Dunham +Jaydeep Patil +Jens Gustedt +Jeremy Huntwork +Jo-Philipp Wich +Joakim Sindholt +John Spencer +Julien Ramseier +Justin Cormack +Kaarle Ritvanen +Khem Raj +Kylie McClain +Leah Neukirchen +Luca Barbato +Luka Perkov +Lynn Ochs +M Farkas-Dyck (Strake) +Mahesh Bodapati +Markus Wichmann +Masanori Ogino +Michael Clark +Michael Forney +Mikhail Kremnyov +Natanael Copa +Nicholas J. Kain +orc +Pascal Cuoq +Patrick Oppenlander +Petr Hosek +Petr Skocik +Pierre Carrier +Reini Urban +Rich Felker +Richard Pennington +Ryan Fairfax +Samuel Holland +Segev Finer +Shiz +sin +Solar Designer +Stefan Kristiansson +Stefan O'Rear +Szabolcs Nagy +Timo Teräs +Trutz Behn +Will Dietz +William Haddon +William Pitcock + +Portions of this software are derived from third-party works licensed +under terms compatible with the above MIT license: + +The TRE regular expression implementation (src/regex/reg* and +src/regex/tre*) is Copyright © 2001-2008 Ville Laurikari and licensed +under a 2-clause BSD license (license text in the source files). The +included version has been heavily modified by Rich Felker in 2012, in +the interests of size, simplicity, and namespace cleanliness. + +Much of the math library code (src/math/* and src/complex/*) is +Copyright © 1993,2004 Sun Microsystems or +Copyright © 2003-2011 David Schultz or +Copyright © 2003-2009 Steven G. Kargl or +Copyright © 2003-2009 Bruce D. Evans or +Copyright © 2008 Stephen L. Moshier or +Copyright © 2017-2018 Arm Limited +and labelled as such in comments in the individual source files. All +have been licensed under extremely permissive terms. + +The ARM memcpy code (src/string/arm/memcpy.S) is Copyright © 2008 +The Android Open Source Project and is licensed under a two-clause BSD +license. It was taken from Bionic libc, used on Android. + +The AArch64 memcpy and memset code (src/string/aarch64/*) are +Copyright © 1999-2019, Arm Limited. + +The implementation of DES for crypt (src/crypt/crypt_des.c) is +Copyright © 1994 David Burren. It is licensed under a BSD license. + +The implementation of blowfish crypt (src/crypt/crypt_blowfish.c) was +originally written by Solar Designer and placed into the public +domain. The code also comes with a fallback permissive license for use +in jurisdictions that may not recognize the public domain. + +The smoothsort implementation (src/stdlib/qsort.c) is Copyright © 2011 +Lynn Ochs and is licensed under an MIT-style license. + +The x86_64 port was written by Nicholas J. Kain and is licensed under +the standard MIT terms. + +The mips and microblaze ports were originally written by Richard +Pennington for use in the ellcc project. The original code was adapted +by Rich Felker for build system and code conventions during upstream +integration. It is licensed under the standard MIT terms. + +The mips64 port was contributed by Imagination Technologies and is +licensed under the standard MIT terms. + +The powerpc port was also originally written by Richard Pennington, +and later supplemented and integrated by John Spencer. It is licensed +under the standard MIT terms. + +All other files which have no copyright comments are original works +produced specifically for use as part of this library, written either +by Rich Felker, the main author of the library, or by one or more +contibutors listed above. Details on authorship of individual files +can be found in the git version control history of the project. The +omission of copyright and license comments in each file is in the +interest of source tree size. + +In addition, permission is hereby granted for all public header files +(include/* and arch/*/bits/*) and crt files intended to be linked into +applications (crt/*, ldso/dlstart.c, and arch/*/crt_arch.h) to omit +the copyright notice and permission notice otherwise required by the +license, and to use these files without any requirement of +attribution. These files include substantial contributions from: + +Bobby Bingham +John Spencer +Nicholas J. Kain +Rich Felker +Richard Pennington +Stefan Kristiansson +Szabolcs Nagy + +all of whom have explicitly granted such permission. + +This file previously contained text expressing a belief that most of +the files covered by the above exception were sufficiently trivial not +to be subject to copyright, resulting in confusion over whether it +negated the permissions granted in the license. In the spirit of +permissive licensing, and of not having licensing issues being an +obstacle to adoption, that text has been removed. diff --git a/lib/string/aarch64/memcpy.S b/lib/string/aarch64/memcpy.S new file mode 100644 index 0000000..48bb8a8 --- /dev/null +++ b/lib/string/aarch64/memcpy.S @@ -0,0 +1,186 @@ +/* + * memcpy - copy memory area + * + * Copyright (c) 2012-2020, Arm Limited. + * SPDX-License-Identifier: MIT + */ + +/* Assumptions: + * + * ARMv8-a, AArch64, unaligned accesses. + * + */ + +#define dstin x0 +#define src x1 +#define count x2 +#define dst x3 +#define srcend x4 +#define dstend x5 +#define A_l x6 +#define A_lw w6 +#define A_h x7 +#define B_l x8 +#define B_lw w8 +#define B_h x9 +#define C_l x10 +#define C_lw w10 +#define C_h x11 +#define D_l x12 +#define D_h x13 +#define E_l x14 +#define E_h x15 +#define F_l x16 +#define F_h x17 +#define G_l count +#define G_h dst +#define H_l src +#define H_h srcend +#define tmp1 x14 + +/* This implementation of memcpy uses unaligned accesses and branchless + sequences to keep the code small, simple and improve performance. + + Copies are split into 3 main cases: small copies of up to 32 bytes, medium + copies of up to 128 bytes, and large copies. The overhead of the overlap + check is negligible since it is only required for large copies. + + Large copies use a software pipelined loop processing 64 bytes per iteration. + The destination pointer is 16-byte aligned to minimize unaligned accesses. + The loop tail is handled by always copying 64 bytes from the end. +*/ + +.global memcpy +.type memcpy,%function +memcpy: + add srcend, src, count + add dstend, dstin, count + cmp count, 128 + b.hi .Lcopy_long + cmp count, 32 + b.hi .Lcopy32_128 + + /* Small copies: 0..32 bytes. */ + cmp count, 16 + b.lo .Lcopy16 + ldp A_l, A_h, [src] + ldp D_l, D_h, [srcend, -16] + stp A_l, A_h, [dstin] + stp D_l, D_h, [dstend, -16] + ret + + /* Copy 8-15 bytes. */ +.Lcopy16: + tbz count, 3, .Lcopy8 + ldr A_l, [src] + ldr A_h, [srcend, -8] + str A_l, [dstin] + str A_h, [dstend, -8] + ret + + .p2align 3 + /* Copy 4-7 bytes. */ +.Lcopy8: + tbz count, 2, .Lcopy4 + ldr A_lw, [src] + ldr B_lw, [srcend, -4] + str A_lw, [dstin] + str B_lw, [dstend, -4] + ret + + /* Copy 0..3 bytes using a branchless sequence. */ +.Lcopy4: + cbz count, .Lcopy0 + lsr tmp1, count, 1 + ldrb A_lw, [src] + ldrb C_lw, [srcend, -1] + ldrb B_lw, [src, tmp1] + strb A_lw, [dstin] + strb B_lw, [dstin, tmp1] + strb C_lw, [dstend, -1] +.Lcopy0: + ret + + .p2align 4 + /* Medium copies: 33..128 bytes. */ +.Lcopy32_128: + ldp A_l, A_h, [src] + ldp B_l, B_h, [src, 16] + ldp C_l, C_h, [srcend, -32] + ldp D_l, D_h, [srcend, -16] + cmp count, 64 + b.hi .Lcopy128 + stp A_l, A_h, [dstin] + stp B_l, B_h, [dstin, 16] + stp C_l, C_h, [dstend, -32] + stp D_l, D_h, [dstend, -16] + ret + + .p2align 4 + /* Copy 65..128 bytes. */ +.Lcopy128: + ldp E_l, E_h, [src, 32] + ldp F_l, F_h, [src, 48] + cmp count, 96 + b.ls .Lcopy96 + ldp G_l, G_h, [srcend, -64] + ldp H_l, H_h, [srcend, -48] + stp G_l, G_h, [dstend, -64] + stp H_l, H_h, [dstend, -48] +.Lcopy96: + stp A_l, A_h, [dstin] + stp B_l, B_h, [dstin, 16] + stp E_l, E_h, [dstin, 32] + stp F_l, F_h, [dstin, 48] + stp C_l, C_h, [dstend, -32] + stp D_l, D_h, [dstend, -16] + ret + + .p2align 4 + /* Copy more than 128 bytes. */ +.Lcopy_long: + + /* Copy 16 bytes and then align dst to 16-byte alignment. */ + + ldp D_l, D_h, [src] + and tmp1, dstin, 15 + bic dst, dstin, 15 + sub src, src, tmp1 + add count, count, tmp1 /* Count is now 16 too large. */ + ldp A_l, A_h, [src, 16] + stp D_l, D_h, [dstin] + ldp B_l, B_h, [src, 32] + ldp C_l, C_h, [src, 48] + ldp D_l, D_h, [src, 64]! + subs count, count, 128 + 16 /* Test and readjust count. */ + b.ls .Lcopy64_from_end + +.Lloop64: + stp A_l, A_h, [dst, 16] + ldp A_l, A_h, [src, 16] + stp B_l, B_h, [dst, 32] + ldp B_l, B_h, [src, 32] + stp C_l, C_h, [dst, 48] + ldp C_l, C_h, [src, 48] + stp D_l, D_h, [dst, 64]! + ldp D_l, D_h, [src, 64]! + subs count, count, 64 + b.hi .Lloop64 + + /* Write the last iteration and copy 64 bytes from the end. */ +.Lcopy64_from_end: + ldp E_l, E_h, [srcend, -64] + stp A_l, A_h, [dst, 16] + ldp A_l, A_h, [srcend, -48] + stp B_l, B_h, [dst, 32] + ldp B_l, B_h, [srcend, -32] + stp C_l, C_h, [dst, 48] + ldp C_l, C_h, [srcend, -16] + stp D_l, D_h, [dst, 64] + stp E_l, E_h, [dstend, -64] + stp A_l, A_h, [dstend, -48] + stp B_l, B_h, [dstend, -32] + stp C_l, C_h, [dstend, -16] + ret + +.size memcpy,.-memcpy diff --git a/lib/string/aarch64/memset.S b/lib/string/aarch64/memset.S new file mode 100644 index 0000000..f0d29b7 --- /dev/null +++ b/lib/string/aarch64/memset.S @@ -0,0 +1,115 @@ +/* + * memset - fill memory with a constant byte + * + * Copyright (c) 2012-2020, Arm Limited. + * SPDX-License-Identifier: MIT + */ + +/* Assumptions: + * + * ARMv8-a, AArch64, Advanced SIMD, unaligned accesses. + * + */ + +#define dstin x0 +#define val x1 +#define valw w1 +#define count x2 +#define dst x3 +#define dstend x4 +#define zva_val x5 + +.global memset +.type memset,%function +memset: + + dup v0.16B, valw + add dstend, dstin, count + + cmp count, 96 + b.hi .Lset_long + cmp count, 16 + b.hs .Lset_medium + mov val, v0.D[0] + + /* Set 0..15 bytes. */ + tbz count, 3, 1f + str val, [dstin] + str val, [dstend, -8] + ret + nop +1: tbz count, 2, 2f + str valw, [dstin] + str valw, [dstend, -4] + ret +2: cbz count, 3f + strb valw, [dstin] + tbz count, 1, 3f + strh valw, [dstend, -2] +3: ret + + /* Set 17..96 bytes. */ +.Lset_medium: + str q0, [dstin] + tbnz count, 6, .Lset96 + str q0, [dstend, -16] + tbz count, 5, 1f + str q0, [dstin, 16] + str q0, [dstend, -32] +1: ret + + .p2align 4 + /* Set 64..96 bytes. Write 64 bytes from the start and + 32 bytes from the end. */ +.Lset96: + str q0, [dstin, 16] + stp q0, q0, [dstin, 32] + stp q0, q0, [dstend, -32] + ret + + .p2align 4 +.Lset_long: + and valw, valw, 255 + bic dst, dstin, 15 + str q0, [dstin] + cmp count, 160 + ccmp valw, 0, 0, hs + b.ne .Lno_zva + +#ifndef SKIP_ZVA_CHECK + mrs zva_val, dczid_el0 + and zva_val, zva_val, 31 + cmp zva_val, 4 /* ZVA size is 64 bytes. */ + b.ne .Lno_zva +#endif + str q0, [dst, 16] + stp q0, q0, [dst, 32] + bic dst, dst, 63 + sub count, dstend, dst /* Count is now 64 too large. */ + sub count, count, 128 /* Adjust count and bias for loop. */ + + .p2align 4 +.Lzva_loop: + add dst, dst, 64 + dc zva, dst + subs count, count, 64 + b.hi .Lzva_loop + stp q0, q0, [dstend, -64] + stp q0, q0, [dstend, -32] + ret + +.Lno_zva: + sub count, dstend, dst /* Count is 16 too large. */ + sub dst, dst, 16 /* Dst is biased by -32. */ + sub count, count, 64 + 16 /* Adjust count and bias for loop. */ +.Lno_zva_loop: + stp q0, q0, [dst, 32] + stp q0, q0, [dst, 64]! + subs count, count, 64 + b.hi .Lno_zva_loop + stp q0, q0, [dstend, -64] + stp q0, q0, [dstend, -32] + ret + +.size memset,.-memset + diff --git a/lib/string/arm/__aeabi_memcpy.s b/lib/string/arm/__aeabi_memcpy.s new file mode 100644 index 0000000..3a527e4 --- /dev/null +++ b/lib/string/arm/__aeabi_memcpy.s @@ -0,0 +1,45 @@ +.syntax unified + +.global __aeabi_memcpy8 +.global __aeabi_memcpy4 +.global __aeabi_memcpy +.global __aeabi_memmove8 +.global __aeabi_memmove4 +.global __aeabi_memmove + +.type __aeabi_memcpy8,%function +.type __aeabi_memcpy4,%function +.type __aeabi_memcpy,%function +.type __aeabi_memmove8,%function +.type __aeabi_memmove4,%function +.type __aeabi_memmove,%function + +__aeabi_memmove8: +__aeabi_memmove4: +__aeabi_memmove: + cmp r0, r1 + bls 3f + cmp r2, #0 + beq 2f + adds r0, r0, r2 + adds r2, r1, r2 +1: subs r2, r2, #1 + ldrb r3, [r2] + subs r0, r0, #1 + strb r3, [r0] + cmp r1, r2 + bne 1b +2: bx lr +__aeabi_memcpy8: +__aeabi_memcpy4: +__aeabi_memcpy: +3: cmp r2, #0 + beq 2f + adds r2, r1, r2 +1: ldrb r3, [r1] + adds r1, r1, #1 + strb r3, [r0] + adds r0, r0, #1 + cmp r1, r2 + bne 1b +2: bx lr diff --git a/lib/string/arm/__aeabi_memset.s b/lib/string/arm/__aeabi_memset.s new file mode 100644 index 0000000..f9f6058 --- /dev/null +++ b/lib/string/arm/__aeabi_memset.s @@ -0,0 +1,31 @@ +.syntax unified + +.global __aeabi_memclr8 +.global __aeabi_memclr4 +.global __aeabi_memclr +.global __aeabi_memset8 +.global __aeabi_memset4 +.global __aeabi_memset + +.type __aeabi_memclr8,%function +.type __aeabi_memclr4,%function +.type __aeabi_memclr,%function +.type __aeabi_memset8,%function +.type __aeabi_memset4,%function +.type __aeabi_memset,%function + +__aeabi_memclr8: +__aeabi_memclr4: +__aeabi_memclr: + movs r2, #0 +__aeabi_memset8: +__aeabi_memset4: +__aeabi_memset: + cmp r1, #0 + beq 2f + adds r1, r0, r1 +1: strb r2, [r0] + adds r0, r0, #1 + cmp r1, r0 + bne 1b +2: bx lr diff --git a/lib/string/arm/memcpy.S b/lib/string/arm/memcpy.S new file mode 100644 index 0000000..869e344 --- /dev/null +++ b/lib/string/arm/memcpy.S @@ -0,0 +1,479 @@ +/* + * Copyright (C) 2008 The Android Open Source Project + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + + +/* + * Optimized memcpy() for ARM. + * + * note that memcpy() always returns the destination pointer, + * so we have to preserve R0. + */ + +/* + * This file has been modified from the original for use in musl libc. + * The main changes are: addition of .type memcpy,%function to make the + * code safely callable from thumb mode, adjusting the return + * instructions to be compatible with pre-thumb ARM cpus, removal of + * prefetch code that is not compatible with older cpus and support for + * building as thumb 2 and big-endian. + */ + +.syntax unified + +.global memcpy +.type memcpy,%function +memcpy: + /* The stack must always be 64-bits aligned to be compliant with the + * ARM ABI. Since we have to save R0, we might as well save R4 + * which we can use for better pipelining of the reads below + */ + .fnstart + .save {r0, r4, lr} + stmfd sp!, {r0, r4, lr} + /* Making room for r5-r11 which will be spilled later */ + .pad #28 + sub sp, sp, #28 + + /* it simplifies things to take care of len<4 early */ + cmp r2, #4 + blo copy_last_3_and_return + + /* compute the offset to align the source + * offset = (4-(src&3))&3 = -src & 3 + */ + rsb r3, r1, #0 + ands r3, r3, #3 + beq src_aligned + + /* align source to 32 bits. We need to insert 2 instructions between + * a ldr[b|h] and str[b|h] because byte and half-word instructions + * stall 2 cycles. + */ + movs r12, r3, lsl #31 + sub r2, r2, r3 /* we know that r3 <= r2 because r2 >= 4 */ + ldrbmi r3, [r1], #1 + ldrbcs r4, [r1], #1 + ldrbcs r12,[r1], #1 + strbmi r3, [r0], #1 + strbcs r4, [r0], #1 + strbcs r12,[r0], #1 + +src_aligned: + + /* see if src and dst are aligned together (congruent) */ + eor r12, r0, r1 + tst r12, #3 + bne non_congruent + + /* Use post-incriment mode for stm to spill r5-r11 to reserved stack + * frame. Don't update sp. + */ + stmea sp, {r5-r11} + + /* align the destination to a cache-line */ + rsb r3, r0, #0 + ands r3, r3, #0x1C + beq congruent_aligned32 + cmp r3, r2 + andhi r3, r2, #0x1C + + /* conditionnaly copies 0 to 7 words (length in r3) */ + movs r12, r3, lsl #28 + ldmcs r1!, {r4, r5, r6, r7} /* 16 bytes */ + ldmmi r1!, {r8, r9} /* 8 bytes */ + stmcs r0!, {r4, r5, r6, r7} + stmmi r0!, {r8, r9} + tst r3, #0x4 + ldrne r10,[r1], #4 /* 4 bytes */ + strne r10,[r0], #4 + sub r2, r2, r3 + +congruent_aligned32: + /* + * here source is aligned to 32 bytes. + */ + +cached_aligned32: + subs r2, r2, #32 + blo less_than_32_left + + /* + * We preload a cache-line up to 64 bytes ahead. On the 926, this will + * stall only until the requested world is fetched, but the linefill + * continues in the the background. + * While the linefill is going, we write our previous cache-line + * into the write-buffer (which should have some free space). + * When the linefill is done, the writebuffer will + * start dumping its content into memory + * + * While all this is going, we then load a full cache line into + * 8 registers, this cache line should be in the cache by now + * (or partly in the cache). + * + * This code should work well regardless of the source/dest alignment. + * + */ + + /* Align the preload register to a cache-line because the cpu does + * "critical word first" (the first word requested is loaded first). + */ + @ bic r12, r1, #0x1F + @ add r12, r12, #64 + +1: ldmia r1!, { r4-r11 } + subs r2, r2, #32 + + /* + * NOTE: if r12 is more than 64 ahead of r1, the following ldrhi + * for ARM9 preload will not be safely guarded by the preceding subs. + * When it is safely guarded the only possibility to have SIGSEGV here + * is because the caller overstates the length. + */ + @ ldrhi r3, [r12], #32 /* cheap ARM9 preload */ + stmia r0!, { r4-r11 } + bhs 1b + + add r2, r2, #32 + +less_than_32_left: + /* + * less than 32 bytes left at this point (length in r2) + */ + + /* skip all this if there is nothing to do, which should + * be a common case (if not executed the code below takes + * about 16 cycles) + */ + tst r2, #0x1F + beq 1f + + /* conditionnaly copies 0 to 31 bytes */ + movs r12, r2, lsl #28 + ldmcs r1!, {r4, r5, r6, r7} /* 16 bytes */ + ldmmi r1!, {r8, r9} /* 8 bytes */ + stmcs r0!, {r4, r5, r6, r7} + stmmi r0!, {r8, r9} + movs r12, r2, lsl #30 + ldrcs r3, [r1], #4 /* 4 bytes */ + ldrhmi r4, [r1], #2 /* 2 bytes */ + strcs r3, [r0], #4 + strhmi r4, [r0], #2 + tst r2, #0x1 + ldrbne r3, [r1] /* last byte */ + strbne r3, [r0] + + /* we're done! restore everything and return */ +1: ldmfd sp!, {r5-r11} + ldmfd sp!, {r0, r4, lr} + bx lr + + /********************************************************************/ + +non_congruent: + /* + * here source is aligned to 4 bytes + * but destination is not. + * + * in the code below r2 is the number of bytes read + * (the number of bytes written is always smaller, because we have + * partial words in the shift queue) + */ + cmp r2, #4 + blo copy_last_3_and_return + + /* Use post-incriment mode for stm to spill r5-r11 to reserved stack + * frame. Don't update sp. + */ + stmea sp, {r5-r11} + + /* compute shifts needed to align src to dest */ + rsb r5, r0, #0 + and r5, r5, #3 /* r5 = # bytes in partial words */ + mov r12, r5, lsl #3 /* r12 = right */ + rsb lr, r12, #32 /* lr = left */ + + /* read the first word */ + ldr r3, [r1], #4 + sub r2, r2, #4 + + /* write a partial word (0 to 3 bytes), such that destination + * becomes aligned to 32 bits (r5 = nb of words to copy for alignment) + */ + movs r5, r5, lsl #31 + +#if __ARMEB__ + movmi r3, r3, ror #24 + strbmi r3, [r0], #1 + movcs r3, r3, ror #24 + strbcs r3, [r0], #1 + movcs r3, r3, ror #24 + strbcs r3, [r0], #1 +#else + strbmi r3, [r0], #1 + movmi r3, r3, lsr #8 + strbcs r3, [r0], #1 + movcs r3, r3, lsr #8 + strbcs r3, [r0], #1 + movcs r3, r3, lsr #8 +#endif + + cmp r2, #4 + blo partial_word_tail + +#if __ARMEB__ + mov r3, r3, lsr r12 + mov r3, r3, lsl r12 +#endif + + /* Align destination to 32 bytes (cache line boundary) */ +1: tst r0, #0x1c + beq 2f + ldr r5, [r1], #4 + sub r2, r2, #4 +#if __ARMEB__ + mov r4, r5, lsr lr + orr r4, r4, r3 + mov r3, r5, lsl r12 +#else + mov r4, r5, lsl lr + orr r4, r4, r3 + mov r3, r5, lsr r12 +#endif + str r4, [r0], #4 + cmp r2, #4 + bhs 1b + blo partial_word_tail + + /* copy 32 bytes at a time */ +2: subs r2, r2, #32 + blo less_than_thirtytwo + + /* Use immediate mode for the shifts, because there is an extra cycle + * for register shifts, which could account for up to 50% of + * performance hit. + */ + + cmp r12, #24 + beq loop24 + cmp r12, #8 + beq loop8 + +loop16: + ldr r12, [r1], #4 +1: mov r4, r12 + ldmia r1!, { r5,r6,r7, r8,r9,r10,r11} + subs r2, r2, #32 + ldrhs r12, [r1], #4 +#if __ARMEB__ + orr r3, r3, r4, lsr #16 + mov r4, r4, lsl #16 + orr r4, r4, r5, lsr #16 + mov r5, r5, lsl #16 + orr r5, r5, r6, lsr #16 + mov r6, r6, lsl #16 + orr r6, r6, r7, lsr #16 + mov r7, r7, lsl #16 + orr r7, r7, r8, lsr #16 + mov r8, r8, lsl #16 + orr r8, r8, r9, lsr #16 + mov r9, r9, lsl #16 + orr r9, r9, r10, lsr #16 + mov r10, r10, lsl #16 + orr r10, r10, r11, lsr #16 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsl #16 +#else + orr r3, r3, r4, lsl #16 + mov r4, r4, lsr #16 + orr r4, r4, r5, lsl #16 + mov r5, r5, lsr #16 + orr r5, r5, r6, lsl #16 + mov r6, r6, lsr #16 + orr r6, r6, r7, lsl #16 + mov r7, r7, lsr #16 + orr r7, r7, r8, lsl #16 + mov r8, r8, lsr #16 + orr r8, r8, r9, lsl #16 + mov r9, r9, lsr #16 + orr r9, r9, r10, lsl #16 + mov r10, r10, lsr #16 + orr r10, r10, r11, lsl #16 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsr #16 +#endif + bhs 1b + b less_than_thirtytwo + +loop8: + ldr r12, [r1], #4 +1: mov r4, r12 + ldmia r1!, { r5,r6,r7, r8,r9,r10,r11} + subs r2, r2, #32 + ldrhs r12, [r1], #4 +#if __ARMEB__ + orr r3, r3, r4, lsr #24 + mov r4, r4, lsl #8 + orr r4, r4, r5, lsr #24 + mov r5, r5, lsl #8 + orr r5, r5, r6, lsr #24 + mov r6, r6, lsl #8 + orr r6, r6, r7, lsr #24 + mov r7, r7, lsl #8 + orr r7, r7, r8, lsr #24 + mov r8, r8, lsl #8 + orr r8, r8, r9, lsr #24 + mov r9, r9, lsl #8 + orr r9, r9, r10, lsr #24 + mov r10, r10, lsl #8 + orr r10, r10, r11, lsr #24 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsl #8 +#else + orr r3, r3, r4, lsl #24 + mov r4, r4, lsr #8 + orr r4, r4, r5, lsl #24 + mov r5, r5, lsr #8 + orr r5, r5, r6, lsl #24 + mov r6, r6, lsr #8 + orr r6, r6, r7, lsl #24 + mov r7, r7, lsr #8 + orr r7, r7, r8, lsl #24 + mov r8, r8, lsr #8 + orr r8, r8, r9, lsl #24 + mov r9, r9, lsr #8 + orr r9, r9, r10, lsl #24 + mov r10, r10, lsr #8 + orr r10, r10, r11, lsl #24 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsr #8 +#endif + bhs 1b + b less_than_thirtytwo + +loop24: + ldr r12, [r1], #4 +1: mov r4, r12 + ldmia r1!, { r5,r6,r7, r8,r9,r10,r11} + subs r2, r2, #32 + ldrhs r12, [r1], #4 +#if __ARMEB__ + orr r3, r3, r4, lsr #8 + mov r4, r4, lsl #24 + orr r4, r4, r5, lsr #8 + mov r5, r5, lsl #24 + orr r5, r5, r6, lsr #8 + mov r6, r6, lsl #24 + orr r6, r6, r7, lsr #8 + mov r7, r7, lsl #24 + orr r7, r7, r8, lsr #8 + mov r8, r8, lsl #24 + orr r8, r8, r9, lsr #8 + mov r9, r9, lsl #24 + orr r9, r9, r10, lsr #8 + mov r10, r10, lsl #24 + orr r10, r10, r11, lsr #8 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsl #24 +#else + orr r3, r3, r4, lsl #8 + mov r4, r4, lsr #24 + orr r4, r4, r5, lsl #8 + mov r5, r5, lsr #24 + orr r5, r5, r6, lsl #8 + mov r6, r6, lsr #24 + orr r6, r6, r7, lsl #8 + mov r7, r7, lsr #24 + orr r7, r7, r8, lsl #8 + mov r8, r8, lsr #24 + orr r8, r8, r9, lsl #8 + mov r9, r9, lsr #24 + orr r9, r9, r10, lsl #8 + mov r10, r10, lsr #24 + orr r10, r10, r11, lsl #8 + stmia r0!, {r3,r4,r5,r6, r7,r8,r9,r10} + mov r3, r11, lsr #24 +#endif + bhs 1b + +less_than_thirtytwo: + /* copy the last 0 to 31 bytes of the source */ + rsb r12, lr, #32 /* we corrupted r12, recompute it */ + add r2, r2, #32 + cmp r2, #4 + blo partial_word_tail + +1: ldr r5, [r1], #4 + sub r2, r2, #4 +#if __ARMEB__ + mov r4, r5, lsr lr + orr r4, r4, r3 + mov r3, r5, lsl r12 +#else + mov r4, r5, lsl lr + orr r4, r4, r3 + mov r3, r5, lsr r12 +#endif + str r4, [r0], #4 + cmp r2, #4 + bhs 1b + +partial_word_tail: + /* we have a partial word in the input buffer */ + movs r5, lr, lsl #(31-3) +#if __ARMEB__ + movmi r3, r3, ror #24 + strbmi r3, [r0], #1 + movcs r3, r3, ror #24 + strbcs r3, [r0], #1 + movcs r3, r3, ror #24 + strbcs r3, [r0], #1 +#else + strbmi r3, [r0], #1 + movmi r3, r3, lsr #8 + strbcs r3, [r0], #1 + movcs r3, r3, lsr #8 + strbcs r3, [r0], #1 +#endif + + /* Refill spilled registers from the stack. Don't update sp. */ + ldmfd sp, {r5-r11} + +copy_last_3_and_return: + movs r2, r2, lsl #31 /* copy remaining 0, 1, 2 or 3 bytes */ + ldrbmi r2, [r1], #1 + ldrbcs r3, [r1], #1 + ldrbcs r12,[r1] + strbmi r2, [r0], #1 + strbcs r3, [r0], #1 + strbcs r12,[r0] + + /* we're done! restore sp and spilled registers and return */ + add sp, sp, #28 + ldmfd sp!, {r0, r4, lr} + bx lr + diff --git a/lib/string/bcmp.c b/lib/string/bcmp.c new file mode 100644 index 0000000..d4c093f --- /dev/null +++ b/lib/string/bcmp.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +int bcmp(const void *s1, const void *s2, size_t n) +{ + return memcmp(s1, s2, n); +} diff --git a/lib/string/bcopy.c b/lib/string/bcopy.c new file mode 100644 index 0000000..25e98a2 --- /dev/null +++ b/lib/string/bcopy.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +void bcopy(const void *s1, void *s2, size_t n) +{ + memmove(s2, s1, n); +} diff --git a/lib/string/bzero.c b/lib/string/bzero.c new file mode 100644 index 0000000..08f1398 --- /dev/null +++ b/lib/string/bzero.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +void bzero(void *s, size_t n) +{ + memset(s, 0, n); +} diff --git a/lib/string/explicit_bzero.c b/lib/string/explicit_bzero.c new file mode 100644 index 0000000..c94f25f --- /dev/null +++ b/lib/string/explicit_bzero.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> + +void explicit_bzero(void *d, size_t n) +{ + d = memset(d, 0, n); + __asm__ __volatile__ ("" : : "r"(d) : "memory"); +} diff --git a/lib/string/i386/memcpy.s b/lib/string/i386/memcpy.s new file mode 100644 index 0000000..0608dd8 --- /dev/null +++ b/lib/string/i386/memcpy.s @@ -0,0 +1,32 @@ +.global memcpy +.global __memcpy_fwd +.hidden __memcpy_fwd +.type memcpy,@function +memcpy: +__memcpy_fwd: + push %esi + push %edi + mov 12(%esp),%edi + mov 16(%esp),%esi + mov 20(%esp),%ecx + mov %edi,%eax + cmp $4,%ecx + jc 1f + test $3,%edi + jz 1f +2: movsb + dec %ecx + test $3,%edi + jnz 2b +1: mov %ecx,%edx + shr $2,%ecx + rep + movsl + and $3,%edx + jz 1f +2: movsb + dec %edx + jnz 2b +1: pop %edi + pop %esi + ret diff --git a/lib/string/i386/memmove.s b/lib/string/i386/memmove.s new file mode 100644 index 0000000..2a6a504 --- /dev/null +++ b/lib/string/i386/memmove.s @@ -0,0 +1,22 @@ +.global memmove +.type memmove,@function +memmove: + mov 4(%esp),%eax + sub 8(%esp),%eax + cmp 12(%esp),%eax +.hidden __memcpy_fwd + jae __memcpy_fwd + push %esi + push %edi + mov 12(%esp),%edi + mov 16(%esp),%esi + mov 20(%esp),%ecx + lea -1(%edi,%ecx),%edi + lea -1(%esi,%ecx),%esi + std + rep movsb + cld + lea 1(%edi),%eax + pop %edi + pop %esi + ret diff --git a/lib/string/i386/memset.s b/lib/string/i386/memset.s new file mode 100644 index 0000000..d00422c --- /dev/null +++ b/lib/string/i386/memset.s @@ -0,0 +1,76 @@ +.global memset +.type memset,@function +memset: + mov 12(%esp),%ecx + cmp $62,%ecx + ja 2f + + mov 8(%esp),%dl + mov 4(%esp),%eax + test %ecx,%ecx + jz 1f + + mov %dl,%dh + + mov %dl,(%eax) + mov %dl,-1(%eax,%ecx) + cmp $2,%ecx + jbe 1f + + mov %dx,1(%eax) + mov %dx,(-1-2)(%eax,%ecx) + cmp $6,%ecx + jbe 1f + + shl $16,%edx + mov 8(%esp),%dl + mov 8(%esp),%dh + + mov %edx,(1+2)(%eax) + mov %edx,(-1-2-4)(%eax,%ecx) + cmp $14,%ecx + jbe 1f + + mov %edx,(1+2+4)(%eax) + mov %edx,(1+2+4+4)(%eax) + mov %edx,(-1-2-4-8)(%eax,%ecx) + mov %edx,(-1-2-4-4)(%eax,%ecx) + cmp $30,%ecx + jbe 1f + + mov %edx,(1+2+4+8)(%eax) + mov %edx,(1+2+4+8+4)(%eax) + mov %edx,(1+2+4+8+8)(%eax) + mov %edx,(1+2+4+8+12)(%eax) + mov %edx,(-1-2-4-8-16)(%eax,%ecx) + mov %edx,(-1-2-4-8-12)(%eax,%ecx) + mov %edx,(-1-2-4-8-8)(%eax,%ecx) + mov %edx,(-1-2-4-8-4)(%eax,%ecx) + +1: ret + +2: movzbl 8(%esp),%eax + mov %edi,12(%esp) + imul $0x1010101,%eax + mov 4(%esp),%edi + test $15,%edi + mov %eax,-4(%edi,%ecx) + jnz 2f + +1: shr $2, %ecx + rep + stosl + mov 4(%esp),%eax + mov 12(%esp),%edi + ret + +2: xor %edx,%edx + sub %edi,%edx + and $15,%edx + mov %eax,(%edi) + mov %eax,4(%edi) + mov %eax,8(%edi) + mov %eax,12(%edi) + sub %edx,%ecx + add %edx,%edi + jmp 1b diff --git a/lib/string/index.c b/lib/string/index.c new file mode 100644 index 0000000..8f6894c --- /dev/null +++ b/lib/string/index.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +char *index(const char *s, int c) +{ + return strchr(s, c); +} diff --git a/lib/string/memccpy.c b/lib/string/memccpy.c new file mode 100644 index 0000000..99f146f --- /dev/null +++ b/lib/string/memccpy.c @@ -0,0 +1,37 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +void *memccpy(void *restrict dest, const void *restrict src, int c, size_t n) +{ + unsigned char *d = dest; + const unsigned char *s = src; + + c = (unsigned char)c; +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + word *wd; + const word *ws; + if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) { + for (; ((uintptr_t)s & ALIGN) && n && (*d=*s)!=c; n--, s++, d++); + if ((uintptr_t)s & ALIGN) goto tail; + size_t k = ONES * c; + wd=(void *)d; ws=(const void *)s; + for (; n>=sizeof(size_t) && !HASZERO(*ws^k); + n-=sizeof(size_t), ws++, wd++) *wd = *ws; + d=(void *)wd; s=(const void *)ws; + } +#endif + for (; n && (*d=*s)!=c; n--, s++, d++); +tail: + if (n) return d+1; + return 0; +} diff --git a/lib/string/memchr.c b/lib/string/memchr.c new file mode 100644 index 0000000..d0f670f --- /dev/null +++ b/lib/string/memchr.c @@ -0,0 +1,30 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define SS (sizeof(size_t)) +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +void *memchr(const void *src, int c, size_t n) +{ + const unsigned char *s = src; + c = (unsigned char)c; +#ifdef __GNUC__ + for (; ((uintptr_t)s & ALIGN) && n && *s != c; s++, n--); + if (n && *s != c) { + typedef size_t __attribute__((__may_alias__)) word; + const word *w; + size_t k = ONES * c; + for (w = (const void *)s; n>=SS && !HASZERO(*w^k); w++, n-=SS); + s = (const void *)w; + } +#endif + for (; n && *s != c; s++, n--); + return n ? (void *)s : 0; +} diff --git a/lib/string/memcmp.c b/lib/string/memcmp.c new file mode 100644 index 0000000..15606f4 --- /dev/null +++ b/lib/string/memcmp.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +int memcmp(const void *vl, const void *vr, size_t n) +{ + const unsigned char *l=vl, *r=vr; + for (; n && *l == *r; n--, l++, r++); + return n ? *l-*r : 0; +} diff --git a/lib/string/memcpy.c b/lib/string/memcpy.c new file mode 100644 index 0000000..de26a00 --- /dev/null +++ b/lib/string/memcpy.c @@ -0,0 +1,127 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <endian.h> + +void *memcpy(void *restrict dest, const void *restrict src, size_t n) +{ + unsigned char *d = dest; + const unsigned char *s = src; + +#ifdef __GNUC__ + +#if __BYTE_ORDER == __LITTLE_ENDIAN +#define LS >> +#define RS << +#else +#define LS << +#define RS >> +#endif + + typedef uint32_t __attribute__((__may_alias__)) u32; + uint32_t w, x; + + for (; (uintptr_t)s % 4 && n; n--) *d++ = *s++; + + if ((uintptr_t)d % 4 == 0) { + for (; n>=16; s+=16, d+=16, n-=16) { + *(u32 *)(d+0) = *(u32 *)(s+0); + *(u32 *)(d+4) = *(u32 *)(s+4); + *(u32 *)(d+8) = *(u32 *)(s+8); + *(u32 *)(d+12) = *(u32 *)(s+12); + } + if (n&8) { + *(u32 *)(d+0) = *(u32 *)(s+0); + *(u32 *)(d+4) = *(u32 *)(s+4); + d += 8; s += 8; + } + if (n&4) { + *(u32 *)(d+0) = *(u32 *)(s+0); + d += 4; s += 4; + } + if (n&2) { + *d++ = *s++; *d++ = *s++; + } + if (n&1) { + *d = *s; + } + return dest; + } + + if (n >= 32) switch ((uintptr_t)d % 4) { + case 1: + w = *(u32 *)s; + *d++ = *s++; + *d++ = *s++; + *d++ = *s++; + n -= 3; + for (; n>=17; s+=16, d+=16, n-=16) { + x = *(u32 *)(s+1); + *(u32 *)(d+0) = (w LS 24) | (x RS 8); + w = *(u32 *)(s+5); + *(u32 *)(d+4) = (x LS 24) | (w RS 8); + x = *(u32 *)(s+9); + *(u32 *)(d+8) = (w LS 24) | (x RS 8); + w = *(u32 *)(s+13); + *(u32 *)(d+12) = (x LS 24) | (w RS 8); + } + break; + case 2: + w = *(u32 *)s; + *d++ = *s++; + *d++ = *s++; + n -= 2; + for (; n>=18; s+=16, d+=16, n-=16) { + x = *(u32 *)(s+2); + *(u32 *)(d+0) = (w LS 16) | (x RS 16); + w = *(u32 *)(s+6); + *(u32 *)(d+4) = (x LS 16) | (w RS 16); + x = *(u32 *)(s+10); + *(u32 *)(d+8) = (w LS 16) | (x RS 16); + w = *(u32 *)(s+14); + *(u32 *)(d+12) = (x LS 16) | (w RS 16); + } + break; + case 3: + w = *(u32 *)s; + *d++ = *s++; + n -= 1; + for (; n>=19; s+=16, d+=16, n-=16) { + x = *(u32 *)(s+3); + *(u32 *)(d+0) = (w LS 8) | (x RS 24); + w = *(u32 *)(s+7); + *(u32 *)(d+4) = (x LS 8) | (w RS 24); + x = *(u32 *)(s+11); + *(u32 *)(d+8) = (w LS 8) | (x RS 24); + w = *(u32 *)(s+15); + *(u32 *)(d+12) = (x LS 8) | (w RS 24); + } + break; + } + if (n&16) { + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + } + if (n&8) { + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + } + if (n&4) { + *d++ = *s++; *d++ = *s++; *d++ = *s++; *d++ = *s++; + } + if (n&2) { + *d++ = *s++; *d++ = *s++; + } + if (n&1) { + *d = *s; + } + return dest; +#endif + + for (; n; n--) *d++ = *s++; + return dest; +} diff --git a/lib/string/memmem.c b/lib/string/memmem.c new file mode 100644 index 0000000..cfd23bb --- /dev/null +++ b/lib/string/memmem.c @@ -0,0 +1,152 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _GNU_SOURCE +#include <string.h> +#include <stdint.h> + +static char *twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) +{ + uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1]; + for (h+=2, k-=2; k; k--, hw = hw<<8 | *h++) + if (hw == nw) return (char *)h-2; + return hw == nw ? (char *)h-2 : 0; +} + +static char *threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) +{ + uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8; + uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8; + for (h+=3, k-=3; k; k--, hw = (hw|*h++)<<8) + if (hw == nw) return (char *)h-3; + return hw == nw ? (char *)h-3 : 0; +} + +static char *fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) +{ + uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3]; + uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3]; + for (h+=4, k-=4; k; k--, hw = hw<<8 | *h++) + if (hw == nw) return (char *)h-4; + return hw == nw ? (char *)h-4 : 0; +} + +#define MAX(a,b) ((a)>(b)?(a):(b)) +#define MIN(a,b) ((a)<(b)?(a):(b)) + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +static char *twoway_memmem(const unsigned char *h, const unsigned char *z, const unsigned char *n, size_t l) +{ + size_t i, ip, jp, k, p, ms, p0, mem, mem0; + size_t byteset[32 / sizeof(size_t)] = { 0 }; + size_t shift[256]; + + /* Computing length of needle and fill shift table */ + for (i=0; i<l; i++) + BITOP(byteset, n[i], |=), shift[n[i]] = i+1; + + /* Compute maximal suffix */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] > n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + ms = ip; + p0 = p; + + /* And with the opposite comparison */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] < n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + if (ip+1 > ms+1) ms = ip; + else p = p0; + + /* Periodic needle? */ + if (memcmp(n, n+p, ms+1)) { + mem0 = 0; + p = MAX(ms, l-ms-1) + 1; + } else mem0 = l-p; + mem = 0; + + /* Search loop */ + for (;;) { + /* If remainder of haystack is shorter than needle, done */ + if (z-h < l) return 0; + + /* Check last byte first; advance by shift on mismatch */ + if (BITOP(byteset, h[l-1], &)) { + k = l-shift[h[l-1]]; + if (k) { + if (k < mem) k = mem; + h += k; + mem = 0; + continue; + } + } else { + h += l; + mem = 0; + continue; + } + + /* Compare right half */ + for (k=MAX(ms+1,mem); k<l && n[k] == h[k]; k++); + if (k < l) { + h += k-ms; + mem = 0; + continue; + } + /* Compare left half */ + for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--); + if (k <= mem) return (char *)h; + h += p; + mem = mem0; + } +} + +void *memmem(const void *h0, size_t k, const void *n0, size_t l) +{ + const unsigned char *h = h0, *n = n0; + + /* Return immediately on empty needle */ + if (!l) return (void *)h; + + /* Return immediately when needle is longer than haystack */ + if (k<l) return 0; + + /* Use faster algorithms for short needles */ + h = memchr(h0, *n, k); + if (!h || l==1) return (void *)h; + k -= h - (const unsigned char *)h0; + if (k<l) return 0; + if (l==2) return twobyte_memmem(h, k, n); + if (l==3) return threebyte_memmem(h, k, n); + if (l==4) return fourbyte_memmem(h, k, n); + + return twoway_memmem(h, h+k, n, l); +} diff --git a/lib/string/memmove.c b/lib/string/memmove.c new file mode 100644 index 0000000..56e1a81 --- /dev/null +++ b/lib/string/memmove.c @@ -0,0 +1,45 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> + +#ifdef __GNUC__ +typedef __attribute__((__may_alias__)) size_t WT; +#define WS (sizeof(WT)) +#endif + +void *memmove(void *dest, const void *src, size_t n) +{ + char *d = dest; + const char *s = src; + + if (d==s) return d; + if ((uintptr_t)s-(uintptr_t)d-n <= -2*n) return memcpy(d, s, n); + + if (d<s) { +#ifdef __GNUC__ + if ((uintptr_t)s % WS == (uintptr_t)d % WS) { + while ((uintptr_t)d % WS) { + if (!n--) return dest; + *d++ = *s++; + } + for (; n>=WS; n-=WS, d+=WS, s+=WS) *(WT *)d = *(WT *)s; + } +#endif + for (; n; n--) *d++ = *s++; + } else { +#ifdef __GNUC__ + if ((uintptr_t)s % WS == (uintptr_t)d % WS) { + while ((uintptr_t)(d+n) % WS) { + if (!n--) return dest; + d[n] = s[n]; + } + while (n>=WS) n-=WS, *(WT *)(d+n) = *(WT *)(s+n); + } +#endif + while (n) n--, d[n] = s[n]; + } + + return dest; +} diff --git a/lib/string/mempcpy.c b/lib/string/mempcpy.c new file mode 100644 index 0000000..1f33e45 --- /dev/null +++ b/lib/string/mempcpy.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _GNU_SOURCE +#include <string.h> + +void *mempcpy(void *dest, const void *src, size_t n) +{ + return (char *)memcpy(dest, src, n) + n; +} diff --git a/lib/string/memrchr.c b/lib/string/memrchr.c new file mode 100644 index 0000000..8d5c742 --- /dev/null +++ b/lib/string/memrchr.c @@ -0,0 +1,14 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +void *__memrchr(const void *m, int c, size_t n) +{ + const unsigned char *s = m; + c = (unsigned char)c; + while (n--) if (s[n]==c) return (void *)(s+n); + return 0; +} + +weak_alias(__memrchr, memrchr); diff --git a/lib/string/memset.c b/lib/string/memset.c new file mode 100644 index 0000000..e780c71 --- /dev/null +++ b/lib/string/memset.c @@ -0,0 +1,93 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> + +void *memset(void *dest, int c, size_t n) +{ + unsigned char *s = dest; + size_t k; + + /* Fill head and tail with minimal branching. Each + * conditional ensures that all the subsequently used + * offsets are well-defined and in the dest region. */ + + if (!n) return dest; + s[0] = c; + s[n-1] = c; + if (n <= 2) return dest; + s[1] = c; + s[2] = c; + s[n-2] = c; + s[n-3] = c; + if (n <= 6) return dest; + s[3] = c; + s[n-4] = c; + if (n <= 8) return dest; + + /* Advance pointer to align it at a 4-byte boundary, + * and truncate n to a multiple of 4. The previous code + * already took care of any head/tail that get cut off + * by the alignment. */ + + k = -(uintptr_t)s & 3; + s += k; + n -= k; + n &= -4; + +#ifdef __GNUC__ + typedef uint32_t __attribute__((__may_alias__)) u32; + typedef uint64_t __attribute__((__may_alias__)) u64; + + u32 c32 = ((u32)-1)/255 * (unsigned char)c; + + /* In preparation to copy 32 bytes at a time, aligned on + * an 8-byte bounary, fill head/tail up to 28 bytes each. + * As in the initial byte-based head/tail fill, each + * conditional below ensures that the subsequent offsets + * are valid (e.g. !(n<=24) implies n>=28). */ + + *(u32 *)(s+0) = c32; + *(u32 *)(s+n-4) = c32; + if (n <= 8) return dest; + *(u32 *)(s+4) = c32; + *(u32 *)(s+8) = c32; + *(u32 *)(s+n-12) = c32; + *(u32 *)(s+n-8) = c32; + if (n <= 24) return dest; + *(u32 *)(s+12) = c32; + *(u32 *)(s+16) = c32; + *(u32 *)(s+20) = c32; + *(u32 *)(s+24) = c32; + *(u32 *)(s+n-28) = c32; + *(u32 *)(s+n-24) = c32; + *(u32 *)(s+n-20) = c32; + *(u32 *)(s+n-16) = c32; + + /* Align to a multiple of 8 so we can fill 64 bits at a time, + * and avoid writing the same bytes twice as much as is + * practical without introducing additional branching. */ + + k = 24 + ((uintptr_t)s & 4); + s += k; + n -= k; + + /* If this loop is reached, 28 tail bytes have already been + * filled, so any remainder when n drops below 32 can be + * safely ignored. */ + + u64 c64 = c32 | ((u64)c32 << 32); + for (; n >= 32; n-=32, s+=32) { + *(u64 *)(s+0) = c64; + *(u64 *)(s+8) = c64; + *(u64 *)(s+16) = c64; + *(u64 *)(s+24) = c64; + } +#else + /* Pure C fallback with no aliasing violations. */ + for (; n; n--, s++) *s = c; +#endif + + return dest; +} diff --git a/lib/string/rindex.c b/lib/string/rindex.c new file mode 100644 index 0000000..897e19e --- /dev/null +++ b/lib/string/rindex.c @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <strings.h> + +char *rindex(const char *s, int c) +{ + return strrchr(s, c); +} diff --git a/lib/string/stpcpy.c b/lib/string/stpcpy.c new file mode 100644 index 0000000..0c1f1b4 --- /dev/null +++ b/lib/string/stpcpy.c @@ -0,0 +1,32 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +char *__stpcpy(char *restrict d, const char *restrict s) +{ +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + word *wd; + const word *ws; + if ((uintptr_t)s % ALIGN == (uintptr_t)d % ALIGN) { + for (; (uintptr_t)s % ALIGN; s++, d++) + if (!(*d=*s)) return d; + wd=(void *)d; ws=(const void *)s; + for (; !HASZERO(*ws); *wd++ = *ws++); + d=(void *)wd; s=(const void *)ws; + } +#endif + for (; (*d=*s); s++, d++); + + return d; +} + +weak_alias(__stpcpy, stpcpy); diff --git a/lib/string/stpncpy.c b/lib/string/stpncpy.c new file mode 100644 index 0000000..ca2ef78 --- /dev/null +++ b/lib/string/stpncpy.c @@ -0,0 +1,35 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +char *__stpncpy(char *restrict d, const char *restrict s, size_t n) +{ +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + word *wd; + const word *ws; + if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) { + for (; ((uintptr_t)s & ALIGN) && n && (*d=*s); n--, s++, d++); + if (!n || !*s) goto tail; + wd=(void *)d; ws=(const void *)s; + for (; n>=sizeof(size_t) && !HASZERO(*ws); + n-=sizeof(size_t), ws++, wd++) *wd = *ws; + d=(void *)wd; s=(const void *)ws; + } +#endif + for (; n && (*d=*s); n--, s++, d++); +tail: + memset(d, 0, n); + return d; +} + +weak_alias(__stpncpy, stpncpy); + diff --git a/lib/string/strcat.c b/lib/string/strcat.c new file mode 100644 index 0000000..723c2ff --- /dev/null +++ b/lib/string/strcat.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strcat(char *restrict dest, const char *restrict src) +{ + strcpy(dest + strlen(dest), src); + return dest; +} diff --git a/lib/string/strchr.c b/lib/string/strchr.c new file mode 100644 index 0000000..ddeca01 --- /dev/null +++ b/lib/string/strchr.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strchr(const char *s, int c) +{ + char *r = __strchrnul(s, c); + return *(unsigned char *)r == (unsigned char)c ? r : 0; +} diff --git a/lib/string/strchrnul.c b/lib/string/strchrnul.c new file mode 100644 index 0000000..6fc86d1 --- /dev/null +++ b/lib/string/strchrnul.c @@ -0,0 +1,31 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +char *__strchrnul(const char *s, int c) +{ + c = (unsigned char)c; + if (!c) return (char *)s + strlen(s); + +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + const word *w; + for (; (uintptr_t)s % ALIGN; s++) + if (!*s || *(unsigned char *)s == c) return (char *)s; + size_t k = ONES * c; + for (w = (void *)s; !HASZERO(*w) && !HASZERO(*w^k); w++); + s = (void *)w; +#endif + for (; *s && *(unsigned char *)s != c; s++); + return (char *)s; +} + +weak_alias(__strchrnul, strchrnul); diff --git a/lib/string/strcmp.c b/lib/string/strcmp.c new file mode 100644 index 0000000..afcb1b7 --- /dev/null +++ b/lib/string/strcmp.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +int strcmp(const char *l, const char *r) +{ + for (; *l==*r && *l; l++, r++); + return *(unsigned char *)l - *(unsigned char *)r; +} diff --git a/lib/string/strcpy.c b/lib/string/strcpy.c new file mode 100644 index 0000000..a761577 --- /dev/null +++ b/lib/string/strcpy.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strcpy(char *restrict dest, const char *restrict src) +{ + __stpcpy(dest, src); + return dest; +} diff --git a/lib/string/strcspn.c b/lib/string/strcspn.c new file mode 100644 index 0000000..ba55fe6 --- /dev/null +++ b/lib/string/strcspn.c @@ -0,0 +1,20 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +size_t strcspn(const char *s, const char *c) +{ + const char *a = s; + size_t byteset[32/sizeof(size_t)]; + + if (!c[0] || !c[1]) return __strchrnul(s, *c)-a; + + memset(byteset, 0, sizeof byteset); + for (; *c && BITOP(byteset, *(unsigned char *)c, |=); c++); + for (; *s && !BITOP(byteset, *(unsigned char *)s, &); s++); + return s-a; +} diff --git a/lib/string/strlcat.c b/lib/string/strlcat.c new file mode 100644 index 0000000..a61821d --- /dev/null +++ b/lib/string/strlcat.c @@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> + +size_t strlcat(char *d, const char *s, size_t n) +{ + size_t l = strnlen(d, n); + if (l == n) return l + strlen(s); + return l + strlcpy(d+l, s, n-l); +} diff --git a/lib/string/strlcpy.c b/lib/string/strlcpy.c new file mode 100644 index 0000000..c2a5142 --- /dev/null +++ b/lib/string/strlcpy.c @@ -0,0 +1,37 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _BSD_SOURCE +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +size_t strlcpy(char *d, const char *s, size_t n) +{ + char *d0 = d; + size_t *wd; + + if (!n--) goto finish; +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + const word *ws; + if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) { + for (; ((uintptr_t)s & ALIGN) && n && (*d=*s); n--, s++, d++); + if (n && *s) { + wd=(void *)d; ws=(const void *)s; + for (; n>=sizeof(size_t) && !HASZERO(*ws); + n-=sizeof(size_t), ws++, wd++) *wd = *ws; + d=(void *)wd; s=(const void *)ws; + } + } +#endif + for (; n && (*d=*s); n--, s++, d++); + *d = 0; +finish: + return d-d0 + strlen(s); +} diff --git a/lib/string/strlen.c b/lib/string/strlen.c new file mode 100644 index 0000000..76e14f2 --- /dev/null +++ b/lib/string/strlen.c @@ -0,0 +1,25 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> +#include <limits.h> + +#define ALIGN (sizeof(size_t)) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +size_t strlen(const char *s) +{ + const char *a = s; +#ifdef __GNUC__ + typedef size_t __attribute__((__may_alias__)) word; + const word *w; + for (; (uintptr_t)s % ALIGN; s++) if (!*s) return s-a; + for (w = (const void *)s; !HASZERO(*w); w++); + s = (const void *)w; +#endif + for (; *s; s++); + return s-a; +} diff --git a/lib/string/strncat.c b/lib/string/strncat.c new file mode 100644 index 0000000..a144e37 --- /dev/null +++ b/lib/string/strncat.c @@ -0,0 +1,13 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strncat(char *restrict d, const char *restrict s, size_t n) +{ + char *a = d; + d += strlen(d); + while (n && *s) n--, *d++ = *s++; + *d++ = 0; + return a; +} diff --git a/lib/string/strncmp.c b/lib/string/strncmp.c new file mode 100644 index 0000000..b98473b --- /dev/null +++ b/lib/string/strncmp.c @@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +int strncmp(const char *_l, const char *_r, size_t n) +{ + const unsigned char *l=(void *)_l, *r=(void *)_r; + if (!n--) return 0; + for (; *l && *r && n && *l == *r ; l++, r++, n--); + return *l - *r; +} diff --git a/lib/string/strncpy.c b/lib/string/strncpy.c new file mode 100644 index 0000000..a828465 --- /dev/null +++ b/lib/string/strncpy.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strncpy(char *restrict d, const char *restrict s, size_t n) +{ + __stpncpy(d, s, n); + return d; +} diff --git a/lib/string/strnlen.c b/lib/string/strnlen.c new file mode 100644 index 0000000..8931c52 --- /dev/null +++ b/lib/string/strnlen.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +size_t strnlen(const char *s, size_t n) +{ + const char *p = memchr(s, 0, n); + return p ? p-s : n; +} diff --git a/lib/string/strpbrk.c b/lib/string/strpbrk.c new file mode 100644 index 0000000..82fbc92 --- /dev/null +++ b/lib/string/strpbrk.c @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strpbrk(const char *s, const char *b) +{ + s += strcspn(s, b); + return *s ? (char *)s : 0; +} diff --git a/lib/string/strrchr.c b/lib/string/strrchr.c new file mode 100644 index 0000000..a45b459 --- /dev/null +++ b/lib/string/strrchr.c @@ -0,0 +1,9 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strrchr(const char *s, int c) +{ + return __memrchr(s, c, strlen(s) + 1); +} diff --git a/lib/string/strsep.c b/lib/string/strsep.c new file mode 100644 index 0000000..2d513f4 --- /dev/null +++ b/lib/string/strsep.c @@ -0,0 +1,16 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#define _GNU_SOURCE +#include <string.h> + +char *strsep(char **str, const char *sep) +{ + char *s = *str, *end; + if (!s) return NULL; + end = s + strcspn(s, sep); + if (*end) *end++ = 0; + else end = 0; + *str = end; + return s; +} diff --git a/lib/string/strspn.c b/lib/string/strspn.c new file mode 100644 index 0000000..f27710d --- /dev/null +++ b/lib/string/strspn.c @@ -0,0 +1,23 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +size_t strspn(const char *s, const char *c) +{ + const char *a = s; + size_t byteset[32/sizeof(size_t)] = { 0 }; + + if (!c[0]) return 0; + if (!c[1]) { + for (; *s == *c; s++); + return s-a; + } + + for (; *c && BITOP(byteset, *(unsigned char *)c, |=); c++); + for (; *s && BITOP(byteset, *(unsigned char *)s, &); s++); + return s-a; +} diff --git a/lib/string/strstr.c b/lib/string/strstr.c new file mode 100644 index 0000000..07e2982 --- /dev/null +++ b/lib/string/strstr.c @@ -0,0 +1,157 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> +#include <stdint.h> + +static char *twobyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1]; + for (h++; *h && hw != nw; hw = hw<<8 | *++h); + return *h ? (char *)h-1 : 0; +} + +static char *threebyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8; + uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8; + for (h+=2; *h && hw != nw; hw = (hw|*++h)<<8); + return *h ? (char *)h-2 : 0; +} + +static char *fourbyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3]; + uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3]; + for (h+=3; *h && hw != nw; hw = hw<<8 | *++h); + return *h ? (char *)h-3 : 0; +} + +#define MAX(a,b) ((a)>(b)?(a):(b)) +#define MIN(a,b) ((a)<(b)?(a):(b)) + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +static char *twoway_strstr(const unsigned char *h, const unsigned char *n) +{ + const unsigned char *z; + size_t l, ip, jp, k, p, ms, p0, mem, mem0; + size_t byteset[32 / sizeof(size_t)] = { 0 }; + size_t shift[256]; + + /* Computing length of needle and fill shift table */ + for (l=0; n[l] && h[l]; l++) + BITOP(byteset, n[l], |=), shift[n[l]] = l+1; + if (n[l]) return 0; /* hit the end of h */ + + /* Compute maximal suffix */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] > n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + ms = ip; + p0 = p; + + /* And with the opposite comparison */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] < n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + if (ip+1 > ms+1) ms = ip; + else p = p0; + + /* Periodic needle? */ + if (memcmp(n, n+p, ms+1)) { + mem0 = 0; + p = MAX(ms, l-ms-1) + 1; + } else mem0 = l-p; + mem = 0; + + /* Initialize incremental end-of-haystack pointer */ + z = h; + + /* Search loop */ + for (;;) { + /* Update incremental end-of-haystack pointer */ + if (z-h < l) { + /* Fast estimate for MAX(l,63) */ + size_t grow = l | 63; + const unsigned char *z2 = memchr(z, 0, grow); + if (z2) { + z = z2; + if (z-h < l) return 0; + } else z += grow; + } + + /* Check last byte first; advance by shift on mismatch */ + if (BITOP(byteset, h[l-1], &)) { + k = l-shift[h[l-1]]; + if (k) { + if (k < mem) k = mem; + h += k; + mem = 0; + continue; + } + } else { + h += l; + mem = 0; + continue; + } + + /* Compare right half */ + for (k=MAX(ms+1,mem); n[k] && n[k] == h[k]; k++); + if (n[k]) { + h += k-ms; + mem = 0; + continue; + } + /* Compare left half */ + for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--); + if (k <= mem) return (char *)h; + h += p; + mem = mem0; + } +} + +char *strstr(const char *h, const char *n) +{ + /* Return immediately on empty needle */ + if (!n[0]) return (char *)h; + + /* Use faster algorithms for short needles */ + h = strchr(h, *n); + if (!h || !n[1]) return (char *)h; + if (!h[1]) return 0; + if (!n[2]) return twobyte_strstr((void *)h, (void *)n); + if (!h[2]) return 0; + if (!n[3]) return threebyte_strstr((void *)h, (void *)n); + if (!h[3]) return 0; + if (!n[4]) return fourbyte_strstr((void *)h, (void *)n); + + return twoway_strstr((void *)h, (void *)n); +} diff --git a/lib/string/strtok.c b/lib/string/strtok.c new file mode 100644 index 0000000..86d9c97 --- /dev/null +++ b/lib/string/strtok.c @@ -0,0 +1,16 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strtok(char *restrict s, const char *restrict sep) +{ + static char *p; + if (!s && !(s = p)) return NULL; + s += strspn(s, sep); + if (!*s) return p = 0; + p = s + strcspn(s, sep); + if (*p) *p++ = 0; + else p = 0; + return s; +} diff --git a/lib/string/strtok_r.c b/lib/string/strtok_r.c new file mode 100644 index 0000000..a702703 --- /dev/null +++ b/lib/string/strtok_r.c @@ -0,0 +1,15 @@ +/* SPDX-License-Identifier: MIT */ +/* Derived from musl libc (Copyright © 2005-2020 Rich Felker, et al.) */ + +#include <string.h> + +char *strtok_r(char *restrict s, const char *restrict sep, char **restrict p) +{ + if (!s && !(s = *p)) return NULL; + s += strspn(s, sep); + if (!*s) return *p = 0; + *p = s + strcspn(s, sep); + if (**p) *(*p)++ = 0; + else *p = 0; + return s; +} diff --git a/lib/string/x86_64/memcpy.s b/lib/string/x86_64/memcpy.s new file mode 100644 index 0000000..3d960ef --- /dev/null +++ b/lib/string/x86_64/memcpy.s @@ -0,0 +1,25 @@ +.global memcpy +.global __memcpy_fwd +.hidden __memcpy_fwd +.type memcpy,@function +memcpy: +__memcpy_fwd: + mov %rdi,%rax + cmp $8,%rdx + jc 1f + test $7,%edi + jz 1f +2: movsb + dec %rdx + test $7,%edi + jnz 2b +1: mov %rdx,%rcx + shr $3,%rcx + rep + movsq + and $7,%edx + jz 1f +2: movsb + dec %edx + jnz 2b +1: ret diff --git a/lib/string/x86_64/memmove.s b/lib/string/x86_64/memmove.s new file mode 100644 index 0000000..172c025 --- /dev/null +++ b/lib/string/x86_64/memmove.s @@ -0,0 +1,16 @@ +.global memmove +.type memmove,@function +memmove: + mov %rdi,%rax + sub %rsi,%rax + cmp %rdx,%rax +.hidden __memcpy_fwd + jae __memcpy_fwd + mov %rdx,%rcx + lea -1(%rdi,%rdx),%rdi + lea -1(%rsi,%rdx),%rsi + std + rep movsb + cld + lea 1(%rdi),%rax + ret diff --git a/lib/string/x86_64/memset.s b/lib/string/x86_64/memset.s new file mode 100644 index 0000000..2d3f5e5 --- /dev/null +++ b/lib/string/x86_64/memset.s @@ -0,0 +1,72 @@ +.global memset +.type memset,@function +memset: + movzbq %sil,%rax + mov $0x101010101010101,%r8 + imul %r8,%rax + + cmp $126,%rdx + ja 2f + + test %edx,%edx + jz 1f + + mov %sil,(%rdi) + mov %sil,-1(%rdi,%rdx) + cmp $2,%edx + jbe 1f + + mov %ax,1(%rdi) + mov %ax,(-1-2)(%rdi,%rdx) + cmp $6,%edx + jbe 1f + + mov %eax,(1+2)(%rdi) + mov %eax,(-1-2-4)(%rdi,%rdx) + cmp $14,%edx + jbe 1f + + mov %rax,(1+2+4)(%rdi) + mov %rax,(-1-2-4-8)(%rdi,%rdx) + cmp $30,%edx + jbe 1f + + mov %rax,(1+2+4+8)(%rdi) + mov %rax,(1+2+4+8+8)(%rdi) + mov %rax,(-1-2-4-8-16)(%rdi,%rdx) + mov %rax,(-1-2-4-8-8)(%rdi,%rdx) + cmp $62,%edx + jbe 1f + + mov %rax,(1+2+4+8+16)(%rdi) + mov %rax,(1+2+4+8+16+8)(%rdi) + mov %rax,(1+2+4+8+16+16)(%rdi) + mov %rax,(1+2+4+8+16+24)(%rdi) + mov %rax,(-1-2-4-8-16-32)(%rdi,%rdx) + mov %rax,(-1-2-4-8-16-24)(%rdi,%rdx) + mov %rax,(-1-2-4-8-16-16)(%rdi,%rdx) + mov %rax,(-1-2-4-8-16-8)(%rdi,%rdx) + +1: mov %rdi,%rax + ret + +2: test $15,%edi + mov %rdi,%r8 + mov %rax,-8(%rdi,%rdx) + mov %rdx,%rcx + jnz 2f + +1: shr $3,%rcx + rep + stosq + mov %r8,%rax + ret + +2: xor %edx,%edx + sub %edi,%edx + and $15,%edx + mov %rax,(%rdi) + mov %rax,8(%rdi) + sub %rdx,%rcx + add %rdx,%rdi + jmp 1b |