animetosho
commented
7 years ago 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:
- load 16 bytes
- check for special characters,
=\r\nsimilar to the encoding algorithm - subtract 42 from all bytes
- if there's no special characters, simply store the vector to memory
- 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 - perform a vector subtract (data - vector_partially_filled_with_64)
- use shuffles to remove occurrences of
=\r\n(similar idea to the encoding algorithm, just instead of expanding data, it compacts it) - 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
sanderjo
hugbug
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
shufMixLUTandshufLUT?