yEnc SSE decode ideas

[Safihre]

I was amazed to find this repo, I have been thinking of some way to do yEnc-decoding (as a Python-C-extension) using SSE instructions but my knowledge of C is just too rudimentary for now.

Do you think think SSE can help compared to regular char-by-char decoding of yEnc body?
How would you go about the decoding-escaping problem? I can imagine finding the escape chars, but how to remove them later on when building the output string?
I tried to grasp your encoding-code, but I think I probably miss the main idea due to the included edge-cases and optimizations.

Thanks!

EDIT: I think I am getting more and more of the code and how you handle the encoding-escaping here: https://github.com/animetosho/node-yencode/blob/master/yencode.cc#L718-L752
I don't completly understand the shuffle operations just yet and how they handle the extra chars, what are shufMixLUT and shufLUT?

[animetosho]

SIMD isn't really designed for text processing tasks like yEnc, so implementation isn't so straight forward unfortunately. Because of this, a scalar (byte by byte) implementation usually isn't so bad, but doing a SIMD implementation is intellectually interesting and works for the epeen factor (as for Nyuu, I intend to integrate PAR2 generation, so reducing CPU usage may help a bit on fast connections).

Having said that, a SIMD implementation of yEnc encoding can usually beat the naive implementation by several factors, due to corner cases that an encoder has to deal with.

