Step 1: Updating reminder

In SSE & AVX2 it's easy to copy the most significant bit to the least significant bit #0. We compare the number interpreted as a signed one with zero. It yields either 0x00 or 0xff ( − 1).

We can rewrite the main loop to shift the dividend left by 1, thus we'll be able to copy all its bits using that technique.

Shifting left by 1 is simple addition, which is a really fast operation.

Step 2: Comparison

There's no unsigned comparison in SSE nor AVX2, only signed one. It is possible to compare two unsigned numbers with a signed comparison: we need to negate their most significant bits. This is done by XOR-ing with 0x80.

Note that we need to perform xor once for the divisor, and eight times for the reminder.

Step 3: Conditional operations

Once we get a mask from the comparison, we can easily compute masked operations.

In fact we need unconditionally shift the quotient by 1 and then conditionally set the i-th bit.

Implementation (SSE)

The following C code shows all the implementation details.

uint8_t long_div_u8(uint8_t dividend, uint8_t divisor) {
    uint8_t reminder = 0;
    uint8_t quotient = 0;
    uint8_t bit = 0x80;

    uint8_t divisor_xored = divisor ^ 0x80;

    for (int i=7; i >= 0; i--) {

        // msb => 0 or -1
        const uint8_t msb = (int8_t)dividend < 0 ? 0xff : 0x00;

        // inject bit
        reminder -= msb;

        if ((int8_t)(reminder ^ 0x80) >= (int8_t)(divisor_xored) {
            // set i-th bit in quotient
            quotient |= bit;

            // adjust reminder
            reminder -= divisor;
        }

        bit >>= 1;
        dividend <<= 1;
        // make room for i-th bit of dividend at 0-th position
        reminder <<= 1;
    }

    return quotient;
}

The actual SSE implementation.

void sse_long_div_u8(const uint8_t* A, const uint8_t* B, uint8_t* C, size_t n) {
    const __m128i msb  = _mm_set1_epi8(int8_t(0x80));
    const __m128i zero = _mm_set1_epi8(0x00);

    for (size_t i=0; i < n; i += 16) {
        __m128i dividend = _mm_loadu_si128((__m128i*)(&A[i]));

        const __m128i divisor = _mm_loadu_si128((__m128i*)(&B[i]));
        __m128i divisor_xored = _mm_xor_si128(divisor, msb);

        __m128i bit      = msb;
        __m128i reminder = _mm_set1_epi16(0);
        __m128i quotient = _mm_set1_epi16(0);
        for (int j=0; j < 8; j++) {
            // copy msb of dividend into reminder
            const __m128i t0 = _mm_cmplt_epi8(dividend, zero);
            reminder = _mm_sub_epi8(reminder, t0);

            // unsigned comparison of divisor and reminder
            const __m128i reminder_xored = _mm_xor_si128(reminder, msb);
            const __m128i gt = _mm_cmpgt_epi8(divisor_xored, reminder_xored);

            // derive condition subtract and quotient bit
            const __m128i cond_divisor      = _mm_andnot_si128(gt, divisor);
            const __m128i cond_quotient_bit = _mm_andnot_si128(gt, bit);

            // conditionally update reminder and quotient
            reminder = _mm_sub_epi16(reminder, cond_divisor);
            quotient = _mm_or_si128(quotient, cond_quotient_bit);

            // next bit for quotient
            bit = _mm_srli_epi32(bit, 1);

            // put the next bit from dividend to MSB
            dividend = _mm_add_epi8(dividend, dividend);

            // make room for bit from dividend
            reminder = _mm_add_epi32(reminder, reminder);
        }

        _mm_storeu_si128((__m128i*)(&C[i]), quotient);
    }
}

Step 1: Updating reminder

Unlike SSE/AVX2 code it's easier to actually perform shift right to place i-th bit at position zero. Then isolating the least siginificant bit and merging it with quotient can be expressed as a single ternary operation.

reminder <<= 1;
t0         = divisor >> i;
reminder   = reminder | (t0 & 1); // ternary operation

Step 2: Comparison

AVX512 supports unsigned byte comparison, and returns a mask.

Step 3: Conditional operations

This is straightforward use of masked operations.

Implementation

The actual AVX512 implementation is shown below. Unlike SSE code, the inner loop is manually unrolled. Also, there's no explictly use of the ternary logic intrinsic function — but examing the assembly code revelas that a compiler nicely fuses binary operation.

void avx512_long_div_u8(const uint8_t* A, const uint8_t* B, uint8_t* C, size_t n) {
    const __m512i one = _mm512_set1_epi8(1);

    for (size_t i=0; i < n; i += 64) {
        const __m512i dividend = _mm512_loadu_si512((const __m512*)(&A[i]));
        const __m512i divisor  = _mm512_loadu_si512((const __m512*)(&B[i]));

        const __m512i dividend_bit7 = _mm512_and_epi32(_mm512_srli_epi32(dividend, 7), one);
        const __m512i dividend_bit6 = _mm512_and_epi32(_mm512_srli_epi32(dividend, 6), one);
        const __m512i dividend_bit5 = _mm512_and_epi32(_mm512_srli_epi32(dividend, 5), one);
        const __m512i dividend_bit4 = _mm512_and_epi32(_mm512_srli_epi32(dividend, 4), one);
        const __m512i dividend_bit3 = _mm512_and_epi32(_mm512_srli_epi32(dividend, 3), one);
        const __m512i dividend_bit2 = _mm512_and_epi32(_mm512_srli_epi32(dividend, 2), one);
        const __m512i dividend_bit1 = _mm512_and_epi32(_mm512_srli_epi32(dividend, 1), one);
        const __m512i dividend_bit0 = _mm512_and_epi32(_mm512_srli_epi32(dividend, 0), one);

        __m512i quotient = _mm512_set1_epi32(0);
        __m512i reminder = dividend_bit7;

        {
            const __mmask64 ge = _mm512_cmpge_epu8_mask(reminder, divisor);
            reminder = _mm512_mask_sub_epi8(reminder, ge, reminder, divisor);
            quotient = _mm512_mask_add_epi8(quotient, ge, quotient, one);
        }

        reminder = _mm512_add_epi32(reminder, reminder);
        reminder = _mm512_or_epi32(reminder, dividend_bit6);

        {
            const __mmask64 ge = _mm512_cmpge_epu8_mask(reminder, divisor);
            reminder = _mm512_mask_sub_epi8(reminder, ge, reminder, divisor);
            quotient = _mm512_add_epi32(quotient, quotient);
            quotient = _mm512_mask_add_epi8(quotient, ge, quotient, one);
        }

        reminder = _mm512_add_epi32(reminder, reminder);
        reminder = _mm512_or_epi32(reminder, dividend_bit5);

        {
            const __mmask64 ge = _mm512_cmpge_epu8_mask(reminder, divisor);
            reminder = _mm512_mask_sub_epi8(reminder, ge, reminder, divisor);
            quotient = _mm512_add_epi32(quotient, quotient);
            quotient = _mm512_mask_add_epi8(quotient, ge, quotient, one);
        }

        reminder = _mm512_add_epi32(reminder, reminder);
        reminder = _mm512_or_epi32(reminder, dividend_bit4);

        {
            const __mmask64 ge = _mm512_cmpge_epu8_mask(reminder, divisor);
            reminder = _mm512_mask_sub_epi8(reminder, ge, reminder, divisor);
            quotient = _mm512_add_epi32(quotient, quotient);
            quotient = _mm512_mask_add_epi8(quotient, ge, quotient, one);
        }

        reminder = _mm512_add_epi32(reminder, reminder);
        reminder = _mm512_or_epi32(reminder, dividend_bit3);

        {
            const __mmask64 ge = _mm512_cmpge_epu8_mask(reminder, divisor);
            reminder = _mm512_mask_sub_epi8(reminder, ge, reminder, divisor);
            quotient = _mm512_add_epi32(quotient, quotient);
            quotient = _mm512_mask_add_epi8(quotient, ge, quotient, one);
        }

        reminder = _mm512_add_epi32(reminder, reminder);
        reminder = _mm512_or_epi32(reminder, dividend_bit2);

        {
            const __mmask64 ge = _mm512_cmpge_epu8_mask(reminder, divisor);
            reminder = _mm512_mask_sub_epi8(reminder, ge, reminder, divisor);
            quotient = _mm512_add_epi32(quotient, quotient);
            quotient = _mm512_mask_add_epi8(quotient, ge, quotient, one);
        }

        reminder = _mm512_add_epi32(reminder, reminder);
        reminder = _mm512_or_epi32(reminder, dividend_bit1);

        {
            const __mmask64 ge = _mm512_cmpge_epu8_mask(reminder, divisor);
            reminder = _mm512_mask_sub_epi8(reminder, ge, reminder, divisor);
            quotient = _mm512_add_epi32(quotient, quotient);
            quotient = _mm512_mask_add_epi8(quotient, ge, quotient, one);
        }

        reminder = _mm512_add_epi32(reminder, reminder);
        reminder = _mm512_or_epi32(reminder, dividend_bit0);


        {
            const __mmask64 ge = _mm512_cmpge_epu8_mask(reminder, divisor);
            reminder = _mm512_mask_sub_epi8(reminder, ge, reminder, divisor);
            quotient = _mm512_add_epi8(quotient, quotient);
            quotient = _mm512_mask_add_epi8(quotient, ge, quotient, one);
        }

        _mm512_storeu_si512((__m512*)&C[i], quotient);
    }
}