Skip to content

Accurate, fast FP4 KV-cache decoding through algorithm-system co-design.

39.6 KB
Raw Blame
"""CuTeDSL K/V page quantization."""

import math
from typing import Tuple

import torch
import tvm_ffi

import cutlass
import cutlass.cute as cute
from cutlass import Int32, const_expr
from cutlass.cute.runtime import make_fake_stream, make_fake_tensor

from ._block_scale import (
    GROUPS_PER_ATOM,
    _load_vector,
    gaussian_global_scale,
    quantize_atom,
    quantize_atom_with_scale,
)
from .quantize_q_kernel import _mul_rn, _sub_rn, _write_tail_token
from .scale_mode import DEFAULT_SCALE_MODE, scale_format, scale_rule, sf_vec_size


PAGE_SIZE = 128
HEAD_DIM = 128
SF_VEC_SIZE = 16
KEY_SCALE_GEOMETRIES = ("local", "gaussian_global")


@cute.jit
def _resolve_work(
    source_tokens: cute.Tensor,
    destination_pages: cute.Tensor,
    work: Int32,
) -> Tuple[Int32, Int32]:
    """Map a grid slot to the token it reads and the page it writes.

    The two ends are independent, which is what a paged cache needs — the
    tokens of one page are somewhere in a flat activation buffer and the page
    they belong to is wherever the block table says. A negative destination
    marks a grid slot with no work, so the launch shape can be fixed while the
    batch varies.
    """
    return source_tokens[work], destination_pages[work]


@cute.jit
def _rebase(
    tensor: cute.Tensor,
    bases,
    region: cutlass.Constexpr[int],
    layer: Int32,
) -> cute.Tensor:
    """The same page layout, based wherever this layer's copy happens to be.

    A caller with one destination passes no table and gets the tensor back
    untouched. A caller with one destination per layer passes their base
    addresses, because independently allocated destinations share only their
    interior layout — their addresses are not a stride apart, so no single
    tensor can reach all of them. Row ``region`` of the table is this tensor's.
    """
    if const_expr(bases is None):
        return tensor
    return cute.make_tensor(
        cute.make_ptr(
            cutlass.Uint8,
            bases[region, layer],
            cute.AddressSpace.gmem,
            assumed_align=16,
        ),
        tensor.layout,
    )


@cute.jit
def _quantize_vector(
    values: cute.Tensor,
    destination: cute.Tensor,
    scales: cute.Tensor,
    page: Int32,
    lane: Int32,
    warp: Int32,
    head: Int32,
    sf_vec_size: cutlass.Constexpr[int],
    rest_k: cutlass.Constexpr[int],
    rule: cutlass.Constexpr,
    use_gaussian_global_scale: cutlass.Constexpr[bool],
):
    """Quantize one thread's vector to E2M1 with one scale per group.

    K and V reduce to this once their page slicing is done: K walks the head
    dimension of one token, V walks one head dimension across the page. The
    scale tile is addressed identically in both, which is what keeps the two
    directions numerically the same.

    ``values`` holds the vector in registers.
    """
    vector_scale = None
    if const_expr(use_gaussian_global_scale):
        vector_scale = gaussian_global_scale(values)
    for k_atom in cutlass.range_constexpr(rest_k):
        if const_expr(use_gaussian_global_scale):
            packed_scale = quantize_atom_with_scale(
                values,
                destination,
                k_atom,
                sf_vec_size,
                vector_scale,
            )
        else:
            packed_scale = quantize_atom(
                values, destination, k_atom, sf_vec_size, rule
            )
        scale_tile = scales[page, lane, warp, 0, None, k_atom, head]
        scale_word = cute.make_tensor(
            cute.recast_ptr(scale_tile.iterator, dtype=cutlass.Int32),
            cute.make_layout(1),
        )
        scale_word[0] = packed_scale


@cute.jit
def _cache_basis(
    values: cute.Tensor,
    shift_vector: cute.Tensor,
    rotate: cutlass.Constexpr[bool],
) -> cute.Tensor:
    """One token's K head as the cache stores it: rotated, then centered.

    The exact BF16 values are widened to FP32 and butterflied ``(a, c) ->
    (a + c, a - c)`` over the index bits, lowest first; one separately rounded
    multiply by the FP32 ``1 / sqrt(128)`` and one separately rounded subtract
    of the shift (already in the rotated basis, BF16 widened exactly) follow,
    and the result is rounded to BF16 once. A butterfly's result depends only
    on its operands' order, not on which thread holds them, so this is the
    decode quantizer's ``_write_tail_token`` arithmetic element for element.
    A contracted FMA in place of either rounded step moves 7 in 307,200 values
    by one BF16 step.
    """
    work = cute.make_rmem_tensor(cute.make_layout(HEAD_DIM), cutlass.Float32)
    work.store(values.load().to(cutlass.Float32))
    if const_expr(rotate):
        for bit in cutlass.range_constexpr(int(math.log2(HEAD_DIM))):
            stride = 1 << bit
            for j in cutlass.range_constexpr(HEAD_DIM):
                if const_expr((j & stride) == 0):
                    low = work[j]
                    high = work[j + stride]
                    work[j] = low + high
                    work[j + stride] = low - high
        inverse = cutlass.Float32(1.0 / math.sqrt(HEAD_DIM))
        for j in cutlass.range_constexpr(HEAD_DIM):
            work[j] = _mul_rn(work[j], inverse)
    if const_expr(shift_vector is not None):
        centre = cute.make_fragment_like(shift_vector)
        cute.autovec_copy(shift_vector, centre)
        for j in cutlass.range_constexpr(HEAD_DIM):
            work[j] = _sub_rn(work[j], cutlass.Float32(centre[j]))
    rounded = cute.make_rmem_tensor(cute.make_layout(HEAD_DIM), cutlass.BFloat16)
    rounded.store(work.load().to(cutlass.BFloat16))
    return rounded


