Decoding a format where we first have 16 k-bit values (for k=1,2,4,8), and then have up to 16 8-bit values for "outliers" which are selected based on whether a k-bit value was equal to (1<<k)-1

decodebytes.cpp

static unsigned char kDecodeBytesGroupShuffle[256][8];
static unsigned char kDecodeBytesGroupCount[256];
static bool gDecodeBytesGroupInitialized;

static void decodeBytesGroupBuildTables()
{
	if (gDecodeBytesGroupInitialized)
		return;

	for (int mask = 0; mask < 256; ++mask)
	{
		unsigned char shuffle[8];
		memset(shuffle, 0x80, 8);

		unsigned char count = 0;

		for (int i = 0; i < 8; ++i)
			if (mask & (1 << (7 - i)))
			{
				shuffle[i] = count;
				count++;
			}

		memcpy(kDecodeBytesGroupShuffle[mask], shuffle, 8);
		kDecodeBytesGroupCount[mask] = count;
	}

	gDecodeBytesGroupInitialized = true;
}

static __m128i decodeShuffleMask(unsigned char mask0, unsigned char mask1)
{
	__m128i sm0 = _mm_loadl_epi64(reinterpret_cast<const __m128i*>(&kDecodeBytesGroupShuffle[mask0]));
	__m128i sm1 = _mm_loadl_epi64(reinterpret_cast<const __m128i*>(&kDecodeBytesGroupShuffle[mask1]));
	__m128i sm1off = _mm_set1_epi8(kDecodeBytesGroupCount[mask0]);

	__m128i sm1r = _mm_add_epi8(sm1, sm1off);

	return _mm_unpacklo_epi64(sm0, sm1r);
}

inline const unsigned char* decodeBytesGroup(const unsigned char* data, unsigned char* buffer, int bitslog2)
{
	switch (bitslog2)
	{
	case 0:
	{
		unsigned char mask0 = data[0];
		unsigned char mask1 = data[1];

		__m128i rest = _mm_loadu_si128(reinterpret_cast<const __m128i*>(data + 2));

		__m128i shuf = decodeShuffleMask(mask0, mask1);

		// note: this will set unused entries to 0 since shuf mask will have high bits set to 1
		__m128i result = _mm_shuffle_epi8(rest, shuf);

		_mm_storeu_si128(reinterpret_cast<__m128i*>(buffer), result);

		return data + 2 + kDecodeBytesGroupCount[mask0] + kDecodeBytesGroupCount[mask1];
	}

	case 1:
	{
		__m128i sel2 = _mm_cvtsi32_si128(*reinterpret_cast<const int*>(data));
		__m128i rest = _mm_loadu_si128(reinterpret_cast<const __m128i*>(data + 4));

		__m128i sel22 = _mm_and_si128(_mm_set1_epi8(15), _mm_unpacklo_epi8(_mm_srli_epi16(sel2, 4), sel2));
		__m128i sel2222 = _mm_and_si128(_mm_set1_epi8(3), _mm_unpacklo_epi8(_mm_srli_epi16(sel22, 2), sel22));

		__m128i mask = _mm_cmpeq_epi8(sel2222, _mm_set1_epi8(3));
		int mask16 = _mm_movemask_epi8(_mm_shuffle_epi8(mask, _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)));
		unsigned char mask0 = (unsigned char)(mask16 >> 8);
		unsigned char mask1 = (unsigned char)(mask16 & 255);

		__m128i shuf = decodeShuffleMask(mask0, mask1);

		__m128i result = _mm_or_si128(_mm_shuffle_epi8(rest, shuf), _mm_andnot_si128(mask, sel2222));

		_mm_storeu_si128(reinterpret_cast<__m128i*>(buffer), result);

		return data + 4 + kDecodeBytesGroupCount[mask0] + kDecodeBytesGroupCount[mask1];
	}

	case 2:
	{
		__m128i sel4 = _mm_loadl_epi64(reinterpret_cast<const __m128i*>(data));
		__m128i rest = _mm_loadu_si128(reinterpret_cast<const __m128i*>(data + 8));

		__m128i sel44 = _mm_and_si128(_mm_set1_epi8(15), _mm_unpacklo_epi8(_mm_srli_epi16(sel4, 4), sel4));

		__m128i mask = _mm_cmpeq_epi8(sel44, _mm_set1_epi8(15));
		int mask16 = _mm_movemask_epi8(_mm_shuffle_epi8(mask, _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)));
		unsigned char mask0 = (unsigned char)(mask16 >> 8);
		unsigned char mask1 = (unsigned char)(mask16 & 255);

		__m128i shuf = decodeShuffleMask(mask0, mask1);

		__m128i result = _mm_or_si128(_mm_shuffle_epi8(rest, shuf), _mm_andnot_si128(mask, sel44));

		_mm_storeu_si128(reinterpret_cast<__m128i*>(buffer), result);

		return data + 8 + kDecodeBytesGroupCount[mask0] + kDecodeBytesGroupCount[mask1];
	}

	case 3:
	{
		__m128i rest = _mm_loadu_si128(reinterpret_cast<const __m128i*>(data));

		__m128i result = rest;

		_mm_storeu_si128(reinterpret_cast<__m128i*>(buffer), result);

		return data + 16;
	}

	default:
		assert(!"Unexpected bit length"); // This can never happen since bitslog2 is a 2-bit value
		return data;
	}
}

