SIMD CSV parsing: nibble classification

Vectorized CSV Parsing with SIMD and Bitmasks

Parsing CSV according to RFC4180 requires identifying structural characters: commas for columns, \r\n for rows, and quotes for escaping. SIMD enables classifying 16 bytes per cycle without branching, using lookup tables for nibbles.

The algorithm works with ARM NEON (similar to x86 AVX2). Each byte is split into high and low nibbles. Two 16-element tables return class bits: COMMA=1, QUOTE=2, NEWLINE=3.

For a comma (0x2C): high nibble 0x2 → COMMA|QUOTE, low nibble 0xC → COMMA. AND leaves COMMA.

False positive check: the number of bytes in a class must equal the product of unique nibbles.

Vectorized Classifier Implementation

The scalar loop is replaced with 16-byte chunk processing:

use std::arch::aarch64::*;

const LO_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x2] = QUOTE;
    t[0xA] = NEWLINE;
    t[0xC] = COMMA;
    t[0xD] = NEWLINE;
    t
};

const HI_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x0] = NEWLINE;
    t[0x2] = COMMA | QUOTE;
    t
};

unsafe {
    let lo_lut = vld1q_u8(LO_LOOKUP.as_ptr());
    let hi_lut = vld1q_u8(HI_LOOKUP.as_ptr());
    let mask = vdupq_n_u8(0x0F);

    for chunk in bytes.chunks_exact(16) {
        let input = vld1q_u8(chunk.as_ptr());
        let lo_nibbles = vandq_u8(input, mask);
        let hi_nibbles = vandq_u8(vshrq_n_u8::<4>(input), mask);
        
        let lo_result = vqtbl1q_u8(lo_lut, lo_nibbles);
        let hi_result = vqtbl1q_u8(hi_lut, hi_nibbles);
        let classified = vandq_u8(lo_result, hi_result);
        
        let mut out = [0u8; 16];
        vst1q_u8(out.as_mut_ptr(), classified);
        classified_bytes.extend_from_slice(&out);
    }
}

Intrinsics vqtbl1q_u8 perform lookup, vandq_u8 — AND. The remainder is handled with padding.

Compression into Bitmasks

Classified bytes are converted into three Vec<u64>, where each bit in the mask corresponds to a character class position. u64 describes 64 bytes of the stream.

Example for alice,30,Irvine\n:

• COMMA mask: positions 5, 8
• QUOTE mask: empty
• NEWLINE mask: position 15

Filtering Quoted Fields

The classifier marks all characters, including internal ones. For filtering, a prefix XOR of the QUOTE mask is used.

Quote parity determines the state:

• Odd count after position → inside field
• Even count → outside field

Escaped "" self-balances. In the example "where she said, ""hi"\nto me":

• Position 0 ("): 1 quote → inside
• Position 17 ("): 2 → outside
• Position 29 ("): 6 → outside

Internal commas and \n are ignored.

Prefix XOR for States

For 16-byte chunks, a cumulative XOR of the QUOTE mask is computed. Bit i equals the parity of quotes from position i to the end.

// Pseudocode
let prefix_xor = 0;
for (i, &bit) in quote_mask.iter().enumerate() {
    prefix_xor ^= bit;
    if prefix_xor == 0 {
        // outside field
    }
}

The SIMD version uses horizontal XOR across chunks with a mask for popcount or bitscan.

Collecting Delimiter Positions

Filtered masks are scanned to extract positions of true delimiters:

• Commas outside → column boundaries
• \n outside → row boundaries

Positions are saved in offset arrays. This allows splitting the stream without copying data.

Advantages of the approach:

• No branching in the core
• 16x parallelism per chunk
• Compact bit representations
• Easily extendable to 32/64 bytes (AVX512)

Key Points

• Two 16-byte nibble tables replace a 256-byte LUT for SIMD.
• AND of two lookups eliminates false classes without conditions.
• Prefix XOR determines quoted field boundaries in O(n).
• Bitmasks compress data to 3/8 of the original size.
• The algorithm is portable: NEON → SSE4/AVX2 with pshufb/_mm_shuffle_epi8.

— Editorial Team