@cute.jit
def _key_page(
    key: cute.Tensor,
    key_shift: cute.Tensor,
    key_pages_fp4: cute.Tensor,
    key_scales: cute.Tensor,
    source_tokens: cute.Tensor,
    destination_pages: cute.Tensor,
    destination_bases: cute.Tensor,
    item: Int32,
    layer: Int32,
    source_offset: Int32,
    heads: cutlass.Constexpr[int],
    sf_vec_size: cutlass.Constexpr[int],
    rest_k: cutlass.Constexpr[int],
    rule: cutlass.Constexpr,
    use_gaussian_global_scale: cutlass.Constexpr[bool],
    rotate: cutlass.Constexpr[bool],
):
    """One head of one K page, one token's head vector per thread."""
    thread, _, _ = cute.arch.thread_idx()
    lane = thread % 32
    warp = thread // 32
    head = item % heads
    source_token, page = _resolve_work(
        source_tokens, destination_pages, item // heads
    )
    if page >= 0:
        source = key[source_token + source_offset + thread, head, None]
        values = _load_vector(source)
        if const_expr(rotate or key_shift is not None):
            shift_vector = None
            if const_expr(key_shift is not None):
                shift_vector = key_shift[layer, head, None]
            values = _cache_basis(values, shift_vector, rotate)
        _quantize_vector(
            values,
            _rebase(key_pages_fp4, destination_bases, 0, layer)[
                page, thread, head, None
            ],
            _rebase(key_scales, destination_bases, 1, layer),
            page,
            lane,
            warp,
            head,
            sf_vec_size,
            rest_k,
            rule,
            use_gaussian_global_scale,
        )


@cute.jit
def _value_page(
    value_pages: cute.Tensor,
    value_pages_fp4: cute.Tensor,
    value_scales: cute.Tensor,
    source_tokens: cute.Tensor,
    destination_pages: cute.Tensor,
    destination_bases: cute.Tensor,
    item: Int32,
    layer: Int32,
    source_offset: Int32,
    heads: cutlass.Constexpr[int],
    sf_vec_size: cutlass.Constexpr[int],
    rest_k: cutlass.Constexpr[int],
    rule: cutlass.Constexpr,
):
    """One head of one V page, one channel across the page per thread."""
    thread, _, _ = cute.arch.thread_idx()
    head = item % heads
    source_token, page = _resolve_work(
        source_tokens, destination_pages, item // heads
    )
    if page >= 0:
        source = value_pages[source_token + source_offset, None, head, thread]
        _quantize_vector(
            _load_vector(source),
            _rebase(value_pages_fp4, destination_bases, 2, layer)[
                page, head, thread, None
            ],
            _rebase(value_scales, destination_bases, 3, layer),
            page,
            thread % 32,
            thread // 32,
            head,
            sf_vec_size,
            rest_k,
            rule,
            const_expr(False),
        )


