Skip to content

Instantly share code, notes, and snippets.

View kprotty's full-sized avatar

protty kprotty

View GitHub Profile
const M = 12; // Probability scale for rANS state. Symbol frequencies in this log range. Usually 8-12.
const L = 23; // Renormalization factor to control dumping rANS state to bitstream. From rans_byte.h.
const m_min = 8 - 2 - (std.math.divCeil(u32, M, 4) catch unreachable); // Small-size-opt limit when compressing frequencies.
const m_max = [_]u16{m_min, m_min+16, m_min+16+256, m_min+16+256+4096, 1<<M}; // Size ranges for frequencies after small size limit.
fn compress(dst: anytype, src: []const u8) !void {
// Histogram for the frequency of each byte in input.
var hist = [_]u32{0} ** 256;
for (src) |byte| hist[byte] += 1;
@kprotty
kprotty / lz4_block.zig
Last active January 2, 2024 11:14
Simple LZ4 block enc/dec in 100 LOC
const assert = @import("std").debug.assert;
fn compressBlock(writer: anytype, src: []const u8) !void {
var table = [_]u32{0} ** 4096; // size is pow2. bump to match more. ideal = (0xffff+1) / sizeof(u32)
var anchor: u32 = 0;
if (src.len > 12) { // LZ4 spec restriction: last match must start 12b before end of block.
var pos: u32 = 0;
while (pos + 4 < src.len - 5) { // LZ4 spec restriction: last 5b are always literal.
const blk: u32 = @bitCast(src[pos..][0..4].*);
const std = @import("std");
const assert = std.debug.assert;
const log = std.log.scoped(.lsm_manifest_fuzz);
const vsr = @import("../vsr.zig");
const constants = @import("../constants.zig");
const stdx = @import("../stdx.zig");
const fuzz = @import("../testing/fuzz.zig");
const allocator = fuzz.allocator;
const snapshot_latest = @import("tree.zig").snapshot_latest;
#include <cstdint>
#include <cstddef>
#include <cstring>
#include <cassert>
#include <x86intrin.h>
typedef struct {
__m256i state[2];
__m256i counter;
__m256i output;
type Event:
wait()
set()
type Link:
get(ptr: Ptr):
if LOAD(ptr, Acquire) |value|:
return value
e = Event{}
@kprotty
kprotty / faa_vs_cas.zig
Last active August 21, 2024 17:26
Updated to Zig 0.13
const std = @import("std");
const builtin = @import("builtin");
pub fn main() !void {
try bench(struct {
pub const name = "FAA";
pub fn inc(counter: *std.atomic.Value(usize), current: usize, rng: *u32) usize {
_ = rng;
_ = current;
const std = @import("std");
const Channel = struct {
value: u32 = undefined,
frame: anyframe,
};
fn generate(out_channel: **Channel) void {
var ch = Channel{ .frame = @frame() };
suspend out_channel.* = &ch;
partial ordering: time/events are related to each other as graphs of dependencies
total ordering: time/events are related to each other as a sequence of steps
atomic op: op which is observed to either happen fully or not at all (no in-between)
atomic variable: memory location which atomic ops happen to
data race: non-atomic ops from 2+ threads on same memory location where one op is a write
load: an atomic read to observe a value
store: an atomic write to publish a value
read-modify-write (rmw): a read, updating the value, then a write, all atomically
@kprotty
kprotty / sync.rs
Last active March 20, 2024 16:11
mod futex {
use std::{sync::atomic::AtomicU32, time::Duration};
pub fn wait(_ptr: &AtomicU32, _cmp: u32, _timeout: Option<Duration>) -> bool {
unimplemented!("TODO")
}
pub fn wake(_ptr: *const AtomicU32, _max_wake: u32) {
unimplemented!("TODO")
}
@kprotty
kprotty / sync.go
Last active March 20, 2024 16:11
Crossplatfomr futex and rwlock for Go
package main
import (
"sync/atomic"
"unsafe"
)
type mutex struct {
key uintptr
}