I've been thinking about writing up how the algorithm works. Unfortunately the code isn't the easiest to read (I'm a little lazy there, admittedly), but here's a rough diagram showing an overview of the main loop:

Note that the byte shuffle instruction requires a CPU with SSSE3 support (which most people should have these days). If the CPU doesn't have SSSE3 support, the algorithm just switches to doing the escaping using standard non-SIMD methods if special characters are found (the 16-bit mask != 0). Despite this, it's still a bit faster than a pure scalar implementation because most bytes aren't escaped in yEnc, and hence, end up hitting the fast route of: load 16 bytes, +42 to all bytes, check special characters, store to memory.

Line endings are a bit complicated, since they have different rules to the rest of the line (more characters to escape). When the algorithm crosses a line boundary, it needs to 'revert' (back-track) until the last character of the line, process the line boundary, then go back to the main loop. A large portion of the code is there just to deal with this case.

Generating vectors for the shuffle and add operation isn't exactly fast, so we pre-generate these instead and just do a lookup when encoding data. shufLUT is a 256 x 16-byte table for the shuffle vectors, whilst shufMixLUT is the corresponding lookup table for add vectors.

Hope that all makes sense.

---

As for decoding, I've actually thought about it, and have tried a few things. A naive implementation is surprisingly fast, since decoding is somewhat simpler than encoding, though you could still probably beat it by a few factors with SIMD.

Here's my scalar implementation:

static size_t do_decode_scalar(const unsigned char* src, unsigned char* dest, size_t len) {
	unsigned char *p = dest; // destination pointer
	unsigned long i; // input position
	unsigned char c; // input character
	
	for(i = 0; i < len - 1; i++) {
		c = src[i];
		switch(c) {
			case '\n': case '\r': continue;
			case '=':
				i++;
				c = src[i] - 64;
		}
		*p++ = c - 42;
	}
	// do final char; we process this separately to prevent an overflow if the final char is '='
	if(i < len) {
		c = src[i];
		if(c != '\n' && c != '\r' && c != '=') {
			*p++ = c - 42;
		}
	}
	
	return p - dest;
}

I see that in your implementation, you handle two dots after a newline which I don't. yEnc doesn't actually allow such to happen (first dot must be escaped), but I suppose a valid decoder should still deal with it.

A general workflow for a SIMD version may be:

1. load 16 bytes
2. check for special characters, = \r \n similar to the encoding algorithm
3. subtract 42 from all bytes
4. if there's no special characters, simply store the vector to memory
5. otherwise take all matches to =, shift one byte across and put the number 64 in each place. All other elements of this vector should be 0
6. perform a vector subtract (data - vector_partially_filled_with_64)
7. use shuffles to remove occurrences of = \r \n (similar idea to the encoding algorithm, just instead of expanding data, it compacts it)
8. store to memory

I actually have a somewhat working implementation of the above.
Against a valid yEnc encoder this works, however, if you want to be fully spec compliant, you'll need to handle invalid yEnc representations, such as a sequence like ====. A spec compliant decoder must treat that as two characters, however the above algorithm won't, even though no good yEnc encoder should ever create such a sequence. There's also the \n.. sequence mentioned above.

I haven't yet thought of a way to deal with such invalid sequences well, but it may be doable. A compromise may be to detect such cases instead (rather than actually handle them), and if encountered, fallback to scalar processing. As I expect most yEnc implementations to be reasonably valid, it's unlikely the slower scalar fallback will ever be invoked, but remains there to be spec compliant.

Hope that's useful. I may eventually add decoding support to this library. Welcome any ideas.
Otherwise, if you wish to implement it yourself, hope that this gives you some ideas on how.

[Safihre]

That's a great overview, thank you! 👍

What would you do with the case where the = is the last character of the 16 byte block? So the character-to-unescape is actually in the next 16 byte block.

The double-dot thing is unrelated to yEnc but inherent to NNTP, the servers will add this extra dot when transmitting the message. While I initially ignored it as an edge case, it actually happens quite often (once per file almost).

I was experimenting a bit with implementing this yesterday, but I am sort of stuck in the "finally understanding what pointers do and how to use them"-stage.. so this stuff is a bit above my head.
You say you already have a somewhat working implementation of it? That would make me and the SABnzbd users very happy 😃

[animetosho]

What would you do with the case where the = is the last character of the 16 byte block? So the character-to-unescape is actually in the next 16 byte block.

That's not too hard to deal with. Once you have the bit mask indicating the location of = characters:

escape_first_char = mask >> 15;

// on next loop
data = read_next_16_bytes();
// check for special characters
if(escape_first_char)
  data = vector_subtract(data, make_vector(42, 42, 42... 42+64)); // note, first byte is at the end
else
  data = vector_subtract(data, make_vector(42, 42, 42... 42));

// ...or, you could optimize the above four lines with a small LUT based on escape_first_char

While I initially ignored it as an edge case, it actually happens quite often (once per file almost).

That's interesting, because a correctly yEnc encoded message should never have a dot as the first character of a line.
Perhaps these messages were encoded incorrectly?

but I am sort of stuck in the "finally understanding what pointers do and how to use them"-stage

I'm sure you'll get it. It's likely a bit different to what you're used to, but you seem to be a very experienced programmer, so it won't take you long to understand.
Programming in SIMD may be more challenging as it requires you to think a bit differently to how you'd usually write code, and stuff like yEnc can require a little creativity. But it just boils down to yet another programming problem, and use it enough and you should be fine too.

[Safihre]

Perhaps these messages were encoded incorrectly?

No, it's not yEnc et al. It's the NNTP server that has to add a dot to every line that starts with a dot per-NNTP-spec during the transmission, some leftovers from ancient times I think.

[animetosho]

It's the NNTP server that has to add a dot to every line that starts with a dot

But there should be never be a line that starts with a dot, no?

[Safihre]

Why not? It's not a special character in the already encoded data, just a char of which 42 can be subtracted.

[animetosho]

Looks like I made a mistake - had thought that yEnc requires dots to be escaped if it's the first character in a line, but re-reading the spec, it's actually optional. Sorry about that.
So it looks like that will need to be handled by most decoders.

[animetosho]

So I've been thinking about this, and I think that dealing with invalid sequences can be solved. But the double-dot issue looks challenging.

Looking at RFC3977:

When a multi-line block is interpreted, the "dot-stuffing" MUST
be undone; i.e., the recipient MUST ensure that, in any line
beginning with the termination octet followed by octets other
than a CRLF pair, that initial termination octet is disregarded

This seems to define how invalid sequences such as \n.a are handled - the dot at the start of the line needs to be discarded, regardless of what comes after it. I can't tell if the document covers how sequences like a\n.. should be handled, other than saying that it's invalid. Presumably, from the language, a line must be terminated by \r\n, hence no special treatment should be done for a\n.., however \r\n.. should have the first dot removed.
In other words, dots should be removed if preceded by \r\n (and not a valid = before that), or the dot is the first character in the article/yEnc body (since it's implicitly at the beginning of a line).

I had a quick look at Nzbget's code and it doesn't appear to handle lines starting with a dot. Presumably SABnzbd didn't do this for a long time either? All yEnc decoders I've seen, apart from SABYenc don't handle this case (which isn't an issue if they go through some NNTP layer, but I have doubts that typically happens).
So is it really the case that most downloaders don't handle this, or am I missing something?

Interestingly, I haven't yet seen an yEnc encoder that doesn't escape dots which start a line. But there's obviously posts out there that have it.

I'll probably take the approach of stripping out all instances of \r\n., even though this is likely different to all existing implementations. It also seems difficult to do from a SIMD perspective.

This does also make incremental processing a little more difficult, as it may need to know the preceeding two characters to be correct.

[Safihre]

NZBGet does it will receiving the data in the NNTP layer:
https://github.com/nzbget/nzbget/blob/develop/daemon/nntp/ArticleDownloader.cpp#L388-L392
NZBGet can have a worker thread per connection that decodes the stream as it comes in and do the check then, however, due to the Python GIL the overhead of thread-switching in Python is terrible and we cannot do this.
Maybe when we switch to Python 3 and can use async/greenlet/etc approaches, but switching to Python 3 is still a long road for us.

I just checked some test-articles, and it seems that usually less than 1% of all 16-byte blocks contains a dot.
So as a first 'solution' I was thinking of doing the check if there is a dot present in the 16-byte block, then revert back to char-by-char processing for the whole block and also the block before/after it (in case it was at the start or finish of the current block).
It's a bit convoluted, but it would allow still a vast majority to be done via SIMD.
I tried to implement something of the sorts, but so far not much luck.

EDIT: All usenet downloaders must correct for this, 60% of posts I tried have the \r\n.. at least once.

[animetosho]

I see, thanks for pointing that out!

I think a SIMD version should be fast enough to make threading not that needed. I mean, this yEnc library is single threaded and synchronous, as I feel that it's fast enough to not really warrant the need (I'll probably eventually add async support though).

