SIMD 프로그래밍

# rust-toolchain.toml (프로젝트 루트)
[toolchain]
channel = "nightly"

// src/lib.rs 또는 main.rs 상단
#![feature(portable_simd)]

use std::simd::prelude::*;
// 이 한 줄로 Simd, Mask, 모든 연산자, 타입 별칭 전부 들어옴

# Cargo.toml
[profile.release]
opt-level = 3

# ARM64에서 NEON을 명시적으로 활성화
# (Pi 5는 기본 활성화지만, 크로스 컴파일 시 필요)
[build]
rustflags = ["-C", "target-cpu=native"]

use std::simd::prelude::*;

// 타입 별칭 (자주 쓰는 것들)
type u8x16  = Simd<u8,  16>; // 128비트 — 해시맵 제어 바이트
type u8x32  = Simd<u8,  32>; // 256비트 — AVX2 활용 가능할 때
type f32x4  = Simd<f32,  4>; // 128비트 — 벡터/색상 연산
type f32x8  = Simd<f32,  8>; // 256비트 — 대규모 수치 연산
type i32x4  = Simd<i32,  4>; // 128비트
type u64x4  = Simd<u64,  4>; // 256비트

let a = u8x16::splat(5);
let b = u8x16::from_array([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,5]);

let mask: Mask<i8, 16> = a.simd_eq(b);
// mask[0]  = false (5 ≠ 1)
// mask[4]  = true  (5 == 5)
// mask[15] = true  (5 == 5)

// Mask → u16 비트마스크 (x86: movemask, ARM: shrn+mov 등으로 컴파일)
let bits: u16 = mask.to_bitmask();
// bit 4와 bit 15가 1

// splat: 하나의 값으로 전체 레인 채우기
let zeros = u8x16::splat(0);
let fives = f32x4::splat(5.0);

// from_array: 배열에서
let v = u8x16::from_array([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]);

// from_slice: 슬라이스에서 (N개 읽음)
let data = vec![1u8; 64];
let v = u8x16::from_slice(&data[0..16]);

// load_or_default: 슬라이스가 N보다 짧으면 0으로 패딩
// (경계에서 유용)
let short = &[1u8, 2, 3];
let v = Simd::load_or_default(short);  // [1,2,3,0,0,...,0]

let v = u8x16::from_array([42u8; 16]);

// to_array: 배열로 변환
let arr: [u8; 16] = v.to_array();

// copy_to_slice: 슬라이스에 쓰기
let mut buf = vec![0u8; 64];
v.copy_to_slice(&mut buf[0..16]);

use std::simd::prelude::*;

let a = f32x4::from_array([1.0, 2.0, 3.0, 4.0]);
let b = f32x4::from_array([10.0, 20.0, 30.0, 40.0]);

let add = a + b;      // [11.0, 22.0, 33.0, 44.0]
let sub = b - a;      // [9.0, 18.0, 27.0, 36.0]
let mul = a * b;      // [10.0, 40.0, 90.0, 160.0]
let div = b / a;      // [10.0, 10.0, 10.0, 10.0]

// 스칼라와의 연산 — Simd * Simd만 가능, 스칼라는 먼저 splat
let doubled = a * f32x4::splat(2.0);  // [2.0, 4.0, 6.0, 8.0]

use std::simd::prelude::*;
use std::simd::num::SimdUint;

let a = u8x16::splat(200);
let b = u8x16::splat(100);

let wrapped   = a + b;              // [44, 44, ...] — 오버플로
let saturated = a.saturating_add(b); // [255, 255, ...] — 포화

// 이미지 밝기 조정
fn brighten(pixels: &mut [u8], amount: u8) {
    let add = u8x16::splat(amount);
    for chunk in pixels.chunks_exact_mut(16) {
        let v = u8x16::from_slice(chunk);
        v.saturating_add(add).copy_to_slice(chunk);
    }
    // 나머지 처리 (16 미만)
    let rest = pixels.chunks_exact_mut(16).into_remainder();
    for p in rest { *p = p.saturating_add(amount); }
}

use std::simd::prelude::*;

let a = u8x16::from_array([0b1010; 16]);
let b = u8x16::from_array([0b1100; 16]);

