🔹 detach — remove node from LRU list#

fn detach(&mut self, i: usize) {

• Removes entry i from the linked list without deleting it.

        let (prev, next) = {
            let e = &self.entries[i];
            (e.prev, e.next)
        };

• Extract neighbors
• Done in a block to avoid borrow conflicts

        if let Some(p) = prev {
            self.entries[p].next = next;

• If i had a previous node

• Link previous → next

        } else {
            // i was head
            self.head = next;
        }

• If no prev, i was MRU

• Update head

        if let Some(n) = next {
            self.entries[n].prev = prev;

• If i had a next node
• Link next → previous

        } else {
            // i was tail
            self.tail = prev;
        }

• If no next, i was LRU
• Update tail

        self.entries[i].prev = None;
        self.entries[i].next = None;

• Fully detach node
• Prevent dangling links
• 완전 분리 노드
• 매달린 링크 방지

🔹 push_front — move node to MRU#

fn push_front(&mut self, i: usize) {

• Adds entry i to the front (MRU position).

        self.entries[i].prev = None;
        self.entries[i].next = self.head;

• New head has no previous
• Points to old head

        if let Some(old_head) = self.head {
            self.entries[old_head].prev = Some(i);

• Old head now points back to i

        } else {
            // list was empty
            self.tail = Some(i);
        }

• First element
• Head and tail are same

        self.head = Some(i);

• pdate MRU pointer

🔹 access — mark key as recently used#

fn access(&mut self, key: &K) {

• Called on every successful get or insert.

        let i = self.map[key];

• Lookup index
• Safe because caller checked existence

        if Some(i) == self.head {
            return; // already MRU
        }

• No work needed if already MRU

        self.detach(i);
        self.push_front(i);

• Move entry to front
• Core LRU behavior

🔹 remove_tail — evict LRU entry#

fn remove_tail(&mut self) {

• Evicts the least recently used entry.
  • 가장 최근에 사용된 항목을 삭제합니다.

        if let Some(i) = self.tail {

• Only if cache is non-empty

            let key = self.entries[i].key.clone();

• Extract key for HashMap removal

            self.detach(i);

• Remove from linked list

            self.map.remove(&key);

            self.entries[i].val = None;

• Mark entry as empty
• Slot stays allocated

🔹 insert#

pub fn insert(&mut self, key: K, value: V) -> Option<V> {

• Insert or update a value.

        if let Some(&i) = self.map.get(&key) {

• Key already exists

            let old = self.entries[i].val.replace(value);

• Replace value
• Keep old for return

            self.detach(i);
            self.push_front(i);

• Update recency

            return old;

• Return replaced value

        if self.len() == self.capacity {
            self.remove_tail();
        }

• Evict LRU if cache is full

        let i = self.entries.len();

• New index

        self.entries.push(Entry {

• Create new entry node

            key: key.clone(),
            val: Some(value),
            prev: None,
            next: None,

• Initially detached

        self.push_front(i);

• New entry becomes MRU

        self.map.insert(key, i);

• Register key → index

        None

• No old value replaced

🔹 get#

pub fn get(&mut self, key: &K) -> Option<&V> {

• Lookup + update recency.

        if self.map.contains_key(key) {
            self.access(key);
        }

• If exists → mark as MRU

        self.map
            .get(key)
            .and_then(|&i| self.entries[i].val.as_ref())

• Return reference to value

🔹 get_mut#

• Same as get, but mutable reference.

🔹 remove#

pub fn remove(&mut self, key: &K) -> Option<V> {

• Remove entry entirely.

        self.map.remove(key).map(|i| {

• Remove from map
• Retrieve index

            self.detach(i);

• Remove from LRU list

            self.entries[i].val.take().unwrap()

• Take ownership of value

🔹 Utility methods#

pub fn contains(&self, key: &K) -> bool
pub fn len(&self) -> usize
pub fn is_full(&self) -> bool
pub fn is_empty(&self) -> bool

• Simple wrappers around HashMap

• O(1) operations

📦 Bit-level result layout#

eax (u32)
31            16 15             0
┌────────────────┬────────────────┐
│ data[0..1]     │ data[len-2..]  │
└────────────────┴────────────────┘

🧩 One-to-one mapping with your Rust inline asm#

🧠 What the function computes (one-screen view)#

look_up_identifier(data: *const u8, len: usize) -> u32

• 기본적인 아이디어는 문자열 앞 2가리, 뒷자리 2자리를 가져와서 hash 값으로 쓰는 아주 단순한 원리.

Memory (bytes)
┌───────────────────────────────────────────┐
│ data[0]  data[1]  ...        data[len-2] │ data[len-1]
└───┬────────┬───────────────────┬─────────┘
    │        │                   │
    │        │                   └─ last 2 bytes
    │        └─ first 2 bytes
    │
    ▼

If len >= 4:
────────────────────────────────────────────────────────

   first WORD (16 bits)          last WORD (16 bits)
┌───────────────┐              ┌───────────────┐
│ data[0..1]    │              │ data[len-2..] │
└───────┬───────┘              └───────┬───────┘
        │                               │
        │                               │
        ▼                               ▼

        eax = first_word << 16
        edx = last_word

        eax = eax | edx

        result (u32):
        ┌─────────────────────────────────────────┐
        │ first_word (16 bits) | last_word (16)  │
        └─────────────────────────────────────────┘


If len < 4:
────────────────────────────────────────────────────────

        result = 80 (constant fallback)

🧩 Instruction-by-instruction flow (diagram)#

Registers on entry:
────────────────────────────────────────
rdi → data pointer
rsi → len

Assembly flow:
────────────────────────────────────────

cmp rsi, 4
│
├─ len < 4 ───────────────► eax = 80
│                          │
│                          └──► return eax
│
└─ len >= 4
   │
   ├─ movzx eax, WORD PTR [rdi]
   │      ↑
   │      │
   │      └─ load first 2 bytes
   │
   ├─ movzx edx, WORD PTR [rdi + rsi - 2]
   │      ↑
   │      │
   │      └─ load last 2 bytes
   │
   ├─ shl eax, 16
   │
   ├─ or eax, edx
   │
   └──► return eax

📦 Bit-level view (hash shape)#

32-bit result layout
────────────────────────────────────────

31            16 15             0
┌────────────────┬────────────────┐
│ first 2 bytes  │ last 2 bytes   │
│ data[0..1]     │ data[len-2..]  │
└────────────────┴────────────────┘

🎯 What this means conceptually#

HASH(data) =
    if len >= 4:
        (first_two_bytes << 16) | last_two_bytes
    else:
        80

🧠 Why this is fast (visual intuition)#

Standard hash (SipHash):
┌─────────────────────────────┐
│ mix → rotate → xor → repeat │  (many rounds)
└─────────────────────────────┘

This hash:
┌──────────┐  ┌──────────┐
│ load 16b │  │ load 16b │
└────┬─────┘  └────┬─────┘
     │             │
     └─── combine ─┘

✅ main.s (macOS / ARM64)#

/* main.s — macOS ARM64 (AArch64)
 *
 * uint32_t look_up_identifier(const uint8_t *data, size_t len)
 *
 * x0 = data pointer
 * x1 = len
 * return value in w0
 */

    .section __TEXT,__text
    .global _look_up_identifier
    .align 2

_look_up_identifier:
    /* if (len < 4) goto fail */
    cmp     x1, #4
    b.lo    fail

    /* load first 2 bytes */
    ldrh    w0, [x0]          // w0 = data[0..1]

    /* compute (len - 2) */
    sub     x2, x1, #2

    /* load last 2 bytes */
    ldrh    w3, [x0, x2]      // w3 = data[len-2..len-1]

    /* shift first half */
    lsl     w0, w0, #16

    /* combine */
    orr     w0, w0, w3

    ret

fail:
    mov     w0, #80
    ret