I've committed up a very rough implementation. From my quick testing, it seems to work and handles all edge cases I've tried so far. Still needs work though, including more testing, tidying up, optimizations etc. I've just pushed it up in case you're interested. Unfortunately the algorithm is a bit convoluted, but maybe can be streamlined better.

The algorithm supports incremental processing by supporting 4 possible previous states (preceeding character is a =, \r, \r\n or something else).

Quick speed test of the current code on a 3.8GHz Haswell CPU, using random input data:
Scalar version: ~400MB/s
SIMD version: ~1700MB/s

Once this is tidied up, maybe I can write up something to help others port the code across (though it's mostly copy the functions across, a few defines, and lookup-table generation code).

[Safihre]

Coool! 💯
I will need to take a closer look and dissect it a bit so I understand it well!

[sanderjo]

Wow, very impressive & cool.

I wanted to ask a noob question: is _mm_movemask_epi8() generic Intel SIMD / SSE, or is it Microsoft specific (because most Google hits are to microsoft.com)? ... But I can answer that question myself:

$ cat /usr/lib/gcc/x86_64-linux-gnu/6/include/emmintrin.h | grep _mm_or_si128
_mm_or_si128 (__m128i __A, __m128i __B)

So: also on Linux, so generic Intel SIMD/SSE. 👍

[animetosho]

The Intel Instrinsics Guide (obviously lacks AMD extensions) is a handy reference. The movemask instruction is one useful instruction SSE has over ARM NEON.

I just realized a mistake: I've been treating =\r\n as a non-newline sequence, but thinking about it, this is incorrect because the NNTP layer doesn't care about yEnc's escaping semantics. So a sequence like =\r\n. should have its dot removed (NNTP protocol), then yEnc kicks in and unescapes the \r, so it should be converted to \xA3 instead of \xA3.. I'll need to fix that up.