let and  = a & b;  // [0b1000; 16]
let or   = a | b;  // [0b1110; 16]
let xor  = a ^ b;  // [0b0110; 16]
let not  = !a;     // [0b11110101; 16]

// 시프트 — Simd << Simd 또는 Simd << 상수
let shifted = a >> u8x16::splat(1);  // [0b0101; 16]

// 상수 시프트 (더 빠름, 컴파일타임 결정)
use std::simd::num::SimdUint;
// 현재 portable SIMD에서 상수 시프트는 보통 splat으로

use std::simd::prelude::*;

let a = i32x4::from_array([1, 5, 3, 8]);
let b = i32x4::from_array([2, 5, 1, 7]);

let eq = a.simd_eq(b);  // [F, T, F, F]
let ne = a.simd_ne(b);  // [T, F, T, T]
let lt = a.simd_lt(b);  // [T, F, F, F]
let le = a.simd_le(b);  // [T, T, F, F]
let gt = a.simd_gt(b);  // [F, F, T, T]
let ge = a.simd_ge(b);  // [F, T, T, T]

use std::simd::prelude::*;

let m1: Mask<i32, 4> = Mask::from_array([true, false, true, false]);
let m2: Mask<i32, 4> = Mask::from_array([true, true, false, false]);

let and = m1 & m2;  // [T, F, F, F]
let or  = m1 | m2;  // [T, T, T, F]
let xor = m1 ^ m2;  // [F, T, T, F]
let not = !m1;      // [F, T, F, T]

// 마스크 쿼리
let any = m1.any();  // true (하나라도 true)
let all = m1.all();  // false (전부 true가 아님)

// 비트마스크 변환 (해시맵에서 핵심!)
let bits: u8 = m1.to_bitmask() as u8;  // 0b0101
let back = Mask::<i32, 4>::from_bitmask(bits as u8);

use std::simd::prelude::*;

let a = f32x4::from_array([1.0, 2.0, 3.0, 4.0]);
let b = f32x4::from_array([10.0, 20.0, 30.0, 40.0]);
let mask = Mask::from_array([true, false, true, false]);

// mask가 true인 레인은 a, false인 레인은 b
let result = mask.select(a, b);  // [1.0, 20.0, 3.0, 40.0]

// 응용: SIMD abs (부호 없는 절댓값)
fn simd_abs(v: f32x4) -> f32x4 {
    let neg = -v;
    let mask = v.simd_ge(f32x4::splat(0.0));
    mask.select(v, neg)
}

// 응용: SIMD clamp
fn simd_clamp(v: f32x4, lo: f32, hi: f32) -> f32x4 {
    let lo_v = f32x4::splat(lo);
    let hi_v = f32x4::splat(hi);
    v.simd_clamp(lo_v, hi_v)
}

use std::simd::prelude::*;
use std::simd::num::{SimdFloat, SimdUint};

let v = f32x4::from_array([1.0, 2.0, 3.0, 4.0]);

let sum  = v.reduce_sum();   // 10.0
let prod = v.reduce_product(); // 24.0
let max  = v.reduce_max();   // 4.0
let min  = v.reduce_min();   // 1.0

let u = u8x16::from_array([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]);
let s: u8 = u.reduce_sum(); // 136 (mod 256 = 136, 실제 합은 136)

// Mask 리덕션
let mask = u.simd_gt(u8x16::splat(8));
let count = mask.to_bitmask().count_ones(); // 8보다 큰 레인 개수 = 8

fn sum_f32(data: &[f32]) -> f32 {
    let mut acc = f32x8::splat(0.0);

    let (chunks, rest) = data.as_chunks::<8>();
    for chunk in chunks {
        acc += f32x8::from_array(*chunk);
    }

    // 나머지 스칼라 처리
    acc.reduce_sum() + rest.iter().sum::<f32>()
}

// 사용
let data: Vec<f32> = (0..1000).map(|x| x as f32).collect();
let total = sum_f32(&data);  // 499500.0

use std::simd::prelude::*;

let a = u8x4::from_array([10, 20, 30, 40]);

// simd_swizzle!: 컴파일타임 상수 인덱스로 레인 재배치
// 인덱스가 N 이상이면 두 번째 벡터에서 가져옴
let rev = simd_swizzle!(a, [3, 2, 1, 0]);  // [40, 30, 20, 10]
let dup = simd_swizzle!(a, [0, 0, 1, 1]);  // [10, 10, 20, 20]