@cute.jit
def _tail_token(
    key: cute.Tensor,
    value: cute.Tensor,
    key_shift: cute.Tensor,
    tail_key: cute.Tensor,
    tail_value: cute.Tensor,
    query_start_loc: cute.Tensor,
    seq_lens: cute.Tensor,
    seqused_fp4: cute.Tensor,
    row_to_slot: cute.Tensor,
    item: Int32,
    layer: Int32,
    decode_rows: Int32,
    first_row: Int32,
    heads: cutlass.Constexpr[int],
    rotate: cutlass.Constexpr[bool],
    sink_tokens: cutlass.Constexpr[int],
    tail_chunks: cutlass.Constexpr[int],
):
    """One token into the BF16 rolling page and/or sink.

    A one-token row in ``[first_row, decode_rows)`` gets one CTA for its
    token. Every later row gets ``PAGE_SIZE + sink_tokens`` candidates: one
    per rolling position past its FP4 prefix, then one per sink position, a
    sink candidate standing down where the rolling side already covers its
    token so that a token in both regions is written by one CTA, to both.
    Candidates past the row's length, before this step's tokens, or in a row
    with no slot exit. ``tail_chunks`` CTAs share a token when its groups
    outnumber one CTA's threads.
    """
    thread, _, _ = cute.arch.thread_idx()
    candidates = const_expr(PAGE_SIZE + sink_tokens)
    candidate = item // tail_chunks
    decode_count = decode_rows - first_row
    is_decode = candidate < decode_count
    later = candidate - decode_count
    row = Int32(
        cutlass.select_(
            is_decode, first_row + candidate, decode_rows + later // candidates
        )
    )
    within = later % candidates
    start = query_start_loc[row]
    seq_len = seq_lens[row]
    quantized = seqused_fp4[row]
    slot = row_to_slot[row]
    computed = seq_len - (query_start_loc[row + 1] - start)
    rolling = within < PAGE_SIZE
    position = Int32(
        cutlass.select_(
            is_decode,
            seq_len - 1,
            cutlass.select_(rolling, quantized + within, within - PAGE_SIZE),
        )
    )
    if (
        (slot >= 0)
        & (position < seq_len)
        & (position >= computed)
        & (is_decode | rolling | (position < quantized))
    ):
        shift = None
        if const_expr(key_shift is not None):
            shift = key_shift[layer, None, None]
        _write_tail_token(
            key,
            value,
            shift,
            tail_key[layer, None, None, None, None],
            tail_value[layer, None, None, None, None],
            start + position - computed,
            slot,
            position,
            position - quantized,
            (item % tail_chunks) * 128 + thread,
            heads,
            HEAD_DIM,
            rotate,
            key_shift is not None,
            sink_tokens,
        )


@cute.kernel
def _write_kv_kernel(
    key: cute.Tensor,
    value: cute.Tensor,
    value_pages: cute.Tensor,
    key_pages_fp4: cute.Tensor,
    key_scales: cute.Tensor,
    value_pages_fp4: cute.Tensor,
    value_scales: cute.Tensor,
    source_tokens: cute.Tensor,
    destination_pages: cute.Tensor,
    query_start_loc: cute.Tensor,
    seq_lens: cute.Tensor,
    seqused_fp4: cute.Tensor,
    row_to_slot: cute.Tensor,
    tail_key: cute.Tensor,
    tail_value: cute.Tensor,
    key_shift: cute.Tensor,
    destination_bases: cute.Tensor,
    layer_index: Int32,
    decode_rows: Int32,
    first_row: Int32,
    key_end: Int32,
    value_end: Int32,
    source_layer_stride: Int32,
    heads: cutlass.Constexpr[int],
    key_sf_vec_size: cutlass.Constexpr[int],
    key_rest_k: cutlass.Constexpr[int],
    key_rule: cutlass.Constexpr,
    value_sf_vec_size: cutlass.Constexpr[int],
    value_rest_k: cutlass.Constexpr[int],
    value_rule: cutlass.Constexpr,
    use_gaussian_global_scale: cutlass.Constexpr[bool],
    rotate: cutlass.Constexpr[bool],
    sink_tokens: cutlass.Constexpr[int],
    tail_chunks: cutlass.Constexpr[int],
):
    """K pages, then V pages, then tail tokens, on one flat CTA axis.

    The roles share no data and need no synchronization between CTAs. A
    per-layer launch (``destination_bases``) takes the layer from the grid,
    a one-layer launch from ``layer_index``, which also selects that layer's
    shift and tail.
    """
    item, _, grid_layer = cute.arch.block_idx()
    layer = layer_index
    if const_expr(destination_bases is not None):
        layer = grid_layer
    source_offset = grid_layer * source_layer_stride
    if item < key_end:
        if const_expr(key_pages_fp4 is not None):
            _key_page(
                key,
                key_shift,
                key_pages_fp4,
                key_scales,
                source_tokens,
                destination_pages,
                destination_bases,
                item,
                layer,
                source_offset,
                heads,
                key_sf_vec_size,
                key_rest_k,
                key_rule,
                use_gaussian_global_scale,
                rotate,
            )
    elif item < value_end:
        if const_expr(value_pages_fp4 is not None):
            _value_page(
                value_pages,
                value_pages_fp4,
                value_scales,
                source_tokens,
                destination_pages,
                destination_bases,
                item - key_end,
                layer,
                source_offset,
                heads,
                value_sf_vec_size,
                value_rest_k,
                value_rule,
            )
    else:
        if const_expr(tail_key is not None):
            _tail_token(
                key,
                value,
                key_shift,
                tail_key,
                tail_value,
                query_start_loc,
                seq_lens,
                seqused_fp4,
                row_to_slot,
                item - value_end,
                layer,
                decode_rows,
                first_row,
                heads,
                rotate,
                sink_tokens,
                tail_chunks,
            )


