Re: Byte Addressability And Beyond

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:

Terje Mathisen wrote:

Anton Ertl wrote:

This approach can also be SIMDified, converting regbits/32 code points
in one representation to the same number of code points in the other
representation plus a length of the UTF-8 representation.
>
The disadvantage of this approach exists particularly for
UTF-8->UTF-32: this is a very sequential approach full of dependences:
each use of the conversion instruction is followed by a dependent load
of the next input fragment, and the next use of the conversion
instruction depends on that load.

 
Rather the opposite:
 
UTF8->UTF32 looks a _lot_ like an easier example of a byte-oriented
variable length (x86?) instruction decoder, but with the big
simplification that the first byte directly tells you how long the
sequence is.
 
Doing a SIMD version corresponds to a superscalar x86 in that the
decoder needs to grab a variable number of bytes for each instruction,
starting the next immediately after.

>
Even better (compared to a superscalar x86 instruction decoder), _every_
byte uses the top two bits to tell you if this is 7-bit ascii, the start
of a UTF-8 encoded code point, or a follow-on byte inside a UTF-8 code
point.
>
This means that each decoder can work alone, without having to wait for
the length decoding of the previous code point ("instruction") before
deciding to discard or pass on the results it got from starting where it
did.
>
It seems like it would be very feasible to have (say) 8 parallel
decoders starting at every corresponding byte offset, and return a SIMD
register with 2-8 32-bit decoded code points, right?

Sounds quite reasonable (and would be like what Mitch describes for his
My 66000 decoders).  Apart from filling the buffers, it would also need
to return the number of bytes consumed and the number of UTF-32
characters generated, plus a possible error indication.

Looking at what IBM did, the CU14 instruction is memory-to-memory
and they use both the length and the address of both the source
and destination data in register pairs.  The number of characters
to process are then decremented according to what has been processed
(and there might be a CPU-defined limit).  They also appear to have
optional error checking only.

Complicated...