// 두 벡터 인터리브
let b = u8x4::from_array([1, 2, 3, 4]);
// a에서 [0, 1], b에서 [0+4, 1+4]
let interleaved = simd_swizzle!(a, b, [0, 4, 1, 5]); // [10, 1, 20, 2]

// 응용: AoS → SoA 변환 (Array of Structs → Struct of Arrays)
// 입력: [r0,g0,b0,a0, r1,g1,b1,a1, r2,g2,b2,a2, r3,g3,b3,a3]
// 출력: [r0,r1,r2,r3], [g0,g1,g2,g3], ...
fn deinterleave_rgba(pixels: [u8; 16]) -> ([u8; 4], [u8; 4], [u8; 4], [u8; 4]) {
    let v = u8x16::from_array(pixels);
    let r = simd_swizzle!(v, [0,  4,  8,  12]);
    let g = simd_swizzle!(v, [1,  5,  9,  13]);
    let b = simd_swizzle!(v, [2,  6,  10, 14]);
    let a = simd_swizzle!(v, [3,  7,  11, 15]);
    // Simd<u8,4> → [u8; 4]
    (r.to_array(), g.to_array(), b.to_array(), a.to_array())
}

#![feature(portable_simd)]
use std::simd::prelude::*;

/// 바이트 슬라이스에서 target 바이트의 첫 번째 위치 찾기
fn find_byte(haystack: &[u8], target: u8) -> Option<usize> {
    let needle = u8x16::splat(target);
    let mut offset = 0;

    // 16바이트씩 처리
    while offset + 16 <= haystack.len() {
        let chunk = u8x16::from_slice(&haystack[offset..]);
        let mask  = chunk.simd_eq(needle).to_bitmask();
        if mask != 0 {
            return Some(offset + mask.trailing_zeros() as usize);
        }
        offset += 16;
    }

    // 나머지
    haystack[offset..].iter().position(|&b| b == target).map(|i| offset + i)
}

fn main() {
    let data = b"hello world! this is a test string for SIMD";
    println!("{:?}", find_byte(data, b'S'));  // Some(38)
    println!("{:?}", find_byte(data, b'z'));  // None
}

#![feature(portable_simd, slice_as_chunks)]
use std::simd::prelude::*;

fn dot_product(a: &[f32], b: &[f32]) -> f32 {
    assert_eq!(a.len(), b.len());

    let mut acc = f32x8::splat(0.0);

    let (a_chunks, a_rest) = a.as_chunks::<8>();
    let (b_chunks, b_rest) = b.as_chunks::<8>();

    for (ac, bc) in a_chunks.iter().zip(b_chunks.iter()) {
        let va = f32x8::from_array(*ac);
        let vb = f32x8::from_array(*bc);
        acc += va * vb;  // fused multiply-add (FMA)로 컴파일될 수 있음
    }

    let mut result = acc.reduce_sum();
    for (&x, &y) in a_rest.iter().zip(b_rest.iter()) {
        result += x * y;
    }
    result
}

// 768차원 임베딩 벡터 유사도 (LLM에서 사용)
fn cosine_similarity(a: &[f32], b: &[f32]) -> f32 {
    let dot  = dot_product(a, b);
    let na   = dot_product(a, a).sqrt();
    let nb   = dot_product(b, b).sqrt();
    dot / (na * nb)
}

#![feature(portable_simd)]
use std::simd::prelude::*;

/// 바이트 배열에서 특정 값보다 큰 원소 개수 세기
fn count_greater(data: &[u8], threshold: u8) -> usize {
    let thresh = u8x16::splat(threshold);
    let mut count = 0usize;
    let mut offset = 0;

    while offset + 16 <= data.len() {
        let v = u8x16::from_slice(&data[offset..]);
        let mask = v.simd_gt(thresh).to_bitmask();
        count += mask.count_ones() as usize;
        offset += 16;
    }

    count += data[offset..].iter().filter(|&&x| x > threshold).count();
    count
}