class _KVWrite:
    """The compile-time half of :class:`KVCacheWriter`: one launch configuration."""

    def __init__(
        self,
        *,
        heads: int,
        write_key: bool,
        write_value: bool,
        write_tail: bool,
        key_scale_mode: str,
        value_scale_mode: str,
        scale_geometry: str,
        rotate: bool,
        sink_tokens: int,
    ) -> None:
        self.heads = heads
        self.write_key = write_key
        self.write_value = write_value
        self.write_tail = write_tail
        self.key_sf_vec_size = sf_vec_size(key_scale_mode)
        self.key_rest_k = scale_atoms(HEAD_DIM, key_scale_mode)
        self.key_rule = scale_rule(key_scale_mode)
        self.value_sf_vec_size = sf_vec_size(value_scale_mode)
        self.value_rest_k = scale_atoms(PAGE_SIZE, value_scale_mode)
        self.value_rule = scale_rule(value_scale_mode)
        self.use_gaussian_global_scale = scale_geometry == "gaussian_global"
        self.rotate = rotate
        self.sink_tokens = sink_tokens
        # A token's K groups padded to whole warps, then its V groups.
        groups = heads * (HEAD_DIM // SF_VEC_SIZE)
        self.tail_chunks = ((groups + 31) // 32 * 32 + groups + 127) // 128
        self.smem = 0

    @cute.jit
    def __call__(
        self,
        key,
        value,
        key_pages_fp4,
        key_scales,
        value_pages_fp4,
        value_scales,
        source_tokens: cute.Tensor,
        destination_pages: cute.Tensor,
        query_start_loc,
        seq_lens,
        seqused_fp4,
        row_to_slot,
        tail_key,
        tail_value,
        key_shift,
        destination_bases,
        layer_index: Int32,
        decode_rows: Int32,
        first_row: Int32,
        stream,
    ):
        layers = Int32(1)
        if const_expr(destination_bases is not None):
            layers = destination_bases.shape[1]
        page_items = self.heads * source_tokens.shape[0]
        key_end = Int32(0)
        if const_expr(self.write_key):
            key_end = page_items
        value_end = key_end
        if const_expr(self.write_value):
            value_end = key_end + page_items
        tail_items = Int32(0)
        if const_expr(self.write_tail):
            tail_items = (
                (decode_rows - first_row)
                + (seq_lens.shape[0] - decode_rows) * (PAGE_SIZE + self.sink_tokens)
            ) * self.tail_chunks
        # One destination per layer means one source per layer too, stacked in
        # that order along the token axis.
        tokens = key
        if const_expr(key is None):
            tokens = value
        source_layer_stride = tokens.shape[0] // layers
        # V reads one channel down a page: a (page, token, head, dim) view whose
        # page axis has a one-token stride, so the leading index is a token
        # offset and a work item can start anywhere. The axes overlap, which is
        # harmless for a read.
        value_pages = None
        if const_expr(value is not None):
            value_pages = cute.make_tensor(
                value.iterator,
                cute.make_layout(
                    (source_tokens.shape[0], PAGE_SIZE, self.heads, HEAD_DIM),
                    stride=(value.stride[0], value.stride[0], HEAD_DIM, 1),
                ),
            )
        _write_kv_kernel(
            key,
            value,
            value_pages,
            key_pages_fp4,
            _as_bytes(key_scales),
            value_pages_fp4,
            _as_bytes(value_scales),
            source_tokens,
            destination_pages,
            query_start_loc,
            seq_lens,
            seqused_fp4,
            row_to_slot,
            tail_key,
            tail_value,
            key_shift,
            destination_bases,
            layer_index,
            decode_rows,
            first_row,
            key_end,
            value_end,
            source_layer_stride,
            const_expr(self.heads),
            const_expr(self.key_sf_vec_size),
            const_expr(self.key_rest_k),
            const_expr(self.key_rule),
            const_expr(self.value_sf_vec_size),
            const_expr(self.value_rest_k),
            const_expr(self.value_rule),
            const_expr(self.use_gaussian_global_scale),
            const_expr(self.rotate),
            const_expr(self.sink_tokens),
            const_expr(self.tail_chunks),
            # The per-layer form is promotion's; a profile tells it from the
            # write path's launches by name.
            _name_prefix="seal" if destination_bases is not None else None,
        ).launch(
            grid=(value_end + tail_items, 1, layers),
            block=(128, 1, 1),
            smem=self.smem,
            stream=stream,
        )


@cute.jit
def _as_bytes(scales):
    if const_expr(scales is None):
        return None
    return cute.make_tensor(
        cute.recast_ptr(scales.iterator, dtype=cutlass.Uint8), scales.layout
    )


_SCALE_TYPES = {
    torch.uint8: cutlass.Uint8,
    torch.float8_e4m3fn: cutlass.Float8E4M3FN,
    torch.float8_e8m0fnu: cutlass.Float8E8M0FNU,
}
_compiled_writers: dict[tuple, object] = {}


def _compile_writer(
    *,
    heads: int,
    key_scales_dtype: torch.dtype | None,
    value_scales_dtype: torch.dtype | None,
    key_scale_mode: str,
    value_scale_mode: str,
    scale_geometry: str,
    write_tail: bool,
    shift_dtype: torch.dtype | None,
    rotate: bool,
    per_layer: bool,
    sink_tokens: int,
):
    """The compiled launch for one configuration; every page interior static.

    TVM-FFI checks each call's tensors against these declarations (dtype,
    rank, device, alignment, every static extent and stride, and equality of
    shared symbols), which is the per-call validation: only token pitches,
    block pitches, and counts are free. Shapes are 32-bit, pitches 64-bit,
    since a block index times a block pitch passes 2^31 at 14563 blocks.
    """
    cache_key = (
        torch.cuda.current_device(),
        heads,
        key_scales_dtype,
        value_scales_dtype,
        key_scale_mode,
        value_scale_mode,
        scale_geometry,
        write_tail,
        shift_dtype,
        rotate,
        per_layer,
        sink_tokens,
    )
    compiled = _compiled_writers.get(cache_key)
    if compiled is not None:
        return compiled

    def fake(dtype, shape, stride, align):
        return make_fake_tensor(dtype, shape, stride, assumed_align=align)

    sym32, sym64 = cute.sym_int32, cute.sym_int64
    write_key = key_scales_dtype is not None
    write_value = value_scales_dtype is not None

    def token_major():
        return fake(
            cutlass.BFloat16,
            (sym32(), heads, HEAD_DIM),
            (sym64(divisibility=8), HEAD_DIM, 1),
            16,
        )

    blocks, layers, work = sym32(), sym32(), sym32()

    def regions(packed_shape, scales_dtype, rest_k):
        packed = fake(
            cutlass.Uint8,
            (blocks,) + packed_shape,
            (sym64(divisibility=16),) + _dense_strides(packed_shape),
            16,
        )
        scales = fake(
            _SCALE_TYPES[scales_dtype],
            (blocks, 32, 4, 1, 4, rest_k, heads),
            (sym64(divisibility=16), 16, 4, rest_k * 512, 1, 512, rest_k * 512),
            16,
        )
        return packed, scales

    key = token_major() if write_key or write_tail else None
    value = token_major() if write_value or write_tail else None
    key_regions = (None, None)
    if write_key:
        key_regions = regions(
            (PAGE_SIZE, heads, HEAD_DIM // 2),
            key_scales_dtype,
            scale_atoms(HEAD_DIM, key_scale_mode),
        )
    value_regions = (None, None)
    if write_value:
        value_regions = regions(
            (heads, HEAD_DIM, PAGE_SIZE // 2),
            value_scales_dtype,
            scale_atoms(PAGE_SIZE, value_scale_mode),
        )
    rows, row_vectors, tails = sym32(), (None,) * 4, (None, None)
    if write_tail:
        row_vectors = (
            fake(Int32, (sym32(),), (1,), 4),
            *(fake(Int32, (rows,), (1,), 4) for _ in range(3)),
        )
        tail_shape = (layers, sym32(), PAGE_SIZE + sink_tokens, heads, HEAD_DIM)
        tail_strides = (sym64(), sym64()) + _dense_strides(tail_shape[2:])
        tails = (
            fake(cutlass.BFloat16, tail_shape, tail_strides, 16),
            fake(cutlass.BFloat16, tail_shape, tail_strides, 16),
        )
    shift = None
    if shift_dtype is not None:
        shift = fake(
            {torch.float32: cutlass.Float32, torch.bfloat16: cutlass.BFloat16}[
                shift_dtype
            ],
            (layers, heads, HEAD_DIM),
            (heads * HEAD_DIM, HEAD_DIM, 1),
            16,
        )
    bases = (
        fake(cutlass.Int64, (4, layers), (sym64(), 1), 8) if per_layer else None
    )
    launch = _KVWrite(
        heads=heads,
        write_key=write_key,
        write_value=write_value,
        write_tail=write_tail,
        key_scale_mode=key_scale_mode,
        value_scale_mode=value_scale_mode,
        scale_geometry=scale_geometry,
        rotate=rotate,
        sink_tokens=sink_tokens,
    )
    compiled = cute.compile(
        launch,
        key,
        value,
        *key_regions,
        *value_regions,
        fake(Int32, (work,), (1,), 4),
        fake(Int32, (work,), (1,), 4),
        *row_vectors,
        *tails,
        shift,
        bases,
        Int32(0),
        Int32(0),
        Int32(0),
        make_fake_stream(use_tvm_ffi_env_stream=True),
        options="--enable-tvm-ffi",
    )
    _compiled_writers[cache_key] = compiled
    return compiled


def _validate_destination(
    pages_fp4: torch.Tensor,
    scales: torch.Tensor,
    *,
    heads: int,
    inner_shape: tuple[int, ...],
    rest_k: int,
) -> None:
    """Reject a destination whose page interior is not the quantizer's layout.

    Only the page pitch is free. Everything inside a page is the layout the
    decode kernel reads back, so a mismatch there is silent corruption.
    """
    if (
        pages_fp4.dtype is not torch.uint8
        or not pages_fp4.is_cuda
        or tuple(pages_fp4.shape[1:]) != inner_shape
        or pages_fp4.stride()[1:] != _dense_strides(inner_shape)
        or pages_fp4.stride(0) % 16
    ):
        raise ValueError(
            f"packed destination must be uint8 CUDA pages of {inner_shape}, "
            "dense within a page, 16-byte page pitch"
        )
    if (
        scales.dtype not in _SCALE_TYPES
        or scales.device != pages_fp4.device
        or tuple(scales.shape[1:]) != (32, 4, 1, 4, rest_k, heads)
        or scales.stride()[1:] != (16, 4, rest_k * 512, 1, 512, rest_k * 512)
        or scales.stride(0) % 16
    ):
        raise ValueError(
            "scale destination must use the quantizer's own scale layout"
        )
    if pages_fp4.shape[0] != scales.shape[0]:
        raise ValueError("packed and scale destinations must have equal pages")


class KVCacheWriter:
    """K/V into FP4 pages and the BF16 tail, one launch per call.

    Constructed once with everything that does not change between steps, and
    all of it is checked here: the scale modes, geometry, the tail buffers
    ``[layers, slots, 128 + sink_tokens, heads, 128]``, the shift
    ``[layers, heads, 128]`` (FP32, or BF16, already in the rotated basis),
    and the ``[4, layers]`` base-address table of a per-layer writer. A call
    passes only what changes: the source K/V, a layer's four regions (as
    :meth:`bind_regions` returned them, or as tensors, which TVM-FFI then
    converts on every call), the step's work table and row
    metadata, the layer index, the decode row count and the first row whose
    tail token this writes. TVM-FFI checks each call's tensors against the
    layouts compiled in.

    The roles present are those given: K pages with K regions, V pages with V
    regions, tail tokens with tail buffers. A per-layer writer (one with
    ``destination_bases``) quantizes the same work items for every layer at
    once from a source holding the layers back to back, each into the
    destination its row of the table names; it writes no tail.

    ``rotate_key`` and ``key_shift`` put raw K into the cache's basis on the
    way in, for the pages and the tail alike, with the arithmetic of
    :func:`_cache_basis`. A work item reads the 128 tokens from its source
    token and writes its destination page; a negative page skips it, which is
    how a fixed launch shape covers a varying batch.
    """

    def __init__(
        self,
        *,
        regions: tuple,
        key_scale_mode: str = DEFAULT_SCALE_MODE,
        value_scale_mode: str = DEFAULT_SCALE_MODE,
        key_scale_geometry: str = "local",
        rotate_key: bool = False,
        key_shift: torch.Tensor | None = None,
        tail_key: torch.Tensor | None = None,
        tail_value: torch.Tensor | None = None,
        sink_tokens: int = 0,
        destination_bases: torch.Tensor | None = None,
    ) -> None:
        key_packed, key_scales, value_packed, value_scales = regions
        any_packed = key_packed if key_packed is not None else value_packed
        if any_packed is None:
            raise ValueError("a writer needs K or V regions")
        heads = any_packed.shape[2 if key_packed is not None else 1]
        self.heads = heads
        self.key_scale_mode = key_scale_mode
        self.value_scale_mode = value_scale_mode
        rules = (scale_rule(key_scale_mode), scale_rule(value_scale_mode))
        if any(isinstance(rule, str) for rule in rules) and key_scale_geometry != "local":
            raise ValueError(
                "MXFP4 pages support local scales only"
            )
        if key_scale_geometry not in KEY_SCALE_GEOMETRIES:
            raise ValueError(
                f"unknown key_scale_geometry {key_scale_geometry!r}, expected "
                f"one of {list(KEY_SCALE_GEOMETRIES)}"
            )
        if key_packed is None and (key_shift is not None or rotate_key):
            raise ValueError("the K transform needs K regions")
        if (tail_key is None) != (tail_value is None):
            raise ValueError("tail_key and tail_value come together")
        if tail_key is not None and destination_bases is not None:
            raise ValueError("a per-layer writer writes no tail")
        device = any_packed.device
        layers = None

        def layer_axis(tensor: torch.Tensor, name: str, inner: tuple, dtypes):
            nonlocal layers
            if (
                tensor.dtype not in dtypes
                or tensor.device != device
                or not tensor.is_contiguous()
                or tuple(tensor.shape[1:]) != inner
            ):
                raise ValueError(
                    f"{name} must be contiguous {' or '.join(map(str, dtypes))} "
                    f"[layers, *{inner}] on {device}"
                )
            if layers is not None and tensor.shape[0] != layers:
                raise ValueError(
                    f"{name} has {tensor.shape[0]} layers, not {layers}"
                )
            layers = tensor.shape[0]

        if destination_bases is not None:
            if (
                destination_bases.dtype is not torch.int64
                or destination_bases.device != device
                or not destination_bases.is_contiguous()
                or destination_bases.ndim != 2
                or destination_bases.shape[0] != 4
            ):
                raise ValueError(
                    "destination_bases must be a contiguous int64 [4, layers] "
                    "table of K packed, K scale, V packed and V scale addresses"
                )
            layers = destination_bases.shape[1]
        if tail_key is not None:
            row = (PAGE_SIZE + sink_tokens, heads, HEAD_DIM)
            for name, tensor in (("tail_key", tail_key), ("tail_value", tail_value)):
                if (
                    tensor.dtype is not torch.bfloat16
                    or tensor.device != device
                    or not tensor.is_contiguous()
                    or tensor.ndim != 5
                    or tuple(tensor.shape[2:]) != row
                    or tensor.shape != tail_key.shape
                ):
                    raise ValueError(
                        f"{name} must be contiguous BF16 [layers, slots, "
                        f"{PAGE_SIZE + sink_tokens}, {heads}, {HEAD_DIM}] on {device}"
                    )
            layers = tail_key.shape[0]
        if key_shift is not None:
            layer_axis(
                key_shift,
                "key_shift",
                (heads, HEAD_DIM),
                (torch.float32, torch.bfloat16),
            )
        self._regions_dtypes = (
            None if key_scales is None else key_scales.dtype,
            None if value_scales is None else value_scales.dtype,
        )
        self.bind_regions(*regions)
        self._compiled = _compile_writer(
            heads=heads,
            key_scales_dtype=self._regions_dtypes[0],
            value_scales_dtype=self._regions_dtypes[1],
            key_scale_mode=key_scale_mode,
            value_scale_mode=value_scale_mode,
            scale_geometry=key_scale_geometry,
            write_tail=tail_key is not None,
            shift_dtype=None if key_shift is None else key_shift.dtype,
            rotate=bool(rotate_key),
            per_layer=destination_bases is not None,
            sink_tokens=sink_tokens,
        )
        self.writes_tail = tail_key is not None
        self.layers = layers if destination_bases is not None else None
        # Converted once: a tvm_ffi.Tensor crosses into the compiled call as a
        # pointer, where a torch tensor is converted on every call.
        self._constants = tuple(
            None if tensor is None else tvm_ffi.from_dlpack(tensor)
            for tensor in (
                tail_key,
                tail_value,
                key_shift,
                destination_bases,
            )
        )

    def bind_regions(
        self,
        key_pages_fp4: torch.Tensor | None,
        key_scales: torch.Tensor | None,
        value_pages_fp4: torch.Tensor | None,
        value_scales: torch.Tensor | None,
    ) -> tuple:
        """Check one layer's four regions once and keep them call-ready."""
        dtypes = (
            None if key_scales is None else key_scales.dtype,
            None if value_scales is None else value_scales.dtype,
        )
        if dtypes != self._regions_dtypes:
            raise ValueError(
                f"regions carry scale dtypes {dtypes}, this writer was built for "
                f"{self._regions_dtypes}"
            )
        if key_pages_fp4 is not None:
            _validate_destination(
                key_pages_fp4,
                key_scales,
                heads=self.heads,
                inner_shape=(PAGE_SIZE, self.heads, HEAD_DIM // 2),
                rest_k=scale_atoms(HEAD_DIM, self.key_scale_mode),
            )
        if value_pages_fp4 is not None:
            _validate_destination(
                value_pages_fp4,
                value_scales,
                heads=self.heads,
                inner_shape=(self.heads, HEAD_DIM, PAGE_SIZE // 2),
                rest_k=scale_atoms(PAGE_SIZE, self.value_scale_mode),
            )
        return tuple(
            None if region is None else tvm_ffi.from_dlpack(region)
            for region in (key_pages_fp4, key_scales, value_pages_fp4, value_scales)
        )

    def __call__(
        self,
        key: torch.Tensor | None,
        value: torch.Tensor | None,
        regions: tuple,
        source_tokens: torch.Tensor,
        destination_pages: torch.Tensor,
        query_start_loc: torch.Tensor | None = None,
        seq_lens: torch.Tensor | None = None,
        seqused_fp4: torch.Tensor | None = None,
        row_to_slot: torch.Tensor | None = None,
        layer: int = 0,
        decode_rows: int = 0,
        first_row: int = 0,
    ) -> None:
        """Write this call's pages and tail tokens; launch nothing if there are none.

        ``key`` and ``value`` are ``[tokens, heads, 128]`` BF16, dense within a
        token; a per-layer writer's holds the layers back to back. Rows
        ``[0, decode_rows)`` of the row metadata are one-token rows; rows
        before ``first_row`` get no tail write.
        """
        if not destination_pages.shape[0] and (
            not self.writes_tail or seq_lens.shape[0] == first_row
        ):
            return
        if self.layers is not None:
            tokens = (key if key is not None else value).shape[0]
            if tokens % self.layers:
                # Rounding the per-layer stride down would shift every layer
                # but the first by a few tokens: a plausible-looking cache,
                # quietly out of step.
                raise ValueError(
                    f"a source of {tokens} tokens does not divide into "
                    f"{self.layers} layers"
                )
        tail_key, tail_value, key_shift, bases = self._constants
        self._compiled(
            key,
            value,
            *regions,
            source_tokens,
            destination_pages,
            query_start_loc,
            seq_lens,
            seqused_fp4,
            row_to_slot,
            tail_key,
            tail_value,
            key_shift,
            bases,
            layer,
            decode_rows,
            first_row,
        )


def scale_atoms(extent: int, scale_mode: str) -> int:
    """How many four-group scale atoms cover ``extent`` values under ``scale_mode``."""
    return extent // (GROUPS_PER_ATOM * sf_vec_size(scale_mode))


def scale_dtype(scale_mode: str) -> torch.dtype:
    """E4M3 for an NVFP4 mode, E8M0 for an MX mode."""
    if scale_format(scale_mode) == "mxfp4":
        return torch.float8_e8m0fnu
    return torch.float8_e4m3fn


def _validate_pages(pages: torch.Tensor, name: str) -> tuple[int, int]:
    if (
        pages.dtype is not torch.bfloat16
        or not pages.is_cuda
        or not pages.is_contiguous()
        or pages.ndim != 4
    ):
        raise ValueError(
            f"{name} must be contiguous BF16 CUDA with shape "
            "[pages, 128, heads, 128]"
        )
    page_count, page_size, heads, head_dim = pages.shape
    if page_count < 1 or page_size != PAGE_SIZE or head_dim != HEAD_DIM:
        raise ValueError(
            f"{name} must have shape [pages, 128, heads, 128]"
        )
    return page_count, heads


def _allocate_scales(
    page_count: int,
    heads: int,
    rest_m: int,
    rest_k: int,
    device: torch.device,
) -> tuple[torch.Tensor, torch.Tensor]:
    atom_bytes = 512
    m_block_stride = rest_k * atom_bytes
    head_stride = rest_m * m_block_stride
    page_stride = heads * head_stride
    shape = (page_count, 32, 4, rest_m, 4, rest_k, heads)
    strides = (
        page_stride,
        16,
        4,
        m_block_stride,
        1,
        atom_bytes,
        head_stride,
    )
    storage = torch.empty(
        page_count * page_stride,
        dtype=torch.uint8,
        device=device,
    )
    return storage, storage.as_strided(shape, strides)


def _dense_strides(shape: tuple) -> tuple:
    """Row-major strides. The leading extent, which may be symbolic, is not used."""
    strides = [1]
    for extent in reversed(shape[1:]):
        strides.append(strides[-1] * extent)
    return tuple(reversed(strides))


def _identity_work(page_count: int, device) -> tuple[torch.Tensor, torch.Tensor]:
    """Work item ``w`` reads source page ``w`` and writes destination page ``w``."""
    pages = torch.arange(page_count, dtype=torch.int32, device=device)
    return pages * PAGE_SIZE, pages


def quantize_key_pages(
    key_pages: torch.Tensor,
    scale_mode: str = DEFAULT_SCALE_MODE,
    scale_geometry: str = "local",
) -> tuple[torch.Tensor, torch.Tensor]:
    """Quantize BF16 K pages into freshly allocated E2M1 and their scales."""
    page_count, heads = _validate_pages(key_pages, "key_pages")
    rest_k = scale_atoms(HEAD_DIM, scale_mode)
    key_pages_fp4 = torch.empty(
        page_count,
        PAGE_SIZE,
        heads,
        HEAD_DIM // 2,
        dtype=torch.uint8,
        device=key_pages.device,
    )
    _, key_scales = _allocate_scales(
        page_count,
        heads,
        1,
        rest_k,
        key_pages.device,
    )
    regions = (key_pages_fp4, key_scales, None, None)
    writer = KVCacheWriter(
        regions=regions,
        key_scale_mode=scale_mode,
        key_scale_geometry=scale_geometry,
    )
    writer(
        key_pages.reshape(-1, heads, HEAD_DIM),
        None,
        regions,
        *_identity_work(page_count, key_pages.device),
    )
    return key_pages_fp4, key_scales.view(scale_dtype(scale_mode))


def quantize_value_pages(
    value_pages: torch.Tensor,
    scale_mode: str = DEFAULT_SCALE_MODE,
) -> tuple[torch.Tensor, torch.Tensor]:
    """Quantize BF16 V pages into freshly allocated E2M1 and their scales."""
    page_count, heads = _validate_pages(value_pages, "value_pages")
    rest_m = HEAD_DIM // 128
    page_rest_k = scale_atoms(PAGE_SIZE, scale_mode)
    value_pages_fp4 = torch.empty(
        page_count,
        heads,
        HEAD_DIM,
        PAGE_SIZE // 2,
        dtype=torch.uint8,
        device=value_pages.device,
    )
    _, value_scales = _allocate_scales(
        page_count,
        heads,
        rest_m,
        page_rest_k,
        value_pages.device,
    )
    regions = (None, None, value_pages_fp4, value_scales)
    writer = KVCacheWriter(regions=regions, value_scale_mode=scale_mode)
    writer(
        None,
        value_pages.reshape(-1, heads, HEAD_DIM),
        regions,
        *_identity_work(page_count, value_pages.device),
    )
    return value_pages_fp4, value_scales.view(scale_dtype(scale_mode))