static const unsigned char dbgxShuffles[4][16] =
{
	{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, },
	{ 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, },
	{ 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, },
	{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, },
};

static const unsigned char dbgxBitMasks[4][16] =
{
	{ 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01, 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01, },
	{ 0xc0, 0x30, 0x0c, 0x03, 0xc0, 0x30, 0x0c, 0x03, 0xc0, 0x30, 0x0c, 0x03, 0xc0, 0x30, 0x0c, 0x03, },
	{ 0xf0, 0x0f, 0xf0, 0x0f, 0xf0, 0x0f, 0xf0, 0x0f, 0xf0, 0x0f, 0xf0, 0x0f, 0xf0, 0x0f, 0xf0, 0x0f, },
	{ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, },
};


static const unsigned short dbgxShiftMul[4][8] =
{
	{ 2, 4, 8, 16, 32, 64, 128, 256 },
	{ 4, 16, 64, 256, 4, 16, 64, 256 },
	{ 16, 256, 16, 256, 16, 256, 16, 256 },
	{ 256, 256, 256, 256, 256, 256, 256, 256, },
};

inline const unsigned char* decodeBytesGroupX(const unsigned char* data, unsigned char* buffer, int bitslog2)
{
	int bits = 1 << bitslog2;

	// load selection bits and remaining data; reads up to 32b
	__m128i selr = _mm_loadu_si128(reinterpret_cast<const __m128i*>(data));
	__m128i rest = _mm_loadu_si128(reinterpret_cast<const __m128i*>(data + bits * 2));

	// move bytes with requisite bits in the right place and mask the other bits out
	__m128i selshuf = _mm_loadu_si128(reinterpret_cast<const __m128i*>(dbgxShuffles[bitslog2]));
	__m128i selmask = _mm_loadu_si128(reinterpret_cast<const __m128i*>(dbgxBitMasks[bitslog2]));
	__m128i selb = _mm_and_si128(_mm_shuffle_epi8(selr, selshuf), selmask);

	// helper for computations below
	__m128i selb4 = _mm_srli_epi16(selb, 4);

	// if SSE had 16-wide variable byte shifts, we'd be done... instead we need to play tricks
	__m128i selrr[4];

	// for bitslog2=0, we need to shift by 0,1,2,3,4,5,6,7 bits - this is very expensive
	// instead, we'll compare selb with selmask
	selrr[0] = _mm_and_si128(_mm_cmpeq_epi8(selb, selmask), _mm_set1_epi8(1));

	// for bitslog2=1, we need to shift by 0,2,4,6 bits
	// sse doesn't have byte shifts so this is REALLY painful
	// our input 4b value is 0xc0_30_0c_03; we'll first shift it to 0x0c_03_0c_03 using a 4b shift
	// shifting 16-bit parts by 4 gives us 0x0c_03_00_c0, which we can merge with source by ORing and then &f
	// after this we get 0x0c_03_0c_03 mask, and we need 0x03_03_03_03; this is a shift by 2
	// shifting 16-bit parts by 2 gives us 0x33_00_33_00, which we can merge with source by ORing and then &3
	__m128i selb2a = _mm_and_si128(_mm_or_si128(selb, selb4), _mm_set1_epi8(15)); // todo: the "and" might be sharable with code below
	__m128i selb2b = _mm_srli_epi16(selb2a, 2);

	selrr[1] = _mm_and_si128(_mm_or_si128(selb2a, selb2b), _mm_set1_epi8(3));

	// for bitslog2=2, we need to shift by 0,4 bits
	// sse doesn't have byte shifts (what gives?); however, selb is masked using 0xf0_0f pattern
	// shifting 16-bit parts by 4 essentially gives us 0xff_00 mask; can OR this with selb and then &f
	selrr[2] = _mm_and_si128(_mm_or_si128(selb4, selb), _mm_set1_epi8(15));

	// for bitslog2=3, we don't need to shift
	selrr[3] = selb;

	__m128i sel = selrr[bitslog2];

	__m128i mask = _mm_cmpeq_epi8(sel, _mm_set1_epi8((1 << bits) - 1));

	// kill the mask for bitslog2=3 so that we don't go and read rest for byte=255
	__m128i maskf = _mm_cmpeq_epi8(selmask, _mm_set1_epi8(-1));
	mask = _mm_andnot_si128(maskf, mask);

	int mask16 = _mm_movemask_epi8(_mm_shuffle_epi8(mask, _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)));
	unsigned char mask0 = (unsigned char)(mask16 >> 8);
	unsigned char mask1 = (unsigned char)(mask16 & 255);

	__m128i shuf = decodeShuffleMask(mask0, mask1);

	__m128i result = _mm_or_si128(_mm_shuffle_epi8(rest, shuf), _mm_andnot_si128(mask, sel));

	_mm_storeu_si128(reinterpret_cast<__m128i*>(buffer), result);

	unsigned char refb[16];
	assert(decodeBytesGroup(data, refb, bitslog2) == data + bits * 2 + kDecodeBytesGroupCount[mask0] + kDecodeBytesGroupCount[mask1]);
	assert(memcmp(refb, buffer, 16) == 0);
	(void)refb;

	return data + bits * 2 + kDecodeBytesGroupCount[mask0] + kDecodeBytesGroupCount[mask1];
}