ctrl[i] 값:
  0xFF (11111111) → EMPTY   (비어있음)
  0x80 (10000000) → DELETED (논리 삭제)
  0b0xxxxxxx     → FULL    (하위 7비트 = 해시 h2)

#![feature(portable_simd)]
use std::simd::prelude::*;

const EMPTY:   u8 = 0xFF;
const DELETED: u8 = 0x80;

struct Group(*const u8);

impl Group {
    unsafe fn new(ptr: *const u8) -> Self { Group(ptr) }

    unsafe fn load(&self) -> u8x16 {
        u8x16::from_slice(std::slice::from_raw_parts(self.0, 16))
    }

    /// h2와 일치하는 슬롯 비트마스크
    unsafe fn match_byte(&self, h2: u8) -> u16 {
        let v = self.load();
        v.simd_eq(u8x16::splat(h2)).to_bitmask()
    }

    /// 비어있는 슬롯 비트마스크
    unsafe fn match_empty(&self) -> u16 {
        self.match_byte(EMPTY)
    }

    /// 빈 슬롯 또는 삭제된 슬롯 (삽입 가능한 슬롯)
    unsafe fn match_available(&self) -> u16 {
        let v = self.load();
        // 최상위 비트가 1 == EMPTY(0xFF) 또는 DELETED(0x80)
        // 즉 ctrl & 0x80 != 0
        let masked = v & u8x16::splat(0x80);
        masked.simd_ne(u8x16::splat(0)).to_bitmask()
    }
}

/// 비트마스크에서 set 비트 인덱스를 순회
fn iter_set_bits(mut mask: u16) -> impl Iterator<Item = usize> {
    std::iter::from_fn(move || {
        if mask == 0 { return None; }
        let i = mask.trailing_zeros() as usize;
        mask &= mask - 1;  // 최하위 set bit 제거 (bit trick)
        Some(i)
    })
}

// 사용 예
fn probe_group(ctrl: *const u8, h2: u8) {
    unsafe {
        let g = Group::new(ctrl);

        // h2와 일치하는 슬롯 탐색
        for slot in iter_set_bits(g.match_byte(h2)) {
            println!("후보 슬롯: {slot}");
            // → 실제 키 비교 후 확정
        }

        // 빈 슬롯 찾기 (삽입 위치)
        if let Some(slot) = g.match_empty().checked_sub(1).map(|_|
            g.match_empty().trailing_zeros() as usize
        ) {
            println!("삽입 위치: {slot}");
        }
    }
}

/// h1: 버킷 그룹 선택 (상위 비트)
fn h1(hash: u64, groups: usize) -> usize {
    (hash >> 7) as usize % groups
}

/// h2: 제어 바이트 값 (하위 7비트, MSB는 항상 0 = FULL 표시)
fn h2(hash: u64) -> u8 {
    (hash & 0x7F) as u8
}

// 탐색 흐름:
// 1. hash = Hash::hash(key)
// 2. group = h1(hash, cap/16)
// 3. h2val = h2(hash)
// 4. Group::match_byte(ctrl + group*16, h2val) → mask
// 5. mask의 각 비트 위치에서 실제 키 비교
// 6. 실패 시 Group::match_empty == 0이면 다음 그룹으로

// benches/simd_bench.rs
use criterion::{black_box, criterion_group, criterion_main, Criterion};
#![feature(portable_simd)]
use std::simd::prelude::*;

fn bench_find(c: &mut Criterion) {
    let data: Vec<u8> = (0..10000).map(|i| (i % 256) as u8).collect();

    c.bench_function("find_scalar", |b| b.iter(|| {
        data.iter().position(|&x| x == black_box(200))
    }));

    c.bench_function("find_simd", |b| b.iter(|| {
        find_byte(black_box(&data), black_box(200))
    }));
}

criterion_group!(benches, bench_find);
criterion_main!(benches);

# ARM64에서 생성된 어셈블리 확인
RUSTFLAGS="-C target-cpu=native" cargo rustc --release -- --emit=asm
# target/release/deps/*.s 에서 CMEQ, CMHS 등 NEON 명령어 확인

# 또는 Godbolt에서: https://godbolt.org/
# target: aarch64-unknown-linux-gnu, rustc nightly
# -C opt-level=3 -C target-cpu=neoverse-v2 (Pi 5)