inline const unsigned char* decodeBytesGroupY(const unsigned char* data, unsigned char* buffer, int bitslog2)
{
	int bits = 1 << bitslog2;

	// load selection bits and remaining data; reads up to 32b
	__m128i selr = _mm_loadu_si128(reinterpret_cast<const __m128i*>(data));
	__m128i rest = _mm_loadu_si128(reinterpret_cast<const __m128i*>(data + bits * 2));

	// move bytes with requisite bits in the right place and mask the other bits out
	__m128i selshuf = _mm_loadu_si128(reinterpret_cast<const __m128i*>(dbgxShuffles[bitslog2]));
	__m128i selmask = _mm_loadu_si128(reinterpret_cast<const __m128i*>(dbgxBitMasks[bitslog2]));
	__m128i selb = _mm_and_si128(_mm_shuffle_epi8(selr, selshuf), selmask);

	// split selb into two 16-bit parts, moving each byte to the high byte (0xXX00)
	__m128i selb0 = _mm_unpacklo_epi8(_mm_setzero_si128(), selb);
	__m128i selb1 = _mm_unpackhi_epi8(_mm_setzero_si128(), selb);

	// multiply each part by shift factor - this is emulating 8-bit right shift by multiplying by the "inverse" and taking the high 16-bit part of the result
	__m128i shiftmul = _mm_loadu_si128(reinterpret_cast<const __m128i*>(dbgxShiftMul[bitslog2]));
	__m128i selb0m = _mm_mulhi_epu16(selb0, shiftmul);
	__m128i selb1m = _mm_mulhi_epu16(selb1, shiftmul);

	// combine parts back
	__m128i sel = _mm_packus_epi16(selb0m, selb1m);

	__m128i mask = _mm_cmpeq_epi8(sel, _mm_set1_epi8((1 << bits) - 1));

	// kill the mask for bitslog2=3 so that we don't go and read rest for byte=255
	__m128i maskf = _mm_cmpeq_epi8(selmask, _mm_set1_epi8(-1));
	mask = _mm_andnot_si128(maskf, mask);

	int mask16 = _mm_movemask_epi8(_mm_shuffle_epi8(mask, _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)));
	unsigned char mask0 = (unsigned char)(mask16 >> 8);
	unsigned char mask1 = (unsigned char)(mask16 & 255);

	__m128i shuf = decodeShuffleMask(mask0, mask1);

	__m128i result = _mm_or_si128(_mm_shuffle_epi8(rest, shuf), _mm_andnot_si128(mask, sel));

	_mm_storeu_si128(reinterpret_cast<__m128i*>(buffer), result);

	unsigned char refb[16];
	assert(decodeBytesGroup(data, refb, bitslog2) == data + bits * 2 + kDecodeBytesGroupCount[mask0] + kDecodeBytesGroupCount[mask1]);
	assert(memcmp(refb, buffer, 16) == 0);
	(void)refb;

	return data + bits * 2 + kDecodeBytesGroupCount[mask0] + kDecodeBytesGroupCount[mask1];
}